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:
- 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.
- Logarithmic Rate ($\Theta(\log T)$): This occurs when $B(\mathcal{C})$ is infinite but the Level-constrained Littlestone dimension $D(\mathcal{C})$ is finite.
- 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