What Functions Does XGBoost Learn?

• URL: http://arxiv.org/abs/2601.05444v1
• Date: Fri, 09 Jan 2026 00:22:08 GMT
• Title: What Functions Does XGBoost Learn?
• Abstract summary: We introduce an infinite-dimensional function class $mathcalFd, s_inftytextST$ that extends finite ensembles of bounded-depth regression trees.<n>We show that every of the XGBoost objective is also an equivalent penalized regression problem over $mathcalFd, s_infty-textST$ with penalty $Vd, s_infty-textXGB(cdot)$.<n>Our results provide the first rigorous characterization of the function space
• Score: 0.8657572235098258
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper establishes a rigorous theoretical foundation for the function class implicitly learned by XGBoost, bridging the gap between its empirical success and our theoretical understanding. We introduce an infinite-dimensional function class $\mathcal{F}^{d, s}_{\infty-\text{ST}}$ that extends finite ensembles of bounded-depth regression trees, together with a complexity measure $V^{d, s}_{\infty-\text{XGB}}(\cdot)$ that generalizes the $L^1$ regularization penalty used in XGBoost. We show that every optimizer of the XGBoost objective is also an optimizer of an equivalent penalized regression problem over $\mathcal{F}^{d, s}_{\infty-\text{ST}}$ with penalty $V^{d, s}_{\infty-\text{XGB}}(\cdot)$, providing an interpretation of XGBoost as implicitly targeting a broader function class. We also develop a smoothness-based interpretation of $\mathcal{F}^{d, s}_{\infty-\text{ST}}$ and $V^{d, s}_{\infty-\text{XGB}}(\cdot)$ in terms of Hardy--Krause variation. We prove that the least squares estimator over $\{f \in \mathcal{F}^{d, s}_{\infty-\text{ST}}: V^{d, s}_{\infty-\text{XGB}}(f) \le V\}$ achieves a nearly minimax-optimal rate of convergence $n^{-2/3} (\log n)^{4(\min(s, d) - 1)/3}$, thereby avoiding the curse of dimensionality. Our results provide the first rigorous characterization of the function space underlying XGBoost, clarify its connection to classical notions of variation, and identify an important open problem: whether the XGBoost algorithm itself achieves minimax optimality over this class.

Related papers

• Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH [11.157319736363823]
  A more structured variant, Factorized AdaBoost.MH, uses base classifiers of the form $mathbfh(x)=mathbfv bmvarphi(x)$.<n>We show that Factorized AdaBoost.MH achieves the same boosting-type convergence rate as AdaBoost.MH up to a universal constant factor.
  arXiv  Detail & Related papers  (2026-08-02T08:46:38Z)
• Instance-dependent Stochastic Lipschitz bandit [28.946496440127603]
  We study the Lipschitz bandit problem, where a learner sequentially maximizes an unknown Lipschitz function $f$ over a domain.<n>Existing regret bounds are either worst-case, scaling as $tilde left ( Td+1/d+2right )$, or adaptive via the zooming dimension $d_z$.<n>We provide an analysis and an algorithm that characterizes the regret through integrals of the suboptimality gap of $f$ over its level sets.
  arXiv  Detail & Related papers  (2026-05-28T10:46:30Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  We study first-order methods for convex optimization problems with functions $f$ satisfying the recently proposed $ell$-smoothness condition $||nabla2f(x)|| le ellleft(||nabla f(x)||right),$ which generalizes the $L$-smoothness and $(L_0,L_1)$-smoothness.
  arXiv  Detail & Related papers  (2025-08-09T08:28:06Z)
• Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems [10.228439000828722]
  We study the sample complexity of differentially private optimization of quasi-concave functions.<n>We show that the lower bound can be bypassed for a series of natural'' problems.
  arXiv  Detail & Related papers  (2025-04-26T19:04:00Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  We provide a unified analysis of two-timescale gradient ascent (TTGDA) for solving structured non minimax optimization problems.<n>Our contribution is to design TTGDA algorithms are effective beyond the setting.
  arXiv  Detail & Related papers  (2024-08-21T20:14:54Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  Decentralized online convex optimization (D-OCO) is designed to minimize a sequence of global loss functions using only local computations and communications.<n>We develop a novel D-OCO algorithm that can reduce the regret bounds for convex and strongly convex functions to $tildeO(nrho-1/4sqrtT)$ and $tildeO(nrho-1/2log T)$.<n>Our analysis reveals that the projection-free variant can achieve $O(nT3/4)$ and $O(n
  arXiv  Detail & Related papers  (2024-02-14T13:44:16Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  We introduce a new tool for BFG convex optimization (SCO): a Reweighted Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. We develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings.
  arXiv  Detail & Related papers  (2023-01-01T18:51:29Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  Modern machine learning algorithms aim to extract fine-grained information from data to provide accurate predictions, which often conflicts with the goal of privacy protection. This paper addresses the practical and theoretical importance of developing privacy-preserving machine learning algorithms that ensure good performance while preserving privacy.
  arXiv  Detail & Related papers  (2022-09-09T08:54:13Z)
• Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical [1.2183405753834562]
  Given a finite set system $(X,mathcal S)$, the emphdiscrepancy of a two-coloring $chi:Xto-1,1$ is defined as $max_S in mathcal S|chi(S)|$. We propose a randomized algorithm which, for any $d>0$ and $(X,mathcal S)$ with dual shatter function $pi*(k)=O(kd)$, returns a coloring with expected discrepancy
  arXiv  Detail & Related papers  (2022-09-02T15:59:09Z)
• Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods [39.87865197769047]
  We study separable minimax optimization problems $min_x max_y f(x) - g(y) + h(x, y)$, where $f$ and $g$ have smoothness and strong convexity parameters $(Lx, mux)$, $(Ly, muy)$, and $h$ is convex-concave with a $(Lambdaxx, Lambdaxy, Lambdayymuyright)$.
  arXiv  Detail & Related papers  (2022-02-09T18:57:47Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  We describe an implicit sparsity-inducing mechanism based on over a family of kernels. As an application, we use this sparsity-inducing mechanism to build algorithms consistent for feature selection.
  arXiv  Detail & Related papers  (2021-10-12T09:36:41Z)
• DIPPA: An improved Method for Bilinear Saddle Point Problems [18.65143269806133]
  This paper deals with point dependency problems $min_bfx max_bfy g(fracx) + bfxtop bfbftop fracbfA kappa_x kappa_x (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y)
  arXiv  Detail & Related papers  (2021-03-15T10:55:30Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.