# Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recovery

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 103 references that are in the map.
- First posted on arXiv 30 Dec 2022.

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

- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Low-Rank Matrix Completion: A Contemporary Survey](https://mlsanity.com/paper/1907.11705/) (2019)
- [Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression](https://mlsanity.com/paper/1804.02605/) (2018)
- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [Statistical consistency and asymptotic normality for high-dimensional robust M-estimators](https://mlsanity.com/paper/1501.00312/) (2015)
- [A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion](https://mlsanity.com/paper/1309.6013/) (2013)
- [A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery](https://mlsanity.com/paper/1603.08315/) (2016)
- [High Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantization](https://mlsanity.com/paper/2202.13157/) (2022)
- [One-bit compressive sensing with norm estimation](https://mlsanity.com/paper/1404.6853/) (2014)
- [The Generalized Lasso for Sub-gaussian Measurements with Dithered Quantization](https://mlsanity.com/paper/1807.06976/) (2018)
- [Adaptive Multinomial Matrix Completion](https://mlsanity.com/paper/1408.6218/) (2014)
- [Quantizing data for distributed learning](https://mlsanity.com/paper/2012.07913/) (2020)
- [Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss](https://mlsanity.com/paper/2202.02063/) (2022)
- [Categorical Matrix Completion](https://mlsanity.com/paper/1507.00421/) (2015)
- [Sub-Gaussian Matrices on Sets: Optimal Tail Dependence and Applications](https://mlsanity.com/paper/2001.10631/) (2020)
- [Generic Error Bounds for the Generalized Lasso with Sub-Exponential Data](https://mlsanity.com/paper/2004.05361/) (2020)
- [Probabilistic low-rank matrix completion on finite alphabets](https://mlsanity.com/paper/1412.2632/) (2014)

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

- [A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing](https://mlsanity.com/paper/2310.03758/) (2023)
- [Quantized Low-Rank Multivariate Regression with Random Dithering](https://mlsanity.com/paper/2302.11197/) (2023)
- [A Parameter-Free Two-Bit Covariance Estimator with Improved Operator Norm Error Rate](https://mlsanity.com/paper/2308.16059/) (2023)
- [Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model](https://mlsanity.com/paper/2310.07367/) (2023)
- [Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition](https://mlsanity.com/paper/2509.04668/) (2025)
- [Improved Quantization Strategies for Managing Heavy-tailed Gradients in Distributed Learning](https://mlsanity.com/paper/2402.01798/) (2024)
- [Bit Efficient Toeplitz Covariance Estimation](https://mlsanity.com/paper/2412.12678/) (2024)
- [Truncated Non-Uniform Quantization for Distributed SGD](https://mlsanity.com/paper/2402.01160/) (2024)
- [Compressive Toeplitz Covariance Estimation From Few-Bit Quantized Measurements With Applications to DOA Estimation](https://mlsanity.com/paper/2512.22527/) (2025)

## Abstract (arXiv)

This paper studies the quantization of heavy-tailed data in some fundamental statistical estimation problems, where the underlying distributions have bounded moments of some order. We propose to truncate and properly dither the data prior to a uniform quantization. Our major standpoint is that (near) minimax rates of estimation error are achievable merely from the quantized data produced by the proposed scheme. In particular, concrete results are worked out for covariance estimation, compressed sensing, and matrix completion, all agreeing that the quantization only slightly worsens the multiplicative factor. Besides, we study compressed sensing where both covariate (i.e., sensing vector) and response are quantized. Under covariate quantization, although our recovery program is non-convex because the covariance matrix estimator lacks positive semi-definiteness, all local minimizers are proved to enjoy near optimal error bound. Moreover, by the concentration inequality of product process and covering argument, we establish near minimax uniform recovery guarantee for quantized compressed sensing with heavy-tailed noise.