# Quantized Training of Gradient Boosting
Decision Trees

Yu Shi1 Guolin Ke211footnotemark: 1 ,
Zhuoming Chen333footnotemark: 3 Shuxin Zheng1 Tie-Yan Liu1
1Microsoft Research 2DP Technology 3Tsinghua University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS>{shuxin.zheng<EMAIL_ADDRESS>Corresponding authors.Work primarily done at Microsoft Research.Work done
during internship at Microsoft Research.

###### Abstract

Recent years have witnessed significant success in Gradient Boosting Decision
Trees (GBDT) for a wide range of machine learning applications. Generally, a
consensus about GBDT’s training algorithms is gradients and statistics are
computed based on high-precision floating points. In this paper, we
investigate an essentially important question which has been largely ignored
by the previous literature - _how many bits are needed for representing
gradients in training GBDT?_ To solve this mystery, we propose to quantize all
the high-precision gradients in a very simple yet effective way in the GBDT’s
training algorithm. Surprisingly, both our theoretical analysis and empirical
studies show that the necessary precisions of gradients without hurting any
performance can be quite low, e.g., 2 or 3 bits. With low-precision gradients,
most arithmetic operations in GBDT training can be replaced by integer
operations of 8, 16, or 32 bits. Promisingly, these findings may pave the way
for much more efficient training of GBDT from several aspects: (1) speeding up
the computation of gradient statistics in histograms; (2) compressing the
communication cost of high-precision statistical information during
distributed training; (3) the inspiration of utilization and development of
hardware architectures which well support low-precision computation for GBDT
training. Benchmarked on CPUs, GPUs, and distributed clusters, we observe up
to 2$\times$ speedup of our simple quantization strategy compared with SOTA
GBDT systems on extensive datasets, demonstrating the effectiveness and
potential of the low-precision training of GBDT. The code will be released to
the official repository of LightGBM.444https://github.com/Microsoft/LightGBM

##  1 Introduction

Gradient Boosting Decision Trees (GBDT) is a powerful machine learning
algorithm. Despite the success of deep learning in recent years, GBDT is one
of the best off-the-shelf choices of machine learning algorithms in many real-
world tasks, including online advertising [33], search ranking [26, 14],
finance prediction [29], etc. Along with carefully designed tools, including
XGBoost [5], LightGBM [17], and CatBoost [24], GBDT has shown outstanding
performance in various data science competitions [36] and industrial
applications [32, 9, 28, 23].

Despite the success of GBDT, we found there is room for GBDT algorithms to
fully exploit modern computation resources. First, the training of GBDT
requires arithmetic operations of high-precision FP (Floating Point) numbers,
which hinders the usage of low-precision computation resources. Low-precision
training has become a standard technique to significantly accelerate the
training of neural networks [20]. The design of new processors for machine
learning tends to encourage high throughput for low-precision computation.
This results in a gap between GBDT training algorithms and the hardware
architectures. Second, distributed training of GBDT is required for large
datasets. The communication cost for distributed training, however, is huge
due to high-precision statistical information passing among machines. The cost
is especially high with a large number of features in the dataset, which hurts
the scalability of GBDT in distributed systems.

In this paper, we propose a low-precision training algorithm for GBDT, based
on stochastic gradient quantization. The main computation cost of training
GBDT is the arithmetic operations over gradients. Before training each
decision tree, we quantize the gradients into very low-precision (e.g., 2-bit
or 3-bit) integers. Thus, we replace most of the FP arithmetic operations with
integer arithmetic operations, which reduces computation time. In addition,
low-bitwidth gradients result in a smaller memory footprint and better cache
utilization. Techniques are proposed to preserve the accuracy of the model,
including stochastic rounding in gradient quantization, and leaf-value
refitting with original gradient values. We show both empirically and
theoretically that quantized training of GBDT with low-bitwidth gradients is
almost lossless in terms of model accuracy. Thus, we empower GBDT to utilize
low-precision computation resources.

Distributed training of GBDT relies on the synchronization of gradient
statistics. The gradient statistics are summarized into a histogram for each
feature. With quantized gradients, only integer histogram values are needed in
our algorithm. The communication among hosts or GPUs becomes sending and
reducing of these integer values. And the size of these histograms is at least
half of the original histograms with FP values. So quantized training of GBDT
has an advantage in communication cost by nature and improves the scalability
of GBDT on distributed systems.

We implement our system on both CPUs and GPUs. The results show that our
methods accelerate the training of GBDT in various settings, including a
single process on CPUs, a single process on a GPU, and distributed training
over CPUs. This validates that our algorithm is general for different types of
computation resources. Besides acceleration on existing hardware
architectures, our algorithm also lay the foundation for GBDT to exploit new
hardware architectures with more flexible support for low-precision operations
in the future. Based on LightGBM, we implement a quantized GBDT training
system. With quantized training, we achieve up to 2$\times$ speedup compared
with SOTA GBDT tools. Experiments also show that quantized GBDT training
scales better in distributed systems.

Our algorithm also verifies huge redundancy in the information contained by
gradient values in GBDT. Moreover, we reveal both theoretically and
empirically how such redundancy can be properly reduced, to keep good model
performance and training efficiency. And we show how to implement the
quantized training of GBDT efficiently across different computation resources.
We believe that these interesting findings will inspire new understandings and
improvements for GBDT in the future.

##  2 Related Work

Trials to use low-precision training in deep neural networks (NN) are
abundant. Using low bitwidth numbers in NN training can reduce memory access
and accelerate training [13, 15, 35, 20, 10]. In addition to efficiency, the
effectiveness of quantized NN training has also been discussed [7, 18, 4].
Besides quantization during the forward and backward calculations,
quantization of gradients has also been applied in distributed training of
neural networks [30] to reduce communication cost. However, the possibility of
low-precision training for GBDT is rarely discussed in existing literature.
RatBoost [22] is a boosting algorithm based on re-weighting samples. In
RatBoost [22], quantization is applied to the weights of training samples
during boosting, while the application of quantization in GBDT is not
discussed. Recently gradient quantization is applied in federated training of
GBDT [6] to transform FP gradients into large integers (e.g., 53-bit integers)
for the sake of encryption. But quantization towards a very small number of
bits is not explored. Accelerating GBDT training with quantized gradients was
exploited by BitBoost [8]. And BitBoost shows empirically that it is possible
to achieve comparable accuracy with quantized gradients of low bitwidth.
However, BitBoost quantizes gradients in a deterministic way. In this paper,
we provide a theoretical guarantee of quantized training based on stochastic
quantization. And we show that stochastic quantization is crucial to preserve
good model accuracy. Besides, BitBoost focuses on accelerating GBDT with bit
operations on a single CPU core, and the implementation is a single-thread
version. In this paper, we discuss important techniques in system
implementation that enable significant acceleration across different
computation platforms, including multi-core CPUs, GPUs, and distributed
clusters.

Distributed training of GBDT is necessary for large-scale datasets. Training
data are partitioned either by rows (data samples) or by columns (features)
across different machines. We call the former strategy data-distributed
training and the latter feature-distributed training. The communication cost
for feature-distributed training grows linearly with the number of training
samples [1, 19]. On the other hand, the communication cost for data-
distributed training is proportional to the number of features [1, 19]. The
two strategies can be combined with each machine getting only part of the
features and samples [11]. The communication complexity of these strategies is
analyzed in detail [31], with empirical studies [11]. Since training of GBDT
requires summarizing the gradient statistics across the dataset into a
histogram for each feature, the cost for data-distributed training is reduced
with the more concise histogram information [5]. Thus, data-distributed
training is more favorable with large-scale datasets. With many features,
feature-distributed or the combination of two strategies can be faster [11].

Based on these distributed training strategies, some efforts have been made to
reduce the communication cost. Meng et al [19] proposed Parallel-Voting Tree
(PV-Tree) to further reduce the cost of data-distributed training. However,
PV-Tree guarantees good performance only when different parts of the
partitioned dataset have similar statistical distributions, which can require
expensive random shuffling over the whole large dataset. Moreover, quantized
training can be applied along with PV-Tree. This is because PV-Tree reduces
communication cost by reducing the number of features to synchronize the
statistics in the histograms. Since quantized training can reduce the size of
histograms, it brings a general benefit for both PV-Tree and ordinary data-
distributed training. DimBoost [16] keeps the number of communicated
histograms unchanged but reduces the size of each histogram by compressing the
histograms instead. Histograms represented by floating-point numbers in
DimBoost are compressed into low-precision values (8-bit integers) before
sending, and decoding into high-precision values. Note that in DimBoost, only
the communication message for distributed training is in low-precision and the
compression is lossy. In addition, reduction of the histograms still requires
floating-point additions. In comparison, we quantized most parts of the
training process of GBDT with low-precision integers, and only need to
maintain histograms with integer values.

In this paper, we compare our algorithm with SOTA efficient implementations of
GBDT, including XGBoost [5], LightGBM [17], and CatBoost [24]. They support
training on CPUs, GPUs [34], and distributed training. However, none of these
support low-precision training. We show that with quantized gradients, GBDT
can be trained much faster compared with these SOTA tools in both single
process and distributed settings, on both CPUs and GPUs. We implement
quantized training based on LightGBM. But our method is general and can be
adopted by all these tools.

##  3 Preliminaries of GBDT Algorithms

Gradient Boosting Decision Trees (GBDT) is an ensemble learning algorithm that
trains decision trees as base components iteratively. In each iteration, for
each training sample, the gradient (first-order derivative) and hessian
(second-order derivative) of the loss function w.r.t. the current prediction
value is calculated. Then a decision tree is trained to fit the negatives of
gradients. Formally, in iteration $k+1$, let $\hat{y}_{i}^{k}$ be the current
prediction value of sample $i$. And $g_{i}$ and $h_{i}$ are the gradient and
hessian of loss function $l$:

$\small g_{i}=\frac{\partial
l(\hat{y}_{i}^{k},y_{i})}{\partial\hat{y}_{i}^{k}},h_{i}=\frac{\partial^{2}l(\hat{y}_{i}^{k},y_{i})}{\left(\partial\hat{y}_{i}^{k}\right)^{2}}$
(1)

For a leaf $s$, denote $I_{s}$ as the set of data indices in the leaf. Let
$G_{s}=\sum_{i\in I_{s}}g_{i}$ and $H_{s}=\sum_{i\in I_{s}}h_{i}$ be the
summations of $g_{i}$’s and $h_{i}$’s over samples in leaf $s$. With the tree
structure being fixed in iteration $k+1$, the training loss can be
approximated by second-order Taylor polynomial:

$\footnotesize\begin{split}\mathcal{L}_{k+1}\approx\mathcal{C}+\sum_{s}\left(\frac{1}{2}H_{s}w_{s}^{2}+G_{s}w_{s}\right)\\\
\end{split}$ (2)

where $\mathcal{C}$ is a constant and $w_{s}$ is the prediction value of leaf
$s$. By minimizing the approximated loss, we obtain the optimal value for leaf
$s$ and the minimal loss contributed by data in $I_{s}$:

$\small
w_{s}^{*}=-\frac{G_{s}}{H_{s}},\quad\mathcal{L}_{s}^{*}=-\frac{1}{2}\cdot\frac{G_{s}^{2}}{H_{s}}.$
(3)

Finding the optimal tree structure is difficult. Thus the tree is trained by
greedily and iteratively splitting a leaf into two child leaves, starting from
a single root leaf. When splitting leaf $s$ into two children $s_{1}$ and
$s_{2}$ in tree $T_{k+1}$, we can calculate the reduction in the approximated
loss

$\small\begin{split}\Delta\mathcal{L}_{s\to
s_{1},s_{2}}&=\mathcal{L}_{s}^{*}-\mathcal{L}_{s_{1}}^{*}-\mathcal{L}_{s_{2}}^{*}=\frac{G_{s_{1}}^{2}}{2H_{s_{1}}}+\frac{G_{s_{2}}^{2}}{2H_{s_{2}}}-\frac{G_{s}^{2}}{2H_{s}}.\end{split}$
(4)

To find the best split condition for leaf $s$, all split candidates of all
features should be enumerated and the one with the largest loss reduction is
chosen.

To accelerate the best split-finding process, an algorithm based on histograms
is used by most state-of-the-art GBDT toolkits. The basic idea of histogram
based GBDT is to divide the values of a feature into bins. Each bin
corresponds to a range of feature values. Then we construct histograms with
the bins such that each bin records the summation of gradients and hessians of
data in that bin. Only the boundaries of the bins (ranges) will be considered
as candidates of split thresholds. Algorithm 1 describes the process of
histogram construction. Bin data matrix $\mathbf{data}$ records for each
feature and sample the index of the bin in the histogram, i.e., which range
the feature value falls in. The $g_{i}$’s and $h_{i}$’s are accumulated in the
corresponding bins in histograms of the features.

Algorithm 1 Histogram Construction for Leaf $s$

Input: Gradients $\left\\{g_{1},...,g_{N}\right\\}$, Hessians
$\left\\{h_{1},...,h_{N}\right\\}$

Input: Bin data $\mathbf{data}[N][J]$, Data indices in leaf $s$ denoted by
$I_{s}$

Output: Histogram $\mathbf{hist}_{s}$

for $i\in I_{s},j\in\left\\{1...J\right\\}$ do

$bin\leftarrow\mathbf{data}[i][j]$

$\mathbf{hist}_{s}[j][bin].g\leftarrow\mathbf{hist}_{s}[j][bin].g+g_{i}$

$\mathbf{hist}_{s}[j][bin].h\leftarrow\mathbf{hist}_{s}[j][bin].h+h_{i}$

end for

Since the split criterion (4) only depends on the summation of gradient
statistics, we can easily obtain the optimal split threshold by iterating over
bins in the histogram. Traditionally 32-bit floating point numbers are used
for $g_{i}$’s and $h_{i}$’s. And the accumulations in the histograms usually
require 32-bit or 64-bit FP numbers. In the next section, we show how to
quantizes $g_{i}$’s and $h_{i}$’s into low-bitwidth integers so that most of
the arithmetic operations can be replaced with integer operations with a fewer
number of bits, which substantially saves computational cost.

##  4 Quantized Training of GBDT

We describe our quantized training algorithm for GBDT. First, we show the
overall framework. Then we identify the two critical techniques to preserve
the accuracy of quantized training, including stochastic gradient quantization
and leaf-value refitting.

###  4.1 Framework for Quantized Training

We first quantize $g_{i}$ and $h_{i}$ into low-bitwidth integers
$\widetilde{g}_{i}$ and $\widetilde{h}_{i}$. We divide the ranges of $g_{i}$’s
and $h_{i}$’s of all training samples into intervals of equal length. To use
$B$-bit ($B\geq 2$) integer gradients, we use $2^{B}-2$ intervals. Each end of
the intervals corresponds to an integer value, resulting in $2^{B}-1$ integer
values in total. Since the first-order derivatives $g_{i}$’s can take both
positive and negative values, half of the intervals will be allocated for the
negative values, and the other half for the positive values. For the second-
order derivatives $h_{i}$’s, almost all commonly used loss functions of GBDT
have non-negative values. We assume that $h_{i}\geq 0$ in subsequent
discussions. Thus the interval lengths are

$\small\delta_{g}=\frac{\max_{i\in[N]}\left|g_{i}\right|}{2^{B-1}-1},\quad\delta_{h}=\frac{\max_{i\in[N]}h_{i}}{2^{B}-2}$
(5)

for $g_{i}$’s and $h_{i}$’s, respectively. Then we can calculate the low-
bitwidth gradients

$\small\widetilde{g}_{i}=\mathit{Round}\left(\frac{g_{i}}{\delta_{g}}\right),\quad\widetilde{h}_{i}=\mathit{Round}\left(\frac{h_{i}}{\delta_{h}}\right).$
(6)

The function $\mathit{Round}$ rounds a floating point number into an integer
number. Note that in the case where $h_{i}$’s are constant, there’s no need to
quantize $h_{i}$. We left the detailed rounding strategy in Section 4.2. We
replace $g_{i}$’s and $h_{i}$’s in Algorithm 1 with $\widetilde{g}_{i}$’s and
$\widetilde{h}_{i}$’s. Then addition operations of the original gradients can
be directly replaced by integer additions. Concretely, the statistics $g$ and
$h$ in the histogram bins will become integers. Thus accumulating gradients
into histogram bins in Algorithm 1 only requires integer additions. In
equation (4), $G_{s_{1}}$, $H_{s_{1}}$, $G_{s_{2}}$ and $H_{s_{2}}$ will
replaced by their integer counterparts $\widetilde{G}_{s_{1}}$,
$\widetilde{H}_{s_{1}}$, $\widetilde{G}_{s_{2}}$, and $\widetilde{H}_{s_{2}}$.
We found that 2 to 4 bits for quantized gradients are enough for good
accuracy. As we will discuss in Section 6.1 and 7.4.3, in most cases, 16-bit
integers will be enough to accumulate such low-bitwidth gradients in
histograms. Thus, most of the operations are done with low-bitwidth integers.
We only need floating point operations when calculating the original
gradients, hessians and the split gain. Specifically, the split gain is
estimated as

$\small\Delta\widetilde{\mathcal{L}}_{s\to
s_{1},s_{2}}=\frac{\left(\widetilde{G}_{s_{1}}\delta_{g}\right)^{2}}{2\widetilde{H}_{s_{1}}\delta_{h}}+\frac{\left(\widetilde{G}_{s_{2}}\delta_{g}\right)^{2}}{2\widetilde{H}_{s_{2}}\delta_{h}}-\frac{\left(\widetilde{G}_{s}\delta_{g}\right)^{2}}{2\widetilde{H}_{s}\delta_{h}},$
(7)

where the scale of the gradient statistics is recovered by multiplying
$\delta_{g}$ and $\delta_{h}$. Figure 1 summarizes the workflow for quantized
GBDT training.

Figure 1: Workflow of the quantized GBDT training.

###  4.2 Rounding Strategies and Leaf-Value Refitting

We find that the $\mathit{Round}$ strategy in equation (6) has a significant
impact on the accuracy of the quantized training algorithm. Rounding to the
nearest integer number seems to be a reasonable choice. However, we found the
accuracy drops severely with this strategy, especially with a small number of
gradient bits. Instead, we adopt a stochastic rounding strategy.
$\widetilde{g}_{i}$ randomly takes values $\lfloor g_{i}/\delta_{g}\rfloor$ or
$\lceil g_{i}/\delta_{g}\rceil$ such that
$\mathbb{E}{\left[\widetilde{g}_{i}\right]}=g_{i}/\delta_{g}$. The formal
definitions of the two rounding strategies are

$\small\mathrm{RN}\left(x\right)=\left\\{\begin{split}\lfloor x\rfloor,\quad
x<\lfloor x\rfloor+\frac{1}{2}\\\ \lceil x\rceil,\quad x\geq\lfloor
x\rfloor+\frac{1}{2}\end{split}\right.,\quad\mathrm{SR}\left(x\right)=\left\\{\begin{split}\lfloor
x\rfloor,\quad\mathrm{w.p.}\quad{\lceil x\rceil-x}\\\ \lceil
x\rceil,\quad\mathrm{w.p.}\quad{x-\lfloor x\rfloor}\end{split}\right.$ (8)

where we use $\mathrm{RN}$ for round-to-nearest and $\mathrm{SR}$ for
stochastic rounding. The key insight is that the split gain is calculated with
the summation of gradients. And stochastic rounding would provide an unbiased
estimation for the summations, i.e. $\mathbb{E}[\widetilde{G}\delta_{g}]=G$,
and $\mathbb{E}[\widetilde{H}\delta_{h}]=H$ in equation (7). The importance of
stochastic rounding is also recognized in other scenarios for quantization,
including NN quantization training [13] and histogram compression in DimBoost
[16]. With stochastic rounding, we provide a theorem in Section 5 which
ensures that the error in split gain estimation caused by quantized gradients
is bounded by a small value with high probability.

With quantized gradients, the optimal leaf value in equation (3) becomes
$\widetilde{w}_{s}^{*}=-\frac{\widetilde{G}_{s}\delta_{g}}{\widetilde{H}_{s}\delta_{h}}$.
In most cases, $\widetilde{w}_{s}^{*}$ is enough for good results. But we
found that for some loss functions, especially ranking objectives, refitting
the leaf values with the original gradients after the tree has stopped growing
is useful to improve the accuracy of quantized training. BitBoost [8] also
recalculates leaf values with real gradients after tree growing. The
difference is that here we consider hessians in split gain (7) during tree
growth, but BitBoost treats hessians as constants during tree growth and uses
true hessians only when refitting the leaf values. It is cheap to calculate
$w_{s}^{*}$ in equation (3) given a fixed tree structure since only a single
pass over $g_{i}$’s and $h_{i}$’s is needed to sum them up into different
leaves.

##  5 Theoretical Analysis

We prove that the difference in the gain of a split due to gradient
quantization is bounded by a small value, with enough training data. We
consider loss functions with constant second-order derivatives (i.e., the
$h_{i}$’s are constant). The square error loss function
$l(\hat{y},y)=\frac{1}{2}\left(\hat{y}-y\right)^{2}$ for regression tasks
falls in this category. The analysis is also fit for GBDT without second-order
Taylor approximation. We leave the case for loss functions with non-constant
second-order derivatives in Appendix B. We focus on the discussion of the
conclusion in this section and leave details of the proof in Appendix B. Our
theoretical analysis is based on a more specific form of weak-learnability
assumption in boosting. Specifically, the assumption considers only two-leaf
decision trees (a.k.a. stumps) as weak learners.

Definition 5.1 (Weak Learnability of Stumps) Given a binary classification
dataset $\mathcal{D}=\\{(\mathbf{x}_{i},c(\mathbf{x}_{i}))\\}_{i=1}^{N}$ where
$c(\mathbf{x}_{i})\in\\{-1,1\\}$, weights $\\{w_{i}\\}_{i=1}^{N}$, $w_{i}\geq
0$ and $\sum_{i}w_{i}>0$, there exists $\gamma>0$ and a two-leaf decision tree
with leaf values in $\\{-1,1\\}$ s.t. the weighted classification error rate
on $\mathcal{D}$ is $\frac{1}{2}-\gamma$. Then the dataset $\mathcal{D}$ is
$\gamma$-empirically weakly learnable by stumps w.r.t. $c$ and
$\\{w_{i}\\}_{i=1}^{N}$.

The weak learnability of stump states that given a binary-class concept $c$
and weights for dataset $\mathcal{D}$, there exists a stump that can produce
slightly better classification accuracy than a random guess. Our analysis is
based on the following assumption over the data in a single leaf $s$.

Assumption 5.2 Let $\mathrm{sign}(\cdot)$ be the sign function (with
$\mathrm{sign}(0)=1$). For data subset $\mathcal{D}_{s}\subset\mathcal{D}$ in
leaf $s$, there exists a stump and a $\gamma_{s}>0$ s.t. $\mathcal{D}_{s}$ is
$\gamma_{s}$-empirically weakly learnable by stumps, w.r.t. concept
$c(\mathbf{x}_{i})=\mathrm{sign}(g_{i})$ and weights
$w_{i}=\left|g_{i}\right|$, where $i\in I_{s}$.

An equivalence of the assumption is: $\mathcal{D}$ is $\gamma_{s}$-empirically
weakly learnable by stumps, w.r.t. concept
$c(\mathbf{x}_{i})=\mathrm{sign}(g_{i})$, and weights
$w_{i}=\left|g_{i}\right|$ for $i\in I_{s}$ and $w_{i}=0$ for
$i\in[N]\backslash I_{s}$. A similar assumption has been adopted in previous
theoretical analysis for gradient boosting [12]. The difference is that here
we restrict the weak learner to be a stump. In Appendix B, we show that for
any leaf $s$ with positive split gain, there exists such a $\gamma_{s}>0$. As
we will see in the experiments, for most leaves during the training of GBDT,
$\gamma_{s}$ won’t be too small.

Let $\mathcal{G}_{s\to
s_{1},s_{2}}=-\left(\mathcal{L}_{s_{1}}^{*}+\mathcal{L}_{s_{2}}^{*}\right)\geq
0$, where $\mathcal{L}_{s_{1}}^{*}$ and $\mathcal{L}_{s_{2}}^{*}$ are defined
in equation (3). And let $\widetilde{\mathcal{G}}_{s\to
s_{1},s_{2}}=-\left(\mathcal{\widetilde{L}}_{s_{1}}^{*}+\mathcal{\widetilde{L}}_{s_{2}}^{*}\right)\geq
0$ be the estimated version of $\mathcal{G}_{s\to s_{1},s_{2}}$ after gradient
quantization. And let $\mathcal{G}_{s}^{*}=\mathcal{G}_{s\to
s_{1}^{*},s_{2}^{*}}$ be the value for the optimal split $s\to
s_{1}^{*},s_{2}^{*}$ in leaf $s$. Note that for leaf $s$, the optimal split is
chosen only according to $\mathcal{G}_{s\to s_{1},s_{2}}$, since
$\mathcal{L}_{s}^{*}$ is a constant for different splits of leaf $s$. Then
based on Assumption 5.2, we have the following theorem.

Theorem 5.3 For loss functions with constant hessian value $h>0$, if
Assumption 5.2 holds for the subset $\mathcal{D}_{s}$ in leaf $s$ for some
$\gamma_{s}>0$, then with stochastic rounding and leaf-value refitting, for
any $\epsilon>0$, and $\delta>0$, at least one of the following conclusions
holds:

  * 1.

With any split of leaf $s$ and its descendants, the resultant average of
absolute values of prediction values by the tree in the current boosting
iteration for data in $\mathcal{D}_{s}$ is no greater than $\epsilon/h$.

  * 2.

For any split $s\to s_{1},s_{2}$ of leaf $s$, with a probability of at least
$1-\delta$,

$\small\begin{split}\frac{\left|\widetilde{\mathcal{G}}_{s\to
s_{1},s_{2}}-\mathcal{G}_{s\to
s_{1},s_{2}}\right|}{\mathcal{G}_{s}^{*}}&\leq\frac{\displaystyle\max_{i\in[N]}\left|g_{i}\right|\sqrt{2\ln\frac{4}{\delta}}}{\gamma_{s}^{2}\epsilon\cdot
2^{B-1}}\left(\sqrt{\frac{1}{n_{s_{1}}}}+\sqrt{\frac{1}{n_{s_{2}}}}\right)+\frac{\left(\displaystyle\max_{i\in[N]}\left|g_{i}\right|\right)^{2}\ln\frac{4}{\delta}}{\gamma_{s}^{2}\epsilon^{2}n_{s}\cdot
4^{B-2}}.\\\ \end{split}$ (9)

In equation (9), the bound of gradients $\max_{i\in[N]}\left|g_{i}\right|$ is
determined by the labels and the loss function. For regression tasks, we can
normalize the labels to a fixed range, e.g., $[0,1]$, thus the gradients are
bounded. For classification tasks, the gradients are bounded (in the range
$[-1,1]$) by nature with cross-entropy loss. With enough data in leaf $s$, if
the split is not too imbalanced and partitions enough data into both children
$s_{1}$ and $s_{2}$, then we can expect the error caused by quantization is
small. Theorem 5.3 ensures that with quantized training, either a split of a
leaf has a limited impact on the prediction values, or quantization does not
change the gains of the splits too much.

In equation (9), we also notice that with more bits (larger $B$) to represent
gradients in quantization, the error will be smaller. This is consistent with
our intuition that with more quantized values, we can approximate the original
gradients better. But in practice, we found that a smaller number of bits
(e.g., 2 to 4 bits) is enough for good accuracy. With $n_{s}=10^{7}$ in parent
node $s$, and $n_{s_{1}}=n_{s_{2}}=5\times 10^{6}$. Let
$\epsilon=\max_{i\in[N]}\left|g_{i}\right|/10$, assume that in leaf $s$ we
have $\gamma_{s}=0.2$ and let $\delta=0.1$. With 3 bits for gradients, the
upper bound in (9) is approximately $0.15$. With 4 bits, the value is smaller
than $0.08$. Thus, with a high probability (greater than $90\%$), changes in
split gain due to quantization is well bounded.

We have a similar analysis for the cases where hessians $h_{i}$’s are not
constant. For non-constant hessian values, the analysis requires additional
assumptions. Due to limited space, we left the details in Appendix B.

##  6 System Implementation

In this section, we show how to implement quantized GBDT for good efficiency.
Current CPU and GPU architectures have limited support for the representation
and calculation of low-precision numbers. For example, most CPUs by today only
support 8-bit integers as the smallest data type. Under these limitations, the
benefits of quantized training cannot be fully exploited. Though the gradients
can be compressed into integers with only 2 to 4 bits, we must use at least
8-bit arithmetics for accumulations in histograms. Even with these
limitations, we achieve a considerable speedup on existing CPU and GPU
architectures, given the techniques introduced in this section.

###  6.1 Hierarchical Histogram Buffers

Note that in Algorithm 1 most operations are accumulating gradients. Thus,
low-bitwidth gradients will not bring much speedup if high-bitwidth integers
are used to store the accumulations. On the contrary, integer overflow may
occur with low-bitwidth integers storing the accumulations. To maximally
exploit low-precision computation resources while avoiding integer overflow,
we partition the training dataset by rows (samples) and assign one partition
to a thread on CPU or multiple CUDA blocks on GPU. Thus, each thread or CUDA
block constructs a local histogram over the samples in the assigned partition.
Since the number of training samples per partition is much smaller, in most
cases 16-bit integers for the accumulations in the histogram is enough. In the
end, local histograms are reduced to the total histogram which may use more
bits per bin, e.g. with 16-bit or 32-bit integers. Figure 2 displays this
divide-and-merge strategy and how the bitwidths differ in local and total
histograms.

###  6.2 Packed Gradient and Hessian

We pack the summations of gradients and hessians in a histogram bin into a
single integer in a similar way as SecureBoost+ [6]. For example, if we use
two 16-bit integers to store the accumulation values, then the packed
accumulation value would be a single 32-bit integer. In our case, however,
since gradients can be either negative or positive, the accumulation of
gradients must reside in the upper part of the packed integer to exploit the
signed bit. The accumulation of hessians resides in the lower part of the
packed integer. When accumulating the gradient and hessian of a sample into a
bin, the low-bitwidth gradient and hessian are packed in the same way before
the addition.

Packed gradient and hessian halves the number of memory accesses in histogram
construction. It also halves the number of integer additions. On GPUs, the
packing has one more contribution to efficiency. This is because histogram
construction on GPUs relies on atomic operations to ensure correctness when
multiple threads add to the same histogram. Thus, packing also reduces the
overhead of atomic operations.

##  7 Experiments

Figure 2: Hierarchical histogram buffers.

Table 1: Datasets used in experiments.

Name | #Train | #Test | #Attribute | Task | Metric
---|---|---|---|---|---
Higgs [2] | 10,500,000 | 500,000 | 28 | Binary |  AUC$\uparrow$
Epsilon555https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/binary.html#epsilon | 400,000 | 100,000 | 2,000 | Binary |  AUC $\uparrow$
Kitsune [21] | 14,545,195 | 3,999,993 | 115 | Binary |  AUC$\uparrow$
Criteo666https://go.criteo.net/criteo-research-kaggle-display-advertising-challenge-dataset.tar.gz | 41,256,555 | 4,584,061 | 67 | Binary |  AUC$\uparrow$
Bosch777https://www.kaggle.com/c/bosch-production-line-performance | 1,000,000 | 183,747 | 968 | Binary |  AUC$\uparrow$
Year [3] | 463,715 | 51,630 | 90 | Regression |  RMSE$\downarrow$
Yahoo LTR 888https://webscope.sandbox.yahoo.com/catalog.php?datatype=c | 473,134 | 165,660 | 700 | Ranking |  NDCG@10$\uparrow$
LETOR [25] | 2,270,296 | 753,611 | 137 | Ranking |  NDCG@10$\uparrow$

We evaluate our quantized GBDT training system on public datasets and compare
both accuracy and efficiency with other GBDT tools. First, we show that
quantized GBDT training preserves accuracy with low-bitwidth gradients. Then,
we assess the efficiency on CPUs and GPU of a single machine, and scalability
with distributed training over multiple CPU machines. Ablation study is
provided to analyze the techniques for accuracy preservation and system
implementation. Table 7 lists the datasets used for the experiments. For
Criteo, we encode the categorical features by target and count encoding. We
include open-source GBDT tools XGBoost, LightGBM, and CatBoost as baselines.
We use the leaf-wise tree-growing strategy [27] for all baselines. A full
description of datasets and hyperparameter settings is provided in Appendix C.

Table 2: Comparison of accuracy, w.r.t. different quantized bits. Algorithm | Binary Classification | Regression | Ranking
---|---|---|---
Higgs$\uparrow$ |  Epsilon$\uparrow$ |  Kitsune$\uparrow$ |  Criteo$\uparrow$ |  Bosch$\uparrow$ |  Year$\downarrow$ |  Yahoo LTR$\uparrow$ |  LETOR$\uparrow$
XGBoost | 0.845778 | 0.950210 | 0.948329 | 0.802030 | 0.706423 | 8.954460 | 0.794919 | 0.505058
CatBoost | 0.845425 | 0.943211 | 0.944557 | 0.803150 | 0.687795 | 8.951745 | 0.794215 | 0.519952
LightGBM | 0.845694 | 0.950203 | 0.950561 | 0.803791 | 0.703471 | 8.956278 | 0.793792 | 0.524191
2-bit SRrefit | 0.845587 | 0.949472 | 0.952703 | 0.803293 | 0.700040 | 8.953388 | 0.788579 | 0.519067
3-bit SRrefit | 0.845725 | 0.949884 | 0.951309 | 0.803768 | 0.702025 | 8.937374 | 0.791077 | 0.522220
4-bit SRrefit | 0.845507 | 0.950049 | 0.950911 | 0.803783 | 0.702959 | 8.942898 | 0.792664 | 0.523702
5-bit SRrefit | 0.845706 | 0.950298 | 0.949229 | 0.803766 | 0.703242 | 8.948542 | 0.793166 | 0.524616
2-bit SRno refit | 0.846713 | 0.944509 | 0.952974 | 0.803750 | 0.701399 | 9.112302 | 0.764862 | 0.486193
3-bit SRno refit | 0.846040 | 0.949593 | 0.951385 | 0.803922 | 0.702460 | 8.990034 | 0.780041 | 0.507689
4-bit SRno refit | 0.845816 | 0.950127 | 0.951197 | 0.803812 | 0.704053 | 8.955256 | 0.787575 | 0.515767
5-bit SRno refit | 0.845842 | 0.950275 | 0.949794 | 0.803790 | 0.702717 | 8.952768 | 0.791631 | 0.520900
2-bit RNrefit | 0.795991 | 0.889149 | 0.962201 | 0.779906 | 0.685407 | 9.429014 | 0.765103 | 0.454512
3-bit RNrefit | 0.830506 | 0.944329 | 0.966606 | 0.782732 | 0.688372 | 9.062854 | 0.772364 | 0.476874
4-bit RNrefit | 0.840747 | 0.949946 | 0.961938 | 0.795803 | 0.691163 | 8.968694 | 0.777347 | 0.487394
5-bit RNrefit | 0.843820 | 0.950457 | 0.962427 | 0.802438 | 0.698529 | 8.952418 | 0.784333 | 0.494828
2-bit RNno refit | 0.836683 | 0.925220 | 0.946016 | 0.768338 | 0.695089 | 10.685840 | 0.632058 | 0.203732
3-bit RNno refit | 0.843482 | 0.946850 | 0.940961 | 0.791709 | 0.697933 | 9.377560 | 0.732487 | 0.350127
4-bit RNno refit | 0.845788 | 0.949676 | 0.949228 | 0.802689 | 0.702767 | 8.969828 | 0.765432 | 0.437317
5-bit RNno refit | 0.845765 | 0.950307 | 0.952420 | 0.803645 | 0.695559 | 8.965400 | 0.782608 | 0.485752

###  7.1 Accuracy of Quantized Training

We evaluate the accuracy of quantized training. For each dataset and each
algorithm, the result of the best iteration of the test set is reported. We
use gradients with 2-bit, 3-bit, 4-bit and 5-bit integers, and compare the
results with 32-bit single-precision FP gradients. Table 2 lists the best
metric achieved on the test set across all boosting iterations. We denote
stochastic rounding by SR and round-to-nearest by RN. And use the subscripts
to indicate whether to apply leaf-value refitting. Here we focus on the effect
of quantization on accuracy only (the SRrefit part), and leave the discussion
of rounding strategy and leaf-value refitting in 7.4.1. And due to limited
space, we list only metrics of the CPU version here. Appendix C provides a
similar table for GPU version. With low-bitwidth gradients, the accuracy is
not affected much. For some datasets, including Epsilon, Yahoo LTR, and LETOR,
more gradient bits can improve the performance. Other datasets are less
sensitive to the number of bits.

###  7.2 Speedup on Standalone Machine

We evaluate the acceleration brought by quantized training (SRrefit) on a
single machine by comparing it with CPU and CUDA implementations of popular
open-source GBDT tools. Our quantized training on CPU is based on LightGBM. We
compare our CPU implementation with XGBoost, CatBoost, and LightGBM with
32-bit gradients. For the comparison on GPU, we implement a new CUDA version
of LightGBM (denoted by LightGBM+, details are in Appendix E) and further
implement quantized training based on it. We summarize the benchmark results
in Table 3. Overall, quantized training achieves comparable accuracy with a
shorter training time. For the histogram construction time, quantized training
speeds up histogram construction by up to $3.8$ times on GPU, with an overall
speedup of up to $2.2$ times compared with LightGBM+. We also see the
acceleration on the CPU, but with relatively small gains compared with GPU. In
summary, quantized training pushes forward the SOTA efficiency of GBDT
algorithms. The number of bits for gradients does not influence the training
time much. For histogram construction time, we only list the results with
2-bit gradients due to limited space. A full table can be found in Table 6 of
Appendix C.

Table 3: Detailed time costs for different algorithms in different datasets (seconds). | Algorithm | Higgs | Epsilon | Kitsune | Criteo | Bosch | Year | Yahoo LTR | LETOR
---|---|---|---|---|---|---|---|---|---
GPU total time | XGBoost | 33.97 | 311.12 | 181.24 | 326.82 | 68.44 | 20.47 | 28.64 | 51.29
CatBoost | 61.10 | 105.00 | 80.20 | 187.80 | 22.12 | 33.96 | 59.22 | N/A
LightGBM+ | 29.05 | 87.12 | 77.43 | 102.33 | 21.41 | 24.33 | 30.79 | 41.79
LightGBM+ 2-bit | 24.78 | 39.04 | 38.26 | 61.04 | 12.57 | 18.19 | 23.09 | 33.60
LightGBM+ 3-bit | 24.45 | 39.25 | 38.63 | 59.93 | 12.60 | 18.24 | 24.93 | 33.87
LightGBM+ 4-bit | 24.53 | 39.82 | 40.00 | 59.49 | 12.55 | 18.34 | 25.65 | 34.11
LightGBM+ 5-bit | 24.55 | 41.30 | 40.83 | 60.24 | 12.08 | 18.41 | 25.50 | 34.36
CPU total time | XGBoost | 109.16 | 1282.97 | 281.72 | 565.52 | 130.92 | 28.85 | 103.87 | 72.37
CatBoost | 1009.8 | 1283.4 | 1495.0 | 7702.2 | 998.4 | 95.8 | 588.2 | 865.4
LightGBM | 83.27 | 519.89 | 332.12 | 524.61 | 59.94 | 12.67 | 75.44 | 103.09
LightGBM 2-bit | 73.36 | 426.50 | 215.91 | 444.28 | 46.63 | 12.94 | 61.50 | 72.08
LightGBM 3-bit | 69.64 | 459.39 | 207.96 | 440.68 | 47.35 | 12.79 | 61.07 | 74.35
LightGBM 4-bit | 69.30 | 458.62 | 208.99 | 416.60 | 46.45 | 11.90 | 61.15 | 77.66
LightGBM 5-bit | 69.86 | 457.68 | 211.53 | 423.80 | 47.52 | 11.79 | 61.76 | 77.92
GPU Hist. time | LightGBM+ | 11.26 | 46.96 | 54.77 | 70.97 | 16.57 | 9.61 | 11.59 | 17.75
LightGBM+ 2-bit | 4.84 | 12.11 | 16.41 | 21.74 | 8.52 | 4.08 | 8.23 | 10.20
CPU Hist. time | LightGBM | 50.74 | 458.46 | 253.07 | 385.98 | 53.08 | 6.68 | 58.53 | 66.39
LightGBM 2-bit | 32.82 | 375.70 | 147.10 | 269.00 | 39.80 | 5.99 | 43.59 | 38.23

###  7.3 Speedup of Distributed Training

We evaluate quantization in distributed GBDT training on an enlarged version
of the Epsilon dataset, which duplicates 20 copies of the training set of the
original Epsilon dataset (denoted by Epsilon-8M), and Criteo. Figure 3 shows
how training time and communication time vary with different numbers of
machines. Quantization can consistently reduce communication cost and
accelerate distributed training. On the Criteo dataset, the communication cost
dominates with 16 machines, and the training time with 16 machines is even
slower than with 4 machines. This shows that there is still some room for
improvement in the scalability of our system.

(a) Epsilon-8M

(b) Criteo

Figure 3: Scaling on distributed systems.

###  7.4 Ablation Study

We analyze the effect of proposed techniques that ensure the effectiveness and
efficiency of quantized training. We also provide a discussion on the
feasibility of the weak-learnability assumption used in Section 5.

####  7.4.1 Rounding Strategies and Leaf-Value Refitting

Stochastic rounding plays an important role in the accuracy of quantized
training. Table 2 also compares the accuracy on test sets with round-to-
nearest (denoted by RN) and stochastic rounding (denoted by SR), with
different numbers of gradient bits. For both strategies, the results with and
without leaf-value refitting are both reported. With smaller numbers of bits,
the SR strategy significantly outperforms the RN strategy. Note that leaf-
value refitting is not able to compensate for the drawback of the RN. Table 2
also demonstrates how leaf-value refitting influences accuracy. For binary
classification, leaf-value refitting is less important as a comparable
accuracy could be achieved without it. While for regression and ranking tasks,
leaf-value refitting is crucial to achieving comparable accuracy.

####  7.4.2 Packed Gradient and Hessian

Figure 6 shows the training time and histogram construction time with and
without packing gradient and hessian, testing with 2-bit gradients of CPU
version. No-packing version on GPU requires atomic addition for 16-bit
integers, which is not natively supported by NVIDIA V100 GPUs. Thus, for a
clear comparison, we only show the results of CPU version here. Overall,
packing is important for the speed of histogram construction.

####  7.4.3 Histogram Bitwidth

Figure 4:  Histogram bitwidth frequency.

Figure 5:  Speedup by packing gradients.

Figure 6: Cumulative distribution of $\hat{\gamma}_{s}$.

Figure 6 shows the frequency of per-thread histograms of different bitwidths
used during training with 2-bit gradients on CPUs. The counts are the number
of leaves in the boosting process using the corresponding bitwidth in per-
thread histograms. On CPUs, our per-thread histograms can use either 8-bit,
16-bit, or 32-bit integers. For now 8-bit integer histogram is only available
with 2-bit gradients in our current version. The bitwidth in histograms is
determined by the number of training samples in the leaves, the number of
threads/blocks to use, the total number of bins in histograms of all features,
and the gradient bitwidth. The minimum bitwidth of histogram integers that
won’t result in an integer overflow is chosen. The figure shows that quantized
training exploits low-precision computations. On GPUs, there’s no native
support for atomic additions of packed 8-bit integers. Thus, we use 16-bit
histograms in CUDA blocks in our current implementation. We leave more
aggressive usage of low-bitwidth computations in our future work.

####  7.4.4 Feasibility of Weak-Learnability Assumption

To verify the feasibility of Assumption 5.2, we should evaluate the largest
$\gamma_{s}$ with which a stump with weighted classification error rate
$\frac{1}{2}-\gamma_{s}$ exists. This requires enumerating all the splits
again and calculating the weighted error rate for each split, which is
costing. Luckily, we have an easy approach to obtaining a lower bound of the
largest $\gamma_{s}$, which can be naturally recorded during training of GBDT,
we name the lower bound as $\hat{\gamma}_{s}$. $\hat{\gamma}_{s}$ is the
weighted error rate of the optimal split in leaf $s$ according to the
criterion in (4). Figure 6 shows the cumulative distribution of
$\hat{\gamma}_{s}$ of all leaves during quantized training of the Year dataset
with 3-bit gradients. For most leaves (over $75\%$), a $\gamma_{s}>0.05$
exists. Thus $\gamma_{s}$ won’t be too small for most leaves.

##  8 Discussion and Future Work

In this paper, we try to answer an important but previously neglected
question: Can GBDT exploit low-precision training? We propose a quantized
training framework with low-bitwidth integer arithmetics which enables the
low-precision training of GBDT. We identify the key techniques to preserve
accuracy with quantized training, including stochastic rounding and leaf-value
refitting. Theoretical analysis shows that quantization has a limited impact
on the selection of optimal splits in leaves, given enough training data. We
implement our algorithm with both CPU and GPU versions. Experiments show that
our quantized training GBDT method can achieve comparable accuracy with
significant speedup over SOTA GBDT tools, with CPUs, GPUs, and distributed
clusters. In this work, we propose a simple stochastic quantization framework.
Designing more sophisticated quantization methods for GBDT is an interesting
direction for future exploration. We also leave the implementation of
quantized GBDT training on multi-GPU distributed systems and more aggressive
usage of low-bitwidth computations in our future work. We believe our method
will bring new inspirations in improving GBDT training algorithms, as low-
precision computation becomes a trend in machine learning.

## References

  * [1] Firas Abuzaid, Joseph K Bradley, Feynman T Liang, Andrew Feng, Lee Yang, Matei Zaharia, and Ameet S Talwalkar.  Yggdrasil: An optimized system for training deep decision trees at scale.  In Advances in Neural Information Processing Systems, pages 3817–3825, 2016.
  * [2] Pierre Baldi, Peter Sadowski, and Daniel Whiteson.  Searching for exotic particles in high-energy physics with deep learning.  Nature communications, 5(1):1–9, 2014.
  * [3] Thierry Bertin-Mahieux, Daniel PW Ellis, Brian Whitman, and Paul Lamere.  The million song dataset.  2011\.
  * [4] Jianfei Chen, Yu Gai, Zhewei Yao, Michael W Mahoney, and Joseph E Gonzalez.  A statistical framework for low-bitwidth training of deep neural networks.  Advances in Neural Information Processing Systems, 33:883–894, 2020\.
  * [5] Tianqi Chen and Carlos Guestrin.  Xgboost: A scalable tree boosting system.  In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pages 785–794, 2016.
  * [6] Weijing Chen, Guoqiang Ma, Tao Fan, Yan Kang, Qian Xu, and Qiang Yang.  Secureboost+: A high performance gradient boosting tree framework for large scale vertical federated learning.  arXiv preprint arXiv:2110.10927, 2021.
  * [7] Matthieu Courbariaux, Yoshua Bengio, and Jean-Pierre David.  Binaryconnect: Training deep neural networks with binary weights during propagations.  In Advances in neural information processing systems, pages 3123–3131, 2015.
  * [8] Laurens Devos, Wannes Meert, and Jesse Davis.  Fast gradient boosting decision trees with bit-level data structures.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 590–606. Springer, 2019.
  * [9] Nick Erickson, Jonas Mueller, Alexander Shirkov, Hang Zhang, Pedro Larroy, Mu Li, and Alexander Smola.  Autogluon-tabular: Robust and accurate automl for structured data.  arXiv preprint arXiv:2003.06505, 2020.
  * [10] Fangcheng Fu, Yuzheng Hu, Yihan He, Jiawei Jiang, Yingxia Shao, Ce Zhang, and Bin Cui.  Don’t waste your bits! squeeze activations and gradients for deep neural networks via tinyscript.  In International Conference on Machine Learning, pages 3304–3314. PMLR, 2020.
  * [11] Fangeheng Fu, Jiawei Jiang, Yingxia Shao, and Bin Cui.  An experimental evaluation of large scale gbdt systems.  Proceedings of the VLDB Endowment, 12(11):1357–1370, 2019.
  * [12] Alexander Grubb and J Andrew Bagnell.  Generalized boosting algorithms for convex optimization.  In Proceedings of the 28th International Conference on International Conference on Machine Learning, pages 1209–1216, 2011.
  * [13] Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan.  Deep learning with limited numerical precision.  In International conference on machine learning, pages 1737–1746. PMLR, 2015.
  * [14] Ziniu Hu, Yang Wang, Qu Peng, and Hang Li.  Unbiased lambdamart: An unbiased pairwise learning-to-rank algorithm.  In The World Wide Web Conference, pages 2830–2836, 2019.
  * [15] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio.  Binarized neural networks.  Advances in neural information processing systems, 29, 2016.
  * [16] Jiawei Jiang, Bin Cui, Ce Zhang, and Fangcheng Fu.  Dimboost: Boosting gradient boosting decision tree to higher dimensions.  In Proceedings of the 2018 International Conference on Management of Data, pages 1363–1376, 2018.
  * [17] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu.  Lightgbm: A highly efficient gradient boosting decision tree.  Advances in neural information processing systems, 30:3146–3154, 2017.
  * [18] Hao Li, Soham De, Zheng Xu, Christoph Studer, Hanan Samet, and Tom Goldstein.  Training quantized nets: A deeper understanding.  Advances in Neural Information Processing Systems, 30, 2017.
  * [19] Qi Meng, Guolin Ke, Taifeng Wang, Wei Chen, Qiwei Ye, Zhi-Ming Ma, and Tie-Yan Liu.  A communication-efficient parallel algorithm for decision tree.  Advances in Neural Information Processing Systems, 29, 2016.
  * [20] Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory Diamos, Erich Elsen, David Garcia, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, et al.  Mixed precision training.  In International Conference on Learning Representations, 2018.
  * [21] Yisroel Mirsky, Tomer Doitshman, Yuval Elovici, and Asaf Shabtai.  Kitsune: An ensemble of autoencoders for online network intrusion detection.  In Network and Distributed Systems Security (NDSS) Symposium, 2018\.
  * [22] Richard Nock and Robert Williamson.  Lossless or quantized boosting with integer arithmetic.  In International Conference on Machine Learning, pages 4829–4838. PMLR, 2019.
  * [23] Phuong Pham, Vivek Jain, Lukas Dauterman, Justin Ormont, and Navendu Jain.  Deeptriage: Automated transfer assistance for incidents in cloud services.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3281–3289, 2020.
  * [24] Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin.  Catboost: unbiased boosting with categorical features.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 6639–6649, 2018.
  * [25] Tao Qin, Tie-Yan Liu, Jun Xu, and Hang Li.  Letor: A benchmark collection for research on learning to rank for information retrieval.  Information Retrieval, 13(4):346–374, 2010.
  * [26] Zhen Qin, Le Yan, Honglei Zhuang, Yi Tay, Rama Kumar Pasumarthi, Xuanhui Wang, Michael Bendersky, and Marc Najork.  Are neural rankers still outperformed by gradient boosted decision trees?  In International Conference on Learning Representations, 2020.
  * [27] Haijian Shi.  Best-first decision tree learning.  PhD thesis, The University of Waikato, 2007.
  * [28] Qingquan Song, Dehua Cheng, Hanning Zhou, Jiyan Yang, Yuandong Tian, and Xia Hu.  Towards automated neural interaction discovery for click-through rate prediction.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 945–955, 2020.
  * [29] Meng Wan, Chongxin Deng, Siyu Yu, and JD Vectorlab.  Diting: A real-time distributed feature serving system for machine learning.  Technical report, EasyChair, 2019.
  * [30] Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li.  Terngrad: ternary gradients to reduce communication in distributed deep learning.  In 31st International Conference on Neural Information Processing Systems (NIPS 2017), 2017.
  * [31] Zeyi Wen, Qinbin Li, Bingsheng He, and Bin Cui.  Challenges and opportunities of building fast gbdt systems.  In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21) Survey Track, 2021.
  * [32] Lei Yang, Hong Wu, Tieying Zhang, Xuntao Cheng, Feifei Li, Lei Zou, Yujie Wang, Rongyao Chen, Jianying Wang, and Gui Huang.  Leaper: a learned prefetcher for cache invalidation in lsm-tree based storage engines.  Proceedings of the VLDB Endowment, 13(12):1976–1989, 2020.
  * [33] Xiao Yang, Daren Sun, Ruiwei Zhu, Tao Deng, Zhi Guo, Zongyao Ding, Shouke Qin, and Yanfeng Zhu.  Aiads: Automated and intelligent advertising system for sponsored search.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1881–1890, 2019.
  * [34] Huan Zhang, Si Si, and Cho-Jui Hsieh.  Gpu-acceleration for large-scale tree boosting.  In SysML Conference, 2018.
  * [35] Shuchang Zhou, Yuxin Wu, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou.  Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients.  CoRR, abs/1606.06160, 2016.
  * [36] Wenjun Zhou, Taposh Dutta Roy, and Iryna Skrypnyk.  The kdd cup 2019 report.  ACM SIGKDD Explorations Newsletter, 22(1):8–17, 2020.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes]  Our implementation is
limited by existing processor architecures, which is discussed in section 6.1

    3. (c)

Did you discuss any potential negative societal impacts of your work? [No]  We
believe our method has no negative societal impacts.

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]
All assumptions are strictly stated.

    2. (b)

Did you include complete proofs of all theoretical results? [Yes] We provide
complete and strict proofs in the supplementary.

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
The data we used are all from public databases.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? All these details are available in our paper and the
appendix. Our source code and processed datasets are publicly available. [Yes]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? Our accuracy evaluation in Table 2 are averaged
over 5 different runs. [Yes]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Provided in
supplementary.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes] We discuss
all the used datasets in the experiment section

    2. (b)

Did you mention the license of the assets? [Yes]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [No]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [No] We use publicly available benchmark datasets.

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [No] We use publicly available
benchmark datasets.

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A] We did not use crowdsourcing or conducted
research with human subjects.

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A] We did not use
crowdsourcing or conducted research with human subjects.

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A] We did not use crowdsourcing
or conducted research with human subjects.

##  Appendix A Summary of Appendix

We provide more details of theoretical analysis (Appendix B and D), experiment
results and settings (Appendix C) and a brief introduction to our new
implementation of LightGBM CUDA version (Appendix E).

##  Appendix B Theoretical Analysis

For the simplicity of notations, we will use $s$ in place of $I_{s}$ to
represent the indices of data instances in leaf $s$ in this section.

###  B.1 Existence of $\gamma_{s}>0$

Theorem B.1.1 With constant hessian value $h$, if leaf $s$ has a split gain
$\Delta\mathcal{L}_{s\to s_{1},s_{2}}>0$, then with weights
$\left|g_{i}\right|$ and labels $\mathrm{sign}(g_{i})$, there exists
$\hat{\gamma}_{s}>0$ such that the split $s\to s_{1},s_{2}$ has a weighted
classification error rate $\frac{1}{2}-\hat{\gamma}_{s}<\frac{1}{2}$ for
$\mathcal{D}_{s}$.

Proof of Theorem B.1.1 Since

$\small\begin{split}\Delta\mathcal{L}_{s\to
s_{1},s_{2}}&=\frac{G_{s_{1}}^{2}}{2H_{s_{1}}}+\frac{G_{s_{2}}^{2}}{2H_{s_{2}}}-\frac{G_{s}^{2}}{2H_{s}}=\frac{G_{s_{1}}^{2}}{2hn_{s_{1}}}+\frac{G_{s_{2}}^{2}}{2hn_{s_{2}}}-\frac{G_{s}^{2}}{2hn_{s}}>0,\end{split}$
(10)

we have $\left|G_{s_{1}}\right|>0$ or $\left|G_{s_{2}}\right|>0$. W.L.O.G.,
suppose $\left|G_{s_{1}}\right|>0$. Define $s_{1}^{+}$ as the set of indices
such that $\forall i\in s_{1}^{+},\mathrm{sign}(g_{i})$ equals the weighted
majority of $\mathrm{sign}(g_{i})$ for all $i\in s_{1}$ (weighted by
$\left|g_{i}\right|$), and $s_{1}^{-}=s_{1}-s_{1}^{+}$. Then

$\begin{split}\left|G_{s_{1}}\right|=\left|\sum_{i\in
s_{1}}g_{i}\right|=\sum_{i\in s_{1}^{+}}\left|g_{i}\right|-\sum_{i\in
s_{1}^{-}}\left|g_{i}\right|>0.\end{split}$ (11)

Similarly we define $s_{2}^{+}$ and $s_{2}^{-}$. Then by definition

$\begin{split}\left|G_{s_{2}}\right|=\left|\sum_{i\in
s_{1}}g_{i}\right|=\sum_{i\in s_{2}^{+}}\left|g_{i}\right|-\sum_{i\in
s_{2}^{-}}\left|g_{i}\right|\geq 0.\end{split}$ (12)

Thus the weighted error rate

$\begin{split}\frac{\sum_{i\in s_{1}^{-}}\left|g_{i}\right|+\sum_{i\in
s_{2}^{-}}\left|g_{i}\right|}{\sum_{i\in s_{1}}\left|g_{i}\right|+\sum_{i\in
s_{2}}\left|g_{i}\right|}&=\frac{1}{2}-\frac{\sum_{i\in
s_{1}^{+}}\left|g_{i}\right|+\sum_{i\in
s_{2}^{+}}\left|g_{i}\right|-\sum_{i\in
s_{1}^{-}}\left|g_{i}\right|-\sum_{i\in
s_{2}^{-}}\left|g_{i}\right|}{2\left(\sum_{i\in
s_{1}}\left|g_{i}\right|+\sum_{i\in s_{2}}\left|g_{i}\right|\right)}\\\
&=\frac{1}{2}-\frac{\left|G_{s_{1}}\right|+\left|G_{s_{2}}\right|}{2\left(\sum_{i\in
s_{1}}\left|g_{i}\right|+\sum_{i\in
s_{2}}\left|g_{i}\right|\right)}<\frac{1}{2}.\end{split}$ (13)

Setting

$\hat{\gamma}_{s}=\frac{\left|G_{s_{1}}\right|+\left|G_{s_{2}}\right|}{2\left(\sum_{i\in
s_{1}}\left|g_{i}\right|+\sum_{i\in s_{2}}\left|g_{i}\right|\right)}>0$ (14)

completes the proof.

###  B.2 Proof of Theorem 5.3

Definition 5.1 (Weak Learnability of Stumps) Given a binary classification
dataset $\mathcal{D}=\\{(\mathbf{x}_{i},c(\mathbf{x}_{i}))\\}_{i=1}^{N}$ where
$c(\mathbf{x}_{i})\in\\{-1,1\\}$, weights $\\{w_{i}\\}_{i=1}^{N}$, $w_{i}\geq
0$ and $\sum_{i}w_{i}>0$, there exists $\gamma>0$ and a two-leaf decision tree
with leaf values in $\\{-1,1\\}$ s.t. the weighted classification error rate
on $\mathcal{D}$ is $\frac{1}{2}-\gamma$. Then the dataset $\mathcal{D}$ is
$\gamma$-empirically weakly learnable by stumps w.r.t. $c$ and
$\\{w_{i}\\}_{i=1}^{N}$.

Assumption 5.2 Let $\mathrm{sign}(\cdot)$ be the sign function (with
$\mathrm{sign}(0)=1$). For data subset $\mathcal{D}_{s}\subset\mathcal{D}$ in
leaf $s$, there exists a stump and a $\gamma_{s}>0$ s.t. $\mathcal{D}_{s}$ is
$\gamma_{s}$-empirically weakly learnable by stumps, w.r.t. concept
$c(\mathbf{x}_{i})=\mathrm{sign}(g_{i})$ and weights
$w_{i}=\left|g_{i}\right|$, where $i\in I_{s}$.

Theorem 5.3 For loss functions with constant hessian value $h>0$, if
Assumption 5.2 holds for the subset $\mathcal{D}_{s}$ in leaf $s$ for some
$\gamma_{s}>0$, then with stochastic rounding and leaf-value refitting, for
any $\epsilon>0$, and $\delta>0$, at least one of the following conclusions
holds:

  * 1.

With any split of leaf $s$ and its descendants, the resultant average of
absolute values of prediction values by the tree in current boosting iteration
for data in $\mathcal{D}_{s}$ is no greater than $\epsilon/h$.

  * 2.

For any split $s\to s_{1},s_{2}$ of leaf $s$, with a probability of at least
$1-\delta$,

$\small\begin{split}\frac{\left|\widetilde{\mathcal{G}}_{s\to
s_{1},s_{2}}-\mathcal{G}_{s\to
s_{1},s_{2}}\right|}{\mathcal{G}_{s}^{*}}&\leq\frac{\displaystyle\max_{i\in[N]}\left|g_{i}\right|\sqrt{2\ln\frac{4}{\delta}}}{\gamma_{s}^{2}\epsilon\cdot
2^{B-1}}\left(\sqrt{\frac{1}{n_{s_{1}}}}+\sqrt{\frac{1}{n_{s_{2}}}}\right)+\frac{\left(\displaystyle\max_{i\in[N]}\left|g_{i}\right|\right)^{2}\ln\frac{4}{\delta}}{\gamma_{s}^{2}\epsilon^{2}n_{s}\cdot
4^{B-2}}.\\\ \end{split}$ (15)

Proof of Theorem 5.3 By leaf-wise weak learnability (Assumption 5.2), there
exists a split $s\to s_{L},s_{R}$ and $\gamma_{s}>0$ for $s$ s.t. for data in
$\mathcal{D}_{s}$, with binary labels $c(\mathbf{x}_{i})=\mathrm{sign}(g_{i})$
and weights $w_{i}=|g_{i}|$, the split results in a stump with weighted
binary-classification error rate is $\frac{1}{2}-\gamma_{s}$. Suppose that in
$s_{L}$, $s_{L}^{+}$ is the set of weighted majority samples, and $s_{L}^{-}$
is the set of weighted minority samples (thus $\mathrm{sign}(g_{i})=+1,\forall
i\in s_{L}^{+}$ and $\mathrm{sign}(g_{i})=-1,\forall i\in s_{L}^{-}$, or
$\mathrm{sign}(g_{i})=-1,\forall i\in s_{L}^{+}$ and
$\mathrm{sign}(g_{i})=+1,\forall i\in s_{L}^{-}$) such that $\sum_{i\in
s_{L}^{+}}|g_{i}|\geq\sum_{i\in s_{L}^{-}}|g_{i}|$. Similarly, we define
$s_{R}^{+}$ and $s_{R}^{-}$. Then we have the weighted error rate

$\begin{split}\overline{\mathrm{err}}=\frac{\sum_{i\in
s_{L}^{-}}|g_{i}|+\sum_{i\in s_{R}^{-}}|g_{i}|}{\sum_{i\in
s}|g_{i}|}=\frac{1}{2}-\gamma_{s}.\end{split}$ (16)

Thus

$\begin{split}\frac{\sum_{i\in s_{L}^{+}}|g_{i}|+\sum_{i\in
s_{R}^{+}}|g_{i}|}{\sum_{i\in
s}|g_{i}|}=1-\overline{\mathrm{err}}=\frac{1}{2}+\gamma_{s}.\end{split}$ (17)

Since $\mathcal{G}_{s}^{*}$ is for the optimal split in leaf $s$, we have

$\begin{split}\mathcal{G}_{s}^{*}&\geq\mathcal{G}_{s\to
s_{L},s_{R}}=\frac{\left(\sum_{i\in
s_{L}}g_{i}\right)^{2}}{2hn_{s_{L}}}+\frac{\left(\sum_{i\in
s_{R}}g_{i}\right)^{2}}{2hn_{s_{R}}}\\\ &\geq\frac{\left(\left|\sum_{i\in
s_{L}}g_{i}\right|+\left|\sum_{i\in
s_{R}}g_{i}\right|\right)^{2}}{2h\left(n_{s_{L}}+n_{s_{R}}\right)}\\\
&=\frac{\left(\sum_{i\in s_{L}^{+}}\left|g_{i}\right|-\sum_{i\in
s_{L}^{-}}\left|g_{i}\right|+\sum_{i\in
s_{R}^{+}}\left|g_{i}\right|-\sum_{i\in
s_{R}^{-}}\left|g_{i}\right|\right)^{2}}{2h\left(n_{s_{L}}+n_{s_{R}}\right)}\\\
&=\frac{\left(\sum_{i\in s_{L}^{+}\cup s_{R}^{+}}\left|g_{i}\right|-\sum_{i\in
s_{L}^{-}\cup
s_{R}^{-}}\left|g_{i}\right|\right)^{2}}{2h\left(n_{s_{L}}+n_{s_{R}}\right)}\\\
&=\frac{\left(\left(\frac{1}{2}+\gamma_{s}\right)\sum_{i\in
s}\left|g_{i}\right|-\left(\frac{1}{2}-\gamma_{s}\right)\sum_{i\in
s}\left|g_{i}\right|\right)^{2}}{2h\left(n_{s_{L}}+n_{s_{R}}\right)}\\\
&=\frac{2\gamma_{s}^{2}\left(\sum_{i\in
s}\left|g_{i}\right|\right)^{2}}{h\left(n_{s_{L}}+n_{s_{R}}\right)}=\frac{2\gamma_{s}^{2}\left(\sum_{i\in
s}\left|g_{i}\right|\right)^{2}}{hn_{s}}\end{split}$ (18)

If $\frac{\sum_{i\in s}\left|g_{i}\right|}{n_{s}}\leq\epsilon$, then suppose
$s^{\prime}_{1},...,s^{\prime}_{m}$ are all descendant leaves of $s$, then the
average prediction values by current iteration for data in $\mathcal{D}_{s}$
in current tree is

$\begin{split}\frac{\sum_{i=1}^{m}n_{s^{\prime}_{i}}\left|w_{s^{\prime}_{i}}^{*}\right|}{\sum_{i=1}^{m}n_{s^{\prime}_{i}}}=\frac{\sum_{i=1}^{m}\left|\sum_{i\in
s^{\prime}_{i}}g_{i}\right|}{\sum_{i=1}^{m}n_{s^{\prime}_{i}}h}\leq\frac{\sum_{i\in
s}\left|g_{i}\right|}{n_{s}h}\leq\frac{\epsilon}{h},\end{split}$ (19)

which guarantees that the first conclusion holds.

If $\frac{\sum_{i\in s}\left|g_{i}\right|}{n_{s}}>\epsilon$, let
$\epsilon_{i}=\delta_{g}\widetilde{g}_{i}-g_{i}$, thus
$\left|\epsilon_{i}\right|\leq\delta_{g}$ and $\mathbb{E}[\epsilon_{i}]=0$.
Then

$\begin{split}\left|\widetilde{\mathcal{L}}_{s_{1}}^{*}-\mathcal{L}_{s_{1}}^{*}\right|&=\left|\frac{\left(\sum_{i\in
s_{1}}g_{i}+\epsilon_{i}\right)^{2}}{2hn_{s_{1}}}-\frac{\left(\sum_{i\in
s_{1}}g_{i}\right)^{2}}{2hn_{s_{1}}}\right|\\\
&=\frac{1}{2hn_{s_{1}}}\left|\sum_{i\in
s_{1}}2g_{i}+\epsilon_{i}\right|\left|\sum_{i\in
s_{1}}\epsilon_{i}\right|\leq\frac{1}{2hn_{s_{1}}}\left(\left|\sum_{i\in
s_{1}}2g_{i}\right|\left|\sum_{i\in s_{1}}\epsilon_{i}\right|+\left|\sum_{i\in
s_{1}}\epsilon_{i}\right|^{2}\right)\end{split}$ (20)

Note that $\epsilon_{i}$’s are independent random variables. Let
$t_{s_{1}}=\delta_{g}\sqrt{2n_{s_{1}}\ln\frac{4}{\delta}}$, then by
Hoeffding’s inequality,

$\begin{split}P\left(\left|\sum_{i\in n_{s_{1}}}\epsilon_{i}\right|\geq
t_{s_{1}}\right)\leq
2\exp{\left(-\frac{2t_{s_{1}}^{2}}{n_{s_{1}}\left(2\delta_{g}\right)^{2}}\right)}=\frac{\delta}{2}.\end{split}$
(21)

Then with a probability of at least $1-\frac{\delta}{2}$

$\begin{split}\left|\widetilde{\mathcal{L}}_{s_{1}}^{*}-\mathcal{L}_{s_{1}}^{*}\right|&\leq\frac{1}{hn_{s_{1}}}\left(\left|\sum_{i\in
s_{1}}g_{i}\right|\cdot\delta_{g}\sqrt{2n_{s_{1}}\ln\frac{4}{\delta}}+\delta_{g}^{2}n_{s_{1}}\ln\frac{4}{\delta}\right)\\\
&=\frac{\left|\sum_{i\in
s_{1}}g_{i}\right|\cdot\delta_{g}\sqrt{\frac{2\ln{\frac{4}{\delta}}}{n_{s_{1}}}}}{h}+\frac{\delta_{g}^{2}\ln{\frac{4}{\delta}}}{h}.\end{split}$
(22)

We have

$\begin{split}\frac{\left|\sum_{i\in
s_{1}}g_{i}\right|\cdot\delta_{g}\sqrt{\frac{2\ln\frac{4}{\delta}}{n_{s_{1}}}}}{h\mathcal{G}_{s}^{*}}&\leq\frac{\sum_{i\in
s_{1}}\left|g_{i}\right|\cdot\delta_{g}\sqrt{\frac{2\ln\frac{4}{\delta}}{n_{s_{1}}}}}{\frac{2\gamma_{s}^{2}\left(\sum_{i\in
s}\left|g_{i}\right|\right)^{2}}{n_{s}}}\leq\frac{\delta_{g}\sqrt{\frac{2\ln\frac{4}{\delta}}{n_{s_{1}}}}}{\frac{2\gamma_{s}^{2}\left(\sum_{i\in
s}\left|g_{i}\right|\right)}{n_{s}}}\\\
&\leq\frac{\delta_{g}\sqrt{\frac{2\ln\frac{4}{\delta}}{n_{s_{1}}}}}{2\gamma_{s}^{2}\epsilon}=\frac{\max_{i\in[N]}\left|g_{i}\right|}{2\gamma_{s}^{2}\epsilon\left(2^{B-1}-1\right)}\sqrt{\frac{2\ln\frac{4}{\delta}}{n_{s_{1}}}}.\end{split}$
(23)

And since

$\begin{split}\mathcal{G}_{s}^{*}\geq\frac{2\gamma_{s}^{2}\left(\sum_{i\in
s}\left|g_{i}\right|\right)^{2}}{hn_{s}}>\frac{2\gamma_{s}^{2}\epsilon^{2}n_{s}}{h},\end{split}$
(24)

we have

$\begin{split}\frac{\delta_{g}^{2}\ln\frac{4}{\delta}}{h\mathcal{G}_{s}^{*}}\leq\frac{\delta_{g}^{2}\ln\frac{4}{\delta}}{2\gamma_{s}^{2}\epsilon^{2}n_{s}}=\frac{\left(\max_{i\in[N]}\left|g_{i}\right|\right)^{2}\ln\frac{4}{\delta}}{2\gamma_{s}^{2}\epsilon^{2}\left(2^{B-1}-1\right)^{2}n_{s}}.\end{split}$
(25)

Thus with a probability of at least $1-\frac{\delta}{2}$,

$\begin{split}\frac{\left|\widetilde{\mathcal{L}}_{s_{1}}^{*}-\mathcal{L}_{s_{1}}^{*}\right|}{\mathcal{G}_{s}^{*}}&\leq\frac{\max_{i\in[N]}\left|g_{i}\right|}{2\gamma_{s}^{2}\epsilon\left(2^{B-1}-1\right)}\sqrt{\frac{2\ln\frac{4}{\delta}}{n_{s_{1}}}}+\frac{\left(\max_{i\in[N]}\left|g_{i}\right|\right)^{2}\ln\frac{4}{\delta}}{2\gamma_{s}^{2}\epsilon^{2}\left(2^{B-1}-1\right)^{2}n_{s}}\\\
&\leq\frac{\max_{i\in[N]}\left|g_{i}\right|}{\gamma_{s}^{2}\epsilon\cdot
2^{B-1}}\sqrt{\frac{2\ln\frac{4}{\delta}}{n_{s_{1}}}}+\frac{\left(\max_{i\in[N]}\left|g_{i}\right|\right)^{2}\ln\frac{4}{\delta}}{2\gamma_{s}^{2}\epsilon^{2}n_{s}\cdot
4^{B-2}}\end{split}$ (26)

Similarly, with a probability of at least $1-\frac{\delta}{2}$

$\begin{split}\frac{\left|\widetilde{\mathcal{L}}_{s_{2}}^{*}-\mathcal{L}_{s_{2}}^{*}\right|}{\mathcal{G}_{s}^{*}}&\leq\frac{\max_{i\in[N]}\left|g_{i}\right|}{\gamma_{s}^{2}\epsilon\cdot
2^{B-1}}\sqrt{\frac{2\ln\frac{4}{\delta}}{n_{s_{2}}}}+\frac{\left(\max_{i\in[N]}\left|g_{i}\right|\right)^{2}\ln\frac{4}{\delta}}{2\gamma_{s}^{2}\epsilon^{2}n_{s}\cdot
4^{B-2}}\end{split}$ (27)

By union bound, with a probability of at least $1-\delta$

$\begin{split}&\frac{\left|\widetilde{\mathcal{G}}_{s\to
s_{1},s_{2}}-\mathcal{G}_{s\to
s_{1},s_{2}}\right|}{\mathcal{G}_{s}^{*}}\leq\frac{\left|\widetilde{\mathcal{L}}_{s_{1}}^{*}-\mathcal{L}_{s_{1}}^{*}\right|+\left|\widetilde{\mathcal{L}}_{s_{2}}^{*}-\mathcal{L}_{s_{2}}^{*}\right|}{\mathcal{G}_{s}^{*}}\\\
&\leq\frac{\max_{i\in[N]}\left|g_{i}\right|\sqrt{2\ln\frac{4}{\delta}}}{\gamma_{s}^{2}\epsilon\cdot
2^{B-1}}\left(\sqrt{\frac{1}{n_{s_{1}}}}+\sqrt{\frac{1}{n_{s_{2}}}}\right)+\frac{\left(\max_{i\in[N]}\left|g_{i}\right|\right)^{2}\ln\frac{4}{\delta}}{\gamma_{s}^{2}\epsilon^{2}n_{s}\cdot
4^{B-2}}\end{split}$ (28)

###  B.3 Loss Functions with Non-constant Hessians

Commonly used loss functions for binary-classification, multi-classification,
and ranking have non-constant hessian values. Note that all these loss
functions have non-negative hessian values. We analyze the error caused by
quantization for these functions in this section. Let
$\overline{h}_{s}=\frac{\sum_{i\in s}h_{i}}{n_{s}}$ to be the average of
hessian values in leaf $s$. We have the following theorem.

Theorem B.3.1 For loss functions with non-constant hessian values, if
Assumption 5.2 holds for the subset $\mathcal{D}_{s}$ in leaf $s$ for some
$\gamma_{s}>0$, then with stochastic rounding and leaf-value refitting, for
any $\epsilon>0$ and $\delta>0$, at least one of the following conclusions
holds:

  * 1.

With any split of leaf $s$ and its descendants, the resultant weighted average
(weighted by $h_{i}$) of absolute values of prediction values by the tree in
current boosting iteration for data in $\mathcal{D}_{s}$ is no greater than
$\epsilon$.

  * 2.

For any split $s\to s_{1},s_{2}$ of leaf $s$, if
$n_{s_{1}}\geq\frac{8\delta_{h}^{2}\ln 8/\delta}{\overline{h}_{s_{1}}^{2}}$
and $n_{s_{2}}\geq\frac{8\delta_{h}^{2}\ln
8/\delta}{\overline{h}_{s_{2}}^{2}}$, i.e.
$n_{s_{1}}\leq\frac{\left(\sum_{i\in
s_{1}}h_{i}\right)^{2}}{8\delta_{h}^{2}\ln{8/\delta}}$ and
$n_{s_{2}}\leq\frac{\left(\sum_{i\in
s_{2}}h_{i}\right)^{2}}{8\delta_{h}^{2}\ln{8/\delta}}$, then with a
probability of at least $1-\delta$

$\begin{split}\frac{\left|\widetilde{\mathcal{G}}_{s\to
s_{1},s_{2}}-\mathcal{G}_{s\to
s_{1},s_{2}}\right|}{\mathcal{G}_{s}^{*}}&\leq\frac{\delta_{g}\sqrt{2\ln{8/\delta}}}{\gamma_{s}^{2}\epsilon}\left(\frac{1}{\overline{h}_{s_{1}}\sqrt{n_{s_{1}}}}+\frac{1}{\overline{h}_{s_{2}}\sqrt{n_{s_{2}}}}\right)\\\
&+\frac{\overline{h}_{s}\delta_{h}\sqrt{2\ln{8/\delta}}}{2\gamma_{s}^{2}}\left(\frac{n_{s}}{\overline{h}_{s_{1}}^{2}n_{s_{1}}\sqrt{n_{s_{1}}}}+\frac{n_{s}}{\overline{h}_{s_{2}}^{2}n_{s_{2}}\sqrt{n_{s_{2}}}}\right)\\\
&+\frac{\delta_{g}^{2}\ln{8/\delta}}{\gamma_{s}^{2}\overline{h}_{s}\epsilon^{2}}\left(\frac{1}{\overline{h}_{s_{1}}n_{s}}+\frac{1}{\overline{h}_{s_{2}}n_{s}}\right)\end{split}$
(29)

Proof of Theorem B.3.1 By leaf-wise weak learnability (Assumption 5.2), there
exists a split $s\to s_{L},s_{R}$ and $\gamma_{s}>0$ for $s$ s.t. for data in
$\mathcal{D}_{s}$, with binary labels $c(\mathbf{x}_{i})=\mathrm{sign}(g_{i})$
and weights $w_{i}=|g_{i}|$, the split results in a stump with weighted
binary-classification error is $\frac{1}{2}-\gamma_{s}$. Similar to the case
of loss functions with constant hessian, we define
$s_{L}^{+},s_{L}^{-},s_{R}^{+}$ and $s_{R}^{-}$, and first derive a lower
bound for $\mathcal{G}_{s}^{*}$,

$\begin{split}\mathcal{G}_{s}^{*}&\geq\mathcal{G}_{s\to
s_{L},s_{R}}=\frac{\left(\sum_{i\in s_{L}}g_{i}\right)^{2}}{2\sum_{i\in
s_{L}}h_{i}}+\frac{\left(\sum_{i\in s_{R}}g_{i}\right)^{2}}{2\sum_{i\in
s_{R}}h_{i}}\\\ &\geq\frac{\left(\left|\sum_{i\in
s_{L}}g_{i}\right|+\left|\sum_{i\in s_{R}}g_{i}\right|\right)^{2}}{2\sum_{i\in
s}h_{i}}\\\ &=\frac{\left(\sum_{i\in s_{L}^{+}}\left|g_{i}\right|-\sum_{i\in
s_{L}^{-}}\left|g_{i}\right|+\sum_{i\in
s_{R}^{+}}\left|g_{i}\right|-\sum_{i\in
s_{R}^{-}}\left|g_{i}\right|\right)^{2}}{2\sum_{i\in s}h_{i}}\\\
&=\frac{\left(\sum_{i\in s_{L}^{+}\cup s_{R}^{+}}\left|g_{i}\right|-\sum_{i\in
s_{L}^{-}\cup s_{R}^{-}}\left|g_{i}\right|\right)^{2}}{2\sum_{i\in s}h_{i}}\\\
&=\frac{\left(\left(\frac{1}{2}+\gamma_{s}\right)\sum_{i\in
s}\left|g_{i}\right|-\left(\frac{1}{2}-\gamma_{s}\right)\sum_{i\in
s}\left|g_{i}\right|\right)^{2}}{2\sum_{i\in s}h_{i}}\\\
&=\frac{2\gamma_{s}^{2}\left(\sum_{i\in
s}\left|g_{i}\right|\right)^{2}}{\sum_{i\in s}h_{i}}\end{split}$ (30)

Let $\xi_{i}=\delta_{h}\widetilde{h}_{i}-h_{i}$ and
$\epsilon_{i}=\delta_{g}\widetilde{g}_{i}-g_{i}$, thus
$\left|\xi_{i}\right|\leq\delta_{h}$,
$\left|\epsilon_{i}\right|\leq\delta_{g}$, $\mathbb{E}[\xi_{i}]=0$ and
$\mathbb{E}[\epsilon_{i}]=0$. We then bound the error of $\sum_{i\in
s_{1}}h_{i}$,

$\begin{split}\left|\sum_{i\in s_{1}}\left(h_{i}+\xi_{i}\right)-\sum_{i\in
s_{1}}h_{i}\right|=\left|\sum_{i\in s_{1}}\xi_{i}\right|.\end{split}$ (31)

Note that $\xi_{i}$’s and $\epsilon_{i}$’s are independent variables. Let
$t^{\prime}_{s_{1}}=\delta_{h}\sqrt{2n_{s_{1}}\ln\frac{8}{\delta}}$, then by
Hoeffding’s inequality,

$P\left(\left|\sum_{i\in s_{1}}\xi_{i}\right|\geq
t^{\prime}_{s_{1}}\right)\leq
2\exp{\left(-\frac{{2t^{\prime}_{s_{1}}}^{2}}{n_{s_{1}}(2\delta_{h})^{2}}\right)}=\frac{\delta}{4}$
(32)

Similarly, let
$t^{\prime\prime}_{s_{1}}=\delta_{g}\sqrt{2n_{s_{1}}\ln\frac{8}{\delta}}$,
then by Hoeffding’s inequality we can bound the error of $\sum_{i\in
s_{1}}g_{i}$,

$P\left(\left|\sum_{i\in s_{1}}\epsilon_{i}\right|\geq
t^{\prime\prime}_{s_{1}}\right)\leq
2\exp{\left(-\frac{{2t^{\prime\prime}_{s_{1}}}^{2}}{n_{s_{1}}(2\delta_{g})^{2}}\right)}=\frac{\delta}{4}$
(33)

If $\frac{\sum_{i\in s}\left|g_{i}\right|}{\sum_{i\in s}h_{i}}\leq\epsilon$,
then suppose $s^{\prime}_{1},...,s^{\prime}_{m}$ are all descendant leaves of
$s$, then the average (weighted by $h_{i}$’s) prediction value for data in
$\mathcal{D}_{s}$ in current tree is

$\begin{split}\frac{\sum_{i=1}^{m}\sum_{i\in
s^{\prime}_{i}}h_{i}\left|w_{s^{\prime}_{i}}^{*}\right|}{\sum_{i=1}^{m}\sum_{i\in
s^{\prime}_{i}}h_{i}}=\frac{\sum_{i=1}^{m}\left|\sum_{i\in
s^{\prime}_{i}}g_{i}\right|}{\sum_{i=1}^{m}\sum_{i\in
s^{\prime}_{i}}h_{i}}\leq\frac{\sum_{i\in s}\left|g_{i}\right|}{\sum_{i\in
s}h_{i}}\leq\epsilon\end{split}$ (34)

which guarantees that the first conclusion holds.

If $\frac{\sum_{i\in s}\left|g_{i}\right|}{\sum_{i\in s}h_{i}}>\epsilon$, then
we denote $\overline{h}_{s_{1}}=\frac{\sum_{i\in s_{1}}h_{i}}{n_{s_{1}}}$. If
$n_{s_{1}}\geq\frac{8\delta_{h}^{2}\ln 8/\delta}{\overline{h}_{s_{1}}^{2}}$,
i.e. $n_{s_{1}}\leq\frac{\left(\sum_{i\in
s_{1}}h_{i}\right)^{2}}{8\delta_{h}^{2}\ln{8/\delta}}$, then we have
$\left|\sum_{i\in s_{1}}\xi_{i}\right|\leq\frac{\sum_{i}h_{i}}{2}$ with a
probability of at least $1-\frac{\delta}{4}$ by equation (32). Thus with a
probability of at least $1-\frac{\delta}{2}$,

$\begin{split}\left|\widetilde{\mathcal{L}}_{s_{1}}^{*}-\mathcal{L}_{s_{1}}^{*}\right|&=\frac{1}{2}\left|\frac{\left(\sum_{i\in
s_{1}}g_{i}+\epsilon_{i}\right)^{2}}{\sum_{i\in
s_{1}}h_{i}+\xi_{i}}-\frac{\left(\sum_{i\in s_{1}}g_{i}\right)^{2}}{\sum_{i\in
s_{1}}h_{i}}\right|\\\ &=\frac{1}{2}\left|\frac{\left(\sum_{i\in
s_{1}}g_{i}+\epsilon_{i}\right)^{2}\left(\sum_{i\in
s_{1}}h_{i}\right)-\left(\sum_{i\in s_{1}}h_{i}+\xi_{i}\right)\left(\sum_{i\in
s_{1}}g_{i}\right)^{2}}{\left(\sum_{i\in
s_{1}}h_{i}+\xi_{i}\right)\left(\sum_{i\in s_{1}}h_{i}\right)}\right|\\\
&\leq\frac{\left|\left(\sum_{i\in
s_{1}}g_{i}+\epsilon_{i}\right)^{2}\left(\sum_{i\in
s_{1}}h_{i}\right)-\left(\sum_{i\in s_{1}}g_{i}\right)^{2}\left(\sum_{i\in
s_{1}}h_{i}\right)\right|}{2\left(\sum_{i\in
s_{1}}h_{i}+\xi_{i}\right)\left(\sum_{i\in s_{1}}h_{i}\right)}\\\
&+\frac{\left|\left(\sum_{i\in s_{1}}g_{i}\right)^{2}\left(\sum_{i\in
s_{1}}h_{i}\right)-\left(\sum_{i\in s_{1}}g_{i}\right)^{2}\left(\sum_{i\in
s_{1}}h_{i}+\xi_{i}\right)\right|}{2\left(\sum_{i\in
s_{1}}h_{i}+\xi_{i}\right)\left(\sum_{i\in s_{1}}h_{i}\right)}\\\
&\leq\frac{\left|\sum_{i\in s_{1}}\epsilon_{i}\right|\left|\sum_{i\in
s_{1}}g_{i}\right|}{\sum_{i\in s_{1}}h_{i}+\xi_{i}}+\frac{\left|\sum_{i\in
s_{1}}\epsilon_{i}\right|^{2}}{2\left(\sum_{i\in
s_{1}}h_{i}+\xi_{i}\right)}+\frac{\left(\sum_{i\in
s_{1}}g_{i}\right)^{2}\left|\sum_{i\in s_{1}}\xi_{i}\right|}{2\left(\sum_{i\in
s_{1}}h_{i}+\xi_{i}\right)\left(\sum_{i\in s_{1}}h_{i}\right)}\\\
&\leq\frac{2\left|\sum_{i\in s_{1}}\epsilon_{i}\right|\left|\sum_{i\in
s_{1}}g_{i}\right|}{\sum_{i\in s_{1}}h_{i}}+\frac{\left|\sum_{i\in
s_{1}}\epsilon_{i}\right|^{2}}{\sum_{i\in s_{1}}h_{i}}+\frac{\left(\sum_{i\in
s_{1}}g_{i}\right)^{2}\left|\sum_{i\in s_{1}}\xi_{i}\right|}{\left(\sum_{i\in
s_{1}}h_{i}\right)^{2}}\end{split}$ (35)

Because

$\begin{split}\frac{2\left|\sum_{i\in
s_{1}}\epsilon_{i}\right|\left|\sum_{i\in
s_{1}}g_{i}\right|}{\mathcal{G}_{s}^{*}\sum_{i\in
s_{1}}h_{i}}\leq\frac{\left(\sum_{i\in s}h_{i}\right)\left|\sum_{i\in
s_{1}}\epsilon_{i}\right|\left|\sum_{i\in
s_{1}}g_{i}\right|}{\gamma_{s}^{2}\left(\sum_{i\in
s}\left|g_{i}\right|\right)^{2}\sum_{i\in
s_{1}}h_{i}}\leq\frac{\left|\sum_{i\in
s_{1}}\epsilon_{i}\right|}{\gamma_{s}^{2}\overline{h}_{s_{1}}\epsilon
n_{s_{1}}}\leq\frac{\delta_{g}\sqrt{2\ln
8/\delta}}{\gamma_{s}^{2}\overline{h}_{s_{1}}\epsilon\sqrt{n_{s_{1}}}},\end{split}$
(36) $\begin{split}\frac{\left|\sum_{i\in
s_{1}}\epsilon_{i}\right|^{2}}{\mathcal{G}_{s}^{*}\sum_{i\in
s_{1}}h_{i}}\leq\frac{\left(\sum_{i\in s}h_{i}\right)\left|\sum_{i\in
s_{1}}\epsilon_{i}\right|^{2}}{2\gamma_{s}^{2}\left(\sum_{i\in
s}\left|g_{i}\right|\right)^{2}\sum_{i\in
s_{1}}h_{i}}\leq\frac{\left|\sum_{i\in
s_{1}}\epsilon_{i}\right|^{2}}{2\gamma_{s}^{2}\overline{h}_{s}\overline{h}_{s_{1}}\epsilon^{2}n_{s}n_{s_{1}}}\leq\frac{\delta_{g}^{2}\ln{8/\delta}}{\gamma_{s}^{2}\overline{h}_{s}\overline{h}_{s_{1}}\epsilon^{2}n_{s}},\end{split}$
(37) $\begin{split}\frac{\left(\sum_{i\in
s_{1}}g_{i}\right)^{2}\left|\sum_{i\in
s_{1}}\xi_{i}\right|}{\mathcal{G}_{s}^{*}\left(\sum_{i\in
s_{1}}h_{i}\right)^{2}}\leq\frac{n_{s}\overline{h}_{s}\left|\sum_{i\in
s_{1}}\xi_{i}\right|}{2\gamma_{s}^{2}\left(\sum_{i\in
s_{1}}h_{i}\right)^{2}}\leq\frac{n_{s}\overline{h}_{s}\delta_{h}\sqrt{2\ln{8/\delta}}}{2\gamma_{s}^{2}\overline{h}_{s_{1}}^{2}n_{s_{1}}\sqrt{n_{s_{1}}}}.\end{split}$
(38)

Thus with probability at least $1-\frac{\delta}{2}$ we have

$\frac{\left|\widetilde{\mathcal{L}}^{*}_{s_{1}}-\mathcal{L}^{*}_{s_{1}}\right|}{\mathcal{G}_{s}^{*}}\leq\frac{\sqrt{2\ln{8/\delta}}}{\gamma_{s}^{2}}\left(\frac{\delta_{g}}{\overline{h}_{s_{1}}\epsilon\sqrt{n_{s_{1}}}}+\frac{\overline{h}_{s}\delta_{h}n_{s}}{2\overline{h}_{s_{1}}^{2}n_{s_{1}}\sqrt{n_{s_{1}}}}\right)+\frac{\delta_{g}^{2}\ln{8/\delta}}{\gamma_{s}^{2}\overline{h}_{s}\overline{h}_{s_{1}}\epsilon^{2}n_{s}}.$
(39)

Similarly with probability at least $1-\frac{\delta}{2}$ we have

$\frac{\left|\widetilde{\mathcal{L}}^{*}_{s_{2}}-\mathcal{L}^{*}_{s_{2}}\right|}{\mathcal{G}_{s}^{*}}\leq\frac{\sqrt{2\ln{8/\delta}}}{\gamma_{s}^{2}}\left(\frac{\delta_{g}}{\overline{h}_{s_{2}}\epsilon\sqrt{n_{s_{2}}}}+\frac{\overline{h}_{s}\delta_{h}n_{s}}{2\overline{h}_{s_{2}}^{2}n_{s_{2}}\sqrt{n_{s_{2}}}}\right)+\frac{\delta_{g}^{2}\ln{8/\delta}}{\gamma_{s}^{2}\overline{h}_{s}\overline{h}_{s_{2}}\epsilon^{2}n_{s}}.$
(40)

And finally, with probability at least $1-\delta$,

$\begin{split}\frac{\left|\widetilde{\mathcal{G}}_{s\to
s_{1},s_{2}}-\mathcal{G}_{s\to
s_{1},s_{2}}\right|}{\mathcal{G}_{s}^{*}}&\leq\frac{\delta_{g}\sqrt{2\ln{8/\delta}}}{\gamma_{s}^{2}\epsilon}\left(\frac{1}{\overline{h}_{s_{1}}\sqrt{n_{s_{1}}}}+\frac{1}{\overline{h}_{s_{2}}\sqrt{n_{s_{2}}}}\right)\\\
&+\frac{\overline{h}_{s}\delta_{h}\sqrt{2\ln{8/\delta}}}{2\gamma_{s}^{2}}\left(\frac{n_{s}}{\overline{h}_{s_{1}}^{2}n_{s_{1}}\sqrt{n_{s_{1}}}}+\frac{n_{s}}{\overline{h}_{s_{2}}^{2}n_{s_{2}}\sqrt{n_{s_{2}}}}\right)\\\
&+\frac{\delta_{g}^{2}\ln{8/\delta}}{\gamma_{s}^{2}\overline{h}_{s}\epsilon^{2}}\left(\frac{1}{\overline{h}_{s_{1}}n_{s}}+\frac{1}{\overline{h}_{s_{2}}n_{s}}\right).\end{split}$
(41)

##  Appendix C Experiment Details

In this section, we provide more details about the results, experiment
environments, and hyperparameter settings.

###  C.1 Variance of Quantized Training

In Table 2 the metric values are averaged over 5 random seeds. The seeds are
used to generate random numbers for stochastic rounding. We omit the standard
deviation in Table 2 due to limited space. Here we provide a full table with
standard deviation listed in Table 4. Note that we report the metric on the
best iteration in the test sets.

Table 4: Accuracy with standard variance, w.r.t. different quantized bits (CPU version). Algorithm | Binary Classification | Regression | Ranking
---|---|---|---
Higgs$\uparrow$ |  Epsilon$\uparrow$ |  Kitsune$\uparrow$ |  Criteo$\uparrow$ |  Bosch$\uparrow$ |  Year$\downarrow$ |  Yahoo LTR$\uparrow$ |  LETOR$\uparrow$
XGBoost | 0.845778 | 0.950210 | 0.948329 | 0.802030 | 0.706423 | 8.954460 | 0.794919 | 0.505058
$\pm.000000$ | $\pm.000000$ | $\pm.000000$ | $\pm.000000$ | $\pm.000000$ | $\pm.000000$ | $\pm.000000$ | $\pm.000000$
CatBoost | 0.845425 | 0.943211 | 0.944557 | 0.803150 | 0.687795 | 8.951745 | 0.794215 | 0.519952
$\pm.000144$ | $\pm.000073$ | $\pm.008969$ | $\pm.000232$ | $\pm.000282$ | $\pm.005324$ | $\pm.000196$ | $\pm.000568$
LightGBM | 0.845694 | 0.950203 | 0.950561 | 0.803791 | 0.703471 | 8.956278 | 0.793792 | 0.524191
$\pm.000162$ | $\pm.000144$ | $\pm.000638$ | $\pm.000052$ | $\pm.001110$ | $\pm.004803$ | $\pm.000259$ | $\pm.000360$
2-bit SRrefit | 0.845587 | 0.949472 | 0.952703 | 0.803293 | 0.700040 | 8.953388 | 0.788579 | 0.519067
$\pm.000042$ | $\pm.000166$ | $\pm.000729$ | $\pm.000091$ | $\pm.001759$ | $\pm.012679$ | $\pm.000357$ | $\pm.000681$
3-bit SRrefit | 0.845725 | 0.949884 | 0.951309 | 0.803768 | 0.702025 | 8.937374 | 0.791077 | 0.522220
$\pm.000193$ | $\pm.000095$ | $\pm.001352$ | $\pm.000050$ | $\pm.001519$ | $\pm.007487$ | $\pm.000894$ | $\pm.000721$
4-bit SRrefit | 0.845507 | 0.950049 | 0.950911 | 0.803783 | 0.702959 | 8.942898 | 0.792664 | 0.523702
$\pm.000127$ | $\pm.000072$ | $\pm.001557$ | $\pm.000073$ | $\pm.000607$ | $\pm.008327$ | $\pm.000467$ | $\pm.000653$
5-bit SRrefit | 0.845706 | 0.950298 | 0.949229 | 0.803766 | 0.703242 | 8.948542 | 0.793166 | 0.524616
$\pm.000171$ | $\pm.000108$ | $\pm.001964$ | $\pm.000053$ | $\pm.001041$ | $\pm.003732$ | $\pm.000487$ | $\pm.000439$
2-bit SRno refit | 0.846713 | 0.944509 | 0.952974 | 0.803750 | 0.701399 | 9.112302 | 0.764862 | 0.486193
$\pm.000184$ | $\pm.000174$ | $\pm.001024$ | $\pm.000068$ | $\pm.001663$ | $\pm.014516$ | $\pm.000858$ | $\pm.001789$
3-bit SRno refit | 0.846040 | 0.949593 | 0.951385 | 0.803922 | 0.702460 | 8.990034 | 0.780041 | 0.507689
$\pm.000178$ | $\pm.000119$ | $\pm.001158$ | $\pm.000064$ | $\pm.000768$ | $\pm.009847$ | $\pm.000618$ | $\pm.001126$
4-bit SRno refit | 0.845816 | 0.950127 | 0.951197 | 0.803812 | 0.704053 | 8.955256 | 0.787575 | 0.515767
$\pm.000304$ | $\pm.000172$ | $\pm.001067$ | $\pm.000074$ | $\pm.000277$ | $\pm.003074$ | $\pm.001173$ | $\pm.000448$
5-bit SRno refit | 0.845842 | 0.950275 | 0.949794 | 0.803790 | 0.702717 | 8.952768 | 0.791631 | 0.520900
$\pm.000119$ | $\pm.000234$ | $\pm.002275$ | $\pm.000096$ | $\pm.001075$ | $\pm.009403$ | $\pm.000590$ | $\pm.001087$
2-bit RNrefit | 0.795991 | 0.889149 | 0.962201 | 0.779906 | 0.685407 | 9.429014 | 0.765103 | 0.454512
$\pm.000582$ | $\pm.000856$ | $\pm.000820$ | $\pm.000323$ | $\pm.001055$ | $\pm.017197$ | $\pm.000918$ | $\pm.005565$
3-bit RNrefit | 0.830506 | 0.944329 | 0.966606 | 0.782732 | 0.688372 | 9.062854 | 0.772364 | 0.476874
$\pm.000495$ | $\pm.000319$ | $\pm.001074$ | $\pm.000210$ | $\pm.000351$ | $\pm.014744$ | $\pm.000822$ | $\pm.001500$
4-bit RNrefit | 0.840747 | 0.949946 | 0.961938 | 0.795803 | 0.691163 | 8.968694 | 0.777347 | 0.487394
$\pm.000241$ | $\pm.000207$ | $\pm.001970$ | $\pm.000099$ | $\pm.000698$ | $\pm.005092$ | $\pm.000969$ | $\pm.003279$
5-bit RNrefit | 0.843820 | 0.950457 | 0.962427 | 0.802438 | 0.698529 | 8.952418 | 0.784333 | 0.494828
$\pm.000073$ | $\pm.000071$ | $\pm.001150$ | $\pm.000083$ | $\pm.000425$ | $\pm.003649$ | $\pm.000612$ | $\pm.001543$
2-bit RNno refit | 0.836683 | 0.925220 | 0.946016 | 0.768338 | 0.695089 | 10.685840 | 0.632058 | 0.203732
$\pm.000468$ | $\pm.001545$ | $\pm.005072$ | $\pm.000202$ | $\pm.001510$ | $\pm.001819$ | $\pm.005683$ | $\pm.005507$
3-bit RNno refit | 0.843482 | 0.946850 | 0.940961 | 0.791709 | 0.697933 | 9.377560 | 0.732487 | 0.350127
$\pm.000306$ | $\pm.000399$ | $\pm.006586$ | $\pm.000379$ | $\pm.001424$ | $\pm.042545$ | $\pm.001121$ | $\pm.004163$
4-bit RNno refit | 0.845788 | 0.949676 | 0.949228 | 0.802689 | 0.702767 | 8.969828 | 0.765432 | 0.437317
$\pm.000176$ | $\pm.000126$ | $\pm.002973$ | $\pm.000096$ | $\pm.000408$ | $\pm.005646$ | $\pm.000426$ | $\pm.001514$
5-bit RNno refit | 0.845765 | 0.950307 | 0.952420 | 0.803645 | 0.695559 | 8.965400 | 0.782608 | 0.485752
$\pm.000248$ | $\pm.000150$ | $\pm.003838$ | $\pm.000102$ | $\pm.000582$ | $\pm.002101$ | $\pm.000514$ | $\pm.001105$

As we can see the variance caused by stochastic rounding in quantization is
small, and quantized training is quite stable with different random seeds.

###  C.2 Accuracy of Quantized Training on GPU

Table 5 shows the accuracy of quantized training on GPU, averaged over 5
random seeds for stochastic rounding with leaf-value refitting. For the GPU
version, we run up to 5 bits for gradient discretization. As we can see, for
most datasets a comparable performance is achieved with quantized training.
Note that we report the metric on the best iteration in the test sets.

Table 5: Accuracy with standard variance, w.r.t. different quantized bits (GPU version). Algorithm | Binary-Class | Regression | Ranking
---|---|---|---
Higgs$\uparrow$ |  Epsilon$\uparrow$ |  Kitsune$\uparrow$ |  Criteo$\uparrow$ |  Bosch$\uparrow$ |  Year$\downarrow$ |  Yahoo LTR$\uparrow$ |  LETOR$\uparrow$
XGBoost | 0.846035 | 0.950305 | 0.949952 | 0.802159 | 0.705095 | 8.949647 | 0.794026 | 0.506957
$\pm.000000$ | $\pm.000000$ | $\pm.000000$ | $\pm.000000$ | $\pm.000000$ | $\pm.000000$ | $\pm.000000$ | $\pm.000000$
CatBoost | 0.845237 | 0.949214 | 0.953293 | 0.803766 | 0.713931 | 8.968944 | 0.794176 | N/A
$\pm.000211$ | $\pm.000115$ | $\pm.001535$ | $\pm.000083$ | $\pm.000685$ | $\pm.004703$ | $\pm.000175$
LightGBM+ | 0.845729 | 0.950228 | 0.955914 | 0.803805 | 0.703479 | 8.956194 | 0.794892 | 0.526611
$\pm.000081$ | $\pm.000110$ | $\pm.000962$ | $\pm.000122$ | $\pm.001100$ | $\pm.004720$ | $\pm.000688$ | $\pm.000614$
2-bit SRrefit | 0.846582 | 0.945205 | 0.952898 | 0.803594 | 0.700896 | 9.107948 | 0.769811 | 0.492340
$\pm.000159$ | $\pm.000255$ | $\pm.001554$ | $\pm.000077$ | $\pm.001099$ | $\pm.007273$ | $\pm.000495$ | $\pm.001090$
3-bit SRrefit | 0.845877 | 0.949494 | 0.951672 | 0.803847 | 0.702262 | 8.980230 | 0.784282 | 0.511955
$\pm.000255$ | $\pm.000277$ | $\pm.002186$ | $\pm.000059$ | $\pm.000903$ | $\pm.006827$ | $\pm.000535$ | $\pm.001200$
4-bit SRrefit | 0.845872 | 0.950176 | 0.951918 | 0.803799 | 0.703318 | 8.962148 | 0.790682 | 0.519747
$\pm.000199$ | $\pm.000066$ | $\pm.001138$ | $\pm.000089$ | $\pm.001258$ | $\pm.016629$ | $\pm.000536$ | $\pm.000716$
5-bit SRrefit | 0.845849 | 0.950177 | 0.950538 | 0.803827 | 0.703152 | 8.953900 | 0.793978 | 0.523701
$\pm.000238$ | $\pm.000174$ | $\pm.000354$ | $\pm.000095$ | $\pm.000360$ | $\pm.004574$ | $\pm.000490$ | $\pm.000390$

###  C.3 Detailed Training Time

Table 6 shows the detailed training time records. Note that training time
numbers are evaluated with 5 random seeds. Time for data loading and pre-
processing is excluded. When recording training time, all metric evaluations
are disabled. For quantized training, the number of bits does not influence
the training time much. This indicates that more acceleration can be achieved
for low-bitwidth gradients like 2-bit or 3-bit, with better hardware support
for operations of low-bitwidth integers.

Table 6: Detailed time costs for different algorithms in different datasets (seconds). | Algorithm | Higgs | Epsilon | Kitsune | Criteo | Bosch | Year | Yahoo LTR | LETOR
---|---|---|---|---|---|---|---|---|---
GPU total time | XGBoost | 33.97 | 311.12 | 181.24 | 326.82 | 68.44 | 20.47 | 28.64 | 51.29
$\pm 0.09$ | $\pm 0.48$ | $\pm 0.26$ | $\pm 0.31$ | $\pm 0.19$ | $\pm 0.36$ | $\pm 0.19$ | $\pm 0.25$
CatBoost | 61.10 | 105.00 | 80.20 | 187.80 | 22.12 | 33.96 | 59.22 | N/A
$\pm 3.98$ | $\pm 0.00$ | $\pm 1.72$ | $\pm 1.17$ | $\pm 0.30$ | $\pm 2.04$ | $\pm 0.37$
LightGBM+ | 29.05 | 87.12 | 77.43 | 102.33 | 21.41 | 24.33 | 30.79 | 41.79
$\pm 0.22$ | $\pm 0.39$ | $\pm 0.50$ | $\pm 1.61$ | $\pm 0.44$ | $\pm 0.30$ | $\pm 0.20$ | $\pm 0.42$
LightGBM+ 2-bit | 24.78 | 39.04 | 38.26 | 61.04 | 12.57 | 18.19 | 23.09 | 33.60
$\pm 0.31$ | $\pm 0.31$ | $\pm 0.12$ | $\pm 0.27$ | $\pm 0.29$ | $\pm 0.07$ | $\pm 0.47$ | $\pm 0.29$
LightGBM+ 3-bit | 24.45 | 39.25 | 38.63 | 59.93 | 12.60 | 18.24 | 24.93 | 33.87
$\pm 0.36$ | $\pm 0.31$ | $\pm 0.52$ | $\pm 0.37$ | $\pm 0.39$ | $\pm 0.18$ | $\pm 0.42$ | $\pm 0.38$
LightGBM+ 4-bit | 24.53 | 39.82 | 40.00 | 59.49 | 12.55 | 18.34 | 25.65 | 34.11
$\pm 0.26$ | $\pm 0.15$ | $\pm 0.24$ | $\pm 0.26$ | $\pm 0.27$ | $\pm 0.20$ | $\pm 0.38$ | $\pm 0.12$
LightGBM+ 5-bit | 24.55 | 41.30 | 40.83 | 60.24 | 12.08 | 18.41 | 25.50 | 34.36
$\pm 0.14$ | $\pm 0.10$ | $\pm 0.46$ | $\pm 0.37$ | $\pm 0.24$ | $\pm 0.15$ | $\pm 0.40$ | $\pm 0.07$
CPU total time | XGBoost | 109.16 | 1282.97 | 281.72 | 565.52 | 130.92 | 28.85 | 103.87 | 72.37
$\pm 2.06$ | $\pm 12.53$ | $\pm 4.84$ | $\pm 1.54$ | $\pm 0.45$ | $\pm 0.47$ | $\pm 0.46$ | $\pm 0.22$
CatBoost | 1009.8 | 1283.4 | 1495.0 | 7702.2 | 998.4 | 95.8 | 588.2 | 865.4
$\pm 9.22$ | $\pm 3.32$ | $\pm 31.43$ | $\pm 55.16$ | $\pm 30.36$ | $\pm 1.17$ | $\pm 4.83$ | $\pm 9.13$
LightGBM | 83.27 | 519.89 | 332.12 | 524.61 | 59.94 | 12.67 | 75.44 | 103.09
$\pm 0.41$ | $\pm 1.91$ | $\pm 4.17$ | $\pm 9.32$ | $\pm 0.08$ | $\pm 0.11$ | $\pm 0.37$ | $\pm 1.05$
LightGBM 2-bit | 73.36 | 426.50 | 215.91 | 444.28 | 46.63 | 12.94 | 61.50 | 72.08
$\pm 0.36$ | $\pm 5.25$ | $\pm 3.05$ | $\pm 7.39$ | $\pm 0.47$ | $\pm 0.16$ | $\pm 0.41$ | $\pm 0.55$
LightGBM 3-bit | 69.64 | 459.39 | 207.96 | 440.68 | 47.35 | 12.79 | 61.07 | 74.35
$\pm 0.50$ | $\pm 2.83$ | $\pm 2.45$ | $\pm 38.97$ | $\pm 0.30$ | $\pm 0.22$ | $\pm 0.41$ | $\pm 0.29$
LightGBM 4-bit | 69.30 | 458.62 | 208.99 | 416.60 | 46.45 | 11.90 | 61.15 | 77.66
$\pm 0.40$ | $\pm 2.55$ | $\pm 1.23$ | $\pm 6.73$ | $\pm 0.28$ | $\pm 0.23$ | $\pm 0.43$ | $\pm 1.94$
LightGBM 5-bit | 69.86 | 457.68 | 211.53 | 423.80 | 47.52 | 11.79 | 61.76 | 77.92
$\pm 0.93$ | $\pm 2.81$ | $\pm 4.20$ | $\pm 19.23$ | $\pm 1.54$ | $\pm 0.09$ | $\pm 0.45$ | $\pm 0.50$
GPU Hist. time | LightGBM+ | 11.26 | 46.96 | 54.77 | 70.97 | 16.57 | 9.61 | 11.59 | 17.75
$\pm 0.03$ | $\pm 0.18$ | $\pm 0.37$ | $\pm 1.33$ | $\pm 0.41$ | $\pm 0.03$ | $\pm 0.09$ | $\pm 0.24$
LightGBM+ 2-bit | 4.84 | 12.11 | 16.41 | 21.74 | 8.52 | 4.08 | 8.23 | 10.20
$\pm 0.03$ | $\pm 0.07$ | $\pm 0.13$ | $\pm 0.10$ | $\pm 0.29$ | $\pm 0.02$ | $\pm 0.25$ | $\pm 0.07$
LightGBM+ 3-bit | 4.74 | 12.25 | 16.07 | 21.14 | 8.49 | 4.11 | 8.54 | 10.29
$\pm 0.07$ | $\pm 0.08$ | $\pm 0.15$ | $\pm 0.07$ | $\pm 0.32$ | $\pm 0.02$ | $\pm 0.27$ | $\pm 0.09$
LightGBM+ 4-bit | 4.74 | 12.51 | 16.45 | 21.02 | 8.44 | 4.15 | 8.66 | 10.52
$\pm 0.04$ | $\pm 0.03$ | $\pm 0.12$ | $\pm 0.10$ | $\pm 0.29$ | $\pm 0.02$ | $\pm 0.25$ | $\pm 0.04$
LightGBM+ 5-bit | 4.70 | 13.54 | 16.78 | 21.31 | 7.93 | 4.24 | 8.60 | 10.78
$\pm 0.04$ | $\pm 0.02$ | $\pm 0.09$ | $\pm 0.15$ | $\pm 0.25$ | $\pm 0.03$ | $\pm 0.31$ | $\pm 0.05$
CPU Hist. time | LightGBM | 50.74 | 458.46 | 253.07 | 385.98 | 53.08 | 6.68 | 58.53 | 66.39
$\pm 0.33$ | $\pm 1.74$ | $\pm 5.00$ | $\pm 9.60$ | $\pm 0.19$ | $\pm 0.09$ | $\pm 0.26$ | $\pm 1.05$
LightGBM 2-bit | 32.82 | 375.70 | 147.10 | 269.00 | 39.80 | 5.99 | 43.59 | 38.23
$\pm 0.26$ | $\pm 5.12$ | $\pm 3.57$ | $\pm 7.70$ | $\pm 0.54$ | $\pm 0.14$ | $\pm 0.33$ | $\pm 0.27$
LightGBM 3-bit | 30.84 | 410.29 | 137.54 | 273.68 | 40.36 | 5.85 | 43.47 | 40.21
$\pm 0.38$ | $\pm 2.56$ | $\pm 1.84$ | $\pm 38.78$ | $\pm 0.34$ | $\pm 0.16$ | $\pm 0.36$ | $\pm 0.18$
LightGBM 4-bit | 30.72 | 406.91 | 133.15 | 252.20 | 39.88 | 5.23 | 43.73 | 43.23
$\pm 0.30$ | $\pm 2.35$ | $\pm 1.26$ | $\pm 6.67$ | $\pm 0.26$ | $\pm 0.15$ | $\pm 0.27$ | $\pm 0.92$
LightGBM 5-bit | 30.97 | 406.26 | 130.13 | 259.50 | 40.70 | 5.14 | 44.80 | 43.68
$\pm 0.48$ | $\pm 2.83$ | $\pm 4.23$ | $\pm 18.63$ | $\pm 1.06$ | $\pm 0.06$ | $\pm 0.44$ | $\pm 0.35$

###  C.4 Experiment Environments

Table 9 and 9 list the experiment environments used in this paper for
standalone machines. For CPU clusters in distributed experiments, we use 16
nodes each with one Intel(R) Xeon(R) CPU E5-2673 v4 or Intel(R) Xeon(R)
Platinum 8171M CPU. The nodes are connected by a network of bandwidth between
$7\sim 8$Gbps (tested with iperf999https://iperf.fr/).

Table 7: Experiment Environments (CPU)

CPU | Intel(R) Xeon(R) Platinum 8370C
---|---
Cores | 16 Physical CPU Cores
OS | Ubuntu 18.04
Memory | 256 GB

Table 8: Experiment Environments (GPU)

CPU | Intel(R) Xeon(R) CPU E5-2690 v4
---|---
Cores | 24 Physical CPU Cores
GPU | NVIDIA Tesla V100 PCIe 16GB
OS | Ubuntu 18.04
Memory | 448 GB

Table 9: Hyperparameters of LightGBM boosting_type | gbdt
---|---
learning_rate | 0.1
min_child_weight | 100
num_leaves | 255
max_bin | 255
num_iterations | 500
num_threads | 16
objective (binary) | binary
objective (regression) | regression
objective (ranking) | lambdarank
metric (binary) | auc
metric (regression) | rmse
metric (ranking) | ndcg@10

###  C.5 Hyperparameter Settings

For all accuracy and training time evaluations in this paper, we use the
hyperparameters of LightGBM, XGBoost, and Catboost as listed in Table 9, 11,
and 11, except for the Bosch dataset.

Table 10: Hyperparameters of XGBoost tree_method | hist/gpu_hist
---|---
eta | 0.1
max_depth | 0
max_leaves | 255
num_round | 500
min_child_weight | 100
nthread | 16
gamma | 0
lambda | 0
alpha | 0
objective (binary) | binary:logistic
objective (regression) | reg:linear
objective (ranking) | rank:pairwise
metric (binary) | auc
metric (regression) | rmse
metric (ranking) | ndcg@10

Table 11: Hyperparameters of CatBoost thread_count | 16
---|---
border_count | 255
iterations | 500
learning_rate | 0.1
grow_policy | Lossguide
boosting_type | Plain
max_leaves | 255
depth | 256
min_data_in_leaf | 100
objective (binary) | Logloss
objective (regression) | RMSE
objective (ranking) | YetiRank
metric (binary) | AUC
metric (regression) | RMSE
metric (ranking) | NDCG:top=10;type=Exp
bootstrap_type | No
random_strength | 0
rsm | 1

For the Bosch dataset, we use learing_rate 0.015 for LightGBM and CatBoost,
eta 0.015 for XGBoost, num_leaves 45 for LightGBM, max_leaves 45 for XGBoost
and CatBoost, and keep other hyperparameters the same as in the tables. The
hyperparameters are chosen so that all these algorithms have similar tree
sizes for a fair comparison of training time. In addition, since our GPU
machine has 24 physical CPU cores, we set the number of threads of all
experiments on GPU to be 24. For training time of LightGBM on CPU, we use
force_col_wise=true mode For Bosch, Yahoo LTR, Year, and Epsilon (except 2-bit
and 3-bit quantized training). For all other cases we use force_row_wise=true
mode of LightGBM CPU version.

The git commit used for CatBoost is 2617a690c77c9c8da1c22d1750b5fbe0eb0eb36d
(Date: Thu Jan 12 05:29:47 2023 +0300). And for XGBoost it is
cfa994d57fb713e203a494319a6d33fcd007adf8 (Date: Wed Jan 11 05:51:14 2023
+0800). For LightGBM, we use the commit
5df7d516f3e64e8431aecfea892a850afeb787bb (Date: Fri Jan 13 17:02:42 2023
+0200) for the FP32 experiments on CPU. For other experiments of LightGBM, we
use the version provided in our Github link https://github.com/Quantized-
GBDT/Quantized-GBDT.

###  C.6 Data Split and Preprocessing

For most datasets (Higgs, Epsilon, Yahoo, LETOR, Year, Bosch) we use the
convention in previous works or the default split [34, 25, 3], without
additional preprocessing. For Criteo, we encode the categorical features in
the original dataset with target and count encoding. We use the train.txt file
of the Kaggle version of the Criteo dataset, with the first $41,256,555$ rows
as the training set and the last $4,584,061$ rows as the test set. For
Kitsune, we select the first $80\%$ packets in each attack method to form the
training set, and the final $20\%$ packets to form the test set. The datasets
can be freely downloaded from
https://pretrain.blob.core.windows.net/quantized-gbdt/dataset.zip.

##  Appendix D Discussion on Loss Functions with Non-constant Hessians

Appendix B.3 provides the theoretical analysis and proof for the error caused
by quantization for loss functions with non-constant hessians. The assumption
is a little bit stronger than constant hessian loss functions in that we are
expecting the average hessian values per leaf won’t be too small, so that
$n_{s_{1}}\geq\frac{8\delta_{h}^{2}\ln 8/\delta}{\overline{h}_{s_{1}}^{2}}$
and $n_{s_{2}}\geq\frac{8\delta_{h}^{2}\ln
8/\delta}{\overline{h}_{s_{2}}^{2}}$ hold. Figure 7 shows the average hessian
values in each iteration with 3-bit gradients. We first calculate the average
hessian values for all leaves in each iteration. Then we plot the mean of the
average hessian values over the leaves in each iteration in solid blue curves,
with the shadow area indicating the range between $10\%$ and $90\%$
percentiles over the leaves in each iteration. For most leaves, the average
hessian values are not too small. And it is easy to meet the condition
$n_{s}\geq\frac{8\delta_{h}^{2}\ln{8/\delta}}{\overline{h}_{s}^{2}}$ with
enough training data. For example, suppose $\overline{h}_{s}=0.01$, then for
binary classification, with 3-bit gradients,
$\delta_{h}=\frac{0.25}{6}=\frac{1}{24}$. Let $\delta=0.01$, then
$\frac{8\delta_{h}^{2}\ln{8/\delta}}{\overline{h}_{s}^{2}}\approx 928$.

(a) Higgs

(b) Criteo

(c) Yahoo LTR

(d) LETOR

Figure 7: Average Hessian Values by Iteration with 3-Bit Gradients

In addition, in the first conclusion of Theorem B.3.1 we consider weighted
prediction values by $h_{i}$. Since with second-order approximation of the
loss function, $h_{i}$ influences how much a training sample contributes to
the approximated loss by second-order Taylor expansion [5]. Thus, considering
the weighted prediction values by $h_{i}$ is meaningful.

Finally, the upper bound in Theorem B.3.1 requires a balanced split to be
small. In other words, the data sizes in child nodes $n_{s_{1}}$, $n_{s_{2}}$
shouldn’t be significantly smaller than that in parent node $n_{s}$, so that
the terms $\frac{n_{s}}{n_{s_{1}}\sqrt{n_{s_{1}}}}$ and
$\frac{n_{s}}{n_{s_{2}}\sqrt{n_{s_{2}}}}$ can be bounded by a small value.

##  Appendix E New CUDA Framework of LightGBM

We implement a new CUDA version for LightGBM. Previous GPU versions of
LightGBM only run histogram construction on GPUs. Our new implementation
performs the whole training process including boosting (calculation of
gradients and hessians) and tree learning on GPUs. We denote this new GPU
version of LightGBM by LightGBM+ in our paper.