Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems
Published in International Conference on Machine Learning (ICML), 2023
We study a primal-dual (PD) method for saddle point problems (SPP) that replaces the standard proximal step with a linear approximation of the primal function, leading to a Linearized Primal-Dual (LPD) method. For convex-strongly concave SPPs, we find that LPD has a suboptimal dependence on the Lipschitz constant of the primal function.
To address this, we integrate features of Accelerated Gradient Descent into LPD, resulting in the Accelerated Linearized Primal-Dual (ALPD) method, which achieves optimal gradient complexity for SPPs with semi-linear coupling functions. For more general nonlinear coupling functions, we introduce an inexact ALPD method, which maintains optimal primal gradient evaluations while significantly reducing the complexity of the coupling term.
We validate our theoretical results through numerical experiments on QCQPs with different rules of regularizations.
Recommended citation: M Khalafi, D Boob - International conference on machine learning, 2023
Download Paper