# Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 16 references that are in the map.
- First posted on arXiv 20 Jul 2021.

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

- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes](https://mlsanity.com/paper/1706.01418/) (2017)

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

- [Universal Online Learning: an Optimistically Universal Learning Rule](https://mlsanity.com/paper/2201.05947/) (2022)
- [Universal Online Learning with Bounded Loss: Reduction to Binary Classification](https://mlsanity.com/paper/2112.14638/) (2021)
- [Universal Online Learning with Unbounded Losses: Memory Is All You Need](https://mlsanity.com/paper/2201.08903/) (2022)
- [Universally Consistent Online Learning with Arbitrarily Dependent Responses](https://mlsanity.com/paper/2203.06046/) (2022)
- [Universal Regression with Adversarial Responses](https://mlsanity.com/paper/2203.05067/) (2022)
- [Contextual Bandits and Optimistically Universal Learning](https://mlsanity.com/paper/2301.00241/) (2022)

## Abstract (arXiv)

This open problem asks whether there exists an online learning algorithm for binary classification that guarantees, for all target concepts, to make a sublinear number of mistakes, under only the assumption that the (possibly random) sequence of points X allows that such a learning algorithm can exist for that sequence. As a secondary problem, it also asks whether a specific concise condition completely determines whether a given (possibly random) sequence of points X admits the existence of online learning algorithms guaranteeing a sublinear number of mistakes for all target concepts.