A Theory of Optimistically Universal Online Learnability for General Concept Classes
Authors: Steve Hanneke
Hongao Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Learning
Statistical Learning
Consistency
Primary area: learning_theory
TL;DR: We provide a full characterization of the concept classes that are optimistically universally online learnable with {0, 1} labels.

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.

A Theory of Optimistically Universal Online Learnability for General Concept Classes
Steve Hanneke
Hongao Wang
Department of Computer Science Purdue University
Department of Computer Science
Purdue University
West Lafayette, IN 47907
West Lafayette, IN 47907
steve. hanneeeeehnne com
wargg2270ppurdue edu
Abstract
We provide a full characterization of the concept classes that are optimistically uni- versally 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 the data process admitting online learnability? (2) Is there a learning algorithm which succeeds under every data process satisfying the minimal assumptions? Such algorithm is said 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 Icarnability in the agnostic and realizable cases, for every concept class, as well as the equivalence of optimistically universal learnability.
Introduction
Just as computability a core question in computation theory, learnability now 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 [Vaiiant (1984), online learning (Littlestone and Warmuth (1986]) and query learning (Angluin (1988). ). In this paper, we focus on variant of online learning: online learning under data processes.
this setting, the learning sequential: round an instance X, is given to the algorithm, and then the algorithm makes the prediction, Yú based on the history (X Yge-1) and the input X,, i.e., Y, = f.( Y: Next, the target value Y, will be revealed to the learner such that it can be used inform future predictions. We model this sequence as a general stochastic process (X, Y) {(X,, Yt) (possibly with dependencies across times t). We say that the algorithm strongly consistent under (X, V) if the long-run average error is
guaranteed to be low, i.c., Di I
Y + Yı
almost surely, when +
In our setting, any theory of learning must be expressed based on the properties of, or restriction on, the data process, 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 C ya 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.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

If there is a target function h E Hi such that Y, = (X), for every t, we say the data process (X, Y) 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 universally consistent under 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. [2099] studied online learning with unrestricted data processes but restricted concept classes. Haussler et al. [1994). |yyaboo [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 11777. Devroye 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, 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 possible under X? The assumption that universal consistency is possible under X is referred to as the "optimist's 's assumption" [Hanneke| [0221] and for this reason, learning rules which are universally consistent for all X satisfying the optimist's 'ss assumption are said to be optimistically universally consistent. There is 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., 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.c. {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 optimistically universally consistent learning possible?
What the sufficient and necessary conditions for processes admit universally consistent online learning for given concept class H?
For which concept classes the case that all processes admit universally consistent online learning?
We first answer these questions in the realizable case. Surprisingly. the answers turn out to be intimately related to combinatorial structures arising in the work of Bousquet et al. [202]] 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.
In this paper, we first provide some interesting examples in section 3 Then section f investigates question three and question one for those classes and section 5 answers question two and question one for remaining classes. Finally, in section we extend our algorithm to the agnostic case.
1.1 More Related Work
Starting from Littlestone's
work [Littlestone] 1988), online learning is becoming more and more important. In this paper, [ittlestone [1988] introduces a combinatorial parameter
of the concept class, known as Littlestone dimension, to characterize the online learnable concept classes the realizable case. After that, [Ben-David et al. [2009] figure out Littlestone dimension still the property to characterize online learnability in the agnostic setting. They extend an online

---

learning algorithm for the realizable case to such an algorithm for the agnostic case using the weighted majority algorithm from Littlestone and Warmuth [1994]. This line of work makes no assumption on the data process and investigates how 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 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 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.idd. and the concept class has finite VC dimension. AAdass and Nobel [0000] 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. sequence (X. Y). and every measurable function f", the long-run average loss is 0 almost surely, such as, [Stone 1977 Devroye et al., 1996. Haanekke et al. 202T]. T.. In the meanwhile, people are also interested in the consistency under non-i.i.d. processes; Gyorf et al. [1999). Morvai et al. [1996] reveal that there are universally consistent online learning rules under general stationary ergodic processes. The paper of Morvai et al. [199]] and the paper of (Steinwart et al. (2009) show universal consistency under some classes of processes satisfying laws of large numbers.
More recently, the work of Hanneke [202T] investigates whether there is 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 the "optimist's assumption", so the consistency under that assumption called optimistically universal consistency. [Hanneke| [002] studies three different learning models: inductive, self- self-adaptive, and online, and proves that there 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. [0022a], [Blanchard] [2022) show that optimistically universal online learning is possible and the processes that admit strongly universal online learning satisfy the condition called C2 (see condition C for reference). This problem is also investigated under different models, such as, in contextual bandit
setting Blanchard et al. 22022b 2023 and general noisy labels Blanchard and Jaillet 22233]
2 Preliminaries and Main Results
In this section, we provide formal definitions and model settings 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.
Model Setting We formally provide the learning model here. Let (X, B)) be a measurable space, in which X' assumed to be non-empty and B is Borel o-algebra generated by a separable metrizable topology T. We also define a space y {O.1) 1} called label space. Here we focus on learning under the 0-1 loss: that is. (g. ( + [y * y'] defined on y x V, where [.] is the indicator function. A stochastic process X = (Xthen is a sequence of X'valued random variables. A stochastic process W = (Vr) is a sequence of (0, 1]-valued random variable. The concept class H. which is a non-empty set of measurable functions h X + y
The online learning rule is a sequence of measurable functions: fc : x ) X ), where t is a non non-negative integer. For convenience, we also define h1 fo Y2t), here (Xer, Yz.) = (X,,, Hi) is the history before round t.
We additionally make standard restrictions on 7/ to ensure certain estimators are well well-behaved; we omit the details for brevity, but refer the reader to Bousquet et al. [021] for thorough treatment of measurability of these estimators.
3

---

There are two ways to define the realizable case: The most common one is that there exists ht E H such that Y, = h (X,). The other is the definition 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.
Definition 1. For every concept class H. we can define the following set of processes R(H):
R(H) = (x, 2) - ((,,, Yi) with probability 1, Vn < oo, Yo))(( realizable by H
In the same way, the set of realizable label processes: Definition 2. For every concept class H. and data process X. define a set R(H, of label processes:
R(H,X) ( (Yihen (X R(H) and 3 non-random function f s.t. Y, f(X)))
In other words, R X) are label processes Y = (X) s.t. (x)) E R(H).
Importantly, while every f E H satisfies f(X) E R(H, X), there can exist f & H for which this is also true, due to R R(H) only requiring realizable prefixes (thus, in a sense, (H, X) represents label sequences by functions in closure of H defined by ]
At first, we define the universal consistency under 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 I Y. + hx-1(X)) = a.s.
realizable case, for every? Y E R(H, X), lim sup, E.
We also define the universal consistency under X and H. for the agnostic case. In that definition, we release the restrictions that Y E R(H, X). instead the label process Y can be set in any possible way, even dependent on the history of the algorithm's 's predictions. Thus, the average loss may be linear and inappropriate for defining consistency. Therefore, with the performance of the best possible Y E RHH, X), which is usually referred to as 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,
compare the performance of our algorithm
Definition 4. An online learning rule is strongly universally consistent under X and H for the agnostic case, if for every 4 +R(H,X) X) and for every V, limsup 1 Dr (I[Y: & he-1(Xi) - -[ xr)) <0
To describe the assumption that universal consistency is possible under the data process X and the concept class H. we need to define the process admitting universal online learning as follows:
Definition 5. We say a process admits strongly universal online learning (or just universal online learning for convenience) if there exists online learning rule that is strongly universally consistent under X and H.
If the online learning rule is universally consistent under every process that admits universal online learning, we call it optimistically universal under the concept class. If there is an optimistically universal learning algorithm under that concept class, we say that concept class is optimistically universally online learnable. The formal definition is provided below:
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.
Definition 6.
there an online learning rule that is optimistically universal under concept class H. we say H is optimistically universally online learnable.
For instance, for X = N. for the process X; = i, and for H. = {1(0) E X3 (singletons), the all-O sequence in R(H, X) though the all-O function is not in H.

---

Next, we define the combinatorial structures we use to characterize the concept class that makes all processes admit universal online learning and is optimistically universally online learnable when all processes admit strongly universally consistent online learning:
Definition 7 (Littlestone tree Bousquet et al. (021). A Littlestone Tree for H is a complete binary tree of depth d I oc whose internal nodes are labeled by X, and whose two edges connecting node to its children are labeled O and 1, such that every finite path emanating from the root is consistent H. We say that has an infinite Littlestone tree if has Littlestone tree of
with a concept depth d
Definition 8 (VCL Tree Bousquet et al. 202
A VCL Tree for H of depth d S co is a collection
(Ir E x :0 k < <, E (0.1)' x {0,1)²
x {0, 1}3}
such that for every n < d and E {0.1)' x {0, 1)2 x .... x {0, 10 there exists a concept h E H. so that h(r) y for all 0 Si i and 0 S k S n,, where denote
(vi (92, 42)
.y...... 1/ 1)))))); Tyex (Zgge...... Uga
Ugk
We say that H has an infinite VCL tree if it has a VCL tree of depth d = 00.
The characterization is formally stated in the following two theorems:
Theorem 9. If and only if concept class H has no infinite VCL tree, any process admits strongly universally consistent online learning under H.
Theorem 10. If and only if concept class H has 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 we know that for those concept classes with an 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.
First, we define the experts as algorithms that generate predictions only based on the input X,, Then we define the following condition (which is property of a data process) and state the main theorem formally:
Condition A. For given concept class H. there exists a countable set of experts E {E1, e..... such that VY² E R(H, Bi + co, with log in o(n), such that:
II)( Yi1 =0
E lim min n- GAS TI
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:
Condition B. There exists countable set of experts E = fei, e2.... }. such that for any X admits universal online learning, and any Y E R(H, X). there exists i, - oo, with log in = on)) such that:
E lim a
min 2=000 GA
1
Σ I (x,, + Y;' =0
(2)
Notice that these two conditions (condition A and B only have one major difference: whether the countable set of experts depends the process X.
Theorem 12. A concept class H with infinite VCL tree 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.
5

---

3 Examples
In this section, we provide some interesting examples to help the reader get sense of what these conditions are. We first provide example of the concept class that is universally online learnable under all processes but not optimistically universally online learnable.
Example 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, Hahreshodd {ha -ha ha(x)) - 2 a] la E R). This concept class has no infinite VCL tree, as there is no (x1, such that Hehreshold shatters all possible results. Thus, all processes admit strongly universally consistent online learning under Hahreshold- 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 optimistically universally online learnable. The sufficient and necessary condition for processes to admit universal online learning under all measurable functions the condition C2 (see below). In the meanwhile, our conditions: A and B vanish C2 when the concept class H becomes the class of all measurable functions,
Condition C (C2 in Hanneke [2021]). For every sequence { disjoint elements of B,
1[k E N: X n Ax * 03 = o(T) a.8.
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 concept class optimistically universally online learnable will be sufficient and necessary to determine whether its subset is optimistically universally online learnable, 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' = X1 U X2 and here X1 and X2 are disjoint. For example, Xi = R2 and X₂ = IR' +R Then we can define the concept class: H. is the set of all threshold functions Xi which are 0 on X2, and H2 is set of all functions on X2 which are constant on X1. Then we can consider the following scenarios:
1. H = H2: is optimistically universally online learnable. The processes that admit universal online learning will satisfy C2 if we replace all the X. E X1 as dummy points.
2. H. = Hi U H2: It is not optimistically universally online learnable, as all processes supported on X1 admit universal online learning under H. However, for every learning strategy, there exists at least one process on X₁ forcing that strategy to make linear mistakes. (Due to theorem 9 and theorem 10
3. H are all measurable functions on X. This 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 H2 The answer formally stated as Theorem 9 We show the sufficiency by providing universal online learning rule (depending 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, Pr, and the adversary, PA and Un 0. Then in each round k:
* PA choose the point X(k) (N Xn.) E x
Pr. choose the prediction Itr- ((X,, Xa,e)) E (0,
Update Uj = UK-1 U (X(M))Stx-)
*
Py wins the game in round & if Hu,
0.

---

Here HUs { E H vi, (i,)(X())) (x)) which is the subset of H. that is consistent on (X)) (()))(((X))) (a))) for all S k.
A strategy is way of playing that can be fully determined by the foregoing plays. And winning strategy a strategy that necessarily causes the player to win no matter what action one's s opponent takes. We have the following lemma from Bousquet al. [202T].
Lemma 13 (Bousquet al. [202]] lemma 5.2). If H has no infinite VCL tree, then there universally measurable winning strategy g. for PL. in the game.
Notice that the winning strategy g is completely decided by U, induced by the set U. We may use this winning strategy JU to design an online learning algorithm
gU the winning strategy
This algorithm is 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 et al. 2021]
In order to describe the algorithm, we first provide the definitions of partial concepts. A partial if and
concept class S {0, 1, $} is set of partial function defined on X, where h(x) only if h is undefined on x. And for set X' C X, X' is shattered if every binary pattern y E {0, (0,1)x' is realized by some h E H. In this algorithm, we have w(H'' X<r) |(S S S {zi hert such that S shattered by H. which is the number of the subsequences of the sequence
Xer that can be shattered by the partial concept class H'. H
{h V'1, X2...., e
X. (h(X)), h(X2),.... h((x)) * ( X2, X2..... X+)} is the partial concept class induced by
gv. which contains the concepts that not consistent with gu at more than k data points, if
= (((()) gi (o)()))) We define H(( (i),) {h E H90 : Vi I t, t,,( = Y/}. We
also define XI.e (Xihesee and (mm) m1m+11
Algorithm 1: Learning algorithm from winning strategy
1, 0. l'
for t = 1,2.3.... do
B.j.j..... .2....
Js < t such that go (X)....... X,.) ) (Y,,...,,,,, then
Advance the game:
U + U ( X,.), ((,))),.,,,,))))
k + k +1.
I. с-< 0.
m + 1.
E' + t 1.
end Predict
Y, argmax Pr
wHH (0 ((((m))))) "0(f , Xz(
Y, # 9, then T TU ((x,, V.))
end
if'
> m(m+1)
+ then m m + 1.
2
end
end
The following lemma from the work of Bousquet et al. 2021 holds:
Lemma 14 (Bousquet et al. (202T). For any process {(x,, Y.JER) E R(H), there exists to such that for all 2 to. algorithm will not update i and U and for all J1. .i the winning strategy gu satisfies
go (X + (Y,...., ).
Proof. By the definition of the winning strategy, it leads to a winning condition for the player Pr. By the definition of Pt, 's winning condition, we know that there exists & such that "i.......... Hx.. N..9..
which means for all j1, j2. Jk. gu (XX ........N. Xzx) ) * (Y,...., y,)) ). That finishes the proof. D
7

---

This lemma shows that if the concept class H. has no infinite VCL tree, for sufficiently large to. the VCL game will stop advancing after round ig. Once the game stops advancing. we are effectively just bounding the number of mistakes by a predictor based on partial concept class of finite VC dimension. This result interesting in its own right, we extract this portion of the algorithm into separate subroutine, which is stated as Algorithm Appendi A.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 < cc. The subroutine (Algorithm in AppendixA.11 only makes T()) mistakes almost surely T co.
For brevity, 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 number of mistakes is (T))
Combining the lemmas above, for a concept class H. with no infinite VCL tree, for any realizable sequence, Algorithm satisfies lim supn- Σi= I Yı * hx,) 0 a.s. Because the winning strategy only updates finite times, the long-ru run average number of mistakes is dominated by the number of mistakes made by the subroutine, which is o(n).
To prove the necessity, we show that for every concept class with an infinite VCL tree, there exists at least one process that does not admit universal online learning under H. Formally,
Theorem 16. For every concept class H. with infinite tree there exists a process X. such that X does not admit universal consistent online learning.
We need the following definition and results from Bousquet et al. 2023 to define the sequence.
Notation 17 (Bousquet et al. [2023]) ), For any any u E (10, 13)", ler index(u) E N denote the index of in the lexicographic ordering of ((0,1))* 1))".
Definition 18 (Bousquet et [0023) Let X be a and H S 10, be hypothesis class, and let
T (au E X (10, 1})*}
be an infinite VCL tree that is shattered by H. This implies the existence of a collection
Hr (hn E H.ue. (10,
of consistent functions.
We say such a collection is indifferent for every v, u, w E (10, if index(v) < index(u), and w is descendant of u the tree T, then hu(dx) hw (Iv). ). In other words, the functions for all the descendants of a node that appears after v agree on
We say that T is indifferent it has set Hr of consistent functions that are indifferent.
Theorem 19 (Bousquet al. (2023). Let X be set and H C (0, 13 be a hypothesis class, and let T be an infintte VCL tree that is shattered by H. Then there exists an infinite VCL tree T" that is shattered by H. that indifferent.
Here is the proof sketch of Theorem 16
Proof Sketch. First, 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-Seare (BFS) order is 2 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 do this the tree is indifferent.) Thus, when reaching node on the path, no matter what the algorithm predicts, it makes mistakes with probability 1 2- Thus, it makes quarter mistake in expectation. Then by Fatou's lemma, for each learning algorithm, get a realizable process such that the algorithm does not make sublinear loss almost surely. O
We finish the proof of Theorem here. We then focus on the existence of the optimistically universal online learner when all processes admit universal online learning.
8

---

4.1 Optimistically Universal Online Learning Rule
In this part, we show that the condition whether H. has an infinite Littlestone tree 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 I0 The sufficiency part
of theorem 10 is proved in |Bousquet et al.) [202T] as the following lemma:
Lemma 20 (Bousquet et al. [2021] Theorem 3.1, the first bullet). H does not have an infinite Littestone tree, then there is stralegy 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, 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 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, matter what the algorithm predicts, makes mistake with a probability of more than half. Then we can use Fatou's 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 process that makes its average loss more than a half with probability more than zero.
5 Concept Classes with an Infinite VCL Tree
In this section, we discuss the necessary and sufficient conditions for process to admit universal online learning under the concept class H with an infinite VCL tree. Theorem IT states the an- swer formally. To prove this theorem, we first prove sufficiency (Lemma (2) 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 s(i+1)> where the index i is the index defined in Aondition well.
1
Lemma 23, If a process X admits universally consistent online learning under concept class H. it satisfies condition A
Proof Sketch. In order prove this lemma, 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 have set of experts E {el, c J. there is sequence } with log in = onn), such that for any realizable sequence (X, Y), for any n E N, there an expert e; with < i, such that Y, (X,) for every I
We modify the construction from the work Bfeeen--avie al. [2009] to build the experts. The experts are based on the set of the indexes of the rounds when the algorithm A makes mistakes, so there is a one-on-one map from the set of the indexes of the mistakes to the experts. Then we can index the experts based on the set of the indexes of mistakes to show the existence of such sequence.
Then we can get the theorem for optimistically universal online learnability, which is theorem Because the proof of lemma 23 and 22 works for any process, we can prove Theorem by reusing the proof of Theorem
6 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- et al. 22099 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 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 for the agnostic case.
Proof Sketch. To prove this lemma, we first build the experts 6; 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 T[++T) for each e to get 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 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 iimplies that all the characterizations for the realizable case are also characterizations for the agnostic case. We formally state the following theorems:
Theorem 25. For the agnostic case and any concept class H with infinite VCL tree, any process X admits strongly universal online learning under H. However, only the concept class with no infinite Littlestone tree optimistically universally online learnable.
For the concept class H with infinite VCL tree:
Theorem 26. For the agnostic case, a data process % admits strongly universal online learning under concept class H with infinite VCL tree if and only if satisfies condition [ However, a concept class H. with infinite VCL tree is optimistically universally online learnable if and only if satisfies condition
References
M. Adams and A. Nobel. Uniform convergence of Vapnik-Chervonn Chervonenkis classes under ergodic sampling. The Annals of Probability, 38(4): 1345 - 1367, 2010. doi: 10.1214/09-AOPS1 URL
fttts::/doi.orgee 12.14// AOP511
N. Alon, S. Hanneke, R. Holzman, and S. Moran. A theory of PAC lcarnability of partial concept classes. In Proceedings of the n2nd Annual Symposium Foundations of Computer Science, 2021.
D. Angluin. Queries and concept learning. Machine Learning, 2:319-342, 1988.
S. Ben-David, D. Pál, and S. Shalev-Shwartz Agnostic online learning. In Annual Conference Computational Learning Theory, 2009.
M. Blanchard. Universal online learning: an optimistically universal learning rule. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1077-1125, PMLR, 02-05 Jul 2022. URL httpt:://///.....t. /procce// ngs. ml www..l.prrsslllee wttl//////bbaaaaaa p.t.ress//11////laccccc. r22.aannchrd2b..... html
M. Blanchard and R. Cosson. Universal online learning with bounded loss: Reduction to binary classification. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Confer- ence on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 499- PMLR, 02-05 Jul 2022. URL https://prroeeeding wtt.:/s..w........1....
blanchard22a.. html
M. Blanchard and P. Jaillet. Universal regression with adversarial responses. The Annals of Statistics, 51(3):1401 1426, 2023. doi: 10. 10.1214/3-AA022000 URL wtthhhtp//////e wttp:/...../000.............
23 A0S2299
10

---

M. Blanchard, R. Cosson, and S. Hanneke. Universal online learning with unbounded losses: Memory is all you need. In Sanjoy Dasgupta and Nika Haghtalab, editors, Proceedings of The 33rd International Conference on Algorithmic Learning Theory, volume 167 of Proceedings of Machine Learning Research, pages 107-127. PMLR, 29 Mar-01 Apr 2022a. URI. https ppppoeeediig ngs m wtt..erereessslslleeeeeeeeeeee
rd22a. html]
M. Blanchard, S. Hanneke, and P. Jaillet. Contextual bandits and optimistically universal learning, 2022b.
M. Blanchard, S. Hanneke, and P. Jaillet. Adversarial rewards in universal learning for contextual bandits, 2023.
O. Bousquet, S. Hanneke, S. Moran, R. van Handel, and A. Yehudayoff. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 532 -22,,,1 New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978 9781450380539. doi: 02.1145/3406325.4555000 34C6325 3451087
O. Bousquet, S. Hanneke. S. Moran, J. Shafer, and I. Tolstikhin. Fine-grained distributionddepedenn learning curves. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5890-5924, PMLR, 12-15 Jul 2023.
L. Devroye, L. Györfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer- Verlag New York, Inc., 1996.
L. Gyorfi, G. Lugosi, and G. Morvai. A simple randomized algorithm for sequential prediction of ergodic time series. IEEE Transactions on Information Theory, 45(7):2642-2650, 1999. doi: 111100918.799422
S. Hanneke. Learning whenever learning is possible: Universal learning under general stochastic processes. Journal of Machine Learning Research, 22(130), 2021.
S. Hanneke, A. Kontorovich, S. Sabato, and R. Weiss. Universal Bayes consistency in metric spaces. The Annals of Statistics, 49(4) 2150, 2021. doi: 10.1214/20-A022022 URL https:://oo .rgg O. 1214 AOS2029
D. Haussler, N. Littlestone, and M. Warmuth. Predicting {0, ff-fucctions on randomly drawn points. Information and Computation, 1 115(2):248-29) 1994.
R. L. Karandikar and M. Vidyasagar. Rates of uniform convergence of empirical means with mixing processes. Statistics Probability Letters, 58(3):297-307, 2002. ISSN 0167-7152. doi: htts:///ooorr////.00000666777770 com/ http:///enneeertteeee///////////
BtLLnttp::/ www aciencedirect
W. M. Koolen and van Erven. Second-order quantile methods for experts and combinatorial games. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, volume 40 of JMLR Workshop and Conference Proceedings, pages 1155 1175. JMLR.org, 2015. URL http::::/rrooeedngg
mlr.press wtt.pprsss//44//ooelll.... html
N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285-318, 1988.
N. Liutletonee and M. Warmuth. Relating data compression and learnability. Unpublished manuscript, 1986.
N. Littlestone and M.K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):12--261 1994. ISSN 0890-5401. doi: http:///oi.orr//00 inco. 1994. 1009. htRtss/::: h//ww/ sci encedi rect. com/ scce///tatttiii..//pii.i S08 0099054018471009

---

G. Morvai, S. Yakowitz, and L. Gyorñ. Nonparametric inference for ergodic, stationary time series. The Annals of Statistics,, 24(1):370-379, 1996. ISSN 00905364. URL http:/ /www. jstor org/ sttable/22422
G. Morvai, S. R. Kulkarni, and A. B. Nobel. Regression estimation from an individual stable sequence. Statistics: A Journal of Theoretical and Applied Statistics, 33(2)999-118 1999.
D. Ryabko. Pattern recognition for conditionally independent data. Journal of Machine Learning Re- search, 7(23):645 664, 2006. URL http://twwe......oooooooo/op///p
html
I. Steinwart, D. Hush, and Scovel. Learning from dependent observations. Journal of Multivariate Analysis, 100(1):155-194 2009.
C. J. Stone. Consistent nonparametric regression. The Annals of Statistics, pages 595-620, 1977.
L. G. Valiant, A theory of the learnable. Communications of the ACM, 27(11): November 1984.
V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies events to their probabilities. Theory of Probability and its Applications, 16(2):264-28)) 1971.
V. Vapnik and A. Chervonenkis. Theory of Pattern Recognition. Nauka, Moscow, 1974.
B. Yu. Rates of convergence for empirical processes of stationary mixing sequences. The Annals of Probability, pages 94-116, 1994.
12

---

A Omitted Proofs
A.1 Proof of lemma 15
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.
++ 0.
m 4-
for / 1,.. do
Predict
Yz argmax Pr uoHH2 LU(X, X X(.a(my) S 2 (H() Xu.cmm)) Xst
Y; + y, then + LU (I).
end
if ス m(m+1) then m 1 1. end
end
Proof. In this proof, we assume that for the partial concept class H with VC dimension < d. Ne) is realizable. As we defined, the weight function, w(H', Xgr) KS 5 C (Xilisr such that S shattered by H'H, which is the number of the subsequences of the sequence Xgr that can be shattered by the partial concept class H..
Consider the k-th batch, consisting of W {X 1
X X J. Let 3
Z
Σ
kit
and
V/2
Zz
5(k-1)
Notice that
E
Vx
X
=(k-1)
E
Z+
E
Zk
X
ki 1)
X
tcc 13
E
Zz
X
Zz
X
0.(a.s.)
Thus, the sequence V& is martingale difference sequence with respect to the block sequence, W1. Wz,- ... By the definition of Vk, we also have -k < Vxx < k. Then by Azuma's Inequality, with probability ne. have
K
Zx
E
X
Aik-1)
+ - log
K2
2.
12
k=1
k= 1
k=
K
<
E Z+
X-
X
Aik-1)
+ v 4k3 log K.
1
13

---

Then we need get an upper bound for Zu X #(k-1) time we make a mistake, we have
According to the prediction rule, every
Pr
w HHu
LU) Ne, m S 2
( , التييمي
X
2
(3)
2
Due to the linearity of expectation, for every k,
k(
x 1 Yo
k(
E
Σ
P + Yi w(HL, X [0t1, ) S 2 zw(Her is X s
X للمطا
11
k(++))
+
I ve # Yo M w(HLe X
w/ wHH.. X )
X س
Here L, = ((X,, Yi)}, where i and the algorithm makes a mistake at round
Notice the first part is the expected number of mistakes, each of which decreases the weight by half. For every realization of X = k(b=1)) 2 ( k(++))
let
k(k+11)
u(k)
Σ
I
Y
I
wo (H of r+] Mey S 2 WHo,, t1 )
1()-1)
By the definition of the weight function and the fact that VC(H) w( (L (H ( kiktn)/
d. 5 hdd Consider the last round I k(k+1) that Y, + Ye 2
we have w(Hi, 1 M441)
1. the set (xe) must be shattered. Thus, we have S w oy kik-11 saauy). Therefore, u(k) S dlog k + 1, for
20(4)- (WH)) 2 )(tt)))
every realization, F ((( k()-))
Thus.
k(k+1)
Σ
[ii+V
wHHoo (amp)) s 5 1 (H p, ) )
ki
< 2d k.
1
(4)
Then consider the second part, we have
1
Y + Yo
w (o X X Kegeel) z WHo. (Hi,
X ( )
X -ل-يل
R(N-1)
k(k+1)
1 w 1 ) }
E
E
Y2 + Yi I w(HL X X )
X
X ببييا
2
A(k+1)
1 > X ارريي
E
I v Yi B w (HHnn (1441)))
X
X ((ー1
k(k-1)
14

---

This is because Yú and Y only depend on Xet. Due to the equation
3 we have
1 >
I Ye * Y E
w (HLL. X [t+1, 
w
HHL
(t, الدييعد )
X5
2
= - [. * Yz
Pr w(HHi X (111, ا
>
w W X السيياة
Xse
2
1 y # yil
- 2
Thus,
1 wWl, X pp (( }
Σ
I
[ + Yo
w(HL, pet1 1 xrrue))
X سسسيول
(5)
1)
ACk++13
E
Σ
1 8e + Yi]
X b1
Combining these two inequalities
4 and
5 we have
1)
2
2
Y1
+ Y
X 11
S 2d log + E
Σ
8g + Yi
X 11--1)
(6)
k(k-1)
kik-12
Thus, for any k, we have
Σ
Ye # Yo
S k(k-1)
S 4d log k.
(7)
According to the inequality least 1
for every k, Zz
X K
I 4d k. Thus, with probability at
KT
E
4d k + / 4K3 log K < 4dK log K + V4K log K.
k=
1=1
By the definition of Zu. with probability least 1 K
KIK
Σ
I x
< 4dK log K + V4K log K s (4d 2) K3 log K.
(8)
Let Tk- K(K+1)
be the number of instances in the sequence, with probability at least
K2
Tx
Σ
Yr Yr
S (4d + 2)T V 2 log Tk.
(9)
Define the event Ex the event that in the sequence XSTX ETH 1 Pr # Yi
(4d
2)T
2 log Tk. Then we know Pr[ER] s 1 < E. By Borel-Cantelli lemma, we know that for any Tk K(K+1) large enough,
Kz. Notice the fact that for any K E N,
K
Σx
K
Yi
< (4d + 2 V 1 log Tk happens with probability
2
Then for any large enough T, we have Tk <T < TK+1 S 2T. Thus, with probability 1,
T
Ye # Ye
$ (4d 2)7 K+1
log Tk+1
(10)
S (4d (2T)
log 2T'
(11)
15

---

Therefore, for any large enough 7 and universal constant c, with probability 1,
T
8 < vog..
(12)
Notice that cT Vlog T is o()). That finishes the proof.
A.2 Proof of Theorem 16
Proof. In this proof, we first modify the chosen indifferent VCL tree, such that the number of elements in each node is increasing exponentially. In other words, hope the k-th node in the Sreadth-First-Saaae (BFS) order contains 2 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 large enough.
Then we define the data process as follows: For the modified VCL tree, we define the sequence {Xi as Xy4-1+5 Xjk- where X5a 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, for each X,. First, we take 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, 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 the path visited afff-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 the label of the elements in the off-branch node. Thus, we can let the label of the elements the bff-branch node be the label decided by the descendant of that in- an-branch node. So, every element the node that is visited by the random walk still may be wrong with probability 2. when the algorithm sees it the first time. Also, the number of elements that come before k-th node in the BFS order, Dh-² 2 2
is roughly the same the number of elements in the k-th node, 2k-1, Thus at the d-th layer of the modified tree, if the random walk reaches the node Ka, for that node, we have
Σ
(X,)
* Yıl
Ka 2
(13)
nka
t=1
Here nK, is the number of elements the process when we reach the Kg-th node. This incquality 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 sebbsequence, which only contains nk, = kk 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
K,,th node and any other v will have smaller ratio of mistakes than 7i,,- Then notice that the ratio of mistakes is always smaller than or equal to 1, we can use the reversed Fatou's 'ss lemma and inequality 13 to get the final result (the fourth line and the last line in the following computations).
16

---

1
E
E
lim sup n
1| 114-1(X) (X,) Yil
(x, Y)
n1
B
lim sup n
[ (Xt) # Yil
71
nK ( + Yil
E
simsup
sup
d-+00
TKKa
nka
2 E
lim E
I ( * Yol n.a
d-+00
TkKa
1=1
Thus, there exists deterministic sequence (X, Y) such that it does not make sublinear expected mistakes.
A.3 Proof of Theorem 21
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 Xt, and no matter what the learning algorithm predicts, uniformly randomly choose Y, Thus, we have E [1 (Xx))(X)) # Y:ll 2 for every t. We get
n
lim sup Exx, n-
1 + Yil
(14)
2
According to Fatou's lemma, notice the ratio of mistakes is smaller than or equal 1, so we have the following inequality,
E lim sup
3 Ibe-((X) + Yıl 2 2
(15)
+20
Thus, for each learning algorithm, there exists data sequence {(x,, Y.)JEEN such that equation 15 holds. That finishes the proof.
A.4 Proof of Lemma 22
For the completeness, we provide the weighted majority algorithm here:
Algorithm 3: The Weighted Majority Algorithm with Non-uniform Initial Weights
For expert 6,, assign wi 7[+11 for / = 1,2... do
its initial weight.
Predict ye =1 1 E; Te(())) }
Update wi = 1 lle: (x)) w. 1-1
end
By using this algorithm, provide the proof of the lemma 22
Proof. In order prove this lemma, we use the weighted majority algorithm with initial weight w ([+1) for each expert i. We set MB = Σn T * Yi), which is the num-
ber of mistakes the algorithm made during n rounds. We also set m: Σn_ (X,) * Y.). Next, compute the total weight of all experts after rounds of the algorithm, W" Notice
17

---

that if the algorithm makes a mistake at round n. there must be majority of the experts mak-
ing a mistake at round n, so Wn W 2 2 _ which means W I | _
Thus, we have W (2) MB Wo (2) MB Notice that W > w for all i, it holds for argmingg,, Ei=1 (X), & Yil. We have the following inequality for all n.
14-1 (Xt) # Yıl S 3 min
[e, + Yi] + log
(16)
iStn
S 3 min 15
(X, + Yi + log in-
(17)
Here comes from the fact that fixed sequence, {in), we have
log logr
S 3. Therefore, for a fixed process X, target function h and
n Σ Im + Y2l
lim sup 12-000
- lim sup
3 min k
I (X, * Yi + 2 log in
12
(18)
Then by the condition A we know the right-hand side of the inequality is O.
Notice that lim sup, =
Ei= II [1k-1 (X+) * Yı] is non-negative random variable, so we have
1
E lim sup
- Σ
h (X,) + Yil = 0.
(19)
n-+00 71 1=1
Therefore, lim sup, n Em= I (
+ Yil almost surely.
A.5 Proof of Lemma 23
Algorithm 4: Expert J
Input: set J
for 1= 1,2,... do
recieve X,-
compute Ve f.A (X Yetx
it't E J then
predict dt -
else
predict Jt = Jr.
end
end
"Y (x.)et
Proof. In this proof, we show how to define a sequence of experts (e1,e2,...)) such that the condition i satisfied, if admits universal online learning. Let an online learning rule fe be the algorithm that can learn all realizable label processes V RHH, X). 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 J. For example, if the algorithm makes mistakes at round (1,4, 7). Thus we have a one-on-one map from J to an expert.
then the set J for that expert
First, we show that for every realizable label process Y E R(H, and any E N, there is an expert e, such that e, (X,)
Y, for all n. This part of the proof is similar the proof of lemma 12 in the work of Ben-Davie David et al. [2009]. Consider a subsequence Ysn of realizable label process Y. E J if and only if f ej Yej, X,) + Y, for all j I Thus, the history (Xet, Yee) for all t < n are the same as (Xee, Yee), which implies (X,) = Y, = Y, for all t < n. Therefore, for any n E N. there is a set J:,, containing all j S such that SA(( Kj, Y X3) 4 Yj. Then the algorithm with input Jr, creates expert et,, such that c.,, (X,) Y, for all n.
18

---

Next, we only need to build the index in for the set Jn to show that log in - onn). The index of set is follows: For all / S N, order them by [m (If two sets have the same value, we use []] tie-breaking.) Here [ is the number of elements in J and max J is the maximal element in J. After that, index J's from following this order.
At last, we show the method mentioned above constructed a set of experts satisfying condition A we have set of experts E {ee, ...... }. there is sequence {in} with log i, o(n), such that for any realizable sequence (x, Y), for any E N, there is an expert e, with S in such that Y, = (X,) for every S n. Therefore, we need to compute the in as follows. Assume Jet, max Jr, k. we have
in S IKJ: max J 1 =
|J
max = =m
m=1
+ 2
VR
m -
k - 1)
2v
em²
S (k: + I)EVE.
m= V
m= vk
Notice that |Ji,, (n, we have
2 [J,, I
0. Thus, we get the set of experts and the corresponding sequence [i, satisfying condition A
lim log
lim +00
(20)
7 70000 71
n
L
A.6 Proof of Theorem 24
Proof. In order prove this theorem, we the procedure based learning with experts' advice.
First, we build and index the experts, fe1, ... J. by using the same method we mentioned in the proof of lemma 23 (A.5). which satisfies Condition A Then, use Squint algorithm from the work Koolen and van Erven [2015]. we need the initial weight of the experts to be distribution. We can the initial weights n, i(i+1) for each e; and this forms distribution, as πī sum of n. reaches 1 when goes to infinity.
i+1 the
According to Theorem 3 in the work of Koolen and van Erven 2015), we have the following upper bound for the regret
T Σ1 I (m) xX, [=1
T Σ (()) t=1
(V
+ Ydl so +Y)
(Vi.
V/ log log log Vx
1
log
(21)
Here the V& 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 have
V4= = Σ (1)..))))) + Yd - [Xe( A Y.))².
(22)
Notice that (1 ( # Y,] (Xe( + Y:))² is either 1 or 0, we have V2 S T. The regret of this algorithm is upper bounded by:
o
o
(
log VE
0 @V
Vi log
log
Tlog
log log T T log k + log k
(23)
T
TTk
According to the condition A also know
lim min T-
(X.) + Yi =0.
(24)
T
ecs
19

---

Thus, the regret of this algorithm is
T
lim sup
limsup
Σ
Y + h
-1 -IX0
T
T-000
t=1
-limsuy T-x00
1
Σ
[ Yi * h
[r; * -x - [(x( & vill)
T
t=1
T
S <limsupp T
1
Σ
[I Y/ + R1 1 (x,)
- I|,, +x exx)) + (ex) # Yi'1)
T-o t=1
T
< $lim T-000
Σ
(1
x
x h (x.)
- 1 + exx())l) + lim sup T-000 T
Σ (ex(()) 4 Y?
T
Because log ir (T)) and log k < log ir we have log k: = o(T). Thus, the regret above is (T)). Therefore, we have an algorithm to extend a universally consistent online learning algorithm for realizable cases to universally consistent online algorithm for agnostic cases.
To prove the necessity, notice that a universally consistent online algorithm for agnostic cases be used to solve the realizable case and the regret is equal to the number of mistakes.
20

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Theorems T0 11 provides the full characterization for realizable case. Theorem 24 provides the method to extend the algorithm for the realizable case to the agnostic setting
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long 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]
21

---

Justification: In the abstract and the introduction, we both mentioned our work focuses on binary classification.
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 encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are 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 few datasets or with 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 is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't '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 proofs are in the Appendix part.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide 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 supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: There experiments in this paper. This work is a learning theory paper.
Guidelines:
22

---

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 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 specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, 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 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 new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source 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 deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., 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:
This is 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.
Please see the NeurIPS code and data submission guidelines (https: cc/
public public//uidees/CCe Sodeedduee/oeSSmimiiccocm ss asionPolicy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "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 NewrIPS code and data submission guidelines (https
/ tnips.cc/putl
wttic//ggiiisseeeee.eeeeee iess Codee bubmi ss i ionPol icy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
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).
23

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
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?
Question:
Answer: [NA]
Justification: This is learning theory paper. There is experiment in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to 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, supplemental material.
7. 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 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 accompanied by error 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 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.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma 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 out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This is learning theory paper. There no experiment in this paper.
Guidelines:
The answer NA means that the paper does 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 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:////...rrr......//////////e
Answer: [Yes]
Justification: We are sure we conform with the NeurlPS 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 NeurlPS 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 (e.g.. there is 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: 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
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 (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
25

---

Justification:
This is 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 high risk for misuse or dual 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 challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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?
Question:
Answer: [NA]
Justification:
This is a learning theory paper with no experiments or code.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.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.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperr snnerswwthhood com. / dataaaaaaaa datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that 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
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: This is learning theory paper. There are no new assets introduced.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/mooel 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.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
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 to participants and screenshots, if applicable, as well details about compensation (if any)?
26

---

Answer: [NA]
Justification: This is learning theory paper. There are no experiments or research with human objects in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 NeurlPS Code of Ethics, workers involved in data collection, curation, 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/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This is learning theory paper. There are experiments research with human objects in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "LM2C3ENUFT", "reviewer": "Reviewer_MwJp", "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.\n\nThe two main characterizations are as follows. Fix hypothesis space $H$.\n1. 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).\n2. 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).\n\nBy 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):\n1. $X$ is learnable iff a countable set of experts exist (which can depend on $X$) that satisfy a certain no-regret condition.\n2. 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.\n\nBoth of these conditions collapse to a previously studied condition if $H$ is the set of all measurable functions.", "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": "See questions.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "Strong progress for an important and recent learning problem.\n\nThis work continues the characterization of distribution-dependent (universal) learning under stochastic processes, which fits into a broad range of recent results in universal learning and combinatorial characterizations.\n\nThe experts advice algorithm Squint is used as a nice black-box reduction from agnostic to realizable, similar to the weighted majority based reductions in adversarial online classification.", "weaknesses": "The paper lacks a bit of exposition to guide the reader and a more thorough discussion of related work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your helpful comments. We will provide more discussion on related works in the final version and help the reader understand our results more easily.\nIn our work, we are focus on the consistency problem. The quantitative rates problem is an interesting future direction, though will certainly require significant work even to formulate the question appropriately (for instance, it could be a question about, for a given rate function R(n), which function classes and processes admit learning with mistakes growing at rate R(n)?  It is definitely an interesting direction, though perhaps challenging, and worthy of a separate future work)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A9Up3xDszB", "reviewer": "Reviewer_vKfY", "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.", "questions": "- Do these results/techniques have any implication for optimistic online learning beyond the binary-label setting?", "limitations": "The authors have adequately address the limitations and assumptions made in their results.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think the question of characterizing optimistic learnability for a given concept class is very interesting, and the paper is well-written in that it clearly explains the intuition and interpretations of the results, and connects to prior work.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your helpful comments.\n\nWe will work to make the notation more readable, such as changing the capital X in the VCL game to make it less confusing.\n\nAs for the optimistically universally online learnability problem beyond binary-labeled cases, this is a very interesting question.  We believe the technique used here extends easily to finite-label multiclass learning.  Beyond that, we have found that further research is needed to understand the problem for infinite-label multiclass learning, regression, and learning with general losses, and we leave this for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9IkN3IoVQX", "reviewer": "Reviewer_jKRy", "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:\n\nStrongly universal: for every $\\mathcal{H}$-realizable process $\\mathbb{X}$ there is a strongly universally consistent online learning algorithm for $\\mathcal{H}$ and $\\mathbb{X}$.\n\nOptimistically 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}$.\n\nThe main results of this work (as far as I understand) are the following:\n\n$\\mathcal{H}$ is strongly universal if and only if it has no infinite VCL tree (Theorem 9).\n\n$\\mathcal{H}$ is optimistically universal if and only if it has no infinite Littlestone tree (Theorem 10).\n\nRecall that $\\mathcal{H}$ has no infinite Littlestone trees implies $\\mathcal{H}$ has no infinite VCL tree.\n\nFurther results extends this characterization to the agnostic case.", "questions": "Please elaborate on the connections between this work and Section 3 of arxiv.org/pdf/2011.04483.\n\nPlease clarify the apparent inconsistency in the Theorems 9, 10, and 12.\n\n[The above questions have been addressed in the rebuttal]", "limitations": "There is no section on limitations, but the work is purely theoretical with no foreseeable societal impact.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The work considers a variant of universal consistency for online learning in which there is a reference class $\\mathcal{H}$ of binary classifiers. A full characterization on universal online learnability is provided.", "weaknesses": "The clarity of the presentation is below the NeurIPS standards.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your helpful comments and we address your questions below.\n\nFirst, let us re-iterate the definitions of the paper.\nFor a given concept class $\\mathcal{H}$, a process $\\mathbb{X} = (X_1,X_2,\\ldots)$ admits a universally consistent online learner if there exists a learning algorithm guaranteeing that, for any realizable classification of the sequence, the learner's number of mistakes grows only sublinearly.  So the property of admitting universal online learning is a property of a concept class $\\mathcal{H}$ *and* a stochastic process $\\mathbb{X}$.  In contrast, the property of admitting an optimistically universal online learner is a property of a concept class $\\mathcal{H}$: namely, $\\mathcal{H}$ admits an optimistically universal online learner if there exists an algorithm which is universally consistent (i.e., makes sublinearly many mistakes for realizable classifications) for *every* process  $\\mathbb{X}$ which admits a universally consistent online learner.  See the paper (e.g., lines 50-52), and references therein, for further explanation about this terminology and the history of this subject (in the context of prior work, our innovation is incorporating the concept class $\\mathcal{H}$ into the theory).\n\nThere is no inconsistency in the results.  As we prove (Theorem 9), any class with an infinite VCL tree has the property that the set of processes $\\mathbb{X}$ admitting a universally consistent online learner is not the set of *all* processes: that is, only some processes admit a universally consistent online learner.  In contrast, Theorem 9 also establishes that any class that has no infinite VCL tree has the opposite property: that is, *every* process admits a universally consistent online learner.  Note that this is different from the property of admitting an optimistically universal online learner; the latter would require also that there exists a single online learning algorithm which is universally consistent for every such process (in the case of classes having no infinite VCL tree, since Theorem 9 implies every process admits a universally consistent online learner, an optimistically universal learner would need to be universally consistent for *every* process; our Theorem 10 establishes that, among classes with no infinite VCL tree, such an optimistically universal learner exists if and only if $\\mathcal{H}$ also has no infinite Littlestone tree).  For classes which have an infinite VCL tree, the property of being an optimistically universal learner only requires the learner to be universally consistent under all processes $\\mathbb{X}$ which admit a universally consistent online learner, hence they do not need to be consistent for *all* processes (this is impossible, by our Theorem 9); for such classes, our condition A describes precisely which processes $\\mathbb{X}$ admit universally consistent learners (Theorem 11), and our condition B describes which concept classes $\\mathcal{H}$ with infinite VCL trees admit optimistically universal learners (Theorem 12).\n\nWe indeed discuss (and use, with citation) the results of the Bousquet et al paper referenced in the review.  The sufficiency half of our results for classes having no infinite Littlestone tree (Theorem 10) are directly based on that work.  We note that their work considers whether there exists an online learner successful under *arbitrary* realizable data sequences.  In contrast, we are interested in understanding which pairs ($\\mathcal{H}$,$\\mathbb{X}$) admit the existence of successful online learners, and the question of whether there can exist a learner which achieves this adaptively (i.e., without dependence on the distribution of the sequence): the former is the question of which processes admit universally consistent learners, and the latter is the question of which concept classes admit optimistically universal learners.  For instance, consider the class $\\mathcal{H}$ of thresholds on the real line; this class admits an infinite Littlestone tree (hence Theorem 10 (which is similar to, but not quite the same as, Bousquet et al.'s Theorem 3.1) shows there is not an algorithm universally consistent under *all* realizable data sequences), but since there is no infinite VCL tree our Theorem 9 reveals that every process $\\mathbb{X}$ admits a (process-specific) universally consistent online learner.  Hopefully this clarifies: the latter is about whether each process admits a (distribution-dependent) universally consistent learner, whereas the former is about whether there is an algorithm (defined independent of the process) which is universally consistent for every process $\\mathbb{X}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We want to thank all reviewers for their helpful suggestions and comments. We will polish our paper to make it easier to read and follow.

We here clarify our results again:   

First, we would like to clarify the motivation of our work. This line of work on optimistically universal learning is trying to capture the minimal assumption needed for learnability. We investigate the **universal consistency** problem **beyond i.i.d. data-generating processes** and for general concept classes.

To emphasize our novelty and contribution: We provide a full characterization of what data processes admit universal online learning under concept class H and what concept classes H have an optimistically universal learning rule. The formal statements are in Theorems 9, 10, 11, 12, and for agnostic cases: Theorems 24, 25. Those results are all new results, except the sufficiency of Theorem 10, which can be derived from Bousquet et al. (2021).  The sufficiency of Theorem 9 is totally novel, though we use some techniques from Bousquet et al. (2021) and Alon et al. (2021).  The necessity of Theorem 10 is also (subtly) different from the necessity part of Theorem 3.1 in Bousquet et al (2021), since our data process must be fixed in advance (rather than adaptively constructed by an adversary) and we need to show not only that the number of mistakes is infinite but that it does not grow sublinearly.

Meta-review: 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
Decision: Accept (poster)