353. Searching for optimal per-coordinate stepsizes with multidimensional backtracking
Invited abstract in session MB-5: Optimization and machine learning I, stream Optimization for machine learning.
Monday, 10:30-12:30Room: B100/4013
Authors (first author is the speaker)
| 1. | Frederik Kunstner
|
| INRIA | |
| 2. | Victor Sanches Portella
|
| Institute of Mathematics and Statistics, University of São Paulo | |
| 3. | Nick Harvey
|
| Computer Science, University of British Columbia | |
| 4. | Mark Schmidt
|
| UBC |
Abstract
The backtracking line-search is an e↵ective technique to automatically tune the step-size in smooth optimization. It guarantees similar performance to using the theoretically optimal step-size. Many approaches have been developed to instead tune per-coordinate step-sizes, also known as diagonal preconditioners, but none of the existing methods are provably competitive with the optimal per-coordinate step-sizes. We propose multidimensional backtracking, an extension of the backtracking line-search to find good diagonal preconditioners for smooth convex problems. Our key insight is that the gradient with respect to the step-sizes, also known as hypergradients, yields separating hyperplanes that let us search for good preconditioners using cutting-plane methods. As blackbox cutting-plane approaches like the ellipsoid method are computationally prohibitive, we develop an ecient algorithm tailored to our setting. Multidimensional backtracking is provably competitive with the best diagonal preconditioner and requires no manual tuning.
Keywords
- First-order optimization
Status: accepted
Back to the list of papers