Bagging Robustly Learns VC Classes with Linear Sample Complexity

Bagging Robustly Learns VC Classes with Linear Sample Complexity Omar Montasser

OMAR . MONTASSER @ YALE . EDU

Yale University

arXiv:2608.13514v1 [stat.ML] 13 Aug 2026

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⋆ ) indpendent 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.

1. Introduction Learning predictors robust to adversarial examples is a major contemporary challenge in machine learning. Adversarial examples can be thought of as carefully crafted perturbations of test examples that cause predictors to misclassify. Over the past decade, there has been a significant interest in how deep learning predictors are not robust to adversarial examples [Szegedy et al., 2013, Biggio et al., 2013, Goodfellow et al., 2015], leading to an ongoing effort to devise methods for learning predictors that are adversarially robust [e.g., Madry et al., 2018, Cohen et al., 2019, Zhang et al., 2019]. Given an instance space X and label space Y = {−1, 1}, we formalize an adversary (or perturbation map) we would like to be robust against as U : X → 2X , where U(x) ⊆ X is the set of perturbations of x that can be chosen by the adversary at test-time. For example, U could be perturbations of bounded ℓ∞ norm which represents “imperceptible” image perturbations in practice [Goodfellow et al., 2015]. The only (implicit) restriction is that U(x) is non-empty for every x. We observe n i.i.d. samples S = ((Xi , Yi ))ni=1 ∼ P n from an (unknown) distribution P over X × Y, and our goal is to learn a predictor fˆ : X → Y having small population robust risk, " RU (fˆ; P ) =

E

(X,Y )∼P

# n o sup 1 fˆ(Z) ̸= Y .

(1)

Z∈U (X)

A central approach to adversarially robust learning in practice is adversarial training, where model parameters are trained to fit the training examples and their corresponding adversarial perturbations [e.g., Madry et al., 2018, Zhang et al., 2019]. Theoretically, this can be viewed as minimizing the empirical robust risk over a function class F ⊆ Y X (e.g., neural networks): n

fbS ∈ RERMF (S) := arg min f ∈F

1X sup 1 {f (Zi ) ̸= Yi } . n i=1 Zi ∈U (Xi )

(2)

This approach is justified by classical uniform convergence arguments applied to the robust risk, i.e., arguing that with sufficiently many training examples, the robust generalization gap |RU (f ; P ) −

©2026 O. Montasser.

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

RU (f ; S)| is small for all f ∈ F [Cullina, Bhagoji, and Mittal, 2018, Bubeck, Lee, Price, and Razenshteyn, 2019, Yin, Ramchandran, and Bartlett, 2019]. However, empirical evidence shows severe overfitting: adversarial training yields models with low empirical robust risk but high population robust risk [Schmidt, Santurkar, Tsipras, Talwar, and Madry, 2018]. This discrepancy suggests that adversarial training and uniform convergence alone may not guarantee provable robust learning. This empirical observation is indeed mirrored by a fundamental theoretical limitation. Montasser, Hanneke, and Srebro [2019] showed that minimizing the empirical robust risk as in (2)–or any surrogate thereof–can provably fail, even in simple settings. Specifically, there are function classes F with VC dimension 1 that are not adversarially robustly learnable with any proper learning algorithm, namely, one constrained to output a predictor fˆ ∈ F. To bypass the limitation of proper learning, Montasser, Hanneke, and Srebro [2019] designed an improper learning algorithm to adversarially robustly learn classes F with finite VC dimension. This separation between proper and improper learning stands in sharp contrast to classical (non-robust) PAC learning [Valiant, 1984], where empirical risk minimization (ERM), a proper learning rule, learns VC classes with near-optimal sample complexity [Vapnik and Chervonenkis, 1971, Valiant, 1984, Blumer, Ehrenfeucht, Haussler, and Warmuth, 1989, Ehrenfeucht, Haussler, Kearns, and Valiant, 1989]. Despite this progress in adversarially robust learning, two fundamental challenges remain concerning: sample-efficiency and oracle-efficiency. First, the best known upper bound on the sample complexity is exponential in the VC dimension d [Montasser, Hanneke, and Srebro, 2019]. Second, the improper learning algorithm attaining this bound is quite complex and inefficient; it makes O(nd ) O(d) oracle calls to RERM (2) with a prohibitive additional computational overhead of n2 . These challenges motivate the central question we study in this work: Can we design sample-efficient and oracle-efficient adversarially robust learning algorithms? Or are there fundamental limitations prohibiting that? In addition to our goal of improving the sample complexity of adversarially robust learning, we are especially interested in oracle-efficient algorithms. Just as efficient PAC learning reduces to efficient ERM, this work seeks an analogous recipe for robustness: reducing efficient robust PAC learning of a class F to efficient RERM. In this context, we view RERM (2) as a natural black-box oracle, since adversarial training methods in practice [e.g., Madry et al., 2018, Zhang et al., 2019] can be viewed as heuristics implementing RERM. Theoretically, oracle-efficient robust learners would strengthen reductions for leveraging non-robust learners [Montasser, Hanneke, and Srebro, 2020b], handling unknown perturbations [Montasser, Hanneke, and Srebro, 2021], and achieving computational efficiency [Montasser, Goel, Diakonikolas, and Srebro, 2020a], thereby unifying algorithmic efficiency with provable robustness. 1.1 Main Results In this work, we prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension, providing an exponential improvement over the best previous bound due to Montasser, Hanneke, and Srebro [2019]. Remarkably, this result is achieved with a simple improper algorithm that combines the classic heuristic bagging (bootstrap aggregation) due to Breiman [1996] with robust empirical risk minimization (RERM, (2)). Given a training sample S, the algorithm ′ constructs N independent bootstrap samples S1′ , . . . , SN (as specified below), runs RERMF on each ′ b ′ bootstrap sample Si to produce a predictor fSi ∈ F, and finally outputs a majority-vote over fbS1′ , . . . , fbSN′ . The formal procedure appears in Algorithm 1, followed by its guarantee.

2

M ONTASSER

Algorithm 1: Bagging Robust ERMs Input: Training set S = ((Xj , Yj ))nj=1 , confidence δ, and an RERMF oracle fb (2). 1. Set N = O(d⋆ + log(1/δ)), and Jn = {n/4, . . . , n − 1}. 2. For each i = 1, . . . , N : 3. Sample t uniformly from Jn . 4. Sample a bootstrap Si′ of t samples uniformly with replacement from S≤t = ((Xj , Yj ))tj=1 . 5. Run RERMF oracle fb on Si′ , denoting its output predictor by fbSi′ .   Output: The majority-vote predictor MAJ fbS ′ , . . . , fbS ′ . 1

N

Theorem 1 (Realizable). 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,      d 1 1 b b ′ ′ RU MAJ(fS1 , . . . , fSN ); P = O + log . n n δ We remark that the oracle complexity (number of calls to RERM) of our algorithm above satisfies N = O(d⋆ ) where d⋆ denotes the dual VC dimension of F 1 , with a computational overhead of just O(d⋆ n). This is a significant improvement over the prior improper algorithm of Montasser, Hanneke, and Srebro [2019], which incurred oracle complexity of O(nd ) and additional computational overhead ⋆ of O(ndd ). Another significant advantage of our bagging algorithm, which is of practical importance, is that it can be parallelized since the N bootstrap samples are independent. The prior improper algorithm of Montasser, Hanneke, and Srebro [2019] relies on boosting which is inherently sequential and cannot be parallelized in general [Karbasi and Larsen, 2024]. By combining the agnostic-to-realizable reduction of Montasser, Hanneke, and Srebro [2019, Theorem 8] with the realizable guarantee of Theorem 1, we obtain the following immediate corollary improving the sample and oracle complexity of agnostic adversarially robust learning. Corollary 1 (Agnostic). 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, the following holds. 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 b hS satisfying s  !   d 1 1 2 b RU hS ; P ≤ inf RU (f ; P ) + O log (n) + log . f ∈F n n δ The agnostic algorithm ALG works as follows. Denote by W an instantiation of Algorithm 1 with fixed parameters ε0 = 1/3, δ0 = 1/3, to be treated as a weak robust learner. Given a training sample S, call RERMF once on S to find a maximal subsequence S ′ that is robustly realizable. Then, run a classical boosting algorithm [e.g., α-Boost, Schapire and Freund, 2012, Section 6.4.2] on S ′ with W as the weak learner. The final output is majority-of-majority of predictors in F. Remark 1 (Computational Efficiency). Our results provide a recipe for computationally efficient robust PAC learning. In particular, if a concept class F and perturbation set U admit an efficient 1. The dual VC dimension, which is the VC dimension of the dual class, is known to satisfy d⋆ ≤ 2d+1 − 1 [Assouad, 1983], which is tight for some classes but for many natural classes d⋆ = d (e.g., halfspaces) or polynomially related d⋆ = poly(d) (e.g., feed-forward network with threshold activations) [Montasser, Hanneke, and Srebro, 2020b]

3

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

sample size n

sharp transition Impossible in general Some VC classes are not robustly learnable with N ≤ d⋆ − 1 oracle calls.

All VC classes learnable
N = O d⋆ + log(1/δ)   d + log(1/δ) n(ε, δ) = O ε

n(ε, δ) Insufficient samples in general

RERM-oracle calls N

N ≍ d⋆

Figure 1: A sharp sample–oracle complexity tradeoff: below d⋆ oracle calls, robust learnability can fail regardless of sample size n.

algorithm implementing RERMF (2), then Theorem 1 implies that F is efficiently adversarially robustly PAC learnable with respect to U in the realizable setting. For the agnostic setting, the same implication follows from Corollary 1 under an additional requirement that the robust loss for f ∈ F can be evaluated efficiently. In light of Theorem 1, a natural follow-up question is whether the oracle complexity can be further improved. Because the dual VC dimension satisfies d⋆ ≤ 2d+1 − 1 with the inequality being tight for some classes [Assouad, 1983], we ask whether the oracle complexity can instead be bounded by a polynomial or even a linear function of the VC dimension d. Recent advances in classical PAC learning suggest that such an improvement might be possible. Larsen [2023] showed that bagging with O(log n) calls to an ERM oracle yields an optimal PAC learner, and subsequent work reduced this number to just three independent ERM calls that are combined by a majority-vote [Aden-Ali, Høandgsgaard, Larsen, and Zhivotovskiy, 2024, Rawal and Zhivotovskiy, 2026]. Can an analogous guarantee be obtained for adversarially robust learning? Our second main result gives a negative answer: unlike in classical PAC learning, the oracle complexity of adversarially robust learning must inherently depend on the dual VC dimension d⋆ . We state this result formally below. Theorem 2. 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 the following holds. 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. We remark that this result proves that Ω(d⋆ ) oracle queries to RERM are necessary regardless of the number of samples m provided to the algorithm. Figure 1 on page 4 illustrates the sample-oracle complexity tradeoff and the sharp transition implied by Theorem 1 and Theorem 2.

2. Discussion, Implications, and Related Work We discuss connections between our work and related literature. We start by discussing several quantitative improvements on prior works that follow from our results. We then situate our work within broader theoretical models of robustness.

4

M ONTASSER

Characterization and Optimal Sample Complexity. Montasser, Hanneke, and Srebro [2022] proposed a refined complexity measure denoted dim(F, U) that characterizes which classes F and perturbation sets U are adversarially robustly learnable. This characterization is based on a generalization of the classical one-inclusion graph of Haussler, Littlestone, and Warmuth [1994]. Our result in Theorem 1, and more directly Lemma 3, implies that this complexity measure is bounded by the VC dimension: dim(F, U) ≤ O(d), positively resolving Conjecture 3 of Montasser, Hanneke, and Srebro [2022]. Reductions in Adversarially Robust Learning. Several works have explored access to different forms of oracles and studied what robust learning guarantees are possible. This includes access to non-robust learners such as ERM [Montasser, Hanneke, and Srebro, 2020b, Ahmadi, Blum, Montasser, and Stangl, 2024], and access to “attack oracles” for U [Montasser, Goel, Diakonikolas, and Srebro, 2020a, Montasser, Hanneke, and Srebro, 2021]. A unifying theme across these works is that each specific form of access is leveraged to implement an RERM oracle (2). Consequently, our algorithmic result in Theorem 1 leads to immediate quantitative improvements when combined with those earlier works in their respective settings. For example, 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)), where lit(F) denotes the Littlestone dimension of F [Littlestone, 1987]. Adversarially Robust Learning with Tolerance. Several prior works have studied a relaxed model of adversarially robust learning where the learner competes with a “larger” perturbation set V ⊇ U, while the adversary is restricted to perturbations in U [Ashtiani, Pathak, and Urner, 2023, Bhattacharjee, Hopkins, Kumar, Yu, and Chaudhuri, 2023, Ashtiani, Pathak, and Urner, 2025]. Concretely, consider metric balls in p dimensions U(x) = Ballr (x) and V(x) = Ball(1+α)r (x). Previously, the best e (d (log(d) + p log(1 + 1/α)) + log(1/δ)/ε) [Ashknown upper bound on sample complexity was O tiani, Pathak, and Urner, 2025]. Theorem 1 improves the sample complexity to O(d/ε) removing dependence on the ambient dimension p and α. Bounded Cardinality Perturbation Sets. In the special case of adversarially robust learning where maxx∈X |U(x)| ≤ k for some fixed k ∈ N, Attias, Kontorovich, and Mansour [2022b] established a sample complexity upper bound of Õ(d log(k)/ε) via a single RERM call and uniform convergence analysis. Theorem 1 improves the sample complexity to O(d/ε) removing the log(k) factor entirely, albeit with an improper learning algorithm making O(d⋆ ) calls to RERM. Broader Models of Robust Learning. Our work studies supervised classification under test-time perturbations. Adversarial robustness has also been studied in semi-supervised and regression settings [Carmon, Raghunathan, Schmidt, Duchi, and Liang, 2019, Alayrac, Uesato, Huang, Fawzi, Stanforth, and Kohli, 2019, Attias, Hanneke, and Mansour, 2022a, Attias and Hanneke, 2023]. A complementary line considers adversarial corruptions at training-time, beginning with the malicious- and nasty-noise models of PAC learning [Kearns and Li, 1993, Bshouty, Eiron, and Kushilevitz, 2002], which were recently shown to be equivalent for efficient distribution-independent learning [Blanc, Huang, Malkin, and Servedio, 2026]. Other theoretical works study clean-label and instance-targeted poisoning and robustly reliable prediction under poisoning attacks [Blum, Hanneke, Qian, and Shao, 2021, Hanneke, Karbasi, Mahmoody, Mehalel, and Moran, 2022, Balcan, Blum, Hanneke, and Sharma, 2022], as well as learning with monotone adversaries [Larsen, Pabbaraju, and Shetty, 2026, Mehrotra, 2026]. Beyond modeling adversarial examples through prescribed perturbation sets, abstention can provide meaningful guarantees under arbitrary test inputs. In particular, PQ learning combines labeled samples from a training distribution P with unlabeled samples from an arbitrary test distribution Q, seeking low error on Q while maintaining a low abstention rate on P [Goldwasser, Kalai, Kalai, and Montasser, 2020, Kalai and Kanade, 2021]. This model is closely connected to reliable learning [Kalai,

5

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

Kanade, and Mansour, 2012], testable learning with distribution shifts [Klivans, Stavropoulos, and Vasilyan, 2024, Patel, Klivans, Stavropoulos, and Vasilyan, 2026], and has extensions to sequential adversarial injections [Goel, Hanneke, Moran, and Shetty, 2023, Edelman and Goel, 2026, Yu and Blanchard, 2026].

3. Technical Overview 3.1 Sample and Oracle Complexity Upper Bound We highlight the main ideas behind the analysis of Algorithm 1 and proof of Theorem 1. Our proof follows a substantially different route from Montasser, Hanneke, and Srebro [2019]. Instead of relying on sample compression arguments which incur a multiplicative factor of dual VC dimension d⋆ in sample complexity, we proceed with a more direct leave-one-out analysis of bagging RERMs. Fix an arbitrary class F with VC dimension d, a perturbation map U : X → 2X , an arbitrary RERMF oracle fb (2), and a distribution P over X × Y that is robustly realizable (inf f ∈F RU (f ; P ) = 0). The analysis is divided into three main parts we sketch below. Distribution over RERMs. The key idea is to the analyze the distribution over the RERMs fbS that are produced from random samples S ∼ P n . In key Lemma 1, we essentially show that in expectation over random test examples (X, Y ) ∼ P , for any perturbation Z ∈ U(X), the fraction of RERMs fbS that misclassify Z, fbS (Z) ̸= Y , is small: " E

(X,Y )∼P

#   h n oi d b sup E n 1 fS (Z) ̸= Y = Õ . S∼P n Z∈U (X)

(3)

One way of thinking about (3) is that it 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 as implied by [Theorem 1, Montasser, Hanneke, and Srebro, 2019], " " ## n o E E sup 1 fbS (Z) ̸= Y = Ω(1). (X,Y )∼P

S∼P n

Z∈U (X)

Bagging Leave-One-Out Analysis. The next idea is to apply (3) on an empirical distribution and establish a leave-one-out bound on the robust risk. Specifically, in Lemma 3, on a fixed robustly realizable sequence T = ((Xi , Yi ))ni=1 , the aggregate vote over all RERMs can be expressed as h i b T (x) := B E n fbS (x) ∈ [−1, 1]. (4) S∼Unif(T )

(4) can be thought of as performing bagging (bootstrap aggregation) over all ordered bootstraps. This idealized full-bagging predictor is analogous to a voting predictor that is analyzed by Larsen [2023] for classical PAC learning, though our analysis follows a fundamentally different route tailored to the robust risk relying on (3) and the leave-one-out analysis we sketch below. Consider a uniform distribution D over T and D−i a uniform distribution on T−i (leaving out the ith tuple) for each i ∈ [n]. Note that the probability the ith tuple is left out when drawing n − 1 samples from D is equal to (1 − 1/n)n−1 ≥ 1/e. Combining this with (3), it follows that   n n h i h i 1X 1X d b b sup Prn−1 fS (Zi ) ̸= Yi ≤ e · sup Pr fS (Zi ) ̸= Yi = Õ . n i=1 Zi ∈U (Xi ) S∼D−i n i=1 Zi ∈U (Xi ) S∼Dn−1 n−1

6

M ONTASSER

By applying Markov’s inequality, we establish the following leave-one-out robust error bound on the full bagging predictor (4)   n n h i n o d 1X 1X b b sup 1 Yi BT−i (Zi ) ≤ 0 ≤ 2 · sup Prn−1 fS (Zi ) ̸= Yi = Õ . (5) n i=1 Zi ∈U (Xi ) n i=1 Zi ∈U (Xi ) S∼D−i n−1 We prove a more general version of this bound that provides an additional margin guarantee in Lemma 3, which will be useful for us later in a sparsification argument. Observe that (5), via an exchangeability argument, implies the following bound on the expected robust risk of (4),   h    i d b E n RU sign BS ; P = Õ . S∼P n High-Probability Bound and Sparsification. We next apply a suffix averaging technique due to Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [2023] to extend the bound in (5) to a high probability bound. With the help an additional technical lemma (Lemma 5), we establish in Lemma 6 a high-probability bound on the robust risk of the suffix-bagging predictor gbS : X → [−1, 1] defined as gbS (x) :=

 n−1 h i 4 X b BS≤t (x) = E E fbS ′ . 3n t∼Unif(Jn ) S ′ ∼Unif(S≤t )t

(6)

t=n/4

Observe that the suffix-bagging predictor (6) computes the aggregate vote over a distribution over RERMs fbS ′ where S ′ is sampled according to the process defined in (6). Finally, note that the suffix-bagging predictor (6) is intractable to compute. To overcome this challenge, we observe that we can approximate (6) via a sparsification technique (Lemma 7) due ′ to Moran and Yehudayoff [2016] by drawing enough bootstrap samples S1′ , . . . , SN according to the process defined in (6). Lemma 7 appeals to uniform convergence over the dual class of F to show that N = O(d⋆ ) bootstrap samples suffice for approximation, where d⋆ denotes the dual VC dimension. Observe the bagging algorithm performs exactly this sampling process of bootstraps to produce its majority-vote output. This is where the oracle complexity dependence on d⋆ shows up. 3.2 Oracle Complexity Lower Bound Proof Overview. 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 (which defines the randomized function class Fπ ). The lower bound rests on two distinct forms of hidden information. First, 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. Second, the returned hypotheses reveal too little information to determine the orientation of a carefully chosen opposite-label pair on a uniformly random unseen block. The second obstruction applies even to an improper learner that combines and evaluates all returned hypotheses arbitrarily. The Function Class and the Role of π. For suitably chosen integer parameters K, N , set B = 2d − 1, so d⋆ = 2B + 1, and consider the latent instance set Θ = {(b, J) : b ∈ {−1, +1}, J ⊆ [K], |J| ≤ B}. The (randomized) class F will consist of K hypotheses. Hypothesis fi labels (b, J) by −b if i ∈ J, and by b otherwise. The instance space X will consist of N disjoint blocks, where each block Zr is merely a copy of Θ: a bijection πr : Zr → Θ determines the behavior of F on block Zr . The permutations π1 , . . . , πN are chosen independently and uniformly, so the class behaves identically on every block, 7

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

up to an unknown permutation of the rows. Thus all combinatorial properties are determined by the behavior on Θ, while π hides where the relevant rows occur. In Lemma 8, we show that the (randomized) function class F has VC dimension d and dual VC dimension d⋆ = 2d+1 − 1. Robust Realizability and the Hidden Target. A distribution Pπ,t draws a block R ∈ [N ], a label Y uniformly, and a random set A ⊆ [K] \ {t}, and places in the perturbation set all types (Y, J) with J ⊆ A. The resulting robust loss has the exact form sup 1{fiπ (z) ̸= Y } = 1{i ∈ A}. z∈U (X)

Since t is always excluded from A, ftπ has zero robust risk. In Lemma 10, we argue that after observing the training sample, every index absent from all sampled sets Aj remains a possible target, and conditional on the training sample the true target is uniform over this version space. The class size K is chosen so that the version space remains large even when the sample size m is arbitrary. Since q = d⋆ − 1 oracle calls can return at most q distinct hypotheses, the probability that the returned set contains the target is less than a small constant η = 10−3 . The Dual-VC Obstruction. Let Q be the set of indices of hypotheses returned by the RERM oracle. Since |Q| ≤ q = 2B, split Q into two parts Q+ and Q \ Q+ , each of size at most B, and define θ+ = (+1, Q+ ),

θ− = (−1, Q \ Q+ ).

Both are valid instances θ+ , θ− ∈ Θ. By construction of F, one can verify that all returned hypotheses indexed by Q predict the same label on θ+ and θ− (21), whereas every unreturned hypothesis with index in [K] \ Q labels θ+ by +1 and θ− by −1 (22). This is the decisive role of the dual VC dimension: fewer than d⋆ = 2B + 1 returned hypotheses necessarily leaves an opposite-label pair that those hypotheses cannot distinguish. On each unseen block during training, the random permutation πr hides which of two instances in Zr is assigned to θ+ and which is assigned to θ− ; this unknown assignment is the orientation bit. The Hidden Orientation is Nearly Uniform. The preceding local symmetry is not sufficient by itself. The response of the RERM oracle is adaptive and may depend on all hidden block permutations, including through arbitrary tie-breaking, so the identities of the returned hypotheses can leak information about the orientations. After conditioning on the target, the learner’s randomness, the training sample, and all sampled-block permutations, the unseen permutations remain independent. On each unseen block, reveal every returned hypothesis and the unordered pair of instance assigned to θ+ and θ− . Swapping the two assignments preserves all revealed information and flips only their orientation, so the orientation is locally uniform. Lemma 11 then implies that the posterior orientation bias ∆R on a uniformly selected unseen test block satisfies E[1{R is unseen in training}∆R ] < η. Thus, despite the entire adaptive interaction, the relevant orientation on a fresh block remains nearly uniform. From Hidden Orientation to Robust Error. For the analysis, we condition on the training sample (and the revealed sampled-block permutations), the learner’s internal randomness, the entire sequence of RERM oracle responses and on the values of every returned hypothesis on the whole domain. This information fixes the, possibly improper, classifier H outputted by the learner. The relevant orientation remains hidden because the two special points are indistinguishable to all returned hypotheses. On the good event that: the test block is unseen, the target was not returned, and Q ⊆ A (32), the point carrying θ+ is a valid perturbation when Y = +1, while the point carrying θ− is valid 8

M ONTASSER

when Y = −1. For any fixed values of H at the two points, a uniform label and a uniform orientation produce an error in exactly two of the four possible cases, and hence with probability 1/2 (34). The posterior bias can reduce this probability by at most ∆R (35). The good event has probability close to one (37), so averaging gives expected robust risk greater than 0.49. Finally, averaging over the prior fixes a single hard pair (Fπ , Pπ,t ), and boundedness of the risk yields the stated constant-probability lower bound.

4. Proof of Theorem 1: Sample and Oracle Complexity Upper Bound In this section, we provide a complete proof of Theorem 1 which we restate below. Theorem 1 (Realizable). 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,      1 1 d RU MAJ(fbS1′ , . . . , fbSN′ ); P = O + log . n n δ 4.1 Leave-One-Out Analysis of Bagging We begin with proving the following key lemma which establishes an important property: the fraction of RERMs that misclassify a worst-case perturbation of a random example is small. Lemma 1. For any class F with VC dimension d, any U, any deterministic RERM oracle fb, any distribution P over X × Y such that inf f ∈F RU (f ; P ) = 0, and any θ ∈ (0, 1), h i c d a(x, y) := sup Pr n fbS (z) ̸= y . Pr [a(X, Y ) ≥ θ] ≤ 2 · , θ n (X,Y )∼P z∈U (x) S∼P To prove Lemma 1, we make use of the following recent second-moment bound for consistent VC rules. We note that we could also rely on classical first-moment bounds [Blumer, Ehrenfeucht, Haussler, and Warmuth, 1989], at the expense of an additional log(n/d) factor in the resulting bound. Lemma 2 (Aden-Ali, Høandgsgaard, Larsen, and Zhivotovskiy [2024], Rawal and Zhivotovskiy [2026]). Let P be a distribution on X ×Y and let C be a class of subsets of X ×Y with VC dimension d. Let C be any deterministic selector satisfying C(S) ∈ C for every S ∈ (X ×Y)n and PrS∼P n [C(S) ∩ S = ∅] = 1. Then, h i d 2 E Pr n [(X, Y ) ∈ C(S)] ≤ c . n (X,Y )∼P S∼P Proof of Lemma 1. By Markov’s inequality, observe that [a(X, Y ) ≥ θ] =

Pr (X,Y )∼P

    1 a(X, Y )2 ≥ θ2 ≤ 2 E a(X, Y )2 . θ (X,Y )∼P (X,Y )∼P Pr

Thus, it suffices to show that " E

(X,Y )∼P

  a(X, Y )2 =

E

(X,Y )∼P

# h i2 d sup Pr n fbS (Z) ̸= Y ≤c . n Z∈U (X) S∼P

We now proceed with analyzing the random variable a(X, Y ). Fix an arbitrary map ϕ : X → X such that ϕ(x) ∈ U(x) for all x ∈ X . Define the collection of error sets Cϕ = {{(x, y) ∈ X × Y : f (ϕ(x)) ̸= y} | f ∈ F } . 9

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

Observe that VCdim(Cϕ ) ≤ VCdim(F) = d, because we are using a fixed map ϕ. Consider the selector C defined as follows n o C(S) = (x, y) ∈ X × Y : fbS (ϕ(x)) ̸= y . Because fb is an RERM oracle for F and distribution P is robustly realizable: inf f ∈F RU (f ; P ) = 0, it follows that on any sample S ∼ P n , fbS is robustly correct on S, i.e., for each (X, Y ) ∈ S and each Z ∈ U(X), fbS (Z) = Y . Since ϕ(x) ∈ U(x), this implies that fbS (ϕ(X)) = Y for each (X, Y ) ∈ S. Therefore, PrS∼P n [C(S) ∩ S = ∅] = 1. Also, since fbS ∈ F, it follows that C(S) ∈ Cϕ . We are now ready to invoke Lemma 2 to establish  h i2  E Pr n fbS (ϕ(X)) ̸= Y = E (X,Y )∼P

S∼P

(X,Y )∼P

h

Pr n [(X, Y ) ∈ C(S)]

S∼P

2

i

d ≤c . n

(7)

Observe that (7) holds for any map ϕ : X → X satisfying ϕ(x) ∈ U(x) for all x ∈ X . Fix an arbitrary f ⋆ ∈ F such that RU (f ⋆ ; P ) = 0. For any scalar η > 0, we will consider a special arbitrary map ϕη : X → X satisfying h i2 2 ϕη (x) ∈ U(x) and Pr n fbS (ϕη (x)) ̸= f ⋆ (x) ≥ a (x, f ⋆ (x)) − η for all x ∈ X . S∼P

In words, ϕη maps each x ∈ X to a perturbation ϕη (x) = z i∈ U(x) that is an approximate maximizer h b n of the probability of disagreement PrS∼P fS (z) ̸= f ⋆ (x) . Since f ⋆ (X) = Y with probability 1, it follows then by (7) that E

  a(X, Y )2 ≤

(X,Y )∼P

 E

(X,Y )∼P

h i2  d b Pr fS (ϕη (X)) ̸= Y + η ≤ c + η. S∼P n n

Taking η arbitrarily close to zero concludes the proof. Bagging. We introduce notation for bagging. For a sequence S = ((X1 , Y1 ), . . . , (Xn , Yn )), let S ′ ∼ Unif(S)n be a bootstrap drawn uniformly at random (with replacement) from S and let fbS ′ be the output classifier of RERM (2) on S ′ . Equivalently, we can express this as drawing a sequence of integers I = (i1 , . . . , in ) ∈ [n]n and denote the bootstrap sample by S(I) = ((Xi1 , Yi1 ), . . . , (Xin , Yin )). b S : X → [−1, 1] over all nn ordered bootstraps of S as Define the aggregate vote B b S (x) := B

i X bS ′ (x) = 1 f fbS(I) (x). nn S ′ ∼Unif(S)n n E

h

(8)

I∈[n]

We now proceed to bound the leave-one-out robust risk of the bagging predictor (8). Lemma 3 (Leave-One-Out Error). There is a universal constant C > 0 such that, for any class F with VC dimension d, any U, any deterministic RERM oracle, any robustly realizable sequence T = ((X1 , Y1 ), . . . , (Xn , Yn )) with n ≥ 2, and any γ ∈ [0, 1), n

n o 1X C d b T (Zi ) ≤ γ ≤ sup 1 Yi · B · . −i 2 n i=1 Zi ∈U (Xi ) (1 − γ) n Remark 2 (Expected Robust Risk). Note that by an exchangeability argument, the leave-one-out-error in Lemma 3 translates to an expected robust risk bound of " " ## n o C d b S (Z) ≤ γ E E sup 1 Y · B ≤ . S∼P n (X,Y )∼P Z∈U (X) (1 − γ)2 (n + 1) 10

M ONTASSER

Proof of Lemma 3. Let m = n − 1. Let D = Unif(T ) be a uniform distribution over T . Fix an arbitrary (Xi , Yi ) ∈ T and an arbitrary Zi ∈ U(Xi ). Denote by Ei the event that (Xi , Yi ) appears in a random sample S ∼ Dm . By law of total probability, h i h i i   h Pr m fbS (Zi ) ̸= Yi = Pr [Ei ] Pr fbS (Zi ) ̸= Yi | Ei + Pr Ēi Pr fbS (Zi ) ̸= Yi | Ēi . S∼D

Because fb is an RERM oracle for F and because distribution D is robustly realizable, it follows that for any sample S ∼ Dn , fbS is robustly correct on S: for each (X, Y ) ∈ S and each Z ∈ U(X), fbS (Z) = Y . Under event Ei , (Xi , Yi ) ∈ S, thus, fbS (Zi ) = Yi . This implies that m h h i i  i   h 1 b b Pr m fS (Zi ) ̸= Yi = Pr Ēi Pr fS (Zi ) ̸= Yi | Ēi = 1 − Pr fbS (Zi ) ̸= Yi | Ēi . S∼D n Let D−i = Unif(T−i ) be a uniform distribution on T−i . Observe that sampling S ∼ Dm condim tioned on event Ei is equivalent to sampling S̃ ∼ D−i , h i h i Pr m fbS (Zi ) ̸= Yi | Ēi = Pr fbS̃ (Zi ) ̸= Yi . S∼D

m S̃∼D−i

Combining the above, we establish that for each (Xi , Yi ) ∈ T and each Zi ∈ U(Xi ), m h h h i  i 1 i 1 b Pr fbS̃ (Zi ) ̸= Yi ≥ Pr fbS̃ (Zi ) ̸= Yi , Pr m fS (Zi ) ̸= Yi = 1 − m m S∼D n e S̃∼D−i S̃∼D−i

(9)

where the last inequality follows from the fact that for m = n − 1, (1 − 1/n)n−1 ≥ 1/e for all n ≥ 2. bT Fix an arbitrary (Xi , Yi ) ∈ T and consider the averaging classifier over all bootstraps B −i computed on T−i . Observe that if n o b T (Zi ) ≤ γ = 1, sup 1 Yi · B −i Zi ∈U (Xi )

then, by definition, there exists Zi ∈ U(Xi ) such that h i 1  b T (Zi ) ≥ 1 − γ . Pr fbS̃ (Zi ) ̸= Yi = 1 − Yi B −i m 2 2 S̃∼D−i b T with that of the Combining this observation with (9), we can relate the performance of B −i b T as follows performance of B    n o h i 1−γ 1−γ b b sup 1 Yi · BT−i (Zi ) ≤ γ ≤ sup 1 Pr fS (Zi ) ̸= Yi ≥ = 1 a(Xi , Yi ) ≥ . S∼D m 2e 2e Zi ∈U (Xi ) Zi ∈U (Xi ) By summing over i = 1, . . . , n and invoking Lemma 1 with θ = (1 − γ)/(2e), we obtain   n n o 1X 1−γ 1 d b T (Zi ) ≤ γ ≤ Pr sup 1 Yi · B a(X, Y ) ≥ ≤ c · 4e2 · · . −i n i=1 Zi ∈U (Xi ) 2e (1 − γ)2 m (X,Y )∼D Since m = n − 1 and n ≥ 2, it follows that n/(n − 1) ≤ 2. This concludes the proof. 4.2 High-Probability Bound and Sparsification Our goal here is to convert the leave-one-out-error bound of Lemma 3 to a high probability bound. Suffix Averaging. Our first step is to apply the suffix averaging technique due to Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [2023] on top of bagging (8). Specifically, for a sequence S = ((X1 , Y1 ), . . . , (Xn , Yn )) where n/4 is an integer, let Jn = {n/4, . . . , n − 1}. For t ∈ Jn , let bS be the bagging predictor produced on S≤t . S≤t = ((Xi , Yi ))i≤t be a suffix of length t, and let B ≤t The proof of the following lemma is a straightforward extension of the suffix averaging argument of Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [2023, Theorem 2.1] applied to our marginrobust loss. We defer it to Appendix A. 11

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

Lemma 4 (High-probability suffix average). Suppose that n/4 is an integer. Then, for every distribution P over X × Y satisfying inf f ⋆ ∈F RU (f ⋆ ; P ) = 0 (i.e., robustly realizable), every δ ∈ (0, 1), and S ∼ P n , with probability at least 1 − δ, " #   n−1 n o 4 X 1 2 d b E sup 1 Y · BS≤t (Z) ≤ γ + log . ≤ 4.82C 3n (1 − γ)2 n n δ (X,Y )∼P Z∈U (X) t=n/4

Suffix-Bagging Predictor. Observe that Lemma 4 is not enough by itself as it only guarantees that the average of the margin-robust risk over the suffixes is small. We introduce next the suffix-bagging predictor which averages all the suffix predictors and then proceed to bound its margin-robust risk. Formally, define the suffix-bagging predictor gbS : X → [−1, 1] as n−1

4 X b gbS (x) := BS≤t (x) = E t∼Jn 3n t=n/4

n−1 h i X 1 X bS ′ = 1 E f fbS(I) (x). |Jn | tt S ′ ∼Unif(S≤t )t t



t=n/4

(10)

I∈[t]

The next lemma helps us bound the robust-margin loss of the suffix-bagging predictor (10) by the average robust-margin loss of the suffixes. Pk Lemma 5 (Averaging two margins). Let g1 , . . . , gk : X → [−1, 1] and ḡ := (1/k) j=1 gj . For every 0 ≤ γ < ρ < 1 and every (x, y), sup 1 {yḡ(z) ≤ γ} ≤ z∈U (x)

k 1+ρ 1 X · sup 1 {ygj (z) ≤ ρ} . ρ − γ k j=1 z∈U (x)

(11)

Proof. Suppose supz∈U (x) 1 {yḡ(z) ≤ γ} = 1, and choose z ∈ U (x) such that yḡ(z) ≤ γ. Let q be the fraction of indices j ∈ [k] for which ygj (z) ≤ ρ. Since every margin lies in [−1, 1], X X 1 1 ygj (z) + ygj (z) ≥ −q + (1 − q)ρ = ρ − (1 + ρ)q. yḡ(z) = k k j:ygj (z)≤ρ

j:ygj (z)>ρ

Since yḡ(z) ≤ γ, by rearranging terms, it follows that q ≥ (ρ − γ)/(1 + ρ). By definition of q and since z ∈ U (x), it follows that k 1X ρ−γ sup 1 {ygj (z) ≤ ρ} ≥ q ≥ . k j=1 z∈U (x) 1+ρ Rearranging terms concludes the proof. We now bound the margin-robust risk of the suffix-bagging predictor (10) with high-probability. Lemma 6. For any class F with finite VC dimension d, any U, any (deterministic) RERM oracle fb, any distribution P over X × Y satisfying inf f ⋆ ∈F RU (f ⋆ ; P ) = 0 (i.e., robustly realizable), any n ≥ 1 and confidence parameter δ ∈ (0, 1), with probability 1 − δ over S ∼ P n , it holds that " #    1 2 d E sup 1 {Y · gbS (Z) ≤ 1/2} ≤ C2 + log . n n δ (X,Y )∼P Z∈U (X) Proof. We start by invoking Lemma 4 to convert the in leave-one-out error bound of Lemma 3 to a high probability bound, with margin parameter set to a constant equal to 3/4. It follows that with probability at least 1 − δ over S ∼ P n , " #    n o 1 X d 1 2 b E sup 1 Y · BS≤t (Z) ≤ 3/4 + log . ≤ 64C1 |Jn | n n δ (X,Y )∼P Z∈U (X) t∈Jn

12

M ONTASSER

To finish the proof, we invoke Lemma 5 with margin parameters γ = 1/2, ρ = 3/4 and apply to the b S t for t ∈ Jn . By definition (10), gbS = 1/|Jn | P classifiers gt := B ≤ t∈Jn gt . The resulting constant C2 = (1 + ρ)/(ρ − γ)64C1 = 7 · 64C1 = 448C1 . Note that the suffix-bagging predictor (10) is intractable to compute. To overcome this challenge, we observe that we can approximate (10) via a sparsification technique due to Moran and Yehudayoff [2016] which we state in the lemma below. Lemma 7 (Sparsification, Moran and Yehudayoff [2016]). Let F be a function class with finite dual VCdimension d⋆ . Let Q be an arbitrary distribution over F. Then, for any ε, δ ∈ (0, 1), letting N =O

d⋆ +log(1/δ) ε2

, with probability at least 1 − δ over f1 , . . . , fN ∼ Q, N

1 X fj (x) − E [f (x)] ≤ ε. f ∼Q N j=1

∀x ∈ X ,

4.3 Putting the Pieces Together Proof of Theorem 1. We start by presenting the learning guarantee for the idealized suffix-baggingaggregate predictor (10). By invoking Lemma 6, with probability at least 1 − δ/2 over S ∼ P n , it holds that " #    4 d 1 E sup 1 {Y · gbS (Z) ≤ 1/2} ≤ C2 + log . (12) n n δ (X,Y )∼P Z∈U (X) By definition (10), observe that the suffix-bagging-aggregate predictor gbS can be viewed as a distribution Q over predictors in the class F. We can sample from this distribution Q by sampling an index t uniformly at random from Jn and then sampling uniformly at random a bootstrap sample S ′ from S≤t . By invoking Lemma 7 with an approximation parameter ε = 1/4, letting ′ N = O(d⋆ + log(4/δ)), we have with probability 1 − δ/2 over the bootstrap samples S1′ , . . . , SN ⊆ S, N

1 1 Xb fSj′ (x) − gbS (x) ≤ . N j=1 4

∀x ∈ X ,

(13)

This implies the following guarantee  ∀(z, y) ∈ X × Y,

if yb gS (z) >

N 1 X



1 1 then y  fbS ′ (z) > . 2 N j=1 j 4

(14)

Combining (12) and (14), with probability at least 1 − δ over the random draw of a training dataset ′ S ∼ P n and N bootstrap samples S1′ . . . , SN ⊆ S,      N     X 1  sup 1 Y  RU MAJ(fbS1′ , . . . , fbSN′ ); P ≤ E fbSj′ (Z) ≤ 1/4  (15)  N j=1 (X,Y )∼P Z∈U (X)  " # ≤

 ≤ C2

sup 1 {Y · gbS (Z) ≤ 1/2}

E

(X,Y )∼P

(16)

Z∈U (X)

d 1 + log n n

This concludes the proof. 13

  4 . δ

(17)

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

5. Proof of Theorem 2: Oracle Complexity Lower Bound In this section, we provide a complete proof of Theorem 2 which we restate below. Theorem 2. 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 the following holds. 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. 5.1 Construction Parameters. Let d, m ≥ 1. We construct below a family of function classes, each of which has VC dimension d and dual VC dimension d⋆ = 2d+1 − 1. Parameter m denotes the number of samples provided to the learning algorithm which can be arbitrarily large, and the number of queries the algorithm can make to an RERM oracle is capped to q = d⋆ − 1. l ⋆ m Set auxiliary parameters B = (d⋆ − 1)/2 = 2d − 1, η = 10−3 , δ = η/d⋆ , p = 1 − δ. Let K = ηδd m , l m q log(K+1) and N = m + m . K will be the cardinality of each of the function classes, N plays η + 2η 2 a role in the cardinality of the instance space. Later in the proof we will make use of the following inequalities which can be verified given the choice of parameters: s q m q log(K + 1) ⋆ ⋆ d K ≥ d /η > d > 2 , < η, < η, < η. (18) Kδ m N 2(N − m) Instance Space. Define the finite set of latent instances Θ := {(b, J) : b ∈ {−1, 1} , J ⊆ [K], |J| ≤ B} . For every r ∈ [N ], let Zr be an abstract set of cardinality |Θ|, with the Zr ’s being pairwise disjoint. We a priori fix an ordering of Zr . For every V ⊆ Zr , introduce a center instance cr,V . Define the instance space
X := ∪N r=1 Zr ∪ {cr,V : r ∈ [N ], V ⊆ Zr } . Perturbations. Define the perturbation map U(z) := {z}

(z ∈ Zr ),

U(cr,V ) := V.

Family of Function Classes. We will now define the family of function classes based on the set of latent instances Θ and a bijection tuple π = (π1 , . . . , πN ) where each πr : Zr → Θ is a bijection map. π For each π, the function class Fπ = {f1π , . . . , fK } is defined as follows. If πr (z) = (b, J), define for every i ∈ [K], ( fiπ (z) :=

−b, b,

i ∈ J, i∈ / J,

fiπ (cr,V ) := +1.

Note that the functions fiπ are distinct since the latent instance (+1, {i}) separates fiπ from every fjπ , j ̸= i. Note also that all functions in Fπ label the center instances cr,V with +1, the nontrivial action happens only in the blocks Zr , r ∈ [N ]. 14

M ONTASSER

This defines the family of function classes {Fπ }π we will use in the lower bound. In the proof, we will draw the block bijections π = (π1 , . . . , πN ) independently and uniformly at random. It may be helpful to think of the (random) function class F Π as a matrix with columns indexed by 1, . . . , K, and rows indexed by the blocks Z1 , . . . , ZN . Lemma 8 (Primal and Dual VC dimension). For every π, VCdim(Fπ ) = d and VCdim⋆ (Fπ ) = d⋆ = 2d+1 − 1. Proof. We start by showing VCdim(Fπ ) ≥ d. Choose 2d = B + 1 distinct indices {is : s ∈ {−1, +1}d } ⊆ [K]. For j ∈ [d], let Jj := {is : sj = −1}. Then |Jj | = 2d−1 ≤ B. In one block πr : Zr → Θ, choose the instances zj ∈ Zr that map to (+1, Jj ). For every s ∈ {−1, +1}d , fiπs (zj ) = sj . Hence z1 , . . . , zd are shattered. We now show that VCdim(Fπ ) ≤ d. Suppose that d + 1 instances were shattered. Choose one function for each of the 2d+1 = 2B + 2 label vectors on these points. At each selected instance, exactly half of these functions, namely B + 1, must be negative. But, by construction of the class, this is impossible. Specifically, on any 2B + 2 functions in Fπ , a latent instance (b, J) ∈ Θ has at most B negative values (if b = 1) or at least B + 2 negative values (if b = −1), because |J| ≤ B and K − |J| ≥ B + 2. Therefore VCdim(Fπ ) = d. We proceed to showing VCdim⋆ (Fπ ) = d⋆ = 2B + 1. For the lower bound, choose any G ⊆ [K] with |G| = d⋆ = 2B + 1. Given J ⊆ G, if |J| ≤ B, the latent instance (+1, J) is labeled negative by every fiπ , i ∈ J and positive by every fiπ , i ∈ G \ J. If |J| ≥ B + 1, then |G \ J| ≤ B, and the latent instance (−1, G \ J) is labeled negative by every fiπ , i ∈ J and positive by every fiπ , i ∈ G \ J. Hence, the dual class shatters G. For the upper bound, we claim that the dual class cannot shatter d⋆ + 1 = 2B + 2 functions. Indeed, on such a set, a subset G of size B + 1 can not be labeled negative since it is neither small nor the complement of a small set, so no latent instance in Θ can realize this labeling. Thus VCdim⋆ (Fπ ) = d⋆ . The Family of Distributions. For every π and t ∈ [K], define a distribution Pπ,t over X × Y as follows. A sample (X, Y ) ∼ Pπ,t is generated by: (i) Draw R ∼ Unif([N ]) and Y ∼ Unif(Y) independently. (ii) Form A ⊆ [K] \ {t} by including each i ̸= t independently with probability p; (iii) Form the set of perturbations Vπ (R, A, Y ) := {z ∈ ZR : πR (z) = (Y, J) for some J ⊆ A} and set X = cR,Vπ (R,A,Y ) . (iv) Output (X, Y ). In the lower bound proof, we will be using the collection {(Fπ , Pπ,t ) : π, t ∈ [K]}. The family of distributions {Pπ,t }t∈[K] is robustly realizable by the class Fπ as given by the following lemma. Lemma 9 (Robust Realizability). Let (X, Y ) ∼ Pπ,t with corresponding latent random variables (R, A, Y ). For every i ∈ [K], sup 1 {fiπ (z) ̸= Y } = z∈U (X)

sup z∈Vπ (R,A,Y )

Consequently, RU (ftπ ; Pπ,t ) = 0. 15

1 {fiπ (z) ̸= Y } = 1 {i ∈ A} .

(19)

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

/ A, then every Proof. Recall that Vπ (R, A, Y ) = {z ∈ ZR : πR (z) = (Y, J) for some J ⊆ A}. If i ∈ J ⊆ A excludes i, so fiπ (z) = Y for every z ∈ Vπ (R, A, Y ). Hence the robust loss is zero. If i ∈ A, then there is a perturbation z ∈ Vπ (R, A, Y ) such that πR (z) = (Y, {i}), on which fiπ (z) = −Y , so the robust loss is one. Since the distribution Pπ,t always excludes t from A, the target ftπ has zero robust risk. Lower Bound Analysis. The bijection maps Π = (Π1 , . . . , ΠN ) are drawn independently and uniformly at random. This determines the random function class FΠ . In addition, the target function is drawn independently T ∼ Unif([K]). This defines the random distribution PΠ,T . Then, a training m sample S = ((Xj , Yj )) ∼ PΠ,T is generated, with corresponding latent variables ((Rj , Aj ))m j=1 . m Upon receiving a training sample S ∼ PΠ,T as input, the learner ALG makes at most q queries to an RERM oracle for FΠ . We denote by I = (I1 , . . . , Iq ) ∈ ([K] ∪ {⊥})q the ordered sequence of indices of the returned functions by the oracle where unused queries are padded with ⊥. We denote by Q = Q(I) ⊆ [K] the set of distinct indices, |Q| ≤ q. We denote by ΦI = (fIΠ1 , . . . , fIΠq ) the returned functions by the oracle. After its interaction and oracle queries, the learner ALG outputs an arbitrary predictor H : X → Y. Note that H depends on S, I, ΦI and ALG’s internal randomness. Our goal is to bound from below the expected robust risk " #

E

E

m Π,T S∼PΠ,T

RU (H; PΠ,T ) = E

E

E

m Π,T S∼PΠ,T (X,Y )∼PΠ,T

sup 1 {H(Z) ̸= Y } . Z∈U (X)

5.2 The Target is Unlikely to be Returned Lemma 10. Let Q ⊆ [K] be the set of distinct indices of all functions returned to a learner making at most q oracle calls. Then, P {T ∈ Q} < η. Proof. Given a realization of latent variables A1 , . . . , Am generating the training sample S, define the set of sample-consistent target indices VS := [K] \ ∪m j=1 Aj . For any realization of A1 , . . . , Am and any t ∈ VS , P {A1 , . . . , Am |T = t} =

m Y

p|Aj | (1 − p)K−1−|Aj | ,

j=1

which does not depend on the particular index t. Hence, conditioning on the random permutations m Π, the training sample S = (Xj , Yj )m j=1 and its latent variables (Aj , Rj )j=1 , T is uniform on VS . Therefore,  q |Q ∩ VS | P T ∈ Q | Π, S, (Aj , Rj )m ≤ . j=1 = |VS | |VS | Conditional on T , every other index other than T is absent from all m sets A1 , . . . , Am with probability R1 a = (1 − p)m . Therefore |VS | = 1 + X where X ∼ Bin(K − 1, a). Using 1/(1 + k) = 0 uk du,   Z 1 1 1 − (1 − a)K 1 E = (1 − a + au)K−1 du = ≤ . 1+X Ka Ka 0 Taking expectations and using the fact that the choice parameters satisfies Ka ≥ d⋆ /η, q = d⋆ − 1,      1 q0 q0 P{T ∈ Q} = E P T ∈ Q | Π, S, (Aj , Rj )m ≤ qE ≤ ≤ ⋆ η < η. j=1 |VS | Ka d This concludes the proof. 16

M ONTASSER

5.3 An Indistinguishable Opposite-Label Pair In this section, we describe a particular choice of a pair of perturbations of test examples that will have opposite labels but will be indistinguishable from the perspective of the learning algorithm conditioning on all available information during training. Recall that there is a fixed ordering on each Zr . For every possible response i ∈ ([K] ∪ {⊥})q by the oracle, let Qi = Q(i) be its set of nondummy indices. Choose   |Qi | + + Qi ⊆ Qi , |Qi | = , 2 and define θi+ = (+1, Q+ i ), ⋆

θi− = (−1, Qi \ Q+ i ).

(20)

+ − 1, it follows that |Q+ i | ≤ B and |Qi \ Qi | = ⌈|Qi |/2⌉ ≤ B. Thus both

Since |Qi | ≤ q = 2B = d θi+ , θi− in (20) belong to the latent space Θ.

Observe that θi+ , θi− are indistinguishable to all returned predictors indexed by Qi . By construction + − + + − of the class F, if j ∈ Q+ i , then fj (θi ) = fj (θi ) = −1. If j ∈ Qi \ Qi , then fj (θi ) = fj (θi ) = +1. Consequently, fj (θi+ ) = fj (θi− ) for every j ∈ Qi . (21) In contrast, every unreturned predictor assigns opposite labels: fj (θi+ ) = +1,

fj (θi− ) = −1

for every j ∈ / Qi .

(22)

In particular, on the event T ∈ / Qi , the target labels θi+ by +1 and θi− by −1. + − For a bijection ρ : Zr → Θ, let zi,r (ρ) = ρ−1 (θi+ ) and zi,r (ρ) = ρ−1 (θi− ) be the instances in Zr to + − which θi and θi are mapped to. Write Li,r (ρ) = (u, v),

u < v,

for the ordered tuple of these two instances (according to the a priori fixed ordering on Zr ), without specifying which instance is mapped to θi+ and which is mapped to θi− . Define the orientation bit by Ωi,r (ρ) = 0

⇐⇒

+ zi,r (ρ) = u,

(23) Z ×|Q |

+ i so Ωi,r (ρ) = 1 means that zi,r (ρ) = v instead. Let Φi,r (ρ) = (fj |Zr )j∈Qi ∈ {−1, 1} r be the ordered tuple, of the restrictions (or projections) of the predictors with indices in Qi to Zr , and set
Γi,r (ρ) = Φi,r (ρ), Li,r (ρ) . (24)

Thus Γi,r reveals every column (predictor indexed in Qi ) on the block r and also the two relevant instances u, v defined above, but not their orientation (which is mapped to θi+ and which is mapped to θi− ). We now verify that the above setup satisfies the requirements (26) of Lemma 11. Let τi : Θ → Θ exchange θi+ and θi− and be identity otherwise. For a block bijection ρ, put ρ′ = τi ◦ ρ. By (21), replacing ρ by ρ′ leaves every returned column unchanged, Φi,r (ρ) = Φi,r (ρ′ ). It also leaves the unordered location pair Li,r unchanged, but it flips the orientation Ωi,r . Hence, on every set {ρ : Γi,r (ρ) = γ}, the mapping ρ 7→ ρ′ pairs each orientation-0 bijection with a unique orientation-1 bijection. Since Πr is uniform over all block bijections, for every side-information value γ of positive probability, P{Ωi,r (Πr ) = 0 | Γi,r (Πr ) = γ} = P{Ωi,r (Πr ) = 1 | Γi,r (Πr ) = γ} =

1 . 2

(25)

Thus the orientation is uniform even after the returned columns and the two relevant instances have been revealed. 17

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

5.4 Low Total Variation Distance from Uniform The following lemma combines the information-usage method for controlling data-dependent selection bias [Russo and Zou, 2020] with the tensorization of relative entropy over independent coordinates [Madiman and Tetali, 2010]; applying data processing and Pinsker’s inequality converts the resulting coordinatewise information budget into an average posterior-bias bound. Related individual-coordinate mutual-information bounds appear in Bu, Zou, and Veeravalli [2020]. Its proof is deferred to Appendix B. Lemma 11. Let W1 , . . . , Wn be independent random variables taking values in finite sets, and let J be any finite-valued random variable jointly distributed with W = (W1 , . . . , Wn ). For each possible value j of J and each r ∈ [n], let Ωj,r = ωj,r (Wr ) ∈ {0, 1}, Γj,r = γj,r (Wr ), and put Γj = (Γj,1 , . . . , Γj,n ). Suppose that, under the prior law of Wr , Law(Ωj,r | Γj,r ) = Unif({0, 1})

for every j, r.

(26)

Thus, for every fixed j, the bit Ωj,r is fair even after the local side information Γj,r is revealed. Define the posterior bias
∆r = TV Law(ΩJ,r | J, ΓJ ), Unif({0, 1}) . Then

"

# r n 1X H(J) E ∆r ≤ . n r=1 2n

(27)

In our context, we will condition on the following information. Fix the random target T , the m learner’s randomness L, the training sample S = ((Xj , Yj ))m j=1 and its latent variables ((Rj , Aj ))j=1 , m the permutations of all blocks appearing in the training sample (ΠRj )j=1 . Define the set of unseen blocks in the domain by U = [N ] \ {R1 , . . . , Rm }, where |U | := n ≥ N − m. We will condition on G = (T, L, S, (Rj , Aj , ΠRj )m j=1 ). The random variables (Πr )r∈U remain independent uniform bijections. Relabeling the n (unseen) coordinates if necessary, we apply Lemma 11 with Wr = Πr ,

J = I,

Ωi,r = Ωi,r (Πr ),

Γi,r = Γi,r (Πr ).

The uniformity requirement of the orientation bit Ωi,r (26) is satisfied by (25). The oracle response I takes values in ([K] ∪ {⊥})q , so for every realization g of G, H(I | G = g) ≤ q log(K + 1).

(28)

Let ΓI = (ΓI,u (Πu ))u∈U and, for r ∈ U, define
∆r = TV Law(ΩI,r (Πr ) | G, I, ΓI ), Unif({0, 1}) .

(29)

Lemma 11, (28), and n ≥ N − m imply, for every realization g of G, s " # r q log(K + 1) q log(K + 1) 1X E ∆r G = g ≤ ≤ < η. n 2n 2(N − m) r∈U

Averaging over G gives "

# 1X E ∆r < η. n

(30)

r∈U

Let R be the block index of an independent test example, and put ∆R = 0 when R ∈ / U . The test index R is uniform on [N ] and independent of the hidden block bijections. Together with (30), this yields " # n 1X E[1{R ∈ U }∆R ] = E ∆r < η. (31) N n r∈U

18

M ONTASSER

5.5 Putting the Pieces Together Proof of Theorem 2. Draw an independent test example (X, Y ) with latent variables (R, A) and define the event E = {R ∈ U, T ∈ / Q(I), Q(I) ⊆ A}. (32) + On event E, both Q+ I and Q(I) \ QI are subsets of A. Therefore − zI,R (ΠR ) ∈ VΠ (R, A, −1).

+ zI,R (ΠR ) ∈ VΠ (R, A, +1),

Define the witness instance Z

wit

( + zI,R (ΠR ), = − zI,R (ΠR ),

if Y = +1, if Y = −1.

Then, on event E, the robust loss is bounded from below as follows sup 1 {H(z) ̸= Y } = z∈U (X)

1 {H(z) ̸= Y } ≥ 1{H(Z wit ) ̸= Y }.

sup

(33)

z∈VΠ (R,A,Y )

Condition on G, I, ΓI , R, A and suppose event E holds. Recall that LI,R (ΠR ) = (u, v), u < v + − (either u = zI,R (ΠR ) and v = zI,R (ΠR ), or vice-versa). The classifier values H(u), H(v) are fixed under this conditioning. Under our convention for ΩI,R (23), the four possibilities are summarized in the following table Y = +1 Y = −1 ?

H(v) = −1

?

H(u) = −1.

ΩI,R = 0 H(u) = +1 ΩI,R = 1

H(v) = +1

?

?

If the ΩI,R and Y are both uniform, the point u is tested once against +1 and once against −1, so exactly one of those two tests is an error. The same is true for v. Hence, for every fixed pair H(u), H(v), exactly two of the four equally likely cases produce an error. Therefore, it follows that E

Ω∼Unif({0,1})

[g(Ω)] =

1 , 2

g(ω) = PY {H(Z wit ) ̸= Y | ΩI,R = ω, G, I, ΓI , R, A}.

(34)

The actual posterior law of ΩI,R may not be uniform, but we can relate it to uniform by the variational characterization of total variation, E[g(ΩI,R )] ≥

E

Ω∼Unif({0,1})

[g(Ω)] − ∆R ≥

1 − ∆R , 2

(35)

where ∆R is the total variation distance (29). Combining (33) and (35), then averaging, and then (31), gives     ERU (H; PΠ,T ) ≥ E 1E E 1 H(Z wit ) ̸= Y G, I, ΓI , R, A    1 − ∆R ≥ E 1E 2 1 ≥ P(E) − E[1{R ∈ U}∆R ] 2 1 ≥ P(E) − η. 2

19

(36)

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

Probability of the good event. It remains to bound the probability of event E (32), P(E), from below. Conditioning on G, I, ΓI fixes T, Q(I), U , but A remains random. If T ∈ Q, then the event Q ⊆ A is impossible because A ⊆ [K] \ T (as specified in PΠ,T ). If T ∈ / Q, then every index in Q is included in A with probability p. Thus P {Q ⊆ A | G, I, ΓI } = 1 {T ∈ / Q} p|Q| ≥ 1 {T ∈ / Q} pq . Consequently, h i P(E) = E 1 {R ∈ U, T ∈ / Q} p|Q| ≥ pq P {R ∈ U, T ∈ / Q} . By a union bound, P {R ∈ U, T ∈ / Q} ≥ 1 − P {R ∈ / U } − P {T ∈ Q} . Conditioning on the training blocks R1 , . . . , Rm , P {R ∈ / U | R1 , . . . , Rm } ≤ m/N . Therefore, P {R ∈ / U } ≤ m/N . Lemma 10 shows that P {T ∈ / Q} < η. Thus,   m P(E) ≥ pq 1 − −η . (37) N Note that the choice of parameters in the construction ensures that m/N < η. By definition, recall that ⋆ p = 1 − η/d⋆ and q = d⋆ − 1. By Bernoulli’s inequality, pq = (1 − η/d⋆ )d −1 ≥ 1 − (d⋆ − 1)η/d⋆ > 1 − η. Combining the above, with the choice of η = 1/1000, it follows that 1 (1 − η)(1 − 2η) − η > 0.49. 2 By the probabilistic method, there must exist a fixed pair π, t (which may depend on learner A) such that E [RU (H; Pπ,t )] > 0.49. Applying a variant of Markov’s inequality concludes the proof. EΠ,T [RU (H; PΠ,T )] >

AI Disclosure The author used ChatGPT Pro (5.5 and 5.6) and Codex during the development of several ideas and proofs presented in this paper. The author also used these models to assist with some of the writing.

References Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. Optimal PAC bounds without uniform convergence. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1203–1223. IEEE, 2023. doi: 10.1109/FOCS57990.2023.00071. URL https://doi.org/10.1109/FOCS57990.2023.00071. Ishaq Aden-Ali, Mikael Møller Høandgsgaard, Kasper Green Larsen, and Nikita Zhivotovskiy. Majorityof-three: The simplest optimal learner? In The Thirty Seventh Annual Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 22–45. PMLR, 2024. URL https://proceedings.mlr.press/v247/aden-ali24a.html. Saba Ahmadi, Avrim Blum, Omar Montasser, and Kevin M. Stangl. Agnostic multi-robust learning using ERM. In International Conference on Artificial Intelligence and Statistics, 2–4 May 2024, Palau de Congressos, Valencia, Spain, volume 238 of Proceedings of Machine Learning Research, pages 2242–2250. PMLR, 2024. URL https://proceedings.mlr.press/v238/ahmadi24a.html. Jean-Baptiste Alayrac, Jonathan Uesato, Po-Sen Huang, Alhussein Fawzi, Robert Stanforth, and Pushmeet Kohli. Are labels required for improving adversarial robustness? In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 12192–12202, 2019. URL http://papers.nips.cc/paper/ 9388-are-labels-required-for-improving-adversarial-robustness. 20

M ONTASSER

Hassan Ashtiani, Vinayak Pathak, and Ruth Urner. Adversarially robust learning with tolerance. In Shipra Agrawal and Francesco Orabona, editors, International Conference on Algorithmic Learning Theory, February 20-23, 2023, Singapore, volume 201 of Proceedings of Machine Learning Research, pages 115–135. PMLR, 2023. URL https://proceedings.mlr.press/v201/ashtiani23a.html. Hassan Ashtiani, Vinayak Pathak, and Ruth Urner. Simplifying adversarially robust PAC learning with tolerance. In Nika Haghtalab and Ankur Moitra, editors, The Thirty Eighth Annual Conference on Learning Theory, June 30 - July 4, 2025, Lyon, France, volume 291 of Proceedings of Machine Learning Research, pages 147–168. PMLR, 2025. URL https://proceedings.mlr.press/v291/ ashtiani25a.html. Patrick Assouad. Densité et dimension. Annales de l’Institut Fourier, 33(3):233–282, 1983. doi: 10.5802/aif.938. URL https://www.numdam.org/articles/10.5802/aif.938/. Idan Attias and Steve Hanneke. Adversarially robust PAC learnability of real-valued functions. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 1172–1199. PMLR, 2023. URL https://proceedings.mlr.press/v202/attias23a.html. Idan Attias, Steve Hanneke, and Yishay Mansour. A characterization of semi-supervised adversarially robust PAC learnability. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022a. URL http://papers.nips.cc/paper_files/paper/2022/hash/ 95a704bd2fdf8ef8242b4adcc7ce3c93-Abstract-Conference.html. Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for adversarially robust learning. J. Mach. Learn. Res., 23:175:1–175:31, 2022b. URL https://jmlr.org/papers/ v23/20-1353.html. Maria-Florina Balcan, Avrim Blum, Steve Hanneke, and Dravyansh Sharma. Robustly-reliable learners under poisoning attacks. In Conference on Learning Theory, Proceedings of Machine Learning Research, pages 4498–4534. PMLR, 2022. URL https://proceedings.mlr.press/ v178/balcan22a.html. Robi Bhattacharjee, Max Hopkins, Akash Kumar, Hantao Yu, and Kamalika Chaudhuri. Robust empirical risk minimization with tolerance. In Shipra Agrawal and Francesco Orabona, editors, International Conference on Algorithmic Learning Theory, February 20-23, 2023, Singapore, volume 201 of Proceedings of Machine Learning Research, pages 182–203. PMLR, 2023. URL https: //proceedings.mlr.press/v201/bhattacharjee23a.html. Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šrndić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, pages 387–402. Springer, 2013. Guy Blanc, Yizhi Huang, Tal Malkin, and Rocco A. Servedio. Is nasty noise actually harder than malicious noise? In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 1114, 2026, pages 6767–6787. SIAM, 2026. doi: 10.1137/1.9781611978971.243. URL https: //doi.org/10.1137/1.9781611978971.243. Avrim Blum, Steve Hanneke, Jian Qian, and Han Shao. Robust learning under clean-label attack. In Conference on Learning Theory, COLT 2021, Proceedings of Machine Learning Research, pages 591–634. PMLR, 2021. URL http://proceedings.mlr.press/v134/blum21a.html. 21

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. ACM, 36(4):929–965, 1989. doi: 10.1145/76359.76371. URL https://doi.org/10.1145/76359.76371. Leo Breiman. Bagging predictors. Mach. Learn., 24(2):123–140, 1996. doi: 10.1007/BF00058655. URL https://doi.org/10.1007/BF00058655. Nader H. Bshouty, Nadav Eiron, and Eyal Kushilevitz. PAC learning with nasty noise. Theor. Comput. Sci., 288(2):255–275, 2002. doi: 10.1016/S0304-3975(01)00403-0. URL https://doi.org/10. 1016/S0304-3975(01)00403-0. Yuheng Bu, Shaofeng Zou, and Venugopal V. Veeravalli. Tightening mutual information-based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(1):121–130, 2020. doi: 10.1109/JSAIT.2020.2991139. URL https://doi.org/10.1109/JSAIT.2020.2991139. Sebastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn. Adversarial examples from computational constraints. In International Conference on Machine Learning, pages 831–840, 2019. Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C. Duchi, and Percy Liang. Unlabeled data improves adversarial robustness. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 11190–11201, 2019. URL http://papers.nips.cc/paper/ 9298-unlabeled-data-improves-adversarial-robustness. Jeremy Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via randomized smoothing. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 1310–1320. PMLR, 2019. URL http://proceedings.mlr.press/v97/cohen19c.html. Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of adversaries. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pages 228–239, 2018. URL http://papers.nips.cc/paper/ 7307-pac-learning-in-the-presence-of-adversaries. Ezra Edelman and Surbhi Goel. Reliable abstention under adversarial injections: Tight lower bounds and new upper bounds. CoRR, abs/2602.20111, 2026. doi: 10.48550/arXiv.2602.20111. URL https://arxiv.org/abs/2602.20111. FORC 2026 Highlights Track. Andrzej Ehrenfeucht, David Haussler, Michael J. Kearns, and Leslie G. Valiant. A general lower bound on the number of examples needed for learning. Inf. Comput., 82(3):247–261, 1989. doi: 10.1016/0890-5401(89)90002-3. URL https://doi.org/10.1016/0890-5401(89)90002-3. Surbhi Goel, Steve Hanneke, Shay Moran, and Abhishek Shetty. Adversarial resilience in sequential prediction via abstention. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10–16, 2023, 2023. URL https://proceedings.neurips.cc/paper_files/paper/ 2023/hash/1967f962c7c2083618236d80eeb9d1ac-Abstract-Conference.html. Shafi Goldwasser, Adam Tauman Kalai, Yael Kalai, and Omar Montasser. Beyond perturbations: Learning guarantees with arbitrary adversarial test examples. In Advances in Neural Information Processing Systems 33, 2020. URL https://proceedings.neurips.cc/paper/2020/hash/ b6c8cf4c587f2ead0c08955ee6e2502b-Abstract.html.

22

M ONTASSER

Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http://arxiv.org/abs/1412.6572. Steve Hanneke, Amin Karbasi, Mohammad Mahmoody, Idan Mehalel, and Shay Moran. On optimal learning under targeted data poisoning. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022. URL http://papers.nips.cc/paper_files/paper/ 2022/hash/c6afe9a5d1e1068796d32613ddca1ab7-Abstract-Conference.html. David Haussler, Nick Littlestone, and Manfred K. Warmuth. Predicting 0,1-functions on randomly drawn points. Information and Computation, 115(2):248–292, 1994. doi: 10.1006/INCO.1994. 1097. URL https://doi.org/10.1006/inco.1994.1097. Adam Tauman Kalai and Varun Kanade. Efficient learning with arbitrary covariate shift. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors, Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pages 850–864. PMLR, 2021. URL http://proceedings.mlr.press/v132/kalai21a.html. Adam Tauman Kalai, Varun Kanade, and Yishay Mansour. Reliable agnostic learning. J. Comput. Syst. Sci., 78(5):1481–1495, 2012. doi: 10.1016/J.JCSS.2011.12.026. URL https://doi.org/10. 1016/j.jcss.2011.12.026. Amin Karbasi and Kasper Green Larsen. The impossibility of parallelizing boosting. In Claire Vernade and Daniel Hsu, editors, International Conference on Algorithmic Learning Theory, 25-28 February 2024, La Jolla, California, USA, volume 237 of Proceedings of Machine Learning Research, pages 635–653. PMLR, 2024. URL https://proceedings.mlr.press/v237/karbasi24a.html. Michael J. Kearns and Ming Li. Learning in the presence of malicious errors. SIAM J. Comput., 22(4): 807–837, 1993. doi: 10.1137/0222052. URL https://doi.org/10.1137/0222052. Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Testable learning with distribution shift. In The Thirty Seventh Annual Conference on Learning Theory, Proceedings of Machine Learning Research, pages 2887–2943. PMLR, 2024. URL https://proceedings.mlr.press/ v247/klivans24a.html. Kasper Green Larsen. Bagging is an optimal PAC learner. In The Thirty Sixth Annual Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 450–468. PMLR, 2023. URL https://proceedings.mlr.press/v195/larsen23a.html. Kasper Green Larsen, Chirag Pabbaraju, and Abhishek Shetty. Learning with monotone adversarial corruptions. In Matus Telgarsky and Jonathan Ullman, editors, Proceedings of the 37th International Conference on Algorithmic Learning Theory, volume 313 of Proceedings of Machine Learning Research, pages 1–18. PMLR, 2026. URL https://proceedings.mlr.press/v313/larsen26a.html. Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Mach. Learn., 2(4):285–318, 1987. doi: 10.1007/BF00116827. URL https://doi. org/10.1007/BF00116827. Mokshay M. Madiman and Prasad Tetali. Information inequalities for joint distributions, with interpretations and applications. IEEE Transactions on Information Theory, 56(6):2699–2713, 2010. doi: 10.1109/TIT.2010.2046253. URL https://doi.org/10.1109/TIT.2010.2046253.

23

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https://openreview.net/forum?id=rJzIBfZAb. Anay Mehrotra. Optimal rates for learning with monotone adversaries. CoRR, abs/2608.06337, 2026. URL https://arxiv.org/abs/2608.06337. Omar Montasser, Steve Hanneke, and Nathan Srebro. VC classes are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, COLT 2019, Proceedings of Machine Learning Research, pages 2512–2530. PMLR, 2019. URL http://proceedings.mlr.press/v99/ montasser19a.html. Omar Montasser, Surbhi Goel, Ilias Diakonikolas, and Nathan Srebro. Efficiently learning adversarially robust halfspaces with noise. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7010–7021. PMLR, 2020a. URL http://proceedings.mlr.press/v119/montasser20a. html. Omar Montasser, Steve Hanneke, and Nati Srebro. Reducing adversarially robust learning to non-robust PAC learning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020b. URL https://proceedings.neurips.cc/paper/2020/hash/ a822554e5403b1d370db84cfbc530503-Abstract.html. Omar Montasser, Steve Hanneke, and Nathan Srebro. Adversarially robust learning with unknown perturbation sets. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 3452–3482. PMLR, 2021. URL http://proceedings.mlr.press/v134/ montasser21a.html. Omar Montasser, Steve Hanneke, and Nathan Srebro. Adversarially robust learning: A generic minimax optimal learner and characterization. In Advances in Neural Information Processing Systems 35, 2022. URL http://papers.nips.cc/paper_files/paper/2022/hash/ f392c6bbb14548df50092f10c9db440f-Abstract-Conference.html. Shay Moran and Amir Yehudayoff. Sample compression schemes for VC classes. J. ACM, 63(3): 21:1–21:10, 2016. doi: 10.1145/2890490. URL https://doi.org/10.1145/2890490. Shyamal Patel, Adam R. Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Equivalence of coarse and fine-grained models for learning with distribution shift. In Steve Hanneke and Tor Lattimore, editors, The Thirty Ninth Annual Conference on Learning Theory, June 29 - July 3, 2026, San Diego, California, USA, volume 336 of Proceedings of Machine Learning Research, pages 4022–4049. PMLR, 2026. URL https://proceedings.mlr.press/v336/patel26a.html. Divit Rawal and Nikita Zhivotovskiy. Majority-of-three is optimal. CoRR, abs/2606.13614, 2026. doi: 10.48550/ARXIV.2606.13614. URL https://doi.org/10.48550/arXiv.2606.13614. Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302–323, 2020. doi: 10.1109/TIT.2019.2945779. URL https://doi.org/10.1109/TIT.2019.2945779. Robert E. Schapire and Yoav Freund. Boosting: Foundations and Algorithms. Adaptive Computation and Machine Learning. The MIT Press, Cambridge, Massachusetts, 2012. ISBN 978-0-262-01718-3. doi: 10.7551/mitpress/8291.001.0001. URL https://doi.org/10.7551/mitpress/8291.001.0001. 24

M ONTASSER

Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially robust generalization requires more data. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 5019–5031, 2018. URL https://proceedings.neurips.cc/ paper/2018/hash/f708f064faaf32a43e4d3c784e6af9ea-Abstract.html. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013. Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134–1142, 1984. doi: 10.1145/ 1968.1972. URL https://doi.org/10.1145/1968.1972. V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971. doi: 10.1137/1116025. URL https://doi.org/10.1137/1116025. Dong Yin, Kannan Ramchandran, and Peter L. Bartlett. Rademacher complexity for adversarially robust generalization. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 7085–7094. PMLR, 2019. URL http://proceedings.mlr.press/v97/ yin19b.html. Jialin Yu and Mo”ise Blanchard. Distribution-free sequential prediction with abstentions. In Steve Hanneke and Tor Lattimore, editors, The Thirty Ninth Annual Conference on Learning Theory, June 29 - July 3, 2026, San Diego, California, USA, volume 336 of Proceedings of Machine Learning Research, pages 6976–7011. PMLR, 2026. URL https://proceedings.mlr.press/v336/yu26a.html. Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 7472–7482. PMLR, 2019. URL http://proceedings.mlr.press/v97/zhang19p.html.

Appendix A. Auxiliary Lemmata for Upper Bound The proof is a straightforward extension of the suffix averaging argument of Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [2023, Theorem 2.1] applied to our margin-robust loss. Observe that the bagging predictor (8) is permutation invariant. That is, for any sequence S and permutation π, bS = B b S . Furthermore, by Lemma 3, its leave-one-out error with respect to the margin-robust loss B π b S (z) ≤ γ} is bounded from above by O(d/n(1 − γ)2 ). (x, y) 7→ supz∈U (x) 1{y B The following Lemmas are the margin-robust counterparts of the forward and reverse martingale bounds in Lemmas 4.2 and 4.3 [Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy, 2023]. Their proofs apply verbatim: the displayed margin-robust loss is measurable and takes values in [0, 1], while the reverse martingale argument uses only bounded leave-one-out error (Lemma 3) and permutation invariance. Lemma 12 (Forward martingale bound, Lemma 4.2 in Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [2023]). Let S = ((X1 , Y1 ), . . . , (Xn , Yn )) ∼ P n . For every η, ρ ∈ (0, 1), with probability

25

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

at least 1 − ρ, "

n−1 X

# n o b S (Z) ≤ γ sup 1 Y B ≤t

E

t=n/4

(X,Y )∼P

Z∈U (X) n−1

≤

n o η ηeη X 1 b S (Z) ≤ γ + e sup 1 Y B log . t+1 ≤t η −1 eη − 1 e ρ Z∈U (Xt+1 ) t=n/4

Lemma 13 (Reverse martingale bound, Lemma 4.3 in Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [2023]). Suppose that P is a distribution over X × Y satisfying inf f ⋆ ∈F RU (f ⋆ ; P ) = 0 (i.e., robustly realizable). Let S = ((X1 , Y1 ), . . . , (Xn , Yn )) ∼ P n . Let Mn = O(d/(1 − γ)2 ). For every λ, ρ ∈ (0, 1), with probability at least 1 − ρ, n−1 X t=n/4

n o λ b S (Z) ≤ γ ≤ e − 1 Mn sup 1 Yt+1 B ≤t λ Z∈U (Xt+1 )

n X m=n/4+1

1 1 1 + log . m λ ρ

Proof of Lemma 4. Apply Lemma 12 and Lemma 13 with confidence parameter ρ = δ/2. By a union bound, with probability at least 1 − δ, " # n−1 n o X b E sup 1 Y BS (Z) ≤ γ t=n/4

(X,Y )∼P

≤t

Z∈U (X)

 ηeη  eλ − 1 ≤ η Mn e −1 λ

n X m=n/4+1

 1 1 2 eη 2 + log + η log . m λ δ e −1 δ

Since x 7→ 1/x is decreasing, n X m=n/4+1

1 ≤ m

Z n

dx = log 4. n/4 x

Consequently, "

n−1

4 X E 3n (X,Y )∼P

# n o b S (Z) ≤ γ sup 1 Y B ≤t Z∈U (X)

t=n/4

η

4 ηe e λ − 1 Mn 4 ≤ log(4) + η 3e −1 λ n 3



eη ηeη + λ(eη − 1) eη − 1



2 1 log . n δ

Taking λ = 0.82 and η = 0.78 gives eλ − 1 4 ηeη log(4) ≈ 4.1246 < 4.82 3 eη − 1 λ

and

4 3



ηeη eη + λ(eη − 1) eη − 1

 ≈ 4.8037 < 4.82.

It follows that n−1

4 X E 3n (X,Y )∼P t=n/4

"

#   n o Mn 1 2 b S (Z) ≤ γ sup 1 Y B ≤ 4.82 + log , ≤t n n δ Z∈U (X)

which proves the lemma.

26

M ONTASSER

Appendix B. Auxiliary Lemmata for Lower Bound Lemma 11. Let W1 , . . . , Wn be independent random variables taking values in finite sets, and let J be any finite-valued random variable jointly distributed with W = (W1 , . . . , Wn ). For each possible value j of J and each r ∈ [n], let Ωj,r = ωj,r (Wr ) ∈ {0, 1}, Γj,r = γj,r (Wr ), and put Γj = (Γj,1 , . . . , Γj,n ). Suppose that, under the prior law of Wr , Law(Ωj,r | Γj,r ) = Unif({0, 1})

(26)

for every j, r.

Thus, for every fixed j, the bit Ωj,r is fair even after the local side information Γj,r is revealed. Define the posterior bias
∆r = TV Law(ΩJ,r | J, ΓJ ), Unif({0, 1}) . Then

"

# r n 1X H(J) E ∆r ≤ . n r=1 2n

(27)

Proof. The point of the lemma is that the transcript value J = j may select a different bit Ωj,r and different side information Γj,r . We therefore keep j fixed until the last averaging step. Fix j and write Γj = (Γj,1 , . . . , Γj,n ). Since Γj is a deterministic function of W , the relative-entropy chain rule gives

KL Law(W | J = j) ∥ Law(W ) = KL Law(Γj | J = j) ∥ Law(Γj ) 
 + E KL Law(W | J = j, Γj ) ∥ Law(W | Γj ) J = j . (38) The first term on the right is nonnegative. Multiplying by P{J = j}, summing over j, and using the definition of mutual information therefore yields X 
 P{J = j}E KL Law(W | J = j, Γj ) ∥ Law(W | Γj ) J = j ≤ I(W ; J) ≤ H(J). (39) j

The second law in each summand conditions on the fixed statistic Γj but not on the event J = j; the KL divergence therefore measures the additional information supplied by that event. We next decompose the left side of (39) across coordinates. For fixed j and every γ in the support of Γj , independence of the Wr and the coordinatewise form of Γj imply Law(W | Γj = γ) =

n O

Law(Wr | Γj,r = γr ).

(40)

r=1

Indeed, before normalization the conditional mass at w = (w1 , . . . , wn ) factors as n Y

P{Wr = wr }1{γj,r (wr ) = γr }.

r=1

For an arbitrary law P on a product space, with marginals Pr , and a product reference law one has ! ! n n n n O O X X KL P Qr = KL P Pr + KL(Pr ∥Qr ) ≥ KL(Pr ∥Qr ). r=1

r=1

r=1

N

r Qr ,

(41)

r=1

Applying (41) conditionally, with the product reference law in (40), and then averaging gives # " n X X
P{J = j}E KL Law(Wr | J = j, Γj ) ∥ Law(Wr | Γj,r ) J = j ≤ H(J). (42) j

r=1

27

S AMPLE AND O RACLE C OMPLEXITY OF R OBUST L EARNING

Again, the second law in each summand conditions only on the fixed local statistic Γj,r , not on the event J = j. For each fixed j, r, the map Wr 7→ Ωj,r is deterministic. Applying the data processing inequality to every summand in (42), followed by (26), gives " n # X
E KL Law(ΩJ,r | J, ΓJ ) ∥ Unif({0, 1}) r=1

=

X

P {J = j} E

≤

#
KL Law(Ωj,r | J = j, Γj ) ∥ Law(Ωj,r | Γj,r ) J = j

r=1

j

X

" n X

P{J = j}E

j

" n X

# KL Law(Wr | J = j, Γj ) ∥ Law(Wr | Γj,r )

J =j

r=1

≤ H(J).

(43)

Applying Pinsker’s inequality, with natural logarithms, gives ∆2r ≤ Dr /2, where Dr = KL Law(ΩJ,r |
J, ΓJ ) ∥ Unif({0, 1}) and ∆r is the total variation distance. Finally, by Cauchy–Schwarz and Jensen’s inequality, # v # v # r " n u " u " n n X X X u u 1 H(J) 1 1 ∆r ≤ tE ∆2 ≤ tE Dr ≤ . E n r=1 n r=1 r 2n r=1 2n This proves (27).

28

Related documents

• Self-Balancing Sequential Sampling: Fast Convergence with Controlled Predictability#670696
• Self-Balancing Sequential Sampling: Fast Convergence with Controlled Predictability#668631
• Unbiased sampling from Boltzmann distributions with noisy energies#821168
• Estimating Time-Varying Coefficients With the VC Program#646075
• DIME: Dynamics Inferred from Monte Carlo Ensembles via Continuous-Time Markov Chains#661907