Agnostic Continuous-Time Online Learning
Authors: Pramith Devulapalli
Changlong Wu
Ananth Grama
Wojciech Szpankowski
Venue: NeurIPS 2025 poster ()
Keywords: continuous-time online learning
query efficiency
adaptive adversaries
importance weighting
Littlestone dimension
Primary area: theory
TL;DR: We develop a general theory of agnostic online learning from continuous-time data streams under limited queries, providing tight regret bounds for both oblivious and adaptive settings.

Abstract: We study agnostic online learning from continuous-time data streams, a setting that naturally arises in applications such as environmental monitoring, personalized recommendation, and high-frequency trading. Unlike classical discrete-time models, learners in this setting must interact with a continually evolving data stream while making queries and updating models only at sparse, strategically selected times. We develop a general theoretical framework for learning from both *oblivious* and *adaptive* data streams, which may be noisy and non-stationary. For oblivious streams, we present a black-box reduction to classical online learning that yields a regret bound of $T \cdot R(S)/S$ for any class with discrete-time regret $R(S)$, where $T$ is the time horizon and $S$ is the *query budget*. For adaptive streams, which can evolve in response to learner actions, we design a dynamic query strategy in conjunction with a novel importance weighting scheme that enables unbiased loss estimation. In particular, for hypothesis class $\mathcal{H}$ with a finite Littlestone dimension, we establish a tight regret bound of $\tilde{\Theta}(T \cdot \sqrt{\mathsf{Ldim}(\mathcal{H})/S})$ that holds in both settings. Our results provide the first *quantitative* characterization of agnostic learning in continuous-time online environments with limited interaction.

Agnostic Continuous-Time Online Learning
Pramith Devulapalli Changlong Wu*.1.233 Ananth Grama 1.2 & Wojeiech Szpankowski 1,4
'Department of Computer Science, Purdue University
"Center for Science of Information and Institute for Physical Artificial Intelligence, Purdue Univ. University of Arizona *Jagiellonian University
pdevulap@purrue..er edu clwu@arizona, edu sww.n edu
Abstract
We study agnostic online learning from continuous-time data streams, setting that naturally arises in applications such as environmental monitoring, personalized recommendation, and high-frequency trading. Unlike classical discrete-time mod- els, learners in this setting must interact with a continually evolving data stream while making queries and updating models only sparse, strategically selected times. We develop general theoretical framework for learning from both oblivions and adaptive data streams, which may be noisy and non-stationary. For oblivious streams, we present black-box reduction to classical online learning that yields a regret bound of T R(S) for any class with discrete-ting time regret R(S), where T is the time horizon and S is the query budget. For adaptive streams, which can evolve in response to learner actions, we design a dynamic query strategy conjunction with novel importance weighting scheme that enables unbiased loss estimation. In particular, for hypothesis class H with a finite Littlestone dimension, we establish a tight regret bound ((''- / (H) that holds in both settings. Our results provide the first quantitative characterization of agnostic learning continuous-tig online environments with limited interaction.
Introduction
Online learning from continuous data streams encountered in many as environmental sensor networks that sample air quality, recommendation engines that adapt as users click real time, and high- figh-freeuency trading platforms that react rapidly to market transients. Unlike batch or discrete-time online settings, the underlying system state evolves continually through time. Consequently, learning algorithms must query the system to construct models of the data streams, which may be noisy and non-stationary. Moreover, due the high cost of retraining online models, both the query and update budgets are often limited.
applications, such
Given the widespread applications of continuous- time online learning, our objective is to establish its foundations from learning-theone theoretic perspective. We are interested questions such as: How frequently must learner sample from continuous stream to maintain accurate predictions? What happens when the stream itself adapts in response to past queries: Can effective learning still take place? And how can provide strong performance guarantees when perfect predictor exists?
Our approach this problem is related the updete-and-deploy framework developed by Devulapalli and Hanneke (77 who recently introduced the setting of continuous-ting online learning. Here, the query strategy and the learning algorithm are treated as distinct entities: the query strategy selects continuous-tin time query points without access to labels, while the learning algorithm updates its parameters only these discrete query times. During each interval between queries, the predictor remains fixed and processes all incoming data. At each query instant, the learning algorithm observes
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

the label, updates the predictor, and redeploys it for the next interval. We note that the theory of continuous-time online learning developed by Devulapalli and Hanneke 7 primarily addresses the realizable setting, in which the data stream is assumed to be generated by function in given hypothesis class H. However, this assumption may not hold in real-world scenarios, where data is often noisy or misspecified.
In this paper, we tackle the more challenging agnostic setting M. where the data stream may be selected arbitrarily and may not align with any function in the hypothesis class. Without assuming the existence of perfectly consistent hypothesis, our primary objective becomes one of minimizing an appropriate notion of regret. Regret measures how much more loss the learner incurs compared to the best fixed predictor from a given hypothesis in hindsight. However, we should emphasize that it not clear a priori how regret should be defined in the continuous-ting setting. We introduce two notions of regret, depending on how the data stream is generated, namely, oblivious and adaptive regrets.
Oblivious Data Streams. An oblivious data stream in our context a continuous stream that is arbitrarily chosen in advance before the learning process begins and does not depend the learner's actions or query times. In this model, regret can be simply defined as the gap between the expected loss incurred by the algorithm when processing the data stream and the minimal expected loss incurred by the best fixed predictor in the hypothesis class on the same data stream.
Adaptive Data Streams. A more challenging setting arises when the data stream is adaptive; that is, it may change in response to the learner's s past queries and deployed predictors. This can occur, for example, when query made by the learner perturbs the environment. One can model adaptive data stream as being controlled by an adversary: initially, the adversary commits to a realization of a continuous data stream, but after each query, it may select new process based on the learner's 's query times and predictor history. In this case, we define regret as the difference between the expected loss of the algorithm and the expected loss of the best fixed predictor in the hypothesis class, evaluated on the same data stream generated jointly by the adversary and the learning algorithm. This notion is analogous regret formulations used in the bandit learning literature
1.1 Main Contributions
We develop generic algorithmic frameworks for agnostic continuous time online learning under both oblivious and adaptive data streams with optimal regret guarantees. We establish fundamental upper and lower bounds on regret that reveal precise trade-offs between query budget S, time horizon T, and complexity of the hypothesis class H. Together, these results establish a comprehensive theoretical foundation for agnostic continuous-time online learning.
Our main results can be summarized as follows:
1.
We show that the regret under oblivious data stream can be reduced to classical discrete-time online regret via a black-bos reduction. This is achieved by partitioning the time horizon into S epochs, each of length := T/S, and sampling one query uniformly within each epoch. Our main technical insight is that the loss incurred by any predictor on the queried example forms an unbiased estimate of the continuous-time risk over the entire epoch. We prove that for any hypothesis class admitting a classical discrete-time regret bound R(S), the corresponding continuous-time regret scales as R(S)/S: S; see Theorem
2. For adaptive processes, we show in Proposition I that a simple uniform query strategy with fixed epochs does not admit sublinear regret. This was resolved by employing a query strategy that samples from dynamic (random) epochs as in (7]. However, such strategy no longer yields an unbiased estimate due to the complex randomness of epoch boundaries. Our main technical innovation is novel weighting scheme that transforms the queried loss into an wnbiased estimate, even in the presence of random epochs-an an idea we believe is of independent interest. More importantly, our weighting scheme is realized algorithmically (cf. Algorithm 3 not just in the analysis. Equipped with these techniques, we show in Theorem 2 that adaptive continuous-time regret for any class H. of finite Littlestone dimension scales as Ô(T- (Ldim()))/S..
3. Finally, we provide lower bounds that match our upper bounds. For finite Littlestone dimensional class H. we show in Theorem 3 that lower bound of 2(T (Ldim(H))//) is necessary for any algorithm, under both oblivious and adaptive data streams. This matches our upper bounds in all relevant parameters: T, S, and Ldim(H). Notably, it demonstrates that even though the optimal
2

---

query strategies differ between oblivious and udaptive settings, their regrets are of the same order. Our proof follows from novel constructions hard data processes: see Appendix D
1.2
Related Work
Online learning in discrete time has been extensively studied in both the realizable and agnostic settings [12] 4 [6]- A foundational characterization of agnostic learnability for Dinary-valued hypothesis classes was established by Ben-David et al. [ via the Littlestone dimension and was subsequently extended to multiclass and real-valued prediction settings [14 5 8]. The study of query- efficient and selective sampling moeels-where the learner decides when to observe labels-has provided deep insights into label complexity and active learning trade-offs in both online and batch frameworks 2 91. Devulapalli and Hanneke 7 recently initiated the study of continuous- time online learning where they designed the update-and-deploy framework which is protocol governing how a learning algorithm interacts with a continuous data stream. This setting departs from classical models by requiring the learner to query both features and labels in continuous-time environment. Although their work establishes a theory for the realizable setting, the agnostic case, particularly its fundamental limits remains largely unexplored. We address this gap by providing the first quantitative characterization of regret in the continuous-tin time agnostic setting. Our approach introduces several technical innovations, including aepprtaacc--eighheee unbiased loss estimators and the novel applications of Khintchine-type inequalities to derive sharp lower bounds in both the oblivious and adaptive settings. Additionally, our setting related to problems in nonparametric filtering and online learning with delayed or partial feedhack [13 4
2 Problem Setup
Let X' be instance space, J/ be a label space, and H C y be hypothesis class. A continuous-time data process over X' x y is defined as a collection of joint random variables Z = {(X,, Yi) where Z, = (X,, Y)) e X' x y' denotes the random sample at time IR
We consider the Protocol The learner begins with an initial predictor hn E y and selects the first query time t R The predictor dn is used to make predictions on instances X, for all t < t1, without revealing the corresponding sample (X,, Y.) to the learner. At query time f1, the environment (or Nature) reveals the labeled example (X Y,,), after which the learner updates the predictor to h and selects the next query time t2. This process repeats until fixed query budget S N+ is exhausted.
framework from Devulapalli and Hanneke 7 as described in
Protocol Continuous Time Online Learning Protocol
1: Select initial predictor hn E y and initial query time i E R+
2: for 1,.... 5 do
make predictions on X, for f E (t)= 4: Query and observe Ze := (X,,, Yr,) at time l,
3: Use h
5: Choose predictor frg E ) and the next query time t.-1 based on history (Z.,..., Zz
6: end for
Note that the selection of h2 and to can be randomized and that the predictor he need not belong to H (i.e., is improper). For clarity of exposition, also assume that the learning process occurs within a finite time horizon T E g+. In this case, we also assume to = and is = T by convention.
Let A be any continuous- timee online learning algorithm, and let Z = {(X,, Yi)RER denote any data process that may depend on A. We define the risk of the algorithm as:
S Σ
risk (A, Z) E
e(b. ((h.-
where y x y + [0, 1] a bounded loss function, and the expectation taken over the randomness in Z and the internal randomness of A. For simplicity, we assume that the function
"One may also assume that the predictor h, itself is randomized.

---

f(t) == e(h)-1(X)) is measurable for any sample path. Similarly, for any (static) hypothesis h E H. define the risky(h,, Z) by replacing the h with h in
For any algorithm A, hypothesis class H. and data process Z, regret is defined as:
(A, H, Z) == risky (A. Z) inf riskr(h, Z). heH
Note that our definition of regret in to quantify the impact of the structural properties of H on regret, we introduce the following two notions of minimax regret for the worst-case data processes.
? depends the data process. To remove this dependency and
Oblivious Minimax Regret. In this setting, we assume that the data process Z is selected arbitrarily but independent (i.e., oblivious) of the internal randomness of A. The oblivious minimax regret for hypothesis class H. is then defined as:
regret (H, 9) == inf (A, Z)
z
where the infimum is taken over all learning algorithms A that make at most S queries and the supremum is taken over all data-generee mata-generating processes Z that may depend on the algorithm's 's structure but not on its internal random choices (such as the realized h, 's and (g's).
Adaptive Minimax Regret. A more challenging setting arises when the data process Z can adapt the learner's s behavior. this case, Nature may select an initial process ( and, after observing the s' th query time t.s switch to new process ( based on the full interaction history up to that point (i.e., the realized {(t, bs) but not the next query time ts+1).
Let A be learning algorithm and & be an adaptive strategy for Nature, we define the adaptive risk
(A, ② == E
Σ
e( ((ha-1(X(()) v
4
where the expectation over the joint distribution of ( (la) and (Z(*) JeE[s] induced by A and 4 and denote ((+) ((x(") ,Y, HER. We can also define the adaptive risk for any (static) hypothesis h H by replacing the h with h in (4), denoted by: riský (h, A. $).
Then, the adaptive minimax regret defined as:
regret (7,, S) == inf sup risky (A, ②) inf risk, (h, A, $)
(5)
NEW
where A runs over all algorithms with < S queries and & runs over all adaptive strategies for Nature.
3
Main Results
We start with simple query strategy shown in Algorithm for oblivious data processes. The core idea to partition the time horizon into S epochs, each of length A := T/S. Within each epoch, we select query time uniformly random and observe sample. These queried samples are then fed into a classical online learning algorithm, which produces the predictor h, used for the next epoch.
The rationale behind this approach is that since the sample is uniformly queried from an interval, the loss incurred by h on the queried sample is an unbiased estimate of the actual (continuous) risk for that interval. Therefore, any regret guarantee achieved by the expert algorithm B the queried samples can be translated to the regret of our continuous- black-box fashion. This observation formally stated in the following lemma:
online algorithm (Algorithm) T in
NNoe that Algorithm 1 slightly deviates from the general protocol described in Protocol 1 by delaying the update of hes until the start of the next epoch (not query time). This can be fitted by adding "dummy" queries the time points (sA: [S]). and will only increase the query budget by factor of 2.

---

Algorithm Uniform Random Query with Fixed Epochs
1: Partition the time horizon into blocks of length A = T/S and select ho arbitrarily
2: for 1,2, .,,,,..,SS. do
3: Deploy predictor ha-1 for the entire epoch [(s 1) sA)
4: Sample ls uniformly from [(8 1)A, +A).
5: Query and observe Ze (x,, Y,,) at step 4-
6: Use any expert algorithm to produce h, with data (Zi,.".. ,
7: end for
Lemma 1. Let Z be any (oblivious) data process, and ((ts, ((t,, Zt,)) (E())) be the (random)
selections generated by Algorithm [ Then, for any E [S] and any (random) predictor h2-1 y that depends only on {tt,, h Ze,) Jie[s-1). we have:
1 A
E (( Y,
TF
(Xhx-1(Xe). Yx)d
(x-1)
where the expectation is over all randomness involved. Proof. By the law of total probability, we have
E
Er, (Xe. [(ts, (ltthhh--eee-- Z
E(ha-1 ((ha-1(Xe), Y:)dt
1s-1)A
where we used the fact that conditioning on {(ts, ()E and Z. the index t, is independent of h--1 and is uniform over [ss 1)A, (we then express the expectation on t, as an integral). O
Note that Lemma I holds for any predictor h2-1 that satisfies the stated condition (including a static predictor), not just for the produced predictor ht--1- We now introduce the classic regret as:
$ Σ
rBg H) =
sup Zty Zag
(x.,,
inf NEW
((h(x,)),
(6)
where the expectation over the internal randomness B that produces hg-1-
Theorem Let be any hypothesis class that admits an expert algorithm with regret ( R(S) for some function R N + R. Then, the oblivious minimax regret of H satisfies
( H) S
regret (H, < A R(S) T R(((S)
S
Moreover, this upper bound is achieved by Algorithm | Jusing the expert algorithm B.
Proof. Let be any fixed data process, and (ts, h Ze, helsst be the selections made by Algo- rithm I Jusing expert algorithm B. Invoking Lemma] D and the linearity of expectation, we have
risky (A, Z)
def
E
((.,)( di
A.E
Σ (h.
1)A
where the expectation is over all randomness involved. Similarly, for any (static) h E H. have risky (h. Z)
A E Σ ((h(X,,), Y..) Therefore,
S Σ e(((X.)))
1 regrety H. 2) = E A
Σ (X.,),
inf I hE'R
5

---

e S E
inf MEH
Σ ((h(x,);),,))
S R(S),
where the first inequality follows by inf 2 E inf and linearity of expectation. This completes the proof, and the final identity follows by A = T/S.
Instantiating Theorem to specific hypothesis classes, we have:
Corollary 1. Let [0. 1J and H 1] be a binary-valued class of Littlestone dimension Ldim(H). Then, for absolute loss E(y.1/ = ly y'), the oblivious minimax regret of H. satisfies
regrety (H, SO T (Ldimi(HH) log S
VS
Proof. By 1. class H. admits an expert algorithm B with classic regret upper bounded by R(S) s Olv S log S Ldim(?() under the expected misclassification loss. The result then follows from Theorem by plugging in R(S) and noting that the expected misclassification loss can interpreted as the absolute loss 4 Chapter 8].
Observe that Corollary D provides the precise trade-off between the query budget S, time horizon T and the resulting regret. For instance, it shows that if the query budget grows linearly as S = (2(T).
then the regret is upper bounded by Ö(vT Ldim(H)) (H)). On the other hand, if the budget is sublinear as 7 for some < 1, then the regret grows as Ó /Ldim(H)) We will show in Section 3.2
that this regret is tight w.r.t. all parameters T, S and Ldim(H).
Remark 1. Note that Theorem D provides a black-box reduction from any achievable classical discrete-time online regret to the (oblivious) continuous-time regret. For instance, for real-valued class H C [0, 1] with
faa-stttrrf-----ttttinnn dimension of order oP, we have R(S) (S
under absolute loss f14j. This leads to the continuous-tin risk: regrety (H, S) < - Furthermore, Algorithm[] computationally efficient, provided that the expert algorithm B is efficient (such as the pracle-efficieed algorithms
171).
3.1 Adaptive Minimax Regret
One might observe that the key ingredient in the proof of Lemma Lis the independence of the query time t, from the data process Z. This independence allows us obtain an unbiased estimate of the continuous- matinuous-timm risk over the epoch [(s A)A, sA), even if only a single sample is queried and the process is selected in a completely arbitrary manner.
Unfortunately, this property does not carry over to an adaptively selected data process that may depend on the query times. This is demonstrated formally in the following proposition.
Proposition 1. For any hypothesis class H C 1) that contains two h1, h2 E H and X1, X2 E X such that by (x1) h2(xx)) but hy (x2) + h2(x2), we can construct an adaptive process, such that Algorithm 7 with any B and S incurs regret lower bounded by Q(T) under absolute loss.
Proof. Let B be uniformly sampled from {0, 1). At each epoch 8, we X, x= X1, hı (x1) for E [s 1) 1.], and switch to x, X2, Y, == B for f E (t,, sA). Note that this data process depends the (random) query times to and realizable w.r.t. H: that is, either h or h2 incurs risk. Since the queried example is always (x1, ( (xi)), which is independent of B. Therefore, the expected risk is lower bounded by the risk of h 1's on the intervals (l.,, sA) as:
s
EBE
Σ
(1 + B} (64 - 12)
E
EB[1
(h + B)] (sA 1x)
==1
S T 8A 1.) = 4 4
E
where the penultimate identity follows by (((AA 4.)) = A Therefore, there must exist some
2
B E {0, } such that Algorithm incurs T/4 regret for our adaptive process constructed above. D

---

Proposition implies that for any class 7. C 10, with Littlestone dimension at least (which satisfies the stated condition), Algorithm incurs adaptive regret 2 - This effectively rules out almost all hypothesis classes of interest. Note that the main reason our adaptive process breaks the arguments in the proof of Theorem is that the loss at the query example t. is no longer an unbiased estimate of the continuous- timm risk over the entire epoch [(s 1)A, sA).
To address this issue, we employ a query strategy adapted from 77]. by sampling the query time t, uniformly from the dynamic epoch (,,-1, 4--1 A), described in Algorithm 2 However, since the data process (++1)) after the query time L, may change under adaptive adversary, analog of Lemma no longer holds. Our main idea a novel weighting scheme on the queried losses (see Algorithm B), which serves substitute unbiased estimator for the continuous-time risks. This is formalized in Lemma below and constitutes the main technical innovation of this section.
Algorithm 2 Uniform Random Query with Dynamic Epochs
1: Select the initial predictor ho y arbitrarily and sample & uniform over [0, A).
2: for = 1, .,, do
3: Use h to make predictions on Xe for (f.-1.ta)
4: Query and observe z[4² (x(1) y- (5)) time t,
5: Use Weighted-EWA (Algorithm 3 to produce h2 with data {(ti, 2, Jis=
6: Sample 1++11 uniformly from the dynamic epoch [la, + A)
7: end for
Algorithm 3 Weighhed-EEAA
1: Let H = (h..... hhs)) be finite of size K
2: Set initial weight w (1, (1,..,, ,1) E [0, 1j and the learning rate r)
log K
3: for = 1,2,...,55 do
4: Retrieve data (t., 2(
5: For all h E [K], update weight
w w*[k] = (= - (1- Baee11i.////o
6: Produce predictor
2==1 w [x[[k] h
h
K
k= (x(k)
7: end for
Lemma 2. Let &e be any adaptive strategy and ( t,,, } be the realizations generated by
interactions between Algorithm and & (see Section 2 Then, for any s E [S] and any (random)
predictor h E yx that depends only on {h,-1, t;, Z
Jise-1 we have:
E [[(
L1 (11-11-11) (-))--)
(x()--((x())) (x.))
E A
(x)"),
where the expectation is over all randomness involved.
Proof. Conditioning on any realizations of { ti, (()) Jise-1, h2-1 and (0), the conditional
distribution l, remains uniform over [1,-1, 4--1 + A). Denote f(1) = E(h, (x)( y(()) and 1ss 1---1 for notation convenience. We have
1 Er, 1/" E(h,-1(X.") r = A Jo co-1
(
f(t)dt dr
A
14-1
7

---

[K]
1
1
J 1- -(((()rr) dt
A
(A + 1--1-111 f(t)dt
A J6-1
(4x)
Be, [(A T) f(tt)] [[t,)]=BB - 1(1-2) f(ta)
where the key identity (+) follows by exchanging the order of integrations, and (**) follows by setting t = since to is distributed uniformly over 1t f- + A). The lemma then follows by taking the expectation over the remaining randomness and by the law of total probability.
Intuitively, Lemma 2 shows that the continuous- time risk of predictor 1,- over the (random) interval
(t,) can be estimated by weighted loss of h at the queried sample 2,() In particular, the weighting factor depends on the query times and discounts those that are far from the previous query time. is also instructive to observe that the expected loss at the query sample without weighting always overestimates the continuous-time risk.
The following lemma provides a useful bound on the discrete-time (weighted) regret incurred by Algorithm at the query samples. The proof follows from the same regret analysis of the classical EWA algorithm 4 Theorem 2.2] and deferred Appendix B for readability.
Lemma Let H C (0, 1|xt be any finite class and E [0. 1 x [0, [0, 1] be any loss that is convex in the first argument. Then, Algorithm yyieds the following regret:
8
sup (it.i,))))))
Eas-
as. E(hs- x((o)
inf Σ as ((((x)))) NEW a=1
E0V0(SSoo (H().
1=11
where a₂ = (1 ( E [0, and {(t,, 2,(00) BOETST run over all possible selections.
Note that the regret guarantec of Lemma holds for any selection of the data {(t, [1,2 )eE[s). including adaptive strategies. It remains valid even when the a, 's take different forms.
We are now ready state our main technical result for this section.
Lemma 4. Let H c [0, 1 any finite class and f [0,1] x [0,1] + [0, 1] be any loss that is convex in the first argument. Then, the adaptive minimax regret of H satisfies: regret (H, S) S
O(T Vllg (H))/S). S). Moreover, this is achieved by Algorithm with A
The proof follows the same argument as Theorem by replacing Lemma with Lemma 2 and invoking Lemma 3 to bound the weighted regret on the queried samples. The only remaining step is to select an appropriate A that ensures ts > T, since the epochs [ta-1, t.) are no longer fixed.
Proof.
To this end, by the multiplicative Chernoff bound 18 Corollary 2.18), we have:
S {
2T
(t.- to-1) < T Pr ts
exp
SA
#=1
Setting A == 4T/S, the error probability becomes contributed by the "bad" event {ts T} is most T cxp( (S/16)) which is negligible.
Therefore, the expected risk
Using a covering argument similar to that in [ Lemma 12]. we extend Lemma 4 to hypothesis classes with finite Littlestone dimension below. The full proof is deferred to Appendix C
Theorem 2. Let H {0, 1)x x be binary-valued class finite Littlestone dimension and é be the absolute loss ( 8²) ) = y 5/l. Then, the adaptive minimax regret for H. satisfies:
( LdimmHt)) -log S
regret (H, 0
VS
We remark that the use of EWA algorithm the proof of Lemma 4 is not essential. In fact, any algorithm that achieves low weighted regret, as in Lemma includes algorithms from the online convex optimization literature [10], such as online gradient descent and the Follow-the Regularizzo-LLaddr (FTRL) family of methods.
3 enables black-box reduction. This

---

3.2 Lower Bounds
In the preceding sections, we presented algorithms for both oblivious and adaptive data streams that achieve sublinear regret rates. We now show that no algorithm with bounded query budget can attain better rate. Specifically, we establish matching lower bounds in both settings. thereby demonstrating that our regret guarantees are optimal.
Theorem Let y = [0. 11. H C 10,11* be any class with Littlestone dimension (d) and & be the absolute loss fyy, y²) y 5/1. Then. for any algorithu A with query budget S, there exists oblivious data process such that:
T [VLdim(H) VS
risky (A, inf risk (h, () 2 Ω
Note that the lower bound in Theorem 3 holds for oblivious data processes, which automatically applies to adaptive data processes. This implies that both upper bounds in Corollary and Theorem are tight (up a log S factor) w.r.t. all parameters: T, S, and LH).
To proceed, we introduce the following key inequality (see 4 Lemma A.9]).
Lemma 5 (Khinchine's 's Inequality). Let "1," Cn be uniform over +1], and a1,". On be real numbers. Then
(E= a. 1/2
< E 1:=1ase & (Ei_
1/2 22)
We present here simplified proof under adaptive data processes and assume that the query strategy data-indd catta-independent. The stronger result for oblivious data processes and general query strategies follows from more intricate construction; the complete proof is deferred to Appendix D
Proof of Theorem (weaker version). We first consider the case where H. = (ho, hn with hn(x) =
O and h1 (x) = 1 for fixed x. Let {bi,... ,bs} Unif( (0, 1) ), we construct adaptive data
process (b() as follows. We set the initial data process z == (x, b1) for all E RR After the query, we switch to another process with z(o+1) (x, b,+1) for all RR Denote T, -t- as the (random) epoch length between the and 1 queries. We have
Eg 1 (A, }10))]
E
Σ
E(h,- (x(()), y(o))a
S
S
T 2
En, (1a (x) - ball
=
2
where we used the independence between by and ttt). For comparator loss, we have:
Eg
inf E NEH H
[x(x) - bell
E.
min (E(0,1)
E 1y
b,
9
(a)
T
E,
min
ag
Σ as
2
2
T
R
Σ
0gf
2
2
(b)
T
(c) T
T
2
2
2
2/25'
where (a) follows by changing of variables 6, := 1-be and setting a, = ETT]: (b) follows by
Lemma 5 (lower bound); (c) follows by Sauchy-Schwird and the fact that a + ag T. By the probabilistic method, there must exist some (b) that attains expected regret of Q(T/VS).
For general class H with Littlestone dimension == Ldim Ld)m(H), we follow an approach similar to that of [1 Lemma 14]. We divide the query budget into d phases, each with S/d queries. The adversarial

---

strategy proceeds as follows: let T be Littlestone tree of H. of depth d. We begin with x1 as the root of and assign the labels using the construction for the simplified case above. Once the learner uses all S/d queries, we choose the next input as the child of x1 in whose outgoing edge label minimizes the comparator loss 77. This process continues until all query budget is exhausted. Let T, be the length of the time-interval for the r' phase, the total regret is lower bounded by:
T,
T
Tvd VS
Σ
Ω
2//0/d
VS/d
Here, we used the fact that there exists h H. whose predictions attain 7 for all phases.
Remark 2. Note that step (b) in Eq. 7 implicitly uses the data-indeeendencee assumption of the queries (i.e., the ag is independent of 6s s). This assumption is removed in our full proof (Appendix D by constructing an oblivious data process. Furthermore, although our simplifted proof here is reminiscent of the classic arguments in III. its adaptation the cisiinouustime setting and the phase- scheduling constitutes a substantive theoretical advancement.
Discussion
Our work focuses primarily on the worst-case setting, where the data process is arbitrary and no distributional assumptions are made. In this adversarial regime, we show that our algorithms achieve optimal regret rates, tightly matching lower bounds in both the oblivious and adaptive settings. These results provide precise characterization of the inherent difficulty of learning from agnostic continuous data streams with limited interaction. However, it is important to note that for specific data processes, improved strategies may be possible by leveraging structural or statistical assumptions. For instance, consider the case where the data process is i.idd and is realizable w.r.t. finite hypothesis class. A strategy that queries at uniformly spaced intervals of length A := T/S and updates the predictor using empirical risk minimization (ERM) at each query point incurs total risk of order:
Tlgg S
since the risk of ERM with i..dd samples is (11ss) [15]. In contrast, naive strategy that queries examples at the very beginning and freezes the predictor for the remainder the time horizon incurs a total risk of order T/S. Therefore, designing optimal query strategies tailored to specific data-generating processes remains an intriguing direction for future research.
Another modeling choice that may raise concern is our use of integration over time to define risk, which may appear idealized real-world settings, where predictions are inherently discrete. We emphasize that the integral formulation is primarily a mathematical abstraction used to simplify exposition and analysis. per-step losses, leads to the same bounds under mild assumptions. In that case, care must be taken to ensure that the number of queries does not exceed the total number of time steps, but all of our arguments and regret guarantees extend naturally with minor modifications.
analogous discrete-time version, where risk computed as the sum of
This work is partially supported by the NSF Center for Science of Information (CSol) Grant CCF-0939370, and also by NSF Grants CCF-2006440 and and CCF-2211423.
Acknowledgments.
References
[1] Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In Conference on Learning Theory, volume 3, 2009.
[2] Alina Beygelzimer, Sanjoy Dasgupta, and John Langford. Importance weighted active learning. In Proceedings of the 26th annual international conference on machine learning, pages 49-56,
2009.
[3] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning 2022.
is easy statistical learning. arXiv preprint
10

---

[4] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning and Games. Cambridge University Press, 2006.
[5] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwart. Multiclass learnability and the erm principle. J. Mach. Learn, Res., 16(1):2377-2404, 2015.
[6] Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Selective sampling and active learning from single and multiple teachers. The Journal of Machine Learning Research, 13(1):2555-269) 2012.
[7] Pramith Devulapalli and Steve Hanneke. Learning from snapshots of discrete and continuous data streams, arXiv preprint arXiv:2412.06077 2024.
[8] Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari. Multiclass online learning and uniform convergence. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of the Thirty-Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5682-5696. PMLR, 12-15 Jul 2023.
[9] Steve Hanneke and Liu Yang. Minimax analysis active learning. J. Mach. Learn. Res., 16()):3487-360,, 2015.
[10] Elad Hazan al. Introduction online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
[11] Sham Kakade and Adam T Kalai. From batch to transductive online learning. Advances in Neural Information Processing Systems, 18, 2005.
[12] Nick Littlestone. Learning quickly when irrelevant attributes abound: new linear-threshold algorithm. Machine learning, 2-285-318, 1988.
[13] Shie Mannor and Nahum Shimkin. On-line learning with imperfect monitoring. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pages 552-566. Springer, 2003.
[14] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability. In Advances in Neural Information Processing Systems, 2010.
[15] Shai Shalev-Shwarke and Shai Ben- Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[16] Shai Shalev-Shwarte al. Online learning and online convex optimization. Foundations and Trendy& in Machine Learning, 4(2):107-194) 2012.
[17] Changlong Wu, Jin Sima, and Wojeiech Szpankowski. Oracle-efficient hybrid online learning with unknown distribution. In Shipra Agrawal and Aaron Roth, editors, Proceedings of the 37th Conference Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 4992-5018. PMLR, 30 Jun-03 Jul 2024.
[18] Tong Zhang. Mathematical analysis of machine learning algorithms. Cambridge University Press, 2023.

---

NeurIPS Paper Checklist
Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We confirm that the abstract and introduction accurately reflect the paper's contribu- tions and scope.
Guidelines:
The answer NA means that the abstract and introduction do include the claims made in 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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in Appendix
Guidelines:
The answer NA means that the paper has no 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 a 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 (c.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, c.g., if the approach was only tested a few datasets with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a sreech-to-texx system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Yes]
Justification:
We confirm that the assumptions and proofs are complete.
Guidelines:
12

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [NA]
Justification: This is pure theory paper with experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer 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.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access 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 (c.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
example, if the contribution
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(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-sourge 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 have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This a pure theory paper.
Guidelines:
The answer NA means that paper does include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https::/nips.cc//nns public/
for more details.
13

---

While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code. unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /ttp::///iii.ooeeee cttpss/iccppb/bcccccccccccccc guidess/CoeeSuuminn ssi onsolicy) for more details.
The authors should provide instructions data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide seripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reprodueible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is a pure theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core of the paper to level of detail that necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or supplemental material.
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is a pure theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, 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 library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experi- ments?
14

---

Answer:
[NA]
Justification:
This a pure theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't 't make into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics ltttts::/ http:///ccc....//..uu...........
Answer: [Yes]
Justification:
We confirm our research aligns fully with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there a special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This a pure theory paper, we do see any immediate societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
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 unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e-g., pretrained language models, image generators, or scraped datasets)?
15

---

Answer:
[NA]
Justification:
This a pure theory paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners assets (c.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 a pure theory paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi wersswithhode thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This a pure theory paper.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions 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 either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: This a pure theory paper.
Guidelines:
16

---

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 the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid 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 is a pure theory paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: We used LLMs solely for writing assistance and editing purposes. No part of the core methodology, theoretical results, or scientific contributions relies on or was derived using LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L..M policy [bcrpp::/earrrss.cco/ooffeeeeeee cccCCanfeeeeccee/22555///////// for what should or should not be described.
17

---

A Empirical Validation
We complement our theoretical results with controlled simulations illustrate how the proposed update rules behave under various data processes. We implement three algorithms corresponding to our theoretical constructions:
1. Uniform Epoch: updates are performed at fixed, evenly spaced intervals.
Dynamic Epoch: update times are chosen adaptively based on past intervals.
3. Dynamic Reweighting: same Dynamic, but each update is weighted by
t--1
to correct post-epoch bias.
All algorithms use the Exponential Weights Algorithm (EWA) with absolute loss over class of threshold experts.
H = -
1f2 T [0,
We instantiate 201 uniformly spaced thresholds Tj - R and simulate over N 30,000 discrete time steps (corresponding a continuous horizon in our theoretical formulation. The number of model updates is varied as
to approximate the integration
S E (25, 40, 64, 80, 100, 128, 160, 200, 256, 320, 400, 512, 640, 800, 1024, 1280).
Each configuration is averaged over five independent random seeds to reduce stochastic variance.
Data processes. In all environments, the features are generated independently as Unif(o, 1]. The environments differ only in how the labels y/ are generated as (possibly adversarial) functions of and the query times }. We consider one stochastic and three adversarial constructions:
Oblivious Drift: Let + 0(t) = 0.5 + 0.3 sin 4Tt/T") denote drifting threshold completing two full cycles over the horizon 00, T). At each discrete tick i, the label is assigned as
1/: 1 (x. 2 0()),
followed by 5% independent label flips (y/ < - Yt with probability 0.05). This produces a smooth periodic drift that is entirely oblivious the learner's updates.
Adversarial A1 cet-after--ueryy Labels alternate over time between two regimes, with switches exactly at the learner's query times. One regime uses the informative threshold ye 1(x, , 2 0.5); the other fixes labels to constant random bit B, ~ Bernoulli
Adversarial A2 (Post-Query Shift): Labels alternate over time between two threshold regimes, with switches exactly at the learner's 's query times. One regime follows the balanced rule ye = 1[x, 0.5): the other adopts skewed rule Yt = 1(2, 2 0.8), creating abrupt post-query shifts that make the data imbalanced and harder to predict.
Adversarial A3 (Refresh-Random-
After each query, the label switches a freshly sampled random bit B, ~ Bernoulli (1/2), which is held fixed until the next query.
Evaluation. We measure the mean regret
N n,, (xx) - -vl.
R(S) = N
Σ 10 Vel
min
N
and report mean std across five seeds. For visual reference, also fit the curve C/VS in log-space.
Results. Figure 1 plots the average regret versus S (log-log scale), together with fitted C/ C/VS reference line. Across all settings, the regret decays approximately as O(1/VS), consistent with our theoretical prediction. Moreover, the deviations around the mean are of small order, indicating that the behavior holds not only expectation but is also robust across runs.
In the oblivious case, all three algorithms achieve the expected scaling, differing only by constants.
18

---

Regret scaling 5 ablivious, drift
Regret scaling vs S - adv br. after aeteruuee query
dynanic septts)
dynamic
10
Bugget
10t
10t (numbbrr
10f
(rumber updatest
(a) Oblivious drift
(b) Adversarial A1: bit-after-query
Regret scaling vs S - adv A2 post query shift
Regret scaling 5 adv, A3 refresh.random bits
dynamic
dynaric
sert151
10
6x10-
30-3
3x
10-1
(d) Adversarial A3: refresh random-bits Figure 1: Regret scaling versus number of updates S (log-log scale) under different query strategy and data processes. The dashed red line shows fitted C/V reference.
(c) Adversarial A2: post-query shift
Under A1 and A2, the dynamic schedule outperforms uniform updates, confirming the benefit of adaptive query placement.
Under A3, the dynamictrreeiightnng strategy outperforms the unweighted dynamic variant, demon- strating the effectiveness of reweighting. Nevertheless, the uniform schedule also attains small regret, which we attribute the simplicity of our threshold-expert class.
B Proof of Lemma 3
Denote (.(:.)) := := ((.,-) and = |H| for notation convenience. Let W EK_ w*lk) be
potential. We have:
W
K
w
[c
(he (x(() ww1)))
log
log
W
W
k
w [k]]
172
17
W (t( (,,))
V..))
=8
k=
S - lo
Σ
Ne (x(())) x((0)
+
172
We-1
8
n²
= -n (h.- (x(1))
where the first inequality follows by Hoeffding's 's lemma Lemma A. and the fact that a, [0, 1). the second incquality follows by Jensen's 's incquality and convexity of lz, and the last identity follows
19

---

by the definition of h (see Algorithm
Summing from s = 1 to S, we have:
W
e (chh--1Xx,) xx(,)) nFT
log
S
Σ
WI
==1
The lemma follows from the fact that:
$ Σ
log W 2 11
inf [E[KK]
(xh )
log W log K;
and setting 1) (log K)/S.
Remark 3. Note that the main difference compared to classical regret analysis of the EWA algo- rithm 4 Theorem 2.2] is that the losses E, at different time steps may vary.
C Proof of Theorem
By M Lemma 12], the class H. admits a finite expert class G C X + {0, 1] such that for any E H and data (2!-) (x.,)) ((."))essss there exists G satisfying:
vs [S]. h(x(,,) = g({x, [.
This implies that, when running Algorithm 3 over G. the incurred (weighted) regret against H. is always upper bounded by the regret against g. Moreover, by []] we have:
log O (Ldim(H)) log S)
Invoking Lemma 3 on expert class G, the (weighted) regret for H on the queried examples grows as:
llg 9 s (V log S Ldim(?())
The result then follows from the same arguments in Lemma
D Proof of Theorem 3
This appendix presents the complete proof of Theorem Before showing the formal proof, we distinguish between the following two settings for query strategies:
Oblivious Query Strategy: query strategy that is independent of the data;
Adaptive Query Strategy: query strategy that depends on the data.
Similarly, we distinguish between the following two settings for Nature:
Oblivious Nature: An adversarial environment where the data-generating process is chosen
independently of the learner's actions;
Adaptive Nature: An adversarial environment where the data-generating process is chosen
dependently on the learner's actions.
This classification yields four lower-boune regimes (0-0), (O-A), (A-O), and (A-A) where the first letter specifies the query strategy and the second the behavior of Nature. Formally, label (X-Y) asserts that for every query strategy of type X, there exists data-generation process of type Y that achieves the stated lower bound.
The following proposition is straightforward:
Proposition The following implications hold among the different types of lower bounds:
(A-0) (0-))), (A-A))
Proof. The proof follows from the facts that (A-X) = (O-X) and (X-0) = (X-A) for all X E A). The first implication holds because lower bound that applies to all Adaptive query strategies also applies to all Oblivious strategies under the same type of data process. The second implication holds because Oblivious Nature is special case of Adaptive Nature.
20

---

Proposition 2 essentially states that if a lower bound holds for any adaptive query strategy with an oblivious data process, then it is the strongest, the lower bounds we established in the proof of Section 3.2 can be classified as type (O-A), which is the weakest type among our classification above.
also holds in the other three settings. Observe that
We now present below the complete proof of Theorem with the strongest type (A-O). For the reader's convenience, we restate the theorem below:
Theorem Let H. C {0.1}* be a binary-valued class of funite Littlestone dimension. Then, for any learning algorithm A with adaptive query strategy and query budget S, there exists oblivious data process such that:
T (Ldim(H)
risk (A,
inf risk (h, 2) 2 hEH
VS
The proof of Theorem relies on several technical lemmas, as follows.
Lemma Let Bi,..., By Lid. formly from {I...., m² (with replacement) and set Y, == BI, for ......K. Let J be uniformly
Bernoulli(). (2). Choose indices II...., Is independently and uni-
sampled from {1...., m.. independently of all previous choices. Let S C E.1.....,44 1b3 be the set of
all distinct sampled indices and denote k SS). Define
Ydistinet
Σ B₁ YYO)
k
k.
jES
jES
where for each j E S, (()) is any index with 11n)) = j. Then
+ k
B Yi Yal
(Vaistinet - 2
2 m
Proof. Condition on (Y,...., Yk). For each j E S, B, is revealed exactly as Y(g). hence E B Yi...., Yu] Y16). For j $ S, B3 remains independent Bernoulli( so EB Yi..... Yxl
Averaging over the uniform J,
E[B, YI.... Ydl
1
ElBy YI,..., Ykl
1
Σ jES
B +
jēS
Simplifying.
1 1 Vdistinct + (m - k)) 1) = m
2 2 + (Vaistinct - 1)
as claimed.
Lemma 7. Let 1 {0, 11 + [0, 1] be any (possibly random) predictor. Then, with the notation as in Lemma 0 we have:
k
Yaisiier 2 2
(Y1,
Yx) B,1ly1, .Yl 2
m
Proof. Condition on Y1,- Yr, we denote p = [Bs Yı, we have
Yuj. Then, for any given b [0, 1].
E B,I Y1, .M Y2 (1 p) + p. (1 (1-b)
2 min (p. 1 - -p}
1 i
K Yassinet 2
}
Yasstiect
min
- +
2 m
2
2
1 1
Ydistinet
2
where the second identity follows from Lemma sides over the internal randomness of Φ.
The lemma follows by taking expectation on both
D
21

---

Lemma 8. With the notations of Lemma 6 let S S (I1...., 1x.. Then, conditioning on the indices I TE (equivalently on S},
k = |S] Ydistinet : /= SaessB By.
- 1)}
Vk
E
ddistinet
1
S
m
2m
Consequently.
k m
1)
EF
IE
VT
E
Y Vdistinet
2m
2m
2m
m
2m
Proof. Condition S (hence on Te). Write X, = B, 2. the {X, (Xyhees are independent, mean and take values in { Then
Ydissinct 2
E
X X
k
Y
ddistinet 1)
Σ Xj
m
JES
jeS
By the Khintchine's inequality (upper bound in Lemma 5),
E
Σ X jES
S
S
E
Σ
xy
S
=
Σ
E[X
= V
1
2
JES
jES
Dividing by m yields the conditional bound E
h Ydisttent
1)
VI 2m
The second bound
follows from the concavity square root: [8[ [[[V hJ s [[]... Finally, for sampling & times with
replacement from bins, E[K] m
)) giving the stated closed form.
Proof Theorem We start by considering the simplified case where = (ho: hy with ho(x) O and (x) = 1 for some fixed x.
We partition the time horizon into T (small) blocks each of length g. We will assign the same label within each block, and assign the feature x for all time steps. Let
Bm s.i.d. Bernoulli ()
B1.
for some be determined. For each block t, assign its label Y, in the following manner: first sample It ~ Uni mm) independent of all other randomness and set Y. := :1.
Let 41 Is be the blocks that are queried by any learning algorithm, possibly dependent on the data. We may assume, w.l.o.g., that all the queries are in different blocks (since same queries within one block reveal no additional information as the labels are the same). Now, consider any block & between 1, and f.+1 that is not queried. By the law of total probability, we have:
E (x) - Yıl
E
E
(x) Y. Y,, h
Yes
2 E
inf TR. (1
Yis)
Y Yo. Yisl
5
E
Y Yaistinet
by Lemma
m
2
VS
by Lemma g
2
2m
22

---

where we have used the fact that the distribution of Y, conditioned on the queried observations
,,,...,,Y,, is exactly the same as B, in Lemma for k S. Since there are (T S S) blocks
that are not queried and each has size 5. the total risk is lower bounded by (for S s m))
VS 2m
T
TVS 2m
S -T (T
(8)
2
2
We now analyze the comparator loss. Denote by T3 the total length of all blocks that are assigned
with variable B, for j E [m]) where ΣØ=1 T3 = T. Conditioned on any realization of T 's, the comparator risk can be expressed as:
E
min be (0,1)
Σ T3 10 Byl j=1
Using similar argument for proving
7p, we conclude that:
m
T
T
E
min
Σ
T3 16 Byl
(E
2v2m
Putting everything together and taking m = 5S, we arrive at the expected regret lower bound:
T
TVS
1
0.123 T
T
20
2/2m
2m
2
VS
VSS
The lower bound for the simplified case now follows by choosing the oblivious data process to be the (deterministic) realization of the Yi's that attains the expected regret lower bound above, which must exist by the probabilistic method.
For general class H with Littlestone dimension d = Ld)m(H), we construct the following oblivious data process. We partition the time horizon 7 into phases, each of length T/d. Let Littlestone tree of H of depth d (see [1] Lemma 14]), and let be the root of T. We assign the feature during the first phase and choose labels as in the simplified case above || for some value m to be determined. Based on the realization of labels in phase one, we set the feature x2 for phase two to be the child of X1 in T whose outgoing edge label minimizes the comparator loss, and generate labels in the same way using fresh randomness. We repeat this process for all d phases.
By the definition of Littlestone tree, there must exist some h E that attains the minimum comparator (9). the total comparator loss is upper bounded by
loss in each of the d phases. Invoking
d T/d T/d
T 2
T
Σ
2v2m
2v2m
We now lower bound the risk of the learning algorithm. To avoid overly technical complications, we assume that the learner assigns fixed (but arbitrary) query budget S, in phase [d]. although the actual query times can be chosen completely arbitrarily [ Note that this case, the learner may assign many queries in single phase, so S, may exceed for some Fortunately, the upper bound in Lemma holds even if & 2 m. Setting k = S, for all E [d] and invoking a similar argument as we obtain the following lower bound on the learner's total risk:
8
d
T/d
T
VS.
Sp 2m
S S
T
S
T
-
0
Σ /s.
0(1)
2
d
2m
2dm m
2dm TVdS
T
T S
2
0(1),
2dm
2dm
*For 2 T2, one may choose the block length as zr to get rid of the 1 additive term.
We still set the block length 1. where S the total query budget.
'The fully adaptive queries can be handled via high-pro high-probabilityy version of Lemma using Bernstein's inequality (with additional log factors). We omit the details, they are technical and not central to this work.
23

---

where we used the fact that Σラ= S, S S, and the final inequality follows from Schwarz. Therefore, by setting 205/d, the total expected regret is lower bounded by
T S
Tyds
0.048 T
T Vd
0(1) 2
0(1)
Ω
2v2m 2dmym m 2dm
/Sdd
VS
This completes the proof of Theorem
4
Remark 4, Note that a key technical innovation in our proef-compared to classical lower bound constructions such as f7iis that the expected risk incurred by the learning algorithm no longer T/2. Instead, in our construction, the learner's 's risk and that of the comparator are subtly linked through the choice of The final regret bound leverages the crucial fact that, as m increases, the learner's 's risk grows faster than the comparator's 's loss, enabling a non non-trivial lower bound on regret appropriate tuning of m.
To illustrate the necessity of our technical argument in the proof of Theorem naive approach-similar to the one used in fails to yield the optimal lower bound. Suppose we partition the time horizon 7' into blocks of length A, and assign the label uniformly random from {0, 1} within each block. this setting, the learner's expected risk not T/2. Instead, the learner query at the beginning of each block and repeat the observed label for the entire block, incurring zero risk on any queried block. Therefore, the total expected risk becomes T-S.A, On the other hand, a standard argument shows that the comparator loss (for the class {ho, h1 }) is upper bounded by _ O(VA T). To obtain non-trivial regret, one must have
4 we explain why
VA T 2 A.A
This implies A < T 53, and the resulting regret lower bound is 9 (2)) which is significantly weaker
than the optimal ? T regret.
24


Reviews:
[{"review_id": "cFgXy3roFp", "reviewer": "Reviewer_YgrP", "summary": "This paper extends te setting of (realizable) continuous-time online learning from Devulapalli and Hanneke to the agnostic case. In this framework, there is a stream in continuous time of queries $X_t$, and the algorithm needs to make online predictions on the stream  by picking a hypothesis to use with a few discrete observation of the true labels $Y_t$ to the stream. The original assumed that the labels in the stream were generated by some hypothesis in the hypothesis class. This paper drops this assumption, and show algorithms (and some matching lower bounds) for both oblivious and adaptive adversaries. In the oblivious case the algorithm splits the time-horizon in equal length epochs and samples a uniform time for each epoch to see the label and use as a black-box an OL algorithm. In the adaptive case this may not work anymore, and they show how to use dynamic epochs, also used by Devulapalli and Hanneke, and dynamic step sizes on EWA to circumvent this issue.", "questions": "Small technical question, but DH24 assume the process $Z_t$  to be countable. I don't think this matters too much except on some of the technical conditions required later on (such as measurability of the sample paths). Do the authors think there are some technical kinks that might need to be ironed out because of this?", "limitations": "The limitations of the setup seem to be well discussed in the paper.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "This paper studies a very natural (and more challenging) extension of the continuous-time online learning framework proposed by Devulapalli and Hanneke, which by itself it already a somewhat natural problem. Many of the techniques in the algorithms seem to drawn upon the ideas of DH24, but are certainly not trivial extensions in any way. The algorithm (or, better saying, reduction) for the oblivious case is clean and serves as a nice way to \"warm-up\" to the adaptive case, although the oblivious case is interesting in itself. Also, the slight modification of EWA  leads to a (relatively) elegant analysis. Unfortunately I did not have the time to check the proofs as I would like to have done, but the few derivations that I had time to check were relatively clearly exposed and seemed to be correct. \n\nOverall, although there does not seem to be major novel ideas in the framework nor in the algorithms, this is a quite solid contribution, and shows optimal rates for both the oblivious and adaptive cases, which makes this a even more complete and solid work. While I have some questions, none of them seem to be crucial for clarity/significance/originality/quality of the paper.", "was_revised": true, "final_justification": "I did not have many concerns, and it seems like the other reviewers only raised minor points. I still lean towards accepting this submission.", "rebuttal": "We thank the reviewer for the thoughtful feedback and helpful comments. Indeed, in our paper, we explicitly assume that the function induced by the loss is measurable for any sample path, so that the risk defined via integration is well-defined. The measurability and boundedness of $f(t)$ ensure that the function is absolutely integrable; thus, the exchange of the order of integration in Lemma 2 follows from Fubini’s theorem, which does not require assumption on the countability of the $Z_t$'s.\n\nFrom a practical point of view, one can also consider a sufficiently small partition of the time horizon to approximate the integral and thereby avoid measurability concerns—in which case, our result still holds."}, {"review_id": "cAAGU8pqsE", "reviewer": "Reviewer_fUeB", "summary": "This paper studies agnostic online learning from continueous-time data streams. learners have to interact with continually envolving data stream while making queries and updating model at strategically selected times. This paper develop theoretical framework for learning from both oblivious and adaptive data streams.", "questions": "1. The paper builds on and extends the update-and-deploy framework of Devulapalli and Hanneke [7], which focused on the realizable setting. Could the authors clearly delineate the conceptual and technical differences and challenges introduced by the agnostic setting?\n2. The paper proposes a novel importance weighting scheme (Algorithm 3) to obtain unbiased loss estimates under adaptive query times with dynamic epochs. Could the authors clarify how sensitive is the performance and regret bound to the exact choice of weighting function?\n3. Practical data streams can be complex and non-stationary beyond Littlestone dimension and scale characterization. Could the authors discuss or exemplify scenarios or hypothesis classes where these bounds translate to meaningful learning guarantees in real-world continuous data and elaborate on how these theoretical guarantees relate to computational or sample complexity in applications like high-frequency trading or personalized recommendations?", "limitations": "Yes, the authors have acknowledged and discussed the limitations in Appendix A,", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths: \nThis paper develops generic algorithmic frameworks for agnostic continuous-time online learning under both oblivious and adaptive data streams with optimal regret guarantees, giving both upper and lower bounds.\n\nWeakness:\nNo experimental results on either synthetic or real world data are conducted in the paper, it remains unclear whether the algorithms proposed can be used in practice.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful feedback and helpful comments. We address the questions raised below:\n\n**Q1:** The primary conceptual difference compared to the framework of Devulapalli and Hanneke [7] is that our setting does *not* assume the existence of a perfect labeling rule from the hypothesis class. We also explicitly treat the query budget as a resource, which allows us to derive a precise quantitative trade-off between regret and the query budget. \n\nFrom a technical standpoint, the work in [7] applies dynamic querying without weighting, leveraging the fact that the plain loss serves as an overestimate that is sufficient to bound mistakes in the realizable setting. However, in the agnostic setting, such an overestimate is insufficient to lower bound the competitor's loss.  Our main technical innovation is the introduction of a weighting factor that produces exactly unbiased loss estimates, along with novel reductions to classic expert algorithms. Additionally, the lower-bounding techniques presented in Section 3 and Appendix D are entirely novel compared to those in [7].\n\n**Q2:** The weighting factor was not arbitrarily chosen, but rather derived from the randomness in the query times $t_s$, as shown in Lemma 2. In fact, other methods of selecting $t_s$ could also work, potentially leading to different weighting factors using the same derivation technique as in the proof of Lemma 2. Note that the weighting factor introduced in our Algorithm 3 lies in $[0,1]$, so it does not increase the variance of the estimator used in Algorithm 1 (which we simulate below).\n\n**Q3:** In fact, we consider the *worst-case* scenario; that is, our results apply to *any* non-stationary data-generating process. The \"complexity\" our framework addresses is the *query* (or update) budget. For example, in high-frequency trading, one must deploy a model that operates in real time, and updating the model can be costly—whether due to retraining overhead or concerns about system stability. As a result, updates must be sparse and strategic. Our work provides a worst-case performance baseline for such applications.\n\n**Synthetic Experiments:**  \nWe conducted synthetic experiments to demonstrate the robustness of our algorithm. We used the expert class \n\n$$\n\\mathcal{H} = \\\\{ h_{\\theta} := \\mathbf{1}\\\\{x \\le \\theta\\\\} : \\theta \\in \\\\{0, 0.001, \\ldots, 1.000\\\\} \\\\},\n$$  \n\nso that $|\\mathcal{H}| = 1000$. We set the time horizon to $T = 5$ and discretize it into 1000 small blocks to approximate the integral regret *without* normalization. So, the simulated regret values reported below are scaled by a factor of $200\\times$ compared to the actual continuous-time regret used in the paper. We simulate our **Algorithm 1** under different query budgets $S$, using the Exponential Weights Algorithm (EWA) as the expert algorithm $\\mathcal{B}$, on the following data streams (all features are generated iid uniform from $[0,1]$):\n1. **`alt_blocks`**: The stream is divided into $S$ equal chunks where the label for the chunks follows an (deterministic) alternating 0/1 pattern.\n2. **`iid`**: Each label is drawn independently from a Bernolli source with parameter $p=0.3$.  \n3. **`realizable`**: The labels are generated by a ground-truth function from $\\mathcal{H}$.  \n4. **upper bnd.**: Our theoretical upper bound.\n5. **lower bnd.**: Our theoretical lower bound.\n\nThe considered data processes span a broad spectrum, ranging from stationary to highly non-stationary regimes. Results are shown below (each experiment is repeated 100 times, and the average regret is reported):\n\n| $S$  | `alt_blocks` | `iid`   | `realizable` | upper bnd. |\n|------|--------------|---------|--------------|------------|\n| 5    | 161.98       | 172.93  | 197.13       | 1175.9     |\n| 10   | 102.30       | 138.96  | 144.92       | 831.4      |\n| 20   | 65.91        | 99.07   | 120.65       | 588.0      |\n| 40   | 57.16        | 79.34   | 86.10        | 415.6      |\n| 80   | 47.65        | 70.96   | 63.50        | 293.3      |\n| 160  | 35.97        | 61.76   | 48.97        | 207.6      |\n| 320  | 41.86        | 35.47   | 36.01        | 147.0      |\n| 640  | 42.18        | 27.73   | 22.81        | 103.9      |\n\nWe also conducted simulations on the *hard* data stream `lower_stream` used in our lower bound proof (cf. Appendix D):\n\n| $S$  | lower bnd. | `lower_stream` | upper bnd. |\n|------|-------------|----------------|-------------|\n| 5    | 71.6        | 132.77         | 1175.9      |\n| 10   | 50.6        | 42.80          | 831.4       |\n| 20   | 35.8        | 89.83          | 588.0       |\n| 40   | 25.3        | 39.83          | 415.6       |\n| 80   | 17.9        | 29.51          | 293.3       |\n| 160  | 12.6        | 27.75          | 207.6       |\n| 320  | 8.9         | 28.40          | 147.0       |\n| 640  | 6.3         | 33.08          | 103.9       |\n\n**Observation 1:** For all four data streams, the regret is upper bounded by our theoretical upper bound. In fact, the curves have very similar slopes when plotted on a log-log scale, demonstrating that the $1/\\sqrt{S}$ order is genuine.\n\n**Observation 2:** The regret for the `lower_stream` data is tightly sandwiched between our theoretical lower and upper bounds, demonstrating the optimality of our theoretical analysis.\n\nWe are happy to incorporate the experimental results reported above in our revision, along with additional discussion."}, {"review_id": "QuqLGyCYkH", "reviewer": "Reviewer_ho6c", "summary": "This paper considers a continuous online learning framework in which a learner selects discrete query times at which the data stream is observed (to evaluate the loss) and the learning strategy is updated. This framework was recently studied in [7], but only in the realizable setting—where the data is assumed to be generated by a function within the hypothesis class. In contrast, the present work focuses on the more challenging agnostic setting. The authors generalize the notion of expected regret to this continuous-time framework by integrating the loss over time, rather than summing it at discrete points.\n\nTwo settings are considered: the oblivious data stream, where the data is generated arbitrarily in advance and independently of the learner’s randomness; and the adaptive data stream, where the data stream may depend on any past information. For both settings, the authors propose a black-box reduction to an expert algorithm, using the observed losses at the random query times as unbiased estimators of the integrated continuous loss. The regret bound then follows by plugging these estimators into the standard regret analysis of the expert algorithm.\n\nIn addition to upper bounds, the authors provide a nearly matching lower bound (up to logarithmic factors) in the oblivious setting, showing that the regret guarantees are essentially optimal.", "questions": "- Is it possible to derive high-probability guarantees, rather than bounds only in expectation? Alternatively, can one obtain upper bounds on the actual expected regret (i.e., using the infimum over $h$ in Equation (5)) instead of pseudo-regret bounds (i.e., the expectation as in Equation (4))?\n\n- The results are presented differently for the oblivious and adaptive settings. Is it not possible to unify the presentation, perhaps by giving a generic analogue of the black-box reduction in Theorem 1 for the adaptive setting—similar to what is done for the oblivious case—rather than relying on the more case-specific Lemma 4 and Theorem 2? The motivation for diverging in presentation is not entirely clear.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strenghts:\n- The paper is well-written and easy to follow.\n- The problem considered is interesting and the authors provide a clean and complete analysis with tight upper and lower bounds. \n\nWeaknesses:\n- The results are restricted to finite hypothesis classes. Is it not possible to extend the black-box reduction to continuous hypothesis classes, and more generally to reduce to any discrete online convex optimization algorithm, rather than limiting to expert algorithms?\n- The paper would benefit from synthetic numerical experiments to illustrate the practical implications of the continuous-time framework on regret. In particular, when setting $T = S$, we would expect to recover similar performance—does this hold in practice? Additionally, how stable are the results, given that they rely on an estimation technique?\n- The proofs appear to be fairly standard and rely on combining known results: the agnostic lower bound follows techniques from [1]; the sampling process for query points is borrowed from [7]; and the use of unbiased loss estimators within an expert algorithm mirrors approaches commonly used in adversarial bandits and online learning with partial feedback.", "was_revised": true, "final_justification": "I have read other reviews and the rebuttal. I think the authors address well my concerns. In particular, they added synthetic experiments that seem to well illustrate their theoretical results. I lean toward acceptance.", "rebuttal": "We thank the reviewer for the thoughtful feedback and helpful comments. We address the questions raised below:\n\n**W1:** In fact, our results for the adaptive case also apply to hypothesis classes with finite Littlestone dimension, not just finite classes, as shown in Theorem 2. For general OCO algorithms, our reduction could still apply by running the algorithm (e.g., OGD or FTRL) on the *weighted* loss function. We only require a regret guarantee of the form stated in Lemma 3. We thank the reviewer for pointing this out and will be happy to include this clarification in the revised version.\n\n**W2 & Q1:** Our regret guarantee relies on estimating the loss, which is bounded by $\\Delta \\approx T/S$. For $S = T$, the variance is constant; in this case, an application of Freedman's inequality for martingales (with filtration induced by $t_s$) yields a high-probability bound on the *learner's risk* (or any fixed comparator risk) with deviation $O(\\sqrt{S}) = O(\\sqrt{T})$. For general $S$, the deviation scales as $O(\\Delta \\sqrt{S}) = O(T/\\sqrt{S})$, which matches the order of our expected regret $\\tilde{O}(T\\sqrt{\\mathsf{Ldim}(\\mathcal{H})/S})$.\n\nIn the *oblivious* case, the learner's high-probability risk can be translated into a high-probability bound for the actual (pointwise) regret. However, for the *adaptive* case, it is unclear whether such a high-probability pointwise regret bound is attainable, since the optimal comparator may depend on the learner’s internal randomness. To our knowledge, no such *adaptive* high-probability pointwise regret bound exists even in the adversarial bandit setting. Nevertheless, the above argument still yields the following weaker form of adaptive high-probability regret: for any given expert $h \\in \\mathcal{H}$, with high probability, the (pointwise) regret of the learner against $h$ is $\\tilde{O}(T\\sqrt{\\mathsf{Ldim}(\\mathcal{H})/S})$.\n\n**W3:** We agree that many of our technical ingredients are inspired by classical ideas. However, synthesizing these ideas in our (novel) setting is far from straightforward. For example, the selection of the weighting factor is derived from the randomness of the query times $t_s$ and is not arbitrarily chosen. The fact that it may appear natural in hindsight does not imply that it is easy to derive or even to recognize it's existence.\nMoreover, our lower bound proof in Appendix D significantly extends the construction in Ben-David et al. [1] by designing an *oblivious* process (see Remark 4 and the accompanying discussion).\n\n**Q2:** We thank the reviewer for the helpful suggestion. As noted in our response to **W1**, a general reduction is indeed achievable in the OCO framework. We will include this discussion in the main text following Theorem 2.\n\n**Synthetic Experiments:**  \nWe conducted synthetic experiments to demonstrate the robustness of our algorithm. We used the expert class \n\n$$\n\\mathcal{H} = \\\\{ h_{\\theta} := \\mathbf{1}\\\\{x \\le \\theta\\\\} : \\theta \\in \\\\{0, 0.001, \\ldots, 1.000\\\\} \\\\},\n$$  \n\nso that $|\\mathcal{H}| = 1000$. We set the time horizon to $T = 5$ and discretize it into 1000 small blocks to approximate the integral regret *without* normalization. So, the simulated regret values reported below are scaled by a factor of $200\\times$ compared to the actual continuous-time regret used in the paper. We simulate our **Algorithm 1** under different query budgets $S$, using the Exponential Weights Algorithm (EWA) as the expert algorithm $\\mathcal{B}$, on the following data streams (all features are generated iid uniform from $[0,1]$):\n1. **`alt_blocks`**: The stream is divided into $S$ equal chunks where the label for the chunks follows an (deterministic) alternating 0/1 pattern.\n2. **`iid`**: Each label is drawn independently from a Bernolli source with parameter $p=0.3$.  \n3. **`realizable`**: The labels are generated by a ground-truth function from $\\mathcal{H}$.  \n4. **upper bnd.**: Our theoretical upper bound.\n5. **lower bnd.**: Our theoretical lower bound.\n\nThe considered data processes span a broad spectrum, ranging from stationary to highly non-stationary regimes. Results are shown below (each experiment is repeated 100 times, and the average regret is reported):\n\n| $S$  | `alt_blocks` | `iid`   | `realizable` | upper bnd. |\n|------|--------------|---------|--------------|------------|\n| 5    | 161.98       | 172.93  | 197.13       | 1175.9     |\n| 10   | 102.30       | 138.96  | 144.92       | 831.4      |\n| 20   | 65.91        | 99.07   | 120.65       | 588.0      |\n| 40   | 57.16        | 79.34   | 86.10        | 415.6      |\n| 80   | 47.65        | 70.96   | 63.50        | 293.3      |\n| 160  | 35.97        | 61.76   | 48.97        | 207.6      |\n| 320  | 41.86        | 35.47   | 36.01        | 147.0      |\n| 640  | 42.18        | 27.73   | 22.81        | 103.9      |\n\nWe also conducted simulations on the *hard* data stream `lower_stream` used in our lower bound proof (cf. Appendix D):\n\n| $S$  | lower bnd. | `lower_stream` | upper bnd. |\n|------|-------------|----------------|-------------|\n| 5    | 71.6        | 132.77         | 1175.9      |\n| 10   | 50.6        | 42.80          | 831.4       |\n| 20   | 35.8        | 89.83          | 588.0       |\n| 40   | 25.3        | 39.83          | 415.6       |\n| 80   | 17.9        | 29.51          | 293.3       |\n| 160  | 12.6        | 27.75          | 207.6       |\n| 320  | 8.9         | 28.40          | 147.0       |\n| 640  | 6.3         | 33.08          | 103.9       |\n\n**Observation 1:** For all four data streams, the regret is upper bounded by our theoretical upper bound. In fact, the curves have very similar slopes when plotted on a log-log scale, demonstrating that the $1/\\sqrt{S}$ order is genuine.\n\n**Observation 2:** The regret for the `lower_stream` data is tightly sandwiched between our theoretical lower and upper bounds, demonstrating the optimality of our theoretical analysis.\n\nWe expect similar results to hold for Algorithm 2 as well, since the weighting factor lies in $[0,1]$ and does not increase the variance of the loss estimation. We are happy to incorporate the experimental results reported above in our revision, along with additional discussion."}, {"review_id": "BH653Yturf", "reviewer": "Reviewer_aPug", "summary": "This paper investigates agnostic continuous-time online learning. In contrast to the classical formulation of online learning, in which the input is a discrete sequence, the input here is a continuous data stream. While previous research has addressed the realizable setting, the more realistic and challenging agnostic setting has remained largely unexplored.  The authors demonstrate that, given a hypothesis class with Littlestone dimension $d$, the regret of online learning this class is exactly $\\tilde{\\Theta}(T\\sqrt{d / S})$ for both oblivious and adaptive adversarial settings, where $T$ represents the time-span and $S$ denotes the number of queries the algorithm can make.", "questions": "1. I am concerned that Lemma 6 may not hold as $I_1,\\dots,I_k$ could overlap. For example, let $m = k = 2$. Given that $Y_1 = Y_2 = 0$, it holds that $E[B_J \\mid Y_1=Y_2=0]>0$ since it is possible (with positive probability) that $J\\neq I_1 = I_2$ and $B_J = 1$. However, the Lemma gives $1/2 + k/m(\\bar{Y}  - 1/2) = 0$.  As this lemma serves as a key inequality in the proof of the lower bound, can you provide a more detailed explanation regarding its validity?\n2. It seems the lower bound only holds when $S$ is not excessively large: in the formula before line 413, the inequality requires $T / \\sqrt{S} = \\Omega(1)$ (i.e., $S = O(T^2)$). In contrast, the upper bound seems to hold even as $S \\to \\infty$. Therefore, the bounds do not match in the extreme regime. Is my understanding correct?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\nThe authors establish a nearly tight $\\tilde{\\Theta}(T\\sqrt{d / S})$ regret bound for the fundamental problem of agnostic continuous-time online learning. For an oblivious adversary, they propose a simple black-box reduction to the discrete case. In the case of an adaptive adversary, they present a novel re-weighting scheme attaining the same bound. Additionally, they provide a matching lower bound that holds even for the most challenging scenario (an adaptive query strategy against an oblivious nature).\n\nFurthermore, the organization and presentation of the paper are quite commendable, making it easy to read and understand.\n\n**Weakness:**\n\nI did not identify any significant weakness. However, I have concerns regarding the correctness of Lemma 6. Please refer to \"Questions\" for further details.\n\nIn the preliminaries, the authors define the protocol (Protocol 1) in a way that it chooses a predictor $\\hat{h}_s\\in\\mathcal{Y}^{\\mathcal{X}}$. However, it appears that sometimes the output is indeed a distribution over predictors (particularly in the adaptive setting, where this is necessary), and at any time step the actual predictor is drawn from this distribution (rather than keep outputting $\\hat{h}_s$ for a period). I recommend the authors clarify this part to make the definition consistent.", "was_revised": true, "final_justification": "This paper investigates agnostic continuous-time online learning and provides tight upper and lower bounds. Though there were some issues in the original proof, they were fully addressed in the rebuttal. I recommend acceptance.", "rebuttal": "We thank the reviewer for the thoughtful feedback and helpful comments. We address the questions raised below:\n\n**Q1:** This is indeed a bug, and we are grateful to the reviewer for identifying it. The correct expression should be\n\n$$\n\\frac{1}{2} + \\frac{\\tilde{k}}{m} \\left( \\bar{Y}_{\\mathrm{distinct}} - \\frac{1}{2} \\right),\n$$\n\nwhere $\\tilde{k} \\le k$ is the number of *distinct* $I_t$'s, and $\\bar{Y}_{\\mathrm{distinct}}$ is the average of all $Y_t$'s corresponding to distinct indices $I_t$. The same replacement should also be made in Lemmas 7 and 8.  \nThis correction does not affect the subsequent argument, as the upper bound in Lemma 8 still holds since $\\tilde{k} \\le k$. We can apply Khintchine's inequality (upper bound) to obtain\n\n$$\n\\frac{\\tilde{k}}{m} \\left| \\bar{Y}_{\\mathrm{distinct}} - \\frac{1}{2} \\right| \\le \\frac{\\sqrt{\\tilde{k}}}{2m} \\le \\frac{\\sqrt{k}}{2m},\n$$\n\nby conditioning on the set of distinct indices. This provides an even better constant $\\frac{1}{2}$ compared to $\\frac{\\sqrt{2}}{2}$, as the counters $N_j$ are simply indicators. We will make this correction in the revised version and again thank the reviewer for the careful reading.\n\n**Q2:** Indeed, our current lower bound proof is only non-vacuous when $S = O(T^2)$, due to the constant factor in (8). For general $S \\ge T^2$, the $\\Omega(T/\\sqrt{S})$ lower bound still holds. This can be remedied by selecting the block length to be $1/S^2$ (instead of $1/S$ as in the paper), so that the constant factor in (8) becomes $O(1/S)$, which is negligible compared to the main term $T/\\sqrt{S}$. We will clarify this in the revision.\n\n**Randomness of Predictors:** Indeed, for the 0–1 loss, it is necessary for the predictor to be randomized in order to achieve sublinear regret in the adaptive case. We will clarify in Protocol 1 that the predictor $\\hat{h}_s$ is allowed to use internal randomness."}]

Author rebuttal:

Meta-review: This paper provides the first guarantees for continuous-time online learning in the agnostic setting for hypothesis classes with a finite Littlestone dimension. All of the reviewers were positive about this submission and overall in favor of acceptance. For the camera-ready version, the authors need to include the fix to the bug in Lemma 6 that was discovered during the review process. Additionally, they are highly recommended to add the experimental results that they shared in the rebuttal, and provide context for the computational complexity and generality of the procedure that some reviewers believed was missing/unclear in the initial submission.
Decision: Accept (poster)