Large deviations for the perceptron model and consequences for active
  learning
  Active learning is a branch of machine learning that deals with problems
where unlabeled data is abundant yet obtaining labels is expensive. The
learning algorithm has the possibility of querying a limited number of samples
to obtain the corresponding labels, subsequently used for supervised learning.
In this work, we consider the task of choosing the subset of samples to be
labeled from a fixed finite pool of samples. We assume the pool of samples to
be a random matrix and the ground truth labels to be generated by a
single-layer teacher random neural network. We employ replica methods to
analyze the large deviations for the accuracy achieved after supervised
learning on a subset of the original pool. These large deviations then provide
optimal achievable performance boundaries for any active learning algorithm. We
show that the optimal learning performance can be efficiently approached by
simple message-passing active learning algorithms. We also provide a comparison
with the performance of some other popular active learning strategies.
