Pith. sign in

REVIEW 5 cited by

Outlier-robust moment-estimation via sum-of-squares

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1711.11581 v2 pith:DUQB34LH submitted 2017-11-30 cs.DS cs.LGstat.ML

Pravesh K. Kothari , David Steurer This is my paper · ORCID
classification cs.DScs.LGstat.ML
keywords algorithmsdistributionsguaranteesdistributionimprovedmomentsoutlierspresence
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in recent works of Diakonikolas et al, Lai et al, and Charikar et al. We also show that the guarantees of our algorithms match information-theoretic lower-bounds for the class of distributions we consider. These improved guarantees allow us to give improved algorithms for independent component analysis and learning mixtures of Gaussians in the presence of outliers. Our algorithms are based on a standard sum-of-squares relaxation of the following conceptually-simple optimization problem: Among all distributions whose moments are bounded in the same way as for the unknown distribution, find the one that is closest in statistical distance to the empirical distribution of the adversarially-corrupted sample.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Exact Worst-Case Tail Probability under Bounded Kurtosis

    math.PR 2026-07 conditional novelty 8.0 of 10

    The worst-case one-sided tail probability under mean 0, variance 1, and fourth moment ≤ κ is a four-regime map with closed forms on three regimes and an algebraic system on the fourth, plus a one-sided/two-sided colla...

  2. Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians

    cs.DS 2025-02 conditional novelty 8.0 of 10

    First polynomial-time, nearly optimal robust scatter and covariance estimation for general elliptical distributions, with O(epsilon log(1/epsilon)) error under strong contamination.

  3. SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More

    cs.DS 2024-12 conditional novelty 8.0 of 10

    New SoS certificates certify nontrivial sparse singular values of random Gaussian and subgaussian matrices whenever n ≫ η²d^(2+ε), nearly matching low-degree and SQ lower bounds and yielding near-optimal robust estima...

  4. Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures

    cs.DS 2024-11 conditional novelty 8.0 of 10

    A sum-of-squares based dimension reduction subroutine gives d^{O(1)}-time clustering for centered non-spherical Gaussian mixtures and d^{O(log w_min^{-1})} for identical-covariance mixtures, improving on d^{O(k)} algorithms.

  5. Active Learning on Adversarially Corrupted Graphs

    cs.LG 2026-07 accept novelty 7.0 of 10

    A poly-time active learning algorithm approximately recovers adversarially corrupted vertices with query complexity polynomial in the adversary's neighborhood budget and the clean graph's vertex expansion.

Pith tools