# List Decodable Learning via Sum of Squares

arXiv: https://arxiv.org/abs/1905.04660 · HTML: https://mlsanity.com/paper/1905.04660/

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2019.

## Built on by (most cited first, 30 of 37)

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Tester-Learners for Halfspaces: Universal Algorithms](https://mlsanity.com/paper/2305.11765/) (2023)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [Privately Learning Mixtures of Axis-Aligned Gaussians](https://mlsanity.com/paper/2106.02162/) (2021)
- [List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering](https://mlsanity.com/paper/2206.05245/) (2022)
- [List and Certificate Complexities in Replicable Learning](https://mlsanity.com/paper/2304.02240/) (2023)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [A Characterization of List Language Identification in the Limit](https://mlsanity.com/paper/2511.04103/) (2025)
- [List-Decodable Covariance Estimation](https://mlsanity.com/paper/2206.10942/) (2022)
- [SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation](https://mlsanity.com/paper/2101.01509/) (2021)
- [High Dimensional Distributed Gradient Descent with Arbitrary Number of Byzantine Attackers](https://mlsanity.com/paper/2307.13352/) (2023)
- [Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Clouds](https://mlsanity.com/paper/2402.10865/) (2024)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Data-Driven Subgroup Identification for Linear Regression](https://mlsanity.com/paper/2305.00195/) (2023)
- [A Characterization of List Regression](https://mlsanity.com/paper/2409.19218/) (2024)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error](https://mlsanity.com/paper/2302.12289/) (2023)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [Conditional Linear Regression for Heterogeneous Covariances](https://mlsanity.com/paper/2111.07834/) (2021)
- [A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm](https://mlsanity.com/paper/2305.00966/) (2023)
- [Asymptotic Characterisation of Robust Empirical Risk Minimisation Performance in the Presence of Outliers](https://mlsanity.com/paper/2305.18974/) (2023)

## Abstract (arXiv)

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 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 (Xi,yi)i ∈ [N] containing a subset S of β N it inliers Xi i ∈ S that are drawn i.i.d. from standard Gaussian distribution N(0,I) in ℝd, where the corresponding labels yi are well-approximated by a linear function ℓ. We devise an algorithm that outputs a list L of linear functions such that there exists some hatℓ ∈ 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. it Mean Estimation: Given data points Xii ∈ [N] containing a subset S of β N it inliers Xi 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 hatμ ∈ L close to μ. The recovery guarantees of the algorithm are analogous to the existing algorithms for the problem by Diakonikolas etal and Kothari etal. In an independent and concurrent work, Karmalkar etal citeKlivansKS19 also obtain an algorithm for list-decodable linear regression using the Sum-of-Squares SDP hierarchy.