Year: 2020

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, computationallyefficient method to boost the validation accuracy of pre-trained overparameterized 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.

text: In this work, we present LLBoost, a theoretically-grounded, computationallyefficient method to boost the validation accuracy of pre-trained overparameterized 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.

heading: 1 INTRODUCTION
text: Over the past decade, deep networks have produced a number of state-of-the-art results including surpassing human performance on the ImageNet classification task (26; 14). However, tuning hyperparameters to produce the best possible neural network in a given application remains a computationally expensive task. State-of-the-art results often involve selecting the best model using multiple random seeds (14; 27; 12; 28) or ensembling (15), and training even a single model can take several days even when using multiple GPUs. Hence, it is critical to identify computationally efficient approaches to improve the performance of pre-trained models without the need of re-training them.
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 training accuracy. Figure 1 provides an overview of our method as well as the main results. As shown in Figure 1A, our method adjusts the last fully-connected layer of a 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 1B, we provide an example showing how our method applied to a model trained under a poorly chosen random seed can boost validation accuracy comparable to that of a model trained under a better seed. Lastly, Figure 1C shows that our method can significantly improve the validation accuracy of pre-trained neural networks on large datasets using a fraction of the training time.
The intuition for our method is based on characterizing the benefit of random initialization in overparameterized linear regression. In particular, consider a dataset (X, y) ⊂ Rd×n×R1×n with n < d for which there exists w∗ ∈ R1×d such that y = w∗X . In order to estimate w∗ from the data, we use gradient descent with learning rate η and initialization w(0) to minimize the squared loss, i.e. to solve:
arg min w∈Rd
1 2 ‖y − wX‖2.
It is well-known (8) that gradient descent converges to the following closed-form solution:
wr = w (0)(I −X(XTX)†XT ) + yX†,
where A† is the pseudo-inverse of A (see Appendix A for a proof). In this work, we prove that when n < d, sampling w(0) on a hyper-sphere leads to wr with lower generalization error than the minimum norm solution yX† 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 at our method, LLBoost.
We end the introduction with a summary of our main contributions:
1. We present LLBoost, a computationally efficient method for boosting the validation accuracy of pre-trained neural networks without affecting training accuracy. Additionally, we provide an efficient implementation of LLBoost on the GPU.
2. We provide a 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 overparameterized models.
3. We provide evidence that LLBoost yields a computational advantage over random seed search for training neural networks.
4. In the over-parameterized linear regression setting, we prove that LLBoost reduces the test error of any interpolating solution with high probability without affecting training error.

heading: 2 RELATED WORK
text: Understanding the benefits of over-parameterization is a 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 a second time. (20) noted that this phenomenon
had been noticed empirically several decades prior to the work of (2). A line of recent work have provided a theoretical analysis of double descent in linear regression (13; 3; 1; 22; 5; 21). In particular, (13; 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 over-parameterized regime than in the under-parameterized regime. Our theoretical analysis primarily builds on that of (3), but we analyze the generalization error of random-initialization interpolating solutions instead of the minimum-norm solution.
Various methods, including random seed search and ensembling, are standardly used to 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-art models; for example, (14) considered 5 random seeds for ResNet-110 and (12) considered at least 2 random seeds on CIFAR10 (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 1 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 is 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) or boosting (10). Recently, (15) presented an approach to ensembling, which involved training a 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 a model across training epochs.
LLBoost can be used in combination with all the above approaches to further boost their performance, since it only adjusts the last layer of a pre-trained model without requiring any training.

heading: 3 PRELIMINARIES AND METHOD
text: We now present the preliminaries relevant for formally introducing LLBoost. Since our method is derived from over-parameterized linear regression, we first describe this problem setting.
Noiseless Regression. Let (X, y) ⊂ Rd×n×R1×n denote the training dataset where d is the number of dimensions and n is the number of samples. In noiseless linear regression there exists w∗ ∈ R1×d such that y = w∗X . In order to estimate w∗ from the data, we use gradient descent to minimize the squared loss. Formally, we solve:
arg min w∈Rd
1 2 ‖y − wX‖2 (1)
using gradient descent with learning rate η, which proceeds according to the updates:
w(t+1) = w(t) + η(y − w(t)X)XT .
The following well-known theorem (8) gives the solution, w(∞), for the objective (1) given by gradient descent.
Theorem 1. Let (X, y) ⊂ Rd×n × R1×n with X of rank r < d, let λmax denote the largest eigenvalue ofXXT , and letA† denote the pseudo-inverse of a matrixA. Given initializationw(0) ∈ Rd, gradient descent used to solve:
arg min w∈Rd
1 2 ‖y − wX‖2
with learning rate η < λ−1max converges to w (∞) = w(0)(I −X(XTX)†XT ) + yX†.
When w(0) = 0 (zero initialization), w(∞) is the minimum `2-norm solution for solving the linear system wX = y. The following property of w(∞) is used to demonstrate that LLBoost does not impact training error.
Lemma 1. Let w(∞) = w(0)(I−X(XTX)†XT ) + yX†. Then, w(0)(I−X(XTX)†XT ) ⊥ yX†.
The proof follows directly by substituting inX = UΣV T given by the singular value decomposition (SVD). 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. We primarily focus on the noiseless regression setting, but we note that our theory directly extends to the Gaussian model from (3) and (7).
We now present a 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 is presented in Appendix B.
Lemma 2. If X ∈ Rd×n with columns x(i) ∼ N (0, Id×d), then the singular vectors of X are uniformly distributed on the unit sphere Sd−1. In particular, if x ∼ N (0, Id×d), then x‖x‖ is uniformly distributed on the unit sphere Sd−1. Method Overview. Given the above preliminaries, we present LLBoost in Algorithm 1. LLBoost takes in the following inputs: (1) the training feature matrix X; (2) the validation feature matrix Xt; (3) the validation labels yt; (4) the last layer weights w; (5) the number of samples to consider T ; and (6) the radius of the hyper-sphere to sample from γ. LLBoost begins by constructing the projection matrix P = I −X(XTX)†XT . Then, LLBoost samples z ∼ N (0, I), normalizes z and adds the perturbation γzP to w. LLBoost repeats this process and returns the perturbation that most improves the validation accuracy.
Remarks. As shown in Figure 1A, X and Xt are constructed by applying all but the last layer of the neural network to the training/test data. If X is not full rank (as is the case for neural networks that are not over-parameterized), we can create a low rank X by truncating the lower singular values of X . This correction only mildly affects training error as is shown in Section 4. For classification settings, yt should be converted to 1-hot vectors. When the last layer has a bias, one can simply append a 1 to w and append an extra row of 1’s to X and Xt. In most of our experiments, we consider up to T = 100, 000 samples. When selecting γ, one can utilize a binary search approach starting with γ = 1√
d and either doubling or halving γ depending on whether the validation accuracy
increased or decreased respectively. However, as a simple heuristic one can start with γ = 1√ d ‖w‖ (as is recommended by Theorem 3). Lastly, when the network has multiple outputs (as in multiclass problems), we let the entries of the weight matrix be i.i.d. standard normal variables and then normalize by the Frobenius norm.
LLBoost does not impact training error/accuracy. Since the perturbations constructed by LLBoost are always projected into the space orthogonal to the training features X , Lemma 1 implies that LLBoost does not alter the training predictions. This is an important aspect of our algorithm since otherwise, LLBoost could just overfit the test data.
Algorithm 1 LLBoost (X,Xt, yt, w, T, γ) Input: X := rank r training feature matrix; Xt := val. feature matrix; yt := val. labels; w := last
layer weights; T := number of samples; γ := radius of hyper-sphere Output: wbest := adjusted last layer weights
1: wbest = None 2: accbest = 0; (1, d) = w.shape; U,Σ, V T ← SVD(X) 3: P ← Id×d − UIr×rUT 4: for t← 1 to T do 5: z ← N (0, Id×d) 6: z ← z‖z‖ 7: wr ← γzP + w 8: acc = GetV alAcc(Xt, yt, wr) 9: if acc > accbest then
10: wbest = wr; accbest = acc 11: end if 12: end for 13: return wbest
GPU Implementation. We can easily remove the loop in Algorithm 1 by using the GPU since the dominating computations are vector-matrix products. A full implementation is provided using PyTorch (25) and NumPy (23; 29) in the footnote below1. In practice, computing the validation accuracy for each sample of wr is the limiting factor in LLBoost. For large datasets, the functions used to compute the SVD and the projection matrix P need to 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 1012 entries, the reduced SVD only requires 108 entries.

heading: 4 EMPIRICAL RESULTS
text: In Figure 2, we provide empirical evidence that LLBoost consistently improves the validation accuracy of state-of-the-art models on CIFAR10, ImageNet32 (24), and ImageNet. For models finetuned2 on ImageNet32 or CIFAR10, we provide all training details in Appendix C. Importantly, as proven by Lemma 1, we note that the training accuracy remains unchanged after applying LLBoost.
Handling under-parameterized models. If n denotes the number of training samples, the size of the training feature matrix is 512 × n for ResNets-18 and 34 while it is 2048 × n for ResNet-50 and FixResNext-101 (28). Hence ResNet-18 and 34 are over-parameterized on the training set when n < 512, while ResNet-50 and FixResNext-101 are over-parameterized for n < 2048. When the 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 = UΣV T , we construct X̂ = U Σ̂V T
where we zero out the bottom entries of Σ. When X̂ has rank k, we refer to it as the rank k approximation of X .
Our experiments are summarized as follows:
1. On ImageNet32, we fine-tune pre-trained ResNets of varying depth on 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 a rank 12
1https://anonymous.4open.science/r/b11fa900-efbf-45ae-aee8-a264d954cb51/ 2By fine-tuning, we mean training a pre-trained model on a new dataset. This is discussed further in the
transfer learning tutorials provided by PyTorch (25).
approximation for the feature matrix when necessary. This set of experiments demonstrates that LLBoost improves transfer learned models on small datasets.
2. On CIFAR10, we fine-tune a pre-trained ResNet-18. We then apply LLBoost to the pretrained network. In this setting, there are 50, 000 training examples and so the feature matrix is full rank. To make the model over-parameterized, we instead use the rank 212 approximation. Remarkably, this approximation does not impact the original training accuracy.
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, we use the rank 1000 approximation, and the original training accuracy decreases from 95.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 1, there is no impact on training accuracy in the over-parameterized setting. In under-parameterized settings such as FixResNext-101 on ImageNet, our experiments indicate only minor decrease in training accuracy when using a low rank approximation to X . In Appendix D, we additionally present: (1) the difference in `2/Frobenius norm between the LLBoost weights and the original weights; (2) the run-time of LLBoost; (3) the choice of γ 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 train/validation accuracy.
Remarks. In the last column of Figure 2, we also provide the performance of perturbing the last layer of a neural network with a usual distribution such as the standard normal. Note that such a 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 normal initialization (instead of uniform on the hyper-sphere as done in LLBoost) can similarly reduce validation accuracy. While we have thus far concentrated on validation accuracy, in Appendix G 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 compare the performance of fine-tuning pre-trained models on ImageNet32 and CIFAR10 using random seeds. Naturally, LLBoost can be applied to boost the performance of all these models. Moreover, Figure 3 illustrates that LLBoost can boost the performance of a model trained using a poor random seed to that of a 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.

heading: 5 THEORETICAL RESULTS
text: We now present our derivation and analysis of LLBoost for over-parameterized noiseless linear regression. In the noiseless regression setting, we assume that the labels y ∈ R1×n are generated by the product of w∗ ∈ R1×d and data X ∈ Rd×n. Let ŵr = w(0)(I − X(XTX)†XT ) + yX† and ŵ = yX† denote interpolating solutions for the linear system wX = y given by gradient descent from initialization w(0) and 0 respectively. In this section we establish the following:
1. Generalization bounds on wr.
2. There exist infinitely many w(0) such that ‖ŵr−w∗‖ < ‖ŵ−w∗‖, i.e. there exist infinitely many random initializations that out-perform the minimum norm solution. In particular, we show that even if ‖w(0) − w∗‖ is large, ‖ŵr − w∗‖ can be arbitrary close to 0.
3. Sampling w(0) uniformly on the hyper-sphere of appropriate radius leads to ŵr outperforming the minimum norm solution with constant probability.
The following proposition (with proof in Appendix H) compares the generalization error of the random initialization solution, ŵr and the minimum norm solution, ŵ.
Proposition 1. Let X = UΣV T denote the SVD of X and let Σ⊥ = I − ΣΣ†. Then, (a) ‖ŵ − w∗‖ = ‖w∗UΣ⊥UT ‖, (b) ‖ŵr − w∗‖ = ‖(w(0) − w∗)UΣ⊥UT ‖ ≤ ‖w(0) − w∗‖.
By using Proposition 1 and extending the proof technique of (3), we establish the following generalization bounds for the solution starting from initialization w(0).
Theorem 2. Assuming data x, x(i) ∼ N (0, Id×d) for i ∈ [n], then (1) Ex,X [(y − ŵx)2] = EX [‖ŵ − w∗‖2] = ‖w∗‖2 ( 1− n
d
) ,
(2) Ex,X [(y − ŵrx)2] = EX [‖ŵr − w∗‖2] = ‖w(0) − w∗‖2 (
1− n d
) .
The proof is presented in Appendix I. From Theorem 2, the out of sample performance of the solution initialized at w(0) is governed by the distance between w(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 if ‖w(0) − w∗‖ = c1 is large, ‖ŵr − w∗‖ can be any value between 0 and c1.
Proposition 2. Let r denote the rank of the data matrix X and let c1 ≥ c2 ≥ 0. Then there exists w(0) such that ‖w(0) − w∗‖ = c1 and ‖ŵr − w∗‖ = c2. The full proof is presented in Appendix J. Importantly, Proposition 2 provides the following intuition around the benefit of random initialization in over-parameterized models. When X has rank r for r small, the space orthogonal toX 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 w(0) to add a term orthogonal to X we can expect to obtain a boost in performance over the minimum norm solution. The following proposition and theorem present a sampling method for w(0), which provably provides a boost over the minimum norm solution with constant probability.
Proposition 3. Let Ud represent the uniform distribution on the sphere. Assume that the data x, x
(2) i ∼ N (0, Id×d) for i ∈ [n] and that w(0) ∼ Ud. Then, Pw(0)(Ex,X [(y − ŵrx)2] ≤ Ex,X [(y − ŵx)2]) = Γ ( d 2 ) √ πΓ ( d−1 2 ) ∫ φ 0 sind−2 θdθ, (2)
where φ = cos−1 (
1 2‖w∗‖
) and Γ(x) denotes the Gamma function, which satisfies Γ(x) = (x −
1)Γ(x− 1) with Γ(1) = 0 and Γ( 12 ) = √ π.
The proof is given in Appendix K. The benefit of Proposition 3 is that we can lower bound the right hand side of Equation (2) by a constant greater than 0. This is computed explicitly in Theorem 3.
Theorem 3. Let Zw(0) = Ex,X [(y − ŵx)2] − Ex,X [(y − ŵrx)2] denote the difference in expected generalization error between the minimum `2-norm solution and the random initialization solution. If w0 ∼ Ud(γ), ≥ 0, and κ = γ+ γ 2‖w∗‖ , then
1 π cos−1 (κ)−
√ d(d− 1)( √ 2(d− 4) + 1)κ (√ 1− κ2 ) 2 √ π(d− 2) ≤ Pw(0) ( Zw(0) ≥ ( 1− n d )) ≤ 1 2
In particular, if ‖w∗‖ = 1, γ = 1√ d , and = 1d , then κ = 1 2 √ d and
1 2 − 1 2 √ 2π ≤ lim d→∞
Pw(0) ( Zw(0) ≥ 1
d
( 1− n
d
)) ≤ 1
2 (3)
Remarks. Theorem 3 is at the core of LLBoost; it implies that the probability of ŵr having lower expected generalization error than ŵ is constant. Note that based on Equation (3) this constant is lower bounded by roughly .3 (meaning we get a 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 `2 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 Inequality (11) and integration by parts. Note that while it may seem at first that φ should be uniformly distributed when w(0) is uniformly distributed on the sphere (and thus the probability should go to 1/2 as d goes to∞), it is in fact not true that φ is uniformly distributed when w(0) is uniformly distributed, which is why a more precise argument is required.

heading: 6 DISCUSSION
text: In this work, we presented LLBoost, a theoretically-grounded, computationally-efficient method to improve the validation accuracy of 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-art pretrained 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 can even boost the performance of a model trained on a poorly selected seed to that of a model trained on a well-selected seed. Thus, LLBoost is a computationally efficient alternative to 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-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.

heading: A GRADIENT DESCENT IN LINEAR REGRESSION
text: Theorem 4. Let (X, y) ⊂ Rd×n × Rn with X of rank r and X = UΣV T its singular value decomposition (SVD). Given an initialization w(0) = 0, gradient descent used to solve:
arg min w∈Rd
1 2 ‖y − wX‖2.
with learning rate η < 1 λmax(XXT ) converges to:
w(∞) = yV Σ†UT , where Σ† =  1 σ1
0 . . . 0
0 1σ2 . . . 0 0r×d−r 0 . . . 1σr 0d−r×r 0d−r×d−r
 .
Proof. Let S = XXT and S′ = yXT . Then, w(t+1) = w(t)(I− ηS) + ηS′. Now we directly solve the recurrence relation; namely,
w(t) = ηS′((I − ηS)t−1 + (I − ηS)t−2 + ...+ (I − ηS)1 + I).
Let X = UΣV T denote the singular value decomposition of X where {σ1, . . . , σr} are the nonzero entries of Σ and r is the rank of X . Then, S = UΣ2UT , and S′ = yV ΣUT . Thus, we can simplify the recurrence relation:
w(t) = ηS′U((I − ηΣ2)t−1 + (I − ηΣ2)t−2 + ...+ (I − ηΣ2)1 + I)UT .
Since (I − ηΣ2)t−1 + (I − ηΣ2)t−2 + ...+ (I − ηΣ2)1 + I is a geometric series, for η < 1 σ21
, we have:
w(t) = ηS′UΣ+UT ,
Σ+ =  1−(1−ησ21)t ησ21 0 . . . 0 0 1−(1−ησ22)t ησ22 . . . 0 0r×d−r 0 . . . 1−(1−ησ2r)t
ησ2r
0d−r×r tId−r×d−r
 .
Now substituting in S′ = yV ΣUT gives us:
w(t) = yV Σ†UT ,
Σ† =  1−(1−ησ21)t σ1 0 . . . 0 0 1−(1−ησ22)t σ2 . . . 0 0r×d−r 0 . . . 1−(1−ησ2r)t
σr
0d−r×r 0d−r×d−r
 .
Lastly, we can take the limit as t→∞ to conclude that
w(∞) = lim t→∞ w(t) = yV Σ†UT , where Σ† =  1 σ1
0 . . . 0
0 1σ2 . . . 0 0r×d−r 0 . . . 1σr 0d−r×r 0d−r×d−r
 .
Note that the proof above can be easily extended to the setting of a random initialization w(0).

heading: B DISTRIBUTION OF SINGULAR VECTORS OF A RANDOM MATRIX
text: Proof. We use the rotational invariance of the multivariate isotropic Gaussian. If A is an orthonormal matrix, then we have:
xT I−1x = xTAT I−1Ax = (Ax)T I−1(Ax).
Now, suppose A,B are both orthonormal matrices, then we have:
AXBT = (A⊗B)Xv,
where Xv ∈ Rdn 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, AXBT must have the same distribution as X , and thus the singular vectors of AXBT must have the same distribution as those of X . Since singular vectors lie on Sd−1 and since the distribution is rotation invariant, we conclude that the singular vectors are uniformly distributed on Sd−1.

heading: C TRAINING DETAILS
text: We now describe the training methodology we used to train pre-trained models on ImageNet32 and CIFAR10. The optimizer, initialization, learning rate, and seeds used to train the ResNets in Figure 2 and 3 are 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 CIFAR10 for 50 epochs. We then saved the model with the highest validation accuracy.
For all experiments, we used the PyTorch deep learning library (25). We trained our models on a shared server with 1 Titan Xp and 2 GeForce GTX 1080 Ti’s. We only used 1 GPU at a time for training neural networks and applying LLBoost.

heading: D ADDITIONAL EXPERIMENTAL DETAILS
text: In this section, we provide the following additional details regarding the experiments in Figure 2 and 3:
1. The number of components used in the low-rank approximations for a full rank training feature matrix (Figure 5).
2. The size of the perturbation produced by LLBoost and the values of γ used for the models in Figure 2 (Figure 6).
3. A comparison between training time and the time taken for LLBoost to improve the models in Figure 2 (Figure 7).

heading: E PERFORMANCE OF PROJECTED STANDARD NORMAL PERTURBATIONS
text: In Figure 2, we demonstrated that perturbing the last layer without projecting to the space orthogonal to the feature matrix provided a drastic decrease in the training and validation accuracy. In Figure 8, we illustrate the impact of using a 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 guaranteed by Lemma 1.

heading: F LOW RANK APPROXIMATIONS FOR FEATURE MATRICES
text: As discussed in Section 4, 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, we discuss our method of
choosing the number of components of the SVD to keep for producing the low-rank approximation forX . We then present how the number of components selected affects the performance of LLBoost.
In Figure 9, we visualize the normalized singular values of the feature matrix for models from Figure 2. In Figure 9A, we do not use a low-rank approximation as the size of the dataset is already smaller than the number of features. In Figure 9B, the feature matrices are full rank, and so we use a lowrank approximation for the feature matrix with the number of components selected shown red. In particular, we chose a number of components that is well past the elbow in the curve so that there was not a significant drop in training accuracy.
In Figure 10, we demonstrate how the number of components selected for the low-rank approximation affects the validation accuracy of LLBoost. In particular, we observe that using a lower rank approximation generally increases the improvement provided by LLBoost. This matches the intuition provided by Proposition 2: when the space orthogonal to the training feature matrix, X , is large, there is no reason to believe that the best linear solution lies in the span ofX . Hence, sampling the space orthogonal to X yields an improvement. We note that since only a few singular values of X are large, there is no impact to the training accuracy when using a low-rank approximation for X (shown in the second column of the tables in Figure 10).

heading: G LLBOOST APPLIED TO TRAIN, VALIDATION, TEST SPLITS
text: In Figure 2 and Figure 3, we demonstrated that LLBoost improves the validation accuracy of pretrained models without impacting the training accuracy. To ensure that LLBoost is not overfitting
the validation set, we additionally split the validation data into validation and test data and check that LLBoost improves validation and test accuracy without impacting training accuracy3.
3For ImageNet32, the validation set size is only 100 examples, and so we split the training set and re-train.
In Figures 11 and 12, we present examples of how LLBoost (which selects the perturbation that improves validation accuracy) improves both validation and test accuracy without impacting training accuracy.

heading: H PROOF OF PROPOSTION 1
text: Proof. We first consider ŵ − w∗:
ŵ − w∗ = yV Σ†UT − w∗
= w∗XV Σ†UT − w∗ (since y = w∗X) = w∗UΣΣ†UT − w∗(UΣ⊥UT + UΣ⊥⊥UT ) = w∗UΣ⊥ ⊥ UT − w∗(UΣ⊥UT + UΣ⊥⊥UT )
= −w∗UΣ⊥UT
Thus, we have shown (1). Now for (2), we have:
ŵr − w∗ = w(0)UΣ⊥UT + ŵ − w∗ = w(0)UΣ⊥UT − w∗UΣ⊥UT = (w(0) − w∗)UΣ⊥UT . Hence, (2) follows from (1).

heading: I PROOF OF THEOREM 2
text: Proof. The proof follows from Lemma 1. Since the columns of X are drawn from N (0, Id×d), Lemma 2 implies that the columns of U are drawn from the uniform distribution on the sphere in Rd. Hence we have that:
EX [UΣ⊥UT ] = EX
[ d∑
i=n+1
uiu T i
] =
d∑ i=n+1 EX [uiuTi ] = 1− n d .
This implies (1) since: EX [‖ŵ − w∗‖2 = w∗EX [UΣ⊥UT ]w∗T = ‖w∗‖2 (
1− n d
) .
Similarly, we get (2), which completes the proof.

heading: J PROOF OF PROPOSITION 2
text: Proof. Let aT = w(0) − w∗. We need to find a such that:
(1) ‖aTUΣ⊥UT ‖2 = d∑
i=r+1
|〈a, ui〉|2 = c22,
(2) aTa = c21.
To do this, we instead first let a′ = c1a and show that there exists a solution to:
(1) ‖a′TUΣ⊥UT ‖2 = d∑
i=r+1
|〈a′, ui〉|2 = c22 c21 ,
(2) a′Ta′ = 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 Rd. Now for a′ = ur+1, we have ‖a′‖ = 1 and ‖a′TUΣ⊥UT ‖2 = 1. Next, note that for a′ = u1, ‖a′‖ = 1 and |a′TUΣ⊥UT ‖2 = 0. Thus, by the intermediate value theorem we conclude that there exists some a′ on the unit sphere such that ‖a′TUΣ⊥UT ‖2 = c 2 2
c21 , which completes the proof.

heading: K PROOF OF PROPOSITION 3
text: Proof. Note that we have:
Pw(0)(Ex,X [(y − ŵrx)2] ≤ Ex,X [(y − ŵx)2]) ⇐⇒ Pw(0) ( ‖w(0) − w∗‖2 ( 1− n
d
) ≤ ‖w∗‖2 ( 1− n
d )) ⇐⇒ Pw(0) ( 〈w(0), w ∗
‖w∗‖〉 ≥ 1 2‖w∗‖
) .
Since w(0) and w ∗
‖w∗‖ are unit vectors on Sd−1, the desired probability is equivalent to that of the ratio of the area of the spherical cap (19) defined by the co-latitude angle φ = cos−1 ( 1
2‖w∗‖
) to the
surface area of Sd−1, which completes the proof.

heading: L PROOF OF THEOREM 3
text: Proof. We here present the proof for the case that γ = 1; however, the proof is easily extendable to the case of arbitrary γ. The proof relies on the following inequalities, which are commonly used in analysis.
Proposition 4 (Reduction Formula).∫ sind θdθ = −1
d cos θ(sin θ)d−1 + d− 1 d
∫ sind−2 θdθ
Proposition 5 (Gautschi’s Inequality).
x1−s < Γ(x+ 1) Γ(x+ s) < (x+ 1)1−s ; s ∈ (0, 1) ; x > 0
Corollary 1. For s ∈ (0, 1) and x > 0:
(1) √ x < Γ(x+ 1) Γ(x+ 12 ) < √ x+ 1,
(2) 1√ x+ 1
< Γ(x+ 12 )
Γ(x+ 1) < 1√ x .
Proposition 6. k∑ i=1 1√ i ≤ ∫ k 0 1√ x dx = 2 √ k Let K = ∫ φ 0
(sin θ)d−2dθ. 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 ∫ (sin θ)ndθ, and assuming d is even for convenience, we have:
K = − 1 d− 2 cosφ(sinφ) d−3 − 1 d− 2 d− 3 d− 4 cosφ(sinφ) d−5 − . . .− (d− 3)!! (d− 2)!! cosφ sinφ+ Γ(d−12 )√ πΓ(d2 ) φ
= − 1 d− 2 cosφ sinφ Γ(d−12 )√ πΓ(d−22 )
[√ πΓ(d−22 )
Γ(d−12 ) (sinφ)d−4 +
√ πΓ(d−42 )
Γ(d−32 ) (sinφ)d−6 + . . .+
√ πΓ( 22 )
Γ( 32 )
]
+ Γ(d−12 )√ πΓ(d2 ) φ
≥ − 1 d− 2 cosφ sinφ
Γ(d−12 ) Γ(d−22 )  d−42∑ i=1 (sin2 φ)i√ 2i+1 2 + 1 + Γ(d−12 )√ πΓ(d2 ) φ (by Gautschi’s Inequality)
≥ − 1 d− 2 cosφ sinφ
Γ(d−12 ) Γ(d−22 )  d−42∑ i=1 (sin2 φ)i√ 2i 2 + 1 + Γ(d−12 )√ πΓ(d2 ) φ
= − 1 d− 2 cosφ sinφ
Γ(d−12 ) Γ(d−22 )  d−42∑ i=1 1√ i + 1 + Γ(d−12 )√ πΓ(d2 ) φ
≥ − 1 d− 2 cosφ sinφ
Γ(d−12 ) Γ(d−22 )
[ 2 √ d− 4
2 + 1
] +
Γ(d−12 )√ πΓ(d2 ) φ.
Since φ = cos−1 (
1+ 2‖w∗‖
) , then
K ≥ − 1 (d− 2) 1 + 2‖w∗‖
√ 1− (1 + ) 2
4‖w∗‖2 Γ(d−12 )
Γ(d−22 )
[ 2 √ d− 4
2 + 1
] +
Γ(d−12 )√ πΓ(d2 )
cos−1 ( 1 +
2‖w∗‖
) .
Again by Gautschi’s Inequality we obtain:
Γ(d−12 ) Γ(d−22 ) <
√ d− 1
2 ,
and hence,
K > − 1 (d− 2) 1 + 2‖w∗‖
√ 1− (1 + ) 2
4‖w∗‖2
√ d− 1
2
[ 2 √ d− 4
2 + 1
] +
Γ(d−12 )√ πΓ(d2 )
cos−1 ( 1 +
2‖w∗‖
) .
Thus, we have that: Γ ( d 2 ) √ πΓ ( d−1 2 ) ∫ φ 0 sind−2 θdθ > − √ d 2π
1 (d− 2) 1 + 2‖w∗‖
√ 1− (1 + ) 2
4‖w∗‖2
√ d− 1
2
[ 2 √ d− 4
2 + 1
]
+ 1 π cos−1
( 1 +
2‖w∗‖
) .
Hence, assuming ‖w∗‖ = √ d c , we obtain:
lim d→∞
Γ ( d 2 ) √ πΓ ( d−1 2 ) ∫ φ 0 sind−2 θdθ ≥ −c(1 + ) 2 √ 2π + 1 π π 2 = 1 2 − c(1 + ) 2 √ 2π .
Note that we have: Pw(0) ( 〈w(0), w ∗
‖w∗‖〉 ≥ (1 + ) 2‖w∗‖
) ≤ Pw(0) ( 〈w(0), w ∗ ‖w∗‖〉 ≥ 0 ) = 1 2 ,
and hence, we conclude that:
1 2 − c(1 + ) 2 √ 2π ≤ lim d→∞
Γ ( d 2 ) √ πΓ ( d−1 2 ) ∫ φ 0 sind−2 θdθ ≤ 1 2 .

Review summaries:
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.