mlsanityData to 14 Oct 2026

Sparse Mean Estimation in Adversarial Settings via Incremental Learning

arXiv 2305.15276 ↗First posted 24 May 2023cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the problem of sparse mean estimation under adversarial corruptions, where the goal is to estimate the k-sparse mean of a heavy-tailed distribution from samples contaminated by adversarial noise. Existing methods face two key limitations: they require prior knowledge of the sparsity level k and scale poorly to high-dimensional settings. We propose a simple and scalable estimator that addresses both challenges. Specifically, it learns the k-sparse mean without knowing k in advance and operates in near-linear time and memory with respect to the ambient dimension. Under a moderate signal-to-noise ratio, our method achieves the optimal statistical rate, matching the information-theoretic lower bound. Extensive simulations corroborate our theoretical guarantees. At the heart of our approach is an incremental learning phenomenon: we show that a basic subgradient method applied to a nonconvex two-layer formulation with an ℓ1-loss can incrementally learn the k nonzero components of the true mean while suppressing the rest. More broadly, our work is the first to reveal the incremental learning phenomenon of the subgradient method in the presence of heavy-tailed distributions and adversarial corruption.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 31 of its 57 references that are in the map. First posted on arXiv 24 May 2023.

Builds on

31 of 57 references.

References · 31

  1. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  2. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  3. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 150
  4. 2016Agnostic Estimation of Mean and Covariancecited by 131
  5. 2019Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networkscited by 124
  6. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  7. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 101
  8. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  9. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  10. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  11. 2019The Implicit Bias of Depth: How Incremental Learning Drives Generalizationcited by 64
  12. 2020The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networkscited by 58
19 more
  1. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 51
  2. 2020Outlier Robust Mean Estimation with Subgaussian Rates via Stabilitycited by 50
  3. 2017Sub-Gaussian estimators of the mean of a random vectorcited by 47
  4. 2022Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Datacited by 46
  5. 2021Implicit Regularization in Tensor Factorizationcited by 44
  6. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  7. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 42
  8. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  9. 2021Implicit Sparse Regularization: The Impact of Depth and Early Stoppingcited by 30
  10. 2019Faster Algorithms for High-Dimensional Robust Covariance Estimationcited by 28
  11. 2022Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networkscited by 27
  12. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 24
  13. 2019Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filteringcited by 23
  14. 2020High-Dimensional Robust Mean Estimation via Gradient Descentcited by 16
  15. 2021Outlier-Robust Sparse Estimation via Non-Convex Optimizationcited by 14
  16. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  17. 2019Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversariescited by 5
  18. 2020Robust subgaussian estimation with VC-dimensioncited by 4
  19. 2022Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decompositioncited by 4

Built on by

Not cited yet.