Not all data are created Equal: Robust Mean Estimation from Heterogeneous and Unreliable Users
summary
Model where N users each send n samples, an epsilon fraction of users are fully adversarial and the remaining users are “good” but lie within a proximity alpha (either each good batch has mean-shift sqrt(alpha) or an alpha-fraction of samples per good batch are corrupted). Two Sum-of-Squares algorithms produce a minimax-optimal error O(sqrt(epsilon/n) + sqrt(d/(nN)) + sqrt(alpha)), exploiting internal averaging across batches so adversarial impact scales by 1/sqrt(n), with polynomial (but high-degree) runtime.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:18Heterogeneous data sources
- 4:26Untrusted batch model
- 9:34Mean shift and error bounds
- 17:01Double corruption model
- 22:14Robust mean estimation
- 27:19Sum of squares method
- 35:10Truncation for mean shift
- 40:15Two-step SOS for corruption
- 44:10Summary and Q&A
related talks
52mMechanisms for Honest Data Sharing under Competition
31mRealizing Robustness
53mOptimality in Locally Private Estimation and Learning
53mDesigning Robust Learners
01h 00mAlgorithmic High Dimensional Robust Statistics I
48mComputational-Statistical Tradeoffs in Robust High-Dimensional Estimation
39mAbove Average-Case Analysis?
21mDimension-free Private Mean Estimation for Anisotropic Distributions