A variational perspective on accelerated methods in optimization
Abstract
Optimization problems arise naturally in statistical machine learning and other fields concerned with data analysis. The rapid growth in the scale and complexity of modern datasets has led to a focus on gradient-based methods and also on the class of accelerated methods, first proposed by Nesterov in 1983. Accelerated methods achieve faster convergence rates than gradient methods and indeed, under certain conditions, they achieve optimal rates. However, accelerated methods are not descent methods and remain a conceptual mystery. We propose a variational, continuous-time framework for understanding accelerated methods. We provide a systematic methodology for converting accelerated higher-order methods from continuous time to discrete time. Our work illuminates a class of dynamics that may be useful for designing better algorithms for optimization.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Nov 09, 2016
- Source ID
- 10.1073/pnas.1614734113
Entities
People
- Andre Wibisono
- Ashia C. Wilson
- Michael I. Jordan
Organizations
- Office of Naval Research
- Statistics New Zealand