Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: In this paper, the authors develop a data selection scheme aimed to minimize a notion of Bayes excess risk for overparametrized linear models. The excess Bayes risk is the expected squared error between the prediction and the target. The authors note that solutions such as V-optimality exist for the underparametrized cases (linear regression), and offer extensions to ridge regression. After the development of a greedy schemes and a tentative extension to deep learning models, the authors show that their selection scheme can outperform random selection on MNIST with a specific model.

Active learning, both online and batch, is a well-studied problem with real-world applications. The paper does a fair job of developing the new technique but the addition seems incremental, and the algebra even though involved, is largely straightforward. The results are also unconvincing, and the one figure in the main body (Fig 2) only shows comparison with a weak (random selection) baseline. Furthermore, in the deep learning regime, 500-800 data points are somewhat unrealistic and do not cement the value of the method in real-world scenarios. Some other concerns include:

1. Unsubstantiated claims like “As such, the theory reported in the literature is often not applicable in the interpolative regime”. 

2. Unconvincing contributions description, “sometimes able to mitigate the double descent phenomena”, “sometimes able to find better design than random selection”.

3. The computational complexity of the method is prohibitive — O(m^2 n^2), where m is the dataset size.

4. Minor formatting issues: “revealing a three possible regimes”, “an interesting connections”, “approach that suggest differs”, “larger then”, “expected expected risk”, etc.

Overall, even though active learning is a highly relevant problem domain, in my opinion, the paper falls short in establishing itself as a strong competitor in the domain for reasons described previously. I would encourage the authors to resubmit with stronger justifications of the contribution and more convincing results.


review_title: Good development. Unconvincing results. Limited applications.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This authors analyzed the V-optimality criterion of the experimental design for the ridge regression setting, proposed a greedy algorithm to optimize the criterion, and connected with the infinite neural tangent kernel. 

The paper contains a number of interesting results, particularly in connecting the V-optimality criterion with the bias-variance trade-off in predictive modeling. However, the problem setting has some overly strong assumptions, such as prefixed design and iid errors, which can make the solutions trivial and not very useful in practice.

I don't recommend the paper to be accepted in its current form for the following reasons:

1. I think the main results of the paper in Section 3-5 concerns a conventional problem: Experimental design for the ridge regression. They do not provide a solution aligned with the main motivation, bridging experimental design and deep learning.
2. The theoretical analysis did not provide sufficient new insights. It actually confuses me that it introduces an additional parameter t on page 5, without exploring its relationship with the original regularization parameter lambda. 
3. The connection with deep active learning is not sufficiently explained. Also the evaluation task looks overly simple and uses a trivial baseline; I would expect at least a comparison with another active learning algorithm, for example, using the coreset approach.

Other specific concerns:

-  I find the expression "single shot active learning" confusing. Does it mean active learning with a prefixed (hence unsupervised) design?
- The last sentence of Sec 2, para 1 is incorrect. Actually, it contradicts Eq 1. 


In general, I think that the paper can be improved with a more focused contribution statement, and better connecting the results with the claimed contributions. The paper's relevance of deep active learning is unconvincing to me; probably the results are more suitable for a different conference.


review_title: Interesting but incomplete work

final_score: rating: 3: Clear rejection
review_content: This paper studies a straightforward generalization of v-optimality from linear regression to (kernel) ridge regression. A standard greedy algorithm is used to optimize the v-optimality criterion.  A simple experiment is conducted comparing the proposed method with random sampling on MNIST. 

I vote for rejection. This is a simple derivation of the v-optimality of ridge regression (or Bayesian linear regression). The novelty is somewhat limited. For a paper with such limited technical novelty, the empirical studies are too thin; only one experiment is presented, comparing with only a naive random baseline. 

The title “single shot active learning” seems a little inappropriate. As far as I understand, the word “active” in the context of active learning means the model “actively” query labels from some oracle in an __iterative__ fashion, so it already means “sequential” I think. Also, it's easy for people to confuse this with "one-shot learning".

typo: K=VV^t \in R^{n,n} should be {m,m}? 

review_title: limited technical novelity, weak experiments 

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposes an active learning (AL) strategy that is based on both of variance and bias of the linear model unlike the classical variance-based criteria. The paper claims that, for over-parameterized setting, incorporating the bias information is particularly important, and further, shows a kernelized extension and a greedy calculation strategy.

The paper focuses on an important problem of active learning, and is written clearly. The approach is reasonable, and the method would be easy to implement. However, technical significance would be somewhat weak. The derived bound of the expected error is quite simple, though it is ok but an important unknown constant is kept and no detailed discussion is provided for that constant. Further, the experimental result is not convincing to show the superiority of the proposed criterion compared with other existing approaches. Detailed comments are as follows.

In the first section, the authors mentioned about the recent 'double decent' phenomenon in over-parameterized model, and related the proposed approach with it. However, I couldn't find any particular technical procedures or discussions specific to the double decent phenomenon in the main text. Although the authors claimed that the proposed method can mitigate the double descent phenomena, this claim is not so particularly attractive currently because the classical OED also mitigates it in the illustration of Figure 1. If the proposed method can mitigate double decent that classical OED cannot, it would be attractive. 

The derivation of the proposed AL criterion is performed through the classical expected risk. The paper repeatedly claims importance of incorporating bias-dominated or mixed nature, unlike classical variance based approach. However, this idea (considering the bias effect in AL) itself is not novel though it is not clearly described. For example, 'Francis R. Bach, Active learning for misspecified generalized linear models, NeurIPS2007'.

A similar bound analysis to the paper is also shown in 'Gu, et al., Selective Labeling via Error Bound Minimization, NeurIPS2012'. Although this paper is for a manifold based semi-supervised learning, it includes the usual linear model estimation as a special case. They derived a bound for the estimation error of the parameter that reflects both of the bias and variance terms (from which expected error can be derived). Their approach is similar to (Yu et al 2006) that the authors cited, but an important point is that they showed the criterion of (Yu et al 2006) can be seen as a bound of 'both of' bias and variance terms though it is originally shown as a variance-based. This would be important past analysis closely related to the proposed method, and should have been mentioned.

Obviously, hyper-parameter t would be a key factor in the proposed criterion. However, no practical discussion on how to set t is provided. In my opinion, as far as this constant remains unknown, the proposed bound is not so particularly innovative. Further the regularization parameter lambda can be problematic because unlike the usual supervised learning scenario, it sometimes should be determined before observing y.

The experiment in Section 7 is not convincing because the authors only compared with random design, and it only shows results of the bias-dominated setting of the proposed method, though the mixed nature of the expected error was repeatedly emphasized in the paper. Comparison with other state-of-the-art AL or classical OED would be indispensable.
review_title: Reasonable analysis, but technical significance is somewhat weak

Meta-review: This paper gives a method of performing experimental design (one-round active learning) in overparameterized regression. Although the comparison with the coreset method baseline is a nice addition, the reviewers still have concerns in the following aspects:
- The novelty compared to the classical v-optimality design is limited
- The hyperparameter t is hard to choose in practice. This is important because each different hyperparameter setting would induce a different set of examples for label queries. 
- Computational complexity
- It is unclear exactly how the proposed method (or other experimental design method) can mitigate double descent 

We encourage the authors to take these into account in the revision. 

Decision: Reject