論文の概要: Boosting and the Expressive Power of Simple Weak Learners via the $γ$-VC Dimension

• arxiv url: http://arxiv.org/abs/2610.10383v1
• Date: Wed, 07 Oct 2026 16:42:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 21:58:23.054581
• Title: Boosting and the Expressive Power of Simple Weak Learners via the $γ$-VC Dimension
• Title（参考訳）: $γ$-VC次元による単純弱学習者のブースティングと表現力
• Abstract要約: 得られた分類器の表現力は、Alonらによって導入された$$-VC次元で調べる。 最初の結果は、このパラメータが弱強学習におけるサンプルの複雑さを、定数因子のスケーリングを$$$で特徴付けることを示している。 また、決定切り株と軸平行長方形の基本概念クラスに対して$$$-VC次元の上下境界を$mathbbRd$で改善する。
• 参考スコア（独自算出の注目度）: 19.237857850212325
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Boosting converts weak hypotheses with a small edge over random guessing into highly accurate predictors, but the expressive power of the resulting classifier can depend strongly on the structure of the base class. We study this phenomenon through the $γ$-VC dimension introduced by Alon et al. (STOC 2021). Our first result shows that this parameter characterizes the sample complexity for weak-to-strong learning up to a constant factor scaling in $γ$. We then sharpen the general relationship between the classic VC dimension and the $γ$-VC dimension. Finally, we also give improved upper and lower bounds on the $γ$-VC dimension for the fundamental concept classes of decision stumps and axis-parallel rectangles in $\mathbb{R}^d$.
• Abstract（参考訳）: ブースティングは、ランダムな推測よりも小さなエッジで弱い仮説を高精度な予測器に変換するが、結果として得られる分類器の表現力は、基底クラスの構造に強く依存する。 Alon et al (STOC 2021) が導入した$γ$-VC次元を用いて, この現象を研究する。 最初の結果は、このパラメータが弱強学習におけるサンプルの複雑さを$γ$の定数因子スケーリングに特徴付けることを示している。 すると、古典的なVC次元と$γ$-VC次元の一般的な関係を研ぎ澄ます。 最後に、$\mathbb{R}^d$ における決定切り株と軸平行長方形の基本的な概念クラスに対して、$γ$-VC次元上の上と下の境界も改善する。

関連論文リスト

• Bagging Robustly Learns VC Classes with Linear Sample Complexity [12.259552039796025]
  我々は,VC クラスが VC 次元$d$O において,サンプル複雑性の線形性に逆向きに頑健に学習可能であることを証明した。 この結果は、Breiman (1996) の古典的なバッグング(ブートストラップアグリゲーション)と堅牢な経験的リスク最小化(RERM)を組み合わせた単純な不適切なアルゴリズムによって達成される。 一般に、このオラクルモデルの学習者は、任意の数のトレーニング例を与えられたとしても、RERMオラクルへの$(dstar)$呼び出しを必要とします。
  論文  参考訳（メタデータ） (2026-08-13T17:36:49Z)
• Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
  実数値関数クラスが一様収束と学習可能性を示す最適尺度について検討する。 本研究の主な成果は,PAC学習の基本定理のスケール敏感な一般化である。 また、定量的サンプルの複雑さと評価可能性に関するオープンな質問をいくつか取り上げる。
  論文  参考訳（メタデータ） (2026-05-13T15:41:30Z)
• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  戦略分類は、個人が分類者の判断に影響を与えるために、コストで特徴を修正できる学習環境を研究する。 中心的な問題は、帰納的(戦略的な)仮説クラスのサンプルの複雑さが、基礎となる仮説クラスの複雑さと、実現可能な操作を管理するコスト構造にどのように依存するかである。 仮説クラスとコスト誘起近傍関係は、$mathbbR_mathtexp$上の一階式で定義することができる。 難易度は, 複雑度によって制御され, 学習性は維持されていることを証明した。
  論文  参考訳（メタデータ） (2026-05-13T12:21:56Z)
• On Reductions and Representations of Learning Problems in Euclidean Spaces [15.07787640047213]
  多くの実用的な予測アルゴリズムはユークリッド空間における入力を表現し、離散的な0/1分類損失を真の自明な代理損失に置き換える。 我々は古典的トポロジカルアプローチと凸性を考慮したボルスク・ウラム理論の一般化を開発する。 また、ランダム性を利用して、より小さな次元で表現できる自然な分類タスクも提示する。
  論文  参考訳（メタデータ） (2024-11-16T12:09:37Z)
• Dual VC Dimension Obstructs Sample Compression by Embeddings [25.63430474763066]
  本研究は、特に極端クラスに焦点を当てた、良好なVCクラスに任意のVCクラスを組み込むことについて研究する。 すべての$d$に対して、$d$の指数よりも小さい任意の極端なVC次元のクラスに組み込むことができないVC次元の$d$を持つクラスが存在することを証明している。 この結果は学習理論において重要な意味を持ち、長期にわたるサンプル圧縮予想に対処するための最も広範囲に研究されたアプローチの1つの基本的限界を明らかにする。
  論文  参考訳（メタデータ） (2024-05-27T12:38:25Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation [67.66904892192794]
  我々は、強化学習のための新しいアルゴリズム、MQL-UCBを用いたモノトニックQ-Learningを提案する。 MQL-UCBは、$tildeO(dsqrtHK)$の最小限の後悔を実現する。 本研究は,非線形関数近似を用いたサンプル効率およびデプロイメント効率のよいQ-ラーニングの設計に重点を置いている。
  論文  参考訳（メタデータ） (2023-11-26T08:31:57Z)
• Restricted Strong Convexity of Deep Learning Models with Smooth Activations [31.003601717265006]
  本研究では,スムーズなアクティベーション機能を持つディープラーニングモデルの最適化問題について検討する。 Restricted Strong Convexity (RSC) に基づく最適化の新しい解析手法を提案する。 深層学習モデルのためのRCCに基づくGDの幾何収束性を確立するための最初の結果である。
  論文  参考訳（メタデータ） (2022-09-29T21:24:26Z)
• New Coresets for Projective Clustering and Applications [34.82221047030618]
  点集合$P$ in $mathbbRd$ が与えられたとき、ゴールは次元$j$、すなわちアフィン部分空間が与えられた距離測度の下で最もよく適合する$k$フラットを見つけることである。 我々は、コーシー、ヴェルシュ、フーバー、ゲマン・マククリール、テューキー、$L_infty$、フェアレグレッションに対して効率的なコアセット構成を提供することを示した。
  論文  参考訳（メタデータ） (2022-03-08T19:50:27Z)

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

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