{"ID":2872432,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.08258","arxiv_id":"2509.08258","title":"Nesterov acceleration for strongly convex-strongly concave bilinear saddle point problems: discrete and continuous-time approaches","abstract":"In this paper, we study a bilinear saddle point problem of the form $\\min_{x}\\max_{y} F(x) + \\langle Ax, y \\rangle - G(y)$, where $F$ and $G$ are $μ_F$- and $μ_G$-strongly convex functions, respectively. By incorporating Nesterov acceleration for strongly convex optimization, we first propose an optimal first-order discrete primal-dual gradient algorithm. We show that it achieves the optimal convergence rate $\\mathcal{O}\\left(\\left(1 - \\min\\left\\{\\sqrt{\\frac{μ_F}{L_F}}, \\sqrt{\\frac{μ_G}{L_G}}\\right\\}\\right)^k\\right)$ for both the primal-dual gap and the iterative, where $L_F$ and $L_G$ denote the smoothness constants of $F$ and $G$, respectively. We further develop a continuous-time accelerated primal-dual dynamical system with constant damping. Using the Lyapunov analysis method, we establish the existence and uniqueness of a global solution, as well as the linear convergence rate $\\mathcal{O}(e^{-\\min\\{\\sqrt{μ_F},\\sqrt{μ_G}\\}t})$. Notably, when $A = 0$, our methods recover the classical Nesterov accelerated methods for strongly convex unconstrained problems in both discrete and continuous-time. Numerical experiments are presented to support the theoretical convergence rates.","short_abstract":"In this paper, we study a bilinear saddle point problem of the form $\\min_{x}\\max_{y} F(x) + \\langle Ax, y \\rangle - G(y)$, where $F$ and $G$ are $μ_F$- and $μ_G$-strongly convex functions, respectively. By incorporating Nesterov acceleration for strongly convex optimization, we first propose an optimal first-order dis...","url_abs":"https://arxiv.org/abs/2509.08258","url_pdf":"https://arxiv.org/pdf/2509.08258v1","authors":"[\"Xin He\",\"Ya-Ping Fang\"]","published":"2025-09-10T03:32:14Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}