PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Gradient Quantization for Data-Parallel SGD

Fartash Faghri, Iman Tabrizian, Ilia Markov, Dan Alistarh, Daniel Roy, Ali Ramezani-Kebrya

arXiv:2010.12460v1cs.LGstat.ML

TL;DR

Data-parallel SGD communication is costly, and fixed or heuristic gradient quantization does not account for changing gradient statistics during training. The paper introduces ALQ and AMQ, which adapt quantization using gradient-distribution statistics. The methods improve validation accuracy in low-cost communication setups and are reported to be more robust to hyperparameter choices.

  • Problem

    Data-parallel SGD must communicate potentially large gradient vectors, while existing quantization methods are often heuristic or fixed before training.

    Source: §1 · p. 1

  • Method

    ALQ and AMQ adapt gradient quantization levels using estimated gradient distributions, with processors updating compression schemes in parallel.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    Almost 2% higher validation accuracy on CIFAR-10 and 1% on ImageNet in challenging low-cost communication setups.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    The methods have convergence guarantees under standard assumptions, and experiments report superiority over nonadaptive methods on deep models and large datasets.

    Source: §6 · p. 9

    The expected normalized variance formulation assumes normalized coordinates are i.i.d. given the gradient norm.

    Source: §3 · p. 4

Abstract

from arXiv · show

Many communication-efficient variants of SGD use gradient quantization schemes. These schemes are often heuristic and fixed over the course of training. We empirically observe that the statistics of gradients of deep models change during the training. Motivated by this observation, we introduce two adaptive quantization schemes, ALQ and AMQ. In both schemes, processors update their compression schemes in parallel by efficiently computing sufficient statistics of a parametric distribution. We improve the validation accuracy by almost 2% on CIFAR-10 and 1% on ImageNet in challenging low-cost communication setups. Our adaptive methods are also significantly more robust to the choice of hyperparameters.

1 Introduction

Data-parallel SGD reduces the limits of single-node training but incurs substantial gradient-communication costs, while gradient distributions change during training. The paper introduces ALQ and AMQ, adaptive quantization methods, and reports improved validation accuracy and hyperparameter robustness over nonadaptive methods.

1 Introduction

  • Data-parallel SGD scales across multiple GPUs, but transmitting large gradient vectors creates substantial communication costs.The paper frames the goal as matching single-machine SGD performance while paying negligible communication cost.Source: §1 · p. 1
  • Gradient distributions change during training, so a quantization method optimal at the first iteration may no longer be optimal after one epoch.Figure 1 describes rapid early variance changes and further changes after learning-rate drops.Source: Figure 1 · p. 1, §1 · p. 2

1.1 Summary of contributions

  • ALQ adapts quantization levels to minimize excess variance using an estimated gradient distribution; AMQ uses exponentially spaced levels and optimizes one multiplier.Both methods update compression schemes in parallel.Source: §1 · p. 2
  • Almost 2% higher validation accuracy on CIFAR-10 and 1% on ImageNet, with greater hyperparameter robustness in challenging low-cost communication setups.The contribution summary reports these comparisons for the adaptive methods.Source: §1.1 · p. 2

1.2 Related work

  • Earlier methods include normalized-gradient QSGD [20], TernGrad [15], nonuniform NUQSGD [21], and natural compression and dithering [22].The paper focuses on unbiased, coordinate-wise gradient compression.Source: §1.2 · p. 2
  • ZipML’s optimal-level dynamic program has quadratic computational and memory cost in the number of quantized points, making it impractical for on-the-fly gradient quantization.The paper also states that a one-time scan is insufficient because stochastic-gradient distributions change during training.Source: §1.2 · p. 2

2 Preliminaries: data-parallel SGD

The preliminaries formulate constrained stochastic optimization and describe synchronous data-parallel SGD with compressed gradient exchange.

  • The objective is to minimize f over a closed, compact set Ω using unbiased stochastic gradients whose expectation equals the gradient of f.Source: §2 · p. 3
  • Data-parallel SGD uses M synchronous processors that exchange and aggregate gradients; with compression, processors compress gradients before transmission and decompress them before aggregation.Source: §2 · p. 3
  • A stochastic compression method is unbiased when its decompressed vector has expectation equal to the original vector.Source: §2 · p. 3

3 Adaptive quantization

The paper quantizes normalized gradient coordinates by random rounding between adaptive levels, then adapts those levels to reduce expected quantization variance. It presents coordinate-descent and gradient-descent approaches, an exponentially spaced AMQ variant, and a formulation that accounts for gradient norms.

3 Adaptive quantization

  • Random quantization maps each normalized coordinate to one of its two neighboring levels, with probabilities determined by its relative distance between them.The quantized vector also uses the original vector norm and coordinate signs.Source: §3 · p. 3
  • The expected normalized variance formulation assumes normalized coordinates are i.i.d. conditional on the vector norm.Source: §3 · p. 4

3.1 ALQ: Adapting individual levels using coordinate descent

  • For ALQ, each level can be updated in closed form given its neighbors, and sequential coordinate descent converges to a local minimum in fewer than 10 steps in the reported practice.The optimization problem is generally nonconvex; uniform or exponentially spaced initial levels are used.Source: §3 · p. 4, §3.1 · p. 4

3.2 Gradient descent

  • Gradient descent can update the levels, while bounding each update by half the minimum neighboring-level gap guarantees that the level ordering remains feasible.The proposed modification avoids a projection step.Source: §3.2 · p. 4

3.3 AMQ: Exponentially spaced levels

  • AMQ restricts levels to a symmetric exponential spacing and updates the single spacing multiplier by gradient descent.Source: §3.3 · p. 5

3.4 Expected variance minimization

  • Expected-variance minimization accounts for randomness in gradient norms by weighting conditional coordinate distributions according to squared gradient norms.The formulation uses observed stochastic gradients and can accommodate normal and truncated-normal distributions.Source: §3.4 · p. 5

4 Theoretical guarantees

The section develops variance and code-length bounds for adaptive quantization and uses them to establish convergence guarantees for AQSGD across several optimization settings. It also shows that average-variance bounds can apply where a worst-case bound may be costly in dimension.

4 Theoretical guarantees

  • Worst-case variance level design increases expected variance by Ω(d) compared with an optimal scheme, a prohibitive increase in deep networks.The paper quantifies this gap in Appendix E.Source: §4 · p. 5
  • AQSGD has convergence guarantees for convex, nonconvex, and momentum-based variants under standard assumptions.The analysis combines variance and code-length upper bounds.Source: §4 · pp. 5–6
  • The variance analysis covers arbitrary quantization levels, including adaptive sequences, and permits average-variance bounds on several problems.Fixed-level analyses are special cases of the theorems.Source: §4 · p. 5
  • With the maximum ratio of consecutive levels unchanged, the variance upper bound decreases as the number of quantization levels increases and matches a known Ω(d) lower bound.The bound applies to quantization under general normalization.Source: §4 · p. 6
  • Theorem 3 bounds expected communication bits for encoded quantized gradients, and AQSGD requires at most NQ bits per iteration in expectation.The stated upper bound increases monotonically with dimension d and number of levels s.Source: §4 · p. 6

5 Experimental evaluation

The evaluation compares adaptive quantizers with single- and multi-GPU baselines on CIFAR-10 and ImageNet, then examines variance, computational cost, hyperparameters, and scaling. With 3-bit quantization, adaptive methods match SuperSGD on CIFAR-10 and close the gap on ImageNet.

5 Experimental evaluation

  • With 3 bits, adaptive methods match SuperSGD on CIFAR-10 and close the gap on ImageNet; ALQ has the best overall ImageNet performance, while ALQ-N is within 0.3% on CIFAR-10.Table 1 covers validation accuracy on CIFAR-10 and ImageNet with 4 GPUs; all methods use 3 bits except SuperSGD and TRN.Source: Table 1 · p. 7, §5 · p. 7
  • Adaptive methods achieve lower average gradient variance during training; on the unquantized single-GPU trajectory, ALQ matches SuperSGD variance on ResNet-110.Figure 5 decouples quantization error from its effect on the optimization trajectory.Source: §5 · pp. 7–8, Figure 4 · p. 8, Figure 5 · p. 8
  • ImageNet training saves at least 60 of 95 hours while quantization adaptation adds at most 10 minutes total.The ALQ-specific update accounts for 0.4–0.5% of total training time.Source: §5 · p. 8

5.1 Hyperparameter studies

  • Adaptive quantization levels are more concentrated near zero at the end of ResNet-32 training on CIFAR-10.Figure 6 depicts the quantization levels at training’s end.Source: §5.1 · p. 8, Figure 6 · p. 9
  • ALQ and ALQ-N perform best across tested bucket sizes and bit counts, while adaptive multiplier methods underperform at extreme bucket sizes or 2 bits.ALQ-N is easier to implement and faster to update than ALQ; it performs well even when vectors with different norms share quantization.Source: §5.1 · p. 8
  • Non-adaptive methods are more sensitive to bucket size: NUQSGD is competitive at size 100 and 3 bits but loses accuracy as bucket size changes, while QSGDinf degrades faster than other methods.The study also reports adaptive methods scaling to 16 and 32 GPUs on CIFAR-10 with ResNet-32; Table 2 uses 3 quantization bits and bucket size 16384.Source: §5.1 · p. 9, Table 2 · p. 9

6 Conclusions

The paper introduces ALQ and AMQ for on-the-fly gradient quantization in data-parallel SGD. It establishes variance, communication, and convergence guarantees and reports empirical gains over nonadaptive methods on deep models and large datasets.

6 Conclusions

  • ALQ and AMQ adapt gradient quantization on the fly, with processors updating their compression methods in parallel using sufficient statistics of a parametric distribution.ALQ minimizes excess quantization variance given an estimated gradient distribution; AMQ optimizes exponentially spaced levels through one multiplier.Source: §6 · p. 9
  • The analysis gives tight excess-variance bounds for arbitrary quantization-level sequences under general normalization, bounds expected communication bits per iteration, and convergence guarantees under standard assumptions.The bounds apply to adaptive methods including ALQ and AMQ.Source: §6 · p. 9
  • Experiments on deep models and large datasets show ALQ and AMQ outperform nonadaptive methods.Source: §6 · p. 9

Broader impact

The broader-impact discussion identifies federated learning as a possible use for the compression schemes and cautions that their long-term effects depend on how machine learning is used. The appendix also gives distribution formulas relevant to the paper’s modeling.

Broader impact

  • The schemes may be used in federated learning, while their long-term impacts may depend on how machine learning is used in society.The discussion describes federated learning as training across multiple owners’ data without exposing that data.Source: Broader impact · pp. 9–10

A.1 Normal distribution

  • The normal-distribution appendix presents CDF and inverse-CDF definitions and notes that approximations of the formulas are available in the literature.Source: §A.1 · p. 13

A.2 Truncated normal distribution

  • For a truncated normal distribution, the appendix defines its PDF and CDF and notes that its mean and variance depend on the interval (a, b).Source: §A.2 · p. 13

B.1 Theorem 1

This section analyzes quantization schemes, including their optimization, implementation variants, and computational, variance, and encoding costs. It also bounds the expected number of nonzeros in Qℓ(v) and the entropy-based code length for transmitting h.

B.1 Theorem 1

  • The two-level objective is generally nonconvex, but a sufficient condition makes it convex and holds for a uniform distribution; the single-level objective has an optimality-condition solution.For normal and truncated normal distributions, the appendix supplies gradient expressions used in projected gradient descent.Source: §B.1 · p. 14, §B.2 · p. 15

B.3 Symmetric Levels

  • Symmetric quantization has a variance expression, and for an even normalized-coordinate PDF its expected normalized variance can be rewritten; gradients support GD and exponentially spaced levels.For single-level coordinate descent, the optimum can be found by bisection; ALQ and AMQ update rules specialize these procedures to (truncated) normal distributions.Source: §B.3 · p. 15, §B.3.1 · p. 16, §B.3.2 · p. 16

C.4 Computational complexity and scalability

  • ALQ requires O(s log(1/ϵ)) iterations, AMQ O(1/ϵ), and GD O(s/ϵ) gradient computations; optimization can run in parallel with negligible overhead and need only occur at lr_scheduler iterations.The methods’ time complexity is independent of the numbers of samples, processors, and parameters.Source: §C.4 · p. 18

D Encoding

  • Encoding represents a quantized gradient using its norm, coordinate signs, and quantized values, with Huffman coding giving expected code length between H(X) and H(X) + 1 bits.The norm is encoded using b bits, and a sign bit is sent for each nonzero quantized entry; the code-length analysis bounds expected communication bits per iteration.Source: D Encoding · pp. 18–19, G Proof of Theorem 3 (code-length bound) · p. 21

E Variance gap

  • The variance gap is Ω(d) when optimal and worst-case expected variances differ by a constant; the analysis quantifies it for one level with truncated normal density.For the one-level case, the optimal level generally differs from 1/2, the level minimizing the worst-case variance bound, depending on the truncated normal parameters.Source: E Variance gap · pp. 19–20

F Proof of Theorem 2 (variance bound)

H AQSGD for smooth nonconvex optimization

AQSGD has a convergence guarantee for smooth nonconvex objectives under the stated learning-rate, gradient, and level-update conditions. It also bounds expected communication per iteration.

I AQSGD with momentum

AQSGD with momentum replaces the standard update in the adaptive data-parallel algorithm with a unified momentum SGD update. The paper gives convex convergence guarantees and states that the momentum variant also converges to local minima for smooth general losses.

I AQSGD with momentum

  • The data-parallel momentum variant replaces Algorithm 1’s update with a unified momentum SGD update, whose heavy-ball and Nesterov cases arise at l = 0 and l = 1, respectively.Source: I AQSGD with momentum · p. 22
  • For convex objectives, AQSGDM satisfies the stated convergence bound when run for T iterations on M processors with independent stochastic gradients and K level updates.The theorem’s bound depends on the quantities shown in the passage, including the momentum parameter µ, learning rate α, and quantization variance bound ϵQ.Source: I AQSGD with momentum · pp. 22–23
  • For AQSGDM on smooth nonconvex problems, the paper guarantees convergence to a local minimum under the stated learning-rate and stochastic-gradient assumptions.Source: I AQSGD with momentum · p. 23

J Theoretical guarantees for levels with symmetry

This section gives guarantees for symmetric quantization levels, including unbiasedness under Lq normalization and a bound on expected communication cost. It also gives symbol probabilities for truncated-normal normalized coordinates.

J Theoretical guarantees for levels with symmetry

  • Under Lq normalization, symmetric-level quantization is unbiased, and the section states a variance bound.The supplied passage identifies the variance bound but does not include its full expression.Source: J Theoretical guarantees for levels… · p. 23
  • For normalized coordinates modeled by a truncated normal, Corollary 4 gives closed-form probabilities for the symmetric quantization symbols.The supplied formulas cover interior levels, the smallest positive level, and the endpoint level.Source: J Theoretical guarantees for levels… · p. 24
  • Expected communication bits per iteration are bounded by b + d(H(L) + 1), and by b + d(log2(2s + 2) + 1).Here L is defined by the symbol-probability mass function in Proposition 8.Source: J Theoretical guarantees for levels… · p. 24

K Experimental details and additional experiments

The appendix adds implementation details and experiments across CIFAR-10 and ImageNet, including a full ImageNet run, clipping tests, and timing measurements. ALQ and ALQ-N outperform QSGDinf by 1% in full-run ImageNet validation accuracy.

K Experimental details and additional experiments

  • The appendix evaluates additional algorithm variants, and similar performance of normalized and unnormalized ALQ and AMQ suggests either formulation can represent normalized gradient coordinates for the tested models and datasets.The variants include ALQ-N, AMQ-N, norm-adjusted ALQ, and gradient-descent adaptations.Source: K Experimental details and additional… · pp. 24, 26
  • Implementation models gradient distributions with weighted truncated normals and uniformly samples bucket statistics; ImageNet experiments use 350 samples.For small networks and CIFAR-10, the sample count is 20; network-wise buckets are used, with only an undersized final bucket sent in full precision.Source: K Experimental details and additional… · pp. 24–25
  • 1%: ALQ and ALQ-N outperform QSGDinf in validation accuracy on a full 600K-iteration ResNet-18 ImageNet run.Table 4 reports validation accuracy for the full run.Source: K Experimental details and additional… · p. 25, Table 4 · p. 25

K.1 Revised Experiments

  • NUQSGD has worse training loss and average variance yet better validation accuracy on CIFAR-10, a pattern not repeated on ImageNet.The authors suggest this indicates better generalization in that specific setting.Source: K Experimental details and additional… · p. 26
  • In the 32-GPU ResNet-32 CIFAR-10 experiment, ALQ performs better in expected variance and training loss but has trouble with validation loss; the authors suspect overfitting from the large total batch size.Each GPU uses batch size 128.Source: §K.1 · p. 26

K.2 Effect of Using Gradient Clipping

  • With layer-wise quantization on ResNet-8 CIFAR-10, ALQ and ALQ-N maintain better or equal accuracy than the other quantization schemes across tested bucket sizes.The clipping experiment uses c = 2.5 for TRN.Source: §K.2 · p. 27

K.3 Timing Overhead

  • Timing tests use four AWS nodes with one V100 GPU each, 1 GBit/s constrained bandwidth, and ImageNet mini-batches of 512.The tables report 32-bit and 16-bit full-precision baselines, including 0.57 s and 0.28 s per step for ResNet-18, respectively.Source: §K.3 · p. 27, Table 5 · p. 29, Table 6 · p. 30

Related papers

Loading 2010.12460v1…