Chernoff Sampling for Active Testing and Extension to Active Regression

Subhojyoti Mukherjee, Ardhendu S. Tripathy, Robert Nowak
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:7384-7432, 2022.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-mukherjee22a, title = { Chernoff Sampling for Active Testing and Extension to Active Regression }, author = {Mukherjee, Subhojyoti and Tripathy, Ardhendu S. and Nowak, Robert}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {7384--7432}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/mukherjee22a/mukherjee22a.pdf}, url = {https://proceedings.mlr.press/v151/mukherjee22a.html}, 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. } }
Endnote
%0 Conference Paper %T Chernoff Sampling for Active Testing and Extension to Active Regression %A Subhojyoti Mukherjee %A Ardhendu S. Tripathy %A Robert Nowak %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-mukherjee22a %I PMLR %P 7384--7432 %U https://proceedings.mlr.press/v151/mukherjee22a.html %V 151 %X 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.
APA
Mukherjee, S., Tripathy, A.S. & Nowak, R.. (2022). Chernoff Sampling for Active Testing and Extension to Active Regression . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:7384-7432 Available from https://proceedings.mlr.press/v151/mukherjee22a.html.

Related Material