On the complexity of learning from drifting distributions

We consider two models of on-line learning of binary-valued functions from drifting distributions due to Bartlett. We show that if each example is drawn from a joint distribution which changes in total variation distance by at most O(epsilon(3)/(d log(1/epsilon))) between trials, then an algorithm can achieve a probability of a mistake at most epsilon worse than the best function in a class of VC-dimension d. We prove a corresponding necessary condition of O(epsilon(3)/d). Finally, in the case that a fixed function is to be learned from noise-free examples, we show that if the distributions on the domain generating the examples change by at most O(epsilon(2)/(d log(1/epsilon))), then any consistent algorithm learns to within accuracy epsilon. (C) 1997 Academic Press.