Scheduling to Learn In An Unsupervised Online Streaming Model
  An unsupervised online streaming model is considered where samples arrive in
an online fashion over $T$ slots. There are $M$ classifiers, whose confusion
matrices are unknown a priori. In each slot, at most one sample can be labeled
by any classifier. The accuracy of a sample is a function of the set of labels
obtained for it from various classifiers. The utility of a sample is a scalar
multiple of its accuracy minus the response time (difference of the departure
slot and the arrival slot), where the departure slot is also decided by the
algorithm. Since each classifier can label at most one sample per slot, there
is a tradeoff between obtaining a larger set of labels for a particular sample
to improve its accuracy, and its response time. The problem of maximizing the
sum of the utilities of all samples is considered, where learning the confusion
matrices, sample-classifier matching assignment, and sample departure slot
decisions depend on each other. The proposed algorithm first learns the
confusion matrices, and then uses a greedy algorithm for sample-classifier
matching. A sample departs once its incremental utility turns non-positive. We
show that the competitive ratio of the proposed algorithm is
$\frac{1}{2}-{\mathcal O}\left(\frac{\log T}{T}\right)$.
