Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: It is generally believed active learning is model-dependent. This paper studies the problem of active learning for multiple target models. The authors first analyze the label complexity for active learning under the setting with multiple target models, then find the label complexity of single model is an upper bound of that for multiple models under the realizable case. They also propose an agnostic disagreement-based selection criterion for the agnostic case. Experiments verify the effectiveness of the proposed approach.
strengths_and_weaknesses: This paper explores a new setting of active learning where there are multiple target models to be learned. How to design effective active learning algorithms is practical and important to the machine learning community. It first analyzes the label complexity of passive learning and active learning for multiple target models under realizable case, and advocates active learning has potential improvement under this setting. For the agnostic setting, the authors propose disagreement-based selection criterion to query examples located in the joint disagreement regions. Theoretical analysis shows the proposed method achieves better label complexity than that of CAL (a representative approach) under some ideal situations. The writing is good and clear. The theoretical analysis and empirical experiments are solid.
questions: Theorem 3 is based on hyperparameter q=1. Is there a tighter result when q>1?
limitations: None
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work investigates an interesting problem, i.e., how to actively select the informative data to improve multiple target models simultaneously. First of all, the authors formally define the active learning (AL) for multiple target models problem and bridge the label complexity between AL for single and multiple models. After revealing the potential improvement of AL for this setting, a novel query strategy DIAM for multiple target models is further proposed, which prefers the data located in the joint disagreement regions. An efficient implementation for deep models is also provided. Both theoretical and empirical studies are conducted to validate the proposed approach.
strengths_and_weaknesses: This work is of high quality in my view due to the following reasons:

1.	The problem explored by this study is very important and meaningful. In many machine learning tasks, the devices to be deployed usually have varying computational resources, and there is a heavy burden of data labeling to train multiple models. These challenges become more tough with the flourishing applications of deep learning in recent years. 
2.	From the technical perspective, active learning is usually believed to be model-dependent. This work presents a nice attempt towards multiple target models from both theoretical and empirical views. It broadens the learning scenarios of active learning and may inspire future work towards thinking of this problem. This contribution is significant in my opinion.
3.	The paper is well-structured and easy to follow. The authors also provide enough supplementary materials and code for reproduction.

Weaknesses：
1. It seems that the specific form of \sigma in DIAM method is not given in the paper, the authors only say that it has the same form with RobustCAL method. I suggest to add this part for a more self-contained presentation.
2. It is better to introduce the structure of target models in the paper rather than in the supplementary materials for better understanding the results.

questions: 1. Theorem 1 also works for passive learning. How to guarantee the superiority of active learning?

2. Intuitively, the target models should share some specifications to make the active selection feasible. However, the proposed method works fine with very different target models according to the results in supplementary materials. The authors may explain more about this phenomenon.

limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies an important setting of active learning, motivated by the need to efficiently acquire a single dataset that is useful to simultaneously train various models/architectures. Contrary to common observations against a possible improvement of AL over PL under this setting, the authors theoretically prove a label complexity bound of active learning for multiple models which combined with a bound on passive learning implies active learning may also be efficient under this setting. The authors then modify a disagreement-based algorithm used for single-model AL to that for multiple models by taking their average disagreement and prove its label complexity in the agnostic setting. Lastly, this paper proposes a heuristic to circumvent the computational complexity when employing neural networks as the hypothesis class, and empirically demonstrates that this method outperforms well-known active learning algorithms designed for single-model AL, extended using the same average over multiple models, under this multiple target setting.
strengths_and_weaknesses: The main (and only) major theoretical contribution in this paper seems to be Theorem 1: It is an improved analysis method over a straightforward proof technique that translates the sample complexity of AL applied to a single hypothesis class indexed by i to that for multiple hypothesis classes as the sum of each complexity, as the authors mention (line 125). For PL, one can easily obtain a stronger translation since by definition of passive learning (random sampling), the complexity of PL for multiple hypothesis classes is the maximum over each sample complexity. I would think that for PL, this is the only guarantee possible without additional assumptions on how the hypothesis classes are related. Theorem 1 is a tool that is used to get a stronger translation from AL bounds for a single model to that for multiple models, and the authors use this to show that AL can potentially achieve an exponential improvement over PL in the multiple-model setting.

This is an interesting conclusion, but the reason I say this is the only theoretical contribution is that these bounds and corresponding comparisons between AL and PL are well-known for the single-model case, which this work uses extensively. In proving the theoretical statements in the paper, the only non-trivial modification to proofs by Henneke under this multiple-model setting is to use Theorem 1 in place of the sum of sample complexities for single-model AL.  This isn’t necessarily bad, but I would appreciate if the authors mention whether it’s possible that a stronger translation bound in place of Theorem 1 is likely. Additionally, I would appreciate if the authors remark on whether the bound translation for PL (as I mentioned above) is perhaps the tightest possible, and if not, it would be nice to see an effort improving the PL bound for multiple models being max_i \Lambda_i to another method analogous to Theorem 1 for AL.

Despite these concerns on theoretical statements, it is nice to see Theorem 4 which shows that DIAM-online is better than CAL applied to multiple target models. However, its presentation could be improved by instead writing that the sample complexity of DIAM-online (e.g. by writing \Lambda_m (DIAM) < \Lambda_m (CAL)), as the terms are redundant.

Here are a few major comments
* Presentation could be improved significantly. Many statements are defined in-text much after they are used, and some notations are never defined formally. Word choices are also poor, making it hard to infer what the authors attempt to say. There are some redundant statements that make the reader confused whether the statements are regarding different situations, and assumed settings go back and forth between agnostic and realizable. How the disagreement regions are to be computed in practice is described briefly in the last paragraph, whereas this the algorithm used throughout experiments. 
* I like how despite this paper being mostly theoretical, the experiments are done using somewhat large models and resembles the motivation mentioned in the introduction. However, I don’t think the tasks being classification on MNIST is convincing and I would like to see experiments on at least one larger dataset (even CIFAR-10 would be fine, or others used in the base code by Cai et al. 2020).
* The proposed problem setting is interesting and well-motivated. This work is the first to theoretically analyze the sample complexity of active learning for multiple target models, when the hypothesis classes are fixed (due to different target deployments). Section 2 compares with related work that studies similar but different problems and helps understand this problem setting’s position within literature.
* Algorithmically, the downside is that DIAM probably doesn’t work in the batch-setting, i.e. the algorithm would collect many similar samples when present. This is of large interest in the single-model AL setting, and I think the authors should mention this in the paper as a limitation.
* Also, the computational complexity should also be mentioned. As the authors note, computing the disagreements is computationally prohibitive for deep models. It would be nice to see how the heuristic overcomes this difficulty and what the resulting runtime is for practically-sized neural networks.

Minor comments
* Many grammatical errors should be fixed, e.g. remove “with” in line 83, must has -> is in line 125 and move the parenthesis before the period or even better, remove the parenthesis brackets and fix accordingly.
* Notations could be improved, but this might require much effort. For example, \Lambda_i is not defined other than the description in parenthesis in line 125-126, although I understand it to be the single-model AL complexity for class C_i (explained later in the draft). The fact that \Lambda_m is the notation for multiple-model AL where m is a different meaning than the “i” in \Lambda_i makes it confusing at first read.
* I don’t think the statement in Theorem 2 should be stated as a “Theorem”. I recommend changing this to a proposition or writing it as an in-text sentence after line 125, since the two statements are related in how to obtain a multiple-model sample complexity for AL (line 125) and PL (this statement). 

In summary, two major concerns I have is originality and presentation. For originality, I would like to hear the authors' remarks on whether Theorem 1 is tight and how a bound on single-model PL may or may not be improved. 
questions: Could the authors elaborate on the remark after Theorem 2? The fact that the target concept h* may not be included in every hypothesis space is not unique to PL, and is problematic for AL as well, no? Further, why is the last sentence in Section 4.1 included here? It seems that this would better fit under Section 4.2.

Please correct me if there are any misunderstandings in my comments above.

limitations: This draft does not clearly state apparent limitations, but does mention future work. Please incorporate my comments on the algorithmic and computational limitations and add others as appropriate.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a novel problem setting for active learning, where the aim is to query samples to improve multiple target models' performance simultaneously. This paper theoretically analyzes the label complexity of active learning under this setting and shows that active learning has the potential to achieve better label complexity. In addition, based on this analysis, this paper proposes an active learning strategy to query samples in the region of the joint disagreement of different target models, and experimentally shows the effectiveness of this strategy with two OCR datasets.
strengths_and_weaknesses: ### Strengths
* The problem setting tackled in this paper seems to be interesting and practically useful although it is difficult to judge novelty correctly for me because I'm not an expert in this field.
* There is a theoretical analysis. It seems intuitive and reasonable to select samples in the disagreement area of multiple target models. However, since I'm not an expert in the field, I was not able to follow all the proof and statements.
* Experimental results show the effectiveness of this method.

### Weaknesses
* Since the proposed method seems to be a general algorithm, it might be better to include evaluation other than OCR benchmark datasets.
questions: * it is better to explicitly define the terms "realizable and agnostic cases" for improving clarity and readability.
* In Theorem 1, each classifier $\hat{h} _i$ is obtained by ${\rm min} _{C_i} \ d(h_i, h_A)$. However, can such $( \hat{h} _i ) _i$ be learned from the same data? This point is unclear to me. 
* In Line 230, it would be better to explain the hyperparameter $q$.
limitations: The paper addressed the limitations in page 6 but does not mention any potential negative social impact.
review_title: null

Meta-review: metareview: This paper studies a novel active learning setting adapted to learning multiple target model. The authors propose a setting that can benefit to all tasks by focusing on regions with high disagreements. This contribution shows in a sense that the active learning procedure can be transferable to multiple tasks. A theoretical analysis is provided in the form of a bound on label complexity. Experimental results support the claims.

The reviewers have globally appreciated the contribution and most the comments raised in the reviews have been addressed in the rebuttal.  
The overall evaluation of the paper is positive and I propose acceptance.

I recommend the authors to take into consideration the last comments of the reviewers, in particular for improving the presentation of the paper.
confidence: Certain
Decision: Accept