Complexity of learning according to two models of a drifting environment

Abstract

The problem of learning functions from some set X to {0, 1} using two models of a drifting environment is studied. It is shown that a bound on the rate of drift of the distribution generating the examples is sufficient for learning to relative accuracy; this matches a known necessary condition to within a constant factor. A sufficient condition is established for the realizable case, also matching a known necessary condition to within a constant factor. A relatively simple proof of a bound of on the sample complexity of agnostic learning in a fixed environment is presented.