mlsanityData to 14 Oct 2026

Bagging Robustly Learns VC Classes with Linear Sample Complexity

arXiv 2608.13514 ↗First posted 13 Aug 2026stat.ML cs.DS cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension d, providing an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019). Remarkably, this result is achieved with a simple improper algorithm that combines the classic heuristic bagging (bootstrap aggregation) of Breiman (1996) with robust empirical risk minimization (RERM). Our algorithm computes RERMs on O(d^star) independent bootstrap samples and outputs their majority vote, where d^star denotes the dual VC dimension. We complement this result with a lower bound showing that this is unavoidable: in general, any learner in this oracle model requires Omega(d^star) calls to an RERM oracle, even when given arbitrarily many training examples.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 44 of its 58 references that are in the map. First posted on arXiv 13 Aug 2026.

Builds on

44 of 58 references.

References · 44

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  3. 2013Intriguing properties of neural networkscited by 5,155
  4. 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,517
  5. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,340
  6. 2017Evasion Attacks against Machine Learning at Test Timecited by 689
  7. 2019Unlabeled Data Improves Adversarial Robustnesscited by 416
  8. 2018Adversarially Robust Generalization Requires More Datacited by 318
  9. 2019Are Labels Required for Improving Adversarial Robustness?cited by 163
  10. 2018Rademacher Complexity for Adversarially Robust Generalizationcited by 132
  11. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  12. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
32 more
  1. 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
  2. 2018Adversarial examples from computational constraintscited by 80
  3. 2015Sample compression schemes for VC classescited by 47
  4. 2020Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examplescited by 44
  5. 2022Bagging is an Optimal PAC Learnercited by 34
  6. 2023Optimal PAC Bounds Without Uniform Convergencecited by 33
  7. 2020Reducing Adversarially Robust Learning to Non-Robust PAC Learningcited by 28
  8. 2023Testable Learning with Distribution Shiftcited by 25
  9. 2021Adversarially Robust Learning with Unknown Perturbation Setscited by 24
  10. 2018Improved Generalization Bounds for Adversarially Robust Learningcited by 22
  11. 2020Efficiently Learning Adversarially Robust Halfspaces with Noisecited by 22
  12. 2022Robustly-reliable learners under poisoning attackscited by 20
  13. 2022Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterizationcited by 17
  14. 2024Majority-of-Three: The Simplest Optimal Learner?cited by 17
  15. 2021Efficient Learning with Arbitrary Covariate Shiftcited by 15
  16. 2021Robust learning under clean-label attackcited by 15
  17. 2022On Optimal Learning Under Targeted Data Poisoningcited by 14
  18. 2022A Characterization of Semi-Supervised Adversarially-Robust PAC Learnabilitycited by 13
  19. 2023Adversarial Resilience in Sequential Prediction via Abstentioncited by 11
  20. 2022Adversarially Robust Learning with Tolerancecited by 9
  21. 2022Adversarially Robust PAC Learnability of Real-Valued Functionscited by 8
  22. 2023The Impossibility of Parallelizing Boostingcited by 7
  23. 2022Robust Empirical Risk Minimization with Tolerancecited by 6
  24. 2025Is nasty noise actually harder than malicious noise?cited by 4
  25. 2026Learning with Monotone Adversarial Corruptionscited by 4
  26. 2026Majority-of-Three is Optimalcited by 4
  27. 2025Simplifying Adversarially Robust PAC Learning with Tolerancecited by 3
  28. 2026Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Boundscited by 3
  29. 2026Optimal Rates for Learning with Monotone Adversariescited by 3
  30. 2023Agnostic Multi-Robust Learning Using ERMcited by 2
  31. 2026Distribution-Free Sequential Prediction with Abstentionscited by 1
  32. 2026Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shiftcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Adversarially Robust PAC Learning with Optimal VC Ratescited by 0