signSGD: compressed optimisation for non-convex problems

By Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, Anima Anandkumar. 2018

1,323 citations recorded by the source corpus.

Training large neural networks requires distributing learning across multiple workers, where the cost of communicating gradients can be a significant bottleneck. signSGD alleviates this problem by transmitting just the sign of each minibatch stochastic gradient. We prove that it can get the best of both worlds: compressed gradients and SGD-level convergence rate. signSGD can exploit mismatches between L1 and L2 geometry: when noise and curvature are much sparser than the gradients, signSGD is expected to converge at the same rate or faster than full-precision SGD. Measurements of the L1 versus L2 geometry of real networks support our theoretical claims, and we find that the momentum counterpart of signSGD is able to match the accuracy and convergence speed of Adam on deep Imagenet models. We extend our theory to the distributed setting, where the parameter server uses majority vote to aggregate gradient signs from each worker enabling 1-bit compression of worker-server communication in both directions. Using a theorem by Gauss, we prove that the non-convex convergence rate of majority vote matches that of distributed SGD. Thus, there is great promise for sign-based optimisation schemes to achieve both communication efficiency and high accuracy.

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

In Optimization & Training

Citations in the corpus

On Empirical Comparisons of Optimizers for Deep Learning (2019, background): “…(cid:15) at the common default value of 10 − 8 for Adam and 10 − 10 for RMSProp (Tieleman and Hinton, 2012; Kingma and Ba, 2015; Dozat, 2016; Balles and Hennig, 2017; Loshchilov and Hutter, 2017; Zou and Shen, 2018; Ma and Yarats, 2018; Bernstein et al., 2018; Chen et al., 2019; Zou et al., 2019).”
Large Batch Optimization for Deep Learning: Training BERT in 76 minutes (2019, methodology): “This convergence rate comparison is similar in spirit to the one obtained in (Bernstein et al., 2018).”
On the Variance of the Adaptive Learning Rate and Beyond (2019, methodology): “For SGD, we set the momentum factor as 0 .”
Distributed Fixed Point Methods with Compressed Iterates (2019, methodology): “Usually, the exchanged information is usually some compressed gradient [1,7,27] or compressed model update [4,25] in a distributed master-worker setting.”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, methodology): “Various approaches have been proposed to reduce the 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, 2”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, background): “Gradient vector sparsification is another approach analyzed in [4, 40, 39, 5, 30, 34, 9, 3, 36, 21, 32].”
FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, background): “…via quantization and compression in distributed learning has recently gained considerable attention for both master-worker [Alistarh et al., 2017, Bernstein et al., 2018, Seide et al., 2014, Smith et al., 2016] and masterless topologies [Koloskova et al., 2019, Reisizadeh et al., 2019a, Zhang et…”
Gradient Descent with Compressed Iterates (2019, methodology): “As a result, there are many algorithms designed with the goal of reducing communication in stochastic gradient methods: including SignSGD (1-bit quantization) [4], TernGrad (ternary quantization) [35], QSGD [1], DIANA (with arbitrary quantization) [11], ChocoSGD [15], and others, see e.”
Robust and Communication-Efficient Collaborative Learning (2019, methodology): “In particular, efﬁcient gradient-compression methods are provided in (Alistarh et al., 2017; Seide et al., 2014; Bernstein et al., 2018) and deployed in the distributed master-worker setting.”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “, 2018) but soon extended to biased compression (Bernstein et al., 2018) as well.”
QUOTIENT: Two-Party Secure Neural Network Training and Prediction (2019, background): “While previous work [2, 4, 9, 24, 30, 36, 46, 56] had already introduced the idea of functions Qw ,Qa to quantize weights and/or activations in the forward pass, they required the weights W or gradients G, e to be represented in floating-point in the backward pass, in order to optimize accurately.”
Natural Compression for Distributed Deep Learning (2019, background): “several state-of-the-art compressors (Karimireddy et al., 2019; Zheng et al., 2019; Bernstein et al., 2018; Vogels et al., 2019) by setting K so that the transmission amount are the same.”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, methodology): “…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 the corresponding element in x (see Bernstein et al. (2018a)).”
PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization (2019, methodology): “…the coordinates of the gradient with only their sign (Seide et al., 2014; Carlson et al., 2015; Bernstein et al., 2018, 2019; Karimireddy et al., 2019), quantizing the individual coordinates (Alistarh et al., 2017; Wen et al., 2017), and low-rank approximation of the gradient (Wang et al., 2018).”
Error Feedback Fixes SignSGD and other Gradient Compression Schemes (2019, methodology): “…faster than SGD (and in fact faster than even the without feedback algorithms) overturns previously understood intuition (cf. [Kingma and Ba, 2015, Bernstein et al., 2018]) for why SIGNSGD and other adaptive methods outperform SGD—i.e. restricting the effect of a some ‘bad’ coordinates with high…”
Don't Use Large Mini-Batches, Use Local SGD (2018, methodology): “We slightly adapt the original signSGD (Bernstein et al., 2018) to ﬁt in the local SGD framework.”
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, neutral): “A similar approach also appears in (Ghadimi & Lan, 2013; Lian et al., 2017; Yu et al., 2018; Bernstein et al., 2018).”