Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

An Optimal Agnostic PAC Algorithm

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A single deterministic classifier reaches the optimal PAC error at every fixed target error L*

desk verdict 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. read the letter →

arxiv 2608.06363 v1 pith:CQKIATQS submitted 2026-08-06 cs.LG cs.AIcs.DSmath.STstat.TH

Markus Engelund Mathiasen , Jian Qian , Nikita Zhivotovskiy This is my paper · ORCID
classification cs.LGcs.AIcs.DSmath.STstat.TH MSC 68Q3262C20
keywords agnosticPAClearningVCdimensionone-inclusiongraphedgeisoperimetricinequalityRademacherwidthleave-one-outboundsamplecomplexityminimaxexcessrisk
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section 3.2, Lemma 3.1, displays (19)-(23)] 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.
  2. [Introduction, Eq. (1) and footnote 2] 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.
  3. [Section 2, Eq. (4) and Lemma 2.1 proof] 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.
minor comments (4)
  1. [Section 3.1, Eq. (13)] 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.
  2. [Section 2, Theorem 2 proof] 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.
  3. [Section 3.3, Lemma 3.3 proof] 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.
  4. [Appendix A] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the upper-bound derivation is self-contained, and the flagged issues are correctness or evidence gaps, not circular reductions.

full rationale

The upper-bound side is derived rather than assumed. Lemma 2.1 constructs random-restriction weights w_{v,p} and verifies (5)-(7) directly, using only the external projected Rademacher bound (4) from Devroye-Lugosi. Theorem 2 converts Lemma 2.1 into the coefficient-one leave-one-out bound (12) via Hall's theorem. Section 3 then converts (12) into PAC bounds through symmetrization (13), the suffix-averaging reverse/forward martingale Lemmas 3.1-3.2, and the thresholding Lemma 3.3 based on local Rademacher complexity from Bartlett-Bousquet-Mendelson. The adaptation from Aden-Ali, Cherapanamjeri, Shetty, and Zhivotovskiy [2] is reproduced in the text with full proofs rather than imported by citation, and [2] is an independent published result; the other same-author citations ([1], [19], [24]) are contextual and not load-bearing. No parameter is fitted to data, no prediction is renamed as an input, and no equation is defined in terms of the quantity it supposedly predicts. Two non-circular concerns are worth flagging explicitly. First, footnote 2 admits that the exact lower bound (1) used for the 'settles the sample complexity' claim is not stated in the cited Devroye-Gyorfi-Lugosi references, so the optimality claim has an external evidentiary gap but not a circular one. Second, the displayed displays (19), (20), and (22) in Lemma 3.1 appear to omit a denominator m^2 inside the square root; the correct term from (13) is 120*sqrt(d*Σerr)/m, not 120*sqrt(d*Σerr)/m. That is a correctness or typographical issue in the proof as written, not a circularity, since the intended estimate is derived from the leave-one-out bound rather than assumed. Score 0.

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

The central claim rests on standard learning-theoretic tools and one new combinatorial lemma (Lemma 2.1). No new physical or mathematical entities are invented. The only non-standard entry is the DGL lower bound, whose exact form is stated to follow from the cited references rather than proven here.

assumptions (5)
  • standard math Projected Rademacher width bound R_D(F) ≤ 60√(d|D|) for classes F with VC(F) ≤ d
    Used in Lemma 2.1 and Theorem 2; the paper cites Devroye and Lugosi [12] and says the constant is retained from their chaining/covering arguments.
  • domain assumption Lower bound (1) from Devroye, Györfi, and Lugosi
    The paper states the exact form is not in [10,11] but follows from their construction; no derivation is given in this manuscript.
  • standard math Local Rademacher complexity theorem of Bartlett, Bousquet, and Mendelson [7, Theorem 3.3]
    Invoked in Lemma 3.3 to convert a localized complexity estimate into a fast-rate generalization bound for the threshold class.
  • standard math Freedman's and Bernstein's martingale and deviation inequalities
    Used in Lemma 3.1 to control the reverse martingale and the binomial fluctuation of the empirical error of the reference hypothesis.
  • standard math Hall's theorem for edge orientations with capacities
    Used in Theorem 2 to convert the edge-count bound into an orientation with outdegree at most the capacity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Optimal Agnostic PAC Algorithm." pith.science (2026). https://pith.science/paper/CQKIATQS

@misc{pith2026260806363,
  author       = {Pith},
  title        = {Pith review of: An Optimal Agnostic PAC Algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CQKIATQS}},
  note         = {Machine review of arXiv:2608.06363}
}
abstract

Let $H\subseteq\{-1,+1\}^X$ be a class of finite VC dimension $d\ge1$. Writing $L$ for the binary risk and $L^*=\min_{h\in H}L(h)$, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size $n$, for every $0<\delta\le 1/2$, with probability at least $1-\delta$, \[ L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/\delta))}{n}} +\frac{d+\log(1/\delta)}{n} \right). \] This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed $L^*$, matching the lower bounds of Devroye, Gy\"orfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Optimistic Rates for Multiclass PAC Learning

    cs.LG 2026-08 accept novelty 8.0 of 10 partial

    For multiclass PAC learning, the optimal excess risk at any fixed oracle error L* equals the square root of L* times the Natarajan dimension over n, plus the realizable DS-dimension rate, with matching upper and lower bounds.

Reference graph

Works this paper leans on

30 extracted references · 17 canonical work pages · cited by 1 Pith paper

  1. [1]

    The One-Inclusion Graph algorithm is not always optimal

    Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. The One-Inclusion Graph algorithm is not always optimal. In Gergely Neu and Lorenzo Rosasco, editors,Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 ofProceedings of Machine Learning Research, pages 72–88. PMLR, 2023. URL:https://proceedings. mlr.pres...

    work page 2023

  2. [2]

    Optimal PAC bounds without uniform convergence

    Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. Optimal PAC bounds without uniform convergence. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1203–1223, Los Alamitos, CA, USA, 2023. IEEE Computer Society.doi:10.1109/FOCS57990.2023.00071

    arXiv 2023

  3. [3]

    Adversarial laws of large numbers and optimal regret in online classification

    Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. Adversarial laws of large numbers and optimal regret in online classification. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 447–455, New York, NY, USA, 2021. Association for Computing Machinery. doi:10.1145/3406325.3451041

    arXiv 2021

  4. [4]

    Regularization and optimal multiclass learning

    Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, and Shang-Hua Teng. Regularization and optimal multiclass learning. In Shipra Agrawal and Aaron Roth, editors,Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 ofProceedings of Machine Learning Research, pages 260–310. PMLR, 2024. URL:https://proceedings.mlr.press/ v247/a...

    work page

  5. [5]

    OnagnosticPAClearninginthesmallerrorregime

    JulianAsilis, MikaelMøllerHøgsgaard, andGrigorisVelegkas. OnagnosticPAClearninginthesmallerrorregime. InAdvances in Neural Information Processing Systems, volume 38, pages 123346–123388. Curran Associates, Inc., 2025. URL:https: //papers.nips.cc/paper_files/paper/2025/hash/b2a2bd5d5051ff6af52e1ef60aefd255-Abstract-Conference.html

    work page 2025

  6. [6]

    Fast learning rates in statistical inference through aggregation.The Annals of Statistics, 37(4):1591–1646, 2009.doi:10.1214/08-AOS623

    Jean-Yves Audibert. Fast learning rates in statistical inference through aggregation.The Annals of Statistics, 37(4):1591–1646, 2009.doi:10.1214/08-AOS623

    work page doi:10.1214/08-aos623 2009

  7. [7]

    Bartlett, Olivier Bousquet, and Shahar Mendelson

    Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local Rademacher complexities.The Annals of Statistics, 33(4):1497–1537, 2005.doi:10.1214/009053605000000282

    doi:10.1214/009053605000000282 2005

  8. [8]

    Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik–Chervonenkis dimension.Journal of the ACM, 36(4):929–965, 1989.doi:10.1145/76359.76371

    arXiv 1989

Show all 30 references
  1. [9]

    Theory of classification: A survey of some recent advances

    Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: Probability and Statistics, 9:323–375, 2005.doi:10.1051/ps:2005018

    2005 doi

  2. [10]

    Springer, New York, NY, 1996.doi:10.1007/978-1-4612-0711-5

    Luc Devroye, László Györfi, and Gábor Lugosi.A Probabilistic Theory of Pattern Recognition, volume 31 ofStochastic Modelling and Applied Probability. Springer, New York, NY, 1996.doi:10.1007/978-1-4612-0711-5

    1996 doi

  3. [11]

    Lower bounds in pattern recognition and learning.Pattern Recognition, 28(7):1011–1018, 1995.doi:10.1016/0031-3203(94)00141-8

    Luc Devroye and Gábor Lugosi. Lower bounds in pattern recognition and learning.Pattern Recognition, 28(7):1011–1018, 1995.doi:10.1016/0031-3203(94)00141-8

    1995 doi

  4. [12]

    Springer Series in Statistics

    Luc Devroye and Gábor Lugosi.Combinatorial Methods in Density Estimation. Springer Series in Statistics. Springer, New York, NY, 2001.doi:10.1007/978-1-4613-0125-7

    2001 doi

  5. [13]

    Springer, Berlin, Heidelberg, 5th edition, 2017.doi:10.1007/978-3-662-53622-3

    Reinhard Diestel.Graph Theory, volume 173 ofGraduate Texts in Mathematics. Springer, Berlin, Heidelberg, 5th edition, 2017.doi:10.1007/978-3-662-53622-3

    2017 doi

  6. [14]

    Richard M. Dudley. Central limit theorems for empirical measures.The Annals of Probability, 6(6):899–929, 1978. doi:10.1214/aop/1176995384

    1978

  7. [15]

    Shaddin Dughmi, Yusuf Hakan Kalayci, and Grayson York. Is transductive learning equivalent to PAC learning? In Gautam Kamath and Po-Ling Loh, editors,Proceedings of The 36th International Conference on Algorithmic Learning Theory, volume 272 ofProceedings of Machine Learning R...

    2025

  8. [16]

    Optimal prediction using expert advice and randomized Littlestone dimension

    Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran. Optimal prediction using expert advice and randomized Littlestone dimension. In Gergely Neu and Lorenzo Rosasco, editors,Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 ofProceedings of Machine Le...

    2023

  9. [17]

    Freedman

    David A. Freedman. On tail probabilities for martingales.The Annals of Probability, 3(1):100–118, 1975.doi:10.1214/aop/ 1176996452

    1975 doi

  10. [18]

    The optimal sample complexity of PAC learning.Journal of Machine Learning Research, 17(38):1–15, 2016

    Steve Hanneke. The optimal sample complexity of PAC learning.Journal of Machine Learning Research, 17(38):1–15, 2016. URL:https://www.jmlr.org/papers/v17/15-389.html. 16

    2016

  11. [19]

    Revisiting agnostic PAC learning

    Steve Hanneke, Kasper Green Larsen, and Nikita Zhivotovskiy. Revisiting agnostic PAC learning. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1968–1982, Los Alamitos, CA, USA, 2024. IEEE Computer Society.doi:10.1109/FOCS61266.2024.00118

    1968

  12. [20]

    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

    1994

  13. [21]

    Bagging is an optimal PAC learner

    Kasper Green Larsen. Bagging is an optimal PAC learner. In Gergely Neu and Lorenzo Rosasco, editors,Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 ofProceedings of Machine Learning Research, pages 450–468. PMLR, 2023. URL:https://proceedings.mlr.press/v1...

    2023

  14. [22]

    Philip M. Long. The complexity of learning according to two models of a drifting environment.Machine Learning, 37(3):337–354, 1999. Expanded version of the paper in the Proceedings of the Eleventh Annual Conference on Computational Learning Theory (COLT 1998), pp. 116–125, doi...

    1999

  15. [23]

    Cambridge University Press, New York, NY, 2014

    Ryan O’Donnell.Analysis of Boolean Functions. Cambridge University Press, New York, NY, 2014. doi:10.1017/ CBO9781139814782

    2014

  16. [24]

    Majority-of-Three is optimal, 2026

    Divit Rawal and Nikita Zhivotovskiy. Majority-of-Three is optimal, 2026. Version 1, submitted 11 June 2026.arXiv: 2606.13614

    2026 arXiv

  17. [25]

    Hans U. Simon. An almost optimal PAC algorithm. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors,Proceedings of the 28th Conference on Learning Theory, volume 40 ofProceedings of Machine Learning Research, pages 1552–1563. PMLR, 2015. URL:https://proceedings.mlr.press/v...

    2015

  18. [26]

    Leslie G. Valiant. A theory of the learnable.Communications of the ACM, 27(11):1134–1142, 1984.doi:10.1145/1968.1972

    1984

  19. [27]

    Vapnik and Alexey Ya

    Vladimir N. Vapnik and Alexey 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. A Development of the proof and AI disclosure This project bega...

    1971 doi

  20. [28]

    For \(U\subseteq\{-1,+1\}^m\), with \(D_U(y)=\{i:y^{\oplus i}\in U\}\) and internal cube edges \(E_U\), deduce \(|E_U|\le\sum_{y\in U}(\rho_V(y)+C_1\operatorname{Rad}_{D_U(y)}(V))\). To localize the Rademacher term, use that \(\rho_V\) is \(1\)-Lipschitz along cube edges, boun...

  21. [29]

    Combine this with \(\operatorname{Rad}_D(V)\le C\sqrt{d|D|}\) and the Hall orientation criterion to obtain \(\operatorname{out}(y)\le\rho_V(y)+C(\sqrt{d\rho_V(y)}+d)\); apply this to the trace of \(\mathcal H\) to obtain a coefficient-one leave-one-out bound

  22. [30]

    Fix all tie rules

    Symmetrize the rule and average over the half-sample suffix \(t=k,\ldots,2k-1\); use a backward martingale to pass from the suffix leave-one-out bounds to the realized held-out errors, and a forward martingale to pass to the population risk; then derandomize by relative valida...

Pith tools

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