Nesterov acceleration for strongly convex-strongly concave bilinear saddle point problems: discrete and continuous-time approaches
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914031196962816 |
|---|---|
| author | He, Xin Fang, Ya-Ping |
| author_facet | He, Xin Fang, Ya-Ping |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_08258 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nesterov acceleration for strongly convex-strongly concave bilinear saddle point problems: discrete and continuous-time approaches He, Xin Fang, Ya-Ping Optimization and Control 90C25, 49M27, 34D05, 37N40 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. |
| title | Nesterov acceleration for strongly convex-strongly concave bilinear saddle point problems: discrete and continuous-time approaches |
| topic | Optimization and Control 90C25, 49M27, 34D05, 37N40 |
| url | https://arxiv.org/abs/2509.08258 |