Timezone: »

 
Spotlight
List-decodable Linear Regression
Sushrut Karmalkar · Adam Klivans · Pravesh Kothari

Tue Dec 10 10:20 AM -- 10:25 AM (PST) @ West Exhibition Hall A
in Track 2 Session 1 »

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 \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 anti-concentrated 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 anti-concentrated 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 anti-concentration assumption on the inliers is information-theoretically necessary.

To solve the problem we introduce a new framework for list-decodable learning that strengthens the ``identifiability to algorithms'' paradigm based on the sum-of-squares 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)

More from the Same Authors