mlsanityData to 7 Oct 2026

Streaming Algorithms for High-Dimensional Robust Statistics

arXiv 2204.12399 ↗First posted 26 Apr 2022cs.DS cs.LG math.STcited by 21

Not on the map. Why?

Abstract (arXiv)

We study high-dimensional robust statistics tasks in the streaming model. A recent line of work obtained computationally efficient algorithms for a range of high-dimensional robust estimation tasks. Unfortunately, all previous algorithms require storing the entire dataset, incurring memory at least quadratic in the dimension. In this work, we develop the first efficient streaming algorithms for high-dimensional robust statistics with near-optimal memory requirements (up to logarithmic factors). Our main result is for the task of high-dimensional robust mean estimation in (a strengthening of) Huber's contamination model. We give an efficient single-pass streaming algorithm for this task with near-optimal error guarantees and space complexity nearly-linear in the dimension. As a corollary, we obtain streaming algorithms with near-optimal space complexity for several more complex tasks, including robust covariance estimation, robust regression, and more generally robust stochastic optimization.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 31 of its 57 references that are in the map. First posted on arXiv 26 Apr 2022.

Builds on

31 of 57 references.

References · 31

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2018Spectral Signatures in Backdoor Attackscited by 457
  3. 2017Certified Defenses for Data Poisoning Attackscited by 288
  4. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  5. 2016Agnostic Estimation of Mean and Covariancecited by 131
  6. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  7. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  8. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  9. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  10. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  11. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  12. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
19 more
  1. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  2. 2020Outlier Robust Mean Estimation with Subgaussian Rates via Stabilitycited by 50
  3. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 49
  4. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  5. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  6. 2020Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingcited by 35
  7. 2018Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learningcited by 32
  8. 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
  9. 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
  10. 2019Faster Algorithms for High-Dimensional Robust Covariance Estimationcited by 28
  11. 2020Choosing the Sample with Lowest Loss makes SGD Robustcited by 26
  12. 2019Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filteringcited by 23
  13. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  14. 2020Online Robust Regression via SGD on the l1 losscited by 20
  15. 2020List-Decodable Mean Estimation in Nearly-PCA Timecited by 17
  16. 2021Outlier-Robust Learning of Ising Models Under Dobrushin's Conditioncited by 14
  17. 2021Outlier-Robust Sparse Estimation via Non-Convex Optimizationcited by 14
  18. 2021Heavy-tailed Streaming Statistical Estimationcited by 10
  19. 2016Robust Learning of Fixed-Structure Bayesian Networkscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 8; 2024: 7; 2025: 1; 2026: 3.

21 papers.

Sort:

  1. 2024How Does Unlabeled Data Provably Help Out-of-Distribution Detection?cited by 36
  2. 2022Online Prediction in Sub-linear Spacecited by 16
  3. 2022Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalitiescited by 11
  4. 2023Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraintscited by 10
  5. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  6. 2023On Differential Privacy and Adaptive Data Analysis with Bounded Spacecited by 9
  7. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
  8. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  9. 2023Geometry-Calibrated DRO: Combating Over-Pessimism with Free Energy Implicationscited by 5
  10. 2024Robust Distribution Learning with Local and Global Adversarial Corruptionscited by 5
  11. 2023Tight Memory-Regret Lower Bounds for Streaming Banditscited by 4
  12. 2023Robust Stochastic Optimization via Gradient Quantile Clippingcited by 3
9 more
  1. 2024Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensingcited by 2
  2. 2024Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Errorcited by 2
  3. 2024A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimationcited by 1
  4. 2025Distributionally Robust Optimization with Adversarial Data Contaminationcited by 1
  5. 2026Robust Learning with Optimal Errorcited by 1
  6. 2023Online Heavy-tailed Change-point detectioncited by 0
  7. 2024LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimizationcited by 0
  8. 2026High-Dimensional Gaussian Mean Estimation under Realizable Contaminationcited by 0
  9. 2026Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruptioncited by 0