# Universal Online Learning with Bounded Loss: Reduction to Binary Classification

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 21 references that are in the map.
- First posted on arXiv 29 Dec 2021.

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

- [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)
- [Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces](https://mlsanity.com/paper/2010.00636/) (2020)
- [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, 8 of 8)

- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [Universal Online Learning: an Optimistically Universal Learning Rule](https://mlsanity.com/paper/2201.05947/) (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)
- [Metric-valued regression](https://mlsanity.com/paper/2202.03045/) (2022)
- [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)
- [Online Consistency of the Nearest Neighbor Rule](https://mlsanity.com/paper/2410.23644/) (2024)

## Abstract (arXiv)

We study universal consistency of non-i.i.d. processes in the context of online learning. A stochastic process is said to admit universal consistency if there exists a learner that achieves vanishing average loss for any measurable response function on this process. When the loss function is unbounded, Blanchard et al. showed that the only processes admitting strong universal consistency are those taking a finite number of values almost surely. However, when the loss function is bounded, the class of processes admitting strong universal consistency is much richer and its characterization could be dependent on the response setting (Hanneke). In this paper, we show that this class of processes is independent from the response setting thereby closing an open question (Hanneke, Open Problem 3). Specifically, we show that the class of processes that admit universal online learning is the same for binary classification as for multiclass classification with countable number of classes. Consequently, any output setting with bounded loss can be reduced to binary classification. Our reduction is constructive and practical. Indeed, we show that the nearest neighbor algorithm is transported by our construction. For binary classification on a process admitting strong universal learning, we prove that nearest neighbor successfully learns at least all finite unions of intervals.