A Linear Speedup Analysis of Distributed Deep Learning with Sparse and Quantized Communication

By Peng Jiang, Gagan Agrawal. 2018

205 citations recorded by the source corpus.

Subfields: Efficiency & Compression, Federated & Distributed Learning

How researchers see this paper

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

In Efficiency & Compression

In Federated & Distributed Learning

Citations in the corpus

Federated Optimization in Heterogeneous Networks (2018, background): “the premise that each local solver is a copy of the same stochastic process (due to the IID assumption). This line of reasoning does not apply to the heterogeneous setting. Although some recent works [38, 34, 12, 15] have explored convergence guarantees in statistically heterogeneous settings, they ”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, background): “…communication overhead of distributed SGD, such as quantization (Seide et al., 2014; Strom, 2015; Wen et al., 2017; Alistarh et al., 2016; Bernstein et al., 2018; Karimireddy et al., 2019; Zheng et al., 2019) and sparsification (Aji and Heafield, 2017; Stich et al., 2018; Jiang and Agrawal, 2018).”
Gradient Descent with Compressed Iterates (2019, background): “Another line of work focused on local stochastic gradient methods that communicate only intermittently and average models, such as Local SGD [20, 28, 31, 32] and Federated Averaging [22], and combinations of such methods and update quantization (where the sum of gradients over an epoch is quantized)”
$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “Previous works mostly focus on a centralized scenario where the compression is assumed to be unbiased [Jiang and Agrawal, 2018, Shen et al., 2018, Wangni et al., 2018, Wen et al., 2017, Zhang et al., 2017].”
Natural Compression for Distributed Deep Learning (2019, background): “Typically, problem (1) is solved by distributed stochastic gradient descent (SGD) [38], which works as follows: i) given model xk maintained on each node, machine i computes a random vector gi(xk) whose mean is∇fi(xk) (i.e., a stochastic gradient), ii) all stochastic gradients gi(x k) are sent to a ”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, methodology): “Note that here unlike many existing work (Alistarh et al., 2017; Jiang & Agrawal, 2018), we do not require the compression to be unbiased, which means we do not assume • 1-Bit Quantization: Compress a vector x into x (cid:107) sign ( x ) , where sign ( x ) is a vector whose element take the sign of…”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, methodology): “…first time that a distributed momentum SGD method for non-convex stochastic optimization is proven to possess the same linear speedup property (with communication reduction) as distributed SGD (without momentum) in (Lian et al., 2017; Yu et al., 2018; Wang & Joshi, 2018a; Jiang & Agrawal, 2018).”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “ed model will be biased towards devices with favorable network conditions. Theoretically, while several recent works have investigated convergence guarantees of variants of federated learning methods [56, 123, 131, 132], few analyses allow for low participation [e.g., 65, 106], or study directly the”
Tighter Theory for Local SGD on Identical and Heterogeneous Data (2019, background): “We note that analysis for nonconvex objectives has been carried out in a few recent works (Zhou and Cong, 2018; Wang and Joshi, 2018; Jiang and Agrawal, 2018), but our focus in this work is on convex objectives and hence they were not included in Table 1.”
Stochastic Controlled Averaging for Federated Learning with Communication Compression (2023, background): “…stringent conditions or assumptions that are not necessarily valid in practice, including but not restricted to: (Bounded Gradient Dissimilarity (Jiang and Agrawal, 2018; Li and Li, 2023; Gao et al., 2021)) (Bounded Compression Error (Haddadpour et al., 2021)) (Averaged Contraction (Alistarh et…”
1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed (2021, unknown): “The compression is mostly assumed to be unbiased (Wangni et al., 2018; Shen et al., 2018; Zhang et al., 2017; Wen et al., 2017; Jiang and Agrawal, 2018).”
Better Communication Complexity for Local SGD (2019, background): “While local SGD has been popular among practitioners for a long time [5, 12], its theoretical understanding has remained elusive until very recently [1, 9, 14, 15, 16, 17] (see Table 1).”
Federated Learning under Arbitrary Communication Patterns (2021, methodology): “A line of work has focused on analyzing local SGD under identical data distribution on clients (Zhou & Cong, 2017; Jiang & Agrawal, 2018; Wang & Joshi, 2018; Stich, 2018; Stich & Karimireddy, 2019; Haddadpour et al., 2019; Khaled et al., 2019b; Wang & Joshi, 2018).”
Model Pruning Enables Efficient Federated Learning on Edge Devices (2019, background): “Under some conditions, this convergence can be bounded asymptotically by O ( 1 √ NK ) + O ( 1 K ) , achieving linear speedup1 with the number of clients N [31], [45] for sufficiently large K.”
Communication-Efficient and Distributed Learning Over Wireless Networks: Principles and Applications (2020, unknown): “Gradient sparsification with a fixed degree of sparsity approach was analyzed in [88].”
On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization (2019, background): “By Theorem 1, we have E[hθ(y(k);y(k−1))− hθ(y(k)∗ ;y(k−1))] ≤ c1 ( T N ) 1+δ 2 E[hθ(y(k−1);y(k−1))− hθ(y(k)∗ ;y(k−1))] + c2√ NT (12) 6For non-convex optimization, local SGD is more widely known as periodic model averaging or parallel restarted SGD since each worker periodically restarts its independ”
Model Compression and Hardware Acceleration for Neural Networks: A Comprehensive Survey (2020, background): “In addition, for distributed learning, sparsifying, and quantizing the gradients can also be combined to reduce the communication cost without impacting the convergence rate [248].”
Distilling On-Device Intelligence at the Network Edge (2019, methodology): “To this end, one can adaptively quantize the model parameters to be exchanged by adjusting their arithmetic precision, or exchanging only a fraction of the model parameters, i.e., sparse parameter averaging that is known to achieve the same training convergence rate as periodic averaging [8].”
Clustered Federated Learning: Model-Agnostic Distributed Multitask Optimization Under Privacy Constraints (2019, background): “Different authors have investigated the convergence properties of Federated Learning in congruent iid and non-iid scenarios: [12],[13],[14] and [15] perform an empirical investigation, [8], [16], [17] and [9] prove convergence guarantees.”