A Theory of Optimistically Universal Online Learnability for General Concept Classes

Authors: steve  hanneke
hongao  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 20:49:06

Abstract: We provide a full characterization of the concept classes that are optimistically universally online learnable with {0, 1} labels. The notion of optimistically universal online learning was defined in [Hanneke, 2021] in order to understand learnability under minimal assumptions. In this paper, following the philosophy behind that work, we investigate two questions, namely, for every concept class: (1) What are the minimal assumptions on the data process admitting online learnability? (2) Is there a learning algorithm which succeeds under every data process satisfying the minimal assumptions? Such an algorithm is said to be optimistically universal for the given concept class. We resolve both of these questions for all concept classes, and moreover, as part of our solution we design general learning algorithms for each case. Finally, we extend these algorithms and results to the agnostic case, showing an equivalence between the minimal assumptions on the data process for learnability in the agnostic and realizable cases, for every concept class, as well as the equivalence of optimistically universal learnability.

Main paper: 
 introduction: 
 Just as computability was once a core question in computation theory, learnability is now a core question in learning theory. Intuitively, learnability is trying to ask whether we can predict the future correctly with high probability by observing enough examples. In order to describe this intuition formally, we need to define learning models, such as, Probably Approximately Correct (PAC) learning (Vapnik and Chervonenkis [1974] and Valiant [1984] ), online learning (Littlestone and Warmuth [1986] ) and query learning (Angluin [1988] ). In this paper, we focus on a variant of online learning: online learning under data processes. In this setting, the learning is sequential: in round t, an instance X t is given to the algorithm, and then the algorithm makes the prediction, ŷt , based on the history (X ≤t-1 , Y ≤t-1 ) and the input X t , i.e., ŷt = f t (X ≤t-1 , Y ≤t-1 , X t ). Next, the target value Y t will be revealed to the learner such that it can be used to inform future predictions. We model these sequence as a general stochastic process (X, Y) = {(X t , Y t )} t∈N (possibly with dependencies across times t). We say that the algorithm is strongly consistent under (X, Y) if the long-run average error is guaranteed to be low, i.e., 1 n n t=1 I [ ŷt ̸ = Y t ] → 0 almost surely, when n → ∞. In our setting, any theory of learning must be expressed based on the properties of, or restriction on, the data process, as the mistake bound is based on the data process. Thus, following an approach found in much of the learning theory literature, such as the PAC model of Valiant [1984] and Vapnik and Chervonenkis [1971] and the online learning model of Littlestone [1988] , we introduce the restriction by an additional component, concept class H ⊆ Y X . The role of the concept class is to restrict the processes we need to face, such that they all are realizable under that concept class. If there is a target function h * ∈ H, such that Y t = h * (X t ) for every t, we say the data process (X, Y) is realizable (though our formal definition below is slightly more general). For a given X, if a learning rule is strongly consistent under (X, Y) for every Y such that (X, Y) is realizable, we say it is universally consistent under X in the realizable case.It is known that we cannot get the low average error guarantee for all concept classes and data processes [Hanneke, 2021] . Thus, we should make several restrictions on either the data process, the concept class, or a mixture of both. All three types of restrictions have been investigated : Littlestone [1988] , Ben-David et al. [2009] studied online learning with unrestricted data processes but restricted concept classes. Haussler et al. [1994] , Ryabko [2006] researched the online learning problem with a mix of both restrictions. There are also substantial amount of papers investigating online learnability with all measurable functions but restricted data processes. Most of these specifically consider the case of i.i.d. processes, such as Stone [1977] , Devroye et al. [1996] , though this has also been generalized to general stationary ergodic processes [Morvai et al., 1996 , Gyorfi et al., 1999] or processes with certain convergence properties enabling laws of large numbers [Morvai et al., 1999 , Steinwart et al., 2009] .More recently, a general question has been studied: In the case of H equals the set of all measurable functions, is there a learning rule guaranteed to be universally consistent given only the assumption on X that universally consistent learning is possible under X? The assumption that universal consistency is possible under X is referred to as the "optimist's assumption" [Hanneke, 2021] , and for this reason, learning rules which are universally consistent for all X satisfying the optimist's assumption are said to be optimistically universally consistent. There is a series of works focusing on this question, starting from Hanneke [2021] and continuing with Blanchard and Cosson [2022] , Blanchard [2022] , Blanchard et al. [2022a] . They tackle this question by first characterizing the minimal assumptions on the data process admitting universally consistent learning and then proposing an online learning algorithm that is universally consistent for all data processes satisfying that assumption. However, their works all focus on the situation with no restrictions on concepts in the concept class (i.e., H as all measurable functions). Thus, a natural question arises: For which concept classes do there exist optimistically universal learning rules?In this paper, we investigate the question mentioned above when the output is binary, i.e. {0, 1}. We handle this problem by first figuring out the minimal assumptions on the data process admitting consistent online learning as well. Thus, Our results answered that question in the following aspects:• For which concept classes is optimistically universally consistent learning possible? • What are the sufficient and necessary conditions for the processes to admit universally consistent online learning for a given concept class H? • For which concept classes is it the case that all processes X admit universally consistent online learning?We first answer these questions under the realizable case. Surprisingly, the answers turn out to be intimately related to combinatorial structures arising in the work of Bousquet et al. [2021] on universal learning rates. This suggests a potential connection between the universal consistency of online learning and universal learning rates, which is of independent interest. We also extend our learning algorithms for the realizable case to the agnostic setting, where the requirement of low average loss is replaced by that of having sublinear regret. Interestingly, our answers to the above questions remain unchanged in the agnostic case, establishing an equivalence between agnostic and realizable learning in this setting.algorithm from the work of Littlestone and Warmuth [1994] . This line of work makes no assumption on the data process and investigates how the restrictions on the concept affect the learnability of the problem. There are two other categories of assumptions also investigated in history: one is to make assumptions on both the data process and the concept, and the other is to make assumptions on the data process but not the concept. Those two categories are discussed in detail subsequently.First, the works investigating the question of learnability with restrictions on both the data process and the concept make a variety of assumptions. For example, Haussler et al. [1994] investigate how the restrictions on the concept will affect learnability given that the data process is i.i.d. This problem is more similar to a streamlined version of PAC learning and they show that there is a logarithmic mistake bound with the assumption that the data process is i.i.d. and the concept class has finite VC dimension. Adams and Nobel [2010] reveal that all stationary ergodic sequences will uniformly converge under the concept class with finite VC dimension. However, they cannot show the convergence rate of that learning algorithm. Many other works focus on revealing the rate with slightly stronger assumptions on the sequences, such as, [Yu, 1994, Karandikar and Vidyasagar, 2002] .Another line of works focuses on the question of learnability with restrictions on the process instead of the concept, starting from the theory of universally consistent predictors under i.i.d sequences.In particular, there exists an online learning rule, such that for any i.i.d sequences(X, Y), and every measurable function f * , the long-run average loss is 0 almost surely, such as, [Stone, 1977 , Devroye et al., 1996 , Hanneke et al., 2021] . In the meanwhile, people are also interested in the consistency under non-i.i.d. processes, Bailey [1976] and Ryabko [1988] show that we can not get a consistent estimator for general stationary ergodic processes when we care about the loss for one round after t rounds of observation and learning. However, Gyorfi et al. [1999] , Morvai et al. [1996] reveal that if we cared about long-run average loss, universally consistent learning rules existed under general stationary ergodic processes. The paper of Morvai et al. [1999] and the paper of Steinwart et al. [2009] show the universal consistency even under the processes generally to satisfy laws of large numbers.More recently, the work of Hanneke [2021] investigates whether there is a consistent learning rule given only the assumptions on X that universally consistent learning is possible. This work generalizes the assumptions on X made by the previous works on universal consistency. The assumption that universally consistent learning is possible is known as "optimist's assumption", so the consistency under that assumption is called optimistically universal consistency. Hanneke [2021] studies three different learning models: inductive, self-adaptive, and online, and proves that there is an optimistically universal self-adaptive learning rule and no optimistically universal inductive learning rule. After this beginning, the works of Blanchard and Cosson [2022] , Blanchard et al. [2022a] , Blanchard [2022] show that optimistically universal online learning exists and the processes that admit strongly universal online learning satisfies the condition called C 2 (see condition C for reference). This problem is also investigated under different models, such as, in contextual bandit setting Blanchard et al. [2022b Blanchard et al. [ , 2023] ] and regression problem Blanchard and Jaillet [2023] . 
preliminaries and main results: 
 In this section, we provide the formal definition and model setting we need and briefly list the main results of this paper without proof. For brevity, we provide the high-level proof sketch in the subsequent sections and proof details are in the appendices.We formally provide the learning model here. Let (X , B) be a measurable space, in which X is assumed to be non-empty and B is a Borel σ-algebra generated by a separable metrizable topology T . We also define a space Y = {0, 1} called label space. Here we focus on learning under the 0-1 loss: that is, (y,y ′ ) → I [y ̸ = y ′ ] defined on Y × Y, where I [•] is the indicator function. A stochastic process X = {X t } t∈N is a sequence of X -valued random variables. A stochastic process Y = {Y t } t∈N is a sequence of {0, 1}-valued random variable. The concept class H, which is a non-empty set of measurable functions f : X → Y. 1The online learning rule is a sequence of measurable functions:f t : X t-1 × Y t-1 × X → Y,where t is a non-negative integer. For convenience, we also define ĥt-1 = f t (X <t , Y <t ), here (X <t , Y <t ) = {(X i , Y i )} i<t is the history before round t.There are two ways to define the realizable case: The most common one is that there exists h * ∈ H such that Y t = h * (X t ). The other is the definition 1 on the realizable data process, which comes from the universal learning setting. These two definitions are equivalent in the uniform PAC learning with i.i.d. samples. However, they are different when talking about universal learning. Thus, we follow the definition from the universal learning setting. The realizable data processes are defined formally as:Definition 1. For every concept class H, we can define the following set of processes R(H):R(H) := (X, Y) = {(X i , Y i )} i∈N : with probability 1, ∀n < ∞, {(X i , Y i )} i≤n realizable by H.In the same way, the realizable label set:Definition 2. For every concept class H and every data process X, we can define the following set R(H, X): R(H, X):= Y = {Y i } i∈N : ∃ a function f, such that Y i = f (X i ) and (X, Y) ∈ R(H). .In this paper, we first investigate the problem of universal consistency under X and H in the realizable case. An online learning rule is universally consistent under X and H if its long-run average loss approaches 0 almost surely when the number of rounds n goes to infinity for all realizable label processes. Formally, we have the following definition:Definition 3. An online learning rule is strongly universally consistent under X and H for the realizable case, if for every Y ∈ R(H, X), lim sup n→∞1 n n t=1 I Y t ̸ = ĥt-1 (X t ) = 0(a.s.).We also define the universal consistency under X and H for the agnostic case. In that definition, we release the restrictions that Y ∈ R(H, X), instead the label process Y can be set in any possible way, even dependent on the history of the algorithm's predictions. Thus, the average loss may be linear and inappropriate for consistency. Therefore, we compare the performance of our algorithm with the performance of the best possible Y * ∈ R(H, X), which is usually referred to regret. We say an online algorithm is universally consistent under X and H for the agnostic case, if its long-run average regret is low for every label process. Formally, the following definition:Definition 4. An online learning rule is strongly universally consistent under X and H for the agnostic case, if for every Y * ∈ R(H, X) and for every Y, lim sup n→∞1 n n t=1 I Y t ̸ = ĥt-1 (X t ) -I [Y t ̸ = Y * t ] ≤ 0(a.s.).To describe the assumption that universal consistency is possible under the data process X and the concept class H, we need the following definition for both realizable and agnostic cases:Definition 5. We say a process X admits strongly universal online learning (or just universal online learning for convenience) if there exists an online learning rule that is strongly universally consistent under X and H.If the online learning rule is universally consistent under the assumption that universally consistent online learning is possible, we call it optimistically universal under the concept class. If there is an optimistically universal learning algorithm under that concept class, we will say that concept class is optimistically universally online learnable. The formal definition is provided below: Definition 6. An online learning rule is optimistically universal under concept class H if it is strongly universally consistent under every process X that admits strongly universally consistent online learning under concept class H.If there is an online learning rule that is optimistically universal under concept class H, we say H is optimistically universally online learnable.Next, we define the combinatorial structures we use to characterize the concept class that makes all processes admit strongly universally consistent online learning and is optimistically universally online learnable when all processes admit strongly universally consistent online learning:Definition 7 (Littlestone tree Bousquet et al. [2021] ). A Littlestone Tree for H is a complete binary tree of depth d ≤ ∞ whose internal nodes are labeled by X , and whose two edges connecting a node to its children are labeled 0 and 1, such that every finite path emanating from the root is consistent with a concept h ∈ H. We say that H has an infinite Littlestone tree if it has a Littlestone tree of depth d = ∞. Definition 8 (VCL Tree Bousquet et al. [2021] ). A VCL Tree for H of depth d ≤ ∞ is a collection{x u ∈ X k+1 : 0 ≤ k < d, u ∈ {0, 1} 1 × {0, 1} 2 × • • • × {0, 1} k } such that for every n < d and y ∈ {0, 1} 1 × {0, 1} 2 × • • • × {0, 1} n+1, there exists a concept h ∈ H so that h(x i y≤k ) = y i k+1 for all 0 ≤ i ≤ k and 0 ≤ k ≤ n, where we denote y ≤k = (y 0 1 , (y 0 2 , y 1 2 ), . . . , (y 0 k , . . . , y k-1 k)), x y ≤k = (x 0 y ≤k , . . . , x k y ≤k ) We say that H has an infinite VCL tree if it has a VCL tree of depth d = ∞.The characterization is formally stated in the following two theorems: Theorem 9. If and only if a concept class H has no infinite VCL tree, any process admits strongly universally consistent online learning under H. Theorem 10. If and only if a concept class H has no infinite Littlestone tree, any process admits strongly universally consistent online learning under H, and the concept class H is optimistically universally online learnable.According to theorem 9, we know that for those concept classes with infinite VCL tree, there exist some processes that do not admit universal online learning. Thus, we need to figure out the sufficient and necessary conditions that the processes required to admit universal online learning. To state the condition, we first define the experts: they are algorithms that generate predictions only based on the input X t . Then we define the following condition (which is a property of a data process) and state the main theorem formally: Condition A. For a given concept class H, there exists a countable set of experts E = {e 1 , e 2 , . . . }, such that ∀Y * ∈ R(H, X), ∃i n → ∞, with log i n = o(n), such that:E lim sup n→∞ min ei:i≤in 1 n n t=1 I [e i (X t ) ̸ = Y * t ] = 0 (1)Theorem 11. A process X admits strongly universally consistent online learning under concept class H with infinite VCL tree if and only if it satisfies condition A.Next, the sufficient and necessary conditions (on the concept class) for optimistically universal online learning and the theorem: Condition B. There exists a countable set of experts E = {e 1 , e 2 , . . . }, such that for any X admits universal online learning, and any Y * ∈ R(H, X), there exists i n → ∞, with log i n = o(n), such that:E lim sup n→∞ min ei:i≤in 1 n n t=1 I [e i (X t ) ̸ = Y * t ] = 0 (2)Notice that these two conditions (condition A and B) only have one major difference: whether the countable set of experts depends on the process X. Theorem 12. A concept class H with infinite VCL tree is optimistically universally online learnable if and only if it satisfies condition B.We also extend the algorithms for realizable cases to an algorithm for agnostic cases and show that the same characterization works for agnostic cases.Example 1. We have the instance space X = R and Y = {0, 1}, a binary output. The concept class H is all of the threshold functions. In other words,H threshold = {h a : h a (x) = I [x ≥ a] |a ∈ R}.This concept class has no infinite VCL tree, as there is no (x 1 , x 2 ) such that H threshold shatters all possible results. Thus, all processes admit strongly universally consistent online learning under H threshold . However, it has an infinite Littlestone tree. Thus, for any learning algorithm, there exists a process that is not learnable by that algorithm. So it is not optimistically universally online learnable.Referring to that line of optimistically universal online learning papers, we know that the concept class of all measurable functions is optimistically universally online learnable. The sufficient and necessary condition for processes to admit universal online learning under all measurable functions is the condition C 2 (see below). In the meanwhile, our conditions: A and B vanish to C 2 when the concept class H becomes the class of all measurable functions.Condition C (C 2 in Hanneke [2021]). For every sequence {A k } ∞ k=1 of disjoint elements of B, |{k ∈ N : X 1:T ∩ A k ̸ = ∅}| = o(T )(a.s.)The following example shows that whether a concept class is optimistically universally online learnable is neither sufficient nor necessary to determine whether its subset is optimistically universally online learnable or not. Whether a concept class is optimistically universally online learnable will be sufficient and necessary to determine whether its subset is optimistically universally online learnable, if and only if the processes that admit universal online learning are the same under those two concept classes.Example 2. We have the data which is sampled from input space X = X 1 ∪ X 2 and here X 1 and X 2 are disjoint. For example, X 1 = R + and X 2 = R\R + . Then we can define the concept class: H 1 is the set of all threshold functions on X 1 which are 0 on X 2 , and H 2 is a set of all functions on X 2 which are constant on X 1 . Then we can consider the following scenarios:1. H = H 2 : It is optimistically universally online learnable. The processes that admit universal online learning will satisfy C 2 if we replace all the X t ∈ X 1 as dummy points.2. H = H 1 ∪ H 2 : It is not optimistically universally online learnable, as all processes supported on X 1 admit universal online learning under H. However, for every learning strategy, there exists at least one process on X 1 forcing that strategy to make linear mistakes.(Due to theorem 9 and theorem 10)3. H are all measurable functions on X . This is also optimistically universally online learnable. 
sufficient and necessary condition that all processes admit universal online learning: 
 In this section, we answer the question: What restrictions on concept classes make ALL processes admit universal online learning under H? The answer is formally stated in theorem 9. We show the sufficiency of this theorem by providing a universally online learning rule (depends on X) under every process X and H with no infinite VCL tree.First, we define the VCL game along with the VCL tree. In this game, there are two players: the learner, P L , and the adversary, P A . These two players can do the following actions in each round k:• P A choose the point X (k) = (X j1 , .. . , X j k ) from the given process.• P L choose the predictiong k = (g k (X j1 ), . . . , g k (X j k )) ∈ {0, 1} k . • P L wins the game in round k if H X (1) ,g1,...,X (k) ,g k = ∅.HereH X (1) ,g1,...,X (k) ,g k = {h ∈ H : ∀i, h(X (i) ) = g i (X (i) )}, which is the subset of H that is consistent on (X (i) , g i (X (i) )) for all i. Here (X (i) , g i (X (i) )) = {(X j k , g i (X j k ))} k=1,2,...,i . {(X (i) , g i (X (i) ))} i≤k is denoted by U in the algorithm.A strategy is a way of playing that can be fully determined by the foregoing plays. And a winning strategy is a strategy that necessarily causes the player to win no matter what action one's opponent takes. We have the following lemma from Bousquet et al. [2021] .Lemma 13 (Bousquet et al. [2021] lemma 5.2). If H has no infinite VCL tree, then there is a universally measurable winning strategy g for P L in the game.Notice that the winning strategy g is completely decided by U , we use g U standing for the winning strategy induced by the set U . We may use this winning strategy g U to design an online learning algorithm 1. This algorithm is a combination of the algorithm in the work of Bousquet et al. [2021] and the algorithm inspired by the learning algorithm for partial concept in the work of Alon et al. [2021] .In this algorithm, we have w(H ′ , X ≤T ) = |{S : S ⊆ {x i } i≤T such that S shattered by H ′ }|, which is the number of the subsequences of the sequence X ≤T that can be shattered by the partial concept class H ′ . H g U is the partial concept class induced by g U , which contains the concepts that are not consistent with g U at more than k -1 data points, if U = {(X (i) , g i (X (i) ))} i≤k-1 .Thus the realizable sequence of the induced partial concept class is formally written asH g U = {{(X i , Y i )} i=1,...,n ∈ R(H) : n ∈ N, ∀i 1 , . . . , i k ∈ [n], (y i1 , . . . , y i k ) ̸ = g k (x i1 , . . . , x i k )}.We also defineH {(Xi,Yi)} i≤t = {h ∈ H : ∀i ≤ t, h(X i ) = Y i }. And X t≤i≤ m(m+1) 2 = {X i } t≤i≤ m(m+1) 2 . Algorithm 1: Learning algorithm from winning strategy k = 1, U = {}, t ′ ← 0. for t = 1, 2, 3, . . . do if ∃j 1 , j 2 , . . . , j k < t such that g U (X j1 , . . . , X j k ) = (Y j1 , . . . , Y j k ) then Advance the game: U ← U ∪ {((X j1 , . . . , X j k ), (Y j1 , . . . , Y j k ))}. k ← k + 1. L ← ∅. m ← 1. t ′ ← t -1. end 1 Predict Ŷt = argmax y Pr w(H g U L∪(Xt,1-y) , X t<i≤ m(m+1) 2 +t ′ ) ≤ 1 2 w(H g U L , X t≤i≤ m(m+1) 2 +t ′ ) X ≤t if Y t ̸ = Ŷt then L ← L ∪ {(X t , Y t )}. end if t ≥ m(m+1) 2 + t ′ . then m ← m + 1. end endThe following lemma from the work of Bousquet et al. [2021] holds: Lemma 14 (Bousquet et al. [2021] ). For any process {(X i , Y i ) i∈N } ∈ R(H), there exists t 0 , such that for all t ≥ t 0 , algorithm 1 will not update k and winning strategy g k and for all j 1 , j 2 , . . . , j k , we will have:g k (x j1 , . . . , x j k ) ̸ = (y j1 , . . . , y j k ).Proof. By the definition of the winning strategy, it leads to a winning condition for the player P L . By the definition of P L 's winning condition, we know that there exists a k such that H X1,g1,...,X k ,g k = ∅, which means for all j 1 , j 2 , . . . , j k , g k (x j1 , . . . , x j k ) ̸ = (y j1 , . . . , y j k ). That finishes the proof.This lemma shows that if the concept class H with no infinite VCL tree, for a sufficiently large t, the VCL game will stop advancing after round t. Once the game stops advancing, we are effectively just bounding the number of mistakes by a predictor based on a partial concept class of finite VC dimension. This result is interesting in its own right, we extract this portion of the algorithm into a separate subroutine 1 (stated as Algorithm 2 in AppendixA.1) for which we prove the following result.Lemma 15. For any process X and H be a partial concept class on X with VC(H) = d < ∞. Subroutine 1 only makes o(T ) mistakes almost surely as T → ∞.For brevity, we put the proof of this lemma in the appendix. The intuition behind the proof is that every mistake decreases the weight by at least half with more than half probability, so the number of mistakes is bounded.Combining the lemmas above, for a concept class H with no infinite VCL tree, for any realizable sequence, Algorithm 1 satisfies lim sup n→∞1 n n t=1 I Y t ̸ = ĥt-1 (X t ) = 0(a.s.). Because the winning strategy only updates finite times, the long-run average number of mistakes is dominated by the number of mistakes made by the subroutine 1, which is o(T ) for large enough T .To prove the necessity, we show that for every concept class H with an infinite VCL tree, there exists at least one process that does not admit universally consistent online learning under H. We need the following definition and results from Bousquet et al. [2023] . Notation 16 (Bousquet et al. [2023] ). For any u ∈ ({0, 1}) * , let index(u) ∈ N denote the index of u in the lexicographic ordering of ({0, 1}) * .Definition 17 (Bousquet et al. [2023] ). Let X be a set and H ⊆ {0, 1} X be a hypothesis class, and let T = {x u ∈ X : u ∈ ({0, 1}) * } be an infinite VCL tree that is shattered by H. This implies the existence of a collectionH T = {h u ∈ H : u ∈ ({0, 1}) * } of consistent functions.We say such a collection is indifferent if for every v, u, w ∈ ({0, 1}) * , if index(v) < index(u), and w is a descendant of u in the tree T , then h u (x v ) = h w (x v ). In other words, the functions for all the descendants of a node that appears after v agree on v.We say that T is indifferent if it has a set H T of consistent functions that are indifferent.Theorem 18 (Bousquet et al. [2023] ). Let X be a set and H ⊆ {0, 1} X be a hypothesis class, and let T be an infinite VCL tree that is shattered by H. Then there exists an infinite VCL tree T ′ that is shattered by H that is indifferent.Then we state our theorem for necessity here: Theorem 19. For every concept class H with infinite VCL tree, there exists a process X, such that X does not admit universal consistent online learning. Proof Sketch. First, we can modify the indifferent infinite VCL tree such that it has the property that the number of elements contained by the k-th node in the Breadth-First-Search (BFS) order is 2 k-1 .The data process we are choosing is all the data come in the lexical order in each node and the BFS order among different nodes. Then we take a random walk on this tree to choose the true label for each instance. The instances in the node visited by the random walk will be labeled by the label on the edge adjacent to it in the path. The instances in the node that is off-branch will be labeled by the label decided by its descendants. (We can do this as the tree is indifferent.) Thus, when reaching a node on the path, no matter what the algorithm predicts, it makes mistakes with probability 1 2 . Thus, it makes a quarter mistake in expectation. Then by Fatou's lemma, for each learning algorithm, we get a realizable process such that the algorithm does not make a sublinear loss almost surely. We finish the proof of theorem 9 here. We then focus on the existence of the optimistically universal online learner when all processes admit universal online learning.In this part, we show that the condition whether H has an infinite Littlestone tree is the sufficient and necessary condition for the existence of an optimistically universal online learning rule, when all processes admit universal online learning. This is formally stated as theorem 10. The sufficiency part of theorem 10 is proved in Bousquet et al. [2021] as the following lemma:Lemma 20 (Bousquet et al. [2021] Theorem 3.1, the first bullet). If H does not have an infinite Littestone tree, then there is a strategy for the learner that makes only finitely many mistakes against any adversary. Notice that the online learning algorithm derived from the winning strategy of the learner only makes finite mistakes against any adversary, so for every realizable data process (X, Y), this online learning algorithm also only makes finite mistakes, which means the long-run average mistake bound goes to 0. Thus, this is an optimistically universal online learning rule, and the concept class H which does not have an infinite Littlestone tree is optimistically universally online learnable.The necessity is restated as the following theorem:Theorem 21. For any concept class H with an infinite Littlestone tree, for any online learning algorithm A, there exists a process X that makes A have an average loss greater than a half with non-zero probability.Proof Sketch. We can take a random walk on the infinite Littlestone tree to generate the target function. Thus, no matter what the algorithm predicts, it makes a mistake with a probability of more than half. Then we can use Fatou's lemma to get a lower bound of the expected average loss of the learning algorithm among all random processes and that means for every algorithm there exists a process that makes its average loss more than a half with probability more than zero. 
concept classes with an infinite vcl tree: 
 In this section, we discuss the necessary and sufficient conditions for a process to admit universal online learning under the concept class H with an infinite VCL tree. Theorem 11 states the answer formally. To prove this theorem, we first prove sufficiency (Lemma 22) and then necessity (Lemma 23).Lemma 22. If a process X satisfies condition A, it admits universally consistent online learning under concept class H.Proof Sketch. To prove this lemma, we use the weighted majority algorithm with non-uniform initial weights on the experts defined in condition A. The initial weight of expert i is 1 i(i+1) , where the index i is the index defined in condition A as well.Lemma 23. If a process X admits universally consistent online learning under concept class H, it satisfies condition A.Proof Sketch. In order to prove this lemma, we need to show the following statement holds: For a given concept class H, and a data process X, if there is a learning algorithm A that is strongly universal consistent under X and H, then we have a set of experts E = {e 1 , e 2 , . . . }, there is a sequence {i n } with log i n = o(n), such that for any realizable sequence (X, Y), for any n ∈ N, there is an expert e i with i ≤ i n such that Y t = e i (X t ) for every t ≤ n.We modify the construction from the work of Ben-David et al. [2009] to build the experts. We build the experts based on the set of the index of the round when the algorithm A makes mistakes, so there is a one-on-one map from the set of the index of the mistakes to the experts. Then we can build the index of the experts based on the set of the index of mistakes to show the existence of such a sequence.Then we can get the theorem for optimistically universal online learnability, which is theorem 12. Notice that the proof of lemma 23 and 22 works for any process. We can prove theorem 12 by reusing the proof of theorem 11Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: This is a learning theory paper. There is no code or data related to this paper. Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
agnostic case: 
 In this section, we extend the online learning algorithm for realizable cases to an online learning algorithm for agnostic cases. The basic idea follows the idea of Ben-David et al. [2009] . In other words, we build an expert for each realizable process (X, Y). Then we run the learning with experts' advice algorithm on those experts and get a low regret learning algorithm.Theorem 24. The following two statements are equivalent:• There is an online learning rule that is strongly universally consistent under X and H for the realizable case.• There is an online learning rule that is strongly universally consistent under X and H for the agnostic case. Proof Sketch. To prove this lemma, we first build the experts e i based on the learning algorithm for the realizable case by using the construction from lemma 23. We then use the learning on experts' advice algorithm called Squint from Koolen and van Erven [2015] , with non-uniform initial weights 1 i(i+1) for each e i to get a sublinear regret. Thus, we can extend the learning algorithm for realizable cases to a learning algorithm for agnostic cases no matter how the algorithm operates.An online learning algorithm for the agnostic case is also an online learning algorithm for the realizable case, by taking Y * = Y, the regret becomes the number of mistakes. Thus, the two statements are equivalent.Theorem 24 implies all the characterization for the realizable case is also a characterization for the agnostic case. We formally state the theorems below: Theorem 25. For the agnostic case and any concept class H with no infinite VCL tree, any process X admits strongly universal online learning under H. However, only the concept class with no infinite Littlestone tree is optimistically universally online learnable.For the concept class H with infinite VCL tree: Theorem 26. For the agnostic case, a data process X admits strongly universal online learning under concept class H with infinite VCL tree if and only if it satisfies condition A. However, a concept class H with infinite VCL tree is optimistically universally online learnable if and only if it satisfies condition B.In order to help the reader understand, we provide the subroutine here again for reference.Algorithm 2: Subroutine for learning a partial concept class H with VC dimension d on the data process X.L ← ∅. m ← 1. for t = 1, 2, 3, . . . do Predict Ŷt = argmax y Pr w(H g U L∪(Xt,1-y) , X t<i≤ m(m+1) 2 ) ≤ 1 2 w(H g U L , X t≤i≤ m(m+1) 2 ) X ≤t if Y t ̸ = Ŷt then L ← L ∪ {(X t , Y t )}. end if t ≥ m(m+1) 2 . then m ← m + 1. end endProof. In this proof, we assume that for the partial concept class H with VC dimension ≤ d, {(x i , y i )} i∈N is realizable. As we defined, the weight function, w(H ′ , X ≤T ) = |{S : S ⊆ {x i } i≤T such that S shattered by H ′ }|, which is the number of the subsequences of the sequence X ≤T that can be shattered by the partial concept class H ′ .Consider the k-th batch, consisting ofW k = {X k(k-1) 2 +1 , • • • , X k(k+1) 2 }. Let Z k = k(k+1) 2 t= k(k-1) 2 +1 I Ŷt ̸ = Y t ,andV k = Z k -E Z k X ≤ k(k-1) 2 .Notice thatE V k X ≤ k(k-1) 2 = E Z k -E Z k X ≤ k(k-1) 2 X ≤ k(k-1) 2 = E Z k X ≤ k(k-1) 2 -E Z k X ≤ k(k-1) 2 = 0.(a.s.)Thus, the sequence V k is a martingale difference sequence with respect to the block sequence,W 1 , W 2 , • • • . By the definition of V k , we also have -k ≤ V k ≤ k.Then by Azuma's Inequality, with probability 1 -1 K 2 , we haveK k=1 Z k ≤ K k=1 E Z k X ≤ k(k-1) 2 + -log 1 K 2 • 2 • K k=1 k 2 ≤ K k=1 E Z k X ≤ k(k-1) 2 + 4K 3 log K.Then we need to get an upper bound for E Z k X ≤ k(k-1). According to the prediction rule, every time we make a mistake, we havePr w(H g U L∪(Xt,Yt) , X t≤i≤ m(m+1) 2 ) ≤ 1 2 w(H g U L , X t≤i≤ m(m+1) 2 ) X ≤t ≥ 1 2 . (3)Due to the linearity of expectation, for every k,E    k(k+1) 2 t= k(k-1) 2 I Ŷt ̸ = Y t X ≤ k(k-1) 2    = E    k(k+1) 2 t= k(k-1) 2 I Ŷt ̸ = Y t I w(H Lt , X t<i≤ k(k+1) 2 ) ≤ 1 2 w(H Lt-1 , X t≤i≤ k(k+1) 2 ) X ≤ k(k-1) 2    + E    k(k+1) 2 t= k(k-1) 2 I Ŷt ̸ = Y t I w(H Lt , X t<i≤ k(k+1) 2 ) > 1 2 w(H Lt-1 , X t≤i≤ k(k+1) 2 ) X ≤ k(k-1) 2    .Here L t = {(X i , Y i )}, where i ≤ t and the algorithm makes a mistake at round i.Notice the first part is the expected number of mistakes, each of which decreases the weight by half.For every realization of X k(k-1)2 ≤i≤ k(k+1) 2 , x k(k-1) 2 ≤i≤ k(k+1) 2 , let u(k) = k(k+1) 2 i= k(k-1) 2 I Ŷt ̸ = Y t I w(H Lt , x t<i≤ k(k+1) 2 ) ≤ 1 2 w(H Lt-1 , x t≤i≤ k(k+1)) .By the definition of the weight function and the fact thatVC(H) = d, w(H L k(k-1) 2 , x k(k-1) 2 ≤i≤ k(k+1) 2 ) ≤ k d . Consider the last round t ≤ k(k+1) 2 that Ŷt ̸ = Y t ,we have w(H Lt-1,x t≤i≤ k(k+1) 2) ≥ 1, as the set {x t } must be shattered. Thus, we haveEQUATION). Therefore, u(k) ≤ d log T + 1, for every realization, x k(k-1)2 ≤i≤ k(k+1) 2. Thus,EQUATIONThen consider the second part, we haveE    k(k+1) 2 t= k(k-1) 2 I Ŷt ̸ = Y t I w(H Lt , X t<i≤ k(k+1) 2 ) > 1 2 w(H Lt-1 , X t≤i≤ k(k+1) 2 ) X ≤ k(k-1) 2    = E   E    k(k+1) 2 t= k(k-1) 2 I Ŷt ̸ = Y t I w(H Lt , X t<i≤ k(k+1) 2 ) > 1 2 w(H Lt-1 , X t≤i≤ k(k+1) 2 ) X ≤t    X ≤ k(k-1) 2    = E    k(k+1) 2 t= k(k-1) 2 I Ŷt ̸ = Y t E I w(H Lt , X t<i≤ k(k+1) 2 ) > 1 2 w(H Lt-1 , X t≤i≤ k(k+1) 2 ) X ≤t X ≤ k(k-1) 2   This is because Ŷt and Y t only depend on X ≤t . Due to the equation 3, we haveI Ŷt ̸ = Y t E I w(H Lt , X t<i≤ k(k+1) 2 ) > 1 2 w(H Lt-1 , X t≤i≤ k(k+1) 2 ) X ≤t = I Ŷt ̸ = Y t Pr w(H Lt , X t<i≤ k(k+1) 2 ) > 1 2 w(H Lt-1 , X t≤i≤ k(k+1) 2 ) X ≤t ≤ 1 2 I Ŷt ̸ = Y t .Thus,E    k(k+1) 2 t= k(k-1) 2 I Ŷt ̸ = Y t I w(H Lt , X t<i≤ k(k+1) 2 ) > 1 2 w(H Lt-1 , X t≤i≤ k(k+1) 2 ) X ≤ k(k-1) 2    (5) ≤ 1 2 E    k(k+1) 2 t= k(k-1) 2 I Ŷt ̸ = Y t X ≤ k(k-1) 2   Combining these two inequalities (4 and 5), we haveE    k(k+1) 2 t= k(k-1) 2 I Ŷt ̸ = Y t X ≤ k(k-1) 2    ≤ 2d log k + 1 2 E    k(k+1) 2 t= k(k-1) 2 I Ŷt ̸ = Y t X ≤ k(k-1) 2    . (6)Thus, for any k, we haveEQUATIONAccording to the inequality 7 for every k, E Z k X ≤ k(k-1)≤ 4d log k. Thus, with probability atleast 1 -1 K 2 , K k=1 Z k ≤ K k=1 4d log k + 4K 3 log K ≤ 4dK log K + 4K 3 log K.By the definition of Z k , with probability at least 1EQUATION) Let T K = K(K+1)2 be the number of instances in the sequence, with probability at least 1 -1EQUATION)Define the event E K as the event that in the sequence X ≤T K ,T K t=1 I Ŷt ̸ = Y t > (4d + 2)T 3 4 K 1 2 log T K . Then we know Pr[E K ] ≤ 1 K 2 . Notice the fact that for any K ∈ N, K k=1 1 k 2 ≤ π 2 6. By Borel-Cantelli lemma, we know that for anyT K = K(K+1) 2 large enough, T K t=1 I Ŷt ̸ = Y t ≤ (4d + 2)T 3 4K 1 2 log T K happens with probability 1. Then for any large enough T , we have T K ≤ T ≤ T K+1 ≤ 2T . Thus, with probability 1,EQUATION)Therefore, for any large enough T and a universal constant c, with probability 1,EQUATION)Notice that cT3 4 √ log T is o(T ).That finishes the proof.Proof. In this proof, we want first to modify the chosen indifferent VCL tree, such that the number of elements in each node is increasing exponentially. In other words, we hope the k-th node in the Breadth-First-Search (BFS) order contains 2 k-1 elements. We may reach this target by recursively modifying the chosen VCL tree. Starting from the root of the tree, for each node that does not satisfy our requirement, we promote one of its descendants to replace that node, such that the number of elements in that node is large enough.Then we define the data process as follows: For the modified VCL tree, we define the sequence {X i } i∈N as X 2 k-1 +j = X jk , where X jk is the j-th element in the k-th node in the BFS order.Next, we define the target function, in other words, choose the label Y t for each X t . First, we take a random walk in the modified VCL tree. Then for the elements in the node on the path we visited (in-branch node), we let Y t be the label given by the edge adjacent to that node. Then, we need to decide the label of those elements in the node not on the path we visited (off-branch nodes). For any off-branch node, we can pick an in-branch node after it in BFS order, as the tree is indifferent, all descendants of the in-branch node agree on the label of the elements in the off-branch node. Thus, we can let the label of the elements in the off-branch node be the label decided by the descendant of that in-branch node. So, every element in the node that is visited by the random walk still may be wrong with probability 1 2 , when the algorithm sees it the first time. Also, the number of elements that come before k-th node in the BFS order, k-2 i=0 2 i = 2 k-1 -1, is roughly the same as the number of elements in the k-th node, 2 k-1 . Thus at the d-th layer of the modified tree, if the random walk reaches the node K d , for that node, we haveEQUATION)Here n K d is the number of elements in the process when we reach the K d -th node. This inequality holds for all d.Then notice that by taking an expectation on the expected mistakes for every deterministic sequence, we get an expectation of the number of mistakes for this random process. Then we can pick the sub-sequence, which only contains n K d = 2 K d -1 elements, and this decreases the ratio of mistakes (the third line in the following computations). This is because we can only make mistakes when the elements are in the K d -th node and any other n will have a smaller ratio of mistakes than n K d . Then notice that the ratio of mistakes is always smaller than or equal to 1, we can use the reversed Fatou's lemma and inequality 13 to get the final result (the fourth line and the last line in the following computations).E E lim sup n→∞ 1 n n t=1 I [h t-1 (X t ) ̸ = Y t ] (X, Y) = E lim sup n→∞ 1 n n t=1 I [h t-1 (X t ) ̸ = Y t ] ≥ E lim sup d→∞ 1 n K d n K d t=1 I [h t-1 (X t ) ̸ = Y t ] ≥ E lim sup d→∞ E 1 n K d n K d t=1 I [h t-1 (X t ) ̸ = Y t ] n K d ≥ 1 4 .Thus, there exists a deterministic sequence (X, Y) such that it does not make sublinear expected mistakes.Proof. As H has an infinite Littlestone tree, we can take a random walk on this tree, then for every step t, take the label of the node as X t , and no matter what the learning algorithm predicts, uniformly randomly choose Y t . Thus, we haveEQUATION)According to Fatou's lemma, notice the ratio of mistakes is smaller than or equal to 1, so we have the following inequality,EQUATION)Thus, for each learning algorithm, there exists a data sequence {(X t , Y t )} t∈N such that equation 15 holds. That finishes the proof.For the completeness, we provide the weighted majority algorithm here:Algorithm 3: The Weighted Majority Algorithm with Non-uniform Initial WeightsFor expert e i , assign w 0 i = 1 i(i+1) as its initial weight. for t = 1,2,. . . doPredict y t = I i w t-1 i i w t-1 i e i (X t ) ≥ 1 2 . Update w t i = 1 2 I[ei(Xt)̸ =Yt] w t-1 i . endBy using this algorithm, we provide the proof of the lemma 22.Proof. In order to prove this lemma, we use the weighted majority algorithm 3 with initial weightw 0 i = 1 i(i+1) for each expert i. We set MB = n t=1 I [h t-1 (X t ) ̸ = Y t ],which is the number of mistakes the algorithm made during n rounds. We also setm i = n t=1 I [e i (X t ) ̸ = Y t ].Next, compute the total weight of all experts after n rounds of the algorithm, W n . Notice that if the algorithm makes a mistake at round n, there must be a majority of the experts making a mistake at round n, soW n-1 -W n ≥ 1 2 • 1 2 W n-1 , which means W n ≤ 3 4 W n-1 . Thus, we have W n ≤ 3 4 MB W 0 ≤ 3 4 MB . Notice that W n ≥ w n i for all i, so it holds for argmin i≤in n t=1 I [e i (X t ) ̸ = Y t ].We have the following inequality for all n,EQUATIONHere 3 comes from the fact that log 2 log( 43 ) ≤ 3. Therefore, for a fixed process X, target function h * and a fixed sequence, {i n }, we haveE lim sup n→∞ 1 n n t=1 I [h t-1 (X t ) ̸ = Y t ] ≤ E lim sup n→∞ 1 n 3 min i≤in n t=1 I [e i (X t ) ̸ = Y t ] + 2 log i n .(18) Then by the condition A, we know the right-hand side of the inequality is 0.Notice that lim sup n→∞1 n n t=1 I [h t-1 (X t ) ̸ = Y t ]is a non-negative random variable, so we haveEQUATIONTherefore, lim sup n→∞1 n n t=1 I [h t-1 (X t ) ̸ = Y t ] = 0 almost surely.Algorithm 4:Expert J Input: set J for t = 1,2,. . . do recieve X t . compute ỹt = f A t (X i<t , Ŷi<t , X t ). a if t ∈ J then predict ŷt = ¬ ỹt else predict ŷt = ỹt end end a Ŷi<t = { ŷi}i<tProof. In this proof, we show that there is a way to build a sequence of experts {e 1 , e 2 , . . . }, such that those experts satisfy the condition A, from the fact that X admits strongly universally consistent online learning. Let an online learning algorithm A and the related online learning rule f A t be the algorithm that can learn all realizable label process Y ∈ R(H, X), with o(n) errors. Then we can build the experts by algorithm 4 and represent the experts by the set of the index of mistake rounds. We can define this set as set J. For example, if the algorithm makes mistakes at round 1, 4, 7 then the set J for that expert is {1, 4, 7}. Thus we have a one-on-one map from the set J to the expert.First, we show that for every realizable label process Y ∈ R(H, X), there is an expert predicting the same as that process. This part of the proof is similar to the proof of lemma 12 in the work of Ben-David et al. [2009] . Consider a realizable label process Y and run algorithm A on (X, Y), j ∈ J if and only if A makes a mistake on (X, Y) in round j. Then consider the algorithm 4 running on X, as for each round t, the history A see is the same as (X, Y). So the original prediction of that algorithm ỹt ̸ = Y t , if and only if t ∈ J. For those rounds, the expert predicts the opposite of ỹt , which is equal to Y t . For any n ∈ N, there is a set J n containing all of the index of the mistake rounds of A running on (X ≤n , Y ≤n ). Then the algorithm 4 with input J n creates an expert e i , such that e i (X t ) = Y t for all t ≤ n.Next, we only need to build the index i n for the set J n to show that log i n = o(n). The index of set J is as follows: order all sets J by |J|(max J). (If two sets have the same value, then use |J| as a tie-breaking.) Here |J| is the number of elements in J and max J is the maximal element in J. After that, index the set J from 1 following this order.At last, we show the method mentioned above constructed a set of experts satisfying condition A. we have a set of experts E = {e 1 , e 2 , . . . }, there is a sequence {i n } with log i n = o(n), such that for any realizable sequence (X, Y), for any n ∈ N, there is an expert e i with i ≤ i n such that Y t = e i (X t ) for every t ≤ n. Therefore, we need to compute the i n as follows. Assume |J in | max J in = k, we havei n ≤ |{J : |J| max J ≤ k}| = 1 + k m=1 |{J : |J| ≤ k m , max J = m}| = 1 + √ k m=1 2 m-1 + k m= √ k m -1 ≤ ( k m -1) ≤ 2 √ k + k m= √ k em 2 k k m ≤ (k + 1)e √ k .Notice that k = |J in |n, we haveEQUATIONThus, we get the set of experts and the corresponding sequence {i n } satisfying condition A.Proof. In order to prove this theorem, we use the procedure based on learning with experts' advice. First, we build and index the experts, {e 1 , e 2 , • • • }. By using the same method we mentioned in the proof of lemma 23 (A.5), we can build and index the experts based on the learning algorithm for the realizable case. And this satisfies Condition A. Then, we can use Squint algorithm from the work of Koolen and van Erven [2015] . To use Squint, we need the initial weight of the experts to be a distribution. We can set the initial weights π i = 1 i(i+1) for each e i and this forms a distribution, as π i = 1 i -1 i+1 , the sum of π i reaches 1 when i goes to infinity. According to Theorem 3 in the work of Koolen and van Erven [2015] , we have the following upper bound for the regretEQUATIONHere the V k is the sum of the square of the difference between the algorithm's mistake and expert k's mistake in each round. In other words, we haveEQUATION) Notice that (I [h t-1 (X t ) ̸ = Y t ] -I [e k (X t ) ̸ = Y t ])2 is either 1 or 0, we have V k ≤ T . The regret of this algorithm is upper bounded by:EQUATION)According to the condition A, we also knowEQUATIONThus, the regret of this algorithm is lim supT →∞ 1 T T t=1 I Y t ̸ = ĥt-1 (X t ) -I [Y t ̸ = Y * t ] = lim sup T →∞ 1 T T t=1 I Y t ̸ = ĥt-1 (X t ) -|I [Y t ̸ = e k (X t )] -I [e k (X t ) ̸ = Y * t ]| ≤ lim sup T →∞ 1 T T t=1 I Y t ̸ = ĥt-1 (X t ) -I [Y t ̸ = e k (X t )] + I [e k (X t ) ̸ = Y * t ]≤ lim supT →∞ 1 T T t=1 I Y t ̸ = ĥt-1 (X t ) -I [Y t ̸ = e k (X t )] + lim sup T →∞ 1 T T t=1 I [e k (X t ) ̸ = Y * t ]Because log i T = o(T ) and log k < log i T we have log k = o(T ). Thus, the regret above is o(T ). Therefore, we have an algorithm to extend a universally consistent online learning algorithm for realizable cases to a universally consistent online algorithm for agnostic cases.To prove the necessity, notice that a universally consistent online algorithm for agnostic cases can be used to solve the realizable case and the regret is equal to the number of mistakes.• 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 a dataset and/or model, the authors should describe the steps taken to 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 is a specific model and empirical evaluation, it 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 is 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 a 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (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.In the case of closed-source models, it 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] Justification: This is a learning theory paper. There is no experiment in this paper.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA] Justification: This is a learning theory paper. There is no experiment in this paper.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence 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 run 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 or 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 2-sigma error bar than state that they have a 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [NA] Justification: This is a learning theory paper. There is no experiment in this paper.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or 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 make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We are sure we conform with the NeurIPS Code of Ethics. This paper does not contain any experiments and all of the proofs have been provided in the appendix or cited appropriately.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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a learning theory paper. We are discussing the learnability of the learning model, which is not directly related to any application.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.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 out 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 as 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 or 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This is a learning theory paper and does not release any data or models. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for 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 a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: This is a learning theory paper with no experiments or code. 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 a 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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: This is a learning theory paper. There are no new assets introduced. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model 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 is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.We additionally make standard restrictions on H to ensure certain estimators are well-behaved; we omit the details for brevity, but refer the reader toBousquet et al. [2021] for a thorough treatment of measurability of these estimators.ExamplesIn this section, we provide some interesting examples to help the reader get a sense of what these conditions are. We first provide an example of the concept class that is universally online learnable under all processes but not optimistically universally online learnable. 
 
 Appendix:  


Decision: This work studies online learning under general stochastic processes (instead of the more common iid or adversarial settings) with binary labels continuing the line of work by Hanneke [2021]. While previous papers focused on the case of all measurable functions, this current work gives characterization for arbitrary hypothesis spaces. At a technical level the problem is a natural generalization of well-studied settings and the results are a significant progress. At the same time it is rather theoretical even by the standards of ML theory. In addition, the presentation is terse and hard to read even for experts on online learning. Still I think that the strengths of the results compensate for the limitations and recommend acceptance

Reviews: review: paper_summary: paper_summary: This work continues the line of work by Hanneke and Blanchard et al universal online learning under general stochastic processes (instead of the more common iid or adversarial settings) with binary labels. While previous papers focused on the case of all measurable functions (as an implicit hypothesis spaces), this current work gives characterization for arbitrary hypothesis spaces.

The two main characterizations are as follows. Fix hypothesis space $H$.
1. For any data generating process $X$ there exists some algorithm that "learns" (i.e., average regret goes to $0$) on $X$ iff $H$ has no infinite VCL tree (a combinatorial dimension like VC used in universal learning).
2. For any data generating process $X$ there exists some algorithm that learns on $X$ and there exists a single algorithm that learns under any data process "under which learning is possible" iff it has no infinite Littlestone tree (a standard combinatorial dimension, characterizing online learning).

By the first chracterization, the existence of an infinite VCL tree just admits, thus, some data processes where learning fails, but it's unclear if learning still is possible on different specific processes. To tackle this, the authors offered an additional more fine-grained condition for each fixed (unlabeled) stochastic process $X$ (for the case the $H$ has infinite VCL trees):
1. $X$ is learnable iff a countable set of experts exist (which can depend on $X$) that satisfy a certain no-regret condition.
2. there is a single algorithm that learns "whenever learning is possible" (i.e., for any process that admits learning) iff there exists a countable set of experts (with no dependents on $X$) that satisfy the no regret condition for all processes $X$ that admit learning.

Both of these conditions collapse to a previously studied condition if $H$ is the set of all measurable functions.
strength_weakness: strength_weakness: The paper lacks a bit of exposition to guide the reader and a more thorough discussion of related work.
questions: questions: The paper only seems to discuss qualitative statements (learning possible iff no infinite tree,...). As far as I can see no quantitative rates are provided (like in uniform/universal learning). Are such rates, even very loose ones, possible (perhaps as future work)?
limitations: limitations: See questions.
paper_summary: paper_summary: This paper considers characterizations for optimistically universal online learnability, a notion that refers to the existence of learning rules that are simultaneously optimal for any data-generating process that satisfies some minimal assumptions, i.e. admitting an optimal process-dependent learning rule. Previous works have studied this notion of learnability when the function being learned can be any measurable function, a very broad class of functions. In this paper, the authors consider characterizations of learnability when the labels of the samples are  realizable some known binary hypothesis class H, and also consider the agnostic task of achieving low regret with respect to the best hypothesis in H. They give characterizations of when H will be optimistically learnable based on VCL and Littlestone trees as well as some additional assumptions in certain cases. They provide clear examples to illustrate these characterizations.
strength_weakness: strength_weakness: I found some of the notation, especially around VCL trees and games, extremely difficult to parse. For instance, it was confusing that a large X may refer to either a tuple of X-values, or just a single X value. It would be great if this could be made more readable.
questions: questions: - Do these results/techniques have any implication for optimistic online learning beyond the binary-label setting?
limitations: limitations: The authors have adequately address the limitations and assumptions made in their results.
paper_summary: paper_summary: This work considers the theory of universal consistency and optimistically universal learning rules in the binary classification case where, instead of considering all measurable target functions, the analysis is parameterized by a specific class $\mathcal{H}$ of binary classifiers. Two types of classes $\mathcal{H}$ are considered:

Strongly universal: for every $\mathcal{H}$-realizable process $\mathbb{X}$ there is a strongly universally consistent online learning algorithm for $\mathcal{H}$ and $\mathbb{X}$.

Optimistically universal: there is an online learning algorithm that is strongly universally consistent for $\mathcal{H}$ and $\mathbb{X}$ for every $\mathcal{H}$-realizable process $\mathbb{X}$.

The main results of this work (as far as I understand) are the following:

$\mathcal{H}$ is strongly universal if and only if it has no infinite VCL tree (Theorem 9).

$\mathcal{H}$ is optimistically universal if and only if it has no infinite Littlestone tree (Theorem 10).

Recall that $\mathcal{H}$ has no infinite Littlestone trees implies $\mathcal{H}$ has no infinite VCL tree.

Further results extends this characterization to the agnostic case.
strength_weakness: strength_weakness: The clarity of the presentation is below the NeurIPS standards.
questions: questions: Please elaborate on the connections between this work and Section 3 of arxiv.org/pdf/2011.04483.

Please clarify the apparent inconsistency in the Theorems 9, 10, and 12.

[The above questions have been addressed in the rebuttal]
limitations: limitations: There is no section on limitations, but the work is purely theoretical with no foreseeable societal impact.

Comments: comment: This is a strong and important paper. I think it should be accepted and hence I increase my score.
Thank you for the clarification. I now better understand that: For classes that have an infinite VCL tree, the property of being an optimistically universal learner only requires the learner to be universally consistent under all processes which admit a universally consistent online learner. This resolves the apparent contradiction I had mentioned in my original review. As a consequence, I have increased my score. However, my reservation about the quality of the presentation remains.
Thanks for your reply and answers to my questions! I will keep my score as-is.