Summary
This paper studies transductive online learning in the multiclass setting, where the label space can be unbounded. In the transductive setting, the adversary commits to a sequence of examples and can only adaptively choose labels for a sequence of instances, unlike the pure online setting where the adversary can adaptively choose both the sequence of examples and the labels, or the pure offline where the adversary commits to both a sequence of examples and labels.
The main result of this paper extends the results of Hanneke et. al. [2023] by characterizing the optimal mistake bound in the unbounded label case. The proof techniques involve defining and leveraging two new combinatorial parameters termed Level-constrained Branching and Littlestone dimensions. The authors prove that the level-constrained Littlestone dimension characterizes this specific variant of online learning.
Hanneke et. al. [2023]: A Trichotomy for Transductive Online Learning.
Strengths
1. This paper characterizes the optimal mistake bound of transductive online learners in the unbounded label space setting in both realizable and agnostic cases.
2. The paper introduces two new combinatorial parameters: the Level-constrained Littlestone dimension $D(C)$ and the Level-constrained Branching dimension $B(C)$, and show that $D(C)$ characterizes transductive online learning in the unbounded label setting. These new parameters are also compared to existing combinatorial parameters like the Natarajan Dimension, DS dimension, and the Graph dimension.
3. The technical parts of the paper involve modifying the Halving technique to work with new notion of shattering using the above newly introduced combinatorial parameters, and a modified version of Littlestone's standard optimal algorithm. Combined with the definition of $D(C)$ and $B(C)$, I feel that these new definitions and techniques could be of independent interest to the learning theory community.
4. This work almost rounds out the literature on regret and mistake bounds in the original transductive online learning setting. Removing the logarithmic factor in the upper bound of Theorem 3 seems to be the final milestone in this setting.
Weaknesses
1. The definitions of expected regret and expected cumulative mistakes in section 2.2 seem to be incomplete. What is the probability distribution that the expectations are taken with respect to? The only clear choice to me is some probability distribution over the label space $\mathcal{Y}$. Since the label space is unbounded (a critical point of this work), the notion of a probability distribution over this unbounded label space should be rigorously defined somewhere in the paper (maybe in the Appendix if there are space constraints). This seems to be an inexplicable oversight in an otherwise highly technical and detailed paper.
2. Even though the regret in the agnostic setting is stated in terms of the level-constrained Littlestone dimension, the proof technique heavily borrows from previous works. The authors state this clearly in the text as well. While the result serves a pedagogical purpose and also lends to completeness of the results, Theorem 4 cannot be counted as a significant contribution.
The following weaknesses do not directly impact my scores but should improve the paper's readability.
3. In reference [Brukhim 2022], the DS dimension characterizes multiclass learnability for unbounded label space in the offline setting. It is not immediately clear from the main text why the DS dimension cannot similarly characterize the transductive online setting and why $D(C)$ and $B(C)$ are required in the first place. The answer is possibly buried in Proposition 2, given in Appendix F.2, and should clearly be stated in the main text (even informal statements suffice), given the fact that the new combinatorial parameters are a core contribution of this paper.
4. The proofs in section 3.1 and 3.2 use the standard Halving technique, but make use of the newly defined combinatorial parameters. Both upper bounds share similar overarching ideas with each other, and also with results in previous works for the constrained label space. These two sections can be rewritten in a manner that highlights the power of the Halving technique. While the proofs themselves appear to be correct, if we take the above weakness into consideration, its also not immediately apparent from the main text why the Halving technique cannot be applied using more standard combinatorial parameters such as the DS dimension. Also, I feel that some parts of the proof can be deferred to the appendix (up to the discretion of the authors).
Questions
Minor issues
------------------
1. It is unclear from the definitions in section 2.2 how optimal regret and optimal mistake bound would be defined differently in the realizable setting. Could the authors expand on this?
2. Equations on lines 210, 285, and 354 should be formatted properly.
Future Work Discussions
-----------------------------------
Please feel free not to answer these questions if the authors are cramped for time. Not answering these questions will not affect my score.
1. Do the lower bounds of Theorem 3 hold directly for the list transductive online setting?
2. In the online real-valued regression setting, can one reduce a discretized version of the problem to the unbounded label case setting?
Limitations
Adequately discussed in the paper.