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

It is shown that a 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.

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.