Title: A Universally Optimal Multistage Accelerated Stochastic Gradient Method,
Abstract: We study the problem of minimizing a strongly convex and smooth function when
we have noisy estimates of its gradient. We propose a novel multistage
accelerated algorithm that is universally optimal in the sense that it achieves
the optimal rate both in the deterministic and stochastic case and operates
without knowledge of noise characteristics. The algorithm consists of stages
that use a stochastic version of Nesterov's accelerated algorithm with a
specific restart and parameters selected to achieve the fastest reduction in
the bias-variance terms in the convergence rate bounds.