論文の概要: Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave
Saddle-Point Problems with Bilinear Coupling
- arxiv url: http://arxiv.org/abs/2112.15199v1
- Date: Thu, 30 Dec 2021 20:31:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-03 15:47:52.710108
- Title: Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave
Saddle-Point Problems with Bilinear Coupling
- Title(参考訳): 双線型カップリングによる平滑および凸凸サドルポイント問題の高速化初等二次勾配法
- Authors: Dmitry Kovalev, Alexander Gasnikov, Peter Richt\'arik
- Abstract要約: 線形凸凹サドル点問題 $min_xmax_y f(x) ytopmathbfA x - g(y) について検討する。
- 参考スコア(独自算出の注目度): 84.47780064014262
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we study a convex-concave saddle-point problem $\min_x\max_y
f(x) + y^\top\mathbf{A} x - g(y)$, where $f(x)$ and $g(y)$ are smooth and
convex functions. We propose an Accelerated Primal-Dual Gradient Method for
solving this problem which (i) achieves an optimal linear convergence rate in
the strongly-convex-strongly-concave regime matching the lower complexity bound
(Zhang et al., 2021) and (ii) achieves an accelerated linear convergence rate
in the case when only one of the functions $f(x)$ and $g(y)$ is strongly convex
or even none of them are. Finally, we obtain a linearly-convergent algorithm
for the general smooth and convex-concave saddle point problem $\min_x\max_y
F(x,y)$ without requirement of strong convexity or strong concavity.
- Abstract(参考訳): 本稿では,凸凹サドル点問題 $\min_x\max_y f について検討する。
(x) + y^\top\mathbf{A} x - g
(y)$, ここで$f
(x)$ と $g
(y)$ は滑らかかつ凸関数である。
この問題を解くために,高速化されたPrimal-Dual Gradient法を提案する。
(i)低複雑性境界(zhang et al., 2021)に適合する強凸強凸配位における最適線形収束速度を達成する。
(ii)関数の1つが$fの場合、加速された線形収束率を達成する
(x)$ と $g
(y)$ は強い凸か、あるいはそれらが存在しない。
最後に、一般の滑らかで凸凸なサドル点問題$\min_x\max_y F(x,y)$に対する線形収束アルゴリズムを、強い凸性や強い凹凸性を必要とせずに得る。
関連論文リスト
- Revisiting Subgradient Method: Complexity and Convergence Beyond
Lipschitz Continuity [29.56022052936922]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究ではまず, 次進法における典型的な複雑性を, 対物関数の凸度と弱凸度に拡張する。
ステップサイズの適切な減少規則を用いて,非Lipschitz凸および弱凸目的関数に対する収束結果を提供する。
論文 参考訳(メタデータ) (2023-05-23T15:26:36Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Black-Box Min--Max Continuous Optimization Using CMA-ES with Worst-case
Ranking Approximation [22.576922942465142]
一般的なアプローチでは、$x$と$y$を同時に、あるいは交互に更新する。
既存のアプローチは、$f$がリプシッツの滑らかで、最適解を囲む凸凸が強い場合失敗する。
本稿では、共分散行列適応進化戦略を用いて、最悪の対象関数 $F(x)=max_yf(x,y)$ を最小化することを提案する。
論文 参考訳(メタデータ) (2022-04-06T08:03:39Z) - Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
この楽観的な手法は凸凹点問題の解法として人気が高まっている。
我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
論文 参考訳(メタデータ) (2022-02-19T20:31:05Z) - 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) - A Unified Single-loop Alternating Gradient Projection Algorithm for
Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。
提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
論文 参考訳(メタデータ) (2020-06-03T04:00:52Z) - Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max
Optimization [61.66927778694731]
エポッチ勾配降下法(エポッチ勾配降下法、Epoch-GD)は、2011年にHazan and Kaleによって提唱された。
Epoch-GDA が SCSC min-max 問題の双対性ギャップに対して$O (1/T) の最適レートを達成できることを示す最初の実験である。
論文 参考訳(メタデータ) (2020-02-13T02:16:57Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。