43baa6762fa81bb43b39c62553b2970d-Reviews.html

In particular, they study batch-mode active learning from two aspects: (1) Suppose the batch sizes are equal. Fix the number of rounds examined, how many labels one has to request in total to achieve some certain error rate; (2) given that the cost to obtain a batch of labels is sublinear in the size of the batch ( as referred to as ``buy-in-bulk discount''), how is the total cost of the proposed batch algorithms compared with that of fully-sequential active learning methods. For the first aspect, the authors propose batch-based variants of the well-known CAL algorithm for sequential active learning, and provide upper bounds on label complexity of k-batch active learning, for both the realizable case and the non-realizable case (with Tsybakov noise). For the second aspect, they provide a cost-adaptive modification of the CAL algorithm, and find that the total cost by this algorithm may often be significantly smaller than that of the analogous methods in the fully sequential setting.