  We present and analyze an approach for distributed stochastic optimization
which is statistically optimal and achieves near-linear speedups (up to
logarithmic factors). Our approach allows a communication-memory tradeoff, with
either logarithmic communication but linear memory, or polynomial communication
and a corresponding polynomial reduction in required memory. This
communication-memory tradeoff is achieved through minibatch-prox iterations
(minibatch passive-aggressive updates), where a subproblem on a minibatch is
solved at each iteration. We provide a novel analysis for such a minibatch-prox
procedure which achieves the statistical optimal rate regardless of minibatch
size and smoothness, thus significantly improving on prior work.
