論文の概要: 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}」の結果を一般化することを示した。
提案手法の高速収束を示す実験により,実験結果を補完する。
関連論文リスト
- Convergence of Some Convex Message Passing Algorithms to a Fixed Point [0.0]
グラフィカルモデルにおけるMAP推論問題に対する一般的なアプローチは、双対線型計画法や(ブロック座標)降下によるラグランジュ緩和から得られる上限を最小化することである。
より強い結果(これは以前予想されたが、決して証明されなかった)を証明します。
本研究の主な結果とは対照的に,制約付き最適化問題に適用された座標降下の類似バージョンは収束しないことを示す。
論文 参考訳(メタデータ) (2024-03-07T13:14:21Z) - Revisiting Subgradient Method: Complexity and Convergence Beyond
Lipschitz Continuity [29.56022052936922]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究ではまず, 次進法における典型的な複雑性を, 対物関数の凸度と弱凸度に拡張する。
ステップサイズの適切な減少規則を用いて,非Lipschitz凸および弱凸目的関数に対する収束結果を提供する。
論文 参考訳(メタデータ) (2023-05-23T15:26:36Z) - Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。
また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
論文 参考訳(メタデータ) (2023-04-27T06:27:37Z) - 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) - ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm [77.71051081132912]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
emphRecursive One-Over-T Root (ROOTSGD) と呼ばれる小説を考案する。
有限サンプル勾配, 漸近感覚, 感覚を同時に達成することを証明する。
論文 参考訳(メタデータ) (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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。