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

2025/12/19 by Even He, He, Even
Computer Science · Mathematics · #Stochastic Gradient Optimization Techniques #Statistical Methods and Inference #Advanced Statistical Methods and Models

paper · doi:10.48550/arxiv.2512.17632

Abstract

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(d³)). 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(Nd²) 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 O(√(r(Σ)/N)) with high probability. This provides a scalable solution for high-dimensional data that exhibits tails heavier than Gaussian but lighter than polynomial decay.

Citations

• Improved covariance estimation: optimal robustness and sub-Gaussian guarantees under heavy tails
• Mean estimation and regression under heavy-tailed distributions--a\n survey
• User-Friendly Covariance Estimation for Heavy-Tailed Distributions
• Estimation of the covariance structure of heavy-tailed distributions
• Large Covariance Estimation by Thresholding Principal Orthogonal\n Complements
• Challenging the empirical mean and empirical variance: a deviation study
• A well-conditioned estimator for large-dimensional covariance matrices
• The Rotation of Eigenvectors by a Perturbation. III

Related

• Estimation of the covariance structure of heavy-tailed distributions
• Improved covariance estimation: optimal robustness and sub-Gaussian guarantees under heavy tails
• User-Friendly Covariance Estimation for Heavy-Tailed Distributions
• Faster Algorithms for High-Dimensional Robust Covariance Estimation
• Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians