論文の概要: Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes

• arxiv url: http://arxiv.org/abs/2002.06768v2
• Date: Fri, 21 Feb 2020 05:04:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-31 12:26:02.206061
• Title: Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
• Title（参考訳）: 非回帰学習における最後の反復収束-凸凹景観に対する制約付きmin-max最適化
• Authors: Qi Lei and Sai Ganesh Nagarajan and Ioannis Panageas and Xiao Wang
• Abstract要約: オンライン学習フレームワーク「OMWU(Optimistic Multiplicative-Weights Update)」は,凸凹型ゲームにおいて,最後の反復収束を示す。 提案手法の高速収束を示す実験により,実験結果を補完する。
• 参考スコア（独自算出の注目度）: 33.2931644228746
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In a recent series of papers it has been established that variants of Gradient Descent/Ascent and Mirror Descent exhibit last iterate convergence in convex-concave zero-sum games. Specifically, \cite{DISZ17, LiangS18} show last iterate convergence of the so called "Optimistic Gradient Descent/Ascent" for the case of \textit{unconstrained} min-max optimization. Moreover, in \cite{Metal} the authors show that Mirror Descent with an extra gradient step displays last iterate convergence for convex-concave problems (both constrained and unconstrained), though their algorithm does not follow the online learning framework; it uses extra information rather than \textit{only} the history to compute the next iteration. In this work, we show that "Optimistic Multiplicative-Weights Update (OMWU)" which follows the no-regret online learning framework, exhibits last iterate convergence locally for convex-concave games, generalizing the results of \cite{DP19} where last iterate convergence of OMWU was shown only for the \textit{bilinear case}. We complement our results with experiments that indicate fast convergence of the method.
• Abstract（参考訳）: 最近の一連の論文で、勾配降下/昇降およびミラー降下の変種が凸凸ゼロサムゲームにおいて最後の反復収束を示すことが示されている。 具体的には、 \cite{DISZ17, LiangS18} は \textit{unconstrained} min-max 最適化の場合、いわゆる "Optimistic Gradient Descent/Ascent" の反復収束を示す。 さらに、著者らは \cite{metal} において、余分な勾配ステップを持つミラー降下は、凸凹問題(制約付きと非制約付きの両方)に対する最後の反復収束を示すが、アルゴリズムはオンライン学習フレームワークに従わない。 本研究は, オンライン学習フレームワークを踏襲した"Optimistic Multiplicative-Weights Update (OMWU)"が, 凸凹型ゲームにおいて, 局所的に最終反復収束を示し, OMWUの最終反復収束を \textit{bilinear case} に対してのみ示す「cite{DP19}」の結果を一般化することを示した。 提案手法の高速収束を示す実験により,実験結果を補完する。

関連論文リスト

• Gradient Methods with Online Scaling [19.218484733179356]
  オンライン学習による勾配に基づく手法の収束を加速する枠組みを提案する。 広範に使用される過勾配降下は勾配降下の収束により改善されることを示す。
  論文  参考訳（メタデータ） (2024-11-04T05:04:18Z)
• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• On the Last-Iterate Convergence of Shuffling Gradient Methods [21.865728815935665]
  対象値に関して勾配法をシャッフルする際の最終点収束率を初めて証明する。 我々の結果は、(ほぼ)既存のラストイテレートの下限と一致するか、あるいは、平均的なイテレートの前の最高の上限と同速である。
  論文  参考訳（メタデータ） (2024-03-12T15:01:17Z)
• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
  次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。 本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
  論文  参考訳（メタデータ） (2023-05-23T15:26:36Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• 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)
• 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)

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

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