We thank the reviewer for their generous score and for raising thoughtful and technically insightful questions. We especially appreciate the technical depth reflected in their questions, which is all the more notable given the self-reported low confidence. We intend to consider and include these open questions in a future revision, with proper acknowledgment of the anonymous reviewer.

Weaknesses

Regarding weaknesses, I do feel like a more concrete (formal) definition of on-path/off-path labels would better help the readers understand the obstacles described in 223-247 if possible.

Yes, this makes sense of course. Conceptually, given a Littlestone tree, each function in the class corresponds to a root-to-leaf path in the tree. The on-path nodes for a function are simply the nodes on that root-to-leaf path. This is mentioned in line 116 and in footnote 9, and is illustrated in Figure 1c. The formal definition is stated in Definition A.5 (lines 463-470). We will explicitly clarify in Definition A.5 that “on-path” refers to nodes that are on the path, as it is defined in that location.

Questions:

While the sparse encoding strategy for the upper bound makes sense, it does require the domain of the function class to be sufficiently large (from my understanding). As someone who is not familiar with online learning, would it make sense to consider this setting with a restriction on the domain size? And if so, would that change the sample complexity?

Thank you for noticing this — yes, and this is a very insightful point!

At present, we show an upper bound of $O(\sqrt{d})$ mistakes using a class that has $2^d$ functions on a domain of size roughly $2^d$.

Clearly, it is not possible to obtain such an upper bound with a domain of size $d$, because a set of $2^d$ functions on a domain of size $d$ is simply the set of all functions on the domain — and so the adversary can force a mistake on each point in the domain (in other words, the VC dimension will be $d$ as well).

But what about a domain of size, say, $2d$, $d^2$, $\mathsf{poly}(d)$, or $2^{\sqrt{d}}$? Is there some nice tradeoff between domain size and the best upper bound? These are very good questions, and we don’t know the answers. We will include them in the Open Questions section in the camera-ready version.

Thanks again for contributing this great technical question — it shows significant insight into our work.

Limitations

It would be better if they could discuss open problems and potential future directions.

Definitely! The final version of the paper is allowed to include an additional page, and in that page we will have a Future Directions section. It will include:

• Open questions (contributed by Reviewer zo5C): Is it possible to achieve the upper bound with an efficient learning algorithm? (See further discussion in our answer to Reviewer zo5C)
• Open question (contributed by you, Reviewer bNtP): for a class of Littlestone dimension $d$, what is the tradeoff between the domain size, and the best upper bound? (As discussed above.)
• Open question: Can we get finer asymptotic bounds? I.e., what are the “correct” (tightest) constants hidden by the $\Omega(\sqrt{d})$ and $O(\sqrt{d})$ notation in the lower and upper bounds? For example, is there some constant $C > 0$ such that the answer is $(C+o(1)) \sqrt{d}$.

Thank you so much for your review!

The Author(s)

Thank you very much for your thoughtful and constructive review. Your comments — including your suggestions to clarify what is new in our work, to improve the presentation of the upper bound, and to make the standard online learning setting more accessible — will help us improve the clarity and presentation of the paper.

Weaknesses

(1) I am convinced that this is a very solid work. However, for reader’s convenience (especially for readers not in this field), it is suggested to give more explanations for which part of proof is new and which idea is borrowed from the existing work of Hanneke, Moran, and Shafer (2023).

Absolutely! The upper bound is new, and does not have a direct analog in [1]. For the lower bound, there are a number of important differences between our proof and theirs:

1. They use an adversary that presents all the nodes in the Littlestone tree, in breadth-first order. However, one can show an upper bound of $O(\log d)$ mistakes for any adversary that presents all the nodes in the Littlestone tree in breadth-first order, so in that sense their technique cannot be improved. To overcome this limitation, we devise an adversary that presents only a subset of the nodes in the tree (see Algorithm 2, “ConstructSequence”). The intuition here is that presenting all the nodes in the tree can be bad for the adversary because some nodes are easy to guess, but still leak a small amount of information about the correct labeling function. Therefore, to obtain a stronger lower bound, one can try to present only a subset of the (“harder to guess”) nodes in the tree.
2. The proof of the lower bound in [1] actually contains a somewhat complex adversary that maintains a parameter $\varepsilon_t$ that is an inverse of a double exponential in the number of mistakes that have been forced so far (see Algorithm 1 in [1]). Because we present a shorter sequence with labels that are “harder to guess”, we are actually able to simplify this somewhat cumbersome aspect of their proof, and use a single value $\varepsilon$ that remains constant (see Algorithm 1 in our paper).

(2) For the exhibition of the proof idea for the upper bound, it is truly hard for me to read the so length words in Sections 2.3.1-2.3.5. I would suggest defer the length proof technique description to the appendix, and give more concise lemmas/claims/mathematic notations in the main paper, to show mathematically how to derive improved mistake upper bound. In the current version, it is still truly hard for me to catch the essence of main proof strategy.

We can understand a preference for mathematical notation over textual description. However, at present, the appendices contain 24 pages of nontrivial mathematical proofs, including definitions, pseudocode, equations, etc. We don’t feel that the proofs could really be made to fit in the 9 pages of the main text, even in a condensed and abbreviated form. If we tried to do so, the result might be hard to understand without the full definitions and pseudocode, etc., and it would likely be confusing and inaccurate.

Therefore, the choice we made for presenting our work was to include a clear (but condensed) statement of our results in Theorem 1.1, and then provide a Technical Overview that explains the main ideas, ingredients, and steps of our proofs at an intuitive level, while referring the reader to specific formal definitions, lemmas, and algorithms in the appendix. Our hope is that after reading the Technical Overview, readers will have a general idea of how the proofs work, and they will be able to read the details of the formal proofs more easily.

We feel that this method of presentation makes sense, but we are of course open to hearing suggestions. Are there any specific changes to the Technical Overview that you feel would make it clearer?

Per your feedback, using the space from the additional 10th page in the camera-ready version of the paper, we will try to add to the main paper a back-of-the-envelope calculation that at least gives a feeling for how the quantity $\sqrt{d}$ arises in the bounds.

(3) The related works section does not introduce the optimal mistake bound for standard online learning setting. It will be easier to see the benefits of access to unlabeled data in online learning when compared with the optimal mistake bound in the standard online setting.

Thank you for pointing this out! Presently, the classic characterization of the mistake bound for the standard setting using the Littlestone dimension is mentioned already in the abstract, and it is mentioned again in the Related Work sections — but you are correct that the formal statement of this result appears only later on, in the appendix (specifically, in Theorem A.7). To make the paper more readily accessible to a broad audience, we will make the following additions:

• On page 2, right after defining the number of mistakes $M_{\mathsf{std}}$ in the standard setting, we will note that this quantity is characterized by the Littlestone dimension, and refer the reader to Theorem A.7 for the full details.
• In the Related Work section, when mentioning this result, we will again refer the reader to Theorem A.7 for full details.

(4) This paper actually exceeds the page limit.

Respectfully, all content in our main submission PDF ends at the bottom of page 9 — and subsequent pages contain only references and the NeurIPS checklist. This adheres to the page limit in the NeurIPS Call for Papers.

In the supplementary material, for which no page limit exists, the main text minimally exceeds 9 pages due to merging documents and slight edits.

Questions:

(1) Could you please give more explanations for which proof idea is essential to derive improved mistake bounds when compared with the latest work Hanneke, Moran, and Shafer (2023)?

[Repeating our response to Weakness (1):]

Absolutely! The upper bound is new, and does not have a direct equivalent in [1]. For the lower bound, there are a number of important differences between our proof and theirs:

1. They use an adversary that presents all the nodes in the Littlestone tree, in breadth-first order. However, one can show an upper bound of $O(\log(d))$ mistakes for any adversary that presents all the nodes in the Littlestone tree in breadth-first order, so in that sense their technique cannot be improved. To overcome this limitation, we devise an adversary that presents only a subset of the nodes in the tree (see Algorithm 2, “ConstructSequence”). The intuition here is that presenting all the nodes in the tree can be bad for the adversary because some nodes are easy to guess, but still leak a small amount of information about the correct labeling function. Therefore, to obtain a stronger lower bound, one can try to present only a subset of the (“harder to guess”) nodes in the tree.
2. The proof of the lower bound in [1] actually contains a somewhat complex adversary that maintains a parameter $\varepsilon_t$ that is an inverse of a double exponential in the number of mistakes that have been forced so far (see Algorithm 1 in [1]). Because we present a shorter sequence with labels that are “harder to guess”, we are actually able to simplify this somewhat cumbersome aspect of their proof, and use a single value $\varepsilon$ that is constant (see Algorithm 1 in our paper).

(2) Could you please introduce more related works about the optimal mistake bound for standard online learning?

Definitely! The paper that established this result is Littlestone [2]. This paper is already cited a number of times in the submission, but as we discuss in our response to Weakness (3) above, we will add direct references to the formal statement of this result (Theorem A.7) from page 2 and from the Related Works. Additionally, we will add references to expositions that are more accessible, including Chapter 21 in Shalev-Shwartz & Ben-David [3], Chapter 8 in Mohri, Rostamizadeh & Talwalkar [4], and the relevant sections in Cesa-Bianchi & Lugosi [5].

Limitations

(1) This paper exceeds the page limit (nine pages).

[Repeating our response to Weakness (4):]

Respectfully, all content in our main submission PDF ends at the bottom of page 9 — and subsequent pages contain only references and the NeurIPS checklist. This adheres to the page limit in the NeurIPS Call for Papers.

In the supplementary material, for which no page limit exists, the main text minimally exceeds 9 pages due to merging documents and slight edits.

[1] Hanneke, S., Moran, S., & Shafer, J. (2023). A trichotomy for transductive online learning. Advances in Neural Information Processing Systems, 36, 19502-19519.

[2] Littlestone, N. (1988). Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2(4), 285-318.

[3] Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.

[4] Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2018). Foundations of machine learning. MIT press.

[5] Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press.

Thank you for your supportive review!

What is the computational efficiency of the algorithm for proving the upper bound? It seems that in the worst case, there could be exponential experts (or probably even super-exponential). Is that correct? Do the authors think the computational efficiency can be improved?

Thanks for raising the question of computational efficiency, which is a very interesting topic! We will include this in the Open Questions section in the final version. More broadly, we will also add a discussion on this topic along the following lines.

First, one needs to define what computational efficiency means in this context. Kakade & Kalai [1] consider a transductive learner to be efficient if it runs in time $\mathsf{poly}(n)$, where $n$ is the length of the sequence $x_1,\dots,x_n$. In their setting they consider the VC dimension to be constant, ignoring the runtime dependence on the VC dimension or the size of the class, etc.

In our upper bound, we construct a class of Littlestone dimension d with a domain of size roughly $2^d$, and a learning algorithm that makes at most $O(\sqrt{d})$ mistakes. The algorithm runs in time polynomial in $n$ and the number of experts. Each expert is associated with a subset $H$ of the hypothesis class, and at each time step these subsets are disjoint, so the number of experts is at most the number of hypotheses in the class. Therefore the algorithm runs in time $\mathsf{poly}(2^d, n)$ which is polynomial in $n$ but is not efficient. (However, the runtime is not super-exponential.)

Note, however, that in our case the class is constructed randomly. Therefore it would be reasonable to think that the learning algorithm receives a description of the hypothesis class as one of its inputs. Such a description would essentially be a $2^d \times 2^d$ binary matrix. So under this view, our runtime of $\mathsf{poly}(2^d, n)$ is polynomial (and potentially even sublinear) in the input length.

It is an interesting open question whether there exists a learning algorithm $A$ and a sequence of classes $\mathcal{H}_1, \mathcal{H}_2, …$, such that for every integer $d$:

• $\mathcal{H}_d$ has Littlestone dimension $d$, and
• Given as input the index $d$ and a sequence $x_1,\dots,x_n$, $A$ runs in time $\mathsf{poly}(d, n)$, and makes at most $O(\sqrt{d})$ mistakes assuming that the labels are realizable by $\mathcal{H}_d$.

A natural variation is to ask for an oracle efficient algorithm: an algorithm that runs in time $\mathsf{poly}(d, n)$ using access to an ERM oracle for the hypothesis class $\mathcal{H}_d$ (or some other similar oracle).

[1] Kakade, S., & Kalai, A. T. (2005). From batch to transductive online learning. Advances in Neural Information Processing Systems, 18.

We’re very grateful for the reviewer’s heartwarming comments and score. This kind of encouraging feedback is both humbling and motivating. Thank you for engaging with our work so thoughtfully.

This is sort of a history question: What do you think was the big insight or connection that let you solve the problem? Or from another perspective, what was blocking the previous papers from getting this bound? All the steps seemed almost obvious when reading your paper (which to be clear I don't think is a bad thing).

Thank you for this question! Looking back at our work, we actually don’t believe that there is a single big insight that leads to this result. Rather, it followed from a process (typical in mathematics) of tinkering with a number of specific examples, carefully considering some proofs and seeing whether they can be pushed further, or whether one can prove lower bounds that would preclude improvements, etc.

As a first point, one needs to understand what is the correct statement to be proved, namely, bounds of $\Theta(\sqrt{d})$. But it is hard to say where $\sqrt{d}$ comes from. Consider:

• In the PAC setting, unlabeled data doesn’t help. So one could conjecture that there is a lower bound of $\Omega(d)$.
• On the other hand, the previous lower bound of $\Omega(\log d)$ is actually tight (cannot be improved) if the adversary presents a sequence consisting of the entire Littlestone tree in breadth-first order (as was the case in [1]). So one could conjecture that this is true for all sequences, and therefore that there is an upper bound of $O(\log d)$.
• Even now, it is not clear that there is a simple and concise intuition for where the $\sqrt{d}$ comes from.

Next, consider the upper bound. It involves constructing a hypothesis class at random, and then utilizing properties of that class in order to learn with few mistakes. While the probabilistic method is of course very common in discrete math, this is arguably not a very typical use case — randomized constructions are more commonly used to obtain “hard instances”: random functions are hard to learn, adding random noise is conjectured to makes it hard to learn linear functions (LPN), refuting random 3-SAT instances is conjectured to be hard [2], random strings are provably hard to compress (Kolmogorov), etc. In contrast, in our proof, we construct a randomized class so that it will be easy to learn.

Additionally, the proofs of the upper bound and lower bounds are very different from each other. Often there is some sort of “correspondence” between elements in the proofs of matching lower and upper bounds, but this does not appear to be the case here.

For the lower bound, the paper [2] offered a characterization of the transductive mistake bound, but that characterization somewhat obscures or deemphasizes the tree structure of the hypothesis class, which turns out to play an important role in our proof and in [1].

That being said, one important insight that allowed us to obtain our improved results, was that in the proof of the previous lower bound in [1], the adversary presents all the nodes in the Littlestone tree, and this can be bad for the adversary because some nodes are easy to guess, but still leak a small amount of information about the correct labeling function. Therefore, to obtain a stronger lower bound, one can try to present only a subset of the (“harder to guess”) nodes in the tree.

[1] Hanneke, S., Moran, S., & Shafer, J. (2023). A trichotomy for transductive online learning. Advances in Neural Information Processing Systems, 36, 19502-19519.

[2] Ben-David, S., Kushilevitz, E., & Mansour, Y. (1997). Online learning versus offline learning. Machine Learning, 29(1), 45-63.

[3] Feige, U. (2002). Relations between average case complexity and approximation complexity. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (pp. 534-543).