Interactive Algorithms: from Pool to Stream

Sivan Sabato, Tom Hess
29th Annual Conference on Learning Theory, PMLR 49:1419-1439, 2016.

Abstract

We consider interactive algorithms in the pool-based setting, and in the stream-based setting. Interactive algorithms observe suggested elements (representing actions or queries), and interactively select some of them and receive responses. Pool-based algorithms can select elements at any order, while stream-based algorithms observe elements in sequence, and can only select elements immediately after observing them. We assume that the suggested elements are generated independently from some source distribution, and ask what is the stream size required for emulating a pool algorithm with a given pool size. We provide algorithms and matching lower bounds for general pool algorithms, and for utility-based pool algorithms. We further show that a maximal gap between the two settings exists also in the special case of active learning for binary classification.

Cite this Paper

BibTeX
@InProceedings{pmlr-v49-sabato16, title = {Interactive Algorithms: from Pool to Stream}, author = {Sabato, Sivan and Hess, Tom}, booktitle = {29th Annual Conference on Learning Theory}, pages = {1419--1439}, year = {2016}, editor = {Feldman, Vitaly and Rakhlin, Alexander and Shamir, Ohad}, volume = {49}, series = {Proceedings of Machine Learning Research}, address = {Columbia University, New York, New York, USA}, month = {23--26 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v49/sabato16.pdf}, url = {https://proceedings.mlr.press/v49/sabato16.html}, abstract = {We consider interactive algorithms in the pool-based setting, and in the stream-based setting. Interactive algorithms observe suggested elements (representing actions or queries), and interactively select some of them and receive responses. Pool-based algorithms can select elements at any order, while stream-based algorithms observe elements in sequence, and can only select elements immediately after observing them. We assume that the suggested elements are generated independently from some source distribution, and ask what is the stream size required for emulating a pool algorithm with a given pool size. We provide algorithms and matching lower bounds for general pool algorithms, and for utility-based pool algorithms. We further show that a maximal gap between the two settings exists also in the special case of active learning for binary classification.} }
Endnote
%0 Conference Paper %T Interactive Algorithms: from Pool to Stream %A Sivan Sabato %A Tom Hess %B 29th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2016 %E Vitaly Feldman %E Alexander Rakhlin %E Ohad Shamir %F pmlr-v49-sabato16 %I PMLR %P 1419--1439 %U https://proceedings.mlr.press/v49/sabato16.html %V 49 %X We consider interactive algorithms in the pool-based setting, and in the stream-based setting. Interactive algorithms observe suggested elements (representing actions or queries), and interactively select some of them and receive responses. Pool-based algorithms can select elements at any order, while stream-based algorithms observe elements in sequence, and can only select elements immediately after observing them. We assume that the suggested elements are generated independently from some source distribution, and ask what is the stream size required for emulating a pool algorithm with a given pool size. We provide algorithms and matching lower bounds for general pool algorithms, and for utility-based pool algorithms. We further show that a maximal gap between the two settings exists also in the special case of active learning for binary classification.
RIS
TY - CPAPER TI - Interactive Algorithms: from Pool to Stream AU - Sivan Sabato AU - Tom Hess BT - 29th Annual Conference on Learning Theory DA - 2016/06/06 ED - Vitaly Feldman ED - Alexander Rakhlin ED - Ohad Shamir ID - pmlr-v49-sabato16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 49 SP - 1419 EP - 1439 L1 - http://proceedings.mlr.press/v49/sabato16.pdf UR - https://proceedings.mlr.press/v49/sabato16.html AB - We consider interactive algorithms in the pool-based setting, and in the stream-based setting. Interactive algorithms observe suggested elements (representing actions or queries), and interactively select some of them and receive responses. Pool-based algorithms can select elements at any order, while stream-based algorithms observe elements in sequence, and can only select elements immediately after observing them. We assume that the suggested elements are generated independently from some source distribution, and ask what is the stream size required for emulating a pool algorithm with a given pool size. We provide algorithms and matching lower bounds for general pool algorithms, and for utility-based pool algorithms. We further show that a maximal gap between the two settings exists also in the special case of active learning for binary classification. ER -
APA
Sabato, S. & Hess, T.. (2016). Interactive Algorithms: from Pool to Stream. 29th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 49:1419-1439 Available from https://proceedings.mlr.press/v49/sabato16.html.

Related Material