Agnostic Active Learning Is Always Better Than Passive Learning

This work resolves a long-standing open question of central importance to the theory of active learning, closing a qualitative and quantitative gap in our understanding of active learning in the non-realizable case. We provide the first sharp characterization of the optimal first-order query complexity of agnostic active learning, and propose a new general active learning algorithm which achieves it. Remarkably, the optimal query complexity admits a leading term which is always strictly smaller than the sample complexity of passive supervised learning (by a factor proportional to the best-in-class error rate). This was not previously known to be possible. For comparison, in all previous general analyses, the leading term exhibits an additional factor, such as the disagreement coefficient or related complexity measures, and therefore only provides improvements over passive learning in restricted cases. The present work completely removes such factors from the leading term, implying that every concept class benefits from active learning in the non-realizable case. Whether such benefits are possible has been the driving question underlying the past two decades of research on the theory of agnostic active learning. This work finally settles this fundamental question. This result resolves an important long-standing open question central to the past two decades of research on the theory of agnostic active learning. Algorithm and Outline of the Analysis We next present the algorithm achieving Theorems 1 and 3 and a sketch of its analysis (the complete formal proof is given in Appendix E). Before stating the algorithm, we first introduce a few additional definitions and convenient notational conventions.