Communication Complexity of Distributed Convex Learning and Optimization

By Yossi Arjevani, Ohad Shamir. 2015

225 citations recorded by the source corpus.

We study the fundamental limits to communication-efficient distributed methods for convex learning and optimization, under different assumptions on the information available to individual machines, and the types of functions considered. We identify cases where existing algorithms are already worst-case optimal, as well as cases where room for further improvement is still possible. Among other things, our results indicate that without similarity between the local objective functions (due to statistical data similarity or otherwise) many communication rounds may be required, even if the machines have unbounded computational power.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Computational Mechanics

In Optimization & Training

Citations in the corpus

Federated Optimization: Distributed Optimization Beyond the Datacenter (2015, background): “There has been an attempt at a thorough understanding of communication lower bounds [1], but the authors note that significant gaps remain in a number of settings.”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, background): “(cid:0) (cid:1) When σ = 0 our communication complexity becomes ˜ (cid:0) βµ (cid:1) and nearly matches the lower bound of ˜Ω for distinct functions by Arjevani and Shamir (2015).”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Unfortunately, these bounds are difficult to match for convex optimization as they are provided in Arjevani and Shamir (2015). Similar bounds have also been provided for the generally easier statistical estimation setting in Duchi et al. (2014); Braverman et al. (2015); Zhang et al. (2013). Feature ”
Semi-Cyclic Stochastic Gradient Descent (2019, background): “…< m/2) = 1 and P(z = 2|i ≥ m/2) = 1, with the following functions taken from Woodworth et al. (2018), which in turn is based on the constructions in Arjevani & Shamir (2015); Woodworth & Srebro (2017); Carmon et al. (2017); Woodworth & Srebro (2017): f (w, 1) = η 8 ( – 2a〈v1, w〉 + φ(〈v4K , w〉) +…”
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “For the prox case, we construct two functions inspired by previous lower bounds for round-based and finite sum optimization [3, 27].”
Distributed Mean Estimation with Limited Communication (2016, background): “This has spurred a line of work focusing on communication cost in learning [23, 4, 25, 3, 7].”
QSGD: Communication-Optimal Stochastic Gradient Descent, with Applications to Training Neural Networks (2016, background): “Recent work [4] focused on round complexity lower bounds on the number of communication rounds necessary for convex learning.”
Communication-Efficient Learning of Deep Networks from Decentralized Data (2016, background): “no better than training a model on a single client [44, 3, 46].”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, background): “Additional relevant lower bounds on the minimum number of communication rounds necessary for a given approximation quality are presented in Balcan et al. (2012) and Arjevani and Shamir (2015).”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, methodology): “Communication Complexity : We showed that A IDE nearly achieves the lower bounds proved in [2] in spe-ciﬁc cases.”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “The theoretical upper bound on number of rounds of communication improves upon DANE and other methods, and in certain settings matches the lower bound presented in [5].”
Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, background): “This problem has drawn significant attention from theoretical perspectives about its communication complexity [33, 43, 3].”
Distributed optimization with arbitrary local solvers (2015, methodology): “Indeed, for existing methods, splitting data among more machines generally increases communication requirements [1, 58], which can severely aﬀect overall runtime.”
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (2018, background): “This lower bound extends the communication complexity lower bound for totally connected communication networks from [17].”
Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks (2017, background): “Finally, note that the case of totally connected networks corresponds to a previous complexity lower bound on communications proven by [18], and is equivalent to our result for centralized algorithms with ∆ = 1 .”
Tight Complexity Bounds for Optimizing Composite Objectives (2016, background): “Our deterministic lower bounds are inspired by a lower bound on the number of rounds of communication required for optimization when each f i is held by a different machine and when iterates lie in the span of certain permitted calculations [5].”