Learning from Snapshots of Discrete and Continuous Data Streams
Authors: Pramith Devulapalli
Steve Hanneke
Venue: NeurIPS 2024 poster (2024)
Keywords: Learning Theory; Online Learning; Continuous Processes
Primary area: learning_theory
TL;DR: This paper builds a theoretical framework for non-adaptive and adaptive algorithms to predict sets of functions from continuous data streams, showing how selective querying supports accurate learning, even with limited observability.

Abstract: Imagine a smart camera trap selectively clicking pictures to understand animal movement patterns within a particular habitat. These "snapshots", or pieces of data captured from a data stream at adaptively chosen times, provide a glimpse of different animal movements unfolding through time. Learning a continuous-time process through snapshots, such as smart camera traps, is a central theme governing a wide array of online learning situations. In this paper, we adopt a learning-theoretic perspective in understanding the fundamental nature of learning different classes of functions from both discrete data streams and continuous data streams. In our first framework, the *update-and-deploy* setting, a learning algorithm discretely queries from a process to update a predictor designed to make predictions given as input the data stream. We construct a uniform sampling algorithm that can learn with bounded error any concept class with finite Littlestone dimension. Our second framework, known as the *blind-prediction* setting, consists of a learning algorithm generating predictions independently of observing the process, only engaging with the process when it chooses to make queries. Interestingly, we show a stark contrast in learnability where non-trivial concept classes are unlearnable. However, we show that adaptive learning algorithms are necessary to learn sets of time-dependent and data-dependent functions, called pattern classes, in either framework. Finally, we develop a theory of pattern classes under discrete data streams for the blind-prediction setting.

Learning from Snapshots of Discrete and Continuous Data Streams
Pramith Devulapalli
Steve Hanneke
Department of Computer Science Purdue University pdevalaap@purdue.ce edu
Department of Computer Science Purdue University steve haweeeehanneeeeememm com
Abstract
Imagine smart camera trap selectively clicking pictures to understand animal movement patterns within particular habitat. These "snapshots", pieces of data captured from a data stream at adaptively chosen times, provide a glimpse of different animal movements unfolding through time. Learning continuous- time process through snapshots, such as smart camera traps, is a central theme governing a wide array of online learning situations. In this paper, we adopt a theoretic perspective in understanding the fundamental nature of learning different classes of functions from both discrete data streams and continuous data streams, In our first framework, the mndate-and-deplo setting, a learning algorithm discretely queries from process to update a predictor designed make predictions given as input the data stream. We construct a uniform sampling algorithm that can learn with bounded етrоr any concept class with finite Littlestone dimension. Our second framework, known as the blind-predicee algorithm generating predictions independently of observing the process, only engaging with the process when it chooses to make queries. Interestingly, we show a stark contrast in learnability where non-trin ann-riivil concept classes are unlearnable. However, show that adaptive learning algorithms time-dependent and data-dependent functions, called pattern classes, in either framework. Finally, develop theory of pattern classes under discrete data streams for the blind-preede hund-prediction setting.
setting, consists of learning
necessary to learn sets
Introduction
Two Motivating Examples
Pretend you're farmer by day and businessperson by night. As farmer, you oversee a 10,000 acre plot land equipped with a smart irrigation system. To feed data to your irrigation system, you rely on hyperspectral imaging taken from satellite to gauge soil moisture conditions. Ideally, you would like to constantly feed your irrigation system with hyperspectral data; however, the steep financial cost of processing hyperspectral data prevents you from doing As result, you need to devise strategy to sparingly use satellite data; at all other times, you rely on the smart irrigation system to accurately extrapolate the soil moisture conditions time passes by.
At night, you become businessperson. You employ a translator on your work laptop during your virtual meetings to automatically convert your voice into the preferred language of your client. This translator is fine-tuned by a speech-to-ter to-text translation system that takes in voice data and updates the translator's 's model on the correct language translation. But, there's caveat. Each request costs money. And each transmission dominates a sizable portion the available Internet bandwidth. Your task is to come up with the optimal strategy of balancing requests to the cloud versus trusting the fidelity of the translator.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

1.2 A New Learning Paradigm
While these settings may seem rather creative in nature, both of these scenarios represent plausible real-world instances of learning from continuous data streams with temporal dependencies. What type of barning-theoretic framework should one construct when framing the question of online learning under continuous data streams? How can we best capture the notion of temporal dependencies and patterns that naturally arise when analyzing such data sources? While these questions are highly pertinent, the answers aren't 't clear due to vast majority of the learning theory literature focusing on online learnability from discrete data streams modeled as round-by-round processes. In the two examples showcased at the beginning, it's clear that establishing theoretical understanding of these settings can be an important step in tackling online learnability under continuous data streams.
In our paper, we present a streamlined approach in tackling these rather fundamental challenges by first establishing two closely related, but separate, frameworks.
Blind-Prediction Prediction Setting The first framework is called blind Winnd-prdiictin which is highlighted by the smart irrigation system using satellite imagery data. The irrigation system receives feedback only when hyperspectral data is requested; at all other times, the system must predict on its own with no input from the environment. This framework is designed such that a learning algorithm must make a prediction based only on the current timestamp and previous queries. The learner's predictions independent of the current values generated by the data stream hence the name blimd-prediction.
Update-and-Deyee Deploy Setting The second framework, called update-and-deploy, is highlighted by the speech-to-text translation system. The speech-to-text translation system, a learning algorithm, and the translator, called the predictor, are considered as two separate entities where the algorithm retrieves snapshots of the data stream to update the predictor. We describe this behavior algorithm activating different modes at different times. A learning algorithm performs updates to a predictor when it queries and deploys the predictor to make predictions as the process rolls by.
learning
Pattern Classes A significant portion of this work is dedicated to studying these frameworks under pattern classes, sets of sequences encoding data-dependent and time-dependent characteristics. First introduced by Moran et al. [. these classes consist of a set of patterns; each pattern is a sequence of instance-label pairs marked with the appropriate timestamp. For example, if we let X' and y represent the instance space and label space respectively, then 700 (X' x y) represents the set of all countably infinite patterns. A discrete pattern class P is defined as P C 7 where any P E P understood as P = (Z = (X,, Y;) Y;)
Pattern classes can also be viewed as natural generalizations of concept classes. Given concept class H consisting of classifiers mapping instances from X' to labels in V, we can derive a pattern class that encapsulates all sequences that could be realized by any single h E H. Formally speaking, the induced pattern class P(H) is defined as P(H) = {(2)) E 2 3h E H, Vt E N, h(X,) = Y.}
Now that the stage has been developed for pattern classes, we turn to set of questions that naturally arise under continuous data streams. What pattern classes are online learnable? Is there a natural dimension that characterizes online learnability of pattern classes under the different querying-basee based models? How does learning pattern classes and concept classes differ under continuous data streams? We tackle these important questions in our paper using our learning frameworks.
1.3 Our Contributions
We detail the primary contributions of this work below.
1. Non-Adaptive Learners in the Updall-and-Deploy Setting, First, we extend the current theory on concept classes to include online learning under continuous data streams for the update-and-deploy setting. A non-adaptive learner is a learning algorithm that queries independent of the process itself. For the apllat-and-deplo setting, we show that the non- adaptive learner, Aunit, that uniformly samples its queries from a fixed uniform distribution, achieves a bounded expected error with a linear querying strategy.
Theorem 1.1 (Informal Version). Given an instance space and a label space Y, let H C yxt be concept class where LD(H) represents the Littlestone dimension of H. For

---

any H that has LD(H) < co, Aunit achieves an expected error bound M Bp (Aunit) S (LD(H) with linear querying strategy A (t) = O(t) where A is an input parameter.
2. Concept Class Learnability in the Woand--redietion Setting. Second, we show that non- trivial concept classes aren't ten't learnable within the Wlnd-prediction setting. Letting H be any concept class that contains a classifier that labels two points differently, then any learning algorithm, adaptive non-adaptive, is not learnable in the blind- -ind-prrdiction setting.
Theorem 1.2 (Informal Version). For any H and two points Iı, 422 E X such that 3h H where l(x1) # h(x2), then for any learning algorithm A, the expected mistake-bound M MP (A) 00.
3. Adaptive Learners for Pattern Classes. As our third result, we investigate what types of learning algorithms are required learn pattern classes under continuous data streams. In Section 4.3 we design a continuous pattern class P. where each pattern P E P is a continuous sequence of point-label pairs (X,, Yo) that is not learnable by any random sampling algorithm such as Aunit. Additionally, we construct an adaptive learning algorithm that successfully learns P with zero expected error. This important example signifies a learnability gap between concept classes and pattern classes.
4. Discrete Data Streams. Fourth, we develop theory for realizable learning of pattern classes under discrete data streams in the blind-prediction setting for deterministic learning algorithms. We characterize a combinatorial quantity called the query-learning distance or QLD for discrete pattern classes P with a query budget Q E N U [0). We show that the optimal mistake-bount given Q queries, MM))), is lower bounded by QLD(P, Q). Then, we construct a deterministic learning algorithm whose optimal mistake- bound upper bounded by QLD(P,Q)
Theorem 1.3 (Informal Version). For discrete pattern class P and number of queries Q, the optimal mistake-bouud -ound MP(P) = MDD(LLLD))))
1.4 Related Work
An extensively studied area in online learning theory closely related our work is the round-by- round learning of concept classes from discrete data streams in the realizable setting. Littlestone (2) successfully characterized the types of concept classes H that are learnable under an adversarial online setting which is now famously known as the Littlestone dimension or LD(H). Later, Daniely et 3 extended this result to the multi-class setting, showing that (.D(H) also characterizes multi-class learnability. A recently explored setting called self-directed online learning shares an important trait with our learning frameworks which is adaptivity in selecting points where Devulapalli and Hanneke 44] constructed a dimension, SDimm (H), characterizing learnable concept classes.
While traditional approaches assume that the learner receives the true label after each round, our study diverges by focusing on frameworks where feedback is only provided when actively queried by the learner. Our work is conceptually aligned with the area of partial monitoring, which investigates how various feedback constraints influence learner's 's ability to minimize regret. A series of studies have established optimal regret bounds across different online learning scenarios, structured as discrete data streams with diverse feedback mechanisms 11
A core principle within learning frameworks is the ability of a learning algorithm to selectively query at different time-steps within a data-stream which is shared by stream-based active learning approaches. Several works within the field have explored theoretical guarantees of active learning in different variations of the stream-based setting [12H15]. However, a crucial difference between stream-based active learning and learning models in this work the decision query at particular time is carried out before the current instance is observed.
2 Learning Frameworks
2.1 Basic Definitions
Let X' and y arbitrary, non-empty sets where X' referred to as the instance space and ) the label space. A concept class H Ç yix consists of functions f X + Y. Depending the context,
3

---

we will specify if we are considering a multi-class setting where ( 2 2 or binary classification
setting where y = {0. 1}.
To define continuous data stream, we use the notation (Z+)e20 = (X,, Ya)e20 to define a point and label pair Z = (Xe; Y2) for each t IRzo- A continuous pattern class P is defined as P S C((,,, (22) where ((x,, (2)) represents the collection of all measurable continuous- time processes on the space X' V. Each pattern /' E P is then continuous-time process (Z))20-
We now proceed to define discrete pattern classes and subsequently. discrete data streams. Let 2 X' x y where E Z and (æ. y). Define - (X )) which is the set of all countably infinite patterns. Then the discrete pattern class P C 2 Both continuous and discrete pattern classes are referred to P so it will be clear from context which type of pattern class we referring to. It then follows that a discrete data stream (Z+) = (X,, Y)) Y) lives in the space g00
2.2 Update-and-Depluy Setting
In this learning framework, aim to describe the online learning game that occurs between learner and an oblivious adversary. An oblivious adversary is an adversary impervious to any of the learner's 's actions; in other words, the adversary does not adapt its strategy based on the learner's 's actions. As result, the oblivious adversary fixes the entire data stream in advance of the learning process.
Denote by F class of predictor functions f. With D representing the timestamps of the data stream, either discrete or continuous, then f X xD + y is designed to make a prediction at every timestamp t E DD. In the update-and-deploy setting, we consider the learning algorithm A and the predictor f to be separate entities. Denote by Q. (t) = {(Xr, Y,,,, (X1,, Yt, ...} the set of queries made by learning algorithm A before time t. Intuitively. a learning algorithm is a mapping A : (X' x y)) - I where (X' x)))" corresponds the set (())). Formally, A((X(t> Ya),.., ..., (X),()), (a)( outputs
predictor f E F given the history of previous queries at(t). It's important to note that we only consider learning algorithms that have linear querying strategy or Qa(t) (t).
Assume the adversary has selected a data stream (Zi) For each E D. the predictor f produces predictions Y, = f(X,, t) given X, and t. On timestamps E D that the learning algorithm A decides to query, the following procedure occurs:
1. The learner A makes a decision to query and receives the true point-label pair (X,, Yt).
2. A updates the predictor f with (X,, Yt).
3. f is redeployed as the new predictor.
It's important to note that the data stream selected by the adversary is constrained be realizable. If the realizability is with respect to concept class H, then 3h E H, Vt E D, ((x,) = Y. If the setting is studied under a discrete pattern class P. then the pattern is considered realizable (X,, Yi) P.P If 'D represents a continuous data stream and P a continuous pattern class, then the pattern (X,, Yi) P implies realizability.
2.3 -ledd-Prediction Setting
For our second learning framework, we describe the online learning game between the learner and an oblivious adversary. As similarly described in Section 2.2 an oblivious adversary acts independently of the learner's 's actions and fixes the entire data stream beforehand.
Let A be any learning algorithm and let Q((() be the of queries made by a learning algorithm A before time l. As mentioned in Section 2.2, we consider algorithms with a linear querying strategy where Q (1) O(t). Letting DD be the timestamps of the data stream, A is described as mapping A: (A' x ) x DD' + y where (X x y)* corresponds to the set (t)... At any time i, A only observes the current timestamp and the history of queries (t) when making prediction Y, If it decides to query, then A witnesses the true instance-label pair (X., Y.).
Assume that the adversary has selected a data stream (Z))Ee. For each E D:
1. The learner A selects a prediction Ý, V.
4

---

2. If the learner decided to query, then the pair (X,, Y2) is revealed to the learner.
It's important note that the data stream selected by the adversary is constrained be realizable. Refer to Section 2.2 for realizability regarding concept classes and pattern classes.
2.4 Integral Mistake-Bounds
To capture the optimal behavior of learning algorithms under continuous data streams, formalize the notion of integral mistake-bounds. Since we consider two separate settings, we construct general mistake-bound and then differentiate from context which setting the mistake-bound operates under.
Due to their nature, pattern classes subsume concept classes so we define all the mistake-bounds with respect to pattern classes. Let D Rz0 which denotes the timestamps of a continuous stream. The pattern class representation of a concept class H, or P(H), defined the following way: P(H) {X,, 220 3h H, Vt D, h(X,) = Y, J. It is important to note that assume that each pattern P E P for any continuous pattern class P is measurable.
Given a continuous pattern class P, learning algorithm A, and some realizable continuous data stream (Z)) the quantity M (A,,, (Z))200) represents the expected error A makes on the data stream (Z))20 given P. Formally,
[ L[A(X))
MBp(A, (Zi)eoo) = lim E
# Yd dt
T-000
To define the optimal mistake-bound for P, we take the supremum over all patterns the class:
M MBp(A)
sup PPP)
MBp(A, (Z))2o).
Finally, we obtain the optimal mistake- bouuuke-bound for the pattern class P by taking the infimum over all learning algorithms corresponding to the learning setting bolind-predictto or update-and-ddploy)
M Bp inf (B)) A
3 Update-and-Deploy Setting: Learning Concept Classes from Continuous Data Streams
3.1 Littlestone Classes are Learnable
In this section, we are interested in multi-class concept classes H that are learnable in the update- and-deploy setting with learning algorithms deploying linear querying strategy. Below, we give definition of the learnability of concept class H which allows us to frame our first important question.
Definition 3.1. A concept class H is learnable if the following condition is satisfied: there exists algorithm A such that M BP(H) (A) < cc and (t( = O(t).
Question: What is the dimension that characterizes the learnability of a concept class H where finiteness implies learnability and an infinite value implies non-learnability?
Once we have defined Icarnability of a concept class H, our interest immediately swings towards the performance of different learning algorithms with linear querying strategies. Naturally, we want to understand if there exists optimal learning algorithms whose expected error is finite if the concept class H is learnable. This then leads to our second important question.
Question: Does there exist learning algorithm A employing linear querying strategy such that for every that is learnable, does M (P(H)((4 (AA) < oo? If so, does the learning algorithm employ an adaptive strategy?
The Littlestone dimension 2 is key measure that defines the learnability across various online learning frameworks. Extending this concept, we investigate whether the Littlestone dimension can similarly influence learnability in the context of continuous data streams. We propose that LD(H)

---

could be a valuable combinatorial tool for designing learning algorithms in the continuous setting. To explore this, we introduce Algorithm I or Aunif. which is designed learn any concept class with a finite Littlestone dimension, (H) < co, by using linear querying approach.
The idea behind Amuit is randomize the timestamp of the query so that the adversary has to "guess" which point in the data stream the learner will decide to target. If the timestamp of the query is not randomized, then the adversary can select data stream designed with this knowledge. A potential strategy an adversary could employ against a deterministic learning algorithm would be to present the same point again and again to the learner for every query. Since the learner has only received information about one point, the adversary can present other points in the data stream at times the learner doesn't query forcing errors occur. As result, the adversary has a strategy to force an infinite mistake-bound to a learning algorithm that employs deterministic querying strategy regardless if it's adaptive or non-adaptive.
To avoid this issue, we fitted Aunif with a randomized querying strategy. As shown in Algorithm | Aunit samples the next timestamp of the query, bg. from uniform distribution over an interval of fixed width A.
Algorithm 1 Uniform Sampler(H, A)
Require: H + (
Require: A > 0
1: V = H,t = time, starts at / = 0, by Unif ( L + A]
2: Deploy f(xr,t) t) arg (0,1) ((..))
3: while truc do
4: if bg then
5: Query at time by and receive point-label pair (Itt, Vl.))
6: Update V = V(er,,88g))
7:
Redeploy f () arg (a0.) (D(((e))))
8:
by ~ Unif A]
9: end if
end while
In Algorithm 1 notice that the predictor function f follows that of the Standard Optimal Algorithm, or SOA, defined by Littlestone [2]. Since the LD(H) < oc, and if the prediction differs from the true label on a query point, then the Littlestone dimension of the subsequent version space reduced by at least 1. This property follows immediately from the analysis of the SOA, so the learner knows that it needs only LD(H) successful queries to fully learn H from the continuous data stream.
Additionally, note that while Algorithm D decides the next tg after the previous query finishes, this is done non-adaptively. The timestamp t, not dependent on the true label witnessed by the previous queries; it's simply sampled from uniform distribution. As result, the set of query timestamps are produced in non-adaptive fashion by sampling the next query from an interval of width A.
Theorem 3.2. Let Aunil be Algorithm 7 For any H that has LD(H) 00, My (Aunit) S (LD(H) where A is an inpul parameter from Algorithm 7 Since Q (1) = O(), then H is learnable.
Proof. For a given with LD(H)- < oo, we show that the expected mistake-bound of algorithm Amni is bounded proportionally to the size of I.(H)) using línear querying strategy. Since Annif deploys the SOA as its predictor, then the mistake-bount of Auait is inherently tied to LD(H). In other words, if Aunif makes LD(H) successful queries, where success implies that the SOA's prediction is incorrect on the query point, then the version space has Littlestone dimension of implying that any consistent classifier subsequently makes zero error onwards. Our analysis first focuses on bounding the maximum expected error Ausif makes until its first successful query. We repeat this analysis LD(H) times to show that M BP( (Aunit) & ALD(H) with linear querying strategy.
As starting point, we define all the necessary quantities in order to begin the analysis. Since our learning model assumes an oblivious adversary, it selects a continuous data stream (7, (2))20 realizable with respect to some target concept f" e H before the learning process begins. Let the random

---

variable B3 be an indicator random variable representing the success of the 1 query on the process (Zi)12o More specifically,
BE {
if the ht query is successful
else
takes a value of if the kthh query succeeds. Then, we define P(B, = 1 0, BR-2
O,..., B1 = 0) C which is the probability that the learner has successful query on the htth try given that the previous k - 1 attempts failed. EK can be equivalently viewed as the probability of the learner making an error on the k4h interval because a successful query results in receiving mistake-point, or a point the predictor incorrectly predicts. Since Aunit selects its k query i from A-sized interval, then Aeg represents the total potential error the learner makes on the htth interval.
Our primary interest is calculating the expected error Aunif makes until reaches (H( successful queries. Since the learner Aunit deploys an SOA predictor, LD successful queries where the predictor is incorrect guarantees the learner to narrow down on the right set of consistent classifiers.
We approach this by first computing the expected error that the learning algorithm makes until its first successful query. It's important note that Annit does alter its querying strategy regardless of the number of successful queries it has received; it constantly chooses its queries from intervals of size A. As a result, after the learner receives its first successful query, the same process repeats again until Aunit finds it second successful query. So, we focus on bounding the maximum expected error Aunit will encounter until its next successful query for the data stream (Z))22o.
Let A be a function that represents the maximum error the learner receives until its first suc- cessful query given the values of the random variables B1, B2, Formally speaking, let A A - = (1 B,). Each Âc₃ represents the error region in the 1tth interval given that the previous k 1 queries failed or each B, = 0 for all i I & - 1. It's important to observe that A is the maximum error the learner receives until the first successful query. As an example, let B, = 1 for some N and B, 0 for all j < n. Then A includes the cumulative error from the first n 1 intervals and the entire potential error on the th interval (represented as Ae,) even though the th query, which is successful, can lie anywhere within the Ae, error region located inside the th interval. Now, we compute the expectation of A.
A(B1, ...). = A(c1 + e1 B1) e3
B1) B2) + +...)
E|A| =
E
A
2 (1 B.)
A
E
[1 - B.)
1=1
k=1
P(B = 0, O..., BB- 00) = A
II 11 -
km
km
Since we are interested in the maximum expected error the learner Auait encounters until its first successful query, we want to bound the term A Σx= {I - <,) by selecting the optimal values for c1, c..... Notice that the expression is recursive in the sense that if we pulled out the first k terms, the structure of the sum doesn't 't change. We then exploit this fact to bound the total value of
the sum. Let U = s A D and so forth. Then,
1= [(K) (1 {()) where { = ε() = E2, and so on
U = sup
( (())=
sup Ad(1) + A(1 - (1)) 2E|0.1|
Σ
aB) ai))
k=1
k=
< sup
Ap + (1 pp)
sup
A Tk) - {())
< sup
Ap + (1 - p)U
pE|0,1]
1=
Ap
< sup pE[O.1] 1 - (1 - p)
A.
Therefore, we show that E[A] A.
At the beginning of this analysis, we assumed some adversarially chosen data stream and target concept, so the result E[A] < A holds for any choice of (Zi)20 realizable with respect to H.
7

---

Now, we repeat this analysis LD(H) times. Therefore, M BP (Auit)) & ALD(H) where Auunt (t) = Ott).
In Theorem 3.2 we establish that if (D) is finite, then H is learnable in the peddat--and-depee setting. This leads to our second result, which demonstrates that (D( serves as the defining dimension for the learnability of a concept class H in this context.
Theorem 3.3. If LH) =x, Qa(t), M MP (A) = implying that H is not learnable.
xc, then for any learning algorithm A with a linear querying strategy
For the formal proof of Theorem 3.3 refer to Appendix A.I, While the results hold for O(t) querying strategies, an open direction is to investigate algorithms with a broader range of querying strategies.
Brind-Prediction Setting: Learning from Discrete and Continuous Data Streams
4.1 It's Impossible to Learn Non-Trivial Concept Classes from Continuous Data Streams
In this section, we discover what constitutes learnability of multi-class concept classes in the blind- prediction setting. We borrow Definition 3.1 to describe the learnability of a concept class H.
Since the blind-prediction setting is harder variant of the anddee-- setting, we frame similar question asking if the Littlestone dimension the right characterization of learnability.
Question: What characterizes the learnability of concept classes H in the blind-prediction setting? Does LD(H) play a pertinent role?
To answer this question, we come up with a simple concept class H that proves to be unlearnable in the blind-prediction setting. This result comes in stark contrast to the results found in Section 3.1 Below, we detail Theorem 4.1 and Corollary 4.2
Theorem 4.1. Let {h} and X (aı, with h(21) 0 and h(x2)
Then, for any learning algorithm A with linear querying strategy, MB = 0o so H is not learnable under the blind -iidd-prediction setting.
For the formal proof of Theorem refer to Appendix
Corollary 4.2. If H is concept class such that 3h E H and 3z,, x2 E X such that h(x1) & h(z2), then H unlearnable in the blind-pree -reedipreiitton setting.
Proof. Let H1' h and X" (x1,,23 x2). From Theorem 4.1 it was shown that M Bp (A) 00
for any learning algorithm A with linear querying strategy so H' is unlearnable. Since H' C H and 11, 22 E X, it follows that M = 3o so H is unlearnable..
4.2 Are Adaptive Learners Required for Pattern Classes?
In this section, we demonstrate the necessity of adaptive learning algorithms for effectively learning pattern classes. Since concept classes represent a set of functions, and functions can be thought as established input-output pairs, different permutations of these pairs don't result in different functions being realizable on the sequence. As a result, non-adaptive learning algorithms are sufficient in learning concept classes but adaptive learning strategies may be required for pattern classes. Below, we construct an example of continuous pattern class P that is only learnale by any adaptive sampling algorithm.
Pattern Class Example Let H be a multi- concept class with LD(H) = co. For E with t2 t1, define P(H, t1, Y.). Then, P(H,t),,22 = {(X,, Yi)eelt.))) (P,tz) and (Xe, Yi)re(titt)) = P]. P(H, f1. t2) corresponds to the set of realizable data streams between I and l2 and ((H,1,12) ensures that at time I the data stream encodes the entire pattern from & to to in Xt, Let N {n {0} x No0 Vi E n(i + 1) > n(i)} and
{(X,, ta) : 3h H. E (t,,t)), AP E P(H, 12) such that (X,, Yo,) =
8

---

Q = fq E {0} x Q in E N. (i) < q(++)) < m(i+1)} Then, we define the
continuous pattern class P in the following way: P = UqEe (TI P(H,q(1)) q(i + 1))) where I P(H, q()), q(2 +1) represents infinite Cartesian product among the valid patterns in each interval dictated by q.
Lemma 4.3. For the update-and-deploy setting, any random sampling algorithm A Awth linear querying strategy Qa(t) has M (p)) = cc.
Proof. Let A be random sampling algorithm with linear querying strategy Qa(t). We will now construct a continuous data stream (Ze)20 that is realizable with respect to in a randomized fashion and prove a bound on the minimum expected enror. Randomly select vector q Q.
To construct such a continuous process (Z)) we first decompose R2z U (2q(n): 2q 1)).
The idea behind this decomposition is to construct a pattern on each interval that corresponds to a randomly chosen E H. To do this, we take each interval [2q(z), 2q(n + 1)), letting (2 + 1)) k for some & E N, and break it further down such that [2q(n), 2q(n + 1))
[q(n+1)-q(x)) (j 1) + 2q(m), (q(n+1)-q<)) j + 2q(n)) By doing this, we can take an ar- -=1
bitrary root-to-leaf path from Littlestone tree of depth 2k, and then paint each sub-interval with an instance-label pair on this path. Since the number of sub-intervals is greater than the number of
queries made by the algorithm A, on some set of sub-intervals the algorithm A is forced to guess the true label.
As described above, assume the interval [2q(n), (n))))) for some n E N, letting Q. (2( 1)) k for some k E N. Since LD(H) = oo, there must exist a Littlestone tree T where the minimum root-to-leaf depth is at least 2k. Then, let
{(X,, Yi),... (X2x, Y2+)] corre-
spond to a randomly chosen root-to-leaf path. For each E {I,.... 2..), populate the interval (q(n+1) 1)- q(a)) (j - 1) + 2q(n), (q(x+1)-q(a)) j + 2g((n) with the pair (X,, For simplic- ity. let 1 = 1)-++))q(())) (j - 1) + 2q(n), (ain-1)-q(nn j -+ 2q(n)). For the process at time t == (n), let 7,- = (P, (q + 1)) where P= = (X1, Yi)ee,, (29(m)) U - (X))
&
k
It's important to note that the constructed continuous process on the interval [2q(n). 2q(n + 1)) lies in P(H, (n(n), 2q(n n + 1)). The first point in the interval corresponds to the point (P. 2q(n + 1)) and PE E P(H, (n). 2q(n + 1)) since it was generated from a root-to-leaf path in T which is realizable by some h E H.
Now, we show that the sub-intervals A does not query in the interval (2q(n), + 1)), A, the minimum expected error is equal to [q(n+1)-q's The analysis closely mirrors that of in Theorem 3.3 Let the jth sub-interval be sub-interval, where < j < 2k, where A does not query. Let E {t 1j= A(X,) # Yj} and Eo {t 4 A(X,) 7 Y where Yý is the other label in tree T for the point X,. Then, E [ 1[A(X,) A Y.] de = E [b(E)) = Y, + u(Eo) = -Y]]l =
k
Yıll + (E)u(Eo))E YY; Y; where μ is the Lebesgue measure. Since a random branch was chosen within the tree T, there was an equal chance of selecting Y- = Y, or Y, - Yy. then Elu( EE) [1) = Y,ll + E = Y/1l = Elu(Eo)) + (lu(E,)]
Elu(EE)
Elu(Eo) + ((E
(qin+1)-(())) Therefore, the learner AA accumulates an expected error of
(q(++1)-q(n) on each interval it doesn't query. Since the learner has only k queries, it can only query in at most & of the 2k intervals. At minimum there will exist k intervals that haven't 't been queried by the learner. Let /1, /,..... Ia represent & of these intervals algorithm A does not query. It follows that
2q(x++) 1[A(X,) # Yi] dt > Σ E [Jr, L[A(X.) + Yi] dt = q(n + 1) - (n)).
E
[2q(m)
Since n E was chosen arbitrarily, then holds for all intervals [2q(n), 2q + 1)). As result,
[ 1[A(X)) # Yil dt
Mex((nN:T22(1111
2q((+1)
lim E
lim +00
Σ
E
1[A(X,) + Y/ dt 2q(+)
T T-000
max MeN:: 22(
lim T-000
Σ
q + 1) (i)) = 30.

---

Since we constructed the process (Zi) by randomly selecting branches from Littlestone trees for each interval, we appeal the probabilistic method to show that there exists fixed choice of continuous-proct procosss (Ze 222 such that M (A, (7)) co. Therefore, M Bp(A) co. IT
Remark 4.4. It can be shown that the results of Lemma 4.3 directly extend for the hiiddpreeiccton setting.
Now, we turn to an adaptive sampling learning algorithm, specifically Algorithm 2 that achieves M (pp((aggg (Algooorihhm 2 O. Specifically, we show this result the blind-reddcction setting. As will be proven in the analysis of Lemma 4.5 Algorithm Baaihhmmmppppiiiiiie specifically queries at the timestamps where makes at most countable number of mistakes because only countable number of such points exist in any continuous data stream realizable by P so has an expected error of with a linear querying strategy.
portion of the future continuous data stream is revealed. As a result, Algorithm P
Algorithm 2 Adaptive Sampler(P)
1: time (starts at 0), tg = 0, initialize be some function f R20 + y
2: while true do
3: Predict f(t)
4:
if't bg then
5: Query and receive point-label pair (X, = (P.n)
6: Update f(t) = Y, for all (X,, Yi) P
7:
fy --m
8:
end if
9:
end while
Lemma 4.5. Let A be the adaptive sampler in Algorithm and M Bp (AA) in the blind-prec -indppredittion setring.
2 Then, the querying strategy Qa(t) S
Proof (Sketch). Let A represent Algorithm stream. Since each q E has q(1) = O, then for any P P. must be the case that Zo (Xp+ Y) where Xo reveals the full sequence until time Yo- Algorithm has its first query time t 0 and fits the predictor f to output the labels of sequence Xo for all time E (0, Yo). Since (Z)) follows the exact sequence described by X, until time = Yo, then fo 1[A(X,) + Y, dt
and and (Z)) = P P be any adversarially chosen data
implying that IE [A(()) * Yj] dt] O. At time Yu, A queries at exactly the right time to gain information about future portion of the data stream (Z))>0 with the same analysis repeating continuously. As a result, M (A,, (Z)) = and since (Z))20 was arbitrarily chosen, then
(BA with QA(t)= st.
Remark 4.6. The results of Lemma 4.5 can also be extended to the update-and-deplog setting.
4.3 Learning Pattern Classes from Discrete Data Streams
As witnessed in the example from Section 4.2 one can construct rather complex pattern class to model almost any sort of structure. While the power of pattern classes is inherent in their ability to express complicated relationships, directly analyzing their behavior under continuous data streams prove to be intractable problem.
without foundational understanding
As result, we initiate study of pattern classes under discrete data streams to provides a foundational understanding of how learning algorithms handle data arriving in distinct, separate chunks. This framework simplifies the complexity by allowing us to focus on key principles of sequential decision- making such as incremental learning. By developing theory in discrete context, we can potentially employ these insights that can prove to be crucial for tackling the more complex scenarios of learning under continuous data streams. In Appendix B we develop complete theory on realizable learning of pattern classes in the blind- predd-prediction setting under discrete streams.
10

---

References
[1] Shay Moran, Ohad Sharon, Iska Tsubari, and Sivan Yosebashvili.. List online classification. In The Thirty Sixth Annual Conference on Learning Theory, pages 1885-1913, PMLR, 2023.
[2] N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285-318, 1988.
[3] A. Daniely, S. Sabato, S. Ben-David, and S.
Multiclass learnability and the ERM principle. Journal of Machine Learning Research, 16(12):3377-240 2015.
[4] Pramith Devulapalli and Steve Hanneke. The dimension of self-directed learning. In Interna-
lional Conference on Algorithmic Learning Theory, pages 544-573, PMLR, 2024.
[5] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
[6] Gergely Neu and Gábor Bartók, An efficient algorithm for learning with semi-bandit feedback. In International Conference on Algorithmic Learning Theory, pages 234-248, Springer, 2013.
[7] Gábor Bartók and Csaba Szepesvári. Partial monitoring with side information. International Conference on Algorithmic Learning Theory, pages 305-319, Springer, 2012.
[8] Gábor Bartók, Dean P Foster, Dávid Pál, Alexander Rakhlin, and Csaba Szepesvári. Partial monitoring-clasiiiccaan classfficatinnnn regret bounds, and algorithms. Mathematics of Operations Research, 39(4):967-997, 2014.
[9] Noga Alon, Nicolo graphs: Beyond bandits. In Conference on Learning Theory, pages 23-35. PMLR, 2015.
Ofer Dekel, and Tomer Koren. Online learning with feedback
[10] Tor Lattimore and Csaba Szepesvári. An information-theeortiic approach to minimax regret in partial monitoring. In Conference Learning Theory, pages 21 2111-2139. PMLR, 2019.
[11] Tor Lattimore. Minimax regret for partial monitoring: Infinite outcomes and rustichini's regret. In Conference on Learning Theory, pages 1547-1575. PMLR, 2022.
[12] Yoav Freund, H. Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Machine Learning, 28:133-168, 1997.
[13] S. Dasgupta, D. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. In Advances in Neural Information Processing Systems 20, 2007.
[14] Liu Yang. Active learning with drifting distribution. Advances in Neural Information Processing Systems, 24, 2011.
[15] T.-K. Huang, A. Agarwal, D. J. Hsu, J. Langford, and R. E. Schapire. Efficient and parsimonious agnostic active learning. In Advances in Neural Information Processing Systems 28, 2015.

---

A Proofs for Learning from Continuous Data Streams
A.1 Proof of Theorem 3
Proof. Let A be a learning algorithm with linear querying strategy QA()). Assume some concept class with LD(H) = -o.. For every n E N. we show that there exists an adversarially con- structed data stream, (Zz)rzo. such that M (A, (Z))r2o) 2 n. Since this holds Vn E N, then M (P(H)) )22 M (P))))( (A, (Zz)120) = co.
Our learning model assumes an oblivious adversary, so we will construct a continuous data stream (Z))20 beforehand that is realizable with respect H. However, we construct (Z))s20 in randomized fashion and bound the minimum expected error of this randomly constructed process. Then, at the end of the proof, we will call upon the probabilistic method to show that there exists continuous process achieving at least that expected error.
Take some N and let Q4(4n) k. Since LD(H) oc, then there must exist Littlestone tree T where the minimum root-to-leaf path of T is at least 2k. Consider a random walk in starting at the root node that picks with probability 1/2 the left child or the right child and descends level-by-level until it reaches a leaf node. Let o = {I11, 31 ..... (12k, 3/2k) correspond to the root-to-leaf path produced by the random walk T. Note that H, (h H ((X,, Yi) E a, h(X,) Y,), the subset of the concept class consistent with the sequence a, will have at least one classifier due to the guarantee provided by the Littlestone tree that every branch in T is realizable by some h E H.
Now, we describe the construction of the continuous process ( (Z))220 using the sequence a. De- 2k compose 40.4n) in the following way: [0, 4n) = - [ (j 1), 5) For the jth interval where 1 j S 2k, Vt E 2 (j - 1), 2m 5), define Z, (X,. = (j). On the time interval [0, 4n., if one segments the process (Ze) into intervals of size 2n
K. then for the jth interval, where 1 i j 24, the process contains the point (j) for the entirety of the interval. For t 2 4n, then define Z, = (X,, Yi) to be a point-label pair (X', ,Y) such that for each h E h(X') = Y'.
Now, we show that on the intervals A does not query in the time period [0, 4n). the minimum expected error is equal to +. Let the jth interval be an interval, where 1 < j < 2k, where A does not query.
Let E1 = {t E 1 (j 1), 2n : A(X,) * }j} and Eg = (t E 2 (j 1), 2n A(Xi) * Y
2g i 2m (i-1) 1[A(X,) # Y.l dt
where Yj is the other label in tree T for the point Xj. Then, E (F( [ = Yj] + (Fo) = Yj] = ())(FE))
En E [V, Y;1] + BB Fo) 1 [V, Yj]
where ju is the Lebesgue measure. Since a random branch was chosen within the tree T. there was an equal chance of selecting Y, = Y2 or Y, = Yj. then E|u(E))]
Y,] + Elu(E))) = Yī1 = (ll(E))]]/ + ([u(Ei)] = Elu(Eo) + /2 Z n//k. Therefore, the learner A accumulates an expected error of n/ on each interval it doesn't query. Since the learner has only & queries, it can only query in at most & of the 24 intervals. At minimum there will exist k intervals that haven't 't been queried by the learner. Let 41, ..., La represent is of these intervals algorithm A does
not query. It follows that IE [ 1[A(x.) + Y.] de 2 E k
IE [Jr. [[A(X.) # Yd] dt n.
The strategy chosen to prove a lower bound on the expected error to be n relied on generating continuous time process by randomly selecting branch within the Littlestone tree T which corresponds to a random selection of a target concept. However, we appeal to the probabilistic method to show that if the expected error for algorithm A is at least n., then there exists a fixed choice of a aantinuous-proces, (Zr)r20 such that M BP(H) (A, (Zz) (Zz))=)) Z n. Since we show that for every n E N and any learning algorithm A there exists an adversarial strategy (Zz)e20 such that M (P (A, (Ze) 2 n, then the adversary can force the learner to make an arbitrarily large error implying that M BP (A) (Z))2)))20 M MB (A, (Z))2o) = so H is not learnable. O
A.2 Proof of Theorem 4.1
Proof. The essence of this proof lies in the simple yet effective scheme the adversary can employ to force any learning algorithm A with a linear querying strategy (() to have M ()) = co. The idea behind this adversarial approach is to divide the timeline, R20, into small enough intervals
12

---

where each interval is populated randomly with point-label pair (x1, 0) or (z2, 1) such that A is forced to guess the right label.
We first describe the construction of the continuous data stream (74) realizable with respect to h. As previously done in Theorem 3.3
randomized approach in constructing (Z))r20 to prove a bound on the expected error. This randomized approach draws upon a family of continuous processes to show that the expected error is some minimum value. However, the mistake-bounde require a singular continuous process to yield that error. So, we apply the probabilistic method to prove the existence of a continuous data stream that can be fixed beforehand that achieves least that expected error.
We first describe the construction of (Zi) in randomized fashion. Decompose Rz0 -n= [n 1, n2. For every E N. let Rn (n) Then, split (n-1, n) into 2k, intervals each of size 2
_ such
that [n - 1, n) = احور n 1+ 2ka (j 1), n - 1+ - Let ~ Unif(1(21, 0), (122, 1)) 2)))))) be a sequence sampled uniformly from the space {(z), 0), (22, 1)), Then, construct the process (Ze)120 such that Vn E N.
Unif(((( 0), (22, 1)] 22)), ). Vj E {I..... 2 J. Vt E [n + Zka 1), n + 1) then Z, = (x,, Y,) = ai). Essentially, we assign the point-label pairs (z1, 0) and (x2, 1) randomly to each interval to construct the process.
Letting E N. then algorithm A makes at most kn queries in the interval [n - 1, n) implying at least k, of the intervals within [n - 1, n) pass by the learner with no query. On the intervals the learner does not query, we show that the learner's expected error is equal to TF," For some S S 2k,- let the j interval within [n - n1 contain no queries from A. Then, let Eg and Ei represent the portion of the jth interval that A predicts as a or respectively. It follows that the expected error of algorithm A on this interval is equivalent to (5 [XY = 0] + pu (o) A[Y, = 1]] where Y, is the true label for the 5th interval and is the Lebesgue measure. Since there's an equal probability 0] + L[)) = 1]] AR.. There are
of Y, or Y, 1, the expected error E[p(E,) at least kn such intervals where A does not query on [n - 1, n) which implies that the minimum expected error is equivalent to 1
Since we decomposed Rz0
U - 1,n), then limy E [ 1[A(x)) + Y. dt)
>
limy E _T_ L[A(X,))))))))))) [__X)( * Yj]
limT E co. We used randomized method to construct a family of continuous processes such that the expected error of a randomly cho- process reaches co. Applying the probabilistic method, there exists continuous process whose expected error also reaches oc. Therefore, M BPCH) = suP(Z)) M MB (A, (Ze)za)) = co for any learning algorithm A with linear querying strategy @x(() so H is unlearnable.
B Learnability of Pattern Classes from Discrete Data Streams
B.1 Query-based Feedback Online Learning
In this section, we are interested in developing a theory of realizable learning of pattern classes under discrete data streams in the plind-prediction setting. While general theory of pattern classes under discrete data streams would involve considering the agnostic case as well, we focus on the simplest scenario which is realizable learning under binary label space y {0, 1} assuming deterministic learning algorithms. While this learning setting might seem quite restrictive, no such theory exists for the learnability of general pattern classes so we provide the first results in this space. We also develop this theory in the blind-prediction setting and a future direction of this work would be to characterize it in the update-and soaite--nd-dee and-deploy setting.
In the blind- prediction setting, assume a non-empty discrete pattern class P and some budget of queries Q. Assume deterministic learning algorithm. One full round in this setting occurs in the following fashion at every E N:
1. The learner makes a prediction Y, y and decides to query or not.
2. The learner reveals Y,
3. The adversary selects the true label Yg.
13

---

4. If the learner does query, then the adversary reveals (X,, Yi) to the learner.
The primary constraints governing this setting are realizability with respect P. Letting (2))²1 (Xe, Yi) be the sequence of data points and true labels, then (Z)) E P to be considered realizable. It's important note that the learner any given time makes a prediction Y, based solely on the current timestamp and history previous queries.
B.2 Query-based Mistake-Bounds
We tur to cuistake-buunde to effectively capture the minimum number of mistakes an optimal deterministic learning algorithm will make.
The number of mistakes a deterministic learning algorithm A makes given a target pattern/discrete data stream P (Z+)²= E P and budget of Q queries is denoted (A, P*). Formally, (A P*) can be understood as
Mo(A, Σ 1(((x,) # Yi}-
To consider the mistake- mistake-bound the learning algorithm A on P given a budget of Q queries, we get
Mg(A,
sup Mo(A,P") p. PI
Finally, obtain the optimal mistake-bound on P given Q queries, we take the infimum over all deterministic learning algorithms.
MQ(P) = inf MQ(A,P)
B.2.1 Query Trees
In this section, we describe certain type of tree, the query tree, which we will be used to capture the learning framework explained in Section B.1 Given the budget of queries Q as an input, the query tree can be used to depict the evolution of the game in the blind-prediction setting. The name query tree comes from the fact that these trees describe the evolution of the game from the learner's perspective through queries. As a result, these trees are used in conjunction to provide upper and lower bounds on the optimal mistake-bounde for deterministic learning algorithms.
Definition B.1 (Query Tree), A query tree T is defined tuple (V, E, Q) where V is a collection of nodes, E is a collection of edges, and Q is the query budget.
T' is a rooted binary tree where each node has at most two children which are referred as the left child and the right child.
Each node V3 E V corresponds to some timestamp LN where Vj = li-
The root node is represented by E V and corresponds Vi l1 where is the timestamp of the first query.
vV V. V / Parent(V), then V' < V
Ve E where
(V', V) with V Parent(V). then the edge weight is defined as w(e) = y with y = 0 if LeftChildV"') or = 1 ifV = RightChild(V'..
Every root-to-leaf path (V1,.., V.) has n Q + 1 nodes.
B.2.2 Query Learning Distance Blind-Prediction Setting
In this section, we describe dimension based on a family of query trees that correctly characterizes the complexity of learning pattern classes the blind-prediction setting. In the following subsections, first tackle the case when Q 0 and then characterize the general setting for Q > 0.
14

---

Special Variant: Blind Learning What if the learner wasn't 't allowed to even query once? How would this affect the number of mistakes the learner would make? We call this special setting the blind learning scenario since the learner receives absolutely no feedback on any round of the game; only the current time-step is given as input. While Section B.T describes the exact procedure round-by-rowd by-round, closer look at the intricacies of this scenario can reduce the game into a simple two-step procedure. The learner is not allowed to query a single time; so this implies that the learner cannot use information about the sequence itself to update its algorithm. Additionally, since the learner is a deterministic learning algorithm, this implies that an all-knowing adversary has complete knowledge about the learner's 's prediction at every timestamp. Combining these two facts together, it follows that the learner's s predictions are independent of the true labels and the adversary can simply select the sequence of true labels all at once. Formally speaking, the entire game can be described in the following two steps:
1. The learner selects prediction vector ý E 1
2. The adversary selects the true outcome vector y E {0, 1
Then, the number of mistakes is equivalent to E== ( + y()) V yl where | stands for the Ll-norm. As is consistent with the framework described in Section B.1 the vector y must be realizable with respect to the pattern class P such that AP E P where v(X,, Yi) P, Y, yt). Below, we present an important lemma that characterizes the optimal mistake- bound Mo (P).
Lemma B.2. If the number of queries Q 0, then
Mo(P) = BBindLcariingDinensioff =
inf sup 1& y 8-f0.11 yEPs
where ||| represents the L. -diiittae and pV = (y E 13. EP PP Y,) E P.Y. (t)} which represents the set of infinite binary vectors that are realizable with respect to P.
Proof. We divide this proof into two parts by devoting the first half to lower bound proof showing that
S. MP)) The second half of the proof is devoted to showing that there exists an algorithm A such that (A, P) BlindLearningg (ameninnDmensiio(())) Finally, combine these two statements to ultimately show that BlindL wew.eeaaaannnnnnisiiii (P) = Mo(P).
We first show the lower-bound proof by letting A be any deterministic learning algorithm. Then, Mo(A, P) is the mistake-bound of the learner AA given the pattern P E P. Let y' be the output of A given queries. This is equivalent to Mo(AA,) P) = ly' yl where (x, y) = P. (M P) is the maximum mistake-boutt of the learning algorithm A over the entire pattern class P. More technically, represent Mo(,APP)
supyeps yy' y/. Since y' {0, 1) it then holds that (n supyepy 1 y| supyepv ly' y/ It follows that BlindLearingDDinnnssoo/?? P). Since A was an arbitrary deterministic learning algorithm, it then follows that < (P))..
For the upper bound proof we focus on the case when BlingLeamiinDDinenssonn Mp(P) = oo when WrindLLeaningDDmensooof?? gorithm that predicts the vector such that supyeP> 18 y inf supyePv 1y y/- Since SarndeLiinnnnnmmiiiiion (P) < 3o and y is a binary vector, then there exists vector ý achieving the minimum. directly follows that MM, P) Biindl.arningDDmenssooo By combining the lower bound and upper bound statements, we get the following inequality Dineerinnnnnnnnnnn(nnn S Mo(P) < BlindLearning DimeniooiDim)ss so Mo(P)
< 0o since oc. Let A be deterministic learning al-
Since
Mp(P) < MA P), then Mp(P) S BhineLLerningDimensson
General Setting We now define the dimension QLD or query learning distance on these family of query trees 7 realizable with respect to the discrete pattern class P given Q queries. The QLD quantity can be thought as analogous to the notion of rank of a binary tree but setup in a slightly different fashion. Below, for each T E T, we describe the query learning distance.
15

---

QLDr(P.Q.1) -1 Q) (iindl.aaminnDDDnnnnsi((())))))) + 1/i < Q]
inf
)
max [To
if + Ti
sup R1 EX
y-yl -1)())((())) # #0 0]
(1)
To +1
else
(0.11155--44111
where
To = QLDD, (0 Q,i+11
(2)
Ti = (
(3)
12 and 3. Tr. is the left subtree of T', T' is the right subtree of T, 9 is the sequence of In Eqs.
predictions. y is the sequence of true labels, Ft, the instance at time 4, and P(t.y) - (P P Vy, E y, (t) = y1 with (t) referring to the fth label of pattern P. Additionally, 4, and 4,-1 refer to the timestamps of the 7th and th queries respectively that correspond to the root-to-leaf path dictated by the recursion.
Defining QLD(P, Q) Let T(P, Q) be the collection of all query trees for the predict-ten--query setting that are realizable with respect to P and contains Q query nodes on each branch. Then, T*(P.Q) Q) = (T E ((P, Q) QLDr((P P..) k} is the collection of trees whose query learning distance is exactly k. Finally, we define QLD(P, Q) = inf (k E NU {0} (P, Q) + 6}.
Lemma B.3. For any discrete pattern class P and query budget Q E NU (0),), QLD(P, Q) S MP).).
Proof. Let A be any deterministic learning algorithm. proof by induction will be established on the pair (P, Q) taking Q = 0 to be the base. We refer to Lemma B.2 to show that VP' S
Mo(P') < (A, P'). Now, we apply the inductive step on (P',Q') where p' C and Q' < Q. then QLD(P', Q') (A,(A, The rest of the proof is devoted to showing that QLD(P, Q) S MQ(A, by deseribing an adversarial strategy that guarantees this bound.
P. QLD(P', 0)
Let E N be the first query timestamp made by the learning algorithm A. Since A is deterministic learner, the adversary has knowledge of tj. To narrow down its selection of the true labels for the first l rounds, the adversary can select an optimal query tree T based on the value QL.r((P, Q, 0) given that the root node has V = 41- Given that QLDD((P, Q, 0) follows the piece-wise function described in Eq. [ the adversary can select the larger of To or Ti (if equal, To is chosen). Without loss of generality, let To be the subtree chosen by the adversary. For the first t 1 rounds, let the adversary selects the optimal vector of true labels y given knowledge of the procedure of algorithm A. Let y represent the vector of predicted labels by the learner for the first 4 - 1 rounds. At time f, the select 21, that corresponds to the supremum in Eq. [ and set the true label y/, = O. In the special case that To = Tı, then y/, = Jt.
learner will present its prediction Dt,- The adversary
Then the number of mistakes made by the learner in the first t rounds is equivalent to ý yl lyt, -- On the remaining number of rounds, MQ-1 (AA, P(r,.)(ms, (x.) represents the optimal mistake-bound of the learner A. Using the inductive step, we can show that 1y y 1 [y,, + 0..] + +LLD(P(t (x,)) Q 1) Ty yl 1+1[v [M,, + 1i,1 MQ-1 (A, (A, ((t,))(=, ). Since (A P) is calculated as the supremum over all adversarial approaches given the algorithm A, then (A P) Z 1 Jy-li y +1 [ye, # ūr,) M ((., We..) )). Now, we show that QLD((, Q) S
y- [M,, # bt, (ol+QQDD(P (+))) ". 111) 1). Assume that the predictions made by algorithm A induce ly 1y-yl+1[ur # QT.. (a),,, (e,)))),)> Q-1) < QT. Q). Since the adversary's selection of true labels is an optimal label vector given the workings of learning algorithm A, then the adversary's 's decision aligns with the supremum in Eq. [ Then, there must exist a tree T' whose largest distance is equal to that value with t being the timestamp of the root node. Formally speaking, this implies the existence of T' such that QLDr((P, Q,0) < QLD(P, Q). If such a tree existed, then the adversary would have selected T' which violates the minimality of QLD(P, Q) and the assumption that the adversary chose the most minimal tree satisfying V 4, As a result, QLD(P, Q) < lý
y + 1 1[2,, # 9r,] + (PLD(P(. (ar.)))))))))) st,), - 1). Placing all the inequalities
16

---

together, we get
* + Q (Kyy) MG ). 1)) vt, - () which results in QLD(P,Q) S Mo.A,P)
llve, * Dt,1 + Since A was arbitrary learning algorithm, then it holds that QLD(P, Q) s MQ(P).
In Algorithm 3 detailed below, we denote by Y1 o Y2 the vector obtained by concatenating vector Y2 after vector y1- Additionally, the usage of To and Tj refer to Eqs. [2dd respectively. If T g. is used, this implies a query subtree that was either the left child if 0 or the right child if y/: 1.
Algorithm 3 BP-SOA(P, Q)
Require: P + 0
Require:
Q 2
1: R history of previously observed instances
2: y1 list of current predictions
3: O history of previous queries (Elements of O are (t, where is time, y is label)
4: = 0, t2 = [Initial query number and timestamp)
5: Select tree 7 such that QLD(Q, Q, 0) QLD(P, Q), Vf
6: Tend = 0C
7: for t = 1 to Tend do
8: if < t4 then
9: ift 1 then
10:
arg mig yE(0,]]=-1 p
sup
1 y/ [[P(.s) # 0] + QLD(P(-s):
Append ý to y: end if
12:
Predict (t), add X
14:
else if < Q then Úr
arg max, ( supm, ex sup yEfu,114-1 18: y|1(P((n.)) x(t)))
* 0
QLDT, (P(r,y)(r,, 1)
Predict de and add de yv.
17:
Receive (I), add (f, yc) to O, and add to 8n.
Set 1,t, Vf (Vi the root node of T
19:
max (To; Ti}
if + Ti else
arg min
sup 2 EX
sup ye (o.1))
(o9--y)-11((scc(t)).))) 00+
()n(+)))))
To +
V(t.))00x(0=v
Append y y%
21:
else y' arg max
y-yl-A(PPss (x...) * O0-BBinnLeamminnDiinnniioooo (P(nni) 50,))))
yE(OJ)
23:
(Bai))) Let ý be such that supyepy ( 19 y/ yyyy=inngegnn =innge((().1)- supyepy (e 18
24:
Append ý ý1
25: Set Tend 4
26: end if
27: end for
28: for tú oc do
29: Predict (t)
30: end for
17

---

Lemma B.4. For any discrete pattern class P and query budger Q E NU (0), Me(P) - QLD(P. Q).
Proof.
Let A be the BP-SOA which is detailed in Algorithm 3 A proof by induction will be
established on the pair (P,Q) Q) taking Q - to be the base case. Let p' C P. In the base
case, we execute Algorithm 3 with the inputs P' and Q 0. Since Q 0, Algorithm 3 se-
lects the vector y corresponding to the 22-24). Then, A skips to lines 28-30 making predictions according to yı. Then, we refer to Lemma B.2 to show that MaanLLLeeninnimmniooooi
and appends it to y1 (lines
I MP((') S Mo(AAgorithn) implying that Mo BlinnLearningg Diwrninnniiiiiio((())
3 P') S
Now, we apply the inductive step on (P', where P' S P and Q' < Q, then Mo (A,P') S
QLD(P', Q'). The rest of the proof is devoted to showing that Mq (A,P) I QLD((, Q)
From Algorithm 3 we know that A selects the query tree T such that QLDr(P,Q.0) - Q)
on line 5 with the first query timestamp أ V1. For rounds & < 4 rounds, Algorithm 3 will select its predictions it that minimizes the optimization expression in lines 10 and 19 based the history of previous queries. On round /1, Algorithm 3 selects Dt, in line 15 based on the larger subtree, To or Ti. Without loss of generality, assume that To is the larger subtree and in the case of tie. To is selected. Then, dt, = 0 and the learner receives (It,, Vt, ) after querying.
It follows that the mistakes made by the learner on the first I rounds correspond ly 9 10t, * Ut, where y and yt, represent the true labels selected by the adversary. Since the adversary is operating under the constraint of realizability, then it must hold that P(),))(m)) M/e)) F where is placeholder for any sequence of instances satisfying the constraint. From the inductive step, it follows that lý - y + 1 * yt,1 + MQ- (A, y( )) S 15 yy-l yl + [0r, * ) Q 1). Assume that the adversary's 's choices of instances and true labels on the first t rounds yield 1 yl + [ūr, * yr, + QP (m.))( .r,) Q 1) QLD(P, Q). Since A selected tree T, this implies that QL.rr Q,0) = QLD(P, Q). Additionally. A always selects the predictions that minimizes over the worst possible game outcomes (line 19 of Algorithm 3) with the query prediction aligning with that of the larger subtree. As result J/ yl + 1 [0r, + 1/.
vt, + QLD((
QLDTe (PlnyYe, Me, ) Q.1) S QLD(P, Q). And by definition @LD(P .r, QLDr, (P(NN) Mn, ) Q, 1), so it must hold that ly - y/+ 1 [ūr, * De, Q (L 86, ) Q-
1) S
1) QLD(P, Q). As result, y y/ + [ + Me, + MM- (A, P(+y) vn, < QLD(PP Q). Since this incquality holds for any choice of It,, and yr, it follows that (A,P)) < QLD(P.Q).
Since Mp(P)= I (A, P), we show that MQ(P) S QT.((P,))) Q).
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In our abstract and in Section 1.3 of the introduction, we give a detailed description of the claims and results we prove in the paper as a technical overview.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings. It is fine include aspirational goals as 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]
Throughout the paper, we explicitly state the assumptions and conditions our results hold under. For example, in Sections 3 and 4, we specifically work with learning algorithms that have a linear querying strategy and an open direction would be understand a broader family of strategies. In Section 4.3, we mention that developing theory for pattern classes in the continuous case is quite challenging so we simplify the problem in the discrete setting. In Appendix B.1 we mention that the theory only holds for the blind-pree freddpprdictionn setting and future direction would extend to the update-and-deplg, setting.
Justification:
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 encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
19

---

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: In every theoretical statement, we characterize the assumptions and conditions of the statement and then we give a proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems. The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This is completely theoretical paper so there are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset 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 to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results.
20

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
This is completely theoretical paper so there are no experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
publ ic gu des / CoomeSuomemmmmmm i s. onPol icy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for 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)
/ //nips. cc/ httpp/ulllcc// cealli//qiieee iiuid//// CooeeooeSuuua Subeiubmiiee wsionsolicyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
This is completely theoretical paper so there are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
This is completely theoretical paper so there are no experiments.
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, confi-
dence intervals, 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 with given experimental conditions).
21

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This is a completely theoretical paper so there are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://tsss///e.r.p...ooo/////la
Answer:
[Yes]
Justification: The research in this paper conforms to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations 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: Since this a learning theory paper focused on characterizing learnability and complexity of learning problems, we do not see any immediate negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
22

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This is completely theoretical paper there are no datasets experimental models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
This is completely theoretical paper we don't have any code, data, or models.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
23

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, (aapersw haperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This is completely theoretical paper don't have any code, data, models.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
We do not conduct any crowdsourcing experiments or research with human subjects.
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We do not conduct any crowdsourcing experiments or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
24

---

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


Reviews:
[{"review_id": "IbnrqAFcfk", "reviewer": "Reviewer_F4wW", "summary": "This paper introduces a novel learning-theoretic framework for understanding online learning from continuous and discrete data streams through selective querying. The authors propose two settings: the update-and-deploy setting, where a learner updates a predictor based on queried data, and the blind-prediction setting, where predictions are made independently of the current data stream. They analyze the learnability of concept classes and pattern classes under these settings, providing theoretical bounds and algorithms.", "questions": "- The Update and Deploy setting and the Blind Prediction settings are not clear to me. In particular, we can think of the update in the Update and Deploy (update from the cloud translator) setting as a kind of feedback (hyper spectral image) in the Blind Prediction setting? In the formal definitions in sections 2.2 and 2.3, is the difference between the two settings is that in one f^ needs to be present in the concept class H and in the second one, there is no such constraint? What is the requirement on the true function f^t from which labels Y^t are generated?\n- Can the authors explain the definition of learnability in definition 3.1? If Q(t) = O(t), then the algorithm can query in every iteration, right? How does this definition extend from the standard online learning definition?\n- Is it true that this framework with timestamps can be expanded into the domain X to form an intuition? So, the function class is over (X,t) and we should think of (X,t) as our new domain and there is a fixed class of functions that are presented in H over this new domain?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The framework presented in this paper for studying continuous data streams is interesting and novel in my opinion.\n- The authors present simple algorithms which are interesting and derive results in terms of already existing concepts like Littlestone dimension which is interesting.", "weaknesses": "- There are certain parts in the paper that are unclear as described below. It would be nice if the examples presented in the paper to describe the settings and the theoretical framework are presented together for better understanding. It would be nice if the authors start from the traditional setting first and then add the elements relating to the continuous setting to clearly differentiate between the two.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments on the novelty and appeal of our work!\n\n### Weaknesses\n**Comment 1**: Thank you for the feedback! We agree that presenting the theoretical framework and giving a tangible construction by referring to the specific examples mentioned in the introduction will make it much easier to understand. \n\nRegarding your second statement, the traditional setting of online learning can be considered as the fully-supervised scenario under a discrete data stream with respect to a concept class $H$. In this scenario, instances are fed one-by-one to a learner who observes the instance $X_t$, makes a prediction $\\hat{Y_t}$, and observes the true label $Y_t$. The primary constraint is that the sequence of points and true labels,$ \\{ (X_t, Y_t) \\}\\_{t=1}^{\\infty} $\n, is realizable with respect to $H$ implying that there exists some $h^* \\in H$ where $ \\{ (X\\_t, Y\\_t)\\_{t=1}^{\\infty} \\} = \\{ (X\\_t, h^*(X\\_t)) \\}\\_{t=1}^{\\infty} $. \n\nIn the continuous setting, the instances and true labels form a continuous process throughout the time: $(X_t, Y_t)_{t \\geq 0}$. Unlike the traditional setting where the learner receives the true label $Y_t$ after every prediction $\\hat{Y}_t$, the learner in either the update-and-deploy or blind-prediction settings must query at that time to receive information about the true label. Additionally, the learner must obey a linear querying strategy so it is limited in the number of times it can query. The blind-prediction setting, a tougher learning framework than update-and-deploy, the learner makes predictions without knowledge of the current instance and only gains information about the instance and its true label through queries. \n\nWe believe that an explanation like the one given above can be a helpful addition to our paper in highlighting the differences between the traditional and continuous settings.\n\n### Questions\n**Question 1**: The update-and-deploy and blind-prediction settings are two separate, but closely related frameworks.\n\nThe update in the update-and-deploy setting can be considered as \"redeploying\" or constructing a new predictor function for future instances from the data stream. In Algorithm $1$, the feedback from the query, the true label, updates the SOA algorithm and this new version of the SOA algorithm is then reinstated as the new predictor function. So, the feedback received from querying, the true point-label pair, can be used to update the predictor function, these two concepts are different. \n\nRegarding the requirements on the true function, the only requirement in both settings is that the sequence of instances and true labels, $(X_t, Y_t)_{t \\geq 0}$, is realizable. If the realizability is with respect to a concept class $H$, then there exists a target concept $h^*$ such that $\\forall t \\geq 0, h^*(X_t) = Y_t$. In both settings, the true function, or also known as the target concept $h^*$, must lie in the concept class $H$.\n\n**Question 2**: Yes, so the definition of learnability as written in Definition 3.1 states that a concept class $H$ is learnable if there exists an algorithm $A$ employing a linear querying strategy such that $MB\\_{\\mathcal{P}(H)}(\\mathcal{A}) < \\infty$ where $\\mathcal{P}(H)$ is simply the collection of all continuous processes that are realizable with respect to $H$. The expression $MB_{\\mathcal{P}(H)}(\\mathcal{A})$ represents the mistake-bound of the algorithm $A$ on $H$. Informally speaking, the mistake-bound is the worst case scenario of the integral of mistakes algorithm $A$ makes on any sequence realized by $H$. If this is finite, then we say that $H$ is learnable (doesn't make infinite error). \n\nRegarding algorithm querying, we can take a look at Algorithm $1$ which is an example of an $O(t)$ querying strategy. Given $\\Delta$ as an input parameter, Algorithm $1$ samples its next query time, $t_q$, from a uniform distribution on an interval of width $\\Delta$. Every iteration of Algorithm $1$ corresponds to its next query time which is on average spaced out by $\\Delta/2$ units of time. An algorithm can query every iteration as long as its sequence of queries grows $O(t)$.\n\nRegarding the extension from standard online learning, the notion of querying primarily exists in the continuous setting because not every data point from a continuous process is observable. In the standard online learning setting, the learner operates on a discrete data stream modeled as a round-by-round process so every point is observable by the learner. \n\n**Question 3**: This is an important question to clarify. With the usual notation of $\\mathcal{X}$ as the instance space and $\\mathcal{Y}$ as the label space, the concept class $H$ represents some set of functions mapping from $\\mathcal{X}$ to $\\mathcal{Y}$. The timestamps $t$ simply represent when a particular instance-label $(X_t, Y_t)$ pair occurs. The realizability condition implies that there must exist a target concept $h^* \\in H$ where $\\forall t \\geq 0, Y_t = h^*(X_t)$ so the ordering of a particular $(X_t, Y_t)$ occurring is irrelevant as long as $h^*(X_t) = Y_t$. When we extend to pattern classes $\\mathcal{P}$, we can now incorporate the idea of temporal dependencies with instance-label pairs. For example, let's assume the continuous sequence $(X\\_t, Y\\_t)_{t \\geq 0} \\in \\mathcal{P}$. Then, for some two timestamps $t, t' \\in \\mathbb{R}\\_{\\geq 0}, t\\neq t'$, we decide to replace $(X\\_t, Y\\_t) = (X\\_{t'}, Y\\_{t'})$ and $(X\\_{t'}, Y\\_{t'}) = (X\\_t, Y\\_t)$ and keep all other timestamps identical to the original continuous sequence. It's not guaranteed that this sequence must lie in the pattern class $\\mathcal{P}$ so the ordering of instance-label pairs becomes crucial.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IqSJHwAm73", "reviewer": "Reviewer_jfDD", "summary": "This paper studies mistake bounds for discrete and continuous labelled data streams in two different coupling settings between labeller and learner (update-and-deploy and blind-prediction)", "questions": "* in line 148, 166, 199 and 239, shouldn't it be $\\in O(t)$ rather than $= O(t)$?\n* the reader would greatly benefit from introducing the Littlestone dimension (LD)\n* in line 267, shouldn't it say \"expected size $\\Delta$\"?\n* line 320: \"are needed to\" should read \"are needed for\"", "limitations": "The result is not allowing to discover new algorithms for this setting; it explains why a random query strategy works.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper is a theory paper that characterizes the learnability of pattern classes. The proof in the main paper is very accessible, easy-to-follow and accessible. I commend the authors for the accessibility of the proof in the main paper.", "weaknesses": "The paper feels overloaded with results for a 9-page NeurIPS submission. All the results for the adaptive learner case feel \"crammed in\" and, unless the reader is prepared to read the appendix, cannot be easily understood. I wish the authors would have constrained on the study of Algorithm 1; while less results, it would have made the paper into a self-contained theory paper with a significant result that may have had a proper conclusion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments about our paper's proofs! We are glad that it was highly accessible!\n\n### Weaknesses:\n**Comment 1**: Thank you for this feedback. We agree that some structural changes can be made to the paper to make it more readable. The main highlights of this paper are to show that non-adaptive learning algorithms are powerful enough to learn concept classes from a continuous stream of data in the update-and-deploy setting and pattern classes require adaptive learning algorithms in either learning framework. One potential revision is to present these two results first with their full proofs so the reader doesn't have to reference the Appendix and understand what the main ideas are of the paper. \n\n### Questions:\n**Question 1**: When describing the growth rate of a function in terms of Big-O notation, both $Q_{\\mathcal{A}}(t) = O(t)$ and $Q_{\\mathcal{A}}(t) \\in O(t)$ convey the same meaning. The expression $Q_{\\mathcal{A}}(t) = O(t)$ is considered an ``abuse of notation\" but it implies that $Q_{\\mathcal{A}}(t)$ is of order $O(t)$. \n\n**Question 2**: Thank you for this comment. We agree and we will add a brief section in the paper introducing the concept. \n\n**Question 3**: According to line $8$ in the pseudo-code of Algorithm $1$, the next query time $t_q$ is sampled in the following way: $t_q \\sim \\mathrm{Unif}[t, t + \\Delta]$. The query time $t_q$ is selected from a uniform distribution over intervals of size $\\Delta$ so it's not an expected size of $\\Delta$ but rather consecutive query times are spaced out on average of size $\\frac{\\Delta}{2}$ since the mean of a uniform distribution on an interval of size $\\Delta$ is $\\Delta/2$.\n\n**Question 4**: Thank you for this edit.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DHq7P5V2m8", "reviewer": "Reviewer_dysh", "summary": "The paper studies the online learning problem where the algorithms are receiving a stream of $(X_i, Y_i)$ in which $X_i$ is an instance and $Y_i$ is the corresponding label, and in each time point  $i$, the algorithm is required to make a prediction $\\hat{Y}_i$, which is based on the historical data and the current instance (or not). The paper studies the problem in several settings:\n\nFor continuous case:\n\n1. In the update-and-deploy setting, the paper proposes a non-adaptive algorithm that achieves a mistake bound $LD(H)$, where the main idea of the learner is using sampling.\n\n2. In the blinding prediction setting,  the paper shows that any learning algorithm, adaptive or non-adaptive, is not learnable in the blind-prediction setting.\n\n3. The paper considers the case where the algorithms are required to learn pattern classes. Then it designs a continuous pattern class that any random sampling algorithms fail but there is an adaptive learning algorithm that successfully learns P with zero expected error.  This shows a separation of the adaptive and non-adaptive case in this setting.\n\nFinally, the paper develops a theory for the discrete case where they characterize a combinatorial quantity QLD where there is a deterministic learning algorithm whose optimal mistake-bound is equivalent to it.", "questions": "See the above question.", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This is a strong theory paper. To get this results, the paper considers several algorithmic ideas which are interesting to me (though I am not an expert in the area of online learning).", "weaknesses": "1. The writing of this paper is not good enough. When I first read this paper, I felt like some parts of the paper were not easy to follow and need to be improved.  For example:\n\n-- In Section 1.3, several notations are not defined until the later Section.\n\n-- The definition of the littlestone dimension is not mentioned.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments regarding the strength of our paper!\n\n### Weaknesses:\n**Comment 1**: Thank you for this comment. After a revisit to Section 1.3, many of the terms such as $MB_{\\mathcal{P}(H)}$ and $LD(H)$ were not properly defined. We will fix this revision to make sure that the terms are defined before their usage in addition to their formal definitions in the later section. \n\n**Comment 2**: Thank you for this comment. We will include a brief section in the paper explaining the Littlestone dimension.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lvsjeGO7lC", "reviewer": "Reviewer_cGKc", "summary": "This paper considers the problem of online learning in the setting of discrete and continous data streams. It first introduces two novel learning frameworks: the update-and-deploy setting and the blind-prediction setting. The update-and-deploy setting allows a learning algorithm to discretely query a data stream to update a predictor, while the blind-prediction setting involves making predictions without observing the current data value but only based on the previous querious and current timestamp. The authors proves the error bound when a non-adaptive learner uniformly samples queries in the update-and-deploy setting. Then in the blind-prediction setting, they show that no matter the learning algorithm is adaptive or non-adaptive, it is not learnable for any concept class. It also discusses the characterization of learning algorithms should have when learning pattern classes in the continous data stream. Finally, it extends it results to the discrete data streams for the second framwork for deterministic algorithms.", "questions": "Is it trivial to consider what kind of non-adaptive learners should be when learning pattern classes under continous data streams?", "limitations": "see weakness.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. It proposes two novel framework for learning under continous data streams and provide substantial theoretical analysis to show the error bound for the first setting and the findings in the second setting.\n2. It has substantial contributions regarding the novel frameworks, discussion about the different learners to learn the pattern class, and extends the results into discrete data stream.\n3. It proposes the new mesaure called the query-learning distance(QLD) and the algorithm they develop has an optimal mistake-bound with respect to the new QLD.", "weaknesses": "1. The paper lacks empirical validation of the results, and there's no comparison with other existing possible solutions or natural extensions of existing solutions to their framwork.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive comments towards the contributions made by our two learning frameworks and algorithms!\n\n### Weaknesses\n**Comment 1**: This paper is primarily a learning-theoretic paper so it's focused on establishing a concrete theory in terms of mathematical statements and proofs. Since the main purpose of our paper is to develop a theory within online learning, we would defer empirical evaluation to future application-oriented research. \n\n### Questions:\n**Question 1**: This is an important question regarding the learnability of pattern classes under a continuous data stream. When we consider learnability of some pattern class $\\mathcal{P}$, this means that we look at all possible learning algorithms and if there exists a learning algorithm whose mistake-bound is finite on $\\mathcal{P}$, then we consider $\\mathcal{P}$ to be learnable. The pattern class example in Section 4.2 illuminates an important pattern class that is only learnable under an adaptive learning algorithm. Since we have shown that there exists pattern classes that are not learnable by non-adaptive learners but learnable by an adaptive algorithm, this means that the criteria for learnability of pattern classes is beyond the scope of non-adaptive learners.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a novel framework for understanding online learning from both discrete and continuous data streams through selective querying. The authors propose two key settings: the "update-and-deploy" setting, where a learner updates a predictor based on queried data, and the "blind-prediction" setting, where predictions are made independently of the current data stream. The paper rigorously analyzes the learnability of concept and pattern classes under these settings, providing theoretical bounds and algorithms.

The paper presents a significant theoretical contribution to the field of online learning, with novel frameworks and insightful results. Despite some concerns about the clarity of presentation and the absence of empirical validation, the overall quality and originality of the work make it a valuable addition to the conference.
Decision: Accept (poster)