  Active learning is a paradigm of machine learning which aims at reducing the
amount of labeled data needed to train a classifier. Its overall principle is
to sequentially select the most informative data points, which amounts to
determining the uncertainty of regions of the input space. The main challenge
lies in building a procedure that is computationally efficient and that offers
appealing theoretical properties; most of the current methods satisfy only one
or the other. In this paper, we use the classification with rejection in a
novel way to estimate the uncertain regions. We provide an active learning
algorithm and prove its theoretical benefits under classical assumptions. In
addition to the theoretical results, numerical experiments have been carried
out on synthetic and non-synthetic datasets. These experiments provide
empirical evidence that the use of rejection arguments in our active learning
algorithm is beneficial and allows good performance in various statistical
situations.
