# RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Aug 2019.

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

- [Matrix Compression via Randomized Low Rank and Low Precision Factorization](https://mlsanity.com/paper/2310.11028/) (2023)
- [Preserved central model for faster bidirectional compression in distributed settings](https://mlsanity.com/paper/2102.12528/) (2021)
- [EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization](https://mlsanity.com/paper/2205.04180/) (2022)
- [Solving Multi-Arm Bandit Using a Few Bits of Communication](https://mlsanity.com/paper/2111.06067/) (2021)
- [Correlated quantization for distributed mean estimation and optimization](https://mlsanity.com/paper/2203.04925/) (2022)
- [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023)
- [Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning](https://mlsanity.com/paper/2301.00944/) (2023)
- [Linear Stochastic Bandits over a Bit-Constrained Channel](https://mlsanity.com/paper/2203.01198/) (2022)
- [Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation](https://mlsanity.com/paper/2110.07751/) (2021)
- [Compressed Federated Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2404.10635/) (2024)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Efficient Randomized Subspace Embeddings for Distributed Optimization under a Communication Budget](https://mlsanity.com/paper/2103.07578/) (2021)
- [Communication-Constrained Bandits under Additive Gaussian Noise](https://mlsanity.com/paper/2304.12680/) (2023)
- [Fundamental limits of over-the-air optimization: Are analog schemes optimal?](https://mlsanity.com/paper/2109.05222/) (2021)
- [Wyner-Ziv Gradient Compression for Federated Learning](https://mlsanity.com/paper/2111.08277/) (2021)
- [Correlated Quantization for Faster Nonconvex Distributed Optimization](https://mlsanity.com/paper/2401.05518/) (2024)
- [Model-Free Learning for the Linear Quadratic Regulator over Rate-Limited Channels](https://mlsanity.com/paper/2401.01258/) (2024)
- [On the Gradient Complexity of Private Optimization with Private Oracles](https://mlsanity.com/paper/2511.13999/) (2025)
- [Optimal Compression of Unit Norm Vectors in the High Distortion Regime](https://mlsanity.com/paper/2307.07941/) (2023)
- [Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation](https://mlsanity.com/paper/2606.00703/) (2026)
- [Unbiased Single-scale and Multi-scale Quantizers for Distributed Optimization](https://mlsanity.com/paper/2109.12497/) (2021)
- [Learning in Distributed Contextual Linear Bandits Without Sharing the Context](https://mlsanity.com/paper/2206.04180/) (2022)
- [Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation](https://mlsanity.com/paper/2609.27860/) (2026)

## Abstract (arXiv)

We present Rotated Adaptive Tetra-iterated Quantizer (RATQ), a fixed-length quantizer for gradients in first order stochastic optimization. RATQ is easy to implement and involves only a Hadamard transform computation and adaptive uniform quantization with appropriately chosen dynamic ranges. For noisy gradients with almost surely bounded Euclidean norms, we establish an information theoretic lower bound for optimization accuracy using finite precision gradients and show that RATQ almost attains this lower bound. For mean square bounded noisy gradients, we use a gain-shape quantizer which separately quantizes the Euclidean norm and uses RATQ to quantize the normalized unit norm vector. We establish lower bounds for performance of any optimization procedure and shape quantizer, when used with a uniform gain quantizer. Finally, we propose an adaptive quantizer for gain which when used with RATQ for shape quantizer outperforms uniform gain quantization and is, in fact, close to optimal. As a by-product, we show that our fixed-length quantizer RATQ has almost the same performance as the optimal variable-length quantizers for distributed mean estimation. Also, we obtain an efficient quantizer for Gaussian vectors which attains a rate very close to the Gaussian rate-distortion function and is, in fact, universal for subgaussian input vectors.