@inproceedings{
hanneke2024universal,
title={Universal Rates for Active Learning},
author={Steve Hanneke and Amin Karbasi and Shay Moran and Grigoris Velegkas},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=T0e4Nw09XX}
}
In this work we study the problem of actively learning binary classifiers
  from a given concept class, i.e., learning by utilizing unlabeled data 
  and submitting targeted queries about their labels to a domain expert.
  We evaluate the quality of our solutions by considering the learning curves
  they induce, i.e., the rate of decrease
  of the misclassification probability as the number of label queries
  increases. The majority of the literature on active learning has 
  focused on obtaining uniform guarantees on the error rate which are
  only able to explain the upper envelope of the learning curves over families
  of different data-generating distributions. We diverge from this line of
  work and we focus on the distribution-dependent framework of universal
  learning whose goal is to obtain guarantees that hold for any fixed distribution,
  but do not apply uniformly over all the distributions. We provide a 
  complete characterization of the optimal learning rates that are achievable
  by algorithms that have to specify the number of unlabeled examples they
  use ahead of their execution. Moreover, we identify combinatorial complexity
  measures that give rise to each case of our tetrachotomic characterization.
  This resolves an open question that was posed by Balcan et al. (2010).
  As a byproduct of our main result,
  we develop an active learning algorithm for partial concept classes
  that achieves exponential learning rates in the uniform setting.
Universal Rates for Active Learning
Steve Hanneke Amin Karbasi Shay Moran Grigoris Velegkas