Natural Compression for Distributed Deep Learning

Motivation

• Dense gradient communication is a major training bottleneck, and more aggressive compression trades fewer bits per iteration for greater variance and potentially more communication rounds.The introduction identifies communication as taking much more time than computation in many practical applications.Source: §1 · pp. 2–3

Summary of Contributions

• Natural compression (Cnat) randomly rounds each float to a signed power of two, adds at most 1/8 variance, and reduces communicated bits 3.56× for float32 and 5.82× for float64.The small variance is presented as leaving theoretical convergence results of SGD-type methods essentially unaffected.Source: §1 · p. 3
• Natural dithering is exponentially better than standard dithering, while compositions with sparsification can yield an order-of-magnitude improvement at a fixed communication budget.Figure 1 compares compressors by communication in bits and second moment ω + 1 for a gradient of size d = 10^6.Source: §1 · p. 3, Figure 1 · p. 3
• Natural compression is computation-free apart from randomization and supplies integer-compatible sign and exponent outputs for SwitchML in-network aggregation.The paper describes it as the first compression mechanism provably able to operate in that framework.Source: §1 · p. 4
• For bidirectional distributed SGD, the paper gives convergence rates for smooth non-convex objectives with linear speed-up in worker count, and proves compression can reduce total training time.The paper states that communication savings from carefully designed compression more than compensate for the increased number of iterations.Source: §1 · p. 4
• Experiments show that Cnat reduces training time, does not hurt convergence as worker counts grow, and can combine with other compressors to reduce communication rounds without noticeable convergence impact.The combined methods are reported to reach the same quality solution.Source: §1 · p. 4

2. Natural Compression

• Applied element-wise, natural compression unbiasedly rounds each nonzero value to one of the neighboring signed powers of two and leaves powers of two unchanged.Zero maps to zero; the rounding probabilities are chosen so that E[Cnat(t)] = t.Source: §2 · p. 5
• Natural compression has variance 1/8 and satisfies E||Cnat(x)||^2 ≤ (1 + 1/8)||x||^2 for every input x.The paper notes that this bounded-second-moment class is compatible with several optimization algorithms and includes most compression operators used in practice.Source: §2 · p. 6
• The analogous unbiased rounding to neighboring integers, Cint, has no finite second moment and is therefore incompatible with existing optimization methods.Source: §2 · p. 6
• Binary32 natural compression uses 9 bits per value, reducing communication 3.56×; binary64 uses 12 bits, reducing communication 5.82×.Apart from randomization, the operation can be implemented by dispensing with the mantissa and retaining the sign and exponent.Source: §2 · pp. 6–7
• Composing Cnat after C ∈ B(ω) yields an operator in B(9ω/8 + 1/8), allowing natural compression to serve as a final compression step.The paper also describes post-compression for operators outside B(ω), such as TopK sparsification (Alistarh et al., 2018).Source: §2 · p. 7

Natural Dithering

• General dithering uses a p-norm and s ordered levels to randomly round each normalized entry magnitude between adjacent levels while preserving its expectation.The definition also allows an operator C in B(ω).Source: §3 · p. 8
• Natural dithering is a special case using a binary geometric partition of the unit interval; for INA, applying C_nat yields powers-of-two outputs and adds a 9/8 second-moment factor.The natural operator ignores mantissas, and its norm can also be compressed; multiplying by a naturally compressed norm amounts to summing exponents.Source: §3 · p. 8
• When general dithering compresses gradients, each worker communicates the norm, vector of signs, and an efficient encoding of the effective levels for each entry.Natural dithering can communicate a compressed norm and exponents only.Source: §3 · p. 8
• For fixed s, natural dithering has O(2^(s-1)/s) times smaller variance than standard dithering.Theorem 8 states this comparison for D_p,s^nat and D_p,s^sta.Source: §3 · p. 9

• Because existing compatible stochastic-gradient methods do not support master-node compression, the authors propose bidirectionally compressed vanilla distributed SGD, complementary to concurrent methods by Tang et al. (2019) and Zheng et al. (2019).Natural compression and dithering can also be used within those other algorithms.Source: §4 · p. 9
• The analysis assumes repeated access to unbiased stochastic gradients with bounded variance, node similarity, and an L-smooth objective.Source: §4 · p. 9
• Theorem 9 assumes a fixed stepsize η ∈ (0, 2/βL), with α and β as in (4), and selects a uniformly random index a from {0, 1, …, T−1}.Source: §4 · p. 9
• For equal data across nodes (ζ = 0), α = (ωM+1)(ωW+1)σ2/n and β = (ωM+1)(1+ωW/n); without compression, α + εβ = σ2/n + ε.The iteration complexity is T(ωM, ωW) := 2L(f(x0)−f(x⋆))ε^-2(α+εβ).Source: §4 · p. 10
• Compression’s communication savings can outweigh its iteration slowdown, while standard sparsification may worsen overall running time; natural methods raise the minimal speedup over their non-natural versions.The worker-side slowdown from compression decreases as the number of nodes n increases.Source: §4 · p. 10

Experiments

• For 200 aggregated 100MB tensors, the microbenchmark varied worker counts from 4 to 8; stochastic-rounding overhead at the aggregator was identified as a bottleneck.Cnat deterministic showed similar performance, indicating the stochastic rounding step accounted for the observed performance difference.Source: §5 · p. 11
• ∼26% lower training time for ResNet110 and 66% for AlexNet came with no final-accuracy loss, while QSGD reduced ResNet110 training time by only 9% in the same setup (Alistarh et al., 2017; He et al., 2016).Training loss was unaffected by compression; combining Cnat with other compression operators also showed no convergence effect.Source: §5 · p. 11
• 84% less data was transferred with natural compression, and communication-intensive VGG and AlexNet benefited more from quantization than computation-intensive GoogleNet, Inception, and ResNet.The amount of transferred data grew linearly over training time.Source: §5 · p. 12
• Cnat incurred no accuracy loss on 16-worker distributed tasks and did not negatively affect weak scaling for ResNet50 ImageNet training.The reported weak-scaling experiment used ResNet50 on ImageNet.Source: §5 · p. 12
• TopK-Cnat saves 37.5% of TopK communication by compressing selected gradient values, and achieves better test accuracy than plain TopK at the same sparsity while communicating fewer bits.Indices cannot be compressed, limiting savings; applying Cnat to values yields a communicated data ratio of K/4 + K = 0.625 * (2K).Source: §5 · pp. 12–13
• 30x speedup over NCCL was achieved by integrating Cnat with OmniReduce on 8 machines when tensors had 1% non-zero elements.OmniReduce reduces index-transmission overhead by partitioning data into blocks and sending only non-zero blocks.Source: Figure 12 · p. 13, §5 · p. 13
• At equal communication budgets, TopK-Cnat outperforms sign-based compressors and matches PowerSGD, using SGD hyperparameters without the extra tuning sign-based methods require (Karimireddy et al., 2019; Zheng et al., 2019; Bernstein et al., 2018; Vogels et al., 2019).The comparison sets K to match transmission amounts across methods.Source: Table 3 · p. 12, §5 · p. 13

6. Conclusions and Future Work

• The paper proposes two new compression operators: natural compression Cnat and natural dithering nat.Source: §6 · p. 13
• The compression operators save communication per iteration with minimal or unnoticeable increase in communication count versus non-natural variants, resulting in faster overall running time.The comparison includes non-natural variants such as Dp,s.Source: §6 · p. 13
• A general theory for SGD with arbitrary bi-directional compression enables analysis of the proposed operators.Source: §6 · p. 13
• Experiments corroborate the theoretical predictions and show speedups on a variety of tasks.Source: §6 · p. 13
• Combining the compression techniques with other compression techniques leads to a theoretically superior method.Source: §6 · p. 13
• Future work will examine very large-scale experiments and uses of the techniques beyond centralized parallel optimization and beyond SGD.Source: §6 · p. 13

Appendix

• The appendix provides a table of contents and figure references for DenseNet40 and AlexNet at batch sizes 256, 512, and 1024.Source: Appendix · p. 18, Figure 13 · p. 20, Figure 14 · p. 20

A.1. Convergence Tests on CIFAR 10

• On CIFAR 10, Cnat achieved significant speed-up without accuracy loss versus the default NCCL baseline, with greater benefit for communication-intensive AlexNet than smaller ResNets and DenseNet40.The networks were trained for the same number of epochs without hyperparameter tuning.Source: §A.1 · p. 20
• At the same number of levels, natural dithering had dramatically smaller empirical variance than standard dithering, as predicted by Theorem 8.The experiments used vectors with different norms and tested p = 1, p = 2, and p = ∞.Source: §A.1 · p. 21
• When standard dithering used u = 2s−1 levels—an exponential advantage—its empirical variance was essentially the same as natural dithering’s.This comparison tests the levels needed by standard dithering to match natural dithering’s variance.Source: §A.1 · pp. 21–22
• At large s, standard dithering converges to the identity with zero variance, while natural dithering retains a variance floor of 1/8; standard dithering can outperform only in a practically meaningless regime.For p = ∞ and s = 32, the empirical variance of both methods was small, and standard dithering’s could be lower while natural dithering’s was already negligible.Source: §A.1 · p. 22

A.2.4. COMPRESSING GRADIENTS

• With optimization-generated gradients instead of synthetic Gaussian vectors, the compression experiments produced essentially the same results.The gradients came from training several deep learning models.Source: §A.2.4 · p. 23

A.3. Different Compression Operators

• With natural compression, test accuracy and training loss were nearly unchanged by epoch while transmitted bits fell substantially, sometimes with better results.The comparison covered no compression, random sparsification, and random dithering on MNIST and CIFAR10; results averaged three runs. Figure 19 covers CIFAR10 with VGG11, and Figure 20 covers MNIST with a two-layer fully connected network.Source: §A.3 · p. 23, Figure 19 · p. 24, Figure 20 · p. 25

Appendix B. Experimental setup

• The experiments use the standard CNN benchmark and compare natural compression with no compression and deterministic rounding; hyperparameter settings are summarized in Appendix B.1.2.The uncompressed variation provides the baseline for In-Network Aggregation, while deterministic rounding illustrates the sampling overhead of natural compression.Source: Appendix B · p. 25
• The implementation places natural compression in Gloo as a drop-in replacement for ring all-reduce, integrates it with Horovod and TensorFlow, and follows SwitchML’s In-Network Aggregation strategy.The strategy is chosen to fit the capabilities of modern hardware that supports basic integer arithmetic, simple logical operations, and limited storage.Source: Appendix B · pp. 25–26
• Workers send chunks of compressed gradients to aggregators, which wait for every worker, restore and aggregate values, recompress the aggregate, and multicast it back.Each aggregator processes a fixed-length array of gradient values at a time.Source: Appendix B · p. 26
• The In-Network Aggregation prototype is a server-based DPDK program; a complete P4 switch implementation is left to future work.The paper notes that programmable switches support the needed bit shifting, masking, and random-bit generation operations.Source: Appendix B · p. 26
• AVX2 optimization compresses 32-bit floats to an 8-bit representation, while aggregators use 64-bit integers and clip exponents to −50 ∼10.The 8-bit representation uses one sign bit, six exponent bits for the clipped range, and one bit for zeros; the paper reports that observed exponents stay within range (Figure 21).Source: Appendix B · p. 26
• 10 ∼15% overhead in random-number generation accompanies stochastic rounding, while deterministic rounding gives nearly the same training curve, neutralizing speedup through slower convergence from biased compression.The paper includes results without stochastic rounding as a reference.Source: Appendix B · p. 26
• Experiments use eight worker machines, each with one NVIDIA P100 GPU, and balance workers with eight aggregators—or four aggregators for four workers—over 10 GbE interfaces.Worker machines have dual Intel Xeon E5-2630 v4 CPUs and 128 GB RAM; aggregators use dual Intel Xeon Silver 4108 CPUs. CPU frequency scaling is disabled, and compressed-gradient chunks are uniformly distributed across aggregators.Source: Appendix B · p. 26

B.1.1. DENSENET HYPERPARAMETERS:

• DenseNet40 (k = 12) was trained for 300 epochs with vanilla SGD and weight decay 10−4, following Huang et al. (2017).The learning rate began at 0.1 and was reduced by a factor of 10 at epochs 150 and 225.Source: §B.1.1 · pp. 26–27

B.1.2. ALEXNET HYPERPARAMETERS:

• AlexNet was trained for 200 epochs with SGD momentum 0.9 across minibatch sizes 256, 512, and 1024.The learning rate started at 0.001 and was reduced by a factor of 10 every 30 epochs.Source: §B.1.2 · p. 27

B.1.3. RESNET HYPERPARAMETERS FOR CIFAR10:

• CIFAR-10 ResNets used vanilla SGD, weight decay 10−4, and 64K iterations, with minibatch size 128 for ResNet 20 and 256 for the others.The learning rate began at 0.1 and was multiplied by 0.1 at 32K and 48K iterations, following He et al. (2016).Source: §B.1.3 · p. 27

B.1.4. RESNET HYPERPARAMETERS FOR IMAGENET:

• ImageNet ResNet50 trained for 50 epochs on 8 and 16 workers with SGD momentum 0.875 and a cosine learning-rate schedule starting at 0.256.Training used 8-epoch linear warmup, weight decay 1/32768 excluded from Batch Norm trainable parameters, and label smoothing 0.1.Source: §B.1.4 · p. 27

B.1.5. NCF HYPERPARAMETERS

• Neural Collaborative Filtering trained for 20 epochs on 8 workers with ADAM (Kingma and Ba, 2015), learning rate 4.5 × 10−3, and global batch size 220.The model has approximately 32 million parameters, uses β1 = 0.25, β2 = 0.5, and dropout 0.5, and applies no weight decay.Source: §B.1.5 · p. 27

C.1. Proof of Theorem 3

• The proof establishes a second-moment factor of 9/8 for natural compression and verifies its unbiasedness.The proof reduces the bound to an optimization problem whose optimal objective value is 9/8.Source: §C.1 · p. 28

C.2. Proof of Theorem 4

• Unbiased rounding to the nearest integer cannot have a finite quantization parameter, because the required bound diverges as x approaches zero.For x in (0, 1), the proof obtains ω ≥ 1/x and takes x → 0+.Source: §C.2 · p. 29

C.3. Proof of Theorem 5

• The proof of Theorem 5 uses the tower property of expectation to analyze the composite compression operator C1 ◦ C2, including its second moment.The proof then concludes its argument for the composite operator.Source: §C.3 · p. 29

C.4. Proof of Theorem 7

• Natural dithering uses 4 levels rather than standard dithering’s 8 to achieve the same variance, an exponential improvement in compression.For s = 4, natural dithering rounds to 0, 2^-3, 2^-2, 2^-1, and 1; standard dithering rounds to 0, 1/8, …, 7/8, and 1.Source: §C.4 · p. 30

C.5. Proof of Theorem 8

• The proof of Theorem 8 uses a connection between natural dithering and standard dithering, with normalized coordinates rounded to levels from 0 to 1 in steps of 1/2^(s−1).The passage points to Figure 22 for a visualization of this connection.Source: §C.5 · p. 30

C.6. Natural Compression and Dithering Allow for Fast Aggregation

• Natural compression and natural dithering support fast aggregation through integer updates, with natural compression reducing master-side aggregation to summing exponents.The passages also describe in-network aggregation and computation-free conversion between floating-point and integer formats.Source: §C.6 · p. 31

D.2. Assumptions and Definitions

• The distributed SGD analysis assumes bounded stochastic-gradient variance, bounded inter-worker gradient variance, and an L-smooth objective.The text says the similarity assumption is automatically satisfied when every worker has the whole dataset, and DIANA can be used instead of SGD to avoid it.Source: §D.2 · pp. 31–32

D.3. Description of Algorithm 1

• Algorithm 1 has workers compress and send stochastic gradients to a master, which aggregates, compresses, broadcasts updates, and has workers update their local parameters.An all-to-all setup makes the master compression operator the identity; in-network aggregation instead uses a switch that current implementations can only use to add integers.Source: §D.3 · p. 32

D.4. Three Lemmas Needed for the Proof of Theorem 9

• The convergence analysis first states three lemmas to bound the variance of the compressed gradient estimator, with master-side compression adding variance.The text contrasts this use of stochasticity to reduce communication with SGD’s use of stochasticity to speed computation.Source: §D.4 · p. 33

Proof

• Lemma 13 addresses global compression variance when workers and the master compress updates and workers’ stochastic gradients are unbiased estimates.The passage introduces parameters involving master and worker compression variances and inter-worker gradient variance.Source: Proof · p. 34

D.5. Proof of Theorem 9

• Theorem 9’s proof applies L-smoothness and Lemma 13 to derive a convergence bound.The proof passage states that a step size can be chosen to satisfy condition (16) for every ε > 0, but the supplied excerpt does not include the full bound.Source: §D.5 · p. 35

D.6. A Different Stepsize Rule for Theorem 9

• The rate generalizes the no-compression rate of Ghadimi and Lan (2013), has better compression-operator dependence than the linear rate of Jiang and Agrawal (2018)7, and scales linearly with worker count n.With per-worker mini-batches of size b and full-data access, σ² becomes σ²/b and ζ² becomes 0, yielding linear speedup in mini-batch size, as in Jiang and Agrawal (2018).Source: §D.6 · pp. 35–36

D.7. SGD with Bidirectional Compression: Four Models

• With equal data across nodes, compression slowdown lies in (ω_M + 1, (ω_M + 1)(ω_W + 1)]; worker-side slowdown decreases as n grows, and communication savings can yield overall speedup.The upper bound is reached at n = 1 or as ε → 0, while the lower bound is approached as n → ∞.Source: §D.7 · p. 36

D.7.1. MODEL 1

• Table 5 reports 2.81× speedup for Cnat at θ = 1 and 3.16× at θ = 0 for distributed-SGD runtime, defined as iteration count times bits sent per iteration.The table assumes binary 32-bit floating-point representation, bi-directional compression using C, and equal communication speed from worker to master and back. Speedup was calculated for d = 10^6, p = 2 for dithering, optimal s for dithering, and q = 0.1d for sparsification.Source: Table 5 · p. 37

D.7.2. MODEL 2

• Model 2 treats worker-to-master communication as the bottleneck and uses no master-side compression (C_M is the identity, ω_M = 0).The assumption is that the master communicates much faster than the workers.Source: §D.7.2 · p. 37

D.7.3. MODEL 3

• For Model 3, the paper uses Model 1’s communication assumptions and takes SGD with Cnat as the baseline because it is simple to analyze and supports in-network aggregation.For in-network aggregation, compression is also useful from master to workers because the master works with integers; Cnat allows translation to floats without extra cost.Source: §D.7.3 · p. 37

D.7.4. MODEL 4

• Model 4 repeats Model 3’s comparison under Model 2’s communication assumptions.Source: §D.7.4 · p. 37

D.7.5. COMMUNICATION STRATEGIES USED IN TABLES 1, 5, 7, 8

• Without compression or with Cnat, each worker sends a possibly dense d-dimensional vector with 32 or 9 bits per scalar, respectively; with sparsification Sq, it sends q sparse entries at full 32- or limited 9-bit precision, plus q(log2(d) + 1) bits for nonzero positions when q is small.Source: §D.7.5 · p. 38

D.8. Sparsification - Formal Definition

• Random sparsification selects exactly q coordinates uniformly; when q = d, it is the identity operator and its variance is zero.The operator is defined for integer 1 ≤ q ≤ d.Source: §D.8 · p. 39

Appendix E. Limitations and Extensions

• Natural quantization can be combined with biased methods such as TopK sparsification (Aji and Heafield, 2017), retaining convergence guarantees and yielding superior practical performance in experiments.Source: Appendix E · pp. 39–40