The complexity of learning according to two models of a drifting environment

P. M. Long. The complexity of learning according to two models of a drifting environment. Machine Learning, 37(3):337-354, 1999.

(Available in Postscript and PDF formats.)

Abstract
We establish new bounds for learning in a drifting environment that are within constant factors of optimal. We give a simple proof of a bound on the sample complexity of agnostic learning in a fixed environment that is within a constant factor of optimal.