Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox

By Jialei Wang, Weiran Wang, Nati Srebro. 2017

55 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Don't Use Large Mini-Batches, Use Local SGD (2018, background): “[29, 30], require iid distributed data, this is not required in the federated setting.”
COLA: Decentralized Linear Learning (2018, background): “Our results are free of the restrictive assumptions made by stochastic methods [Zhang et al., 2015, Wang et al., 2017], which requires i.i.d. data distribution over all devices.”
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “[25] Jialei Wang, Weiran Wang, and Nathan Srebro.”
On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization (2017, neutral): “Similar averaging approaches have been proposed in the literature, see Hazan and Kale [2014], Johnson and Zhang [2013], Smith et al. [2016], Zhang et al. [2016], Loshchilov and Hutter [2016], Chen et al. [2016], Wang et al. [2017].”
Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, background): “The existing works on distributed machine learning mainly focus on two directions: 1) how to design communication efficient algorithms to reduce the round of communications among workers [43, 31, 13, 27, 42], and 2) about how to use large mini-batches without compromising the convergence speed [21, ”
Distributed Stochastic Optimization via Adaptive SGD (2018, methodology): “Algorithms that use Newton’s method typically make the assumption that D is a distribution over quadratic losses [20, 22, 16, 21], and leverage the fact that the expected Hessian is constant to compute a Newton step in parallel.”
Gradient Diversity Empowers Distributed Learning (2017, methodology): “In [28, 45], mini-batch proximal algorithms are presented that require solving a regularized optimization algorithm on a sampled batch as a subroutine.”
Efficient Meta Learning via Minibatch Proximal Update (2019, methodology): “As a building block of our approach, the minibatch proximal update method has been studied in different contexts including online passive-aggressive learning [28], asynchronous stochastic gradient optimization [29], and communication-efficient distributed learning [30], to name a few.”
A Distributed Hierarchical SGD Algorithm with Sparse Global Reduction (2019, background): “Such phenomena have been observed for similar type of algorithms by many others in the community as well, see Zhang et al. [2016], Lin et al.”
Gradient Diversity: a Key Ingredient for Scalable Distributed Learning (2017, methodology): “Mini-batch proximal algorithms are studied by Li et al. (2014), Wang et al. (2017), Wang and Srebro (2017), and these algorithms require solving a regularized optimization algorithm on a sampled batch as a subroutine.”
Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate (2019, methodology): “Compared with SAA, SA is more efficient due to the low computational cost per iteration, and has received significant research interests from optimization and machine learning communities (Zhang, 2004; Duchi et al., 2011; Ge et al., 2015; Wang et al., 2017).”
The Effect of Network Width on the Performance of Large-batch Training (2018, unknown): “Mini-batch proximal algorithms are presented in [37].”