# On Learnability under General Stochastic Processes

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2020.

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

- [On Empirical Risk Minimization with Dependent and Heavy-Tailed Data](https://mlsanity.com/paper/2109.02224/) (2021)
- [Trade-off Between Dependence and Complexity for Nonparametric Learning -- an Empirical Process Approach](https://mlsanity.com/paper/2401.08978/) (2024)
- [Forecasting Competitions with Correlated Events](https://mlsanity.com/paper/2303.13793/) (2023)
- [How Patterns Dictate Learnability in Sequential Data](https://mlsanity.com/paper/2510.10744/) (2025)

## Abstract (arXiv)

Statistical learning theory under independent and identically distributed (iid) sampling and online learning theory for worst case individual sequences are two of the best developed branches of learning theory. Statistical learning under general non-iid stochastic processes is less mature. We provide two natural notions of learnability of a function class under a general stochastic process. We show that both notions are in fact equivalent to online learnability. Our results hold for both binary classification and regression.