{"id":"db0b3e42-c369-4003-9496-41bc9cef49b7","arxiv_id":"2411.15109","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Effective Littlestone dimension is necessary but not sufficient for computable online learning, yet it exactly characterizes learnability with an upper bound and implies the class contains only computable functions.","lead":"This paper defines an effective version of the Littlestone dimension, a combinatorial measure of how hard a concept class is to learn online. It shows this effective dimension captures computable online learning only when the learner gets an upper bound on the numbers it will see, and that finite effective dimension still forces every function in the class to be computable.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 12's second case rests on the imported consistent-oracle bound of [8] and on a never-f oracle; both appear sound, but a targeted check of [8]'s exact hypotheses would close the gap.","rationale":"We read the paper as establishing that effective Littlestone dimension is the right complexity measure for computable online learning in the bounded regime (Proposition 11) and that finiteness forces computability of the class (Theorem 12). The reductions in Proposition 11 and the negative construction in Theorem 10 appear sound. The induction in Theorem 12 is the delicate part. Lemma 13 is correct: the two candidate machines A0 and A1 cannot both fail. The closure to an effectively closed class is standard. The first case of the induction contains a typo ('or' should be 'and'); the second case is the real substance. Its only external input is [8]. Under the stated properties of [8]'s algorithm, the use of a never-f oracle is legitimate: for every H-realizable sample a consistent function in H\\{f} exists, and all such functions are computable by induction; hardwiring finitely many programs is a valid non-constructive computability argument. Thus no fatal flaw was found. The verdict remains conditional pending a check of [8]'s hypotheses and correction of the typos.","tokens_in":20,"tokens_out":33992,"duration_ms":457226,"concrete_test":"Open Kozachinskiy and Steifer (COLT 2024), restate the theorem in the exact form used here, and check two things: (1) the algorithm's mistake bound is proved for any oracle O(S,x) that returns a value consistent with some g in H on S, with no computability or global-consistency requirement; (2) for a fixed input sample S, the algorithm queries O only on subsamples of S. If both checks pass, the never-f oracle and finite-hardwiring argument in Theorem 12 are valid. An independent formalization of the second case in a proof checker, with [8] as an axiom, would also settle the step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of Theorem 12 — finite effective Littlestone dimension implies all functions in H are computable — is the load-bearing result. Its second case proves that the distinguished function f is computable by invoking the Kozachinskiy–Steifer theorem [8]: any class of Littlestone dimension d is online learnable with O(256^d) mistakes given a consistent oracle, and by Lemma 1 some sample S makes the learner's hypothesis equal to f. The proof then hardwires the finitely many oracle answers. Three conditions must hold: (i) [8]'s bound is valid for an arbitrary sample-consistent oracle, not necessarily computable; (ii) there is a consistent oracle for H that never returns f; and (iii) for a fixed S, only finitely many samples are queried. The paper argues (ii) correctly, since in the relevant case every H-realizable sample has a consistent function in H\\{f}, and those functions are computable by induction; (iii) is asserted for [8]'s algorithm (queries only S and subsamples). The unproved, imported condition is (i). If [8] actually requires a computable oracle, or an oracle consistent with a single master hypothesis, the hardwiring step collapses and f need not be computable. Separately, the written case split in Theorem 12 says 'eLdim(H_x^0) < d or eLdim(H_x^1) < d' and then concludes both subclasses are computable; the 'or' must be 'and' for the induction to be valid. This looks like a typo, not a substantive gap, but it should be fixed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper defines an effective version of Littlestone dimension (eLdim) for hypothesis classes of binary functions on N, in analogy with the effective VC dimension of Delle Rose et al. It shows that finite eLdim is necessary for total computable online learning (Prop. 9), that it is not sufficient by constructing a class of eLdim 2 with no partial computable online learner (Thm. 10), and that in the bounded regime, where the learner receives an upper bound on the numbers seen, eLdim exactly characterizes total computable learnability with d mistakes (Prop. 11). The central theorem (Thm. 12) states that finite eLdim implies every function in the class is computable, giving as a corollary that eLdim 1 classes have total computable 1-mistake learners. The paper also proves an effective version of the equivalence between Littlestone and threshold dimension (Thm. 7 and Cor. 8).","tokens_in":12909,"tokens_out":24730,"duration_ms":235794,"significance":"If the results are correct, eLdim is a natural effective analogue of Littlestone dimension. The bounded-regime characterization (Prop. 11) is a clean and useful equivalence, and Theorem 12 is a strong structural consequence: finite effective dimension forces full computability of the class. The proof techniques are interesting and mostly well executed: the compactness-based enumeration (Prop. 5), the diagonal construction in Thm. 10, the branching argument in Lemma 13, and the finite-domain reduction in Prop. 11 are all coherent. The main caveats are two proof typos and the imported consistent-oracle theorem, which should be stated explicitly; none of these appears to undermine the central claims.","major_comments":[{"comment":"The case split in the induction step is misstated. The text says: \"Assume first that for some x, we have eLdim(H_x^0)<d or eLdim(H_x^1)<d. Then by the induction hypothesis, both H_x^0 and H_x^1 consist of computable functions.\" A disjunction does not imply both subclasses have effective dimension smaller than d; the first case must be \"for some x, both eLdim(H_x^0)<d and eLdim(H_x^1)<d\", which is precisely the negation of the second case. As written, the induction step is not sound, although the intended fix is a single word.","section":"Section 6, proof of Theorem 12"},{"comment":"The proof that f is computable relies on the theorem of Kozachinskiy and Steifer [8] that any class of Littlestone dimension d is online learnable with O(256^d) mistakes given a consistent oracle. Since this is a load-bearing black box, please state the theorem with its exact hypotheses: in particular, whether the bound holds for an arbitrary sample-consistent oracle (not necessarily computable), and make explicit that in the computation of L(S,x) only finitely many oracle queries are made, so that hardwiring programs for the computable oracle answers yields a computable function. If [8] requires a computable oracle, an additional argument is needed.","section":"Section 6, proof of Theorem 12, second case"}],"minor_comments":[{"comment":"Theorem 7(b) is misstated: it says \"has effective threshold dimension at most dt\" but should say \"effective Littlestone dimension at most dt\"; the proof also refers to \"the threshold dimension of H\" where it means the threshold dimension of the constructed \\hat H.","section":"Theorem 7(b)"},{"comment":"In the second case of Theorem 12, \"a consistent oracle H\" should be \"a consistent oracle O\" and \"apart from H\" should be \"apart from f\", to avoid confusion with the class H.","section":"Section 6, Theorem 12"},{"comment":"The construction shows eLdim(H) <= 2 and that no partial computable learner exists; the proof should explicitly note why eLdim(H) > 1, since otherwise the class would admit a total computable 1-mistake learner by Corollary 14.","section":"Theorem 10"},{"comment":"In the WLOG reduction to effectively closed classes in Theorem 12, if the enlarged class \\hat H has effective dimension smaller than d, the induction hypothesis applies immediately; the proof should mention this case before proceeding.","section":"Section 6, WLOG reduction"},{"comment":"In the proof of Proposition 11, after H_N is defined, the sentence \"The set H_N includes all functions that can be continued to a function in H\" should be phrased as \"includes all restrictions to {1,...,N} of functions in H\" for clarity.","section":"Proposition 11"}],"recommendation":"minor_revision","confidential_remarks":"I am sympathetic to the paper and believe the results are correct after minor fixes. The only nontrivial concern is the use of [8]'s consistent-oracle theorem; if the authors state its exact hypotheses, the proof of Theorem 12 will be complete. The typo in the Theorem 12 case split must be corrected. I see no grounds for rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick read: this is a solid paper, and the central results are real. The authors define effective Littlestone dimension, prove an equivalence with effective threshold dimension up to logs, give a dimension-2 counterexample showing the converse of Proposition 9 fails, and nail the bounded regime: effective Littlestone dimension at most d iff there is a total computable learner with an upper bound making at most d mistakes. The headline is Theorem 12: finite effective Littlestone dimension forces every function in the class to be computable. I spent most of my time on that proof, and it holds up.\n\nWhat's new: the definitions are natural, and the bounded-regime equivalence is a clean characterization. Theorem 10's priority construction is intricate but believable, and the proofs are mostly detailed enough to check.\n\nSoft spots: there are typos in the write-up. In Theorem 12, the first case says 'eLdim(H_x^0) < d or eLdim(H_x^1) < d' and then concludes both subclasses are computable; that must be 'and'. The stress-test note flags this, and it's indeed a typo, not a gap—the subsequent 'assume now' case handles the rest. Theorem 7(b) similarly says 'effective threshold dimension at most dt' where it should say 'effective Littlestone dimension at most dt.' Also, in the second case of Theorem 12, 'apart from H' should be 'apart from f.' These should be fixed, but they don't affect the mathematics.\n\nThe load-bearing dependency on [8] (the consistent-oracle bound) is fine: [8]'s theorem is about arbitrary consistent oracles, not necessarily computable ones, so the hardwiring argument goes through. The 'never-f' oracle exists because of the case assumption. Still, a referee should double-check [8]'s exact hypotheses to close the loop.\n\nWho is this for: people in algorithmic learning theory, especially the computability angle. It's a good paper, not a blockbuster, but it deserves a serious referee. My recommendation: accept with minor corrections.","headline":"A genuine and mostly correct contribution to computable online learning; the bounded-regime characterization and Theorem 12 are the highlights, with a few typos to fix and a citation to [8] to verify.","tokens_in":13399,"tokens_out":6231,"would_cite":true,"duration_ms":55823,"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":"A computable version of the Littlestone dimension characterizes online learning exactly when the learner receives an upper bound on the values it will see, and finite effective dimension forces every function in the class to be computable.","keywords":["effective Littlestone dimension","computable online learning","Littlestone dimension","online learning","computability theory","bounded regime","consistent oracle","threshold dimension"],"falsifier":"Construct a hypothesis class H whose effective Littlestone dimension is certified to be 2 and, for some bound N, a realizable sample using only numbers ≤ N on which every total computable learner with bound N makes at least 3 mistakes; Proposition 11 says this cannot happen. Running the paper's brute-force learner construction on a candidate class and checking its mistake bound on all realizable samples inside a given N would settle the matter.","tokens_in":12392,"feed_emoji":"🎯","tokens_out":15271,"duration_ms":119349,"temperature":0.7,"pith_summary":"The paper introduces the effective Littlestone dimension, a computability-theoretic variant of the classical equivalent-mistake-bound measure for online learning. It asks when the existence of a Turing-machine learner with a fixed mistake bound can be read off from a combinatorial dimension of the hypothesis class. The main positive result is a precise characterization in what the paper calls the bounded regime: a class has effective Littlestone dimension at most d exactly when a total computable learner, given an upper bound on the numbers it will see, online learns the class with at most d mistakes. Independently, the paper proves that any class of finite effective Littlestone dimension consists entirely of computable functions, so the dimension is also a computability constraint on the class itself.","feed_headline":"One number measures computable online learning—if inputs are bounded","feed_subtitle":"With a bound on the numbers it will see, effective Littlestone dimension gives the exact mistake count.","key_machinery":"The central object is the effective Littlestone dimension: the minimal depth d for which a total Turing machine exists that, on any depth-(d+1) Littlestone tree, returns a branch not realizable by the hypothesis class. This is a direct effectivization of ordinary Littlestone dimension, replacing existential non-realizability with an explicit witness-producing procedure. The other key mechanism is the 'bounded regime' learner, which receives an upper bound N on the input values before play begins. Proposition 11 proves the equivalence by translating between this learner and the effective-dimension witness: a learner with bound N certifies non-realizable leaves by playing against any tree, and an effective-dimension machine lets the learner reduce the class on {1,...,N} to a finite class of small Littlestone dimension, which a brute-force search then learns. The proof of Theorem 12 additionally imports a consistent-oracle online learning algorithm from [8] to show that the one possibly non-computable function in the class is actually computable.","core_discovery":"Effective Littlestone dimension is the least d for which a total Turing machine can, given any Littlestone tree of depth d+1, output a branch that no function in the class realizes. The paper's central discovery is that this dimension is the exact optimal mistake bound for computable online learning in the bounded regime, where the learner is handed an upper bound N on all numbers that will appear: such a learner with d mistakes exists if and only if the effective Littlestone dimension is at most d (Proposition 11). It also shows that outside this regime the equivalence fails, constructing a class of effective Littlestone dimension 2 that no partial computable learner can learn with finitely many errors (Theorem 10). Finally, finite effective Littlestone dimension forces every function in the class to be computable (Theorem 12), which yields a total computable learner with one mistake for every class of effective Littlestone dimension 1 (Corollary 14).","pith_inferences":["The bounded-regime result suggests a general recipe for other learning settings: if a complexity measure admits an 'effective witness' — a total machine that finds a counterexample from the combinatorial object — then that measure will characterize computable learners that receive a domain-size bound; the paper's effective-threshold equivalence is one instance of this pattern.","Because finite effective Littlestone dimension forces all functions in the class to be computable, the failure at dimension 2 means the obstruction is structural, not due to non-computable concepts; investigating whether such classes must have non-decidable index sets or non-computable enumerations of their elements would sharpen what 'effectively small' means.","The paper explicitly leaves open the time-bounded version; an immediate test is whether the same equivalence holds when 'computable' is replaced by 'polynomial-time computable' for finite classes, where the brute-force learner construction asks for an explicit bound on the search time."],"forward_implications":["In the bounded regime, effective Littlestone dimension is an exact computable analogue of the classical characterization: it equals the minimum number of mistakes a total computable online learner can guarantee when given an upper bound on the inputs.","In the unbounded regime the picture is strictly worse: there exists a class with effective Littlestone dimension 2 that admits no partial computable online learner with a finite mistake bound, so the effective dimension alone does not characterize computable online learning.","Every hypothesis class with finite effective Littlestone dimension consists entirely of computable functions, which means the dimension is a strong syntactic restriction on the class and not merely a measure of learnability.","Classes of effective Littlestone dimension 1 are tractable: they always admit a total computable online learner making at most one mistake.","Effective threshold dimension and effective Littlestone dimension are equivalent up to the same logarithmic factors as their classical counterparts, so the effective dimension can be witnessed through threshold-based certificates."],"supporting_citations":[{"why":"Supplies the consistent-oracle online learning algorithm with O(256^d) mistakes used in Theorem 12 to prove the last hard function is computable.","marker":"[8]"},{"why":"Establishes the classical theorem that Littlestone dimension equals the optimal mistake bound, which the paper effectivizes and invokes in Corollary 14.","marker":"[9]"},{"why":"Introduces effective VC dimension and its characterization of computable PAC learning, the template on which the paper's effective Littlestone dimension is built.","marker":"[4]"},{"why":"Provides the quantitative threshold-to-Littlestone bound used in Theorem 7(b) to transfer effective threshold dimension to effective Littlestone dimension.","marker":"[7]"},{"why":"Provides the quantitative Littlestone-to-threshold bound used in Theorem 7(a) to transfer effective Littlestone dimension to effective threshold dimension.","marker":"[2]"},{"why":"Shows the classical finiteness equivalence between threshold and Littlestone dimension that the effective dimension extends.","marker":"[10]"}],"fun_headline_variants":["Exact mistake bound for computable learners if numbers are bounded","Effective Littlestone dimension gives exact mistakes when inputs are capped","Computable learning's exact error count: know the upper bound","Effective dimension: bounded inputs yield exact mistake bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that every function in the class is computable leans on an imported result about learning from a consistent oracle; if that result or the choice of an oracle that never names a specific function fails, the conclusion no longer follows.","fun_headline_variants_meta":{"raw":{"variants":["Exact mistake bound for computable learners if numbers are bounded","Effective Littlestone dimension gives exact mistakes when inputs are capped","Computable learning's exact error count: know the upper bound","Effective dimension: bounded inputs yield exact mistake bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000825,"raw_usage":{"total_tokens":3572,"prompt_tokens":875,"completion_tokens":2697,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":491,"completion_tokens_details":{"reasoning_tokens":2629}},"tokens_in":491,"tokens_out":2697,"duration_ms":20088,"temperature":1.0,"reasoning_tokens":2629,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:29:55.257951+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a hypothesis class H whose effective Littlestone dimension is certified to be 2 and, for some bound N, a realizable sample using only numbers ≤ N on which every total computable learner with bound N makes at least 3 mistakes; Proposition 11 says this cannot happen. Running the paper's brute-force learner construction on a candidate class and checking its mistake bound on all realizable samples inside a given N would settle the matter.","supporting_citations":[{"cited_title":"Simple online learning with consistent oracle","cited_arxiv_id":null,"evidence_quote":"Supplies the consistent-oracle online learning algorithm with O(256^d) mistakes used in Theorem 12 to prove the last hard function is computable."},{"cited_title":"Learning quickly when irrelevant attributes abound: A new linear-th reshold algorithm","cited_arxiv_id":null,"evidence_quote":"Establishes the classical theorem that Littlestone dimension equals the optimal mistake bound, which the paper effectivizes and invokes in Corollary 14."},{"cited_title":"Find a witness or shatter: the landscape of computable pac learning","cited_arxiv_id":null,"evidence_quote":"Introduces effective VC dimension and its characterization of computable PAC learning, the template on which the paper's effective Littlestone dimension is built."},{"cited_title":"A shorter model theory","cited_arxiv_id":null,"evidence_quote":"Provides the quantitative threshold-to-Littlestone bound used in Theorem 7(b) to transfer effective threshold dimension to effective Littlestone dimension."},{"cited_title":"Private and online learn- ability are equivalent","cited_arxiv_id":null,"evidence_quote":"Provides the quantitative Littlestone-to-threshold bound used in Theorem 7(a) to transfer effective Littlestone dimension to effective threshold dimension."},{"cited_title":"Classification theory and the number of nonisomorphic models","cited_arxiv_id":null,"evidence_quote":"Shows the classical finiteness equivalence between threshold and Littlestone dimension that the effective dimension extends."}],"review_version":1}