# Optimal and Near-Optimal Adaptive Vector Quantization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 40 references that are in the map.
- First posted on arXiv 5 Feb 2024.

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

- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Mixed Precision Training](https://mlsanity.com/paper/1710.03740/) (2017)
- [Up or Down? Adaptive Rounding for Post-Training Quantization](https://mlsanity.com/paper/2004.10568/) (2020)
- [FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU](https://mlsanity.com/paper/2303.06865/) (2023)
- [Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing](https://mlsanity.com/paper/1912.10557/) (2019)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Q-BERT: Hessian Based Ultra Low Precision Quantization of BERT](https://mlsanity.com/paper/1909.05840/) (2019)
- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)
- [Expanding the Reach of Federated Learning by Reducing Client Resource Requirements](https://mlsanity.com/paper/1812.07210/) (2018)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [Natural Compression for Distributed Deep Learning](https://mlsanity.com/paper/1905.10988/) (2019)
- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [Dataset Quantization](https://mlsanity.com/paper/2308.10524/) (2023)
- [Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor](https://mlsanity.com/paper/2002.08958/) (2020)
- [Adaptive Gradient Quantization for Data-Parallel SGD](https://mlsanity.com/paper/2010.12460/) (2020)
- [Randomized Distributed Mean Estimation: Accuracy vs Communication](https://mlsanity.com/paper/1611.07555/) (2016)
- [DoCoFL: Downlink Compression for Cross-Device Federated Learning](https://mlsanity.com/paper/2302.00543/) (2023)
- [NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization](https://mlsanity.com/paper/1908.06077/) (2019)
- [THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression](https://mlsanity.com/paper/2302.08545/) (2023)
- [How to send a real number using a single bit (and some shared randomness)](https://mlsanity.com/paper/2010.02331/) (2020)
- [QUIC-FL: Quick Unbiased Compression for Federated Learning](https://mlsanity.com/paper/2205.13341/) (2022)

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

- [PacTrain: Pruning and Adaptive Sparse Gradient Compression for Efficient Collective Communication in Distributed Deep Learning](https://mlsanity.com/paper/2505.18563/) (2025)
- [VQ-bench: A Composable Vector Quantization Framework](https://mlsanity.com/paper/2608.11240/) (2026)

## Abstract (arXiv)

Quantization is a fundamental optimization for many machine-learning use cases, including compressing gradients, model weights and activations, and datasets. The most accurate form of quantization is adaptive, where the error is minimized with respect to a given input, rather than optimizing for the worst case. However, optimal adaptive quantization methods are considered infeasible in terms of both their runtime and memory requirements. We revisit the Adaptive Vector Quantization (AVQ) problem and present algorithms that find optimal solutions with asymptotically improved time and space complexity. We also present an even faster near-optimal algorithm for large inputs. Our experiments show our algorithms may open the door to using AVQ more extensively in a variety of machine learning applications.