论文标题
使用批次的有效列表可解码回归
Efficient List-Decodable Regression using Batches
论文作者
论文摘要
我们开始使用批处理研究列表可解码的线性回归。在这种情况下，只有$α\在（0,1] $中的一小部分是真实的。每个批次都包含$ \ ge n $ i.i.d.中的样本中的样品，来自常见的未知分布，其余批次可能包含任意或偶数的样本。我们得出了$ n的$ n \ ge sige a for $ n \ ge \ ge \ ge \ ge \ ge \ n \ tilde \ \ tilde \ tilde（1） $ \ MATHCAL O（1/α^2）$，使列表中的一个项目接近真实的回归参数。 结果证明了批处理结构的实用性，该实用性允许使用列表可解码的第一个多项式时间算法，这对于非批次设置可能是不可能的，如最近的SQ下限\ cite {diakonikolas2021stattististion}的最新SQ下限。
We begin the study of list-decodable linear regression using batches. In this setting only an $α\in (0,1]$ fraction of the batches are genuine. Each genuine batch contains $\ge n$ i.i.d. samples from a common unknown distribution and the remaining batches may contain arbitrary or even adversarial samples. We derive a polynomial time algorithm that for any $n\ge \tilde Ω(1/α)$ returns a list of size $\mathcal O(1/α^2)$ such that one of the items in the list is close to the true regression parameter. The algorithm requires only $\tilde{\mathcal{O}}(d/α^2)$ genuine batches and works under fairly general assumptions on the distribution. The results demonstrate the utility of batch structure, which allows for the first polynomial time algorithm for list-decodable regression, which may be impossible for the non-batch setting, as suggested by a recent SQ lower bound \cite{diakonikolas2021statistical} for the non-batch setting.
