PaperlayerView exact revision on arXiv

Source-linked AI summary

Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization

Jiaxiang Wu, Weidong Huang, Junzhou Huang, Tong Zhang

arXiv:1806.08054v1cs.CVcs.DC

TL;DR

Large-scale distributed learning can be bottlenecked by inter-node gradient communication, motivating methods that reduce communication without harming optimization. The paper proposes ECQ-SGD, which quantizes local gradients while accumulating quantization error, and reports tighter theoretical error bounds, effective experiments, and substantial training speedups.

  • Problem

    Inter-node gradient communication often bottlenecks data-parallel distributed learning, while quantization introduces error that can slow convergence or cause divergence.

  • Method

    ECQ-SGD compresses locally computed gradients with stochastic quantization and compensates them using accumulated quantization error from previous iterations.

  • Results

    ECQ-SGD has a tighter worst-case error bound than QSGD with suitable hyper-parameters, and experiments demonstrate efficacy on convex linear models and non-convex convolutional neural networks.

  • Takeaways & Limitations

    ECQ-SGD can reduce communication substantially while maintaining comparable performance and improve distributed-training efficiency.

  • Takeaways & Limitations

    The reported connection bandwidth is relatively large, so the measured speedup may differ for clusters with smaller bandwidth.

Abstract

from arXiv · show

Large-scale distributed optimization is of great importance in various applications. For data-parallel based distributed learning, the inter-node gradient communication often becomes the performance bottleneck. In this paper, we propose the error compensated quantized stochastic gradient descent algorithm to improve the training efficiency. Local gradients are quantized to reduce the communication overhead, and accumulated quantization error is utilized to speed up the convergence. Furthermore, we present theoretical analysis on the convergence behaviour, and demonstrate its advantage over competitors. Extensive experiments indicate that our algorithm can compress gradients by a factor of up to two magnitudes without performance degradation.

1. Introduction

Large-scale distributed learning uses data parallelism, but inter-node gradient communication can bottleneck training. ECQ-SGD addresses compression-induced quantization error by accumulating it across iterations and analyzing its convergence theoretically.

  • Distributed optimization is needed when massive training datasets cannot be efficiently handled by a single computation node.
  • Data-parallel systems split data across nodes, compute local gradients, and communicate them to update shared model parameters.
  • Gradient quantization and sparsification reduce communication by representing gradients with fewer bits, but compression introduces quantization error that can slow convergence or cause divergence.
  • ECQ-SGD compensates current local gradients with accumulated quantization errors from all previous iterations, extending 1Bit-SGD’s last-iteration error feedback.
  • ECQ-SGD requires a convergence analysis beyond QSGD’s variance-based argument because its quantized gradients are biased and have a larger variance bound.
  • The proposed analysis shows that error feedback suppresses quantization error’s contribution, yielding a tighter worst-case error bound and smaller sub-optimality gap than QSGD with suitable hyper-parameters.

2. Related Works

Distributed-learning research has pursued asynchronous updates, gradient quantization, and gradient sparsification to improve stochastic-gradient training efficiency and reduce communication overhead.

  • Asynchronous SGD: Asynchronous distributed SGD decouples computation from communication and has been analyzed extensively for several learning problems.
  • Gradient Quantization: 1Bit-SGD quantizes each gradient component to 1 or -1 and uses error feedback from the previous iteration.
  • Gradient Quantization: Strom’s method accumulates local gradients across iterations and transmits only components exceeding a selected threshold.
  • Gradient Quantization: Ternary gradient compression extends quantization with a stochastic function intended to preserve unbiasedness.
  • Gradient Sparsification: Gradient sparsification reduces communication by exchanging only selected gradient components, with later methods combining sparsity with correction and training techniques.

3. Preliminaries

The paper formulates convex distributed optimization in a data-parallel setting, where data and model replicas are distributed across nodes that exchange local gradients for parameter updates.

  • The optimization problem minimizes a convex differentiable function f over parameters w ∈ R^d.
  • The objective is often defined over training samples, motivating distribution when the dataset is too large for one node.
  • Data parallelism evenly distributes the full dataset across P nodes, with D_p denoting the subset stored at node p.
  • Each node initializes a consistent model replica, computes a mini-batch local gradient, broadcasts it, and uses gathered gradients to update parameters.

4. Error Compensated Quantized SGD

ECQ-SGD compresses local gradients before transmission while compensating them with accumulated quantization error. Stochastic quantization reduces communication, and the workflow aggregates quantized gradients for distributed parameter updates.

  • ECQ-SGD compensates each current local gradient with quantization error accumulated over all previous iterations before stochastic compression.
  • Each node quantizes its local gradient before broadcasting, after which a node aggregates received gradients and updates its local model replica.
  • The quantization function maps vector components to elements of a limited codebook, enabling efficient encoding.
  • The scaling factor can use the l2-norm or l∞-norm, while stochastic quantization maps scalar values to quantization points.
  • Increasing s provides more fine-grained quantization but increases communication cost.
  • With r = ⌈log2 (2s + 1)⌉ bits per component, communication costs 32 + dr bits instead of 32d bits for full-precision gradients.
  • Quantizing local gradients before transmission greatly reduces communication overhead, which is crucial when inter-node communication bottlenecks learning efficiency.

5. Theoretical Analysis

The analysis bounds ECQ-SGD’s quantization-error variance and parameter error, then compares its accumulated-error contribution with QSGD under suitable parameter conditions.

  • 5.1. Variance Bound of Quantization Error: Under bounded local-gradient second moments, QSGD provides the baseline quantization-error bound used to analyze ECQ-SGD.The assumption is that the second moment of local gradients satisfies ∥g(t)∥2^2 ≤ B for all nodes and iterations.
  • 5.1. Variance Bound of Quantization Error: ECQ-SGD’s quantization-error variance remains bounded across iterations when λ < 1.The bound is stated as independent of iteration t, so the variance does not diverge during optimization.
  • 5.2. Convergence for Quadratic Optimization: ECQ-SGD’s error bound for strongly convex quadratic optimization includes stochastic-gradient noise and quantization-error contributions.The analysis assumes bounded mini-batch stochastic noise and defines H = I − ηA in the resulting bound.
  • 5.2. Convergence for Quadratic Optimization: ECQ-SGD differs from QSGD in the final two terms of the error bound, while the other two terms are identical.This isolates the theoretical effect of accumulated error feedback in the comparison.
  • 5.2. Convergence for Quadratic Optimization: With suitable α and β, ECQ-SGD increasingly suppresses previous quantization errors’ contribution relative to QSGD as iterations progress.The multiplier ratio approaches zero for large time gaps, and error cancellation yields a tighter worst-case upper bound.

6. Experiments

Experiments evaluate ECQ-SGD on synthetic and public linear-model tasks, convolutional networks, scalability, and hyper-parameter choices. Across these settings, the method generally preserves or improves optimization performance while substantially reducing communication cost.

  • Linear Models: ECQ-SGD converges faster than QSGD and closer to full-precision SGD across Syn-256, Syn-512, and Syn-1024.Its smaller distance gap to the optimum indicates a reduced quantization-error contribution.
  • Linear Models: ECQ-SGD achieves similar test loss to 32Bit-FP in less time on Syn-20K.Encoding and decoding add overhead, but reduced gradient communication improves overall training speed.
  • Linear Models: 281.88× compression on gisette lets ECQ-SGD match full-precision SGD, exceeding TernGrad’s 34.67× compression ratio.On YearPredictionMSD, most methods converge at similar speeds and reach nearly identical final performance, except 1Bit-SGD.
  • Convolutional Neural Networks: ECQ-SGD reduces communication cost by over 80× while maintaining negligible accuracy loss and similar convergence speed to the full-precision baseline.Against QSGD under matched settings, it is consistently superior in convergence speed and classification accuracy, with similar communication reduction.
  • Performance Model: 143.5% speed-up over vanilla SGD is achieved by ECQ-SGD at 512 GPUs, reaching 66.42k versus 27.28k images per second.The experiments use a performance model and lightweight profiling of computation and communication time.
  • Parameter Study: Setting β = 1 gives the lowest error rate when α = 0.01, while α values from 0.01 to 0.1 achieve similar error rates when β = 1.Too-small α weakens error feedback; α = 0.15 violates the stability condition and does not converge.

7. Conclusion

The paper presents ECQ-SGD for large-scale distributed optimization and reports theoretical and experimental evidence of its efficacy on convex and non-convex models.

  • ECQ-SGD improves learning efficiency for large-scale distributed optimization by using error feedback to suppress quantization error in the error bound.The paper analyzes convergence theoretically and evaluates the method on convex linear models and non-convex convolutional neural networks.

8. Proof for Lemma 2

The proof analyzes accumulated quantization errors by expressing them as combinations of prior errors and bounding their second moments using independence assumptions.

  • The accumulated-error update is reorganized, and λ is defined as α2γ + (β −α)2.
  • Accumulated quantization error h(t) is represented as a linear combination of all previous quantization errors.
  • The proof takes expectations of squared l2-norms and uses the independence of quantization errors as i.i.d. random noises.
  • The variance bound from Theorem 1 is substituted into the preceding bound to control the accumulated quantization error.
  • Substituting the resulting expression into the t-th iteration’s quantization-error variance bound completes the proof.

9. Proof for Theorem 1

The theorem proof starts from ECQ-SGD’s update rule, rewrites the dynamics around the optimum, and bounds the expected squared distance using accumulated-error structure and noise independence.

  • The proof begins with the ECQ-SGD update rule for w(t+1), including stochastic noise, accumulated quantization error, and quantization error terms.
  • Subtracting the optimum w∗ and introducing H = I −ηA rewrites the update for analyzing convergence.
  • Because each accumulated quantization error combines previous errors, the proof simplifies the resulting Φ(t) expression accordingly.
  • Independence among stochastic and quantization noises yields a bound on the expected squared Euclidean distance between w(t+1) and w∗.
  • The proof concludes after establishing this distance bound.

10. Proof for Lemma 3

The proof uses the spectral lower bound on A and a learning-rate condition to control powers of I −ηA, then substitutes this inequality into Θ(t′).

  • Since A ⪰a1I and ηa1 < 1, powers of I −ηA are bounded by (1 −ηa1)t′′I.
  • Substituting the matrix-power inequality into Θ(t′) produces the desired bound for t′ < t.
  • The proof defines ν as (β −α)/(1 −ηa1).

11. Proof for Lemma 4

The proof establishes Lemma 4 by introducing the time gap and parameter relations, then substituting β = 1 −ηa1 into the reduction-ratio bound to complete the argument.

  • The proof defines the time gap as ∆t = t −t′ and sets β = 1 −ηa1 with 0 < α < β.
  • From β and α, it defines ν = β−α for the proof.
  • The proof uses 1−ηa1 ∈(0, 1) before deriving the stated intermediate result.
  • It recalls the upper bound of the reduction ratio and substitutes β = 1 −ηa1 into that bound.
  • The resulting expression completes the proof of Lemma 4.
Loading 1806.08054v1…