Pith. sign in

REVIEW 4 minor 34 references

Optimistic Rates for Multiclass PAC Learning

T0 review · 0 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper establishes that at every fixed oracle risk $L^\star$, the optimal excess risk for a multiclass class is $\widetilde{\Theta}(\sqrt{L^\star d_N/n}+d_{DS}/n)$, with both terms forced by one class and one distribution.

desk verdict Resolves the open optimistic-rate interpolation for multiclass PAC learning with matching upper and lower bounds and a genuine partial Lean formalization; the main caveat is a disclosed dependence on very recent imported preprints. read the letter →

arxiv 2608.10869 v1 pith:BQYUP73S submitted 2026-08-11 cs.LG stat.ML

Xiaoyu Li , Andi Han , Jiaojiao Jiang , Junbin Gao This is my paper · ORCID
classification cs.LGstat.ML MSC 68Q32
keywords multiclassPAClearningoptimisticratesNatarajandimensionDSsamplecompressioncover-menu-compressionlistlowerbounds
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

Multiclass PAC learning is known at two extremes: realizable classes learn at $d_{DS}/n$, while fully agnostic classes pay $\sqrt{d_N/n}+d_{DS}/n$. This paper closes the gap by showing that at every fixed oracle risk $L^\star$ the optimal excess risk is $\widetilde{\Theta}(\sqrt{L^\star d_N/n}+d_{DS}/n)$, uniformly in the label alphabet size. The upper bound is attained by a parameter-free learner that knows neither $L^\star$ nor the confidence level, and the lower bound forces both terms at once on one class and one distribution. If the result is correct, the interpolation is intrinsic: the DS dimension pays for making correct labels visible, while the Natarajan dimension controls fluctuations that shrink with the oracle error.

What carries the argument

The load-bearing mechanism is a learned menu $\mu$, a map from points to short lists of candidate labels, which converts multiclass prediction into a selective binary problem. The selective-menu decomposition $\mathbf{L}_D(g)-\mathbf{L}_D(h)\le \mathbf{L}_\mu(g)-\mathbf{L}_\mu(h)+\alpha_\mu(h)$ separates the two error sources: $d_{DS}$ controls the probability that a correct label is missing from the menu, and $d_N$ controls the description length of the rule chosen inside the frozen menu. The new engine of the upper bound is the comparator-facing relative compression theorem: a deterministic size-$k$ rule that empirically dominates a fixed comparator $h$ has population risk at most $L(h)+O(\sqrt{L(h)\Gamma}+\Gamma)$ with $\Gamma=(k\log n+\log(1/\delta))/n$, with no stability assumption. The lower bound is carried by a noisy pair-Assouad scheme calibrated to $L^\star$ on a Natarajan cube and a fiber lemma that makes every unseen coordinate of a pseudo-cube ambiguous, forcing the $d_{DS}/n$ coverage term.

What would settle it

Search for a finite class and a distribution with oracle risk exactly $L^\star$ where a learner's expected excess risk is below $\frac{1}{12}\sqrt{L^\star d_N/n}+\frac{1}{15}\min\{d_{DS}/n,1/4\}$ for infinitely many $n$, or demonstrate that one of the imported compression/cover lemmas fails on a concrete class; either observation would refute the claimed optimal rate.

Watch

Extended reading notes

Core claim

The paper claims that multiclass classification has a single two-dimensional optimistic rate: for any class of Natarajan dimension $d_N$ and DS dimension $d_{DS}$, at every fixed oracle risk $L^\star$ the optimal excess risk is $\widetilde{\Theta}(\sqrt{L^\star d_N/n}+d_{DS}/n)$, uniformly in the alphabet size. The upper bound is achieved by a three-block learner that constructs a compression cover of size roughly $d_{DS}\log^2 n$, learns a menu of candidate labels, and then applies a new comparator-facing relative compression inequality; the learner does not know $L^\star$ or $\delta$. The matching lower bound produces one class and one distribution at every $L^\star$ that force every learner to pay both terms, combining a noisy Natarajan cube with a Natarajan-free pseudo-cube. The same two engines extend to list learning, where they yield an optimistic rate against the best $r$-tuple of hypotheses and remove a factor $r$ from the known realizable list lower bound.

Load-bearing premise

The upper-bound proof leans on three recently claimed helper results about sample compression and menu construction; if any of those helpers is wrong or does not apply under the paper's conventions, the main upper bound fails even though the surrounding argument is machine-checked.

Editorial extensions

If this is right

  • At $L^\star=0$ the formula collapses to the realizable rate $d_{DS}/n$; at constant $L^\star$ it becomes $\sqrt{d_N/n}+d_{DS}/n$, so both previously known endpoints are special cases of one bound.
  • A single learner, independent of $L^\star$ and $\delta$, attains the upper bound at every oracle level, so no meta-selection over error targets is needed.
  • The sample-complexity form $n=\widetilde{O}(L^\star(d_N+\log(1/\delta))/\epsilon^2+(d_{DS}+\log(1/\delta))/\epsilon)$ makes the allocation explicit: first resolve in-menu fluctuations at scale $L^\star$, then make correct labels visible.
  • The matching lower bound shows both terms are unavoidable at every fixed $L^\star$ on the same class and distribution, so the two-dimensional split is a property of multiclass learning and not an artifact of the analysis.
  • For list learners, the same architecture and lower-bound engines hold against the best $r$-tuple of hypotheses, with the same two-term shape and a factor-$r$ improvement in the realizable list lower bound.

Reading between the lines

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

  • The relative compression theorem is modular: replacing the imported cover or menu bounds by sharper ones would immediately sharpen the final rate, so the theorem functions as an interface as much as a result.
  • The proof's uniformity in the alphabet size suggests the two-dimensional rate could survive very large label sets, provided a realizable learner with finite DS dimension exists; the paper explicitly leaves infinite alphabets open.
  • The calibration trick of padding a noisy lower-bound family with realizable mass so the oracle risk lands exactly on $L^\star$ could be reused to build exact-fixed-risk lower bounds for other structured learning problems.
  • A cross-fitting variant of the three blocks might reduce the sample split, but the coefficient-one comparison relies on freezing the menu before the final sample, so any such variant would need new independence arguments.
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

0 major / 4 minor

Summary. The paper proves an optimistic-rate characterization for multiclass PAC learning. For a class with Natarajan dimension d_N and DS dimension d_DS, it gives a learner RMC whose excess risk over the oracle risk L* is Õ(√(L* d_N/n) + d_DS/n) at every fixed L*, with no knowledge of L* or δ (Theorem 3.1), and a matching lower bound forcing both terms simultaneously in one class and one distribution at every L* (Theorem 4.1). The upper bound is assembled from a compression cover, a learned menu, and a new comparator-facing relative compression theorem (Theorem 3.3) that compares an empirical-risk-dominating compression rule to a fixed comparator with coefficient one on the comparator risk, without a stability assumption. The lower bound combines a noisy pair-Assouad construction calibrated to L* with a fiber/leave-one-out argument on separation pseudo-cubes. Section 5 extends both directions to list learning, giving optimistic rates against the best r-tuple and a realizable list lower bound without the factor r. Appendices supply proof details, and Section D documents a Lean 4 formalization covering Theorem 3.3, the assembly behind Theorem 3.1 (with imported modules as hypotheses), and Theorem 4.1, except that Lemma 4.2 is fully discharged only at D = 2.

Significance. Assuming the imported results from [Pab26] and [CEH+26] are correct, this is a substantial contribution: it closes the interpolation gap between the known realizable and agnostic multiclass rates, and it does so with a parameter-free learner and explicit constants rather than fitted parameters. The conceptual separation of the DS dimension as a coverage cost and the Natarajan dimension as a localized fluctuation is clean and is certified by a lower bound that activates both dimensions under one distribution. The paper ships machine-checked proofs (no sorry, no ad-hoc axioms) for the relative compression theorem and the lower-bound assembly, and it is unusually transparent about which parts of the upper bound are formalized relative to imported statements. The list-learning extension and the removal of the factor r from the realizable list lower bound are interesting byproducts. The main caveat is dependency on very recent preprints, but the manuscript restates the imported modules with source locators and convention checks.

minor comments (4)
  1. [Appendix A.1 (Lemma A.1)] The displayed bound for d_RE(H) is inconsistent with the substitution in its proof: using the source sample-size bound (9.64 d_DS + log(2/δ0))/ε0 with ε0 = δ0 = 1/(18e) gives d_RE(H) ≤ ⌈9.64(18e)d_DS + 18e log(36e)⌉, whereas the printed expression appears to decay in d_DS and would be false for d_DS ≥ 4. Please correct the display; the subsequent O(d_DS) conclusion is unaffected.
  2. [Abstract and Section D] The phrase "main theorems are machine-checked" is stronger than the certificate: in the Lean formalization, rmc_master imports the six results from [Pab26] and [CEH+26] as per-block hypotheses, the final bookkeeping from (a1, a2, Γ) to the rate (3.1) is not formalized, and Lemma 4.2 is fully discharged only at D = 2. Section D already says this, but the abstract should not imply a fully unconditional formal certificate for Theorem 3.1.
  3. [Section 2.1] The notation (X, X) uses the same symbol for the input space and its sigma-algebra; please use a distinct symbol, for example (𝒳, Σ), to avoid confusion with the pointwise loss and the label notation.
  4. [Theorem 4.1 and Remark 4.6] The lower-bound family's label alphabet grows with d_DS/d_N through the [BCD+22] separation family, so the quantification "there are a finite label set [K]" in Theorem 4.1 should state explicitly that K is allowed to depend on (d_N, d_DS); Remark 4.6 explains why this is necessary, but the theorem statement currently leaves the dependence implicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the rate is derived from external imported theorems, a new comparator-facing compression bound, and self-contained lower-bound constructions; no fitted parameters or self-citation chains appear.

full rationale

I walked the derivation chain of Theorems 3.1, 3.3, 4.1, and the list extensions, looking for reductions of a claimed prediction to its own inputs. No such reduction exists. The upper bound (3.1) is assembled from (i) a new relative-compression theorem (Theorem 3.3), whose proof in Appendix A.2 is a self-contained counting-plus-Bernstein argument that fixes a comparator h and localizes at L(h); (ii) the selective-menu identity of Lemma 2.4, proved directly; and (iii) four external results — the DS-to-realizable bridge [Pab26, Cor. 1.1], the compression cover [CEH+26, Thm. 3.2], the menu guarantee [CEH+26, Thm. 3.4], and the fixed-menu compressor [CEH+26, Prop. 3.6]. All four are cited from other author teams, not from the present authors, and each is restated with its source locator in Appendix A.1. Section D explicitly records that these imported modules enter the Lean formalization as per-block hypotheses; that is an honest limitation about certification scope, not a circular step: the paper does not claim to have proved the imports, and the target rate does not appear among the imported assumptions. The lower bound (4.1) is similarly self-contained except for the separation pseudo-cube of Lemma 4.2, imported from [BCD+22] and used only to obtain a finite class with Nat = 1 and DS = D; the pair-Assouad engine (Lemma B.1), the fiber lemma (Lemma 4.5), the padded leave-one-out bound (Lemma B.2), and the dimension calculus (Lemma 4.4) are all proved in the paper, and the formalization confirms the probability core uses no imported inequalities. No parameter is fitted to data and then renamed a prediction; the claimed novelty of Theorem 3.3 is explicitly confined to its comparator-facing interface, with the concentration mechanism credited to [GKN17], which is an acknowledgement of provenance rather than a circular import. The paper's main risk is that the unformalized external preprints might be wrong or inapplicable, but that is an external-correctness risk, not self-referential circularity. I therefore find no significant circularity and score 0.

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

The central claim introduces no fitted constants; all construction parameters (block sizes, ν, γ, τ, ¯L) are explicit functions of L*, d_N, d_DS, n, and δ. The proof rests on six imported results from prior work, listed as axioms because the Lean formalization treats them as hypotheses, plus a standard measure-theoretic convention. No new postulated entities are introduced.

assumptions (7)
  • domain assumption Assumption 2.1: measurability and deterministic tie-breaking for all hypothesis evaluations, learning maps, selection maps, and reconstruction maps.
    Stated in Section 2.1 as the only regularity condition beyond iid sampling; used throughout to keep probability statements literal.
  • domain assumption Lemma A.1 (DS-to-realizable-dimension bridge): d_RE(H) ≤ C d_DS for finite-label classes, from [Pab26, Corollary 1.1].
    Imported in Appendix A.1; converts the realizable sample complexity at d_DS into the compression-cover size used in Block S1.
  • domain assumption Lemmas A.2 and A.3: a deterministic ordinary compression scheme with size O(d_RE log(en)) and a correct-region compression-cover guarantee, from [CEH+26, Propositions 3.3 and Theorem 3.2].
    Imported; these build the finite family F and the canonical witness with guarantee (2.7).
  • domain assumption Lemma A.4: finite-family menu coverage bound (S.3), from [CEH+26, Algorithm 3 and Theorem 3.4].
    Imported; gives the correct-label menu miss bound (2.8) and (3.7) in Block S2.
  • domain assumption Lemma A.5: fixed-menu loss compression of size O(d_N log p log(en)) under the inside-menu loss, from [CEH+26, Proposition 3.6].
    Imported; supplies the final empirical-risk-dominating compressor with Natarajan-size messages.
  • domain assumption Lemma 4.2: for every D there is a pseudo-cube class of DS dimension D with Natarajan dimension at most 1, from [BCD+22].
    Imported; the only external input to the lower bound, used to build the DS-side factor W on the pseudo-cube.
  • standard math Standard probabilistic tools: one-sided Bernstein inequalities, Pinsker's inequality, and the Neyman-Pearson two-point testing bound.
    Used in the relative-compression proof (Lemma A.7, self-contained) and in the pair-Assouad lower bound (Lemma B.1); the formalization uses Hellinger affinity instead of Pinsker.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimistic Rates for Multiclass PAC Learning." pith.science (2026). https://pith.science/paper/BQYUP73S

@misc{pith2026260810869,
  author       = {Pith},
  title        = {Pith review of: Optimistic Rates for Multiclass PAC Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BQYUP73S}},
  note         = {Machine review of arXiv:2608.10869}
}
abstract

Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself. For a class of Natarajan dimension $d_N$ and Daniely-Shalev-Shwartz dimension $d_{DS}$, the optimal excess risk is known at the two endpoints ($d_{DS}/n$ realizable, $\sqrt{d_N/n}+d_{DS}/n$ agnostic [HMZ24, CEH+26, Pab26]) and open in between. We close the gap: at every fixed oracle risk $L^\star$, the optimal excess risk is $\widetilde{\Theta}(\sqrt{L^\star d_N/n}+d_{DS}/n)$, uniformly in the alphabet size, attained by a learner that knows neither $L^\star$ nor the confidence level. The upper bound composes the cover-menu-compression architecture of [CEH+26], at the realizable rate of [Pab26], with a new comparator-facing relative compression theorem: a size-$k$ compression rule that empirically dominates a comparator $h$ has population risk at most $L(h)+O(\sqrt{L(h)\Gamma}+\Gamma)$ with $\Gamma=(k\log n+\log(1/\delta))/n$, without stability; this transfers the comparison principle of the sharp binary theory [MQZ26] while discarding its Boolean-cube geometry, which does not lift to multiclass labels. The lower bound forces both terms using one class and one distribution at every fixed $L^\star$, by a pair-Assouad scheme calibrated to $L^\star$ and a fiber argument on the pseudo-cubes underlying the Natarajan-versus-DS separation of [BCD+22]. Both theorems extend to list learning: against the best $r$-tuple of hypotheses, the same architecture and the same two engines yield an optimistic rate and a lower bound of the same shape, forcing the fluctuation term that [Pab26] expected to be necessary against list comparators, and removing the factor $r$ from the known realizable list lower bound.

Figures

Figures reproduced from arXiv: 2608.10869 by the authors.

Figure 1
Figure 1. The proof does not apply one complexity measure to the original multiclass loss. It first pays 𝑑DS to make correct labels visible, then pays 𝑑N to learn within the resulting menu. Then the desired comparison has the form 𝐿D (𝑔) − 𝐿D (ℎ) ≤ 𝐿𝜇 (𝑔) − 𝐿𝜇 (ℎ)  + 𝛼𝜇 (ℎ). (2.6) The first term asks how well the learner predicts inside a fixed menu. The second asks only whether the menu contains labels on which the comparat… view at source ↗
Figure 2
Figure 2. Dependency structure of the proof. Blue boxes are imported modules: each carries its source locator and the lemma below in which it is restated with its convention checks. Red boxes are proved in this paper. Gray boxes are the intermediate estimates and the pointwise identity that composes them. The concentration input to Theorem 3.3 is the one-sided Bernstein inequality of Lemma A.7 [BLM13, Sections 2.4 and 2.8]. R… view at source ↗
Figure 3
Figure 3. displays the dependency structure. separation pseudo￾cube 𝑉, Nat ≤ 1 [BCD+22]; Lemma 4.2 fiber lemma Lemma 4.5 dimension calculus: Nat and DS are additive Lemma 4.4 padded leave-one-out Lemma B.2 noisy pair-Assouad Lemma B.1 Theorem 4.1: E [PITH_FULL_IMAGE:figures/full_fig_p033_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 29 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 Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science , pages 1203--1223, 2023

    work page 2023

  2. [2]

    Regularization and optimal multiclass learning

    Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, and Shang-Hua Teng. Regularization and optimal multiclass learning. In Proceedings of the 37th Conference on Learning Theory , volume 247 of Proceedings of Machine Learning Research , pages 260--310, 2024

    work page 2024

  3. [3]

    A theory of PAC learnability of partial concept classes

    Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of PAC learnability of partial concept classes. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science , pages 658--671, 2021

    work page 2021

  4. [4]

    On agnostic PAC learning in the small error regime

    Julian Asilis, Mikael M ller H gsgaard, and Grigoris Velegkas. On agnostic PAC learning in the small error regime. In Advances in Neural Information Processing Systems 38 , 2025. arXiv:2502.09496

    arXiv 2025

  5. [5]

    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

    work page 2005

  6. [6]

    A characterization of multiclass learnability

    Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science , pages 943--955, 2022

    work page 2022

  7. [7]

    Shai Ben-David, Nicol \`o Cesa-Bianchi, David Haussler, and Philip M. Long. Characterizations of learnability for classes of \ 0, ,n\ -valued functions. Journal of Computer and System Sciences , 50(1):74--86, 1995

    work page 1995

  8. [8]

    Multiclass boosting: Simple and intuitive weak learning criteria

    Nataly Brukhim, Amit Daniely, Yishay Mansour, and Shay Moran. Multiclass boosting: Simple and intuitive weak learning criteria. In Advances in Neural Information Processing Systems 36 , pages 1403--1425, 2023

    work page 2023

Show all 34 references
  1. [9]

    Concentration Inequalities: A Nonasymptotic Theory of Independence

    St \'e phane Boucheron, G \'a bor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence . Oxford University Press, Oxford, 2013

    2013

  2. [10]

    Sample complexity of agnostic multiclass classification: Natarajan dimension strikes back

    Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang. Sample complexity of agnostic multiclass classification: Natarajan dimension strikes back. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing , 2026. arXiv:2511.12659

    2026

  3. [11]

    A characterization of list learnability

    Moses Charikar and Chirag Pabbaraju. A characterization of list learnability. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , 2023

    2023

  4. [12]

    Lower bounds in pattern recognition and learning

    Luc Devroye and G \'a bor Lugosi. Lower bounds in pattern recognition and learning. Pattern Recognition , 28(7):1011--1018, 1995

    1995

  5. [13]

    Supervised learning through the lens of compression

    Ofir David, Shay Moran, and Amir Yehudayoff. Supervised learning through the lens of compression. In Advances in Neural Information Processing Systems 29 , pages 2784--2792, 2016

    2016

  6. [14]

    Optimal learners for multiclass problems

    Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Proceedings of the 27th Conference on Learning Theory , volume 35 of Proceedings of Machine Learning Research , pages 287--316, 2014

    2014

  7. [15]

    Multiclass learnability and the ERM principle

    Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the ERM principle. Journal of Machine Learning Research , 16:2377--2404, 2015

    2015

  8. [16]

    A general lower bound on the number of examples needed for learning

    Andrzej Ehrenfeucht, David Haussler, Michael Kearns, and Leslie Valiant. A general lower bound on the number of examples needed for learning. Information and Computation , 82(3):247--261, 1989

    1989

  9. [17]

    Sample compression, learnability, and the Vapnik -- Chervonenkis dimension

    Sally Floyd and Manfred Warmuth. Sample compression, learnability, and the Vapnik -- Chervonenkis dimension. Machine Learning , 21(3):269--304, 1995

    1995

  10. [18]

    PAC - Bayesian compression bounds on the prediction error of learning algorithms for classification

    Thore Graepel, Ralf Herbrich, and John Shawe-Taylor. PAC - Bayesian compression bounds on the prediction error of learning algorithms for classification. Machine Learning , 59(1--2):55--76, 2005

    2005

  11. [19]

    Nearly optimal classification for semimetrics

    Lee-Ad Gottlieb, Aryeh Kontorovich, and Pinhas Nisnevitch. Nearly optimal classification for semimetrics. Journal of Machine Learning Research , 18(37):1--22, 2017

    2017

  12. [20]

    A sharp lower bound for agnostic learning with sample compression schemes

    Steve Hanneke and Aryeh Kontorovich. A sharp lower bound for agnostic learning with sample compression schemes. In Proceedings of the 30th International Conference on Algorithmic Learning Theory , volume 98 of Proceedings of Machine Learning Research , pages 489--505, 2019

    2019

  13. [21]

    Stable sample compression schemes: New applications and an optimal SVM margin bound

    Steve Hanneke and Aryeh Kontorovich. Stable sample compression schemes: New applications and an optimal SVM margin bound. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory , volume 132 of Proceedings of Machine Learning Research , pages 697--721, 2021

    2021

  14. [22]

    David Haussler, Nick Littlestone, and Manfred K. Warmuth. Predicting \ 0,1\ -functions on randomly drawn points. Information and Computation , 115(2):248--292, 1994

    1994

  15. [23]

    Revisiting agnostic PAC learning

    Steve Hanneke, Kasper Green Larsen, and Nikita Zhivotovskiy. Revisiting agnostic PAC learning. In Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science , 2024

    2024

  16. [24]

    An optimal Sauer lemma over k -ary alphabets, 2026

    Steve Hanneke, Qinglin Meng, Shay Moran, and Amirreza Shaeiri. An optimal Sauer lemma over k -ary alphabets, 2026. arXiv:2604.12952

    2026 arXiv

  17. [25]

    Representation preserving multiclass agnostic to realizable reduction

    Steve Hanneke, Qinglin Meng, and Amirreza Shaeiri. Representation preserving multiclass agnostic to realizable reduction. In Proceedings of the 42nd International Conference on Machine Learning , volume 267 of Proceedings of Machine Learning Research , pages 21995--22008, 2025

    2025

  18. [26]

    Improved sample complexity for multiclass PAC learning

    Steve Hanneke, Shay Moran, and Qian Zhang. Improved sample complexity for multiclass PAC learning. In Advances in Neural Information Processing Systems 37 , 2024

    2024

  19. [27]

    An optimal agnostic PAC algorithm, 2026

    Markus Engelund Mathiasen, Jian Qian, and Nikita Zhivotovskiy. An optimal agnostic PAC algorithm, 2026. arXiv:2608.06363

    2026 arXiv

  20. [28]

    Natarajan

    Balas K. Natarajan. On learning sets and functions. Machine Learning , 4(1):67--97, 1989

    1989

  21. [29]

    The optimal sample complexity of multiclass and list learning, 2026

    Chirag Pabbaraju. The optimal sample complexity of multiclass and list learning, 2026. arXiv:2604.24749

    2026 arXiv

  22. [30]

    Some extensions of an inequality of Vapnik and Chervonenkis

    Dmitriy Panchenko. Some extensions of an inequality of Vapnik and Chervonenkis . Electronic Communications in Probability , 7:55--65, 2002

    2002

  23. [31]

    Benjamin I. P. Rubinstein, Peter L. Bartlett, and J. Hyam Rubinstein. Shifting, one-inclusion mistake bounds and tight multiclass expected risk bounds. In Advances in Neural Information Processing Systems 19 , 2006

    2006

  24. [32]

    Optimistic rates for learning with a smooth loss, 2010

    Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with a smooth loss, 2010. arXiv:1009.3896. Conference version: Smoothness, low noise and fast rates, NeurIPS 2010

    2010 arXiv

  25. [33]

    Tsybakov

    Alexandre B. Tsybakov. Introduction to Nonparametric Estimation . Springer Series in Statistics. Springer, New York, 2009

    2009

  26. [34]

    Localization of VC classes: Beyond local Rademacher complexities

    Nikita Zhivotovskiy and Steve Hanneke. Localization of VC classes: Beyond local Rademacher complexities. Theoretical Computer Science , 742:27--49, 2018

    2018

Pith tools

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