Learning with a Drifting Target Concept
  We study the problem of learning in the presence of a drifting target
concept. Specifically, we provide bounds on the error rate at a given time,
given a learner with access to a history of independent samples labeled
according to a target concept that can change on each round. One of our main
contributions is a refinement of the best previous results for polynomial-time
algorithms for the space of linear separators under a uniform distribution. We
also provide general results for an algorithm capable of adapting to a variable
rate of drift of the target concept. Some of the results also describe an
active learning variant of this setting, and provide bounds on the number of
queries for the labels of points in the sequence sufficient to obtain the
stated bounds on the error rates.
