📊 statistics

Bagging Robustly Learns VC Classes with Linear Sample Complexity

This paper demonstrates that bagging combined with robust empirical risk minimization achieves adversarial robust learning for VC classes with linear sample complexity in the VC dimension, significantly improving upon previous bounds while establishing a matching lower bound on the required oracle calls.

Original authors: Omar Montasser

Published 2026-08-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Omar Montasser

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to recognize cats in photos. You show it thousands of pictures, and it learns to spot whiskers and pointy ears. But what if someone sneaks a tiny, almost invisible sticker onto the cat's nose? To a human, the cat still looks like a cat, but the robot suddenly thinks it's a toaster. This is the world of "adversarial examples"—tiny, tricky changes that fool smart machines. Scientists have been trying to build robots that can ignore these tricks, but there's a catch: the more complex the robot's brain (its "function class"), the harder it is to teach it to be tough against these tricks without needing a million examples.

To understand the problem, think of "learning" as finding the best rulebook in a giant library. The "VC dimension" is just a fancy way of counting how many different rules the library has. If the library is huge, you usually need a lot of examples to find the right rule. But when adversarial tricks are involved, the old methods suggested you might need an astronomical number of examples—so many that it felt impossible for complex rules. Another key idea here is the "oracle," which is like a magical black box that can instantly solve a specific, hard puzzle for you. The big question researchers have been asking is: Can we build a robot that learns to be robust (trick-proof) using a reasonable number of examples and by asking our magical black box only a few times?

This paper, titled "Bagging Robustly Learns VC Classes with Linear Sample Complexity," answers that question with a resounding "Yes, but with a twist." The author, who leads the work, proves that you don't need an impossible number of examples to teach a machine to be robust. In fact, they show that for many types of learning problems, the number of examples you need grows in a simple, straight-line relationship with the complexity of the rules (the VC dimension). This is a massive improvement over previous ideas, which suggested the number of examples would explode exponentially.

The secret sauce in their recipe is a clever combination of two old ideas: "Bagging" and "Robust Training." Imagine you have a team of detectives trying to solve a case. Instead of relying on just one detective, you hire many. You give each detective a slightly different, random selection of clues (a "bootstrap sample") and ask them to solve the case using a special "robust" method that ignores the tricky fake clues. Then, you let the detectives vote on the final answer. If most of them agree, you go with that. The paper proves that if you hire enough of these detectives (specifically, a number related to the "dual VC dimension," which is a measure of how complex the rules are), you can find the right answer with very few examples.

However, the paper also draws a hard line in the sand. While they found a way to do this efficiently, they also proved that you cannot do it any better than a certain limit. They showed that no matter how many examples you give the robot, if you ask the magical black box (the oracle) fewer than a specific number of times (related to the dual VC dimension), the robot will fail. It's like trying to solve a puzzle with only half the pieces; no amount of staring at the picture on the box will help you finish it. The author proved that this limit is unavoidable.

In short, this paper provides a simple, practical recipe for making AI robust against tricks. It shows that by using a "voting team" approach, we can learn complex rules with a manageable number of examples. But it also warns us that there is a fundamental cost: we must ask our helper tools a specific minimum number of times, or the learning simply won't work. This moves us from thinking robust learning is impossible for complex systems to knowing exactly how to build it and what the minimum requirements are.

Technical Summary: Bagging Robustly Learns VC Classes with Linear Sample Complexity

Problem Statement

The paper addresses the fundamental challenge of learning predictors that are robust to adversarial examples at test-time. Given an instance space $\mathcal{X}$ , a label space $\mathcal{Y} = \{-1, 1\}$ , and an adversary defined by a perturbation map $U: \mathcal{X} \to 2^\mathcal{X}$ , the goal is to learn a predictor $\hat{f}$ that minimizes the population robust risk:
$R_U(\hat{f}; P) = \mathbb{E}_{(X,Y) \sim P} \left[ \sup_{Z \in U(X)} \mathbb{1}\{\hat{f}(Z) \neq Y\} \right]$
where $P$ is an unknown distribution over $\mathcal{X} \times \mathcal{Y}$ .

The paper focuses on the learnability of function classes $\mathcal{F}$ with finite Vapnik-Chervonenkis (VC) dimension $d$ . Prior work established that while VC classes are learnable in the standard PAC setting, adversarially robust learning faces significant hurdles. Specifically, Montasser, Hanneke, and Srebro [2019] showed that:

Proper learning (constraining the output to be in $\mathcal{F}$ ) can fail even for classes with VC dimension 1.
Improper learning is possible, but the best known upper bound on sample complexity was exponential in $d$ .
Existing improper algorithms are computationally inefficient, requiring $O(nd)$ calls to a Robust Empirical Risk Minimization (RERM) oracle with prohibitive overhead.

The central question is whether one can design algorithms that are both sample-efficient (linear in $d$ ) and oracle-efficient (few calls to RERM) for adversarially robust learning.

Methodology

The author proposes a simple improper learning algorithm that combines Bagging (Bootstrap Aggregation) with Robust Empirical Risk Minimization (RERM).

The Algorithm (Bagging Robust ERMs)

Given a training set $S$ of size $n$ , a confidence parameter $\delta$ , and an RERM oracle $\hat{f}$ :

Set the number of bootstrap samples $N = O(d^\star + \log(1/\delta))$ , where $d^\star$ is the dual VC dimension of the class $\mathcal{F}$ .
For each $i \in \{1, \dots, N\}$ $i \in {1, \dots, N}$ :
- Select a random size $t$ from a specific range $J_n = \{n/4, \dots, n-1\}$ .
- Sample a bootstrap dataset $S'_i$ of size $t$ uniformly with replacement from the prefix of $S$ of length $t$ .
- Run the RERM oracle on $S'_i$ to obtain a predictor $\hat{f}_{S'_i} \in \mathcal{F}$ .
Output the majority vote of the $N$ predictors: $\text{MAJ}(\hat{f}_{S'_1}, \dots, \hat{f}_{S'_N})$ .

Theoretical Approach

The analysis diverges from previous sample-compression arguments. Instead, it employs a leave-one-out analysis tailored to the robust risk:

Distribution over RERMs: The author analyzes the distribution of errors made by RERMs trained on random subsets. They prove that for a random test example $(X, Y)$ and any perturbation $Z \in U(X)$ , the fraction of RERMs that misclassify $Z$ is small in expectation ( $\tilde{O}(d/n)$ ).
Leave-One-Out Bound: By applying this expectation to an empirical distribution, they establish a bound on the robust risk of the "full bagging" predictor (an idealized average over all possible bootstraps).
Sparsification: Since the full bagging predictor is intractable, the author uses a sparsification technique (Moran and Yehudayoff [2016]) to approximate the aggregate vote using only $N = O(d^\star)$ independent bootstrap samples. This step links the oracle complexity directly to the dual VC dimension $d^\star$ .

Key Contributions and Results

1. Upper Bound: Linear Sample Complexity

The primary result (Theorem 1) establishes that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension $d$ .

Sample Complexity: $O(d/\epsilon + \frac{1}{\epsilon}\log(1/\delta))$ . This provides an exponential improvement over the previous $O(\exp(d))$ bound.
Oracle Complexity: The algorithm makes $N = O(d^\star)$ calls to the RERM oracle.
Computational Efficiency: The algorithm is parallelizable (unlike previous boosting-based approaches) and incurs only $O(d^\star n)$ computational overhead.
Agnostic Setting: By combining this realizable result with a reduction from the agnostic setting (Montasser et al. [2019]), the author derives an agnostic learner with sample complexity $\tilde{O}(\sqrt{d/n})$ and oracle complexity $O(d^\star \log n)$ .

2. Lower Bound: Necessity of Dual VC Dimension

The paper proves that the dependence on the dual VC dimension $d^\star$ in the oracle complexity is unavoidable (Theorem 2).

Result: There exist classes with VC dimension $d$ and dual VC dimension $d^\star = 2^{d+1}-1$ such that any algorithm making fewer than $d^\star - 1$ calls to an RERM oracle fails to learn robustly, regardless of the number of training samples provided.
Implication: Unlike classical PAC learning where $O(\log n)$ or constant ERM calls suffice, adversarially robust learning inherently requires $\Omega(d^\star)$ oracle queries. This highlights a fundamental separation between standard and robust learning complexity.

3. Technical Characterization

The results imply that the refined complexity measure $\dim(\mathcal{F}, U)$ proposed by Montasser, Hanneke, and Srebro [2022] is bounded by the VC dimension $d$ , resolving a conjecture that this measure could be significantly larger.

Significance and Claims

The paper claims to provide a "recipe" for computationally efficient robust PAC learning. By demonstrating that a simple bagging heuristic combined with RERM achieves optimal sample complexity, the work bridges the gap between theoretical robustness and practical algorithmic efficiency.

Key claims regarding the paper's contribution include:

Exponential Improvement: Moving from exponential to linear sample complexity in $d$ .
Oracle Efficiency: Reducing oracle calls from $O(nd)$ to $O(d^\star)$ , making the approach feasible for classes where RERM is computationally tractable.
Fundamental Limit: Establishing that the dual VC dimension is the correct barrier for oracle efficiency in robust learning, contrasting with the VC dimension's role in standard learning.
Practical Relevance: The algorithm's parallelizability and reliance on standard RERM oracles (which correspond to adversarial training heuristics used in practice) suggest that these theoretical improvements are directly applicable to modern deep learning contexts.

The author notes that while the algorithm is improper (outputting a majority vote rather than a single function in $\mathcal{F}$ ), this is necessary to achieve these bounds, mirroring the distinction between proper and improper learning in the robust setting. The work unifies algorithmic efficiency with provable robustness, suggesting that efficient robust learning is possible if one accepts improper learners and leverages the dual VC dimension.