List-Decodable Linear Regression

Abstract

We give the first polynomial-time algorithm for robust regression in the list-decodable setting where an adversary can corrupt a greater than 1/2 fraction of examples. For any < 1, our algorithm takes as input a sample \(x_i,y_i)\_i n of n linear equations where n of the equations satisfy y_i = x_i,^* + for some small noise and (1-)n of the equations are arbitrarily chosen. It outputs a list L of size O(1/) - a fixed constant - that contains an that is close to ^*. Our algorithm succeeds whenever the inliers are chosen from a certifiably anti-concentrated distribution D. In particular, this gives a (d/)^O(1/^8) time algorithm to find a O(1/) size list when the inlier distribution is standard Gaussian. For discrete product distributions that are anti-concentrated only in regular directions, we give an algorithm that achieves similar guarantee under the promise that ^* 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.

Tasks

Reproductions