Distributed learning with compressed gradients

By Sarit Khirirat, Hamid Reza Feyzmahdavian, Mikael Johansson. 2018

92 citations recorded by the source corpus.

Asynchronous computation and gradient compression have emerged as two key techniques for achieving scalability in distributed optimization for large-scale machine learning. This paper presents a unified analysis framework for distributed gradient methods operating with staled and compressed gradients. Non-asymptotic bounds on convergence rates and information exchange are derived for several optimization algorithms. These bounds give explicit expressions for step-sizes and characterize how the amount of asynchrony and the compression accuracy affect iteration and communication complexity guarantees. Numerical results highlight convergence properties of different gradient compression algorithms and confirm that fast convergence under limited information exchange is indeed possible.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

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 Computer Networks and Communications

Citations in the corpus

Natural Compression for Distributed Deep Learning (2019, background): “1 Natural compression has a negligible variance: ω = 1/8 We identify natural compression as belonging to a large class of unbiased compression operators with bounded second moment [23, 26, 19], defined below.”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Some of the work in this direction can be found in Zhang et al. (2017); Wen et al. (2017); Wangni et al. (2017); Sa et al. (2015); Na et al. (2017); Gupta et al. (2015); Alistarh et al. (2016); Khirirat et al. (2018).”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, background): “Khirirat et al. (2018) study quantization in the deterministic setting, i.e. when the gradients ∇ f i ( x ) can be computed without noise, and show that parallel gradient descent with unbiased quantization converges to a neighborhood of the optimal solution on strongly convex functions.”
Better Theory for SGD in the Nonconvex World (2020, unknown): “…compression map Q : R d → R d , the local gradients ∇ f i ( x ) are ﬁrst compressed to Q i ( ∇ f i ( x )) , where Q i is an independent instantiation of Q sampled by machine i in each iteration, and subsequently communicated to a master node, which performs aggregation (Khirirat et al., 2018).”
Distributed learning with compressed gradient differences (2019, unknown): “Unlike in (Khirirat et al., 2018), in a noiseless regime our method converges to the exact optimum, and at a linear rate.”
Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization (2020, methodology): “Algorithm μ-strongly convex f convex f Compressed Gradient Descent (CGD (Khirirat et al., 2018)) O ( (1 + ω)Lμ log 1 ) O ( (1 + ω) )”
Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor (2020, unknown): “Compressed GD (Khirirat et al., 2018) smooth, strongly convex O ( κ ( ω + 1) log 1 / ε ) DIANA (Horv ath et al., 2019b) smooth, strongly convex O ( κ + ω + ω ) log 1 / ε Distributed SGD ( et al., 2019a) smooth, non-convex”