Buy-in-Bulk Active Learning
In many practical applications of active learning, it is more cost-effective to request labels in large batches, rather than one-at-a-time. This is because the cost of labeling a large batch of examples at once is often sublinear in the number of examples in the batch. In this work, we study the label complexity of active learning algorithms that request labels in a given number of batches, as well as the tradeoff between the total number of queries and the number of rounds allowed. We additionally study the total cost sufficient for learning, for an abstract notion of the cost of requesting the labels of a given number of examples at once. In particular, we find that for sublinear cost functions, it is often desirable to request labels in large batches (i.e., buying in bulk); although this may increase the total number of labels requested, it reduces the total cost required for learning.
*Summary* This paper discusses 
      (disagreement-based) batch-mode active learning, and puts forward a 
      theoretical framework bounding the sample complexity and the total cost of 
      buy-in-bulk active learning (i.e., batch-mode active learning with 
      sublinear cost functions w.r.t. the size of a batch). 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. *Quality* This 
      paper nicely extends the previous work (Hanneke ’10) to the batch-mode 
      setting. The first part (section 3, 4) derives upper bounds (depending the 
      size of a batch) of label complexity of the proposed batch algorithms. It 
      is technically sound, and thoroughly explained. The second part (section 
      5), however, is less clear. From line 376 to 380, the authors directly 
      compare two upper bounds that are obtained separately (potentially with 
      different low-order terms hidden in the big O notation), and conclude that 
      buy-in-bulk active learning are usually more cost-efficient - which seems 
      not fair to me. Besides, there is no empirical evaluation of the 
      proposed algorithm. Given the various motivating applications mentioned 
      before, it would be interesting to see how the Cost-Adaptive CAL performs 
      empirically with different cost models. *Clarity* The 
      second result (Section 5) for buy-in-bulk active learning, as appears in 
      the paper, is striking, yet unconvincing. According to Theorem 5.1, if the 
      cost function is linear in batch sizes, then the proposed batch-mode 
      algorithm (Cost-Adaptive CAL) will exhibit the same form of upper bound as 
      that of the fully-sequential CAL algorithm. Intuitively, under such (unit) 
      cost setting, the cost of Cost-Adaptive CAL should be higher than fully 
      sequential CAL. However, according to the two upper bounded provided in 
      line 343 and 367, one can not tell the difference. Further analysis on the 
      difference (hidden constant or low-order terms) between the cost bounds 
      would be helpful. Originality and Significance Active learning 
      problems under the batch-mode setting are quite natural and interesting, 
      but so far only a few theoretical work have been done (e.g., Chen & 
      Krause, ICML’13 formulate it as an adaptive optimization problem). This 
      paper explores the theoretical aspect of the mellow schemes for batch-mode 
      active learning. Although the proof technique relies heavily on the 
      previous work on (sequential) active learning, it is one of the few 
      attempts made along this line of research. Editorial issue(s): 
      1. line 171, second term in the max bracket: $er(h)$ is not a 
      subscript. 2. the paper exceeds the submission page limit by 3 lines. 
      Update: I've considered the authors' rebuttal, and decide not to 
      change my score. Specifically, I’m still not convinced that the cost of 
      the batch algorithm is only constant factor away from the sequential CAL 
      (according to the rebuttal) -- there might be some lower order terms in 
      the bound of the batch algorithm, which is important when comparing with 
      the sequential bound. This is one of the main reasons that I would like to 
      see some empirical evidence of the statement.