Learning from Snapshots of Discrete and Continuous Data Streams

Thank you for your positive comments towards the contributions made by our two learning frameworks and algorithms!

Weaknesses

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.

Questions:

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.

Thank you for your comments regarding the strength of our paper!

Weaknesses:

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.

Comment 2: Thank you for this comment. We will include a brief section in the paper explaining the Littlestone dimension.

Thank you for your comments about our paper's proofs! We are glad that it was highly accessible!

Weaknesses:

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.

Questions:

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)$.

Question 2: Thank you for this comment. We agree and we will add a brief section in the paper introducing the concept.

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$.

Question 4: Thank you for this edit.

Thank you for your comments on the novelty and appeal of our work!

Weaknesses

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.

Regarding 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}$ , 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}$.

In 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.

We 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.

Questions

Question 1: The update-and-deploy and blind-prediction settings are two separate, but closely related frameworks.

The 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.

Regarding 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$.

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).

Regarding 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)$.

Regarding 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.

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.