List Decodable Learning via Sum of Squares

In the list-decodable learning setup, an overwhelming majority (say a 1β-fraction) of the input data consists of outliers and the goal of an algorithm is to output a small list L of hypotheses such that one of them agrees with inliers. We develop a framework for listdecodable learning via the Sum-of-Squares SDP hierarchy and demonstrate it on two basic statistical estimation problems

• Linear regression: Suppose we are given labelled examples (X i , y i ) i∈[N] containing a subset S of βN inliers X i i∈S that are drawn i.i.d. from standard Gaussian distribution N(0, I) in d , where the corresponding labels y i are well-approximated by a linear function ℓ. We devise an algorithm that outputs a list L of linear functions such that there exists some l ∈ L that is close to ℓ. This yields the first algorithm for linear regression in a list-decodable setting. Our results hold for any distribution of examples whose concentration and anticoncentration can be certified by Sum-of-Squares proofs.

• Mean Estimation: Given data points X i i∈[N] containing a subset S of βN inliers X i i∈S that are drawn i.i.d. from a Gaussian distribution N(µ, I) in d , we devise an algorithm that generates a list L of means such that there exists μ ∈ L close to µ. The recovery guarantees of the algorithm are analogous to the existing algorithms for the problem by Diakonikolas et al. [DKS18] and Kothari et al. [KS17a].

In an independent and concurrent work, Karmalkar et al. [KKK19] also obtain an algorithm for list-decodable linear regression using the Sum-of-Squares SDP hierarchy.