Closing the convergence gap of SGD without replacement
  Stochastic gradient descent without replacement sampling is widely used in
practice for model training. However, the vast majority of SGD analyses assumes
data is sampled with replacement, and when the function minimized is strongly
convex, an $\mathcal{O}\left(\frac{1}{T}\right)$ rate can be established when
SGD is run for $T$ iterations. A recent line of breakthrough works on SGD
without replacement (SGDo) established an
$\mathcal{O}\left(\frac{n}{T^2}\right)$ convergence rate when the function
minimized is strongly convex and is a sum of $n$ smooth functions, and an
$\mathcal{O}\left(\frac{1}{T^2}+\frac{n^3}{T^3}\right)$ rate for sums of
quadratics. On the other hand, the tightest known lower bound postulates an
$\Omega\left(\frac{1}{T^2}+\frac{n^2}{T^3}\right)$ rate, leaving open the
possibility of better SGDo convergence rates in the general case. In this
paper, we close this gap and show that SGD without replacement achieves a rate
of $\mathcal{O}\left(\frac{1}{T^2}+\frac{n^2}{T^3}\right)$ when the sum of the
functions is a quadratic, and offer a new lower bound of
$\Omega\left(\frac{n}{T^2}\right)$ for strongly convex functions that are sums
of smooth functions.
