Chernoff Sampling for Active Testing and Extension to Active Regression
arXiv:2012.08073
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.
47 pages, 9 figures
References in corpus (10)
- Optimal Best Arm Identification with Fixed Confidence
- Best-Arm Identification in Linear Bandits
- Beyond Disagreement-based Agnostic Active Learning
- Gamification of Pure Exploration for Linear Bandits
- Pure Exploration with Multiple Correct Answers
- Gradient Ascent for Active Exploration in Bandit Problems
- Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality
- Online A-Optimal Design and Active Linear Regression
- An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits
- Improved Algorithms for Agnostic Pool-based Active Classification