Paper Info
Title
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Abstract
We study polynomial-time algorithms for linear regression and covariance estimation in the absence of strong (Gaussian) assumptions on the underlying distributions of samples, making assumptions instead about only finitely-many moments. We focus on how many samples are required to perform estimation and regression with high accuracy and exponentially-good success probability in the face of heavy-tailed data. For covariance estimation, linear regression, and several other problems in high-dimensional statistics, estimators have recently been constructed whose sample complexities and rates of statistical error match what is possible when the underlying distribution is Gaussian, but known algorithms for these estimators require exponential time. We narrow the gap between the Gaussian and heavy-tailed settings for polynomial-time estimators with: (a) a polynomial-time estimator which takes n samples from a d-dimensional random vector X with covariance Σ and produces Σ such that in spectral norm ||Σ − Σ ||2 ≤ Õ(d3/4/√n) w.p. 1−2−d where the information-theoretically optimal error bound is Õ(√d/n), while previous approaches to polynomial-time algorithms were stuck at Õ(d/√n) and (b) a polynomial-time algorithm which takes n samples (Xi,Yi) where Yi = ⟨ u,Xi ⟩ + i where both X and have a constant number of bounded moments and produces û such that the loss ||u − û||2 ≤ O(d/n) w.p. 1−2−d for any n ≥ d3/2 log(d). This (information-theoretically optimal) error is achieved by inefficient algorithms for any n ≫ d, while previous approaches to polynomial-time algorithms suffer loss Ω(d2/n) and require n ≫ d2. Our algorithms make crucial use of degree-8 sum-of-squares semidefinite programs. Both apply to any X which has constantly-many certifiably hypercontractive moments. We offer preliminary evidence that improving on these rates of error in polynomial time is not possible in the median of means framework our algorithms employ. Our work introduces new techniques to high-probability estimation, and suggests numerous new algorithmic questions in the following vein: when is it computationally feasible to do statistics in high dimensions with Gaussian-style errors when data is far from Gaussian?
Year
DOI
Venue
2020
10.1145/3357713.3384329
STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing Chicago IL USA June, 2020
Keywords
DocType
ISSN
Heavy-Tailed Estimation, Sum-of-squares, Algorithms
Conference
0737-8017
ISBN
Citations 
PageRank 
978-1-4503-6979-4
0
0.34
References 
Authors
0
5
Name
Order
Citations
PageRank
Yeshwanth Cherapanamjeri1174.51
Samuel Hopkins2889.47
tarun kathuria3143.33
Prasad Raghavendra4101350.58
Tripuraneni Nilesh500.34