Exponential savings in agnostic active learning through abstention

Nikita Puchkin, Nikita Zhivotovskiy
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3806-3832, 2021.

Abstract

We show that in pool-based active classification without assumptions on the underlying distribution, if the learner is given the power to abstain from some predictions by paying the price marginally smaller than the average loss 1/2 of a random guess, exponential savings in the number of label requests are possible whenever they are possible in the corresponding realizable problem. We extend this result to provide a necessary and sufficient condition for exponential savings in pool-based active classification under the model misspecification.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-puchkin21a, title = {Exponential savings in agnostic active learning through abstention}, author = {Puchkin, Nikita and Zhivotovskiy, Nikita}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {3806--3832}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/puchkin21a/puchkin21a.pdf}, url = {https://proceedings.mlr.press/v134/puchkin21a.html}, abstract = {We show that in pool-based active classification without assumptions on the underlying distribution, if the learner is given the power to abstain from some predictions by paying the price marginally smaller than the average loss 1/2 of a random guess, exponential savings in the number of label requests are possible whenever they are possible in the corresponding realizable problem. We extend this result to provide a necessary and sufficient condition for exponential savings in pool-based active classification under the model misspecification.} }
Endnote
%0 Conference Paper %T Exponential savings in agnostic active learning through abstention %A Nikita Puchkin %A Nikita Zhivotovskiy %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-puchkin21a %I PMLR %P 3806--3832 %U https://proceedings.mlr.press/v134/puchkin21a.html %V 134 %X We show that in pool-based active classification without assumptions on the underlying distribution, if the learner is given the power to abstain from some predictions by paying the price marginally smaller than the average loss 1/2 of a random guess, exponential savings in the number of label requests are possible whenever they are possible in the corresponding realizable problem. We extend this result to provide a necessary and sufficient condition for exponential savings in pool-based active classification under the model misspecification.
APA
Puchkin, N. & Zhivotovskiy, N.. (2021). Exponential savings in agnostic active learning through abstention. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:3806-3832 Available from https://proceedings.mlr.press/v134/puchkin21a.html.

Related Material