# Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 34 references that are in the map.
- First posted on arXiv 23 Feb 2022.

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

- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [A Survey of Quantization Methods for Efficient Neural Network Inference](https://mlsanity.com/paper/2103.13630/) (2021)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor](https://mlsanity.com/paper/2002.08958/) (2020)
- [An Information-Theoretic Justification for Model Pruning](https://mlsanity.com/paper/2102.08329/) (2021)
- [Transform Quantization for CNN (Convolutional Neural Network) Compression](https://mlsanity.com/paper/2009.01174/) (2020)
- [Rate Distortion For Model Compression: From Theory To Practice](https://mlsanity.com/paper/1810.06401/) (2018)
- [Efficient Randomized Subspace Embeddings for Distributed Optimization under a Communication Budget](https://mlsanity.com/paper/2103.07578/) (2021)
- [Quantized Estimation of Gaussian Sequence Models in Euclidean Balls](https://mlsanity.com/paper/1409.6833/) (2014)

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

- [Matrix Compression via Randomized Low Rank and Low Precision Factorization](https://mlsanity.com/paper/2310.11028/) (2023)

## Abstract (arXiv)

High-dimensional models often have a large memory footprint and must be quantized after training before being deployed on resource-constrained edge devices for inference tasks. In this work, we develop an information-theoretic framework for the problem of quantizing a linear regressor learned from training data (X, y), for some underlying statistical relationship y = Xboldsymbolθ + v. The learned model, which is an estimate of the latent parameter boldsymbolθ ∈ ℝd, is constrained to be representable using only Bd bits, where B ∈ (0, ∞) is a pre-specified budget and d is the dimension. We derive an information-theoretic lower bound for the minimax risk under this setting and propose a matching upper bound using randomized embedding-based algorithms which is tight up to constant factors. The lower and upper bounds together characterize the minimum threshold bit-budget required to achieve a performance risk comparable to the unquantized setting. We also propose randomized Hadamard embeddings that are computationally efficient and are optimal up to a mild logarithmic factor of the lower bound. Our model quantization strategy can be generalized and we show its efficacy by extending the method and upper-bounds to two-layer ReLU neural networks for non-linear regression. Numerical simulations show the improved performance of our proposed scheme as well as its closeness to the lower bound.