Bagging Robustly Learns VC Classes with Linear Sample Complexity

This paper proves 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]. The 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). The algorithm computes RERMs on O(d⋆) independent bootstrap samples and outputs their majority-vote, where d⋆ denotes the dual VC dimension.

The proposed Algorithm 1 (Bagging Robust ERMs) works as follows:

• Input: Training set S = ((Xj, Yj))nj=1, confidence δ, and an RERMF oracle fb (2)

• Set N = O(d⋆ + log(1/δ)), and Jn = n/4,..., n − 1

• For each i = 1,..., N:

• Sample t uniformly from Jn

• Sample a bootstrap Si′ of t samples uniformly with replacement from S≤t = ((Xj, Yj))tj=1

• Run RERMF oracle fb on Si′, denoting its output predictor by fbSi′

• Output: The majority-vote predictor MAJ(fbS1′,..., fbSN′)

For any function class F with VC dimension d and dual VC dimension d⋆, any perturbation set U, any deterministic RERMF oracle fb, any distribution P over X × Y where inf f∈F RU(f; P) = 0, for every n ≥ 4 and every δ ∈ (0, 1), letting N = O(d⋆ + log(1/δ)), with probability 1 − δ over the random draw of a training dataset S ∼ P n and N bootstrap samples S1′..., SN′ ⊆ S:

RU(MAJ(fbS1′,..., fbSN′); P) = O(d/n + (1/n) log(1/δ))

There is an algorithm ALG so that for any class F with VC dimension d and dual VC dimension d⋆, any perturbation set U, any deterministic RERMF oracle fb, for any distribution P over X × Y, for every n ≥ 4 and every δ ∈ (0, 1), with probability 1 − δ over S ∼ P n and randomness of ALG, ALG makes at most O(d⋆(log(n) + log(1/δ))) calls to oracle fb and returns a predictor ĥS satisfying:

RU(ĥS; P) ≤ inf f∈F RU(f; P) + O(√(d/n log2(n) + (1/n) log(1/δ)))

For every integers d, m ≥ 1, there is an instance space X, a perturbation map U, and a finite collection of classes F = F where each class F has VC dimension d and dual VC dimension d⋆ = 2d+1 − 1 such that: For any (randomized) learning algorithm ALG making at most d⋆ − 1 calls to RERM, there exists a class F ∈ F and a distribution P over X × Y such that:

• P is robustly realizable, i.e., inf f∈F RU(f; P) = 0

• With probability at least 1/3 over S ∼ P m and randomness of ALG, RU(ALG(S); P) > 1/5

This proves that omega(d⋆) oracle queries to RERM are necessary regardless of the number of samples m provided to the algorithm.

The proof follows a substantially different route from Montasser, Hanneke, and Srebro [2019], avoiding sample compression arguments which incur a multiplicative factor of dual VC dimension d⋆ in sample complexity. Instead, it proceeds with a more direct leave-one-out analysis of bagging RERMs.

Distribution over RERMs (Lemma 1): The key lemma shows that in expectation over random test examples (X, Y) ∼ P, for any perturbation Z ∈ U(X), the fraction of RERMs fbS that misclassify Z is small:

E(X,Y)∼P [sup Z∈U(X) ES∼Pn [1 fbS(Z) ≠ Y]] = Õ(d/n)

This swaps the order of sup and inner expectation relative to the expected robust risk of a single RERM, which does not vanish to zero in general.

Bagging Leave-One-Out Analysis (Lemma 3): On a fixed robustly realizable sequence T, the aggregate vote over all RERMs can be expressed as BT(x):= ES∼Unif(T)n [fbS(x)] ∈ [−1, 1]. The leave-one-out robust error bound is:

(1/n) Σi=1n sup Zi∈U(Xi) 1 Yi · BT−i(Zi) ≤ γ ≤ C/(1−γ)2 · d/n

High-Probability Bound and Sparsification: The proof applies a suffix averaging technique due to Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [2023] to extend the bound to a high probability bound, then uses a sparsification technique due to Moran and Yehudayoff [2016] to approximate the intractable suffix-bagging predictor with N = O(d⋆) bootstrap samples.

The proof constructs a finite hard family (Fπ, Pπ,t) π,t and places a prior on it by choosing the target index T ∈ [K] uniformly and independently permuting N copies of a latent instance set. The lower bound rests on two distinct forms of hidden information:

1. Hidden target: Even after observing an arbitrarily large training sample and making fewer than d⋆ oracle calls, the learner is unlikely to have the zero-robust-risk target among the hypotheses returned by the oracle.

2. Dual-VC obstruction: The returned hypotheses reveal too little information to determine the orientation of a carefully chosen opposite-label pair on a uniformly random unseen block. Fewer than d⋆ = 2B + 1 returned hypotheses necessarily leaves an opposite-label pair that those hypotheses cannot distinguish.

• Characterization: The result implies that dim(F, U) ≤ O(d), positively resolving Conjecture 3 of Montasser, Hanneke, and Srebro [2022].

• Oracle efficiency: The oracle complexity (number of calls to RERM) is N = O(d⋆) with computational overhead of just O(d⋆n), a significant improvement over the prior improper algorithm which incurred oracle complexity of O(nd) and additional computational overhead of O(ndd⋆).

• Parallelizability: The bagging algorithm can be parallelized since the N bootstrap samples are independent, unlike the prior boosting-based approach which is inherently sequential.

• Reductions: Theorem 1 implies an improved polynomial attack-oracle complexity of O(poly(d, d⋆) · lit(F)) in the perfect attack oracle framework of Montasser, Hanneke, and Srebro [2021, Theorem 2] over the previously exponential bound O(exp(d, d⋆) · lit(F)).

• Bounded cardinality perturbation sets: Theorem 1 improves the sample complexity to O(d/ε) removing the log(k) factor entirely compared to Attias, Kontorovich, and Mansour [2022b].

• Adversarially robust learning with tolerance: Theorem 1 improves the sample complexity to O(d/ε) removing dependence on the ambient dimension p and α compared to Ashtiani, Pathak, and Urner [2025].

Improvements to AI Systems:

1. Robust Learning with Oracle Efficiency: AI systems can now achieve adversarial robustness with sample complexity linear in VC dimension (O(d/ε)) instead of exponential, and require only O(d⋆) calls to a robust ERM oracle rather than O(nd). This makes robust learning computationally feasible for large-scale models where oracle queries are expensive.

2. Parallelizable Robust Training: The bagging-based algorithm enables fully parallelizable robust training—each bootstrap sample can be processed independently on separate GPUs/TPUs. This is a direct improvement over sequential boosting approaches, reducing wall-clock training time for robust models by orders of magnitude in distributed settings.

3. Improved Attack-Oracle Efficiency: In security-critical AI systems using attack oracles (e.g., adversarial training with red-team models), the new result reduces oracle complexity from exponential O(exp(d,d⋆)·lit(F)) to polynomial O(poly(d,d⋆)·lit(F)). This allows AI systems to query adversarial attack oracles far more times within budget, leading to stronger certified defenses.

4. Sample-Efficient Robust Learning in High-Dimensional Spaces: For perturbation sets with bounded cardinality (e.g., discrete token perturbations in NLP), the sample complexity improves from O(d log(k)/ε) to O(d/ε), removing the logarithmic dependence on perturbation set size. This enables robust NLP systems to train effectively with fewer labeled examples, especially for large token vocabularies.

5. Robust Learning with Tolerance Constraints: In applications with tolerance requirements (e.g., medical diagnosis with allowable error margins), the improved bound removes dependence on ambient input dimension p and tolerance parameter α. This makes robust learning practical for high-dimensional data (e.g., genomic sequences, 3D point clouds) where previous bounds were prohibitively loose.

6. Theoretical Guarantees for Ensemble Robustness: The majority-vote over robust ERMs provides provable robustness guarantees that scale linearly with model complexity (VC dimension). This gives AI practitioners a principled method to construct robust ensembles with known worst-case performance, rather than relying on heuristic ensemble methods without guarantees.

7. Lower-Bound-Aware Algorithm Design: The proven lower bound of Ω(d⋆) oracle queries informs AI system designers about fundamental limits—any robust learning algorithm must make at least d⋆ oracle calls. This prevents over-engineering and guides resource allocation in robust AI pipelines.

8. Improved Robust Learning in Agnostic Settings: The agnostic bound O(√(d/n log2(n))) enables robust learning even when the optimal robust classifier is not in the hypothesis class. This is critical for real-world AI systems where the true data-generating process rarely matches model assumptions, allowing deployment in noisy, adversarial environments with finite-sample guarantees.

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 (d) calls to an RERM oracle, even when given arbitrarily many training examples.