Multiclass Transductive Online Learning

We thank the reviewer for pointing out that our techniques could be of independent interest to the learning theory community and that our result almost rounds out the literature on regret and mistake bounds in the original transductive online learning setting. All minor issues and suggestions will be incorporated in the final version. We address each weakness and question below.

• The expectation is taken with respect to only the randomness of the learner. The learner makes predictions by sampling from distributions over $Y$. Thus, the reviewer is correct in the sense that the expectation is taken with respect to distributions over the label space $Y$. Regarding issues of measurability, following the work of [1], we only require that the singleton sets $\lbrace{y \rbrace}$ need to be measurable. We will make the assumption needed on $Y$ more clear in the camera-ready version.
• We agree with the reviewer that our agnostic upper bound uses a pretty standard technique. Our main contribution is in the realizable setting.
• Hanneke et al. [2023] in Claim 5.3 show that the DS dimension cannot characterize multiclass transductive online learnability. Namely, they give a class $C$ such that $DS(C) = 1$, but $C$ is not transductive online learnable. This necessitates the need for new dimensions since the Littlestone dimension is clearly not necessary. We will make this explicit in the main text of the camera ready version.
• We provided a brief explanation of the relevance of the Halving algorithm in transductive online learning in lines 110-120. In particular, we noted that a naive adaptation of the Halving algorithm for multiclass learning would not work and that we defined a new notion of shattering that would allow us to apply an analog of the Halving algorithm. Nevertheless, we will make sure to point out that both algorithms in Section 3.1 and 3.2 share similar overarching ideas in the sense that they both use the Halving technique with a particular combinatorial dimension. We note that the Halving technique using the DS dimension cannot work because the finiteness of the DS dimension is not sufficient for online learnability.
• In the realizable setting, we evaluate the learner through its mistake bound. On the other hand, in the agnostic setting, we evaluate the learner through its regret bound. In the realizable setting, the regret bound and mistake bound are the same quantities. However, this is not the case in the agnostic setting, where one usually only cares about the regret bound.
• Regarding the list setting, our lower bound applies to the list transductive online setting. However, it is possible to establish tighter lower bounds by adapting our definitions for $(L+1)$-array trees when the list size is $L$. Regarding the regression setting, one could approach this problem using binary results. We are uncertain whether our results will be directly applicable.

[1] S. Hanneke, S. Moran, V. Raman, U. Subedi, A. Tewari. Multiclass Online Learning and Uniform Convergence. 36th Conference on Learning Theory, 2023.

We thank the reviewer for finding our work to be well written and a nice contribution to a fundamental problem. All minor typos and suggestions will be incorporated in the final version. We address each weakness and question below.

• The algorithm achieving the $\log{T}$ upper bound in the realizable setting is the most significant contribution of our work, as mentioned in Section 1.2. We believe that the adaptation of this algorithm is applicable to various other settings, including list transductive online learning and transductive online learning with bandit feedback.
• In lines 102-103, we first stated that $D(C) = VC(C)$ for binary classification. Then, we stated that $B(C) < \infty$ if and only if $L(C) < \infty$ for binary classification. We did not make the claim that $B(C) < \infty$ if and only if $D(C) < \infty$.
• The label space $Y$ does not need to be countable. Following the work of [1], we only require that the singleton sets $\lbrace{y \rbrace}$ need to be measurable. We will make the assumption needed on $Y$ more clear in the camera-ready version.
• No, it is not possible to express Theorem 1 using DS and D because $DS(C) \leq D(C)$ for every $C$. In addition, Claim 5.4 in Hanneke et al. [2023] shows that the DS dimension does not characterize multiclass transductive online learning. Namely, there is a class where $DS(C) = 1$, but $C$ is not transductive online learnable. However, if $|Y| < \infty$, then the DS dimension does characterize learnability. We also note that we have comparisons to other existing dimensions in Appendices B and F.

[1] S. Hanneke, S. Moran, V. Raman, U. Subedi, A. Tewari. Multiclass Online Learning and Uniform Convergence. 36th Conference on Learning Theory, 2023.

We thank the reviewer for finding our work timely and interesting. All minor typos and suggestions will be incorporated in the final version. We address each weakness and question below.

• For small $k$ (i.e. $k << 2^{(\log{T})^2}$), the Natarajan bound can be smaller than the upper bound in terms of the Level-constrained Littlestone dimension. However, for large $k$ (i.e. $k > 2^{(\log{T})^2}$), our upper bound in terms of $D(C)$ can be better. We will make sure to point this out in the camera ready version.
• There can indeed be an arbitrary gap between $B(C)$ and $D(C)$. For example, for the class of thresholds $C = \lbrace{x \mapsto 1\lbrace{x \geq a \rbrace}: a \in \mathbb{R} \rbrace}$, we have that $D(C) = VC(C) = 1$, however $B(C) = \infty$ using the lower bound from Hanneke et al. [2023]. We will make sure to point this out in the main text. With regards to $B(C)$ and $L(C)$, there can also be an arbitrary gap. Proposition 4 in Appendix F gives a class where $B(C) \leq 2$ but $L(C) = \infty$. We will make this explicit in the main text again.
• Regarding the case when the rate is $O(1)$, Theorem 3 shows that when $B(C) < \infty$, the minimax rate is at most $B(C)$ in the realizable setting. With regards to lower bounds, we can also show that when $T$ is large enough (namely $T >> 2^{B(C)}$), the lowerbound in the realizable setting is also $B(C)/2$. We will include this lower bound in the camera-ready version.
• We thank the reviewer for pointing out these related previous works. We note that we do have a more in-depth discussion of prior work in Appendix A. In the final version, we will relocate this section to the main text. Additionally, we will incorporate a sentence that draws a precise comparison between our $B(C)$ and the rank notion from the paper by [Ben-David et al. 1997]. It is also important to note that while the dimension introduced by Devulapalli and Hanneke provides a lower bound, it is not feasible to establish an upper bound based on it. Specifically, their paper includes a theorem demonstrating the gap between transductive and self-directed online learning, even in the binary case.

We thank the reviewer for noting that our work resolves an open problem in online learning theory and that our paper is very well written and easy to understand. We address each weakness and question below.

• Multiclass learning with unbounded label spaces is a fundamental setting that has been under study for nearly 40 years, starting with [1,2] and more recently in [3,4,5,6]. Studying infinite label spaces is important as guarantees for multiclass learning should not inherently depend on the number of labels, even when it is finite. This is quite a practical concern as many modern machine learning paradigms have massive label space, such as in face recognition, next word prediction, and protein structure prediction, where the dependence of label size in learning bounds would be undesirable. Beyond being of practical interest, multiclass learning with infinite labels might also advance the understanding of real-valued regression problems [7]. Finally, in mathematics, concepts involving infinities often provide clearer insights into the true hardness of a problem. These motivations have been highlighted in lines 78-85.
• To define the Level-constrained Littlestone dimension, we first need to define the Level-constrained Littlestone tree. A Level-constrained Littlestone tree is a Littlestone tree with the additional requirement that the same instance has to label all the internal nodes across a given level. The Level-constrained Littlestone dimension is just the largest natural number $d \in \mathbb{N}$, such that there exists a shattered Level-constrained Littlestone tree of depth $d$. We will add a more intuitive explanation of this dimension in the final version.
• To define the Level-constrained Branching dimension, we first need to define the Level-constrained Branching tree. The Level-constrained Branching tree is a Level-constrained Littlestone tree without the restriction that the labels on the two outgoing edges are distinct. The Level-constrained Branching dimension is then the smallest natural number $d \in \mathbb{N}$ that satisfies the following condition: for every shattered Level-constrained Branching tree $\mathcal{T}$, there exists a path down $\mathcal{T}$ such that the number of nodes on this path whose outgoing edges are labeled by different elements of $Y$ is at most $d$. We will add a more intuitive explanation of this dimension in Section 1.2 of the final version.
• Our algorithms are not computationally efficient. Indeed, our algorithms require calculating the level-constrained Littlestone dimension or level-constrained branching dimension for concept classes. In the binary setting, the level-constrained Littlestone dimension equals the VC dimension, which is computationally hard to compute for general concept classes. That said, most online learning algorithms in online learning theory are not computationally efficient. For instance, in the case of adversarial online learning, SOA involves computing the Littlestone dimension of concept classes defined by the online learner in the course of its interaction with the adversary, which are challenging computations, even when the concept class and the set of features are finite [8]. Notably, no efficient algorithm can achieve finite mistake bounds for general Littlestone classes [9].

[1] Balas K. Natarajan. Some results on learning. 1988.

[2] B. K. Natarajan. On learning sets and functions. Machine Learning, 4:67–97, 1989.

[3] A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz. Multiclass learnability and the ERM principle. 24th Conference on Learning Theory, 2011.

[4] A. Daniely and S. Shalev-Shwartz. Optimal learners for multiclass problems. 27th Conference on Learning Theory, 2014.

[5] N. Brukhim, D. Carmon, I. Dinur, S. Moran, and A. Yehudayoff. A characterization of multiclass learnability. 63rd Annual IEEE Symposium on Foundations of Computer Science, 2022.

[6] S. Hanneke, S. Moran, V. Raman, U. Subedi, A. Tewari. Multiclass Online Learning and Uniform Convergence. 36th Conference on Learning Theory, 2023.

[7] I. Attias, S.Hanneke, A.Kalavasis, A. Karbasi, G. Velegkas. Optimal learners for realizable regression: Pac learning and online learning. Advances in Neural Information Processing Systems 36 (2023).

[8] P.Manurangsi, A. Rubinstein. Inapproximability of VC dimension and littlestone’s dimension. 30th Conference on Learning Theory, 2017.

[9] A. Assos, I. Attias, Y. Dagan, C.Daskalakis, M. K. Fishelson. Online learning and solving infinite games with an erm oracle. 36th Conference on Learning Theory, 2017.