Search papers, labs, and topics across Lattice.
This paper establishes that VC classes can be learned robustly against adversarial examples with a sample complexity that scales linearly with the VC dimension, a significant improvement over previous results. The authors achieve this using a straightforward improper algorithm that merges bagging techniques with robust empirical risk minimization, demonstrating the effectiveness of majority voting from multiple bootstrap samples. Additionally, they provide a lower bound that confirms the necessity of this sample complexity in the oracle model, highlighting the fundamental limits of learning in this context.
Achieving adversarial robustness in VC classes now requires only linear sample complexity, revolutionizing our understanding of learning under attack.
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.
