Unified Analysis of Stochastic Gradient Methods for Composite Convex and
  Smooth Optimization
  We present a unified theorem for the convergence analysis of stochastic
gradient algorithms for minimizing a smooth and convex loss plus a convex
regularizer. We do this by extending the unified analysis of Gorbunov, Hanzely
\& Richt\'arik (2020) and dropping the requirement that the loss function be
strongly convex. Instead, we only rely on convexity of the loss function. Our
unified analysis applies to a host of existing algorithms such as proximal SGD,
variance reduced methods, quantization and some coordinate descent type
methods. For the variance reduced methods, we recover the best known
convergence rates as special cases. For proximal SGD, the quantization and
coordinate type methods, we uncover new state-of-the-art convergence rates. Our
analysis also includes any form of sampling and minibatching. As such, we are
able to determine the minibatch size that optimizes the total complexity of
variance reduced methods. We showcase this by obtaining a simple formula for
the optimal minibatch size of two variance reduced methods (\textit{L-SVRG} and
\textit{SAGA}). This optimal minibatch size not only improves the theoretical
total complexity of the methods but also improves their convergence in
practice, as we show in several experiments.
