# Universal Online Learning: an Optimistically Universal Learning Rule

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 32 references that are in the map.
- First posted on arXiv 16 Jan 2022.

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

- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [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)
- [Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces](https://mlsanity.com/paper/2010.00636/) (2020)
- [Universal Online Learning with Bounded Loss: Reduction to Binary Classification](https://mlsanity.com/paper/2112.14638/) (2021)
- [Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?](https://mlsanity.com/paper/2107.09542/) (2021)

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

- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [Beyond IID: data-driven decision-making in heterogeneous environments](https://mlsanity.com/paper/2206.09642/) (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)
- [Adversarial Rewards in Universal Learning for Contextual Bandits](https://mlsanity.com/paper/2302.07186/) (2023)
- [Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Models](https://mlsanity.com/paper/2602.09402/) (2026)
- [Contextual Bandits and Optimistically Universal Learning](https://mlsanity.com/paper/2301.00241/) (2022)
- [A Theory of Optimistically Universal Online Learnability for General Concept Classes](https://mlsanity.com/paper/2501.08551/) (2025)
- [Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness](https://mlsanity.com/paper/2602.20585/) (2026)
- [Universal Multiclass Transductive Online Learning](https://mlsanity.com/paper/2605.30479/) (2026)
- [When Is Inductive Inference Possible?](https://mlsanity.com/paper/2312.00170/) (2023)
- [Online Consistency of the Nearest Neighbor Rule](https://mlsanity.com/paper/2410.23644/) (2024)

## Abstract (arXiv)

We study the subject of universal online learning with non-i.i.d. processes for bounded losses. The notion of an universally consistent learning was defined by Hanneke in an effort to study learning theory under minimal assumptions, where the objective is to obtain low long-run average loss for any target function. We are interested in characterizing processes for which learning is possible and whether there exist learning rules guaranteed to be universally consistent given the only assumption that such learning is possible. The case of unbounded losses is very restrictive, since the learnable processes almost surely visit a finite number of points and as a result, simple memorization is optimistically universal. We focus on the bounded setting and give a complete characterization of the processes admitting strong and weak universal learning. We further show that k-nearest neighbor algorithm (kNN) is not optimistically universal and present a novel variant of 1NN which is optimistically universal for general input and value spaces in both strong and weak setting. This closes all COLT 2021 open problems posed by Hanneke on universal online learning.