The complexity of learning according to two models of a drifting environment
Philip M. Long · 1998
We show that a vccf&rJ bound on the rate of drift of the distribution generating the examples is sufficient for agnostic learning to relative accuracy E, where c > 0 is a constant; this matches a known necessary conditionto within a constant factor.We establish a A7 sufficient condition for the realizable case, also matching a known necessary condition to within a constant factor.We provide a relatively sim 0 (5 (VCdim(3) + log k 7 le proof of a bound of ) on the sample complexity of agnostic learning in a fixed environment.