Primal-Dual Coordinate Descent for Nonconvex-Nonconcave Saddle Point Problems Under the Weak MVI Assumption
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_ | 1866911012169449472 |
|---|---|
| author | Walwil, Iyad Fercoq, Olivier |
| author_facet | Walwil, Iyad Fercoq, Olivier |
| contents | We introduce two novel primal-dual algorithms for addressing nonconvex, nonconcave, and nonsmooth saddle point problems characterized by the weak Minty Variational Inequality (MVI). The first algorithm, Nonconvex-Nonconcave Primal-Dual Hybrid Gradient (NC-PDHG), extends the well-known Primal-Dual Hybrid Gradient (PDHG) method to this challenging problem class. The second algorithm, Nonconvex-Nonconcave Stochastic Primal-Dual Hybrid Gradient (NC-SPDHG), incorporates a randomly extrapolated primal-dual coordinate descent approach, extending the Stochastic Primal-Dual Hybrid Gradient (SPDHG) algorithm.
To our knowledge, designing a coordinate-based algorithm to solve nonconvex-nonconcave saddle point problems is unprecedented, and proving its convergence posed significant difficulties. This challenge motivated us to utilize PEPit, a Python-based tool for computer-assisted worst-case analysis of first-order optimization methods. By integrating PEPit with automated Lyapunov function techniques, we successfully derived the NC-SPDHG algorithm.
Both methods are effective under a mild condition on the weak MVI parameter, achieving convergence with constant step sizes that adapt to the structure of the problem. Numerical experiments on logistic regression with squared loss and perceptron-regression problems validate our theoretical findings and show their efficiency compared to existing state-of-the-art algorithms, where linear convergence is observed. Additionally, we conduct a convex-concave least-squares experiment to show that NC-SPDHG performs competitively with SAGA, a leading algorithm in the smooth convex setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_15597 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Primal-Dual Coordinate Descent for Nonconvex-Nonconcave Saddle Point Problems Under the Weak MVI Assumption Walwil, Iyad Fercoq, Olivier Optimization and Control 90C26, 68W20, 68V05, 65K15 We introduce two novel primal-dual algorithms for addressing nonconvex, nonconcave, and nonsmooth saddle point problems characterized by the weak Minty Variational Inequality (MVI). The first algorithm, Nonconvex-Nonconcave Primal-Dual Hybrid Gradient (NC-PDHG), extends the well-known Primal-Dual Hybrid Gradient (PDHG) method to this challenging problem class. The second algorithm, Nonconvex-Nonconcave Stochastic Primal-Dual Hybrid Gradient (NC-SPDHG), incorporates a randomly extrapolated primal-dual coordinate descent approach, extending the Stochastic Primal-Dual Hybrid Gradient (SPDHG) algorithm. To our knowledge, designing a coordinate-based algorithm to solve nonconvex-nonconcave saddle point problems is unprecedented, and proving its convergence posed significant difficulties. This challenge motivated us to utilize PEPit, a Python-based tool for computer-assisted worst-case analysis of first-order optimization methods. By integrating PEPit with automated Lyapunov function techniques, we successfully derived the NC-SPDHG algorithm. Both methods are effective under a mild condition on the weak MVI parameter, achieving convergence with constant step sizes that adapt to the structure of the problem. Numerical experiments on logistic regression with squared loss and perceptron-regression problems validate our theoretical findings and show their efficiency compared to existing state-of-the-art algorithms, where linear convergence is observed. Additionally, we conduct a convex-concave least-squares experiment to show that NC-SPDHG performs competitively with SAGA, a leading algorithm in the smooth convex setting. |
| title | Primal-Dual Coordinate Descent for Nonconvex-Nonconcave Saddle Point Problems Under the Weak MVI Assumption |
| topic | Optimization and Control 90C26, 68W20, 68V05, 65K15 |
| url | https://arxiv.org/abs/2506.15597 |