List-Decodable Linear Regression

We give the first polynomial-time algorithm for robust regression in the list-decodable setting where an adversary can corrupt a greater than $1\mathrm{/}2$ fraction of examples. For any $\alpha <1$, our algorithm takes as input a sample ${(x_i,y_i)}_{i \leq n}$of$n$linearequationswhere$\alpha n$oftheequationssatisfy$y_i = \langle x_i,\ell^*\rangle +\zeta$forsomesmallnoise$\zeta$and$(1-\alpha)n$oftheequationsare\text{em}arbitrarilychosen\mathrm{.}Itoutputsalist$L$ofsize$O(1/\alpha)$-afixedconstant-thatcontainsan$\ell$ that is close to ${\mathrm{\ell }}^{\ast }$. Our algorithm succeeds whenever the inliers are chosen from a \emph{certifiably} anti-concentrated distribution $D$. In particular, this gives a $(d\mathrm{/}\alpha {)}^{O(1\mathrm{/}{\alpha }^8)}$ time algorithm to find a $O(1\mathrm{/}\alpha )$ size list when the inlier distribution is standard Gaussian. For discrete product distributions that are anti-concentrated only in \emph{regular} directions, we give an algorithm that achieves similar guarantee under the promise that ${\mathrm{\ell }}^{\ast }$ has all coordinates of the same magnitude. To complement our result, we prove that the anti-concentration assumption on the inliers is information-theoretically necessary. Our algorithm is based on a new framework for list-decodable learning that strengthens the `identifiability to algorithms’ paradigm based on the sum-of-squares method. In an independent and concurrent work, Raghavendra and Yau also used the Sum-of-Squares method to give a similar result for list-decodable regression.