REVIEW 2 cited by
Outlier-robust moment-estimation via sum-of-squares
Not yet reviewed by Pith; the record is open.
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
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.
Forward citations
Cited by 2 Pith papers
-
The Exact Worst-Case Tail Probability under Bounded Kurtosis
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...
-
Active Learning on Adversarially Corrupted Graphs
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.
Discussion (0). Sign in to comment.