Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper tackles the pool-based active learning problem using a constrained learning formulation. The authors use the dual variable corresponding to each labeled data point as a measure of its information, and they train another model to predict the dual variable for the unlabeled data to determine which ones are the most informative, i.e., if the most informative ones are labeled and learned, the overall performance of the model will improve the most. The authors have also done experiments on classification tasks with images and a regression task with Unified Parkinson’s Disease Rating Scores. Additionally, there is a visualization of the relationship between the dual variable and the informativeness.
strengths_and_weaknesses: Major strengths:

1. This paper provides a new type of solution for active learning from a novel perspective of the usage of the dual variable in constrained optimization. Although Theorem 3.2 can be obtained straightforward with the Lagrangian function, it is very insightful to connect this formulation to the active learning problem where labeling and learning a new data point is explained as a way to satisfy a stricter constraint on the loss of this data point.
2. I would like to emphasize the merit of the simplicity of the formulation and analysis in this paper. Although the only requirement for Theorem 3.2, the strong dualality of CSL, is still strong, it leaves a space for readers to adapt the general idea in this paper to their own problem settings.

Minor strengths:

1. This paper is well-written.
2. The authors provide the ablation study for the constraint tightness.

Major weakness:

1. Theorem 3.2 could be wrong. The proof in Appendix B has some issues. For Line 577, $\lambda$ depends on $\epsilon$ but this is not shown. This affects the derivation in Line 580 where there is $\epsilon$. Also, the sub-gradient is not defined in the way as shown in Line 580. In general, this could be potentially fixed, but I still think it is a major problem because this is the crucial reason why one want to use the dual variable as the information indicator.

Minor weakness: 

1. The citations in Line 87-88 are not correct.
2. The citations in the Appendix are missing, e.g., Line 558, 571-572, 585, etc.
questions: ### 

1. The constrained optimization formulation can be think inversely where larger $\lambda$ corresponds to the data point that we do NOT want to include in learning. Here, we assume that including one data point in the learning process makes the model enjoy a lower loss on this specific data point. It is intuitive that having a stricter constraint will let the minimum of the objective function value becomes larger (i.e., worse) which means the overall loss is larger. Therefore, learning a data point with large $\lambda$ forces the model forgetting other information and the overall loss will only decrease more because of this learning. In this way, we want to learn the data with $\lambda=0$ because they do not hinder the minimization of the overall loss. Why is this explanation incorrect?
2. For the Batch Active Learning setting, Line 98, why the loss is evaluated on only the training dataset (already labeled + actively labeled)? I think we want the model to be good on any data from the population, not specifically on the ones we want to label.
3. We know that $\lambda$ depends on the derivative of $P$ in terms of $\epsilon$, but the derivative only captures the slope. Adding a newly labeled data point in model training may cause a large change of $\epsilon$. Is there any result on the second order derivative of $P$?
4. For Line 123, when you say ‘The most informative samples often lie in the tails of the distribution’, how do you define the informativeness strictly or specifically?
5. In the Abstract, Line 14, ‘(we) also discuss its limitations depending on the capacity of the model used’. Could you point out where the discussion is?
limitations: The authors have not discussed the limitation or the societal impact of their method.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors present a new active learning algorithm by formulating AL as a constrained statistical learning algorithm (CSL). In the CSL formulation the objective is to minimize loss on the data distribution subject to an auxiliary loss being upper bounded by epsilon everywhere. The authors then consider the Lagrangian of the optimization problem to derive a primal-dual algorithm to solve the optimization problem over the labeled dataset. The dual variables, obtained for the labeled dataset, are then generalized over the unlabeled pool by using a 2-head neural net, where one head predicts the labels and another head predicts the dual variables. This neural net is used to generalize the value of the dual variables to the entire unlabeled pool. The sample with the maximum dual variable is then chosen for labeling in the next round and this process is repeated. The authors provide an interpretation of the dual variables and also demonstrate the efficacy of their methods against a few baseline algorithms. The paper is well written and was easy to follow.
strengths_and_weaknesses: Strengths:
The paper is well written and easy to follow.
The algorithm is pretty simple and intuitively sound. 
The framing of active learning problem as a constrained statistical learning problem is innovative.
The experimental results look good.
On the whole I like the paper and I think it puts forward an interesting formulation and I can see quite a bit of follow up work stemming out of this work.

Weaknesses:
The motivation to frame AL as a CSL problem is not clear to me. In general the paper, while being good on the optimization front, does not do a good job in connecting the formulation to statistical principles.

Some design choices (such as choosing a constant epsilon) are not well explained. 

questions: 1. What is the reason for formulating the AL problem as a CSL problem ? Can we reason about this choice of formulation from a statistical viewpoint?
2. The role of the auxiliary loss function was unclear to me? What would the advantage be of choosing an auxiliary loss function to be different from the main loss function?
3. Algorithm 2 chooses the unlabeled point with the maximum value of lambda as the data point to label next. Section 5.2 shows that lambda is a score of informativeness and large values of lambda are associated with very noisy samples. While I see wisdom in designing the algorithm to be noise seeking, would it be better to interpret lambda as probabilities and sample in proportion to lambda (favouring noisy samples in general) instead of choosing the sample with largest lambda? This would allow one to use importance weights in the CSL formulation and allow for optimizing an unbiased loss function.
4. While I understand the reason for the simplistic choice of epsilon ( epsilon(x) = c), can the authors suggest other possible choices? Would it be possible to design sensible heuristics or apply simple, unsupervised learning algorithms apriori to get good choice for epsilon and then use this choice in the algorithms? If yes, what would such heuristics or unsupervised algorithms look like?
5. The constant choice of epsilon and section 4.3 are at odds with each other. In Section 4.3, eqn 3, the authors take gradient w.r.t. epsilon. But, all experiments are with a constant epsilon. Furthermore,  it was not clear to me what the term \grad \theta/\grad epsilon that  appears in equation 3 captures? Could the authors shed some light here and interpret what this additional term do?
6. Are the networks retrained after addition of every single sample? If yes, are the old network values used to warm start training? A bit more clarity on the tricks used to train the network and compute optimizations would be useful.
limitations: Computational limitations of repeatedly training the network were not addressed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Batch active learning improves the sample qualities (avoid sample collapsing due to incremental improvement of the backbone model) and enables parallel oracles.  This paper tried to solve a critical issue for active learning. Unlike existing works, this paper proposed to solve the problem as a constrained learning problem and the algorithm solves the objective duality form.
strengths_and_weaknesses: Pros:

The motivation is clear and well motivating.
The presentation is good and easy to follow.
The method proposed is interesting.

Cons:

Did not provide asymptotically analysis and empirical analysis about the query cost. 

questions: Continue with the cons of the pros and cons, it will be stronger if the authors could provide an empirical analysis of the query costs. For example, what is the wall-clock time of querying N examples to provide to the oracles? Practitioners of this method should have a clear understanding what is the overhead and when should use this proposed method. 
limitations: N/A
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 proposes a new algorithm for batch-mode active learning, which is the problem of selecting and labeling a batch of unlabeled data points in order to yield the best possible improvement in a downstream model once trained. This algorithm uses Lagrangian duality in convex optimization to obtain an informativeness measure for every labeled data point; it then trains a model to predict the informativeness of unlabeled data and selects the most informative points from different clusters in the feature space. The algorithm demonstrates some improvement over classification and regression baselines.
strengths_and_weaknesses: 
**Strengths**

- Using Lagrangian dual variables as an informativeness measure is a novel idea. Moreover, the idea of estimating the dual variables for unlabeled data points presents an interesting approach to capture this informativeness.



**Weaknesses**

- The batch active learning problem (BAL) is written as selecting a set of points that minimizes the training set loss. However, this is incorrect and we typically want to minimize out-of-sample error/test loss (e.g., see Sener & Saverese ’18). Note that when we select what data points to train, we void any iid or distribution assumptions and thus, minimizing train loss does not guarantee low test loss. 
- The methodology is heavily motivated by an assumption of strong duality, which holds only for convex loss functions and hypothesis sets.
- The idea of using 3 models, e.g., a feature encoder, a classifier head, and an auxiliary estimator, has been explored in several works, e.g., VAAL (Sinha et al ’19), WAAL (Shui et al ’20). 


**References**

Sinha, Samarth, Sayna Ebrahimi, and Trevor Darrell. "Variational adversarial active learning." Proceedings of the IEEE/CVF International Conference on Computer Vision. 2019.

Shui, Changjian, et al. "Deep active learning: Unified and principled method for query and training." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

questions: - Does strong duality actually hold in your empirical results? If not, how large is the duality gap? Moreover, how would a lack of strong duality affect the Frechet subdifferential result in Theorem 3.2?
- How does this method scale to and perform in larger data sets, e.g., ImageNet?
- The mathematical comparison vs BADGE is interesting. A useful ablation would be to compare the correlations between BADGE and ALLY embeddings. This is important because the theory doesn’t necessarily hold with non-convex losses or hypothesis classes.
limitations: Limitations are briefly discussed. Societal impact isn't discussed.
review_title: null

Meta-review: metareview: In this paper, the authors formulate batch active learning as a constrained optimization problem, and develop a primal-dual approach to select a diverse set of unlabeled samples. The idea of using constrained optimization for active learning is novel and interesting, and the experimental results are also promising.
confidence: Certain
Decision: Accept