論文の概要: 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条件が満たされることを示す。
非パラメトリック推定においてよく知られた関数クラスをいくつか議論し,この概念の実用性を説明する。
関連論文リスト
- An Inexact Halpern Iteration with Application to Distributionally Robust
Optimization [9.529117276663431]
決定論的および決定論的収束設定におけるスキームの不正確な変種について検討する。
不正確なスキームを適切に選択することにより、(予想される)剰余ノルムの点において$O(k-1)収束率を許容することを示す。
論文 参考訳(メタデータ) (2024-02-08T20:12:47Z) - When Does Confidence-Based Cascade Deferral Suffice? [69.28314307469381]
カスケードは、推論コストをサンプル毎に適応的に変化させる古典的な戦略である。
deferralルールは、シーケンス内の次の分類子を呼び出すか、または予測を終了するかを決定する。
カスケードの構造に執着しているにもかかわらず、信頼に基づく推論は実際は極めてうまく機能することが多い。
論文 参考訳(メタデータ) (2023-07-06T04:13:57Z) - Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity,
and Robust Algorithms [31.478874616470048]
本稿では,ReLUアクティベーション機能を持つニューラルネットワークの実証的損失に対する定常性試験の計算問題について検討する。
片方向線形関数に対するある一階近似定常性の概念の検証はコ-NPハードであることが示される。
本稿では,Clarke と Fr'echet の差分で近似近距離定常性をテストするアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-23T17:26:51Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。