Accelerated primal-dual dynamics and algorithms for strongly convex-concave bilinear saddle point problems
In the authors' words
In this paper, we develop accelerated primal-dual dynamics and algorithms for strongly convex-concave saddle point problems with bilinear coupling. Combining strongly convex Nesterov dynamics with scaled heavy-ball dynamics, we propose a second-order primal-dual dynamical system with constant damping and derive an associated algorithm by time discretization and coefficient adjustment. Under suitable conditions on the continuous scaling function and the discrete scaling sequence , we establish primal-dual gap estimates of in continuous time and in discrete time. The maximal admissible growth rates of these scales recover the exponential and linear convergence rates of strongly convex Nesterov methods in continuous and discrete time, respectively. We also prove convergence of the primal-dual trajectory and sequence, even when the dual solution is nonunique. Saddle residual estimates of and hold under globally Lipschitz gradients in continuous time and with a possibly nonsmooth dual potential in discrete time. Numerical experiments illustrate the theoretical results and the performance of the proposed methods.
Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 30 pages, 12 figures