Why do some optimization algorithms run so much faster than plain gradient descent? Over the years, people have discovered many “accelerated” methods, each with its own clever analysis, so it’s natural to wonder whether one simple idea lies behind them all. In this talk, I’ll argue that there is, and that it comes from physics. Picture a ball rolling down a hill with some friction. Its motion is described by the heavy ball ODE, one of the simplest equations around. If we discretize it in a very natural way, using implicit Euler, we nearly match the speed of two very different accelerated methods. The first is Nesterov’s method, which only uses gradients. The second is Monteiro–Svaiter acceleration, which can minimize the function inside a small ball. A single picture in phase space explains both, and the same Lyapunov function proves both, with a very simple argument. With one small tweak, we match both rates exactly, and Nesterov’s algorithm itself pops out.
Zoom Meeting: https://zoom.us/j/95724465033?pwd=GePuoFchDlMPCbfGEs54zLo416ayCa.1
Meeting ID: 957 2446 5033
Passcode: 203060