Online Classification with Predictions

We thank the reviewer for noting that we present a new and fairly natural problem in online learning. We will incorporate all suggestions and fix typos in the final camera-ready version. We address each weakness and question below.

Strengths

2. This technique of constructing a few online learners and running MW on top is not completely new. For example, this technique is used to design agnostic online learning algorithms for multiclass and binary online classification [1, 2]. However, in the context of Online Algorithms with Predictions, we are unaware of any other work that uses this technique.

Weaknesses

1. Although our techniques may not be groundbreaking, we disagree with the reviewer that our proofs use combinations of existing ones. Since this setting has not been studied before, we argue that new techniques needed to be developed. For example, it is not obvious apriori how to construct the class of Experts used by Algorithm 5 or that this entire approach as a whole leads to a near optimal upper bound.
2. We thank the reviewer for pointing out the ambiguity between contributions (1) and (2). Contribution (1) is mainly aimed at quantifying the minimax rates while Contribution (2) is concerned with characterizing learnability. In particular, Contribution (1) aims to answer: For any hypothesis class $H$ and a predictor $P$, what is the minimax expected number of mistakes/regret when given access to $P$? Here, the goal is to derive mistake and regret bounds in terms of the performance of $P$. Contribution (2) aims to answer: does having access to a Predictor make online learning easier and if so, when? That is, are there classes $H$ that are online learnable when given access to a Predictor but not online learnable otherwise? If so, which classes $H$ become online learnable when given access to a Predictor? We will make this distinction more clear in the final version.

Questions

1. There are indeed other ways of making the standard online learner setting more optimistic. The "stochastic adversary" mentioned by the reviewer is actually one of them and is known formally as "smoothed online learning" in literature. We do mention smoothed online learning in Line 64-65 and Appendix A as an alternative way of going beyond a worst-case analysis. We will add a larger discussion about the smoothed model in the main text of the final version.
2. Since realizable and agnostic learnability are equivalent, it doesn't matter whether we use either (1) the existence of a learner with sublinear mistake bound or (2) the existence of a learner with sublinear regret to characterize offline learnability in both the realizable or agnostic settings. Lines 172-173 is just saying that we will always pick (2) the existence of a learner with sublinear regret, to characterize offline learnability in both the realizable and agnostic settings. We will remove this phrase in the final version to avoid confusion.
3. Our setting with a Predictor is actually more general than "transductive online learning with possible noise in the given examples." This is because we allow the Predictor to change its predictions about future instances throughout the game. On the other hand, in the noisy transductive online setting, one presumably fixes the noisy instances revealed to the learner before the game begins. We give a brief discussion of this on lines 136-141. In addition, we find that access to a Predictor (and therefore dynamic predictions about future instances) is more natural in practice. For example, one often has the ability to update predictions about future instances given the present instance (e.g. temperature forecasting).
4. One natural predictable collection of streams are those induced by dynamical systems. That is, let $X$ be the state space for a collection of transition functions $G: X \mapsto X$. Then, given an initial state $x_0$, one can consider the stream class $Z$ to be the set of all trajectories induced by transition functions in $G$. We will add a discussion of what predictable stream classes might look like in the camera ready version.

[1] Ben-David, Shai, Dávid Pál, and Shai Shalev-Shwartz. "Agnostic Online Learning." COLT. Vol. 3. 2009.

[2] Hanneke, Steve, et al. "Multiclass online learning and uniform convergence." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

We thank the reviewer for finding the theoretical results to be solid and the presentation to be clear. We address the concerns below.

• Indeed, the stream of instances $x_1, ..., x_T$ could be very unpredictable and $M_P$ can be very large. However, in this case the minimum in Theorem 3.1 is obtained by $L(H)$, the Littlestone dimension of $H$. Thus, our algorithm's guarantee is never worse than the worst-case mistake bound (up to constant factors). However, if $M_P$ is very small, then our algorithm's guarantee (see (ii) and (iii) in Theorem 3.1) can be much smaller than $L(H)$. In this way, our algorithm adapts to the quality of predictions made by $P$.

• Indeed, if the Predictor makes a lot of mistakes, Algorithm 3 will restart the Offline learner frequently causing its expected number of mistakes to explode. This is precisely why we give Algorithm 5, which explicitly controls the number of restarts. Note that the expected number of mistakes made by Algorithm 5 (see Lemma 3.7) can be significantly smaller than that by Algorithm 3 (see Lemma 3.5), and this is captured by term (iii) in Theorem 3.1.

• The "soft" criteria when initializing a new copy is an interesting idea. However, it is not immediately obvious to us that such an idea would work since the Offline learner is only useful when the instances it gets initialized with actually matches the true instances in the stream. In any case, note that the guarantee of Algorithm 5 (see Lemma 3.7) is already near optimal (up to log factors in $T$) given the lower bound in Theorem 3.8.

We thank the reviewer for finding that our work presents an "interesting result answering an important question." We address the concerns below.

• We thank the reviewer for pointing out our use of "adversary" in Page 4 Section 2.3. We will change this to "Nature" to make it consistent with the setup in Section 2.1.
• Yes, we take \bar{f} to the smallest concave sublinear function that upper bounds g. We will make this explicit in the camera-ready version.

We thank the reviewer for noting that our main result is intuitive and elegant. We address each of the weaknesses and questions below.

Weaknesses

• In this paper, we consider abstract instance spaces $X$. Accordingly, we did not discuss how the predictions can be generated since there is unlikely to be a one-size-fits-all Predictor. That said, for particular choices of the instance space $X$, existing literature in ML can certainly provide methods for generating predictions. For example, if $X$ is the state space for a discrete-time dynamical system, then existing algorithms for next-state predictions for discrete-time dynamical systems can be used to forecast future instances/states. We will make sure to include a concrete example of how predictions may be generated from ML models in the camera ready version.
• This paper is mainly focused on the theoretical/conceptual benefits of instance predictions. In particular, an important implication/insight of our results is that the difficulty in adversarial online classification is not due to the uncertainty of the labels, but rather, the uncertainty with respect to future instances. That said, we do agree with the reviewer that experiments on synthetic data showcasing the improved performance of the proposed algorithms is an interesting and important direction. We do note that our algorithms use black-box access to Offline learners and Predictors. Thus, the efficiency of our learning algorithms depend on the efficiency of existing Offline learner and Predictors. To the best of our knowledge, we do not know of any implementation of an Offline learner, let alone an efficient one. In particular, the Offline learner from Hanneke et al. [2023] is provable inefficiency since it requires computing the VC dimension. Finally, we would like to point out that there are several influential papers in learning-augmented algorithms whose contributions were primarily theoretical [1, 2, 3, 4, 5].

Questions

• Yes, there are public benchmarks where one can evaluate the performance of online classification algorithms (e.g UCI ML Repository). However, these public benchmarks are also used to evaluate batch learning algorithms. Accordingly, it is unclear how to design a Predictor for these datasets since these datasets are not inherently online - it is not known how the instances were generated or whether there is any particular order to the rows in the datasets.
• Yes, in the third sentence of line 107, it should be $\hat{y}_t \in Y$.
• Yes, these two citations cite the same paper. We will fix this in the final version.
• We will make sure to define the Predictor and $\hat{x}^t_{1:T}$ explicitly in the camera-ready version. We use $P(x_{1:t})$ to denote the prediction made by Predictor $P$ after observing $x_1, ..., x_t$. We also use $\hat{x}^t_{1:T}$ to denote these predictions when it is more convenient. We will make sure to define these quantities explicitly.

[1] Rohatgi, D. (2020). Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1834-1845). Society for Industrial and Applied Mathematics.

[2] Dütting, Paul, et al. "Secretaries with advice." Proceedings of the 22nd ACM Conference on Economics and Computation. 2021.

[3] Lattanzi, Silvio, et al. "Online scheduling via learned weights." Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2020.

[4] Antoniadis, Antonios, et al. "Secretary and online matching problems with machine learned advice." Advances in Neural Information Processing Systems 33 (2020): 7933-7944.

[5] Angelopoulos, Spyros, et al. "Online computation with untrusted advice." arXiv preprint arXiv:1905.05655 (2019).