Efficient Algorithms and Lower Bounds for Robust Linear Regression
Efficient Algorithms and Lower Bounds for Robust Linear Regression
复制标题
稳健线性回归的高效算法和下界
DOI：
10.1137/1.9781611975482.170
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Stewart, Alistair
中科院分区：
文献类型：
--
作者：
Diakonikolas, Ilias;Kong, Weihao;Stewart, Alistair
我们在一个稳健的模型中研究高维线性回归的原型问题，其中样本的 ε 部分可能会被对抗性破坏。我们关注基本设置，其中未损坏样本的协变量是从 ℝd 上的高斯分布 N(0, Σ) 中得出的。我们给出了这个问题的近乎严格的上限和计算下限。具体来说，我们的主要贡献如下：对于已知协方差矩阵为恒等式的情况，我们给出了一种近乎最优且计算高效的算法，该算法绘制Õ(d/ε2)个标记示例，并输出近似于ℓ2-normO(εlog(1/ε)σ)内的未知回归向量β的候选假设向量，其中σ是随机观测噪声的标准差。即使样本量无限，Ω(εσ) 的误差在信息理论上也是必要的。因此，我们算法的误差保证是最优的，达到对数因子 1/ε。先前的工作针对样本复杂度问题给出了一种算法，其误差保证与 β 的ℓ2-范数成比例。对于未知协方差 Σ 的情况，我们表明，使用额外的 Õ(d2/ε2) 个未标记示例，我们可以有效地实现与已知协方差情况下相同的 O(εlog(1/ε)σ) 误差保证。另一方面，O(εσ) 的误差可以通过 O(d/ε2) 个样本在信息理论上获得。我们证明了统计查询（SQ）下界，提供了样本大小的二次权衡是固有的证据。更具体地说，我们表明，任何用于鲁棒线性回归（在 Huber 污染模型中）的多项式时间 SQ 学习算法，其估计复杂度为 O(d2–c)，其中 c> 0 是一个任意小的常数，必须产生 的误差。
We study the prototypical problem of high-dimensional linear regression in a robust model where anε-fraction of the samples can be adversarially corrupted. We focus on the fundamental setting where the covariates of the uncorrupted samples are drawn from a Gaussian distributionN(0, ∑) on ℝd. We give nearly tight upper bounds and computational lower bounds for this problem. Specifically, our main contributions are as follows:For the case that the covariance matrix is known to be the identity, we give a sample near-optimal and computationally efficient algorithm that drawsÕ(d/ε2) labeled examples and outputs a candidate hypothesis vector that approximates the unknown regression vectorβwithinℓ2-normO(εlog(1/ε)σ), whereσis the standard deviation of the random observation noise. An error of Ω(εσ) is information-theoretically necessary, even with infinite sample size. Hence, the error guarantee of our algorithm is optimal, up to a logarithmic factor in 1/ε. Prior work gave an algorithm for this problem with sample complexity whose error guarantee scales with theℓ2-norm ofβ.For the case of unknown covariance ∑, we show that we can efficiently achieve the same error guarantee ofO(εlog(1/ε)σ), as in the known covariance case, using an additionalÕ(d2/ε2) unlabeled examples. On the other hand, an error ofO(εσ) can be information-theoretically attained withO(d/ε2) samples. We prove a Statistical Query (SQ) lower bound providing evidence that this quadratic tradeoff in the sample size is inherent. More specifically, we show that any polynomial time SQ learning algorithm for robust linear regression (in Huber's contamination model) with estimation complexityO(d2–c), wherec> 0 is an arbitrarily small constant, must incur an error of .
登录
查看更多内容
影响因子：
1.5
作者：
Chao Gao
通讯作者：
Chao Gao
通过平方和进行异常值稳健矩估计
DOI：
--
发表时间：
2017
期刊：
arXiv.org
影响因子：
--
作者：
Pravesh Kothari;David Steurer
通讯作者：
David Steurer
DOI：
10.1145/3188745.3188758
发表时间：
2017-11
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Ilias Diakonikolas;D. Kane;Alistair Stewart
通讯作者：
Ilias Diakonikolas;D. Kane;Alistair Stewart
DOI：
10.1137/1.9781611975031.171
发表时间：
2017-04
期刊：
ArXiv
影响因子：
--
作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
通讯作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
DOI：
--
发表时间：
2016-06
期刊：
--
影响因子：
--
作者：
Yu Cheng;Ilias Diakonikolas;D. Kane;Alistair Stewart
通讯作者：
Yu Cheng;Ilias Diakonikolas;D. Kane;Alistair Stewart