List Decodable Estimation in Majority Outlier Regimes

29 concepts20 papers1 proposal

Traditional robust statistics operates under a comforting assumption: the majority of the data is clean. If a dataset contains 10% outliers, standard robust estimators can locate the dominant statistical pattern and discard the noise. But what happens when the situation is inverted? Imagine a dataset where only a small fraction—say, $\alpha = 10\%$—of the points are drawn from the true distribution, while the remaining 90% are arbitrary, potentially adversarial outliers.

In this majority-outlier regime, unique parameter recovery is information-theoretically impossible. As noted by Sushrut Karmalkar et al., an intelligent adversary can arrange the overwhelming majority of outliers to mimic multiple alternative, valid-looking distributions. Because the noise can perfectly simulate the structure of a genuine signal, no algorithm can distinguish the "true" model from a well-crafted adversarial cluster using a single point estimate. This fundamental barrier forces a shift in how we define success in robust learning.

The List-Decoding Paradigm

To bypass this symmetry barrier, we must relax our expectations. Instead of demanding a single unique answer, we design algorithms that output a small, finite list of candidate parameters. The guarantee shifts: we no longer promise that our single output is correct, but rather that at least one candidate in the returned list is close to the ground truth.

[Raw Data: 90% Outliers, 10% Inliers] 
                 │
                 ▼
    ┌─────────────────────────┐
    │ List-Decodable Algorithm│
    └─────────────────────────┘
                 │
      ┌──────────┼──────────┐
      ▼          ▼          ▼
┌──────────┐┌──────────┐┌──────────┐
│Candidate ││Candidate ││Candidate │  ──► (One of these is guaranteed
│  Model 1 ││  Model 2 ││  Model 3 │       to be the true model)
└──────────┘└──────────┘└──────────┘

This framework, introduced to algorithmic robust statistics by Jacob Steinhardt et al., borrows its name from coding theory: list-decodable learning. By allowing the output to be a set of hypotheses, list-decodable estimation makes it possible to extract accurate parameters even when the fraction of reliable data is significantly below 50%.

Why It Works: Certifiable Resilience

How can an algorithm isolate a tiny fraction of signal buried under a mountain of adversarial noise? The key intuition relies on the concept of resilience. As established by Jacob Steinhardt et al., a dataset or distribution is resilient if the evaluation of its properties (such as the mean) on any sufficiently large subset does not deviate too far from the true population parameters.

While an adversary can easily manipulate the global mean of the dataset, they cannot easily destroy the internal consistency of the true inlier subset. If the true data distribution possesses natural structural properties—like sub-Gaussianity or anti-concentration—the inliers will form a tightly knit cluster in a higher-order statistical sense.

To operationalize this intuition, algorithms often leverage the Sum-of-Squares (SoS) optimization framework or semidefinite programming (SDP). As shown by Prasad Raghavendra et al., these frameworks allow us to search for "certifiably resilient" subsets. The algorithm systematically searches for any subset of data points (of size $\alpha$) that exhibits the expected statistical properties of clean data. When it finds one, it computes a candidate parameter, records it, and then penalizes or removes those data points to uncover the next valid hypothesis.

Managing the List Size and Computational Complexity

A primary challenge in list-decodable estimation is ensuring that the list of candidates remains small and independent of the data's dimensionality. Ideally, the list size should scale only with the inverse of the clean data fraction ($O(1/\alpha)$). Ilias Diakonikolas et al. demonstrate that by analyzing higher-order moments of the data and applying cross-candidate consistency tests during iterative refinement, algorithms can maintain a candidate list size that strictly matches the information-theoretic minimum.

While early list-decoding algorithms relied on computationally heavy SoS hierarchies, recent work focuses on making these methods practical:

  • Spectral Methods: To avoid the high computational cost of SDPs, Ilias Diakonikolas et al. developed purely spectral, polynomial-time algorithms for covariance estimation, drastically speeding up parameter recovery in high dimensions.
  • Batching Structures: Abhimanyu Das et al. showed that if data arrives in small groups or batches rather than isolated points, the sample complexity can scale nearly linearly with the dimension, bypassing previous computational bottlenecks.
  • Nonconvex Optimization: By designing descent-style algorithms on carefully engineered nonconvex landscapes, Yeshwanth Cherapanamjeri et al. achieved list-decodable mean estimation in nearly linear time.

Broadening the Horizon

The list-decoding paradigm has expanded from basic mean estimation to a wide array of high-dimensional problems where unique recovery fails.

Regression

In linear regression where the majority of observations are garbage, Ilias Diakonikolas et al. mapped out the statistical query lower bounds, proving the necessity of the list-decodable approach. While unique recovery is possible up to the 50% outlier limit for multivariate polynomials (Arnab Bhattacharyya et al.), crossing into the majority-outlier regime requires list-decodable regression contracts to guarantee geometric model recovery (Luca Carlone).

Mixture Models

List decoding also provides a powerful meta-algorithm for learning mixture distributions. When attempting to learn a mixture of multiple sub-populations, one can treat the target component as the "signal" and all other components as adversarial noise. As demonstrated by Ishaq Aden-Ali et al. and Daniil Dmitriev et al., this perspective allows algorithms to disentangle complex, overlapping distributions and recover accurate parameters for every individual group, even when small sub-populations are entirely overwhelmed by noise.

Key Foundational Work

Learning from Untrusted Data (2016) — contributed 2 concept elements to this direction.
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers (2017) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 20 papers
  2. Version 1 · 2026-10-04 · 31 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_list_decodable_estimation_33aab020,
  title = {list-decodable estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/list-decodable-estimation/rdr_33aab020c8aa4eb683817a77f9d138f9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_list_decodable_estimation_33aab020_v2,
  title = {list-decodable estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/list-decodable-estimation/rdr_33aab020c8aa4eb683817a77f9d138f9/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake