  We study actively labeling streaming data, where an active learner is faced
with a stream of data points and must carefully choose which of these points to
label via an expensive experiment. Such problems frequently arise in
applications such as healthcare and astronomy. We first study a setting when
the data's inputs belong to one of $K$ discrete distributions and formalize
this problem via a loss that captures the labeling cost and the prediction
error. When the labeling cost is $B$, our algorithm, which chooses to label a
point if the uncertainty is larger than a time and cost dependent threshold,
achieves a worst-case upper bound of $\widetilde{O}(B^{\frac{1}{3}}
K^{\frac{1}{3}} T^{\frac{2}{3}})$ on the loss after $T$ rounds. We also provide
a more nuanced upper bound which demonstrates that the algorithm can adapt to
the arrival pattern, and achieves better performance when the arrival pattern
is more favorable. We complement both upper bounds with matching lower bounds.
We next study this problem when the inputs belong to a continuous domain and
the output of the experiment is a smooth function with bounded RKHS norm. After
$T$ rounds in $d$ dimensions, we show that the loss is bounded by
$\widetilde{O}(B^{\frac{1}{d+3}} T^{\frac{d+2}{d+3}})$ in an RKHS with a
squared exponential kernel and by $\widetilde{O}(B^{\frac{1}{2d+3}}
T^{\frac{2d+2}{2d+3}})$ in an RKHS with a Mat\'ern kernel. Our empirical
evaluation demonstrates that our method outperforms other baselines in several
synthetic experiments and two real experiments in medicine and astronomy.
