# Universally Consistent Online Learning with Arbitrarily Dependent Responses

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 26 references that are in the map.
- First posted on arXiv 11 Mar 2022.

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

- [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 Online Learning: an Optimistically Universal Learning Rule](https://mlsanity.com/paper/2201.05947/) (2022)
- [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, 6 of 6)

- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [Adversarial Rewards in Universal Learning for Contextual Bandits](https://mlsanity.com/paper/2302.07186/) (2023)
- [Uncertainty quantification in metric spaces](https://mlsanity.com/paper/2405.05110/) (2024)
- [Contextual Bandits and Optimistically Universal Learning](https://mlsanity.com/paper/2301.00241/) (2022)
- [Conformal and kNN Predictive Uncertainty Quantification Algorithms in Metric Spaces](https://mlsanity.com/paper/2507.15741/) (2025)
- [Variable Selection Methods for Multivariate, Functional, and Complex Biomedical Data in the AI Age](https://mlsanity.com/paper/2501.06868/) (2025)

## Abstract (arXiv)

This work provides an online learning rule that is universally consistent under processes on (X,Y) pairs, under conditions only on the X process. As a special case, the conditions admit all processes on (X,Y) such that the process on X is stationary. This generalizes past results which required stationarity for the joint process on (X,Y), and additionally required this process to be ergodic. In particular, this means that ergodicity is superfluous for the purpose of universally consistent online learning.