Generalized Chernoff Sampling for Active Learning and Structured Bandit Algorithms

Subhojyoti Mukherjee, Ardhendu Tripathy, Robert D. NowakarXiv 2020 · arXiv

Abstract

This paper bridges the gap between active hypothesis testing and active regression by extending Chernoff’s asymptotically optimal sampling strategy. We provide the first non-asymptotic sample complexity bounds for these algorithms and demonstrate that this unified approach outperforms state-of-the-art methods in tasks ranging from simple hypothesis tests to training neural networks. By characterizing the relationship between discrete testing and continuous parameter estimation, we offer a robust framework for sequential experimental design under a fixed confidence or fixed budget.

1. Introduction

In standard machine learning, data is typically assumed to be collected independently and identically distributed (i.i.d.). However, in many real-world scenarios—such as clinical trials or sensor placement—data collection is expensive. Active learning addresses this by allowing an algorithm to sequentially choose which data points (or "actions") to sample, potentially reaching high accuracy with significantly fewer observations.

While active learning is well-understood for classification, it has remained less developed for regression and hypothesis testing in finite-sample regimes. Most existing theoretical guarantees for these problems are "asymptotic," describing behavior only as the number of samples approaches infinity. This presents a challenge for practitioners operating under limited budgets. Furthermore, a unifying theory connecting discrete testing (selecting one of $J$ hypotheses) with continuous regression (estimating a parameter $\theta \in \mathbb{R}^d$) has been largely absent. This paper addresses these gaps by revisiting and generalizing Chernoff Sampling (CS).

2. The Chernoff Sampling Framework

Originally proposed in 1959 for sequential experimental design, Chernoff Sampling (CS) uses a "max-min" optimization strategy. The authors extend this logic to create a versatile framework for both testing and regression.

2.1 Active Testing

For discrete hypotheses, the algorithm identifies the current most likely hypothesis and then selects the action that best discriminates it from its "closest" competitor. The paper introduces a novel non-asymptotic bound for this process, characterizing performance at a fixed confidence level ($\delta$). This allows for a precise understanding of the sample complexity required to reach a decision.

2.2 Active Regression

The framework extends to continuous parameter spaces by proving that the optimal sampling distribution for regression is related to E-optimality in experimental design. In this context, the algorithm chooses samples that maximize the minimum eigenvalue of the information matrix, effectively reducing uncertainty in the "most uncertain" direction of the parameter space. The authors demonstrate that as the distance between discrete hypotheses goes to zero, the discrete optimization problem converges to this eigenvalue optimization.

2.3 Algorithmic Variants

To improve practical utility, the authors propose several variants:

  • T2 (Top-2) Sampling: A computationally efficient heuristic that focuses only on the two most likely hypotheses.
  • Batch-CS: Updates the sampling strategy every $B$ rounds to reduce the computational overhead of solving optimizations at every step.
  • CSE (CS with Exploration): Incorporates a small degree of random exploration to prevent the algorithm from converging on suboptimal actions due to noisy early estimates.

3. Empirical Evaluation

The authors evaluated the generalized CS framework across a diverse range of benchmarks:

  • Synthetic "3-Group" Setting: A controlled environment with 50 actions designed to test the algorithm's ability to ignore non-informative data.
  • Non-Linear Regression: A synthetic problem involving a sigmoid-like reward function to test the limits of the linear assumption.
  • Neural Network Learning: Training a single-hidden-layer ReLU network to learn a 2D function from noisy observations, demonstrating scalability to complex models.
  • Real-World Datasets: The UCI Red Wine Quality and UCI Air Quality datasets were used to simulate linear regression active learning tasks.

4. Key Insights

4.1 Exploration vs. Verification

The non-asymptotic bounds reveal two distinct phases in the learning process: an initial exploration phase, where the algorithm identifies the true hypothesis, and a subsequent verification phase, where it collects samples at an optimal rate to meet the required confidence threshold.

4.2 Sparsity of Optimal Design

A significant finding is that the optimal sampling distribution is generally sparse. In the Red Wine dataset, for instance, the Chernoff strategy ignores the majority of available data points, concentrating its sampling budget on a few highly informative actions. This suggests that active learning can drastically simplify data collection protocols.

4.3 Likelihood-Free Flexibility

Unlike many classical methods that rely on specific noise models, this approach is "likelihood-free." It remains valid for any sub-Gaussian observation noise, making it applicable to a wider range of real-world distributions than standard Maximum Likelihood estimators.

5. Results and Conclusion

Theoretical analysis shows that the derived non-asymptotic bounds for CS match known minimax lower bounds up to logarithmic factors. Experimentally, CS and its variants consistently reached target confidence levels faster than uniform sampling or the "Two-Phase" (TP) policy. In neural network experiments, CS and CSE reduced estimation error significantly faster than the "ActiveS" baseline.

While the computational cost of solving convex optimizations remains a factor, the introduction of Batch-CS and the theoretical bridging of testing and regression mark a significant step forward. Future work may focus on extending these results to non-differentiable functions and deeper neural architectures where the mean function is less smooth.

Summary updated

Abstract

Active learning can reduce the number of samples needed to perform a hypothesis test and to estimate the parameters of a model. In this paper, we revisit the work of Chernoff that described an asymptotically optimal algorithm for performing a hypothesis test. We obtain a novel sample complexity bound for Chernoff's algorithm, with a non-asymptotic term that characterizes its performance at a fixed confidence level. We also develop an extension of Chernoff sampling that can be used to estimate the parameters of a wide variety of models and we obtain a non-asymptotic bound on the estimation error. We apply our extension of Chernoff sampling to actively learn neural network models and to estimate parameters in real-data linear and non-linear regression problems, where our approach performs favorably to state-of-the-art methods.
BibTeX
@misc{mukherjee2020generalized,
  author = {Subhojyoti Mukherjee and Ardhendu Tripathy and Robert D. Nowak},
  title = {{Generalized Chernoff Sampling for Active Learning and Structured Bandit Algorithms}},
  year = {2020},
  eprint = {2012.08073},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.08073},
}
Figure