Fast primal-dual methods for convex-concave bilinear saddle point problems: continuous-time dynamics and discrete algorithms

Abstract

This paper studies Nesterov accelerated methods for continuously differentiable convex-concave bilinear saddle point problems. For the continuous-time model, we analyze a second-order primal-dual dynamical system with vanishing damping $\hat{I}\pm /t$, where $\hat{I}\pm \ge 3$. Under the merely convex-concave setting, we prove convergence of the primal-dual trajectory to a saddle point. In the noncritical regime $\hat{I}\pm >3$, we further obtain the improved rate $o(1/t^2)$ for the primal-dual gap and $o(1/t)$ for the velocity, and, under an additional Lipschitz gradient assumption, $o(1/t)$ for the stationarity residual. We then derive a structure-preserving finite-difference discretization, which leads to a fast primal-dual algorithm with Nesterov extrapolation. For a general accelerated parameter sequence $t_k$ satisfying $t_{k+1}^2-t_k^2\le \ddot{I}t_{k+1}$ with $\ddot{I}\in (0,1]$, we prove the $O(1/t_k^2)$ convergence rate for the primal-dual gap and convergence of the generated sequence. In the noncritical case $\ddot{I}<1$, we further establish the improved rate $o(1/t_k^2)$ for the gap and $o(1/t_k)$ for the stationarity residual. These results provide continuous-discrete acceleration methods for bilinear saddle point problems in the merely convex-concave setting.

25 pages, 4 figures