A Lecture on SGD and Markov Chains

based on a paper by Dieuleveut, Durmus, and Bach (2020), Dec 2024

To access the document, please click [PDF]

Image credits

Dall-E2. The exact prompt was “A conceptual visualization of Stochastic Gradient Descent (SGD) and Markov Chains in a simple, mathematical style”.

Synopsis

In this short lecture, we will review the paper in the title. After presenting the framework, we will prove the starting statement, and just briefly comment the other ones, which have very long proofs. To conclude, we will overview the Richardson-Romberg extrapolation method, which is one direct application of the results, and the ideas behind the deeper theorems. Emphasis is on intuition and quick understanding. References are to a minimum. Computations, when performed, are explicit. Throughout, we omit the full expressions of the theorems, but specify when these are available in the original publication.