# Error Feedback Shines when Features are Rare

arXiv: https://arxiv.org/abs/2305.15264 · HTML: https://mlsanity.com/paper/2305.15264/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 30 references that are in the map.
- First posted on arXiv 24 May 2023.

## Builds on (most cited first, 18 of 18)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [The Loss Surfaces of Multilayer Networks](https://mlsanity.com/paper/1412.0233/) (2014)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019)
- [Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization](https://mlsanity.com/paper/2002.11364/) (2020)
- [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [Permutation Compressors for Provably Faster Distributed Nonconvex Optimization](https://mlsanity.com/paper/2110.03300/) (2021)
- [FL_PyTorch: optimization research simulator for federated learning](https://mlsanity.com/paper/2202.03099/) (2022)

## Built on by (most cited first, 1 of 1)

- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)

## Abstract (arXiv)

We provide the first proof that gradient descent left(colorgreensf GDright) with greedy sparsification left(colorgreensf TopKright) and error feedback left(colorgreensf EFright) can obtain better communication complexity than vanilla colorgreensf GD when solving the distributed optimization problem minx∈ ℝd f(x)=frac1nsumi=1n fi(x), where n = # of clients, d = # of features, and f1,dots,fn are smooth nonconvex functions. Despite intensive research since 2014 when colorgreensf EF was first proposed by Seide et al., this problem remained open until now. We show that colorgreensf EF shines in the regime when features are rare, i.e., when each feature is present in the data owned by a small number of clients only. To illustrate our main result, we show that in order to find a random vector hatx such that lVert nabla f(hatx) rVert2 ≤ varepsilon in expectation, colorgreensf GD with the colorgreensf Top1 sparsifier and colorgreensf EF requires cal O left(left( L+colorbluer √ fraccolorredcn min left( fraccolorredcn maxi Li2, frac1nsumi=1n Li2 right) right) frac1varepsilon right) bits to be communicated by each worker to the server only, where L is the smoothness constant of f, Li is the smoothness constant of fi, colorredc is the maximal number of clients owning any feature (1≤ colorredc ≤ n), and colorbluer is the maximal number of features owned by any client (1≤ colorbluer ≤ d). Clearly, the communication complexity improves as colorredc decreases (i.e., as features become more rare), and can be much better than the cal O(colorbluer L frac1varepsilon) communication complexity of colorgreensf GD in the same regime.