論文の概要: On the Convergence of CART under Sufficient Impurity Decrease Condition

• arxiv url: http://arxiv.org/abs/2310.17114v1
• Date: Thu, 26 Oct 2023 03:01:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-27 22:34:47.126930
• Title: On the Convergence of CART under Sufficient Impurity Decrease Condition
• Title（参考訳）: 不純物減少条件下におけるCARTの収束性について
• Authors: Rahul Mazumder, Haoyue Wang
• Abstract要約: 回帰条件下でのCARTの収束率について検討する。 誤差境界が定数や対数係数以上でさらに改善できないことを示す例を示す。 本稿では、この概念の実用性を説明するために、非パラメトリック推定におけるいくつかのよく知られた関数クラスについて論じる。
• 参考スコア（独自算出の注目度）: 18.454596304803868
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The decision tree is a flexible machine learning model that finds its success in numerous applications. It is usually fitted in a recursively greedy manner using CART. In this paper, we investigate the convergence rate of CART under a regression setting. First, we establish an upper bound on the prediction error of CART under a sufficient impurity decrease (SID) condition \cite{chi2022asymptotic} -- our result improves upon the known result by \cite{chi2022asymptotic} under a similar assumption. Furthermore, we provide examples that demonstrate the error bound cannot be further improved by more than a constant or a logarithmic factor. Second, we introduce a set of easily verifiable sufficient conditions for the SID condition. Specifically, we demonstrate that the SID condition can be satisfied in the case of an additive model, provided that the component functions adhere to a ``locally reverse Poincar{\'e} inequality". We discuss several well-known function classes in non-parametric estimation to illustrate the practical utility of this concept.
• Abstract（参考訳）: 決定木はフレキシブルな機械学習モデルであり、多くのアプリケーションで成功している。 通常はCARTを用いて再帰的にグリード状に取り付けられる。 本稿では,回帰条件下でのCARTの収束率について検討する。 まず,cartの予測誤差の上限を十分不純物減少 (sid) 条件 \cite{chi2022asymptotic} 下で定め, 同様の仮定下では \cite{chi2022asymptotic} により既知の結果に改善する。 さらに,誤差境界が定数や対数係数以上によってさらに改善されないことを示す例を示す。 第2に、SID条件に対する検証が容易な条件のセットを導入する。 具体的には、成分関数が ``locally reverse Poincar{\'e} inequality' に従属すると、加法モデルの場合、SID条件が満たされることを示す。 非パラメトリック推定においてよく知られた関数クラスをいくつか議論し,この概念の実用性を説明する。

関連論文リスト

• Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem [7.443139252028032]
  非有界な状態空間と報酬関数を持つ平均逆強化学習を考える。 近年の研究では、この問題をアクター批判の枠組みで研究している。 線形関数近似を用いた時間差分学習(TD)について検討した。
  論文  参考訳（メタデータ） (2024-10-29T03:40:53Z)
• Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
  我々はNesterov加速度アンダーホ条件の一般化版に対する新しい収束率を証明した。 本分析により, 従来の研究に比べて, 強い成長定数への依存度を$$$から$sqrt$に下げることができた。
  論文  参考訳（メタデータ） (2024-04-03T00:41:19Z)
• Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications [2.0584253077707477]
  目的関数 $J(cdot)$ の定常点を求めるグラディエント・Descent (SGD) 法の収束特性について検討した。 この結果は、すべての定常点が大域最小値である性質を持つ invex' 関数のクラスに適用できる。
  論文  参考訳（メタデータ） (2023-12-05T15:22:39Z)
• Minimax Instrumental Variable Regression and $L_2$ Convergence Guarantees without Identification or Closedness [71.42652863687117]
  インストゥルメンタル変数(IV)回帰の非パラメトリック推定について検討した。 固定IV解に収束できる新しいペナル化ミニマックス推定器を提案する。 ラックス条件下での推定値に対して強い$L$誤差率を導出する。
  論文  参考訳（メタデータ） (2023-02-10T18:08:49Z)
• Large deviations rates for stochastic gradient descent with strongly convex functions [11.247580943940916]
  勾配降下を伴う一般高確率境界の研究のための公式な枠組みを提供する。 強い凸関数を持つSGDの上限となる大きな偏差が見つかる。
  論文  参考訳（メタデータ） (2022-11-02T09:15:26Z)
• Inference on Strongly Identified Functionals of Weakly Identified Functions [71.42652863687117]
  本研究では,ニュアンス関数が存在しない場合でも,関数を強く識別するための新しい条件について検討する。 本稿では,プライマリおよびデバイアスのニュアンス関数に対するペナル化ミニマックス推定器を提案する。
  論文  参考訳（メタデータ） (2022-08-17T13:38:31Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• Convergence of Gradient Algorithms for Nonconvex $C^{1+\alpha}$ Cost Functions [2.538209532048867]
  勾配が収束する副生成物を示し、収束率に明示的な上限を与える。 これにより、ドオブマルティンの超ガレ収束定理によるほぼ確実な収束を証明できる。
  論文  参考訳（メタデータ） (2020-12-01T16:48:59Z)
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation [17.199023009789308]
  予想されるSGD(SGD)の仮定は、非アーティザン関数に対して日常的に使われている。 本稿では,スムーズな非線形設定への収束のパラダイムを示す。 また,異なるステップサイズ条件の理論的保証も提供する。
  論文  参考訳（メタデータ） (2020-06-18T07:05:56Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  我々はReLU回帰の根本的な問題を考察する。 目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
  論文  参考訳（メタデータ） (2020-05-26T16:26:17Z)

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

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