Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper studies the problem of boosting test performance of the last layer by crafting random perturbations that are orthogonal to the train feature matrix of the last layer (at least in the overparametrized case) thus leaving train performance unaffected. 

==========================================

Main Comment:
While the idea seemed interesting to me at first I find the paper overselling the results. The claim that LLboost improves performance is very strong when looking at the numbers: 0.2% improvement for cifar10 and 0.08% improvement for imagenet is marginal to say the least. This is even starker when looking at test performance as opposed to validation where for cifar the improvement is 0.03%-0.1%. The benefit for 2 class imagenet32 is more significant at the low sample regime but also fails to impress, and feels more like cherry picking rather than a serious experimental ablation. 

Minor Comments:
Figure 2 (should be a table environment, btw), shows that standard normal perturbations of the last layer reduce accuracies significantly. I'm wondering what would happen if we apply the same variance as the LLboost, as having different variances gives  a false impression of whether random perturbations help or hurt.

review_title: While having some theoretical justification the method fails to deliver in practice.

final_score: rating: 6: Marginally above acceptance threshold
review_content: ################################################################

Summary:

This paper provided an efficient algorithm (LLBoost) to boost the validation accuracy without spending too much time tuning hyperparameter. The algorithm is theoretically and empirically guaranteed.

################################################################

Reason for Score:

This paper provides an innovative way to improve generalization performance. My major concern is about experiment part. Since the algorithm use valid data to tune the parameter, it should another held-out test data to show the result. However, the author only did experiment on test-data for model ResNet-18, which is not sufficient to support the paper.

################################################################

pros:

1, This paper gave an efficient LLBoost algorithm to quickly improve the validation accuracy. The algorithm is theoretically guaranteed.

2, The paper clearly stated the intuition of the algorithm. The paper considered models that have fc layer as the last layer (most of the current models have this property), and transformed the problem into a linear regression problem.

3, A surprising point of the algorithm is that it does not impact the training loss.

################################################################

cons:
1, While the algorithm has a theoretically guarantee, the experiment part did not convince me. This is the major concern for the paper. The author tune the parameter using valid data and say valid accuracy is improved, which is not enough. It should another held-out test data to show the result for all the experiment. However, the author did an experiment on test-data only for ResNet-18, which is not sufficient to support the paper. Also, The author should put this test-data-ResNet-18 experiment in main part of the paper, not Appendix.

2, Section 3 (preliminaries and method) is not well-organized. I cannot see why the author put this two lemmas here.

(1) why "Lemma 1 implies that LLBoost does not affect training predictions since it only ever adds a component orthogonal to the span of the training feature matrix"? The lemma 1 seems having nothing to do with the LLBoost algorithm

(2) what is the purpose for lemma 2? The paper doesn't clearly state it.

I understand the reason after the author explained it in response. But I strongly suggest the author to explain it in paper for the final version.

3, Based on my understanding of this paper, the algorithm has to be applied to an existing pretrained model which is sufficient good. If we don't have a good pretrained model, does this algorithm provide a better (or comparable) result than the well-tuned model? I am just curious about it and hope the author to do some experiments in the future.




review_title: An innovative way to improve generalization performance

final_score: rating: 5: Marginally below acceptance threshold
review_content: ##########################################################################

Summary:

This paper proposes LLBoost that enables adjusting the last linear layer without impacting the training accuracy under the assumption that the last linear layer is in an over-parametrized situation. When the last layer is not over-parametrized, LLBoost first applies the low rank approximation to the training feature matrix through the SVD decomposition, which may affect the original training accuracy. The reason why LLBoost does not change the training accuracy is explained as follows: In an over-parametrized noiseless linear regression, a solution of a linear system $y = wX$ obtained by the gradient descent with an initial value of $w^{(0)}$ is given in a closed form of $\hat{w} = w^{(0)} (I - X(X^\top X)^\dagger X^\top) +  yX^\dagger$. Therefore, we can compute a solution of $y = wX$ by simply generating $w^{(0)}$ randomly and applying this formula. It is also experimentally verified that LLBoost can adjust the last linear layer without impacting the training accuracy (after appriximated with SVD when necessary). The authors also present theoretical results that sampling $w^{(0)}$ uniformly on the hyper-shpere of appropriate radius leads to a solution that is better than the minimum norm solution ($yX^\dagger$) with constant probability.

##########################################################################

Reasons for score: 

Overall, I vote for weak reject. It is interesting that LLBoost can adjust the last layer without impacting the training accuracy. And the theoretical results give a reason to sample $w^{(0)}$ uniformly on a hyper-sphere in Alg. 1. However, the condition that the last layer is over-parametrized is rarely satisfied in practical problems to which DNNs are applied. As discussed in Sec. 4, the low rank approximation can harm the accuracy in large problems like ImageNet.
The authors show in Figure 1/2/3,  that LLBoost can improve the validation accuracy without impacting the training accuracy. However, since Alg. 1 directly uses the validation labels (though it is denoted by 'test labels' in Alg. 1) to select $w_{best}$, it should be compared in terms of the 'hold-out' test accuracy to examine the usefulness of LLBoost.

 
##########################################################################

Pros: 

1. The authors propose a method to adjust the last linear layer of a DNN without impacting the training accuracy, under the assumption that the last layer is over-parametrized.

2. The authors give theoretical results that sampling $w^{(0)}$ on a hyper-sphere leads to a good solution with constant probability.

 
##########################################################################

Cons: 

1. In practical problems to which DNNs are applied, the over-parametrized assumption rarely holds. And the low rank approximation with SVD may worsen the accuracy.

2. Because Alg. 1 uses validation labels as its input to select the best solution, it is not enough to report the validation accuracy in experimental results like Figure 1/2/3. The accuracy of a 'hold-out' test set should also be reported.
 
##########################################################################

Other concerns:

- In line 3 of Alg. 1, why $P=I_{d \times d} - U I_{r \times r} U^\top$ is used, though it is explaned as $P=I -  X(X^\top X)^\dagger X^\top$ in Method Overview paragraph.

- Although the input of Alg. 1 includes 'test feature matrix' and 'test labels', they seem better denoted by 'validation feature matrix' and 'validation labels', respectively.

- In Figure 2, Train/Val. Acc. (Original) should be values without low rank appriximations (e.g. 95.193% for train acc. in ImageNet as denoted in Sec. 4). Also, it is not clear whether the val. acc. is computed with or without low rank appriximations.


review_title: Adjusting the last linear layer without changing the training accuracy is interesting, but the over-parametrized assumption rarely holds in practice

Meta-review: Though the method suggested in this paper is interesting, theoretically motivated, and resulted in some practical improvement, the reviewers ultimately had low scores. The reasons for this are:
1) The improvements obtained by this method were rather small, especially on the standard datasets (CIFAR, Imagenet).
2) In the main results presented in the paper, it seems that a proper validation/test split was not done (which seems quite important for demonstrating the validity of this method). In some of the results, presented in supplementary, such a split was done, but this seems to decrease the performance of the method even more.
3) The method requires that features in the last hidden layer approximately span a low dimensional manifold. This seems like a major limitation for the accuracy of this method, which becomes approximate in datasets where the number of datapoints is larger than the size of the last hidden layer (which is the common case).

Therefore, I suggest the authors try to improve all of the above issues and re-submit. For example, one simple way to address issue 3 and potentially improve the results (issue 1) is to use the same method on all the features in all the layers, instead of just the last layer. In other words, concatenate all the features and all the layers, and then add a linear layer from this concatenated feature vector directly to the network output, in a direction that is orthogonal to the data.

 
Decision: Reject