{"id":"f4a0ea41-68b9-418a-ad06-fc5c9e6fb143","arxiv_id":"2608.06363","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An agnostic PAC learner attains excess risk L* + C(√(L*d'/n) + d'/n) with d' = d + log(1/δ), matching known lower bounds up to constants.","lead":"This paper presents a learning algorithm for binary classification that achieves the statistically optimal error rate up to a large constant factor, closing a gap that has been open for decades. The result settles, at the level of sample complexity, how many labeled examples any agnostic PAC learner can require for any fixed noise level.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.1's printed displays (19)-(23) contain a factor error: the leave-one-out square-root term is written as 120√(d·Σerr/m) instead of 120√(d·Σerr/m²). Taken literally, inequality (22) is false and the proof of Theorem 3 collapses; the correction from Eq.","rationale":"The central claim of the paper is two-fold: a constructive optimal upper bound (Theorem 1) and the claim that it settles the minimax rate by matching lower bounds. The reader's stated weakest assumption was the attribution of the lower bound (1), but the same reader also flagged the typesetting/proof error in Lemma 3.1. In my independent read, the more immediately load-bearing problem is the latter: Theorem 3 and Theorem 1 are derived through Lemma 3.1, and the displayed inequalities (19)-(23) use the wrong denominator in the square-root term, making the printed proof invalid. However, the error is localized and the correction is transparent from Eq. (13): the leave-one-out additive term is 120√(d·bL*/m) with bL*·(1/m)=Σerr/m² inside the root. After fixing this factor, the reverse-martingale variance and mean estimates appear to have the correct decay, and the constants work out to the claimed 8200. Thus the intended mathematics appears sound, but the manuscript as written is not fully verifiable. The lower-bound concern is also real but secondary: even if (1) is not rigorously sourced, the upper bound contribution stands; the optimality framing would be weakened but not the algorithm's guarantee. Since both issues are repairable and the reader already imposed a CONDITIONAL verdict, I see no basis to change that verdict. A careful re-derivation of Lemma 3.1 with corrected denominators is the single check that would settle the main remaining risk.","tokens_in":16444,"tokens_out":33937,"duration_ms":394148,"concrete_test":"Independently re-derive Lemma 3.1 starting from Eq. (13), writing the additive leave-one-out term as 120√(d·Σ_{i∈I_m}err_i/m²). Verify that the sum of conditional means B satisfies B/k ≤ C(√(L(h)(d+log(1/δ))/k)+(d+log(1/δ))/k), that the Freedman variance term has the matching decay, and that the constant 8200 in (16) is attained. In parallel, evaluate the printed inequality (22) at L(h)=0.1, d=1, k=10^6, δ=0.1 to confirm that, as printed, its left side exceeds the right side, isolating the factor error.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The upper-bound side of the central claim rests on Lemma 3.1, and as written the proof of that lemma is invalid. From the leave-one-out bound (13), the additive square-root term is 120√(d·bL*_S/m) = 120√(d·Σ_{i}err_i/m²). However displays (19), (20), and the bounds leading to (22)-(23) print 120√(d·Σerr/m), and after the m≥k step they use 120√(d·Σerr/k) rather than 120√(d·Σerr/k²). This is not a harmless constant change: on the event in (21), the printed first term of (22) is of constant order 120√(3d(L(h)+log(1/δ)/k)), which does not vanish as k grows, whereas the claimed right-hand side is O(√(L(h)d/k)+d/k). For L(h)=0.1, d=1, k=10^6 the printed left side is about 65 and the claimed right side is about 2.5, so (22) is false as stated; consequently (23) and the final bound (16) cannot be derived from the displayed inequalities. The intended correction is clearly recoverable from (13): replace the term by 120√(d·Σerr)/m, or equivalently put m² in the denominator inside the root. With that correction the reverse-martingale estimates appear to go through with the claimed constants, but the manuscript currently does not state them. Until Lemma 3.1 is rewritten with correct denominators, Theorem 3 and hence the upper bound in Theorem 1 are unverified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper constructs a deterministic, generally improper learner for binary classification over a VC class H, and claims a high-probability excess-risk bound of the form L(hat h) <= L* + C ( sqrt(L*(d+log(1/delta))/n) + (d+log(1/delta))/n ), matching the lower bound of Devroye, Gyorfi, and Lugosi up to universal constants at every fixed L*. The proof has three parts: a new edge-isoperimetric lemma on the Boolean cube (Lemma 2.1) yielding an orientation with outdegree rho(v) + O(sqrt(d rho(v)) + d); a leave-one-out bound (Theorem 2) and its symmetrization; and a conversion to a high-probability PAC bound by suffix averaging with reverse and forward martingale arguments, followed by a thresholding step on a validation sample. The final theorem does not use L* or delta in the algorithm.","tokens_in":16768,"tokens_out":12303,"duration_ms":147125,"significance":"If the result is correct, it resolves the distribution-free high-probability minimax excess risk for binary classification at every fixed L*, a central open question in agnostic PAC learning. The paper's main constructive contribution is Lemma 2.1, a localized edge-isoperimetric inequality that gives coefficient-one dependence on rho_F(v) and projected Rademacher widths; this is a genuine new idea compared with previous agnostic one-inclusion analyses. The constants are explicit, and the learner is deterministic and does not need L* or delta. The main caveat is that the proof of Lemma 3.1 contains a systematic display error that must be corrected before the upper bound is verified.","major_comments":[{"comment":"The square-root term in the leave-one-out bound is dimensionally incorrect as printed. Equation (13) gives a term 120 sqrt(d * Lbar_S / m) = 120 sqrt(d * sum_i err_i / m^2), i.e. 120 sqrt(d * sum_i err_i) / m. The manuscript instead writes 120 sqrt(d * sum_i err_i / m) in displays (19) and (20), and after the m >= k step uses 120 sqrt(d * sum_i err_i / k). On the event in (21), the printed first term of (22) then has order 120 sqrt(3d(L(h)+log(1/delta)/k)), which does not vanish as k grows; for example L(h)=0.1, d=1, k=10^6 gives a left-hand side of about 65 while the claimed right-hand side is about 2.5, so inequality (22) is false as stated. Consequently (23) and Lemma 3.1 are not established by the displayed inequalities. The intended correction is local and recoverable: replace the term by 120 sqrt(d * sum_i err_i) / m, equivalently 120 sqrt(d * sum_i err_i / m^2), after which the event-bound substitution appears to yield the intended displays. Because Lemma 3.1 is load-bearing for Theorem 3 and hence for Theorem 1, the proof must be rewritten with correct denominators before the upper bound can be considered verified.","section":"Section 3.2, Lemma 3.1, displays (19)-(23)"},{"comment":"The matching lower bound is asserted to follow from Devroye-Gyorfi-Lugosi [10,11], but the exact form is not stated in those references; the footnote says it follows by retaining the bounded witness in their dimension-dependent construction and combining it with deviation and realizable lower bounds. Since the abstract and introduction claim that Theorem 1 settles the sample complexity up to universal constants, this lower bound is part of the central claim. The authors should either include a self-contained proof of (1) in an appendix or give a precise derivation with theorem numbers, so that the optimality statement is checkable rather than an assertion about prior work.","section":"Introduction, Eq. (1) and footnote 2"},{"comment":"The projected Rademacher width bound R_D(F) <= 60 sqrt(d |D|) is stated to follow by 'keeping the constants' in Devroye-Lugosi [12, Sections 3.2 and 4.3] and by Dudley's bound plus chaining. Since this is the only point where the VC dimension enters the upper-bound proof and the constants feed into all later numerical constants, a short derivation or a precise statement of the covering/chaining constants should be included; the current wording is too terse for a reader to reproduce the factor 60 without going back to the cited texts.","section":"Section 2, Eq. (4) and Lemma 2.1 proof"}],"minor_comments":[{"comment":"The notation S_{-i} is used in the statement of the averaged leave-one-out bound but is defined only in the surrounding prose; it should be defined at first use in a displayed equation.","section":"Section 3.1, Eq. (13)"},{"comment":"The proof of Theorem 2 derives a strict inequality for out(v; sigma) using ceil(x) < x+1, while the theorem statement and the subsequent leave-one-out bound use non-strict inequalities; the strict/non-strict notation should be aligned for consistency.","section":"Section 2, Theorem 2 proof"},{"comment":"The constants 223000 and the application of [7, Theorem 3.3] are asserted with minimal verification ('retaining the numerical constant' in [12, Section 3.2]); a few lines showing how the local Rademacher bound and the sub-root function produce the displayed constants would substantially improve verifiability.","section":"Section 3.3, Lemma 3.3 proof"},{"comment":"Appendix A is a description of an AI-assisted proof development and a long prompt, rather than a mathematical appendix. It is unusual in a research paper and should be moved to supplementary material or shortened to a disclosure statement, depending on the journal's policy.","section":"Appendix A"}],"recommendation":"major_revision","confidential_remarks":"The main technical obstacle is a systematic typesetting error in the denominator of the square-root terms in Lemma 3.1; the intended argument appears recoverable, and the rest of the proof strategy is coherent and novel. If the authors fix the display errors and provide a proper derivation or citation for the matching lower bound, the paper would be a strong candidate for acceptance. The AI-disclosure appendix is unusual but does not affect the mathematical content."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is the real thing—an optimal agnostic PAC learner matching the Devroye–Györfi–Lugosi lower bound up to constants at every L*, with the polylog factor gone from the fast-rate term. The new edge-isoperimetric lemma (Lemma 2.1) is genuinely new: coefficient one on the distance to the trace, projected Rademacher widths, and a Hall orientation that yields the coefficient-one leave-one-out bound. The suffix-averaging conversion from Aden-Ali et al. plus the thresholding derandomization is a sensible combination, and the constants are explicit.\n\nThe soft spot is the written proof of Lemma 3.1. Displays (19)–(22) put the square root over dΣ/m and then dΣ/k instead of √(dΣ)/m and √(dΣ)/k. Taken literally, inequality (22) is false—the left side is of constant order while the right side vanishes—so the proof of Theorem 3 as printed does not go through. This is a systematic denominator error under the radical, and the correction is immediate from (13). With that correction, the reverse-martingale argument appears to go through with the claimed constants. But the manuscript as it stands does not state the corrected inequalities, so the upper bound in Theorem 1 is currently unverified.\n\nTwo smaller things. The matching lower bound (1) is attributed to Devroye–Györfi–Lugosi, but the exact form is not in their book; the footnote says it follows by retaining the bounded witness. That is probably true, but I would want the derivation spelled out before claiming the problem is settled. Also, the AI-disclosure appendix says the key lemma was found with GPT-5.6. That is not a flaw—they provide a complete proof and the lemma is checkable—but it does mean referees should verify the proof rather than defer to the authors.\n\nWho is this for? Statistical learning theorists working on PAC bounds, one-inclusion graphs, and minimax rates. It deserves a serious referee, not a desk reject. If Lemma 3.1 is fixed, this is a major result. I would send it back for revision with a request for a corrected proof of Lemma 3.1 and a fuller account of the lower bound.","headline":"Important paper with a genuinely new isoperimetric lemma; the printed proof of Lemma 3.1 has a repairable but currently invalid denominator error that must be fixed.","tokens_in":17352,"tokens_out":9771,"would_cite":true,"duration_ms":101103,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","62C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single deterministic classifier reaches the optimal PAC error at every fixed target error L*","keywords":["agnostic PAC learning","VC dimension","one-inclusion graph","edge isoperimetric inequality","Rademacher width","leave-one-out bound","sample complexity","minimax excess risk"],"falsifier":"Take a simple class such as thresholds on the real line, fix an intermediate value of L* (say L*=1/2), and compute the minimax excess risk for large n and small δ; if any learner provably achieves excess risk $o(\\sqrt{L^*(d+\\log(1/\\delta))/n})$, the claimed optimality is false. The same check can be repeated at the boundary $L^* = c(d+\\log(1/\\delta))/n$ where the two terms in the bound cross.","tokens_in":16201,"feed_emoji":"🎯","tokens_out":6154,"duration_ms":72027,"temperature":0.7,"pith_summary":"The paper constructs a deterministic classification algorithm for any class of finite VC dimension d that, from n i.i.d. samples, is guaranteed with probability at least 1−δ to have error at most L* plus a universal constant times sqrt(L*(d+log(1/δ))/n) plus (d+log(1/δ))/n, where L* is the best error achievable by the class. This matches known lower bounds at every fixed L*, interpolating between the fast realizable rate when L*=0 and the classical agnostic rate when L* is bounded away from zero. The authors claim this settles, up to universal constants, the distribution-free high-probability minimax sample complexity of agnostic PAC learning. The learner is improper, deterministic, and does not need to know L* or the confidence δ, so it can be run once and still satisfy any requested confidence.","feed_headline":"A single learner matches the optimal PAC error at every L*","feed_subtitle":"Cube orientation plus suffix averaging settles agnostic PAC sample complexity up to universal constants.","key_machinery":"The load-bearing object is Lemma 2.1, a class-dependent edge-isoperimetric inequality on the Boolean cube: there exist weights $w_{v,p} \\in [0,1]$ satisfying the edge complementary symmetry $w_{v,p}+w_{v\\oplus p,p}=1$ and the localized sum bound $\\sum_{p\\in D} w_{v,p} \\le \\rho_F(v)+R_D(F)$, where $\\rho_F(v)$ is the Hamming distance from vertex $v$ to the trace $F$ and $R_D(F)$ is the projected Rademacher width of $F$ on coordinate set $D$. These weights are constructed by randomly omitting coordinates and projecting to the nearest point of the trace; the Rademacher term is then bounded via the estimate $R_D(F)\\le 60\\sqrt{d|D|}$, the only place where the VC dimension enters. From the weights, a Hall-type orientation theorem gives a cube orientation with outdegree at most $\\rho_F(v)+120\\sqrt{d\\rho_F(v)}+7202d$, meaning the coefficient on the distance to the trace is one, and that coefficient is what keeps $L^*$ with coefficient one in the final risk bound.","core_discovery":"The central discovery is an optimal agnostic PAC learner: a deterministic, generally improper algorithm that, without knowing L* or δ, outputs a classifier with excess risk matching the lower bound up to universal constants at every fixed L*. The proof reduces the problem to orienting the Boolean cube of all labelings of the sample relative to the trace of the class. A new edge-isoperimetric lemma assigns fractional weights to cube coordinates so that, for every vertex and every coordinate subset, the sum of weights at that vertex over the subset is at most its Hamming distance to the trace plus the projected Rademacher width of the trace on that subset. This yields a leave-one-out bound with coefficient one on the empirical optimum, which suffix averaging with comparator-dependent martingales converts into a high-probability PAC bound, and a final thresholding step over the resulting score makes the predictor deterministic and binary while preserving the rate.","pith_inferences":["The same randomized-restriction weighting might transfer to multiclass or non-binary losses, where projected Rademacher widths appear naturally; the paper does not explore this extension.","Because the final derandomization proceeds by relative validation over nested threshold sets, the approach suggests a general recipe for converting symmetric but randomized score predictors into deterministic classifiers with matching rates, possibly applicable beyond one-inclusion rules.","A direct, self-contained proof of the exact lower bound in the claimed form, without relying on an attribution gap, would make the 'settles sample complexity' assertion airtight and allow one to check whether the constant gap between upper and lower bounds can be reduced.","A tighter audit of the chaining, Freedman, and threshold constants might bring the large numerical constant down from $10^8$ by several orders of magnitude, revealing how much of the gap is an artifact of the proof."],"forward_implications":["A single deterministic algorithm attains the statistically optimal PAC risk bound for every VC class and every distribution, so no distribution-specific tuning is needed.","The bound interpolates: at $L^*=0$ it recovers the realizable rate $O((d+\\log(1/\\delta))/n)$, and for $L^*$ bounded away from zero it gives the classical agnostic rate $O(\\sqrt{L^*(d+\\log(1/\\delta))/n})$.","The coefficient one on $L^*$ in the square-root term means the fast-rate term is not damped by a factor depending on $L^*$, improving on earlier bounds that carried polylogarithmic factors.","The learner uses neither $L^*$ nor $\\delta$, so it is parameter-free in the sense that it can be run once without knowing the target error or the requested confidence.","The high-probability guarantee is achieved without uniform convergence, using leave-one-out and martingale arguments instead, showing that optimal PAC learning does not require empirical risk minimization."],"supporting_citations":[{"why":"Supplies the lower bound that the algorithm's risk bound is claimed to match.","marker":"[10, 11]"},{"why":"Introduces the one-inclusion graph whose orientation is the starting point for the leave-one-out analysis.","marker":"[20]"},{"why":"Provides the original idea of orienting the entire Boolean cube for agnostic one-inclusion learning.","marker":"[22]"},{"why":"Contributes the suffix-averaging and martingale technique that converts leave-one-out bounds into high-probability PAC bounds.","marker":"[2]"},{"why":"Gives the chaining and covering arguments behind the projected Rademacher width bound used in the isoperimetric lemma.","marker":"[12]"},{"why":"Provides the local Rademacher complexity machinery used to bound the final thresholded ERM step.","marker":"[7]"},{"why":"Supplies the Hall theorem form used to turn edge-count bounds into a cube orientation with outdegree constraints.","marker":"[13]"},{"why":"Provides a related agnostic one-inclusion formalism and an all-coordinate bound that the new lemma refines.","marker":"[15]"}],"fun_headline_variants":["Optimal agnostic PAC learner hits bound","Settles agnostic PAC sample complexity","Agnostic PAC optimal risk for every L*","Tight PAC bound via cube orientation","One learner, all L*, optimal excess risk"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes that the lower bound the algorithm matches is valid in exactly the stated form at every fixed L*, even though the paper does not quote that precise two-term bound from the cited source; if the lower bound is not tight at some L*, the claim that sample complexity is settled would be too strong.","fun_headline_variants_meta":{"raw":{"variants":["Optimal agnostic PAC learner hits bound","Settles agnostic PAC sample complexity","Agnostic PAC optimal risk for every L*","Tight PAC bound via cube orientation","One learner, all L*, optimal excess risk"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000174,"raw_usage":{"total_tokens":1257,"prompt_tokens":892,"completion_tokens":365,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":508,"completion_tokens_details":{"reasoning_tokens":295}},"tokens_in":508,"tokens_out":365,"duration_ms":4917,"temperature":1.0,"reasoning_tokens":295,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:21:15.274132+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a simple class such as thresholds on the real line, fix an intermediate value of L* (say L*=1/2), and compute the minimax excess risk for large n and small δ; if any learner provably achieves excess risk $o(\\sqrt{L^*(d+\\log(1/\\delta))/n})$, the claimed optimality is false. The same check can be repeated at the boundary $L^* = c(d+\\log(1/\\delta))/n$ where the two terms in the bound cross.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the one-inclusion graph whose orientation is the starting point for the leave-one-out analysis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides a related agnostic one-inclusion formalism and an all-coordinate bound that the new lemma refines."}],"review_version":1}