301. Inertial methods beyond minimizer uniqueness
Invited abstract in session TD-7: Accelerated methods in modern optimization, stream Optimization for Inverse Problems and Machine Learning.
Thursday, 14:10 - 15:50Room: M:I
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. Since the seminal works of Polyak in 1964 and Nesterov in 1983, inertial methods have been widely studied and 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
- Optimization for learning and data analysis
Status: accepted
Back to the list of papers