pipette
ENEnglish

Accelerated primal-dual dynamics and algorithms for strongly convex-concave bilinear saddle point problems

Yun-xi Zhang, Yi-bin Xiao, Xin He

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 22 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 30 pages, 12 figures