Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Prox
This addresses efficiency challenges in distributed machine learning, offering a flexible tradeoff for large-scale optimization, though it appears incremental as it builds on prior minibatch-prox approaches.
The paper tackles distributed stochastic optimization by proposing a method that achieves statistical optimality and near-linear speedups, with a communication-memory tradeoff allowing either logarithmic communication with linear memory or polynomial communication with reduced memory.
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.