論文の概要: 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)$に対する線形収束アルゴリズムを、強い凸性や強い凹凸性を必要とせずに得る。
関連論文リスト
- On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms [17.227158587717934]
滑らかな凸凹型双線型結合型サドル点問題である $min_xmax_y f(x) + langle y,mathbfB xrangle - g(y)$ を再検討する。
この問題クラスに対して、第一低次複雑性境界と最適線形収束アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-11-21T22:06:25Z) - Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approach [4.895675355301809]
凸凹型双線型サドル点問題 $min_x max_y f(x) + ytop Ax - g(y)$ について検討する。
この問題の解決策は多くの機械学習タスクの中核にある。
論文 参考訳（メタデータ） (2024-10-18T16:43:10Z) - Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions [41.43895948769255]
非滑らかな非漸近公正問題のクラスを$min_x[yin Yphi(x, y) - max_zin Zpsix(x, z)]$の形で示す。
本稿では,これらの問題を解く最初の方法であるエンベロープ近似勾配SMAGを提案する。
論文 参考訳（メタデータ） (2024-05-28T20:52:46Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、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) - 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) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。