Training Data Size Induced Double Descent For Denoising Neural Networks and the Role of Training Noise Level
Authors: Rishi Sonthalia
Raj Rao Nadakuditi
Venue: ICLR 2022 Submitted (2022)
Keywords: Double Descent
Denoising Neural Neworks
High Dimensional Statistics.

Abstract: When training a denoising neural network, we show that more data isn’t more beneficial. In fact the generalization error versus number of of training data points is a double descent curve.
Training a network to denoise noisy inputs is the most widely used technique for pre-training deep neural networks. Hence one important question is the effect of scaling the number of training data points. We formalize the question of how many data points should be used by looking at the generalization error for denoising noisy test data. Prior work on computing the generalization error focus on adding noise to target outputs. However, adding noise to the input is more in line with current pre-training practices. In the linear (in the inputs) regime, we provide an asymptotically exact formula for the generalization error for rank 1 data and an approximation for the generalization error for rank r data. We show using our formulas, that the generalization error versus number of data points follows a double descent curve. From this, we derive a formula for the amount of noise that needs to be added to the training data to minimize the denoising error and see that this follows a double descent curve as well.

Under review as a conference paper at ICLR 2022
TRAINING DATA SIZE INDUCED DOUBLE DESCENT FOR DENOISING NEURAL NETWORKS AND THE ROLE OF TRAINING NOISE LEVEL.
Anonymous authors Paper under double-blind review
ABSTRACT
When training denoising neural network, show that more data isn't more beneficial. fact the generalization error versus number of training data points is double descent curve.
Training network to denoise noisy inputs the most widely used technique for pre-training deep neural networks. Hence one important question is the effect of scaling the number of training data points. We formalize the question of how many data points should be used by looking at the generalization error for denoising noisy test data. Prior work on computing the generalization error focus on adding noise to target outputs. However, adding noise to the input is more in line with current pre- are-training practices. In the linear (in the inputs) regime, we provide asymptotically exact formula for the generalization error for rank 1 data and an approximation for the generalization error for rank r data. We show using our formulas, that the generalization eтror versus number of data points follows a double descent curve. From this, we derive a formula for the amount of noise that needs be added to the training data minimize the denoising error and see that this follows double descent curve as well.
INTRODUCTION
X
Madel
0
Model
Suges
Das derancating
Iggat
Model
Inpux
Ouspuct
Ouapett
Denoising Loss
Loss
(a) Denoising Setup
Supervised Learning Setup
Figure 1: Figure showing the difference in the noise placement between the traditional supervised learning set up for which empirical and thcoretical double descent curves have been found versus our denoising set up for which we recover double descent curves.
Denoising noisy training data is a widely used technique for pretraining networks to learn good representations of the data. Two extremely common examples of pretraining via denoising are Masked Language Modelling (MLM) (Devlin et al. 2019) and Stacked Denoising Autoencoders (SDAE) (Vincent et al.) 2010). For many modern problem, work large scales in terms of the number of parameters and the number training samples. Recently there has been significant work in understanding the effect of scaling the number of parameters in the neural network. This resulted

---

Under review as a conference paper at ICLR 2022
in the discovery of the much celebrated double descent phenomena (Belkin et al. 2019). However, we do not have as good of an understanding of the effect of scaling the number of data points.
Works such as Nakkiran et al. (2020); Nakkiran (2020) d d'Ascoli et al. [020a;[Adlam Addam & Pennington (2020) show either empirically or via theoretical analysis that sample wise double descent exists. However, these were in the regime of supervised learning- On the other hand, our motivation comes from understanding denoising autoencoders. For MLM and SDAEs the denoising is pretraining procedure, in which case the generalization error would depend on the downstream task. We shall instead look at the generalization error with respect to denoising test data. The difference between prior supervised learning set up and our denoising set up can be seen in Figure II]
In an attempt to theoretically understand the denoising setting, we look at the simplest setting, Specifically we look at the case, when our network is a linear (with respect to the inputs) network and we are denoising data that lies on a line embedded in high dimensional space. In this setting, we derive the exact asymptoties for the generalization error. We see that in this case, the generalization error spikes at the interpolation threshold (Figure 5a and the amount of noise that we want to add also spikes at the interpolation threshold (Figure 5b). From the theoretical analysis, we see that the spike occurs due to the variance of the model increasing.
Contributions. The main contributions of our works are as follows.
1. We empirically show that when denoising data using feedforward network, the curve for the generalization error versus the number of training data points as well the curve for the ratio of the test data SNR to the optimal training data SNR has double descent. Further changing the training data SNR can mitigate the double descent in the generalization error curve.
2. Assuming we have mean O, rotational invariant noise, we derive an analytical formula for the expected mean squared generalization error for denoising rank 1 data by a linear network. Further, we use the same method to derive an approximation for higher rank data and experimentally verify the accuracy of the formula for general low rank data.
3. Using our formula, we show that even in this simple model, we see that the double descent exists for the generalization error and for the amount of noise that should be added versus the number of training data points.
Related work. Understanding deep neural networks is current active area of research with many exciting theoretical results. The discovery that fixed depth infinite width neural networks can be thought of as kernel regression (Jacot et al., 2018) and the discovery of double descent for neural networks (Belkin et al.) 2019) has sparked significant research into understanding the generalization in the linear regime (in parameters not inputs). The exact asymptotic for generalization loss were first understood for ridge regression (Bartlett et al., 2020: Hastie et al.) 2019 Belkin et al., 2020 Advani & Saxe, (020). This was further generalized to understand the situation for the Random Features model and the Neural Tangent Kernel (NTK) model (Mei & Montanari, 2019 Ghorbani et al. 2019
Adlam & Pennington 2020). A partial list of recent work for supervised learning includes Jacot et al.
(2020); Mel & Ganguli (2021); Derezinski et al. [2020): d' Ascoli al.
Mel
(2020); Dobriban & Wager
(0155) Geiger et al. (2019); Lampinen & Ganguli (2019); Liang et al.
[2020): Muthukkmmr et al.
(2019): Loureiro et al. (202T). However, there has been no work, to our knowledge, that looks at the
problem either empirically or theoretically for the denoising set up.
The idea of adding noise to improve generalization has been seen before. One popular strategy is to use Dropout (Hinton et al. [2012; Wan et al.] 2013 Srivastava et al., 2014), where we randomly zero out either neurons or connections. Another idea that is commonly used is data augmentation. In revolutionary paper, Krizhevsky et al. (202)) showed that augmenting the dataset with noisy versions of the images, greatly improved the accuracy. Another area where noise is useful is adversarial learning. Dong et al. (2021) shows epoch wise double descent for adversarial training.
In terms of recent thcoretical work related to SDAEs, Pretorius et al. (018)) derived the learning dynamics of a linear autoencoder in the presence of noise. They also establish some relationships between the noise added and weight decay. However, they do not look at the generalization error or
quantify the optimal amount of noise that should be added. (Gnansambandam & Chan (2020) looked at the problem of what is the optimal amount of noise that should be added. However, they studied this from the perspective of minimizing the variance of the performance.
2

---

Under review as a conference paper at ICLR 2022
2 SET-UP
Let U E Rx be our feature matrix. For case of notation, we assume that the columns of U have unit norm and pairwise orthogonal. Then generate N data points, sample latent variables Ve e R and E R such that V has columns that have unit norm and are pairwise orthogonal and Σ is diagonal matrix such that |E|| = 1. Then a data matrix X is given by X = UEV For us, we have two matrices X Xtrn and Xst that correspond the train and test data sets. Hence we have corresponding Vern E R R Vist R Rtx,Nst and Eern, Etst. We make no other assumptions on U, Virn: Etrn Vist; Etst except that they are given and fixed. Finally, let Pest. itrn E R.+ be scalars that will scale the singular values of X Xtrn, Xest so that we can control the SNR. We also assume that Otst is fixed and that we have control over Otrn. Let c = M/N and let A Aest be noise matrices that are added to the training and the test data. Let W be the linear autoencoder that is the solution to the following problem
minimizew
110ernXeen
W WOrenneem +ern)) 11..
Yeen
Then, the expected mean squared error, is given by
R(Oern: Best, C2 Eteny Etst) == 11ostt
W
W(Ostt Xest Aese)
(2)
Nost
2.1 ASSUMPTIONS ABOUT THE NOISE
We assume that each entry of the noise matrix A has mean O variance 1/M and that the entries of A are pairwise uncorrelated. Additionally, we shall assume that A is rotationally bi-invariant. That is, if Q is an M by M (N by N) orthogonal matrix, then QA (AQ) has the same distribution A. Another way to phrase this is if A = VVEAVA is the SVD, then UΛ and VA are uniformly random orthogonal matrices and are independent from ΣA and each other. Finally, we shall assume that A has full rank with probability 1 and that the limiting distribution of the eigenvalues of A A converge to the Parchenko-Pasttur distribution. While such assumptions the noise may seem restrictive. This encompasses a large family of noise distributions.
Proposition If B is a random matrix that has full rank with probability and entries are independent, have mean 0, have variance 1/M, and bounded fourth moment, and P, Q are uniformly random orthogonal matrices. Then A = PBQ satisfies all of our noise assumptions.
2.2 SIGNAL NOISE RATIO (SNR)
A quantity of interest to us will be the SNR, given by |X||=/|A|| Hence, we need to normalize everything by ||Al|p. p. In this case, due to our assumptions, we have that |||| = N. Hence, for any variables and constants, it has hat, then that refers to that variable constant normalized by VN. For example, given Iern; Xtrns and Atru then we have that
|10rm dem/le// Arral | r = Otrn/ Atrn II Rs Otrn/ / Nern =: 0trn.
3 EMPIRICAL DOUBLE DESCENT
We first show that sample wise double descent occurs for denoising neural networks empirically. Figure [ shows that if we train a feedforward network denoise data such that the training data signal noise ratio (SNR) 0trm the same SNR as that of the test data set (ft.z). then the curve for the denoising generalization eтror vs the number of training samples has the shape of a double descent curve. Thus, together with prior work, this suggests that the double descent with respect to the number of data points is universal phenomena. However, unlike other hyperparameters, such as number features and number of training epochs, we cannot arbitrarily change the number of data points are limited by the data set that we have. Hence it could be the case, that the maximum number data points that we have corresponds to the peak of the generalization error curve.
However, look at the amount of noise that add to the training data. To the effect of the noise, for a variety of different Oern/ /Osto we compute the denoising generalization error versus
3

---

Under review as a conference paper at ICLR 2022
18-
1071
213
Rank Data
(b) Non Linear Synthetic Data
(c) MNIST
IC- Mencl
IC Strrl
(d) Rank Data
(e) Non Linear Synthetic Data
(f) MNIST
Figure 2: Figure showing the double descent phenomena for the generalization error versus the number of the training data points. The top row is for linear network and the bottom row is for 3 layer ReLU network. Here the training data SNR and the test data SNR both equal 9.
Optimal
10
Optimal
17.5
-
-30
Generlization Eror
15.0
05 x000
225
0pn
125
0pm
10
Oat
10:3
10.0
Pat
1
9x10-1
25
0.0
0.
15
2.0
25
1/C NtrrMM
1/C 3 NtmuM
(a) MNIST
(b) CIFAR
Figure 3: Figure showing the denoising generalization error for 3 layer neural network trained for various different values of Öern/Oes and number of training data points. Each neural network was trained for 1500 epochs, using gradient descent with learning rate of 10 For MNIST, we averaged over 20 trials and for CIFARIO we averaged over 5 trials.
the number of data points curve. We do this for MNIST and CIFAR dataset. We create test data sets by taking the test data for each and then adding Gaussian noise. We fix the test SNR to be 1 for both datasets. Hence we know the test data SNR. We then take various different fractions of the training data and train a layer ReLU neural network (without bias) for various levels of training noise. For each of pair of parameters (number of training data points and the level of training noise), we compute the generalization error averaged over 20 trials for MNIST and 5 trials for CIFAR. Here the test noise and training noise is resampled for each trial. The plots for the generalization error can be seen in Figures 3a (MNIST) and 3b| (CIFARIO). The first thing we notice that for most ratios for the test SNR to training SNR we see sample wise double descent. Further, we see that the optimal denoising error does not oceur when the train SNR is equal to the test SNR. This very surprising contradicts standard thought that training data distribution should be the same the test data distribution. Interestingly, as seen in Figures and 4b we see that the optimal ratio depends on the number of data points and the shape of the curve for the values otrn/Oe that results in the best generalization emor versus the number data points also has the shape of double descent curve.
4

---

Under review as a conference paper at ICLR 2022
20.0
15.0
10.0
12
25-
1/C Minil
(a) MNIST
(b) CIFAR
Figure 4: Figure showing the sample wise double descent for the optimal amount of training noise.
THEORETICAL RESULTS AND CONSEQUENCES
In this paper, we want to theoretically understand the phenomena seen in Section 3. The main theoretical result of the paper is summarized below in Theorem
Theorem 1. Let ort oft be entries Etrns East and let = Let M/Nera be fixed. Suppose Orr is O(v Nern) and Orat is Ol (NNa)) Then, if < 1, we have that (Destofet)2 R(O Oeat: C2 Etrns Eest) = Nea(1 (memnotm)ac + ((( + (ftrnofrm)1))
M(1 + (Oern (f - + +0(1)
(3)
and i c. > 1, we have that
of
R( R(eerns Bests c, Etrns Erst) N1æe(1 + ofmnoorm)2y + The o(1) error term goes to O as Nern; M + 0o.
M + (2 + (1). (4)
We could imagine that the rank version the same the above but with summation over the rank as shown in the equations below. But, we shall see in Section 5 that this turns out to only be an approximation.
(0ts1ot5t)2
2² ((Brrno)) + (Bumno)ra)))
R(Orrns Dree, e, Etrns Eest)
M(1 + ( +o(1)
Nest (1 + (fernot tra 22)
(5)
c(een olono fnnjz
R(O Orst; C. Exeny Enst) 2
M(1 + (0 ( (/ o(1)
Nest (1 + (rrnotrajjy
(6)
4.1 OPTIMAL AMOUNT OF NOISE
First, if we ignore the error term, differentiate the formula to get the following formula for the optimal training SNR.
02 0,
0 ppt-trr
max
Nest
2-c
<< 1
N1rn
max
2
Neat
0
(c 1) Naw..
<>
(7)
We already see the surprising result that the optimal training SNR and the test. SNR are not equal. This is surprising, as traditional philosophy is that the training data should be drawn from the same distribution as the test data. Here instead we see that the optimal training distribution actually depends
Further, the formulas in Equation 7 also describe a double descent curve for 0 trpt-trnNNur versus c curve as shown in Figure 5b
Derivation and exact assumptions for when the formulas accurate the appendix.
5

---

Under review as a conference paper at ICLR 2022
0.0
Genernltatioon Erter
0.4
00
0.5
1.0
1.5
25
30
0.
0.5
1.5
2.0
2.5
30
C- M4httmm
Miltton
(a) Rank
Theory Generalization Error
(b) Rank SNR
Theery Test SNR Optimal training
Figure 5: Plot showing the double descent curves for the generalization error as well as for the ratio of the test SNR to the optimal training SNR. Here M = 1000 and Ozse = 1 and e was changed by changing Ntrn-
4.2 DOUBLE DESCENT CURVES
We have already seen that the optimal amount of training noise follows double decent curve. This due to the double descent seen in the asymptotics for the generalization error. To understand this phenomenon, first note that the bias of our model is given by the first term in formula in Theorem and the variance given by the second term. That is, we have that the variance given by
EL M(I+ of (1
afflenn fra
EL M(I+ P)--i
C>
From these formulas, linear model, is the interpolation threshold (i.e., the point after which we have O training error). Hence as with previous models for double descent, see that we approach the interpolation threshold, the variance of model increases, resulting in an increase in the generalization error.
that
these formulas have singularity. Since have
fix the number of features M and change by varying Ntrns and also scale 6iyn as itrn 0rrn / Nerm: then we see that as c -> 1, the variance of the model increases. Once we have enough data points so that see that as we increase the number of data points, the bias decreases until we hit the interpolation threshold, after this point, the bias is constant. Similarly, if we fixed Nton and changed by changing M then after the interpolation threshold, the inductive bias of the model kicks in. Here we see that that
1, we have the variance of the model starts decreasing. Additionally, we
the variance terms corresponds to ||I Henee regularize the weights of the network and get the second descent the generalization error. That is, the variance of the model decreases of parameters, the bias of the model of the model decreases and then after the interpolation threshold becomes constant. Note that this value non-zero and depends on the training SNR.
0o, have that this implicitly
xc. Additionally, see that as we increase the number
In previous work (such as Mei & Montanari 2019) on double descent curves for ridge regression, we that optimal ridge regularization results in the vanishing of the double descent phenomena. This is also seen empirically for Lg regularization for classification in Nakkiran et al. (2020). However, in our theoretical model even if we optimally pick the amount training noise, we still have double descent. This is in contrast to results seen with a deep network on real data in Figure
5 PROOF OF THEOREM
We prove Theorem [ via the steps shown in Figure The proofs for all of the lemmas have been moved to the appendix. Here present a proof sketch that details the high-level ideas.

---

Under review as a conference paper at ICLR 2022
Decompose into Bias and Variance
Derive formula for
Bi (sst WX
E Aeas A
Seenl uh Pinlle Rten uh Sr "mmp us "
ukt
A
e<
c>
Bios
Variance
Estimate trace terms using Random Matrix Theory
Expand bias and variance into trace terms
(TT(""(AA"))
F +11
p<q
0 11
2B Irih's
Ammlli
0-1 pI-C-T t(1)
Tr A)
Tr(ss")
p>q
T
Figure 6: Figure showing the major steps used derive the formula for the generalization error.
5.1 STEP 1: DECOMPOSE THE ERROR INTO BIAS AND VARIANCE TERMS
First, we decompose the error into its bias and variance.
Lemma 1. If Atst has mean O entries and Aest. independent of Xtst and W, then
EA..lllOtst W Yeatlel [1a) = Aest Ill W Westell l1ee] [
Ae [
A 1
(8)
Bios
Varsance
5.2 STEP 2: FORMULA FOR W
In current setup, know that W is the solution least-squares problem. Hence W
Xtrn yi trm. Expanding this out, we get the following formula for W. Let h o A
A U,
= (I - A trm J. = Vten and 72 0% ||s| | + 32.
AlrmArr)) 3 = 1 + Pern uyr Alra u, T1 = 6?, ||t| ||| 2 + B2,
Proposition 2. If 8 # 0 and Atrn hus full rank then
Ocen uh
6 uk
e<1
W
tr
Bern uh
us
c>
For Gaussian noise Aer has full rank with probability and 8 is a random variable whose expected value is equal 1, and the distribution is highly concentrated. Thus, Proposition 2 applies when Atr is isotropic Gaussian noise. Here we restricted ourselves to rank 1, as using Meyer 1973), we can expand formulas of the form (A + myy")t where x, are vectors. For the higher rank case, we apply the formula form Meyer (973) iteratively. This is the main difficulty of the method. Previous work on deriving asypmtotics for the generalization error had the noise on the output. Hence would take the pseudoinverse of matrix that only depended on the data. However, in our case, taking the pseudoinverse matrix that depends on the noise.
5.3
STEP 3:DEMMPOOSE THE TERMS INTO SUM OF VARIOUS TRACE TERMS.
Let us first look the bias term.
Lemma 2. If W is the solution to Equation!
[ then
P Xest if <
Xest W Xist
2 Xest ifc>1
Let us now look at the second or the variance term.
Lemma 3. If the entries of Arst are independent with mean and variance 1/M, then we have that
E [ A 2 A |||l2

---

Under review as a conference paper at ICLR 2022
Note that this did not need any assumptions on W or X(st. All that needed were the assumptions on Atst. Thus, this holds more generally. This decomposition also follows from Bishop (1995) In
light of Lemmas | 2 and the fact that || || ff we see that the expected mean squared generalization error is given by,
Xist WY
3 rist +
1
A
|W]?
Nest
Nia 7i
M
where 7; depends on whether c 1 or e >.1, 1. Finally, let us look at the [[]] term.
Lemma 4. 1f + 0 and Aern has full rank, then we have that if 1,
|W]] Pr Tr(h" h) + 7
07 1 ||t|1?3
8 ||
Tr(h KJT Alrr))
Tr((At " Tok? lak"Atrrn Afrm)
T
and i > 1, then we have that
02 0rmm1 82
| 0 Tr(h ))
Ot |||| Tr(ss
Tr(h"h) h) +
T2
2
5.4 STEP 4: ESTIMATE USING RANDOM MATRIX THEORY.
While the formula given by Lemmas 3 and is correct, we need a simpler formula to analyze the situation. Using ideas from random matrix theory, we can simplify the expression for || [/.. To do so, we first need prove Lemmas and
The main idea behind Lemmas and is that due to the rotational invariance of Atrn. the expectation of the trace of products of various matrices derived from Atro is determined by the expected value of some function X of the eigenvalues of Aten However, instead of directly computing this expected value, we note that for any matrix A, that satisfies the noise assumptions, if we let M, N - oc, with M/N - c, then the eigenvalue distribution converges to the Marchenko Pastur distribution (Marcenko & Pastur] [967] Götze & Tikhomirov 2011: 2003 2004; 2005 Bai et al. (2003). Götze & Tikhomirov ( (2004) showed that the distribution of the eigenvalues converged almost surely with rate of at least ONN-1/2+ for any 0. Thus, we can use the expected value of the x(A) for À sampled from the Marchenko Pastur distribution as an approximation.
For space reasons, we provide only one instance of the lemmas in the main text. The complete versions can be found in the appendix.
an p by q matrix such that the entries of A are independent and have mean O, variance 1/g, and bounded fourth moment. Let W, AA" and let W A Let C = p/q. Suppose Xp, >g are random eigenvalue of Wp. Wg. Then
Lemma 5. Suppose
1. 1fp q. then E
+
Lemma 6. Suppose is by matrix that satisfies the noise assumptions. Let x. y be unit vectors in and dimensions. Let = p/q. Then
1. [T (AAT)))))
- +(()
p<q
i - o(1) p
p>q
Using these technical lemmas, we can now deal with all of the terms in the expressions in Lemma 4 First, let us look at the non-trace terms.
Lemma 7. If Atrn satisfies the noise assumptions, then we have that
1. E[3/0mmm = 1/0ern + (1) and Var(3/0crr) = (mar(M [1-c]]] + o(1).
2
c22 (c)
2. Ifc 1, then [[[]]/||]] 1 c + o(1 and Var( = N - c]}3 + 2 1)
3. Ifc > 1, then |[][h|[]] c-1 + o(1) and Var( [[b[]]]
Nem 1)3 + +
c222 c)) + ((1)
4. ||][|||]]
c + o(1) and Var(I]k]?)=
1-c
M c)3
8

---

Under review as a conference paper at ICLR 2022
5. |||||| + ((1) and Var(I|s|?3) = t(1)
Mc
6. |||M[|]= = + o(1), Var([1[])= = Nern + (1).
Lemma 8. Under the noise assumptions, we have that
E[Tr(h" RT Alma) O and Var(Tr(h" k. Alrm) Xx(c)/Norms
where Xz(c) E[1/>3), X is an eigenvalue for AAT and A is in Lemma Lemma 9, Under the noise assumptions, we have that
c²
Tr((A kkk Alrn) =
c1- to(1) and Var(Tr((AA kk? Atra) T
Xa(c)
M
M (1 c)6
where Xa(e) E[1/x*), X is an eigenvalue for AAT and A is in Lemin 6
Lemma 10. Under the same assumptions as Proposition we have that Tr(h Tr(h" =
Lemmas 7 and telll us that all of the terms are highly concentrated. Thus, even though such terms may not be uncorrelated, we can use the fact that [[[ E E < VVar(X)Var(>>> treat the terms if they are uncorrelated. Since these variances have now been shown to ] + o(1) For example, since T1 B + 66,,, [|]]]|]]]]]|[]]]]]] + (11), using Lemmas and 6 we have that E = 1 + f o(1).
be o(1). we have that for each of these terms X
Similarly, E[r2] = 1 8 + o1). Finally, using these lemmas, we can simplify the expressions in
Lemma 4 to get the formulas for the expected generalization error shown Equations and
01
011
0.3
04
04
0.
07
07
03
-000
11
11
0.04
14
17
0.02
17
19
20
2.0
20
100
200
100
200
(a) Low SNR
(b) High SNR
Figure 7: Figure showing the relative error for our formula. = 2500 and e changed by changing Nten- For low rank, average over 10 trials and for high rank, average over 100 trials.
ACCURACY OF APPROXIMATION
this section we experimentally verify accuracy our formula for general rank r data. Here for low SNR (Otrns Ozst are O(1)), we sample o:Th of L.I.. from the squared standard Gaussian and for high SNR (ftmn; Otst are ((vNrr)), (VVNss))) we multiply this by VNtrn, VNest- As we can we see that our formula is better for low SNR and low rank data.
from Figure 7
CONCLUSION
In this paper, we switch focus from supervised set up to the unsupervised set up. Specifically, we look at the problem of denoising data. We empirically show that sample wise double descent exists for the generalization error. Further, we show that the optimal amount of training noise is not the same as the test noise. In fact, optimal training noise. To understand this phenomena, we study the simplest model, denoising rank data using linear model. Here derive the exact asymptotics for the generalization error.
sample wise double descent for the ratio for the test SNR the

---

Under review as a conference paper at ICLR 2022
REFERENCES
Ben Adlam and Jeffrey Pennington. The neural tangent kernel in high dimensions: Triple descent and multi-scale theory of generalization. ICML, 2020.
Madhu S. Advani and Andrew M. Saxe. High-dimensional dynamics of generalization error neural networks. Neural Networks, 132:428 446, 2020.
Bai, B. Miao, and J. Yao. Convergence rates of spectral distributions of large sample covariance matrices. SIAM J. Matrix Anal. Appl., 25:105-127, 2003.
Bartlett, Philip M. Long, G. Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 1 117:30063 30070, 2020.
Mikhail Belkin, Daniel J. Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical variance trade-off. Proceedings of the National Academy of Sciences, 116: 15849 15854, 2019.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM J. Math. Data Sci., 2:1 167-1180, 2020.
Chris M. Bishop. Training with noise is equivalent tikhonov regularization. Neural Comput., 7 (1):108-116, January 1995. ISSN 0899-7667. doi: 10.1162/neco. 1995.7.1.108. URL https
Stéphane Ascolli Levent Sagun, and G. Biroli. Triple descent and the two kinds of overfitting: Where & why do they appear? ArXiv, abs/2006.03509) 2020.
Michal Derezinski, Feynman T. Liang, and Michael W. Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. ArXiv, abs/1912.04533, 2020.
J. Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep
bidirectional transformers for language understanding. In NAACL, 2019.
E. Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. arXiv: Statistics Theory, 2015.
Chengyu Dong, Liyuan Liu, and Jingbo Shang. Double descent in adversarial training: An implicit label noise perspective. ArXiv, abs/21 10.03135, 2021.
M. Geiger, Arthur Jacot, S. Spigler, Franck Gabriel, Levent Sagun, Stéphane d' Ascoli, G. Biroli, Clément Hongler, and M. Wyart. Scaling description of generalization with number of parameters in deep learning. ArXiv, abs/1991.01600 2019.
B. Ghorbani, Song Mei, Theodor Misiakiewicz, and A. Montanari. Linearized two-layers neural networks in high dimension. ArXiv, Abs/1994.11219 2019.
Abhiram Gnansambandam and Chan, One size fits all: Can we train one denoiser for all noise levels? In ICML, 2020.
Götze and A. Tikhomirov. Rate of convergence to the semi-circular law. Probability Theory and Related Fields, 127:228-276, 2003.
Götze and Tikhomirov. Rate of convergence in probability to the marchenko-pastur law. Bernoulli, 10:503-548, 2004.
F. Götze and A. Tikhomirov. Central European Journal of Mathematics, 3:666-704, 2005.
The rate of convergence for spectra of gue and lue matrix ensembles.
F. Götze and A. Tikhomirov. On the rate of convergence to the marchenko-pastee distribution. arXiv: Probability, 2011.
Hastie, A. Montanari, S. Rosset, and R. Tibshirani. Surprises in high- high-dimensional ridgeless least squares interpolation. ArXiv, abs/1 0bs//193.088 903.08860, 2019.
10

---

Under review as a conference paper at ICLR 2022
Geoffrey E. Hinton, Nitish Srivastava, A. Krizhevsky, llya Sutskever, and R. Salakhutdinov. Improving neural networks by preventing co-adaptation of feature detectors. ArXiv, abs//107.000 .0580, 2012.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel:: convergence and generalization in neural networks (invited paper). Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, 2018.
Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clement Hongler, and Franck Gabriel. Implicit regularization of random feature models. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1633-4640.. PMLR, 13-18 Jul 2020. URL _ htttss:/ppprtttte
ngs
A. Krizhevsky, Nya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolu- tional neural networks. Communications of the ACM, 60:84 - 90, 2012.
A. Lampinen and S. Ganguli. An analytic theory of generalization dynamics and transfer learning in deep linear networks. ArXiv, abs/
2019.
Tengyuan Liang. A. Rakhlin, and Xiyu Zhai On the multiple descent of minimum-norn interpolants and restricted lower isometry of kernels. In COLT, 2020.
Bruno Loureiro, Gabriele Sicuro, Cédric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborová. Learning gaussian mixtures with generalised linear models: Precise asymptotics in high-dimensions, 2021.
V. Marcenko and L. Pastur. Distribution of cigenvalues for some sets of random matrices. Mathematics of The Ussr-sbornik, 1:457-483, 1967.
Song Mei and A. Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv: Statistics Theory, 2019.
Gabriel Mel and Surya Ganguli. A theory of high dimensional regression with arbitrary correlations between input features and target functions: sample complexity, multiple descent eurves and hierarchy of phase transitions. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 7578-7587. PMLR, 18-24 Jul 2021. URL
mlr. w....peess/v33//eee
html
Carl D. Meyer, Jr. Generalized inversion of modified matrices. SIAM Journal on Applied Mathe- matics, 24())315-323, 1973, doi: 10. 10.1137/0124033, URL
0124033
Muthukumar, Kailas Vodrahalli, and A. Sahai. Harmless interpolation of noisy data in regression. 2019 IEEE International Symposium Information Theory (ISIT), pp. 2299-2303 2019.
Preetum Nakkiran. More data can hurt for linear regression: Sample-wise double descent, 2020.
Preetum Nakkiran, Prayaag Venkat, Sham M. Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. In International Conference on Learning Representations, 2020. URL
net/ wwwp::/eeweeetteeeeeeeememeee fowummmdd=7k7faoolloo
Arnu Pretorius, S. Kroon, and H. Kamper. Learning dynamics of linear denoising autoencoders. ArXiv, abs/1806.05413, 2018.
N. R. Rao and A. Edelman. The polynomial method for random matrices. Foundations of Computa- tional Mathematics, 8:649-702, 2008.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way prevent neural networks from overfitting. Journal of Machine Learning Research, 15(56):192--1955 2014. URL http:// jmir.orr, www.rrg/ppao. aozg/papers/v1s/
sri vasteva html

---

Under review as a conference paper at ICLR 2022
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, and Pierre-Antoine Manzagol. Stacked denoising autoencoders: Learning useful representations a deep network with local denoising criterion. J. Mach. Learn. Res., 11:3371 1-3408, December 2010. ISSN 1532-4435.
Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. Regularization of neural networks using dropconnect. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning. volume 28 of Proceedings of Machine Learning Research, pp. http://procceddingg ngs. r. press/ /v2//v2///// wan 13.html
Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL
12

---

Under review as a conference paper at ICLR 2022
In this section present all of the proofs for the results in the main text. Here we present the proofs in the same order they appear in the text.
A NOISE ASSUMPTIONS
Proposition 1 If B is a random matrix that has full rank with probability and entries are independent, have mean O, and have variance 1/M and P. Q are uniformly random orthogonal matrices. Then A = PBQ satisfies all of our noise assumptions.
Proof. Since P.Q uniformly random orthogonal matrices, and A PBQ, then it is clear that is rotationally bi-invariant and has full rank.
Since each entry of B has mean 0 and each entry of A is linear combination of entries of B where the coefficients (i.e., the entries from P, Q are independent of B), we have that each entry of have mean O. Due to the orthogonal nature of P, Q. have the variance for entry of A is the same as the variance of entry in B.
Thus, the only thing left prove that the entries of A are uncorrelated. To do this, we note that
0ij
PabiR
k=1t=
Consider two entries 0igh and 0igi2-
Then we have that
N
M
M
Elann Aizial = E
Pi,tbra
Σ
Piz bra
Blpa,
Elbb E[gai Ukia]
M Σ
N Thn Ukja
E
Σ
M
The second inequality follows from the fact that P. Q, independent from each other, and that fact that the entries of B are independent and have mean O. Hence the cross terms have expectation 0. If we have that and ýı * j2, then have that since
orthogonal matrix
N
N
Elaaj 9kin]
Σ
Dech. Qkia
0.
Thus, the entries are uncorrelated. Similarly when in * 12 since P is orthogonal matrix, we get that the entries uncorrelated.
Convergence to Marchenko-Pasturr If we strengthened the uncorrelated condition, to the entries being independent. Then due the mean and variance assumptions (along with an assumption that the fourth moment is bounded), we would have convergence to Marchenko-Pastur distribution. However, the independence along with the bi-invariance would then force our noise distribution be i.i.d. Gaussian.
In general however, with relaxed assumption of the entries only being uncorrelated, convergence is not known. However, in our case, we have much simpler proof for matrices formed by Proposition I In our case, the noise matrices satisfy the standard assumptions for convergence. We then multiply B by orthogonal matrices that are independent to B. Hence this has effect the eigenvalue distribution. Thus, the eigenvalues distribution for these matrices also converge to the Marchenko-Paee Pastur distribution.
B PROOFS
Due to our data generation assumptions that || | trn geet
|Esee F = 1 for rank data, we have that
13

---

Under review as a conference paper at ICLR 2022
B.1 STEP ??: DECOMPOSE INTO BIAS AND VARAINCE
Lemma
If Asa has mean entries and Aest is independent of Xist and W, then
E Eu - WYtal EAA
[|l W W1st [1s E W
[AllWWAAA Asst
Bias
Variance
Proof. Using the fact that for any two matrices ||G - HI = G |1 -2Tr(G" H), we get that
| WY tor 112 1att W Xtst W A 1|
= X - W X + Atsel 2Tr((Xest - ( Wts)).
Then since the trace is linear, and Xest, W are independent of Alst, and Aest has mean 0 entries, we see that
E [Tr((X.st W W W Atac)] 0.
Thus, we have the needed result.
B.2 STEP ??: FORMULA FOR Wopt opt
Proposition 2 Let = viin Alro & Atr, == (1 Aer ArmnAtrn) t Utrn(1 - AtrnArri
3 = 1 + Bryn V Vrrn-trr u. = (lrnllt|31111 3?, and 0 || ||/1|/1//11 + 3². If + 0 and
Atrn has full rank then
Pvna wh
03 1t11 uk T Arm
c<1
W opt
itvn uh
07 1bll
u8
T
e>1
Proof. Let us first proof the case when > 1. Here we know that u is arbitrary. Here we have that Atr has full rank. Thus, since e 1, we have that M Nerns thus Agra has rank Ntrn- Thus, the rows of Arn span the whole space. Thus, Utrn lives in the range of A Finally, since B & 0, we want Theorem from Meyer 1973)..
Here let us further define
8 ||
iern 1trn||lll
||Al|
A A
1it
Otrnk and of
T
D2
3
3
and finally 72 0z |||1/
11112 + 8..
Then we have from Meyer 1973 that
Oern
B
(Atrn + Oern Ovenuurr wf Airo +
Afru hTs S
p292
3
72
In our case, we only care about Orr wo (Atra + wern Thus let us multiply this through and see what we get.
Ourn
B
i Bernuuty (Aera + Oern (rrm)
Pernuut T (At.m.
+
At
ST
P292
T2
0
Prmnl12111
Own 3
0rrllss12
Ownuh +
us
Witrn
At nT +
Oernk
oo
3
T2
3
02 |1112
03
||=>|||||||]
Ownuh
us"
whaugz
3
72
T2
Then have that
03 0
||]
2|
032
us
uh
(9)
T2
T2.
T2
14

---

Under review as a conference paper at ICLR 2022
and
mnm 3 whaqz
03 0irnl1/ll whus"
Or uhuh.
(10)
Using that B - 1- = Iern
T
Al Alp = Oirnhu, we get that
trrn
Prm 3
0 h|] 1) us
0tm 1)
uhugz
T
wh.
(1I)
Substituting back in and collecting like terms get that
80r Urnutrr (Aern + Iern wom) = Oern (1-
0 1p
B(3 1)) h+
72
11A112
02
|1
|1
1000-11 1)
ST
trm
B
T213
T2
can then simplify the constants as follows.
02
|111211112
3(3-1)
02
|||2||A|12 B²
1
T2
T2
T2
T2
and
|//1
82
[B 1)
(T2 0
3(3 - -1)
|||1233
||b|13
8
723
8TZ
8TZ
T2
This gives the result for 1.
If c > 1. then we have that < Nirn- Thus, the rank of A is M the range of Arr is the whole space. Thus, lives in the range of Atrn. In this case, then want Theorem 3 from Meyer (1973). In this case, we define
03 ||/11 iT
Own |t|1 KT
P
and of
At
h.
B
3
Then in this case, we have that
(Atrn + Otrn ue 20m
A/ro + Own
RT.
At
3
pid
B trn
51
Then simplify the equation we did before!
B.3
STEP ??: EXPAND INTO TRACE TERMS
Lemma
If the entries of Aest are independent with mean 0, and variance 1 1/M, then we have that A = Nest
EAca
Af ?|
Proof. To see this, we note if we look at Arst AT then this is a M by M, for which the expected value of the off diagonal entries is equal to while the expected value of each diagonal entry is Ntst/M, That is, E... [AsttATs]]
Not M
IM.
Then note that
I Aest Tr(A, WTW Atst) = Tr(W" W. Asse Tr(WT WWWttWAstAA Atst Using the fact that the trace is linear again, we see that
Nest Nest Tr(WTW) Nost [[
EAU (Tr(WTW A (TT) TT(WTWB (Aest
(. (Tr1)
M
15

---

Under review as a conference paper at ICLR 2022
Lemma 2 If W is the solution Equation
7 then
Xist ifc <
Xest WXst
1
Xest ifc > 1
Proof. To see this, we have the following calculation for when Nern M.
OcrnOcat
0 SnnOOeall 11e11 uk² At Arnutts
Xist W West
Xest
whuvee
71 Bern
TI
0 Bealltl)
= Xtst
whrnn trn uoist
uk? A Afrm uo
First, we note that 3 = 1 + Otrn Uern Af Aprm u. Thus, we have that Ou A A substituting this into the second term, we get that
1. Thus,
0 Best Xtat W Xest Xest Oas -1 1)
uvist
uk Atrr uo
T1
Ti
For the third term, we note that A: Abr u. Thus, have that k2 Almm kF 1|&|12. Substituting this into the expression, we get that
Xest - W Wist Xest 3( wiist
wusst
T1
Noting that Xtst = Orstwvls we get that
Xist WXst = X1sr (1- 133--1
6% |111
T1
To simplify the constants, we note that T1 = 82
||661 - B8. Thus, we get that
Ti 3 82 0
|t| |||1111
Ti
For the case when Nrr < M, we note that the first term of W is the same (modulo replacing t for 72) it is for the when 1. Thus, we just need to deal with the last term. Here that the last term is
Pi Seo |12 us un
72
Here we note that = (I Atr Al. ). Thus, in particular, s is the projection of onto the kernel of A Thus, we have that + 8, where & 8. This then tells us that 8f ||s||2 Thus, for this term, we get that it is equal to
h ||
Xest-
For this term we note that T2 = f + 8 1 |u| Thus, doing the same simplification as before, we see that for the case when Nen < M, we have that
8
Xist W WXss
Xest-
T2
In light of Lemma 2 and the fact that [[xesll] 0 We see that if we look at the expected MSE, we have that.
Xtet
W(Xest + Arse))
1
E
Neat 02 +
W
Nest
M
16

---

Under review as a conference paper at ICLR 2022
where 7; depends whether 1 or > 1.
Finally, let us look at the ||W|| term.
Lemma If 3 + 0 and Aer has full rank, then we have that if < 1,
0 Pn 3 of
03 |
0 |t|| r
| I| =
Tr(h" h) +
Trih K- Alra))
)
Tr((A F kkk? Alrr)
and if > then we have that
0 82
|/ 03 Tr(h" h)) +
0 |||||* Tr(ss").
|
Tr(h" 5") +
2
2
-
Proof. To deal with the term Tr(WTW) we are again going to have to look at whether Newn is bigger than or smaller than M. First, let us start by looking at the case when Nern > M. Here we have that
[ 1|3
Tr(W"W)
(000) (trn
0 1012
( (Otrm
0g Orrn 11112 whi Abrr
Tr
uh +
uk?
Atrm
uh +
T1
71
TI
TI
0 p 8²
|t||
Otrn l|tll*
Tr(h" u² uh) +
Tr(h" ut uk Almn) +
Tr((A ku uk? T Atrn)
82 Tr(h h) +2 0
03
||t|13
0 0tlllell+ Tr Al..) +
Tr((At k Alrn).
rf
Where the last inequality is true due to the fact that ||/]122 = 1. How about when Neen < M. Then we have the following string of equalities instead.
|| 12
WW)
(errB wh +
8 @e us"
1irn3 uh + Pern 11/112 us
Tr
0g 82
uh) + Orrn 1 Tr(h. (Fuh)
0g 1/
Tr(h? us" (FuuT) +
Tr(su us²)
T2
7p
0
0 |11133
Tr(h 5J) 01 |11ll1 Tr(ss
Tr(h h) +
T2
B.4 STEP ??: ESTIMATE USING RANDOM MATRIX THEORY.
Lemma Suppose A is by g matrix such that the entries of A are independent and have mean O, variance 1/g, and bounded fourth moment. Let W, = AAT and let W AT Let = p/q. Suppose Xp, Xg are random eigenvalue of Wp, Wg. Then
1. Pf q, then E
T-c + o(1).
Ap
2. lfp 4 then F.
X7 (I- + o(1).
3. Pf 4 then E
(--C + o(1)
XT
1 C2+220+1
4. If < q, then
+ (1). (1-C)
A
5. Pf q. then
1
I + o())
G-1
A
6. 1f > 4, then E
n-C-1- + (1))
6-2
X
17

---

Under review as a conference paper at ICLR 2022
(140
7. If q. then
X (1-C 175 + o11)
X (C 24 20 ++))
8. 1f > 4, then E
(1-0-ly + o(1)
Proof. Suppose is an p by matrix such that the entries of A are independent and have mean variance 1/g. and bounded fourth moment. Then we know that W, AA is by Wishart matrix with c = C. we send q to infinity such that p/g remains constant, then we have the eigenvalue distribution Fp converges to the Marchenko Pastur distribution F in probability.
From Rao & Edelman 2008), we know there exists a bi variate polynomial L(m, 2) = cam2 (1 such that the zeros of L(m, 2) given by [(m()), 2) are such that
m
m(z) / -
1 dF
Ex
For the Marchenko-Pastie distribution, we have that for O, we get that m(z) = 1/(1 - c). Thus, for Ap is an eigenvalue value Wp. we have that
E
+ o(1)
For Ex
1
we need to calculate m'(0). Using the implicit function theorem, we know that
[)-2)²
m m'(z)= - =1=)=-1[ -1 (m{ (m(2);²)
0L
OL (m( ()n(2),0 2))
3m
Oz
Here see that aT//0m 2czm + + 1. Thus, (1/(1 c), 0), this is equal to 1. Also 0T./O= = cm3 + m. Again at (1/(1 - (). c).0) this is equal to (1-c}z + I-c (1-c)7- Thus, we
c
have that
1
m (0)
(1 c)3
Similarly, using the implicit function formulation, we can calculate m0 and m m0)
On the other hand if < p. then W,, := A is not Wishart matrix here, because it is scaled by the wrong constant. However, multiplying it by 1/C gives us the correct scaling. Thus, ATA/C C' is Wishart matrix with 1/C Thus, for Xg is an eigenvalue value of Wg. we have that
C-1 --
E
d(1). +(1)
Agg
We obtain the rest in similar manner from the previous results.
Lemma 6 Suppose A is p by q matrix that satsifies the standard noise assumptions. Let x, be unit vectors p and dimensions. Let = p/g. Then
1. EETT(= (AAT)(z))
T- - o(1) q C-1
p<q
p
p1-C-r
+ o0)
p>q
[- +
p<
2. (AA")
(1-C 1F +o(1)
2-2
p>q
1
+ +1(
p<q
3. EATTH" A\t))
1-
+
o(1) p>q
y c-- + o(1) p<g
1
()* 4. E(TH(y (AT)) A)ta) (ATtv)))
--C-- d(1) p>q
0-2
18

---

Under review as a conference paper at ICLR 2022
Proof. Let A = UEVT be the SVD. Then have that (AAT)1 U(E))UTT Then since A is bi-umitary invariant, we have that U is a uniformly random unitary matrix. Thus, a = x"U is uniformly random unit vector. Note with probability 1, the rank of A is full and that the non-zero eigenvalues of A and AA are the same.
If p q. then have that
P Σ
(AA))
a
i=1
Using Lemma 5 we have that [B(1/]] = CC +()) Thus, we have that
(TTra"(AA"")aa) Σ カ +
1
On the other hand, if > q. from Lemma we have that = o(1) Thus,
"TTT"" - +o(1)
Similarly, if we had we looking Tr(a" (MA=" would have 1/1 term instead. Thus, p < g. we would have that
(AA") = (1 (1- + +
A similar calculation holds for the others.
Now we have the following Lemma in the main text. However, here instead of having one big proof, we will separate each term out into its own lemma.
Lemma
7 If Asrn satisfies the standard noise assumptions, then we have that
oi [moz[M,NNen]ll + o(1).
1. 3 1 o(1) and Var(B)
(2 + c)
2. Ifc < 1, then [|]]/|?]- 1-c o(1) and Var (ar(11 = Nim c)3 + +01).
2 - 1)
3. Ifc > 1, then E ||[
c-1 o(1) and Var( [|]|])=
c
Nerac 1)3 + +0(1)
c2 + t())
4. ||][|||9
1 + o(1) and Var(1]k|
M(1 c)3
5. |||||||| =
+ o() and Var(Il>|13) = Mc
+ o1)
6. ||||+ = 1 - c + o(1), Var(1 = 22 c
+ o(1)
N
Lemma 11. term
Proof. First, we calculate the expected value of 3. To do so, let Arm UEVT be the SVD. Then since A is bi-unitarily invariant, we have that U, V are uniformly random unitary matrices. Since u, Vtrn are fixed. We have that := off V E Ntrn and b ;= UTu RM are uniformly random unit vectors. In particular, we have that [[a,]] = 0, [[, = 0, Var(a,) = 1/Nern, Var(b.) = 1/M.
Thus, if or are the singular values for A then we have that
MainM.Nasr
8 = 1 Otrn
Σ
0 b.b.
Thus, you take the expectation you get that
| 1.
19

---

Under review as a conference paper at ICLR 2022
On the other hand, lets look at the variance. For the variance, need to compute E[39). Now if let ter u. Then have that
g 1+ + 2T.
Thus, again if we take the expectation, we get that
R R = 1 RT
Again due to the fact that a, are independent have have mean entries, the cross terms in E Thus, we have that
min (Nrr))
min( (ern)
B[T2] = Atrn 2
Σ
Btrn 2
E
Σ
MNtrn
2
Now we need to case on whether MM q M and Nten-
Nen or Nten- Now to use Lemma 5
we note that
Suppose we have that M Ntrns then in this case, we have that q > p. Thus, we have that
= 1 +o1),
where C = =p/q= Nern/M /M- = 1/c. Thus, we have that
E
1
=
+ +o(1)
c
+
o(1)
1
1/c
c-
Thus, we have that
E[T 02
c
+
M(c 1)
M
Thus, we have
1
Var(B) o
M(c
M
On the other hand, if M Norn- Then have that q < p. Thus, we have that
C-1 - o(1)
where C' = cpppqq Ntrn/M 1/c. Thus, we have that
E o
1-c + o(1)
Thus, we have that
( c
+ +((1)) = Nem (1 c) to
I
BiT = 8zn Ner
Nern
1--c
Thus, we have
Var( O7 Nern (1 - c)
+o
Ntrn
Lemma 12. |[Al[ term.
Proof. We want to do a calculation similar to that Lemma 1 Here we have that
||al| Tr(hh h) Tr((Atrr)) "arn
of up Atry) Tr(už At Atrm (A vern)) Tr(ritm (AT Atra)) vern).
20

---

Under review as a conference paper at ICLR 2022
To use Lemma we note that A Afra q M, Nern Let us now suppose that M < Nirn Then again taking the expectation, we see that
[[||||]]=
c (1-c Ntrn
M
6² 1 - +0))
For the expectation of ||A|| let Atr UEV' be the svd. Then h= = vfrn VELUT Let = vtmm V and note that a a uniformly random unit vector. Thus, we have that
M
|| =
For the expectation of ||A|| note that
M
|b]
ΣΣ
Σ
0
ifj
Taking the expectation of the first term, we get
ΣE
M
E Bla
N trn
3M
(1 cI-
+ +((1)
= =3
Ner (1 - c)3 + o(1).
e
1=1
Taking the expectation of the second term, we get
(M
B[aq]² 1M-1) 1
(1 c1- + +(11)
c²
ct
Non (1 -1- +o(1.
e²
Ntrn
(1 c]-
Thus, have that
+ (2
B[|A|]
= (1 c)2
Nern (1 - c]3 + +0(1)
Thus, the variance is
Var(I1h|13= = c² cc)
Nin (1 - c]3 (1).
For M > Nern we instead have that
|[[lb||]= Ntrn
c- + t
c- +1)).
Norn
For the expectation of ||Al| we note that
New Nern
Nern
Σ 1
|
0 +
03
of
($)
Taking the expectation of the first term, we get
Nirn
3Nrrn
G
Bla
(c (c-18 1)3 + =01))
3
Ner (c 1)3 + o(1)
N2
trm
Taking the expectation of the second term, we get
62
Nern Nern(Nen
1)E
Bia = Nern (Nemn
1)
(c- 1)2 + o((1)
N2
trn
o²
à²
Norn (c 1)3 + o()).
(c 1)2
Thus, we have that
c²
2
(2c
|||||| = 1)2
3
Nir(c- - 1)2 +o(1) = (c-1)²
+ +0(1)
Neracc- 1)3
New (c - 1)3
Thus, the variance is
c2 + o(1)
Var(116]13)
Ni 1)3
21

---

Under review as a conference paper at ICLR 2022
Lemma 13. || term.
Proof. First note that & only appears in the formula when e < 1. Thus, we can focus on this case. As with h, we have that
| = Tr(u" (Atrm) Alr, - -Tr(u' (Aern Yen)
Again using Lemma 6 with y = M,P = Nerns A y = u. Thus, since we have g = M < Ntr we get that
E B||
1 - + o(1)
To calculate the variance, need to calculate the expectation of ||]|*. Here be again let A UEVT be the SVD. Then let == UTu u. Then we have that
M
|
2
1=1
Thus, see that
M
|||||
+
Σ
o.
b963.
ifj
Taking the expectation of the first term we get
M
3x²
M (1
c)3
M(1 c)33
Taking the expectation of the second term get
M(M 1)
M
c)
(1-c) c)
M(1 c)2²
Thus, have that
c2 c))
|||
+ o(1).
(1 c)2
M(1 c)3
Thus, we have that
(2)
Var(1|+|1))=
M(1 c)3 + o1)
Lemma 14. || term
Proof. First, we note that only appears when M > Nirn Thus, we only need to deal with that case. For this term, we note that (I-Atr Atr is projection matrix onto uniformly random M Nyr dimensional subspace. Here be again let A UEVT be the SVD. Then let = U u.
Narn 1
|||||||
EluJ u² A A u0
E
x
IN 0
0
0
=
M
=
Similarly, we have that
Nern b2
||s||
Nern
Nirn
1+
62
2
New
Nyn
New
1
61
6²b33
- 2
b2
1=1
22

---

Under review as a conference paper at ICLR 2022
Taking the expectation, we get that
Ner
Ntrn
Ntrn
B
-|||||-1=1
=1+3
=
+
2
M
2
M
1=1
1=1
3
Ntrn
N
-
1)
=1+
cM
M
3
1
+
2
cM
6²
c.
cM
Thus, we have that
Var(I|s|13) =2 1
c.M
Lemma 15. ||t||2 term.
Proof. First, we note that only appears when < Ntw. Thus, we only need to deal with that case. For this term, we note that (I- Alr is a projection matrix onto a uniformly random Ntrn M dimensional subspace. Then similar ||s ||s we have that
Ts
0
1 = -
|| Elv? Vtrn T Alro Aem Vtrnl
E 1 -
T
0
0
Ntrn
Similarly, we have that
M
2
||0|
1
2
f=1
M
2
M
=1+
2
2
1=1
9
070
{
i=1
Taking the expectation, we get that
M
M
M
-
3
2
i-1
trn
N2
trn
iml
Ntrn
3c
Ntrn (N -1)
+
2c
Ntrn
M
1 + Ntrn
3c
+ 2
c
2c
Ntrn
(1 c)² +
c.
Thus, we have that
Var(I1(/3) = c
Ner
Now we could just use the the fact that [ do this is via using big O in probability. Which is defined follows:
E|] < (Vr((X)aar()) Another way to
23

---

Under review as a conference paper at ICLR 2022
Definition 1. We save that sequence of random variables X,, is Op(a,). there exists N such for all e > O, there exists a constant such that for all n 2 N, we have that Pr||Xn] >> Lan] < c.
Then the trace terms.
Lemma Under standard noise assumptions, we have that
E[Tr(h² R2T Alra)l =
and
Var(Tr(h"k" Xa(c)/Nerns
where
Xa(c) B[1/A3], À is an eigenvalue for AAT and A is as in Lemma
6
Proof.
First we note that
Tr( Afmn (r((Atrn)
" Vtrn (A ((r)) n (A (A Atrn)" Vttr))
Again let Aen UEVT be the SVD. Then, we have the middle terms depending on Aer simplifies
(Atrn) TT A -(())
Thus, again letting 6 == u and a = VT Utrn. We see that
M 1
Ca.b
agb
Now take the expectation, since a, b are independent and mean O we see that
E [Tr(hT Atr)) 0.
Let us also compute the variance. Here have that
M
ETTTCTT A Σ
[[a]] +
Now for the Marchenko Pastur distribution we have that the expectation of 1/13 x3(c). where X3 some function. Thus, have that
1
E Tr(h KJ At
Xx(c) + o(1).
Nern
Lemma
Under standard noise assumptions, we have that
c²
Tr((A),m))) kkT Alon) Rkk" (1 c1- oo)
and
d
Var(T)((A)),.))) T Atrn)) M x(((c) M c)6
where (4(c)= E[1/>*] X is an eigenvalue for AAT and A is as in Lemma
6
Proof.
Now using Lemma 6 we see that
à²
E Eeern ( A!rmm]] (1 c1-
Similar to proofs before, we have that
M
X((c) + Σ 1 d
3
E (Tr((Atra))
TKk At Atmm FF
Σ
M2
+ o(1)
M c)6
i41
24

---

Under review as a conference paper at ICLR 2022
Where Xa(c) [[[/X*] for the Marchenko Pastur distribution. Thus, have that
e²
Var(Tr((AAom)) Alrnn) M xa(c) + M (1 - c) + o(1)
Lemma 10 Under the same assumptions as Proposition 2 have that Tr(h² sT) 0.
Proof. Here we note that h²" = (AArr)) vern and S = u² Ammntrrn) Thus, we have that Veen Tr(h"'s 5²) -Tr((A)mm) )² "ernut (Atrm) (aan)"'vre "eraau (ArraAlon)
Tr(ufrn Abm Tr(u" (A (Arrn (Alon) P vtra)
-Tr(Vimn -Tr(ufn Arn Atrn
Tr(ufrn A Afr, Ar(virn//on Almu
0
As see that if take the expectation of ||] over Agrns since the variance of each of the terms small, we can approximate E. XY] with E [VE Then we get the following.
If M < Nerns have that
02
c
04 (1 c)² c
E E [|[
+
(1 + 0% c)²
(1 c)
(1 + 02
c) (1
c)3
fm 8
(1 + 0) () -1
On the other hand, M > Nerns we have that
02 trn
04
e² c-1
E A... [||
C
fm
02 tmn
12
(1
0 Prn
)
(c 1)2
Opr (1 0frm)
(1 + 0rrn)
Orn
+ Oz C
Now combining everything together, we get that
6r
2² t.
Aeen
1|st
W(X,st + Asst)l
Nod 11
c)z
+
37 [1+0
c c1-1-
c<1
Nis
82
8²
C>1
Nec
(1+0 km
2
M 1+0 tmn
c-1
B.5 PROOF OF THEOREM
We that the main text has how put all of the pieces together to prove the main Theorem. We don't replicate that here.
B.6 FORMULA FOR Óapt-trn
As stated in the main text, we only need to take the derivative. So, we don't 't present that calculation here as it is fairly straightforward.
C
GENERALIZATIONS
In this section discuss possible generalizations of the method.
25

---

Under review as a conference paper at ICLR 2022
C.I HIGHER RANK
Let us present some heuristics for the higher rank formula. To do so we shall need some notation.
Let Xtrn
-Ei= 0f (u Let A be the noise matrix. Then for 1 S j S r, define
A
ot u (
We shall now make some assumptions. Specifically, we assume that ujs of and A, are all such that for i o i2, and for all j we have that
Elu A,4/una E(( AfA 0.
Additionally, we assume that for all i1, i2.j we have that E[((!T")TAA A/Juual = We also assume that the variance of these terms goes 0 as Ntrn; M go to infinity.
Lemma 16. With the given assumptions, we have that for all j. 0, us un ) A} " (ut AJ_1 ss of u.(o A} R of " (t. (rim))
Proof. Write Aj- = Aj-1 + u (y( (z and the use Meyer 1973 to expand the pseudoinverse
of Aj. When we do this, we see that due to the assumption all terms expect of uy (utrn) small.
A
A/_1 are
Define h = (ofm)TTA) A}, K = o A.r.rnAA......... tj (1 AA]A). 8j = -, AJAJ.us
8g = 1 0f tr (nt ) Aluu. o = |1,111111111 + 88. 12 = ||s,11211bl1 + B3. and similarly
(1) (1)
Pi P2 911 and 42 Now, we can write
Xum + tr (u. u + Ar-1
Then have that
W X(o (u (T + A,)*
oi trn u ( (o Up u (ut Ar)
Expanding and using the lemma, we get that
Ei= grn ()) uhts + (eleell
uik! A
c <<
W
tm (u
E uhs + (0
(1)
U
c>1
Where the second equality comes from the rank results.
Now that we have an approximation for W (given our assumptions). we can now approximate the variance and bias terms again. Let W, denote the ith factor (corresponding to u,) of W. First, for the bias, due to the orthogonality of the u's we get that
Σ
|xtst W WX
of (of W, Σ
u
F
Again, using our assumptions, we see that the terms the j summation dropout besides when j = i. Then again using rank 1 result, we get that
Xest - Wi
Σ 1=1
8
tst o
For the variance, we again estimate the norm of W by expanding the trace. Here we see that the cross terms are 0 due to factors uf,, Uig. For the diagonal terms, we again use the rank results and get that
Tr(aT h2) +2 (o.mm)3111:113 (7
(oM"AAI (7
TrCKT
Tr( TT((A)) TA A!)
(7 (7
26

---

Under review as a conference paper at ICLR 2022
and if 1, then we have that
(o )2
Tr(hi sf) + (1bil) Tr(s;ss)) /2
|W
Tr(hTh,)
(rg))2
The final step would be estimate each of these terms using random matrix theory. However, unfortunately the Aj may not satisfy all of the needed conditions. However, we know that Aj is perturbation of A and A satisfies all of the needed conditions. Hence, if the perturbation is small, we can replace Aj with A and hopefully not incur too much cost. Note this is also the reason why the previous assumptions might be reasonable. If we replace Aj's 's with A use our estimates from the rank result. We then get our estimate for the generalization error for general rank data.
((Otrno) (fern +0(1)
R(Orrns Orees C, Etens Enst)
Nes + (Oemn 200 M(1 + (0mm fro (r) - 0)
(12)
and if > 1, we have that
(Otncofat)
c(ternormy fra)a
R(O tear e, Eern, E(st)
+ Nist + of M + (f (c- + o())
i=1
(13)
In the experimental section, we see that for small values of for bounded away from 1. This seems be good estimate for the generalization error.
C.2 RANDOM FEATURES MODEL
Here assumed that data is given X UEVT. One generalization of this that we have G who entries i.i.d Gaussian, or whose columns are uniformly distributed on the unit sphere. Then for non linear function σ, we assume that X oGUEVTT). If we assume that linear, the we have that as L + o0, GO IM. Thus, we have that GU approximately satisfies our assumptions of orthogonal columns. Hence we expect our formula to still be reasonable approximation.
D EXPERIMENTS
Please see accompanying notebook for code produce the data for all of the figures.
D.1 Low SNR AND HIGH SNR DATA
For low SNR data, we sample the 0 times singular values from squared standard Gaussian. We do this independently for all 2r singular values. We call this the low SNR region because not being scaled with the number of data points. Hence as Nirn; Nest cc, the SNR goes 0.
For the high rank data, we sample 9 times singular values from a squared Gaussian and then multiply by Nirrs /N Hence here the SNR does not go to 0 N Nist -
27

---

Under review as a conference paper at ICLR 2022
E GENERALIZATION ERROR VERSUS TRAINING NOISE LEVEL PLOTS
E. MORE TESTS FOR RANK I
Here we provide more examples of c and how our theoretical formula matches the experimental performance exactly.
Each empirical point is the average over 50 trials. These were run on a laptop with 8gb of RAM and an i3 processors. The average time produce any of these plots is about 10 to 30 minutes.
Thra and
7427
Exrron aind
4x20
Tura tut
099
63R
6.8
518
012
414
090
609
823
5.08
$13
612
034
859
234
(a) C
(h) c= 0.5
(c) c = 0.9
Opona
Oceaal
Impiria lestt
Irpainal
2+
(d) 2
(e) 10
(f) c 2, Pest = 0.01
Figure 8: Figures (a) (e) showing the accuracy of the formula for the expected mean squared error for c 0.1, 0.5, 0.9, 2, for fixed value of &tot Figure empirically verifies the existence of regime where training on pure noise is optimal. Here the red and green lines represent EE and E trm. respectively. Each empirical data point averaged over at least 50 trials.
E.2
RANK DATA
Let us now demonstrate that the double descent shaped curve exists beyond rank data and linear autoencoders. We will do this by gradually making the set up more complicated until we can no longer recreate this phenomena. First, we consider rank data of the following form. Let Wanta be some fixed matrix, then our data is generated by
X rer DeeLu(Waaareelffee
Where a different v is sampled for the training and test data. the results for this can be seen in Figure g As we can from the figure, we have the exact same qualitative trend for that saw before. That is, goes from 0 to 1, we have that 6.., goes from d to O, and then as > we have that 0,r goes to infinity as well.
E.3 MNIST DATA
We now look at the linear network with MNIST data.
E.3.1 NON-LINEAR NETWORK
Here, trained each network for 1500 epochs. During each epoch computed gradient using the whole data set. We used Adam as the optimizer with the code written in Pytorch. Each data point was generated over 20 trials.
28

---

Under review as a conference paper at ICLR 2022
C004
(a) 0.3
(h) 0.5
(c) 0.9
(d) -=
(e) c 10
Figure 9: Rank
Nom 5000
PMIIS DUAM
4.00
140
0.04
(b) 0.16
(c) 0.784
700
Nin
Nim
0N2
480
0m
3
Reatsader
430
(d) 1.12
(e) 3.92
(1) 39.2
Figure 10: MNIST
These experiments take a little bit more time to run and the one with bigger amounts of data can take upto 5 hours on a google cloud instance with 16gb RAM. Here we used Telse P4 gpu.
LRL is a model with reLU at the end of the first layer only.
29

---

Under review as a conference paper at ICLR 2022
10
Tate
(a) 0.261
(b) 0.784
(0) = 1.12
03005
EOROL
COROO
500
034
6.0
0.30
034
052
034
0200
0.4
055
622
630
(d) c = 1.57
(e) C 3.92
Figure 11: MNIST LRL model
30


Reviews:
[{"review_id": "vhhZII_dPVV", "reviewer": "Reviewer_5V96", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "**Writing and flow:**\n\nOverall the writing and flow of the paper are good. What is being done is clear and makes sense. This is great and a strength.\n\n**Assumptions and model:**\n\nThe assumptions (e.g., noise statistics) and model used are all reasonable (strength).\n\n**Introduction:**\n\nThe introduction has good logic flow and is easy to understand the intuition and motivation behind the paper, which is a strength. The authors do a good job explaining their points. I especially found it interesting the idea that, if double descent depends on the number of samples, that datasets may be unfortunately placed at the peak without our knowing.\n\nNow for a few weaknesses. The intuition that noise regularizes is useful but not absolutely accurate. If I am not mistaken, please correct me if I am, additive noise only regularizes in a supervised setting with small noise amplitude (Bishop, 1995). Thus, the claim, which is made in the first paragraph of page 3, that more regularization via adding noise doesn’t remove the double descent shape is a weak claim because adding lots of noise may not actually be equivalent to regularization. \n\nAlso, the figure labels on Figure 3 are extremely confusing and the axis labels are so small that I can’t really make out what Figure 3 is actually saying. Figure 4a is good but Figure 4b is confusing. The caption says that the plot is of training SNR and the axis label says it is a ratio instead. \n\n**Related work:**\n\nThe related work section is very small and needs to be expanded in order put the author’s contribution into context. This is a weakness.\n\n**Theorem 1:**\n\nTheorem 1 is great and the section is well written. The only confusing part for me is how “The $o(1)$ error term goes to $0$ as $N_{trn}, M \\rightarrow \\infty.$”? This mean that the error term depends on $N_{trn}, M$ and hence is not constant, i.e., $o(1)$.\n\n**Section 3.1:**\n\nThe implications of Equation 7 are very interesting to me and I think this is a great contribution because it is non-intuitive. \n\n**Section 3.2:**\n\nAs mentioned above, saying that you have “optimal regularization” because you pick the optimal amount of training noise does not make sense because they are not equivalent if the noise variance is too large. In fact, you can actually see no double descent if you just set the noise variance to 0. This is a weakness of the paper.\n\n**Experiment and conclusion:**\n\nThe experiment section is very short and there is no conclusion, which makes the paper incomplete. The conclusion section is important but most important is the experiment section. The results for MNIST are quite interesting actually but there isn’t much detail in the paper describing them, which is unfortunate. There is some information in the appendix, but it should be described in the original paper. Some of the figures can be removed to make room for it, in my opinion, such as Figure 1 and 6. ", "summary_of_the_paper": "In this paper, the authors study overparameterization of autoencoders in terms of varying sample size. They derive an analytic expression for the bias-variance decomposition of the loss for a bottleneck of size 1. Furthermore, they approximate the bias-variance decomposition for larger bottleneck sizes. This is done with all linear networks. They experimentally show double descent in nonlinear networks as well.", "summary_of_the_review": "**Strengths:**\n\nThe paper shows a novel result: the bias-variance decomposition of the rank-1 linear denoising autoencoder. This introduces some interesting new concepts, such as optimal training SNR as compared to test SNR. The paper is clearly written and is easy to understand. In addition, the authors find an approximation to the bias-variance decomposition for bottlenecks of larger size than 1.\n\n**Weaknesses:**\n\nThe others equate adding noise and regularizing the model, which is not equivalent if the noise variance is too large. If they want to make statements about regularization, then they should explicitly regularize and see what happens. If the results are similar then even that is convincing, even if it is empirical. Moreover, some of their figures are hard to read and interpret. Finally, the authors leave out most of the details regarding the experiments and completely omit the conclusion.\n\nOverall, I based my score on the fact that the paper is incomplete and rough, not because the work has major problems. This is very interesting work and should be polished before next submission.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "qOmwhrZPCH", "reviewer": "Reviewer_dPcd", "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": "I think the topic of this paper is interesting. I like the result that the optimal amount of noise in the training data is not equal to the noise level in the test data. The following are some detailed comments.\n\n1. Authors claim that the noise in the training samples can be controlled. That is misleading. Actually, we can enlarge the noise by manually adding more noise into the training data, but we cannot reduce the noise. A related question is whether Eq.(7) suggests that we can actually get a better result by adding more noise to the training data.\n\n2. The explanation of the double descent with respect to the number of training samples is not satisfactory. Eq.(3) and (4) only suggest that the error has a peak when $c=1$, i.e., when $N_{trn}=M$. It only implies that when N_trn increases, the error will increase to the peak in the region $N_{trn}\\in (M-{small\\ value},M)$ and then decrease when $N_{trn}\\in (M, M+{small\\ value})$. Maybe it will be clear to see the monotonicity by doing the derivative of Eq.(3) and (4) with respect to $N_{trn}$.\n\n3. How does Theorem 1 compare with results about double descent in other literature? For example, is the descending speed with respect to the number of training samples characterized by Theorem 1 similar to that in the existing literature?\n\n4. In Eqs. (3)~(7), N_tst, M, and c appear at the same time. Since c=M/N_trn, maybe it is a good idea to replace M with c*N_trn.", "summary_of_the_paper": "This paper considers a denoising setup for a linear model. Compared with the traditional supervised learning setup where the noise is added to the output, the denoising setup has noise in the input. The authors provide an asymptotically exact formula for the generalization error for rank 1 data and an approximation for higher rank data. Both the theoretical and numerical results validate that the generalization error has a peak when the number of samples is equal to the number of features, which is consistent with existing literature about the double descent phenomenon. Authors also derive a formula for the amount of noise in the training data for the best generalization performance, which leads to a novel conclusion that the optimal noise amount in the training data is not always equal to the noise level in the test data.", "summary_of_the_review": "This paper is a good paper with novel results in the denoising setup, yet some places can be made clearer.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "N6obxJ87Whe", "reviewer": "Reviewer_f7hC", "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": "Strengths: The paper investigates a novel double-descent phenomenon as a function of the number of samples for the denoising task. The authors make a large variety of experiments and investigate the phenomenon from different angles (i.e. neural networks, real-world datasets, etc). \n\nWeaknesses: I found the paper structure confusing. The introduction takes 3.5 pages with many figures already presented before introducing the concepts. I would recommend moving Figure 1 or making it substantially smaller as the comparison between (a) and (b) can be made with such little effort (with some equations or a smaller figure). I was confused by what M is in Figures 3 and 4 which is introduced much later. The paper does not have a conclusion part. \n\nRelevant work:\nOn page 2, I found that the citations are centered around Nakkiran et. al.'s work unfairly. Note that sample-wise double-descent is also studied in d'Ascoli et. al. 2019 (https://arxiv.org/pdf/2006.03509.pdf), Adlam et. al. 2020 (http://proceedings.mlr.press/v119/adlam20a). I see that these works are cited but I think these should be presented already on page 2 where sample-wise descent is motivated. \n\nMoreover, for the double-descent and asymptotics of random features, the following works should be cited as well in the related works section on page 4: Jacot et. al. (http://proceedings.mlr.press/v119/jacot20a.html), Mel et. al. 2021 (https://proceedings.mlr.press/v139/mel21a.html).  \n\nTypos: \n* page 4: U \\Sigma V^T: T should be removed. also in many other places, there is some confusion on transposes.  \n* Figure 7 caption: for the our formula -> remove the", "summary_of_the_paper": "The paper investigates a new double-descent in denoising task for linear predictors. As the number of samples increases the denoising loss exhibits a peak in the case of linear predictions, but the peaks are less pronounced in the case of neural networks, except for the case with rank 1 data. The authors calculate an asymptotical formula for their special rank-1 data model in theorem 1 which proves the explosion at (c=1). For the arbitrary rank data, the authors present an approximate formula too. ", "summary_of_the_review": "The paper proposes a low-rank data model and studies the double-descent phenomenon for denoising tasks. The main theorem presents an asymptotical formula for the risk for rank 1 data, and also approximate formulas for the general rank cases are presented. The theory is presented for the linear case, whereas the experiments cover also neural networks and MNIST. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HCrltmYBLhz", "reviewer": "Reviewer_yBGu", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strengths:\n1. Double descent has been observed in various contexts and it's an interesting and important question to understand it thoroughly. While previous work only focused on supervised learning settings, this paper considers a denoising setting instead, which is a reasonable first step to consider in the unsupervised space.\n2. The paper gives an answer in the rank-1 case in terms of the double descent phenomenon wrt the training data size. There is also some interesting characterization of the optimal SNR.\n\nWeaknesses: Overall, this paper is not well written and needs significant improvement. There are a lot of things not explained clearly, and it's very difficult to follow the paper. Below are some major questions/issues.\n1. What are the scales of all the relevant quantities in the main result (Thm. 1)? Which are considered constants and which grow with $N, M$? This needs to be explained clearly.\n2. The data model setup also needs some more explanation. It's assumed that $V$ has orthonormal columns. Why is this a reasonable assumption? This assumption means that the datapoints are not independent, which makes it unrealistic for statistical learning.\n3. The rank-r result is not explained clearly. It is claimed that formulas (5) and (6) are \"approximations.\" In what sense are they approximating the true risk? What does it mean to \"assume that $A_j$ has similar spectral properties to $A_{trn}$\"?\n4. Even the introduction section is quite chaotic. There's first some motivation and an overview of the type of results in the paper (which is itself somewhat confusingly written), and then suddenly at \"contributions\" it goes back to the motivation again...\n5. At the bottom of page 6, it is claimed that picking the optimal training noise would not prevent double descent, in contrast to other results showing that optimal regularization prevents double descent. What about other regularization? This doesn't seem to rule out the possibility that other regularization can eliminate double descent.\n\nMinor points: \n1. It is claimed (page 3) that a 2-layer linear network model is considered. However, the model is just a usual (1-layer) linear model, not a linear network.\n2. In the setup (Section 2 beginning), $V\\in\\mathbb{R}^{r\\times N}$ should be $V\\in\\mathbb{R}^{N\\times r}$?\n3. In \"contributions\" (page 3): \".... focus on representation learning...\" I don't think there's any representation learning aspect here.", "summary_of_the_paper": "This paper identifies and studies a double descent phenomenon (wrt the training data size) for a denoising problem, where the goal is to recover a low-rank ground truth given a corrupted version of it (with added full-rank noise). The paper considers the linear regression estimator, and gives the exact formula for the test risk in the asymptotic regime for the rank-1 case; for a general rank r, the paper also gives a formula, but it's not entirely rigorous. Furthermore, the paper also studies the role of the training and testing SNRs.", "summary_of_the_review": "This paper extends double descent (wrt data size) to a low-rank denoising setting with linear regression. While the result is novel and has some interesting aspects, many aspects of the problem and the results are not clearly explained, and the writing overall needs significant improvement.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a theory for double descent phenomena in denoting deep neural networks. There are two major concerns: (1) The assumption that the data lie in a low dimensional subspace is quite strong, and needs to be weaken or better justified. (2) The theory only works for r=1, where the rank is one. For general rank, how to apply the proposed analysis is hand wavy and not convincing. The paper can be significantly strengthen if these two issues could be addressed.
Decision: Reject