Statistical Query Lower Bounds for List-Decodable Linear Regression

Abstract

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.

References in corpus (8)

• Poisoning Attacks against Support Vector Machines
• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• Distributions of Angles in Random Packing on Spheres
• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• EM Converges for a Mixture of Many Linear Regressions
• List-Decodable Mean Estimation in Nearly-PCA Time
• List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time