{"id":"42537ffd-3bec-44ad-a45d-c218031c4371","arxiv_id":"2502.06089","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Computable multiclass PAC learnability for finite label spaces is characterized exactly by the finiteness of computable distinguisher dimensions, including a new computable Natarajan dimension.","lead":"This paper defines computable versions of standard multiclass learning dimensions and proves they characterize when a learning problem can be solved by an algorithm that always halts and outputs a computable predictor. It shows that a broad family of such dimensions, the distinguishers, all work, and that one known dimension for infinite labels cannot be captured this way.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the central meta-characterization is credible and the flagged proof gaps are local, repairable issues rather than load-bearing flaws.","rationale":"The paper's central claim is a computable analogue of a classical characterization. I examined the three main pillars. (1) Necessity: Theorem 16 constructs a computable Natarajan witness from a CPAC learner using a computable no-free-lunch search; the search terminates because the expected risk is exactly computable and the classical lower bound guarantees a witness. (2) The embedding lemma: the 'truncation' argument for H'|_T = G|_T is valid once one notes that any bad pattern in the truncation would be a witness violation for H. (3) Sufficiency: the constructed H' has classical Ψ-dimension at most k+1 and a computable ERM because the good functions on [M] are finitely enumerable using the witness. The flagged off-by-one in Proposition 32 does not affect the theorem, since 'finite' is the operative condition. The proof of Lemma 19's N(H')≤k+1 can be repaired by choosing the added point so that the label prescribed by the witness is nonzero, or by omitting it from the witness subset when g1 is zero at that point. I therefore see no reason to move the verdict; the paper remains conditionally acceptable pending the minor corrections the reader identified.","tokens_in":17337,"tokens_out":38775,"duration_ms":356216,"concrete_test":"Run the following check on Proposition 32: for H = all functions from N to {y1,y2} with Ψ collapsing y1,y2, exhibit the 0-witness that outputs, for each x and ψ, the bit 1−b where b is the value (if any) that neither ψ(y1) nor ψ(y2) equals. If this 0-witness exists, the proposition's stated value is an off-by-one and should be amended to 'finite'; the finiteness argument for Theorem 33 remains valid. This check also isolates whether any hidden issue in the witness definition is responsible for the mismatch.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing concern that would invalidate Theorem 33. The meta-characterization depends on the classical Ben-David et al. (1992) distinguisher theorem, which is a standard, accepted result; the computable transfer is built on Lemmas 17 and 19, whose arguments I checked in detail. The concrete issues the reader flags are real but local: Proposition 32's counterexample class actually admits a 0-witness, so its c-Ψ-dim is 0 rather than 1, but the conclusion that a non-distinguisher can give finite dimension for a non-learnable class still stands; Lemma 19's 'WLOG' ordering of the two labels near the added point needs a small case split when g1(k+2)=0; and Lemma 34 is terse. None of these touches the central equivalence, and each has an evident repair. The one external input that is genuinely load-bearing — that for a distinguisher, finite Ψ-dimension yields uniform convergence — is inherited from the cited classical theorem and is not in tension with current consensus.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17496,"tokens_out":20971,"duration_ms":183487,"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":[{"comment":"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.","section":"Theorem 25"},{"comment":"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.","section":"Section 4.4, Lemma 34"},{"comment":"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.","section":"Lemma 34"}],"minor_comments":[{"comment":"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.","section":"Proposition 32"},{"comment":"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.","section":"Lemma 19, Equation (3)"},{"comment":"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.","section":"Definitions 12, 14, 24"},{"comment":"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.","section":"Lemma 17"}],"recommendation":"major_revision","confidential_remarks":"The main characterization theorem (Theorem 33) is plausible and appears to be correct in substance, but the proofs of several load-bearing lemmas contain real gaps and indexing errors that must be fixed before the paper can be accepted. The issues in Lemma 19 (the computable enumeration of G|T) and Theorem 25 (witness indexing) are local and repairable, but they are not purely cosmetic: as written, the proofs do not establish the claimed results. The DS-dimension lemma also needs a complete proof. I recommend major revision rather than rejection because the central ideas are sound and the repairs are evident."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper gives the first multiclass analogue of the binary CPAC characterization: it defines computable Natarajan and graph dimensions, then generalizes to computable distinguishers. The main result, Theorem 33, is a clean meta-characterization: a family of embeddings Ψ yields a computable dimension that characterizes CPAC learnability iff Ψ is a distinguisher. That is a natural and useful outcome, and getting there required real work, not just re-indexing binary proofs.\n\nWhat's genuinely new: the computable Natarajan dimension, the computable distinguisher dimensions, and the proof that the DS dimension cannot be expressed as a distinguisher. The DS non-expressibility result is a nice standalone observation. The necessary-condition proof (Theorem 16) is a honest multiclass extension of the no-free-lunch argument, and the construction in Lemma 19—embedding H into a class of 'good' functions with controlled Natarajan dimension and a computable ERM—is the technical heart and it works. The paper also avoids circularity: the new theorems are proved from the definitions, and the dependence on Ben-David et al. (1992) is standard and appropriate.\n\nThere are a few real but local soft spots. Proposition 32's example: the witness described is actually a 0-witness, so c-Ψ-dim is 0, not 1 as claimed. The conclusion (a non-distinguisher can give finite dimension for a non-learnable class) still stands, but the proof should be corrected. Lemma 19's case analysis has a small gap: when h(x_{k+2})=0 through the WLOG label ordering, the case where g1(x) itself is 0 needs a separate split. The fix is easy but should be spelled out. Lemma 34 is too terse; the case analysis jumps, and the H* examples need a few more lines to be checkable. None of these touch the central equivalence, and each has an evident repair.\n\nBottom line: this is a solid contribution to computational learning theory. The right readers are theory people working on computable or multiclass learnability; it won't change practice outside that circle, but it moves the subfield forward. It deserves a serious referee, and with those proof patches I'd be comfortable with acceptance. I'd bring it to reading group and cite it in my own work.","headline":"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.","tokens_in":18011,"tokens_out":2195,"would_cite":true,"duration_ms":19905,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["computable PAC learning","multiclass classification","Natarajan dimension","graph dimension","distinguisher","DS dimension","agnostic learning","effective VC dimension"],"falsifier":"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.","tokens_in":17120,"feed_emoji":"🧮","tokens_out":7973,"duration_ms":66331,"temperature":0.7,"pith_summary":"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.","feed_headline":"Computable multiclass learning collapses to a 'distinguisher' test","feed_subtitle":"A finite computable shattering dimension certifies learnability exactly when its label map separates every pair of labels.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Sets the CPAC framework with computable learners and decidably representable hypothesis classes, which the paper adopts and extends to multiclass classification.","marker":"Agarwal et al. (2020)"},{"why":"Defines distinguishers and proves that Ψ-dimension finiteness characterizes classical multiclass PAC learnability exactly for distinguishers; Theorem 23 is the non-computable base of the meta-characterization.","marker":"Ben-David et al. (1992)"},{"why":"Introduces the Natarajan and graph dimensions and the sample-size bound used in Lemma 27 to bound the number of labelings on a finite set.","marker":"Natarajan (1989)"},{"why":"Gives the binary CPAC necessity result with the witness/certificate approach that the computable Natarajan lower bound adapts to the multiclass setting.","marker":"Sterkenburg (2022)"},{"why":"Defines the effective VC dimension and proves the binary CPAC sufficiency via embedding; the multiclass sufficiency proof generalizes this approach.","marker":"Delle Rose et al. (2023)"},{"why":"Introduces the DS dimension and shows finiteness is necessary for multiclass PAC learning with infinite labels, the object Lemma 34 studies.","marker":"Daniely and Shalev-Shwartz (2014)"},{"why":"Proves DS dimension sufficiency and exhibits separations between Natarajan and DS dimensions, contextualizing why the DS dimension sits outside the distinguisher framework.","marker":"Brukhim et al. (2022)"}],"fun_headline_variants":["Computable PAC learning collapses to a dimension test","Distinguisher dimensions exactly capture computable multiclass learning","No computable distinguisher for DS dimension, even finite labels","Computable Natarajan dimension characterizes CPAC learnability","Multiclass learning: computable dimensions characterize the whole picture"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Computable PAC learning collapses to a dimension test","Distinguisher dimensions exactly capture computable multiclass learning","No computable distinguisher for DS dimension, even finite labels","Computable Natarajan dimension characterizes CPAC learnability","Multiclass learning: computable dimensions characterize the whole picture"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000798,"raw_usage":{"total_tokens":3525,"prompt_tokens":975,"completion_tokens":2550,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":591,"completion_tokens_details":{"reasoning_tokens":2469}},"tokens_in":591,"tokens_out":2550,"duration_ms":18400,"temperature":1.0,"reasoning_tokens":2469,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T16:49:57.563127+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"On learnability wih computable learners","cited_arxiv_id":null,"evidence_quote":"Sets the CPAC framework with computable learners and decidably representable hypothesis classes, which the paper adopts and extends to multiclass classification."},{"cited_title":"Characterizations of learnability for classes of \\ O,…, n \\ -valued functions","cited_arxiv_id":null,"evidence_quote":"Defines distinguishers and proves that Ψ-dimension finiteness characterizes classical multiclass PAC learnability exactly for distinguishers; Theorem 23 is the non-computable base of the meta-characterization."},{"cited_title":"On learning sets and functions","cited_arxiv_id":null,"evidence_quote":"Introduces the Natarajan and graph dimensions and the sample-size bound used in Lemma 27 to bound the number of labelings on a finite set."},{"cited_title":"On characterizations of learnability with computable learners","cited_arxiv_id":null,"evidence_quote":"Gives the binary CPAC necessity result with the witness/certificate approach that the computable Natarajan lower bound adapts to the multiclass setting."},{"cited_title":"Find a witness or shatter: the landscape of computable PAC learning","cited_arxiv_id":null,"evidence_quote":"Defines the effective VC dimension and proves the binary CPAC sufficiency via embedding; the multiclass sufficiency proof generalizes this approach."}],"review_version":1}