Computable universal online learning
Authors: Dariusz Kalociński
Tomasz Steifer
Venue: NeurIPS 2025 poster ()
Keywords: universal learning
computable learners
online learning
computational learning theory
agnostic learning
Primary area: theory
TL;DR: When can learning be implemented as a computer program? We answer this question for the theoretical model of universal online learning.

Abstract: Understanding when learning is possible is a fundamental task in the theory of machine learning. However, many characterizations known from the literature deal with abstract learning as a mathematical object and ignore the crucial question: when can learning be implemented as a computer program? We address this question for universal online learning, a generalist theoretical model of online binary classification, recently characterized by Bousquet et al. (STOC 2021). In this model, there is no hypothesis fixed in advance; instead, Adversary—playing the role of Nature—can change their mind as long as local consistency with the given class of hypotheses is maintained. We require Learner to achieve a finite number of mistakes while using a strategy that can be implemented as a computer program. We show that universal online learning does not imply computable universal online learning, even if the class of hypotheses is relatively easy from a computability-theoretic perspective. We then study the agnostic variant of computable universal online learning and provide an exact characterization of classes that are learnable in this sense. We also consider a variant of proper universal online learning and show exactly when it is possible. Together, our results give a more realistic perspective on the existing theory of online binary classification and the related problem of inductive inference.

Computable universal online learning
Dariusz Kalociáski Institute of Computer Science Polish Academy of Sciences
Tomasz Steifer
Institute of Fundamental Technological Research Polish Academy of Sciences tsteiferrippt. pan pan.pl
kallocinski@ipipan wttppppaan.ww..p........m. waw.pl
Abstract
Understanding when learning is possible is fundamental task in the theory of machine learning. However, many characterizations known from the literature deal with abstract learning as mathematical object and ignore the crucial question: when can learning be implemented as a computer program? We address this question for universal online learning, a generalist theoretical model of online binary classification, recently characterized by Bousquet et al. (STOC'2I1 21). In this model, there is no hypothesis fixed in advance; instead, Adversary-playinn the role of Nature-can change their mind as long as local consistency with the given class hypotheses is maintained. We require Learner achieve a finite number of mistakes while using strategy that can be implemented as a computer program. We show that universal online learning does not imply computable universal online learning, even if the class of hypotheses is relatively easy from computability- theoretic perspective. We then study the agnostic variant of computable universal online learning and provide an exact characterization of classes that are learnable in this sense. We also consider a variant proper universal online learning and show exactly when it is possible. Together, our results give more realistic perspective on the existing theory of online binary classification and the related problem of inductive inference.
Introduction
The quest to understand the fundamental limits of machine learning has led to the development of powerful theoretical frameworks, such PAC learning or multi-armed bandits. These frameworks provide a high-level abstraction machine learning, capable of capturing broad class of learning problems within single unified theoretical model. A good theoretical model should least be able to say when learning is possible and when it is not. Take, for example. the online version of binary classification. The seminal papers by Littlestone (1988) and Angluin (1988) studied the question of when Learner has a strategy that guarantees a uniform bound on mistakes. Littlestone (1988) famously gave a combinatorial characterization now known the Littlestone dimenston-oo hypothesis classes that are learnable with uniform mistake bound. Under such a restriction, one can equivalently assume that Adversary fixes one true function in advance. Recently, (Bousque et al.) (2021) extended this work to a more general adversarial setting, where Learner makes finitely many mistakes (but possibly not uniformly bounded) and where Adversary can adapt dynamically. This setting is in line with real-world scenarios where uniform bounds are not always available. We call it universal online learning
The notion of the Littlestone dimension was generalized to ordinal numbers by Bousquet et al. (0021) who used give a characterization of universal online lcarnability: a class is universally online
Please note that Bousquet (021) deseribe two related settings: one probabilistic (universal learning) one adversarial (universal online learning). This paper uniquely concerned with the latter (see Bousquet
et al.
2020 Section 3).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

learnable if and only if it has an ordinal Littlestone dimension. More recently, the framework of universal online learning was extended multiclass classification with bandit feedback (Hanneke et al. 2025).
Although the work of [Bousquet et al. (2021) provides deep theoretical insights, it leaves open critical question: when can such learning be implemented by an actual computer program? Having an appropriate Littlestone dimension is sufficient to guarantee the existence of learner understood as an abstract object-a mathematical function. However, such a function may be computationally hard or even uncomputable, meaning that cannot be implemented on a computer.
In this work, we bridge this gap by introducing computability constraints into the universal online learning framework, asking when a class of hypotheses admits computable learning scheme that guarantees a finite number of mistakes.
Recently, different authors have begun to study combinatorial characterizations from the point of view of computability theory, introducing computable analogs of PAC learning (Agarwal et al.) 2020; Sterkenburg. 2022; Delle Rose et al. 22023), robust PAC learning (Gourdeau et al. (022), and uniform online learning (Hasrati and David 2023). In all cases, special attention was given to the so-called recursively enumerably representable (RER) classes-classes specified by program that enumerates all the functions in the class. In particular, RER classes of finite Littlestone dimension always learnable by computable learner with uniform mistake bound (Assos et al. 2023 Kozachinskiy and Steifer 2024).
The standard notion of computability makes sense for countable domains such as the set of all natural numbers. For this reason, in this paper we limit our attention to universal online learning of hypotheses defined on N. While this restriction may appear limiting, it is motivated by practical considerations. Indeed, all practical machine learning takes place on computers, which inherently operate over countable domains such as images or binary strings. From the point of view of computability, learnability on the natural numbers sufficiently general to model any domain relevant to practical applications
2
Main results
We begin with a brief outline of the main results of the paper. This is followed by a detailed presentation of the framework, accompanied by examples and discussion of the key concepts involved. The formal statements of all new theorems appear in Sections 2. 2.3
The first important observation (Section 2.1 Theorem ! states that there exist RER classes that are universally online learnable but cannot be learned by any computable learner. This stands in sharp contrast to the case of R.R classes with finite Littlestone dimension, as discussed in the introduction.
we investigate the agnostic variant of computable universal online learning. In agnostic learning, Adversary is no longer restricted to choose hypotheses that are consistent with the class. When the class is universally online learnable, one can guarantee a sublinear expected regret for agnostic learning (Littlestone and Warmuth| 1994] Cesa-Bianchi et al. 1997 Hutter et al. 2005 Blanchard al. 2022 Hanneke al.] 2025). We show that this no longer holds when computability is required. In Theorem 3 we give an example of a class that is computably universally online learnable in the realizable case, but for which there cannot be a computable universal agnostic learner. On the positive side, Theorem gives an exact characterization of classes that are agnostically online learnable by a computable learner. Furthermore, in Theorem 4 we show that the standard equivalence between realizable and agnostic learning holds if we restrict our attention to RF R classes.
In Section 2.2
2
we study notion of proper learning adapted for universal online learning- Here, we say that a learner is proper if it outputs a realizable function while playing against realizable Adversary. Again, in Theorem 5 we give a precise characterization of proper learning in the computable regime. We also show that proper learning is harder than non-proper learning. In particular, Theorem 0 gives an example of a class for which computable universal online learners
Finally, in Section 2.3
DDespite our efforts to make the paper accessible to the machine learning community, the reader may occasionally wish to consult an introductory textbook on computability theory (Cutland) 1980). or more advanced work (Odifreddi 1989).

---

exist, but none of them can be proper in this sense. In fact, such examples can be found even among RER classes.
2.1 Setting
Our model is given by the following game, played between Learner and Adversary. The game starts with a predefined hypothesis class H. which is a set of (total) functions from some domain X to {0, 13. As announced in the introduction, X = N. The game continues for infinitely many rounds. In each round, Adversary first gives Learner an element æ E X. Learner then makes prediction y E {0, } for the label of æ. After the prediction, Adversary reveals the "true" label E (0, 1) of x. If y A D. we say that Learner has made mistake.
Learner's 's goal is to make as few mistakes as possible. Otherwise, their moves are unrestricted in any other way. However, Adversary is expected to maintain consistency in their answers with H. That means that at each step, the labels revealed so far must agree with some function E H. Adversary is malicious in very strong sense they can change their mind; that is, they can change h H according to which their labels are given. An Adversary who maintains consistency with the class H is called realizable.
We use the term learner (without capitalization) to refer to a strategy according to which Learner could play. Formally, a learner is partial function that maps elements of (N x 0, 1)<w x N to {0, 1}; namely, a function that, given a sample and number æ, predicts a binary label for æ. A sequence (It, Yt He,, where N E NU {oo}, I4 E N, and y, {0. 1}, is realizable by H. (or H-realizable) if, for every T < _N, there exists h E H. such that (Zt, yt o is consistent with h, i.c., h(x;)) = y1 for t T.
Definition (universal online learning). We say that a class H. is universally online learnable if there is a learner L. such that for every H-realizable sequence (It, yt) 30)00- there exists m such that for every n > m we have L(S, In+1)= = Vn+1, where S= (It, Yt yt this strategy can be implemented as computer program, we say that H is computably universally online learnable.
Equivalently, H is universally online learnable if there is a learner L such that for every H-realizable sequence R. there exists M E N such that L makes at most M mistakes on R. In contrast, a class H is universally online learnable with a uniform mistake bound there is a learner and a mistake bound M N such that for every H-realizable sequence, L makes at most M mistakes that sequence. Clearly, every class that is universally online learnable with a uniform mistake bound is also universally online learnable. The reverse does not hold (see Bousquet et al. 2020 Section 3.4).
In the uniform case, does not matter whether Adversary allowed to change the target function. the Littlestone dimension is finite, uniform mistake bound can be achieved even against adaptive Adversary. Conversely, if the Littlestone dimension infinite, Adversary need not be adaptive to force mistakes arbitrary sequences. For this reason, many authors prefer to assume that the target function is fixed in advance (see, e.g., Shalev-Shwartz and Ben-David 2014). Indeed, this is also how the setting was originally defined Litlestone (1988). The flexibility of Adversary becomes relevant only once the requirement of uniformity is dropped.
Example 1. Consider the class of all singletons, that is, the class of hypotheses on N that have exactly one nonzero label. Even though this class does not contain a function with all zeros, Adversary is allowed play as if this were their "true" hypothesis. This is because every finite set of numbers all labeled with zeros is consistent with one of the functions in the class. This class is uniformly online learnable with a uniform mistake bound.
Example 2. Consider the class containing all the functions that have a finite number of nonzero labels. If Adversary cannot change their mind, this class is online learnable but with non-uniform mistake bound. There are only countably many hypotheses, and we can check each one by one. However, in our setting, Adversary can effectively play whatever sequence of labels they want and still maintain consistency with the class. Therefore, this class is not universally online learnable.
Example 3. Imagine that the role of Adversary is played by a large language model (LLM). The generated sequence of tokens is not chosen in advance but produced online, and it is always consistent with the set of all possible outputs of this LLM. We can think about different random choices produced by the model as moves of Adversary. At a high level of abstraction, the theory of universal learning tells us when it possible to predict (the binary representation of) this sequence of tokens with only finite number of mistakes.
3

---

We will assume that our classes of hypotheses contain only total computable functions on the natural numbers, i.e. functions that can be implemented by a computer program which halts on every input. This is justified since computable universal online learning is only possible when all the hypotheses in the class are total computable (cf. Lemma 4 The classes of Examples
T all contain only
computable functions and all are RER, that is, there is a program that enumerates list of programs computing all and only the functions from the class (see Definition 5). Some RER classes are also decidably representable (DR), which means that they can be presented as decidable set of programs. Not every RE class is DR. The following classes are all DR and computably universally online learnable (but not with uniform mistake bound); all functions with finite support, thresholds on N, and thresholds on Z (see Examples 3.8-3.10 3. in Bousquet et al. 2020
The above examples motivate the notion of the closure H of class H. The closure contains all functions that can be effectively used by Adversary who is realizable-that is, all the functions that are locally consistent with H. after a finite number of steps.
Definition 2. A function 9 belongs to H. if there exists a sequence of functions he, h1.-.. -from H and a sequence of natural numbers no nn <... ... such that, for every E N, h₂(2)) g(x) for all t < n2.
Effectively, a mind chindnchanging Adversary behaves as if they had selected a true hypothesis from H in advance and then never changed their mind this observation is straightforward to prove and is stated more precisely in Section 4.1
It was recently discovered that any RER class that is online learnable with uniform mistake bound is also learnable by a computable learner (Assos al., [023] Kozachinskiy and Steifer 2024).
However, this implication fails when the requirement of a uniform mistake bound is dropped.
Theorem 1.
There exists RER class that is universally online learnable but not computably universally online learnable. In fact, such a class can even be DR.
The proof of this result, given in Section 4.2, relies on the fact that even if H. contains only computable functions, its closure may contain functions that are uncomputable. Similarly, natural examples of universally online learnable but not computably universally online learnable classes can be extracted from the existing literature (see, e.g.. Cenzer and Remmell 1998). where sets of solutions to computably presented problem are represented as infinite paths in a computable tree. See Appendix D for details.
2.2 Agnostic learning
Our definition of computable universal online learning only asks that computable learner behave in a certain way on realizable samples. In particular, this means that such a learner can be undefined on non-realizable samples. Think about a program that halts on realizable inputs but might go into an infinite loop if fed different input. For instance, we can have a computable learner for the class of singletons from Example [] with an additional instruction saying: once you see two numbers labeled with 1, go into loop. This learner is still good in the realizable case, because Adversary will never show us a function with more than one nonzero label.
The situation changes once we try to move to the agnostic setting. We adopt a relatively weak requirement of sublinear regret, which is known to be equivalent to realizable universal online learning, even in the multiclass setting under bandit feedback (Hanneke et al., 2025). Such a property usually requires randomization. The notion of computable learning naturally generalizes to randomized computations, A randomized program is just program that has access to an additional source of random bits sampled with probability 1/2. We say that a randomized computable function f is almost total if it is total with probability one with respect to its internal randomness. To be precise, with probability once we fix the internal randomness, the computation halts on each input. We can now give the definition of universal agnostic online learnaillity. In the remainder of the paper, it is simply called agnostic learnability
Definition 3 (agnostic universal online learnability). Let T, a learner, and let H be class of hypotheses. We say that L agnostically universally online learns H. or that L is an agnostic universal

---

online learner for H. for every sequence (Iz, vi)
E
min
Σ h(xz)) # yt
E Octin
(L((z,, wizo x1) + yr)
KER
G<rin
grows sublinearly in with the expectation taken relative to the internal randonmess of the learner. Moreover, we say that H is computably agnostically universally online learnable if there exists universal agnostic online learner for H which is realized almost total randomized computable function.
Example 4. Consider class of all decision trees of depth 3. In realistic scenario, small decision trees cannot perfectly capture the complexity of the data. However, there are reasons for using small decision trees for classification, such as interpretability. Agnostic learning with small decision trees requires that, while we cannot perfectly classify the data, we can still do almost as well as the best decision tree.
In agnostic learning, Learner's strategy must be defined for all possible imputs, not only the realizable ones. In fact, the standard methods for transforming realizable learner into an agnostic one require evaluating the (old) learner on non-realizable samples. Indeed, a standard approach as follows: start with a method of prediction with expert advice (for countable set of experts), like Weighted Majority Algorithm with nonuniform weights (Littlestone and Warmuth, 1994), Follow the Perturbed Leader (Hutter et al. 2005) or some version of Hedge algorithm (Blanchard et al. 2022) and apply to the class of experts defined by simulating the realizable learner on different inputs 3 In turn,
having computable agnostic learner we can transform it into computable (non-randomized) realizable learner. The following theorem, proved Section 4.3 formalizes this idea and gives two characterizations of agnostic learnability in the computable regime.
Theorem 2. Let H be an arbitrary class of hypotheses. The following are equivalent:
1. H. is computably universally online learnable (in the realizable setting) by a total learner.
2. There exists a RER class 2 such that H. S Z.
3. is computably agnostically learnable.
Without computability constraints, universal online learning implies agnostic learning (Hanneke et al. 2025). The following theorem shows that this implication does not hold in the computable regime. The proof is given in Section 4.4 and Appendix C
Theorem 3. There exists a class H that computably universally online learnable but not computably agnostically learnable.
The class given in the proof of Theorem 3 is not RER. It is not possible computably enumerate all the hypotheses from this class. In Section 4.5 we prove that once we limit our attention to RER classes, computable universal online learning again equivalent agnostic learning:
Theorem 4. Let H be a RER class. The following are equivalent:
1. H. is computably universally online learnable.
2. There exists an RER class Z such that H. C 2.
3. H. is computably universally online learnable by a total learner.
2.3 Proper versus improper learning
In computational learning theory, proper learning usually refers to the setting in which a learning algorithm is restricted to output hypotheses that belong the class H. In the uniform mistake- bound regime, this is equivalent to requiring that the learner output only realizable functions. In our setting, however, these two notions no longer coincide. The latter is too strong, since Adversary may effectively use a function that does not belong to the class but rather to its closure. Indeed, the standard definition can be satisfied only in the very restrictive case H = H. Hence, we adopt the second interpretation, is the less trivial one.
et al. (2009 introduced this idea for the agnostic learning with respect Littlestone classes.
5

---

Definition 4 (proper learner). We say that a learner L is proper with respect to H. if. for every H-realizable sample S, L(S.-) (..5),s, H-realizable.
In the above definition, L(S,.) is total function L' NN- {0,1} of the single variable indicated by- :, defined as follows: T (x) = x)) for all x E N.
When it is clear which class we referring to, we often simply say that learner is proper, instead of "proper with respect to t.... ". For example, in the formulation of the theorem below, "proper" means "proper with respect to H". The following characterization is proved is Section 4.6
Theorem 5. For every RER class H. H. is computably universally online learnable by proper learner if and only if H a RER class.
Trivially, if a class is computably universally online learnable by a proper learner, then it is com- putably universally online learnable. In Section 4.7. we show that the reverse implication does not hold, thereby establishing separation between proper computable universal online learning and computable universal online learning.
Theorem 6. There exists a RER class that is computably universally online learnable but has no computable proper learner.
Discussion
Theorems 2 and provide an exact characterization of agnostic and proper learning in the framework of universal online learning. Together with Theorem 4 this yields an exact characterization of realizable universal online learning for the family of RER classes, which arguably includes all hypothesis classes of practical relevance. It remains interesting open problem provide exact characterization of realizable computable universal online learning for arbitrary classes. related open question how to characterize computable online learning with uniform mistake bound. A recent attempt by Delle Rose et al. (2025) suggests that this question may be hard.
Theorem I together with the accompanying discussion, indicates that universally online learnable RER classes without computable learners do exist and can arise in naturally occurring problems. How complex can the learners for such classes be? This question admits precise craputability-theoree formulation, and its resolution will be presented in a separate manuscript (in preparation).
4 Proofs
For the sake of mathematical rigor, we state certain notions in more precise way. Programs in fixed programming language are finite objects and can be indexed by natural numbers. We use the notation 9n, to denote the function computed by the program with index n (n-th program, or program n). Such a function can be partial, that is, undefined on some inputs. We say that a set 2 C N is computably enumerable (c.e.) if there exists a program that enumerates all (and only) the elements of Z. If 20, 21.... is such an enumeration of Z generated by a program, we call it computable enumeration of Z. In particular, Z can be set of (indices of) programs.
Definition 5 (RER class). H. is RER if there exists c.e. set H (of the indices of programs) such that,for each total function from N to {0, 1}, f E H iff there exists e E H such that y =
Equivalently, H is RER if there exists c.e. H such that H (ye : H}.
4.1 Helpful lemmas
Before we dive into the proof of the main results, it will be helpful to state some technical lemmas. The proofs of these observations use standard techniques, and we relegate them all to Appendix A
In our setting, Adversary can ask Learner to label numbers in an arbitrary order, perhaps even omitting some the numbers completely. Adversary has to maintain consistency of each sample with some hypothesis in the class but we imagine that at each round there might be different target hypothesis. Lemmas T [nd 2 tell us that equivalently we can assume that Adversary just chooses advance single target function from the closure of the class.

---

Lemma 1. Let h E H. and let (x1) be any sequence of non-negative integers. Then the sequence ((,,)( H-rralizable.
Lemma 2 (Closure Lemma). Every H--relizablee sequence (Zi, Vo) is consistent with some element H. In particular, an H-realizable sequence (I Ve Ve) is such that the enumeration To, #1,... mentions all natural numbers, then the function z; + Yi is an element H.
The next lemma states that if H. is learnable even in a very weak sense, then there exists a sample on which the learner "outputs" given hypothesis from H. This lemma describes a phenomenon similar to locking sequences from the inductive inference theory, first considered by Blum and Blum (1975).
Lemma (Projection Lemma). Fix a class of hypotheses H and a learner L. Suppose that for each H-realizablle play of Adversary, I predicts infinitely many labels correctly, i.e,, for each h E H and X = ((11, h((ra), (122, h(x2).....) there are infinitely many k such that ((S,T443) = h((x+1)) where S is the prefix of X of length k. Then there exists a sample S' such that S' is consistent with and L(S', h; moreover, such a sample S' is always H-realizable.
The above lemma implies the following:
Lemma 4. Let H. be computably universally online learnable. Then each member H.
H. is computable.
4.2 Proof of Theorem
Theorem 1.
There exists RER class that is universally online learnable but not computably universally online learnable. In fact, such a class can even be DR.
Proof. A tree is of strings T' such that, if T, then each prefix of is also a member of A tree is computable if there is a program that, for given a, decides whether belongs to the tree, An infinite path in T is infinite string such that each its prefixes of infinite paths in T by [T]. It is folklore result that there exist computable binary trees with at most countably many infinite paths, at least one of which uncomputable (see, e.g.. Cenzer et al. 1986). Fix such tree T. Let H fa00 and that H. is countable. Given enumeration he,.... of H. an uncomputable learner for 7. can be defined as follows: given a sample S and x, we choose the least such that h, is consistent with S
member of T. We denote the set
Т). is easy
that H. is R.R class, [7] H
and we output (2)). However, there is no computable learner for H. Otherwise, by Lemma every member of H would be computable, and thus all paths of T would be computable.
4.3 Proof of Theorem 2
Theorem 2. Let H be an arbitrary class of hypotheses. The following are equivalent:
1. H is computably universally online learnable (in the realizable setting) by total learner.
2. There exists RFR class Z such that H S Z.
3. H. is computably agnostically learnable.
Proof. The implication online learnable via a total learner L. Let So. Si... be a computable enumeration of all possible samples (not necessarily realizable ones). For each Sn, the function L(S... is total computable with range {0, }. This gives us computable enumeration of the class Z (L(Sm,)) :) E NJ. which shows that Z is R.R. Lemma 3 then allows to conclude that 2 is a superset of H.
follows from Lemma 3 Assume that is computably universally
The implication 2
3 follows from the standard results about prediction with expert advice using countable experts. To be precise, we use the following lemma:
Lemma 5. Given computably enumerable set of total computable functions A, there exists computable randomized algorithm with sublinear regrel relative to the best function in A.
Several techniques are known that can be used to obtain the above lemma (see, e.g., Theorem 5 in Huutter et al., 2005). Computability of these techniques is usually only briefly discussed or even not mentioned at all. We give detailed proof of computability for one such algorithm in the Appendix B
7

---

Finally, we argue how to transform a computable agnostic learner into total computable universal for the realizable case. The argument proceeds two steps. First, we show that (3) (2). Then, the
implication (2) ① is straightforward: the strategy of the learner is to enumerate the elements of Z and try each hypothesis until we stop making mistakes.
We now argue that 2 2 Again, we want to apply Lemma 3 to show that we can obtain an
enumeration of superset of 7c by enumerating all functions of the form -, where L' satisfies the condition from Lemma 3 (i.e., making infinitely many correct predictions against any Adversary). Therefore, we need to show how to transform the randomized agnostic learner L into deterministic L' that makes infinitely many correct predictions on any H-realizable sequence.
In principle, it suffices to consider the majority vote taken over the internal randomness of I,, that is, always predict the more probable outcome (breaking ties arbitrarily). However, the majority vote for an almost total randomized function is not always computable. To guarantee computability, we need one additional simple trick. Imagine that we run an almost total randomized algorithm on some input æ, and the computation stops after finite number of steps. In particular, this means that f has seen only finite number of bits of the random advice ff can read at most one bit at each computation step. Now, suppose that we simulate f()) for all possible random advices until the computations stop for at least c probability mass of the random advices, for some small > O. This happens after finite number of steps since f is defined on random advices of probability one.
With that in mind, behavior of I. on all random inputs until these computations stop for at least 1 (k+ + 1-- probability measure of random advices. For each round, this also induces a new probability measure on random advices, where the whole probability mass is restricted to the set of the uniform measure 1 1 -kk+1] 1) Let us denote the product of these probability measures by P'.
define the learner L'_ Given the k-th number to label, T,' first simulates the
Now, suppose that we are playing against Adversary on some H-realizable sequence X. Let us define new random variable m7(5) the number of mistakes made by L on sample S divided by [S]. Also, let Xn, be the prefix of X of length n. Since L is an agnostic learner for H. we have limsup (X,),,,, E(lim = (X,,,, = 0). At the same time, we can observe that the same property holds if the expectation is taken with respect to the P' measure. This is because, at each round, the probability of making an error cannot increase more than (k: + 1) (recall that for binary variables expectation is equal the probability of sampling 1). Since En>o 1)- converges, this additional error can be neglected in the limit.
0). By the dominated convergence theorem,
obtain
This allows P' p'-prbbability at least 1/2. As a consequence, L' makes infinitely many correct predictions on X. Since X chosen to be arbitrary realizable sequence, we have shown that L' satisfies the condition from Lemma
apply Markov's inequality to conclude that lim - (X,)) 0 occurs with
4.4 Proof of Theorem
Theorem 3. There exists a class H. that is computably universally online learnable but not computably agnostically learnable.
Proof. We define a hypothesis class H that is computably universally online learnable yet has no total computable learner. Once this is established, the result follows by application of Theorem 2
Recall that i denotes the function computed by the n-th program. We say that infinite binary string h is an evil sequence for a learner yn if it satisfies the following conditions:
1. The initial segment of h of length n + 1 is 0"1: i.e., h[(n + 1) 0"11;
2. For every k > n, when the learner pPn is given the first k bits of that is, the sample (i, ( and is asked to predict the k-th bit, it outputs 1-1-hh h(k)).
If pr, is a total learner, then there is a unique evil sequence for pn. We define H as the least class containing the evil sequences of all total learners yn-
Clearly, no total computable yo, learns H. because makes infinitely many mistakes on the realizable sequence (i, h( where h is the evil sequence for Pn.
8

---

Before presenting computable learner for H. we need to establish certain properties of the class. Countability follows from the fact that there are countably many total learner (Pn, and each of them uniquely determines an evil sequence. Below, we show that H H (00)
It is clear that 0 E H. because there are hypotheses in H that start with 0", for infinitely many Towards a contradiction, suppose that f E H H. and f * 0 Then there exists a least no with (()) 1. Henee, some hypothesis E H starts with 0 By the uniqueness of evil sequences, follows that H contains only one hypothesis extending 0 However, the assumption f E H. \ H implies that there are natural numbers n1 < n2 < and hypotheses h1, h2.... from H. such that each h2 is distinct from f but h2 and f agree on the first n, bits. It follows that H. contains infinitely many hypotheses extending 0 1, contradiction.
A partial function e(n, x)) such that, for every n, if Pn is total learner, then e(n,.) is the evil sequence for Pn. can be computed by the following well-defined recursive procedure: on input x S n, output the x-th bit of 1"1; on input I > n, output ğ E {0, 13 such that ý * y ((i, e(n, ((r,,,))) i)) z)..
Computable learner for H. We start by guessing according to the hypothesis 0 until Adversary reveals one. Suppose the latter happens for the first time at position m, i.e., y(m) 1. At this point we know that Adversary is restricted to finitely many hypotheses from Hm := {h E H is the evil sequence for a total learner PP. n I m².. At subsequent stages, given sample S and an element we search for n S y such that e(n, 0). e(n, M) are defined and consistent with S, where M the maximum of x and all numbers appearing in S. Such n exists, because Adversary is consistent with element of Hmm and is able to compute it, as we observed above. Once such n is found, we predict e(n, x). Notice that if we make a mistake by predicting e(n, æ)), we will not predict according to e(n, -) again. If we were to make infinitely many mistakes, it would mean that Hm is infinite, which is not the case.
4.5 Proof of Theorem 4
Theorem 4. Let H be RER class. The following equivalent:
1. H is computably universally online learnable.
2. There exists R.R. class Z such that H. C Z.
3. H is computably universally online learnable by a total learner.
Proof. Let H. be a RER class. The implication
obvious. We first prove
Assume that H. is computably universally online learnable via L. Let So. Si,... be computable enumeration of all finite H-realizable samples. Such an enumeration exists because H. RER class. For each Sn, the function I(S..,) is total computable with range (0. 1]. This follows from the fact that Sn is H-realizable and that L is a learner for H. We observe that the class 2 = (L n NJ is R.R.R The reason for this is as follows: each L(S,, -) is a function computable by program that can be effectively obtained from the program computing and n, uniformly in n. (We use this kind of reasoning frequently, but state it explicitly only here.)
remains to prove that H. C Z. Let h E H. By Lemma 3 we can choose an H-realizable sample Se such that S. is consistent with h and L(S., -)= h. Therefore, h Z.
Suppose H. C 2, for some RER class Z. Let Z be a c.e. set of programs 2), and let 2g. ø1, be a computable enumeration of Z. We define a leamer L for H. as follows. On input (S, z), where S is any (finite) sample and x E N, we compute in = the least < |.S] such that S consistent with y... If no such < |S] exists, we set in = [S]. The output of the learner on (S, x) is 22.. (ar). Since each yz, is total, and y0:. (x) are always defined. Therefore, I. is total computable.
Now, we prove such that
[ee
To show that L learns H. let R (x1, ye 30 be H-realizable. By Lemma 2 and the fact that H. C Z. there exists ju := the least j such that for all n, Ren is consistent with Pay, By the definition of T., for almost all n, I(Rqn;; ) = Pazo (æn), and thus makes only finitely many mistakes on R. hence H is computably universally online learnable by total learner.

---

4.6 Proof of Theorem 5
Theorem 5. For every RER class H. H. is computably universally online learnable by a proper learner if and only if H. is RER class.
Proof. Let H be RER. To prove (+), assume that H. is RER, take Z := H. and proceed as in the proof of the implication 2 for H.
in Theorem 4 This way, we obtain computable proper learner
To prove (+), assume that H. is computably universally online learnable by proper learner L. Let So. St.... be computable enumeration of all H-realizable samples. Let = {L(Sp:)) n E NJ. Clearly, F is RER. Below, we show that F = H.
To show F C H. letg E F. We have !- L(S.,)) -), for some n. By the definition of proper learner (Definition 4) g is H-realizable. By Lemma 2 follows that g H.
To prove that H C F, let E H. By Lemma 3 there exists n such that S, is consistent with & and L(S,. g. Hence, by the definition of F, have g F.
4.7 Proof sketch of Theorem 6
Theorem 6. There exists a RER class that is computably universally online learnable but has no computable proper learner.
The full proof can be found in Appendix C We construct class A as stated in the theorem. The construction of A a program that enumerates its elements. To ensure that no computable learner for A is proper, we satisfy the following requirement R, for each program e:
If a learner &e is proper with respect to A. then (e does not learn A.
(Re)
Below, we briefly explain the approach to satisfying the requirements. Each R. is assigned its unique starting string 0 The strategy for the requirement R. operates at timesteps put into A only certain elements of [0*1] 1]. By definition, [0*1] consists of all infinite binary sequences that extend 0º1.
and is allowed to
Strategy for Re. At timestep let %e 1 At subsequent timesteps, we monitor which bit ye predicts come right after Ye- knowing that currently in A there is only one element extending Ye. namely y000. More precisely, we think Yh as the sample (0)), (1, 1, Ye(1- 1)), where / the length of Tes and we monitor the value of pe((Te l). Obviously, we cannot know this in advance-we can only check, at subsequent timesteps the construction, whether the program e outputs the prediction before executing at most instructions.
there is only one point in [0$1] n A. namely 0910 We
If never (that is, no timestep s) outputs a prediction, then e a learner for A. because is undefined on the A-realizable sample Ye. In this case, R, is vacuously satisfied, since the antecedent of R. false. Now suppose that e eventually outputs prediction. Then we consider two cases.
In the first case, we see that Pe is not proper for the current A-that is, (e((e, 1) = 1 (recall that, currently, the only element of A extending Ye is y²0)). In that case, we stop enumerating any points from [0=1] into A. Consequently, PPr. will remain non-proper for A and R. will be satisfied forever.
In the second case, we see that be may be proper for the current that is, 4e (%e I) = In that case, enumerate into A new hypothesis 10% This way, we force ye (Ye, () to make mistake, because now Adversary could disagree with the prediction (e(Te, = and reply with 1. We set Te := 7 and / : lxcl and the strategy continues monitoring the prediction of p. (), with these new values of Ye, 1. This ends the description of the strategy for R..
If, at subsequent stages, we keep getting the result that Pe(Te. is proper for the current A (the second case above), we will put into [0$1] n A infinitely many hypotheses (in the limit), namely 0000 for every > 0. By the construction, 9e. will make infinitely many mistakes on the A-realizable sequence 0 oo, Consequently, &a will not be a computable learner for A and R. will be satisfied.
10

---

Acknowledgments and Disclosure of Funding
Dariusz Kaloeiński acknowledges support of National Science Centre Poland grant under the agree- ment no. 2023/49/B/HS1/0399 Tomasz Steifer was supported by the Agencia Nacional de Investi- gación y Desarrollo grant no. 3230203.
References
Agarwal, S., Ananthakrishnan, N., Ben-David, S., Lechner, T., and Urner, R. (2020). On learnability wih computable learners. In Algorithmic Learning Theory, pages 48-60. PMLR.
Angluin, D. (1988). Queries and concept learning. Machine learning, 2:319-342.
Assos, A., Attias, I., Dagan, Y., Daskalakis, C., and Fishelson, M. K. (2023). Online Learning and Solving Infinite Games with an ERM Oracle. In The Thirty Sixth Annual Conference on Learning Theory, pages 274-324. PMLR.
Ben-David, S., Pál, D., and Shalev-Shwartz, S. (2009). Agnostic online learning. In COLT, volume page 1.
Blanchard, M., Hanneke, S., and Jaillet, P. (2022). Contextual bandits and optimistically universal learning. arXiv preprint arXiv:2301.002411
Blum, and Blum, M. (1975). Toward mathematical theory of inductive inference. Information and Control, 28:125-155
Bousquet, O., Hanneke, S., Moran, S., Handel, R. v., and Yehudayoff, A. (2020). A Theory of Universal Learning. CoRR, abs/201 1is//2011.0483.... .04483. arXiv: 201 1.1444488.
Bousquet, O., Hanneke, S., Moran, S., Van Handel, R., and Ychudayoff, A. (2021). A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 532-541.
Cenzer, D., Clote, P., Smith, R. L., Soare, R. I., and Wainer, S. S. (1986). Members of countable 11f classes. Annals of Pure and Applied Logic, 31:145-166.
Cenzer, D. and Remmel, B. (1998). IH classes in mathematics. In Ershov, L.., Goneharov, S. S., Nerode, A., Remmel, J. B., and Marek, V. W., editors, Handbook of Recursive Mathematics, volume 139 Studies Logic and the Foundations of Mathematics, pages 623-821. Elsevier. ISSN: 0049-237X.
Cesa-Bianchi, N., Freund, Y., Haussler, D.,, Helmbold, D. P., Schapire, R. E.,, and Warmuth, M. K. (1997). How to use expert advice. Journal of the ACM (JACM), 44(3):427
BiannBia,ch, N. and Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press.
Cutland, N. (1980), Computability: An Introduction to Recursive Function Theory. Cambridge University Press.
Delle Rose, V., Kozachinskiy, A., Rojas, C., and Steifer, T. (2023). Find witness shatter: the landscape of computable PAC learning. In The Thirty Sixth Annual Conference on Learning Theory, pages 511-524. PMLR.
Delle Rose, V., Kozachinskiy, A., and Steifer, T. (2025). Effective Littlestone dimension. Proceedings of Machine Learning Research vol, 272:1-13.
Engelking, R. (1989). General topology, volume 6 of Sigma Series in Pure Mathematics. Heldermann Verlag, Berlin.
Gourdeau, P., Tosca, I.., and Urner, R. (2024). the computability of robust PAC learning. The Thirty Seventh Annual Conference Learning Theory, pages 2092-2121. PMLR.

---

Hanneke, S., Shaeiri, A., and Wang, H. (2025). For universal multiclass online learning, bandit feedback and full supervision are equivalent. 36th International Conference on Algorithmic Learning Theory.
Hasrati, N. and Ben-David, S. (2023). On computable online learning. In International Conference on Algorithmic Learning Theory, pages 707-725. PMLR.
Hutter, M., Poland, J., and Warmuth, M. (2005). Adaptive online prediction by following the perturbed leader. Journal of Machine Learning Research, 6(4).
Kozachinskiy, A. and Steifer, T. (2024). Simple online learning with consistent oracle. In The Thirty Seventh Annual Conference on Learning Theory, pages 3241-3256. PMLR.
Kuratowski, K. (1972). Introduction to Set Theory and Topology, volume 13 of International Series of Monographs Pure and Applied Mathematics. Pergamon, second edition edition. ISSN: 02783231.
Littlestone, N. (1988). Learning Quickly When Irrelevant Attributes Abound: A New Linear- Threshold Algorithm. Machine Learning, 2(4):285-318.
Littlestone, N. and Warmuth, M. K. (1994). The weighted majority algorithm. Information and Computation, 108(2):
Odifreddi, P. (1989). Classical Recursion Theory. The Theory of Functions and Sets of Natural Numbers, volume 125 of Studies in Logic and the Foundations of Mathematics. Amsterdam.
Remmel, J. B. (1986). Graph colorings and recursively bounded Ill-lassess Annals of Pure and Applied Logic, 32:185-194.
Rogers, Jr., H. (1967). Theory of Recursive Functions and Effective Computability. McGraw-Hii series in higher mathematics. McGraw-Hill Book Company, New York, NY, USA.
Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding Muchine Learning: From Theory to Algorithms. Understanding Machine Learning: From Theory Algorithms. Cambridge University Press.
Sterkenburg, T. F. (2022). On characterizations of learnability with computable learners. In Confer- ence on Learning Theory, pages 3365-3379. PMLR.
Zvonkin, A. K. and Levin, L. A. (1970). The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematical Surveys, 25.6):83.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: claims are accurate and correspond theorems summarized at the beginning of Section and described in more detail in that section. Proofs are in Section or in the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
12

---

The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings. is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
limitations are discussed at the end of Section (Introduction) and in Section
(Discussion).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: all assumptions mentioned, proofs are complete and (to the best of our knowledge) correct.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
13

---

4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: the paper does not contain any experimental results
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: the paper does not include experiments requiring code
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //ni http://ccwii//eeaa/ee////etaaaaa
for more details.
14

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: the paper does not contain experiments
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: the paper does not contain experiments
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2iggma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
15

---

Justification:
the paper does not contain experiments
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: we have reviewed the NeurlPS Code of Ethies and adhered it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper's focus is in theoretical characterization of formal model of learning. As such, there no direct or indirect societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (c.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
16

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: the paper poses no such risks
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: the paper does not existing assets
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pwperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
17

---

14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsoureing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsoureing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLM was not used.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.LM for what should or should not be described.
18

---

A Proofs of helpful lemmas
To prove the required lemmas from Section 4.1 we invoke basic concepts and results from topology.
The Cantor space is the topological space on 2nd (the set of all infinite binary sequences) with basic open sets of the form [o] := {aX: X 2") for all E 2 (finite binary strings). For brevity, we denote this space by 2 is clear that members of 2 correspond to hypotheses, and that sets of points in the Cantor space correspond to hypothesis classes. The notion of closure introduced in the main text coincides with the standard topological closure: the closure of A. denoted by A, is defined as the least closed set containing A.
We say that p is an accumulation point of Af E A {p). In other words, every neighborhood of p contains points of A different from p. Intuitively, can be "approximated" by points in A. The set of accumulation points of A is denoted by D(A) and called the derived set of A. The closure of class can then be expressed in terms of the derived set as A ((A).
Proof of Lemmal 7 The lemma is obvious if h E H. Now suppose H. H. Since H. (H), it follows that h E D(H). Therefore. every open set containing h also contains points of H distinct from h (see, e.g., Kuratowski 1972. Theorem 1, p. 141). In other words, for every n E N, there exists hn E H such that h j h, and hn E [h [ nl.. It follows that for each n, (Ie, h(xx)) consistent with hn E H. Hence, h is H-realizable.
Lemma follows from some basic properties the Cantor space. Recall that the Cantor space is induced by the following metric on 2", known as the Baire metric:
if f 9, otherwise.
8(
The Cantor space is complete with respect to 6.
Let (Zt, y/ y be an H-realizable sequence. Hence, there exists sequence (hx) of elements of H. such that for every is E N, the sample (zi, b:) is consistent with hg. We call such a sequence a witness.
Proof of Lemma 2
Suppose there exists a witness (h+) such that { hI.... } is finite. Then there is Ç E H that occurs in (h4) infinitely often, and therefore ( is consistent with (zt, 9:) Moreover, <E E H. S H. so Ç as desired.
Now suppose that for every witness (h:); the set (ho, hi....) } is infinite. Fix a witness (hr), and let W (ha, ......
Let D (No, r.,..... We define sequence of subsets of 2 We set C-1 = 2". For n 2 0, we define:
On [Cn- [nn, s(n)] Cn--1 (n-(( (nn
if E D, and if D, b E 10, and Cn-1 ((n, n W is infinite.
(2)
Above, [(n, s(n)) [X E 2 X(n) s())
is clear that C² 2 C. 2 C. 2 .... We now show that C₂ W is infinite, for n -1, 1,0, This is obvious for 7 1. Fix 2 0 and suppose that Cn n W is infinite.
First, assume n E D. By the definition of witness, see that (n, s()) n W (hy H n).
Since Cn-1 n W is infinite, Cn n W = Cn-1 1 n [ni, sn)) n W is also infinite.
Second, assume that n & D. Now, since Cn-1 O W is infinite, it must be the case that either Cn-1 W n [(n, 0)] or Cn-1 n W n [(n, 1)] is infinite. So we can choose that satisfies 2
Observe that C_1, Co, Ct.... are closed. Obviously, C=1 is closed, and if Cn-1 is closed then C.. being the intersection of Cn-1 and a clopen set, is also closed.
Pick a sequence of points (g,) such that Śn E Cn n W. The sequence (Go = is Cauchy under the Baire metric. Since the Cantor space is complete with respect to the Baire metric, there exists lim Sn 2", All elements of (5x) ) belong to H. Since H. is closed, E H.
19

---

First, we briefly recall the randomized version of the algorithm for fixed time horizon T and finite number of experts n. At each round < T, the algorithm computes the weight wx(t) for each expert e, The prediction is obtained by sampling from probability distribution supported on the set of experts, with the probability of each expert e, being u. (t) Ejen (t))), and returning the prediction of the chosen expert. The weights are initialized as uniform (1, = 1) and then, at each round, we multiply the weight of the expert by e" if and only if the expert made incorrect prediction in the last round (otherwise, the weight remains the same). More precisely, w: the number of incorrect predictions of expert e, before round l. is known that for the appropriate It remains to show that ( is consistent with s. Suppose not. Hence, for some E D, ((x) & s(x).
Hence Ç [zz, 1 s(z)),, so ( & Cz. On the other hand, for each n 1,,0, l..... almost all elements of (Gn) are in Cn. and since Cn is closed, Ç E C.. So { E C2 and Ç & Cz, contradiction. So ( is consistent with s.
Proof of Lemma Let H be class of hypotheses and L learner. Assume that for each H-reallizblee play of the Adversary, L predicts infinitely many labels correctly. Towards a contradiction, suppose that there exists h E H such that for every sample S, if S is consistent with h then L(S.-) ) + h. Choose such an h.
We define a sequence (u=) by induction. Let Up = 0. Given Un, we define Un+1 as Un prolonged by (In, h(x,)), where F, is the least x such that L(U,, x) * h(x). This definition is correct which can be shown by simple inductive argument.
Each Un = (I,, ((x))) is an initial segment of the sequence (nt, h(x))) By Lemma 1 (I2,, (())))== is H-realizable by assumption, L predicts infinitely many labels correctly when playing against (æ,, proves the first part of the lemma.
However, L(Un, In+1) & h((a+1), for all n. A contradiction. This
The second part follows from the simple observation that if S is consistent with h E H then S is H-realizable.
Let L be computable learner for H and let h E H. By Lemma there exists sample such that L(S,-) = h. Hence, is computable.
Proof of Lemma 4
B Proof of Lemma 5
Suppose that we have countable set of experts N = {ei, e.. Our goal is to prove that there exists an almost total randomized computable algorithm that achieves sublinear expected regret with respect to N (where the expectation is taken with respect to the random advice sampled from the uniform measure). We will employ a variant of Weighted Majority Algorithm (W M.MA A), also known as Exponentially Weighted Average (Littlestone and Warmuth 1994 Cesa-Bianchhi et al. 1997). combined with the so-called doubling trick and increasing the number of experts over time.
enLi()) where Le(l) is
value of 7, depending in a computable way on 7 and n. the expected regret of this algorithm with respect to the finite set of experts, at each round < T, is bounded by / Th In (see Theorem 2.2. in Cesa-Bianchi Bianchi and Lugosi (2006) for modern exposition of this fact).
2
To extend this algorithm to an infinite pool of experts and an unbounded time horizon, we employ version of the doubling trick. We divide all rounds into disjoint blocks of increasing length, where k-th block consists of 2* rounds. In each block, we run the initial algorithm from scratch (i.e.. initializing the weights uniformly), with T = 2$ and the first & experts, adjusting the parameter 7) as required for the bound.
Now, consider an expert cm There are only finitely many rounds in which this expert is not taken into account. In these rounds, in principle, it can happen that the expected regret wrt em grows linearly. However, starting from the round / > Eo 2osiem 2²_ em is added to the active pool of experts, and the expected regret bound with respect to this expert applies. For k > m. the expected regret with
respect to 6ms in the k-th block of rounds, increases by at most / 1 In 2 < vI'
In particular, the
total expected regret for Ek11 2 < t < Σ 2 is bounded by 0(1) + Σt V2' for sublincarity.
which suffices
20

---

The above expectation is taken with respect to the product measure defined by the probability distributions over the experts considered in each round. We briefly argue how implement this procedure as an almost total randomized algorithm, with the bound on expected regret holding when expectation is taken with respect to the uniform measure (from which the random advice sampled).
Given an infinite random advice we split it into an infinite number of columns I1, 22, Ef- fectively, these columns form infinite sequence mutually independent random advices, each sampled from the uniform measure. We will use TR. the k-th column of x, to decide what to do in the k-th round of prediction.
In each round, our prediction procedure needs to sample one expert from a finitely supported probability distribution. The probability of sampling given expert is computable real number that
r, meaning that there is a computable procedure, which given n, outputs an approximation & such
2- In particular, this implies that there exists almost total preserig- mapping from the uniform measure on infinite binary sequences into the set experts (see, e.g., Theorem 3.1 in Zvonkin and Levin 1970p. We apply this mapping the zg to obtain the chosen expert. Since this mapping is finitely- vaalud, it is enough to read a finite prefix of x to know which expert is chosen.
More precisely, we interpret Iy as a real number in the interval [0, 1] in the usual way and use the correspondence between the uniform measure and the Lebesque measure that interval. The mapping between infinite binary sequences and real numbers is not unique, but becomes unique if we omit the rational numbers (which have which form a set of measure zero. Finally, we partition [0. 1] into disjoint subintervals, where each expert and its length is equal to the probability of sampling that expert. suffices to read finite prefix of Ik. to know to which of these subintervals zy is mapped to, except in the case when the real number corresponding Ik lies on the boundary of the subinterval. There are only finitely many such boundaries, and they form set of measure zero.
than one representation
binary sequences)
subinterval corresponds
C Full proof of Theorem 6
We construct as stated in the theorem. The construction proceeds computably in the number of timesteps 0, l.... At each timestep, we have finite set A, of programs, each computing an infinite binary sequence. We guarantee that A, S As+1 for all s E N, and define A= U Ag. The class A is then defined as A = {ipe
A}.
The requirements R. are formulated Section 4.7
Below, we describe the strategy for R. more formally. During the construction, the strategy maintains a variable "e that stores binary word. At timestep 0, we set % 0 and Ao = 0. The strategy may be one of two complementary stages: active or inactive. Initially, all strategies are active.
We use the notation (...) denote the execution of at most s instructions of program e on given input. The program may or may not halt (and return a value) within the time bound A halting computation (within the time bound) denoted by (e.)(...) J. and non-halting one by (e.s(...)
-trattry at timestep s O.
(1) If c, set A, == As U (760%)).
(2) If
(the strategy is inactive or (ee ITel) 1), we do nothing.
(3) If and the strategy is active, and (P,ss(e, hr/) 4. then let b Pe,a Itel)-
(a) If b = 1, the R. -trsttra changes its state to invactive.
(b) If 6 0, set A, A. (Te10%) and % %.l.
This ends the description of the strategy.
Construction. At each timestep 0, 1...., we first Ag Ao-1 and then we run the Rta-ttatteeiss for all < s.
The verification is split into lemmas.
Lemma 6. A is a R.E.R. class.
21

---

Proof. Given binary string Z E N, and E {0, 1). let 9: x) output a(z) for x < |a] and i otherwise. Let f.. E {0, 13, be total computable function such that ()((a))) In the construction, the operations A, == A, {re00} and A, := A. respectively. The set A = =U A is computably A, := U (f(Te)) and A, := A, U, enumerable because it can be defined as follows: n E A if and only if there exists a timestep at which n E Ag. Clearly, the predicate of two number variables defined by n E Ag is computable.
9: (a :)
10 10 really mean
follows that computably enumerable Since we define A {pe: : c E A), A is RER.
Lemma 7, A is computably univerally online learnable.
Proof. We define RER class such that A C Z, and apply Theorem
Let Z = {fa(0'1)) e, E (f e, E N}. where fo. fi are as in the proof of Lemma 6 and define Z = {tpa e ZJ. By the projection theorem (see the proof of previous lemma), Z is computably enumerable because it can be defined as follows: n E Z iff there exist e, such that fo 1') or ( 1)). It follows that Z is RER.
It remains show that A C Z. In Appendix A we observed that À = AUD(A)
First, we prove A C Z. If is enumerated into A, then e' = fo(71), for some e, with 7 of the form 0'1 > 0, j E N. It follows that A S Z, so A C Z.
Finally, we prove ((A) C Z. Let E (00) -0 e N}. Clearly, E C Z. Let
A' = 10000000 : e,j > 0}. A C A' so D(A) S D(A'). is enough to show D(A') C E. For a contradiction, let X E D(A) \ E. By the properties of D(-):
For all there are infinitely many elements of A' starting with X | n.
(3)
X starts with 0 because every element of A'' starts with O. Since X A 0 X starts with 0*1 for some k > 0. Since * 0* 10, X starts with 0* 1'0, for some j > O. But A' n [0$150] = {0*100>) which is finite set. This contradicts 3
Lemma 8. No computable online learner for A is proper.
Proof. We show that every requirement Re is satisfied. Assume that ye is a learner and that yoe is proper with respect to A. The are three cases to consider.
1. The value of Te becomes 0$15, j O, and p0.00 f) 1, that is the program on input (0$15, e + j) never halts, which causes the Re-strategy to execute step (2) indefinitely thereafter.
We argue that this case is not possible. Suppose the contrary. Note that since Ye has become 0'12, it must have gone through the previous values 0-1 for 1 I k < j. Therefore, for each previous value 0*1* of %e, the Rt-strategy has executed step (b) at some point (otherwise, it would not have reach the current value 0"1",, and therefore 1***+100 was enumerated into A, for 1 < k < j. So 0 1 is in A. It follows that 0'12 is A-realizable. Since &e is proper with respect to A, pp (0 15 + 5) 4. contradiction.
It follows that whatever value 7 assumes, we encounter a stage 8 at which (e,5 ITel) and thus we execute step (3).
2. The value of Te becomes 0$1 > 0 and (0 1.
We argue that this case is also not possible. Assume otherwise. By the reasoning above, 0 000 E A for 1 S k S j. Since (0"1s,, e j) 1, we finally execute step (a) while Ne 0'13, which makes the Rt-strategy inactive. Afterwards. the Rtssteyy always exectues step (2) due to it being inactive. Hence, we will never enumerate into A any hypothesis starting with 0-1 11+1, But then (0*1)),. is not A-reaizzable, because for an
'It is computer science folklore that, given program and an input to it, one can effectively transform it into another program that behaves exactly like the original on that input (see. e.g. Rogers 1967 Theorem 1-V). "According to the standard characterization of computably enumerable sets, B is computably enumerable if and only if there exists a computable relation R(x, y) such that x E B < 3yR( y). Formal details can be found in Rogers 1967 Corollary 5-XI).
22

---

A-realizable sample 0-12 and x = e j. the learner Pe outputs 1, yet no element of A is consistent with this prediction. Hence yp, is not proper contradiction.
From this and the previous case, it follows that:
3. For every value of Ne. there is a stage at which the Rt-Sttategy executes step (b).
It follows that " assumes, in order, all the possible values 0'12 for all j > 0. This means that = 0 1-000 E A for all j > 0. It follows that 09 E A and that yoe (0 1001,,,e11 (e = 0. for all j > By Lemmal] [ the sequence (z. (z)))== is A-realizable. But for every n 2 e, Pe makes a mistake on the sample (z, r (z))) == and x + 1. Hence, Se does not learn A.
D A graph-coloring example
By Theorem I there exist RER (and even DR) classes that are universally online learnable but have no computable learner. The proof of this result relies on the existence of computable trees of certain kind. The notion of a computable tree is defined Section 4.2) For brevity, and following standard usage in the literature, the set (T') of all infinite paths through computable tree T is called a 1Iς class.
Although the class of hypotheses from Theorem I may appear artificial, the existing literature on applications of 11 classes allows us identify more natural examples. Below, we describe one such example-the the problem of learning colorings of computable graph.
Imagine that graph is given with fixed but unknown coloring, and attempt learn this coloring. Graph coloring can represent an existing allocation or strategy- as frequency assignments in wireless networks conflict-free strategy choices in game-theoretic settings. This learning scenario represents various evvers-engineeriig problems, in which one seeks to infer the internal logic or policy of system from its observable outcomes.
Before going into the specifics of our graph-coloring example, let us describe the key idea behind such applications. Given computably presented problem, the corresponding set of solutions be represented as a 11f class [P]. The correspondence between the elements of [P] and the solutions to the problem is typically established via natural coding of the latter by infinite sequences pptts through a computable tree P. As a result, coding-invariann properties that hold for all (some) II! classes automatically extend the corresponding sets of solutions. For comprehensive survey of similar applications of IIŞ classes in logic, combinatorics, game theory, and analysis, see Cenzer and Remmel 1998).
computable graph G (V, E) consists of a computable set C N of vertices and a computable edge relation E C V V. We consider only undirected graphs. A k-coloring of G is map from V to (1. k} such that g(u) # g(v) for any vertices u, v with E(u,v) v).
Learning k-colorings of computable graph. Let (V, E) be k-colorable computable graph, and let Hg be some set of k-colorings of G. In each round, Adversary gives vertex E V. Learner outputs color ÿ E 21.2..... k), and then Adversary reveals the "true" color y {1, (1.2....,A) k).
Below we present an example of the above lcarning problem: a computable graph G and a set He of k-colorings of G, such that He is universally online learnable but cannot be learned by any computable learner. This example is corollary of the following result by Remmel (1986).
Theorem 7. There exists a k-colorable computable graph with a decidable k-coloring problem and a k--olloiig g such that g the unique uncomputable coloring of G.
A graph G has decidable k-coloring problem if there is a program that decides, for any k-coloring of finite subgraph F' of G. whether f is extendable k-coloring g of G.
Let Vo. Ui.... be a 1-1 enumeration of and let E fw) be the length of this enumeration. A coloring of G may be represented as a sequence X E {1, 2, ..., k)' such that X * X(j) whenever Elv, v.). We let G' denote the induced subgraph of G with vertex set (Vo, Ui,..., 1n-1).
23

---

Lemma 9. Suppose G is a computable k-colorable graph with decidable k-coloring problem. Then there exists a program computing function cff. n) with the following property: for any n E N and any f {0, 1, : 1- - 21....... k). .......,,,. k-coloring g of G, then e(f.-) is a k-colloing of extending f-
if is a k-coloring of G and f is extendable to
The proof of the above lemma is straightforward.
We now define our example of graph-coloring problem. Let Go (Vo, Eo) be graph from Theorem 7
Definition Let the class HG, consist precisely of those functions c(f,) )) for which there exists N such that f represents k-coloring of Go In that is extendable k-coloring of Go-
It can be easily shown that HG. is RER.
Lemma 10. HG. represents the set of all k-colorings of Go-
Proof. If g E HG. then every initial segment gin represents k-coloring of Go Gn.n. If g were not a k-coloring of Go, then there would exist i, such that g(i) = g(j) and Bo 0j); but then any sufficiently long initial segment of g would not represent a k-coloring of the corresponding subgraph of Gu.
For the other direction, if g is k-coloring of Go. then every initial segment g|n is k-coloring of Go in that can be extended k-coloring of Go. Therefore, c(g n..) E HG which shows that g E Ho.
follows immediately from Theorem that the class HG, is countable. By Lemma HG. is not computably universally online learnable because HG. contains an uncomputable member. remains observe that Ha. universally online learnable. Since HG. is countable, arrange its elements into a sequence fuo hi..... A universal online learner for Hg. works as follows: on input (S,z), z). where a sample obtained in previous stages of the game, output h2 (z), where is the least j such that hy is consistent with S. By Lemma any realizable sequence arising from Adversary's moves is consistent with some element of HG. so the described learning strategy will eventually stop making mistakes.
We note that the previous paragraph requires reproving the lemmas from Section 4.1 for the topological space (1.2..... k] k}"" which is the product space of the discrete space 21, kj. The Cantor space 2 can be obtained in a similar way as a countable product of the discrete space {0, 1 In general, the proofs lemmas from Section 4.I depend on the properties of the underlying topological space, such as compactness and metrizability. It is known that a countable product of compact spaces is compact with respect the product topology (Tychonoff's theorem). Moreover, there exists a metric such that the topology on {1,2,... k induced by that metric coincides with the product topology (see, e.g., [nngelinng] 1989. Theorem 4.2.2., p. 259).
24


Reviews:
[{"review_id": "JUsltSWwQl", "reviewer": "Reviewer_K2dL", "summary": "The authors introduce computability requirements to the framework of universal learning and show:\n- That there exists a recursively enumerable class that is universally learnable but not computably universally learnable.\n- A characterization of agnostic computable universal learning\n- A characterization of a variant that requires algorithms to be proper", "questions": "Could you comment on the set-up/my confusion between the universal learning set-up of Bousquet et al. (2021) and the universal vs uniform online learning set-up mentioned in the weakness section? It is a bit difficult to evaluate the rest of the paper without that issue clarified. \n\nCould you give more intuition/details on your definition of proper learning, as it is not really standard? \n\nThere are also proper/improper separation results in standard CPAC learning (Delle Rose et al., 2023) -- how do your results compare?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- Novel set-up: computability has not yet been considered for universal learning, of interest to the learning theory community\n- A variety of results are shown, with very few lose ends\n- The technical weight of the proofs seems adequate for NeurIPS\n\n## Weaknesses\n- There isn't much context/review/explanations about universal learning, which is relatively recent (2021). I would guess most of the NeurIPS readership (even learning theory folks) would not be familiar enough with these concepts for the level of explanations given here. If the authors intend on submitting in a conference like NeurIPS, more explanations should be given on this set-up.\n- Likewise, there is a lack of clarity in the beginning of Section 2.1. Most readers will be familiar with online learning, but, at first glance, lines 88-92 do not make it clear what is the difference with the more common set-up of online learning and this one: even in (uniform) online learning the adversary is allowed the flexibility to change the target as long as it is consistent with the history. What differentiates uniform and universal online learning is that, in the former, the number of mistakes has to be uniformly bounded (there exists a learner $\\mathcal A$ and integer $d\\in\\mathbb N$ such that *for any* $h\\in \\mathcal H$ , $\\mathcal A$ makes at most $d$ mistakes) vs in the uniform online learning, the number of mistakes is simply required to be finite (so, there is an algorithm $\\mathcal A$ such that for any $h\\in\\mathcal H$ there exists $d_h\\in\\mathbb N$ such that $\\mathcal A$ makes at most $d_h$ mistakes). This is distinction between set-ups is not clear at all, and would be confusing for most readers who are only/mostly familiar with uniform online learning.\n- I am not very familiar with universal learning, but my understanding is that there is a distribution at hand (in a PAC-like set-up, but where the learning rate can also be distribution-dependent), and that the universal online learning results are tools to take back to this main set-up. In particular, the error in universal learning depends on the distribution at hand (as in p.2-3 of Bousquet et al., 2021), and a central concern in universal learning is that of learning rates (not really studied here). Here it seems the paper is mostly concerned about the online version of universal learning? In any case, the authors do not provide any explanations for the departure from the universal learning set-up of Bousquet et al. (2021)\n\t- An attempt was made for Definition 1 to be readable/intuitive, but this was at the cost of clarity and precision, which is not ideal considering that the whole paper is based on this set up. Please include appropriate mathematical objects ( $\\mathcal H$ , $X$ , labels $y_t$ ) and quantifiers. The authors should also reference the work of (Bousquet et al, 2021) in the definition (and the appropriate works in any subsequent definition)\n- There are basic definitions missing:\n\t- For example, a computable learner not only halts on every sample, but also output functions that are themselves total computable (see Definition 8 in Argarwal et al., 2020). Most NeurIPS readers will *not* be familiar with computable learning frameworks, and some more effort should be made in the write-up to introduce these concepts, and also attribute the definitions to the works they originally belong to.\n- The authors state many literature results without references:\n\t- l.127-129: Delle Rose et al., 2025.\n\t- l.184: not sure where this comes from. Definition 2 should read agnostic online learning I believe.  In any case, universal learning depends on the learning rates, so you have classes that are universally learnable but at arbitrarily slow rates, and thus not PAC learnable (implying not online learnable). So I am not sure this assertion is true -- but it is hard to check without a proper reference.\n- Overall, the writing lacks clarity, precision, rigour and the necessary definitions/ideas to get the point through to a NeurIPS audience (including learning theory folks), which has been a big factor in my score. I am a bit confused by the various set-ups and the difference with the Bousquet et al. (2021) paper (which I read briefly to prepare for this review).\n\n## A note on writing:\n- Learner vs learner (l.139): it would be better to have different names. Why not simply \"strategy\"?\n- The writing could be improved (e.g., l.169 \"In agnostic learning, it only makes sense when the Learner has a strategy defined on all possible inputs, including non-realizable ones\", awkward phrasing, l.184 \"in standard theory\" - of what?, etc., and there are many instances where an article is missing before the noun, e.g., l.13 \"We then study agnostic variant of\" -> \"We then study the agnostic variant of\"; l. 25 \"a strategy that guarantees uniform bound on mistakes\" -> \"a strategy that guarantees a uniform bound on mistakes\", etc.)\n- In Section 4, it would be worth restating the theorems being proved for readability (right now, the reader has to go back and forth)\n- I am also generally not a fan of anthropomorphizing learners/ adversaries (even less so with only \"he\" for all parties). Perhaps the authors would consider changing \"he/his to \"it/its\"\n- While not crucial, it would also be helpful to have definitions of DR, RER, closure of $\\mathcal H$ , and general computability definitions in proper definition environments for readability.", "was_revised": true, "final_justification": "Upped my score 3 -> 5 (see response to reviewers for justification)", "rebuttal": "Let us elaborate on the relation between our definitions and the work of Bousquet et al 2021. In the full version of their paper (posted on arxiv) there are at least two learning settings that are called universal learning. \nYou are right that Bousquet et al. 2021 was primarily concerned with studying learning rates under probabilistic sampling. But a crucial technical contribution of their paper - announced in the main paper and developed in the full version - is the notion of ordinal Littlestone dimension and showing that ordinal Littlestone dimension characterizes online learning without uniform mistake bound under Adversarial sampling (compare this to the line 28 of our paper). Bousquet et al 2021 mention this setting on page 535 (the paragraph below Definition 1.7) of the conference paper and refer to the full arxiv version for details, where they call it the \"universal variant of online learning\" (Section 3.1 on Page 15 of the full arxiv version of their paper). This name was further used by Hanneke et al (ALT 2025). We understand that this may seem somehow confusing and personally, we would prefer to call this setting “non-uniform online learning”. However, in the light of this setting being called “universal learning” and “universal online learning” by other authors (Bousquet et al. 2021, Hanneke et al 2025), we decided to follow the established terminology. \n\nIndeed, our Definition 1 simply repeats the earlier definition of “universally online learnable” as introduced by Bousquet et al (page 15 of the full paper) and then generalized to multiclass learning on page 9 of Hanneke et al 2025. To avoid confusion we will rewrite lines 88-92, highlight the main difference between uniform and non-uniform set-ups and extend the definition with additional symbolic explanation: We say that $L$ universally online learns $H$ if for every $H$-realizable sequence $(x_t,y_t)_{t>0}$ there exists $m$ such that for all $n>m$ and every sample $S=(x_1,y_1),(x_2,y_2),...$ we get $L(S,x_n)=y_n$.\n\nSimilarly, our definition of agnostic learning is adapted from the Definition 6 of Hanneke et al 2025. Please note that we reference this paper in the line 151 when we introduce the agnostic setting. So indeed, for the agnostic learning defined as having sublinear expected regret, it is already known that both realizable and agnostic settings are fully characterized by the ordinal Littlestone dimension, as shown by Hanneke et al 2025 (Theorem 3 there). \n\nWe will disambiguate our citation of Bousquet et al. 2021 to clearly point to the right (adversarial online) setting.  We also propose to change “universally learnable” to “universally online learnable” (and similarly “agnostic learning” -> “agnostic universally online learning”) in any occurrence of these notions in the text. This is an easy fix that should help avoid confusion. We will also add a brief comment in the introduction to make it clear that there are two meanings of universal learning in the full version of Bousquet et al. 2021 and that we are concerned with the online one. We humbly note that we have repeated multiple times that we work with an online learning setting. \nFurthermore, we have provided all relevant definitions in the text, which should clear any confusion. We believe that our presentation, together with the suggested improvements, is of sufficient mathematical rigour, similar to that usually encountered in learning theory papers. \n\nRegarding flexibility of the Adversary. In the uniform case, it doesn’t matter if the Adversary can change the target function. If the Littlestone dimension is finite, then we can achieve uniform mistake bound even if the Adversary is adaptive and if the Littlestone dimension is not finite, Adversary does not need to be adaptive to force $k$ mistakes for arbitrary $k$. Perhaps for this reason, many authors choose to say instead that the target function is fixed in advance (for instance, see the standard textbook by Shai Shalev-Shwartz and Shai Ben-David). In fact, this is how the setting was originally defined in Littlestone 1998. The flexibility only matters when we drop the requirement of uniformity. This is why we highlighted this aspect in our presentation. \n\nRegarding computable learners. In online learning a learner outputs a prediction on a point, not a whole function. The definition 8 from Agarwal et al. 2023 is a definition of computable learner in cPAC setting, not in online learning. Our definition of a learner (see line 140) follows that used by previous authors, both in standard online learning and in its computable version e.g. Hasrati and Ben-David 2023 or Delle Rose et al 2025. A computable learner is just a function $f$ such that $f$ is a learner and $f$ is computable. We use “computable” in the standard sense. The only subtle point in our setting is concerned with learner being a partial or total computable function but this distinction is discussed in detail in the paper.\n\nWe will add the reference to the Lines 127-129. This reference is not Delle Rose et al 2025. Please note that the correct references were already given when the claim first appeared in line 50.\n\nRegarding proper learners. First of all, let us say that for the universal online learning, there is no established notion of 'proper learning' yet. In other learning settings, “proper” usually means 'predicting always according to some function from the class'. In the non-uniform online learning, this notion is too strong, since the Adversary can effectively use a function that is not in the class (but rather in its topological closure). Therefore, to be able to say something non-trivial, we decided to define 'proper universal online learning' as 'predicting always according to some realizable function\". \nThe Reviewer also asked about proper vs improper learning in cPAC setting. This scenario differs in many ways from our case. Proper cPAC learning is problematic in the agnostic case, when we cannot guarantee a computable Empirical Risk Minimizer (ERM). In computable universal online learning, proper is problematic already in the realizable case. In the realizable cPAC, every $RER$ class of finite VC dimension is properly cPAC learnable in the realizable case (see Agarwal et al 2020). This is because in the realizable setting, any $RER$ class has a computable ERM. This can be contrasted with the universal online learning setting, where even a computable ERM is not always enough to construct a computable learner. This observation (Proposition 1) is one of the main contributions of our paper."}, {"review_id": "1pmFm4Y7Ez", "reviewer": "Reviewer_iVFU", "summary": "Recently, it has been shown that PAC learning might be undecidable, and that learnability cannot be determined within ZFC. In the model of computational PAC learning, where algorithms must computably output predictors, the main idea is that the VC dimension no longer characterizes learnability. Instead, a \"computational\" version of the VC dimension, known as the effective VC dimension, takes its place. Similar results have been shown for online learning and the Littlestone dimension.\n\nThis paper studies the computational version of universal learning, a model introduced by Bousquet et al., STOC 2021. This model lies between classical universal consistency and PAC learning. Unlike PAC learning, the sample complexity in this model depends on unspecified constants that themselves depend on the (fixed but unknown) data distribution.\n\nMy main concern is that the learning model described in the paper does not actually correspond to universal learning, see below.", "questions": "My main concern is about the definitions of the learning model, see above.", "limitations": "Limitations are addressed.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "I believe there is considerable confusion in the paper regarding the definition and scope of the universal learning setting as introduced by Bousquet et al. (STOC '21). In particular, the authors refer to this model as an online learning setting, which is not accurate. For example:\n\nAbstract: \"We address this question for universal learning, a generalist theoretical model of online binary classification, recently characterized by Bousquet et al. (STOC´21).\"\nThe model proposed by Bousquet et al. is not an online learning model. Although online learning techniques are used within the algorithm, the setting itself is batch, not sequential.\n\nLines 30–31: \"This setting aligns with real-world scenarios where uniform bounds are not always available and where data distributions may shift.\"\nThis is misleading. The distribution in this setting is fixed in advance and does not shift. The key feature is that the sample complexity may depend on the distribution (via unknown constants), but the distribution itself does not change with the sample size.\n\n The paper claims to study “agnostic computable universal learning,” but the characterization of even the simpler model of agnostic universal learning is still unresolved. Without a full understanding of the base model, it is unclear how one can meaningfully study a more complex, computability-based variant.\n\nDefinition 1: This is neither the standard definition of universal learning nor a rigorous formalization. \n\nAdditional Comments:\n\nLine 20 (Introduction): It is unclear what relevance multi-armed bandits have to the discussion in this paper.\n\nLine 28: \"Adversary fixes one true function H in advance.\"  There seems to be a typo here. \n\nDefinition 2: The definition of the agnostic setting appears to be incorrect. It is not clear what learning model is being formalized here.\n\nFinally, I must note that some sections may have been generated or heavily by an LLM, especially the introduction.", "was_revised": true, "final_justification": "POST-REBUTTAL:\nThe authors clarified the exact setting they are studying and suggested simple modifications to improve the clarity of the presentation.\nTherefore, I am updating my score.", "rebuttal": "Let us elaborate on the relation between our definitions and the work of Bousquet et al 2021. In the full version of their paper (posted on arxiv) there are at least two learning settings that are called universal learning. \nYou are right that Bousquet et al. 2021 was primarily concerned with studying learning rates under probabilistic sampling. But a crucial technical contribution of their paper - announced in the main paper and developed in the full version - is the notion of ordinal Littlestone dimension and showing that ordinal Littlestone dimension characterizes online learning without uniform mistake bound under Adversarial sampling (compare this to the line 28 of our paper). Bousquet et al 2021 mention this setting on page 535 (the paragraph below Definition 1.7) of the conference paper and refer to the full arxiv version for details, where they call it the \"universal variant of online learning\" (Section 3.1 on Page 15 of the full arxiv version of their paper). This name was further used by Hanneke et al (ALT 2025). We understand that this may seem somehow confusing and personally, we would prefer to call this setting “non-uniform online learning”. However, in the light of this setting being called “universal learning” and “universal online learning” by other authors (Bousquet et al. 2021, Hanneke et al 2025), we decided to follow the established terminology. \n\nIndeed, our Definition 1 simply repeats the earlier definition of “universally online learnable” as introduced by Bousquet et al (page 15 of the full paper) and then generalized to multiclass learning on page 9 of Hanneke et al 2025. To avoid confusion we will extend the definition with additional explanation: We say that $L$ universally online learns $H$ if for every $H$-realizable sequence $(x_t,y_t)_{t>0}$ there exists $m$ such that for all $n>m$ and every sample $S=(x_1,y_1),(x_2,y_2),...$ we get $L(S,x_n)=y_n$. Again, please note that this definition simply follows the work of previous authors, including that of Bousquet et al.\n\nSimilarly, our definition of agnostic learning is adapted from the Definition 6 of Hanneke et al 2025. Please note that we reference this paper in the line 151 when we introduce the agnostic setting. We cannot agree that this definition is incorrect or that it is not clear what setting we formalize, as we give a precise reference to the paper from which we took it. So indeed, for the agnostic learning defined as having sublinear expected regret, it is already known that both realizable and agnostic settings are fully characterized by the ordinal Littlestone dimension, as shown by Hanneke et al 2025. We hope that it is now clear that the base model is already fully understood.\n\nWe will disambiguate our citation of Bousquet et al. 2021 to clearly point to the right (adversarial online) setting.  We also propose to change “universally learnable” to “universally online learnable” (and similarly “agnostic learning” -> “agnostic universally online learning”) in any occurrence of these notions in the text. This is an easy fix that should help avoid confusion. We will also add a brief comment in the introduction to make it clear that there are two meanings of universal learning in the full version of Bousquet et al. 2021 and that we are concerned with the online one. We humbly note that we have repeated multiple times that we work with an online learning setting. \nFurthermore, we have provided all relevant definitions in the text, which should clear any confusion. We believe that our presentation, together with the suggested improvements, is of sufficient mathematical rigour, similar to that usually encountered in learning theory papers. \n\nThe expression “where data distributions may shift.” refers to the fact that in the universal online learning setting the Adversary is adaptive and can change the target function. We will remove this sentence to avoid unnecessary confusion. Similarly, “multi-armed bandit” are mentioned simply as an example of many formal models studied in learning theory."}, {"review_id": "SaFyOKpsp9", "reviewer": "Reviewer_b4op", "summary": "This work investigates when learners that achieve objectives such as universal learning (i.e., making only finitely many mistakes in the limit) can be made computable in the online binary classification setting. Specifically, it asks: for which hypothesis classes $\\mathcal{H}$ does there exist a computable online learner that makes only finitely many mistakes on every realizable example sequence $(z_t) = (x_t, y_t)$ such that for any $t \\in \\mathbb{N}$, there exists a hypothesis $h \\in \\mathcal{H}$ such that $y_s = h(x_s)$ for all $s \\le t$? Note that this definition allows the realizing hypothesis $h_t$ to vary with the finite horizon $t$, a condition the authors call local consistency of the labels with $\\mathcal{H}$.\n\nPrevious work has provided a characterization of universally learnable hypothesis classes. However, the question of whether learners achieving the finite-mistakes objective can be made computable has remained unaddressed until now. In this sense, the present work fills a fundamental gap by focusing on the algorithmic implementability of the online learner, emphasizing that a learning \"procedure\" must be an algorithm (in the Turing sense), not merely an explicit mathematical construction.\n\nThe main contributions are several. First, the authors show that even if $\\mathcal{H}$ is recursively enumerably representable (RER), this alone does not guarantee the existence of a computable universal learner. Undeterred by the failure of this natural sufficient condition, the authors develop a deeper characterization, which falls short of their initial goal but still yields significant and interesting results. \n\nIt is shown that $\\mathcal{H}$ admits a *total* computable universal learner if and only if the topological closure of $\\mathcal{H}$ is contained in an RER set. Note that “computable” alone refers to partial computability, meaning the learner may be undefined or fail to halt on some inputs in its domain. Hence, the existence of a total computable learner is a strictly stronger assumption than merely requiring computable universal learning. Moreover, the aforementioned conditions are equivalent to the existence of a computable agnostic learner for $\\mathcal{H}$, where a computable agnostic learner is a randomized, almost-total learner that achieves sublinear regret relative to $\\mathcal{H}$ on any example sequence, not just those realizable by $\\mathcal{H}$. A complete characterization of computable universal learning, which was perhaps the original inspiration for this work, remains an open problem.", "questions": "1. **Are the authors assuming that each hypothesis in the given class is a total computable function?** Identifying $h$ with an infinite binary sequence in Cantor space appears to require that every entry of the sequence is defined. Moreover, in parts of the proof where the consistency of $h$ with the current finite history of examples is checked, it seems crucial to ensure that a defined (halted) value for $h(x_s)$ exists for all $s \\le t$.\n\n2. **Related to the above issue, Lemma 5 seems to require that every expert is a total function.** If an active expert's prediction is undefined on feature x_t, then we cannot compute the exponential weights update for time t+1.\n\n3. **Proof of Theorem 5, (3) => (2) is unclear. In particular, in lines 310-314 and 324-327.** I do not see the necessity of introducing a new probability measure $P'$. Given the $[0,1]$-valued forecasts produced by the multiplicative weights update (MWU) algorithm, which the authors denote as the randomized no-regret algorithm $L$, the goal is to construct a deterministic online learner $L'$. The authors achieve this by simulating all random advice sequences at round $t$ until all but a $1/(k+1)^2$ fraction have halted, and taking a majority decision. However, the majority decision yields a deterministic value with no residual randomness because the random advice sequences are simulated according to a fixed (potentially dovetailed) enumeration to ensure that $L'$ is deterministic. Therefore, the introduction of the probability measure $P'$ seems unnecessary and is confusing to me.\\\n\\\nThe quantity of interest seems to be the gap between the expected 0/1 loss of the randomized prediction $\\hat{y}_t$, output by $L$, and the majority decision $\\bar{y}_t$, a deterministic quantity once the enumeration of random advice sequences is fixed, computed from all but a $\\delta_k$ fraction of the random advice sequences on which $L$ halts. Using the inequality $(\\bar{y}_t \\neq y_t) \\le (\\bar{y}_t \\neq \\hat{y}_t) + (\\hat{y}_t \\neq y_t)$, where $y_t$ is the observed label, and then taking the expectation over $\\hat{y}_t$, appears sufficient to analyze the regret gap.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. **Addresses a significant and often overlooked gap in the field.** The majority of works in learning theory, aside from a recent line of remarkable contributions, leave the issue of computability entirely unaddressed. These works often incorrectly refer to explicit mathematical procedures as “algorithms,” a term with a precise technical meaning established by Gödel, Church, and Turing, without formally considering their computability. I therefore find it greatly satisfying that this work rigorously tackles the computability question in the context of online learning.\n2. **Proof techniques are particularly illustrative.** The authors identify hypotheses on the input domain $\\mathbb{N}$ with elements of Cantor space, which is a complete metric space (w.r.t. the Baire metric on infinite sequences) and hence a well-defined topological space. This identification enables a clean mathematical formulation and facilitates the use of well-established tools from analysis.\n3. **Excellent exposition.** I believe this level of clarity is a significant contribution on its own, given the technical nature of the notions and proof techniques involved in computability. Minor clarifications could further improve it, especially since computability is highly sensitive to precise specification of the objects involved (see **Questions** for details).\n\n### Weaknesses\n1. **Setup is clean but lacks a connection to standard hypothesis classes.** For example, which reasonable subsets of linear threshold functions (LTFs) over $\\mathbb{S}^{d-1}$ are RER? This gap could leave the exposition feeling incomplete. The authors’ statement,\n> ... in this paper we limit our attention to universal learning of hypotheses defined on $\\mathbb{N}$. This might seem limiting but this choice is guided by practical considerations. Indeed, all practical machine learning happens on computers, which inherently work with countable domains, such as images or binary strings. From the point of view of computability, learnability on natural numbers is sufficiently general to model any domain relevant to practical applications.\n>\nreads more like a deflection than a rigorous argument, as it does not directly address how standard hypothesis classes like LTFs can be formalized within this framework. While it is reasonable to view focusing on $\\mathbb{N}$ as a necessary first step, it should also be recognized that many standard hypothesis classes, particularly those defined over continuous domains with real-valued parameters like threshold functions on [0,1], are technically not RER and thus fall outside the current formalism.\\\nExtending this computability framework to encompass more standard hypothesis classes, such as LTFs defined on unit spheres in $\\mathbb{R}^d$, remains an important connection to establish and will require careful, meticulous formalization, even if it does not involve fundamentally new ideas.\n    \n2. Some aspects of the setup and proofs are unclear, as detailed in the **Questions** section.", "was_revised": true, "final_justification": "Rating remains the same. Reasons are provided in my response to the authors' rebuttal.", "rebuttal": "Thank you a lot for such a positive review!\n\nAd. 1 and 2. You are right in both cases. We assume that each hypothesis is a total computable function and indeed, we should have stated in Lemma 5 that each expert is total as well. Thank you for noticing this.\n\nAd 3. In our argument, the no-regret randomized learner is only assumed to be almost total. This means that the set of random advices on which the algorithm halts is of measure 1 but still it is possible that the algorithm does not halt on some random advice. In such case we cannot always derandomize the algorithm into a computable majority vote. If the algorithm is defined everywhere, on every random advice, we can just enumerate all the random oracles until at some point the computations will stop on exactly measure 1 set of random advices. But if the algorithm is only almost everywhere total, then enumerating random oracles only guarantees that we will keep seeing larger and larger measure, approximating $1$ but possibly never reaching it. Roughly speaking, what can happen is that both label 1 and label 0 will keep having approximately 1/2 of all the measure we have enumerated so far and we will never know what is the value of majority vote. For instance, it could happen that our randomized algorithms halts on random advices of form 01..10 (outputting 0) and 1..10 (outputting 1), in which case we have a tie. But seeing always only a finite set of oracles we cannot distinguish this from the case when for some advice of form 01....1 the output is 1, in which case the majority vote should give 1.\n\nThat's why we need this small trick, in which we say that we will care only about the measure that is very close to $1$ (this is our $P'$). On this restricted set of random advices the majority is computable and we then simply note that any additional mistakes we have got this way can be neglected, since we are only interested in the asymptotic property of sublinear regret."}, {"review_id": "AsSMgr94H9", "reviewer": "Reviewer_A9r9", "summary": "This submission studies universal learning from a computability perspective. Universal Learning is a theoretical model of online binary classification where an adaptive Adversary can change the target concept (rather than fixing it ahead of time). Prior work (e.g., Bousquet et al. 2021) characterized universal learnability. This paper adds the constraint that the Learner must be implementable as a computer program. In this case, no characterization was known. The submission also studies proper computable universal learning.\n\nThe submission shows:\n- Universal learnability does not imply computable universal learnability, even for recursively enumerably representable (RER) classes.\n- A characterization for when a hypothesis class is computably learnable in the agnostic setting (here, the Adversary can choose any sequence, not just one belonging to the class).\n- A characterization for when proper computable learning is possible.\n- Separations that indicate that some classes are computably universally learnable but not computably agnostically learnable, and some RER classes are computably universally learnable but not by any computable proper learner.", "questions": "1. How does randomized sampling on LLMs fit into example 3, if at all?\n2. Proposition 1 shows that even DR (decidably representable) classes might not be computably universally learnable. Is there some intuition on what aspects of a DR class leads to the noncomputability of a universal learner?", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- I find the paper to be written pretty clearly, even as someone who has not studied universal learning in depth.\n- The paper makes progress on and in some cases (e.g., characterizations) fills what stands as a gap in the literature on the topic.\n- The paper's topic is fundamental: what are the limits of universal learning when we require that the learner be implementable as a program?\n\n**Weaknesses**\n- The paper feels much better aligned with theoretical computer science venues such as COLT, STOC/FOCS, and even CCC (computational complexity conference). While the connection to \"learning\" is clear, in my opinion, the paper doesn't demonstrate why these specific computability results will inspire future research in the typical scope of Neurips (relative to COLT, STOC/FOCS, CCC).\n- The paper motivates the question it studies (we should be able to implement algorithms by a program), but it does not sufficiently motivate why answering this kind of question with computability theory is appropriate.\n- It is hard to interpret example 3 (LLMs and universal learning) since it is stated \"At a high level of abstraction.\"\n\n**Overall:**\nI understand that computability is an established, classical approach to complexity. And I also agree that initial motivation is good, which is that universal learning should be studied with attention to the fact that learning algorithms, for all intents and purposes, should be implemented as a computer program. However, I'm not convinced that characterizing computability (in the sense defined) of universal learning actually answers this question in a practically meaningful way.", "was_revised": true, "final_justification": "I recommend a score of 3 (Borderline Reject).\n\nWhile the paper is technically solid, its central contributions have limited significance for the NeurIPS audience (in my opinion). The main results link properties of hypothesis classes (like RER and DR), which relate to their \"describability,\" to a very weak, binary notion of learnability (whether an algorithm is computable or not). This is a step away from more informative and fine-grained efficiency questions that are central to machine learning.\n\nThe proof techniques, such as diagonalization-style \"evil sequence\" arguments from TCS, are applied here to establish results whose practical implications for machine learning remain unclear.", "rebuttal": "Thank you for your review! \n\nRegarding computability, it certainly makes sense to study universal learning under stricter complexity bounds—such as primitive recursiveness or polynomial-time computability. However, the most general notion of effectiveness (i.e., computability) provides a natural starting point for analysis. This approach encompasses all practically meaningful learners. Negative results in this setting are especially informative: if no computable learner exists, then there can be no primitive recursive or polynomial-time learner either.\nFrom a presentation standpoint, computability-theoretic proofs are often cleaner and easier to understand than those involving finer-grained bounds like polynomial-time or primitive recursion. At the same time, NeurIPS has already published papers on related formal frameworks (even without any computational constraints) in the recent past (see for instance Z. Lu \"When Is Inductive Inference Possible?\", NeurIPS 2024). From this perspective, our paper makes a small step closer towards the practical aspects as compared to pure learning theory papers with no computability.\n\nAd 1. We can think that randomized sampling in LLMs corresponds to decisions made by the Adversary (each path in the tree of random choices is a different possible adversarial behavior). As usual in adversarial setting, we are interested in the worst-case scenario (what is the worst we can see while doing random sampling) as opposed to average case. \n\nAd 2.  Yes, there is a short intuition. In our setting the Adversary is adaptive, which means that they can effectively use a hypothesis outside of the DR or RER class $\\mathcal{H}$, even if locally at each round the target hypothesis is consistent with some function from $\\mathcal{H}$. To be more precise, the Adversary can use any function from the topological closure $\\overline \\mathcal{H}$.  A DR class of hypotheses $\\mathcal H$ may have a non-computable element $h$ in its closure $\\overline \\mathcal{H}$.  The intuition is that we can approximate a non-computable object by an infinite sequence of computable ones. To take the LLMs example, any finite sequence of tokens produced by an LLM is computable (even under randomized sampling), but if we let the token generation run indefinitely, we can obtain a sequence that is no longer computable (hence, outside of computable learner's grasp)."}]

Author rebuttal:

Meta-review: The paper studies the problem of defining computable learners for online learning, under universal quantification (i.e., we require only a finite number of mistakes on every realizable data sequence, not necessarily bounded over all such sequences).  Both universal online learning and computable online learning have been studied actively in recent years.  One might be tempted to guess that computable universal online learning might be a simple mash-up of these two theories, with all the same equivalences and separations.  But surprisingly, this paper shows it's not so simple.  Unlike uniform online learning, this work shows there exist recursively enumerable classes that are universally online learnable but not computably universally online learnable.  They also give an extension to the agnostic case, where they show there exist realizable-case computably universally online learnable classes which are not agnostic-case computably universally online learnable (though the agnostic-to-realizable reduction continues to work in the case of recursively enumerable classes).  They further completely characterize the agnostic-case computably universally learnable classes.  They also characterize properly learnable classes.  The characterizations reflect an important connection to topological closures of concept classes.  These results reveal an interesting landscape of scenarios, beyond a mere extension of the theory of computable uniform online learning.

The reviewers agree that the results are novel, and align with recent topics of interest in learning theory.

Some reviewers (though not others) found issues in the presentation, leading to much confusion about the setting.  The authors have indicated they will implement appropriate changes to address these.

Another review notes the paper would be enhanced by the addition of natural examples illustrating the theory (e.g., perhaps a higher-dimensional example such as the discrete positive-halfspaces example in Bousquet et al. 2021).
Decision: Accept (poster)