On Learnability under General Stochastic Processes
This work addresses a gap in learning theory for non-iid settings, which is incremental as it extends existing frameworks.
The paper tackles the problem of defining learnability for function classes under general non-iid stochastic processes, showing that two natural notions are equivalent to online learnability, with results applicable to binary classification and regression.
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.