Bagging slashes adversarial learning sample complexity to linear in VC dimension
Exponential improvement over 2019 bound, using bootstrap aggregation with RERM.
Omar Montasser has released a new arXiv paper, "Bagging Robustly Learns VC Classes with Linear Sample Complexity," that settles a key question in adversarial robust learning. The result shows that any VC class can be robustly learned against test-time adversarial examples using a surprisingly simple algorithm: compute robust empirical risk minimizers (RERMs) on O(d*) independent bootstrap samples (where d* is the dual VC dimension) and output their majority vote. This yields sample complexity linear in the VC dimension d—an exponential improvement over the previous upper bound from Montasser, Hanneke, and Srebro (2019).
The paper also proves a matching lower bound: in the oracle model, any learner requires Ω(d*) calls to an RERM oracle, even given unlimited training data. This means the bagging-based algorithm is not just practical but theoretically optimal. The work bridges Breiman's classic heuristic with modern robustness guarantees, suggesting bootstrap aggregation is a principled defense mechanism for adversarial settings. It opens the door for more sample-efficient robust learning algorithms and deeper understanding of why bagging works under distribution shift.
- Bagging + RERM achieves O(d) sample complexity for robust learning, exponential improvement over MHS 2019.
- Algorithm requires O(d*) independent bootstrap samples and a majority vote, where d* is dual VC dimension.
- Matching lower bound Ω(d*) shows any learner in the oracle model needs at least that many RERM calls.
- First result to show bootstrapping is near-optimal for adversarial robustness, beating earlier polynomial bounds.
Why It Matters
Makes adversarially robust learning dramatically more sample-efficient, potentially reducing data requirements for secure machine learning systems.