Statistical Inference for Gradient Boosting Regression
Authors: Haimo Fang
Kevin Tan
Giles Hooker
Venue: NeurIPS 2025 poster ()
Keywords: Boosting
regression
nonparametric
trees
inference
statistics
Primary area: general_machine_learning
TL;DR: We provide confidence intervals, prediction intervals, and hypothesis tests for variable importance for boosting with dropout and parallel training.

Abstract: Gradient boosting is widely popular due to its flexibility and predictive accuracy. However, statistical inference and uncertainty quantification for gradient boosting remain challenging and under-explored. We propose a unified framework for statistical inference in gradient boosting regression. Our framework integrates dropout or parallel training with a recently proposed regularization procedure called Boulevard that allows for a central limit theorem (CLT) for boosting. With these enhancements, we surprisingly find that \textit{increasing} the dropout rate and the number of trees grown in parallel at each iteration substantially enhances signal recovery and overall performance. Our resulting algorithms enjoy similar CLTs, which we use to construct built-in confidence intervals, prediction intervals, and rigorous hypothesis tests for assessing variable importance in only $O(nd^2)$ time with the Nyström method. Numerical experiments verify the asymptotic normality and demonstrate that our algorithms perform well, do not require early stopping, interpolate between regularized boosting and random forests, and confirm the validity of their built-in statistical inference procedures.

Statistical Inference for Gradient Boosting Regression"
Haimo Fang', Kevin Tan?; Giles Hooker
"School of Economics, Fudan University
Department of Statistics and Data Science, The Wharton School, University of Pennsylvania
Abstract
Gradient boosting is widely popular due its flexibility and predictive accuracy. However, statistical inference and uncertainty quantification for gradient boost- ing remain challenging and under-explored. We propose unified framework for statistical inference in gradient boosting regression. Our framework integrates dropout or parallel training with recently proposed regularization procedure called Boulevard that allows for a central limit theorem (CLT) for boosting. With these enhancements, we surprisingly find that increasing the dropout rate and the number of trees grown in parallel at each iteration substantially enhances signal recovery and overall performance. Our resulting algorithms enjoy similar CLTs, which we use to construct built-in confidence intervals, prediction intervals, and rigorous hypothesis tests for assessing variable importance in only O(nd²) time with the Nyström method. Numerical experiments verify the asymptotic normal- ity and demonstrate that our algorithms perform well, do not require early stop- ping, interpolate between regularized boosting and random forests, and confirm the validity of their built-in statistical inference procedures.
Introduction
Gradient boosting Friedman (2000), particularly through widely used implementations such XG- Boost Chen and Guestrin (2016), LightGBM Ke et al. (2017), and CatBoost Prokhorenkova et al. (2018), has become one of the most powerful and widely adopted methods for supervised learning. especially on tabular data. However, this flexibility and predictive accuracy come at a cost. Unlike their base learners such decision trees or linear models boosting methods less interpretable, and uncertainty quantification for their predictions is far from straightforward. While point estimates may suffice for ad hoc prediction tasks, they overlook randomness inherent in both the data and the algorithm itself. Uncertainty quantification therefore asks a central question: a new dataset were collected and models retrained, how different would the resulting predictions be? This is a central ingredient in propagating uncertainty through forecast models, prioritizing data collection and a host of other downstream tasks.
typically far
In this light, various methods have been proposed for uncertainty quantification in boosting. These include Langevin boosting Tan et al. (2023); Ustimenko and Prokhorenkova (2022); Malinin et al. (2021), k-nearest neighbors-bar based techniques Brophy and Lowd (2022), Gaussian graphical models Chen and Wang (2023). quantile regression approaches Yin et al. (2023), and probabilistic prediction via natural gradients Duan et al. (2020). However, most of these methods lack formal theoretical guarantees, with many relying primarily heuristic justifications.
A principled route to uncertainty quantification is through statistical inference, e.g. via prediction intervals. However, this remains limited. In the Bayesian setting, Ustimenko al. (2023) show randomized boosting converges to a kernel ridge regression and approximate Gaussian process pos- terior. Yet, they re-run the entire boosting procedure to generate Malinin et al. (2021) suggest a virtual ensemble method, but do not provide formal guarantees.
single posterior sample.
"ooee available https: /ttp//ggtttt..t///
gittt
This work was done prior to employment at Amazon.
39th Conference on Ncural Information Processing Systems (NcurIPS 2025).

---

In the frequentist setting,,, Zhou and Hooker (2022) propose regularization scheme yielding central limit theorem for boosting via convergence kernel ridge regression. However, they do not provide proper confidence or prediction intervals, and their method recovers at most half the true signal (rescaling is suggested, but this amplifies errors). Despite these limitations, their framework remains the primary foundation for frequentist inference in boosting, which we extend here. In a concurrent work, we adapt the same perspective to explainable boosting machines (EBMs) and derive feature- wise intervals with additional computational accelerations (e.g., binning) Fang et al. (2026).
Other literature. Recent advances for random forests yield principled statistical methods for uncertainty quantification via the construction of valid confidence intervals Wager et al. (2014); Wager and Athey (2017); Athey et al. (2018); Mentch and Hooker (2016b), and interpretability via hypothesis tests for variable importance Mentch and Hooker (2016a); Coleman et al. (2022). Much of this is achieved through viewing random forest (2021); Athey et al. (2018). This also holds for various incarnations of boosting Zhou and Hooker (2022); Ustimenko et al. (2023). Despite these findings, the literature on uncertainty quantification and statistical inference for boosting is far sparser - gap we fill by exploiting this equivalence.
adaptive kernel method Friedberg et al.
Motivated by this gap, we study frequentist inference for uncertainty quantification in boosting under supervised nonparametric regression: y = f(x + 6, with subgaussian noise with variance 0². Our goal is to develop principled, statistically sound procedures for uncertainty quantification, outlined below.
Methodological contributions. In detail, we provide the following methodological contributions:
1. Improvements via dropout: We incorporate random dropout Rashmi and Gilad- haad-Bachrachh (2015) into the regularization procedure of Zhou and Hooker (2022). This yields improved procedure (Algorithm 1) that achieves provably better performance by up to factor of 4 in the asymptotic relative efficiency (ARE), and inereased signal recovery by up to factor of 2. By tuning the dropout rate in Algorithm 1, we smoothly bridge the vanilla Boulevard method Zhou and Hooker (2022) and modified Random Forest Breiman (2001) that draws observation subsamples with- out replacement and considers the full covariate space at each split.
2. Parallel boosting: We construct a novel ceave-one-our procedure for parallel boosting (Algorithm
2) that, when coupled with the above regularization procedure, improves the ARE by at least a factor of 4, and enjoys increased signal recovery by at least a factor of 2.
3. Prediction, confidence, and reproduction intervals: We leverage the central limit theorems our procedures enjoy to construct a variety of procedures for statistical inference. First, we conduct predictive inference via constructing prediction intervals (potentially unseen) labels y. We then construct confidence intervals for the underlying ground truth function f. Lastly, to quantify uncertainty within the learning algorithm, we provide reproduction intervals Zhou and Hooker (2022) for another booster f trained on an independent realization of the training set.
4. Hypothesis testing: We construct chi-squared hypothesis test for variable importance, extend- ing the work of Mentch and Hooker (2016b) for random forests to the boosting setting.
5. Computational efficiency: Unlike prior approaches to statistical inference for random forests and boosting, we utilize the Nyström approximation of Musco and Musco (2017). This allows our tests and intervals to scale linearly with the number of data points. Relatedly, in the EBM setting, Fang et al. (2026) exploit covariate binning to further accelerate feature- -ist inference.
CI
RI
Conformal Pt
Coverage: 87.00%
Coverage: 82.33%
Coverage: 96.67%
Coverage: 97.33%
The aa
Bering Dold
Buinig 201e
60
0.6
1.0
0.2
06
1.0
3.0
0.4
0.8
60
64
06
06
1.5
Figure 1: Demonstration of confidence, prediction, and reproduction intervals on (xx = sin 2 +
J Conformal baseline. 200 trees, learning rate 0.6, depth 8, subsampling and dropout 0.6.
Theoretical contributions. Our primary theoretical contributions are central limit theorems (CLT's for boosting with dropout (Algorithm 1) and parallel training (Algorithm 2)- - the first such results for these settings to our knowledge. These extend the theoretical arguments of Zhou and Hooker (2022). In analyzing boosting with dropout, the stochasticity introduced into ensemble construc- tion must be accounted for in addition to randomness from data subsampling. To address this,

---

we establish a weak law for finite-sampll sample convergence in the stochastic contraction framework of Almudevar (2022). The arguments for parallel boosting are more challenging. Inspired by classical backfitting methods Breiman and Friedman (1985), we develop a delayed averaging scheme that enables parallelism while preserving convergence guarantees. To achieve central limit theorems that hold unconditionally on the data X, we show bound on the maximal leaf size is sufficient to limit the influence of distant points and promote balanced splits, enabling rigorous distributional results.
Numerical experiments. We establish the efficacy of our methods on both a simulation study and wallwworld datasets. Our numerical experiments showease that our algorithms can be tuned to interpolate between regularized boosting and random forests, and are highly competitive in terms of MSE. These also demonstrate the correctness, coverage, and computational efficiency of the statistical procedures we construct via the central limit theorems our algorithms enjoy.
2 Setup
Consider boosting for nonparametric regression with squared error loss. Given random features x E [0, 1]S. labels y E R, and noise e ~ SubG(O, o²), say there exists some function I such that y f(x) + The learner is given training set (Xitain , ydtaia) of size n, and learns an estimate f of f by minimizing the mean squared error (MSE) EE - y2)² over the training set. is customary to analyze how f converges to f. or in other words, the generalization ervor of f on test set (Xlest, y Subscripts fi(h) indicate the estimated predictor trained on datapoints for b boosting rounds, where we omit dependencies on b and n whenever possible.
Regularized stochastic gradient boosting. Zhou and Hooker (2022) propose a regularization pro- cedure called Boulevard that recovers central limit theorem for boosting. They do so by showing that the resulting regularized procedure converges to kernel ridge regression. At each iteration
b = 1.., B - 1, instead of f(b+1) + f(h) + (t they update f ((+ 1) t- --1 + ()
for the current function estimate f(0), built tree ((6), and learning rate À E [0, 1). As this is equiv- alent to updating f((+1) + 2/ Σ === t(6), the resulting ensemble is an average of trees. This obser- vation, along with assumptions on tree adaptivity, allows them to prove that Boulevard predictions are asymptotically normal, though they do not construct confidence or prediction intervals. Addi-
tionally, this regularization comes at a cost. It turns out that f% converges only to I S f/2 as n. + oo, and so Boulevard recovers at most half the signal. Still, this is the only method available for frequentist inference for gradient boosting, and so we seek to improve upon it in this paper.
Tost MSE vs. Younds mean
SE (B=30)
00 Rot ground y + 2x 1
6X:1P
161
5x10P
Semple
40:10P
Thoorotical Quartile
Figure 2: An added benefit of Boulevard regularization is that it renders early stopping unnecessary. Because the procedure converges to a fixed point, one can (in theory) boost indefinitely without encountering overfitting. It also produces asymptotically normal predictions (see the Q-Q plot).
Regression trees and tree structure. We are primarily concerned with boosting algorithms where we use regression trees weak learners. We introduce formulation of regression tree below. Definition (Regression trees). regression tree tn trained on n datapoints segments the covariate space [0, 1)d into a partition of hyper-rectangler {A, When A(x) for the rectangle containing x, and 8n.j (x) is the frequency at which training point X; and test point x share a leaf:
8n.j (x) Σr= [(x]) the regression tree t, predicts i, (x) = =E 8m.j (x) Yj-
E(x))
As such, a tree can be thought of as an adaptive nearest neighbor method Athey et al. (2018);
Friedberg et al. (2021), where (x) yields the influence of datapoint X, on the tree's prediction
3

---

at test point x. This motivates the definition of a structure vector and matrix from Zhou and Hooker (2022):
Definition 2 (Structure vectors and matrices). Let bn be a tree trained on the input (Xn: For an arbitrary point x, lel 8n (x) = (8n,1 (.),,..,,,,, (x)) be the structure vector of x. As such, we say that the matrix S, = (8n. (x:)) with rows 8, (x,) is the structure matrix of tn.
The structure matrix is kernel matrix. A natural idea is to perform kernel ridge regression (KRR);
(x) = (x)) (x) = (x),, K,, = E[S.]: and rx) = kr,, (x) (A-
Zhou and Hooker (2022) show Boulevard regularization converges to a kernel ridge regression (x) = yx) as b + Co. However, as À E (0, 1]. this converges to at most half the signal. We later propose two algorithms in Algorithms 1 and 2, that converge to (r.(xx), kn (x- + " and (x), yn) kr, (x) (I (K
respectively,
achieving increased signal recovery. As final note, to accommodate training (x, g) on a sub- sample G C {1. n), we write ( 9) 1(x; E A.j E 9)/Ex= 1(x; E A., k 9), and
m tn (x; = دド=1 8n (x; g) Dj- We suppress the dependence on subsamples when possible.
Integrity & adaptivity. We inherit the following two assumptions from Boulevard regularization:
) Assumption 2 (Non-adaptivity). There exists a probability measure 2n on the space of tree struc- tures and some V/ so the free structure iteration b = b ,.., B is an independent draw from 2n.
Assumption (Structure-value isolation). (t!") )==1 has sn (b) (x) TT for all b- 1..... B.
These are required for theoretical guarantees. In practice, the first can be implemented via stronger form of honesty Wager and Athey (2017) that we call integrity, refitting leaf values on an indepen- dent dataset after boosting. One can also randomly sample splits, or get them from random forest trained on an independent sample. The second only requires non- non-adaptivity after a finite number of iterations, which may occur naturally Zhou and Hooker (2022). To enforce it, can boost normally for a fixed number of steps and then sample tree structures from earlier iterations. Still, numerical experiments indicate that algorithms perform well even without these adjustments. Our assumptions are given in a colleted format in the supplement.
3 Algorithms
To address the limitations of Boulevard regularization while retaining its statistical guarantees, we propose two improvements that achieve enhanced signal recovery and improved sample complexity:
Alg. 1: By incorporating random dropout Rashmi and Gilad-Bachrach (2015) in the ensemble.
Alg. 2: By growing trees in parallel within each round with a leave-one-out procedure.
The intuition is as follows. Surprisingly, increasing the dropout probability allows one to recover more of the signal. This is because each tree the current ensemble is effectively downweighted during residual construction, and the new tree is fit on more of the signal. On the other hand, as the number of trees grown in parallel within each round grows, the resulting ensemble increasingly resembles the procedure of boosting random forests in sequence allowing each round to recover more signal than single tree can. We present both algorithms and explain them in detail below.
Algorithm Boulevard Regularized Additive re- gression Trees Dropout (BRAT-D)
Algorithm BRAT Parallel (BRAT-P)
Input: Features X, labels y, subsample & trees/round K, rounds B. f()), ((0.)) <- 0.
1: Input: Features X, labels y. dropout rate
p 1 q. subsample rate &, learning rate
2: Fit f()), (t(,))) K
3: for b 2,.., B k=1 with K boosting steps.
X, boosting rounds B. Set f(u), ;0, ((0) + 0.
do
2: for b = 1, B - 1 do
4: for k = = 1,..,, K in parallel do
3: Subsample S₁ C (0, ..., b -- 13 w.p. g.
Subsample Go C (1....,,) n) w.p. E. 6: 2i,k + y1 6 e=1 Ensr (xG)
4: Subsample data Go C (I,...,. n) w.p. E.
5: 2, y E.es. t()) (x,).
7: Construct tree z (b.kk on (xi, 2i, JeGGu.
6: Construct tree (0) on (x;, zz)ieg0.
8: end for
7: f(++)) + - f(O) + b x2) = b
=b= {())
9: Define f(b+1) +- -
((a,))
8: end for
10: end for
9: Return final predictor 1+A0 (B).
11: Return final predictor ((B).
4

---

Random dropout. Unlike vanilla boosting, Algorithm 1 computes residuals with both data Friedman (2002) and ensemble subsampling Rashmi and
(2015). At each round b= 1, ....., B 1, each tree is subsampled with a dropout rate of p E [0, 1) (equivalently, with proba- bility q = p). We write Sp C (0. ..., b 1} for the collection of subsampled tree indices at each round b. Likewise, data indices G. C {1, ,.,,, n) are subsampled with probability & E (0, 1].
As a result, each tree (0) is trained on the dataset (x,, =))E where the residuals are given by z = - Exes (x;). Within the residual computation, we intentionally divide the sum of the subsampled ensemble's 's predictions by instead of [S]. This is done so each new tree is fit on more of the signal, allowing for increased signal recovery when applying Boulevard regularization.
We later show in Section 5 that the predictions of Algorithm converge to kernel ridge regression that enjoys a central limit theorem. Informally, for any test point we have that:
y (b)
a.s. (A- + EاE [S..1) E [Sn) yn. || (x) ( (x)
T (x))
NN
o²),
for a kernel matrix induced by the tree ensemble K,, = E[S,), and limit f lim P where (x) = (r.(()), yx) = (x) (x) T g - ||r llll is the norm of kernel weights. Algorithm I encompasses two important special cases. When À = and p + 1, this yields random forest. When p O, Algorithm corresponds to the original Boulevard algorithm Zhou and Hooker (2022). Tuning the dropout parameter p allows the user to interpolate between the two, while improving over Zhou and Hooker (2022) by up to factor of 1+
T-Xq (1,2] in signal recovery.
Parallel boosting. Algorithm 2 integrates novel leave-one-out procedure and Boulevard regular- ization into the parallel boosting framework Long and Servedio (2011) 1); Karbasi and Larsen (2023); da Cunha et al. (2024). The algorithm is warm-started by performing K vanilla boosting iterations in the first round. At each subsequent round b 2, ...., B - 1, we grow K trees (f(b,)) ) in paral- lel on the K datasets ((xi, =i.A) ieG.). ) These consist of independently subsampled data indices Go.k S (1)....n), and residuals that are computed by leaving one "column" out (or alternatively, one tree out per round): 2 = y/ -
Eis (x:). The resulting predictor given by E (bb,)) :/2 E. Σk ((0.))
the regularized boosting update: f(+1)
I. Likewise, we later show in Section 5 that the predictions of Algorithm 2 also converge to a kernel ridge regression that enjoys central limit theorem. Informally, for any test point x:
II + (K - 1)E (S.)) KE [S,) (x)(x)))l (Fr (x) f(x)) d N(0,
b
with limit fi"' = lim fa given by (x) = (r yn) kn, (x) (K -K-1)K -Ky, Algorithm 2 can be viewed as boosting modified parallel backfitting algorithm Breiman and Fried- man (1985)² that is warm-started with K vanilla boosting iterations. 4 When K = B, + co, Algorithm 2 reduces to random forest E [S,,] yn- On the other hand, Algorithm 2 reduces to vanilla boosting when B- = 1, K + Xc. Note that the CLT only holds for 1 < K 00.
The attentive reader may observe that we do not divide the final predictions by K. This is because the combination of leaving one column out when fitting tree and Boulevard averaging sufficient to allow our procedure to stabilize. Still, dividing by K yields a viable algorithm (deferred to future work) that can be thought of as boosting random forests each of trees over B rounds, using the natural strategy of averaging all trees but the left-out column to form predictions.
Statistical Inference and Uncertainty Quantification for Boosting
We now introduce our methods for conducting statistical inference for boosting: the theoretical basis for these procedures is provided below. Our methods rest on the aforementioned convergence to kernel ridge regression and central limit theorems that we formally prove later in Theorems I and 2. In the meantime, we provide the following asympiotically valid procedures.
"This can be thought of as a structured variant dropout Zhao et (2022); Xin al. (2020); Fan et al. (2019). Dropping one out of every K trees allows the regularization to scale in 1/K.
'The initial K boosting iterations yield better convergence in practice, and do not hinder our theoretical arguments as the impact the vanilla boosting iterations washes out when we take - x0.
$ PParallelized backfitting can be thought of as parallelized coordinate descent. Averaging over the coordinate updates is sufficient for convergence. Dividing by b, as in Boulevard averaging, is sufficient when 5 > K.
5

---

Estimation of asymptotic variance. The CLTs for Algorithms 1 and imply that one can con- struct confidence intervals for f with the following normal approximations:
X (1+Ag))) (x) & N (f(x), A 2 As such, it remains to estimate r r and o², We first estimate Kn (x) by the sample averages
(x)))))))) fr (x) & N (f
(x) Ei
1 Sn. xx Gb), [x) = BK E'
(b.R) k= nn, (x, Go,k);
(1)
where 2n (x; (b) is the fraction of subsampled datapoints in the same Ieaf A,t) as over the trees. Likewise, we estimate (K, (Kn)..j. the fraction of trees where datapoints i and j fall in the same leaf:
(k)) = Em (b)
nn. (x; Go), (k,),, 1 E Sn.. (x:; Go,))s
Our estimates Fn are then given by plugging the above into the formula for Tni
(x) R (x) T (A-'I++ )
P (x) T R (x) (I+ (K 1)K
Lastly, we estimate o² with the residuals H² = Viat Li=l
Real (y: ) on hold-out calibration set.
We describe a tweak later in Section 6 that uses the calibration set for increased robustness.
Confidence intervals for f. Putting everything together yields a confidence intervals for f (where 21 -1 is the (1 a/2)-quamtil of the standard normal distribution):
x- + F (x) + 21 21-a (1 ) (x)]l2, f (x) + # a
a FI
(3)
Prediction intervals for y. We can construct prediction intervals for y|x x as follows:
Ag) 2 (1 (1+ \1) / [F
(x)x
||
(x)
These prediction intervals have asymptotic pointwise coverage, conditional on the test point x. That is, IP(y E PI(x)|x) + 1 a as n + oc, which holds as a corollary of the CLTs we present in the following section. Note that this conditional coverage guarantee is stronger guarantee than is typically possible with conformal inference Barber et al. (2020). We compare our prediction intervals conformal prediction intervals within numerical experiments later in this paper.
Reproduction intervals for f. We now turn our attention towards computing reproduction in- tervals. That is, a confidence interval for another realization of f trained on another independent realization of the data. To do so, Zhou and Hooker (2022) suggest, suffices to scale the width of
the above confidence intervals for f by v2 as X1,X2 i.i.d. (N o²) = X X2 (O, 2x²). Note that one can invert the above confidence, prediction, or reproduction intervals order to test if the underlying function, another realization of the response, average learner is equal to given constant. This amounts to checking if the constant is contained in the interval of choice.
Variable importance tests. Suppose we wish to test for variable importance. Consider the possi- bility that there exists some subset of the feature space [o, 1]d containing only d < d features, and let g: [0, 1]d + R be the projection of f onto ( 1] We test the possibility that f(x) (xx) by proxy. Consider a split of the training dataset (Xn.yn) into (Xn,1,yn,11 (X,22.nn22 where X E Rgn/2dd Xn, Rn/2,d Let f be the boosting learner trained on (X,,, vn), and fu, be the same trained on (2.2. Given a hold-out dataset (Xm, ym), we test the null:
Ho f({x) gxx,) for all j 1,... m against H1 f (x,) # gXx)) for some
by comparing (x,) and fx,2(x;). We exploit the CLTs our algorithms enjoy to do so. Write PD.P (x,)) T Rmxxn for the matrix with rows (x)) T)m where we write D, P within the superscript if the formula holds for both Algorithms 1 and 2. The difference in predictions
(),))) y 4 Nm (0, (0,006000 ( is multivariate normal under the null, åm = (fD D.P (X.) - D.P
with covariance matrix O²E, o² a.1
(F (Xm,) - = (X,)))((F)) (FRP, D (Xm)) esti-
mated by plugging in 2². As such, we can conduct chi-squared test with test statistic
--2 "T á ~ Xm under the null, rejecting the null if - 2.,. > Xm.
The test as presented runs in O(n3) time. In Appendix A, we present an accelerated version of the test that runs in ((ns(r s) + قو time, where s is the number of points subsampled for Nyström approximation and r is the number of test points subsampled.

---

Matrix sketching. Although the CLT reduces the problem of inference to kemel ridge regression (with the right kemel), computing K,, is O(n²) problem intractable for large This is the chief difficulty that Zhou and Hooker (2022) face when constructing replication intervals for vanilla Boulevard. We bypass this issue, making our procedures practical and tractable via matrix sketching. In a concurrent work with related setting. Fang et al. (2026) bin covariates in EBMs to accelerate the computation of feature- seature-wise intervals.
We approximate Kn, using the Nyström method Williams and Seeger (2000), via either uniform subsampling or the recursive approach of Musco and Musco (2017), producing an approximation where S E IRax* is a random subsampling matrix. With the Nys-
K₂ ~ SiS S),SS trom method of Musco and Musco (2017), we can choose mension det of ridge regression problem with regularization parameter on the kernel matrix: = ((d")) This requires only O(ns²) time to precompute the kernel, and only O time for inference - yielding practical statistical inference in near-linear time in the number of datapoints n. We adopt this approach in our experiments, allowing our procedures run in linear time and remain practical, in contrast to previous work Zhou and Hooker (2022); Mentch and Hooker (2016b). See Appendix A.
be near-linear in the effective di-
5 Theoretical Guarantees
We now formally present guarantees for convergence and asymptotic normality for Algorithms and 2. Consider the (Lipschitz) nonparametric regression model introduced below:
Assumption 3 (Lipschitz Nonparametric Regression). Let y f(x) + c, where x has density satisfying c1 S p(x) S C2 < co on its support. Further assume f is a-Lipschitz continuous on supp(u), and noise is aub-Gaussian with variance proxy o².
Fimite-sample convergence to KRR.
We now show that our algorithms achieve finite-sample con- vergence to kernel ridge regression the number of boosting rounds increases. At first glance, this is surprising - greedy split selection and sequential ensemble construction create a highly nonlinear and demendepndeent mapping. Fortunately, the regularization procedure of Zhou and Hooker (2022) provides a way forward. For the special case of = O within Algorithm 1, they show convergence to kernel ridge regression via the stochastic contraction framework of Almudevar (2022), utiliz- ing Assumptions 1 (structure-value isolation) and (non-adaptivity) to ensure stagewise stability. A key novelty within our analysis lies in showing that this convergence extends Algorithms and 2, even with the added complexity introduced by dropout and parallelism respectively. Despite these added sources of stochasticity and dependence, our use of the same regularization mechanism ensures that both algorithms inherit the stability required for convergence:
Theorem (Finite Sample Convergence to KRR). For fixed X, y, under Assumptions 1, 2, and 3,
To < (A II qE [. E S.l for Alg. 1. 3o 3 (I (K 1)E (S.))) KE [S.]] y for Alg. 2,
as b + 00, where q= 1- - is one minus the dropout probability, is the number of trees grown in parallel, and S, the kernel matrix induced by the tree structures within the ensemble.
The proof, deferred to Appendix C, departs from Zhou and Hooker (2022) in two crucial ways. Within Algorithm 1, dropout injects unbounded variance into the ensemble updates. To control this, we introduce the hard truncation function T' (v) sign(v) min M, /y} into each residual update, y, = d-1 ensemble escaping this cap vanishes as b + 30. Within Algorithm 2, truncating No,A = =o-1k ( Ex1 ().s) alone is insufficient. We further introduce a delay mechanism, requiring that br does not rely on 44 allowing us to apply Theorem 3 and parallelize tree training.
b- - + -े2 Sy (T))). and then show that the probability of the partial
A central limit theorem. Having established almost-sure convergence to fixed points, we now examine the asymptotic distribution of our estimators to justify the statistical procedures introduced in Section& 4. We seek a central limit theorem for the learner f.P.P trained on random X,., Yn. demonstrating that the predictions T..P(x) are asymptotically normal with mean f(x) as + co. To do so, we inherit the following assumptions from Zhou and Hooker (2022): two on the leaves to control the norm of the KRR weight vector y.D. D.P. and restriction the tree distribution space:
7

---

Assumption 4 (Bounded Leaf Diameter), Write diam(A) = yEA || v/1. For any leaf A in a tree with structure q E Qn. we need sup (iam(A) = O(dn), where dn O(n -1/(4t)))).
Assumption 5 (Increased Minimal Leaf Size). For any 0, Un #12 to < n पी O(d)),
Assumption 6 (Restricted Tree Support). The cardinality of the tree space Qn is bounded by O(n e000=epp0..mmmm4444 (/0000))mm/(+2)- - =)")), for some small a > O.
Intuitively, Assumption 5 prevents leaves from becoming too small too quickly, which in turn con- trols the maximal coordinate of the weight vectors across random samples. Assumption 6, guaran- tees that the complexity of possible tree partitions does not explode with n. We also make assump- tions the regularity of tree splits in line with the notion of a-regularity in Athey al. (2018):
Assumption 7 (Median Splitting Rules). The trees in Algorithm 2 are split at the medians.
We defer the details to Definition 3. Under this splitting rule, the point-to- to-point collision probability well-controlled, i.e. to say none of the leaves are big enough to contain most of the points. These conditions allow for uniform control over both leaf sizes and tree complexity, yielding the result:
Theorem 2 (Central Limit Theorem for Predictions). Letx E [0,, 1]4. 9 E (0, 1], > As n - 00,
|| 2 -x + ((x)) م N(,,
| (P(x))
d (0,
We prove this in two stages. In the first, with proof deferred to Appendix D. we show asymp- totic normality of the predictions around the noiseless KRR predictions (T... ((K,)), con- ditional on the training data X Yn and test point x, by applying the Lindeberg-Feller CLT to (r..P(()), e). Next, we show that (x)),((x),. f(X,)) converges to the underlying ground truth function at sufficiently fast rate in Appendices E and F. For Algorithm 1, although r now in- volves [ + [K,] -1, this still preserves the rate ||r^ x n- n=1//((d+1)), allowing us to show (In. (X,,) - 1+A9 f(x) = (((rall2)) The Lindeberg- Feller verification then proceeds identi- cally to the non-dropout case. However, to give a CLT for Algorithm 2, controlling the influence from distant training points is challenging, though we show that Assumption 7 is sufficient to do so.
Understanding the result. The rate of convergence of the CLT in Theorem 2 depends on the norm of r.. This is controlled as follows, yielding generalization bounds for Algorithms I and 2: Lemma (Rate of Convergence). Let B, := {i: ||x x:|| < dn be the points within distance dn from test point x. If [Bm|| = 2 (n d.)), then ||k,l|2 = O(n コ 1r D.P ll2 O(n -(n )
Corollary 1. EE(( 1+0g
X fP (x) - f (x)) S ( 2002 गों and
-x(x)) - 02n गें.
Corollary 2. n 2 Ω
(0g(1/6) 2
N Ω mA then w.p. at least 1 - 5, ( (x) f(x) Sc c.
The first an asymptotic risk bound, while the second is nonasymptotic PAC guarantee. Recall that M is the truncation level. The results above recover the minimax rate for nonparametric regression on 1/2-Holder smooth functions Stone (1982) quadratically worse than the rate for Lipschitz functions (the setting we are in). We believe this can be improved - trees should inherit adaptivity to the intrinsic dimension as an adaptive nearest neighbor method, but we leave this for future work.
Furthermore, Theorem yields asymptotic coverage of our intervals constructed in Section 4: Corollary 3. The Cls, PIs and RIs achieve almost sure pointwise coverage as n, b OC.
We show in Lemma I that the rate at which D- grows is the same for Algorithms and 2. This shows that our methods achieve asymptotic relative efficiency relative Zhou and Hooker (2022) by up to a factor of 4 for Algorithm 1, and at least a factor of 4 for Algorithm 2:
Corollary 4 (Asymptotic Relative Efficiency). Write f" for the scaled predictions made by vanilla Boulevard Zhou and Hooker (2022) with the same learning rate X E 10. as Algorithm 1. Then, V fB) Var This has the implication that Algorithmss 1 and 2 achieve increased signal recovery in the square root of the ARE relative to vanilla Boulevard. The intuition for this improvement is as follows. For any choice of X within vanilla Boulevard, there exists choice of p within Algorithm that requires a smaller rescaling. On the other hand, as Algorithm 2 requires no rescaling, it can achieve an unbounded improvement in relative efficiency over vanilla Boulevard
Var(
(+22)) )² E [1, 4], Varl ( / - - E [4, oc).
take À - 0.
8

---

Type & Type BI Error
Wine Quality
Obesity
Air Quality
Typel Froor
BAAD
GST
6.8
Type Bro
0.6
XSSeee:
550
MSE
1332
$.144
302
044
60
2.01
350
300
2000
200
400
192
200
3033
400
500
200
300
+33
500
Training Samples
Ensemble Size
Ensemble
Ensemble Size
Figure 3: Left: Type I and Type II error of the hypothesis test for variable importance against train- ing set size. Test set is of the same size. Error rates computed over 30 trials. Right: Comparison of MSE achieved by various machine learning algorithms on different datasets, with hyperparameters tuned for each by Optuna. Shaded area depicts two standard deviations over 5 trials.
6 Numerical Experiments
The previous section presents a rich theory: alongside convergence to kernel ridge regression and central limit theorem for predictions, we provide asymptotic risk bounds and nonasymptotic PAC guarantees, and show asymptotic coverage for our intervals. In light of this, we present a series of numerical experiments to empirically justify our algorithms and methods.
Predictive accuracy. The first, and most natural, thing to do is to examine the performance of our algorithmss against handful of competitors in terms of test MSE on nine datasets from the UCI Machine Learning Repository in Figure 3 and Figure 6 in the supplement. Our competitors include popular methods such as XGBoost Chen and Guestrin (2016), LightGBM Ke al. (2017), as well as random forests and vanilla boosting, We also compare to vanilla Boulevard Zhou and Hooker (2022), and an elastic net regression as baseline. All hyperparameters were tuned with Optuna Akiba al. (2019), reported in Appendix I. There is no clear winner in general, but XGBoost is a consistently strong performer, and random forests are clearly more suited to some datasets than others. Neither Algorithm I nor Algorithm 2 consistently outperform each other, but Algorithm 2 occasionally exhibits instability on some datasets. Regardless, both of our algorithms are competitive in terms of final MSE and rate of convergence, and exhibit the ability to be tuned to be closer to boosting (Wine Quality) or random forests (Air Quality), providing increased flexibility by interpolating between the two.
Our results in Figure are somewhat unfair to Algorithm as the x-axis is in the ensemble size and not the number of boosting rounds. The number of boosting rounds that Algorithm 2 encounters can be few 31 on Abalone, in contrast the 500 boosting rounds all other algorithms enjoy. Given the same number of boosting rounds, we would certainly expect an improvement.
Variable importance tests. We examine their performance by conducting a simulation study, test- 0 on data from f f(x) 4x =2² +wbrz. We fit Algorithm on data generated from f(x) and (x) = 4x - 2²3 with 100 trees, x = 1, subsampling rate 1, dropout rate 0.95, and max depth of 6. The size and power of our test presented in Section 4 are depicted in the left panel within Figure 3. Our test performs very well, maintaining appropriate size control throughout while the Type II error decreases quickly. Empirically, increasing the dropout rate increases power.
ing the null Hg
Coverage of intervals. Other than the Nyström approximations for fast and practical interval com- putation in Appendix A, there is one more tweak that we encourage users to make in practice. We demonstrate in Corollary 3 that our intervals have asymptotic coverage, but this says nothing about its finite sample properties. Fortunately, Romano et al. (2020) yields a simple enhancement. Since we estimate ē through computing the residuals on hold-out calibration set, we reuse the calibration set to adaptively grow or shrink our intervals according to the empirical prediction interval coverage on the calibration set. This procedure converges quickly (amounting to a doubling trick and binary search), and empirically is very helpful in increasing robustness and finite-sample performance.
To examine the empirical performance of our intervals, we consider the Friedman function f(x) 10 (in((x)x2)) + 20(x;; - 0.5)² + 5x; 10 Friedman (2000). This is depicted as a raincloud plot in Figure 4. Importantly, we consider two notions of coverage: marginal coverage, where coverage is averaged over test points, and conditional coverage, where the coverage is conditional on test point. The first two rows depict the former, while the last two depict the latter. Our intervals perform rea- sonably well, attaining nominal coverage with the exception of the reproduction interval's 's coverage and the confidence interval's ''s conditional coverage. In particular, the prediction interval performs

---

Built-In Confidence interval
Built-In Reproduction interval
Built-In Prediction interval
Conformal Prediction Interval
Models
Models
Modells
Moxbels
U5
6A6
0.7
2975
Coverage
Coverage
Coverage
Coverage
Models
Models
390
58
Width
Width
Width
Width
Points
Points
0.73 Coverage
835
Coverage
Coverage
Coverage
Points
Paints
BERANGES
Width
Width
Width
Width
Figure 4: Points in the first two rows represent of 30 models, depicting the fraction of test points that fell inside the interval generated by the model (marginal coverage) and average width for each model. Points in the last two represent intervals containing the test point (conditional coverage) and average width for each point. Results from Algorithm with 200 trees, learning rate 0.6, subsampling 0.8, dropout 0.3, max depth 4.
of 100 test points, depicting the fraction of models with
very well after the adaptive coverage adjustment. Importantly, unlike the conformal benchmark that has a constant width at each point, our prediction intervals have different interval widths at cach point, allowing users to identify 'hard" examples. See Appendix J for other hyperparameter choices.
CI tuning. Reducing subsample rate & inflates variance proportionally. while deeper trees yield narrower intervals as finer splits yield sparser (x) and smaller |ra]l Variance grows with shrink- age 1/> and falls as dropout p increases. Choosing moderate À and increasing p yields stabler Cls. Setting p > 0 empirically leads to wider intervals and less power in the hypothesis test for variable importance. This can be seen in Figure
Type & Type Error vs Dropout Rate
10-
325
1.-
1.0
Error Rate
aas 025 sio a.5 Ompout Probabilit
0.00 ais pie 5
060 62s ald Dis
0.5
Bropout Probabl ity
Decpout Probability
68-
67-
0.0
Coverage
BI Coveraee
Cavergge
2598
Co-
Trpe Enor Type tnr
-05
0.0
0.2
0.4
0.6 0.0
1.0
8892
Dropout Hate
080
075
325
050
Dropout
Figure 5: Comparison of size and power of statistical inference procedures against dropout probability. Conformal adjustment is not performed (for clearer benchmarking. hence the un- der/overeoverage), and plot the coverage and width across all datapoints and repetitions.
7 Conclusions and Further Work
We incorporate dropout and parallel boosting into the regularization procedure of Zhou and Hooker (2022), allowing for increased signal recovery and improved asymptotic variance. With the CLTs our algorithms enjoy, we construct confidence and prediction intervals, and hypothesis tests for variable importance. Numerical experiments empirically validate our algorithms and statistical procedures.
Our theoretical guarantees depend on structure- value isolation, non-adaptivity, and tree regularity assumptions. Relaxing these e.g., via honesty-based splitting or quantifying mild adaptivity would broaden applicability. Extending inference beyond regression (to classification, survival, or structured outputs) also poses new challenges: non-quadratic losses, different tree behavior, and the need for new CLTs. Doing so under weaker assumptions is a welcome direction for future work.
10

---

References
(2019). Estimation Obesity Levels Based On Eating Habits and Physical Condition. UCI Machine Learning Repository. DOI: https//bbb.rr//022433//1111
Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M. (2019). Optuna: A next-generation hyperparameter optimization framework. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.
Almudevar, A. (2022). A stochastic contraction mapping theorem.
Athey, S., Tibshirani, J., and Wager, S. (2018). Generalized random forests.
Barber, R. F., Candès, R. J., Ramdas, A., and Tibshirani, R. (2020). The limits of distribution-free conditional predictive inference.
Breiman, (2001). Random forests. 45(1):5-32.
Breiman, L. and Friedman, J. H. (1985). Estimating optimal transformations for multiple regression and correlation. Journal of the American Statistical Association, 80(391):580-598.
Brophy, J. and Lowd, D. (2022). Instance-based uncertainty estimation for gradient- regres- sion trees. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A., editors, Advances in Neural Information Processing Systems, volume 35, pages 11145-11159, Curran Associates, Inc.
Chen, M. and Wang, D. (2023). Uncertainty estimation for gradient boosting models based on Gaussian graph model and natural gradient. In Ba, S. and Zhou, F., editors, Third International Conference on Machine Learning and Computer Application (ICMLCA 2022), volume 12636, page 1263633. International Society for Optics and Photonics, SPIE.
Chen, T. and Guestrin, C. (2016). Xgboost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, page 785-794. ACM.
Coleman, T., Peng, W., and Mentch, (2022). Scalable and efficient hypothesis testing with random forests. J. Mach. Learn. Res., 23(1).
Cortez, (2008). Student Performance. https://di..org/In www.o////....42///TTTTT0
UCI Machine Learning Repository.
DOI:
Cortez, P., Cerdeira, A., Almeida, F., Matos, T., and Reis, J. (2009). Wine Quality. UCI Machine
Learning Repository. DOI: https://doi.co ort.:iiorr/110000 orgg/1024432/C566333
da Cunha, A., Høgsgaard, M. M., and Larsen,
(2024). Optimal parallelization boosting.
Duan, T., Avati, A., Ding, D. Y., Thai, K. K., Basu, S., Ng, A. Y., and Schuler, A. (2020). Ngboost: Natural gradient boosting for probabilistic prediction.
Fan, A., Grave, E., and Joulin, A. (2019). Reducing transformer depth on demand with structured dropout.
Fang, H., Tan, K., and Hooker, G. (2026). Statistical inference for explainable boosting machines.
Friedberg, R., Tibshirani, J., Athey, S., and and, S. (2021). Local linear forests. Journal of Computational and Graphical Statistics, 30(2):503-517.
Friedman, H. (2000). Greedy function approximation: A gradient boosting machine. Annals of Statistics, 29: 189-1222.
Friedman, J. H. (2002). Stochastic gradient boosting. Comput. Stat. Data Anal., 38(4):367-378.
Karbasi, A. and Larsen, K. G. (2023). The impossibility of parallelizing boosting.

---

Ke, G., Meng, Q. Finley, T., Wang. T., Chen, W., Ma, W., Ye, Q.. and Liu, T.-Y. (2017). Lightgbm: A highly efficient gradient boosting decision tree. In Guyon, I., Luxburg, U. V., Bengio, S., Wal- lach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.
Long, P. and Servedio, R. (2011). 1). Algorithms and hardness results for parallel large margin learning- In Shawe-Taylon J., Zemel, R., Bartlett, P., Pereira, F,, and Weinberger, K., editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc.
Malinin, A., Prokhorenkova, L., and Ustimenko, A. (2021). Uncertainty gradient boosting via ensembles.
Mentch, L. and Hooker, G. (2016a). Formal hypothesis tests for additive structure in random forests.
Mentch, L. and Hooker, G. (2016b). Quantifying uncertainty in random forests via confidence intervals and hypothesis tests. Journal of Machine Learning Research, 17(26):1-41.
Musco, C. and Musco, C. (2017). Recursive sampling for the nystrom method. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.
Nash, W., Sellers, T., Talbot, S., Cawthorn, A., and Ford, W. (1994). Abalone. UCI Machine Learning Repository. DOI: http:///do.org//002444///////
Prokhorenkova, L., Gusev, G., Vorobev, A., Dorogush, A. V., and Gulin, A. (2018). Catboost: unbiased boosting with categorical features. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS'18 18, page 6639-6649, Red Hook, NY, USA. Curran Associates Inc.
Rashmi, K. V. and Gilad-Bachrach, R. (2015). Dart: Dropouts meet multiple additive regression trees.
Redmond, M. (2002). Communities and Crime. UCI Machine Learning Repository. DOI:
Romano, Y. Sesia, M., and Candes, E. (2020). Classification with valid and adaptive coverage. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 3581-3591. Curran Associates, Inc.
Schlimmer, J. (1985). Automobile.
UCI Machine Learning Repository.
DOI:
http::/dbi.rr/11.2443////3 102443//CCCBIICC
Stone, C. J. (1982). Optimal Global Rates of Convergence for Nonparametric Regression. The
Annals of Statistics, 10(4): 1040 1053-
Tan, T., Huertas, C., and Zhao, Q. (2023). Efficient and effective uncertainty quantification in gradient boosting via cyclical gradient meme.
Ustimenko, A., Beliakov, A., and Prokhorenkova, L. (2023), Gradient boosting performs gaussian process inference.
Ustimenko, and Prokhorenkova, L. (2022). Sglb: Stochastic gradient langevin boosting.
Vito, S. (2008). Air Quality. http:///bi..r///022443///CCC
UCI Machine Learning Repository.
DOI:
Wager, S. and Athey, S. (2017). Estimation and inference of heterogeneous treatment effects using random forests.
Wager, S., Hastie, T., and Efron, (2014). Confidence intervals for random forests: The jackknife and the infinitesimal jackknife. Journal of Machine Learning Research, 15(48):1255-1551
Williams, C. and Seeger, M. (2000). Using the nyström method to speed up kernel machines. In Leen, T., Dietterich, T., and Tresp, V., editors, Advances Neural Information Processing Systems, volume 13. MIT Press.
12

---

Xin, J., Tang, R., Lee, J., Yu, Y., and Lin, J. (2020). Deebert: Dynamic early exiting for accelerating bert inference.
Yin, X., Fallah-Shorshani, M., McConnell, R., Fruin, S., Chiang, Y.-Y,, and Franklin, M. (2023). Quantile extreme gradient boosting for uncertainty quantification.
Zhao, Y., Dada, O., Gao, X., and Mullins, R. D. (2022). Revisiting structured dropout.
Zhou, Y. and Hooker, G. (2022). Boulevard: Regularized stochastic gradient boosted trees and their limiting distribution. Journal of Machine Learning Research, 23(183):1
A
Matrix Sketching
We first sketch the kernel inversion where we approximate KD & K R R
(x) yn (x yn
SS
= (x) (AI- - (XI->RR S K { R.) yn
-x) (R ko (x) à..
where we define the n-dimensional coefficient vector
2n - RR yn:
and write
AD = (S ( (RP)))) RP) Rx
for our sketched estimate of the inverse kernel matrix. Computing this takes O(ns²) time when is a subsampling matrix Musco and Musco (2017).
Now we further sketch the coefficients ã = (S S E R in line with Appendix C of Musco and Musco (2017):
TP (x) an = (x), RR = = (ko (x), am
When C. KS Roan is precomputed, we can make new KRR point predic- tion in only Oss) time. This is because we only need to compute the coordinates of the vector T:D (x) S Tx)()) (x) E R", taking kernel evaluations, and multiplication with o, = (S K &.a R can be done in O(s) time.
(ss²) time inference. O(ns²) time:
So in order perform inference in sublinear time, we first precompute in
N ARRDS((T Ra
ED = (A
A Rxx
To obtain a sketched estimate of | (x) || on a new test point x, we compute the s coordinates of the vector kP S T (x) E IR and obtain an estimate
[xx
S.PT (x)
in O(s²) time. The equivalent expression
(x)
| k (x)]l2
takes (nn) time.
13

---

No.
Condition
Use
How Satisfied
Tree structure (b) (x) Yn for all 6 1, 1,...
11
Theorem 1; allows kernel
Random tree structures, sample splitting
ridge regression representa- tion
2
Trees eventually i.i.d. ~Qn
8
Theorem 1; ensures aver-
Random tree structures,
aging tree structures has a limit
draw from library of trees.
a-Liipchitz
x(x)
Theorem 2; controls ability to approximate by kernel ridge regression
Structural about data generating pro-
assumption
bounded away from
cess
Shrinking 4
maxi-
Theorem 2; controls within- leaf bias
Minimum probability of splitting each feature
mum leaf diameter sup diam(A) bounded by ((n-1/(4+))
Growing observations per
Theorem controls vari- ance within leaves
Minimum leaf size
4+1 leaf Un = nd+1 tv
natT =((M)
Cardinality of tree
Theorem 2: restricts vari- ance of models
Restrict tree depth, choose library of trees
space 1Q11 bounded by
O(n-1 cxp((05n 1/442)- n)))
Trees Split on Medians
Alg 2 only; Restrict candidate splits controls bias and variance Table I: Table assumptions required for our theory and their use.
Theorem 2:
Sketched hypothesis testing.
Given a hold-out dataset (x)) we test the null hypothesis:
Ho f(x)) = g(x;) for L,... m against Hi f(x;) A gn (x,) for some j
by comparing f (x,). However, given m test points on a test dataset (Xm, Ym) we subsample points with subsampling matrix r to compute the doubly subsampled kernel matrix Rip, (Xm.) S T (Xm)r Rexr, which we only need to perform x kernel operations to compute. So the difference statistic is then given by
dm = (Xm) 0n.1 - Kn, (m)) 0n, = Fon, (2))tnn(Xm)) YER..
A
Modulo subsampling and Nyström approximation error, this is multivariate normal under the null: dh ~ N₂ (0.0²Em) with covariance matrix
ED = ( 2(Xm))))(m)))
Ri (X)m)))) 2 Rx
We then have the test statistic:
22 ( ~ x2 m
The runtime of the test is as follows. takes O precomputation time form N A paxs O(nsr) time for the multiplication with K (Xm). (x.,((,))) and O(n) time for multipli- cation with y. Once one has the noise estimate, inverting the covariance matrix and computing the test points takes (r33) time.
B Table of Assumptions
Table provides a summary of the assumptions we require, a brief explanation of how they are used and conditions under which they are satisfied.
14

---

C Finite Sample Convergence
C.1 Stochastic Contraction Mapping Theorem
To show convergence for both algorithms, we will show both of them are a stochastically contracted process. The criteria of deciding such process be found in Almudevar (2022), and introduce the theorem below.
Theorem 3. Given -alued stochastic process {Ze hEN, sequence of < de S 1, define
Fo = F, oZz,...., Zt),
6 2, R
We call z, a stochastic contraction if the following properties hold
1. Vanishing coefficients
Ar) 00, which implies
II A = 0.
t=1
1=1
2. Mean contraction
B Fi-1]] 1 de || . a.s.
3. Bounded deviation
sup leel - 0,
Σ Bilk <c.
In particular, a multiddimensional stochastic contraction exhibits the following behavior
1. Contraction
0.8
Z
2. Kolmogorov inequality
4v WdEETT+ R[1]
P
sup 12T
24
S
|z
21
min min B3}
holds for all T, > 0 s. 3 = |z +
vdsuptsr ||ec|| > 0.
In the following proof we benefit from the a.s. convergence of the difference vector to 0. And the Kolmogorov inequality gives us a PAC argument
C.2 Subsampling
We will also introduce lemma to regularize the expected tree kernel in finite sample case with respect to subsampling rate.
Lemma 2. Considering subsampled regression tree. Assume that each leaf contains fewer than
पंΣ sample points before subsampling. we are subsampling at rate at least & uiz then the expected structure vector's 's norm follows the rate below:
k = 1
Proof. By Zhou and Hooker (2022), know that ||TE,,.r - [.]] 1. By this know that least | ll2 < 1. The task remained is to give the distance between kkull and 1.
Define the subsampling index set as To see clearly why rate containing would exists, recall the definition of structure vector with subsampling for any x E Aj.
1(xU E A,) E ww) E 1(x, E (i) ExIEs, 1li w)
1(xx E A,) E
n (x)
Sn, S,,
The structure vector is given by
(x) (x), (1) ... 8n, (z)
15

---

Taking expectation we have the kernel vector
P(x:: E A,)P E w)
k =
Ex,E,, P(i w)
Notice the expectation taken with respect to both structure distribution and the subsampling dis- tribution. And this vector is not defined if one leaf is empty, since the denominator would be 0. Let indicator LA denote whether the leaf of interest is empty. It values on the leaf is empty and it values 1 if the value is not empty. The L1 norm is given by:
|
B (8n,A(x) (x)]
k=1
(2) = 0) + (s = 1|P(1A = 1))
If the leaf is empty, then we will have define [. 0] = 0, otherwise the denomi-
nator would be 0 and the whole structure vector is undefined. If the leaf is not empty, we would then want define the conditional expectation such that it sums up to 1:
[[)sn =
Hence the L norm above simplifies to:
1 1
E(smmA(=))L 1]P(LA = =1) =11 =0)
Hence the problem is reduced to finding the probability of missing all subsampled points in leaf of interest.
By assertion, the subsample size should be Ên n++2 2 log n. Consider the probability that one leaf misses all sample points p(n, E). That is, all the subsampled points sampled are points that are in this partieular leaf. Thus only choosing with choice (" ("-n 8+2
On
F(n,))=
En
En
(n
En)(n
En 1)(n - En -2. ... (n
En ntz + 1)
n(n 1)(n 2) ... ..(n n + 1)
n=#2
71 En
11 1
1 - {
n
8+2
1 n
n0#2
log
n
natz
notz
(1
atz
logn
#42
Notice that
1
1 + n
<
71
443
71
16

---

n n
11
na#2
+ n 052
3e
And meanwhile recognize
log 11
(1 n 2+2 log
(1-
a+2 log
log
1
elog
Hence we have
242
(1 (1-
n (1-n
ata log
n
d+1 242
1t.
noto
Se. (1 1- n 21ड logn)
Hence the probability of single leaf missing all subsampled points is of rate O (H). And hence [|k,]] = (H)
C.3 Proof for Theorem
Combining all the results above, the proof for Theorem is as follow.
Proof. To show Algorithm is stochastic contraction mapping, we aim to show the conditions 1-3 are satisfied. Define the difference z, := Re+1 y And define the partial ensemble y. :=
E XaTR, Xs
s,dd. Ber(g). To check mean contraction, first notice as + co, tr(Var(ý))) S Hence with b large enough, we can get rid of the truncation.
gl (1-9)uM
b
X Sn TM 3" Fo-1
E 21 1o-1]11=
E
bb-1
b
b
A T B[Sal(y ET M (J 1) F 1])
(fo-1
8*)
b
18
8'1l
R.s.. - E[T Fr 1))
2
E[S.,[( 28
b
b
EIS ET
b
1 E|Sw -E IF
b
+ Xq
118-11
- 5"1l S 18--11 - 8-11
Next we check for bounded deviations.
||a/| |u. Fo-1ll ||l
17

---

1(5 8* - (E - -
[E| - Sx) - (Vb-)) RIT Fo-1)) -))
1n [| - S ||Y - T-M + (5-
Now, by Zhou and Hooker (2022), know S. has both row sum and column greater than 1, hence see that [E Bm | & vix Vn. Then, it can be seen that
A ||bl|| S b (1 + vn) 2M
Then we can show that Σ Similarly we can show both conditions for Algorithm 2. Replacing the stepwise difference according to the new update rule gives:
( o0.
| 26 Foll
E V 1+1K
VK
Full
b
Yo.K + b+1
E[Sn]
Σ (y Fo,b2) -Fk
b+1
k=
b
Vo.K
E[S,]
y (Fo. -IM Σ E.,k)) Pxx
b+1
b+1
k=1
g=1
b K
K
Fo,K
E[Sm]y
E[S.1/e. +
E(S,.] Σ M (3 Σ (g.k)
8ix
b+1
b+1
b+1
b+
9=1
K
b
1
(bT K (Fo.x - -ix) +
E[S,.]
T
(b.
Σ [gik) FPx)
b+1
b+1
km
9=1
K
S
1
|0 KEK
E[S..] 115. - 82ll
+ b+1
1
||B[S,]||
Σ
r as (1
> (y.k) - -8
b+1
Am
9=1
K
1
|6 K
E|S 18.K 9kll
1
||E[SA]]
Σ
Σ mn, 92
b+1
b+7
9=1
1
([ KK [E(.,,111 18.. Vr
b ++1
1
(b+ 1- o())) 15r, ykll
+1
Hence we have checked the mean contraction condition. Checking the bounded deviation condition works in a similar way for Algorithm 2 since it shares the same expected tree kernel with Algorithm and the tree signal is also bounded by M. Hence the stochastic contraction mapping follows.
D Conditional CLT Around KRR Predictions
Doing so requires control on the weighting vectors (z)) And we will begin such analysis on giving the rate of the expected structure vector (x) first. This is because recall that in both algorithms our final weight vector (x) is linear map of the voting vector k,, (x). begin with, we will first notice that Lemma 2 implies Lemma 3.
18

---

D.1 Bounding the weights
Lemma 3. Suppose the assumptions for Lemma 2 are satisfied. We have Ei= rn. 1t29
( -
Proof. We begin with the analysis on Algorithm 1. Consider the expansion
A + sknn
= =>> (Aq)) (Aq) 2 -
We examine the column sums of each of the matrix powers. Start with K2
[ Σ> (
Σ (K)) [KK).s.
j=l
Take subsampling in to consideration, since Kn consists of structure vectors of sample points, hence for some can bound the sum:
Kn)ss S1, i= i=
n
which also hold true for
c
<
K Kn)ja $1 i= 1=.....,
Given K, is nonnegative, multiply the inequalities above and notice it is actually the row sum of K2, we have
(1
(1-
9 2 S
Σ (K,) j.1
Kn)es S 1.
1=1
1=1
Repeating the same procedure above yields
(1
C
m
K 1,1 1.
n
Therefore,
Ag
n
+ KK,
1 12 - 2)2
1 X²q²
j=1
1.2
= Y
Σ (Aq) KK 21
111 - (2g)22 (x 222 )
21+1
(K2it
Ag
X29²
1 X2 -1,
where both the LHS and RHS reduce to I+Ag + ( So true for any column sum of
[k,] -1 And we know that k2 is nonnegative and - | = O (+) and kn simply reweights the columns. Hence we prove the convergence of weights Σ Pn,i for Algorithm 1.
And
The analysis for Algorithm 2 is similar. We simply substitute = K24 = K-1 This will give the bound:
K
K - 1
K
K
K
1- (K 1)2(1 -1 1 1 K 1)2
K
K
K
Σ
(K
(K 23.1 (K
(K1))2++1
(K22+1) 1)25+((K2)+))
19

---

K - - (K - 1)3 9)²
< K
1 (K 1)2
We can reduce both sides of the inequalities to + ( similarly. That proves the converging weight of Algorithm 2.
Intuitively, knowing that the weights sum to (almost) constant tells us the total "mass" of our weighting vector fixed. we have leaf size assumptions such that no single weight can be too large, the mass must be spread out over many small pieces. Whenever you distribute a fixed amount of weight across many entries, the Euclidean length of the vector necessarily shrinks. other words, near-unit & norm plus bound on the largest coordinate forces the Eg norm to be small. We control the rate of r D.P in Lemma 1. To do so, we need to both upper bound and lower bound [k, Il. which
helped by Assumption 5, implying inf AEgEQ.. E 1 (x, E A) S2 3FT
D.2 Proof for Lemma
We will make use of the Q 3+ in Assumption 7 to control ||<,]] and ||ra]]- The first bound in the max operator is vital for our unconditional CLT analysis Lemma We will first show Lemma which is sufficient for us to get a conditional CLT.
Proof. To bound ||, ll. recall:
1(I, EA) Σ 1(r A)
knj [[(nn(()) E
x A
encodes the expected influence of point Ty on point of interest among other n points. Then the condition
inf AEgE
Σ 10, E A) 2 Ω n
implies that kng = 0 a#1 since we can't have total weights more than O(1) in a leaf. By
Lemma 2, || I 1,
kk S / //aulla = -0(
By assetion |Bx| = 2 (n d²), there are at most
a (n dh) 52
2
knj's that are positive. Equivalently, we can have the magnitude each non-zero kng is lower bounded by n 2'1 This holds also because the total weights can't be larger than O(1). Since ||k,|] = On-
- = Ω ( | = Ω (v(r कों
To check the rate of ||rall- ll. since rn is mapped from kn by the KRR matrix. For Algorithm 1 it's [ + gK,]] and for Algorithm 2 is [ + K-1 K-1K,]-1 and we know K
eigen [ sk,, 1') < X, 15 eigen
( K K
Kn 11)
SK
1 Aq
Since we can fix K to be a constant, ||r/]] will enjoy similar rates as |
This rate complies with the Lindeberg-Feide conditions, hence establish the conditional CLT.
20

---

D.3 Conditional Asymptotic Normality on Training Set
Theorem 4 (Conditional Asymptotic Normality for BRAT-D and BRAT-P Predictions). For any E [0, 11 write f(X,)) = (f.x))...., f(x,)) Then under Assumptions 2, 4 and assumptions Lemma I, we have fD. (x) (TD.P. f(Xx)) N
D.P.
I'n
Proof. For notational convenience, since ||r, yielded by both Algorithm and Algorithm shares the same rate in n, will suppress the notation of D, P in this proof, and denote the kernel ridge regression matrix respectively with KRR and KRR". Also define cº T+x0 1.
Write
(x( - f(X,) r
To establish the CLT, we verify the Lindeberg- Feller condition for the triangular array TT i.e. for any 8 0,
lim In
E
||r o,] = O. >
Since || =0 (n and KR having row sums of CD.. + (n()))
we have
1 - 100 KRRD.P| = 0 (n a+1
Furthermore, since ||r, O(n ) ) we get
| rnll
= 0 (n (n-
This allows us to check out the Sindeberg-Fellee conditions:
E [(rne6s) (prnits) > |r []] <
2 nd
IE[1 (prnitsl
> 5 r 22)
t=1
n
8 1|rrloo
mmi [E(E]]
P |eal
Tni
(811rallo 2
1
mi V
ecx
-02
Tné
-=1
[x exp (-0 (nehs)
<
0,
Since is sub- Gaussann noise, the concentration bound holds by definition of e. This concludes the proof for Theorem 4.
E Extension to Random Design and Exponential Locality
Now move to the discussions in which our input to the model is longer restricted only to the training set X,, but to any x E [0, 1]d. To do so, we begin by defining a new probability space and, of course, new probability measure. This can be uniquely designed by Kolmogorov's 's extension theorem.
Write the coordinate projection II, = (TT, (X) (E)) as the finite-dimensions projection contain- ing the first n samples. Under this framework, we can obtain the corresponding expected struc- ture vector kn, expected structure matrix (kernel matrix) Kn and the standardized prediction error Pn (X, é), given by
Pr. (X e) fx: (KT (x; II, KRRR D.P (II.), f(L,))
k (x: II,)) K.RRR.P
21

---

Here, Pn denotes the prediction error after using n random samples incorporating both the dropout mechanism and the sample randomness.
To prove our desired CLT under random design, we need to first introduce a lemma that allows us to propagate the normality from fixed sample to random sample cases. This is taken care of by Lemma 8, which allows us to claim our CLTs if we verify it being correct for a.s.Vx E [0. 1J". Then, we seek almost sure validation of the assumptions of Theorem under the random sample sequence II, = (Ta(X), Ta (E)), which is helped by our Assumption 6. Formally, it is as shown below:
Lemma 4. Suppose we have random sample {(x: y:) C [0, 1] x I for each If for any small ax v s.t.
1Qml 100 exp ( n (
na)) ))
(
then
TD.P(x)
(TR.P [(Xx)) و ((
I'n P.P.
Proof. We will direct the reader to Zhou and Hooker (2022). Despite the introduction stochastic- ity in dropout, extending the CLT of 4 does not require additional effort. The intuition for the proof as follows: By restricting the tree space, one bounds the probability of the assumptions being vi- olated to be summable, and per Borel-Cantelli will take place almost surely. Tree space cardinality here gives a nice union probability bound to achieve that.
We define the following notation for later use: For any nevecttr e and an index set D, denote
f1 1(1 E D)
Un 1nn D)
This implies the decomposition that v 1 De
We almost ready prove the main theorem. However, check Lindeberg-Fellie conditions under random design, one needs to establish exponential decay of points that sit far away from the point of interest. That is, ||r ID= for well chosen ball centered x needs vanish to 0 rather quickly. And we prove it in the following lemma. To control this for Algorithm 1, we have the following lemma:
Lemma S. Given sample ((x; and a point of interest x, set bn
log
Ca log ni. ei
log
log Aq
and define index set D,, (i [x; x S In d then
r D
0 -
Proof. Let's first write out the expression of the desired peripheral points:
r
DE
X- 1>
Recall:
1 1(x, E A)
h = E E(s (x))
kny
E[snn (x)) = E
Σn 1(x, E A) 1
This term would be zero if two points not even in the same leaf,, i.c. xx - x²1 dn. Hence the sum inside would be simplified to
Σ xx >1
Σ
knj
- + gKn
|x)-x/Sd,
22

---

And also notice, by decreasing d, to (4n - 1)dx, we are actually allowing more peripheral points outside the local region D,, and hence we have the inequality at line below. Completely, it given as:
F
Σ Di
Σ
Σ
kinj
I
+ qkn
DE
xx xx
dn
x
xi porte th
1/
Σ
knj
I + g
x-xx Iili
lx-xxylsh
5.8
knj
E
J I gk
x X; SSd
knj
E
1 I + 9k
X,y (dd,
(xs |x)-Xyl 12 -1)-a
Σ knj
Σ
Σ (Ag) (
X Sdd
|x1-xy X3 1>1(a (/-x//2(aa
13ida
1=hn
knj Σ (1g)
x x-xy Sdn
1=hn
(Ag)
1 Xq
The lower bound in the sum of the powers of K,, follows this argument. To compute higher powers of K,, consider how entries of K2 are calculated:
Σ
Kn Knli,kiJK,n [ki, K2] Kn 11,5]
For Ki [1,5] of O, there must exist chain of intermediate points (ki, k2,..., k--13 such that:
Xx X S
dns
[Xk - xx2l S dns
[ - xyl S dn.
By summing the distances and by a triangular inequality, the locality condition propagates:
Xyy S dd
where is the number of steps (or multiplications) required to connect and Iy through the inter- mediate points. Now notice the summing condition x æ,5 > (I, 1)d, requires us have such chain that is longer than L since such chain doesn't it exist at all.
least. Hence the kernel's power K' would be 0 for any I S L, 1,
To control weights from distant points for Algorithm 2 is bit more complicated. We need to make use of Assumption 7. This assumption is inspired by the definition in Athey et al. (2018), where state below.
Definition 3 (a-regular tree predictor). A tree predictor grown by recursive partitioning called a-regular for some
if either
1. (Standard case) each split leaves least a fraction a of the available training examples on each side of the split, and furthermore the trees are fully grown to depth k for some k E N. Equivalently, every terminal node contains between k and 2k observations;
2. (SVI case) It satisfies part (a) when applied to the sample used to fit the leaf value. In this case this will be our response vector Y.
Lemma 6. If tree is 2 rregular with the terminal leaf size being lower bounded by k. where ls is constant, then the operator norm of P is O (1).
23

---

Proof. Define a- = max(a, 1 1111-- falling into the same leaf after one split would be upper bounded by a. And since we have the minimal terminal leaf size requirement, for any leaf with depth d, it should comply with:
a). a)
By definition of a-regularity, the probability of point i.
{ k f a S 2k 1,
k $ (1 an)"n 2k 1.
which translates into In]] In( 1 S d m (
n
Notice that the probability of two points sharing leaf is the probability that they survive all splits down the tree. Then we can bound the collision probability by:
Pi.j S 0 Amin
dn? In(
2k-1
lnil
a+
2k
lan. Ti(] 0oJ
2k 1
log: -o.
2k:
1
Then =.p.5=001
Well-behaved leaves exclude non-decaying distant weights. Formally, we prove the lemma
below:
Lemma 7. Given sample (:) and a point of interest x, set ln In(E/2)
In
ln and
define index set D, = {i: [x4 - x S In d. then
p D
Proof. We will use the same matrix expansion technique used in Lemma5. By analogy,
r
Σ
kaj
K
DE
K
K
|x bx=x:|Di,.dd d.
x by dh
Σ
knj
+
K
1
K
x- x; So
xx (S-x
4.b
knj
Σ
K
Kn
x Sdn Sdh
3.8
knj
Σ
I+
K
Kn
K
K
1x-X, Sdn
[x) 1x)- (l1-)dd
knj
Σ
K
Σ
(-1) - 13
Sdn
(x| 1x1-2|12(1n- (1):chh-
Lm
Σ
kng K Σ(K- -1)
Σ
||C
x X3y Sdn
12hn
|xc xx11>> d)
1x:-x;1>1
Σ
KnjK K
Σ (K 1 1)¹
||c]
Sdn
12hm
knn K
(K-
(K - 1)¹
|K
Sdn
12hn
24

---

Σ Sdn
kny K
E(K - 1)² Knn ll'00
12
Denote the probability of any point xi, Xj sharing the same leaf as Pij- By definition of the kernel matrix, we can write each element as:
Knkes
Ey
[
Ew
X xy are in the same leaf Pij
E X Pii
where Binomial([ma (m, M), E), with m being the minimal number of points in a leaf and M being the maximal number of points within a leaf. Since X = m..... M,, it follows that X S almost
surely and hence
1 s me. Then by assumption m max (12 (n गंं
K K-1}. it follows that
B
R
Hence we have
Σ
knj Σ (K 10K--11110 K
S
DE
xx 1x-x,lSdn
12
5¹
Σ
Kng K
Σ
(K - 1)¹
2'K - 1) |P]|
|X- xx
12hn
el
Σ
knj
K
(1)
27
|x xsdx
12h
(1)
=0
F
Proof for Theorem 2
Combining all discussions above, we present the main result Theorem 2 of this paper.
Proof. Define cD= 1+2q and cº = To begin with, we will show that for Vx E [0, 11%
D.P. (((x))
D. f(x) P
D.P
I'
Let APP = consider the following decomposition:
-DP -.P D.P 0 (n and f(x) = (xxx))...,[(()) an n-vector. We
i= n.i
...
(r f((x)))
c..Pffl f(x)
(r f(x,) f(x))
A.P. -(xx)
D.P
I D.P
D.P
A fxx)
(T
,f((,,))))
f(x)) p.)
(r
(f(x,) F(())] mz)
Dr,
+
D.P
D.P
D,P
rn
rm
rn
By 4, we have
| = Op(n - 1| Op(n =221s).
25

---

Notice that
D 1 11111((x.)) fx))] = =0p ( 12.2g =0, (n
(rD Ing lf(x,) - f(x))l DE.
- p
D.P
Hence we have the second term
(m P
(f(X,) f(x))ln2) 3+0.
D,,
D.P.
I'
And by an argument earlier PA 0 (n-1), thus
A f(x)
||rml _ 0.
Meanwhile, we can show similarly |Dnl = S2p (n- (Lo - dn)")) a.s.. And recall our underlying
function is a-Lipischitz, therefore
D.P (r D
[f(X))
f(x)]l
|
f(x)]lba
Dr
1
D.P
I'n
1 [f(x,)) f(x))l
(V n. (Lnda) (In a)2
Op (Vn (logn)dtt..oo . gd+2
Og (Vn- (n.(logn)dtt (logn)d+2. 741
Op (logm) 2 -
Therefore
(T..PP f(X,))
D.P f(x)
D.P
I'n
Slutsky's Theorem then yields
f
(x)
D.P
f(x)
fa(x) - Pr.. .((,)))
(T
- -.P.f(( ((x)))
d (0(0,0))
D.P
D.P
D.P
I'
In
Pn
G Coverage Rates and Risk Bounds Guarantees
In this section we provide the proof' for coverage rates and risk bounds guarantees we gave in 5.
G.1 Proof for Corollary 1
Proof. The corollary holds by noticing that the variance of the scaled prediction of Algorithm is (*+ | di o²_ Plugging in the rate of ||r-2|] by lemma yields the risk bound. Similarly this can be shown for Algorithm 2.
G.2 Proof for Corollary 3
Proof. We will show this convergence for the confidence interval Algorithm 1. For Algorithm 2, replacing the asymptotic variance and the final rescale constant will follow the same proof.
26

---

Denote the staged empirical coverage rate of the built-in confidence interval at any point [0, 1]
- D (x)x)) 1 Σ [((x) ==1
[(cP c² 1|r 21-0/20, c Fx(x) + c. 1|r =1-0/20]
Notice that with b + have fo + fox. Hence, sending to infinity and drop the subscript for denote the coverage at infinite epoch.
1- ( = Σ (((x) [c) - -||1:11 21-0/0,, cD fxo + +c0l1 =1-0/20|
which is equivalent to
fae (x) c² f(xx)
1 n 1
21-0/2
|r
Since the indicator function is always finite, by SLLN:
(x) f(x)
a
(x)
" E
-1 / 21 -1/02
||T
foo (x) (x((x)
21 a 21
||r
-
For prediction intervals, we observe data according to the model
y f(x) e,
((,
and our infinite-epoch estimator satisfies the CLT
fac (x) N(c" fxx), |r as b oo.
Since Fax (x) and the new noise are independent Gaussians, their sum
y = f(x) - c fxx c Foo te =N (c (rr || +0²)
And we produce prediction interval with the empirical coverage rate evaluated
1 Pl (x)
Σ [(x) e [(off((x) - V(DD 11) + 1- 21 21-0/20, c fa(()) + V(cP I1)))
+ 1 21 a /2/
n
By similar argument above, sending n, b + oo gives almost sure convergence.
Regarding the reproduction interval, since we will have independent model following the CLT in Theorem 2, their difference will also follow a CLT centered at zero with a variance inflated by factor of 2 by independence. So we construct the reproduction interval such:
1 aRl (x)
7 (x) E (x)
1122)1171) (x) + 22r201|121)1 [|
n
And by similar argument prove almost sure convergence.
27

---

G.3 Proof for Corollary 2
Proof. To give PAC argument, decompose enror into statistical error f.(x) f(x and algorithmic error fx(x) fx).
From the Theorem 2, (r((f(())) f(x)] > s) S 2exp Nebry n I1d+1)) Under the stated lower
bound on this probability is S 8/2.
To quantify the algorithmic error, we wish make of the Komolgorov inequality in Theorem 3.
For VX [0, 1]s, let fo(x) be the stage-b predictor, let fx) be the fixed point defined in Theorem 1, and write
2 (x) = fx(x) fx)..
= E E[2, F6-1).
It holds that the process 2 (x) is eventually also stochastic contraction mapping by the exact same argument we made in proving Theorem I, only replacing K,, with k, (x) which still have row sum smaller than 1. And even we only have in probability guarantee of the staged mean contraction condition hold, since we are doing truncations and we can get rid off it after sufficiently large b, still check out the mean contraction condition Σb= Xb) Kolmogorov Inequality given 3.
Hence we invoke the
Consider the decomposition:
Pr(sup z > 12b
E) S Pr((lll > 2) Pr(sup Izcl > [2bl + 5) 12b
Because the SCM conditions are satisfied from onward and E.so [R(e]] S C2/b., where C' 21 + vn). Theorem 3 gives the Kolmogorov's inequality below. Specifically, we can choose 6 such that the numerator m 2 á for suffieciently V, where 83 = 2/2 + |zel
Vdsupi ||e/]| when b = Ω
m22m²) (28
Hence
4.1. (C2/b 4-1-(0%/6)
16C
Pr(sup |z:| > 12ol + : 12b
min 2 5,33)
(e/2)² 22b
Since lcal S C, V, = Σ
Ble < x²22//6 /6 < 2C
1=1
Set the martingale sum Sb Σk=1 k= Cj. Because |z I |2t11 + |c]. telescoping gives
2 Zool + |Sp]
< .M [Sp].
Thus the event {[za] e/2} implies [Sa] (e 2M)
Freedman's maximal inequality for increments bounded by and quadratic variation S 2C yields
(e - 2222
Pr( |20 > $) Pr(IsA) 2-2
< 2exM
16
Then the non-asymptotic algorithmic error bound:
Pr Pr(1zo [x(z((x)] > <) < 2exp(- (e 4M)2
16
C 21M vn).
16
e2b
With the stated lower bound on b this is < 5/2.
H
Miscellanious Lemmas
Theorem (Kolmogorov's 's Extension Theorem). Define the random variables:
X (2,,X,,..) E [0, 1]dxN
E= (E1, ..) I²
28

---

The probability measure on [0, 1]4x8 and R are uniquely determined by their product measures on the cylinder spaces, reflecting the i..d. sampling of X and é, such that
Y: = f(x:) + CG. iEN
Lemma 8. Let X : 22 - S and U2 - S be independent random variables. Assume (Sr SxS - RJ sequence of measurable functions. Suppose that for almost surely x Oi and 6E92
(n(2,e) 4 N(.,
Then:
(x(X,e) S. 1).,
Or equivalently
lim (X, 7)) = (1))
Proof.
lim P(, st) lim // (s,())))) du due
(5)
lim / [([u(zz S St) dje
(6)
lim P(n t) due
6(1) du +(1).
(8) is justified by the Fubini theorem since the indicator function is always non-negative. And (9) guaranteed by Dominated Convergence Theorem since the integrand is always bounded (with assumption of it being sub-Gaussia Gaussian density of e).
29

---

I Mean Squared Error on UCI Machine Learning Repository
We provide further results for the MSE of our methods, benchmarks, and competitors on six addi- tional UCI datasets. The dataset we are using this work are from: Nash al. (1994), Vito (2008), Schlimmer (1985), est (2019), Cortez (2008), Cortez et al. (2009), Redmond (2002).
The hyperparameters chosen by Optuna listed below:
Table 2: Abalone
Hyperparameter
GBT
XGBoost
LightGBM
RF
BRAT-D
Boulevard
BRAT-P
ElasticNet
estimators
500
500
500
500
500
500
500
learning-rate
0.0213
0.0249
0.0108
0.5476
0.5750
0.2724
max_depth.
10
16
subsample
0.6332
num num_leaves
37
alpha
0.1299
11_ratio
0.3753
min_samples.epli
43
42
subsample rate dropout rate
0.5071
0.5133
0.6266
0.4766
0,0000
n.trees.per-group
16
Table 3: Automobile
tlyperparameter
GBT
XGBoost
LightGBM
RF
BRAT-D
Boulevard
BRAT-P
ElasticNet
n. eestimatooss
500
500
500
500
500
learning.rate rate
0.2019
0,2153
0.2341
0.9411
0.1416
0.5671
max max_depth
3
8
14
6
11
aubsample
0.9850
num nemvleaves
alpha
0,3634
1i-ratio
0316
min_samples_spl
23
9
30
aubsample_rate
0.9368
0.9899
0.7344
dropout rate n trees per group
0.2145
0.0000
16
Table 4: Communities and Crime
Hyperparameter
GBT
XGBoost
LightGBM
RF
BRAT-D
Boulevard
BRAT-P
ElasticNet
nesstimators
500
500
500
500
500
500
500
learning_rate
0.0224
0.0379
0.0215
0.6904
0.5772
0.3578
max_depth
16
15
16
subsample
0.5375
num_leaver
20
alpha
3.8079
1i.ratio
0.9556
min
han.samples.epp
35
49
subsample_rate
0.7385
0.7209
0.5148
dropout.rate
0.1903
0.0000
strees_per.group
30

---

C10
0003
C.08
600
6403
6.03
50
400
AIDS Ciinical Thals Group Study 175
Communities and Crime
300
Ensemble Size
Ensemble Sizee
LightBM
300
GET
100
Boulenard Darbblet
BIAT
3e-33
10-32
PASE
0009
0.00
0005
1500
Figure 6: Mean Squared Error on UCI Machine Learning Repositories
500
Infrared Thermogr apmm Temperatte aaturer
400
Student Performance
300
Ersemble Size
Ensemble Size
LightSMM
300
GBT
100
Boulenerd Elattoe Net
BEAT O
BPAT
1--0
200
MSE
6399
4003
0355
030
0376
500
465
36
Ensemble Size
Ensemble Size
Abalone
Automobile
Light00 MORH
AP Xclloom
200
GRT
100
Rowwaard
Elattchltt.
0RATP
50-03
M5E
31

---

Table 5: Wine Quality
Hyperparameler
GBT
XGBoost
LightGBM
RF
BRAT-D
Boulevard
BRAT-P
ElasticNet
n.estimatora
500
500
500
500
500
500
500
learning rate
0.0731
0.1139
0.1186
0.8396
0.8905
0.8200
depth
10
10
16
20
15
15
16
subsample
0.6980
num numvleaves
42
alpha
3.8079
11_ratio
0.9556
min min www.samples.o.mm split
4
2 0.7431
13
subsample rate
0.7317
0.6669
dropout aropout_rate rate
0.2762
0.0000
sxrees-pergrovee
10
Table 6: Student Performance
Hyperparameter
GBT
XGBoost
LightGBM
RF
BRAT-D
Boulevard
BRAT-P
ElasticNet
nesstmatorss
500
500
500
learning rate
0.0177
0.1836
0.0218
0.9256
0.8698
0,9824
max max_depth
3
5
11
3
9
subsample
0.5780
num_leaves
38
alpha
0.4855
11 ratio
0.1373
min samples split
39
32
48
subsample rate
0.8418
0.5249
0.5964
dropout.rate
0.1230
0.0000
n.trees.per.group
13
Table 7: Obesity Level
Hyperparameter
GBT
XGBoost
LightGBM
RF
BRAT-D
Boulevard
BRAT-P
ElasticNet
nessimmaoors
500
500
500
500
500
500
500
learning_rate
0.1905
0.0916
0.0834
0.2487
0.5382
0.3643
max_depth
7
16
16
16
subsample
0.8121
num leaves
25
alpha
0.2182
11.ratio
0.00
min han.samples.epp split
3
3
subsample_rate
0,6466
0.7153
0.5595
dropout.rate
0.8079
0.0000
strees_per.group
32

---

Table 8: AIDS Clinical Trials Group Study 175
Hyperparameler
GBT
XGBoost
LightGBM
RF
BRAT-D
Boulevard
BRAT-P
ElasticNet
n.estimatora
500
500
500
500
500
500
500
learning rate
0.0177
0.0226
0.0108
0.8519
0.9137
0.3010
depth
3
5
4
4
subsample
0.7530
num nemveeavss
37
alpha
3.8079
11_ratio
0.9556
min san.samples.oo split
12
27
46
subsample rate
0.5335
0.7374
0.5342
dropout propout_rate rate
0.3421
0.0000
n.trees.per group
Table 9: Infrared Thermography Temperature
Hyperparameter
GBT
XGBoost
LightGBM
RF
BRAT-D
Boulevard
BRAT-P
ElasticNet
n. esetmmatoors
500
500
500
500
500
500
500
learning rate
0.0289
0.0167
0.1836
0.7616
0.6558
0.9864
max depth
5
20
3
3
subeample
0.6988
num leaves
24
alpha
3,8079
11_ratio
0.9556
gun_samples.splet
subsample_rate
0.5055
0.5438
0.6371
dropout rate trees per group
0.2395
0.0000
The learning rate for BRAT-P is only valid in the first vanilla boosting round. After that, all trees are fixed with learning rate
33

---

J
Rainclouds for Interval Coverage
Following the discussion in Section 6, we present more raincloud plots below:
Built-in Confidence interval
Built-In Reproduction interval
Built Prediction interval
Conformnal Pred iction Interval
Model
Models
Models
Models
0.75
035
3975
0.92
026
C59
Coverage
Coverage
Coverage
Models
Models
Models
Width
Width
Wiath
Width
Paints
Points
Coverage
Coverage
Coverage
Coverage
Paints
Points
Points
BERONGAS
Width
Width
Wisth
Width
Figure Moderate coverage, where there is neither overfitting nor underfitting.
(a) Test size: 200; Model Replications: 30; Ensemble Size: 200; Learning Rate: 0.6; Subsampling Rate: 0.8;
Dropout Rate: 0.3; Maximum Depth: 4; Nystrom subsampling rate: 0.1.
Built In Confidence Interval
Built In Reproduction Interval
Builtin Prediction Interval
Conformal Prediction Interval
Models
Models
Coverage
Coverage
Coverage
Coverage
Models
Models
163
191
Width
Width
Points
Points
33
0.09
0.99
0.00
3.3
000
Coverage
Coverage
Coverage
Coverage
Points
Points
Width
Width
Width
Width
Figure 8: Wide coverage, when there is overfitting.
(a) Test size: 200: Model Replications: 30: Ensemble Size: 200; Learning Rate: 0.3; Subsampling Rate: 0.8;
Dropout Rate: 0.3; Maximum Depth: 6; Nystrom subsampling rate: 0.1.
34

---

Built--in Confidence Interval
Built--in Reproduction Interval
Built-in Prediction Interval
Conformal Prediction Intervel
Models
Modells
Coverage
Coverage
Models
Models
Wilth
Width
Width
Width
Points
Points
Coverage
Coverage
Coverage
Coverage
Points
Points
50
Width
Width
Width
Width
Figure 9: Narrow coverage, when there is underfitting.
(a) Test size: 200; Model Replications: 30; Ensemble Size: 200; Learning Rate: 1.0; Subsampling Rate: 0.8;
Dropout Rate: 0.9; Maximum Depth: 4; Nystrom subsampling rate: 0.1.
35

---

K Visualizations of Interval Coverage on a 1D Signal
As an extension of Section 6, we display more visualizations of our intervals ID interval.
Conformal
Dana
Dana
Feedctin
Feddctions
Prediction
Predict on Mean Conformal
Meon
Fue Funcion
Thae Fundtoo
Tuc Function
Tue Fundioon on
0.0
02
04
06
0.0
10
0.8
52
0.6
06
08
1.0
0.0
02
04
06
0.8
10
06
02
0.6
06
08
10
Figure 10: Moderate coverage, neither overfitting nor underfitting.
Ensemble Size: 300; Learning Rate: 1.0; Maximum Depth: 8; Subsampling Rate: 0.9; Dropout rate: 0.6
Conformal
-2
Mean Pred
Eaming
Predctionns Mean
Meen Prediction
Twinnng
Presict
Mean
Mean
Mean Conformal
Funciss
Thae Fundson
Tuee Function
Tuu Fundtion
0.0
02
04
0.0
10
6.0
02
0.4
0.
08
1.0
0.0
02
04
06
0.8
1.0
06
02
0.4
0.0
08
2.0
Figure 11: Low coverage, overfitting.
(a) Ensemble Size: 100; Learning Rate: 0.3; Maximum Depth: 12; Subsampling Rate: 0.6; Dropout rate: 0.3
Pi
Conformal
15
-5
Twiing Data
Teming Data Mean Prediction
Theniin Near Frediction
Klean Prediction
Predictions Moon
-10
Klean
Mean PI
Near Conforma
Tue Fundzon
Tue Funcion
Tue Funczon
Tiue Function
0.0
0.2
5.4
00
08
1.0
0.0
02
0.4
0.
0.
1.0
0.0
02
0.6
06
08
10
0.0
02
04
0.
08
3.0
Figure 12: High coverage, underfitting.
Ensemble Size: 100; Learning Rate: 0.3; Maximum Depth: 4; Subsampling Rate: 0.6; Dropout rate: 0.6
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes]
Justification: The abstract and introduction state that we (1) propose both random-dropout
and structured-dropout boosting algorithms, (2) derive their asymptotic normality via CLT, and (3) establish finite-sample statistical rates. These claims correspond directly to algorithms definitions and CLT statement in Section (proof in Appendix E). Statistical rates are given in Section 4 (proofs in Appendix G). Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: We explicitly acknowledge in Section 7 that theoretical guarantees rest on strong assumptions (structure- value isolation, non-adaptivity, and tree regularity) which may hold in practice, and outline the need relax these; we also note that our meth- ods are currently limited to regression and discuss challenges in extending to classification, survival analysis, and structured outputs. Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
37

---

Answer: [Yes]
Justification: The paper mainly introduced two modified boosting algorithms: Algorithm and Algorithm 2. In Section 2 and 5 we introduced all assumptions needed for our follow- ing results hold. Both algorithms are shown to converge to fixed point in Appendix C. And the corresponding derivations of CLT's are provided in Appendix E. Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the of the paper should be comple- mented by formal proof's provided in appendix or supplemental material. Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All parameters used produce the presented results are either provided in Section 6, or provided in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (c.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code
38

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes)
Justification: We include all data-processing scripts, model training and evaluation code, and README with exact commands and environment specifications in the supplemen- tary materials. All UCI datasets used are public and instructions for download and prepro- cessing are provided. Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurIPS code and data submission guidelines (https://nips... cc/
cublic/guides// www.eedsuummssiooooooooo
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
ct/publiccppcpccccoccpcccpc guwdgg/ie/////e sewidde/oeeeuueeeeeeeeeeeeeeeeee Stt//eoddeuiiiiicc ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We describe our train/test splits, evaluation protocol, and Optuna- based hy- perparameter optimization in Section 6, with full model settings tabulated in Appendix Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of
detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Ye]]
Justification: In MSE races, we run models for replications and fill the mean MSE trajec-
tories + In coverage rate simulations we provide kernel density estimations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
39

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text. 8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: All experiments were run on an Apple MacBook Pro (2022, Apple M2, 8 GB RAM); individual runs took under 2 hours and the full suite under hours. These modest requirements mean the results can be reproduced on any modern laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https https://neute http:::///eeeppppeeeeee wwtpppccl///eeeiiecccee httppblii//tiicccttceleeeeeeeese Answer:
[Yes]
Justification: All authors have reviewed the NeurIPS Code of Ethics and will preserve anonymity.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid-
eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work develops statistical inference tools for gradient boosting in tabular regression-a foundational methodological advance without specific application domain or direct deployment context. As such, there is no clear pathway to societal harms or benefits tied exclusively to our contributions. Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no socictal
impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimeess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate point out that an improvement in the quality of generative models could be used to
40

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)? Answer: [NA]
Justification: Our work focuses on statistical inference for gradient boosting on tabular regression tasks, involving no pretrained networks, scraped media, or high-risk generative models, and thus does not pose significant misuse risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite each UCI dataset by name and reference (all publicly available under the UCI Machine Learning Repository terms), and we reference the original papers for all libraries and methods used (e.g., XGBoost, LightGBM).
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode wwwoee. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of a dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
41

---

Justification: We do not introduce or release any new datasets, codebases, or pre- pre-trained models-ouu our experiments use publicly available UCI datasets and standard libraries. Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: All experiments are done on sythetic dataset existing dataset from UCI repository.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: All core methodological components were designed and implemented by the authors. Any use of LLMs was limited to writing, editing, or formatting and did not influ- ence the scientific content originality of the work. Guidelines:
The answer NA means that the method development in this research does involve L.LMs as any important, original, or non-standard components.
42

---

Please refer to our LLM policy http:////nriiigcccc/////arrere/e for what should or should be described.
43


Reviews:
[{"review_id": "S5iL6SZZio", "reviewer": "Reviewer_kHmv", "summary": "This paper focuses on gradient boosting and builds upon the Boulevard regularization framework introduced by Zhou and Hooker (2022). It extends Boulevard in two directions: first, by introducing random dropout of trees; and second, by integrating the leave-one-out procedure and Boulevard regularization into a parallel boosting framework. The paper studies the statistical properties of both extensions. In particular, it shows that despite the randomness introduced by dropout, the algorithm still converges to a kernel ridge regression estimator that satisfies a central limit theorem (CLT). Moreover, the dropout improves signal recovery over the original Boulevard regularization. The authors also conduct theoretical analysis for the second algorithm, proving convergence to kernel ridge regression and a central limit theorem. The paper discusses confidence interval construction, and provides numerical experiments to support the theoretical claims.", "questions": "- Would it be possible to add some visual diagnostics (e.g., QQ plots) to verify the empirical normality implied by the CLT?\n- Could the authors provide a more in-depth discussion on how to tune hyperparameters such as the regularization strength $\\lambda$ and the dropout probability $p$ in practice? Practical guidance or heuristics for selecting these values would be valuable for applying the method effectively.", "limitations": "The paper is theoretical and methodological in nature and does not raise direct societal concerns.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The paper is very well written, with clear explanations of both the algorithms and the theoretical developments. \n- The paper makes both algorithmic and theoretical advances. On the algorithmic side, it introduces two meaningful extensions to Boulevard regularization, dropout boosting and parallel tree growth with leave-one-out structure, with improvement in signal recovery. On the theoretical side, the authors rigorously prove that these new algorithms retain key statistical properties, including convergence to kernel ridge regression and central limit theorems. \n- One of the key contributions is the introduction of dropout in the boosting process. While dropout is often used heuristically in ensemble methods, this paper provides a formal justification for its use and shows that it leads to improved signal recovery compared to the original Boulevard method. This insight is valuable both from a theoretical and practical standpoint.\n\nWeaknesses:\n- While the role of dropout is mentioned, not much discussion is on how to choose the dropout probability $p$ in practice.", "was_revised": true, "final_justification": "I would like to retain my score, as I find the contributions of this work to be solid in both algorithmic design and theoretical analysis.", "rebuttal": "Thank you for your kind review! We are heartened to see your kind comments on our paper being “very well written” (which is high praise!), that we offer both practical and theoretical advancements, and of you highlighting the utility of a formal justification for the use of dropout within boosting. We provide answers to your questions below (the second is addressed before the first, given that the second was also raised as a weakness).\n\n## Weaknesses and Questions\n\n1. **Practical guidance for choosing hyperparameters.** \n- **Learning rate $\\lambda$.** We found that a learning rate close to $\\lambda=1$ seemed to work well empirically. At no point did we choose a learning rate smaller than $0.1$. As a strategy, we would try $\\lambda=1$ first, and decrease this in increments of $0.2$ based on cross-validated performance or its performance in a hold-out validation set. $\\lambda$ should not be set to more than $1$, as specified in the setup of the paper in Line 99. Doing so invalidates the theory, and leads to instability in practice.\n- **Dropout probability $p$.** Regarding the choice of dropout, we found that intermediate values of $p=0.3, 0.6, 0.9$ seemed to work well. The extremes lead to interesting behavior – $p=0$ (yielding vanilla Boulevard) did not yield stable prediction intervals, and $p=1$ yielding a random forest. In Lines 339-341, we highlight that the variance of the estimator, and therefore the CIs, grows as $\\lambda$ and $p$ decrease – but we certainly agree that more discussion is warranted, and will make this amendment in the final paper.\n- **Number of boosting rounds $K$.** We would set this to the highest possible $K$ that does not lead to a significant slowdown in the time taken for one (parallel) boosting round. This is likely to be a multiple of the number of processors one has available. \nWhy? Having a larger $K$ essentially allows us to boost a mini-random forest. Boosting random forests (a strong learner) should lead to better prediction error than boosting a tree (a weak learner), if one keeps the number of boosting rounds the same.\nAlgorithm 2 can in theory achieve an unbounded improvement in asymptotic relative efficiency compared to vanilla Boulevard. However, this improvement is in terms of the number of boosting rounds, not ensemble size! \n    - Our results in Figure 2 regarding the MSE of Algorithm 2 are somewhat unfair to Algorithm 2 – as the x-axis is in the ensemble size, not the number of boosting rounds. The number of boosting rounds that Algorithm 2 encounters can be as few as 31 on Abalone and 50 on Wine Quality, in contrast to the 500 boosting rounds all other algorithms enjoy! Given the same number of boosting rounds, we would certainly expect an improvement. \n2. **Visual diagnostics on empirical normality.** Recent response guidelines do not allow us to provide new figures. However, we have created the requested QQ plot from a simulation using Algorithm 1 and have lodged it with the AC. \n- Qualitatively it gives us a good fit to the proposed CLT – this is almost a linear fit, with a slope that is just smaller than one. There is some indication of heavy tails in the extreme quantiles that involve only six out of 100 simulations, and the worst-behaved datapoint had a theoretical quantile of around $-2.75$ and a sample quantile of $-6$. This is not entirely unexpected – trees are notoriously bad at the very edge of the support of the data. \n- In case this is inaccessible to the reviewer, we also conducted normality tests (Shapiro-Wilk and Jarque-Bera tests) based on the simulation. Results suggest that aside from outliers (that can be blamed on the poor behavior of trees near the edge of the data support), overall the predictions are pretty normal:\n\n| Test           | Trimming   | Outliers Removed | Statistic | p‑value    |\n| -------------- | ---------- | ---------------- | --------: | ---------: |\n| Shapiro–Wilk   | None       | —                |   0.9472  |   0.0005   |\n| Shapiro–Wilk   | $2 \\sigma$       | 8                |   0.9876  |   0.5431   |\n| Jarque–Bera    | None       | —                |  20.9855  | 2.7736e‑05 |\n| Jarque–Bera    | $2 \\sigma$       | 8                |   1.0995  |   0.57709  |\n\nOverall, the results are encouraging for verifying empirical normality, and we thank the reviewer for this suggestion. We will include this QQ plot in the revised manuscript. \n\n\nWe hope that if our response and additional figures that we have generated in response to your review and that of Reviewers cjXq and AVWH have improved the paper in your eyes, that you might consider increasing your confidence in your assessment of the paper. Thank you for your kind review again!"}, {"review_id": "pjgcKAQR2p", "reviewer": "Reviewer_cjXq", "summary": "Gradient boosting is one of the most widely used machine learning (ML)  methods, but the theoretical properties are less well understood than for other ML methods. The paper wants to fill this gap and provides theoretical results for boosting, namely a central limit theorem for boosting predictions. Two algoritms (Boulevard Regularized Additive regression Trees - Droput (BRAT-D) and BRAT parallel (BRAT-P) are proposed and their theoretical results are dervied. Finally, numerical experiments are presented which underscore the theoretical results.", "questions": "- Is it possible to give (feasible) stopping criteria for the boosting algorithms and analyze the behaviour under stopping criteria.\n- How do different stopping criteria affect the results from the numerical experiments?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**  \nOverall, the paper is an important contribution for understanding boosting algorithms better. The developed theory is very involved and impressive. The paper is structured clearly.\n\n**Weaknesses**\n- The literature review seems incomplete. The claim that \"Still, this is only method available for frequentist inference for gradient boosting,...\" is not correct. E.g. Luo et al. (2016) analyse gradient boosting with univariate regressions as base learners and derive theoretical properties. A comparison with this method would be interesting and  including other related papers in the literature review.\n\nYe Luo, Martin Spindler, Jannis Kueck (2016): High-Dimensional L_2Boosting: Rate of Convergence. arxiv 1602.08927, Journal of Machine Learning Research forthcoming.\n\n- A crucial point of boosting is early stopping and when to determine when to stop. This is also key for empirical applications, in particular having a feasible stopping criterion. It seems that the stopping time is given in the algorithms, but how would the optimal (feasible) stopping be determined and how does the stopping criterion affect the theoretical results? How does stopping / stopping criteria affect the empirical results?  \n-  The theoretical settings seems to be very much inspired by Random Forests, in particular \"parallel structure\", but are not directly related to the concrete implementation of gradient, in particular sequential proceeding.", "was_revised": true, "final_justification": "I keep my score. It is a theoretical interesting contribution building on previous work. My onl caveat, as outlined above is, that the algorithms are modified so that they don't have much in common with the original boosting algorithm (which of course is common practice to get theoretical results at all.)", "rebuttal": "We thank the reviewer for their kind comments on the strengths of the paper! We are very pleased to hear that you think that this is an important contribution towards understanding boosting algorithms. We are also glad that you think that the paper is structured clearly – we put a lot of thought on how this can be presented in 8 pages. We also thank you for your kind comments on how you think that our theory is involved and impressive. \n\nBelow are responses and answers to the weaknesses and questions you raised. These include more numerical results that pertain to whether or not early stopping affects our algorithms. We hope that these assuage your concerns. \n\n## Weaknesses and Questions\n\n1. **Are there other methods available for frequentist inference for gradient boosting?** This is a good question. We hope that there are! Alternatives to Boulevard regularization are very much needed. We thank the reviewer for their comment – we had read Luo et al. (2016), but it did not come to mind that statistical inference could be possible with their approach. There are two things that you might mean, and we address them below. \n- **Do you mean that one can extract valid intervals out of their post-L2 boosting estimator, given that it is a valid post-selection inference algorithm?** This is likely! Though we aren’t sure that this would provide inference for boosting in the sense that we had in mind. Their method performs boosting on component-wise linear models, and not trees. \n    - Furthermore, their post-L2 boosting method refits a linear model on the predictors selected by their boosting procedure. This does not provide statistical inference for the model that was fitted by boosting.  \n    - This observation does raise a question. Viewing trees as OLS on adaptively selected rectangular indicator variables, can we fit a kernel regression on the kernel given by gradient boosting and perform inference on that model? Yes. This would constitute a similar algorithm to Friedberg et al. (2018), except applied to boosting and not random forests. We are working on it right now for another related paper. Please don’t scoop us! \n- **Do you mean that one may be able to obtain valid intervals in general given rates of convergence?** \nLuo et al. (2016) show rates of convergence, but neither provide a CLT, nor do they use the convergence rates established to provide methods for statistical inference.\n    - A CLT alone is not sufficient for statistical inference – one needs also an estimate of the asymptotic variance. It is unclear how this can be done in the framework of Luo et al. (2016). An analysis of the convergence rates is also not sufficient for statistical inference – constants are untracked, and the limiting distribution, or even whether asymptotic normality holds, is unknown. \n    - Their paper makes no mention of confidence etc. intervals, and it is unclear to us how their results can be used for that. We think that this may be possible if one can either estimate the complexity of the early-stopped function class on the fly, or if one can track down the exact constants within their analysis -– but this extends far beyond the scope of their paper. \n    - Having said that, we do agree that we should have included this within the literature review – we did read the paper, and found it to yield spiritually similar conclusions to Zhang and Yu (2005), which should also have been included.  We thank the reviewer for pointing this out, apologize for the omission, and will fix this in the final version of the paper. \n2. **Stopping times.** On questions about stopping criteria: one of the features of the Boulevard framework is that we do not need an explicit stopping criterion to avoid overfitting.  Because it works on a running average rather than a sum of trees, it is akin to random forests where building a larger ensemble never hurts you, but leads to diminishing returns. \n- In that sense, we do not need explicit stopping rules in our theory – in fact the case we analyse is based on the limit of infinite boosting rounds – and in practice would use similar tools as in random forests; monitoring test set performance and stopping at the point that we no longer see improvements.   \n- Having said that, the reviewer alludes to an important point: gradient boosting with early stopping is a promising direction for statistical inference. Certainly, if rates of convergence are available (such as with the work of Luo et al. (2016) and Zhang and Yu (2005)), perhaps something can be pulled out from them. Asymptotic normality may not hold, but non-normal limits and nonasymptotic results are still possible even then. We are interested in addressing this in future work.\n- **How does early stopping affect the empirical results?** Last minute guidance restricts us from providing figures in this response, but we created a new figure that plots the test set performance against the number of boosting rounds which verifies this. We have lodged it with the AC. Under a moderate noise-to-signal ratio DGP with the ground truth being a sinusoid: $y = \\sin(4\\pi x) + \\epsilon, \\epsilon \\sim \\mathcal{N}(0,4)$, we fit Algorithm 1 with $p=0.5$ and Algorithm 2 with $K=2$, boost to 500 rounds, and keep all other hyperparameters the same. \n    - The test MSE decreases rapidly for all models.  For gradient boosting, and stochastic gradient boosting, it starts to increase dramatically after 10 to 20 rounds. XGBoost and LightGBM achieve the minimum at around the same mark, but the test MSE increases to a lesser degree (the former more than the latter) after this point. We attach a table below, depicting the results from highest final MSE to lowest final MSE at the end of 500 boosting rounds.\n    - Algorithm 1, Algorithm 2, and vanilla Boulevard achieve approximately the same minimum, but the test set MSE remains flat thereafter – unlike the previously described boosting algorithms, it does not increase in the number of boosting rounds past this point. Early stopping is not necessary for our algorithms, both in theory and in practice!\n\n| Algorithm   | Step the minimum was achieved   | Approximate minimum MSE | Final MSE    | Early stopping needed? |\n| ---------------------------- | ----------------------- | -------------------------------- | -------------- | ---------------------------: |\n| GBT                                 |             ~10               |                      ~40.5                |        ~60       |                    Yes               |\n| SGBT (subsample=0.6)   |             ~12               |                      ~40.5                |        ~60       |                    Yes               |                \n| XGBoost                          |             ~15               |                      ~41                   |       ~50        |                    Yes               |\n| LightGBM                        |             ~18               |                      ~41                   |       ~44        |                    Yes               |\n| Algorithm 2                      |      Flat at 50-500      |                      ~42                   |       ~42        |                    No                |\n| Boulevard                        |      Flat at 50-500      |                      ~41                   |       ~41        |                    No                |\n| Algorithm 1                      |      Flat at 50-500      |                      ~41                   |       ~41        |                    No                |\n| Random Forest                |      Flat at 50-500      |                      ~40.7               |       ~40.7      |                    No                |\n\n3. **Random forests.** A final weakness was suggested to be the similarity structure between random forest and our parallelization structure. \n- The referee could be referring to the contrast between the parallel structure of parallelized boosting (which starts to look more like a random forest) and the sequential processing in gradient boosting. This applies only to Algorithm 2 – as Algorithm 1 is a bona-fide sequentially processed gradient boosting algorithm for the L2 loss.\n- In either case, this does not mean that Algorithms 1 and 2 are a reduction of boosting to random forests. While trees are averaged instead of summed, these trees are still grown in sequential order, one after the other. This leads to a convergence to a kernel ridge regression $\\widehat{\\mathbf{y}}_n^{(b)} \\xrightarrow[b \\rightarrow \\infty]{a . s .}\\left(\\lambda^{-1}\\mathbf{I}+(1-p) \\mathbb{E}\\left[\\mathbf{S}_n\\right]\\right)^{-1}  \\mathbb{E}\\left[\\mathbf{S}_n\\right] \\mathbf{y}_n$, rather than convergence to a random forest $\\mathbb{E}\\left[\\mathbf{S}_n\\right]  \\mathbf{y}_n$. The analysis in terms of kernel ridge regression is in fact quite different, and these lead to different estimators in practice as well.\n\n-------------------------------\n\nAgain, we thank the referee for your kind comments and insightful questions. We hope that the response above is helpful and has addressed your concerns. **If you think our response has adequately addressed your concerns, we will be glad if you choose to increase your score!**\n\n## References\n1. Tong Zhang and Bin Yu (2005), Boosting with early stopping: Convergence and consistency.\n2. Friedberg et al. (2018), Local linear forests\n3. Luo et al. (2016), High-dimensional L2 boosting: Rate of convergence"}, {"review_id": "SZTbX1TRBR", "reviewer": "Reviewer_oGZf", "summary": "The paper proposes a variation of gradient boosting decision trees where dropout and parallel boosting are incorporated. It then proposes theoretical analysis of the algorithm showing central limit theorems (CLTs). This can be used for statistical inference: prediction, confidence, and reproduction intervals. Some numerical experiment results are presented.", "questions": "XGBoost and other tree ensembles have been widely used for many practical problems without CLT and statistical inference. Why does one need these in practice? I think the paper needs to motivate more the importance of statistical inference.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 3, "strengths_and_weaknesses": "The paper proves for the first time a central limit theorem (CLT) for gradient boosting regression trees. However, I find the paper quite difficult to follow because of its dense mathematical presentation. While the theoretical derivations and equations seem rigorous and technically sound, their practical implications are not clearly conveyed. The central limit theorem (CLT) results rely on multiple assumptions, many of which seem to difficult to verify/ensure in practice. Moreover, the empirical evaluation does not convincingly demonstrate a significant performance improvement over strong baselines such as XGBoost. As a result, the contribution of the proposed method remains unclear in practice. Also, these CLT results are shown for a modified version of gradient boosting. Why this has not been shown for a traditional version of Friedman's gradient boosting is not clear.", "was_revised": true, "final_justification": "The paper is more theoretically oriented, and the practical significance of the results still remains unclear to me. It seems to have merit in this more theoretically oriented statistics community. I did not check the theory, and so I decrease my confidence score and raise my rating.", "rebuttal": "We appreciate the referee's attention to the paper and their confirmation that our mathematical development is sound.\n\nHowever, we do strongly feel that the reviewer's score is unreasonable, as is their framing of comparisons solely in terms of predictive performance. We think that inference should be regarded as an additional component -- you don't need it to predict well on aggregate, but it can be important for some applications.\n\n**On the importance of statistical inference.** \n\nTo the question of \"Why does one need statistical inference?\" which we will interpret as meaning for these models specifically.  Here we could provide a very considerable range of situations where uncertainty quantification would be relevant. By this we mean \"if you collected a new data set and ran the model again, how different would your prediction be\"?\n\n- You might feel quite different about having knee reconstruction surgery if you were told that it had an 80% success rate empirically, than if you were told that the confidence interval for what this success rate might actually be ran from 40% to 95%.\n- To be more concrete, if you had run XGBoost on geologic samples to give you a predicted yield for proposed rare earth mines, you might prioritise a mine with a smaller but more certain predicted yield than one with a larger prediction but an enormous confidence intervals. \n- Conversely, a marketing campaign may want to avoid sending materials to someone who is very unlikely to respond in order not to antagonise them, but might want to send materials out to someone of whom we have very high uncertainty.\n\nThese are all immediately practical situations in which uncertainty about a predicted value is already relevant. This is without considering use in downstream tasks:\n- Prioritizing data to collect to reduce uncertainty over all.\n- Propagating uncertainty through to forecasts about the consequences of taking actions in a sequential decision-making poblem.\n- Propagating uncertainty into explanation or interpretation methods which might also be relevant for.\n- Model reduction, or testing whether expensive features are worth collecting given how they affect performance.\n\nWe note that in all these cases, inference is in addition to prediction. **Our methods perform comparably with SoTA boosting, but *also* provide uncertainty quantification** – we are not sacrificing one for the other. \n\nThe NeurIPS format does not allow space for an in-depth discussion of the uses of inferential quantities. We felt both that these would be broadly understood and that it was important to focus on the technical components of our results; but we will include some additional motivation in the introduction.\n\n**On the algorithmic changes to boosting and assumptions.**\n\nFor the remainder of your comments; our results do require specific algorithmic changes to boosting. It is not clear how this can be done otherwise – for instance, boosting to a set number of rounds can lead to rampant overfitting and absolutely no hope for convergence or a CLT, while early stopping has its own issues, as we highlight in our response to Reviewer cjXq. \n\nHowever, the assumptions about the data are not stronger than theoretical guarantees for most machine learning algorithms:  we need the distributions of our features and response to behave reasonably, and we need the data we collect to be both independent and representative of the task. These assumptions are relevant for any ML modeling task. Regarding the assumptions about the trees and the learning algorithm itself, we address this in detail within Lines 131-137, 255-258, and 261-263. None of these assumptions are new – they are all inherited from prior work (Zhou and Hooker (2022), Athey et al. (2018)) on trees. As we allude to in Line 137, numerical experiments indicate that our boosting algorithms and inferential procedures work even when these assumptions are not explicitly verified. \n\nWe note that purely on an algorithmic level, our extension of Boulevard also provides an interpolation between boosting and bagging methods such as random forests, and while this was not our focus, it does allow us extra degrees of freedom to optimize between them.\n_________________\n\nAt the end of the day, we do not think this review is fair. We strongly feel that both the reviewer's score, and the lion’s share of their objections, are unreasonable, and that this review does not provide a meaningful assessment of our work. \n\n**Given that you do acknowledge that our results appear to be correct, we hope that you will consider significantly revising your score; inadequacies in expressing motivation does not render a paper irredeemable.**"}, {"review_id": "5pXrBV0C5G", "reviewer": "Reviewer_AVWH", "summary": "The paper builds upon Boulevard regularization and proposes two modified algorithm (dropout, parallel). They show the asymptotic normality of the proposed estimators including statistical inference.", "questions": "- The asymptotic variance is estimated. Can you please comment on the convergence to the true asymptotic variance?\n- The proposed confidence intervals are quite large limiting the practical use. Could you please comment on potential optimality?\n- It is hard to compare the MSE-performance of the different methods in Figure 2. Please make the figures larger (in particular Fig. 2 and 4).", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n- the paper is well motivated and tackles a relevant problem\n- the paper proposes a unified framework: algorithm, proof of asymptotic normality and statistical inference\n- the results and the corresponding assumptions are clearly discussed\n\nWeaknesses\n- In my opinion, once the asymptotic normality is achieved, the contributions regarding statistical inference are straightforward. It is not clear to me why the proposed two algorithms should be preferred over vanilla Boulevard regularization which is also asymptotically normal and allows for statistical inference. A clear description about the advantages and disadvantages (e.g. MSE, asymptotic efficiency, resources...) of vanilla Boulevard regularization, BRAT-D and BRAT-P including a discussion when to use what would be beneficial. Furthermore, to empirically compare the confidence intervals etc. with those based on vanilla Boulevard regularization, would strengthen the contribution, particularly Corollary 4.", "was_revised": true, "final_justification": "The authors addressed my concerns. I have raised my score accordingly.", "rebuttal": "We thank the reviewer for recognizing the strengths of the paper, and for offering very helpful suggestions. We respond below to your concerns. In particular, we offer a description on the advantages of each algorithm, and provide additional results comparing the confidence intervals with vanilla Boulevard. **If our response sufficiently addresses your concerns, we would greatly appreciate it if you’d consider increasing your score.** \n\n## Weaknesses\n1. **Methodological contribution past the CLT.** We agree with the reviewer that constructing the baseline procedures for statistical inference are straightforward once the CLT is established. The intervals do indeed fall out of the CLT. The hypothesis test requires a little more insight, but also does so. \n- **Problem with the straightforward approach.** Unfortunately, the straightforward procedures are not computationally tractable on large datasets commonly encountered when using gradient boosting! Although the CLT reduces the problem of inference to kernel ridge regression (with the right kernel), computing the intervals is an $O(n^3)$ problem. **This is the chief difficulty that Zhou and Hooker (2022) face when constructing replication intervals for vanilla Boulevard.** \n    - They mention in Section 6.2 that: “Although the matrix inverse involved in the expression is too time consuming to compute for large $n$, it is possible to estimate it using Monte Carlo when $n$ and $d$ are small.”\n- **We do not have this problem.** An important methodological contribution that we should have highlighted more is in making the intervals and tests practical and tractable via matrix sketching. We employ the Nystrom method and subsample $s$ landmarks to form a low-rank approximation of the kernel. This yields a solution that requires only $O(ns^2)$ time to precompute the kernel, and only $O(s^2)$ time for inference -- yielding practical statistical inference in near-linear time in the number of datapoints $n$.\n    - With the Nystrom method of Musco and Musco (2017), we can choose $s$ to near-linear in the effective dimension $d_{\\text{eff}}^\\mu$ of a ridge regression problem with regularization parameter $\\mu$ on the kernel matrix: $s = \\widetilde{O}(d_{\\text{eff}}^\\mu)$. \n2. **Comparison to vanilla Boulevard.** Certainly! We provide the requested comparison below, and will include it in the final version.\n- **Should I use Boulevard or Algorithm 1?** Boulevard regularization is a special case of Algorithm 1 when no dropout is used $p=0$. Should we use dropout? There are good reasons to believe so. \n    - **Improvements in prediction error.** In theory, as we discuss in Lines 59 and Corollary 4, Algorithm 1 achieves up to a fourfold improvement in terms of the asymptotic relative efficiency compared to vanilla Boulevard, when all other hyperparameters but the dropout rate are held equal.\n        - In practice, this is similar to asking if one should use dropout with a neural network. There, it is almost always used, but when it is not, there are alternatives, such as weight decay, that also allow for regularization. With this analogy in mind, choosing $p$ can be a go-to knob for tuning the amount of regularization – though alternatives like tree depth and learning rate exist. \n    - **Improvements in statistical inference.** From a coverage/statistical inference perspective, as we discuss in Line 339, there are drawbacks to using vanilla Boulevard instead of Algorithm 1. Setting $p \\to 0$ empirically leads to wider intervals and less power in the hypothesis test for variable importance. \n        - Why does this happen? We scale Algorithm 1 by $\\frac{1+\\lambda (1-p)}{\\lambda}$ to correct the bias. As a result, the irreducible error will be scaled up as well -- but less so when $p$ is large. A higher dropout rate also introduces decorrelation between trees, suggesting a stabler variance estimate.\n- **Should I use Boulevard or Algorithm 2?** Asking why one should use Algorithm 2 over Boulevard amounts to asking whether one wants to fit trees in parallel or not, and there are computational reasons (e.g. parallelism) to do so.\n    - **Improvements in prediction error.** In theory, Algorithm 2 can achieve an unbounded improvement in relative efficiency over vanilla Boulevard as we take $\\lambda \\to 0$, as we discuss in Lines 295-296. \n        - But this improvement is in terms of the number of boosting rounds, not ensemble size! This clarifies the intuition – boosting random forests (a strong learner) should lead to better prediction error than boosting a tree (a weak learner), with the same number of boosting rounds.\n        - Our results in Figure 2 are somewhat unfair to Algorithm 2, as the x-axis is in the ensemble size and not the number of boosting rounds. The number of boosting rounds that Algorithm 2 encounters can be as few as 31 on Abalone and 50 on Wine Quality, in contrast to the 500 boosting rounds all other algorithms enjoy. Given the same number of boosting rounds, we would certainly expect an improvement. \n   - **Parallel computation.** With modern multi-core processors and distributed computing, there is immense potential for exploiting the possibility of increased parallelism in boosting. \n3. **Comparison of confidence intervals.** We provide the requested comparison below.\n    - For a quantitative comparison, we provide a new figure that plots the width and coverage of our intervals against the dropout probability. We have lodged this with the AC. Unlike in Figure 3, we do not perform the conformal adjustment outlined in Lines 320 to 327, and we plot the coverage and width across all datapoints and repetitions for simplicity. Although not performing this leads to overcoverage in the PIs, we have to do so to compare the widths – otherwise any over-or-under-coverage would simply be adjusted to the nominal 0.95 level. \n       - The mean CI and PI widths decrease as $p$ increases. The PI coverage remains close to 1 throughout (unlike in Figure 3, overcoverage occurs as we do not perform the conformal adjustment here), while the CI coverage decreases as $p$ increases -- as we see in the table below.\n    - For a qualitative comparison, we also provide a version of Figure 1 that we have lodged with the AC. This uses the same hyperparameters, except for setting $p=0$. Empirically, it seems that the width of the intervals does indeed decrease in $p$, though this can come at a cost with respect to CI coverage (though achieving good CI coverage is difficult in nonparametric regression in general).\n\n|  Dropout rate   | CI width | CI coverage | PI width | PI coverage |\n|-|-|-|-|-|\n| 0.0 (vanilla Boulevard) | 57.98   | 0.66 | 80.74 | 0.9997|\n| 0.1 | 45.62   | 0.61| 70.02| 0.9998|\n| 0.2 | 23.22   | 0.46 | 54.08| 0.9995|\n| 0.3 | 16.66   | 0.42 | 49.43| 0.9997|\n| 0.4 | 23.36   | 0.47 | 54.35| 0.9998|\n| 0.5 | 15.73   | 0.44 | 48.76| 0.9950|\n| 0.6 | 13.77   | 0.43| 47.64| 0.9950|\n| 0.7 | 10.21   | 0.42| 44.90| 0.9957|\n| 0.8 | 5.57    | 0.41| 41.83| 0.9950 |\n| 0.9 | 6.88    | 0.47| 42.33| 0.9950 |\n\n- We also examine test size and power as a function of dropout. Performance is strong for $p \\in [0.2, 0.5]$, peaking at $p=0.5$. However, for $p \\leq 0.1$, Type II error rises significantly (vanilla Boulevard has Type II error $0.43$), and for $p \\geq 0.6$, Type I error becomes uncontrollable. We provide a detailed figure lodged with the AC.\n\n| Dropout Rate | Average Type I Error       | Average Type I Error        |\n|------------|-------------------|-------------------|\n|0.0         |0.0                  |0.43 |\n|0.1         |0.0                   |0.33 |\n|0.2         |0.033 |0.1 |\n|0.3         |0.067 |0.1 |\n|0.4         |0.033|0.033|\n|0.5         |0.033|0.0                 |\n|0.6         |0.7             |0.0                 |\n|0.7         |0.67|0.0                 |\n|0.8         |0.77|0.0                 |\n|0.9         |0.63|0.0                 |\n|1.0         |0.7            |0.0                 |\n\n## Questions\n1. **The asymptotic variance is estimated.** It is unclear whether the reviewer is referring to $\\mathbf{r}_n$ or $\\widehat{\\sigma}^2$. We address both. The convergence in $\\mathbf{r}_n$ in Theorem 2 is in the theorem statement, in the sense that this is the exact quantity used in the CLT. This is a happy result – showing that the estimation is baked into the result, and the empirical quantity is the quantity of interest. Regarding $\\widehat{\\sigma}^2$, we estimate this as the sample average of the residuals on a hold-out dataset, for which the convergence and consistency is clear. \n2. **The CIs are large.** This is a known issue with nonparametric regression. \n- **In theory.** Sadly, large intervals are expected due to the curse of dimensionality, as minimax optimal rates are exponentially dependent on dimension. Although Corollaries 1 and 2 show that our algorithm is suboptimal by a quadratic factor for Lipschitz functions, this is small compared to the exponential dependence in $d$ that no algorithm can escape without making further assumptions, e.g. on additive structure.\n- **In practice.** Empirically, Figure 3 demonstrates our prediction intervals achieve comparable median widths to conformal baselines, while providing stronger conditional (rather than merely marginal) coverage guarantees. This should be viewed positively. \n3. **Size of Figure 3.** We agree, thank you for pointing this out. We will enlarge it for the camera-ready version.\n- Regarding MSE performance, there is no consistent winner. Our methods remain competitive: rounding to three decimals, GBT and LightGBM each win four times; SGBT wins three; Algorithm 1, random forests, and XGBoost each win twice; Algorithm 2 and Boulevard each win once.\n___\n\nWe hope that this response has assuaged your concerns to your satisfaction. \n**Again, if it has, we would greatly appreciate it if you’d consider increasing your score!** \n\n## References\nMusco and Musco (2016), Recursive Sampling for the Nystrom Method"}]

Author rebuttal:

Meta-review: Building on work by Zhou & Hooker (2002), this paper proposes a gradient boosting algorithm with a CLT guarantee: in the limit of boosting rounds, the ensemble output converges to a kernel ridge regression. The CLT guarantee means that one can use the ensemble for statistical inference, like computing confidence intervals around the predictions or ground truth. The paper accomplishes improvements over Zhou & Hooker by incorporating dropout, in addition to Zhou & Hooker's _Boulevard regularization_. Two boosting algorithms are proposed: one sequential, and one parallel -- the latter of which also incorporates a leave-one-out procedure. Experiments on synthetic and real data round out the study.

The reviews all say this is a technically solid, well written paper. The weaknesses are mostly about the writing, with some reviewers asking for more elaboration on tuning the dropout parameter, the importance of the CLT, and comparison/advantages over prior work (notably, Zhou & Hooker). The authors' rebuttal seems to have addressed most of these concerns, so their points could be incorporated into the camera-ready.

As all scores are on the positive side, I will agree with the reviews and recommend acceptance. Since there is no overwhelmingly positive review (i.e., strong accept), and the impact of this work is a bit unclear, I recommend poster presentation.
Decision: Accept (poster)