論文の概要: Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity
- arxiv url: http://arxiv.org/abs/2511.02821v1
- Date: Tue, 04 Nov 2025 18:47:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-05 18:47:06.154055
- Title: Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity
- Title（参考訳）: 高速化Frank-Wolfeアルゴリズム:相補性条件とスパーシリティ
- Authors: Dan Garber,
- Abstract要約: 我々はコンパクト凸集合上の滑らかな凸関数に対する新しい1次高速化アルゴリズムを開発した。
重要な技術的要素は、ソリューションのスパーシリティをキャプチャする相補性条件である。
- 参考スコア（独自算出の注目度）: 10.491266065801982
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop new accelerated first-order algorithms in the Frank-Wolfe (FW) family for minimizing smooth convex functions over compact convex sets, with a focus on two prominent constraint classes: (1) polytopes and (2) matrix domains given by the spectrahedron and the unit nuclear-norm ball. A key technical ingredient is a complementarity condition that captures solution sparsity -- face dimension for polytopes and rank for matrices. We present two algorithms: (1) a purely linear optimization oracle (LOO) method for polytopes that has optimal worst-case first-order (FO) oracle complexity and, aside of a finite \emph{burn-in} phase and up to a logarithmic factor, has LOO complexity that scales with $r/\sqrt{\epsilon}$, where $\epsilon$ is the target accuracy and $r$ is the solution sparsity $r$ (independently of the ambient dimension), and (2) a hybrid scheme that combines FW with a sparse projection oracle (e.g., low-rank SVDs for matrix domains with low-rank solutions), which also has optimal FO oracle complexity, and after a finite burn-in phase, only requires $O(1/\sqrt{\epsilon})$ sparse projections and LOO calls (independently of both the ambient dimension and the rank of optimal solutions). Our results close a gap on how to accelerate recent advancements in linearly-converging FW algorithms for strongly convex optimization, without paying the price of the dimension.
- Abstract（参考訳）: 我々は,コンパクト凸集合上の滑らかな凸関数を最小化するFW(Frank-Wolfe)ファミリーにおいて,(1)ポリトープ,(2)ポリトープの2つの顕著な制約クラスに着目した新しい1次高速化アルゴリズムを開発した。
重要な技術的要素は、多面体(polytopes)の顔次元と行列のランクをキャプチャする相補性条件である。
1 つのアルゴリズムを提案する: (1) 極端最悪の1次数(FO)オラクル複雑性を持つポリトープに対する純粋線形最適化オラクル法(LOO)法と、有限の \emph{burn-in} フェーズと対数係数を除いて、$r/\sqrt{\epsilon}$ にスケールする LOO 複雑性を持ち、$\epsilon$ は目標精度であり、$r$ は解空間幅$r$ とスパースプロジェクションまたはオラクル(例えば、低ランクの解を持つ行列ドメインに対する低ランクSVD)を組み合わせたハイブリッドスキーム。
この結果から, 線形収束FWアルゴリズムの最近の進歩を, 次元の代償を払わずに, 強い凸最適化のために加速する方法のギャップを埋めることができた。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - First-Order Methods for Linearly Constrained Bilevel Optimization [38.19659447295665]
本稿では,高次ヘッセン計算に対する一階線形制約最適化手法を提案する。
線形不等式制約に対しては、$widetildeO(ddelta-1 epsilon-3)$ gradient oracle callにおいて$(delta,epsilon)$-Goldstein固定性を得る。
論文 参考訳（メタデータ） (2024-06-18T16:41:21Z) - First-order Methods for Affinely Constrained Composite Non-convex
Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods [23.948126336842634]
合成非滑らかな最適化問題の解法として, 1次FOMのより低い複雑性境界を確立するための最初の試みを行う。
本手法と提案したIGG法は,ほぼ改善可能であることがわかった。
論文 参考訳（メタデータ） (2023-07-14T19:59:18Z) - Riemannian Projection-free Online Learning [5.918057694291832]
プロジェクション操作は、オンライン勾配降下(OGD)のような最適化アルゴリズムにおける重要な要素である。
これは高次元の設定における計算上の制限や、不条件の制約セットを扱う際に悩まされる。
本稿では,曲面空間上でのオンライン測地線凸最適化において,線形後悔の保証を得る手法を提案する。
論文 参考訳（メタデータ） (2023-05-30T18:22:09Z) - Functional Constrained Optimization for Risk Aversion and Sparsity
Control [7.561780884831967]
リスクとスパーシリティの要件は、ポートフォリオ最適化、アソート計画、放射線計画など、多くのアプリケーションで同時に実施する必要がある。
本稿では,これらの課題に対して凸あるいはスパース軌道を生成するレベル条件勾配(LCG)法を提案する。
提案手法は,極小勾配を解くための内部条件近似(CGO)を最適値のレベル1セット投影することを示す。
論文 参考訳（メタデータ） (2022-10-11T02:51:51Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Second-order Conditional Gradient Sliding [70.88478428882871]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。