{"id":"91e2683b-ce69-4d8f-8ce1-83e80589f191","arxiv_id":"2511.02644","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"This theory paper studies machine learning when learners must be computable functions, not just arbitrary ones. It shows the effective VC-dimension can be wildly larger than the classical one even for algorithmically listable hypothesis classes, and that listable classes are always learnable in a relaxed 'nonuniform' sense.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified. Theorem 3.2 and Theorem 5.3 are mathematically sound; the only weakness is reliance on unpublished thesis [K25] for some supporting results.","rationale":"I re-derived the key steps of Theorem 3.2. The enumeration of pairs and the partition of evens are computable; H_E has pairwise disjoint supports and VCdim 1; G has VCdim k-1; Step III's membership test is a correct decision procedure; Step IV's witness is computable and satisfies the witness condition (the case h∈G requires treating h_e' as the zero function, but the argument is unchanged); Step V is a sound diagonalization against any computable (ℓ−1)-witness, using the fact that the pair enumeration contains a machine computing the projected witness. Thus Theorem 3.2 holds. Theorem 5.3's SRM construction is also sound: Hoeffding gives (5.4), F(n)=E_S(h_n)+n√(mb) is computably minimizable because a finite cutoff N suffices, and s(b)=4b^5 is computable. The main residual issue is that the paper defers several supporting results to [K25], an unpublished thesis; this is a verifiability concern, not a correctness flaw. I therefore see no load-bearing mathematical objection; the reader's CONDITIONAL verdict remains appropriate.","tokens_in":17244,"tokens_out":27139,"duration_ms":252446,"concrete_test":"Prove Lemma 3.1 directly: show that for disjoint-support G,H with 0, a set A is shattered by G⊕H iff A∩supp(G) is shattered by G and A∩supp(H) by H; this yields additivity. Also archive [K25] (or include the deferred proofs) so Corollary 4.5 and 5.8 can be checked.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims survive scrutiny. Theorem 3.2's construction is a valid diagonalization: Step III's membership test correctly identifies G⊕H_E, Step IV's witness works (with a trivial patch for h∈G, where h_e' is the zero function), and Step V's lower bound is a standard acceptable-numbering diagonalization. The only local result used without proof is Lemma 3.1, which is elementary: for disjoint-support G,H both containing 0, any shattered set splits into parts in supp(G) and supp(H), so VCdim(G⊕H)=VCdim(G)+VCdim(H); this does not threaten Theorem 3.2. The genuine but non-mathematical weakness is that several supporting results (Corollary 4.5, Corollary 5.8, details behind Remark 4.4) are deferred to the first author's unpublished master's thesis [K25], hampering independent verification. This is a verifiability issue, not a correctness risk.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies computable PAC (CPAC) learning, the effective VC-dimension, and recursively enumerably representable (RER) hypothesis classes. The central contributions are: (1) Theorem 3.2, which constructs, for every 1 ≤ k ≤ ℓ ≤ ∞, an RER class H_{k,ℓ} ⊆ H_fin with VCdim(H_{k,ℓ}) = k and eVCdim(H_{k,ℓ}) = ℓ, showing that the effective VC-dimension can be arbitrarily larger than the classical one even for algorithmically listable classes; (2) Proposition 3.3, which shows that existence of a total computable ERM forces equality of the two dimensions; (3) Section 4, which characterizes proper strong CPAC learnability via containment of an RER subclass realizing the same samples, and proves that unique-identification (UIP) classes that are realizably CPAC learnable must be RER; and (4) Theorem 5.3, which shows that every RER class is properly nonuniformly CPAC learnable via a computable structural risk minimizer. The proofs are constructive and, for the main theorems, internally consistent; the primary weakness is the deferral of several supporting results to the first author's unpublished master's thesis [K25].","tokens_in":17431,"tokens_out":15767,"duration_ms":140418,"significance":"If the results stand, they substantially clarify the computable-learning landscape. The construction in Theorem 3.2 rules out any general relationship between VCdim and eVCdim beyond the trivial inequality, even under the strong RER and finite-support assumptions; this is a meaningful sharpening of the earlier example of Delle Rose et al. with VCdim 1 and eVCdim ∞. Proposition 3.3 identifies a clean sufficient condition for equality. The RER-based characterizations in Section 4 give a useful sample-realization perspective on proper SCPAC learnability, and the SRM construction in Section 5 shows that the RER property alone guarantees a relaxed agnostic learnability notion. The paper is careful with the many variants of PAC learning, provides a helpful table of notions, and is honest about which auxiliary results are deferred. The main mathematical claims are plausible and the proofs of Theorems 3.2, 4.2, and 5.3 are detailed enough to be checked. The main deficit is not correctness but self-containedness: several load-bearing lemmas and corollaries are relegated to [K25], which is not a peer-reviewed publication.","major_comments":[{"comment":"The computation VCdim(H_{k,ℓ}) = k in Theorem 3.2 rests entirely on Lemma 3.1, which is stated without proof and deferred to [K25, Lemma 3.51]. Since [K25] is an unpublished master's thesis, this is a load-bearing gap in an otherwise self-contained proof. The lemma is elementary, but the reader should not have to consult an external thesis to verify the central claim. Please include a proof, or at least a complete proof sketch, in the paper.","section":"§3, Lemma 3.1"},{"comment":"The proof of Theorem 5.3 relies on the SRM guarantee (5.6), which is stated as 'one can show' and deferred to [K25, Lemma 4.14]. This inequality is the central mechanism that converts a computable SRM into a nonuniform PAC learner, so it is load-bearing. The proof is not long and should be included. Similarly, the realizable version of Fact 2.8 used in Theorem 4.2 is deferred to [K25, p. 65ff]; please include that argument as well.","section":"§5, Lemma 5.2 and Theorem 5.3"},{"comment":"Several results used in the paper's summary and Table 3 are deferred to [K25]: the non-strong CPAC analog in Remark 4.4, Corollary 4.5 ('For a full proof see [K25, Corollary 3.58]'), and Corollary 5.8 ('See [K25, Proposition 4.23] for details'). These are not merely peripheral: Corollary 4.5 is stated as a characterization of agnostic CPAC learnability and Corollary 5.8 as a necessary condition for nonuniform CPAC learnability. For archival publication, these should be proved in the text or replaced by references to published, accessible sources.","section":"§4, Remark 4.4 / Corollary 4.5 and §5, Corollary 5.8"}],"minor_comments":[{"comment":"In the bibliography, the second author of [BS14] is spelled 'Shalez-Shwartz'; this should be 'Shalev-Shwartz'.","section":"References"},{"comment":"The phrase 'a computable function A′:N⇀N of A' is awkward; it should say 'a computable function A′ representing A' or 'such that A′ computes A'.","section":"Definition 2.6"},{"comment":"In the enumeration of pairs ((T_j, k_j)), saying that 'the maps j↦code(T_j) and j↦k_j are computable' is redundant once a computable enumeration is fixed; consider simplifying the phrasing.","section":"§3, Step I"},{"comment":"In the proof, the line 'Prob ≥ 1/2 > 0' implicitly uses the realizable PAC guarantee with confidence parameter b = 2. This is correct but should be stated explicitly to avoid confusion.","section":"Lemma 4.7"},{"comment":"The witness-based definition of VC-dimension is nonstandard. A one-sentence explanation of its equivalence to the usual shattering definition would improve readability for readers more familiar with the standard formulation.","section":"Definition 2.3"}],"recommendation":"major_revision","confidential_remarks":"The paper's mathematical core is sound, but it leans heavily on the first author's master's thesis [K25] for several supporting results, including Lemma 3.1, the realizable version of Fact 2.8, Corollary 4.5, and Corollary 5.8. This is a verifiability problem rather than a correctness problem. I would urge the editor to require the authors to make the paper self-contained on exactly these points, or to ensure [K25] is publicly archived in a stable, citable form. If those proofs are added, the paper would be suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things before reading this paper: the main constructions are correct, and the only real problem is verifiability. Several supporting results are deferred to Kattermann's master's thesis [K25]. The thesis is deposited with a URN, so it is not hidden, but it is still not the same as having the proofs in the paper or in a permanent, widely indexed venue.\n\nThe genuinely new content is Theorem 3.2, which constructs RER classes realizing every pair k≤ℓ as VCdim and eVCdim, generalizing the single example in DKR+23. I checked the diagonalization: the membership decision in Step III works, the computable ℓ-witness in Step IV works, and the lower bound in Step V is a standard acceptable-numbering argument. The odd-k case is handled by analogy and is routine. Lemma 3.1 is the one load-bearing local result stated without proof, but it is elementary—disjoint supports split any shattered set into independent parts—so it is not a correctness risk. Proposition 3.3 is clean and useful: total computable ERM collapses eVCdim down to VCdim. Theorem 4.2 and Corollary 4.3 give a nice structural characterization of proper SCPAC learnability via containment of an RER class with the same realized samples. Proposition 4.8 is a satisfying partial converse: under a unique identification property, realizable CPAC learnability forces the class to be RER.\n\nThe most interesting result is Theorem 5.3: every RER class is properly nonuniformly CPAC learnable in the agnostic sense, with no dependence on VCdim or eVCdim. The SRM proof is correct, and the sample size is polynomial-ish in a, b, and the index of the hypothesis. That is a real positive result, not a restatement.\n\nSoft spots: the paper leans on [K25] for Lemma 3.1, Corollary 4.5, the asymptotic-ERM variant in Remark 4.4, Corollary 5.8, and parts of the SRM background. None of these look wrong, and the reader/stress-test both say the central claims survive scrutiny. I agree. But a referee will reasonably ask the authors to move those proofs into an appendix or ensure the thesis is openly archived. The acceptable Gödel numbering assumption in Step V should also be stated explicitly; it is standard, but it is an assumption.\n\nThis paper deserves a serious referee. It is not a breakthrough, but it is careful, correct, and answers natural open-ended questions in the computable-PAC-learning program. I would send it out, with a request that the missing proofs be included or made trivially accessible. I would cite it, especially for Theorem 3.2 and Theorem 5.3.","headline":"Solid, useful paper: it fills the gap between VCdim and eVCdim for all pairs k≤ℓ on RER classes and shows every RER class is properly nonuniformly CPAC learnable; the main weakness is that several supporting proofs live in the first author's master's thesis rather than the preprint.","tokens_in":18012,"tokens_out":3958,"would_cite":true,"duration_ms":43410,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","03D80","03D25","68Q32","68T09","68T27","68Q04","03D32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Computable PAC learning does not inherit the classical Fundamental Theorem: for any k ≤ ℓ, an algorithmically listable class can have VC-dimension k and effective VC-dimension ℓ.","keywords":["computable PAC learning","effective VC-dimension","VC-dimension","RER classes","nonuniform learning","structural risk minimization","unique identification property","agnostic learning"],"falsifier":"Run the construction for k = 1, ℓ = 2 and search for a computable 1-witness for H_{1,2}; finding one would refute the claimed eVCdim = 2. More directly, exhibit two finite hypothesis classes G and H with disjoint supports for which VCdim(G ⊕ H) ≠ VCdim(G) + VCdim(H); that single counterexample refutes Lemma 3.1 and with it the proof of Theorem 3.2.","tokens_in":17089,"feed_emoji":"🧮","tokens_out":7674,"duration_ms":76241,"temperature":0.7,"pith_summary":"The paper maps exactly how the Fundamental Theorem of Statistical Learning breaks when learners must be computable. Its central result is a construction: for every pair 1 ≤ k ≤ ℓ ≤ ∞, there is a hypothesis class that can be algorithmically listed (an RER class) whose ordinary VC-dimension is k and whose effective, computable VC-dimension is ℓ. Thus the effective dimension is not just sometimes larger; it can be tuned to any value above the classical one, even under listability and finite-support assumptions. On the other side, the paper proves that every RER class is properly learnable in the relaxed agnostic sense of nonuniform CPAC learning, with a computable structural risk minimizer, regardless of either dimension. The upshot is a precise division: listability alone does not restore the classical theorem, but computable empirical risk minimization and nonuniform learning do.","feed_headline":"Effective VC-dimension can exceed VC-dimension by any amount","feed_subtitle":"Even algorithmically listable classes realize every gap; yet all of them stay nonuniformly learnable.","key_machinery":"The load-bearing objects are: (i) the direct sum of hypothesis classes with disjoint supports, whose VC-dimension is claimed to add (Lemma 3.1); (ii) the RER class of all finitely supported hypotheses with a computable list representation, which supplies the ambient decidability; (iii) halting-based hypotheses h_e that place a 1 at a unique odd marker u_e and read off block labels from the halting output of machine T_e, making computable witnesses fail by diagonalization; and (iv) structural risk minimization with weight ω(n) = 2n² and error ε(m,b) = √(b/2m), whose computable minimizer yields the nonuniform learner.","core_discovery":"On its own terms, the paper's central claim is Theorem 3.2: for every 1 ≤ k ≤ ℓ ≤ ∞ there exists an RER class H_{k,ℓ} contained in the finitely supported hypotheses such that VCdim(H_{k,ℓ}) = k and eVCdim(H_{k,ℓ}) = ℓ. The construction splits the domain into a fixed k−1 point block and computably many disjoint blocks indexed by Turing machines; each block's labels are the output of a machine that halts, with a unique odd marker marking the block. Membership in the class is decidable from the list representation of the class of all finitely supported hypotheses, so the class is RER, and a diagonalization in step V shows no computable witness of size ℓ−1 can exist. The paper also proves Propos","pith_inferences":["The theorem's only unproved local input, Lemma 3.1, is doing real work: if additivity of VC-dimension under direct sums of disjointly supported classes fails, the claimed equality VCdim(H_{k,ℓ}) = k falls with it. A direct proof of the lemma would remove the paper's main caveat.","The construction suggests a design principle: whether a computable learning guarantee holds is governed more by the complexity of empirical-risk minimization than by the complexity of listing the class. This is an editorial inference, not a thesis stated by the paper.","The SRM proof yields an explicit polynomial sample-complexity bound in a, b, and the index n_h of the hypothesis; treating that quantitative bound as a formal theorem would give practitioners a concrete curve for nonuniform computable learning.","The paper leaves open whether any CPAC-learnable class contains an uncomputable hypothesis; a negative answer would imply that learnable classes are effectively listable in a strong sense and would sharpen the boundary between computable and uncomputable hypotheses."],"forward_implications":["The family H_{k,ℓ} yields a complete table of non-equivalences: when k < ℓ < ∞ the class is agnostically CPAC learnable but not properly agnostically strongly CPAC learnable; when ℓ = ∞ it is not agnostically CPAC learnable at all.","A total computable empirical risk minimizer forces the two dimensions to coincide, so restoring the classical characterization in the computable setting requires computable optimization, not merely computable listing.","Proper SCPAC learnability is equivalent to the existence of an RER subclass with the same realized samples, so every counterexample to the converse must be an extension of an RER class that adds hypotheses without adding new realizable samples.","For classes with the unique identification property, realizable CPAC learnability collapses to the RER property plus finite VC-dimension, giving a full analog of the Fundamental Theorem in that setting.","Every RER class, no matter its dimensions, is properly nonuniformly CPAC learnable; hence the agnostic barrier is not learnability itself but the demand for a single uniform sample-complexity bound."],"fun_headline_variants":["Effective VC-dimension can outpace VC-dimension by any amount","Even listable classes realize every gap between VCdim and eVCdim","Every VC-eVC gap is achievable, and all such classes stay learnable","eVCdim can be arbitrarily larger than VCdim, even for RER classes"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The arbitrary-gap theorem rests on Lemma 3.1, stated without proof and deferred to a companion thesis, that VC-dimension adds across disjointly supported direct sums—and, in the lower bound, on an acceptable Gödel numbering—so if either gives way the claimed gap collapses.","fun_headline_variants_meta":{"raw":{"variants":["Effective VC-dimension can outpace VC-dimension by any amount","Even listable classes realize every gap between VCdim and eVCdim","Every VC-eVC gap is achievable, and all such classes stay learnable","eVCdim can be arbitrarily larger than VCdim, even for RER classes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000317,"raw_usage":{"total_tokens":1655,"prompt_tokens":797,"completion_tokens":858,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":541,"completion_tokens_details":{"reasoning_tokens":777}},"tokens_in":541,"tokens_out":858,"duration_ms":9499,"temperature":1.0,"reasoning_tokens":777,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T00:05:32.305148+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the construction for k = 1, ℓ = 2 and search for a computable 1-witness for H_{1,2}; finding one would refute the claimed eVCdim = 2. More directly, exhibit two finite hypothesis classes G and H with disjoint supports for which VCdim(G ⊕ H) ≠ VCdim(G) + VCdim(H); that single counterexample refutes Lemma 3.1 and with it the proof of Theorem 3.2.","supporting_citations":[],"review_version":1}