Noise-tolerant, Reliable Active Classification with Comparison Queries

Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:1957-2006, 2020.

Abstract

With the explosion of massive, widely available unlabeled data in the past years, finding label and time efficient, robust learning algorithms has become ever more important in theory and in practice. We study the paradigm of active learning, in which algorithms with access to large pools of data may adaptively choose what samples to label in the hope of exponentially increasing efficiency. By introducing comparisons, an additional type of query comparing two points, we provide the first time and query efficient algorithms for learning non-homogeneous linear separators robust to bounded (Massart) noise. We further provide algorithms for a generalization of the popular Tsybakov low noise condition, and show how comparisons provide a strong reliability guarantee that is often impractical or impossible with only labels - returning a classifier that makes no errors with high probability.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-hopkins20a, title = {Noise-tolerant, Reliable Active Classification with Comparison Queries}, author = {Hopkins, Max and Kane, Daniel and Lovett, Shachar and Mahajan, Gaurav}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {1957--2006}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/hopkins20a/hopkins20a.pdf}, url = {https://proceedings.mlr.press/v125/hopkins20a.html}, abstract = { With the explosion of massive, widely available unlabeled data in the past years, finding label and time efficient, robust learning algorithms has become ever more important in theory and in practice. We study the paradigm of active learning, in which algorithms with access to large pools of data may adaptively choose what samples to label in the hope of exponentially increasing efficiency. By introducing comparisons, an additional type of query comparing two points, we provide the first time and query efficient algorithms for learning non-homogeneous linear separators robust to bounded (Massart) noise. We further provide algorithms for a generalization of the popular Tsybakov low noise condition, and show how comparisons provide a strong reliability guarantee that is often impractical or impossible with only labels - returning a classifier that makes no errors with high probability.} }
Endnote
%0 Conference Paper %T Noise-tolerant, Reliable Active Classification with Comparison Queries %A Max Hopkins %A Daniel Kane %A Shachar Lovett %A Gaurav Mahajan %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-hopkins20a %I PMLR %P 1957--2006 %U https://proceedings.mlr.press/v125/hopkins20a.html %V 125 %X With the explosion of massive, widely available unlabeled data in the past years, finding label and time efficient, robust learning algorithms has become ever more important in theory and in practice. We study the paradigm of active learning, in which algorithms with access to large pools of data may adaptively choose what samples to label in the hope of exponentially increasing efficiency. By introducing comparisons, an additional type of query comparing two points, we provide the first time and query efficient algorithms for learning non-homogeneous linear separators robust to bounded (Massart) noise. We further provide algorithms for a generalization of the popular Tsybakov low noise condition, and show how comparisons provide a strong reliability guarantee that is often impractical or impossible with only labels - returning a classifier that makes no errors with high probability.
APA
Hopkins, M., Kane, D., Lovett, S. & Mahajan, G.. (2020). Noise-tolerant, Reliable Active Classification with Comparison Queries. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:1957-2006 Available from https://proceedings.mlr.press/v125/hopkins20a.html.

Related Material