Active Learning for Smooth Problems.
Eric Friedman · 2009
Recently it was shown that the true sample com-plexity of active learning is asymptotically better than that for passive learning. In many interesting cases, the improvement has been shown to be ex-ponential [BHW08]; however, there are artificial examples in which the improvement is small. In this paper we provide a basis for a exponential im-provements in active learning. We show that ex-ponential improvements arise when the underlying learning problem is “smooth, ” i.e., the hypothesis class, the instance space and the distribution can all be described by smooth functions. This provides a unified and simplified analysis for most known ex-amples and significantly extends the class learning problems that are “actively learnable at an expo-nential rate.” 1