Gradient Boosting Performs Gaussian Process Inference
Authors: Aleksei Ustimenko
Artem Beliakov
Liudmila Prokhorenkova
Venue: ICLR 2023 poster (2023)
Keywords: gradient boosting
gaussian process
knowledge uncertainty
kernel gradient boosting

Abstract: This paper shows that gradient boosting based on symmetric decision trees can be equivalently reformulated as a kernel method that converges to the solution of a certain Kernel Ridge Regression problem. Thus, we obtain the convergence to a Gaussian Process' posterior mean, which, in turn, allows us to easily transform gradient boosting into a sampler from the posterior to provide better knowledge uncertainty estimates through Monte-Carlo estimation of the posterior variance. We show that the proposed sampler allows for better knowledge uncertainty estimates leading to improved out-of-domain detection.

Published as a conference paper at ICLR 2023
GRADIENT BOOSTING PERFORMS GAUSSIAN PROCESS INFERENCE
Aleksei Ustimenko"
Artem Beliakov
ShareChat
Yandex Research, HSE University be 1 yakov..vvvvomm arteom20111 58gma1 1 com
research awaccch@@lekeeee aleksei.ur
Liudmila Prokhorenkova
Yandex Research
ostrouneva- 1aa0 com
ABSTRACT
This paper shows that gradient boosting based on symmetric decision trees can be equivalently reformulated kernel method that converges to the solution of certain Kernel Ridge Regression problem. Thus, we obtain the convergence to a Gaussian Process' posterior mean, which, in turn, allows gradient boosting into sampler from the posterior to provide better knowledge uncertainty estimates through Monte-Carke estimation of the posterior variance. We show that the proposed sampler allows for better knowledge uncertainty esti- mates leading to improved out-of-domain detection.
easily transform
INTRODUCTION
Gradient boosting (Friedman 2001) classic machine learning algorithm successfully used for web search, recommendation systems, weather forecasting, and other problems (Roe et al. 2005
Caruana & Niculescu-Mizz 2006 Richardson et al. 2007 Wu et al.) 2010 Burges 2010 Z &
Haghani 2015). In nutshell, gradient boosting methods iteratively combine simple models (usually decision trees), minimizing a given loss function. Despite the recent success of neural approaches in
various areas, tradient-boostedd decision trees (GBDT) still state-of-the-an algorithms for tabular
datasets containing heterogeneous features (Gorishniy et al.)
2021 Katzir et al., 2021).
This paper aims at a better theoretical understanding of GBDT methods for regression problems assuming the widely used RMSE loss function. First, we show that the gradient boosting with regularization can be reformulated as optimization problem in some Reproducing Kernel Hilbert Space (RKHS) with implicitly defined kernel structure. After obtaining that connection between GBDT and kernel methods, we introduce technique for sampling from prior Gaussian process distribution with the same kernel that defines RKHS so that the final output would converge to sample from the Gaussian process posterior. Without this technique, we can view the output of GBDT as the mean function of the Gaussian process.
Importantly, our theoretical analysis assumes the regularized gradient boosting procedure (Algo- rithm()) without any simplifications- properly randomized (Algorithm/) []. These assumptions are non-restrictive and are satisfied some popular gradient boosting implementations, e.g., CatBoost (Prokhorenkova et al. 2018).
only need decision trees to be symmetric (oblivious) and
Our experiments confirm that the proposed sampler from the Gaussian process posterior outperforms the previous approaches (Malinin et al.] 2021) and gives better knowledge uncertainty estimates and improved out-of-domain detection.
"A major part of the work done while working Yandex Research.

---

Published as a conference paper at ICLR 2023
2 BACKGROUND
Assume that we are given a distribution ! over X x Y, where X C Rd called a feature space and Y C R target space. Further assume that are given dataset {(i;, W X Y of size N 2 1 sampled i..d. from Let us denote by p(dx) = Jy do(dx, dy). W.l.o.g,, we also assume that X = supp p = { E Rd Ve plf( E Rd | x' 2'1lRa < ()) > 0} which is a Σ
closed subset of IRd. Moreover, for technical reasons, assume that 2N Di=1 ve I R for some constant R >> 0 almost surely, which can always be enforced by clipping. Throughout the paper, we also denote by xN and yN the matrix of all feature vectors and the vector of targets.
2.1 GRADIENT BOOSTED DECISION TREES
Given loss function T. R2 + IR, a classic gradient boosting algorithm (Friedman, 2001 iteratively combines weak learners (usually decision trees) to reduce the average loss over the train set z: L(F) (fx), v)]- At each iteration the model is updated as: fx) = fr-1 (x) - ew, (x)) where w+).) E W a weak learner chosen from some family of functions W, and c is a learning rate. The weak learner w, is usually chosen to approximate the negative gradient of the loss function aL(s.u)
-9t 9- (x. =
88
fo ((x)
Wr arg min [2[( 9r (I. x(x))²
wEW
The family W usually consists of decision trees. In this case, the algorithm is called GBDT (Gradient Boosted Decision Trees). A decision tree is model that recursively partitions the feature space into disjoint regions called leaves. Each leaf Ry of the tree is assigned to value, which is the estimated
Σッ 2j=1 0, (xER,), so the response y in the corresponding region. Thus, we can write wxx) = decision tree is a linear function of the leaf values fz.
A recent paper Ustimenko & Prokhorenkoval (2021) proposes modification of classic stochastic gradient boosting (SGB) called Stochastic Gradient Langevin Boosting (SGLB). SGL.B combines gradient boosting with stochastic gradient Langevin dynamics achieve global convergence even for non-convex loss functions. As result, the obtained algorithm provably converges to some stationary distribution (invariant measure) concentrated near the global optimum of the loss function. We mention this method because it samples from similar distribution as our method but with different kernel.
2.2 ESTIMATING UNCERTAINTY
In addition to the predictive quality, it is often important to detect when the system is uncertain and can be mistaken. For this, different measures uncertainty can be used. There are two main sources of uncertainty: data uncertainty (a.k.a. aleatoric uncertainty) and knowledge uncertainty (a.k.a. epistemic uncertainty). Data uncertainty arises due to the inherent complexity of the data, such as additive noise overlapping classes. For instance, if the target is distributed y ((f(r), (z)). then (zx) reflects the level of data uncertainty. This uncertainty can be assessed if the model is probabilistic.
Knowledge uncertainty arises when the model gets input from region either sparsely covered by or far from the training data. Since the model does not have enough data in this region, it will likely make a mistake. A standard approach to estimating knowledge uncertainty is based on ensem- bles (Gall 2016 Malinin| 2019). Assume that we have trained an ensemble of several independent models. If all the models understand an input (low knowledge uncertainty). they will give similar predictions. However, for out-of-domain examples (high knowledge uncertainty), the models are likely to provide diverse predictions. For regression tasks, one obtain knowledge uncertainty by measuring the variance of the predictions provided by multiple models (Malinin) 2019).
Such ensemble-based approaches are standard for neural networks (Lakshminarayanan al. 2017 Recently, ensembles were also tested for GBDT models (Malinin et al. (021). The authors consider two ways of generating ensembles: ensembles of independent SGB models and ensembles of inde- pendent SGLB models. While empirically methods are very similar, SGLB has better theoretical properties: the convergence of parameters to the stationary distribution allows one sample models
2

---

Published as a conference paper at ICLR 2023
from particular posterior distribution. One drawback of SGLB is that its convergence rate is un- known, as the proof is asymptotic. However, the convergence rate can be upper bounded by that of Stochastic Gradient Langevin Dynamies for log-concave functions, e.g., Zou al. (202I). which is not dimension-free. In contrast, our rate is dimension-free and scales linearly with inverse precision.
2.3 GAUSSIAN PROCESS INFERENCE
In this section, we briefly describe the basics of Bayesian inference with Gaussian processes that is closely related to our analysis. A random variable f with values in (p) is said to be Gaussian pro- cess GP (fu. of PC +d) with covariance defined via a kernel K(x, x') cov (f(') and mean value fo T2(p) iff Vy E T2(()) we have
J f(=)g(=))((z)) ~ N (1/ (o(=))(=))(ds))d)
[xxxxlenn g(x)K((, x' (a))g("))) pl(dz) @ p(dx') + 6 (19122))
typical Gaussian Process setup is to assume that the target y|ı distributed as GP (z)) o² KC+ rlld,,) for some kernel (amection<((a, x²) with scales a > and > 0:
u|x = f(x), f GP(OL 2 1
The posterior distribution ((x))ar, NN. again Gaussian Process GP(J,, +1ldrg)) with mean and covariance given by (see Rasmussen & Williams (006)):
f. (K(,, - AIN) " YN,
E(x, x)) <(),,))) K(xx, (x) (K((,,, + ANN) x))
with x = z.. To estimate the posterior mean (x) JR ['(S]ax YN, dS. can use the maximum a posteriori probability estimate (MAP) - the only solution for the following Kernel Ridge Regression (KRR) problem:
N
L() = 2N
Σ
(f(x.) - -.)²
2N 1
min JEH
where H span (K(+, x X} L2(p) is the reproducing kernel Hilbert space (RKHS) for the kernel (C(,;)) and L(f) minjeH means that seeking minimizers of this funetion L(f)- We refer to Appendix D for the details on KRR and RKHS.
To solve the KRR problem,
apply the gradient descent (GD) method in the functional space:
1 N N
fr+1 (1 N
de x
Σ (fr())) K.K.. fo = -Da(e))
(2)
where 0 is learning rate.
Since this objective is strongly convex due to the regularization, the gradient descent rapidly con- verges to the unique optimum:
lim fo f+ =K. K(, xN) + AIN) YN.
see Appendices C and for the details.
Gradient descent guides f- the posterior mean f. of the Gaussian Process with kernel o²K + 52Id To obtain the posterior variance estimate K(2 æ) for any x, one can use sampling and introduce source of randomness in the above iterative scheme as follows:
1. sample fimit ~ GP(DDLLO), KC &rIdzz);
2. set new labels new = =N - pinit pxx)
3. fit GD (+) on new assuming Fo(.) Oz(())
4. output pimit( (.) + fr(+) as final model.
"K(x,,)') kernel function if [K((,, N.N , 2 for any and any J, X almost surely.

---

Published as a conference paper at ICLR 2023
This method is known Sample-then-Optinne (Matthews et al., 2017) and is widely adopted for Bayesian inference. As T + oc, we get fonit + foe distributed as a Gaussian Process posterior with the desired mean and variance. Formally, the following result holds:
Lemma 2.1. finit + foe follows the Gaussian Process posterior GP(fA.oRk + 1dI,,, with:
(x) K(x, XN ) ALN) YN. "YN,
K(z,z) K(xz, 2)) -
+ (NN) K(xN,
3 EVOLUTION OF GBDT IN RKHS
3.1 PRELIMINARIES
In our analysis, we assume that we are given finite set of weak learners used for the gradient boosting 2 Each y corresponds to decision tree that defines a partition of the feature space into disjoint regions (leaves). For each v E V. we denote the number of leaves in the tree by L, 2 1. Also, let Ø2 X + {0, 1 be mapping that maps
the vector indicating its leaf index in
the tree This mapping defines decomposition of X into the disjoint union: X -/=1=
X| x1)) (z) 1). Having 6u. we define weak learner associated with it as + (0, (x))RE for any choice of 0 RR which we refer to 'leaf values'. In other words, 0 corresponds to predictions assigned to each region of the space defined by v.
Let us define linear space C L2(p) of all possible ensembles of trees from V:
F = span (.): X - {0, H V.j E (1,.... [w]]-
We note that the space F can be data-dependent since V may depend on z, but we omit this depen- dence in the notation for simplicity. Note that we do not take the closure w.r.t. the topology L2(p) since we assume that V is finite and therefore F is mnite-dimensionll and thus topologically closed.
3.2 GBDT ALGORITHM UNDER CONSIDERATION
Our theoretical analysis holds for classic GBDT algorithms discussed Section 2.1 equipped with regularization from Ustimenko & Prokhorenkova 2021). The only requirement need is that the procedure choosing each new tree has to be properly randomized. Let us discuss a tree selection algorithm that we assume in our analysis.
Each new tree approximates the gradients of the loss function with respect to the current predictions of the model. Since we consider the RMSE loss function, the gradients proportional to the residuals rj = yj fzz)), where f is the currently built model. The tree structure is defined by the features and the corresponding thresholds used to split the space. The analysis in this paper assumes the Sample'Tree procedure (see Algorithm []. which is classic approach equipped with proper randomization. SampleTrree builds an oblivious decision tree (Prokhorenkova et al. 2018), i... all nodes at given level share the same splitting criterion (feature and threshold) To limit the number candidate splits, each feature is quantized into n + bins. In other words, for each feature, we have thresholds that can be chosen arbitrarily f The maximum tree depth is limited by m. Recall that we denote the set of all possible tree structures by V.
We build the tree in top-down greedy manner. At each step, choose split among all the remaining candidates based on the following score defined for v e V and residuals r:
Ly (IN
0 1 (T.)).))
D(v,r) = N J=1
ΣN (x:)
The finiteness of V important for our analysis, and usually holds in practice, see Section 3.2 In fact, the procedure can be extended arbitrary trees, but this would com--comel formulation of the algorithm and would not change the space of tree ensembles as any non-symmetric tree he represented sum of symmetric ones.
AA standard approach is to quantize the feature such that all + 1 buckets have approximately the same number of training samples.
4

---

Published as a conference paper at ICLR 2023
Algorithm 1 (m (,,
Algorithm TrainGBDD m, B,
input: residuals r = (r:)
input: dataset z = (NN.yN)
output: oblivious tree structure v E
hyper-parameters: learning rate 0,
hyper-parameters: number of feature splits max. tree depth m, random strength 3 [0, 0o) definitions:
regularization X > 0, iterations of boost- ing T, parameters of SampleTree m, n,
S = (G k)lj E (l....,d]) ......,,,.. E E [1,...,nt}
instructions:
indices of all possible splits
initialize T = 0, fo(-) = (p2(p)
instructions:
repeat
initialize = 0 10 0, ((0) =
YN f+(xN) compute residu- als
repeat
sample (s)) U(0, 1) choose next split
V, SampleTrec(r,::m struct a tree
{8++1}
0, Ei (as))))))
Lur
arg max (D r) Blog( log u.g,u(0 (8))
Li= (x.)
set val-
j=1
sES())
ues in leaves
update tree: 1/+11 (v/ 8141)
f++1(-)
(1
()+(() +
update candidate splits: S(++1) = 8(0) (6++1)
<< (d (),0r)
update model
i=i+1 until 2 m = =0==
7 +1
until 7 2
return: 2/2
return: fr(-)
In classic gradient boosting, one builds a tree recursively by choosing such split s that maximizes the score (( s), (Ibragimov & Gusev 2019) 5 Random noise often added to the scores to improve generalization. In SampleTree, we choose a split that maximizes D ((v,,)), + where Gumbel(0, 3)
Here B is random strength: B 0 gives the standard greedy approach, while oo gives the uniform distribution among all possible split candidates.
To sum up. SampleTree a classic oblivious tree construction but with added random noise. We do this to make the distribution of trees regular in certain sense: roughly speaking, the distributions should stabilize with iterations by converging to some fixed distribution.
Given the algorithm SampleTree, we describe the gradient boosting procedure assumed in our analysis Algorithm 2 It a classic GBDT algorithm but with update rule f++1()) = (1 \e/N) f-(+) ew- (a)). In other words, we shrink the model at each iteration, which serves as regularization (Ustimenko & Prokhorenkoval 202I). Such shrinkage is available, c.g., in the CatBoost library.
3.3 DISTRIBUTION OF TREES
The SampleTree algorithm induces a local family of distributions p(-15, B) for each f E f(xx); E dey) drr).
p(dv)f (
(SamlleTrree
Remark 3.1. Lemma D.5 ensure that such distribution coincides with the one where we use f. (xN)
instead of v- This due to the fact that ((,, - [xxN)) = D(v, ((xx) Yu E V, ʃ E
The following lemma describes the distribution p(dvlf, f, B). see Appendix F for the proof.
Lemma 3.2. (Probability of tree
Die (i
p(uls,3)=
ΣI SEP E1 EeES
Maximizing 4 is cquivalent minimizing the squared error hetween the residuals and the mean values the leaves.
"Note that for oblivious decision trees, changing the order of splits does not affect the obtained partition. Hence, we assume that each tree is defined by unordered set of splits.
5

---

Published as a conference paper at ICLR 2023
where the sum is over all permutations < Pms V,, ($<(1):.... Sc(s)), and ($1,..., Sm).
Let us define the stationary distribution of trees as T() lim ()) It follows from Re-
mark 3.1 that also have π(-) p(,
Corollary 3.3. (Stationary distribution is the uniform distribution over tree structures)
We have π (dv)) = drl/ (d)) where (m)) (md))
1mm
3.4 RKHS STRUCTURE
In this section, we describe the evolution of GBDT in a certain Reproducing Kernel Hilbert Space (RKHS). Even though the problem finite dimensional, treating as functional regression is more beneficial dimension of the ensembles space grows rapidly and therefore we want to obtain dimension-free constants which is impossible if we treat it as finite dimensional optimization prob- lem. Let start with defining necessary kernels. For convenience, illustrating the introduced kernels and relations between them in Appendix
also provide diagram
Definition 3.4. A weak learner's kernel ku(-,)) )) is kernel function associated with tree structure y E which can be defined as:
Iy
N
N
ku(x,
Σ
(x) where w max G)
NO
Σ
か6 (x:).
13
This weak learner's kernel is building block for any other possible kernel in boosting and is used to define the iterations of the boosting algorithm analytically. Definition 3.5. We also define greedy kernel of the gradient boosting algorithm as follows:
K,(x,x')
Σ (x, x' p)v1.f...
DEV
This greedy kernel is kernel that guides the GBDT iterations, i.e., we can think of each iteration as SGD with kernel from 3.5 and 3.4 is used as stochastic gradient estimator of the Fréchet derivative in RKHS defined by the kernel from 3.5
Definition 3.6. Finally, there is a stationary kernel C(( x²)
that is independent from f: Σ Ki (2r,2x)))
K(x,x')
which we call prior kernel of the gradient boosting.
This kernel defines the limiting solution since the gradient projection on RKHS converges to zero, and thus 3.5 converges to 3.6
Note that span (K(,,a) x E x}. Having the space of functions F, we define RKHS structure H = (F, ()) on using a scalar product defined as
(f, x)), f(x).
Now, let define the empirical error of model f::
L(f,A) = 2N luN - fxxx)ll + 2 I1
2N
Then, we define V(f.A) = L(f,A) - inf pEr L(f, Let us also define the following functions:
fA E arg min fer V(f,A) and
f. lim fa x
arg min V(f), where V()) V(S00-
JEF
known that such f. exists and is unique since the set of all solutions is convex, and therefore there is unique minimizer of the norm || 1|x. Finally, the following lemma gives the formula of the GBDT iteration in terms of kernels in Lemma 3.7 which will be useful in proving our results. See Appendix for the proofs.
Lemma 3.7. Iterations fr of Gradient Boosting (Algorithm 2 can be written in the form:
de, fr41 = (1 X², ),r + e hkv (1, (fxx)][F(xxx) I (xw)] ~ p(ylfr.8).
N

---

Published as a conference paper at ICLR 2023
3.5 KERNEL GRADIENT BOOSTING CONVERGENCE TO KRR
Consider the sequence (/r TEE generated by the gradient boosting algorithm. Its evolution is de- scribed by Lemma 3.7 The following theorem estimates the expected (w.r.t. the randomness of tree selection) empirical error of fr relative to the best possible ensemble. The full statement of the theorem and its proof can be found Appendix G
Theorem 3.8. Assume that 3, Ti sufficiently large and is sufficiently small (see Appendix G Then, VT 2 Tí.
(V A) 2) 0
A:E
N2
BN2
Corollary 3.9. (Convergence to the solution of the KRR problem) Under the assumptions of the previous theorem, we have the following dimension-fres bound:
Elfr f21le, 20(e -0(--00-00 ((T=-1))))
A +
A
Net
N
BN
This bound is dimension-free thanks to functional treatment and exponentially decaying to small value with iterations and therefore justifies the observed rapid convergence of gradient boosting algorithms in practice even though dimension of space H. is enormous.
GAUSSIAN INFERENCE
So far, the main result of the paper proved in Section 3.5 Ridge Regression problem, which can be interpreted as learning Gaussian Process posterior mean f under the assumption that f ~ us the posterior variance. Still, as mentioned earlier, we can estimate the posterior variance through Monte-Carlo sampling in sample-then-optimize way. For that, we need to somehow sample from the prior distribution GOP o2 + 8'ld,,).
shows that Algorithm solves the Kernel
o² where X = 52 Lee,, Algorithm does not give
4.1 PRIOR SAMPLING
We introduce Algorithm 3 for sampling from the prior distribution. SamplePrior generates ensemble of random trees (with random splits and random values leaves). Note that while being random, the tree structure depends on the dataset features XN since candidate splits are based on XN.
Algorithm SamplePrior(T;, m, n)
byper-parameters: number of iterations T,
parameters of SampleTrre m,n
instructions:
initialize T = 0, ho(r)= =
We first note that the process hT(.) is centered with covariance operator K::
repeat
24 = SampleTree(DPxx) (Dp:: m, sample random tree
Ehr(z) = O Vx E X, Ehr (x))((()()) KC Vz,yE X.
NN(ORer diag max .1)
(5)
{1, {1.....,II.) I.,
generate random values
Then, we show that h-) converges to the Gaussian Process in the limit.
in leaves
h-+1(-) = h-(+) + + (-), R
Lemma 4.1. The following convergence holds almost surely in X;
update model
= T + 1 until > T
hr(-)
GP (P(0Lz(0), T-x
return: hr(-)
4.2 POSTERIOR SAMPLING
Now we are ready to introduce Algorithm 4 for sampling from the posterior. The procedure is simple: first perform To iterations of SamplePrior to obtain function hr, (-) and then train standard GBDT model fr, approximating y ohn, xx))= + (Oxx,, 821x). Our final model is alr,, (+) Fr (.).

---

Published as a conference paper at ICLR 2023
(a) D
(b)
(c) log
Figure 1: KGB on synthetic dataset.
We further refer this procedure as SamplePosterior or KGB (Kernel Gra- dient Boosting) for brevity. Denote
Algorithm 4 SamplePosterior(z::, Ti, To, m, n, 3, 0,
input: dataset (XN:yN)
hyper-parameters: learning rate > 0, boosting iter- ation Ti, SamplePrior iterations To, parameters of Sam- pleTree m, n, B. kernel scale a > (default a 1).
h00 lim ITo Jox lim STS: To-
where the first limit is with respect to the point-wise convergence of stochas- tic processes and the second one with respect L2(p) convergence.
noise scale 5 > 0 (default: 0.01)
instructions:
hr, (+) SamplePrior(To, m.
yR = yN olr, (xN) + +O(00, (000x,82 8²
The following theorem shows that KGB indeed samples from the desired poste- rior. The proof directly follows from Lemmas 4. and 2.11
fr. (-) TrainGBDT (XN.YN"))
return: alrr, (-) fr
Theorem 4.2. In the limit, the output of Algorithm ffoorithmmfoolooss the Gaussian process posterior:
ahx()) + N(0, ~ GP(FRR)
with mean f(x) = ((z,,N) + AUN) YN and covariance K(æ, x) = 82 +
o² (K(zx))) X(,,)) ANN) (K(x))(()
EXPERIMENTS
This section empirically evaluates the proposed KGB algorithm and shows that it indeed allows for better knowledge uncertainty estimates.
Synthetic experiment To illustrate the KGB algorithm in controllable setting, first conduct a synthetic experiment, For this, we defined the feature distribution as uniform over = {(x, y) E [0, 1]2 10 (xr 2 (y ) < A (x < v 2 3) A (y S V 2 }) We sample 10K points from U[0 1f2) and take into the train set only those that fall into D). The target is defined as f(x, v) = x + Figure (aa) illustrates the training dataset colored with the target values. For evaluation, we take the same TOK points without restricting them to D.
0.1, = 4, n 64, and sampled 100 KGB models. Figure ((b) shows the estimated by Monte-Carlo posterior mean j.. On Figure [c)) we show log ã. where o² is the posterior variance estimated by Monte-Carlo, One can see that the posterior variance is small in-domain and grows when we move outside the dataset D, as desired.
For KGB, we fix 0.3, To = 100, Ti = 900,
10-2
Experiment on real datasets Uncertainty estimates for GBDTs have been previously analyzed by Malinin et (2021). Our experiments real datasets closely follow their setup, and compare the proposed KGB with SGB, SGLB, and their ensembles. For the experiments, we use several standard regression datasets (Gal Ghahramani 2016). The implementation details can be found in Appendix The code of our experiments can be found on GitHub
8

---

Published as a conference paper at ICLR 2023
Table I: Predictive performance, RMSE
Table 2: Error and OOD detection
Single SGLB
Ensemble SGLB
PRR SGLB
AUC
Dataset
Dataset
KGB
SGB
KGB
SGB
KGB
SGLB
KGB
Boston
3.06
3.12
2.81
3.04
3.10
2.82
Boston
36
37
43
80
80
88
Concrete
5.21
5.11
4.36
5.21
5.10
4.30
Concrete
29
29
37
Energy
0.57
0.54
0.33
0.57
0.54
0.33
Energy
36
31
60
100
100
Kin8um
0.14
0.14
0.11
0.14
0.14
0.10
Kinšnm
18
19
20
45
45
41
Naval
0.00
0.00
0.00
55
35
Power
3.55
3,56
3.48
3.52
3.54
3.43
Power
8
9
31
72
73
76
Protein
3.99
3.79
3.99
Protein
30
29
Wine
0.63
0.63
0.61
0.63
0.63
0.60
Wine
25
19
37
74
72
87
Yacht 0.82
0.84
0.52
0.83
0.84
0.50
Yacht
74
78
86
60
Year
8.99
8.97
8.97
8.93
8.94
Year
30
30
32
We note that in our setup, we cannot compute likelihoods as kernel I. is defined implicitly, and its evaluation requires summing up among all possible trees structures number of which grows as (nd) which is unfeasible, not to mention the requirement to inverse the kernel which requires O(N2+=) operations which additionally rules out the applicability of classical Gaussian Processes methods with our kernel. Therefore, typical Bayesian setup is not applicable, and we resort to the uncertainty estimation setup described in Malinin et al. (2021). Also, the intractability the kernel does not allow us treat o, in fully Bayesian way, as it will require estimating the likelihood. Therefore, we fix them as constants, but we note that this will not affect the evaluation metrics for our setup they are scale and translation invariant.
First, we compare KGB with SGLB since they both sample from similar posterior distributions. Thus, this comparison allows to find out which of the algorithms does better sampling from the posterior and thus provides us with more reliable estimates of knowledge uncertainty. Moreover, we consider the SGB approach as the most "straightforward" way generate an ensemble of models.
In [ we compare the predictive performance of the methods. Interestingly, we obtain improve- ments on almost all the datasets. Here we perform cross-validation to estimate statistical significance with paired t-test and highlight the approaches that are insignificantly different from the best one (p-value > 0.05). Then, we check whether uncertainty measured as the variance of the model's pre- dictions can be used to detect errors and oof-oann inputs. Detecting errors can be evaluated via the Prediction Prediction-Reecctinn Ratio (PRR) (Malinin, 2019; Malinin et al. 2020). PRR measures how well uncertainty estimates correlate with errors and rank-order them. Out-of-domain (OOD) detection is usually assessed via the area under the ROC curve (AUC-ROC) for the binary task of detecting whether sample is OOD (Hendrycks & Gimpel 2017). For this, one needs OOD test set. We use the same OOD test sets (sampled from other datasets) as Malinin et al. (022). The results of this experiment are given in Table 2] We can see that the proposed method significantly outperforms the baselines for out-of-domain detection. These improvements can be explained by the theoretical soundness of KGB: convergence properties are theoretically grounded and asy-ttomp..i.c. trast, for SGB, there are no general results applicable in our setting, while for SGLB the guarantees are asymptotic. In summary, these results show that our approach is superior to SGB and SGLB, achieving smaller values of RMSE and having better knowledge uncertainty estimates.
con-
6 CONCLUSION
This paper theoretically analyses the classic gradient boosting algorithm. In particular, we show that GBDT converges to the solution of a certain Kernel Ridge Regression problem. We also introduce a simple modification of the classic algorithm allowing one to sample from the Gaussian poste- rior. The proposed method gives much better knowledge uncertainty estimates than the existing approaches.
We highlight the following important directions for future research. First, to explore how one can control the kernel and use it for better knowledge uncertainty estimates. Also, we do not analyze generalization in the current work, which another important research topic. Finally, we need to establish universal approximation property which further justifies need for functional formalism.
9

---

Published as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
Susan Athey, Julie Tibshirani, and Stefan Wager. Generalized random forests. The Annals of Statis- tics, 47(2): 1111-114881....
2019. 2019.
Matej Balog, Balaji Lakshminarayanan, Zoubin Ghahramani, Daniel M. Roy, and Yee Whye Teh. The Mondrian kernel. In 32nd Conference on Uncertainty in Artificial Intelligence (UAI), 2016.
Christopher JC Burges. From RankNet to LambdaRank to LambdaMART: An overview. Learning, 11(23-581):88 2010.
Rich Caruana and Alexandru Niculescu-Mizil. An empirical comparison of supervised learning algorithms. In Proceedings of the 23rd International Conference on Machine Learning, pp. 161- 168. ACM, 2006.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. In Advances in Neural Information Processing Systems, volume 22, 2009.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2019.
Jerome H Friedman. Greedy function approximation: gradient boosting machine. Annals of
Statistics, pp. 1189-1232, 2001.
Yarin Gal. Uncertainty in Deep Learning. PhD thesis, University of Cambridge, 2016.
Yarin Gal and Zoubin Ghahramani. Dropout as Bayesian Approximation: Representing Model Uncertainty in Deep Learning. In Proc. 33rd International Conference on Machine Learning, 2016.
Yury Gorishniy, Ivan Rubachev, Valentin Khrulkov, and Artem Babenko. Revisiting deep learning models for tabular data. In Advances in Neural Information Processing Systems 34 (NeurIPS 2021), 2021.
Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. In International Conference on Learning Representations, 2017.
Bulat Ibragimov and Gleb Gusev, Minimal variance sampling in stochastic gradient boosting. Ad- vances in Neural Information Processing Systems, 32, 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel:
Convergence and gen- cralization in neural networks. Advances in Neural Information Processing Systems, 31, 2018.
Ryuichi Kanoh and Mahito Sugiyama. A neural tangent kernel perspective of infinite tree ensembles. In International Conference on Learning Representations, 2022.
Liran Katzir, Gal Flidan, and Ran El-Ya..y. Net-DNF: Effective deep modeling of tabular data. In International Conference on Learning Representations, 2021.
B. Lakshminarayanan, A. Pritzel, and Blundell. Simple and Scalable Predictive Uncertainty Es- timation using Deep Ensembles. In Proc. Conference Neural Information Processing Systems, 2017.
Jaehoon Lee, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak, Sam Schoenholz, and Yasaman Bahri. Deep neural networks as gaussian processes. In International Conference on Learning Representations, 2018.
Jachoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Journal of Statistical Mechanics: Theory and Experiment, 2020.
10

---

Published as a conference paper at ICLR 2023
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances in Neural Information Processing Systems, 31, 2018.
David G. Luenberger. Optimization by Vector Space Methods. John Wiley & Sons, 1969.
Andrey Malinin. Uncertainty Estimation in Deep Learning with application to Spoken Language Assessment. PhD thesis, University of Cambridge, 2019.
Andrey Malinin, Bruno Mlodozeniee, and Mark Gales. Ensemble distribution distillation. In International Conference Learning Representations, 2020.
Andrey Malinin, Liudmila Prokhorenkova, and Aleksei Ustimenko. Uncertainty in gradient boosting via ensembles. In International Conference on Learning Reprexentations, 2021.
AG de G Matthews, Jiri Hron, Richard E Turner, and Zoubin Ghahramani. posterior sampling for bayesian linear models. In NeurlPS Workshop on Advances in Approximate Bayesian Inference, 2017.
Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. CatBoost: unbiased boosting with categorical features. Proceedings of the 32nd Inter- national Conference Neural Information Processing Systems, pp- 6638 66-86648, 2018.
C.E. Rasmussen and C.K.I. Williams. Gaussian Processes for Machine Learning. The MIT press, 2006.
Matthew Richardson, Ewa Dominowska, and Robert Ragno. Predicting clicks: estimating the click- through rate for new ads. In Proceedings of the 16th International Conference on World Wide Web, pp. 521-530. ACM, 2007.
Byron P Roe, Hai-Jun Yang, Ji Zhu, Yong Liu, Ion Stancu, and Gordon McGregor. Boosted decision trees as an alternative to artificial neural networks for particle identification. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associ- ated Equipment, 543(2)5577-584, 2005.
Aleksei Ustimenko and Liudmila Prokhorenkova. SGLB: Stochastic Gradient Langevin Boosting. In International Conference on Machine Learning, pp. 10487-10496. PMLR, 2021.
Qiang Wu, Christopher JC Burges, Krysta M Svore, and Jianfeng Gao. Adapting boosting for information retrieval measures. Information Retrieval, 13(3):254-270, 2010.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint arXiv:1902.04760 2019.
Yanru Zhang and Ali Haghani. A gradient boosting method improve travel time prediction. Transportation Research Part C: Emerging Technologies, 58:308-323 324, 2015.
Difan Zou, Pan Xu, and Quanquan Gu. Faster convergence of stochastic gradient langevin dynamics for non-log-concave concave sampling. In Uncertainty in Artificial Intelligence, pp. 1152-1162. PMLR, 2021.

---

Published as a conference paper at ICLR 2023
A NOTATION USED IN THE PAPER
For convenience, let us list some frequently used notation:
C Rd feature space;
d dimension of feature vectors;
Y C R target space;
p distribution of features;
N number of samples;
2 = (XN:yM) - dataset;
V - set of all possible tree structures;
Ly : - N number of leaves for E V;
((v, score used choose split (3);
S indices of all possible splits;
n number of borders in our implementation of Sample'Tree .
m depth of the tree in our implementation of SampleTree;
3 random strength;
learning rate;
A regularization;
F space of all possible ensembles of trees from
Φu X 10, tree structure;
d indicator of j-th leaf;
v()) empirical error of a model f relative to the best possible I' e F;;
k,(s) ) - single tree kernel;
K(.,-) stationary kernel of the gradient boosting;
p(-IS. B) distribution of trees, f F;
x-) l p(- B) p(-1f,, stationary distribution of trees;
kernel scale.
The following diagram illustrates the kernels introduced in our paper:
Weak learner' kernel ku, X x X R4,
asssss f-ke, f(xN) Ear F
expected valiee
F
expected value
Iteration kernel K,, X' X R4
Stationary Kernel KC X' X - RR+
used doi product
71 = (F)))
B ADDITIONAL RELATED WORK
Let us briefly discuss some additional related work. Mondrian forest method (Balog et al. 2016) and Generalized Random Forests (Athey et al. 2019). besides having links to the kernel methods, in fact, have the underlying limiting RKHS space that is much smaller than the space of all possible ensembles built the same weak learners due the independence of the trees that are added to the ensemble. Therefore, there an issue of high bias when comparing plain gradient boosting with the plain random forest method. Also, these methods are built from scratch to obtain RKHS
12

---

Published as a conference paper at ICLR 2023
interpretation while provide link between the existing standard gradient boosting approaches to the kernel methods, i.e. we do not create novel gradient boosting algorithm but rather show that the existing already have such link to derive convergence rates and to exploit such linkage to obtain formal Gaussian process interpretation of the gradient boosting learning to get uncertainty estimates using well-established gradient boosting libraries.
Let us mention that there are approaches that study kemelss induced by tree ensembles through the perspective of Neural Tangent Kernel (Kanoh & Sugiyama, 2022). though this analysis is not applicable for classical gradient boosting, while ours is.
Let us also briefty discuss the papers on Neural Tangent Kernel, e.g., Pa.ot et al. 2018); Li & Liang 22018); [llenn-Zhu et al. (2019); ; Du et al. (2019). that study deep learning convergence through the perspective of kernel methods. Though such works share similarities with what we do, there are fundamental differences. First, our work is not in the over- paramettrization regime, i.e., our kernel method correspondence works for tree ensembles with fixed parameters, but the correspondence is achieved as the number of iterations goes to infinity. It is worth noting that the kernel method perspective on deep learning basically establishes that each trained deep learning model is a sample from Gaussian Process posterior (Lee et al. 2020 2018: Yang 2019; Cho & Saul, 2009), i.e., is sample-ther then-optimize. For boosting, we achieve this only by introducing Algorithm 4relying on Algorithm Bl which in its essence, is random initialization for gradient boosting. The classic gradient boosting (A (Algorithm{2 ( can be considered as the mean value of the Gaussian Process, which has no analogs in the world of deep learning, and to achieve convergence to posterior mean there, one needs to average among many trained models. This can be considered as an advantage of gradient boosting over deep learning that we derive in our paper.
C CONVEX OPTIMIZATION IN FUNCTIONAL SPACES
In this section, we formulate basic definitions of differentiability in functional spaces and the theo- rem on the convergence of gradient descent in functional spaces. For the proof of the theorem and further details convex optimization in functional space, the reader can consult Consult(Leenberger (969)..
We consider H. to be a Hilbert space with some scalar product (.. Definition C.1. We say that F H - R is Fréchet differentiable if for any f H there exists bounded linear functional Ly H + IR such that Yh E H.
F( + h)) = F(J) + [,] + o(1)
The value of Ly H. + R is denoted by DfF(f) and is called a Fréchet differential of F at point
f. So, Fréchet differential is a functional D H + B(H, R), where B(X, denotes a normed space of linear bounded functionals from X to Y.
Definition C.2. Let : + be Fréchet differentiable with a Fréchet differential Dj FJ) that is a bounded linear functional. Then, by the Riesz theorem there exists a unique hy such that (D, [k] (hy, h) vh E H. We call such element gradient of F in H at f E H. and denote it by FxF(f) = hy H.
Definition C.3. F H + R said to be twice Fréchet differentiable if D Fréchet dif- ferentiable, where the definition of Fréchet differential is analogous to Definition C.I with the only difference that F takes values B(H, The second Fréchet differential is denoted by D3FFF H. B(H, B(H H. R), we can consider the second Fréchet differential to take values in B(H x H, R). Henceforth, we will not differentiate between B(H, B(H, R)) and B(H x H, R).
As there is an isomorphism between BHH, B R)) and
Definition C.4. A linear operator : H H - is said be semi-positive definite (denoted by P = 0) V f H we have P(f, 2 0. P is said to be positive definite (P 0) if V E H. \ (0) we have f) >>>>0 O.
Definition C.5. Given two linear operators P,G: x H - R we write P> Gif G 2 0 and P
Gf P G > O.
Let E B(H x H, IR) be linear operator defined [gg, = (g,
Theorem C.6. Let F be bounded below and twice Fréchet differentiable functional on a Hilbert
space H. Assume that D3F F()) satisfies 0 x ml N D3 F(J) I pl. Then the gradient descent
13

---

Published as a conference paper at ICLR 2023
scheme:
fk+1 = -
converges to Ja that minimizes F.
Proof. For the proof see Luenberger 1969).
D KERNEL RIDGE REGRESSION AND RKHS
Definition D.1. K. : x - is called kernel function is positive semi-definite, i.e., VV E N VxN E XA K[XN, XN) ž O.
Definition D.2. For any kernel function we can define Reproducing Kernel Hilbert Space (RKHS)
H(K) = span ( x
with a scalar product such that
(f (f.K(;))))((K)) = f(x).
Consider the following Kernel Ridge Regression problem:
V( = 2N IyN [(xN)
[1 min V(SA)
min fEH(K)
2N
SEH(K)
and the following Kernel Ridgeless Regression problem:
V()) 2N ly - [(xN)] min V() + min
SEHIK)
SEH(K)
Lemma D.3. ming(r)) V(S, A) has the only solution
f. ( (K(XNN)(((NNNN)) A yN.
Proof. First, let us show that l E span {K)) Let H(K) = span {K(+) @ span (K((, ax)) and consider the projector P H(K)) + H(K) onto the space span {K(,, x;)]. is easy to show that ((f)(x)) = f(xN) for any f E H(K)). Indeed,
(S - [[-()]) (S- P()) xN)) =0
If fA does lie in span (K)) then (1(xk))(()) [|P(f))lmm)) and V(P(f.), V(f., A). We get a contradiction with the minimality of f..
Now, let us prove the existence of f... Consider KC,, XN)c, where E RR Then, we find the optimal e by taking a derivative of V(,A) with respect to e and equating to zero:
(X)(N xN)c UN) + XC((x,,N)c== 0.
Then,
C, (N((N,,NN - u),
where a E ker IC(x,, xy). Note that all KC(, )c are equal. Then, we have the only solution of the KRR problem:
S = K(,,x))(((Xx, + -yN-
Lemma D.4. min V(f) has the only solution in span ([((,x))) and is the solution of min- imum RKHS norm:
f. ((xxx))
14

---

Published as a conference paper at ICLR 2023
Proof. Consider f K(.,xx)( where E R Now consider V(f) and differentiate it with respect to c. If we equate the derivative to zero, we get:
N
YN) =0.
Then, K(xN, XN xx)c- Ny +u) - 0 some v E ker (x),,xx) Note that yN ker K(XN: XN) Im KX,,, xN) * 0. Then, for any such that yN + E Im K(x,, XN) there exists solution ((xN, Xx (yN + v) + ker ([xN, xx). This follows from the fact that K(xNN, XN K((N,, xN) an orthoprojector onto Im K[x,,, Xy). Note that
S. (x)(xxx xN) (yN + v) ker K(xN,xN)) = (xx,
Then, the existence and uniqueness of f. follow.
Now, consider linear space L2(p) of all possible ensembles of trees from V:
F span (.) {0.1) tul)
Define the unique function:
(f+) lim arg min V(f,)) C arg min (()). x- fEF
JEF
Then following two lemmas hold: Lemma D.5. (y [x(x)) = 0 for any f E F.
Proof. Assume that (y Lo (x(x),, (XxN))RN * O for some ʃ E F. Then, for some / E F,
(yN fx(x)), f(xN) O. We have:
Ilyn - (f. + axn)
= Ilyy - (x 20(yN f((x)); + =211f(xxN)) +x]] )|
< Ily [xNN))l
for small enough a > 0, which contradicts with the definition of f..
Lemma D.6.
V(f,) 1
2N [xf((x)) f(xN)1
2N 115 Cx
where Cx inn JEF L(f,A) -in JEF L(f) 2
Proof. We need to prove it only for V(f) without regularization as for regularized it follows imme- diately (note that fa is minimizer of not regularized objective). By definition,
1 v(f) = 2N lyy f(xN)11
lly - f=(xx)llEx.
2N
Now, let us prove that
Ily - [(xN) Ily - f [1fx(x))
((x)) -00-0---0---------0010----00-0)1 0.
Indeed,
Il f(xN) - - -1fp://ww_11((xx=-11-1___>> fxx))le
= =_2( - 2 (x(x))) + (xx),(xx),
=-2 f.(xx), (o.))-(x(xx))) [x(x))) =0,
where the last equality follows from the previous lemma.
Lemma D.7. V(S,)) 1122 ((xx) + A 1152 -1122
15

---

Published as a conference paper at ICLR 2023
Proof. f2 is optimum for V(f, A). Then Fréchet derivative f2 equals O:
Consider then writing:
V(S.)) = + - fa] 1 D - 1.1
À
2N 1f f(x + 2N
fxx))l
The explicit formula for the Fréchet Derivative of V A) can be found in Appendix
E GAUSSIAN PROCESS INFERENCE
In this section, we prove Lemma 2.1 from Section 2.3 of the main text.
Firstly, consider the following regularized error functional:
V(J.)) = 2N
1 (s(z)) vi)
|5
min FEH(K))
( -i))+
A 2N l
2N
2N
With this functional we can consider the following optimization problem:
min V(f.A), SEN(K)
which is called as Kernel Ridge Regression.
We will show that this functional satisfies the conditions needed for Theorem C.6 We will also deduce the formula of the gradient of V in order to show that gradient descent takes the form 2
Lemma E.1. (f, is Fréchet differentiable with the differential given by:
N (f(x)) eU,,
1
DyV(f.)) NN:: (F: +
N
where evu H(K) + IR is bounded linear functional such that evn, (f) f(x;) (f,K(z;)
Proof. As Fréchet differential is linear, we only need to find Fréchet differential for (f(x;) - y1)
Note that (f(x;) y;) is composition of two functions:
F: H((A) + R, = etp, - V
G - R, G(z) = x²2
The differential of the composition be found
DjG(F()) =
Fr. G(FU))D,FU)) D)G(F())) = ((((r) - y:)evs;
where FfF(f) CUx, because
eU2, (f+h) yi EUz (f) - ys + cvn. (h)
Lemma E.2. The gradient of V(J,)),. Riesz representative of the functional above, is given by:
X f 1
N (f(x.) V.)
V,V(FA))
We further the notation Kzz, := K(.
16

---

Published as a conference paper at ICLR 2023
Proof. Follows from the previous lemma.
Lemma E.3. Af is twice Fréchet differentiable with the differential given by:
DJV: H(K) ((H((C), ((H()))
N
DiV( = N /h, June + N h(r;)eva,
Σ
Proof. Due to the linearity of Fréchet differential and lemma E.1 we need to find only Fréchet differential for (f(x,) y22,.
Consider S(f) = (f(x;) - y/ evg. Then we need to find Vy E ((H(K), S(f+ + h) = S(f) + Vy[hi] ((Ilb])).
such that
It easy to show that + h(,,)e0,, E B(H(()), (CH) R)) and S h)) = S(J) b(r)) Thus, get that [A) = h(rz)eU,, From this the statement of the lemma follows.
Given all the above lemmas, as a corollary of Theorem C.6 we have the following. Corollary E.4. Gradient descent, defined by the following iterative scheme
f++1= = (1- de converges to the optimum of V(f, A). Thus,
Xx ) E (f(())) Kz) fo 010(e)
f = lim fr k((,xN) (K(XN, + +ANN) yN. T
(6)
Proof. By Lemma
22
update rule has the form
fr+1 fo (f.,
Then, we will find m, μ such that 0 < ml = 3 (3V( I μT. By Lemma E.3
>
D3V(S,N)lo h| = N
(g. h) + (
Then, can take
N. Let us also write
N llg ( 1 |l((x))11= X
N ll (10)) + } ll (N))
X + max K(I,, 11)l
1
( N
Then, can take μ N + maxxex x)x, By theorem C.6 and lemma D.3 the corollary follows.
Lemma F.S. Consider the gradient descent:
de
fr11= (1=
N ffrr
Σ (fr(z,) M.)K
fo OL)(p)
fz. = lim fr
and the following randomization scheme:
1. sample finit ~ CP x2C+ + 1ld1)));
2. new labels new yNN pinit (xN);
fit GD f-(.) on y noe assuming fo(:) = Dzg(o)i
4. output f(.) pinit (.) f.o( as final model.
17

---

Published as a conference paper at ICLR 2023
Then, ff from the scheme above follows the Gaussian Process posterior with the following mean and covariance:
(N(x)((((K ([(xN,xN) + +NN) -1 +1xx "xx "x(x),)))
Ef(x) K(a,,xx xN)
yN,
K((x, cov(f(x)) 82 o² - (N(xx,,NN)
Proof.
fso = x((xxN) (K(X)))K(K,
YN ynew xx) (K(Xx, (K " (yNN pinit (inniiin(xx) (xx)).
Let us find the distribution of f at R". It can be easily seen that:
Ef(x)= = K(z,x(())))))) (K(XN, + Alx) YN.
Let us now calculate covariance:
cov)(x) = I(f(x) (())
-
(C((NN,N)) ((,,,,) + +NN) -1 (imit(xx)
=((fin((x) - x(xxxN)
(f) K(z,xN) (K(XN, + AlN)
pinit (XN))
E pini (x)
(x:) (intt
E (x)) (XN) (C(XN,XN) + Mlx) k((N,2))
- K(e,, xNv (K(XN,NN) ANN)
(int)
+ K(x,, xN) ( (K(XxN xN) + ANN) " (x (XN)) (K(Xx, XN) + +NN
k((xN,))
= 6" + (K(x, x)) - (N)) ANN)
XN + o x() = 82 0² (K( (K(x, K(o, + ANN) (W))~K((xN,a))
ANN)
which is exactly what we need.
F DISTRIBUTION OF TREES
Lemma F1 (Lemma 3.2 in the main text).
p(v1,,3) Σ SEP s= EsES
D((k,.-1-)).)
8
where the sum is over all permutations S Pmo Vs (84(1)..... sc(1)) and ($1, Sm).
Proof. Let us fix some permutation Pm. W.l.o.g,, let < idp... i.c. <(i) iii. It remains to derive the formula for the fixed permutation. The probability of adding the next split given the previously build tree is:
e D(
E EvESY ed D((V(-1,))))))
which comes from and the Gumbel-SofttMa trick. Then, we decompose the probability P(v) of tree as:
P(v) = II m
P((--1s((Pt-)))
1=1
18

---

Published as a conference paper at ICLR 2023
and for the fixed permutation have
3 D(u.i)
P(v) - II
i=1 EsEs et (((())))))
Then we sum over all permutations and the lemma follows.
Now, let us define the following value indicating how different are the distribution of trees for f and fe:
plulf 3) p(vlf. 3)
p(v(f,8) p(vlfr,8)
[s(f)
max
max WEV
max NEV
Lemma F2. The following bound relates the distributions.
Po(f) S vm)
Proof. Consider p(-1f.. B) and the following expression P(v,s):
e D(ps...r)
P(u,s)
E sEs D((vGa-1()))))
Then,
Σ p(v.s)
Σ E D(v,r) II
m
2mV(f)
T(V).
E 20
SEPm
where in second inequality we used D(v,r) I (f) which straightly follows from the definition.
By noting that the probabilities remain the same if shift D(.r)) D(.rr) (f) which becomes everywhere non-positive and allows us to do the above trick once more but in reverse manner: if we formally replace the D with such modified function and repeat the steps with reversing the inequalities which is needed since the new function is everywhere negative then the lemma follows.
Σ p(v,s) Σ 3 D(( <EP...
2mV())
TTV).
Exeske
<EP...
G PROOF OF THEOREM 3.8
G.1 RKHS STRUCTURE
In section 3.4 we defined RKHS structure on as:
())K(,))))H0) = f(x)
and introduced the kernels ky K,, Kr. Let also define kernel - (c(:))p(v))
for arbitrary distribution on V. This way, taking 8.).), p(u f. 3). T(-) we get Kyp equal to ky, KJ,, K., respectively.
For each kernel, we define the operator associated with it denoted similarly:
f / x,(()))(())(((r))
Lemma G.1. Consider two positive semidefinite operators on finite dimensional vector space V: A: V V and B : V V such that A B. Then, Tm A > Tm B.
Lemma G.2. Kn F - F is invertible for non-vanishing V.
19

---

Published as a conference paper at ICLR 2023
Proof. Note that Im ky span fo? j 1.... Lu and p(y)k, = Kpp Then, Im Kp F follows from lemma G.1 Thus, x is invertible.
Lemma G.3. F span (K)(;;)) | E X) for p non-vanishing V.
Proof. From lemma G.2 Im Kp F. From the definition of the operator, InK, span (x))) x E j. Then, the lemma follows.
Lemma G.4. For non-vanishing distribution p on
(KPJ-D)HKK,)) (f:9) L2(0)-
Proof. It is sufficient to check on the basis. So, we take = Kp(,, 2:). Then, (x, H(K,), = k,(f((z)= = (f. ( where the second equality holds by the definition of the operator Kpp
For weak learner v, we define covariance operator:
[n / (.o()x))f(xx) Ey 71 H.
Also, for an arbitrary probability distribution p over V, we denote Exp Evey Eup(v). These operators are typically referred to covariance operators.
Let us formulate and prove several lemmas about the RKHS structure and operators Σ, Ej, Ey.
Lemma G.5. (Courant-Fischer) Let A be an n n real symmetric matrix and \ S ... An its eigenvalues. Then,
A = min max RA (3);
dimU DEU
0 dimt! 141 aCU
max
min RA(x))
where Ra(x) = (Az.z) is the Rayleigh-Rizz quolient. (2,2)
Lemma G.6. (x,,(xN, xN)) (xN, xx)] = for any u V.
Proof. It is easy see that
(xN, = 0 ( NexN:
where 1 1xn is matrix of size x consisting of ones. Then, we note that || and now the statement of the lemma follows.
Lemma G.7. (Covariation majorization) The following operator inequality holds for probability distributions p. over V, where p is arbitrary and p' does not vanish any v E V:
Amax EEp) $ 1,
Amin (2w) 2 N
Proof. Consider the following operators:
A: F - R" f + f(xN),
B: RR" - F, G + Kpl:, xN)..
Then, Σ,p B and KN Kx,, xN) ABB As AB and BA have the same spectra, we further study the spectrum of KN-
We have KN K, XN) Evey 1o (xN, (p(v) and Amaz (KN) S follows from lemma G.6 Then, Xmar (Ep)) < follows.
20

---

Published as a conference paper at ICLR 2023
Now need to show that Amiu (Ep') 2 N Consider the following formula:
N
E
Kpp (5 Buikp) (x;),
N
1 N
Kpr (..2i)))
Ky (1.20)))))
(H(x))))) where (a @H(p,) b][c (b, C)XK,, I b and |all)((,,)) 1, then and 0 are the only eigenvalues of (H(Kp))) a.
2
Σ ==1
(Fi x;)
N
v Kyp (ris vie)
v Kep (ri, v3/)
Denote by S span (Kpp (x 22) | =1=1 I.....N) c H(K))) and m dimS, n dim?l(KKpp)) Then,
Amin (Epp) = Xn-m+112pp dimU=n
min
max Rs (x)) DEU
where (x)
dimU = n m + 1, then UNS + Ø. Suppose (;, E u(x,)
U U.SS then
max Rx (1) 2 Bry, Kgr ZEU
Kyp (Ti, Iz)
VKg (Kg,
N
N
where (*) is fulfilled as a (H(K)))) a positive semidefinite operator and the last inequality follows
from Kep (x,x) 2 1 Vo E X.
G.2 NORM MAJORIZATION
The following lemmas relate the norms L2, H. R with respect to each other Indeed, by these lemmas we can consider the bound || 11,,, S 1Iæ I || I|RN. Further, in the main theorems we will use these relations extensively.
Corollary G.8. [x.f(x)) 2 Il for f e (pan((((,, | 1, I,...,Ny N7.
Proof.
N [[f((x)]l= = | 11f
1
as Σ > I on span (K(, N..
Lemma G.9. Amax (1)) max K(x,x))
Proof. Consider as an operator on (F, L2(p)). We will prove that [[]) S max K(x,,) x)) and the lemma will follow. Consider the inequality
{If((x) (Kz. fr I ta
Then, ||]]]|| S max || ||,, || Note also that K(x,, S min(K((a, a)), K(s', a()) which can be easily seen from the definition. Then, [|Az, & K(x, and the lemma follows.
Corollary G.10. (Expected squared norm majorization by RKHS norm) The following bound holds Vff E H:
l1 I max K(xx, x))111
wEX
Proof. We have
Amaz (K) 2 (Kf.fN (fifl1 115112..
Then, from the previous lemma the bound holds.
Note that
|| |la indeed becomes norm restrict our space span span(K((, | 1,..., N).
21

---

Published as a conference paper at ICLR 2023
G.3 SYMMETRY OPERATORS
In this section, we establish symmetry of various operators with respect to the norms L2, H, RR-. These results are mainly required claim that the spectral radii of these operators coincide with their operator norms in various spaces: B L2). BHH), (sspan ( Though, we use symmetry of operators not only this way.
L....,N,, }. ||
Lemma G.11. (Universal symmetry of covariance operators in H.) The operator En for any p is symmetric w.r.t. the dot product of (Hy) ) for any non-singular p'.
Proof. First, let us prove the statement for non-singular distribution p. To that, we consider the following quantity:
1 N
E (Kpls (Kac)
Then, we use the following trick: (Kp(,, SmUCK,,)) = (KGr Ko xz), (.), f' allows us to rewrite:
1
(2)))))(())) = N ( ( (2),
From this, immediately follows:
N Σp Σ KGpx SHIKg) (KG (x)p(())))))
This shows that Ep is indeed symmetric w.r.t. the dot product of H(Kgrr) Finally, we can use the continuity argument, which we can use due intrinsic finite dimension, conclude that symmetry must hold for arbitrary distributions, in particular for p = 6, which corresponds to E..
Lemma G.12. (Universal symmetry of covariance operators L2) The operator Ep for any p symmetric w.r.f. the dot product of L2-
Proof. We consider similarly the following quantity:
1
(EpfighuK,,)) = N
Then, we use the following trick (.) (K, KG (x 8 Lo. It alloos us to rewrite:
N
(Epf = N
Σ
KCp 21), (la, kpp(.
From this, it immediately follows:
Σ, Σ Kgp (p)))()))))) LL (p))K((()))))
Which shows that 2, is indeed symmetric w.r.t. the dot product of L2-
Lemma G.13. (Universal symmetry of kernel operators in H) The operator Kop for any p is sym- metric w.r.t. the dot product H.. H.
Proof. We consider decomposing Kip as:
(Kpf.g)L, = f Kola, ((la,,))((adol))(ataood
22

---

Published as a conference paper at ICLR 2023
Then, the following trick: f(x) (K((; f) It alloww to rewrite:
(K Seux xxxx
From this, it immediately follows:
Kp Kp= 30=JxxxXple Kpla, v) (K(,,) (K(,,) on K(. p(dz)) p(dt)))(t))))))
This shows that Kr is indeed symmetric w.r.t. the dot product H since both K(, x)) Gn (..)))) and K((,)) 8H K((, x)) are present with the same weight (z, p)p(dr) Kp x)
G.4 ITERATIONS OF GRADIENT BOOSTING
Lemma G.14. For any E V. we have xN)lyN- [x(xN)] = O.
Proof. Follows from Lemma D.5
Lemma G.15 (Lemma 3.7 in the main text). Iterations for of gradient boosting (Algorithm 2 can be written the form:
fat1 (1 Ac
fo (. [xx)]] [x (1 de 15. + c N
N (.xNN[fF((xN) (xx)],
N
N
v, ~ p(vlsr,0).
Proof. According Algorithm
2
(1) (Ii)r Lur
de [z() + (((d,,()))r)))) ()) for 0, [++1()) (1 N
Li=l
Lim D.. (Ix)) j=1
Thus,
Lur
f141 (1- ) +
Σ r
N
N
1: th, (x;)=1
Now note that ku, (1,24)) wh, Nr (.), where j is such that di, (xt) From this the lemma follows.
L
From Lemmas G.15 D.4 it is easy to show that fr, E (pan(K((,,z)) | I.....N). Then, hereafter Corollary G.8 to bound H. norm with RV norm.
Lemma G.16. The iterations of gradient boosting can be represented as:
E PPI Kr, s-] N ST.
where FF F is bounded linear operator defined as Riesz representative with respect to L2 scalar product of such bilinear function +x(xx)xxxxxx) (Df, 12- Similar decomposition holds for = [f] A.
Proof. First, observe that ft to ). Keep in mind that in the definition of VffrA), the norm in the regularizer term is taken with respect H(K,,)) instead of H(K)). Thus, we need only to prove that VxV(J,)
where gradient here is taken with respect
KDIf f-] f f.
Consider Fréchet differential Df f
(Dff f,),A) By
Lemma G.4 we deduce
1
(f(()
N (f(xN) fl(x))) (KDIf -
which implies VV() = KDDJ S.] and the lemma follows.
23

---

Published as a conference paper at ICLR 2023
G.5 MAIN LEMMAS
Lemma G.17. Let A, B E BHH, H) be two PSD operators such that EB - A and ξAA - B are PSD for some & E (1) Let g, H be two arbitrary vectors and E R++ be a constant. Then,
(A[g) Agh, Bly] Miix 2 ( |||[a]
+ Agh 1
- -(6 - -1(--1)))
Proof. Consider the following equality:
A + Xh, Blg] + Xh)
2 (11 - Algl + Abll + Blg] + Ah | - || - A>ga))
which is basically the classical decomposition of the dot product (a, 1) = 1 (1|==|| + |1 - || -
v..3). Then, we note that (1 3 B - (B - -- A) ( B) is PSD by assumption and
since (B g-____a___ 5-1A A) is PSD it implies that (1 (1-5-2) N [B 8
A), -A), which implies:
(A[a) + XEh B + X1) 2 (1|- Algl + AA 1 + BB4 + Mn -(1 (1 3
Finally, note that 2 2- 2 following equality:
1 (1 2/2
1 E 1. Then, the result directly follows from the
2-
|| [ + >MIl - (1 61-5-2)2 1
B|a||| ||
= =115-1 22 - B-
+
A
11 11
X²
g2
8- 2 - --
2
5-2
Denote s(A, B) = =I[d<æ BA- (1A-HI) = |I AAA1- (|,,,))))(,,1)))) Lemma G.18. !f--iK = K2 3 for > 1, then x(K,, -
Proof. First, we note that both operators are symmetric semi-positive definite in L2. Now, let us look at the Rayleigh quotient:
I1AC - -K)KK-
I - KC,) f
[I - ",C,),"C"
max SEFV(O)
SEF((U)
llfllx
lffl
In the last equality we used fact that K. symmetric positive definite and therefore K² too and hence we can substitute f t J and use the explicit formula for the dot product in H via the product in Lg. Now we observe that
(E - 1))dd, = - -x)x 3 K
(K-
=k - "K) - -1- 1 (5 1)Id
which implies that the spectral radius - -KC KC, )b) bounded by E - Therefore, we obtain:
||C ( KT)KK 3 fllee p(K =(K -K2)K -,)))())EE 5)
max SEF(/O}
11ʃ1lzz
Lemma G.19. Let A, E B(H, H). Then, the following inequality holds:
X² =(A, + Ab11 ,A, B)
(Aig) + Ah, Big + Xh) 2 2
|1h112
24

---

Published as a conference paper at ICLR 2023
Proof. Let rewrite the left part
[A[g]+ -h, Ah, B(g) + 2 = AA, (1L,, +M) - -BA 1
= =I|A[g] + Aa 1 - (A(g) + >h, (Idr.,- - BA BA- (A[0) + Ab))
(A[g) + Xı, X(Td,, -BA -BA-))A)
Then, we use the equality (a. b) (Ilal12 + ||6||2 - ||a -11) Also, we use
(A(g) + Ah. (Idr,- BA ( + X1))
- AAgl + Xbllxell - BA BA + Xn)lm
S ((A, B)] + AMI
to obtain
3
(A[g) + Mh, B[g] + Ah/H 2 (2 - (x(A.)) [[A[o] + 1ill
2²
2 [1 BA 1 2 [1([1 + +b) A(Id72 BA Malle
12
x(A,
||Alg] Nill2 [1(A[o] + Abi11
- =1(1d11 BA B)ll2
2
X2 x(A. ||4(g] + Aall ,A B)
2 ||
1
The following lemma holds.
Lemma G.20. If X + 1)c < 1 and fo O2t then V7 the following holds almost surely
Ilfr full s lf++ll
for norms Il ll 2l and || IRx..
Proof. Note that
de Id1, EEv. [f f.] F..
fr+1 fo= (Id12
Now observe that S = [Idı,- - de
N IdL,, -CEv,) is symmetric with eigenvalues 0 < (s) S 1 Ac
N
therefore its operator norm in (([2). B(H), and N is less than 1 de N- Taking the norm of left and right sides and using the sub-additivity of the norm, we obtain:
Ae
de
|| - f-ll s (1
N I|lf - f.ll + N ||f-11
Since I15o - full = [|f=|| that recurrent relation inductively yields the statement of the lemma.
Corollary G.21. Under the same conditions, || s fll
G.6 MAIN THEOREMS
Let us denote R ||fellex. We argue that it is a constant value since the kernel H. and fa are convergent as N
+ do which makes it bounded by some constant with probability arbitrary close to
onc. By Lemma F2 (ff se 2mV())
2m atx 1f+ f-112
RM
mn²
Then, (a(f+) Se
E and we denote
8 Mg = e N8
>
1.
Theorem G.22. Consider an arbitrary c, 0 c X + 1) 1 and (1+MAA) 4Mg
2 The following
inequality holds:
n²
1 2MgN
Te
EV(fr)
2N
M
1
4M₂ (M3
1) N 1
À
2X² 22 Mp(1
x )) n².
2N
14 M₁A
Ma
25

---

Published as a conference paper at ICLR 2023
Proof. To prove the theorem, we will bound V(f) - (Vf, const. It will allow to invoke
Lemma G.17 After that by using strong convexity we obtain a bound on (f)))M)))))))) and then a bound on LV (f+) will follow straightforwardly.
To get the result for (i Mad), we expand V(f++1, by substituting the formula for f++1 and first dealing with the term v(f++1):
1
1
1
2N [If++1(xN)= - (xx
2N [xx) fx(x))ll +
N (f++1(XNN)
- fxx(N), - f-(xN)) +
2N [1f++((XN) - fr (xN))
= =V(f- cEEu, - -.1++ N (r,KD[ - + 2N 1E 1s+ - -fa++ + X
X
à²
N J ll
X²e²
- (
[s- [-] + N 1r, KDIs- f.1)> + V(++) + N3 (xxx ) )
where we used the inequality ||a + B11 < +|||b=+ and Lemma G.7 which allows us to bound [En, (fr - -f.)lR I ll(f= - -f----)l-- fR)l.R.. Then, we analyze the regularization:
A_
A Malls: lire + (fr-1- Sv. Mafe N
de2
Ma 12i, [s+ - [+]+ A
Ma Mollf++alle
f- ll
2N
2N
2N
N
A Mol
el A
A
Mallf= - f.1lk + ex²
Matri Ev, Ev,lfr - Nr>H
N3 Mollf+ li
2N
N
N
S A 2N
2N MollEall x Mofr, Li,, 1fc - fo]+ N 1. + AA
4X²
N Mp +
N2 1l
N
where in the first inequality we used [Ev, f=lllx S - f- which is due to Lemma G.7 Summing up the expectations of those two expressions, we obtain:
-
M& 2N
(f Mad) EV +
Elfr+1ll3 -CMAAd
A
Ma
EV((+) cE Ur- S.] +
Nr.KDD - [J.]+
J+ + 2E7EV(
N
N
X22
X
2x
4X2
+
N3 (l) 12x +
M&E [f 11
M1 +
)llf+1 - -CMAA
2N
N
N2
< (1+ 2) (EV (f+) + MoE - CMON) - -EE(E, 15- - -f] A
-.K.DIF--J. -.. f-]
2N
Mad
X²22
N3 El]f((xN)] + ed
N Mc(1+ + 412
+ N fr) +
No 111.1112 + +2222MMN
< (1 + 22 EV)
- -EE(K,, ff]
N fr. - fal+ Ma
X
ft) +
262x ( 22
+ +Ma(1
2X²
N2 1) RR2
N
N N2
Here we used
x
inf inf je
inf L(F) < L(.)) = 2N fer
llf -
Rt2
2N
Then, by applying Lemma G.16 for > = Ky, D and applying Lemma G.17 with E = Ma. A = K.
B K g = DD f.l. and h = fr. we obtain the following bound:
>
M&d
- - -A]+ + n fr. - fJ++ N
STY
c VI, MaNIl + 2 SMa(MM (077-11.111 -1) X2
S S- 2Mg
A2 11 N2 R²
< 2Mg
+2cMo(M13
26

---

Published as a conference paper at ICLR 2023
Then, by using Polyak-Lojasiewiin inequality 2/I 2 (restricted on spen(K((,x;)) i = 1,...,NN) with 2 we obtain:
μV for j-strongly convex function V
L+MaA 0, which is due to Corollary G.8
N
X <KE fal+ NN (r,KD( f.]+ N
Mad
N
- - E MM +1
12 M&N (V, + 2cM 1)
1
N2 1t?
Substituting it into the bound on V(f+11, Mpd) gives:
[f
$ (1 d( M&R V())
26d
(Ma(M} -1 A
+c(
2X
+ +Ma(1 + N²)) R²
212
M&N
N
N
N2
1 MA
2Ed
2\
+ +M + 21²
- (1 E 2M
M&N)+ +
MM - 1) N
E
N2 1) R²
N
N2
which yields
EV S
R2
1+Mad IMgN
Te
4MaX
(Ma(M 1) N
+
tel No + Ma +
22
2
212
No 1))))²² n2²
2N
+ M&d
where we used the bound
R²
V(fo. M₂A) = V(O, = 2N (f.(x)) -MMpA I
2N
Next, we use the following inequality:
v(f) = L(f) min L(f) S L(f, MaA) min L(f. Mgd) + min M(F min L(f)
Mad R²
S VV.. + L(fe, [(f=) (of, +
2N
which finally gives us the following bound EV (fr):)
Rs
1+ M IM
EV
Te
2N
4MB
-1) A
4e
2>
212
+ Mad
+
(M3
+
+ Ma(11 + N2 1) R².
2N 1 Mad
N 1 Mad
N2
Theorem G.23. (Theorem 3.8
in the main text) Let C = M9d 1
EN + I+MaX
4Mgs
(M3 1) +
1+
4F
24 N
+ M1(1
+
> e, 3 (this bound can be achieved by taking 3 arbitrary large) and define
2x
No
R2, Assume that 0 < E( + 1) < 1 and 4Mg
(1+
(1+A)
2 E, e
AmC
8N
T =
2M
log 2CN
R²
+ 1. Then VT 2 Ti it holds that
[[+
AV N R2)e 4 (T
8A
AM + <(1 + 2X(1 + 11 R².
I+
N
N2
Proof. First, we apply the previous theorem to obtain bound on V(f=) which we will use to claim that the kerels Kf, and K. are close to each other expectation. If we take
2M
R² +1,
7i Le(1 + M₁Aj
log 2CN
then the following inequalities hold VT 2 Ti:
EV 2C,
27

---

Published as a conference paper at ICLR 2023
A EV A) S 2( N 182).
Then, analogously with the previous theorem, we estimate:
EV(f++1, (1 (1+22) EVV A) eEE f+]
+ N IT.KD - fa]+ J+) + 2621
X
21(1 + X)
N (1
R²
N2
Further, we bound (K, DIf, - f., - f.] 2 fr) by Lemma G.19
instead of
Lemma G.17 which we used in the previous theorem:
VT 2 Ti
A N=) -E( - f.I+ KD. fa]+
2mV
-1) 1) -1)- VV A)1B + E(e
2mV(f=)
11)
2N2 115 1
X²
3
I+>EV(S A)
2
22
R82
2
N
N2
2 +
AmC
-31+2)
-3
11
(V) + 2
R2
N
N
N2
4mc
1+
AV) +
2
R²
N2
1 A
2X
EV
R².
2N
N2
Substituting this in the formula, we get:
V7 Ti
EV(J++,, 5 (1-e( 1+1 Ev)
2Ed
XM3
21(1 + 11) 1T2
+ +e(1+
2N
N
N
N2
1+
2Ed
XM3
2X(1 + 11) RP.
< (1
+e(1+
4N
N
N
N2
Iterating the bound yields
( S A)e 122 (TT-TTT))
8A
+c(1 + 2A(1 + A)
R2
1 1+1 X
N
N
\ < 2C R2 4 (T-
8A
AM2
3
+ +c(1+
2X(1 + 2)
R².
N
1+1
N
N²
Corollary G.24. (Convergence to the solution of the KRR / Convergence to the Gaussian Process posterior mean finction). Under the assumptions of both previous theorems we have that
E| - 121 S max K((,, (AN(C+ ZEX
((N(CC
A A rt)e
1= JN (T-T1)
N
16NA
AM
2A(1 + 21
3
+e(1+ +
122
1+
N
N2
Proof. By Lemma D.7 V(f.))
= b - (xx)) - + NN
If
1.
Then, by the
previous theorem, we get bound 1 we majorize our L2 norm by Ry norm. Lemma then follows.
b Ellf((xx)
11 and by Lemmas G. and G.8
10hhen N -> XC converges to certain kernel. Thus, maxzex K(x, can be estimated with constant with probability arbitrary close one.
28

---

Published as a conference paper at ICLR 2023
Lemma G.25 (Lemma 4.1 the main text), The following convergence holds almost surely in X:
hr()) (P(DL2(o).
Proof. From (5). we have that the covariance of bo is I. independently from T. Thus, it remains show that the limit is Gaussian almost surely which essentially holds due to the central limit theorem almost surely in X:
T E (T.((x) - N ((L,,
hr(x)
VT
where each individual tree h centered i.i.d. (with the same distribution h1).
H IMPLEMENTATION DETAILS
In the experiments, we fix 10 (scale of the kemnel and 10-4 (scale of noise), which theoretically can be taken arbitrarily. As hyperparameter (that is estimated on the validation set), we consider 3 E {10-2, 10-1111 1}. We use the standard CatBoost library and add the Gumbel noise term in selecting the trees for the "L2" scoring function, which is implemented in CatBoost out of the box but is not used by SGB and SGLB since it is not the default one for the library. Moreover, do not consider subsampling of the data (as SGLB does also), and differently from SGB and SGLB, we disable the "boost-from-avers -ror-average" option. Finally, we set f2-leaf-ree value to 0, as SGLB does.
29


Reviews:
[{"review_id": "iacnM6uvoWH", "reviewer": "Reviewer_HjFB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "A method for posterior inference with a variant of GBDT is proposed. The weak learner used in this paper is a variant of the standard decision tree, where decision rules are oblivious (same split used at all nodes of the tree at the same level), the splitting procedure is randomized by use of the max-Gumbel trick to sample the decision rule. Shrinkage is applied throughout the training process as a regularizer.\n\nThe proposed inference technique is a form of sample-then-optimize, wherein a posterior sample is acquired by first sampling from a prior on the function space, then applying GBDT to the residuals of the sample from the prior and the training data.\n\nThe paper provides theoretical justification for their method, including finite-sample convergence of the gradient boosting algorithm, and convergence of the sampler to the posterior distribution.\n", "summary_of_the_review": "The connection between boosting and GP inference is a compelling unification of different approaches to uncertainty quantification.  The paper is theoretically grounded and shows strong empirical results. The presentation could be made clearer, with more explanation of the significance of the theory, and intuition behind the performance of the method. ", "strength_and_weaknesses": "Strengths\nThe paper presents a compelling connection between gradient boosting and Gaussian Process inference.  It presents a tree-based kernel, which is used to define a RKHS and the definition of the Gaussian process.  The paper presents experimental results that show impressive performance both for prediction and uncertainty quantification on a range of datasets. The paper is addressing an important and unsolved problem in a principled way.\n\nWeaknesses\nThe paper would benefit from editing and condensing to make it clearer and to provide more intuition to the reader. The mathematical exposition is provided without much explanation or connection to empirical results, other than ensuring convergence. For example, the authors show some empirical improvement on bagged SGB and SGLB, but it’s not clear where the relative weakness of those methods stem from.\n\nThe experiments could be further strengthened in a way that both bolsters the case for the method, and improves the paper’s arguments.  For example, the authors do not compare to GP with standard kernels. This would be interesting to see, given the close connection to these methods. What is the dimensionality of these problems?  Does the method work well in high-dimensional problems, especially with sparsity?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "brHOY4RyVbW", "reviewer": "Reviewer_iZU9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper is a nice theoretical one which shows an equivalence between two seemingly unrelated ML methods: gradient boosting decision trees on hand, and kernel methods/Gaussian processes on the other. On top of this equivalence, it is shown that model uncertainty can be obtained according to the GP variance.", "summary_of_the_review": "In summary, I find that the paper is making well-grounded contributions which I think should be of interest for the ML community working on uncertainty quantification.", "strength_and_weaknesses": "Strengths: the paper strikes a is a nice balance between theory and practical relevance of the proposed method. In particular, there are nice non-asymptotic results in section 4.1.\nExperiments show interesting results in posterior variance estimation and OOD detection.\n\nWeaknesses: I find it hard (even for a Bayesian) to fully get the methods proposed in section 4, esp. regarding Bayesian terms as prior, posterior, on Monte Carlo sampling. \n-Providing transitions between subsections would help. The discussion after corollary 4.2 is difficult to read, probably because it is essentially made of equations/complexities. What do you conclude from it?\n- Usually, Bayesian have a handle on their priors, eg with hyper parameters. Is it the case here? I find this subsection difficult to get.\n- SOme diagram to relate the different quantities from the prior/posterior/asymptotic posterior would be helpful.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IrtSSax3Pj", "reviewer": "Reviewer_1ARD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "  \n        This paper analyzes gradient boosting ensembles and shows that they can be understood as a kernel method that is indeed finding the solution to an optimization problem that converges to the posterior mean of a Gaussian process. Using the technique known as sample-first-then-optimize the considered method can be used to generate samples from the posterior distribution of a Gaussian process. This means that output uncertainty can be readily obtained and used, for example for out of distribution detection. The proposed method is evaluated on several datasets from the UCI repository.\n", "summary_of_the_review": "   I believe this is a nice paper showing a nice theoretical results. However, it is impaired by the questionable applications. In particular, I wonder why not using directly a Gaussian process if KGB is precisely approximating that. The experimental section is also weak and does not allow to check if the method proposed is significant. In particular, no error bars are given.\n\nMinor:\n\nEquations are not numbered and cannot be referred. There is a typo in the Eq. for the posterior variance of the GP.\n\nN (f (x), σ 2 (x) is missing ).\n", "strength_and_weaknesses": "Strengths:\n\n        - Nice theoretical results showing that gradient boosting can be understood as a kernel method.\n\nWeaknesses:\n\n        - The main result is a bit obvious since gradient boosting is minimizing objectives in functional space.\n\n        - The fact that KGB performs better questions why not using a Gaussian process as the learning method.\n\n        - The experimental section is weak. No error bars are given and therefore it is not possible to assess the significance of the results.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster