Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

On the Computability of Multiclass PAC Learning

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

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

Pith's one-line read Over finite label spaces, agnostic computable PAC (CPAC) learnability is characterized exactly by the finiteness of computable distinguisher dimensions, including computable versions of the Natarajan and graph dimensions.

desk verdict A credible meta-characterization for multiclass CPAC learning; the central theorems hold up, but a few proof details need patching before I'd sign off. read the letter →

arxiv 2502.06089 v1 pith:YX7J2HQS submitted 2025-02-10 cs.LG stat.ML

Pascale Gourdeau , Tosca Lechner , Ruth Urner This is my paper · ORCID
classification cs.LGstat.ML MSC 68Q32
keywords computablePAClearningmulticlassclassificationNatarajandimensiongraphdistinguisherDSagnosticeffectiveVC
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 extends the recently introduced computable PAC (CPAC) framework, in which learners and their output predictors must be algorithms, to multiclass classification with finitely many labels. Its central claim is a meta-characterization: for any family Ψ of functions mapping labels to {0,1,*}, the "computable Ψ-dimension" — the smallest number of points for which a computable proof of non-shattering exists — characterizes agnostic CPAC learnability if and only if Ψ is a distinguisher, meaning it can separate every pair of distinct labels. In particular, the computable Natarajan and computable graph dimensions characterize CPAC learnability. This matters because it shows that adding computability requirements changes the learnability landscape: some multiclass classes that are learnable in the classical sense are not computably learnable, and the dividing line is the existence of a computable certificate that rules out shattering. The paper also proves that the DS dimension, which characterizes classical multiclass learning even with infinitely many labels, cannot be expressed through this distinguisher framework, suggesting that infinite-label computable learning will require different machinery.

What carries the argument

The load-bearing object is the computable k-witness: a total computable function that, given any set of k+1 domain points together with a Ψ-encoding of labelings, returns a {0,1}-pattern that no hypothesis in the class realizes. The computable Ψ-dimension c-Ψ-dim(H) is the least k admitting such a witness. A distinguisher is a family Ψ of functions Y→{0,1,*} with the property that for every two distinct labels y,y′ there is some ψ∈Ψ with ψ(y),ψ(y′) both in {0,1} and unequal. The witness turns "no shattering" into a concrete certificate an algorithm can check, which is precisely what lets the proof construct a computable empirical risk minimizer for a bounded-complexity superclass. The classical distinguisher theorem supplies the non-computable base; the paper effectivizes both of its directions.

What would settle it

Exhibit a hypothesis class H over a finite label space with c-N(H)<∞ that is not agnostically CPAC learnable; Theorem 18 and the embedding Lemma 19 predict no such class exists. Equivalently, search for a class where every computable witness of non-shattering exists but no computable ERM for the embedded superclass can be implemented — the proof claims the two always come together.

Watch

Extended reading notes

Core claim

We prove that for finite label spaces, a hypothesis class is agnostically CPAC learnable exactly when, for every distinguisher family Ψ, its computable Ψ-dimension is finite. The central theorem states that c-Ψ-dim(H) qualitatively characterizes CPAC learnability if and only if Ψ is a distinguisher, i.e., a family of maps from Y to {0,1,*} that separates every pair of distinct labels. The necessity direction runs through a computable Natarajan lower bound: any improperly CPAC-learnable class admits a computable k-witness that no set of k+1 points can be N-shattered. The sufficiency direction embeds the class into a superclass of bounded classical Natarajan dimension with a computable empirical risk minimizer, using the witness to certify which labelings are forbidden. As special cases, the computable Natarajan and computable graph dimensions characterize CPAC learnability. We also show that the DS dimension cannot be written as a distinguisher dimension for any family Ψ, even over finite label spaces.

Load-bearing premise

The characterization rests on the classical theorem that, for finite label spaces, the finiteness of Ψ-dimension characterizes PAC learnability exactly when Ψ is a distinguisher; the computable proof inherits that dichotomy, and the construction also assumes the domain is the natural numbers with the standard computable order.

Editorial extensions

If this is right

  • For finite label spaces, the computable Natarajan dimension and computable graph dimension each give a necessary and sufficient condition for agnostic CPAC learnability.
  • Any other classical dimension that can be defined through a distinguisher family, such as a computable Pollard pseudo-dimension, automatically yields a CPAC characterization by the meta-theorem.
  • The computable Natarajan dimension can be arbitrarily larger than the classical Natarajan dimension, so classical PAC learnability of a finite-label multiclass class does not guarantee computable learnability.
  • The DS dimension is not expressible as a distinguisher dimension even for finite label spaces, so the meta-characterization cannot be extended to the infinite-label setting by this route.
  • The computable graph dimension can exceed the computable Natarajan dimension by an arbitrary amount, mirroring the classical separation between the two.

Reading between the lines

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

  • A consequence the authors leave implicit: the witness-based definition suggests a general recipe for effectivizing any first-order shattering dimension, and the distinguisher condition is exactly what makes the certificate computably searchable when the label space is finite.
  • A natural testable extension is a computable version of the DS dimension defined by witnesses over pseudo-cubes; the non-expressibility result hints that such witnesses, not label maps, would be needed for infinite-label CPAC learning.
  • Observation 20 suggests infinite-label CPAC learnability may hold for classes with computably bounded label sets on each initial segment; one could test whether DS dimension finiteness plus such a bound implies CPAC learnability.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper studies computable PAC (CPAC) learning in the multiclass setting with finite label space. It defines computable versions of the Natarajan and graph dimensions, proves that finiteness of the computable Natarajan dimension characterizes agnostic CPAC learnability for finite Y, and then generalizes this to a meta-characterization: for finite Y, the computable Ψ-dimension c-Ψ-dim(H) qualitatively characterizes CPAC learnability if and only if Ψ is a distinguisher (Theorem 33). The paper also proves that the DS dimension, which characterizes non-computable multiclass PAC learnability for infinite label spaces, cannot be expressed as a Ψ-family for finite label spaces.

Significance. If the theorems are correct, this is a valuable and clean result: it extends the binary effective-VC-dimension picture of Sterkenburg and Delle Rose et al. to multiclass learning, unifies the computable Natarajan and graph dimensions, and shows that the classical distinguisher framework of Ben-David et al. transfers to the computable setting. The paper gives explicit constructions and machine-checkable-style witness definitions, and the central meta-characterization is falsifiable by checking whether a family separates labels. The negative result on the DS dimension is also interesting, as it indicates that the infinite-label CPAC case will require genuinely different techniques. The main structural claim is credible and builds on well-established prior results rather than on ad hoc assumptions.

major comments (3)
  1. [Theorem 25] The proof that the constructed class H' has a computable restriction function v is not correct as written. The proposed algorithm lists all patterns in Y^M and excludes a pattern p if there exists a (k+1)-subset U ⊆ [M] and labelings y,y' such that p|_U = f_{I,y,y'}|_U with I = w_N(U,y,y'). This over-excludes: a pattern can equal f_I on a tuple whose last coordinate lies beyond the support of the intended good function, even though the pattern is in G|_T. For example, with k=1 and a witness that outputs I selecting the zero label on the second coordinate, the all-zero pattern can be excluded although the constant-zero function is good. Consequently v(T) may be a proper subset of H'|T, and the claimed stopping criterion for ERM and the bound in Lemma 27 do not follow. The argument that H'|T = G|T also conflates h ∈ H with h ∈ G: for h ∈ G the claim is immediate, while for h ∈ H one needs the truncation argument; the proof should split the two cases explicitly. This is repairable by enumerating finitely supported functions according to their support size and checking goodness only on tuples within that support, but the repair must be written out.
  2. [Section 4.4, Lemma 34] The proof of the bound on c-Ψ-dim(H) is inconsistent with Definition 24. A k_B-witness is defined on inputs of size k_B+1, but the proof takes T ∈ X^{k_B} and then concludes c-Ψ-dim(H) ≤ k_B - 1; the witness constructed is therefore a (k_B-1)-witness, not a k_B-witness. In addition, the bound invoked from Lemma 27 should be |v(T)| ≤ m^{k_N+1}|Y|^{2(k_N+1)} for |T|=m, but the proof writes m^{k_N}(|Y|+1)^{2k_N}. The arithmetic also needs to be stated with m = d+1 where d is the c-Ψ-dimension. These are essentially indexing and notational errors, but as printed the proof does not formally establish the claimed inequality; it needs a careful rewrite.
  3. [Lemma 34] The proof that the DS dimension cannot be expressed as a Ψ-family is too terse to verify. The proof refers to classes H and H' and to specific label values 2, 4, 6 without first defining H or H', and the case analysis is not self-contained. The constructions of H* = {12, 32, 56, 16} and H* = {12, 16, 56, 54} are asserted without explaining how they satisfy Ψ-dim(H*) = 2 and DS(H*) = 1. Since this lemma contains the paper's closing claim about the DS dimension, the proof should be expanded into a complete argument with explicit definitions of the classes involved.
minor comments (4)
  1. [Proposition 32] The constructed witness is actually a 0-witness: it takes inputs of size 1, not 2, so the proof shows c-Ψ-dim(H) = 0, not c-Ψ-dim(H) = 1. The proposition's conclusion that a non-distinguisher can yield finite c-Ψ-dim for a non-learnable class is unaffected, but the stated value should be corrected.
  2. [Lemma 19, Equation (3)] The notation {(U,y,y') : U ⊆ [M], y,y ∈ Y^M and for all i ∈ [M] we have y_i ≠ y'_i} is ambiguous: the witness function w_N expects a (k+1)-subset U and labelings of length k+1, not length M. The set should be defined over all (k+1)-element subsets of [M] and labelings in Y^{k+1}, or the text should explain the conversion.
  3. [Definitions 12, 14, 24] The paper speaks of a 'sequence X ∈ X^{k+1}' in the witness definitions, while the shattering definitions are stated for sets S = {x_1,...,x_n}. The distinctness of the entries should be stated explicitly to avoid ambiguity, and the same convention should be used consistently in Definitions 12, 14, and 24.
  4. [Lemma 17] The proof is labeled a sketch and omits the step showing that a pair satisfying the expectation bound implies the third requirement with probability at least 1/7. The authors say this is 'nearly identical' to the No-Free-Lunch theorem; for a journal submission, this step should either be given in full or be replaced by a precise citation to the exact lemma in Agarwal et al. or Shalev-Shwartz and Ben-David.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the central meta-characterization is proved from new computable-witness definitions and the independent classical distinguisher theorem; no load-bearing step reduces to its own inputs.

full rationale

I find no step in which a claimed prediction or characterization is equivalent by construction to a fitted input or to a self-citation. The main theorem (Theorem 33) is a computable analogue of the classical distinguisher characterization (Theorem 23, Ben-David et al. 1992); the transfer requires genuinely new content: c-Psi-dim is defined via computable witnesses, the necessity direction runs through the computable Natarajan dimension and a new lower bound (Theorem 25), and the sufficiency direction constructs an extended class with bounded Psi-dimension and a computable ERM (Theorem 28, Corollary 29). Theorem 28 is explicitly conditional on finite Psi-dimension implying uniform convergence, a condition discharged for distinguishers by the cited classical theorem rather than by the conclusion being proved. The self-citations (Gourdeau et al. 2024; Lechner and Ben-David 2024) appear only as related-work framing or definitional inspiration and do not supply proof obligations for Theorem 33. Reader-flagged gaps, such as the truncated-function case split in Lemma 19, the witness-value detail in Proposition 32, and the terse Lemma 34, are local and repairable; they do not make any derivation circular.

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

No free parameters are fitted. The proofs rely on standard computability assumptions and on classical learning-theoretic results (Natarajan-Sauer bound, distinguisher characterization of Ben-David et al. 1992). No new entities are postulated; the computable dimensions are definitions, not entities.

assumptions (4)
  • standard math Classical distinguisher characterization: for finite label spaces, Ψ-dimension finiteness characterizes PAC learnability iff Ψ is a distinguisher (Theorem 23, Ben-David et al. 1992).
    This prior result is the foundation for both the classical and the computable meta-characterization. Cited in Section 4 and used to justify Corollary 29.
  • domain assumption The domain is restricted to X=N with the standard computable order.
    Section 2 states 'We will focus on the case X = N'. The constructions of 'good' functions and truncations rely on the ordering and computability of natural numbers.
  • domain assumption Finite label space Y in the main theorems.
    Theorems 18, 25, 28, 30, and 33 assume |Y|<∞. The proofs use finiteness to enumerate label patterns and compute witnesses.
  • standard math Natarajan's Sauer-type bound for classes with bounded Natarajan dimension.
    Used in Lemma 27 to bound the number of behaviors of the embedded class H'. Cited from Natarajan (1989).

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Computability of Multiclass PAC Learning." pith.science (2026). https://pith.science/paper/YX7J2HQS

@misc{pith2026250206089,
  author       = {Pith},
  title        = {Pith review of: On the Computability of Multiclass PAC Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YX7J2HQS}},
  note         = {Machine review of arXiv:2502.06089}
}
read the original abstract

We study the problem of computable multiclass learnability within the Probably Approximately Correct (PAC) learning framework of Valiant (1984). In the recently introduced computable PAC (CPAC) learning framework of Agarwal et al. (2020), both learners and the functions they output are required to be computable. We focus on the case of finite label space and start by proposing a computable version of the Natarajan dimension and showing that it characterizes CPAC learnability in this setting. We further generalize this result by establishing a meta-characterization of CPAC learnability for a certain family of dimensions: computable distinguishers. Distinguishers were defined by Ben-David et al. (1992) as a certain family of embeddings of the label space, with each embedding giving rise to a dimension. It was shown that the finiteness of each such dimension characterizes multiclass PAC learnability for finite label space in the non-computable setting. We show that the corresponding computable dimensions for distinguishers characterize CPAC learning. We conclude our analysis by proving that the DS dimension, which characterizes PAC learnability for infinite label space, cannot be expressed as a distinguisher (even in the case of finite label space).

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. Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning

    cs.LG 2025-11 conditional novelty 7.0 of 10

    For computable PAC learning, the effective VC-dimension can take any value above the VC-dimension, and every recursively enumerably representable class is nonuniformly agnostically learnable.

Reference graph

Works this paper leans on

34 extracted references · 27 canonical work pages · cited by 1 Pith paper

  1. [1]

    Computable PAC learning of continuous features

    Nathanael Ackerman, Julian Asilis, Jieqi Di, Cameron Freer, and Jean-Baptiste Tristan. Computable PAC learning of continuous features. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 1--12, 2022

    work page 2022

  2. [2]

    On learnability wih computable learners

    Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, and Ruth Urner. On learnability wih computable learners. In Algorithmic Learning Theory, pages 48--60. PMLR, 2020

    work page 2020

  3. [3]

    Regularization and optimal multiclass learning

    Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, and Shang-Hua Teng. Regularization and optimal multiclass learning. In The Thirty Seventh Annual Conference on Learning Theory, pages 260--310. PMLR, 2024

    work page 2024

  4. [4]

    Characterizations of learnability for classes of \ O,…, n \ -valued functions

    Shai Ben-David, Nicolo Cesa-Bianchi, and Philip M Long. Characterizations of learnability for classes of \ O,…, n \ -valued functions. In Proceedings of the fifth annual workshop on Computational learning theory, pages 333--340, 1992

    work page 1992

  5. [5]

    Learnability can be undecidable

    Shai Ben - David, Pavel Hrubes, Shay Moran, Amir Shpilka, and Amir Yehudayoff. Learnability can be undecidable. Nat. Mach. Intell., 1 0 (1): 0 44--48, 2019

    work page 2019

  6. [6]

    Learnability and the vapnik-chervonenkis dimension

    Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36 0 (4): 0 929--965, 1989

    1989

  7. [7]

    Multiclass boosting and the cost of weak learning

    Nataly Brukhim, Elad Hazan, Shay Moran, Indraneel Mukherjee, and Robert E Schapire. Multiclass boosting and the cost of weak learning. Advances in Neural Information Processing Systems, 34: 0 3057--3067, 2021

    work page 2021

  8. [8]

    A characterization of multiclass learnability

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

    2022

Show all 34 references
  1. [9]

    Improper multiclass boosting

    Nataly Brukhim, Steve Hanneke, and Shay Moran. Improper multiclass boosting. In The Thirty Sixth Annual Conference on Learning Theory, pages 5433--5452. PMLR, 2023

    2023

  2. [10]

    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. Advances in Neural Information Processing Systems, 36, 2024

    2024

  3. [11]

    Optimal learners for multiclass problems

    Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Conference on Learning Theory, pages 287--316. PMLR, 2014

    2014

  4. [12]

    Multiclass learnability and the erm principle

    Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the erm principle. In Proceedings of the 24th Annual Conference on Learning Theory, pages 207--232. JMLR Workshop and Conference Proceedings, 2011

    2011

  5. [13]

    Multiclass learning approaches: A theoretical comparison with implications

    Amit Daniely, Sivan Sabato, and Shai Shwartz. Multiclass learning approaches: A theoretical comparison with implications. Advances in Neural Information Processing Systems, 25, 2012

    2012

  6. [14]

    Multiclass learnability and the erm principle

    Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the erm principle. J. Mach. Learn. Res., 16 0 (1): 0 2377--2404, 2015 a

    2015

  7. [15]

    Inapproximability of truthful mechanisms via generalizations of the vc dimension

    Amit Daniely, Michael Schapira, and Gal Shahaf. Inapproximability of truthful mechanisms via generalizations of the vc dimension. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 401--408, 2015 b

    2015

  8. [16]

    Find a witness or shatter: the landscape of computable PAC learning

    Valentino Delle Rose, Alexander Kozachinskiy, Crist \'o bal Rojas, and Tomasz Steifer. Find a witness or shatter: the landscape of computable PAC learning. In The Thirty Sixth Annual Conference on Learning Theory, pages 511--524. PMLR, 2023

    2023

  9. [17]

    Effective littlestone dimension

    Valentino Delle Rose, Alexander Kozachinskiy, and Tomasz Steifer. Effective littlestone dimension. arXiv preprint arXiv:2411.15109, 2024

    2024 arXiv

  10. [18]

    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 0 (3): 0 247--261, 1989

    1989

  11. [19]

    On the computability of robust PAC learning

    Pascale Gourdeau, Tosca Lechner, and Ruth Urner. On the computability of robust PAC learning. In The Thirty Seventh Annual Conference on Learning Theory, pages 2092--2121. PMLR, 2024

    2024

  12. [20]

    Universal rates for multiclass learning

    Steve Hanneke, Shay Moran, and Qian Zhang. Universal rates for multiclass learning. In The Thirty Sixth Annual Conference on Learning Theory, pages 5615--5681. PMLR, 2023

    2023

  13. [21]

    On computable online learning

    Niki Hasrati and Shai Ben-David. On computable online learning. In International Conference on Algorithmic Learning Theory, pages 707--725. PMLR, 2023

    2023

  14. [22]

    Decision theoretic generalizations of the pac model for neural net and other learning applications

    David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and computation, 100 0 (1): 0 78--150, 1992

    1992

  15. [23]

    A generalization of sauer's lemma

    David Haussler and Philip M Long. A generalization of sauer's lemma. Journal of Combinatorial Theory, Series A, 71 0 (2): 0 219--240, 1995

    1995

  16. [24]

    Multiclass learnability beyond the pac framework: Universal rates and partial concept classes

    Alkis Kalavasis, Grigoris Velegkas, and Amin Karbasi. Multiclass learnability beyond the pac framework: Universal rates and partial concept classes. Advances in Neural Information Processing Systems, 35: 0 20809--20822, 2022

    2022

  17. [25]

    Inherent limitations of dimensions for characterizing learnability of distribution classes

    Tosca Lechner and Shai Ben-David. Inherent limitations of dimensions for characterizing learnability of distribution classes. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning R...

    2024

  18. [26]

    On learning sets and functions

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

    1989

  19. [27]

    Two new frameworks for learning

    Balas K Natarajan and Prasad Tadepalli. Two new frameworks for learning. In Machine Learning Proceedings 1988, pages 402--415. Elsevier, 1988

    1988

  20. [28]

    Multiclass learnability does not imply sample compression

    Chirag Pabbaraju. Multiclass learnability does not imply sample compression. In International Conference on Algorithmic Learning Theory, pages 930--944. PMLR, 2024

    2024

  21. [29]

    Empirical processes: theory and applications

    David Pollard. Empirical processes: theory and applications. Ims, 1990

    1990

  22. [30]

    Shifting, one-inclusion mistake bounds and tight multiclass expected risk bounds

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

    2006

  23. [31]

    Understanding Machine Learning - From Theory to Algorithms

    Shai Shalev - Shwartz and Shai Ben - David. Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, 2014

    2014

  24. [32]

    On characterizations of learnability with computable learners

    Tom F Sterkenburg. On characterizations of learnability with computable learners. In Conference on Learning Theory, pages 3365--3379. PMLR, 2022

    2022

  25. [33]

    A theory of the learnable

    Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27 0 (11): 0 1134--1142, 1984

    1984

  26. [34]

    On the uniform convergence of relative frequencies of events to their probabilities

    Vladimir Vapnik and Alexey Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Theory of Probability and Its Applications. 1971

    1971

Pith tools

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