論文の概要: Boosting as Frank-Wolfe
- arxiv url: http://arxiv.org/abs/2209.10831v1
- Date: Thu, 22 Sep 2022 07:36:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-23 14:34:48.924149
- Title: Boosting as Frank-Wolfe
- Title（参考訳）: Frank-Wolfeとしてのブースティング
- Authors: Ryotaro Mitsuboshi, Kohei Hatano, Eiji Takimoto
- Abstract要約: フランク=ウルフアルゴリズムと任意の二次アルゴリズムを組み合わせた汎用的なブースティング手法を提案する。
ERLPBoost や C-ERLPBoost と同じ収束保証を維持していることを示す。
- 参考スコア（独自算出の注目度）: 0.6875312133832078
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Some boosting algorithms, such as LPBoost, ERLPBoost, and C-ERLPBoost, aim to
solve the soft margin optimization problem with the $\ell_1$-norm
regularization. LPBoost rapidly converges to an $\epsilon$-approximate solution
in practice, but it is known to take $\Omega(m)$ iterations in the worst case,
where $m$ is the sample size. On the other hand, ERLPBoost and C-ERLPBoost are
guaranteed to converge to an $\epsilon$-approximate solution in
$O(\frac{1}{\epsilon^2} \ln \frac{m}{\nu})$ iterations. However, the
computation per iteration is very high compared to LPBoost.
To address this issue, we propose a generic boosting scheme that combines the
Frank-Wolfe algorithm and any secondary algorithm and switches one to the other
iteratively. We show that the scheme retains the same convergence guarantee as
ERLPBoost and C-ERLPBoost. One can incorporate any secondary algorithm to
improve in practice. This scheme comes from a unified view of boosting
algorithms for soft margin optimization. More specifically, we show that
LPBoost, ERLPBoost, and C-ERLPBoost are instances of the Frank-Wolfe algorithm.
In experiments on real datasets, one of the instances of our scheme exploits
the better updates of the secondary algorithm and performs comparably with
LPBoost.
- Abstract（参考訳）: LPBoost、ERLPBoost、C-ERLPBoostなどの強化アルゴリズムは、$\ell_1$-norm正規化でソフトマージン最適化問題を解決することを目指している。
LPBoost は、実際に $\epsilon$-approximate の解に急速に収束するが、最悪の場合、$m$がサンプルサイズである$\Omega(m)$の反復をとることが知られている。
一方、ERLPBoost と C-ERLPBoost は$O(\frac{1}{\epsilon^2} \ln \frac{m}{\nu})$反復の $\epsilon$-approximate 解に収束することが保証される。
しかし、反復毎の計算はLPBoostに比べて非常に高い。
この問題に対処するため,フランク=ウルフアルゴリズムと任意の二次アルゴリズムを組み合わせた汎用的なブースティング手法を提案し,反復的に一方を他方に切り替える。
ERLPBoost や C-ERLPBoost と同じ収束保証を維持していることを示す。
実際に改善するために任意の二次アルゴリズムを組み込むことができる。
このスキームは、ソフトマージン最適化のためのブースティングアルゴリズムの統一的なビューに由来する。
具体的には, LPBoost, ERLPBoost, C-ERLPBoostがFrank-Wolfeアルゴリズムの例であることを示す。
実データセットでの実験では,提案手法のインスタンスの1つが二次アルゴリズムのより良い更新を活用し,lpboostと互換性のある処理を行う。
関連論文リスト
- The Many Faces of Optimal Weak-to-Strong Learning [10.985323882432086]
提案手法は, サンプルの複雑さを証明し得る, 驚くほど単純なブースティングアルゴリズムである。
我々のパイロット実験研究は、我々の新しいアルゴリズムが大規模なデータセットで以前のアルゴリズムより優れていることを示唆している。
論文 参考訳（メタデータ） (2024-08-30T09:38:51Z) - How to Boost Any Loss Function [63.573324901948716]
損失関数はブースティングにより最適化可能であることを示す。
また、古典的な$0の注文設定でまだ不可能な成果を達成できることも示しています。
論文 参考訳（メタデータ） (2024-07-02T14:08:23Z) - The Cost of Parallelizing Boosting [1.9235143628887907]
本研究は,学習用弱強化アルゴリズムの並列化コストについて検討する。
ブースティングの"軽い"並列化でさえ、トレーニングの複雑さが指数関数的に爆発的に大きくなる必要があることを示す。
論文 参考訳（メタデータ） (2024-02-23T07:03:52Z) - Boosting with Tempered Exponential Measures [40.961820572346426]
一般的なMLアルゴリズムであるAdaBoostは、相対エントロピー最小化問題の双対から導出することができる。
我々は、この設定を最近導入された指数測度(TEM)に一般化し、測度そのものではなく、測度の特定の力に正規化を強制する。
我々のアルゴリズム $t$-AdaBoost は AdaBoostas を特別なケース (t=1$)
論文 参考訳（メタデータ） (2023-06-08T18:17:48Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳（メタデータ） (2021-06-21T20:16:40Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - On the Dual Formulation of Boosting Algorithms [92.74617630106559]
AdaBoost,LogitBoost,Soft-marginBoostのラグランジュ問題は、すべて一般化されたヒンジ損失エントロピーの双対問題であることを示す。
これらのブースティングアルゴリズムの2つの問題を見て、より良いマージン分布を維持するという観点から、ブースティングの成功を理解することができることを示す。
論文 参考訳（メタデータ） (2009-01-23T02:14:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。