Certifiable Robust Statistics via Sum of Squares

This direction is split into other directions: certifiable hypercontractivity. Its last version stays readable and citable here.

Version 1 of 133 papers44 conceptsfrozen 2026-10-04

In high-dimensional statistics, a small fraction of adversarial outliers can completely compromise traditional estimators. While we have long known that robust estimation is information-theoretically possible, the challenge has been finding algorithms that are both computationally efficient and accurate in high dimensions.

A powerful research direction has emerged to solve this by linking robustness to algorithmic certifiability. By using the Sum-of-Squares (SoS) optimization framework, researchers have shown that if a distribution’s stability can be "proven" via low-degree polynomials, we can design algorithms that remain resilient even when the majority of the data is noise.

The Gap Between Existence and Certifiability

To estimate the mean of a distribution robustly, the distribution must be "stable"—its mean and covariance shouldn't change drastically if you remove a small fraction of points. For many distributions, like Gaussians, we know this property exists. However, knowing a property exists is not enough for an algorithm to exploit it.

David Steurer and Pravesh K. Kothari in Outlier-robust moment-estimation via sum-of-squares reframed the problem: the feasibility of robust estimation depends on whether these stability properties are certifiable.

A property is certifiable if its defining inequality can be established through a low-degree algebraic proof (a sum of squares of polynomials). If such a proof exists, the SoS hierarchy—a sequence of increasingly powerful semidefinite programming relaxations—can efficiently find a "pseudo-distribution" that satisfies these properties, effectively filtering out outliers that fail the "proof."

Certifiable Hypercontractivity

A central concept in this framework is hypercontractivity. A distribution is hypercontractive if its higher-order moments are bounded by its lower-order moments (e.g., the 4th moment is at most a constant times the square of the 2nd moment).

In Efficient Algorithms for Outlier-Robust Regression, Adam Klivans, Pravesh K. Kothari, and Raghu Meka demonstrate why this matters for robustness. If a distribution is certifiably hypercontractive, any model that fits a large enough subset of the (possibly corrupted) data is guaranteed to generalize to the uncorrupted distribution. The SoS algorithm doesn't need to identify which points are outliers; it simply searches for a subset that satisfies the "proof" of hypercontractivity. Since outliers are unlikely to satisfy this structured moment growth, they are naturally ignored.

This principle was extended to even more extreme cases by Prasad Raghavendra and Morris Yau in List Decodable Subspace Recovery. They used certifiable resilience to recover signals even when outliers make up the vast majority (e.g., 90%) of the dataset.

The Subgaussian Breakthrough

For years, a major open question was whether all subgaussian distributions—those with tails that decay at least as fast as a Gaussian—were SoS-certifiable. Subgaussianity is defined by tail behavior, but SoS requires polynomial proofs about moments.

Ilias Diakonikolas, Samuel B. Hopkins, and Stefan Tiegel resolved this in SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications. They proved that all subgaussian distributions are fundamentally equivalent to SoS-certifiable distributions. This means that the entire class of subgaussian data—not just Gaussians—can be handled with the same formal guarantees using low-degree polynomial certificates.

Beyond Bounded Moments

The SoS framework has proven surprisingly flexible, reaching into domains where traditional moments don't even exist. Gleb Novikov, David Steurer, and Stefan Tiegel showed in Robust Mean Estimation Without Moments for Symmetric Distributions that one can robustly estimate the location of heavy-tailed distributions (like the Cauchy distribution).

Instead of certifying the moments of the raw data, they use SoS to certify that transformed versions of the data (using techniques like Huber-loss or spatial signs) satisfy the necessary concentration properties. This allows for dimension-independent error rates even when the variance is infinite, as further explored by Gleb Novikov in Robust Scatter Matrix Estimation for Elliptical Distributions in Polynomial Time.

Why It Works: The Power of the Certificate

The intuition behind this entire research direction is a shift from estimation to verification.

  1. The Adversary's Constraint: If an adversary wants to corrupt a dataset and fool an estimator, they must provide "fake" data that still looks "clean" to the algorithm.
  2. The Algorithm's Defense: By using SoS, the algorithm demands a "certificate of cleanliness" (a low-degree proof of stability or hypercontractivity).
  3. The Result: If the original distribution is certifiably stable, the only way an adversary can fool the algorithm is by providing outliers that also satisfy that certificate. But if the outliers satisfy the certificate, they must also be "stable" and cannot pull the mean or covariance very far.

This "tester-learner" perspective, as described by Aravind Gollakota and Adam R. Klivans in Tester-Learners for Halfspaces: Universal Algorithms, ensures that we either get a correct answer or a clear signal that the data is too irregular to be trusted.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_certifiable_robust_statistics_via_sum_of_09cb4b7a,
  title = {Certifiable Robust Statistics via Sum of Squares},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/certifiable-robust-statistics-via-sum-of-squares/rdr_09cb4b7aa34a4980bb6e2d9c6b12d839},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_certifiable_robust_statistics_via_sum_of_09cb4b7a_v1,
  title = {Certifiable Robust Statistics via Sum of Squares},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/certifiable-robust-statistics-via-sum-of-squares/rdr_09cb4b7aa34a4980bb6e2d9c6b12d839/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}