Chernoff Sampling for Active Testing and Extension to Active Regression
This work provides improved theoretical guarantees and a practical extension of an optimal active learning algorithm, benefiting researchers and practitioners in machine learning seeking to reduce sample complexity for hypothesis testing and parameter estimation.
This paper revisits Chernoff's asymptotically optimal algorithm for hypothesis testing, deriving a novel non-asymptotic sample complexity bound. The authors extend Chernoff sampling to estimate model parameters, providing a non-asymptotic bound on estimation error, and demonstrate its favorable performance against state-of-the-art methods in active learning for neural networks and real-data regression.
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.