REVIEW 2 major objections 5 minor 1 cited by
Effective Littlestone Dimension
T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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).
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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).
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 (2)
- [Section 6, proof of Theorem 12] 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 6, proof of Theorem 12, second case] 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.
minor comments (5)
- [Theorem 7(b)] 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 6, Theorem 12] 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.
- [Theorem 10] 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 6, WLOG reduction] 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.
- [Proposition 11] 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.
Circularity Check
No significant circularity: the effective Littlestone dimension results are derived from the definitions plus external classical and prior computational learning theorems; self-citations are used as independent black boxes, not as inputs that already contain the target conclusions.
full rationale
Effective Littlestone dimension is introduced by definition (the minimal d for which a total Turing machine can output an unrealizable leaf in every depth d+1 Littlestone tree), not by assuming the target theorems. Proposition 9 is a direct mistake-forcing argument. Proposition 11's reverse direction constructs a bounded-regime learner from the witnessing machine A by enumerating all depth d+1 trees over the initial segment, forming the finite class H_N, and applying the classical Littlestone learner (Proposition 3); this is constructive and not definitional. Theorem 7 reduces effective threshold dimension to effective Littlestone dimension by using A to eliminate every depth d+1 tree over the relevant labels, while the classical threshold/Littlestone bounds from [7,2] do the combinatorial work. Theorem 12 proves computability by induction: the base case is self-contained, and the intended split into two smaller subclasses is handled by the induction hypothesis. The second case invokes the consistent-oracle result [8] by two of the current authors. That citation is load-bearing, but it is an external theorem about all classes of Littlestone dimension d with an arbitrary consistent oracle, and it does not state or contain the conclusion that all functions in H are computable. The present proof extracts computability only by hardwiring finitely many oracle answers, so the target theorem is not assumed. The only concern is a typo in the induction split in Theorem 12 ("or" appears where "and" is needed for the induction to go through), but that is a correctness issue, not a circularity. No step reduces to its own input by construction or by self-citation.
Assumptions & free parameters
assumptions (5)
- standard math Cantor space {0,1}^N is compact and cylinders are clopen.
- domain assumption Littlestone's theorem: Ldim(H) equals the optimal number of mistakes for online learning of H (Proposition 3).
- domain assumption Shelah/Hodges/Alon et al.: Littlestone dimension and threshold dimension are within a logarithm of each other (Theorem 6).
- domain assumption The consistent-oracle online learning algorithm of Kozachinskiy and Steifer [8] has mistake bound O(256^d) for any class of Littlestone dimension d using only a consistent oracle.
- domain assumption Standard conventions of computability theory: learners are partial functions computed by Turing machines, hypothesis classes are subsets of {0,1}^N, and trees and samples have effective encodings.
Cite this review
Pith. "Pith review of Effective Littlestone Dimension." pith.science (2026). https://pith.science/paper/BC5X5GBF
@misc{pith2026241115109,
author = {Pith},
title = {Pith review of: Effective Littlestone Dimension},
year = {2026},
howpublished = {\url{https://pith.science/paper/BC5X5GBF}},
note = {Machine review of arXiv:2411.15109}
}
read the original abstract
Delle Rose et al.~(COLT'23) introduced an effective version of the Vapnik-Chervonenkis dimension, and showed that it characterizes improper PAC learning with total computable learners. In this paper, we introduce and study a similar effectivization of the notion of Littlestone dimension. Finite effective Littlestone dimension is a necessary condition for computable online learning but is not a sufficient one -- which we already establish for classes of the effective Littlestone dimension 2. However, the effective Littlestone dimension equals the optimal mistake bound for computable learners in two special cases: a) for classes of Littlestone dimension 1 and b) when the learner receives as additional information an upper bound on the numbers to be guessed. Interestingly, finite effective Littlestone dimension also guarantees that the class consists only of computable functions.
Forward citations
Cited by 1 Pith paper
-
On the Computability of Multiclass PAC Learning
Computable multiclass PAC learnability for finite label spaces is characterized exactly by the finiteness of computable distinguisher dimensions, including a new computable Natarajan dimension.
Reference graph
Works this paper leans on
-
[8]
Simple online learning with consistent oracle
Kozachinskiy, A., and Steifer, T. Simple online learning with consistent oracle. In The Thirty Seventh Annual Conference on Learning Theory (2024), PMLR, pp. 3241–3256
work page 2024
-
[1]
On learnability wih computable learners
Agarwal, S., Ananthakrishnan, N., Ben-David, S., Lechner, T., and Urner, R. On learnability wih computable learners. In Algorithmic Learning Theory (2020), PMLR, pp. 48– 60
work page 2020
-
[2]
Private and online learn- ability are equivalent
Alon, N., Bun, M., Livni, R., Malliaris, M., and Moran, S. Private and online learn- ability are equivalent. J. ACM 69 , 4 (2022)
work page 2022
-
[3]
Assos, A., Attias, I., Dagan, Y., Daskalakis, C., and Fishel son, M. K. Online learning and solving infinite games with an erm oracle. In The Thirty Sixth Annual Conference on Learning Theory (2023), PMLR, pp. 274–324
work page 2023
-
[4]
Find a witness or shatter: the landscape of computable pac learning
Delle Rose, V., Kozachinskiy, A., Rojas, C., and Steifer, T. Find a witness or shatter: the landscape of computable pac learning. In The Thirty Sixth Annual Conference on Learning Theory (2023), PMLR, pp. 511–524
work page 2023
-
[5]
On the computability of robust pac learning
Gourdeau, P., Tosca, L., and Urner, R. On the computability of robust pac learning. In The Thirty Seventh Annual Conference on Learning Theory (2024), PMLR, pp. 2092–2121
work page 2024
-
[6]
Hasrati, N., and Ben-David, S. On computable online learning. In International Conference on Algorithmic Learning Theory (2023), PMLR, pp. 707–725
work page 2023
-
[7]
Hodges, W. A shorter model theory . Cambridge university press, 1997
work page 1997
Show all 11 references
-
[9]
Learning quickly when irrelevant attributes abound: A new linear-th reshold algorithm
Littlestone, N. Learning quickly when irrelevant attributes abound: A new linear-th reshold algorithm. Machine learning 2 (1988), 285–318
1988
-
[10]
Classification theory and the number of nonisomorphic models
Shelah, S. Classification theory and the number of nonisomorphic models. Journal of Symbolic Logic 47, 3 (1982), 694–696
1982
-
[11]
Sterkenburg, T. F. On characterizations of learnability with computable learners. In Con- ference on Learning Theory (2022), PMLR, pp. 3365–3379. 12
2022
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.