Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic
  Gradient Descent
  We aim to make stochastic gradient descent (SGD) adaptive to (i) the noise
$\sigma^2$ in the stochastic gradients and (ii) problem-dependent constants.
When minimizing smooth, strongly-convex functions with condition number
$\kappa$, we prove that $T$ iterations of SGD with exponentially decreasing
step-sizes and knowledge of the smoothness can achieve an $\tilde{O} \left(\exp
\left( \frac{-T}{\kappa} \right) + \frac{\sigma^2}{T} \right)$ rate, without
knowing $\sigma^2$. In order to be adaptive to the smoothness, we use a
stochastic line-search (SLS) and show (via upper and lower-bounds) that SGD
with SLS converges at the desired rate, but only to a neighbourhood of the
solution. On the other hand, we prove that SGD with an offline estimate of the
smoothness converges to the minimizer. However, its rate is slowed down
proportional to the estimation error. Next, we prove that SGD with Nesterov
acceleration and exponential step-sizes (referred to as ASGD) can achieve the
near-optimal $\tilde{O} \left(\exp \left( \frac{-T}{\sqrt{\kappa}} \right) +
\frac{\sigma^2}{T} \right)$ rate, without knowledge of $\sigma^2$. When used
with offline estimates of the smoothness and strong-convexity, ASGD still
converges to the solution, albeit at a slower rate. We empirically demonstrate
the effectiveness of exponential step-sizes coupled with a novel variant of
SLS.
