190. Primal-Dual Coordinate Descent for Nonconvex-Nonconcave Saddle Point Problems Under the Weak MVI Assumption
Invited abstract in session WC-6: Structured nonsmooth optimization -- Part III, stream Nonsmooth and nonconvex optimization.
Wednesday, 14:00-16:00Room: B100/7013
Authors (first author is the speaker)
| 1. | Iyad WALWIL
|
| Image, Données, Signal (IDS), Télécom Paris | |
| 2. | Olivier Fercoq
|
| Telecom Paris University |
Abstract
We introduce two novel primal-dual algorithms for tackling non-convex, non-concave, and non-smooth saddle point problems characterized by the weak Minty variational inequality (MVI). The first algorithm generalizes the well-known Primal-Dual Hybrid Gradient (PDHG) method to address this challenging problem class. The second algorithm introduces a randomly extrapolated primal-dual coordinate descent approach, extending the Stochastic Primal-Dual Hybrid Gradient (SPDHG) algorithm. Designing a coordinated algorithm to solve non-convex, non-concave 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 our second novel algorithm. Both methods are effective under a mild condition on the weak-MVI parameter, achieving convergence with constant step sizes that adapt to the problem’s structure. Numerical experiments on sigmoid and perceptron-regression problems validate our theoretical findings.
Keywords
- Computer-aided algorithm analysis
- Optimization for learning and data analysis
- Non-smooth optimization
Status: accepted
Back to the list of papers