# Variance Reduction with Sparse Gradients

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jan 2020.

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

- [A Coefficient Makes SVRG Effective](https://mlsanity.com/paper/2311.05589/) (2023)
- [Balance is Essence: Accelerating Sparse Training via Adaptive Gradient Correction](https://mlsanity.com/paper/2301.03573/) (2023)
- [DeepReduce: A Sparse-tensor Communication Framework for Distributed Deep Learning](https://mlsanity.com/paper/2102.03112/) (2021)
- [RS-DGC: Exploring Neighborhood Statistics for Dynamic Gradient Compression on Remote Sensing Image Interpretation](https://mlsanity.com/paper/2312.17530/) (2023)
- [Grad Queue : A probabilistic framework to reinforce sparse gradients](https://mlsanity.com/paper/2404.16917/) (2024)

## Abstract (arXiv)

Variance reduction methods such as SVRG and SpiderBoost use a mixture of large and small batch gradients to reduce the variance of stochastic gradients. Compared to SGD, these methods require at least double the number of operations per update to model parameters. To reduce the computational cost of these methods, we introduce a new sparsity operator: The random-top-k operator. Our operator reduces computational complexity by estimating gradient sparsity exhibited in a variety of applications by combining the top-k operator and the randomized coordinate descent operator. With this operator, large batch gradients offer an extra benefit beyond variance reduction: A reliable estimate of gradient sparsity. Theoretically, our algorithm is at least as good as the best algorithm (SpiderBoost), and further excels in performance whenever the random-top-k operator captures gradient sparsity. Empirically, our algorithm consistently outperforms SpiderBoost using various models on various tasks including image classification, natural language processing, and sparse matrix factorization. We also provide empirical evidence to support the intuition behind our algorithm via a simple gradient entropy computation, which serves to quantify gradient sparsity at every iteration.