Seminar, Hosted by International Centre for Theoretical Sciences (ICTS-TIFR) Seminars
Universal Acceleration: New Approaches to Heavy Ball Discretization
Tata Institute of Fundamental Research, Mumbai (TIFR)
Abstract
Why do some optimization algorithms run so much faster than plain gradient descent? Many accelerated methods have been discovered, each with its own analysis, raising the question of whether one simple idea lies behind them all. The talk argues that there is one and that it comes from physics: a ball rolling down a hill with friction, described by the heavy ball ODE. Discretizing this equation naturally with implicit Euler nearly matches the speed of two very different accelerated methods: Nesterov's method, which uses only gradients, and Monteiro-Svaiter acceleration, which can minimize the function inside a small ball. A single phase-space picture explains both, and the same Lyapunov function proves both with a simple argument. With one small tweak both rates are matched exactly, and Nesterov's algorithm itself emerges.
Topics
- optimization algorithms
- gradient descent
- accelerated methods, search World Wide
- heavy ball ODE, search World Wide
- implicit Euler, search World Wide
- Nesterov's method, search World Wide
- Monteiro-Svaiter acceleration, search World Wide
- phase space
- Lyapunov function, search World Wide
- Discretization, search World Wide