Gradient Compression

A technique that transmits only a subset of gradient elements with the largest magnitudes, setting the rest to zero. Top-k sparsification retains only the most significant gradient components, achieving compression ratios of 100-1000x without severely degrading model convergence. The accumulated error from dropped gradients is stored locally in a residual gradient buffer and added to the next round's update, ensuring no information is permanently lost. This method is particularly effective in cross-device federated learning where uplink bandwidth is severely constrained.

A compression method that reduces the bit-width of each gradient element from the standard 32-bit floating-point representation to a lower precision format. Stochastic quantization randomly rounds values to discrete levels, providing an unbiased estimate of the original gradient. SignSGD takes this to the extreme by transmitting only the sign of each gradient element, achieving 32x compression. QSGD (Quantized SGD) uses variable-length encoding to balance compression ratio with statistical fidelity, making it suitable for over-the-air computation scenarios where analog modulation naturally supports low-precision aggregation.

A critical component that compensates for the bias introduced by aggressive compression. When gradients are sparsified or quantized, the compression error is not discarded but accumulated in a local error memory. This residual is added to the gradient in the subsequent communication round, ensuring that the compressed updates remain an unbiased estimator of the true gradient over time. Without error feedback, naive compression leads to divergence in non-convex optimization. The EF21 algorithm provides a modern variant with provable convergence guarantees for deep learning workloads.

A structural compression approach that approximates the gradient matrix of each neural network layer as a product of two smaller matrices using singular value decomposition (SVD). Instead of transmitting the full gradient tensor, only the top singular vectors and values are communicated. PowerSGD applies this technique to distributed deep learning, achieving compression ratios proportional to the rank chosen. This method is particularly effective for large fully-connected and convolutional layers where gradient matrices exhibit strong low-rank structure, and it integrates naturally with secure aggregation protocols.

A dynamic strategy that varies the compression ratio throughout the training process based on convergence state. Early in training, when gradients are large and noisy, aggressive compression can be applied with minimal impact. As the model approaches convergence, the compression ratio is reduced to preserve fine-grained optimization signals. AdaQS (Adaptive Quantization Scheme) monitors gradient variance and automatically adjusts quantization levels. This approach is essential for straggler mitigation in heterogeneous federated networks where client bandwidth varies unpredictably over time.

The fundamental tension between communication savings and model accuracy. Key considerations include:

• Compression ratio vs. convergence speed: Higher compression requires more training rounds to reach target accuracy
• Statistical heterogeneity impact: Non-IID data distributions amplify the variance introduced by compression, requiring more conservative compression rates
• Uplink vs. downlink asymmetry: Compression typically targets the bandwidth-constrained client-to-server uplink, while the server broadcast remains uncompressed
• Compatibility with differential privacy: Quantization noise can complement privacy noise, but sparsification may leak information about which gradients were selected

Reduces the bit-width of each gradient element from the standard 32-bit floating-point representation to a lower precision format. Techniques range from 8-bit integer quantization to extreme 1-bit binary quantization (signSGD), where only the sign of each gradient is transmitted.

• QSGD (Quantized SGD) provides tunable precision-variance tradeoffs
• TernGrad uses three levels: {-1, 0, +1} for further compression
• Quantization noise can act as a regularizer, sometimes improving generalization

Techniques that address the problem of slow or unresponsive clients delaying synchronous training rounds. Gradient compression indirectly helps by reducing transmission time, but dedicated straggler strategies include:

• Asynchronous SGD: server updates immediately upon receiving any client's gradient
• Coded computation: introduces redundancy so the server can proceed after receiving a subset of updates
• Deadline-based scheduling: sets a time limit per round and discards late updates
• Compression reduces the variance in communication time, making straggler behavior less pronounced