Error Feedback

The core mechanism of Error Feedback is the maintenance of a local error memory on each client. After compressing a gradient, the difference between the original dense gradient and its compressed representation is calculated. This compression residual is not discarded; it is stored in a local buffer and added to the gradient generated in the subsequent training iteration before the next compression step. This creates a closed-loop system where information delayed by compression is eventually transmitted.

Without Error Feedback, aggressive compression techniques like sparsification (retaining <1% of gradients) or low-bit quantization introduce a biased error that causes the model to converge to a suboptimal point or diverge entirely. Error Feedback corrects this bias by ensuring the optimization trajectory follows the true gradient direction in expectation. Theoretical proofs demonstrate that SGD with Error Feedback and arbitrary compression operators converges at the same asymptotic rate as uncompressed SGD for both convex and non-convex objectives.

Implementing Error Feedback introduces a memory overhead proportional to the model size, as each client must store a residual tensor equal in dimensions to the full gradient. For large models with hundreds of millions of parameters, this can be significant. Techniques to mitigate this include:

• Quantizing the residual itself to reduce its memory footprint
• Applying momentum masking to zero out residuals for coordinates where momentum is small
• Using factorized error feedback that stores residuals in a compressed low-rank format

A naive combination of Error Feedback with SGD with momentum (SGDM) or Adam leads to a problematic interaction: the momentum term smooths the gradient, but the error feedback mechanism injects stale, delayed residuals that disrupt this smoothing. Momentum Correction solves this by applying the compression operator to the momentum-adjusted update vector rather than the raw gradient, and storing the residual of this combined update. This ensures the optimizer's dynamics remain consistent with the dense training regime.

In the early stages of training, gradients are large and volatile. Aggressive compression during this phase can cause the error feedback buffer to accumulate a massive residual that destabilizes later iterations. Common mitigation strategies include:

• Progressive compression: Starting with mild compression and gradually increasing the ratio over the first few epochs
• Residual clipping: Applying norm-based clipping to the accumulated error before re-injection
• Delayed feedback: Training without compression for a small number of initial iterations to establish a stable optimization trajectory

In production federated systems, Error Feedback is often applied in a two-stage pipeline. The client first compresses the gradient for upload using sparsification, accumulating the residual locally. The server then applies a second compression step—typically gradient quantization—to the aggregated sparse updates before broadcasting them back to clients. Each stage maintains its own independent error feedback loop. This architecture, used in algorithms like DoubleSqueeze, maximizes bandwidth savings in both directions.