Theory of accelerated methods

Computer Science/Discrete Mathematics Seminar II
Topic:Theory of accelerated methods
Speaker:Zeyuan Allen-Zhu
Affiliation:Member, School of Mathematics
Date:Tuesday, November 22
Time/Room:10:30am - 12:30pm/S-101
Video Link:

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.