# Universal Multiclass Transductive Online Learning

arXiv: https://arxiv.org/abs/2605.30479 · HTML: https://mlsanity.com/paper/2605.30479/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 28 references that are in the map.
- First posted on arXiv 28 May 2026.

## Builds on (most cited first, 15 of 15)

- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes](https://mlsanity.com/paper/1706.01418/) (2017)
- [Multiclass Online Learning and Uniform Convergence](https://mlsanity.com/paper/2303.17716/) (2023)
- [A Trichotomy for Transductive Online Learning](https://mlsanity.com/paper/2311.06428/) (2023)
- [Universal Online Learning: an Optimistically Universal Learning Rule](https://mlsanity.com/paper/2201.05947/) (2022)
- [Universal Online Learning with Unbounded Losses: Memory Is All You Need](https://mlsanity.com/paper/2201.08903/) (2022)
- [Multiclass Transductive Online Learning](https://mlsanity.com/paper/2411.01634/) (2024)
- [Fine-Grained Distribution-Dependent Learning Curves](https://mlsanity.com/paper/2208.14615/) (2022)
- [Universal Rates for Multiclass Learning](https://mlsanity.com/paper/2307.02066/) (2023)
- [Universal Rates of Empirical Risk Minimization](https://mlsanity.com/paper/2412.02810/) (2024)
- [Optimal Mistake Bounds for Transductive Online Learning](https://mlsanity.com/paper/2512.12567/) (2025)
- [A Theory of Optimistically Universal Online Learnability for General Concept Classes](https://mlsanity.com/paper/2501.08551/) (2025)

## Built on by (most cited first, 1 of 1)

- [Two Dimensions Govern Agnostic Multiclass Transductive Learning](https://mlsanity.com/paper/2608.25326/) (2026)

## Abstract (arXiv)

We consider the problem of universal transductive online classification with a possibly unbounded label space. This setting considers online learning, with the sequence of instances (without labels) known to the learner in advance. We say a concept class H is learnable if there is a learning algorithm A, such that for every realizable sequence, the number of mistakes made by A grows at most sublinearly with the number of predictions. We characterize the learnability of this setting and show that there are only two possible optimal rates for the learnable classes: either bounded or increasing logarithmically. We introduce a new combinatorial structure, called ``Level-Constrained-Littlestone-Littlestone (LCLL) tree'', which, along with the indifference property, characterizes the learnability. We also extend the learnability result to the agnostic case and the case where only the stochastic process that generates the instance sequence is known.