We give the first polynomialtime algorithm for robust regression in the listdecodable setting where an adversary can corrupt a greater than 1/2 fraction of examples.
For any \alpha < 1, our algorithm takes as input a sample {(xi,yi)}{i \leq n} of n linear equations where \alpha n of the equations satisfy yi = \langle x_i,\ell^\rangle +\zeta for some small noise \zeta and (1\alpha) n of the equations are {\em arbitrarily} chosen. It outputs a list L of size O(1/\alpha)  a fixed constant  that contains an \ell that is close to \ell^.
Our algorithm succeeds whenever the inliers are chosen from a certifiably anticoncentrated distribution D. In particular, this gives a (d/\alpha)^{O(1/\alpha^8)} time algorithm to find a O(1/\alpha) size list when the inlier distribution is a standard Gaussian. For discrete product distributions that are anticoncentrated only in regular directions, we give an algorithm that achieves similar guarantee under the promise that \ell^* has all coordinates of the same magnitude. To complement our result, we prove that the anticoncentration assumption on the inliers is informationtheoretically necessary.
To solve the problem we introduce a new framework for listdecodable learning that strengthens the ``identifiability to algorithms'' paradigm based on the sumofsquares method.
Author Information
Sushrut Karmalkar (The University of Texas at Austin)
Adam Klivans (UT Austin)
Pravesh Kothari (Princeton University and Institute for Advanced Study)
Related Events (a corresponding poster, oral, or spotlight)

2019 Poster: Listdecodable Linear Regression »
Tue Dec 10th 10:45 AM  12:45 PM Room East Exhibition Hall B + C
More from the Same Authors

2019 Poster: Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals »
Surbhi Goel · Sushrut Karmalkar · Adam Klivans 
2019 Spotlight: Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals »
Surbhi Goel · Sushrut Karmalkar · Adam Klivans 
2019 Poster: OutlierRobust HighDimensional Sparse Estimation via Iterative Filtering »
Ilias Diakonikolas · Daniel Kane · Sushrut Karmalkar · Eric Price · Alistair Stewart 
2017 Poster: Eigenvalue Decay Implies PolynomialTime Learnability for Neural Networks »
Surbhi Goel · Adam Klivans 
2014 Poster: Sparse Polynomial Learning and Graph Sketching »
Murat Kocaoglu · Karthikeyan Shanmugam · Alexandros Dimakis · Adam Klivans 
2014 Oral: Sparse Polynomial Learning and Graph Sketching »
Murat Kocaoglu · Karthikeyan Shanmugam · Alexandros Dimakis · Adam Klivans