Online Classification with Predictions

Summary

The paper studies an online classification problem that interpolates between transductive online classification and (standard) online classification. The interpolation is controlled by a "predictor" entity that tries to predict the examples to be labelled: If the predictor is good, the setting is more like transductive online classification, and otherwise it is more like (standard) online classification. For this problem, the authors design an online learner that uses a predictor and can do better than a standard online learning algorithm if the predictor is good. As a corollary, they show that transductive online learning implies online learning when the input stream is taken from a "predictable" collection of streams. For the first result, they also provide a lower bound that shows that it is nearly tight in some sense.

Strengths

1. The paper presents a new and fairly natural problem in online learning, and provides nearly tight guarantees for it. 2. The idea of using a few learners to cover all cases and then use WM on them is useful and interesting (is it novel?).

Weaknesses

1. Most of the proofs use combinations of known techniques. 2. There is some room for improvements in the writing and presentation. For example, in page 2, I didn't understand the difference between contributions (1) and (2).

Questions

Questions: 1. To provide motivation, it is written that the standard online learning setting is often too pessimistic. However, there are other ways to make it more optimistic. For example, what about a stochastic adversary? It seems like a more natural way to make the setting more optimistic, but it is not discussed in the paper. 2. Why is line 172 "without loss of generality"? 3. I am not quite sure that the story of a "predictor" in the background is the most natural way to present the problem. Isn't the setting you define is just transductive online learning with possible noise in the given examples (which is interesting as well)? 4. A notion of "predictable stream collections" is defined, but the paper does not study it or even just discuss open questions about it. Do we know how a predictable collection of streams looks like? Suggestions: 1. I didn't understand the sentence in lines 155-156. I suggest rephrasing. 2. The weighted majority algorithm is originally due to the seminal work [1]. I would mention it. Typos/english: 1. Line 56 is unclear. 2. Line 145: "to ability to define" References: [1] Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm.Information and computation, 108(2):212–261, 1994.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes

Summary

This paper studies the complexity of the online classification problem when provided with a predictor $\mathcal{P}$ that can forecast future features of data samples. Using black-box access to this predictor, the authors provide a beyond-worst-case analysis of online classification algorithms that can adapt to the 'easiness' of the online stream. Specifically, in Theorem 3.1, they demonstrate that there exists an online learner whose mistakes can be upper bounded by the Littlestone dimension, while additionally being bounded by the performance of predictor $\mathcal{P}$ and that of the employed offline learner. As a corollary, their result reveals the relationship between offline learnability and realizable online learnability given such a predictor. A lower bound is provided to demonstrate the tightness of the upper bound.

Strengths

1. The presentation of this paper is clear, and I can quickly grasp the main idea of how to construct an online learner that satisfies the upper bound. 2. This paper explores beyond-worst-case guarantees by leveraging a predictor and an offline learner. With the constructed online protocol, the authors reveal the linkage between offline learnability and online learnability to some extent. 3. The theoretical results appear solid with both the upper bounds and the lower bound, although I have not checked the appendices carefully.

Weaknesses

My main concern is about the accuracy of the predictor $\mathcal{P}$. Unlike in the offline setting, where the features $x_{1:T}$ are naturally provided, in the online setting—especially the adversarial one—the predictor $\mathcal{P}$ might not be accurate, and the factor $M_{\mathcal{P}}$ could be extremely large. Also, Algorithm 3 will initialize a new copy every time the predictor makes a mistake. It seems that Algorithm 3 might initialize the copy frequently, and it might not learn the potential pattern even if the mistakes made are minor.

Questions

Could we consider 'soft' criteria when initializing the copy? For example, could the online learner initialize a new copy only when the cumulative errors, such as $\sum_t \|x_t - \hat{x}_t\|$, exceed some threshold?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

Summary

The paper belongs to the field of statistical learning. The learner is seeing pairs $(x,y)$ and needs to predict labels $y$s to compete (in terms of the expected number of errors) with any hypothesis from the given class. The main result of the paper, Theorem 3.1, establishes a connection between the offline and the online setup. In the offline setup, the learner knows the sequence $x_1, x_2, \ldots, x_T$ where it needs to predict labels in advance. In the online setup it gets $x$s one by one but gets help from a predictor $\cal P$ that tries to predict what remains of the sequence. The paper constructs an online algorithm utilising an offline algorithm and a predictor and gets an upper bound on its performance in terms of the quality of the offline bound and the quality of the predictor. Corollary 3.2 shows that if a class of sequences is predictable ( = can be predicted with sublinear cumulative error) and a class of hypotheses is learnable under offline settings (the regret is sublilear), then their combination is learnable under online settings. Theorem 3.8 provides a lower bound.

Strengths

I believe the paper presents an interesting result answering an important question.

Weaknesses

I am worried the very technical presentation may limit the appeal of the paper. Typos etc: Page 4, Section 2.3, first line: to ability -> the ability Page 4, Section 2.3. I believe the mentioning of the adversary appears here for the first time, and it is confusing. I understand we are talking of the adversary because we are interested in the supremum of the loss over sequences, but I may be wrong... Page 6. Lemma 2.2 says there is _a_ concave function upper-bounding $g$. Then $\bar f$ is defined as _the_ concave function upper-bounding $f$. Which one is used? The minimal perhaps?

Questions

None

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

Yes

Summary

This paper studies learning-augmented online classification, where the classifier has access to a predictor that forecasts future examples. The paper proposes an algorithm that uses these predictions, and the algorithm's performance depends on the prediction error. The proposed algorithm is robust (never worse than the worst-case mistake bound), consistent (as good as the best offline learner if the predictions are perfect), and degrades smoothly as prediction quality decreases. Their findings show that accurate predictions can make online learning as straightforward as transductive online learning. The contribution of this paper is theoretical.

Strengths

- This is the first paper exploring the task of online classification with predictions. The main result is intuitive and elegant, showing that "online learnability with an effective predictor can be reduced to transductive online learnability." - The theoretical part of this paper is sound and well-organized. The paper effectively analyzes the robustness, consistency, and smoothness of the proposed algorithm, which are key aspects of learning-augmented algorithms.

Weaknesses

- The paper does not discuss how the predictions can be generated, particularly from machine learning models. Admittedly, most designs in learning-augmented algorithms focus on the algorithmic side. Yet, linking the proposed algorithm to settings where machine learning models can be involved would strengthen the paper's relevance to the NeurIPS audience. - The paper does not include any experiment or evaluation on how the proposed algorithms would perform in real-world scenario. Similar to the previous point, I think the community studying learning-augmented algorithms value both theoretical soundness and practicality (which is the reason to include learned predictors in the first place). I think some experiments (even on synthetic data) would make this paper more complete. - The paper lacks experiments or evaluations on the proposed algorithms' performance in real-world scenarios. Similar to the previous point, I think the community studying learning-augmented algorithms value both theoretical soundness and practicality (which is the reason to include learned predictors in the first place). Some experiments even on synthetic data showcasing the improved performance of the proposed algorithm would make this paper more comprehensive.

Questions

- I am not an expert in online classification, but are there any public benchmarks or test sets to evaluate the performance of online classification algorithms? If so, I strongly encourage the author to perform experiments to demonstrate the proposed algorithm's performance. - In the third sentence of line 107, should it be $\hat y_t \in \mathcal{Y}$? Otherwise, I am confused about why the prediction is binary. - In lines 377 - 380, do these two citations refer to the same paper? - The notation in the paper is somewhat confusing. Specifically, regarding the predictor, I did not find the formal definition of $\mathcal{P}\left(x_{1: t}\right)$ and $\hat{x}_{1: T}$.

Rating

6

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

The majority of limitations are addressed in the 'weaknesses' and 'questions' sections. From a broader societal perspective, given the theoretical nature of this work, there is no immediate negative impact, and I cannot foresee any.