Pith. sign in

REVIEW 3 major objections 5 minor 58 references

Bagging Robustly Learns VC Classes with Linear Sample Complexity

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that bagging robust empirical risk minimizers learns any VC class with sample complexity O(d), an exponential improvement, and that no algorithm in the RERM-oracle model can do it with fewer than Ω(d*) calls.

desk verdict An important paper with a real gap: the upper bound needs an attained zero-robust-risk target, but the main theorem only assumes inf=0. read the letter →

arxiv 2608.13514 v1 pith:N6ABW2HU submitted 2026-08-13 stat.ML cs.DScs.LG

Omar Montasser This is my paper · ORCID
classification stat.MLcs.DScs.LG MSC 68Q3268T05
keywords adversarialrobustnessbaggingrobustempiricalriskminimizationVCdimensiondualsamplecomplexityoracleimproperlearning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes that any function class with finite VC dimension d is adversarially robustly learnable from O(d) samples, an exponential improvement over the previous O(exp(d)) bound. The algorithm is bagging: draw N = O(d* + log(1/δ)) independent bootstrap samples, run robust empirical risk minimization (RERM) on each, and output the majority vote, where d* is the dual VC dimension. In the realizable setting, the robust risk of this improper learner is O(d/n + (1/n) log(1/δ)) with probability 1 − δ. A matching lower bound shows that Ω(d*) calls to an RERM oracle are necessary for any learner, even given arbitrarily many samples, so the oracle complexity of this scheme cannot be improved in general. The result reframes adversarially robust PAC learning as an oracle-efficiency question: if the class admits an efficient RERM, the bagging recipe yields an efficient robust learner.

What carries the argument

The load-bearing object is the majority vote of RERMs computed on independent bootstrap samples, analyzed through the idealized full-bagging aggregate vote bS(x) = E_{S'∼Unif(S)^n}[bf_{S'}(x)] over all ordered bootstraps. The proof uses a second-moment bound for consistent VC selectors to show that the probability an RERM misclassifies a worst-case perturbation is small in expectation, then applies leave-one-out and suffix-averaging arguments to convert this into a high-probability robust-risk bound. A sparsification lemma over the dual class justifies replacing the intractable full bagging average by N = O(d*) bootstrap draws. The lower bound uses a construction with latent instances Θ = {(b, J) : b ∈ {−1, +1}, J ⊆ [K], |J| ≤ B} where B = 2^d − 1, and relies on the fact that fewer than d* returned hypotheses necessarily leave an opposite-label pair θ+ and θ− that all returned functions classify identically, hiding an orientation bit that the learner cannot recover.

What would settle it

Run Algorithm 1 with an exact deterministic RERM oracle on a class from the paper's lower-bound construction, which has d* = $2^{{d+1}}$ − 1, using a large training sample m and comparing N = d* − 1 bootstraps with N = d* bootstraps; Theorem 2 predicts constant robust risk at the smaller N while Theorem 1 predicts O(d/m) risk at the larger N. Alternatively, compute E_{(X,Y)∼P}[a(X,Y)^2] for a realizable class with a deterministic RERM, where a(x,y) is the supremum over perturbations of the probability that a fresh RERM misclassifies; Lemma 1 claims this second moment is at most c d/n, so exceeding that bound for a universal constant c would falsify the proof's foundation.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for any function class F with VC dimension d and dual VC dimension d*, any perturbation set U, any deterministic RERM oracle, and any distribution P that is robustly realizable by F, running RERM on N = O(d* + log(1/δ)) independent bootstrap samples and taking their majority vote achieves robust risk O(d/n + (1/n) log(1/δ)) with probability 1 − δ. This replaces the previous best known upper bound, which was exponential in d, with a linear-in-d sample complexity. The matching lower bound (Theorem 2) constructs classes with VC dimension d and dual VC dimension d* = $2^{{d+1}}$ − 1 such that any algorithm making at most d* − 1 RERM calls has constant worst-case robust risk on a robustly realizable distribution, even with arbitrarily many samples. Thus the dual VC dimension is both sufficient and necessary for oracle-efficient robust learning in this model.

Load-bearing premise

The entire upper-bound argument assumes that the RERM oracle returns an exact, deterministic, global minimizer of the empirical robust risk; if the oracle is approximate, randomized, or tie-breaks in a way that breaks consistency on the training sample, the leave-one-out and second-moment analysis no longer applies.

Editorial extensions

If this is right

  • Robust learning of VC classes becomes sample-efficient: in the realizable setting, O((d + log(1/δ))/ε) examples suffice for robust risk ε, removing the exponential-in-d dependence.
  • The agnostic setting inherits the improvement through an agnostic-to-realizable reduction, yielding excess risk O(sqrt(d/n log^2 n + (1/n) log(1/δ))) with O(d*(log n + log(1/δ))) RERM calls.
  • The refined robust-learnability complexity dim(F, U) is at most O(d), positively resolving Conjecture 3 of Montasser, Hanneke, and Srebro [2022].
  • For tolerance-based robust learning and bounded-cardinality perturbation sets, the sample complexity improves to O(d/ε), removing dependence on the ambient dimension and on log k.
  • The Ω(d*) oracle lower bound shows that, unlike classical PAC learning where a constant number of ERM calls suffices, adversarially robust learning in the RERM-oracle model must pay the dual VC dimension.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An open question this raises is whether the exact deterministic RERM oracle assumption can be relaxed: if the oracle is approximate or randomized, the consistency step in Lemma 1 can break, and the linear sample-complexity guarantee would need a different argument or fail.
  • The lower-bound construction uses arbitrary perturbation maps that map each center to an arbitrary subset, not metric-ball perturbation sets; for structured perturbations such as ℓ_p balls, an algorithm with fewer than d* oracle calls might still exist, since the dual-VC obstruction may not embed into those perturbations.
  • Because the N bootstrap calls are independent, the bagging algorithm is parallelizable, and the Ω(d*) lower bound quantifies a tradeoff between sequential boosting-based robust learners and parallel bagging-based ones; this suggests parallelizable adversarial training as a practical route consistent with the theory.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies adversarially robust PAC learning in an oracle model where the learner has access to a deterministic RERM_F oracle. It proves (Theorem 1) that for any function class F with VC dimension d and dual VC dimension d*, any perturbation set U, and any distribution P satisfying inf_{f in F} R_U(f;P)=0, running RERM on N=O(d*+log(1/delta)) bootstrap samples and taking a majority vote yields robust risk O(d/n + (1/n)log(1/delta)) with probability 1-delta. This is an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019), and the algorithm is parallelizable and oracle-efficient. Corollary 1 extends the bound to agnostic learning via an agnostic-to-realizable reduction. Theorem 2 gives a lower bound showing that Omega(d*) RERM oracle calls are necessary in this model, even with arbitrarily many training samples, matching the oracle complexity of the upper bound. The upper-bound proof is a leave-one-out analysis of bagging combined with suffix averaging and sparsification; the lower bound uses a randomized function class and an information-usage argument.

Significance. If the results are correct, this is a substantial advance: it replaces an exponential-in-d sample-complexity upper bound for adversarially robust learning of VC classes with a linear one, gives oracle complexity O(d*) instead of the previous O(n^d) calls with additional n^{2^{O(d)}} overhead, and shows with Theorem 2 that the oracle complexity is tight. The paper also positively resolves Conjecture 3 of Montasser, Hanneke, and Srebro (2022) and yields quantitative improvements in several derived settings, including robust learning with tolerance, bounded-cardinality perturbation sets, and attack-oracle complexity. The proof architecture is transparent and builds on independent prior lemmas (second-moment bounds for consistent selectors, suffix averaging, and Moran-Yehudayoff sparsification); no fitted parameter is used to force the conclusion. The main qualifications are that one step of Lemma 1 is not justified as written under the stated inf=0 assumption, and the formal statement of the lower bound should make the oracle-only model explicit.

major comments (3)
  1. [§4.1, Lemma 1] The proof of Lemma 1 fixes an exact f* in F with R_U(f*;P)=0 and later uses 'Since f*(X)=Y with probability 1' after Eq. (7), but Theorem 1 assumes only inf_{f in F} R_U(f;P)=0. If the infimum is not attained, the construction of phi_eta and the claim that bf_S is robustly correct on every sample S~P^n are not justified. This is load-bearing because Lemma 1 feeds Lemma 3, Lemma 4, Lemma 6, and finally Theorem 1. The gap appears repairable by choosing a sequence f_k with R_U(f_k;P)->0 and adding an O(R_U(f_k;P)) approximation error, together with a union-bound argument showing that a random sample is almost surely robustly realizable, but the manuscript must supply that argument.
  2. [§4.1, text after (7)] The pointwise choice of an approximate maximizer phi_eta(x) requires a measurable selection, but no measurability assumptions on X or U and no measurable-selection argument are given. Without such an argument the expectation over (X,Y) in Eq. (7) involving phi_eta(X) is not formally well-defined. This is likely fixable under standard Borel assumptions, but as written the integration over P is not justified.
  3. [§5, Theorem 2] The lower bound is only valid in a model in which the learner has black-box access to the RERM oracle and is not given the realized class F_pi directly. The formal statement of Theorem 2 does not say this, and the proof relies on the learner not knowing the permutations Pi_r on unseen blocks: Sections 5.4-5.5 treat H(u),H(v) as fixed while the orientation bit Omega remains hidden. If ALG were handed F_pi, it could use its oracle responses to identify the set Q, compute theta+ and theta-, locate their preimages on the unseen test block via Pi_R, and label those two points correctly, making the robust loss zero on the good event E. Please state the black-box assumption explicitly in Theorem 2 and in the surrounding discussion, since the current formal statement can be read as false in the standard setting where the learner knows the class.
minor comments (5)
  1. [§4.2, Lemma 4 and Theorem 1] Lemma 4 assumes n/4 is an integer, while Theorem 1 claims the bound for every n>=4; please either state the restriction or handle general n with floors and ceilings.
  2. [Abstract] The abstract contains the typo 'indpendent'; it should be 'independent'.
  3. [§5.1, parameter definitions] The definitions of K and N after Eq. (18) are hard to parse in the typeset text; please make the exponent m in delta^m and the ceiling delimiters unambiguous.
  4. [References] The reference 'Aden-Ali, Høandgsgaard, Larsen, and Zhivotovskiy [2024]' appears with a misspelled author name; the spelling 'Høandgsgaard' should be corrected.
  5. [§5, Theorem 2 statement] The notation F={F} for the finite collection of classes is confusing; denoting the collection by {F_pi}_pi would be clearer.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the robust-learning bound follows from independent second-moment and sparsification lemmas, while the author's own prior results are used only for context and for the agnostic corollary.

full rationale

The central claim, Theorem 1, is not circular. The proof chain starts from Lemma 1, which is derived by applying Lemma 2, an external second-moment bound for consistent VC selectors due to Aden-Ali, Høandgsgaard, Larsen, and Zhivotovskiy [2024] and Rawal and Zhivotovskiy [2026]. The RERM property is used only to supply the consistency condition C(S) in C and C(S) cap S = empty; Lemma 2 does not assume the theorem's robust-learning conclusion. Lemma 3 then turns the second-moment bound into a leave-one-out robust error bound, Lemma 4 uses the suffix-averaging argument of Aden-Ali et al. [2023], Lemma 5 is an elementary margin-averaging inequality, and Lemma 7 is the Moran-Yehudayoff sparsification bound. None of these inputs define the target O(d/n + log(1/delta)/n) bound into existence, and no data-dependent parameter is fitted to force the inequality. The bootstrap count N = O(d* + log(1/delta)) is set in advance and is not tuned to the sample. The lower bound in Theorem 2 is a separate construction based on an explicit hard family and the information-usage lemma proved in Appendix B, so it does not borrow the upper bound. The self-citations to Montasser, Hanneke, and Srebro [2019, 2022] are used for prior context, for the improved exponential comparison, and for the agnostic-to-realizable reduction in Corollary 1; they are not load-bearing for Theorem 1 itself. One caveat should be flagged explicitly because it is emphasized in the proof: in Lemma 1 the text fixes 'an arbitrary f* in F such that R_U(f*;P)=0' even though Theorem 1 assumes only inf_{f in F} R_U(f;P)=0. If the infimum is not attained, the displayed step 'Since f*(X)=Y with probability 1' is not justified as written. This is a technical correctness gap in the proof as stated, not a circularity, because the missing condition is not being smuggled in as a conclusion. Accordingly, the circularity score is low, reflecting only minor non-load-bearing self-citations.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The central result relies on several imported lemmas from prior literature (second-moment bounds, sparsification, information usage, martingale suffix bounds). These are independent established results, not derived in this paper. The lower bound construction uses several hand-chosen parameters, but they are part of the hard instance, not fitted to data. No new physical or mathematical entities are postulated.

free parameters (5)
  • eta = 1e-3
    Tolerance for probability bounds in the lower bound construction; chosen small enough to push the final expected robust risk above 0.49.
  • delta = eta/d*
    Set to eta/d* to make p=1-delta close to 1 and to satisfy the inequalities in (18).
  • B = 2^d - 1
    Defines the dual VC dimension d* = 2B+1 = 2^{d+1}-1 in the lower bound construction.
  • K = ceil(d*/(eta*delta))^m
    Cardinality of each function class; chosen so that K*(1-p)^m >= d*/eta, keeping the target hidden in Lemma 10.
  • N = m + ceil(m/eta + q log(K+1)/(2 eta^2))
    Number of blocks in the instance space; chosen so that the information-theoretic bias bound sqrt(q log(K+1)/(2(N-m))) < eta.
assumptions (6)
  • domain assumption Second-moment bound for consistent VC rules (Lemma 2)
    Imported from Aden-Ali, Høandgsgaard, Larsen, and Zhivotovskiy 2024 and Rawal and Zhivotovskiy 2026. Used in Lemma 1 to bound the fraction of RERMs misclassifying a worst-case perturbation.
  • domain assumption Sparsification for dual VC classes (Lemma 7)
    Moran and Yehudayoff 2016; used to approximate the suffix-bagging predictor with N=O(d*+log(1/delta)) iid draws from the RERM distribution.
  • domain assumption Information-usage bound (Lemma 11)
    Combines Russo and Zou 2020 and Madiman and Tetali 2010; used in the lower bound to control the posterior bias of the orientation bit.
  • domain assumption Forward and reverse martingale bounds for suffix averaging
    Adapted from Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy 2023, Theorem 2.1; the paper states the proofs apply verbatim to the margin-robust loss.
  • domain assumption Realizability inf_f R_U(f;P)=0
    Assumed in Theorem 1; ensures RERM returns a robustly consistent classifier on every sample, which is central to the second-moment argument.
  • domain assumption Deterministic exact RERM oracle
    The theorem is stated for a deterministic RERM oracle; the analysis requires the selector C(S) to be a deterministic function of the sample.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Bagging Robustly Learns VC Classes with Linear Sample Complexity." pith.science (2026). https://pith.science/paper/N6ABW2HU

@misc{pith2026260813514,
  author       = {Pith},
  title        = {Pith review of: Bagging Robustly Learns VC Classes with Linear Sample Complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N6ABW2HU}},
  note         = {Machine review of arXiv:2608.13514}
}
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.

Figures

Figures reproduced from arXiv: 2608.13514 by the authors.

Figure 1
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 ∈ … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 37 canonical work pages

  1. [1]

    Optimal PAC bounds without uniform convergence

    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.2...

    arXiv 2023

  2. [2]

    Majority-of-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

    Ishaq Aden - Ali, Mikael M ller H andgsgaard, Kasper Green Larsen, and Nikita Zhivotovskiy. Majority-of-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

    work page 2024

  3. [3]

    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/ah...

    work page 2024

  4. [4]

    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 1...

    work page 2019

  5. [5]

    Adversarially robust learning with tolerance

    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/v20...

    work page 2023

  6. [6]

    Simplifying adversarially robust PAC learning with tolerance

    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://proceeding...

    work page 2025

  7. [7]

    Densit \'e et dimension

    Patrick Assouad. Densit \'e et dimension. Annales de l'Institut Fourier, 33 0 (3): 0 233--282, 1983. doi:10.5802/aif.938. URL https://www.numdam.org/articles/10.5802/aif.938/

    work page doi:10.5802/aif.938 1983

  8. [8]

    Adversarially robust PAC learnability of real-valued functions

    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 Re...

    work page 2023

Show all 58 references
  1. [9]

    A characterization of semi-supervised adversarially robust PAC learnability

    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 Con...

    2022

  2. [10]

    Improved generalization bounds for adversarially robust learning

    Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for adversarially robust learning. J. Mach. Learn. Res., 23: 0 175:1--175:31, 2022 b . URL https://jmlr.org/papers/v23/20-1353.html

    2022

  3. [11]

    Robustly-reliable learners under poisoning attacks

    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

    2022

  4. [12]

    Robust empirical risk minimization with tolerance

    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, volum...

    2023

  5. [13]

    Evasion attacks against machine learning at test time

    Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim S rndi \'c , 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 ...

    2013

  6. [14]

    Servedio

    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 1...

    2026 doi

  7. [15]

    Robust learning under clean-label attack

    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

    2021

  8. [16]

    Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the V apnik- C hervonenkis dimension. J. ACM , 36 0 (4): 0 929--965, 1989. doi:10.1145/76359.76371. URL https://doi.org/10.1145/76359.76371

    1989

  9. [17]

    Bagging predictors

    Leo Breiman. Bagging predictors. Mach. Learn., 24 0 (2): 0 123--140, 1996. doi:10.1007/BF00058655. URL https://doi.org/10.1007/BF00058655

    1996 doi

  10. [18]

    Bshouty, Nadav Eiron, and Eyal Kushilevitz

    Nader H. Bshouty, Nadav Eiron, and Eyal Kushilevitz. PAC learning with nasty noise. Theor. Comput. Sci., 288 0 (2): 0 255--275, 2002. doi:10.1016/S0304-3975(01)00403-0. URL https://doi.org/10.1016/S0304-3975(01)00403-0

    2002 doi

  11. [19]

    Veeravalli

    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 0 (1): 0 121--130, 2020. doi:10.1109/JSAIT.2020.2991139. URL https://doi.org/10.1109/JSAIT.2020.2991139

    2020

  12. [20]

    Adversarial examples from computational constraints

    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

    2019

  13. [21]

    Duchi, and Percy Liang

    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

  14. [22]

    Zico Kolter

    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, Ca...

    2019

  15. [23]

    Pac-learning in the presence of adversaries

    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 \' e al, Canad...

    2018

  16. [24]

    Reliable abstention under adversarial injections: Tight lower bounds and new upper bounds

    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

    2026 doi

  17. [25]

    Kearns, and Leslie G

    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 0 (3): 0 247--261, 1989. doi:10.1016/0890-5401(89)90002-3. URL https://doi.org/10.1016/0890-5401(89)90002-3

    1989 doi

  18. [26]

    Adversarial resilience in sequential prediction via abstention

    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,...

    2023

  19. [27]

    Beyond perturbations: Learning guarantees with arbitrary adversarial test examples

    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/b6c8cf4c58...

    2020

  20. [28]

    Goodfellow, Jonathon Shlens, and Christian Szegedy

    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 Proceed...

    2015 arXiv

  21. [29]

    On optimal learning under targeted data poisoning

    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...

    2022

  22. [30]

    David Haussler, Nick Littlestone, and Manfred K. Warmuth. Predicting 0,1 -functions on randomly drawn points. Information and Computation, 115 0 (2): 0 248--292, 1994. doi:10.1006/INCO.1994.1097. URL https://doi.org/10.1006/inco.1994.1097

    1994

  23. [31]

    Efficient learning with arbitrary covariate shift

    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 Rese...

    2021

  24. [32]

    Reliable agnostic learning

    Adam Tauman Kalai, Varun Kanade, and Yishay Mansour. Reliable agnostic learning. J. Comput. Syst. Sci., 78 0 (5): 0 1481--1495, 2012. doi:10.1016/J.JCSS.2011.12.026. URL https://doi.org/10.1016/j.jcss.2011.12.026

    2012 doi

  25. [33]

    The impossibility of parallelizing boosting

    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...

    2024

  26. [34]

    Kearns and Ming Li

    Michael J. Kearns and Ming Li. Learning in the presence of malicious errors. SIAM J. Comput. , 22 0 (4): 0 807--837, 1993. doi:10.1137/0222052. URL https://doi.org/10.1137/0222052

    1993 doi

  27. [35]

    Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan

    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/v24...

    2024

  28. [36]

    Bagging is an optimal PAC learner

    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

    2023

  29. [37]

    Learning with monotone adversarial corruptions

    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 Le...

    2026

  30. [38]

    Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm

    Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Mach. Learn., 2 0 (4): 0 285--318, 1987. doi:10.1007/BF00116827. URL https://doi.org/10.1007/BF00116827

    1987 doi

  31. [39]

    Madiman and Prasad Tetali

    Mokshay M. Madiman and Prasad Tetali. Information inequalities for joint distributions, with interpretations and applications. IEEE Transactions on Information Theory, 56 0 (6): 0 2699--2713, 2010. doi:10.1109/TIT.2010.2046253. URL https://doi.org/10.1109/TIT.2010.2046253

    2010

  32. [40]

    Towards deep learning models resistant to adversarial attacks

    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, Confe...

    2018

  33. [41]

    Optimal rates for learning with monotone adversaries

    Anay Mehrotra. Optimal rates for learning with monotone adversaries. CoRR, abs/2608.06337, 2026. URL https://arxiv.org/abs/2608.06337

    2026 arXiv

  34. [42]

    VC classes are adversarially robustly learnable, but only improperly

    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/m...

    2019

  35. [43]

    Efficiently learning adversarially robust halfspaces with noise

    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 o...

    2020

  36. [44]

    Reducing adversarially robust learning to non-robust PAC learning

    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, virtu...

    2020

  37. [45]

    Adversarially robust learning with unknown perturbation sets

    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 Mac...

    2021

  38. [46]

    Adversarially robust learning: A generic minimax optimal learner and characterization

    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/f392c6bbb14548df50092f1...

    2022

  39. [47]

    Sample compression schemes for VC classes

    Shay Moran and Amir Yehudayoff. Sample compression schemes for VC classes. J. ACM , 63 0 (3): 0 21:1--21:10, 2016. doi:10.1145/2890490. URL https://doi.org/10.1145/2890490

    2016 doi

  40. [48]

    Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan

    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...

    2026

  41. [49]

    Majority-of-three is optimal

    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

    2026 doi arXiv

  42. [50]

    How much does your data exploration overfit? controlling bias via information usage

    Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66 0 (1): 0 302--323, 2020. doi:10.1109/TIT.2019.2945779. URL https://doi.org/10.1109/TIT.2019.2945779

    2020

  43. [51]

    Schapire and Yoav Freund

    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

    2012 doi

  44. [52]

    Adversarially robust generalization requires more data

    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 20...

    2018

  45. [53]

    Intriguing properties of neural networks

    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

    2013 arXiv

  46. [54]

    Leslie G. Valiant. A theory of the learnable. Commun. ACM , 27 0 (11): 0 1134--1142, 1984. doi:10.1145/1968.1972. URL https://doi.org/10.1145/1968.1972

    1984

  47. [55]

    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 0 (2): 0 264--280, 1971. doi:10.1137/1116025. URL https://doi.org/10.1137/1116025

    1971 doi

  48. [56]

    Bartlett

    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 Mac...

    2019

  49. [57]

    Distribution-free sequential prediction with abstentions

    Jialin Yu and Mo " i se 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 Ma...

    2026

  50. [58]

    Xing, Laurent El Ghaoui, and Michael I

    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,...

    2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.