Multiclass Transductive Online Learning

Steve Hanneke, Vinod Raman, Amirreza Shaeiri, Unique Subedi

Abstract

In the realm of online learning, the transductive setting—where the learner observes all unlabeled instances at the outset—offers a significant information advantage. While well-understood for binary and finite multiclass classification, the case of infinite label spaces has remained an open challenge. This paper establishes a complete characterization of multiclass transductive online learning in the infinite-label regime. By introducing two novel combinatorial dimensions—the Level-constrained Littlestone and Level-constrained Branching dimensions—we demonstrate that the minimax expected mistakes follow a strict trichotomy: $\Theta(1)$, $\Theta(\log T)$, or $\Theta(T)$.

1. Introduction

Online learning involves a sequential interaction where a learner predicts labels for instances $x_t$ and receives feedback $y_t$ over $T$ rounds. In the transductive variant, the adversary reveals the sequence of instances $(x_1, \dots, x_T)$ at the beginning of the game, though labels are still revealed sequentially. This setting is often more representative of real-world scenarios where the pool of data to be labeled is known, such as in certain semi-supervised or active learning contexts.

While binary transductive learning is well-characterized, extending these results to multiclass settings with an infinite number of labels (e.g., natural language processing or open-set recognition) presents unique theoretical hurdles. Traditional complexity measures, such as the Sauer-Shelah-Perles lemma, rely on finite label spaces and fail to provide meaningful bounds when the label set $\mathcal{Y}$ is unbounded. This paper identifies the fundamental dimensions that determine learnability in this infinite-label regime.

2. Fundamental Dimensions for Infinite Labels

To address the limitations of existing tools, this work proposes two new combinatorial dimensions based on tree structures that capture the complexity of a concept class $\mathcal{C}$ without depending on the size of the label set.

2.1 Level-constrained Littlestone Dimension ($D(\mathcal{C})$)

The Level-constrained Littlestone dimension measures the complexity of the concept class by considering trees where all nodes at a specific depth (level) are associated with the same instance $x$. This dimension is the critical threshold for determining whether sublinear regret is achievable.

2.2 Level-constrained Branching Dimension ($B(\mathcal{C})$)

The Level-constrained Branching dimension is a more granular measure. It tracks the frequency with which paths in a tree branch into distinct labels. This dimension determines whether a learner can achieve a constant number of mistakes, independent of the time horizon $T$.

3. The Trichotomy of Learning Rates

A central contribution of this research is the discovery of a "trichotomy" in the minimax expected number of mistakes $M^*(T, \mathcal{C})$. Unlike other learning settings where rates might vary continuously, transductive multiclass learning exhibits only three possible growth rates in the realizable setting:

  1. Constant Rate ($\Theta(1)$): This occurs if and only if the Level-constrained Branching dimension $B(\mathcal{C})$ is finite. In this regime, the learner makes a bounded number of mistakes regardless of how many rounds are played.
  2. Logarithmic Rate ($\Theta(\log T)$): This occurs when $B(\mathcal{C})$ is infinite but the Level-constrained Littlestone dimension $D(\mathcal{C})$ is finite.
  3. Linear Rate ($\Theta(T)$): This occurs if $D(\mathcal{C})$ is infinite, indicating that the concept class is too complex to learn even with transductive information.

Notably, there is no "middle ground" (such as $\sqrt{T}$) for the expected mistake bound in the realizable setting. This highlights how much easier transductive learning can be; for example, in the class of "halfspaces," the mistake bound drops from linear ($\Theta(T)$) in the traditional setting to logarithmic ($\Theta(\log T)$) in the transductive setting.

4. Algorithmic Framework

The paper introduces two primary algorithms to achieve these optimal rates:

  • Modified Halving Algorithm: To handle infinite label spaces, the authors adapt the classic Halving algorithm using a new notion of "shattering" that replaces simple concept counting.
  • Modified Standard Optimal Algorithm (SOA): By adapting Littlestone’s SOA to the Level-constrained Branching dimension, the authors provide a mechanism for achieving the constant mistake bound.

5. Agnostic Learning and Regret Bounds

In the agnostic setting, where the data may not be perfectly labeled by any concept in $\mathcal{C}$, the paper establishes bounds on the expected regret $R^*(T, \mathcal{C})$. The authors prove: $$\frac{\sqrt{T \cdot D(\mathcal{C})}}{8} \leq R^*(T, \mathcal{C}) \leq \sqrt{T \cdot D(\mathcal{C}) \log \left( \frac{eT}{D(\mathcal{C})} \right)}$$ This result demonstrates that the Level-constrained Littlestone dimension remains the governing factor for regret in the presence of noise or model mismatch.

6. Conclusion and Future Directions

This work provides the first complete characterization of multiclass transductive online learning with infinite labels, removing the dependence on label set size $|\mathcal{Y}|$. While the trichotomy of rates is now firmly established, a small logarithmic gap remains in the agnostic regret bounds. Future research may focus on closing this gap, extending the framework to bandit feedback models, or applying these level-constrained dimensions to transductive real-valued regression.

Summary updated

Abstract

We consider the problem of multiclass transductive online learning when the number of labels can be unbounded. Previous works by Ben-David et al. [1997] and Hanneke et al. [2024] only consider the case of binary and finite label spaces respectively. The latter work determined that their techniques fail to extend to the case of unbounded label spaces, and they pose the question of characterizing the optimal mistake bound for unbounded label spaces. We answer this question, by showing that a new dimension, termed the Level-constrained Littlestone dimension, characterizes online learnability in this setting. Along the way, we show that the trichotomy of possible minimax rates established by Hanneke et al. [2024] for finite label spaces in the realizable setting continues to hold even when the label space is unbounded. In particular, if the learner plays for $T \in \mathbb{N}$ rounds, its minimax expected number of mistakes can only grow like $\Theta(T)$, $\Theta(\log T)$, or $\Theta(1)$. To prove this result, we give another combinatorial dimension, termed the Level-constrained Branching dimension, and show that its finiteness characterizes constant minimax expected mistake-bounds. The trichotomy is then determined by a combination of the Level-constrained Littlestone and Branching dimensions. Quantitatively, our upper bounds improve upon existing multiclass upper bounds in Hanneke et al. [2024] by removing the dependence on the label set size. In doing so, we explicitly construct learning algorithms that can handle extremely large or unbounded label spaces. A key component of our algorithm is a new notion of shattering that exploits the sequential nature of transductive online learning. Finally, we complete our results by proving expected regret bounds in the agnostic setting, extending the result of Hanneke et al. [2024].
BibTeX
@inproceedings{hanneke2024multiclass,
  author = {Steve Hanneke and Vinod Raman and Amirreza Shaeiri and Unique Subedi},
  title = {{Multiclass Transductive Online Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=3EREVfwALz},
}
Figure