論文の概要: Proximal Gradient Descent-Ascent: Variable Convergence under K{\L}
Geometry
- arxiv url: http://arxiv.org/abs/2102.04653v1
- Date: Tue, 9 Feb 2021 05:35:53 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-10 14:50:46.310276
- Title: Proximal Gradient Descent-Ascent: Variable Convergence under K{\L}
Geometry
- Title（参考訳）: K{\L} ジオメトリにおける近位勾配Descent-Ascent: Variable Convergence
- Authors: Ziyi Chen, Yi Zhou, Tengyu Xu, Yingbin Liang
- Abstract要約: 有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。
本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
- 参考スコア（独自算出の注目度）: 49.65455534654459
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The gradient descent-ascent (GDA) algorithm has been widely applied to solve
minimax optimization problems. In order to achieve convergent policy parameters
for minimax optimization, it is important that GDA generates convergent
variable sequences rather than convergent sequences of function values or
gradient norms. However, the variable convergence of GDA has been proved only
under convexity geometries, and there lacks understanding for general nonconvex
minimax optimization. This paper fills such a gap by studying the convergence
of a more general proximal-GDA for regularized nonconvex-strongly-concave
minimax optimization. Specifically, we show that proximal-GDA admits a novel
Lyapunov function, which monotonically decreases in the minimax optimization
process and drives the variable sequence to a critical point. By leveraging
this Lyapunov function and the K{\L} geometry that parameterizes the local
geometries of general nonconvex functions, we formally establish the variable
convergence of proximal-GDA to a critical point $x^*$, i.e., $x_t\to x^*,
y_t\to y^*(x^*)$. Furthermore, over the full spectrum of the
K{\L}-parameterized geometry, we show that proximal-GDA achieves different
types of convergence rates ranging from sublinear convergence up to finite-step
convergence, depending on the geometry associated with the K{\L} parameter.
This is the first theoretical result on the variable convergence for nonconvex
minimax optimization.
- Abstract（参考訳）: 勾配降下度アルゴリズム(GDA)は極小最適化問題の解法として広く応用されている。
ミニマックス最適化のための収束ポリシーパラメータを達成するためには、GDAが関数値や勾配ノルムの収束シーケンスではなく収束変数シーケンスを生成することが重要です。
しかし、GDAの変数収束は凸ジオメトリーの下でのみ証明され、一般の非凸極小最適化に対する理解が欠如している。
本稿では,正規化非凸強凸ミニマックス最適化のためのより一般的な近位gdaの収束を研究することにより,そのようなギャップを埋める。
具体的には、近位GDAは、ミニマックス最適化プロセスの単調に減少し、可変列を臨界点に駆動する新しいLyapunov関数を認めることを示した。
この Lyapunov 関数と一般非凸関数の局所幾何をパラメータ化する K{\L} ジオメトリを利用することで、近位-GDA の変数収束をクリティカル点 $x^*$、すなわち $x_t\to x^*, y_t\to y^*(x^*)$ に公式に確立する。
さらに、K{\L}-パラメータ化幾何学の全スペクトル上で、近位GDAは、K{\L}パラメータに付随する幾何によって、下線収束から有限ステップ収束までの様々な種類の収束率を達成することを示す。
これは、非凸ミニマックス最適化の変数収束に関する最初の理論結果である。
関連論文リスト
- On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳（メタデータ） (2023-05-30T17:47:27Z) - On the Convergence of AdaGrad(Norm) on $\R^{d}$: Beyond Convexity,
Non-Asymptotic Rate and Acceleration [33.247600151322466]
我々は、滑らかな凸関数の標準設定において、AdaGradとその変種についてより深く理解する。
まず、制約のない問題に対して、バニラ AdaGrad の収束率を明示的に拘束する新しい手法を示す。
第二に、平均的な反復ではなく、最後の反復の収束を示すことのできる AdaGrad の変種を提案する。
論文 参考訳（メタデータ） (2022-09-29T14:44:40Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Escaping Saddle Points in Nonconvex Minimax Optimization via
Cubic-Regularized Gradient Descent-Ascent [13.565010494569243]
勾配降下度アルゴリズム(GDA)は、非ミニマックス最適化問題の解法として広く応用されている。
我々は,非コンケーブ極小最適化における点のエスケープのための第一型GDAアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-10-14T00:36:44Z) - 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) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - The Convergence Indicator: Improved and completely characterized
parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
我々は、粒子が最終的に単一点に収束するか、分岐するかを計算するのに使用できる新しい収束指標を導入する。
この収束指標を用いて、収束群につながるパラメータ領域を完全に特徴づける実際の境界を提供する。
論文 参考訳（メタデータ） (2020-06-06T19:08:05Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。