論文の概要: Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization
- arxiv url: http://arxiv.org/abs/2206.08573v1
- Date: Fri, 17 Jun 2022 06:10:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-20 15:48:02.146426
- Title: Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization
- Title（参考訳）: 最適外向き二成分結合サドル点最適化
- Authors: Simon S. Du, Gauthier Gidel, Michael I. Jordan, Chris Junchi Li
- Abstract要約: 滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
- 参考スコア（独自算出の注目度）: 116.89941263390769
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the smooth convex-concave bilinearly-coupled saddle-point
problem, $\min_{\mathbf{x}}\max_{\mathbf{y}}~F(\mathbf{x}) +
H(\mathbf{x},\mathbf{y}) - G(\mathbf{y})$, where one has access to stochastic
first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$.
Building upon standard stochastic extragradient analysis for variational
inequalities, we present a stochastic \emph{accelerated gradient-extragradient
(AG-EG)} descent-ascent algorithm that combines extragradient and Nesterov's
acceleration in general stochastic settings. This algorithm leverages scheduled
restarting to admit a fine-grained nonasymptotic convergence rate that matches
known lower bounds by both \citet{ibrahim2020linear} and \citet{zhang2021lower}
in their corresponding settings, plus an additional statistical error term for
bounded stochastic noise that is optimal up to a constant prefactor. This is
the first result that achieves such a relatively mature characterization of
optimality in saddle-point optimization.
- Abstract（参考訳）: 滑らかな凸凸凸双線型共役saddle-point問題、$\min_{\mathbf{x}}\max_{\mathbf{y}}~f(\mathbf{x}) + h(\mathbf{x},\mathbf{y}) - g(\mathbf{y})$ を考える。
変分不等式に対する標準確率的超次数解析に基づいて,一般の確率的設定において,超次数とネステロフの加速度を結合した確率的昇降アルゴリズムを提案する。
このアルゴリズムは、スケジュールされた再起動を利用して、既知の下界と対応する設定で一致するような細粒度の漸近収束率を許容し、また、一定の事前因子に最適化された有界確率雑音に対するさらなる統計誤差項を付与する。
これは、鞍点最適化における最適性の比較的成熟したキャラクタリゼーションを達成する最初の結果である。
関連論文リスト
- An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
本稿では,上層関数が非非有界な滑らかさであり,下層関数が強く凸であるような二層最適化問題のクラスについて検討する。
これらの問題は、ニューラルネットワークを用いたテキスト分類など、データ学習に大きな応用がある。
論文 参考訳（メタデータ） (2024-09-28T02:30:44Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises:
High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。
本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
論文 参考訳（メタデータ） (2023-03-22T03:05:28Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs [16.96562173221624]
有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。
特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。
崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
論文 参考訳（メタデータ） (2020-05-15T21:14:22Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。