Online Classification with Predictions
Authors: Vinod Raman
Ambuj Tewari
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Learning
Algorithms with Predictions
Primary area: online_learning
TL;DR: We show that having access to good predictions about future examples can lead to better regret bounds in online classification.

Abstract: We study online classification when the learner has access to predictions about future examples. We design an online learner whose expected regret is never worse than the worst-case regret, gracefully improves with the quality of the predictions, and can be significantly better than the worst-case regret when the predictions of future examples are accurate. As a corollary, we show that if the learner is always guaranteed to observe data where future examples are easily predictable, then online learning can be as easy as transductive online learning. Our results complement recent work in online algorithms with predictions and smoothed online classification, which go beyond a worse-case analysis by using machine-learned predictions and distributional assumptions respectively.

Online Classification with Predictions
Vinod Raman
Ambuj Tewari
Department of Statistics University of Michigan Ann Arbor, MI 48104 vkr Kkraman@uma ch. edu
Department of Statistics University of Michigan Ann Arbor, MI 48104 tewar NowariaBie aeriiiiuummiimm ch. edu
Abstract
We study online classification when the learner has access to predictions about future examples. We design an online learner whose expected regret is never worse than the worst-case regret, gracefully improves with the quality of the predictions, and can be significantly better than the worst-case regret when the predictions of future examples are accurate. As a corollary, we show that if the learner is always guaranteed observe data where future examples are easily predictable, then online learning can be easy as transductive online learning. Our results complement recent work in online algorithms with predictions and smoothed online classification, which go beyond a worse-case analysis by using machine-learned predictions and distributional assumptions respectively.
1 Introduction
In online classification, Nature plays a game with a learner over E N rounds. In each round I [T). Nature selects labeled example (5+, Mr) E X x y and reveals just the example o, the learner. The learner, using the history of the game (æ1, y1)..., (I,-1, 3t-1) and the current example Tt. makes potentially randomized prediction ÿt E V. Finally, Nature reveals the true label yr and the learner suffers the loss L # y. Given access to a hypothesis class H C yd consisting of functions h : X + V, the goal of the learner is minimize cumulative mistake and that of the best fixed hypothesis f E H in hindsight. We say a class H is online learnable if there exists learning algorithm that achieves vanishing average regret for any, potentially adversarial chosen, stream of labeled examples (I1, 81 )....... (IT, yr). Canonically, one also distinguishes between the realizable and agnostic settings. the realizable setting, Nature must choose stream (I1, y1 ) ..., (IT, yr) such that there exists a / E H for which h(xz) y/ for all I [T]. On the other hand, the agnostic setting, no such assumptions on the stream are placed.
regret, the difference between its
Due to applications in spam filtering, image recognition, and language modeling, online classification has had long, rich history in statistical learning theory. In seminal work, Littlestone [1987
provided sharp quantitative characterization of which binary hypothesis classes H C (0, 1 1 are online learnable in the realizable setting. This characterization was in terms of the finiteness of combinatorial dimension called the Littlestone dimension. Twenty-two years later, - et al. (2009) proved that the Littlestone dimension continues to characterize the online learnability of binary hypothesis classes in the agnostic setting. Later, Daniely et al. [201T) generalized the Littlestone dimension multiclass hypothesis classes H. C y and showed that it fully characterizes multiclass
online learnability when the label space ) is finite. More recently, Hanneke et al. 2023 extended this result to show that the multiclass Littlestone dimension continues to characterize multiclass online learnability even when y is unbounded.
While elegant, the characterization of online classification in terms of the Littlestone dimension is often interpreted as an impossibility result (Haghaalbb) 2018). Indeed, due to the restrictive nature of the Littlestone dimension, even simple classes like the 1-dimensional thresholds Hurres {a +>
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

1fr 2 a) : E NJ are not online learnable in the realizable setting. This hardness arises mainly due to a worst-case analysis: the adversary is allowed to choose any sequence of labeled examples, even possibly adapting to the learner's s strategy. In many situations, however, the sequence of data "easy" and a worst-case analysis is too pessimistic. For example, if one were to use the daily temperatures to predict snowfall, it is unlikely that temperatures will vary rapidly within given week. Even so, one might have to access to temperature forecasting models that can accurately predict future temperatures. This motivates beyond-worst-case analysis of online classification algorithms by proving guarantees that adapt to the "casiness" of the example stream.
The push for beyond-worst-cuse analysis has its roots in classical algorithm design [Roughaadden 2021]. Of recent interest is Algorithms with Predictions (AwP), a specific sub-field of beyond- -worst case analysis of algorithms [Mitzenmacher and Vassilvitskii 2022]. Here, classical algorithms are given additional information about the problem instance in the form of machine-learned predictions. Augmented with these predictions, the algorithm's 's goal is to perform optimally on a per-input basis when the predictions are good (known as consistency), while always ensuring optimal worst-case guarantees (known as robustness). Ideally, algorithms are also smooth, obtaining performance guarantees that interpolate between instance and worst-case optimality as a function of prediction quality, After a successful application to learning index structures [Kraska et al., 2018), there has been an explosion of work designing algorithms whose guarantees depend on the quality of available, machine-learned predictions Mitzenmacher and Vassilvitskii (2022). For example, machine-learen
predictions have been used to achieve more efficient aata-structures [Lin et al. [2022], faster runtimes [Chen et al. 2022 Ergun et al. 2021], better accuracy-space tradeoffs for streaming algorithms (Hsu 2019 and improved performance bounds for online algorithms (Purohit et al. 2018).
et al.
Despite this vast literature, the accuracy benefits of mearied predictions for online classifi- cation are, to the best of our knowledge, unknown. In this work, we bridge the gap between AwP and online classification. In contrast to previous work, which go beyond a worst-case analysis in online classification through smoothness or other distributional assumptions (Haghtalab et al.) 2020 Block et al. 2022 Wu et al. [023), we give the learner access to a Predictor, a forecasting algorithm that predicts future examples in the data stream. The learner, before predicting a label ft. can query the Predictor and receive predictions 2141, ..... 27 on the future examples. The learner use the history of the game (21, v1), .... 1.t-1.8h-11) the current example Tt, and the predictions ft-1;--- ..... &r to output a label Ut- We allow Predictors be adaptive they can change their predic- tions of future examples based on the actual realizations of past examples. From this perspective, Predictors are also online learners, and we quantify the predictability of example streams through their mistake-bounds.
then
In this work, we seek to design online learning algorithms whose expected regret, given black-box access to a Predictor, degrades gracefully with the quality of the Predictor's predictions. By doing so, we are also interested in understanding how access to Predictor may impact the characterization of online lcarnability. In particular, given a Predictor, when can online learnability become easier than in the standard, worst-case setup? Guided by these objectives, we make the following contributions.
(1) In the realizable and agnostic settings, we design online learners that, using black-box access to a Predictor, adapt to the "easiness" of the example stream. When the predictions of the Predictor are good, our learner's 's expected mistakes/regret significantly improves upon the worst-case guarantee. When the Predictor's 's predictions are bad, the expected mistakes/regret of our learner matches the optimal worst-case expected iistake-bound/rege Finally, our learner's expected Predictor's 's predictions.
degrades gracefully with the quality of the
(2)
We show that having black-box access to a good Predictor can make learning much easier than the standard, worst-case setting. More precisely, good Predictors allow "offline" " learnable classes to become online learnable. In this paper, we take the "offline" setting to be transductive online learning [Ben-David et al. 1997, Hanneke et al. 2024 where Nature reveals the entire sequence of examples 21...., .T (but not the labels y/1 vi.,... yr) to the learner before the game begins. Many "offline" learnable classes are not online learnable. For example, when y = {0. 1). transductive online learnability is characterized by the finiteness of the VC dimension, the same dimension that characterizes PAC learnability. Thus, our result is analogous to that in smoothed online classification, where PAC learnability is also sufficient for online learnaillity Haaghtalb et al. 2020 Block et al. 2022

---

A notable property of our realizable and agnostic online learners is their use of black-box access to transductive online learner to make predictions. In this sense, our proof strategies involve reducing online classification with predictions to transductive online learning. For both contributions (1) and (2), we consider only the realizable setting the main text. The results and arguments for the agnostic setting are nearly identical and thus deferred to Appendix
1.1 Related Works
Online Algorithms with Predictions. Online Algorithms with Predictions (OAwP) has emerged as important paradigm lying at the intersection of classical online algorithm design and machine learning. Many fundamental online decision-makinn
problems including ski rental [Gollapudi and
Panigrahi| 2019 Wang al.) 20200] Bamas al. 2020], online scheduling [Lattanzi et al.]|2020 Wei
and Zhang |020|Scullyy Scully et al. [2021] online facility location (Almanza et al. [202] Jiang Jiang et al. [202]] J.
caching [Lykouris and Vassilvitskii
202T Elias et al. 2024). and metrical task systems [Antoniadis)
jet al., 2023]. have been analyzed under this framework. Recently, Elias et al. [0244 consider a
model where the predictor is allowed to learn and adapt its predictions based on the observed data.
This is contrast to previous work on learning-augmented online algorithms, where predictions are made from machine learning models trained on historical data, and thus their predictions are static and non-adaptive to the current task at hand. Elias et al. [2024] study number of fundamental problems, like caching and scheduling, and show how explicitly designed predictors can lead to improved performance bounds. In this work, we consider model similar to Elias et al. (2024), where the predictions available to the learning algorithms are not fixed, but rather adapt the true sequence of data processed by the learning algorithm. However, unlike Elias et al. (2024). we do not hand-craft these predictions, but rather assume our learning algorithms have black-box access to a machine-learned prediction algorithm.
Transductive Online Learning. In the Transductive Online Learning setting, Nature reveals the entire sequence of examples æ1...., FT to the learner before the game begins. The goal of the learner is to predict the corresponding labels yi,.... yr in order, receiving the true label ye only after making the prediction åt for example zt. First studied by BBvn- et al. [1997), recent work by HHanneke et al. (2024) has established the minimax rates on expected mistakes/regret in the realizable/agnosti settings. In the context of online classification with predictions, one can think of the transductive online learning setting as special case where the Predictor never makes mistakes.
Smoothed Online Classification. In addition to AwP, smoothed analysis (Spielman and Teng 2009 another important sub-field of beyond worst-caee analysis of algorithms. By placing distributional assumptions on the input, one can typically go beyond computational and information -hhooreti bottlenecks due to worst-case inputs. To this end, Rakhlin et al. [201T). (Hahhtlab) (2018), [Haghtalab] al. 2020). Block et al. [2022] consider a smoothed online classification model. Here, the adversary has to choose and draw examples from sufficiently anti-concentrated distributions. For binary classification, [Haghtalab (2018) and Haghtalab et al.] (2020) showed that smoothed online learnability is as easy as PAC Icarnability. That is. the finiteness of a smaller combinatorial parameter called the VC dimension is sufficient for smoothed online classification. In this work, we also go beyond the worst-case analysis standard in online classification, but consider a different model where the adversary is constrained to reveal sequence of examples that are predictable. In this model, we also show that the VC dimension can be sufficient for online learnability.
2 Preliminaries
Let X' denote an example space and y' denote the label space. We make no assumptions about ), so it can be unbounded (e.g., y = N). Let 7. S yd denote a hypothesis class. For set A, let A' = U A denote the set of all finite sequences of elements in A. Moreover, we let ASn denote the set of all sequences of elements in A of size at most n. Then, X denotes the set of all finite sequences of examples in X' and C X denotes a particular family of such sequences. We abbreviate sequence 21,..., 27 by Z1.T. Finally, for a, b, E R. we let A b A min(a, b, c}.
3

---

2.1 Online Classification
In online classification, learner plays repeated game against Nature over T E N rounds. In each round E [T], Nature picks labeled example (I,, (2), E & x y and reveals to the learner. The learner makes a randomized prediction ÿt E V.. Finally, Nature reveals the true label yt and the learner suffers the 0-1 loss 11 {t yr Given a hypothesis class H C yuk the goal of the learner is to minimize its expected regret
T
T inf NER
R. (T, H):= sup
sup #LTEX VIT
E
Σ ((A(a))
+ v.)
Σ ((h(a)) + vr 1=1
where the expectation is only over the randomness the learner. A hypothesis class is said to be online learnable if there exists (potentially randomized) online learning algorithm A such that (T. H) = (T)) If it is guaranteed that the learner always observes sequence of examples labeled by some hypothesis h E H. then say are in the realizable setting and the goal of the learner is to minimize its expected cumulative mistakes,
I1AA(E) # M(x))
MA (T, H) == sup sup EE ZITEX DEH
where again the expectation is taken only with respect to the randomness of the learner. It is well known that the finiteness of the multiclass extension of the Littlestone dimension (Ldim) characterizes realizable and agmostic online learnability [Littlestone] 1987 Daniely et al., 2011 Hanneke et al. 2023).
See Appendix A for complete definitions.
2.2 Online Classification with Predictions
Motivated by the fact that real-world example streams F1.7 are far from worst-case, we give our learner black-box access to a Predictor P, defined algorithmically in Algorithm and formally in Definition I In the rest of the paper, abuse notation by not explicitly indicating that P takes its own past predictions as input. That is, given a sequence F1.7 E X²' we will P P(11a) denotes its prediction the t'th round.
Definition (Predictor). A Predictor P x I(xTT) is map that takes in a sequence of instances 31, I22 ils own past predictions 21.T, N1.T, n.; and outputs distribution j E II(x²)). The Predictor make its next prediction by sampling āir j..
Algorithm Predictor P
Input: Time horizon T
for t = 1,.... do
Nature reveals the true example Tt-
Observe ze, update, and make (potentially randomized) prediction $4.7
end
We highlight that our Predictors are very general and can also use side information, in addition the past examples, make predictions about future examples. For example, if the examples are daily average temperatures, then Predictors can also use other covariates, like humidity, precipitation, and wind speed, to predict future temperatures.
Remark.
In each round & E [T], the learner A can query the Predictor P to get a sense of what examples it will observe in the future. Then, the learner A can use the history (I1, 91), (#r-1, Mt-1), the current example Ht, and the future predicted examples to classify the current example. Protocol makes explicit the interaction between the learner, the Predictor, and Nature.
Note that, in every round E [T]. the Predictor makes a prediction about the entire sequence of T examples, even those that has observed in the past. This is mainly for notational convenience assume that our Predictors are consistent.
Assumption (Consistency). Predictor is consistent if for every sequence Fi. XT and every time point t E [T', the prediction रn. P(æra) satisfies the property that ā F1:t-

---

Algorithm 2 Online Learning with a Predictor
Input: Predictor P, Hypothesis class H. Time horizon T 1 for t = 1,..., T do
Nature reveals the true example ft-
The Predictor P observes 2t, updates, and reveals its predictions Li.T.
Learner makes randomized prediction de using ii.r, Te, and (I1,81), ... (21-1191-1)
Nature reveals the true label y/ to the learner.
Learner suffers loss I (y * vi and updates itself.
7 end
Although stated as assumption, it is without loss of generality that Predictors consistent any inconsistent Predictor can be made consistent by hard coding its input into its output. In addition to consistency, we assume that our Predictors are lazy.
Assumption 2 (Laziness). A Predictor is lazy if for every sequence Fu. E X and every E [T], if P(x1.-11) 2t, then P (=11:) = ((r..t1)) That is, P does not change its prediction if it is correct.
Since Predictors are also online learners, the assumption of laziness also mild: non-lazy online learners can be generically converted into lazy ones [Littlestone] 1987 1989.. We always assume that Predictors are consistent and lazy and drop these pronouns for the rest of the paper.
Remark. We highlight that Predictors are adaptive and change their predictions based on the realizations of past examples. This contrast existing literature in OAwP, where machine-learner predictions are often static. Nevertheless, our framework is more general and captures the setting where predictions of examples are made once and fixed throughout the game, Indeed, consider the consistent, lazy Predictor that fixes sequence 21:7 E X before the game begins, and for every t E [T], outputs the predictions Kf.r such that &f. = Fist and ff+1-T = 2t-1:T.
Ideally, when given access to a Predictor P, the expected regret of A should degrade gracefully with the quality of P's predictions. To this end, we quantify the performance of a Predictor P through
T
Mp((1T) = IE
Σ 2=
1(P(aiaa
the expected number of mistakes that P makes on a sequence of examples ø1.7 E X², In Section 3 we design an online learner whose expected regret/mistakke-bunn on stream (x1, V1), (2T, VT can be written in terms of Mp (æ1:)).
2.3 Predictability
Predictors and their mistake bounds offer to ability to define and quantify notion of "easiness" for example streams 11.7. In particular, we can distinguish between example streams that are predictable and unpredictable. To do so, let 2 C X denote collection of finite sequences of examples. By restricting Nature to playing examples streams in Z, we can define analogous notions of minimax expected regret
T
RA (T, 2)
E 21 T
sup
sup
1 (A(z)) #v NEW
inf
1 ((h(rs) + vc)
==
and minimax expected mistakes,
T Σ HA(z)) #M()))
M MA 7, 2) = sup sup E ZITEZ NEH
As usual, we say that tuple 2H is online and realizable online learnable if inf A RA H. 2) o(T)) and inf A (T, H. Z) o(T) respectively. If Z = X*, then the definitions above recover the standard, worst-case online classification setup. However, in the more general case where 2' X', we can use the existence of good Predictors P and their mistake bounds to quantify the "easiness" of a stream class Z. That is, we say 2 predictable there exists a consistent, lazy Predictor such that Mp(T) Z) su Mp(IIT) = o(T).
5

---

Definition 2 (Predictabilityy) A class 2 C X* is predictable if and only if (T, = o(T).
Definition provides qualitative definition of what it means for sequence of examples to be predictable, and therefore "easy". If Z S X is a predictable class of example streams, then stream F1:T E X" is predictable if FIr Z. By having access good Predictor, sequences of examples that previously exhibited "worst-case" behavior, now become predictable. One natural predictable collection of streams are those induced by easy-to-learn discrete-time dynamical systems [Raman et al. 2024). That is, let X' be the state space for a finite collection G of transition functions. 'Then given an initial state za E X, one can consider the stream class 2 to be the set of all trajectories induced by transition functions in G. In Section 3 we show that for such classes of predictable examples, "offline" learnability is sufficient for online learnability.
2.4 Offline Learnability
In the classical analysis of online algorithms, one competes against the best "offllne" solution. In the context of online classification, this amounts to comparing online learnability to "offline" learnability, where we interpret the "offline" setting as the case where Nature reveals the sequence of examples (f1,...,Ty) before the game begins. In particular, compared to the standard online learning setting, in the "offline" version, the learner knows the sequence of examples 21, ....... 2r before the game begins, and its goal is to predict the corresponding labels y1..... yr- This setting was recently named "Transductive Online Learning" (Hanneke et al. 2024] and the minimax rates in both the realizable and agnostic setting have been established [Ben-David et al.) 1997 Hanneke et al. 2023). For the remainder of the paper, we will use offline and transductive online learnability interchangeably.
For randomized offline learner B, we let
T
T
RB H) = sup sup ELTEXT U ELE
E
1 [B (Ix) $ v1
inf HEH
1 [(((z))
# vi
denote its minimax expected regret and
MT(T, H) = sup sup HETTTT
E Σ
( h(xz))
denote its minimax expected mistakes. We use the notation B to indicate that B was initialized with the sequence F1.r before the game begins. If MB (T, H) o(T)) or Rs(T, H) oT)), then we say that B is a no-regret offline learner. It turns out that realizable and agnostic offline learnability are equivalent (Hanneke et al. 2024]. That is, Ms (T, H. oTT + Rs(T, H) o(T). Thus, say class H. C y is offline learnable if and only there exists a no-regret offline learner for H.
When | = 2, Ben-David et al. 1997] and Hanneke et al. 2023 show that the finiteness of combinatorial dimension called the Vapnik- Chhikk-Chhrvoneniis (VC) dimension (or equivalently PAC
learnability) is sufficient for offline learnability (see Appendix A for complete definitions).
Lemma 2.1 (Ben-David et al. 1197], Hanneke et al. (2024] ). For every H. S 10,1 there exists a deterministic offline learner B such that
Ms(T, () = O (og))) log, 7)
where VC(H) is the VC dimension of
In Section 3 we use this upper bound in Lemma 2.1 to prove that PAC Icarnability of H. implies (H, Z) online learnability when Z is predictable. Interestingly, Hanneke al. [2024) also establish a trichotomy in the minimax expected mistakes for offline learning in the realizable setting. That is, for any H. S y with | < oo, the quantity Mg(T (T, H) can only be O(1), O(lgg T), or ( On the other hand, in the agnostic setting, (T, H) can be ((VT) or O(T), where θ hides poly-log terms in T.
Our main result in Section shows that offline learnability is sufficient for online learnability under predictable examples. The following technical lemma will be important when proving so.
Lemma 2.2. (Ceecherini-Sileertten et al. 2017, Lemma 5. 1.] Let g Z + R4 be a positive sublinear function. Then, g is bounded from above by a concave sublinear function f R4 + R4

---

In light of Lemma 2.2 we let f denote the smallest concave sublinear function upper bounding the positive sublinear function f. For example, our regret bounds in Section will often be terms of M3(T, H). Although in full generality M&(T H) I Mg (T, H), in many cases we have equality. For example, when D 2, the trichotomy of expected minimax rates established by Theorem 4.1 in Hanneke et al. [2024] shows that MT(T, ( H) = MR (T, H).
3 Adaptive Rates in the Realizable Setting
In this section, we design learning algorithms whose expected mistake bounds. given black-box access to a Predictor and offline learner B, adapt to the quality of predictions by P and Our main quantitative result is stated below.
Theorem 3.1 (Realizable upper bound). For every H S yxx Predictor P, and no-regret offline learner B, there exists an online learner such that for every realizable stream (I1,91), U1), (IT, yr), A makes at most
L(H) (1)
(Mp(21a) 1) (T(,,H) 6 ((MP(or))) + +1) Mg
Mp +1 + 1, +,71 loga 7)
T
+log)
+
(66)
(1is)
mistakes in expectation, where L(H) is the Littlestone dimension H.
We highlight some important consequences of Theorem 3.1 Firstly, when Mp(x1:)) = 0, the expected mistake bound of AA matches (up constant factors) that of the offline learner B. Thus, when Mp(11:)) = 0 and B is a minimax optimal offline learner, our learner A performs as well as the best offline learner. Secondly, the expected mistake bound of A is always most 3 L(H) + 5; the minimax worst-case mistake bound up to constant factors. Thus, our learner A never does worse than the worst-case mistake bound. Thirdly, the expected mistake bound of A gracefully interpolates between the offline and worst-case optimal rates as a function of Mp (x1:T) In Section 3.3 we show that the dependence of AA's mistake bound on MP(TLT) and Ma(T, H. can be tight. Lastly, highlight that Theorem 3.1 makes no assumption about the size of y
With respect learnability, Corollary 3.2 shows that offline learnability of H is sufficient for online learnability under predictable examples.
Corollary 3.2 (Offline learnability For every H C yd and Z C X",
- Realizable Online learnability with Predictable Examples).
Z is predictable and H. is offline learnable
(H, 2) realizable online learnable.
This follows from slight modification of the proof of Theorem 3.1 along with the fact that the term T
=(T) (T, 2) + 1)MB Mo(T.2)41 7)= o(T) when Mg (T, H. = (T) and (T, Z) = oT)). In
addition, can also establish quantitative version of Corollary 3.2 for VC classes.
Corollary 3.3. For every 7 C f0, 1}x, Predictor P and Z X", there exists online learner A such that
MA (T, (T, (CCC))))(T..)+++)))) -
T
+ logg T T)
Mp 2) +
We prove both Corollary 3.2 and 3.3 in Appendix C Corollary 3 shows that PAC learnability implies
online learnability under predictable examples. Moreover, for VC classes, when Mp (x = 0, the upper bound in Corollary 3.3 exactly matches that of Lemma 2.1 An analogous corollary in terms of
the Natarajan dimension (see Appendix A for definition) holds when [ < co.
The remainder of this section is dedicated to proving Theorem 3. The proof involves constructing three different online learners, with expected mistake bounds (i), (ii), and (iii) respectively, and then running the Deterministic Weighted Majority Algorithm (DWMA) using these learners as experts [Arora et al.) 2012]. The following guarantee DWMA along with upper bounds (i), (ii), and (iii)
gives the upper bound in Theorem 3.1 (see Appendix D for complete proof).
7

---

Lemma 3,4 (DWMA guarantee [Arora et al. 2012 ). The DWMA run with N experts and learning rate 17 = 1/2 makes at most ( M.; log2 N) mistakes, where M, the number of mistakes made by expert E [M].
The online learner obtaining the upper bound L(H)) is the celebrated Standard Optimal Algorithm [Littlestone] 1987 Daniely et al., 2011], and thus we omit the details here. Our second and third learners are described in Sections 3.1 and 3.2 respectively. Finally, in Section 3.3 we give lower bound showing that our upper bound in Theorem 3.1 can be tight.
3.1 Proof of upper bound (ii) in Theorem 3.1
Consider a lazy, consistent predictor P. Given any sequence of examples 31. X²", the Predictor P makes E N mistakes at some timepoints 4 ...... le E [T). Since P may be randomized, both and l1y...;4 le are random variables. Crucially, since P is lazy, for every E {0, + 1}. the predictions made by P on timepoints strictly between 4 and 4++1 are correct and remain unchanged, where we take to = 0 and (e+1 = T + 1. This means that round 4, we have that o 11 = -i,,44111 -1-
Therefore, initializing fresh copy of an offline learner B with the predictions Sx, ensures that makes at most M3 (T 44 1, H) mistakes on the stream (It, Mr. )... (fr 11++1-1)- Repeating this argument for all adjacent pairs of timepoints in {ti,... te gives the following strategy: initialize
a new offline learner every time P makes a mistakes, and use B to make predictions until the next time P makes a mistake. Algorithm implements this idea.
Algorithm 3 Online Learner
Input: Hypothesis class H. Offline learner B, Time horizon
Initialize: =0 0
2 for t I....
Receive He from Nature.
Receive predictions Gir from Predictor P such that a1. Z1:1-
if't = or a * xı (i.e. P made a mistake) then Let B be a new copy of B initialized with the sequence at.r and set i + i 1.
7
Query B on example x, and play its returned prediction 9t-
Receive true label from Nature and pass it to B².
9
end
Lemma 3.5. For every H C yx Predictor P. no-regret offline learner B, and realizable stream (T(T, H) mistakes in expectation.
(W1,)),..., (IT, YT), Algorithm makes at most
Proof. Let A denote Algorithm (211, (IT, yT) denote the realizable stream to be observed by A, and lt* E H to be the labeling hypothesis. Let e be the random variable denoting the number of mistakes made by Predictor on the stream and ti.....t te the random variables denoting the time points where 'P makes these errors (e.g. .4.-1 1 F xt.)) Note that t, 2 2 for all i [c]. We will show pointwise for every value of and f1...., Le that A makes most (c + 1) M& (T, H) mistakes in expectation over the randomness of B3 Taking an outer expectation with respect to the randomness of 'P and using the fact that E [c] MM (21.T) completes the proof.
First, consider the case where c= (i.e. makes no mistakes). Then, since is lazy, we have that #f.7 F1.r for every / E [T]. Thus line 5 fires exactly once round t = 1, A initializes an offline learner 13 with T1.7, and A uses 13 make its prediction on all rounds. Thus, makes at most MB(T, H) mistakes in expectation.
Now, let c and .,,.., te be the time points where errs. Partition the sequence 1,... into the disjoint intervals (1, 4 1), (41,..., L/ 1),..,, (te, ..., T). Define to = and lc+1 := T. Fix an i {O....,c} c). Observe that for every j E (14, .... 4++1 1}. we have that d-j di. comes from the fact that P does not error on timepoints f; + .... f - T1, This and is both consistent and lazy (see Assumptions and 2). Thus, line 5 fires on round f,, AA initializes an offline learner B with the sequence d4. GoTT Lt,sta
#t T and A uses B it to make predictions for all remaining
timepoints t,,..., f.1 - 1. Note that line 5 does not fire timepoints 1, t+t L.
8

---

Consider the hypothetical labeled stream of examples (#% h² (2()), ..., (#7, h (Ze,, Vt. )t.)... (Fet 91-1 (#h+1: ht (2 (fh41)) D.... (07, (2
By definition, B', after initialized with ", makes most MB(T 4 1, H) mistakes in expectation when simulated on the stream (# ht (af;)) (1% (iihh"" h (2)))) Thus, makes at most MT, H.) mistakes in expectation on the prefix (22) h²(2)) (e (2 (11 ( (Ie,, ( ... (1 1-1) Since on the interval timepoint 4, A instantiates B with the sequence #/r and proceeds simulate B on the sequence of labeled examples (az,, Ht.), ... (It 1-1 A makes at most Mp(T,, H) mistakes in expectation on the sequence (Ia, yt. ... (1t,41-1, Mt - 1-) Since the interval i was chosen arbitrarily, the above analysis is true for every i {0, (0,...,., ef and therefore A makes at most (c 1) Mg ;H) mistakes in expectation over the entire stream.
3.2 Proof sketch of upper bound (iii) in Theorem 3.1
When Ms(T, H) is large (i.e. S (VVT), upper bound (ii) is sub-optimal. Indeed, if ..., te denotes the timepoints where P makes mistakes the stream TT.T. then Algorithm 3 initializes offline learners with sequences of length 7- 44+1, 1. The resulting mistake-bound of these offline learners are then in the order of - + +. which can be large ff, are evenly spaced across the time horizon. To overcome this, we construct a family & of online learners, each of which explicitly controls the length of the sequences offline learners can be initialized with. Finally, we run DWMA using & as its set of experts. Our family of online learners is parameterized by integers c E (0, --.,,- 1}. Given an input e E (O...., - 1}, the online learner parameterized by partitions the stream into + roughly equally sized parts of size [ and runs fresh copy of Algorithm on each partition. In this way, the online learner parameterized by e ensures that offline learners initialized with time T
1. Algorithm formalizes this online learner and Lemma 3.6, whose proof is in Appendix B bounds its expected number of mistakes.
horizons at most
c+I
Algorithm 4 Expert(c)
Input: Copy of Algorithm denoted IC, Offline Learner B, Time horizon T Initialize: 4; = c+1
for E {I,..., c). to 0, and l641 = T.
for f 1..., do
Let i (0. such that t { 1,.., 1,...,.4411 1.
ift + then
copy of K. initialized with time horizon 4,41 i and new copy of B. Receive I, from Nature.
Let K.; be
Receive predictions ~ from Predictor P such that ai.. = F1d-
Forward ze and at f,+1:d.41 to KC, via Lines 2 and 3 of Algorithm respectively.
Receive Úr from Kc; via line 6 in Algorithm 3 and predict ÿt. Receive true label and forward it to KG; via line in Algorithm)
10
11 end
Lemma 3.6 (Expert guarantee). For any H. C y*, Predictor P, and no-regret offline learner B, Algorithm 4 given as input e E (O..... 1). makes at most
(Mp(z1T) + c+ 1)M6
c c+1 + 1, H.
mistakes in expectation on any realizable stream (x1, 11), (IT, yr).
Note that when e and Mg (T,H) Ms (T, (H),,, this bound reduces to the one Lemma 3.5 up to constant factor. On the other hand, using c = (x1:r)] gives the upper bound
T
2(M((11:)) 1)Mg
+ 1,7).
+ Since contains an Expert parameterized for every E (O,..., T 1). there always exists an expert (( E initialized with input [Mp(I1T]] Running DWMA using these set of experts
Mp(X1T))

---

Algorithm 5 Online learner
Input: Hypothesis class H. Offline learner B, Time horizon T
For every E {0, (O,.... T 1} let Eg denote Algorithm parameterized by input 6. Run the DWMA using {Eb (E.............. 1) over the stream (æ1; y1), .... (2T2, yr).
on the data stream (I1, /1 ...., (IT, yr) ensures that our learner does not perform too much worse than E [[Mp(s1r]]- Algorithm 5 formalizes this idea and Lemma 3.7 is proved in Appendix B
Lemma 3.7. For every H y Predictor P, and no-regret offline learner B, Algorithm makes at most
6 (MP(FL)) + 1)MB Mp(IIT) +1 + 1, H. log2 T
mistakes in expectation on any realizable stream (T1.31)...., (FT,
3.3 Lower bounds
it is natural ask whether the upper bounds derived in Section 3 are tight. A notable feature in upper bounds (ii) and (iii) is the product of the two mistake bounds Mp (Z1:7) and MB(T, Ht). Can this product can be replaced by a sum? Unfortunately, Theorem 3.8 shows that the upper bound Theorem 3.1 can be tight.
In light of Theorem 3.J
Theorem 3.8. Let X'
[0, (+),)) = = 1}. and H. = fz + 1(x I a}1(x + +}}- Let T. E IN be such that + 1 divides T and T n+I + 2 for some is N. Then, there exists Predictor P such that for every online learner A that uses P according to Protocol there exists realizable stream (I1,31): (IT, such that Mp(IL.T) = n but
Σ ((A())) + vod
(n +
T
log2
2
n n+11
Theorem 3.8 shows that the upper bound in Theorem 3.1 is tight up to an additive factor in log, T because Lemma 2.1 gives that infg MT(T, H)) = O(VC (PC((H))) (H) logz 7) and VC(H) = 1. The proof of Theorem 3.8 is technical and provided in Appendix E Our proof involves four steps. First, construct class of streams 2, S X Then, using Zn, we construct deterministic. lazy, consistent Predictor P such that P makes mistakes exactly on timepoints { ( 1, a+I 1] for every stream T1.7 Z,, Next, whenever 21:7 E Zn. establish an equivalence between the game defined by Protocol [2 when given access to Predictor and Online Classification with Pecks, a different game where there is no Predictor, but the learner observes the next
nf
T n+I examples timepoints
t {1,
T x+I + 1,
1}. Finally, for Online Classification with Peeks, we give a strategy for n+I
nT
Nature such that it can force any online learner to make (n+1) log,(
mistakes in expectation while -=1 1 (1( o y.) = 0. A key
ensuring that its selected stream satisfies 31.7 2n and inf D component of the fourth step the stream constructed by [Hanneke et al. 2024 Claim 3.4] to show that the minimax mistakes for classes with infinite Ldim is at least log, T in the offline setting.
Remark. Although Theorem 3.8 is stated using the class of one dimensional thresholds, it can be adapted to hold for any VC class with infinite Ldim as these classes embed thresholds (Alon et al. Theorem 3].
2019
4
Discussion
In this paper, we initiated the study of online classification when the learner has access to machine- learned predictions about future examples. There are many interesting directions for future research and we list two below. Firstly, we only considered the classification setting, and it would be interested to extend our results to online scalar-valued regression. Secondly, we measure the performance of a Predictor through its mistake-bounds, When X' is continuous, this might be an unrealistic measure of performance. Thus, would interesting to see whether our results can be generalized to the case where X is continuous and the guarantee of Predictors is defined in terms of Ê losses.
10

---

Acknowledgments and Disclosure of Funding
VR acknowledges the support from the NSF Graduate Research Fellowship Program.
References
Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice. Advances in Neural Information Processing Systems, 34:4661-4613 2021.
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private pac learning implies finite littlestone dimension. In Proceedings of the 51 Anmual ACM SIGACT Symposium Theory of Computing, pages 852-860, 2019.
Antonios Antoniadis, Christian Coester, Marek Eliáš, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM Transactions on Algorithms, 19(2):1-34, 2023.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta- algorithm and applications. Theory of computing, 8(1):121-64, 2012.
Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning aug- mented algorithms. Advances in Neural Information Processing Systems, 33:20083-20094, 2020.
Shai Ben-David, Eyal Kushilevitz, and Yishay Mansour. Online learning versus offline learning. Machine Learning, 29:45-63, 1997.
Shai Bev-Da Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In COLT, volume 3, page 1, 2009.
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy statistical learning. In Conference on Learning Theory, pages 1716-1786. PMLR, 2022.
T. Ceccherini-Silberrsiee M. Salvatori, and E. Sava-Huss. Groups, Graphs and Random Walks. London Mathematical Society Lecture Note Series. Cambridge University Press, 2017. doi:
10.1017/9781316556571
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Justin Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pages 3583-3602. PMLR, 2022.
Amit Daniely, Sivan Sabato, Shai Ben-Davine and Shai Shwarr. Multiclass learnability and the erm principle. In Sham M. Kakade and Ulrike von Luxburg, editors, Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 207-232, Budapest, Hungary, 09-11 Jun 2011. PMLR.
Marek Elias, Haim Kaplan, Yishay Mansour, and Shay Moran. Learning augmented Leaming-augmentedd algorithms with
explicit predictors. arXiv preprint arXiv:2403.0741.. 074113, 2024.
Jon C Ergun, Zhili Feng, Sandeep Silwal, David P Woodruff, and Samson Zhou. Learning-augmentel k-means clustering. arXiv preprint arXiv:21 14094, 2021.
Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In International Conference on Machine Learning, pages 2319-2327. PMLR, 2019.
Nika Haghtalab. Foundation of Machine Learning, by the People, for the People. PhD thesis, Carnegie Mellon University. 2018.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differ- entially private learning. Advances Neural Information Processing Systems, 03:9203-9215, 2020.

---

Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari. Multiclass online learning and uniform convergence. Proceedings of the 36th Anmual Conference on Learning Theory (COLT), 2023.
Steve Hanneke, Shay Moran, and Jonathan Shafer. trichotomy for transductive online learning. Advances in Neural Information Processing Systems, 36, 2024.
Chen-Yo Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In International Conference on Learning Representations, 2019.
Shaofeng H-C Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang. Online facility location with predictions. arXiv preprint arXiv:21 10.08840, 2021.
Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 international conference on management of datu, pages 489-504, 2018.
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859-1877. SIAM, 2020.
Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In Interna- tional Conference on Machine Learning, pages 13431-13440. PMLR, 2022.
Nicholas Littlestone. Mistake bounds and logarithmic linear- thres-th learning algorithms. Univer- sity of California, Santa Cruz, 1989.
Nick Littlestone. Learning quickly when irrelevant attributes abound: A new lhnear-threshold algorithm. Machine Learning, 2:285-318, 1987.
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1-25, 2021.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65(7):33-335 2022.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 24, 2011.
Vinod Raman, Unique Subedi, and Ambuj Tewari. The complexity of sequential prediction in dynamical systems. arXiv preprint arXiv:2402.0666 16611, 2024.
Tim Roughgarden. Beyond the worst-case analysis of algorithms. Cambridge University Press, 2021.
Ziv Scully, Isaac Grosof, and Michael Mitzenmacher. Uniform bounds for scheduling with job size estimates. arXiv preprint arXiv:21 10. 10.00633, 2021.
Daniel A Spielman and Shang Hua Teng. Smoothed analysis: attempt to explain the behavior of algorithms in practice. Communications of the ACM, 7-610) 2009.
Shufan Wang, Jian Li, and Shiqiang Wang- Online algorithms for multi-shop ski rental with machine learned advice. Advances in Neural Information Processing Systems, 33:8150-8166 2020.
Alexander Wei and Fred Zhang. Optimal robustness-coossiseengg trade-offs for learning- seamminng-uummnneed online algorithms. Advances in Newral Information Processing Systems, 33:8042-8055. 2020.
Changlong Wu, Ananth Grama, and Wojeiech Szpankowski. Online learning in dynamically changing environments. In The Thirty Sixth Annual Conference on Learning Theory, pages 325-358. PMLR, 2023.
12

---

A Combinatorial dimensions
In this section, we review existing combinatorial dimensions in statistical learning theory. We start with the VC and Natarajan dimensions which characterize PAC learnability when [J]| = 2 and |)] < respectively.
Definition 3 (VC dimension). A set (. Fnd ah E H, such that Vi E [nt] h((x:) y/- The VC dimension H, denoted VC(H), is defined as the largest natural number n. E N such that there exists a set {21, Fn E X that is shattered by H. Definition& 4 (Natarajan Dimension). A set S = == Ta. is shattered by a multiclass function class H S yx if there exist two witness functions f,g: i [d]. for every {0, {0,1]4 there exists function ha E. H such that for all [d], have
is shattered by H. if Vyr..... On E {0. 1}.
y such that (xxx) + g(x;) for all
h1(r)) ( (f(a.) ifa = (g(z)) =0
The Natarajan dimension of H. denoted ((H), is the size of the largest shattered set S S X. If the size of the shattered set can be arbitrarily large, we say that N(H) = 0c.
We note that N(H) = VC(H) whenever | = 2. Next, we move to the online setting, where the Littlestone dimension (Ldim) characterizes multiclass online learnability. To define the Ldim, first define a Littlestone tree and notion shattering.
Definition 5 (Littlestone tree). A Littlestone tree of depth d is complete binary tree of depth d where the internal nodes are labeled by examples of X and the left and right outgoing edges from each internal node are labeled by 0 and respectively.
Given Littlestone tree T of depth d, root-to-leaf path down T is a bitstring a E {0, 1] indicating
whether to go left (a, = 0) or to go right (a, = 1) at each depth E [d]. A path a E 1 down T gives a sequence of labeled examples {(x,, ] where I; is the example labeling the internal node following the prefix (01, (01...., down the tree. A hypothesis h H shatters path In other words, h is consistent with the labeled examples when following a. Littlestone tree T shattered by H for every root-to-leaf path down T, there exists hypothesis ha E H. that shatters it. Using this notion of shattering, define the Littlestone dimension of a hypothesis class.
E {0. 1),, if for every E [d]. we have hr;));
Definition 6 (Littlestone dimension). The Littlestone dimension H. denoted L(H), is the largest e N such that there exists a Littlestone tree T of depth d shattered by H. If there exists shattered Littlestone trees T of arbitrary depth, then we say that L(H)) ac.
Finally, the following notion of shattering is useful when proving the lower bound in Appendix E Definition 7 (Threshold shattering). A sequence (I1,..., 2.ke) 2 is threshold-shatten by H. C
{0, 1)x if there exists (hi,..,, hs) E H* such that h₂(x;) 1 < i) for all i, E [K].
B Proof of Lemmas 3.6 and 3.7
Proof. (of Lemma 3.6) Let (x1, y1), (2T, yr) be the realizable stream be observed by the Expert. For every (0. .... c). let m, be the random variable denoting the number of mistakes made by P rounds { + 1.., } J. Recall that by = 0 and (.41 = T. Let M = Ei= m, be the random variable denoting the total number of mistakes made by P on the realizable stream. Finally, let A denote Algorithm Observe that,
T
i
E
Σ
((A(z)) # 4.
E
1(A(z)) # #
(=ī++
i4
IE
Σ
Σ
1(K+(x)) 4 vr
i=0
+1
< E
(m: + 1)M - Es. 71)
13

---

where the first inequality follows from the guarantee of K. and Lemma 2.2 Using Jensen's 's inequality. we get that
Σi=o (m; + (1)(1++1-1 H
F
Σ (ma + 1)MB((++1 - 7,, H1)
S TF
Σ ms +1) M8
Σizo( (m; +1)
(m, + 1f(4++1 - H
M + 1) 1)
IB
M c c
Li=D my Ei=omi m;(1++1 - [1)) T
E
M +M+c+1 1)
MB
71
M + c
0= mi (1 + +T H.
E
M + + 1)
C-1
M Mc++1
M +T
BB
M (M+
C-1
M M+c+1 H
Using the fact that
T
S
T c+1
+ 1, have
c+1
c m,
MT + M + T
MB(E441 - E, H)
$ E
M [M+++1) 1|
c+1
M +c+1 H.
==
T
E
(M+++1) 1)
c+1 + +1
T c+1 + +17
(Mp(217) (Mo(2in)+c+
which completes the proof.
Proof. (of Lemma 3.7) Let (21, vI), (ZT, yT) be the realizable stream be observed by the
learner. Let A denote the online learner in Algorithm 5 By the guarantees of the DWMA, we have
E
1(((z) # ve
< 3E
inf bE(O......
1 1(Es(x)) # yc} Σ 1=1
+ +llog2 T
-1}
$ 3E
((( # vi
+ +olog T
T [M
3(Mp(Zur) [Mp(Eer]] 1)MB
+ 1, -3 3log2 T
T
< 6(Mp(zIT) + 1) Mp(11.) -1
+ 1, +6 logg
where the last inequality follows from Lemma 3.6 and the fact that Mp(rir)) S [Mp(a1T)] < (p(2 +1.
C Proof of Corollary 3.2 and 3.3
Using Theorem 3.1 we first show that for every H C y Predictor P, S X', and no-regret offline learner B, we have that
inf (T, H. 2) (100 (M.
(M) ( Mg
Mp (T, Z) + H1 127 +log, )
T
14

---

Proof. It suffices to show that Algorithms and have mistake bounds D( 2) + 1) MT(T, H)) and (M,(T. + Mg
MT (T,22) +1+1 H) log, T respectively, To see that
Algorithm 3 mistake bounds is (MMp (T, 2)
1) (T, H)), note that Mp(21:7) - Mp(T.
for every æ1.T E 2. To that Algorithm 5 expected mistake bound is O (Mp(T,
1) Mg
T (p( H. logg follow the exact same proof strategy in the proof of Lemma
3.7 but picking a different expert when upper bounding the expected number of mistakes. Namely, following the same steps in the proof of Lemma 3.7 we have that
(A(x,) + yo3
3
Σ (1E((x)) + vo + 3 log, T BE (0. T-11)
inf
where A denotes Algorithm 5
Picking
[M, 2)1, using Lemma 3.6 and the fact that
Mp(X1.) I (T, 2) gives the desired upper bound on Σ 1 {A(xx)) * vel of
H)) + log, T + MP 2) + 177
T
completing the proof.
Corollary 3.2 follows from the fact that the upper bound inf M (T,, H. 2) is sublinear whenever
(T 2) 2)= o(T) and Mg(T, , H) = o(T). To get Corollary 3.3 recall that by Lemma 2.1 there
exists an offline learner B such that
Ms(T. 7) = o (VVC(H)) log.
Plugging this bound into upper bound 1 completes the proof.
D Proof of Theorem 3.1
Let AA denote the DWMA using the Standard Optimal Algorithm (SOA), Algorithm and Algorithm as experts. Then, for any realizable stream (I1, 81), B1).... (IT, (r).yr)))).. Lemma 3.4 gives that
Σ (((xt)) + 3e S 3IE
min M₁ + log, 3 [EE(3
< 3 min x
[M,] + 5,
where we take Mj. M2 and Ms be the number of mistakes made by the SOA, Algorithm 3 and Algorithm prespectivvll Note that M2 and M3 are random variables since B and P may be randomized algorithms. Finally, using Lemma 3.5 Lemma 3.7 and the fact that the SOA makes at most L(H) mistakes on any realizable stream Littlestone 1987 completes the proof of Theorem
Proof of Theorem 3.8
X'= R U {+} and H = {z 1f S a)1(z * x}}. Let N be chosen such that T' is multiple of n + and n+I +1= = 2* for some k E N. Our proof of Theorem 3.8 will be in four steps, as described below.
T
(1) We construct a class of streams 2, C X'.
(2) Using Zn, we construct deterministic, lazy, consistent Predictor such that P makes mistakes exactly timepoints { .... of 1} for every stream F1. E Zn.
15

---

(3) When F1.T E 2n, we establish an equivalence between the game defined by Protocol 2 when given access Predictor P and Online Classification with Peeks, different game where there is no Predictor, but the learner observes the next n+I examples timepoints
E (1,
++1 1,... x+1 + 1}.
(4) For Online Classification with Peeks, we give a strategy for Nature such that can force any online learner make (n+1) log2 RET) mistakes in expectation while ensuring that the stream of labeled examples it picks (I1, (IT, yr) satisfies the constraint that F1.r E 2, and Anf E (1(x))) ye) =0
?
Composing steps 1-4 shows the existence of a Predictor such that for any learner A playing Protocol using P. there exists a realizable stream where makes at least (n+1) log2( n-1 mistakes in expectation.
Step 1: Construction of 2,,
Let S be the set of all strictly increasing sequences of real numbers in (0, 1) of size n+111 Fix function f IR² -> S which, given < b E RR, outputs element of S that lies strictly in between and b. For example, given
E R, the function can output evenly spaced real numbers of size n+1 Let Dyd S + XTII be a function that reorders the input S E S in Dyadic order. Namely, if (NN,,,,N)) where + 2 for some k N, then Dyd(S) is
T
x x x Tay 2t g. Eay Faa, Ti (2
2
See the Proof of Claim 3.4 in Hanneke et al. (2024) for more detailed description of a Dyadic order. On the other hand, let Sort x44 + be function that reorders its input in increasing order. Let J = {1, .... n+T + 1 be the set of all sequences of indices of length at most n taking values in {1, .... n + 1}. For the remainder of this section, we will use S, denote the ith element in sequence S E S. Moreover, for any two sequences S S E S, we say S < S2 if S/ss < ST. That
is, S < S2, if 5 lies strictly to the left of $2.
Algorithm Stream Generator (SG)
Input: 5 E S, Jim J Initialize: ag = 0, 60 = 1
for i 1, ..., 77 do
if j, = then
S + f(a;-1, S
a; 0:-1
b: -S-- S(-1
else if j; a+i
+ then
5, + S(S
b-n)
a Si-1
10
6; + b-1
else
S (1
12
13
0 - 5
14
S
15
end
end
Return: Dyd(S") o ... Dyd(Sm))
We will construct stream for every sequence jum E J. m S n, algorithmically as follows. Fix 5 = f(0, 1) E S and let SG denote Algorithm 6 Let
2, = (S ..im)) From E J, m E (1, [1,..,n1}
16

---

denote the stream class generated by applying SG to inputs S and j1:m for every J1:m E J. m. S n. We make four important observations about Zn, which we will use construct a Predictor that can reconstruct St given 5 and the first example of the block 5
Observation 1. For every sequence 21. E Z, we have that z I
Dyd(5").
The first observation follows from the fact that the same initial sequence 5 is used to generate every stream in 2n,
Observation 2. For any pair P. E I and mn S n, fl.m = jm then SG((S) ; = SG(S", (tmm)
The second observation follows from the fact that SG is deterministic.
Observation For every F1.T E 2n such that æ1.T := SG .Jim) Dyd(S") o ... Dyd(S")) the index ji can be computed exactly using only S and S for every i E [m]]
To see the third observation, fix some 21.7 E Zn Then, there exists sequence S ..... S that æ1:T = Dyd(5") o Dyd(S")) as well as a sequence (Ag, bo), (a,, b,,) In addition, there exists a J1.m J such that Fı.r = SG(S", fim)). ). Fix i [m] and consider S' and S By definition of Algorithm 6 there exists an index y E (1,..., a+I + 1} such that S = ( : S where we take 5 a and S² *+1 +1 1 We claim that the index is unique. This follows from the
such
क is pairwise disjoint since a; S S <... s'=! < + 1 Finally, we claim that 5 and the element S identifies the index q. This M*I
fact that the collection
follows because (a,-1, Si-)) < [(S S
< S(S -1. < J(S b,_1) and n+l
thus is the smallest index p E {I,..., n+1 such that S < Sp- exist.
and n+I + 1 such p does not
o o... Dyd(5 SG(S jimm). For Observation 4. Fix sequence fuan I and let Dyd(S every i, E [n] such that i < p. we have that:
(i) S < = 1; 1;
(ii) S <S) 1f T: n+1*
(ii) S SD if
n+1 +1.
The fourth observation follows from the fact that for every i E [n] and index ji {1,
ntT +1},
T
the remaining sequence of sets gi+1 ,.... 5 Sth all lie the interval (S), S..) by design of Algorithm 6 where again we take 5 a:-1 < Si and S gi-1
+ = b S
Step 2: Constructing Predictor for Z,
We now show that Algorithm T
7 is lazy, consistent Predictor for Z, that only makes mistakes at timepoints { 1 + 1, I,..,
af 1}.
a+1
Lemma E.1. For any sequence F1.T Zno Algorithum T
7 is lazy, consistent Predictor for 2n that of
only makes mistakes at timepoints { (44I + +1, 1,,...
n+I
Proof. Let P denote Algorithm 7 and FI. E Zn. Then, there exists S1 ..... Sth E S and sequence of indices J1.m E I such that Fi.T = Dyd o Dyd(S²) o o Dyd(5") = SG( fjim).
We now prove that P makes mistakes only timepoints (.ITT + +1, I,,.. n=I 1) and where else. Our proof is by induction using the following inductive hypothesis. For every i {1...., n). we have that P:
(i sets J1a jus round
iT n+1
+
1;
ii makes mistakes rounds
T
+ 1,
2T
IT + 1) and no where in between.
17

---

Algorithm/ 7 Predictor for 2n
Input: 2n Initialize: J= for t 1,.., do
Receive It if then
Set 8 = Dyd(S") o 2 #* +I: where 2 --1 +11 (+,..,,*))
11 else if t = n+1 + for some i {l...., then
Let S = Sort( -t--- be the last #FT examples sorted in increasing order.
Find the smallest j {I,.... mt1) such that Ia < Sj. If no such exists, set Update J + j.
T n+1 + 1.
10
Set $1. SG J) o l I where eet I (*)....,
11
else
12
Set a'. + 11TT
13
end
14
Predict $1.7.
end
For the base case, let i 1. does not make any mistakes in {1, n since knows S using Zn, computes 1: #FI Dyd(S") in line 5, and does not change its prediction until round er n+1 + 1 based on line 6. At time point ( n+I + 1, P makes mistake since //11 + Ttz Moreover, using Observation 3 the index j E {l..., } computed in round & on line matches ji. Thus, we have that J1 J1- This completes the base case.
T
Now for the induction step, let i E (2....,n) n). Suppose that the induction step is true for i This means that P:
sets J1.-1 = J1:-1 on round
(i-1)T n+1 + 1;
(ii) makes mistakes on rounds
T
+ 1,
27 n+1
(111)T n+1
+ 1) and no where in between.
We need show that P sets J, = J: on round n+I 1, makes no mistakes between (i-1)7
+
*+1
and x+1* but makes a mistake
(2' At timepoint f (6-1)7
n+1 +1, computes J/-1 = ji-1
n+1
(by assumption) and thus sets a 1.T
f4-1 SG(S0, J1:-1) = SG (J1.... Ji-1)) = Dyd(
o Dyd(S using Observation 2 Therefore, P predicts on round 4--1 the sequence "/:7'' if "1 o (*,,..,+)) +), implying that P makes no mistakes for rounds (6-1)T + 2.... nFI since it does not change its prediction until round IT SI mistake on round t; x+1 + 1. Finally, by Observation 3 the example F4, and the previously :T' observed sequence 21,-1:f--1 gives away ji, thus P sets J, Js line 8 in round n+1 +1. This completes the induction step and the proof of the claim that P only makes mistakes on timepoints ( 1,.., xf 1+1 + 13. To see that P is lazy, observe that by line 12, P does not update its prediction on rounds in between those in T + 1,..., nf nT
*, P makes a+1 1 by line 12. However, since a
#FT 1]. J. To see that P. is consistent, note that P uses prefixes of j1,..., Jn, S and SG to compute its predictions in line 10. Thus, consistency follows from Observation
Step 3: Equivalence to Online Classification with Peeks
For any stream F1.7 Zn. having access the Predictor specified by Algorithm 7 immlies that nT n+I }. the learner observes predictions & where Via-1 -1:-11
every / E {1, n+i + 1,
gl
Fest - and de c+ + +1T
(K...., *). Accordingly, the timepoints
{1, n
bit
ItI af
1.
+ 1}. the learner observes the next n+1
examples Frat T. in the stream, but learns wil
n+1
18

---

nothing about the future examples 2+ +1T In addition, for timepoints in between those in n-I + 1}. the learner does not observe any new information from P since by line 12 T
{1, n+I + +1, L..... n7
T
aT + 1} and r {I,... x+ }}. As Algorithm 7 Gi.r = 1 for every E {1, n+I + I,... n+1
result, whenever 21.7 E Zn 2 with the Predictor specified by Algorithm 7 is equivalent to the setting we call Online Classification with Peeks where there is no Predictor, but the learner observes the next 1-1 examples exactly timepoints i (1, x+I + ,,,,, n+1 + 13. Indeed, by =T
T having knowledge of the next n+I examples exactly timepoints / E {1, R+I + 1,, ..... n+I + 1). a learner for Online Classification with Peeks can simulate a Predictor that acts like Algorithm 7 Likewise, learner for Online Classification with Predictions can use Algorithm 7 7oo simulate an adversary that reveals the next n+1 I examples exactly at timepoints E {1, T
T
nf ,.... a+1 + 1}.
Accordingly, we consider Online Classification with Peeks for the rest of the proof and show how Nature can force the lower bound in Theorem 3.8 under this new setting.
Step 4: Nature's Strategy for Online Classification with Peeks
Let A be any online learner and consider the game where the learner A observes the next n+I 1 nT.
examples timepoints (1, .+I + 1, .... n+I + 1}. We construct hard stream for A in this setting. We first describe a minimax optimal offiiee strategy for Nature when it is forced to play a sequence of examples
T
sorted in Dyadic order.
Algorithm 8 Nature's s Minimax Offline Strategy
Input: S (S) for some S E S, Version space V S {0, 1)
Initialize: 1
Reveal S to the learner A.
for f. 1,.,, n+I do
Observe the probability P. of A predicting label 1.
pr 2 1/2 then
If there exists h V, such that h(xe) = 0, reveal true label 1/2 0. Else, reveal y: 1. else
If there exists h V, such that h(x))) = 1, reveal true label 1/2 1. Else, reveal y/: 0. Update Vi+1 = (h E V h(x;)= y.)
end
Return: True lahels yı . Version space
Lemma E.2. For any learner A, S DS)( and Version space V S (0, 10, Algorithu forces A to make at least 1 logg( (2+1) mistakes in expectation if hhresholdsshatered (Definition by V.
Proof. The lemma follows directly from Theorem 3.4 in Hanneke et al. 2024
For the definition of threshold-shatteringg see Appendix A Note that for every input Š = Dyd(S) and V C {0, 1) Algorithm 8 its output version space S is non-empty and consistent with the
n=T as long as [V] 0. This property will be crucial when proving Lemma E.4 We are now ready describe Nature's 's strategy for Online Classification with Peeks.
sequence ($1, 31 ).... ($
The pseudocode is provided in Algorithm
We establish series of important lemmas.
Lemma E.3. For every learner A, if (x1,8)), (IT, Wr) is the stream the output of Algorithm when playing against A, then F1rr E Zn.
Proof. Fix a learner A and let (#1,81), ..., (IT,9T) denote the output of Algorithm playing against A. Let Jio denote the sequences of indices output by Algorithm 9 Then, since SG deterministic. by line 6-7 in Algorithm we have that F1.7 = SG(S", (ji, E Zn.
Lemma E.4. For every learner A. if (x1,))) ..., (XT, (xT.yTT) is the stream the output of Algorithm when playing against A, then (I1, (ØT, yr) is realizable by H.
19

---

Algorithm 9 Nature's Strategy for Online Classification with Peeks
Input: Learner A, Hypothesis class H Initialize: 1/1 = for i I,.., n + do
if then
Set 11: - Dyd(s") and reveal it the learner A.
else
Compute 5 = SG(S), (ii,...,---)))) Let 1.T +1: fr
be the last T examples in S and reveal it to the learner A.
Play against A according to Algorithm 8 using Te D1 +1: and version space V,- n11 WII
Let y (--11 +1" vz be the returned labels and Vi+1 V2 be the returned version space. w11
10
Let y u- +1" m+1
be the sequence of true labels after sorting
(I +1 y لببيي +1) i
(x =r nFI
WF1
11
in increasing order with respect to the examples.
12
ū e = then
Set T x+1 1.
13
else
15
Set j. to be the smallest p {1,..., n+1
T
such that ua-1 0.
#+1 +p
end
17
Return: Stream (11,81),,.,, (IT, Wr), indices jien. and version spaces Vi,... Vn42-
Proof. Fix learner A and let (I1, U1), (ZT, yr) be the output of Algorithm when playing against A. Let .., V2 be the sequence of version spaces output by Algorithm to show that Vn+2 is not empty and is consistent with (æ1, vi), .... (CT,YT), Our proof will be by induction using the following hypothesis:
suffices
Vi+1 non-empty and consistent with the sequence ). For the base case, let i = 1. Then, by Algorithm 8 line 8 in Algo-
(21, (x 3/ n+1
n+1
rithm and the fact that |V1 = 77| > O, we have that [V/ > O and V22 is consistent with 12 91 yi..... TT_T_ v ). Now consider some i and suppose the induction hypothesis is true for i 1. Then, we know that [V] > 0 and V& is consistent with (1), (Ø ((--1 (u-nr)
Again, by design of Algorithm 8 and line 9 in Algorithm 9 it follows that [Veal >> 0 and Vi+1 consistent with (xr (--
I ....... (x ir
- ST Since Vi+1 S Vg, and V/ is consistent
with (21, (1,.8)).... (-1 V/--1 completing the induction step.
we get that V1+1 is consistent with (x1 (11.)),,... (2
m+11 m01
Lemma E.5. For every learner A, if (I1, (aT1,91).... y1)..., spaces output by Algorithm 9 when playing against A, then for every E {I,.... 1}, the version space V; meeshold-shateer
(IT, Ur) and Vi...., Vn42 are stream and version
DI #1:
Proof. Fix learner A and let (æ1, Vi), .... (IT, yr) denote the output of Algorithm 9 playing against A. Let jısm and Vi...., Vn+2 denote the sequences of indices and version spaces output by Algorithm 9 respectively. Note that I1.T SG(S" ....).. Moreover, for every E (2....n)) n). I SG(S0, (Ji,..,, (.,,.)..-)))) by lines 6-7.
we have that
Fix an i f1...., n 1}. It suffices to show that the hypotheses parameterized by Za-17 +1: ST belong in V, Our proof will be by induction. For the base case, since V = H. it trivially follows that the hypothesis parameterized by I (--17 +1:,77 belong Vi. Now, suppose that (6
#+1
w+1 +1: a
belong to Vm. for some < i. We show that Vm+1 also contains the hypothesis parameterized by Recall that Vn Vn+11 S Vn is the subset of Vm that consistent with the labeled data
NFT
(m-11T 41 9 (mm-1)r 1)7 +1) .... (I mT mz m41
mt1
nt1
20

---

and is the result of running Algorithm with input version space Vm and sequence I' (m--1 +1: #1: suffices to show that the hypotheses parameterized by 2 (7-17 +1: 141
are also consistent with
(2 (m 1yT 1 ((n 122
mi mT
To show this, recall that im is the index computed in Lines 11-14 of Algorithm 9 on round m. Let
(yT +11 (m- +1
be the sample sorted in increasing order by examples. There are three cases to consider. Suppose jm = then // (m- +1 and it must be the case that (mm-1
mtl +p for all p {2, + }. Since
mil
a+1 entries of I1: mr = SG Jm- 1)), by definition of Algorithm 6 we have that the last
n1T SG(S", (m. )) all lie strictly to the left of (m-12 +1' Moreover, by Observation 4 this true of T +1}.
w+1
the last T entries of SG(S), (f1: Jm 9m+1. 9i-1) for any 9m+1:... 9i-1 E {1..... .... a+1 n+1
Therefore, we must have that (1- eT which are the last x+1 entries of SG(S", (i-.)))...1))
n*1 +1:
lies strictly the left of tm uJ +17 implying that their associated hypotheses output on all of ++1
(2 (m--1) +1 V (im-1)7 +1) ..., (Ir mt V mz) as needed. By symmetry, when jm = n+1 + 1, we have a+1
n+1
"II NTI
lies strictly the right of mJ implying that their associated hypotheses output that x (1-1 +1: m*I
n+1
1 on all of (Ir 1m= +1 (m IiT +1); ..... (x mT y mz as needed. Now, consider the case where
T n+1
n+1
fm E (2,
San and Observation for any qm+l, qi E {l,.... nt + +1). n+I entries of SG(S", (f1..., Im, 9m+1, 9i-1) lie strictly in between ã (m-1ı +jm
... w+I Then, by Algorithm
the last T
-TI and T (m-- -II +jm Thus, the hypotheses parameterized by [1-10 +1: output on examples
I (m--117 (m-1" + +jm-1 and 0 on examples ã (m-111 +5m: mr Finally, note that by definition of Jm. it must be the case that "mm-!!m +1. (m-177 + (1, 1) and ūm--!" +jm: mr = (O,..., 0).
Thus, once again the hypotheses parameterized by x 11-11 +1: mFx
are consistent with the sample
(m 1yT +11 3 (m-117 +1 n+1
This shows that these hypotheses contained in Vm+1, completing the induction step.
Step 5: Completing the proof of Theorem 3.8
We are now ready to complete the proof of Theorem 3.8 which follows from composing E.1
E.2 E.3
E.4 and E.5
Namely, Lemma I and the discussion in Section 15 show that there exists Predictor P. such that for any learner A playing according to Protocol Online Classification with Predictions is equivalent to Online Classification with Peeks whenever the stream (z,. V1), (Ør, yr) selected by the adversary satisfies the constraint that 11.T 2n, Lemmas E..3 and a.d]E..sshov that for any learner A. Nature playing according to Algorithm guaranttes that the resulting sequence (I1, V1), .... (IT, yr) satisfies the constraint that F1.7 E Zn and realizability by H. Thus, for the Predictor P specified by Algorithm
7 and Nature playing according to Algorithm 9 Online Classification with Predictions equivalent to Online Classification with Peeks. Finally, for Online Classification with Peeks, combining Lemmas F.2 and F.5 shows that for any learner A, Nature, by playing according to T Algorithm guarantees that A makes at least lorg! mistakes in expectation every पमI rounds.
Thus, Nature forces A to make at least (m+1) loga game, completing the proof.
T mistakes in expectation by the end of the
F Adaptive Rates in the Agnostic Setting
In this section, we consider the harder agnostic setting and prove analogous results as in Section Our main quantitative result is the agnostic analog of Theorem 3.1
21

---

Theorem F.1 (Agnostic upper bound). For every H. S yx, Predictor P, and no-regret offline learner B. there exists an online learner A such that for every stream (2 vi).... (IT, (eT,yT), A's expected regret is at most
T Mp(xI.)) -
L(H) logg (eT)
(2(Mp(FIT) + Rg
1,H) TTog T
VT.
(16)
With respect to learnability, Corollary 1:2 shows that offline learnability H. is sufficient for online learaailiity under predictable examples.
Corollary F2 (Oftline learnability - Agnostic Online learnability with Predictable Examples). For every H _ yx and 2 S X*,
predictable and is offline learnable = (H, 2) agnostic online learnable.
In addition, we can also establish a quantitative version of Corollary F2 for VC classes. Corollary F.3. For every H C {0, 13x, Predictor P, 2 C X', and no-regret offline learner B, there exists an online learner A such that
R (T, H. - o (0(.2) (((M)(T,))+ (M)(T,2)+1))
vy MT 2)+1 +1 log2 (T, +VToog T)
VC(H)
T
The proof of Corollary F3 is in Section F44 The remainder of this section is dedicated to proving The proof is similar to the realizable case. involves constructing two online learners with expected regret bounds (i) and (ii) respectively, and then running the celebrated Randomized Exponential Weights Algorithm (REWA) using these learners as experts [Cesa- Bianchi and Lugosi 2006). The following guarantee of REWA along with upper bound (i) and (ii) gives the upper bound in Theorem F.
Theorem 3.1 and Corollary F.3
Lemma F.4 (REWA guarantee (Cesa-Bianchi and Lugosi 2006)). The expected regret of REWA
when run with N experts and learning rate 1) 8ln is most minte[N] M, + v Tog, N.
where M, is the number of mistakes made by expert E [N].
The online learner obtaining the regret bound v TTHH) T (eT)(eT) is the generic agnostic online learner from Hanneke et al. [2023) thus we omit the details here. Our second learner is described in Section F2 and uses Algorithm 3 as a subroutine. The following lemma, bounding the expected regret of Algorithm in in the agnostic setting, will be crucial.
Lemma F.5. For every H C y Predictor P. no-regret offline learner B. and stream (21, (i.....,,, (FT, yr), the expected regret of Algorithm is at most (Mp(Iur) + Rg H).
F1 Proof Lemma F5
The proof closely follows that of Lemma 3.5
Proof. Let A denote Algorithm 3 and (#1 31), (IT, yr) denote the stream to be observed by A. Let be the random variable denoting the number of mistakes made by Predictor P on the stream and ..,, te be the random variables denoting the time points where P. makes these errors (e.g #f--1 # J. Note that 4 for all i E [c]. We will show pointwise for every value of and t1, ..,, te that makes at most (c RT(T,, H) mistakes in expectation over the randomness of B. Taking an outer expectation with respect to the randomness of P and using the fact that E [c] Mp (21.T), completes the proof.
First, consider the case where c= 0 (i.e. P makes no mistakes). Then, since P is lazy, we have that ii. 21.7 for every [T]. Thus line 5 fires exactly once round t 1, A initializes an offline learner 33' with 11,7, and .A uses B¹ to make its prediction on all rounds. Thus, A makes at most (T H) mistakes in expectation.
Now, let and (1,-.,, Le the time points where P errs. Partition the sequence 1,... into the disjoint intervals t1, 1), (t1, to 1)..., ...,,, (t,,..,,") T'). Define to = and fc+1 := T. Fix an
22

---

i E {O....,.) c}. Then, for every j E (t,...., f++1 - 1}. we have that 2 1:::+1-1 21. This comes from the fact that p does not error on timepoints & + L...., f and is both consistent and lazy (see Assumptions and 2 Thus, line fires on round 1, A initializes an offline learner B with the sequence t -t o 1 t and A uses B' it to make predictions for all remaining timepoints 4.11 - 1. Note that line 5 does not fire timepoints ( 11.....411
Let h' E arg new Ei=t 1(h(rz) * ye be an optimal hypothesis for the partition (ti,... t++1 1). Let yi ye for t S S t++ and y h'())') for all 2 4441. Then, note that
T
h++1-1
inf (M(2)) # 3
inf MEH ==
Σ
1(((x)) # v.).
NEH
t=
Now, consider the hypothetical labeled stream
(it vi. (d.)... (#17 vrr = (art, Vr.). ... (1 U4441
1), (f (i (e..o)
By definition, B¹, after initialized with 2// makes at most
f+111
inf Σ (h(a)) # vi + RB(T - t4, H.) KEH
inf NEH
Σ [h((r)) + ye) + RRT(T t4, H.
mistakes in expectation when simulated on the stream (# vi,), ,.... (24, v/)) Thus, B makes most hnf 1
(1(x))) # y1 Rs(T 1, 1, H) mistakes in expectation the t: 111- Vi 1-1) = (Zz, Vt.),.., (It -,, -1). Since on timepoint t, A instantiates B with the sequence - and proceeds to simulate B on the sequences of labeled examples (It, Vt.),,..... (Itz+1 1, 11 A makes at most inf Ele 1144111, [h((x) * yr} + Rs(T- - t, + 1.) mistakes in expectation on the sequence (Iz,, Vc.), ..., (Tt 11, M141-1). Since interval was chosen arbitrarily, this is true for every E {O,..., c) and
prefix (#) vt,) ).... (
h+1-1
E
((A(z) F
E
1(A(z)) & ye)
h+11-1
inf Whe
1(h(ze) # v0 Ro(T - t, 1, (.11)
t=f
T
< inf
1(h(z)) + ve + +c++ 1) Rs(T.
NEW
as needed.
F.2 Proof of upper bound (ii) in Theorem F.1
The proof of upper bound (ii) in Theorem closely follows the proof of upper bound (iii) in Theorem 3.1 from the realizable setting. The main idea is to run REWA using the same experts defined in Algorithm 4 and bounding the expected regret in terms of the expected regret of K. from
Lemma F3
We show that Sonniihhjjusinng REWA in line 3 and the experts in Algorithm 4 with their guarantee Lemmal F.5 achieves upper bound (ii) in Theorem F.1 Let (x1, y1), (TT: yr) be the stream to be observed by the learner. Let A denote the online learner in Algorithm using REWA in line 3 of
23

---

Algorithm 5
By the guarantees of the REWA, we have that
B
[((()) & $10
- EE
inf (0 1) 1=1
Σ
1[b((z)) + vo
VT T
EI
L (((M)((n))((()) * #11
+VT /'loo T
[M
< E3
Σ
Σ
1(K((z)) # vo + Togg2
(=,+1
[Mp(21711
E
(m, + 1)Rg(t,+1 - E, H) + inf
E
1(h(z,) # v
/ T
bEH
t=++11
[Mp(117]
<
IE
(m, + 1)Rx((i+1 - -1;, H)
+ inf
Σ
11(())) 41 + /Tlog T
NEW t=1
i=0
T Mp (1
$ inf NEW
Σ
((h(,)) * y. 2(MM + 1)Rg
+ 1, H.) + Tlog2" T,
where the fourth inequality uses the guarantee of K. from Lemma F.5 and the last inequality follows using an identical argument as in the proof of Lemma 3.6 since Rg(2 T. H) is concave, sublinear function of T.
F.3
Proof of Theorem F1
Let A denote the REWA using the generic agnostic online learner from Hanneke et al. [2023 and the algorithm described in Section F2 as experts. Then, for any stream (11,91), m. (TT, VT), Lemma
gives that
T 1 (A(a)) # yi
E
< E
min M 12
+ VT < min E [M]] + VT, 2
where we take Mj and M2 to be the number of mistakes made by the generic agnostic online learner from Hanneke al. [2023] and the algorithm described in Section F.2iionF22pp respectively. Note that Mr and M2 are random variables. Finally, using (Hanneke et al. 2023 Theorem 4] as well as upper bound (ii) completes the proof of Theorem F.
F.4 Proof of Corollaries F22 and
K3
The proof of the generic upper bound on MT H. 2) follows by using the same learner A as the proof of upper bound (ii) Theorem F.1 However, this time we bound
E
inf bE (O.....
E ((E((a))) + vi)
E
1 1 (z. + vr
and use identical analysis in the proof of upper bound (ii) and Lemma 3.6 to get
(T, = o [[HH) T (T))) Rg
T
Mp Z) H2)
T T
Corollary F22 follows from the fact that RA H. (()
= and R (T, H)
T()). To get the upper bound in Corollary R3 suffices to plug in the upper bound RB (T, H)
VC(H)7 log2 7 given by Theorem 6.1 from Hanneke et al. 2024 into the above upper
bound on (T, 2).
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims in the abstract and introduction are proven in Section B and Appendix In particular, Theorem 3.11 Corollary 3.2 and Corollary 3.3 in the main text cover the main claims made about the realizable setting. The results in Appendix cover the main claims made about 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 or
NA answer to this question will not 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.
It 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]
Justification: The assumptions about Predictors are explicitly stated Section 2. Section discusses limitations and future work. One example limitation is the fact that measuring the performance of the Predictor using the 0-1 loss may be restrictive if X' is continuous.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency 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 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 not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
25

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results are numbered and cross-referenced. Assumptions are are made clear in the theorem statements. All new theoretical results have a complete, detailed proof either in the main-text of the appendix. Theorem 3.1 follows immediately
from Lemma 3.4 Lemma 3.5 Lemma 3.6] and Lemma 3.7 Lemma 3.4 well-known
result. Lemma 3.5 is proven in the detail in the main text. Lemma 3.6 and 3.7 are proven
in Appendix [ Theorem 3.8 is proven in Appendix E Corollary 3.2 and 3.3 proved in
Appendix C All theoretical results for the agnostic setting are stated and proven in Appendix
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 or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch provide intuition.
Inversell, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper has experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, 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 a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) 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 dataset instructions for how to construct the dataset).
26

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
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:Thi This paper has experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://niis.cc.
cos.sicyyniooiiiiooooo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wttps/cccpbcccguuiiieeeeeec /etpi////uidee//ooceubbbiiii ottt://///ooeeeubeiiiiiimmmee asionnolicy 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification: This paper has no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to 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, as 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 paper has experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
27

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, 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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper has no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well 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 in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We have read and made sure that our paper conforms to the NeurlPS Code of Ethics. We have also made sure to preserve anonymity.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
28

---

Justification: Our work is theoretical and contributes to our understanding of machine learn- ing algorithms. Beyond theoretical insights that can be used develop better algorithms. our work does not have direct societal impacts.
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 partieular 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 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 train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper has no experiments and therefore poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
29

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssi thoode com/ com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create 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 as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
30

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "lqMKd1zfMP", "reviewer": "Reviewer_EJB4", "summary": "This paper studies learning-augmented online classification, where the classifier has access to a predictor that forecasts future examples. The paper proposes an algorithm that uses these predictions, and the algorithm's performance depends on the prediction error. The proposed algorithm is robust (never worse than the worst-case mistake bound), consistent (as good as the best offline learner if the predictions are perfect), and degrades smoothly as prediction quality decreases. Their findings show that accurate predictions can make online learning as straightforward as transductive online learning. The contribution of this paper is theoretical.", "questions": "- I am not an expert in online classification, but are there any public benchmarks or test sets to evaluate the performance of online classification algorithms? If so, I strongly encourage the author to perform experiments to demonstrate the proposed algorithm's performance.\n- In the third sentence of line 107, should it be $\\hat y_t \\in \\mathcal{Y}$? Otherwise, I am confused about why the prediction is binary.\n- In lines 377 - 380, do these two citations refer to the same paper?\n- The notation in the paper is somewhat confusing. Specifically, regarding the predictor, I did not find the formal definition of $\\mathcal{P}\\left(x_{1: t}\\right)$ and $\\hat{x}_{1: T}$.", "limitations": "The majority of limitations are addressed in the 'weaknesses' and 'questions' sections. From a broader societal perspective, given the theoretical nature of this work, there is no immediate negative impact, and I cannot foresee any.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This is the first paper exploring the task of online classification with predictions. The main result is intuitive and elegant, showing that \"online learnability with an effective predictor can be reduced to transductive online learnability.\"\n- The theoretical part of this paper is sound and well-organized. The paper effectively analyzes the robustness, consistency, and smoothness of the proposed algorithm, which are key aspects of learning-augmented algorithms.", "weaknesses": "- The paper does not discuss how the predictions can be generated, particularly from machine learning models. Admittedly, most designs in learning-augmented algorithms focus on the algorithmic side. Yet, linking the proposed algorithm to settings where machine learning models can be involved would strengthen the paper's relevance to the NeurIPS audience.\n\n- The paper does not include any experiment or evaluation on how the proposed algorithms would perform in real-world scenario. Similar to the previous point, I think the community studying learning-augmented algorithms value both theoretical soundness and practicality (which is the reason to include  learned predictors in the first place). I think some experiments (even on synthetic data) would make this paper more complete.\n- The paper lacks experiments or evaluations on the proposed algorithms' performance in real-world scenarios.  Similar to the previous point, I think the community studying learning-augmented algorithms value both theoretical soundness and practicality (which is the reason to include  learned predictors in the first place). Some experiments even on synthetic data showcasing the improved performance of the proposed algorithm would make this paper more comprehensive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for noting that our main result is intuitive and elegant. We address each of the weaknesses and questions below. \n\n**Weaknesses**\n- In this paper, we consider abstract instance spaces $X$. Accordingly, we did not discuss how the predictions can be generated since there is unlikely to be a one-size-fits-all Predictor. That said, for particular choices of the instance space $X$, existing literature in ML can certainly provide methods for generating predictions. For example, if $X$ is the state space for a discrete-time dynamical system, then existing algorithms for next-state predictions for discrete-time dynamical systems can be used to forecast future instances/states.  We will make sure to include a concrete example of how predictions may be generated from ML models in the camera ready version. \n- This paper is mainly focused on the theoretical/conceptual benefits of instance predictions. In particular, an important implication/insight of our results is that the difficulty in adversarial online classification is not due to the uncertainty of the labels, but rather, the uncertainty with respect to future instances. That said, we do agree with the reviewer that experiments on synthetic data showcasing the improved performance of the proposed algorithms is an interesting and important direction. We do note that our algorithms use black-box access to Offline learners and Predictors. Thus, the efficiency of our learning algorithms depend on the efficiency of existing Offline learner and Predictors. To the best of our knowledge, we do not know of any implementation of an Offline learner, let alone an efficient one. In particular, the Offline learner from Hanneke et al. [2023] is provable inefficiency since it requires computing the VC dimension.  Finally, we would like to point out that there are several influential papers in learning-augmented algorithms whose contributions were primarily theoretical [1, 2, 3, 4, 5]. \n\n**Questions** \n- Yes, there are public benchmarks where one can evaluate the performance of online classification algorithms (e.g UCI ML Repository). However, these public benchmarks are also used to evaluate batch learning algorithms. Accordingly,  it is unclear how to design a Predictor for these datasets since these datasets are not inherently online - it is not known how the instances were generated or whether there is any particular order to the rows in the datasets. \n- Yes, in the third sentence of line 107, it should be $\\hat{y}_t \\in Y$. \n- Yes, these two citations cite the same paper. We will fix this in the final version. \n- We will make sure to define the Predictor and $\\hat{x}^t_{1:T}$ explicitly in the camera-ready version. We use $P(x_{1:t})$ to denote the prediction made by Predictor $P$ after observing $x_1, ..., x_t$. We also use $\\hat{x}^t_{1:T}$ to denote these predictions when it is more convenient. We will make sure to define these quantities explicitly.\n\n\n[1] Rohatgi, D. (2020). Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1834-1845). Society for Industrial and Applied Mathematics.\n\n[2] Dütting, Paul, et al. \"Secretaries with advice.\" Proceedings of the 22nd ACM Conference on Economics and Computation. 2021.\n\n[3] Lattanzi, Silvio, et al. \"Online scheduling via learned weights.\" Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2020.\n\n[4] Antoniadis, Antonios, et al. \"Secretary and online matching problems with machine learned advice.\" Advances in Neural Information Processing Systems 33 (2020): 7933-7944.\n\n[5] Angelopoulos, Spyros, et al. \"Online computation with untrusted advice.\" arXiv preprint arXiv:1905.05655 (2019).", "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": "x6rqxuK7Yf", "reviewer": "Reviewer_yULk", "summary": "The paper belongs to the field of statistical learning. The learner is seeing pairs $(x,y)$ and needs to predict labels $y$s to compete (in terms of the expected number of errors) with any hypothesis from the given class.\n\nThe main result of the paper, Theorem 3.1, establishes a connection between the offline and the online setup. In the offline setup, the learner knows the sequence $x_1, x_2, \\ldots, x_T$ where it needs to predict labels in advance. In the online setup it gets $x$s one by one but gets help from a predictor $\\cal P$ that tries to predict what remains of the sequence. The paper constructs an online algorithm utilising an offline algorithm and a predictor and gets an upper bound on its performance in terms of the quality of the offline bound and the quality of the predictor.\n\nCorollary 3.2 shows that if a class of sequences is predictable ( = can be predicted with sublinear cumulative error) and a class of hypotheses is learnable under offline settings (the regret is sublilear), then their combination is learnable under online settings.\n\nTheorem 3.8 provides a lower bound.", "questions": "None", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I believe the paper presents an interesting result answering an important question.", "weaknesses": "I am worried the very technical presentation may limit the appeal of the paper.\n\nTypos etc:\n\nPage 4, Section 2.3, first line: to ability -> the ability\n\nPage 4, Section 2.3. I believe the mentioning of the adversary appears here for the first time, and it is confusing. I understand we are talking of the adversary because we are interested in the supremum of the loss over sequences, but I may be wrong...\n\nPage 6. Lemma 2.2 says there is _a_ concave function upper-bounding $g$. Then $\\bar f$ is defined as _the_ concave function upper-bounding $f$. Which one is used? The minimal perhaps?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding that our work presents an \"interesting result answering an important question.\" We address the concerns below. \n\n- We thank the reviewer for pointing out our use of \"adversary\" in Page 4 Section 2.3. We will change this to \"Nature\" to make it consistent  with the setup in Section 2.1. \n- Yes, we take \\bar{f} to the smallest concave sublinear function that upper bounds g. We will make this explicit in the camera-ready version.", "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": "z5OcZeLLYd", "reviewer": "Reviewer_HoBJ", "summary": "This paper studies the complexity of the online classification problem when provided with a predictor $\\mathcal{P}$ that can forecast future features of data samples. Using black-box access to this predictor, the authors provide a beyond-worst-case analysis of online classification algorithms that can adapt to the 'easiness' of the online stream. Specifically, in Theorem 3.1, they demonstrate that there exists an online learner whose mistakes can be upper bounded by the Littlestone dimension, while additionally being bounded by the performance of predictor $\\mathcal{P}$ and that of the employed offline learner. As a corollary, their result reveals the relationship between offline learnability and realizable online learnability given such a predictor. A lower bound is provided to demonstrate the tightness of the upper bound.", "questions": "Could we consider 'soft' criteria when initializing the copy? For example, could the online learner initialize a new copy only when the cumulative errors, such as $\\sum_t \\|x_t - \\hat{x}_t\\|$, exceed some threshold?", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The presentation of this paper is clear, and I can quickly grasp the main idea of how to construct an online learner that satisfies the upper bound.\n\n2. This paper explores beyond-worst-case guarantees by leveraging a predictor and an offline learner. With the constructed online protocol, the authors reveal the linkage between offline learnability and online learnability to some extent.\n\n3. The theoretical results appear solid with both the upper bounds and the lower bound, although I have not checked the appendices carefully.", "weaknesses": "My main concern is about the accuracy of the predictor $\\mathcal{P}$. Unlike in the offline setting, where the features $x_{1:T}$ are naturally provided, in the online setting—especially the adversarial one—the predictor $\\mathcal{P}$ might not be accurate, and the factor $M_{\\mathcal{P}}$ could be extremely large. Also, Algorithm 3 will initialize a new copy every time the predictor makes a mistake. It seems that Algorithm 3 might initialize the copy frequently, and it might not learn the potential pattern even if the mistakes made are minor.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding the theoretical results to be solid and the presentation to be clear. We address the concerns below. \n\n- Indeed, the stream of instances $x_1, ..., x_T$ could be very unpredictable and $M_P$ can be very large. However, in this case the minimum in Theorem 3.1 is obtained by $L(H)$, the Littlestone dimension of $H$. Thus, our algorithm's guarantee is never worse than the worst-case mistake bound (up to constant factors). However, if $M_P$ is very small, then our algorithm's guarantee (see (ii) and (iii) in Theorem 3.1) can be much smaller than $L(H)$. In this way, our algorithm adapts to the quality of predictions made by $P$.\n \n- Indeed, if the Predictor makes a lot of mistakes, Algorithm 3 will restart the Offline learner frequently causing its expected number of mistakes to explode. This is precisely why we give Algorithm 5, which explicitly controls the number of restarts. Note that the expected number of mistakes made by Algorithm 5 (see Lemma 3.7) can be significantly smaller than that by Algorithm 3 (see Lemma 3.5), and this is captured by term (iii) in Theorem 3.1. \n\n- The \"soft\" criteria when initializing a new copy is an interesting idea. However, it is not immediately obvious to us that such an idea would work since the Offline learner is only useful when the instances it gets initialized with actually matches the true instances in the stream. In any case, note that the guarantee of Algorithm 5 (see Lemma 3.7) is already near optimal (up to log factors in $T$)  given the lower bound in Theorem 3.8.", "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": "MgeZ0xombI", "reviewer": "Reviewer_f4Qh", "summary": "The paper studies an online classification problem that interpolates between transductive online classification and (standard) online classification. The interpolation is controlled by a \"predictor\" entity that tries to predict the examples to be labelled: If the predictor is good, the setting is more like transductive online classification, and otherwise it is more like (standard) online classification. For this problem, the authors design an online learner that uses a predictor and can do better than a standard online learning algorithm if the predictor is good. As a corollary, they show that transductive online learning implies online learning when the input stream is taken from a \"predictable\" collection of streams. For the first result, they also provide a lower bound that shows that it is nearly tight in some sense.", "questions": "Questions:\n1. To provide motivation, it is written that the standard online learning setting is often too pessimistic. However, there are other ways to make it more optimistic. For example, what about a stochastic adversary? It seems like a more natural way to make the setting more optimistic, but it is not discussed in the paper.\n2. Why is line 172 \"without loss of generality\"?\n3. I am not quite sure that the story of a \"predictor\" in the background is the most natural way to present the problem. Isn't the setting you define is just transductive online learning with possible noise in the given examples (which is interesting as well)?\n4. A notion of \"predictable stream collections\" is defined, but the paper does not study it or even just discuss open questions about it. Do we know how a predictable collection of streams looks like?\n\n\nSuggestions:\n1. I didn't understand the sentence in lines 155-156. I suggest rephrasing.\n2. The weighted majority algorithm is originally due to the seminal work [1]. I would mention it.\n\nTypos/english:\n1. Line 56 is unclear.\n2. Line 145: \"to ability to define\"\n\nReferences:\n\n[1] Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm.Information and computation, 108(2):212–261, 1994.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper presents a new and fairly natural problem in online learning, and provides nearly tight guarantees for it.\n2. The idea of using a few learners to cover all cases and then use WM on them is useful and interesting (is it novel?).", "weaknesses": "1. Most of the proofs use combinations of known techniques.\n2. There is some room for improvements in the writing and presentation. For example, in page 2, I didn't understand the difference between contributions (1) and (2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for noting that we present a new and fairly natural problem in online learning. We will incorporate all suggestions and fix typos in the final camera-ready version. We address each weakness and question below. \n\n**Strengths**\n\n2. This technique of constructing a few online learners and running MW on top is not completely new. For example, this technique is used to design agnostic online learning algorithms for multiclass and binary online classification [1, 2]. However, in the context of Online Algorithms with Predictions, we are unaware of any other work that uses this technique.  \n\n**Weaknesses**\n1. Although our techniques may not be groundbreaking, we disagree with the reviewer that our proofs use combinations of existing ones. Since this setting has not been studied before, we argue that new techniques needed to be developed. For example, it is not obvious apriori how to construct the class of Experts used by Algorithm 5 or that this entire approach as a whole leads to a near optimal upper bound. \n2. We thank the reviewer for pointing out the ambiguity between contributions (1) and (2).  Contribution (1) is mainly aimed at quantifying the minimax rates while Contribution (2) is concerned with characterizing learnability. In particular, Contribution (1) aims to answer: For any hypothesis class $H$ and a predictor $P$, what is the minimax expected number of mistakes/regret when given access to $P$? Here, the goal is to derive mistake and regret bounds in terms of the performance of $P$.  Contribution (2) aims to answer: does having access to a Predictor make online learning easier and if so, when? That is, are there classes $H$ that are online learnable when given access to a Predictor but not online learnable otherwise?  If so, which classes $H$ become online learnable when given access to a Predictor? We will make this distinction more clear in the final version. \n\n**Questions**\n1. There are indeed other ways of making the standard online learner setting more optimistic. The \"stochastic adversary\" mentioned by the reviewer is actually one of them and is known formally as \"smoothed online learning\" in literature. We do mention smoothed online learning in Line 64-65 and Appendix A as an alternative way of going beyond a worst-case analysis. We will add a larger discussion about the smoothed model in the main text of the final version. \n2. Since realizable and agnostic learnability are equivalent, it doesn't matter whether we use either (1) the existence of a learner with sublinear mistake bound or (2) the existence of a learner with sublinear regret to characterize offline learnability in both the realizable or agnostic settings. Lines 172-173 is just saying that we will always pick  (2) the existence of a learner with sublinear regret, to characterize offline learnability in both the realizable and agnostic settings. We will remove this phrase in the final version to avoid confusion. \n3. Our setting with a Predictor is actually more general than \"transductive online learning with possible noise in the given examples.\" This is because we allow the Predictor to change its predictions about future instances throughout the game. On the other hand, in the noisy transductive online setting, one presumably fixes the noisy instances revealed to the learner before the game begins. We give a brief discussion of this on lines 136-141. In addition, we find that access to a Predictor (and therefore dynamic predictions about future instances) is more natural in practice. For example, one often has the ability to update predictions about future instances given the present instance (e.g. temperature forecasting).\n4. One natural predictable collection of streams are those induced by dynamical systems. That is, let $X$ be the state space for a collection of transition functions $G: X \\mapsto X$. Then, given an initial state $x_0$, one can consider the stream class $Z$ to be the set of all trajectories induced by transition functions in $G$. We will add a discussion of what predictable stream classes might look like in the camera ready version. \n\n\n[1] Ben-David, Shai, Dávid Pál, and Shai Shalev-Shwartz. \"Agnostic Online Learning.\" COLT. Vol. 3. 2009.\n\n[2] Hanneke, Steve, et al. \"Multiclass online learning and uniform convergence.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.", "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:

Meta-review: The paper studies online classification when the learner has access to predictions about instances. For the Binary classification setting an online algorithm is derived which in the worst case attains the minimax regret bound against the worst case sequence of instances but at the same time, if the instances generated are realizable by a predictor in the function class, or in other words if the learner is guaranteed to observe data where future examples are easily predictable then the mistake bound obtained matches the online transductive setting (where Littlestone dimension is replaced by VC dimension).

The reviewers are in agreement that this paper is a strong theoretical paper. I agree as well and recommend an accept.
Decision: Accept (poster)