論文の概要: 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})$ を考える。
変分不等式に対する標準確率的超次数解析に基づいて,一般の確率的設定において,超次数とネステロフの加速度を結合した確率的昇降アルゴリズムを提案する。
このアルゴリズムは、スケジュールされた再起動を利用して、既知の下界と対応する設定で一致するような細粒度の漸近収束率を許容し、また、一定の事前因子に最適化された有界確率雑音に対するさらなる統計誤差項を付与する。
これは、鞍点最適化における最適性の比較的成熟したキャラクタリゼーションを達成する最初の結果である。
関連論文リスト
- Finite-Time Error Bounds for Greedy-GQ [25.655180037837766]
We show that Greedy-GQ algorithm converges under $1/s。
我々の分析は、実際の収束を早めるためのステップサイズの選択を提供し、貿易の複雑さと得られた政策の質を示唆する。
論文 参考訳（メタデータ） (2022-09-06T15:04:57Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Convergence and Complexity of Stochastic Subgradient Methods with
Dependent Data for Nonconvex Optimization [7.513100214864646]
一般データサンプリング方式では,弱凸関数に対する古典的および近位下降法が最悪のケース収束率を有することを示す。
最適収束保証率と適応的なステップサイズを持つ投影勾配法に基づく従属データに対する最初のオンライン非行列分解アルゴリズムを得る。
論文 参考訳（メタデータ） (2022-03-29T17:59:10Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。