# Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2016.

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

- [Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance](https://mlsanity.com/paper/2202.11632/) (2022)
- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [On Estimating Rank-One Spiked Tensors in the Presence of Heavy Tailed Errors](https://mlsanity.com/paper/2107.09660/) (2021)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)
- [Provably Robust Temporal Difference Learning for Heavy-Tailed Rewards](https://mlsanity.com/paper/2306.11455/) (2023)
- [Non-Asymptotic Guarantees for Robust Statistical Learning under Infinite Variance Assumption](https://mlsanity.com/paper/2201.03182/) (2022)
- [Robust Methods for High-Dimensional Linear Learning](https://mlsanity.com/paper/2208.05447/) (2022)
- [Multi-task Representation Learning for Pure Exploration in Bilinear Bandits](https://mlsanity.com/paper/2311.00327/) (2023)
- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [Generalized Low-Rank Matrix Contextual Bandits with Graph Information](https://mlsanity.com/paper/2507.17528/) (2025)
- [Robust supervised learning with coordinate gradient descent](https://mlsanity.com/paper/2201.13372/) (2022)
- [Robust empirical risk minimization via Newton's method](https://mlsanity.com/paper/2301.13192/) (2023)
- [Concentration inequalities for semidefinite least squares based on data](https://mlsanity.com/paper/2509.13166/) (2025)
- [Robust High-dimensional Tuning Free Multiple Testing](https://mlsanity.com/paper/2211.11959/) (2022)
- [Empirical Risk Minimization for Losses without Variance](https://mlsanity.com/paper/2309.03818/) (2023)
- [Transfer Learning for Matrix Completion](https://mlsanity.com/paper/2507.02248/) (2025)
- [Interpretive Efficiency: Information-Geometric Foundations of Data Usefulness](https://mlsanity.com/paper/2512.06341/) (2025)
- [Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors](https://mlsanity.com/paper/2609.33025/) (2026)

## Abstract (arXiv)

Estimation of the covariance matrix has attracted a lot of attention of the statistical research community over the years, partially due to important applications such as Principal Component Analysis. However, frequently used empirical covariance estimator (and its modifications) is very sensitive to outliers in the data. As P. J. Huber wrote in 1964, "...This raises a question which could have been asked already by Gauss, but which was, as far as I know, only raised a few years ago (notably by Tukey): what happens if the true distribution deviates slightly from the assumed normal one? As is now well known, the sample mean then may have a catastrophically bad performance..." Motivated by this question, we develop a new estimator of the (element-wise) mean of a random matrix, which includes covariance estimation problem as a special case. Assuming that the entries of a matrix possess only finite second moment, this new estimator admits sub-Gaussian or sub-exponential concentration around the unknown mean in the operator norm. We will explain the key ideas behind our construction, as well as applications to covariance estimation and matrix completion problems.