# A Combinatorial Characterization of Supervised Online Learnability

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 19 references that are in the map.
- First posted on arXiv 7 Jul 2023.

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

- [Multiclass Online Learning and Uniform Convergence](https://mlsanity.com/paper/2303.17716/) (2023)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [Online Learning with Set-Valued Feedback](https://mlsanity.com/paper/2306.06247/) (2023)

## Abstract (arXiv)

We study the online learnability of hypothesis classes with respect to arbitrary, but bounded loss functions. No characterization of online learnability is known at this level of generality. We give a new scale-sensitive combinatorial dimension, named the sequential minimax dimension, and show that it gives a tight quantitative characterization of online learnability. In addition, we show that the sequential minimax dimension subsumes most existing combinatorial dimensions in online learning theory.