論文の概要: Reducing Discretization Error in the Frank-Wolfe Method
- arxiv url: http://arxiv.org/abs/2304.01432v1
- Date: Tue, 4 Apr 2023 00:43:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-05 16:01:25.088138
- Title: Reducing Discretization Error in the Frank-Wolfe Method
- Title（参考訳）: フランクウルフ法による離散化誤差の低減
- Authors: Zhaoyue Chen, Yifan Sun
- Abstract要約: Frank-Wolfeアルゴリズムは、構造的に制約された機械学習アプリケーションで一般的な方法である。
この手法の1つの大きな制限は、不安定なジグザグングステップの方向のために加速が難しい収束速度の遅いことである。
最適化された高次離散化スキームを直接適用するマルチステップFrank-Wolfe法と、離散化誤差を低減したLMO-averagingスキームの2つの改善を提案する。
- 参考スコア（独自算出の注目度）: 2.806911268410107
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Frank-Wolfe algorithm is a popular method in structurally constrained
machine learning applications, due to its fast per-iteration complexity.
However, one major limitation of the method is a slow rate of convergence that
is difficult to accelerate due to erratic, zig-zagging step directions, even
asymptotically close to the solution. We view this as an artifact of
discretization; that is to say, the Frank-Wolfe \emph{flow}, which is its
trajectory at asymptotically small step sizes, does not zig-zag, and reducing
discretization error will go hand-in-hand in producing a more stabilized
method, with better convergence properties. We propose two improvements: a
multistep Frank-Wolfe method that directly applies optimized higher-order
discretization schemes; and an LMO-averaging scheme with reduced discretization
error, and whose local convergence rate over general convex sets accelerates
from a rate of $O(1/k)$ to up to $O(1/k^{3/2})$.
- Abstract（参考訳）: Frank-Wolfeアルゴリズムは、構造的に制約された機械学習アプリケーションで一般的な方法である。
しかし、この方法の1つの大きな制限は、解に漸近的に近づいたとしても、不安定なジグザグングステップの方向のために加速し難い収束速度である。
これは離散化の成果物であり、つまり、漸近的に小さなステップサイズでの軌道であるFrank-Wolfe \emph{flow} は zig-zag ではなく、離散化誤差を減らせばより安定な方法が生成され、より良い収束性を持つ。
最適化された高階離散化スキームを直接適用するマルチステップのFrank-Wolfe法と、離散化誤差を低減し、一般凸集合上の局所収束速度が$O(1/k)$から$O(1/k^{3/2})$まで加速するLMO拡張スキームを提案する。
関連論文リスト
- Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳（メタデータ） (2024-02-04T05:54:51Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳（メタデータ） (2023-04-23T20:05:09Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - A Multistep Frank-Wolfe Method [2.806911268410107]
フランク=ウルフ法におけるジグザグ現象を離散化の成果物として検討した。
多重ステップのフランク・ウルフ変種は、トラニケート誤差が$O(Deltap)$として崩壊し、$p$はメソッドの順序である。
論文 参考訳（メタデータ） (2022-10-14T21:12:01Z) - Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method
for Empirical Risk Minimization [1.4504054468850665]
In Empirical Minimization -- Minimization -- We present a novel computer step-size approach to we have compute guarantees。
提案手法は実世界のバイナリデータセットに非常に重要な問題を示す。
また、計算の保証を得るための新しい適応的なステップサイズアプローチを提案する。
論文 参考訳（メタデータ） (2022-08-30T00:08:37Z) - Accelerating Frank-Wolfe via Averaging Step Directions [2.806911268410107]
ステップ方向が過去のオラクル呼び出しの単純な重み付け平均であるフランク=ウルフの修正を考える。
本手法は, スパース多様体が検出された後に, いくつかの問題に対して収束率を向上することを示す。
論文 参考訳（メタデータ） (2022-05-24T05:26:25Z) - Nesterov Accelerated Shuffling Gradient Method for Convex Optimization [15.908060383231371]
このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。
我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。
数値シミュレーションはアルゴリズムの効率を実証する。
論文 参考訳（メタデータ） (2022-02-07T21:23:17Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z) - Boosting Frank-Wolfe by Chasing Gradients [26.042029798821375]
本稿では,降下方向をサブルーチンによる負勾配に整合させることにより,Frank-Wolfeアルゴリズムの高速化を提案する。
我々は、一連の計算実験において、反復時間とCPU時間の両方において、その競争上の優位性を実証する。
論文 参考訳（メタデータ） (2020-03-13T16:29:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。