On the complexity of learning from drifting distributions

R. D. Barve and P. M. Long. On the complexity of learning from drifting distributions. Information and Computation, 138(2):101-123, 1997.

(Available in Postscript and PDF formats.)

Abstract
We prove performance guarantees for learning algorithms in two models of on-line learning of binary-valued functions from drifting distributions due to Bartlett.