LLBoost: Last Layer Perturbation to Boost Pre-trained Neural Networks
Authors: Adityanarayanan Radhakrishnan
Neha Prasad
Caroline Uhler
Venue:  (2021)
Keywords: Pre-trained Neural Networks
Over-parameterization
Perturbations

Abstract:     While deep networks have produced state-of-the-art results in several domains from image classification to machine translation, hyper-parameter selection remains a significant computational bottleneck.  In order to produce the best possible model, practitioners often search across random seeds or use ensemble methods.  As models get larger, any method to improve neural network performance that involves re-training becomes intractable.  For example, computing the training accuracy of FixResNext-101 (829 million parameters) on ImageNet takes roughly 1~day when using 1~GPU.   
    In this work, we present LLBoost, a theoretically-grounded, computationally-efficient method to boost the validation accuracy of pre-trained over-parameterized models without impacting the original training accuracy.  LLBoost adjusts the last layer of a neural network by adding a term that is orthogonal to the training feature matrix, which is constructed by applying all layers but the last to the training data.  We provide an efficient implementation of LLBoost on the GPU and demonstrate that LLBoost, run using only 1 GPU, improves the test/validation accuracy of pre-trained models on CIFAR10, ImageNet32, and ImageNet.  In the over-parameterized linear regression setting, we prove that LLBoost reduces the generalization error of any interpolating solution with high probability without affecting training error.  

Under review as a conference paper at ICLR 2021
LLBOoST: LAST LAYER PERTURBATION TO BOOST PRE-TRAINED NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
While deep networks have produced state-of-the-art results in several domains from image classification to machine translation, hyper-parameter selection re- mains a significant computational bottleneck. In order to produce the best possible model, practitioners often search across random seeds or use ensemble methods. As models get larger, any method to improve neural network performance that involves re-training becomes intractable. For example, computing the training ac- curacy of FixResNext- 101 (829 million parameters) on ImageNet takes roughly day when using GPU.
In this work, we present LLBoost, theoretically-grounde computationally- efficient method to boost the validation accuracy pre-trained over- parameterized models without impacting the original training accuracy. LLBoost adjusts the last layer of a neural network by adding term that is orthogonal to the training feature matrix, which is constructed by applying all layers but the last the training data. We provide an efficient implementation using only 1 GPU, improves the test/validation
LLBoost on the GPU
and demonstrate that LLBoost, accuracy of pre-trained models on CIFARIO, ImageNet32, and ImageNet. In the over-parameterized linear regression setting, we prove that LLBoost reduces the generalization егror of any interpolating solution with high probability without affecting training error.
INTRODUCTION
Over the past decade, deep networks have produced number of state-of-the-arr results including surpassing human performance on the ImageNet classification task (4). However, tuning hyper- parameters to produce the best possible neural network in given application remains computa- tionally expensive task. State-of-the-ard results often involve selecting the best model using multiple random seeds (14) 27: [1. 28) ensembling (15), and training even single model can take sev- cral days even when using multiple GPUs Hence, is critical to identify computationally efficient approaches to improve the performance of pre- trained models without the need of re- re-training them.
In this work, we present LLBoost, a aheoreticall-grooudded, computationallyyeffiiii efficcient method to boost the validation accuracy of pre-trained, parametterre models without impacting the train- ing accuracy. Figure [ provides an overview of our method as well as the main results. As shown in Figure DA, our method adjusts the last fully-connected layer of neural network by selecting the best performing perturbation out of several orthogonal to the training feature matrix, which is constructed by applying all but the last layer to the training data. In Figure DB. we provide an ex- ample showing how our method applied to a model trained under a poorly chosen random seed can boost validation accuracy comparable that of model trained under a better seed. Lastly, Figure IC shows that our method can significantly improve the validation accuracy of pre-trained neural networks on large datasets using a fraction the training time.
The intuition for our method is based on characterizing the benefit of random initialization in over- parameterized linear regression. particular, consider a dataset (X,9) y) C Rdxx,, I with for which there exists w E glxd such that w X. In order to estimate w" from the data, we use gradient descent with learning rate r and initialization (0) to minimize the squared loss, i.c. to solve:
arg min wERd
1ly w

---

Under review as a conference paper at ICLR 2021
It is well-known (8) that gradient descent converges to the following closed-form solution:
Wy - ww( -1- X(XXXxX" +
where At is the pseudo-inverse of A (see Appendix A for proof). In this work, we prove that when < d, sampling w()) on hyper-sphere leads to we with lower generalization error than the minimum norm solution y-T with constant probability. Since the last layer of modern deep networks is usually linear, we apply this result from regression to the last layer of networks to arrive our method, L.LBoost.
We end the introduction with summary of our main contributions:
We present LLBoost, a computationally efficient method for boosting the validation accu- racy of pre-trained neural networks without affecting training accuracy. Additionally, provide an efficient implementation of L.Boost on the GPU.
2. We provide wealth of empirical evidence that LLBoost improves the validation accuracy of pre-trained neural networks and prove that it does not affect training accuracy for over- parameterized models.
3. We provide evidence that L.Boost yields computational advantage over random seed search for training neural networks.
4. In the wer-paaramtterized linear regression setting, we prove that LLBoost reduces the test error any interpolating solution with high probability without affecting training error.
2 RELATED WORK
Understanding the benefits of over-parametteriztion is recent topic of major interest in machine learning. 2 introduced the double descent curve showing that when increasing model capacity past the interpolation threshold, test error can drop second time. (20) noted that this phenomenon
Training Images
Pre-trained Network
Adjust This Layer
Dataset: 100 Ex. ImageNet32
Model: Pret-trained
ResNet-18
W
Outputs
Seed
Acc.
200
Transformed Features:X
25
Adjustment:
500
W' + x(Xx+)xx") 00.
Our Method on Seed 3
(E)
Dataset
Model
Train/Val. Acc. (Original)
Train/Val, Acc. (Ours)
Training Time
Correction Time
100 Ex. ImageNet32
ResNet-50
100%
83%
100% 89%
164.07 sec
0.12 sec
CIFAR10
ResNet-18
99.99% 05%
99.99%
1.35 hr
15.36 min
ImageNet
FiRResNext-100
94.92% / 86.26%
94.92% / 86.34%
day/epoch
7.59 hr
(C)
Figure 1: overview of L.Booot and a demonstration of benefits of our method in boosting pre-trained models. (A) A breakdown of LLBoost, which improves the performance of pre-trained neural networks by adjusting the layer of pre-trained network with term orthogonal to the training feature matrix, X. (B) LLBoost applied to model trained poorly-chosen seed boosts performance to that of a model trained on a well-chosen seed. (C) LLBoost provides a boost to the pre-trained models fraction of the computational cost of training.
2

---

Under review as a conference paper at ICLR 2021
had been noticed empirically several decades prior to the work of 22.. A line of recent work have provided a theoretical analysis of double descent in linear regression (13 22 3 21). In partic- ular, (33 3 analyzed the generalization error for the minimum norm solution in over parameterized linear models. These works proved that the minimum norm solution can yield lower generalization error in the wver-parameterized regime than in the under-parann padder-prameterized regime. Our theoretical anal- ysis primarily builds on that of (3), but we analyze the generalization error of mundom-iittializtionn interpolating solutions instead of the minimum-norm solution.
Various methods, including random seed search and ensembling, standardly used improve the performance of machine learning models through training. (4) recommends using 5-10 random seeds if computational power is available, and this is typically done in state-of-the-an models; for example, (14) considered random seeds for ResNet- 10 and
(12) considered at least random seeds on CIFARIO (17). (9) rigorously analyzed the impact of random seeds on model performance by considering between 50-400 random seeds for models of varying depth on MNIST (18). Figure from their work demonstrates that random seeds can affect the validation accuracy of models by up to a few percentage points on MNIST. Since this comes at a significant computational price, it critical to identify methods that can obtain such boosts without having to perform random seed search, which is the topic of this paper.
Another popular approach to improving neural network performance is ensembling, for example via bagging (6) boosting (T)). Recently, (15) presented approach to ensembling, which involved training single network and saving the model parameters each time training stopped at a local minimum. (15) built upon (30), which introduced horizontal and vertical voting to ensemble model across training epochs.
LLBoost can be used in combination with all the above approaches to further boost their perfor- mance, since it only adjusts the last layer of pre-trained model without requiring any training.
3 PRELIMINARIES AND METHOD
We now present the preliminaries relevant for formally introducing LLBoost. Since our method is derived from werrparameterized linear regression, we first describe this problem setting.
Noiseless Regression. Let (X, _g 11x= denote the training dataset where d is the number of dimensions and is the number of samples. In noiseless linear regression there exists w" E IR 1xd such that y w" X. In order estimate w* from the data, we use gradient descent minimize the squared loss. Formally, we solve:
_ lly xX12
1
arg min WERd
using gradient descent with learning rate 17. which proceeds according to the updates:
w (t) .7ly w X)X*.
The following well-known theorem g gives the solution, (oo)) for the objective given by gradient descent.
Theorem 1. Let (X,y) C. Rdxa x xx with X of rank r < d, let Amaz denote the largest eigenvalue of XX", and let A denote the pseudo-inverse of matrix Given initialization w(()) Rdd gradient descent used to solve:
arg min
2 11y 2xl1
with learning rate 7) < Am1 converges to (xc) (0) (I X(XX(XX))XX)) yxt.
When ()) = (zero initialization). (xx) is the minimum & norm solution for solving the linear system w.X- = y. The following property of (=))) used to demonstrate that LLBoost does not impact training error.
Lemma 1. Let (00) (0 (00(--XXXX xXXxxxxxXX + yxtt Then, (I (XxX(xx)) yxt.
3

---

Under review as a conference paper at ICLR 2021
The proof follows directly by substituting in X UEV? given by the singular value decomposition (SVD). Lemma Lemma[Timg iimplies that LLBoost does not affect training predictions since it only ever adds a component orthogonal to the span of the training feature matrix. We primarily focus on the noiscless regression setting, but we note that our theory directly extends to the Gaussian model from (3) and (7).
We now present result from random matrix theory, which is at the basis of our results. The proof of the following lemma relies on the rotation invariance of the multivariate Gaussian distribution and presented in Appendix B
Lemma 2. If X Rd with columns 200) NO, Iaxa). then the singular vectors of X are uni- formly distributed on the unit sphere Sa-1- In particular, if ~ (xx,), then | is uniformly distributed on the unit sphere Sa-1-
Method Overview. Given the above preliminaries, we present LLBoost in Algorithm 1 LLBoost takes the following inputs: (1) training feature matrix X; (2) the validation feature matrix X2; (3) the validation labels yrs (4) the last layer weights (5) the number of samples to consider T: and (6) the radius of the hyper-sphere to sample from 7,. LLBoost begins by constructing the projection matrix / = X x(X (X"X))XX" '"..". Then, LLBoost samples (O,, normalizes and adds the perturbation y2 P to w. LLBoost repeats this process and returns the perturbation that most improves the validation accuracy.
Remarks. As shown in Figure DA X and X, are constructed by applying all but the last layer of the neural network to the training/test data. X is not full rank (as is the case for neural networks that are not vee-paaratterizeed), we create low rank X by truncating the lower singular values of X. This correction only mildly affects training error as shown in Section 4 For classification settings, Yt should be converted 1-hot vectors. When the last layer has bias, append a 1 to w and append an extra row of I's to X and X,, In most of our experiments, we consider up T 100, 000 samples. When selecting 7, one can utilize binary search approach starting with y = Va and either doubling or halving depending on whether the validation accuracy increased or decreased respectively. However, as a simple heuristic one can start with y = vaa |||||| (as is recommended by Theorem B). Lastly, when the network has multiple outputs (as in multi- class problems), we let the entries of the weight matrix be i.i.d. standard normal variables and then normalize by the Frobenius norm.
simply
LLBoost does not impact training error/accuracy. Since the perturbations constructed by LL- Boost are always projected into the space orthogonal the training features X. Lemma [I iippies that LLBoost does not alter the training predictions. This is an important aspect of our algorithm since otherwise, L.ooostt could just overfit the test data.
Algorithm LLBoost (X, X,, Dt, T,7)
Input: X rank training feature matrix; X, := val. feature matrix; V1 val. labels; :- last layer weights; 7 = number of samples; 7 == radius hyper-sphere
Output: Whest adjusted last layer weights
1: Whest None
2: acCbest = 0; (1, d) w shoope; U,E,VT < SVD(X)
3: P *-laxa U
4: for t + 11 1 do
5:
N(O,Laxe)
6:
+ |²
7:
wr t -=P
8:
acc = GetV alAcc((A,,,), Yts w,)
9:
facc > acCbest then
10:
Wbest = wr: aCCbest = acc
end if
12:
end for
return Wbest
4

---

Under review as a conference paper at ICLR 2021
Dataset
Model
Train/Val. Acc. (Original)
Train/Val. Acc.
Acc. (Ours)
Train/Val. Acc. (Standard Normal)
100 Ex. ImageNet32
ResNet-18
100%/80%
100%/84%
88%/81%
2600 Ex. ImageNet32
ResNet-18 18*
99.96%/95%
99.96%/97%
99.96%/95%
100 Ex. ImageNet32
ResNet-34 34
100%/85%
100%/87%
74%//82%
2600 Ex. ImageNet32
ResNet-34"
99.77%/95%
99.77%/98%
99.65%/97%
100 Ex. ImageNet32
ResNet-50
100%//83%
100%/89%
84%/833%
200 Ex. ImageNet32
ResNet-50
100%//8%%
100%/93%
79.5%/87%%
500 Ex. ImageNet32
ResNet-50
99.6%/91%
39.6%/93%
93.2%/92%%
800 Ex. ImageNet32
ResNet-50
100%/949%
100%/98%
97.75%/96%
ImageNet32
ResNet-50
100%/93%
100%/97%
98. 98.5%
Ex. ImageNet32
ResNet:50
99.85%/95%
99.85%/97%
98. 98.8%/97%%
2600 Ex. ImageNet32
ResNet-50*
99.88%
99. 89..8%%999%
99.698 99.6%%/988
CIFAR10
ResNet-18"
99.99%
99. 199.99%/95 25%.
42.53%/36.4465
ImageNet
FixResNext-100
94.924%./86. 26%
94.924%
.57%//56%%
Figure 2: LLBoost consistently improves the performance of pre-trained neural networks across
variety of experiments on ImageNet32, CIFARIO, 10, and ImageNet without impacting training accu- racy. The last column indicates that applying a standard perturbation instead of LLBoost to the last layer of a neural network can significantly impact training and validation accuracy. *'s indicate that the training feature matrix X was full rank, and thus, we used low rank approximation of X for LLBoost. See Appendix for description of how the rank was chosen, and an analysis of how low rank approximations affect train/validation accuracy.
GPU Implementation. We can easily remove the loop in Algorithm I by using the GPU since the dominating computations are vector-matrix products. A full implementation is provided using PyTorch (25) and NumPy (23 29) the footnote below In practice, computing the validation accuracy for each sample of w, is the limiting factor in LLBoost. For large datasets, the functions used compute the SVD and the projection matrix need be selected carefully. Note that with respect to SVD, the reduced SVD is sufficient for our algorithm. While for the ImageNet training features from FixResNext- 101 the full SVD would require constructing a matrix with roughly 10 entries, the reduced SVD only requires 10t entries.
4 EMPIRICAL RESULTS
In Figure we provide empirical evidence that LLBoost consistently improves the validation curacy of State-of-the-art models on CIFARIO, ImageNet32 (24), and ImageNet. For models fine- tuned on ImageNet32 or CIFARIO, we provide all training details in Appendix C Importantly, as proven by Lemma] we note that the training accuracy remains unchanged after applying LLBoost.
Handling under-paraamterrized models. If n denotes the number of training samples, the size of training feature matrix is 512 x n for ResNets- and 34 while it is 2048 x n for ResNet-50 and Nexte (28). Hence ResNet-18 18 and 34 are over-parameterized on the training set when < 512, while ResNet-50 and FixResNext- training feature matrix, X, has full rank, we truncate the lower singular values of X in order to be able to search the space orthogonal to X. Formally, if X UEVT, we construct X UEVT where we zero out the bottom entries of Σ. When X has rank we refer to it as the rank approximation of X.
are over- wver-parameterized for n < 2048. When the
Our experiments are summarized as follows:
1. On ImageNet32, fine-tune pre-trained ResNets of varying depth subsets of varying size of two classes (Kit-Fox vs. English-Setter). There are a total of 2600 examples (1300 of each class). We then apply LLBoost to these pre-trained models and use rank 12
4open. sci eece///bblaal0000
By fine-tuning, mean training pre-trained model on new dataset. This is discussed further in the transfer learning tutorials provided by PyTorch 2
5

---

Under review as a conference paper at ICLR 2021
approximation for the feature matrix when necessary. This set of experiments demonstrates that LLBoost improves transfer learned models on small datasets.
2. On CIFARIO, we fine-tune a pre-trained ResNet- We then apply LLBoost to the pre- trained network. In this setting, there are 50, 000 training examples and so the feature matrix full rank. To make the model over-parameterized, we instead use the rank 212 approximation. Remarkably, this approximation does not impact the original training curacy.
3. On ImageNet, we apply LLBoost to pre-trained FixResNext-101 ImageNet contains 1, 281, 167 training examples and the feature matrix is again full rank. In this case, use the rank 1000 approximation, and the original training aceuracy decreases from 193% to 94.924% when applying the original weights to the rank 1000 approximation.
In all settings, LLBoost improves validation accuracy. In addition, as proven by Lemma L there is no impact on training accuracy in the wver-parametrrized setting. In under-parameterized settings ImageNet, our experiments indicate only minor decrease in training
such as Fix accuracy when using a low rank approximation to X. In Appendix we additionally present: (1) the difference in fy/Frobenius norm between the LLBoost weights and the original weights; (2) the run-time of LLBoost; (3) the choice of y used in the experiments. In Appendix F we discuss how the rank was chosen when approximating full rank feature matrices, and provide an analysis of how low rank approximations affect validvvaiittion accuracy.
Remarks. In the last column of Figure 2 we also provide the performance of perturbing the last layer of neural network with usual distribution such as the standard normal. Note that such standard normal perturbation significantly impacts the original training accuracy; in fact for larger datasets such as ImageNet, the training and validation accuracies drop below 1%. Hence, without the projection operator, perturbations to the last layer can be devastating to network performance. In Appendix[E] we also demonstrate that when including the projection operator but using standard nor- mal initialization (instead of uniform on the hyper-sphere as done in L.Booott can similarly reduce validation accuracy. While we have thus far concentrated on validation accuracy, in Appendix we show that in the setting of training, validation, and test splits, LLBoost not only improves validation accuracy, but also improves test accuracy without impacting training accuracy.
Improvement over Random Seed Search. We demonstrate in Figure 3 that LLBoost provides a significant computational advantage over random seed search. In particular, in Figure 3 we com- pare the performance of fine-tuning pre-trained models on ImageNet32 and CIFARIO using random seeds. Naturally, LLBoost can be applied to boost the performance of all these models. Moreover, Figure Jillustrates that LLBoost can boost the performance of a model trained using poor random seed to that of model trained using a well-selected seed. Since LLBoost only takes a fraction of the training time, these experiments identify LLBoost as a computationally efficient alternative to random seed search.
5 THEORETICAL RESULTS
We now present our derivation and analysis of L.BBoost for over- wee-paaraeterrized noiseless linear regression. In the noiseless regression setting, we assume that the labels y E 1 are generated by the product of w" E R and data Rddxn Let 6, (0) (I X x(X"x))x") + yxXt and @ = y denote interpolating solutions for the linear system w.X = y given by gradient descent from initialization (0) and O respectively. In this section we establish the following:
1. Generalization bounds on Wy--
2. There exist infinitely many (0) such that || wI [|0-w"ll: many random initializations that out-perform the minimum norm solution. In particular, show that even if ()) w²ll || is large, || w'1l can be arbitrary close to 0.
|l i.c. there exist infinitely
3. Sampling (0) uniformly on the hyper-sphere of appropriate radius leads to wp out- performing the minimum norm solution with constant probability.
The following proposition (with proof in Appendix H compares the generalization enror of the random initialization solution, Wi and the minimum norm solution, w.

---

Under review as a conference paper at ICLR 2021
Seed
Val Acc.
Seed
Val Acc.
Seed
Val Acc.
200
94%
200
95%
200
95.05%
94%
3
95%
3
94.98%
70
97%
70
95%
70
95.06%
94%
25
97%
25
94%
95%
500
500
95.1%
LLBoost
98%
LLBoost Seed 3
97%
LLBoost Seed 3
95.18%
Seed 200
(A) 800 Ex. ImageNet32 Classes 1, ResNet-50
(B) 2000 Ex. ImageNet32 Classes 1,
(C) CIFAR10 ResNet-18
ResNet-50
Figure 3: LLBoost provides a computational advantage over random seed search. While LLBoost only improves the performance of every pre-trained model above, our method boosts the per- formance of a model trained using a poor random seed to at least that of a model trained using well-selected seed at fraction of the computational cost.
Proposition Let X -UEV denote the SVD of X and let Σ = =I IIE Then,
(a) | w"ll || = U--
(b) 1r w0|l = (w - w" JUE UT S 11 - w*ll-
By using Proposition and extending the proof technique of (3) we establish the following gener- alization bounds for the solution starting from initialization w(())
Theorem 2. Assuming data w. (1) _O, Taxa) for [n]. then
(1) Ex,x (1v wx) ) Ex Ex w" w1 || 1|2
7)
(2) E,, x w = Ex w [1 = [w w' (1-1)
71
The proof is presented Appendix ! From Theorem 2 the out sample performance of the solu- tion initialized (") is governed by the distance between (0)) and w", which matches intuition. While this result is in expectation over the data drawn from an isotropic Gaussian, we now prove the remarkable fact that even ((()) - w"ll c1 is large, | w"ll can be any value between and e₁.
Proposition 2. Let r denote the rank of the data matrix X and let ei 2 2 0. Then there exists (0) such that (0) w" ei and 1 w² C2.
The full proof is presented in Appendix J Importantly, Proposition Proposition&proviidee provides the following intuition around the benefit of random initialization in over- per-parameteriieed models. When X has rank for small, the space orthogonal to X is large with dimension d-r. There is thus a priori no reason for the true w² to lie in the span of the training data. Hence, by sampling (()) to add a term orthogonal to X we can expect obtain a boost in performance over the minimum norm solution. The following proposition and theorem present sampling method for (0), which provably provides boost over the minimum norm solution with constant probability.
Proposition 3. Let Va represent the uniform distribution on the sphere. Assume that the data J, 3 (2) (0, Idxa) for E [r]] and that w0 -Ma Then,
r (
/ sin 0d0,
PP.. to) 1(v x)x) Er.x wz
(2)
where ò cos
2 and r(x) denotes the Gamma function, which satisfies [(x) (x
1)T(x- 1) with r(1) and ((}) VT.

---

Under review as a conference paper at ICLR 2021
The proof is given in Appendix K The benefit of Proposition
is is that can lower bound the right hand side of Equation ( by a constant greater than O. This is computed explicitly in Theorem
Theorem 3. Let zu Ex,xi(y [ Ex,x((y w,z)²1 denote the difference in expected generalization error between the minimum ---norm solution and the random initialization solution. wo Ua(?), 2 and 21 then
7+
COS (n) V - ()(v 2(d - 4) 1)s (VI- VI-MM x2)
S PP mn()) (Zuto) 2 (1
2/T((= - 2)
In particular, if ||1""| = 1, 7
and then 1 and 2/a
vd
1
lim P Pot d=000
1
11 d
1 $
2T 2m
Remarks. Theorem is at the core of LLBoost; implies that the probability of w. having lower expected generalization error than @ is constant. Note that based on Equation (3) this constant is lower bounded by roughly .3 (meaning
get 30% chance of improvement). Importantly,
Theorem 3 can be trivially extended to demonstrate that LLBoost can reduce the generalization error of any interpolating solution with constant probability (provided that the generalization error is not already 0). We also remark that the lower bound in Equation (3) is nearly tight: in practice, this constant is roughly .31. Lastly, note that all of the above theory holds also for the regression setting with multiple outputs by replacing the usual & norm with the Frobenius norm.
While the full proof of Theorem 3 is presented in Appendix L we here provide a sketch. The proof provides an approximation for the integral on the right hand side of Equation (2) by using Gautschi's 's Inequality (I] and integration by parts. Note that while may seem at first that á should be uniformly distributed when w(() is uniformly distributed on the sphere (and thus the probability should go 1/2 as d goes to oo), it is in fact not true that & is uniformly distributed when (0 is uniformly distributed, which is why a more precise argument is required.
6 DISCUSSION
In this work, we presented LLBoost, poooreticallyggronndee computationally-efiitiii method to improve the validation accuracy pre-trained neural networks without impacting training accuracy. Through a variety of experiments on ImageNet32, CIFAR10, and ImageNet, we demonstrated that our method is practically relevant and can be used to boost the performance of state-of-the-at pre- trained models. A standard method to improve the performance of neural networks is random seed search. We showed that LLBoost provides a significant computational advantage over random seed search and even boost the performance of a model trained on poorly selected seed to that of a model trained on a well-selected seed. Thus, LLBoost is a computationally efficient alternative random seed search. Lastly, we provided theoretical footing for our method by showing that LLBoost provably reduces the test error of any interpolating solution in over over-parameterized linear regression. An interesting direction of future work is to identify alternate sampling schemes for LLBoost (other than uniform on the hyper-sphere) that provably yield a greater increase in validation accuracy without decreasing training accuracy.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
[1] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
[2] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical biri-variance trade-off. Proceedings of the National Academy of Sciences, 156632)11844-1158
2019.
[3] Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. 1rX10:1903.0757,, 2019. 2019.
[4] Yoshua Bengio. Practical recommendations for gradient-based training of deep architectures. CoRR, abbs/120655333 2012.
[5] K Bibas, Y. Fogel, and M. Feder. new look at an old problem: A universal learning approach to linear regression. arXiv preprint UrXiv:/905.044 2019.
[6] Leo Breiman. Bagging predictors. Machine Learning. 24(2):123-44) 1996.
[7] Leo Breiman and David Freedman. How many variables should be entered in regression equation? Journal of the American Statistical Association, 78(381):131-16, 1983.
[8] Heinz Werner Engl, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems, volume 375. Springer Science Business Media, 1996.
[9] Dumitru Erhan, Yoshua Bengio, Aaron Courville, Pierre-Antoine Manzagol, Pascal Vincent, and Samy Bengio. Why Does Unsupervised Pre-training Help Deep Learning? Journal of Machine Learning Research (JMLR), 11:625-660, 2010.
[10] Yoav Freund and Robert Schapire. A short introduction to boosting. Journal of Japanese Society for Artificial Intelligence, 14(5):771-780, 1999.
[11] Walter Gautschi. Some Elementary Inequalities Relating to the Gamma and Incomplete Gamma Function. Journal of Mathematics and Physics, 38(1-4):77-88 1959.
[12] Seyyed Hossein Hasanpour, Mohammad Rouhani, Mohsen Fayyaz, and Mohammad Sabokrou. Lets keep it simple, using simple architectures to outperform deeper and more complex architectures. arXiv preprint (tth:::6000003.77. 2016.
[13] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint 1rXiv:/903.08355 2019.
[14] Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Computer Vision and Pattern Recognition (CVPR), 2016
[15] Gao Huang, Yixuan Li, Geoff Pleiss, Zhuang Liu, John E. Hopcroft, and Kilian Q. Wein- berger. Snapshot ensembles: Train 1, get m for free. In International Conference on Learning Representations (ICLR), 2017.
[16] Like Hui and Mikhail Belkin. Evaluation of Neural Architectures Trained with Square Loss vs Cross-Entrope in Classification Tasks. arXiv preprint arXiv:2006.07322. 2020.
[17] Alex Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, University of Toronto, 2009.
[18] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 36(11))2278-23) 1998.
[19] Shengquiao Li. Concise formulas for the area and volume of hyperspherical cap. Asian Journal Mathematics and Statistics, 4(1):66-70, 2011.
[20] Marco Loog, Alexander Mey, Jesse H. Krijthe, and David M. J. Tax. A brief prehistory of double descent. Proceedings of the National Academy of Sciences, 1 117220)::0255-166 2020.

---

Under review as a conference paper at ICLR 2021
[21] Partha P. Mitra. Understanding overfitting peaks in generalization error: Analytical risk curves for le and 4 penalized interpolation. arXiv preprint 19X1::19066.336,,,20000
[22] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation of noisy data in regression. IEEE Journal Selected Areas Information Theory, 1(1):67-83, 2020.
[23] Travis E Oliphant. A guide to NumPy, volume 1. Trelgol Publishing USA, 2006.
[24] Aaron van den Oord, Nal Kalchbrenner, and Koray Kavukcuglu. Pixel recurrent neural net- works. International Conference on Machine Learning (ICML), 2016.
[25] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[26] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Fei-Fei Li. ImageNet large scale visual recognition challenge. International Journal of Computer Vision, 2015.
[27] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Conference on Computer Vision and Pattern Recognition, 2015.
[28] Hugo Touvron, Andrea Vedaldi, Matthijs Douze, and Hervé Jégou. Fixing the train-test reso- lution discrepancy. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[29] Stefan Van Der Walt, S Chris Colbert, and Gael Varoquaux. The numpy array: structure for efficient numerical computation. Computing in Science & Engineering. 13(2):22, 2011.
[30] Jingjing Xie, Bing Xu, and Zhang Chuang. Horizontal and vertical ensemble with deep repre- sentation for classification. ICML Workshop Representation Learning, 2013.
10

---

Under review as a conference paper at ICLR 2021
APPENDIX
GRADIENT DESCENT IN LINEAR REGRESSION
Theorem Let (X,9) C Rdxn Rn with of runk r and X UEVT its singular value
decomposition (SVD). Given an initialization w()) O, gradient descent used to solve:
arg min Gly w WER
with learning rate n XXT=(XXT) converges to:
0
w (x)) =yVEUU where Σ
0
0pxd Pxd-r
Og-rxr
0g Ox-xdd
Proof. Let = XXT and S' = yX Then, w(+1) (I + n15". Now we directly solve the recurrence relation; namely,
w = m n
m75)' + (1 n75) + I).
Let X = UEVT denote the singular value decomposition X where (o.,.... or are the non- zero entries of Σ and is the rank of X. Then, S US"UT and S' yVEU Thus, can simplify the recurrence relation:
w n 11) + (I - -) + (I - -m-) + TYU".
Since (I n (I - + (I nT) + I is geometric series, for 17 07
have:
w U
1-(1-nof)
0
no
1- (1 yo
0
0
Opxd-r
Σ+
no?
1- 11(1-10 (1
0
ga?
0 Od-rxr
-xd--
Now substituting in S' UVEUT gives us:
w
yV LT.
1- (
d1
1- (=(1-
Opxd-r
D
d2
dr
O4--xr
Od-rxd-r
Lastly, we can take the limit as + co to conclude that
(oc) lim (t
VVEUU. where Et
0
0, Oxxd_r
de
0 Og-rxr
0 Od-rxd-r
Note that the proof above be easily extended to the setting of random initialization ())
11

---

Under review as a conference paper at ICLR 2021
DISTRIBUTION OF SINGULAR VECTORS OF RANDOM MATRIX
Proof. We use the rotational invariance of the multivariate isotropic Gaussian. If A is an orthonor- mal matrix, then we have:
-
(Az)"
Now, suppose A, B are both orthonormal matrices, then have:
AXB" = (A @ B)
where X2 Rdd is the row-major vectorization of X and @ is the Kronecker product. Now, since A, B are orthonormal, we have that A & B is orthonormal. Hence, AXB" must have the same distribution X, and thus the singular vectors of AXB" must have the same distribution those of X. Since singular vectors lie on Sa-1 and since the distribution is rotation invariant, we conclude that the singular vectors uniformly distributed S4-1.
C TRAINING DETAILS
We now describe the training methodology used to train pre-trained models ImageNet32 and CIFARIO. The optimizer, initialization, learning rate, and seeds used to train the ResNets in Figure and presented in Figure 4 Note that all of our models were trained with mean squared error, as discussed in (16). We trained models on ImageNet32 for 150 epochs and on CIFAR1O for 50 epochs. We then saved the model with the highest validation accuracy.
Dataset
Optimizer, Learning
Initialization
Seed
Classes 1 and 2, ImageNet32
Adam, 1e-4
Default Pytorch Initialization
200
CIFAR10
Adam, 1e-4
Default Pytorch Initialization
200
Figure 4: An overview of the optimizer, learning rate, initialization, and seeds used fine-tune pre-trained models on ImageNet32 and CIFAR1O.
For all experiments, we used the PyTorch deep learning library (25). We trained our models on a shared server with Titan Xp and 2 GeForee GTX 1080 Ti's. We only used I GPU time for training neural networks and applying LLBoost.
D ADDITIONAL EXPERIMENTAL DETAILS
In this section, we provide the following additional details regarding the experiments in Figure and 3
1. The number of components used in the low-rank approximations for full rank training feature matrix (5)
2. The size of the perturbation produced by LLBoost and the values of y used for the models in Figure 2 (Figure
3. A comparison between training time and the time taken for LLBoost improve the models in Figure (Figure ?
E PERFORMANCE PROJECTED STANDARD NORMAL PERTURBATIONS
In Figure 2 we demonstrated that perturbing the last layer without projecting to the space orthogonal the feature matrix provided a drastic decrease the training and validation accuracy. In Figure 8 we illustrate the impact of using perturbation that is randomly sampled from a standard normal and then projected to the space orthogonal to the feature matrix. Again, we see that the validation accuracies can drop significantly for larger datasets in this case. Note that including the projection operator preserves the training accuracy in all cases, as is guarantced by Lemma
F Low RANK APPROXIMATIONS FOR FEATURE MATRICES
As discussed in Section when the feature matrix, X, is full rank, we needed to use a low-rank approximation such that the space orthogonal to X. In this section, discuss method of
12

---

Under review as a conference paper at ICLR 2021
Dataset
Model
Number of Components
2600 ImageNet-32
ResNet-18
2600 Ex. Imagenet-32
ResNet:34
12
2600 Ex. Imagenet-32
ResNet:50
1548
CIFAR10
ResNet-18
212
ImageNet
FixResNext-100
1000
Figure 5: The rank of the approximation used for the training feature matrix, X, when X was full rank.
Dataset
Model
Train/Val, Acc. (Original)
Train/Val. Acc. (Ours)
Perturbation
100 Ex. ImageNet32
ResNet-18
0.226
100%/80%
100%/84%
0.21
2600 Ex. ImageNet32
ResNet-18*
11.314
99.96%//55%
99.96%/97%
11.210
100 Ex. ImageNet32
ResNet-34
2.263
100%/85%
100%/87%
2.263
2600 Ex. ImageNet32
ResNet-34*
4.525
99.77%/95%
99.77%
4,474
100
ImageNet32
ResNet:50
0.453
100%/83%%
100%/89%
0.440
Im.memegee2222
ResNet-50
100%/87%
100%/93%%
0.431
ImageNet32
39.6%
99. 98.6%%/93%
800 Ex. ImageNet32
ResNet-50
9.051
100%/94%%
100%//88%
7.215
1000 Ex. ImageNet32
ResNet-50
33.941
100%/93%
100%//9%%
23.784
2000 Ex. ImageNet32
ResNet-50
45.255
99.85%
19.88%
6.338
2600 Ex. ImageNet32
ResNet-50*
36.204
99.880 99..88%/99%
17.364
ImageNet
MaResNNet-1055
10
94.924%/86 26%
94.924%%/86 34%%
0.4428
CIFARIO
ResNet-18*
2.0
99.99%
99.99% 25%
1.724
Figure 6: An extended version of Figure that includes the choice of considered and the size of the perturbation (in Frobenius norm) produced by LLBoost. *'s indicate the use of low-rank approximations for full rank training feature matrices.
choosing the number of components of the SVD to keep for producing the low-rank approximation for X. We then present how the number of components selected affects the performance of LLBoost.
In Figure we visualize the normalized singular values of the feature matrix for models from Figure In Figure AA we do use a low-rank approximation than the number of features. In Figure BB, the feature matrices are full rank, and so we use a low- rank approximation for the feature matrix with the number of components selected shown red. In particular, we chose number of components that is well past the elbow in the curve so that there was not a significant drop training accuracy.
the size of the dataset is already smaller
In Figure I0 we demonstrate how the number of components selected for the low-rank approx- imation affects the validation accuracy of LLBoost. In particular, observe that using lower rank approximation generally increases the improvement provided by LLBoost. This matches the intuition provided by Proposition when the space orthogonal to the training feature matrix, X, is large, there no reason to believe that the best linear solution lies in the span of X. Hence, sampling the space orthogonal to X yields an improvement. We note that since only few singular values of X are large, there is no impact to the training accuracy when using low-rank approximation for X (shown in the second column of the tables Figure 10).
G LLBOOST APPLIED TRAIN, VALIDATION, TEST SPLITS
In Figure 2 and Figure g we demonstrated that LLBoost improves the validation accuracy of pre- trained models without impacting the training accuracy. To ensure that L.LBoost is not overfitting
13

---

Under review as a conference paper at ICLR 2021
Dataset
Model
Training Time
Correction Time (s)
100 Ex. ImageNet32
ResNet-18
77.753 sec
0.116
2600 Ex. ImageNet32
ResNet-18"
1020.413
0.112 sec
100 ImageNet32
ResNet-34
122.85 sec
0.111 sec
2600 Ex. ImageNet32
ResNet-34"
1397.989
0.098
100 ImageNet32
ResNet-50
164.07 sec
0.113 sec
200 ImageNet32
ResNet-50
190.473 sec
0.111
500 ImageNet32
ResNet-50
407.454 sec
0.105
800 ImageNet32
ResNet-50
628.997 sec
0.137
1000 Ex. ImageNet32
ResNet-50
1054.061
0.087
2000 Ex. ImageNet32
ResNet-50
1996.991
0.129
2600 Ex. ImageNet32
ResNet:50*
2488.621
0.11
ImageNet
FixResNext-101*
day/epoch
7.59
CIFAR10
ResNet-18*
1.35 hr
15.36 min
Figure 7: A comparison between the training time and LLBoost correction time for models from Figure 2 For the ImageNet32 models, the third column represents the time to compute the valida- tion accuracy for 100, 000 samples from LLBoost. For CIFARIO and ImageNet, the time addition- ally includes the cost of computing the perturbation for LLBoost. *'s indicate the use of low-rank approximations for full rank training feature matrices.
Dataset
Model
Train/Val, Acc. (Original)
Train/Val. Acc. (Standard Normal @ Perp)
100 Ex. ImagaNet32
ResNet-18
100%/80%
100%/76%
2600 ImageNet32
ResNet-18*
99.96%//55%
99.96%/96%%
100 Ex. ImageNet32
ResNet-34
100%/85%
100%/75%
2600 Ex. ImageNet32
ResNet-34*
99.77%
99.77%/88%
100 Ex. ImageNet32
ResNet:50
100%//83%
100%/76%%
ImageNet32
ResNet-50
100%/87%
100%
500 Ex. ImageNet32
ResNet-50
99.6%/911%
99.6%
800 Ex. ImageNet32
ResNet-50
100%/949%
100%/87%
1000 Ex. ImageNet32
ResNet-50
100%//33%
100%/96%
2000
ImageNet32
ResNet:50
99.85%
99.85%
2600 ImageNet32
ResNet-50*
99.88%/95%
99.88%/99%
ImageNet
FiRReNextt1011
94.924%/88..25
11.924/18.5449
CIFAR10
ResNet-18*
99.99%
99.99%
Figure 8: demonstration that using samples from standard normal projected onto the space orthogonal to the training data leads to a decrease in validation accuracy but has no impact on training accuracy. *'s indicate the use of low-rank approximations for full rank training feature matrices.
the validation set, additionally split the validation data into validation and data and check that LLBoost improves validation and test accuracy without impacting training accuracy
For Iea3eNet32, the validation size is only 100 examples, and split the training and re-train.
14

---

Under review as a conference paper at ICLR 2021
(A)
ResNet-18, 100Ex. ImageNet32
ResNet-50, 100 ImageNe132
ResNet-50, 2000 Ex ImageNet32
140
1.00 CMO
Magritude
Megnitude
Megniuude
Singular Index
Singulaar Value
Singular Value
ResNel1a,
FixResNext- ImageNet
(B)
2000
200
Magnituds
200
Magnitude
2018
2008
Singular Value Index
Singular Value Index
Figure 9: Visualizations of the singular values of training feature matrices for models from 2 (A) The singular values of the training feature matrices for small datasets. (B) The singular values of full rank training feature matrices from large datasets. The red vertical line indicates the size of the approximation used for Figure
(Aoproe)
(Ongroi)
Redbwe-0
Rediee-18
Origial Festure Matra
Orggnl
93.03%
Aparox
Appros
03.22%
Aparce
Appros.
Rank 1909 Apaine
04 68%
06.88%
Rank Anprix
98 995
96.6%
1998 Aparox
59.08%
Asprox
90% 23.99%
95.19%
Kank 2023 Apaiix
99 80%
$9.885
99%
Rank Approx
28 23.99%
$1.13%
Figure 10: The impact of using approximations of varying rank for full rank training feature ma- trices. The first row provides the training accuracy and validation of the original model. The first column is the training accuracy of the model on the original dataset, the second column is the training accuracy on the training data reconstructed from the low-rank approximation, and the third column is the validation accuracy. We see that the validation accuracy generally increases when lowering the rank of the approximation. Since only few singular values of the training feature matrix are large, there is no impact to the training accuracy when using low-rank approximation for X.
present examples of how LLBoost (which selects the perturbation that improves validation accuracy) improves both validation and test accuracy without impacting training accuracy.
In Figures I and 12
15

---

Under review as a conference paper at ICLR 2021
Dataset
Model
Train/Val/Testt.c.. (Origina))
Train/Val./esttcc (Ours)
2600 Ex. ImageNet32 (80/20 split)
ResNet-18
99.9%/91..%%/93%%
99.9%/92.5%%/94%%
CIFAR10 (20/80 split)
ResNet-18
(999%/95.2%/94.99
99.99%/95.33/994955
CIFAR10 (50/50 split)
ResNet-18
1t.99%955.99/44.4.
99.99% 8/44.844%
CIFAR10 (90/10 split)
ResNet-18
99.99%
99.99% %/994.00%
Figure 11: Using LLBoost improve validation accuracy also leads to an improvement in test accuracy (i.e. LLBoost does not overfit the validation set). We split the original validation set of CIFARIO into validation and test set according to the splits indicated in parentheses. As the validation set of ImageNet32 for 2 classes only has 100 images, we perform 80/20 train/validation split the training set, use the 100 validation images as test data, and re-train our models on the smaller training set.
Dataset
Model
Train/Val./eesttcc (Original)
Train/Val/Test Acc. (Ours)
200 Dogs/Cats CIFAR10
ResNet-18 18
100%/78%//7.50%%
100%/79%/75.53%
1000 Dogs/Cats
ResNet-18 18
100%/84.5%//8.
100%/86%//86.54%
CIFAR10
2000 Dogs/Cats CIFAR10
ResNet-18
100%%/89.15%/89.442
Using LLBoost to improve validation accuracy also leads to improvement in test accuracy (i.e. LLBoost does not overfit the validation set). In our experiments, we use the same number of examples for training and validation and use the entirety of the remaining examples for testing. For example, in row 1, we use 200 examples for training, 200 for validation and 11600 for testing.
Figure 12:
PROOF OF PROPOSTION
Proof. We first consider u w
-VVIU w"
X'V w² (since = w" X)
w' U n ( + U Uz))
-'UE-- UT w (US-UZ + C
=-"
Thus, we have shown (1), Now for (2), we have:
Cr w' w UUE-T + T w" w -UUS--t-wUS--- (w w" -')UUUUT
W--E
Hence, (2) follows from (1).
I PROOF OF THEOREM 2
Proof. The proof follows from Lemma 1 Since the columns are drawn from WN Laxa), Lemma 2 implies that the columns of U are drawn from the uniform distribution on the sphere in Rdd. Hence we have that:
d Σ
EX Ex
Σ
Ex [
d'
This implies (1) since:
Ex -01l==0112-- "U'
=1|
1001((11))
Similarly, get (2), which completes the proof.
16

---

Under review as a conference paper at ICLR 2021
J PROOF OF PROPOSITION 2
Proof. Let a = w( - w". We need to find such that:
(1) |1 UE- E ua,us))
(2) a"a a = c7-
To do this, we instead first let a' = cia and show that there exists a solution to:
Ka', 21)² c3 cf
(1) la 11-
11++
(2) _h d' 1.
We will show that there is a solution to the above system by using the intermediate value theorem. First, note that the unit sphere is path connected in R.. Now for a' Ur+1. have ||a'll = 1 and JaaTUU-"" = Next, note that for a' = u1, ||a'll = and la UE"""1 the intermediate value theorem we conclude that there exists some a' on the unit sphere such that IlaT U which completes the proof.
0. Thus, by
K PROOF OF PROPOSITION 3
Proof. Note that we have:
or E. [(y wyx) Ex,x((x 1)x)
PP
m= ||1 "I'
112 (1 4 S 11 11/w011
(w)
P to
||=1|
2|
Since (0) and
are unit vectors on S4-1, the desired probability is equivalent that of the
1 π
ratio of the area of the spherical cap 19) defined by the co-latitude angle 6 cos-1 2|| the surface area of S which completes the proof.
L PROOF OF THEOREM 3
Proof. We here present the proof for the case that y = 1; however, the proof is easily extendable to the case of arbitrary 7. The proof relies on the following inequalities, which commonly used in analysis.
Proposition 4 (Reduction Formula).
d-1 / sin d-2-0 2d0
sin 0do cos (sin d
Proposition 5 (Gautschi's Inequality).
[(x + 1) T(x +)
<x ; s (0,1): x x>0
Corollary 1. For E (0, 1) and x > 0:
[( + 1)
(1) Vx <
< V
T(x + !)
T(x 1 1
(2) Vo+1
[(x +
V
17

---

Under review as a conference paper at ICLR 2021
Proposition 6.
Σ Al
k Jo
1 Vx
_dx -2V
Let K == ()in We will lower bound this integral. For convenience of notation, we will skip writing the limits of integration. By using the reduction formula for the powers of () and assuming d is even for convenience, we have:
K
1
cos (ssn 0)d-3
1 d 3
cos Φ(sin 3)
(d - 3)
COS I Φ +
T( ((22)))
d-2
2 d 4
[d 2)!!
v V
1
cos ausssind Ø
(
(sin (sin))d1
d-1
T ((-)))
(sin (sin d) + +....
(x)
d --2 2
/I d-2)
r( [(
r
d-
r(3)
2
r(
V (
1
((111)
sin 6)'
[(
2
Cos sin
1
2
(by Gautschi's Inequality)
2
T(d-2)
21+1 2
(x[(g)
2
1
1((=1))
(sin? 2 2)
I(
T(d-1) d-11
2
Cos sisin
1
2 0
2
(((-2))
V (1)
2
1
r(
cos o sin
d 2
[(=-2)
T(
Vi
V n
i=1
r(
r( | l 7
2
cos o sin
21
2
2
2
Since o- cos-1
1tc 2||=01
then
+
(1 22+ r 1-1
d 4
r -(-)
1 +
K3 (d- 2) 2|
4 w
2
r
d-2
2
+1
+
| 2
cos
21|
2
Again by Gautschi's Inequality we obtain:
r dd11
1-1 2
<
r(
d-22
and hence,
1 1
(1 c)
d
d - 4
I(
+
K
2
+1
+
Cos -1
(d dd-2) 2) 2| [
100
2
VT
(d)
Thus, have that:
sin din 2 0d0 > - V
1 1
(1+ c)2
1
2
d 4
1
2T (d 2) 2 21|
4
16
2
2
2
1
1 + c
+
cos
2 |
Hence, assuming [|o01] Vd
obtain:
r d
c(1+c)
+ 1 1
c(1 (1+c)
lim
sin
Ad0
2
71'
d-1
2
π 2
2
2T
18

---

Under review as a conference paper at ICLR 2021
Note that we have:
P (0)
(w())
w
(1
s IP wi)
((wr)))
21
) 2 20
|
2 1011 ||
1| ||
2
and hence, we conclude that:
1
c(1 + E)
r 1
1
lim
sin sin 2 Add
S
2
2n 2m
d
V [
d-1
2
19


Reviews:
[{"review_id": "xhk4-wg9ni", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\n==========================================\n\nMain Comment:\nWhile 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. \n\nMinor Comments:\nFigure 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.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "rJSvYrPqqah", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "################################################################\n\nSummary:\n\nThis 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.\n\n################################################################\n\nReason for Score:\n\nThis 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.\n\n################################################################\n\npros:\n\n1, This paper gave an efficient LLBoost algorithm to quickly improve the validation accuracy. The algorithm is theoretically guaranteed.\n\n2, 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.\n\n3, A surprising point of the algorithm is that it does not impact the training loss.\n\n################################################################\n\ncons:\n1, 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.\n\n2, Section 3 (preliminaries and method) is not well-organized. I cannot see why the author put this two lemmas here.\n\n(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\n\n(2) what is the purpose for lemma 2? The paper doesn't clearly state it.\n\nI 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.\n\n3, 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.\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "MKj0UNxTPvl", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\nThis 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.\n\n##########################################################################\n\nReasons for score: \n\nOverall, 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.\nThe 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.\n\n \n##########################################################################\n\nPros: \n\n1. 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.\n\n2. The authors give theoretical results that sampling $w^{(0)}$ on a hyper-sphere leads to a good solution with constant probability.\n\n \n##########################################################################\n\nCons: \n\n1. 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.\n\n2. 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.\n \n##########################################################################\n\nOther concerns:\n\n- 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.\n\n- 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.\n\n- 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.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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