# Fast and Robust: Computationally Efficient Covariance Estimation for Sub-Weibull Vectors

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 19 references that are in the map.
- First posted on arXiv 19 Dec 2025.

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

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [User-Friendly Covariance Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/1811.01520/) (2018)

## Abstract (arXiv)

High-dimensional covariance estimation is notoriously sensitive to outliers. While statistically optimal estimators exist for general heavy-tailed distributions, they often rely on computationally expensive techniques like semidefinite programming or iterative M-estimation (O(d3)). In this work, we target the specific regime of Sub-Weibull distributions (characterized by stretched exponential tails exp(-tα)). We investigate a computationally efficient alternative: the Cross-Fitted Norm-Truncated Estimator. Unlike element-wise truncation, our approach preserves the spectral geometry while requiring O(Nd2) operations, which represents the theoretical lower bound for constructing a full covariance matrix. Although spherical truncation is geometrically suboptimal for anisotropic data, we prove that within the Sub-Weibull class, the exponential tail decay compensates for this mismatch. Leveraging weighted Hanson-Wright inequalities, we derive non-asymptotic error bounds showing that our estimator recovers the optimal sub-Gaussian rate tildeO(√r(Sigma)/N) with high probability. This provides a scalable solution for high-dimensional data that exhibits tails heavier than Gaussian but lighter than polynomial decay.