Fugu-MT 論文翻訳(概要): Tight Generalization Bound for AdaBoost

論文の概要: Tight Generalization Bound for AdaBoost

arxiv url: http://arxiv.org/abs/2607.26838v1
Date: Wed, 29 Jul 2026 12:27:29 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-30 21:06:25.664606
Title: Tight Generalization Bound for AdaBoost
Title（参考訳）: AdaBoostのタイト一般化境界
Abstract要約: AdaBoostの一般化誤差は$big(tfracdln(n2/d)n2+tfracln (1/)nbig)$であることを示す。
参考スコア（独自算出の注目度）: 6.768558752130311
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this paper we show that the generalization error of AdaBoost is $Θ\big(\tfrac{d\ln(nγ^{2}/d)}{nγ^2}+\tfrac{\ln(1/δ)}{n}\big)$, where $γ$ is the advantage guaranteed by the weak learner, $d$ is the VC-dimension of the class containing the weak hypotheses, $n$ is the sample size, and $δ$ is the confidence parameter. The contribution of this paper is the upper bound; the matching lower bound follows from prior work. The upper bound proof follows by combining the known fact that AdaBoost outputs a voting classifier whose voting function has zero empirical $γ/2$-margin loss with what is, to the best of our knowledge, a new margin-based generalization bound for voting classifiers.
Abstract（参考訳）: 本稿では、AdaBoost の一般化誤差が $ \big(\tfrac{d\ln(nγ^{2}/d)}{nγ^2}+\tfrac{\ln(1/δ)}{n}\big)$, ここで、$γ$ は弱学習者によって保証される利点であり、$d$ は弱仮説を含むクラスの VC-次元であり、$n$ は標本サイズであり、$δ$ は信頼パラメータであることを示す。本論文の寄与は上界であり, 一致する下界は先行作業から従う。上界証明は、AdaBoostが、投票関数が経験的な$γ/2$-margin損失がゼロである投票分類器を出力しているという既知の事実と、我々の知る限り、投票分類器の新たなマージンベースの一般化を組み合わせて、従う。

関連論文リスト

Inevitability of Encrypted Traffic Side-Channel Leakage in the Multi-Class Setting [20.06940271479014]
クラスごとの分解$I(X;Y)=sum_i_i D_mathrmKL(P_Y|i|P_Y)$を介して、Side-Channel Existence Theoremを$k$クラスに拡張します。以下の3つの結果が従う: (1) 活性クラス全体の和形式 MI の下限、(2) カスケード臨界コスト定理と、一様予算境界が消滅する非ゼロ、(3) 精度 $mathrmAcc*
論文参考訳（メタデータ） (2026-09-06T00:48:40Z)
Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH [11.157319736363823]
より構造化された亜種である Factorized AdaBoost.MH は $mathbfh(x)=mathbfv bmvarphi(x)$ という形の基底分類器を使用する。因子化 AdaBoost.MH は AdaBoost.MH と同じ加速型収束率を普遍定数係数まで達成することを示す。
論文参考訳（メタデータ） (2026-08-02T08:46:38Z)
Boosting with List-Decodable Codes [4.3070965805068875]
我々は,$O(log frac1)$-XORの下で閉じた任意のクラスに対して,新しいブースティングアルゴリズムを提案する。我々のアルゴリズムは、ブーピングとリストデコダブルコードの間の新しい単純な接続から生まれる。
論文参考訳（メタデータ） (2026-07-07T03:34:53Z)
Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
我々は、Rényi tripartite information $I_3() が小フェルミ運動量での質的に $exclusion-dependent scaling を示すことを示した。 I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal can builded from integer Rényi data。
論文参考訳（メタデータ） (2026-03-09T22:27:00Z)
Proofs as Explanations: Short Certificates for Reliable Predictions [25.157401709060064]
我々は、予測$h(x)=y$がトレーニングデータのサブセット$S'$から成り立つ、説明可能なAIのモデルを考える。集合 $S'$ of size $d+1$ は正の予測の説明として解放され、実現可能性の仮定の下での予測の正しさの短い証明として機能する。
論文参考訳（メタデータ） (2025-04-11T09:26:37Z)
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
スムースブースターは任意の例にあまり重みを付けない分布を生成する。もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
論文参考訳（メタデータ） (2024-09-17T23:09:25Z)
Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文参考訳（メタデータ） (2024-06-18T08:54:04Z)
Boosting with Tempered Exponential Measures [40.961820572346426]
一般的なMLアルゴリズムであるAdaBoostは、相対エントロピー最小化問題の双対から導出することができる。我々は、この設定を最近導入された指数測度(TEM)に一般化し、測度そのものではなく、測度の特定の力に正規化を強制する。我々のアルゴリズム $t$-AdaBoost は AdaBoostas を特別なケース (t=1$)
論文参考訳（メタデータ） (2023-06-08T18:17:48Z)
Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文参考訳（メタデータ） (2023-03-06T17:54:33Z)
Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
論文参考訳（メタデータ） (2023-02-27T16:34:21Z)
Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization [10.787390511207683]
二つの微分可能な$L$-smooth, $mu$-strongly convex objective $phimph over a $ntimes n$frac14(L/mu-1)2rstar$を考える。非局所性にもかかわらず、局所最適化は、任意の初期点から大域的最適点へグローバルに収束することが保証される。
論文参考訳（メタデータ） (2022-07-05T03:18:17Z)
High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文参考訳（メタデータ） (2022-04-06T13:50:33Z)
Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文参考訳（メタデータ） (2020-06-29T17:10:10Z)

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