TY - GEN
T1 - Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling
AU - Kovalev, Dmitry
AU - Gasnikov, Alexander
AU - Richtarik, Peter
N1 - KAUST Repository Item: Exported on 2023-07-10
Acknowledgements: The work of Alexander Gasnikov was supported by a grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000000D730321P5Q0002) and the agreement with the Ivannikov Institute for System Programming of the Russian Academy of Sciences dated November 2, 2021 No. 70-2021-00142.
PY - 2022/1/1
Y1 - 2022/1/1
N2 - In this paper we study the convex-concave saddle-point problem minx maxy f(x)+ yTAx- g(y), where f(x) and g(y) are smooth and convex functions. We propose an Accelerated Primal-Dual Gradient Method (APDG) for solving this problem, achieving (i) an optimal linear convergence rate in the strongly-convex-strongly-concave regime, matching the lower complexity bound (Zhang et al., 2021), and (ii) 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 minx maxy F(x, y) without the requirement of strong convexity or strong concavity.
AB - In this paper we study the convex-concave saddle-point problem minx maxy f(x)+ yTAx- g(y), where f(x) and g(y) are smooth and convex functions. We propose an Accelerated Primal-Dual Gradient Method (APDG) for solving this problem, achieving (i) an optimal linear convergence rate in the strongly-convex-strongly-concave regime, matching the lower complexity bound (Zhang et al., 2021), and (ii) 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 minx maxy F(x, y) without the requirement of strong convexity or strong concavity.
UR - http://hdl.handle.net/10754/692832
UR - https://proceedings.neurips.cc/paper_files/paper/2022/hash/883f66687a521536c505f9b2fbdcbf1e-Abstract-Conference.html
UR - http://www.scopus.com/inward/record.url?scp=85163193959&partnerID=8YFLogxK
M3 - Conference contribution
SN - 9781713871088
BT - 36th Conference on Neural Information Processing Systems, NeurIPS 2022
PB - Neural information processing systems foundation
ER -