The complexity of learning according to two models of a drifting environment
We show that a c epsilon(3)/VC dim(F) bound on the rate of drift of the distribution generating the examples is sufficient for agnostic learning to relative accuracy epsilon, where c > 0 is a constant; this matches a known necessary condition to within a constant factor. We establish a c epsilon(2)/VC dim(F) sufficient condition for the realizable case, also matching a known necessary condition to within a constant factor. We provide a relatively simple proof of a bound of O((epsilon)1/2 (VC dim(F) + log 1/delta)) on the sample complexity of agnostic learning in a fixed environment.
agnostic learning computational learning theory concept drift context-sensitive learning prediction pac learning uniform convergence vc theory