# Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond

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

## Key facts

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

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

- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials](https://mlsanity.com/paper/2106.02129/) (2021)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [List-Decodable Covariance Estimation](https://mlsanity.com/paper/2206.10942/) (2022)
- [A Complete Characterization of Linear Estimators for Offline Policy Evaluation](https://mlsanity.com/paper/2203.04236/) (2022)
- [Time varying regression with hidden linear dynamics](https://mlsanity.com/paper/2112.14862/) (2021)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Robust empirical risk minimization via Newton's method](https://mlsanity.com/paper/2301.13192/) (2023)
- [Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification](https://mlsanity.com/paper/2201.01973/) (2022)
- [Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models](https://mlsanity.com/paper/2206.02455/) (2022)
- [Robustifying Markowitz](https://mlsanity.com/paper/2212.13996/) (2022)
- [A Novel Framework for Improving the Breakdown Point of Robust Regression Algorithms](https://mlsanity.com/paper/2305.12220/) (2023)
- [Online Heavy-tailed Change-point detection](https://mlsanity.com/paper/2306.09548/) (2023)

## Abstract (arXiv)

We study efficient algorithms for linear regression and covariance estimation in the absence of Gaussian assumptions on the underlying distributions of samples, making assumptions instead about only finitely-many moments. We focus on how many samples are needed to do estimation and regression with high accuracy and exponentially-good success probability. For covariance estimation, linear regression, and several other problems, estimators have recently been constructed with sample complexities and rates of error matching what is possible when the underlying distribution is Gaussian, but algorithms for these estimators require exponential time. We narrow the gap between the Gaussian and heavy-tailed settings for polynomial-time estimators with: 1. A polynomial-time estimator which takes n samples from a random vector X ∈ Rd with covariance Sigma and produces hatSigma such that in spectral norm |hatSigma - Sigma |2 ≤ tildeO(d3/4/√n) w.p. 1-2-d. The information-theoretically optimal error bound is tildeO(√d/n); previous approaches to polynomial-time algorithms were stuck at tildeO(d/√n). 2. A polynomial-time algorithm which takes n samples (Xi,Yi) where Yi = langle u,Xi rangle + varepsiloni and produces hatu such that the loss |u - hatu|2 ≤ O(d/n) w.p. 1-2-d for any n ≥ d3/2 log(d)O(1). This (information-theoretically optimal) error is achieved by inefficient algorithms for any n gg d; previous polynomial-time algorithms suffer loss Omega(d2/n) and require n gg d2. Our algorithms use degree-8 sum-of-squares semidefinite programs. We offer preliminary evidence that improving these rates of error in polynomial time is not possible in the median of means framework our algorithms employ.