Nuances in Margin Conditions Determine Gains in Active Learning
This work challenges the established intuition in machine learning that active learning should always offer improvements over passive learning in nonparametric contexts, highlighting a critical limitation for researchers and practitioners in the field.
The paper investigates how subtle differences in margin conditions affect the potential gains of active learning over passive learning in nonparametric classification, showing that certain nuances, such as the uniqueness of the Bayes classifier, can prevent any active learner from outperforming passive rates in common settings with near-uniform marginal distributions.
We consider nonparametric classification with smooth regression functions, where it is well known that notions of margin in $E[Y|X]$ determine fast or slow rates in both active and passive learning. Here we elucidate a striking distinction between the two settings. Namely, we show that some seemingly benign nuances in notions of margin -- involving the uniqueness of the Bayes classifier, and which have no apparent effect on rates in passive learning -- determine whether or not any active learner can outperform passive learning rates. In particular, for Audibert-Tsybakov's margin condition (allowing general situations with non-unique Bayes classifiers), no active learner can gain over passive learning in commonly studied settings where the marginal on $X$ is near uniform. Our results thus negate the usual intuition from past literature that active rates should improve over passive rates in nonparametric settings.