Preprint

Bagging Robustly Learns VC Classes with Linear Sample Complexity

Omar Montasser

Aug 2026 · 1 citation · 58 references

Mathematics Computer Science

TL;DR

It is proved 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).

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

arXiv Semantic Scholar

View source

Similar papers

Preprint Aug 2026

Optimal Rates for Learning with Monotone Adversaries

This model shows that adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning.

Anay Mehrotra · 4 citations · ⚡3

Preprint Aug 2026

Optimistic Rates for Multiclass PAC Learning

Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself. For a class of Natarajan dimension $d_N$ and Daniely-Shalev-Shwartz dimension $d_{DS}$, the optimal excess risk...

Xiao-Yu Li, Andi Han, Jiao-Jiao Jiang et al. · 1 citation

Preprint Jul 2026

Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams

It is proved that for any sub-multiplicative norm, the existence of an efficient classical linear sketch is equivalent to the existence of an efficient robust turnstile algorithm, up to polynomial factors, formalizing $L_1$ embeddability as the fundamental mechanism governing both models.

Elena Gribelyuk, Honghao Lin, David P. Woodruff et al. · 0 citations

Preprint Jul 2026

Local Regularization Does Not Characterize Multiclass PAC Learnability

Local regularization assigns each hypothesis a test-point-dependent score and predicts with a minimum-score hypothesis consistent with the sample consistent with the sample, and this principle characterizes multiclass PAC learnability is negative.

Eric Hou · 1 citation

Preprint Aug 2026

The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences

This analysis reveals a scale-sensitive interaction between the statistical estimation of classification error and its amplification by robustness, sharply explaining the transition in the agnostic rate.

Elad Aigner-Horev, Daniel Rosenberg, Roi Weiss · 1 citation · ⚡1

Preprint Aug 2026

An Efficient Near-Optimal Algorithm for Adversarial $m$-Set Bandits

We study adversarial combinatorial bandits with $m$-set actions, where at each round the learner selects $m$ out of $d$ items and observes only the aggregate loss of the selected items. The resulting action set contains $K=\binom{d}{m}$ elements and can therefore be exponentially large. Nevertheless, the loss of every...

F. Bacchiocchi, Tommaso Cesari, Roberto Colomboni · 0 citations