論文の概要: Last-Iterate Convergence of Optimistic Multiplicative Weight Update

• arxiv url: http://arxiv.org/abs/2606.11773v1
• Date: Wed, 10 Jun 2026 07:57:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-11 16:42:38.352525
• Title: Last-Iterate Convergence of Optimistic Multiplicative Weight Update
• Title（参考訳）: 最適乗算重み更新における最終Iterate Convergence
• Authors: Francesco Orabona,
• Abstract要約: 最後のOGDAは滑らかな問題においてサドル点に収束することが知られている。 OMWUが同じ資産を持っているかどうかは不明である。 I show that OMWU convergesally for smooth convex-concave saddle-point problem。
• 参考スコア（独自算出の注目度）: 13.093938062156852
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative-Weights Update (OMWU) are two very popular algorithms to solve convex/concave saddle-point problems, where OMWU is the non-Euclidean, entropic version of OGDA. It is known since the '80s that the last iterate of OGDA asymptotically converges to a saddle point in smooth problems. On the other hand, it is unknown if OMWU has the same property. In this paper, I show that OMWU converges asymptotically for smooth convex-concave saddle-point problems, with a small enough constant learning rate. The result does not require uniqueness, strict complementarity, an error bound, or initialization near a solution. The main new ingredient is a boundary argument showing that every cluster point satisfies the inactive-coordinate KKT inequalities. The boundary argument was discovered with assistance from ChatGPT and is documented in the appendix.
• Abstract（参考訳）: Optimistic Gradient Descent Ascent (OGDA) とOptimistic Multiplicative-Weights Update (OMWU) は、OGDAの非ユークリッドエントロピーバージョンである凸/凹サドル問題を解くための非常に一般的なアルゴリズムである。 80年代以降、OGDAの最後の反復が漸近的に滑らかな問題においてサドル点に収束することが知られている。 一方、OMWUが同じ性質を持っているかどうかは不明である。 本稿では,OMWUが円滑な凸凹型サドル点問題に対して漸近的に収束することを示す。 結果は、一意性、厳密な相補性、エラー境界、あるいは解の近くでの初期化を必要としない。 主な新しい要素は、すべてのクラスター点が非活性座標KKTの不等式を満たすことを示す境界論である。 境界引数はChatGPTの助けを借りて発見され、付録に記録されている。

関連論文リスト

• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。 有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
  論文  参考訳（メタデータ） (2023-12-13T21:41:06Z)
• Extragradient Type Methods for Riemannian Variational Inequality Problems [25.574847201669144]
  我々は、REG と RPEG の両者の平均収束度が、2020 年の場合と一致する$Oleft(frac1Tright)$であることを示す。 結果はホロノミー効果の偏見に対処することで可能となり、さらなる観測を減らせることができる。
  論文  参考訳（メタデータ） (2023-09-25T14:08:02Z)
• SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization [11.15617238382324]
  SPIRAL は有限和問題に対する収束pRoximal algogomrithor である。 軽微な仮定の下では顕著な収束がある。 それは芸術の状況に競争力がある。
  論文  参考訳（メタデータ） (2022-07-17T14:58:06Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• Proximal Gradient Descent-Ascent: Variable Convergence under K{\L} Geometry [49.65455534654459]
  有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。 本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
  論文  参考訳（メタデータ） (2021-02-09T05:35:53Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
  我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。 平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。 任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-06-16T20:53:04Z)
• Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization [31.185065331321734]
  広く使われているグラディエント・ディキセント/アセンセント法は凸問題におけるサドル点への最終点収束を示す。 我々は、非回帰乗算重み更新法の変則の下で、エム制約最小値最適化のより一般的な問題において、同じことが成り立つことを示す。
  論文  参考訳（メタデータ） (2018-07-11T17:20:03Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。