Abstract
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.
| Original language | English (US) |
|---|---|
| Title of host publication | 36th Conference on Neural Information Processing Systems, NeurIPS 2022 |
| Publisher | Neural information processing systems foundation |
| ISBN (Print) | 9781713871088 |
| State | Published - Jan 1 2022 |
Bibliographical note
KAUST Repository Item: Exported on 2023-07-10Acknowledgements: 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.