# A Trichotomy for Transductive Online Learning

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 33 references that are in the map.
- First posted on arXiv 10 Nov 2023.

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

- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Efficient Algorithms for Adversarial Contextual Learning](https://mlsanity.com/paper/1602.02454/) (2016)

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

- [Multiclass Transductive Online Learning](https://mlsanity.com/paper/2411.01634/) (2024)
- [Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem](https://mlsanity.com/paper/2407.07765/) (2024)
- [Online Classification with Predictions](https://mlsanity.com/paper/2405.14066/) (2024)
- [Online Learning of Neural Networks](https://mlsanity.com/paper/2505.09167/) (2025)
- [Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Models](https://mlsanity.com/paper/2602.09402/) (2026)
- [Mistake-bounded online learning with operation caps](https://mlsanity.com/paper/2509.03892/) (2025)
- [Transductive Learning Is Compact](https://mlsanity.com/paper/2402.10360/) (2024)
- [Smoothed Online Classification can be Harder than Batch Classification](https://mlsanity.com/paper/2405.15424/) (2024)
- [Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning](https://mlsanity.com/paper/2506.00135/) (2025)
- [Optimal Mistake Bounds for Transductive Online Learning](https://mlsanity.com/paper/2512.12567/) (2025)
- [Universal Multiclass Transductive Online Learning](https://mlsanity.com/paper/2605.30479/) (2026)
- [Self-Directed Learning of Convex Labelings on Graphs](https://mlsanity.com/paper/2409.01428/) (2024)
- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)
- [An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order](https://mlsanity.com/paper/2609.10196/) (2026)

## Abstract (arXiv)

We present new upper and lower bounds on the number of learner mistakes in the `transductive' online learning setting of Ben-David, Kushilevitz and Mansour (1997). This setting is similar to standard online learning, except that the adversary fixes a sequence of instances x1,dots,xn to be labeled at the start of the game, and this sequence is known to the learner. Qualitatively, we prove a trichotomy, stating that the minimal number of mistakes made by the learner as n grows can take only one of precisely three possible values: n, Thetaleft(log (n)right), or Theta(1). Furthermore, this behavior is determined by a combination of the VC dimension and the Littlestone dimension. Quantitatively, we show a variety of bounds relating the number of mistakes to well-known combinatorial dimensions. In particular, we improve the known lower bound on the constant in the Theta(1) case from Omegaleft(√log(d)right) to Omega(log(d)) where d is the Littlestone dimension. Finally, we extend our results to cover multiclass classification and the agnostic setting.