Understanding the Effects of Batching in Online Active Learning

Kareem Amin, Corinna Cortes, Giulia DeSalvo, Afshin Rostamizadeh
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:3482-3492, 2020.

Abstract

Online active learning (AL) algorithms often assume immediate access to a label once a query has been made. However, due to practical constraints, the labels of these queried examples are generally only available in “batches”. In this work, we present an analysis for a generic class of batch online AL algorithms, which reveals that the effects of batching are in fact mild and only result in an additional label complexity term that is quasilinear in the batch size. To our knowledge, this provides the first theoretical justification for such algorithms and we show how they can be applied to batch variants of three canonical online AL algorithms: IWAL, ORIWAL, and DHM. Finally, we also present empirical results across several benchmark datasets that corroborate these theoretical insights.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-amin20a, title = {Understanding the Effects of Batching in Online Active Learning}, author = {Amin, Kareem and Cortes, Corinna and DeSalvo, Giulia and Rostamizadeh, Afshin}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {3482--3492}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/amin20a/amin20a.pdf}, url = {https://proceedings.mlr.press/v108/amin20a.html}, abstract = {Online active learning (AL) algorithms often assume immediate access to a label once a query has been made. However, due to practical constraints, the labels of these queried examples are generally only available in “batches”. In this work, we present an analysis for a generic class of batch online AL algorithms, which reveals that the effects of batching are in fact mild and only result in an additional label complexity term that is quasilinear in the batch size. To our knowledge, this provides the first theoretical justification for such algorithms and we show how they can be applied to batch variants of three canonical online AL algorithms: IWAL, ORIWAL, and DHM. Finally, we also present empirical results across several benchmark datasets that corroborate these theoretical insights.} }
Endnote
%0 Conference Paper %T Understanding the Effects of Batching in Online Active Learning %A Kareem Amin %A Corinna Cortes %A Giulia DeSalvo %A Afshin Rostamizadeh %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-amin20a %I PMLR %P 3482--3492 %U https://proceedings.mlr.press/v108/amin20a.html %V 108 %X Online active learning (AL) algorithms often assume immediate access to a label once a query has been made. However, due to practical constraints, the labels of these queried examples are generally only available in “batches”. In this work, we present an analysis for a generic class of batch online AL algorithms, which reveals that the effects of batching are in fact mild and only result in an additional label complexity term that is quasilinear in the batch size. To our knowledge, this provides the first theoretical justification for such algorithms and we show how they can be applied to batch variants of three canonical online AL algorithms: IWAL, ORIWAL, and DHM. Finally, we also present empirical results across several benchmark datasets that corroborate these theoretical insights.
APA
Amin, K., Cortes, C., DeSalvo, G. & Rostamizadeh, A.. (2020). Understanding the Effects of Batching in Online Active Learning. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:3482-3492 Available from https://proceedings.mlr.press/v108/amin20a.html.

Related Material