The Complexity of Learning According to Two Models of a Drifting Environment

Abstract

We show that a \(\frac{{c \in ^3 }}{{{\text{VCdim(}}\mathcal{F}{\text{)}}}}\) bound on the rate of drift of the distribution generating the examples is sufficient for agnostic learning to relative accuracy ∈, where c > 0 is a constant; this matches a known necessary condition to within a constant factor. We establish a \(\frac{{c \in ^2 }}{{{\text{VCdim(}}\mathcal{F}{\text{)}}}}\) 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(\frac{1}{{_ \in 2}}({\text{VCdim(}}\mathcal{F}{\text{)}}\) + \(\log \frac{1}{\delta }))\) on the sample complexity of agnostic learning in a fixed environment.