  Stochastic convex optimization algorithms are the most popular way to train
machine learning models on large-scale data. Scaling up the training process of
these models is crucial, but the most popular algorithm, Stochastic Gradient
Descent (SGD), is a serial method that is surprisingly hard to parallelize. In
this paper, we propose an efficient distributed stochastic optimization method
by combining adaptivity with variance reduction techniques. Our analysis yields
a linear speedup in the number of machines, constant memory footprint, and only
a logarithmic number of communication rounds. Critically, our approach is a
black-box reduction that parallelizes any serial online learning algorithm,
streamlining prior analysis and allowing us to leverage the significant
progress that has been made in designing adaptive algorithms. In particular, we
achieve optimal convergence rates without any prior knowledge of smoothness
parameters, yielding a more robust algorithm that reduces the need for
hyperparameter tuning. We implement our algorithm in the Spark distributed
framework and exhibit dramatic performance gains on large-scale logistic
regression problems.
