Statistical Query Lower Bounds for List-Decodable Linear Regression
Statistical Query Lower Bounds for List-Decodable Linear Regression
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas;D. Kane;Ankit Pensia;Thanasis Pittas;Alistair Stewart
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;D. Kane;Ankit Pensia;Thanasis Pittas;Alistair Stewart
我们研究列表可译码线性回归问题，其中对手可以破坏大多数例子。具体地说，我们被赋予了一组$T$的带标签的例子$(x，y)\in\mathbb{R}^d\Times\mathbb{R}$和一个参数$0<；\α<；1/2$，使得$T$中的$\α$-分数的点是I.D.样本来自具有高斯协变量的线性回归模型，剩余的$(1-\α)$分数的点是从任意噪声分布中提取的。目标是输出一小部分假设向量，以使其中至少一个接近目标回归向量。我们的主要结果是这个问题的一个统计查询(SQ)下界为$d^{\mathm{poly}(1/\α)}$。我们的SQ下界与以前开发的算法的性能定性地匹配，提供了证据，表明目前这项任务的上界几乎是最好的。
We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples. Specifically, we are given a set $T$ of labeled examples $(x, y) \in \mathbb{R}^d \times \mathbb{R}$ and a parameter $0<\alpha<1/2$ such that an $\alpha$-fraction of the points in $T$ are i.i.d. samples from a linear regression model with Gaussian covariates, and the remaining $(1-\alpha)$-fraction of the points are drawn from an arbitrary noise distribution. The goal is to output a small list of hypothesis vectors such that at least one of them is close to the target regression vector. Our main result is a Statistical Query (SQ) lower bound of $d^{\mathrm{poly}(1/\alpha)}$ for this problem. Our SQ lower bound qualitatively matches the performance of previously developed algorithms, providing evidence that current upper bounds for this task are nearly best possible.