Source-linked AI summary
Natural Compression for Distributed Deep Learning
Samuel Horvath, Chen-Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, Peter Richtarik
TL;DR
Distributed deep learning is bottlenecked by communication of dense gradient vectors, while stronger compression trades lower per-iteration cost for higher variance and more communication rounds. This paper introduces natural compression and natural dithering, achieving substantial communication savings with minimal convergence impact and faster overall running time.
Problem
Communication of dense gradient vectors is a key bottleneck, while more aggressive compression increases variance and can require more communication rounds.
Method
The paper introduces natural compression, which unbiasedly rounds each value to a neighboring signed power of two, and extends the idea to natural dithering.
Results
The operators provide substantial communication savings with minimal or unnoticeable increases in communication rounds, and experiments observe speedups across varied tasks.
Takeaways & Limitations
Natural compression and natural dithering can be used alone or combined with existing techniques to reduce communication and achieve faster overall running time.
Takeaways & Limitations
The analysis assumes node similarity and an L-smooth objective, and does not explore very large-scale experiments or uses beyond centralized parallel optimization and SGD.
Abstract
from arXiv · showhide
Modern deep learning models are often trained in parallel over a collection of distributed machines to reduce training time. In such settings, communication of model updates among machines becomes a significant performance bottleneck and various lossy update compression techniques have been proposed to alleviate this problem. In this work, we introduce a new, simple yet theoretically and practically effective compression technique: natural compression (NC). Our technique is applied individually to all entries of the to-be-compressed update vector and works by randomized rounding to the nearest (negative or positive) power of two, which can be computed in a "natural" way by ignoring the mantissa. We show that compared to no compression, NC increases the second moment of the compressed vector by not more than the tiny factor $\frac{9}{8}$, which means that the effect of NC on the convergence speed of popular training algorithms, such as distributed SGD, is negligible. However, the communications savings enabled by NC are substantial, leading to $3$-$4\times$ improvement in overall theoretical running time. For applications requiring more aggressive compression, we generalize NC to natural dithering, which we prove is exponentially better than the common random dithering technique. Our compression operators can be used on their own or in combination with existing operators for a more aggressive combined effect and offer new state-of-the-art both in theory and practice.
1. Introduction
Distributed deep learning makes communication of dense gradient vectors a major bottleneck, motivating compression methods that balance transmitted bits against variance and convergence speed. The paper introduces natural compression and natural dithering as simple operators designed to improve this trade-off.
- Motivation: Distributed SGD exchanges dense d-dimensional gradients between workers and a master, making communication costly for modern models.The aggregated gradient is also broadcast back to workers in parameter-server implementations.
- Motivation: More aggressive compression reduces communication per iteration but increases variance, slows convergence, and may require more communication rounds.The resulting trade-off is between per-iteration communication cost and the number of communication rounds.
- Contributions: Natural compression rounds each float to a positive or negative power of 2 using an unbiased randomized scheme.The paper also develops natural dithering as a more aggressive compression operator.
- Contributions: Natural compression has variance at most 1/8, while float32 and float64 communication are reduced by 3.56× and 5.82×, respectively.The paper links the small variance to essentially unaffected theoretical convergence of SGD-type methods.
- Contributions: Natural dithering is exponentially better than standard random dithering and can provide an order of magnitude improvement when composed with sparsification.These comparisons are stated for fixed communication budgets and are illustrated in Figure 1.
- Contributions: Natural compression is computation-free apart from randomization because it trims the floating-point mantissa and may increase the exponent by one.This gives the operator compatibility with binary floating-point types.
2. Natural Compression
Natural compression independently rounds each nonzero input to one of its neighboring signed powers of two, choosing probabilities that preserve unbiasedness. Its variance is bounded by 1/8 while its floating-point representation substantially reduces communication, and composition preserves controlled variance growth.
- Definition and properties: Natural compression applies element-wise randomized logarithmic rounding to neighboring signed powers of two and leaves zero unchanged.For example, -2.75 is rounded to -4 or -2, while 0.75 is rounded to 1/2 or 1.
- Definition and properties: The rounding probabilities make Cnat(t) an unbiased estimator of t for every input.The operator leaves values that are already integer powers of 2 unchanged.
- Definition and properties: Cnat belongs to B(1/8), so its variance parameter is at most 1/8 under the paper’s compression-operator definition.The class B(ω) controls the second moment by E||C(x)||^2 ≤ (ω + 1)||x||^2.
- Implementation and communication: In binary floating-point, the operator can be implemented by discarding the mantissa while retaining the sign and exponent, or incrementing the exponent by one.The randomization selects between the two neighboring powers of two.
- Implementation and communication: Natural compression represents binary32 outputs with 9 bits and binary64 outputs with 12 bits, yielding 3.56× and 5.82× less communication.The representation uses the exponent bits plus one sign bit.
- Composition: Composing Cnat with any operator in B(ω) yields an operator in B(9ω/8 + 1/8), enabling additional compression with controlled second-moment growth.The paper identifies composition with existing compression techniques as a use beyond applying natural compression alone.
3. Natural Dithering
Natural dithering generalizes randomized quantization through norm-based level partitions, with natural levels yielding substantially lower variance than standard dithering.
- General dithering: Natural dithering generalizes standard and natural quantization using p-norm normalization and s levels partitioning the unit interval.The general operator applies randomized rounding between adjacent levels while preserving each normalized coordinate in expectation.
- Natural dithering: Natural dithering uses a binary geometric partition of the unit interval, with levels corresponding to powers of two.For implementation with In-Network Aggregation, Cnat is applied so outputs remain powers of two, adding a 9/8 second-moment factor.
- Implementation: Natural dithering communicates a norm and efficiently encoded levels, while Cnat ignores mantissas and communicates exponents only.Compressed norms are particularly useful at the master because multiplying by a naturally compressed norm becomes exponent summation.
- Comparison with standard dithering: Natural dithering uses s levels, whereas standard dithering uses 2^s−1 levels for comparable constructions.The natural scheme therefore represents levels more compactly than the standard scheme.
- Comparison with standard dithering: For fixed s, natural dithering has O(2^s−1/s) times smaller variance than standard dithering.The paper identifies this as an exponential improvement over standard random dithering.
4. Distributed SGD
The paper analyzes bidirectionally compressed distributed SGD under bounded-variance stochastic gradients and smoothness assumptions. It shows that communication savings can outweigh compression-induced iteration slowdown, producing overall speedups without reported accuracy loss in the cited experiments.
- Algorithm and assumptions: Bidirectional distributed SGD compresses worker-to-master and master-to-worker communication using operators characterized by second-moment parameters ωM and ωW.The algorithm assumes unbiased stochastic gradients with bounded variance, node similarity, and an L-smooth objective.
- Convergence analysis: Compression increases the limiting gradient-norm bound linearly with the worker-side compression parameter α.The convergence theorem establishes O(1/T) convergence to a compression-dependent value.
- Running-time analysis: Compression-induced slowdown can be outweighed by communication savings, yielding an overall speedup over uncompressed training.The paper notes that standard sparsification does not necessarily improve running time, whereas natural methods raise the minimum speedup.
5. Experiments
Experiments evaluate natural compression across distributed training tasks and compression baselines, finding preserved convergence alongside substantial communication and throughput benefits.
- Experimental setup: The proof-of-concept evaluation measured aggregation throughput and convergence on ResNet110 and AlexNet using distributed training experiments.The aggregation benchmark varied worker counts between 4 and 8 and used 100MB tensors.
- Convergence and training time: 26% and 66% lower training time were observed for ResNet110 and AlexNet, respectively, without final-accuracy loss.The ResNet110 reduction was 2.89× larger than QSGD’s 9% decrease in the same setup.
- Additional evaluations: Additional experiments covered ImageNet-scale benchmarks and Neural Collaborative Filtering on MovieLens-20M without modifying benchmark hyperparameters.Cnat was also evaluated on the publicly available NCF benchmark.
- Convergence and training time: Cnat preserved accuracy on 16-worker distributed tasks while improving throughput, especially for communication-intensive models.The reported throughput comparison used TensorFlow + Horovod with NCCL as the baseline.
- Communication efficiency: Cnat further improved OmniReduce, reaching 30× speedup over NCCL for tensors with 1% non-zero elements.The comparison was conducted on an 8-machine microbenchmark.
6. Conclusions and Future Work
The paper concludes that natural compression and natural dithering reduce communication with little convergence impact, can be combined with other compressors, and achieve observed speedups. It also identifies unexplored large-scale and broader-use settings.
- Conclusions: The paper proposes natural compression Cnat and natural dithering as new compression operators.The conclusion presents both as central contributions.
- Conclusions: The general theory supports substantial communication savings with minimal or unnoticeable increases in communication rounds versus non-natural variants.The theory is developed for SGD with arbitrary bidirectional compression.
- Conclusions: Combining the proposed operators with other compression techniques yields a theoretically superior method and experimentally observed speedups across varied tasks.The conclusion states that experiments corroborate the theoretical predictions.
- Future work: Very large-scale experiments and uses beyond centralized parallel optimization remain unexplored.These are explicitly listed as future directions.
A.1. Convergence Tests on CIFAR 10
Cnat is evaluated on CIFAR10 and compared with other compression operators through convergence, variance, and communication experiments. The results show similar training behavior with lower communication and favorable variance properties for natural dithering.
- Convergence tests: Cnat achieved significant speedups without accuracy loss, with larger benefits for communication-intensive AlexNet than computation-intensive ResNets and DenseNet40.AlexNet has 62.5 M parameters, whereas ResNets have fewer than 1.7 M and DenseNet40 has 1 M.
- Variance experiments: The variance experiments generated 100 vectors of dimension d = 10^5 from independent standard Gaussian entries and measured normalized empirical variance.The authors report similar results for other tested distributions.
- Natural versus standard dithering: Natural dithering had dramatically smaller variance than standard dithering when both used the same number of levels.This agrees with the theoretical prediction in Theorem 8.
- Natural versus standard dithering: Giving standard dithering exponentially more levels made the two methods’ empirical variances essentially the same.The comparison used u = 2^s−1 for standard dithering.
- Large-level regime: For very large s, standard dithering can outperform natural dithering, but this regime is practically meaningless because it provides insufficient compression.At p = ∞ and s = 32, both empirical variances were small and standard dithering could be lower.
- Comparison with other operators: Across comparison experiments, training loss and test accuracy were nearly unchanged by compression while transmitted bits were substantially reduced.The plots report accuracy and loss against transmitted bits and over training epochs.
Appendix B. Experimental setup
The experiments implement natural compression as a communication-library replacement and optimize its representation for hardware-efficient aggregation. Stochastic rounding introduces measurable overhead, while deterministic rounding provides a comparison condition.
- Deterministic rounding is evaluated alongside no compression to expose sampling overhead, and it produces nearly the same training curve in practice.
- Natural compression is implemented in C++ within Gloo as a drop-in replacement for ring all-reduce, integrated with Horovod and TensorFlow.
- Compressed gradients are streamed in network packets, aggregated as integers, and requantized by the aggregator.
- 32-bit floats are compressed to 8-bit values using one sign bit and seven exponent bits, with exponents clipped to −50 ∼10.
- 10 ∼15% overhead is incurred by random-number generation for stochastic rounding.
B.1.1. DENSENET HYPERPARAMETERS:
This section collects training configurations for DenseNet40, AlexNet, ResNet variants, and Neural Collaborative Filtering, alongside proof fragments concerning randomized integer and power-of-two rounding.
- DENSENET HYPERPARAMETERS: DenseNet40 is trained for 300 epochs with vanilla SGD, weight decay 10−4, and learning-rate drops at epochs 150 and 225.
- AlexNet uses SGD with momentum 0.9, minibatches 256, 512, and 1024, and trains for 200 epochs with learning-rate drops every 30 epochs.
- ResNet experiments use vanilla SGD, weight decay 10−4, and learning-rate reductions at 32K and 48K iterations.
- The natural compression proof establishes unbiasedness and a second-moment bound with optimal objective value 9/8.
- Unbiased rounding to the nearest integer cannot have a finite uniform quantization parameter because its required bound diverges as x approaches 0.
C.4. Proof of Theorem 7
The proof develops natural dithering bounds through unbiasedness, second-moment control, and composition arguments, then connects these operators to distributed SGD and in-network aggregation.
- The proof represents natural dithering coordinates using levels 0, 1/2^(s−1), 2/2^(s−1), ..., 1 and visualizes the construction in Figure 22.
- Natural and standard dithering are compared through a shared parameterization, with natural dithering using fewer levels for the same fixed variance.
- With s = 4, standard dithering uses 8 levels while natural dithering uses 4 levels, yielding an exponential compression improvement.
- Natural compression and natural dithering support integer-based in-network aggregation and can provide additional speedups through simple exponent-based operations.
- Distributed SGD compresses worker gradients before transmission, aggregates them at the master, compresses the aggregate, and broadcasts it back to workers.
- Compression at the master injects additional variance into the gradient estimator, which the analysis bounds using compression-variance lemmas.
D.6. A Different Stepsize Rule for Theorem 9
The analysis relates compression-induced iteration slowdowns to communication savings across distributed-training regimes. It also specifies the communication and encoding assumptions used for theoretical comparisons.
- A Different Stepsize Rule for Theorem 9: The convergence rate generalizes the uncompressed non-convex SGD rate and retains linear speedup in the number of workers.
- Mini-batching reduces stochastic-gradient variance by σ2/b and removes the node-similarity term when every worker accesses the whole dataset, yielding linear mini-batch speedup.
- The theoretical models vary communication asymmetry, master aggregation capability, and resource variability across workers.
- Compression increases the limiting gradient-norm term linearly through the compression parameter, but communication savings can outweigh the resulting iteration slowdown.
- The tables compare overall runtime using communication rounds multiplied by transmitted bits under specified bidirectional or worker-to-master assumptions.
- For natural compression, each dense coordinate uses 9 bits instead of the 32-bit baseline, while sparsification additionally communicates nonzero positions.
Appendix E. Limitations and Extensions
Natural quantization can be combined with biased techniques such as TopK while retaining convergence guarantees. This combination delivers superior practical performance in experiments.
- Natural quantization can be combined with biased techniques such as the TopK sparsifier while retaining convergence guarantees.
- The combination of natural quantization and TopK leads to superior practical performance in experiments.