Agnostic Continuous-Time Online Learning

We thank the reviewer for the thoughtful feedback and helpful comments. We address the questions raised below:

Q1: This is indeed a bug, and we are grateful to the reviewer for identifying it. The correct expression should be

where $\tilde{k} \le k$ is the number of distinct $I_t$'s, and $\bar{Y}_{\mathrm{distinct}}$ is the average of all $Y_t$'s corresponding to distinct indices $I_t$. The same replacement should also be made in Lemmas 7 and 8.
This correction does not affect the subsequent argument, as the upper bound in Lemma 8 still holds since $\tilde{k} \le k$. We can apply Khintchine's inequality (upper bound) to obtain

by conditioning on the set of distinct indices. This provides an even better constant $\frac{1}{2}$ compared to $\frac{\sqrt{2}}{2}$, as the counters $N_j$ are simply indicators. We will make this correction in the revised version and again thank the reviewer for the careful reading.

Q2: Indeed, our current lower bound proof is only non-vacuous when $S = O(T^2)$, due to the constant factor in (8). For general $S \ge T^2$, the $\Omega(T/\sqrt{S})$ lower bound still holds. This can be remedied by selecting the block length to be $1/S^2$ (instead of $1/S$ as in the paper), so that the constant factor in (8) becomes $O(1/S)$, which is negligible compared to the main term $T/\sqrt{S}$. We will clarify this in the revision.

Randomness of Predictors: Indeed, for the 0–1 loss, it is necessary for the predictor to be randomized in order to achieve sublinear regret in the adaptive case. We will clarify in Protocol 1 that the predictor $\hat{h}_s$ is allowed to use internal randomness.

We thank the reviewer for the thoughtful feedback and helpful comments. We address the questions raised below:

W1: In fact, our results for the adaptive case also apply to hypothesis classes with finite Littlestone dimension, not just finite classes, as shown in Theorem 2. For general OCO algorithms, our reduction could still apply by running the algorithm (e.g., OGD or FTRL) on the weighted loss function. We only require a regret guarantee of the form stated in Lemma 3. We thank the reviewer for pointing this out and will be happy to include this clarification in the revised version.

W2 & Q1: Our regret guarantee relies on estimating the loss, which is bounded by $\Delta \approx T/S$. For $S = T$, the variance is constant; in this case, an application of Freedman's inequality for martingales (with filtration induced by $t_s$) yields a high-probability bound on the learner's risk (or any fixed comparator risk) with deviation $O(\sqrt{S}) = O(\sqrt{T})$. For general $S$, the deviation scales as $O(\Delta \sqrt{S}) = O(T/\sqrt{S})$, which matches the order of our expected regret $\tilde{O}(T\sqrt{\mathsf{Ldim}(\mathcal{H})/S})$.

In the oblivious case, the learner's high-probability risk can be translated into a high-probability bound for the actual (pointwise) regret. However, for the adaptive case, it is unclear whether such a high-probability pointwise regret bound is attainable, since the optimal comparator may depend on the learner’s internal randomness. To our knowledge, no such adaptive high-probability pointwise regret bound exists even in the adversarial bandit setting. Nevertheless, the above argument still yields the following weaker form of adaptive high-probability regret: for any given expert $h \in \mathcal{H}$, with high probability, the (pointwise) regret of the learner against $h$ is $\tilde{O}(T\sqrt{\mathsf{Ldim}(\mathcal{H})/S})$.

W3: We agree that many of our technical ingredients are inspired by classical ideas. However, synthesizing these ideas in our (novel) setting is far from straightforward. For example, the selection of the weighting factor is derived from the randomness of the query times $t_s$ and is not arbitrarily chosen. The fact that it may appear natural in hindsight does not imply that it is easy to derive or even to recognize it's existence. Moreover, our lower bound proof in Appendix D significantly extends the construction in Ben-David et al. [1] by designing an oblivious process (see Remark 4 and the accompanying discussion).

Q2: We thank the reviewer for the helpful suggestion. As noted in our response to W1, a general reduction is indeed achievable in the OCO framework. We will include this discussion in the main text following Theorem 2.

Synthetic Experiments:
We conducted synthetic experiments to demonstrate the robustness of our algorithm. We used the expert class

so that $|\mathcal{H}| = 1000$. We set the time horizon to $T = 5$ and discretize it into 1000 small blocks to approximate the integral regret without normalization. So, the simulated regret values reported below are scaled by a factor of $200\times$ compared to the actual continuous-time regret used in the paper. We simulate our Algorithm 1 under different query budgets $S$, using the Exponential Weights Algorithm (EWA) as the expert algorithm $\mathcal{B}$, on the following data streams (all features are generated iid uniform from $[0,1]$):

1. alt_blocks: The stream is divided into $S$ equal chunks where the label for the chunks follows an (deterministic) alternating 0/1 pattern.
2. iid: Each label is drawn independently from a Bernolli source with parameter $p=0.3$.
3. realizable: The labels are generated by a ground-truth function from $\mathcal{H}$.
4. upper bnd.: Our theoretical upper bound.
5. lower bnd.: Our theoretical lower bound.

The considered data processes span a broad spectrum, ranging from stationary to highly non-stationary regimes. Results are shown below (each experiment is repeated 100 times, and the average regret is reported):

We also conducted simulations on the hard data stream lower_stream used in our lower bound proof (cf. Appendix D):

Observation 1: For all four data streams, the regret is upper bounded by our theoretical upper bound. In fact, the curves have very similar slopes when plotted on a log-log scale, demonstrating that the $1/\sqrt{S}$ order is genuine.

Observation 2: The regret for the lower_stream data is tightly sandwiched between our theoretical lower and upper bounds, demonstrating the optimality of our theoretical analysis.

We expect similar results to hold for Algorithm 2 as well, since the weighting factor lies in $[0,1]$ and does not increase the variance of the loss estimation. We are happy to incorporate the experimental results reported above in our revision, along with additional discussion.

We thank the reviewer for the thoughtful feedback and helpful comments. We address the questions raised below:

Q1: The primary conceptual difference compared to the framework of Devulapalli and Hanneke [7] is that our setting does not assume the existence of a perfect labeling rule from the hypothesis class. We also explicitly treat the query budget as a resource, which allows us to derive a precise quantitative trade-off between regret and the query budget.

From a technical standpoint, the work in [7] applies dynamic querying without weighting, leveraging the fact that the plain loss serves as an overestimate that is sufficient to bound mistakes in the realizable setting. However, in the agnostic setting, such an overestimate is insufficient to lower bound the competitor's loss. Our main technical innovation is the introduction of a weighting factor that produces exactly unbiased loss estimates, along with novel reductions to classic expert algorithms. Additionally, the lower-bounding techniques presented in Section 3 and Appendix D are entirely novel compared to those in [7].

Q2: The weighting factor was not arbitrarily chosen, but rather derived from the randomness in the query times $t_s$, as shown in Lemma 2. In fact, other methods of selecting $t_s$ could also work, potentially leading to different weighting factors using the same derivation technique as in the proof of Lemma 2. Note that the weighting factor introduced in our Algorithm 3 lies in $[0,1]$, so it does not increase the variance of the estimator used in Algorithm 1 (which we simulate below).

Q3: In fact, we consider the worst-case scenario; that is, our results apply to any non-stationary data-generating process. The "complexity" our framework addresses is the query (or update) budget. For example, in high-frequency trading, one must deploy a model that operates in real time, and updating the model can be costly—whether due to retraining overhead or concerns about system stability. As a result, updates must be sparse and strategic. Our work provides a worst-case performance baseline for such applications.

Synthetic Experiments:
We conducted synthetic experiments to demonstrate the robustness of our algorithm. We used the expert class

so that $|\mathcal{H}| = 1000$. We set the time horizon to $T = 5$ and discretize it into 1000 small blocks to approximate the integral regret without normalization. So, the simulated regret values reported below are scaled by a factor of $200\times$ compared to the actual continuous-time regret used in the paper. We simulate our Algorithm 1 under different query budgets $S$, using the Exponential Weights Algorithm (EWA) as the expert algorithm $\mathcal{B}$, on the following data streams (all features are generated iid uniform from $[0,1]$):

1. alt_blocks: The stream is divided into $S$ equal chunks where the label for the chunks follows an (deterministic) alternating 0/1 pattern.
2. iid: Each label is drawn independently from a Bernolli source with parameter $p=0.3$.
3. realizable: The labels are generated by a ground-truth function from $\mathcal{H}$.
4. upper bnd.: Our theoretical upper bound.
5. lower bnd.: Our theoretical lower bound.

The considered data processes span a broad spectrum, ranging from stationary to highly non-stationary regimes. Results are shown below (each experiment is repeated 100 times, and the average regret is reported):

We also conducted simulations on the hard data stream lower_stream used in our lower bound proof (cf. Appendix D):

Observation 1: For all four data streams, the regret is upper bounded by our theoretical upper bound. In fact, the curves have very similar slopes when plotted on a log-log scale, demonstrating that the $1/\sqrt{S}$ order is genuine.

Observation 2: The regret for the lower_stream data is tightly sandwiched between our theoretical lower and upper bounds, demonstrating the optimality of our theoretical analysis.

We are happy to incorporate the experimental results reported above in our revision, along with additional discussion.

We thank the reviewer for the thoughtful feedback and helpful comments. Indeed, in our paper, we explicitly assume that the function induced by the loss is measurable for any sample path, so that the risk defined via integration is well-defined. The measurability and boundedness of $f(t)$ ensure that the function is absolutely integrable; thus, the exchange of the order of integration in Lemma 2 follows from Fubini’s theorem, which does not require assumption on the countability of the $Z_t$'s.

From a practical point of view, one can also consider a sufficiently small partition of the time horizon to approximate the integral and thereby avoid measurability concerns—in which case, our result still holds.