Bagging Robustly Learns VC Classes with Linear Sample Complexity

Forum topic · 小凯 · 2026-08-15

Summary

This paper revisits adversarially robust learning of predictors at test time. The authors prove that VC classes can be robustly learned with sample complexity linear in the VC dimension d, delivering an exponential improvement over the prior upper bound of Montasser, Hanneke, and Srebro (2019). The result is achieved by a simple improper algorithm that combines Breiman's classic bagging (bootstrap aggregation, 1996) with robust empirical risk minimization (RERM). The algorithm computes RERMs on O(d*) independent bootstrap samples and returns a majority vote, where d* denotes the dual VC dimension. A matching lower bound shows the result is tight: any learner in this oracle model requires Omega(d*) calls to an RERM oracle, even given arbitrarily many training examples. The work clarifies the statistical and computational role of bagging in adversarial robustness and tightens the sample complexity landscape for robust PAC learning.

Paper Overview

Field: Machine Learning (ML)
Author: Omar Montasser
Posted: 2026-08-13
arXiv: 2608.13514

Chinese Summary (Translated)

We revisit the problem of learning predictors that are robust to adversarial examples at test time. We prove that VC classes can be adversarially robustly learned 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 by a simple improper algorithm that combines Breiman's classic bagging (bootstrap aggregation, 1996) with robust empirical risk minimization (RERM). The algorithm computes RERMs on $O(d^*)$ independent bootstrap samples and outputs their majority vote, where $d^*$ 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^*)$ calls to an RERM oracle, even when given arbitrarily many training examples.

Original 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^*)$ independent bootstrap samples and outputs their majority vote, where $d^*$ 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^*)$ calls to an RERM oracle, even when given arbitrarily many training examples.

Key Points

Setting: Adversarially robust PAC learning of VC classes under a strong test-time adversary.
Upper bound: Sample complexity of $O(d)$, an exponential improvement over prior bounds.
Algorithm: Bagging (Breiman, 1996) + RERM — improper, simple, and oracle-based.
Oracle budget: $O(d^*)$ RERM calls on independent bootstrap samples; final predictor is a majority vote, where $d^*$ is the dual VC dimension.
Lower bound: $\Omega(d^*)$ RERM oracle calls are necessary in general, even with unlimited training data, establishing tightness of the upper bound within the oracle model.
Takeaway: Bagging is not merely a heuristic — it provably closes the gap between standard and robust sample complexity for VC classes.