### 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.

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

# Related Articles

**2017-03-08**

1703.02647 | stat.ML

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

**2018-03-12**

1803.04509 | cs.NE

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

**2019-01-16**

1901.05515 | cs.LG

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

**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

**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

**2019-05-13**

1905.04941 | cs.DS

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

**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

**2018-10-02**

1810.01489 | cs.DC

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

**2019-05-07**

1905.02367 | cs.DS

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

**2018-11-19**

1811.07971 | cs.DS

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

**2019-01-09**

1901.02857 | cs.DS

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

**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

**2017-11-08**

1711.03091 | cs.LG

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

**2016-02-23**

1602.07120 | cs.LG

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

**2016-05-22**

1605.06792 | cs.LG

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

**2018-04-09**

1804.03197 | cs.DS

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