論文の概要: What Functions Does XGBoost Learn?

• arxiv url: http://arxiv.org/abs/2601.05444v1
• Date: Fri, 09 Jan 2026 00:22:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-12 17:41:49.797287
• Title: What Functions Does XGBoost Learn?
• Title（参考訳）: XGBoostはどんな機能を学ぶか?
• Authors: Dohyeong Ki, Adityanand Guntuboyina,
• Abstract要約: 無限次元関数クラス $mathcalFd, s_inftytextST$ を導入する。 XGBoost の目的の全ては、$mathcalFd, s_infty-textST$ のペナルティ$Vd, s_infty-textXGB(cdot)$ よりも同等のペナル化回帰問題であることを示す。 我々の結果は関数空間の最初の厳密な特徴を与える。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 本稿では,XGBoostが暗黙的に学習した関数クラスの厳密な理論的基礎を確立し,その経験的成功と理論的理解のギャップを埋める。 無限次元関数クラス $\mathcal{F}^{d, s}_{\infty-\text{ST}}$ は、XGBoostで使われる$L^1$正規化ペナルティを一般化する複雑性測度 $V^{d, s}_{\infty-\text{XGB}}(\cdot)$ とともに有界回帰木の有限アンサンブルを拡張する。 XGBoost の目的の最適化子はいずれも $\mathcal{F}^{d, s}_{\infty-\text{ST}}$ のペナルティである $V^{d, s}_{\infty-\text{XGB}}(\cdot)$ に対する等価なペナル化回帰問題のオプティマイザであり、より広い関数クラスを暗黙的に対象とする XGBoost の解釈を提供する。 また、Hardy--Krause 変分で $\mathcal{F}^{d, s}_{\infty-\text{ST}}$ と $V^{d, s}_{\infty-\text{XGB}}(\cdot)$ を滑らかに解釈する。 我々は、$\{f \in \mathcal{F}^{d, s}_{\infty-\text{ST}}: V^{d, s}_{\infty-\text{XGB}}(f) \le V\}$が$n^{-2/3} (\log n)^{4(\min(s, d) - 1)/3} の収束の最小値-最適速度を達成することを証明している。 この結果は、XGBoostの基底となる関数空間を初めて厳密に評価し、古典的な変分の概念との関係を明確にし、XGBoostアルゴリズム自体がこのクラスに対して極小最適性を達成するかどうかという重要な開問題を特定するものである。

関連論文リスト

• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems [10.228439000828722]
  準凹関数の微分プライベート最適化のサンプル複雑性について検討する。 我々は、下界が一連の自然問題に対してバイパス可能であることを示す。
  論文  参考訳（メタデータ） (2025-04-26T19:04:00Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical [1.2183405753834562]
  有限集合系 $(X,mathcal S)$ が与えられたとき、2色の $chi:Xto-1,1$ は数学的な S|chi(S)|$ において $max_S として定義される。 我々は、任意の$d>0$と$(X,mathcal S)$に対して、二重シャッター関数 $pi*(k)=O(kd)$ のランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-09-02T15:59:09Z)
• Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods [39.87865197769047]
  分離可能なミニマックス最適化問題 $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)$。
  論文  参考訳（メタデータ） (2022-02-09T18:57:47Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  カーネル群に基づく暗黙の空間性誘導機構について述べる。 アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
  論文  参考訳（メタデータ） (2021-10-12T09:36:41Z)
• DIPPA: An improved Method for Bilinear Saddle Point Problems [18.65143269806133]
  本稿では,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) kappa_y (kappa_x + kappa_y)について述べる。
  論文  参考訳（メタデータ） (2021-03-15T10:55:30Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。