# Compressing Gradient Optimizers via Count-Sketches

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2019.

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

- [1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed](https://mlsanity.com/paper/2102.02888/) (2021)
- [From Distributed Machine Learning to Federated Learning: A Survey](https://mlsanity.com/paper/2104.14362/) (2021)
- [Communication Efficiency in Federated Learning: Achievements and Challenges](https://mlsanity.com/paper/2107.10996/) (2021)
- [1-bit LAMB: Communication Efficient Large-Scale Large-Batch Training with LAMB's Convergence Speed](https://mlsanity.com/paper/2104.06069/) (2021)
- [MicroAdam: Accurate Adaptive Optimization with Low Space Overhead and Provable Convergence](https://mlsanity.com/paper/2405.15593/) (2024)
- [Grass: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients](https://mlsanity.com/paper/2406.17660/) (2024)
- [Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity](https://mlsanity.com/paper/2406.15575/) (2024)
- [Towards Efficient Synchronous Federated Training: A Survey on System Optimization Strategies](https://mlsanity.com/paper/2109.03999/) (2021)
- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [CountSketches, Feature Hashing and the Median of Three](https://mlsanity.com/paper/2102.02193/) (2021)
- [Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2207.00956/) (2022)
- [Communication-Efficient Distributed Deep Learning via Federated Dynamic Averaging](https://mlsanity.com/paper/2405.20988/) (2024)
- [Sketched Adaptive Federated Deep Learning: A Sharp Convergence Analysis](https://mlsanity.com/paper/2411.06770/) (2024)
- [Lego Sketch: A Scalable Memory-augmented Neural Network for Sketching Data Streams](https://mlsanity.com/paper/2505.19561/) (2025)
- [Contractive error feedback for gradient compression](https://mlsanity.com/paper/2312.08538/) (2023)
- [Tula: Optimizing Time, Cost, and Generalization in Distributed Large-Batch Training](https://mlsanity.com/paper/2603.18112/) (2026)
- [The Dialect Tax: Dialectal Biases Persist throughout the Language Modeling Pipeline](https://mlsanity.com/paper/2608.24952/) (2026)

## Abstract (arXiv)

Many popular first-order optimization methods (e.g., Momentum, AdaGrad, Adam) accelerate the convergence rate of deep learning models. However, these algorithms require auxiliary parameters, which cost additional memory proportional to the number of parameters in the model. The problem is becoming more severe as deep learning models continue to grow larger in order to learn from complex, large-scale datasets. Our proposed solution is to maintain a linear sketch to compress the auxiliary variables. We demonstrate that our technique has the same performance as the full-sized baseline, while using significantly less space for the auxiliary variables. Theoretically, we prove that count-sketch optimization maintains the SGD convergence rate, while gracefully reducing memory usage for large-models. On the large-scale 1-Billion Word dataset, we save 25% of the memory used during training (8.6 GB instead of 11.7 GB) by compressing the Adam optimizer in the Embedding and Softmax layers with negligible accuracy and performance loss. For an Amazon extreme classification task with over 49.5 million classes, we also reduce the training time by 38%, by increasing the mini-batch size 3.5x using our count-sketch optimizer.