SGD: General Analysis and Improved Rates

Understand

We propose a general yet simple theorem describing the convergence of SGD under the arbitrary sampling paradigm.

• Our theorem describes the convergence of an infinite array of variants of SGD, each of which is associated with a specific probability law governing the data selection rule used to form mini-batches.
• This is the first time such an analysis is performed, and most of our variants of SGD were never explicitly considered in the literature before.
• Our analysis relies on the recently introduced notion of expected smoothness and does not rely on a uniform bound on the variance of the stochastic gradients.