List Decodable Learning via Sum of Squares

Understand

In the list-decodable learning setup, an overwhelming majority (say a $1-\beta$-fraction) of the input data consists of outliers and the goal of an algorithm is to output a small list $\mathcal{L}$ of hypotheses such that one of them agrees with inliers.

• We develop a framework for list-decodable learning via the Sum-of-Squares SDP hierarchy and demonstrate it on two basic statistical estimation problems {\it Linear regression:} Suppose we are given labelled examples $\{(X_i,y_i)\}_{i \in [N]}$ containing a subset $S$ of $\beta N$ {\it inliers} $\{X_i \}_{i \in S}$ that are drawn i.i.d.
• from standard Gaussian distribution $N(0,I)$ in $\mathbb{R}^d$, where the corresponding labels $y_i$ are well-approximated by a linear function $\ell$.
• We devise an algorithm that outputs a list $\mathcal{L}$ of linear functions such that there exists some $\hat{\ell} \in \mathcal{L}$ that is close to $\ell$.