407. Inertial methods beyond minimizer uniqueness
Invited abstract in session MD-32: Algorithms for machine learning and inverse problems: adaptive strategies, stream Advances in large scale nonlinear optimization.
Monday, 14:30-16:00Room: 41 (building: 303A)
Authors (first author is the speaker)
| 1. | Hippolyte Labarrière
|
| Università di Genova |
Abstract
When considering a convex composite minimization problem, it is well known that momentum allows first-order methods to be accelerated both theoretically and numerically. In particular, we know that for a suitable choice of parameters inertial methods ensure fast convergence rates under additional geometry assumptions such as strong convexity. However, the improved convergence results demonstrated in the literature hold only if the function to minimize has a unique minimizer. This extra assumption is limiting, since some common functions (such as the LASSO function or $L^1$ regularized functions in general) can satisfy some growth condition without having a unique minimizer. The question then arises: is this assumption necessary to prove fast convergence properties?
We propose an approach that aims to avoid this hypothesis while still obtaining fast convergence rates. This strategy allows to extend several known convergence results in the continuous setting (i.e. for dynamical systems associated to inertial schemes). We also provide fast convergence guarantees for the iterates of FISTA (introduced by Beck and Teboulle) and V-FISTA (proposed by Beck) in a relaxed setting, showing that this uniqueness assumption is not required for inertial methods to be efficient.
Keywords
- Algorithms
Status: accepted
Back to the list of papers