論文の概要: On the Statistical Optimality of Optimal Decision Trees

• arxiv url: http://arxiv.org/abs/2603.05340v1
• Date: Thu, 05 Mar 2026 16:16:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-06 22:06:11.315983
• Title: On the Statistical Optimality of Optimal Decision Trees
• Title（参考訳）: 最適決定木の統計的最適性について
• Authors: Zineng Xu, Subhroshekhar Ghosh, Yan Shuo Tan,
• Abstract要約: ランダムな設計の下で,世界規模で最適な経験的リスク最小化木に対する包括的統計理論を構築した。 まず,葉高が少なくとも$L$である木で達成可能な最適近似に対して,ERM推定器の過大なリスクを負う鋭いオラクル不等式を確立する。 新しい関数クラスよりも極小最大速度を導出する: 断片的にスパースな異方性ベソフ空間(PSHAB)である。
• 参考スコア（独自算出の注目度）: 6.920276126310231
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While globally optimal empirical risk minimization (ERM) decision trees have become computationally feasible and empirically successful, rigorous theoretical guarantees for their statistical performance remain limited. In this work, we develop a comprehensive statistical theory for ERM trees under random design in both high-dimensional regression and classification. We first establish sharp oracle inequalities that bound the excess risk of the ERM estimator relative to the best possible approximation achievable by any tree with at most $L$ leaves, thereby characterizing the interpretability-accuracy trade-off. We derive these results using a novel uniform concentration framework based on empirically localized Rademacher complexity. Furthermore, we derive minimax optimal rates over a novel function class: the piecewise sparse heterogeneous anisotropic Besov (PSHAB) space. This space explicitly captures three key structural features encountered in practice: sparsity, anisotropic smoothness, and spatial heterogeneity. While our main results are established under sub-Gaussianity, we also provide robust guarantees that hold under heavy-tailed noise settings. Together, these findings provide a principled foundation for the optimality of ERM trees and introduce empirical process tools broadly applicable to other highly adaptive, data-driven procedures.
• Abstract（参考訳）: グローバルに最適な経験的リスク最小化(ERM)決定木は計算可能で経験的に成功しているが、統計的性能の厳密な理論的保証は限られている。 本研究では,高次元回帰と分類の両方においてランダムな設計の下でERM木の包括的統計理論を開発する。 まず,最大でL$の葉を持つ木が達成できる最適近似に対して,ERM推定器の過大なリスクを負う鋭いオラクル不等式を確立し,解釈可能性と精度のトレードオフを特徴づける。 実験的な局所化Rademacher複雑性に基づく新しい一様濃度フレームワークを用いて,これらの結果を導出する。 さらに、新しい関数クラスよりも極小最大速度(PSHAB)を導出する。 この空間は、空間性、異方性、空間的不均一性の3つの重要な構造的特徴を明示的に捉えている。 我々の主な成果は、準ガウス性の下で確立されているが、重み付きノイズ設定で保持される堅牢な保証も提供する。 これらの知見は、ERMツリーの最適性の基礎となるとともに、他の高度に適応し、データ駆動の手順に広く適用可能な経験的プロセスツールを導入している。

関連論文リスト

• Efficient Thought Space Exploration through Strategic Intervention [54.35208611253168]
  本稿では,この知見を2つの相乗的コンポーネントを通して操作するHint-Practice Reasoning(HPR)フレームワークを提案する。 フレームワークの中核となる革新は、動的に介入点を識別する分散不整合低減(DIR)である。 算術的および常識的推論ベンチマークによる実験は、HPRの最先端の効率-精度トレードオフを実証している。
  論文  参考訳（メタデータ） (2025-11-13T07:26:01Z)
• NDCG-Consistent Softmax Approximation with Accelerated Convergence [67.10365329542365]
  本稿では,ランキングの指標と直接一致した新たな損失定式化を提案する。 提案したRG損失を高効率な Alternating Least Squares (ALS) 最適化手法と統合する。 実世界のデータセットに対する実証的な評価は、我々のアプローチが同等または上位のパフォーマンスを達成することを示す。
  論文  参考訳（メタデータ） (2025-06-11T06:59:17Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Tuning for Trustworthiness -- Balancing Performance and Explanation Consistency in Neural Network Optimization [49.567092222782435]
  我々は,異なる特徴帰属法間の合意として定義された,XAI整合性という新しい概念を紹介する。 予測性能と説明のバランスをとる多目的最適化フレームワークを構築した。 本研究は、トレードオフゾーンバランス性能損失とXAI整合性による強靭性向上のモデルについて、今後の研究基盤を提供する。
  論文  参考訳（メタデータ） (2025-05-12T13:19:14Z)
• Risk-Averse Certification of Bayesian Neural Networks [70.44969603471903]
  本稿では,RAC-BNNと呼ばれるベイズニューラルネットワークに対するリスク・アバース認証フレームワークを提案する。 提案手法はサンプリングと最適化を利用して,BNNの出力集合の音響近似を計算する。 我々は,RAC-BNNを回帰および分類ベンチマークで検証し,その性能を最先端の手法と比較した。
  論文  参考訳（メタデータ） (2024-11-29T14:22:51Z)
• Fair Risk Minimization under Causal Path-Specific Effect Constraints [3.0232957374216953]
  本稿では,機械学習を用いて最適な予測を推定するためのフレームワークを提案する。 平均二乗誤差とクロスエントロピーリスク基準に基づく制約付き最適化のための閉形式解を導出する。
  論文  参考訳（メタデータ） (2024-08-03T02:05:43Z)
• Statistical Properties of Robust Satisficing [5.0139295307605325]
  Robust Satisficing(RS)モデルは、堅牢な最適化に対する新たなアプローチである。 本稿では,RSモデルの理論的特性を包括的に解析する。 実験の結果,RSモデルは小サンプル体制における基礎的経験的リスクを常に上回ることがわかった。
  論文  参考訳（メタデータ） (2024-05-30T19:57:28Z)
• Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximation [54.61816424792866]
  本稿では,リスク感性分布強化学習(RS-DisRL)と静的リプシッツリスク対策(LRM),一般関数近似について紹介する。 モデルに基づく関数近似のためのモデルベース戦略であるtextttRS-DisRL-M と、一般値関数近似のためのモデルフリーアプローチである textttRS-DisRL-V の2つの革新的なメタアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-02-28T08:43:18Z)
• Bayesian Nonparametrics Meets Data-Driven Distributionally Robust Optimization [29.24821214671497]
  機械学習と統計モデルのトレーニングは、しばしばデータ駆動型リスク基準の最適化を伴う。 ベイズ的非パラメトリック(ディリクレ過程)理論と、スムーズなあいまいさ-逆選好の最近の決定論的モデルを組み合わせた、新しいロバストな基準を提案する。 実用的な実装として、よく知られたディリクレプロセスの表現に基づいて、評価基準の抽出可能な近似を提案し、研究する。
  論文  参考訳（メタデータ） (2024-01-28T21:19:15Z)
• f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization [9.591164070876689]
  本稿では、f-divergence measures(f-FERM)に基づく公正な経験的リスクに対する統一的な最適化フレームワークを提案する。 さらに,f-FERMによるほぼ全てのバッチサイズに対するフェアネス・精度トレードオフの優位性を実証した。 我々の拡張は、不確実集合として$L_p$ノルムの下で f-FERM の目的を分布的に頑健に最適化する手法に基づいている。
  論文  参考訳（メタデータ） (2023-12-06T03:14:16Z)
• Federated Distributionally Robust Optimization with Non-Convex Objectives: Algorithm and Analysis [21.913563167426872]
  Asynchronous Single-looP alternatIve gRadient projEction という非同期分散アルゴリズムを提案する。 新しい不確実性集合、すなわち制約付きD-ノルムの不確実性集合は、以前の分布を利用し、強靭性の度合いを柔軟に制御するために開発される。 実世界のデータセットに関する実証研究は、提案手法が高速収束を達成できるだけでなく、悪意のある攻撃だけでなく、データに対する堅牢性も維持できることを示した。
  論文  参考訳（メタデータ） (2023-07-25T01:56:57Z)
• On the Variance, Admissibility, and Stability of Empirical Risk Minimization [57.63331017830154]
  経験的リスク最小化(ERM: Empirical Risk Minimization)は、平均2乗誤差で最小限の最適値が得られる。 比較的軽度な仮定の下では、ERMの準最適性はその大きなバイアスによるものでなければならない。
  論文  参考訳（メタデータ） (2023-05-29T15:25:48Z)
• Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence [66.83161885378192]
  ROC(AUROC)と精度リコール曲線(AUPRC)の下の領域は、不均衡問題に対する分類性能を評価するための一般的な指標である。 本稿では,深層学習のためのAUPRCの最適化手法を提案する。
  論文  参考訳（メタデータ） (2021-04-18T06:22:21Z)

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

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