Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond
Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond
复制标题
DOI：
10.1145/3357713.3384329
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Yeshwanth Cherapanamjeri;Samuel B. Hopkins;Tarun Kathuria;P. Raghavendra;Nilesh Tripuraneni
中科院分区：
文献类型：
--
作者：
Yeshwanth Cherapanamjeri;Samuel B. Hopkins;Tarun Kathuria;P. Raghavendra;Nilesh Tripuraneni
我们研究了线性回归和协方差估计的多项式时间算法，在缺乏对样本底层分布的强（高斯）假设的情况下，只对有限多个矩进行假设。我们关注的是在面对重尾数据时，需要多少样本才能以高精度和指数级良好的成功概率进行估计和回归。对于协方差估计、线性回归和高维统计中的其他几个问题，最近已经构建了估计器，其样本复杂性和统计错误率与潜在分布为高斯分布时的可能情况相匹配，但是这些估计器的已知算法需要指数时间。我们用以下方法缩小了多项式时间估计器的高斯和重尾设置之间的差距：(a)一个多项式时间估计器，它从一个协方差为Σ的d维随机向量X中取n个样本，并产生Σ，使得在谱范数||Σ−Σ ||2≤Õ（d 3/4/√n） w.p.1−2−d，其中信息理论最优误差界为Õ（√d/n）；而以前的多项式时间算法的方法被卡在Õ（d/√n）和(b)一个多项式时间算法，它取n个样本（X i,Y i），其中Y i =⟨u,X i⟩+ i，其中X和都具有恒定数量的有界矩，并产生û，使得损失||u - û||2≤O(d/n) w.p 1−2−d对于任何n≥d 3/2 log(d)。这种（信息理论最优的）误差是通过对任何n²d的低效算法实现的，而以前的多项式时间算法的方法遭受损失Ω（d²/n）并且需要n²d。我们的算法充分利用了8次平方和半定程序。两者都适用于任何X，只要它有恒定多的可证实的超收缩矩。我们提供的初步证据表明，在我们的算法采用的中位数框架中，在多项式时间内提高这些错误率是不可能的。我们的工作为高概率估计引入了新技术，并在以下方面提出了许多新的算法问题：当数据远离高斯时，在高维中使用高斯式误差进行统计何时在计算上可行？
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 ≤ Õ(d 3/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 (X i ,Y i ) where Y i = ⟨ u,X i ⟩ + 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 ≥ d 3/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 Ω(d 2/n) and require n ≫ d 2. 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?