論文の概要: An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent
- arxiv url: http://arxiv.org/abs/2604.03782v1
- Date: Sat, 04 Apr 2026 16:08:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-07 15:49:18.76838
- Title: An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent
- Title（参考訳）: アンコレドグラディエント沈み込みにおける最終Iterate Convergence速度の改善
- Authors: Anja Surina, Arun Suggala, George Tsoukalas, Anton Kovsharov, Sergey Shirobokov, Francisco J. R. Ruiz, Pushmeet Kohli, Swarat Chaudhuri,
- Abstract要約: 滑らかな凸凹 min-max 問題に対する Anchored Gradient Descent Ascent アルゴリズムの最終点収束を解析した。
この結果は、Leanで正式な証明を書くことができるAIシステムによって自律的に発見された。
- 参考スコア（独自算出の注目度）: 16.33291279757442
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We analyze the last-iterate convergence of the Anchored Gradient Descent Ascent algorithm for smooth convex-concave min-max problems. While previous work established a last-iterate rate of $\mathcal{O}(1/t^{2-2p})$ for the squared gradient norm, where $p \in (1/2, 1)$, it remained an open problem whether the improved exact $\mathcal{O}(1/t)$ rate is achievable. In this work, we resolve this question in the affirmative. This result was discovered autonomously by an AI system capable of writing formal proofs in Lean. The Lean proof can be accessed at https://github.com/google-deepmind/formal-conjectures/pull/3675/commits/a13226b49fd3b897f4c409194f3b cbeb96a08515
- Abstract（参考訳）: 我々は, 滑らかな凸凹 min-max 問題に対する Anchored Gradient Descent Ascent アルゴリズムの最終点収束を解析した。
以前の研究は、二乗勾配ノルムに対して$\mathcal{O}(1/t^{2-2p})$の最後の定位レートを確立したが、$p \in (1/2, 1)$は、改善された正確な$\mathcal{O}(1/t)$レートが達成可能かどうかという未解決の問題のままであった。
本稿では、この問題を肯定的に解決する。
この結果は、Leanで正式な証明を書くことができるAIシステムによって自律的に発見された。
Leanの証明はhttps://github.com/google-deepmind/formal-conjectures/pull/3675/commits/a13226b49fd3b897f4c409194f3b cbeb96a08515でアクセスすることができる。
関連論文リスト
- Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。
我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
論文 参考訳（メタデータ） (2024-03-05T12:28:00Z) - High Probability Convergence of Stochastic Gradient Methods [15.829413808059124]
最適解への初期距離に依存する有界収束を示す。
AdaGrad-Normのハイバウンドが得られることを示す。
論文 参考訳（メタデータ） (2023-02-28T18:42:11Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [11.15373699918747]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
本稿では,機械学習,統計的学習,ネットワーク最適化などにおける顕著な応用を網羅した大規模有限サム包含のクラスに適用する。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad
Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。
我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。
我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文 参考訳（メタデータ） (2022-04-06T13:50:33Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。