論文の概要: Blended Conditional Gradients: the unconditioning of conditional gradients
- arxiv url: http://arxiv.org/abs/1805.07311v4
- Date: Fri, 21 Mar 2025 11:03:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-25 14:28:26.571289
- Title: Blended Conditional Gradients: the unconditioning of conditional gradients
- Title（参考訳）: Blended Conditional Gradients: 条件勾配の無条件化
- Authors: Gábor Braun, Sebastian Pokutta, Dan Tu, Stephen Wright,
- Abstract要約: ポリトープP上の滑らかな凸関数を最小化するための混合条件勾配法を提案する。
強凸関数に対する線形収束と実用的な性能を実現する。
このアルゴリズムは遅延性があり、線形プログラミングサブプロブレムの安価な不正確な解を利用する。
- 参考スコア（独自算出の注目度）: 21.157733932548695
- License:
- Abstract: We present a blended conditional gradient approach for minimizing a smooth convex function over a polytope P, combining the Frank--Wolfe algorithm (also called conditional gradient) with gradient-based steps, different from away steps and pairwise steps, but still achieving linear convergence for strongly convex functions, along with good practical performance. Our approach retains all favorable properties of conditional gradient algorithms, notably avoidance of projections onto P and maintenance of iterates as sparse convex combinations of a limited number of extreme points of P. The algorithm is lazy, making use of inexpensive inexact solutions of the linear programming subproblem that characterizes the conditional gradient approach. It decreases measures of optimality (primal and dual gaps) rapidly, both in the number of iterations and in wall-clock time, outperforming even the lazy conditional gradient algorithms of [arXiv:1410.8816]. We also present a streamlined version of the algorithm for the probability simplex.
- Abstract（参考訳）: 本稿では,多面体P上の滑らかな凸関数を最小化するための混合条件勾配法を提案し,Frank-Wolfeアルゴリズム(条件勾配とも呼ばれる)と勾配に基づくステップを組み合わせる。
提案手法は, P の極小点の疎凸結合として, P への射影の回避, 反復の維持など, 条件勾配アルゴリズムの良好な特性を保っている。
これは、[arXiv:1410.8816]の遅延条件勾配アルゴリズムでさえも、イテレーション数とウォールクロック時間の両方において、最適性(最適性と二重ギャップ)の尺度を急速に減少させる。
また,確率単純度に対するアルゴリズムの合理化版も提示する。
関連論文リスト
- Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。
ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。
ゲームにおける高速収束と拡張逆最適化への応用について述べる。
論文 参考訳（メタデータ） (2024-08-17T02:22:08Z) - Efficient Gradient Approximation Method for Constrained Bilevel
Optimization [2.0305676256390934]
大規模高次元データを用いたバイレベル最適化が開発されている。
本稿では凸と微分不可能な近似を伴う制約付き二値問題について考察する。
論文 参考訳（メタデータ） (2023-02-03T19:34:56Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - A conditional gradient homotopy method with applications to Semidefinite Programming [1.3332839594069592]
ホモトピーに基づく条件勾配法による凸最適化問題の解法。
我々の理論的複雑さは、最先端のSDPに直面すると競合し、安価なプロジェクションフリーの決定的な利点がある。
論文 参考訳（メタデータ） (2022-07-07T05:48:27Z) - Constrained and Composite Optimization via Adaptive Sampling Methods [3.4219044933964944]
本論文の動機は,制約付き最適化問題を解くための適応サンプリング手法を開発することにある。
本論文で提案する手法は、f が凸(必ずしも微分可能ではない)である合成最適化問題 min f(x) + h(x) にも適用できる近位勾配法である。
論文 参考訳（メタデータ） (2020-12-31T02:50:39Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Conditional Gradient Methods for Convex Optimization with General Affine
and Nonlinear Constraints [8.643249539674612]
本稿では,一般アフィンおよび非線形制約を用いた凸最適化問題に対する条件勾配法を提案する。
まず、スムーズかつ構造化された非滑らかな関数制約凸最適化に対して、$cal O (1/epsilon2)$の反復複雑性を達成できる新しい制約外挿条件勾配(CoexCG)法を提案する。
さらに,制約外挿法と二重正規化条件勾配法(CoexDurCG)の新たな変種を開発した。
論文 参考訳（メタデータ） (2020-06-30T23:49:38Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。