NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:4034
Title:List-decodable Linear Regression

This paper studies the challenging problem of doing linear regression in the setting where an overwhelming fraction (1-alpha) of the examples are adversarially corrupted. It extends recent work on using the Sum-of-Squares hierarchy for robust estimation. The main contribution is realizing that anti-concentration (and being able to certify anti-concentration) is the key. The algorithm has a high running time (d^(1/alpha^8)) but given the challenging nature of the problem, the reviewers felt that the fact that the problem can be solved in polynomial time for any fixed alpha > 0 is surprising and an important contribution.