論文の概要: Adaptive extra-gradient methods for min-max optimization and games
- arxiv url: http://arxiv.org/abs/2010.12100v2
- Date: Thu, 19 Nov 2020 13:47:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-04 08:43:06.822598
- Title: Adaptive extra-gradient methods for min-max optimization and games
- Title（参考訳）: min-max最適化とゲームのための適応的外勾配法
- Authors: Kimon Antonakopoulos and E. Veronica Belmega and Panayotis
Mertikopoulos
- Abstract要約: 本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。
この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。
滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
- 参考スコア（独自算出の注目度）: 35.02879452114223
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a new family of min-max optimization algorithms that automatically
exploit the geometry of the gradient data observed at earlier iterations to
perform more informative extra-gradient steps in later ones. Thanks to this
adaptation mechanism, the proposed method automatically detects whether the
problem is smooth or not, without requiring any prior tuning by the optimizer.
As a result, the algorithm simultaneously achieves order-optimal convergence
rates, i.e., it converges to an $\varepsilon$-optimal solution within
$\mathcal{O}(1/\varepsilon)$ iterations in smooth problems, and within
$\mathcal{O}(1/\varepsilon^2)$ iterations in non-smooth ones. Importantly,
these guarantees do not require any of the standard boundedness or Lipschitz
continuity conditions that are typically assumed in the literature; in
particular, they apply even to problems with singularities (such as resource
allocation problems and the like). This adaptation is achieved through the use
of a geometric apparatus based on Finsler metrics and a suitably chosen
mirror-prox template that allows us to derive sharp convergence rates for the
methods at hand.
- Abstract（参考訳）: 本稿では,前回観測した勾配データの幾何を自動的に活用し,後回からより有意義な超勾配ステップを行う,min-max最適化アルゴリズムの新たなファミリーを提案する。
この適応機構により、オプティマイザによる事前チューニングを必要とせず、問題の滑らかさを自動で検出する。
その結果、アルゴリズムは次数-最適収束率を同時に達成し、すなわち、滑らかな問題における$\mathcal{o}(1/\varepsilon)$の反復と、非スムース問題における$\mathcal{o}(1/\varepsilon^2)$の反復で$\varepsilon$-optimalの解に収束する。
重要なことに、これらの保証は、典型的には文献で仮定される標準有界性やリプシッツ連続性条件を一切必要とせず、特に特異点を持つ問題(資源割り当て問題など)にも適用される。
この適応は、フィンスラー計量に基づく幾何学的装置と、手前の方法の鋭い収束率を導出できる適切な選択されたミラープロックステンプレートを使用することによって達成される。
関連論文リスト
- Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。
本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。
本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
論文 参考訳（メタデータ） (2024-06-18T20:14:52Z) - Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization [32.939120407900035]
私たちのアルゴリズムは、イテレーション毎に1つの線形システムだけを解決する必要のある、単純な更新ルールを備えています。
また,提案アルゴリズムの実用性能を,既存の2次アルゴリズムと比較して評価した。
論文 参考訳（メタデータ） (2024-06-04T06:56:41Z) - An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - 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 Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。