Skip to contentSkip to filters

We use cookies for analytics.

Universal Acceleration: New Approaches to Heavy Ball Discretization

Deeksha Adil

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