ML p(r)ior | Interactive algorithms: from pool to stream

Interactive algorithms: from pool to stream

2016-02-02
1602.01132 | stat.ML
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.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2017-03-08

In many machine learning applications, it is important to explain the predictions of a black-box cla… show more
PDF

Highlights - Most important sentences from the article

2018-03-12

We study sorting of permutations by random swaps if each comparison gives the wrong result with some… show more
PDF

Highlights - Most important sentences from the article

2019-01-16

We quantify the separation between the numbers of labeled examples required to learn in two settings… show more
PDF

Highlights - Most important sentences from the article

2014-09-11
1409.3600 | cs.DS

We revisit the selection problem, namely that of computing the $i$th order statistic of $n$ given el… show more
PDF

Highlights - Most important sentences from the article

2019-03-31
1904.00507 | stat.ML

Source coding is the canonical problem of data compression in information theory. In a {\em locally … show more
PDF

Highlights - Most important sentences from the article

2019-05-13
1905.04941 | cs.DS

We study the submodular secretary problem with a cardinality constraint. In this problem, $n$ candid… show more
PDF

Highlights - Most important sentences from the article

2019-01-25
1901.09017 | cs.DS

Consider a totally ordered set $S$ of $n$ elements; as an example, a set of tennis players and their… show more
PDF

Highlights - Most important sentences from the article

2018-10-02
1810.01489 | cs.DC

Submodular optimization has received significant attention in both practice and theory, as a wide ar… show more
PDF

Highlights - Most important sentences from the article

2019-05-07

We propose the first adversarially robust algorithm for monotone submodular maximization under singl… show more
PDF

Highlights - Most important sentences from the article

2018-11-19
1811.07971 | cs.DS

Differentially Private algorithms often need to select the best amongst many candidate options. Clas… show more
PDF

Highlights - Most important sentences from the article

2019-01-09

We initiate a study of algorithms with a focus on the computational complexity of individual element… show more
PDF

Highlights - Most important sentences from the article

2018-09-24
1809.09165 | cs.LG

One of the key resources in large-scale learning systems is the number of rounds of communication be… show more
PDF

Highlights - Most important sentences from the article

2017-11-08

Data-driven algorithm design, that is, choosing the best algorithm for a specific application, is a … show more
PDF

Highlights - Most important sentences from the article

2016-02-23
1602.07120 | cs.LG

We consider interactive learning and covering problems, in a setting where actions may incur differe… show more
PDF

Highlights - Most important sentences from the article

2016-05-22

We propose a pool-based non-parametric active learning algorithm for general metric spaces, called M… show more
PDF

Highlights - Most important sentences from the article

2018-04-09

We give new upper and lower bounds for the {\em dynamic} set cover problem. First, we give a $(1+\ep… show more
PDF

Highlights - Most important sentences from the article