mlsanityData to 7 Oct 2026

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

arXiv 2107.09542 ↗First posted 20 Jul 2021cs.LG cs.AI math.PRcited by 6

Not on the map. Why?

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.

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

Builds on

3 of 16 references.

References · 3

  1. 2020A Theory of Universal Learningcited by 59
  2. 2019Universal Bayes consistency in metric spacescited by 32
  3. 2017Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processescited by 23

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 5.

6 papers.

  1. 2022Universal Online Learning: an Optimistically Universal Learning Rulecited by 12
  2. 2021Universal Online Learning with Bounded Loss: Reduction to Binary Classificationcited by 8
  3. 2022Universal Online Learning with Unbounded Losses: Memory Is All You Needcited by 8
  4. 2022Universally Consistent Online Learning with Arbitrarily Dependent Responsescited by 6
  5. 2022Universal Regression with Adversarial Responsescited by 5
  6. 2022Contextual Bandits and Optimistically Universal Learningcited by 2