418. Difference-of-convex algorithm with weakly convex functions: improved splitting technique and equivalence with proximal gradient descent
Invited abstract in session MB-8: Systematic and computer-aided analyses I: Analyses of proximal splittings methods & friends, stream Systematic and computer-aided analyses of optimization algorithms.
Monday, 10:30-12:30Room: B100/7007
Authors (first author is the speaker)
| 1. | Teodor Rotaru
|
| Electrical Engineering, KU Leuven | |
| 2. | Panagiotis Patrinos
|
| Electrical Engineering, KU Leuven | |
| 3. | François Glineur
|
| ICTEAM/INMA & CORE, Université catholique de Louvain (UCLouvain) |
Abstract
The difference-of-convex algorithm (DCA) is a classical, simple parameter-free algorithm designed to minimize a difference of convex functions. We present a comprehensive convergence analysis of DCA extended to handle the case where the second, subtracted function is weakly convex.
Assuming at least one function is smooth, we evaluate the algorithm's performance using the norm of the best (sub)gradient residual or the best (prox-)gradient mapping. Six distinct regimes are identified, two of them corresponding to the previously studied standard difference-of-convex setting. Our simplified proofs are based on deriving six distinct descent lemmas, inspired by solving the associated performance estimation problems (PEP). These establish sublinear convergence rates, which are provably tight for three of the regimes. We also conjecture the exact behavior across any number of iterations in all regimes, informed by extensive numerical simulations.
We also propose a new method to improve the best worst-case convergence rate based on a curvature-shifting technique, which can potentially transform the subtracted function into a weakly convex one. Additionally, we investigate the underexplored equivalence between proximal gradient descent (PGD) and DCA iterations, showing that PGD convergence rates can be derived from DCA rates, where in particular the weakly convex subtracted function enables to deduce rates for large PGD stepsizes.
Keywords
- Computer-aided algorithm analysis
- First-order optimization
- Complexity and efficiency of algorithms
Status: accepted
Back to the list of papers