Distributed stochastic optimization and learning

By Ohad Shamir, Nati Srebro. 2014

154 citations recorded by the source corpus.

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

Federated Optimization: Distributed Optimization Beyond the Datacenter (2015, background): “Works including [2, 8, 3, 9] have established basic theoretical results and developed distributed versions of existing methods, but as this is a relatively new area, many open questions remain.”
Attack of the Tails: Yes, You Really Can Backdoor Federated Learning (2020, methodology): “Each client usually runs a standard optimization algorithm such as SGD to update its own local model.”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “Rates for the stochastic optimization are derived in (Shamir & Srebro, 2014; Rabbat, 2015), under the assumption that the distributions on all nodes are equal.”
Is Local SGD Better than Minibatch SGD? (2020, methodology): “We emphasize that Table 1 lists the guarantees specialized to our setting—some of the bounds are presented under slightly weaker assumptions, or with a more detailed dependence on the noise: Stich and Karimireddy (2019) analyzes local SGD assuming not-quite-convexity(3); and Wang and Joshi (2018); D”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, background): “[48, 31, 11, 16] represent statistical convergence analysis with only one-pass over the training data which usually is not enough for the training error to converge.”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “Rates for the stochastic setting are derived in (Shamir & Srebro, 2014; Rabbat, 2015), under the assumption that the distributions on all nodes are equal.”
Local SGD Converges Fast and Communicates Little (2018, background): “[49] show statistical convergence (see also [10, 13, 33]), but the analysis restricts the algorithm to at most one pass over the data, which is in general not enough for the training error to converge.”
Communication-Efficient Learning of Deep Networks from Decentralized Data (2016, background): “In the convex setting, the problem of distributed optimization and estimation has received significant attention [4, 15, 33], and some algorithms do focus specifically on communication efficiency [45, 34, 40, 27, 43].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “ethods, which involve extending classical stochastic methods to process multiple data points at a time, have emerged as a popular paradigm for distributed machine learning in data center environments [28, 88, 96, 102, 103]. In practice, however, they have been shown to have limited ﬂexibility to ada”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “However, mini-batch versions of both SGD and coordinate descent (CD) (e.g., Dekel et al., 2012; Takáč et al., 2013; Shalev-Shwartz and Zhang, 2013b; Shamir and Srebro, 2014; Qu et al., 2015; Richtárik and Takáč, 2016; Défossez and Bach, 2017) suffer from their convergence rate degrading towards the ”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “Fundamental limitations of stochastic versions of the problem (1) in terms of runtime, communication costs and number of samples used are studied in [90].”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, methodology): “Indeed, for existing methods, splitting data among more machines generally increases the requirements for communication (Shamir & Srebro, 2014), which often has severe effects on overall runtime.”
Communication Complexity of Distributed Convex Learning and Optimization (2015, background): “data [19, 7, 10, 8], or settings where the computing architecture is different, e.”
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 Smooth and Strongly Convex Distributed Optimization in Networks (2017, background): “In several related ﬁelds, complexity lower bounds were recently investigated, including the sequential optimization of a sum of functions [15, 16], distributed optimization in ﬂat (i.e. totally connected) networks [17, 18], or distributed stochastic optimization [19].”
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants (2015, background): “And in this setting, asynchronous variants of SGD remain indispensable [2, 7, 12, 20, 27, 29].”
Distributed Multi-Task Learning (2015, background): “Such single-source distributed problems have been studied both in terms of predictive performance [13, 14] and parameter estimation [15, 16, 17].”
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox (2017, methodology): “This is the most communication-efficient method with linear speedup we are aware of (Shamir and Srebro, 2014).”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “…distributed variants of stochastic gradient descent (SGD) (Mahajan et al., 2013, Recht et al., 2011, Zinkevich et al., 2010), accelerated SGD (Shamir and Srebro, 2014), variance reduction SGD (Lee et al., 2015, Reddi et al., 2015), substantially reduce the amount of local computations but…”
On the Convergence of Local Descent Methods in Federated Learning (2019, background): “[6,11,29,38] analyze convergence from statistical point of view with only one-pass over the training data which usually is not suﬃcient for the convergence of training error.”