Learning with a slowly changing distribution
Peter L. Bartlett · 1992
In this paper, we consider the problem of learning a subset of a domain from randomly chosen examples when the probability distribution of the examples changes slowly but continually throughout the learning process. We give upper and lower bounds on the best achievable probability of misclassification after a given number of examples. If d is the VC-dimension of the target function class, t is the number of examples, and fl is the amount by which the distribution is allowed to change (measured by the largest change in the probability of a subset of the domain), the upper bound decreases as d=t initially, and settles to O(d 2=3 fl 1=3 ) for large t. The general lower bound on the probability of misclassification again decreases as d=t initially, but settles to \\Omega\\Gamma d 1=2 fl 1=2 ) for large t. These bounds give necessary and sufficient conditions on fl, the rate of change of the distribution of examples, to ensure that some learning algorithm can produce an acceptably s...