{"id":"b35f31d2-1262-44bb-b856-6fdcccccc723","arxiv_id":"2608.13514","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Bagging robust ERMs achieves robust risk O(d/n) for VC classes with VC dimension d, and Ω(d*) RERM calls are necessary where d* is the dual VC dimension.","lead":"This paper proves that adversarially robust learning of VC classes can be done with sample complexity linear in the VC dimension, an exponential improvement over prior bounds. It does so with a simple bagging algorithm that runs robust empirical risk minimization on many bootstrap samples and takes a majority vote, and it proves a matching lower bound on the number of RERM oracle calls.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1 assumes an exact zero-robust-risk function f* in F, but Theorem 1 only assumes inf=0; without attainment the second-moment bound is unproved for the stated generality.","rationale":"The paper aims to prove that bagging RERMs achieves linear-in-d sample complexity for adversarially robust learning in the realizable setting, which would be a major improvement over Montasser, Hanneke, and Srebro [2019]. The proof structure is coherent: Lemma 1 gives a second-moment bound, Lemma 3 converts it to a leave-one-out bound, suffix averaging gives high probability, and sparsification via the dual VC dimension yields the final majority-vote algorithm. The lower bound in Theorem 2 is detailed and appears to address adaptivity of the oracle through the information-theoretic Lemma 11. I have no serious objection to the overall architecture or to the lower bound. My concern is specifically that Theorem 1, as stated for any distribution with inf_{f∈F} R_U(f;P)=0, is not established by the proof, because Lemma 1 requires an exact zero-risk function f⋆∈F. This is not a minor stylistic point: the whole argument for bounding the adversarial supremum rests on choosing a perturbation map φ that is independent of the label y, and the proof achieves that only by comparing all predictions to f⋆. If no exact f⋆ exists, the class of selectors one would need for Lemma 2 can have VC dimension controlled by neither d nor d⋆. A limiting argument with a sequence of functions of risk tending to zero might patch the proof, but the additive error is not analyzed and the statement 'f⋆(X)=Y with probability 1' fails for every finite-risk approximation. Since all subsequent upper-bound lemmas depend on Lemma 1, the central claim is therefore not yet proven in its stated generality. I would recommend either strengthening the assumption to exact robust realizability (there exists f⋆∈F with R_U(f⋆;P)=0) or supplying the missing approximation argument. The reader's verdict is CONDITIONAL; my concern is more specific and affects the main theorem's statement, so I move the verdict to UNVERDICTED until the gap is resolved.","tokens_in":27790,"tokens_out":23168,"duration_ms":241890,"concrete_test":"Restate and check Lemma 1 under the stronger hypothesis 'there exists f⋆∈F with R_U(f⋆;P)=0' versus the stated inf=0. Concretely, construct a countable VC class F={f_k} and a distribution P with error sets E_k satisfying P(E_k)=2^{-k} and inf_k P(E_k)=0 but no f_k with P(E_k)=0 (e.g., a dyadic partition), and compute the RERM second moment E_{(X,Y)}[sup_{z∈U(x)} Pr_{S~P^n}[bf_S(z)≠Y]^2] for a natural deterministic RERM oracle. If the quantity is Θ(1) while c d/n is small, the theorem fails in the stated inf=0 regime; if it is O(d/n), identify the missing argument that avoids an exact f⋆. A purely analytical version: re-derive Lemma 1 allowing f_k with risk δ_k and show the additive term tends to 0 uniformly in n; if it does not, the inf=0 case requires a separate proof.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"Section 4.1, Lemma 1, is the foundation of the upper bound: it yields the second-moment bound E[a(X,Y)^2] ≤ c d/n, which is fed into Lemma 3, Lemma 4, Lemma 6, and finally Theorem 1. In the proof, after establishing (7) for an arbitrary fixed perturbation map φ, the author writes 'Fix an arbitrary f⋆ ∈ F such that R_U(f⋆;P)=0' and chooses φ_η(x) as an approximate maximizer of Pr_{S~P^n}[bf_S(z)≠f⋆(x)]. But the theorem's assumption is only inf_{f∈F} R_U(f;P)=0; nothing guarantees that the infimum is attained, since F is an arbitrary VC class with no closedness or compactness assumed. If no exact f⋆ exists, the construction of φ_η is not available. This is not cosmetic: the reason for using f⋆ is to make φ independent of the true label y, so that the selector C(S) = {(x,y): bf_S(φ(x))≠y} lies in a class C_φ of VC dimension at most d. Allowing φ to depend on y would make the effective class potentially much larger than F, so Lemma 2 would not apply. Replacing f⋆ by a sequence f_k with R_U(f_k;P)→0 introduces an additive approximation error that is not analyzed; the displayed statement 'Since f⋆(X)=Y with probability 1' fails for each f_k unless its error set is empty. Thus, as written, Lemma 1—and hence Theorem 1 for the stated inf-condition—is unproved. The measurable-selection step for φ_η is a related gap, but the attainment issue is the load-bearing one.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":28149,"tokens_out":37198,"duration_ms":403802,"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":[{"comment":"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.","section":"§4.1, Lemma 1"},{"comment":"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.","section":"§4.1, text after (7)"},{"comment":"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.","section":"§5, Theorem 2"}],"minor_comments":[{"comment":"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.","section":"§4.2, Lemma 4 and Theorem 1"},{"comment":"The abstract contains the typo 'indpendent'; it should be 'independent'.","section":"Abstract"},{"comment":"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.","section":"§5.1, parameter definitions"},{"comment":"The reference 'Aden-Ali, Høandgsgaard, Larsen, and Zhivotovskiy [2024]' appears with a misspelled author name; the spelling 'Høandgsgaard' should be corrected.","section":"References"},{"comment":"The notation F={F} for the finite collection of classes is confusing; denoting the collection by {F_pi}_pi would be clearer.","section":"§5, Theorem 2 statement"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is not circular: the upper bound derives from independent second-moment, suffix-averaging, and sparsification results, and the lower bound is an explicit construction. The main risk is the formal statement of Theorem 2: if a reader interprets the learner as knowing the realized class F_pi, the lower bound is false. The oracle-only model is implicit in the abstract and discussion but should be made explicit in the theorem statement. The upper-bound gaps in Lemma 1 are local and repairable, so I do not see a reason to reject on technical grounds."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: this is an important paper with a real gap in the upper-bound proof as written. The bagging algorithm and the lower bound are the real news; the stated inf=0 version of Theorem 1 is not proven.\n\nWhat's genuinely new: a simple improper learner—bagged RERMs with N=O(d*) bootstrap samples and majority vote—that would give linear-in-d sample complexity if the proof holds, and a matching Omega(d*) oracle-call lower bound. The lower bound construction is explicit and the information-usage argument is clever. The paper also resolves Conjecture 3 of Montasser–Hanneke–Srebro 2022 and improves several reduction bounds.\n\nThe soft spot is load-bearing. Lemma 1 fixes f* in F with R_U(f*;P)=0, then builds phi_eta as an approximate maximizer of Pr[bf_S(z) ≠ f*(x)]. But Theorem 1 only assumes inf_{f in F} R_U(f;P)=0. For an arbitrary VC class there is no guarantee the infimum is attained, and without f* the construction of the label-independent perturbation map breaks. Replacing f* by a sequence f_k with R_U(f_k) -> 0 adds an error term that is not analyzed; 'f*(X)=Y with probability 1' fails for each f_k. Since Lemma 1 is the foundation for Lemmas 3, 4, 6, and Theorem 1, the upper bound is unproved for the stated generality. This looks fixable—either require attainment or add a slack/approximation argument—but it is a real gap, not a stylistic quibble.\n\nTwo smaller concerns: the measurable-selection step for phi_eta is hand-wavy, and Appendix A says the martingale bounds apply 'verbatim' to the margin-robust loss, which is not quite a standard loss; that needs more detail. The AI disclosure is honest, but the proofs deserve independent verification for that reason.\n\nThe lower bound looks solid to me: the dual-VC obstruction is convincing, and the total-variation/bias control is a nice application of Russo–Zou. Even if the upper bound needs repair, the oracle lower bound is a substantial contribution on its own.\n\nWho should read this: anyone working in adversarial robust learning theory. It deserves a serious referee—send it to a top venue—but the author should be required to fix the attainment issue or restate the theorem to match what is actually proven.","headline":"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.","tokens_in":28702,"tokens_out":3023,"would_cite":true,"duration_ms":30416,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["adversarial robustness","bagging","robust empirical risk minimization","VC dimension","dual VC dimension","sample complexity","oracle complexity","improper learning"],"falsifier":"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.","tokens_in":27578,"feed_emoji":"🛡️","tokens_out":8530,"duration_ms":85298,"temperature":0.7,"pith_summary":"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.","feed_headline":"Robust learning now needs O(d) samples, not 2^d","feed_subtitle":"Majority-voting O(d*) robust ERMs achieves O(d/n) risk—and Ω(d*) calls are provably required.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the previous exponential-in-d upper bound, the proper-learning separation that motivates improper robust learners, and the agnostic-to-realizable reduction used in Corollary 1.","marker":"Montasser, Hanneke, and Srebro [2019]"},{"why":"Introduces bagging, the classic algorithm whose robust-ERM variant is analyzed here.","marker":"Breiman [1996]"},{"why":"Provides the suffix-averaging technique used to convert the leave-one-out bound into a high-probability bound.","marker":"Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [2023]"},{"why":"Supplies the second-moment bound for consistent VC selectors that underlies Lemma 1, the key probabilistic estimate of the upper bound.","marker":"Aden-Ali, Høandgsgaard, Larsen, and Zhivotovskiy [2024]"},{"why":"Co-supplies the second-moment bound for consistent VC rules used in Lemma 2.","marker":"Rawal and Zhivotovskiy [2026]"},{"why":"Provides the sparsification result over the dual class that determines the N = O(d*) bootstrap-sample count in Theorem 1.","marker":"Moran and Yehudayoff [2016]"},{"why":"Gives the general bound d* ≤ 2^{d+1} − 1 and the parameter choices used in the lower-bound construction.","marker":"Assouad [1983]"},{"why":"Shows that bagging is an optimal PAC learner in the classical setting and provides the full-bagging viewpoint adapted here to robust risk.","marker":"Larsen [2023]"},{"why":"Supplies the information-usage method controlling data-dependent selection bias, a component of the lower-bound Lemma 11.","marker":"Russo and Zou [2020]"},{"why":"Provides the tensorization of relative entropy over independent coordinates used in the lower-bound information analysis.","marker":"Madiman and Tetali [2010]"}],"fun_headline_variants":["Robust learning now linear: O(d) samples, not 2^d","Bagging majority vote cracks robust VC learning","Exponential to linear: robust sample complexity slashed","Dual VC dimension sets robust oracle calls","Linear robust learning via bagged RERM majority"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Robust learning now linear: O(d) samples, not 2^d","Bagging majority vote cracks robust VC learning","Exponential to linear: robust sample complexity slashed","Dual VC dimension sets robust oracle calls","Linear robust learning via bagged RERM majority"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000195,"raw_usage":{"total_tokens":1338,"prompt_tokens":910,"completion_tokens":428,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":526,"completion_tokens_details":{"reasoning_tokens":350}},"tokens_in":526,"tokens_out":428,"duration_ms":5248,"temperature":1.0,"reasoning_tokens":350,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:21:12.597365+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"VC classes are adversarially robustly learnable, but only improperly","cited_arxiv_id":null,"evidence_quote":"Supplies the previous exponential-in-d upper bound, the proper-learning separation that motivates improper robust learners, and the agnostic-to-realizable reduction used in Corollary 1."},{"cited_title":"Densit \\'e et dimension","cited_arxiv_id":null,"evidence_quote":"Gives the general bound d* ≤ 2^{d+1} − 1 and the parameter choices used in the lower-bound construction."},{"cited_title":"Bagging is an optimal PAC learner","cited_arxiv_id":null,"evidence_quote":"Shows that bagging is an optimal PAC learner in the classical setting and provides the full-bagging viewpoint adapted here to robust risk."}],"review_version":1}