PaperlayerView exact revision on arXiv

Source-linked AI summary

signSGD: Compressed Optimisation for Non-Convex Problems

Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, Anima Anandkumar

arXiv:1802.04434v3cs.LGcs.DCmath.OC

TL;DR

Large-scale neural-network training is communication-intensive because workers repeatedly exchange gradients. The paper analyses sign-based compression, momentum, and distributed majority vote, finding SGD-like theoretical convergence in suitable geometries and comparable practical performance to ADAM for SIGNUM. Its conclusions are conditional on the geometry and assumptions governing gradients, noise, and curvature.

  • Problem

    Communicating every parameter gradient across distributed workers is time-intensive, motivating theory for robust gradient-compression schemes.

  • Method

    The paper analyses stochastic sign updates, signed momentum, and majority-vote aggregation of worker gradient signs for non-convex optimisation.

  • Results

    SIGNUM and ADAM have very similar performance experimentally, while both lose out to SGD by about 2% test accuracy on Imagenet.

  • Takeaways & Limitations

    Sign-based methods offer compressed communication and non-vacuous convergence guarantees in ℓ1-favourable regimes, including distributed 1-bit communication under the paper's assumptions.

  • Takeaways & Limitations

    The theory indicates that SIGNSGD can lose to SGD when R1 ≫ 1 and gradients are sparser than curvature, with curvature comparisons requiring caution because the SGD bound may be slack.

Abstract

from arXiv · show

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. The relative $\ell_1/\ell_2$ geometry of gradients, noise and curvature informs whether signSGD or SGD is theoretically better suited to a particular problem. On the practical side 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 majority vote can achieve the same reduction in variance as full precision distributed SGD. Thus, there is great promise for sign-based optimisation schemes to achieve fast communication and fast convergence. Code to reproduce experiments is to be found at https://github.com/jxbz/signSGD .

1. Introduction

The paper studies sign-based gradient compression for non-convex optimisation, arguing that SIGNSGD can retain SGD-like convergence in suitable ℓ1 geometries while reducing communication. It extends the analysis to momentum and distributed majority-vote schemes.

  • Motivation: Distributed training accelerates large neural-network training but repeatedly communicating every parameter gradient remains time-intensive.Gradient compression is proposed to reduce this communication cost.
  • SIGNSGD: SIGNSGD compresses each stochastic-gradient coordinate to its sign, discarding the exponent and mantissa of a 32-bit floating-point number.The method is introduced as a particularly simple form of gradient compression.
  • Theory: Under a particular ℓ1 geometry, SIGNSGD can achieve a theoretical convergence rate with dimension dependence similar to or better than SGD.This occurs when gradients are as dense or denser than stochasticity and curvature; experiments find gradients and noise are dense in deep learning.
  • Distributed optimisation: In distributed training, the parameter server aggregates worker gradient signs by majority vote, enabling 1-bit communication in both directions.The paper proves that the theoretical speedup matches distributed SGD under natural assumptions validated by experiments.
  • Momentum methods: SIGNUM takes the sign of momentum and is theoretically extended as a way to control bias and variance in stochastic-gradient estimates.On large Imagenet models, tuned learning rate and weight decay suffice while other SGD hyperparameter settings may be reused.

2. Related Work

Related work covers communication-efficient gradient compression, adaptive gradient methods, non-convex optimisation, and signed-gradient theory. The paper distinguishes its approach by targeting non-vacuous analysis under ℓ2 rather than ℓ∞ majorisation and by addressing distributed optimisation.

  • Gradient compression: The paper compares communication costs for gradient compression schemes when training a d-dimensional model with M workers.Table 1 is introduced as the communication-cost comparison.
  • Gradient compression: Existing 1-bit compression methods can perform well empirically, while theoretically guaranteed unbiased schemes incur variance inflation that can make SGD-style bounds vacuous.For 1-bit QSGD, the variance explosion is by a factor of d, with modern networks commonly having d > 10^8.
  • Adaptive methods: SIGNSGD is related to RPROP, RMSPROP, and ADAM, but prior sign-based work emphasised robust convergence rather than gradient compression.The paper also notes limited convincing theory for this adaptive-gradient family and discusses concerns about ADAM's original convergence proof.
  • Non-convex optimisation: Non-convex optimisation theory commonly measures convergence to stationary points because finding a global minimum is generally intractable.This motivates analysing signed methods in non-convex rather than only convex settings.
  • Signed-gradient theory: The paper is the first, to the authors' knowledge, to study stochastic signed updates under ℓ2 majorisation rather than the ℓ∞ majorisation used in earlier analyses.Its non-stochastic SIGNSGD interpretation is classical steepest descent with the ℓ∞ norm.
  • Experimental benchmarks: Experiments use Resnet-20 on CIFAR-10 and Resnet-50 v2 on Imagenet.These benchmarks provide the paper's neural-network evaluation settings.

3. Convergence Analysis of SIGNSGD

SIGNSGD is analyzed for non-convex optimization under coordinate-wise smoothness and variance assumptions that capture heterogeneous curvature and stochasticity. Its convergence and comparison with SGD depend on the relative ℓ1 geometry of gradients, noise, and curvature, while large batches and dense gradients support favorable theoretical and empirical behavior.

  • Assumptions: SIGNSGD is analyzed under fine-grained smoothness and coordinate-bounded variance assumptions tailored to signed updates.These assumptions are compatible with standard SGD assumptions through suitable norm definitions.
  • Proof strategy: The convergence proof controls sign errors through each component’s signal-to-noise ratio, with mistakes becoming less consequential near stationary points under large batches.The proof directly handles the bias introduced by applying the nonlinear sign operation.
  • Convergence rate: Large-batch training reaches N stochastic gradient calls in O(√N) iterations rather than O(N), reducing iteration and distributed communication rounds.The theorem’s iteration complexity is measured alongside the cumulative number of stochastic gradient calls N.
  • Geometry-dependent comparison: SIGNSGD’s rate depends on density ratios involving gradient, stochasticity, and curvature, favoring SIGNSGD when gradients are not sparser than noise or curvature.When curvature and stochasticity are denser than gradients, the comparison suggests SGD is better suited; when neither is much denser, SIGNSGD may match or outperform SGD.
  • Geometry-dependent comparison: Dense gradients with sparse, highly noisy coordinates can favor SIGNSGD because sign updates equalize coordinate influence instead of letting sparse noise dominate SGD dynamics.The theory summarizes this regime as greater robustness to large stochasticity concentrated on a sparse set of coordinates.

4. Majority Rule: the Power of Democracy in the Multi-Worker Setting

The distributed scheme uses majority vote over workers’ gradient signs, enabling 1-bit communication in both directions. Under symmetric unimodal noise, the theory gives improved convergence through variance reduction, while skewed or bimodal noise limits the guarantee.

  • Distributed majority vote: Majority vote lets the parameter server aggregate workers’ gradient signs and return a 1-bit decision to every worker.This makes worker-server communication 1-bit in both directions.
  • Convergence theory: Under natural assumptions, majority vote converges at least as fast as SIGNSGD.Theorem 2 states this as its general distributed convergence result.
  • Convergence theory: Under unimodal, symmetric stochastic-gradient noise, majority vote achieves an improved convergence rate through variance reduction.The analysis uses Gauss’ tail bound together with binomial concentration for the workers’ votes.
  • Scope of the guarantee: The variance-reduction benefit is expected mainly when the signal-to-noise ratio satisfies S > 1; the general bound does not express this speedup compactly.When S < 1, additional workers need not provide the same improvement.
  • Scope of the guarantee: Symmetry and unimodality matter because highly skewed or bimodal noise can make more workers increase sign-error probability rather than reduce it.The central limit theorem may make these assumptions increasingly reasonable as minibatch size grows.

5. Extending the Theory to SIGNUM

The paper extends sign-based optimization to SIGNUM, which updates using the sign of a momentum estimate. Its theory frames momentum as a bias-variance tradeoff, while experiments show performance comparable to ADAM on the reported tasks.

  • Method: SIGNUM is obtained by taking the sign of momentum rather than the raw stochastic gradient.The method is incorporated into the paper’s theoretical framework and analyzed in Theorem 3.
  • Implementation: SIGNUM requires a warmup period of C(β) iterations before momentum bias settles; for β = 0.9, C = 54.During warmup, updates use the sign of the stochastic gradient.
  • Proof strategy: The theoretical proof uses a general master lemma that supports the paper’s convergence results for sign-based methods.The authors identify this proof as the paper’s greatest technical challenge.
  • Theory: Momentum can reduce estimator variance through longer averaging, but stale gradients increase curvature-induced bias.The theory describes this as a tradeoff controlled by β.
  • Experiments: SIGNUM’s performance rivals ADAM’s across the reported Imagenet and CIFAR-10 experiments.The Imagenet figure reports approximately equal test performance to ADAM, with about a 2% gap to well-tuned SGD with weight decay.

6. Discussion

The discussion connects majority vote to ternary compression and evaluates SIGNUM against ADAM and SGD. It also proposes measurable gradient-density geometry as a guide for architecture search.

  • Extensions: Majority vote can be extended to ternary quantization by allowing uncertain workers to abstain and returning zero when quorum is not reached.The authors state that this extension should fit their theory.
  • Empirical comparison: SIGNUM and ADAM show similar performance in the experiments, while both trail SGD by about 2% test accuracy on Imagenet.The discussion relates this gap to unresolved regularization issues and possible noise-level effects.
  • Generalization: The authors suggest that adding Gaussian noise to SIGNUM updates might improve generalization, while retaining communication efficiency in distributed training.Workers can generate the same noise after sharing a random seed.
  • Architecture search: The Welford algorithm measures the ratio between noise and gradient density, which the authors propose using to identify architectures suited to gradient compression.This provides an experimental way to assess one geometric aspect of the theory.

7. Conclusion

The paper presents a unified framework for sign-based stochastic non-convex optimization, covering signed momentum and multi-worker majority vote. It concludes that majority vote merits further distributed-systems benchmarking.

  • Conclusion: The framework provides non-vacuous bounds and identifies ℓ1 geometries in which sign-based gradient compression can succeed.It also covers signed-momentum methods such as SIGNUM and distributed schemes such as majority vote.
  • Future work: The majority-vote algorithm remains to be benchmarked with distributed-systems practitioners despite its theoretical promise for 1-bit bidirectional communication.The authors identify this benchmarking as their next step.

A. Further experimental results

The experiments examine when sign-based methods are robust to sparse noise, how dense neural-network gradients are, and how SIGNUM compares with ADAM and SGD on CIFAR-10.

  • Toy problem: SIGNSGD converges faster than SGD in a quadratic toy problem with extremely sparse Gaussian noise affecting one gradient component.Learning rates were tuned separately to 0.001 for SGD and 0.01 for SIGNSGD; results average 50 repeats.
  • Gradient density: Full gradients were remarkably dense across the evaluated datasets and neural-network architectures.The measurements use Xavier-initialised parameter points and a full pass over each dataset.
  • CIFAR-10 experiments: SIGNUM closely resembles ADAM on CIFAR-10 ResNet-20 validation and test plots, with little difference in final test performance.Hyperparameters were tuned using a separate validation split.
  • CIFAR-10 experiments: All algorithms approach the 91.25% baseline, while SIGNSGD and ADAM remain stable across a broader learning-rate range than SGD.SGD has a larger region of very high-scoring configurations, whereas its heatmap shifts with increasing momentum because of an implementation coupling.

C. Large and small batch SGD

The SGD analysis compares large- and small-batch regimes using cumulative stochastic-gradient calls, finding the same convergence rate in that measure while large batches reduce iterations and communication rounds.

  • Comparison of batch regimes: Large- and small-batch SGD have exactly the same convergence rate when measured by the number N of stochastic-gradient calls.The large-batch case uses N = O(K2), while the small-batch case uses N = O(K).
  • Comparison of batch regimes: Large-batch SGD is theoretically preferred because it reaches N gradient calls in fewer iterations than small-batch SGD.Fewer iterations can imply lower wall-clock time when large batches are parallelised.
  • Convergence analysis: The SGD convergence theorem sets a constant learning rate and mini-batch size under the stated assumptions.The theorem applies to K iterations under Assumptions 1 to 3.
  • Convergence analysis: The proof bounds one-step objective improvement, conditions on the previous iterate, and telescopes the resulting expectation over iterations.The analysis treats both large- and small-batch cases through these proof steps.

D. Proving the convergence rate of distributed SIGNSGD with majority vote

The distributed analysis uses majority vote to aggregate workers’ sign bits, proving single-worker-level convergence generally and improved rates under unimodal symmetric noise.

  • Theorem setup: The theorem sets the learning rate and mini-batch size for each worker independently of the iteration step.The distributed convergence theorem is stated under Assumptions 1 to 3.
  • General guarantee: Majority vote with M workers converges at least as fast as single-worker SIGNSGD under the baseline assumptions.The argument treats workers’ sign estimates as repeated noisy observations of the true gradient sign.
  • Improved-rate regime: The improved distributed result requires noise in each gradient component to be unimodal and symmetric about its mean.The text warns that very skewed or bimodal distributions can have failure probability above one half, limiting the benefit of additional workers.
  • Improved-rate regime: Under unimodal symmetric gradient noise, majority vote converges at an improved rate.The proof uses a bound on single-worker sign failure probability and a binomial model for correct worker signs.
  • Failure-probability analysis: The analysis defines the signal-to-noise ratio as S = |g_i|/σ_i and controls sign errors through Cantelli’s inequality.When S > 1, the single-worker failure probability is below one half, enabling majority-vote improvement.

E. General recipes for the convergence of approximate sign gradient methods

The paper develops a general convergence framework for approximate sign-gradient updates, then uses it to analyze majority voting and momentum-based SIGNUM.

  • Applications: The same machinery handles SIGNUM and majority voting by verifying the required approximation condition for each algorithm.This establishes a shared proof route for the two sign-based schemes.
  • General framework: A master lemma analyzes updates of the form x_{k+1} = x_k − δ_k sign(v_k), where v_k may depend on the full algorithmic history.The framework requires v_k to be measurable and square-integrable.
  • Proof strategy: The proof strategy bounds expected objective improvement at each step and sums these bounds across iterations.The argument conditions on the current iterate before taking expectations over stochastic-gradient randomness.
  • Proof strategy: An estimation-to-testing reduction provides a sufficient condition for the approximate-sign convergence lemma.The reduction uses Markov’s inequality to relate expected approximation error to sign-testing error.
  • General framework: The framework permits poor gradient approximation at rare iterates, provided the approximation improves in expectation according to the stated rate condition.This feature enables analysis of momentum and supports the convergence result for SIGNUM.

F. Analysis for SIGNUM

The analysis establishes SIGNUM’s convergence through stochastic-gradient error control, a gradient-approximation lemma, and curvature-based bounds. The proof also accounts for a warmup period and increasing minibatch sizes.

  • Stochastic-gradient error: Lemma F.1 bounds the cumulative error of stochastic gradients under fixed weighting coefficients.Its proof verifies the martingale definition and then applies martingale-difference properties to obtain the variance bound.
  • Stochastic-gradient error: A martingale argument treats dependent stochastic-gradient errors as if they were independent for variance analysis.The dependence arises because later errors depend on earlier iterates, but the lemma establishes a variance bound through martingale difference properties.
  • Gradient approximation: Lemma F.2 provides a gradient-approximation guarantee for SIGNUM after the warmup threshold C.The stated algorithm uses v_k = ˜m_k and follows the parameter choices from Theorem 3 for C ≤ k ≤ K.
  • Curvature analysis: The curvature analysis decomposes the Hessian as H = H+ − H− and applies Taylor expansion along sign vectors.The proof uses the positive- and negative-semidefinite parts of H to bound the change in the gradient under a sign-vector step.
  • Convergence proof: Theorem 3 follows by substituting the gradient-approximation bound into a prior convergence lemma and accounting for increasing minibatch sizes.The analysis notes that the increasing schedule yields N_K = O(K^2), while the prescribed learning-rate and minibatch schedules govern the post-warmup proof.
Loading 1802.04434v3…