Active Learning with Neural Networks: Insights from Nonparametric Statistics

Yinglun Zhu, Robert D Nowak

Deep learning has revolutionized standard "passive" machine learning, where models are trained on massive, pre-labeled datasets. However, in Active Learning (AL), the model takes an active role, querying a human expert to label only the most informative data points from an unlabeled pool. The ultimate goal is to achieve high accuracy with the fewest possible labels.

While deep active learning has demonstrated immense empirical success, its theoretical foundations have historically lagged behind. Proving exactly why it works—and mathematically bounding the number of labels required to reach a specific error level (label complexity)—has remained a formidable challenge. Previous theoretical proofs often relied on oversimplified models, such as linearizing a network, which fail to capture the true behavior of deep neural networks.

Presented at NeurIPS 2022, this paper bridges the gap between empirical success and theoretical guarantees. The authors provide the first near-optimal label complexity guarantees for deep active learning by framing it as a nonparametric statistics problem, demonstrating that neural networks can achieve minimax optimality and even exponential label savings.

A Nonparametric Perspective

To establish rigorous guarantees, the authors shift the theoretical framework from parametric models to nonparametric statistics. Rather than evaluating standard image datasets like CIFAR-10 or ImageNet, the paper defines mathematical problem instances within specific function spaces. They assume the "true" relationship between data and labels is a smooth function belonging to standard Sobolev or Hölder spaces.

Crucially, they leverage recent advances in approximation theory to demonstrate that a neural network of a specific depth and width can effectively "mimic" the optimal smooth functions required by nonparametric theory. Furthermore, they extend their results to Radon $BV^2$ spaces—a more recent mathematical space that naturally describes the types of functions ReLU networks excel at representing.

Algorithmic Frameworks: NeuralCAL and NeuralCAL++

The authors introduce two primary active learning algorithms designed for neural networks:

  1. NeuralCAL (Disagreement-Based Learning): This algorithm maintains a "version space" of candidate neural networks. It only requests a label for a new data point if the candidate networks disagree on what that label should be. Under standard noise conditions, NeuralCAL achieves a label complexity that matches the theoretical lower bounds for any nonparametric learner, up to small logarithmic factors.
  2. NeuralCAL++ (Learning with Abstention): This extension incorporates an abstention option, related to Chow’s error. The model is allowed to output "I don't know" for a small penalty cost. This mechanism allows the algorithm to focus its labeling budget strictly on the most resolvable parts of the data distribution.

Key Breakthroughs and Insights

The theoretical analysis of these algorithms yields several profound insights into why deep active learning is so effective:

  • Neural Networks as Universal Classifiers: By carefully calibrating the network architecture, neural networks can achieve "minimax" label complexity, which is considered the gold standard of statistical efficiency.
  • The Power of "I Don't Know": The most striking insight is that adding an abstention option bypasses the traditional need for "low-noise" assumptions. Typically, fast learning rates require clean data near the decision boundary. By allowing the model to abstain on ambiguous data, NeuralCAL++ achieves massive label savings even in noisy environments.
  • Exponential Speedups: With the abstention option, the number of labels required scales as $\text{polylog}(1/\epsilon)$. In practical terms, to achieve a 10x improvement in accuracy, the model does not need 10x more labels; it may only need a few more. This represents a massive leap from polynomial to logarithmic scaling.
  • Beating the Curse of Dimensionality: By applying their framework to Radon $BV^2$ spaces, the authors prove that active learning with ReLU networks can avoid the exponential slowdown typically associated with high-dimensional input features.
  • Computational Efficiency: The abstention algorithm is shown to be "oracle-efficient." It can be implemented using standard square-loss regression, meaning it is compatible with standard training tools like Stochastic Gradient Descent (SGD).

Limitations and Future Directions

While this paper establishes a robust theoretical foundation for deep active learning, it acknowledges several limitations that pave the way for future research:

  • Parameter Knowledge: The current algorithms require prior knowledge of problem-dependent parameters, such as the smoothness of the underlying function or the exact noise level in the labels. In real-world applications, these parameters are rarely known in advance.
  • The Disagreement Coefficient: The theoretical bounds rely on a "disagreement coefficient" ($\theta$), which measures the variance among networks in the version space. While the authors provide bounds for this coefficient, developing a universal understanding of it for general neural network architectures remains an open problem.
  • Adaptivity: To bridge the remaining gap between theory and practice, future work must focus on developing "adaptive" algorithms capable of automatically sensing data smoothness and noise levels without requiring explicit prior inputs.

Summary updated

Abstract

Deep neural networks have great representation power, but typically require large numbers of training examples. This motivates deep active learning methods that can significantly reduce the amount of labeled training data. Empirical successes of deep active learning have been recently reported in the literature, however, rigorous label complexity guarantees of deep active learning have remained elusive. This constitutes a significant gap between theory and practice. This paper tackles this gap by providing the first near-optimal label complexity guarantees for deep active learning. The key insight is to study deep active learning from the nonparametric classification perspective. Under standard low noise conditions, we show that active learning with neural networks can provably achieve the minimax label complexity, up to disagreement coefficient and other logarithmic terms. When equipped with an abstention option, we further develop an efficient deep active learning algorithm that achieves $\mathsf{polylog}(\frac{1}{\varepsilon})$ label complexity, without any low noise assumptions. We also provide extensions of our results beyond the commonly studied Sobolev/H\"older spaces and develop label complexity guarantees for learning in Radon $\mathsf{BV}^2$ spaces, which have recently been proposed as natural function spaces associated with neural networks.
BibTeX
@inproceedings{zhu2022active,
  author = {Yinglun Zhu and Robert D Nowak},
  title = {{Active Learning with Neural Networks: Insights from Nonparametric Statistics}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=LRMmgkcoCnW},
}
Figure