{"ID":2827131,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.17632","arxiv_id":"2512.17632","title":"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.","short_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 specif...","url_abs":"https://arxiv.org/abs/2512.17632","url_pdf":"https://arxiv.org/pdf/2512.17632v2","authors":"[\"Even He\"]","published":"2025-12-19T14:34:30Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"stat.CO\"]","methods":"[]","has_code":false}