Theory of accelerated methods

In this talk I will show how to derive the fastest coordinate descent method [1] and the fastest stochastic gradient descent method [2], both from the linear-coupling framework [3]. I will relate them to linear system solving, conjugate gradient method, the Chebyshev approximation theory, and raise several open questions at the end. No prior knowledge is required on first-order methods.

[1] Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling.
[2] The First Direct Acceleration of Stochastic Gradient Methods.
[3] Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent.