Bagging Robustly Learns VC Classes with Linear Sample Complexity
2026-08-13 • Data Structures and Algorithms
Data Structures and AlgorithmsMachine Learning
AI summaryⓘ
The authors study how to train machine learning models that resist tricky, adversarial test inputs. They show it's possible to do this efficiently for a broad class of models, with the number of training samples needed growing only linearly with a complexity measure called the VC dimension. Their method cleverly uses a simple technique called bagging combined with robust optimization. They also prove you can't do much better in terms of efficiency, since any method must perform a certain number of these optimizations based on another complexity measure, the dual VC dimension.
VC dimensionadversarial examplesrobust learningsample complexitybaggingbootstrap aggregationrobust empirical risk minimizationdual VC dimensionmachine learning theory
Authors
Omar Montasser
Abstract
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 $Ω(d^\star)$ calls to an RERM oracle, even when given arbitrarily many training examples.