論文の概要: Beyond Short Steps in Frank-Wolfe Algorithms
- arxiv url: http://arxiv.org/abs/2501.18773v1
- Date: Thu, 30 Jan 2025 21:52:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-03 13:58:18.311727
- Title: Beyond Short Steps in Frank-Wolfe Algorithms
- Title（参考訳）: Frank-Wolfeアルゴリズムのショートステップを超えて
- Authors: David Martínez-Rubio, Sebastian Pokutta,
- Abstract要約: 本稿では,関数のスムーズさを従来のショートステップを超えて活用することで,フランク・ウルフアルゴリズムを強化する新しい手法を提案する。
楽観的なフレームワークを用いた新しいフランク・ウルフアルゴリズムを提案し、原始双対収束証明を提供する。
- 参考スコア（独自算出の注目度）: 25.808224336342683
- License:
- Abstract: We introduce novel techniques to enhance Frank-Wolfe algorithms by leveraging function smoothness beyond traditional short steps. Our study focuses on Frank-Wolfe algorithms with step sizes that incorporate primal-dual guarantees, offering practical stopping criteria. We present a new Frank-Wolfe algorithm utilizing an optimistic framework and provide a primal-dual convergence proof. Additionally, we propose a generalized short-step strategy aimed at optimizing a computable primal-dual gap. Interestingly, this new generalized short-step strategy is also applicable to gradient descent algorithms beyond Frank-Wolfe methods. As a byproduct, our work revisits and refines primal-dual techniques for analyzing Frank-Wolfe algorithms, achieving tighter primal-dual convergence rates. Empirical results demonstrate that our optimistic algorithm outperforms existing methods, highlighting its practical advantages.
- Abstract（参考訳）: 本稿では,関数のスムーズさを従来のショートステップを超えて活用することで,フランク・ウルフアルゴリズムを強化する新しい手法を提案する。
本研究は,基本二元保証を組み込んだステップサイズを持つFrank-Wolfeアルゴリズムに着目し,事実上の停止基準を提供する。
楽観的なフレームワークを用いた新しいフランク・ウルフアルゴリズムを提案し、原始双対収束証明を提供する。
さらに,計算可能な原始双対ギャップの最適化を目的とした,一般化されたショートステップ戦略を提案する。
興味深いことに、この新しい一般化されたショートステップ戦略は、フランク・ウルフ法以外の勾配降下アルゴリズムにも適用できる。
副産物として、Frank-Wolfeアルゴリズムを解析し、より厳密な主元-双対収束率を達成するための原始-双対手法を再検討し、洗練する。
実験の結果、我々の楽観的アルゴリズムは既存の手法よりも優れており、実用的優位性を強調している。
関連論文リスト
- Invex Programs: First Order Algorithms and Their Convergence [66.40124280146863]
Invexプログラムは、固定点ごとに世界最小値が得られる特別な非制約問題である。
そこで我々は,超凸問題における一般収束率を解くために,新しい一階法アルゴリズムを提案する。
提案アルゴリズムは,制約付き凸プログラムを解く最初のアルゴリズムである。
論文 参考訳（メタデータ） (2023-07-10T10:11:01Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳（メタデータ） (2023-04-23T20:05:09Z) - 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) - Regularized Frank-Wolfe for Dense CRFs: Generalizing Mean Field and
Beyond [19.544213396776268]
我々は,高次条件場に対する汎用的で効果的なCNNベースライン推論である正規化Frank-Wolfeを導入する。
新しいアルゴリズム、新しいアルゴリズム、新しいデータセット、強力なニューラルネットワークの大幅な改善が示されています。
論文 参考訳（メタデータ） (2021-10-27T20:44:47Z) - An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm
for First-order and Zeroth-order Optimization [111.24899593052851]
条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。
ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。
1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
論文 参考訳（メタデータ） (2021-09-18T07:08:11Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Projection-Free Adaptive Gradients for Large-Scale Optimization [22.0439695290991]
フランク=ウルフアルゴリズムは、目的から近似した一階情報のみをクエリすることで、両方の計算負担を軽減するため、ユニークな位置を占める。
本手法は,制約付き最適化のための適応アルゴリズムの性能を向上させることができることを示す。
論文 参考訳（メタデータ） (2020-09-29T15:56:12Z) - Efficient Optimization of Dominant Set Clustering with Frank-Wolfe
Algorithms [4.873362301533825]
ドミナント・セット・クラスタリングの効率的な最適化のために,Frank-Wolfeアルゴリズム(標準,ペアワイズ,アウトステップ)について検討する。
フランク=ウルフ法の異なる変種を利用するための統一的で計算効率の良いフレームワークを提案する。
論文 参考訳（メタデータ） (2020-07-22T20:08:41Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳（メタデータ） (2020-06-11T18:49:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。