Fast and Robust: Computationally Efficient Covariance Estimation for Sub-Weibull Vectors
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^3)$). In this work, we target the specific regime of \textbf{Sub-Weibull distributions} (characterized by stretched exponential tails $\exp(-t^α)$). We investigate a computationally efficient alternative: the \textbf{Cross-Fitted Norm-Truncated Estimator}. Unlike element-wise truncation, our approach preserves the spectral geometry while requiring $O(Nd^2)$ 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 $\tilde{O}(\sqrt{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.
Summary
This paper addresses the challenge of robust covariance estimation in high-dimensional settings where data follows Sub-Weibull distributions, characterized by stretched exponential tails. The authors note that while statistically optimal estimators exist for general heavy-tailed distributions, they often involve computationally expensive techniques like semidefinite programming or iterative M-estimation (O(d^3)). The paper proposes a computationally efficient alternative called the Cross-Fitted Norm-Truncated Estimator, which truncates data points based on their Euclidean norm. Unlike element-wise truncation, this approach preserves spectral geometry and achieves a complexity of O(Nd^2), the theoretical lower bound for constructing a full covariance matrix. The key insight is that for Sub-Weibull distributions, the exponential tail decay compensates for the geometric suboptimality of spherical truncation, which is traditionally considered unsuitable for anisotropic data. The authors leverage weighted Hanson-Wright inequalities to derive non-asymptotic error bounds. These bounds demonstrate that the estimator recovers the optimal sub-Gaussian rate of ~O(sqrt(r(Σ)/N)) with high probability, where r(Σ) is the effective rank of the covariance matrix and N is the sample size. This provides a scalable solution for high-dimensional data exhibiting tails heavier than Gaussian but lighter than polynomial decay, offering a computationally efficient alternative to more complex robust covariance estimation methods. The paper also demonstrates through simulations that the proposed estimator matches the statistical convergence rates of sophisticated robust estimators with superior computational scalability.
Key Insights
- •The paper proposes a computationally efficient (O(Nd^2)) Split-Sample Norm-Truncated Estimator for robust covariance estimation in Sub-Weibull distributions.
- •It demonstrates that for Sub-Weibull distributions, simple norm-based truncation can achieve optimal sub-Gaussian error rates, contrary to the conventional wisdom that geometrically sophisticated methods are necessary for anisotropic data.
- •Theoretical guarantees are provided using weighted Hanson-Wright inequalities, showing that the estimator recovers the optimal sub-Gaussian rate ~O(sqrt(r(Σ)/N)) with high probability.
- •The method addresses the problem of geometric mismatch of spherical truncation by leveraging the exponential tail decay of Sub-Weibull distributions, showing that the bias decays rapidly enough to be negligible.
- •Empirical results show that the Cross-Fitting Estimator outperforms Ledoit-Wolf shrinkage and a state-of-the-art spectrum-wise truncation method under Huber contamination in terms of estimation error.
- •Simulations demonstrate a significant speedup (up to 200x at d=2000) compared to SVD-based spectrum-wise truncation, scaling as O(Nd^2) instead of O(d^3).
- •The theoretical guarantees rely on the assumption that the effective rank r(Σ) is greater than C logN, which is necessary for the concentration of the Euclidean norm of Sub-Weibull vectors.
Practical Implications
- •The proposed estimator can be used in various real-world applications where data exhibits heavy tails but not as heavy as polynomial tails, such as financial returns, wireless fading channels, and gene expression data.
- •Researchers and engineers working with high-dimensional data can benefit from this efficient and robust covariance estimation method, particularly when computational resources are limited.
- •The estimator can be used as a highly efficient initialization or replacement for Robust PCA in time-critical settings, as the paper demonstrates consistent eigenvector recovery.
- •Future research directions include extending the analysis to distributions with heavier polynomial tails, where iterative updates of the truncation shape (estimating the Mahalanobis distance) might be necessary.
- •The cross-fitting strategy can be explored further to quantify the variance reduction achieved by utilizing the full sample size.