Training Data Size Induced Double Descent For Denoising Feedforward Neural Networks and the Role of Training Noise
Authors: Rishi Sonthalia
Raj Rao Nadakuditi
Venue: Accepted by TMLR ()

Abstract: When training an unregularized denoising feedforward neural network, we show that the generalization error versus the number of training data points is a double descent curve.
We formalize the question of how many training data points should be used by looking at the generalization error for denoising noisy test data. Prior work on computing the generalization error focuses 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. 
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. This results in the emergence of a shrinkage phenomenon for improving the performance of denoising DNNs by making the training SNR smaller than the test SNR. Further, we see that the amount of shrinkage (ratio of the train to test SNR) also follows a double descent curve. 

Published in Transactions on Machine Learning Research (04/2023)
Training Data Size Induced Double Descent For Denoising Feedforward Neural Networks and the Role of Training Noise
Rishi Sonthalia
rsonthal@math.uclu.. edu
Deportment of Mathematics
University of California, Los Angeles
Raj Rao Nadakuditi
rajiarao@humichh edu
Department of EECS
University of Michigan, Ann Arbor
Reviewed on OpenReview: https: // openreview. net/ form/f id- id=FdWttpVTS VTII
Abstract
When training an unrogularized denoising foodforward noural network, we show that the generalization error versus the number of training data points is a double descent curve. We formalize the question of how many training data points should be used by looking at the generalization error for denoising noisy test data. Prior work on computing the generalization error focuses adding noise to target outputs. However, adding noise to the input is more in line with current pre-training practices. Tn 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. From this, we derive a formula for the amount of noise that needs to added to the training data to minimize the denoising error. This results the emergence of a shrinkage phenomenon for improving the performance of denoising DNNs by making the training SNR smaller than the test SNR. Further, we that the amount of shrinkage (ratio of the train to test SNR) also follows double descent curve.
1 Introduction
Denoising noisy training data is a widcly used technique for pretraining networks to learn good data representations. 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 problems, we work at large scales in terms of the mumber of parameters and the number of training samples. Recently there has been significant work in understanding the effect of scaling the number of parameters in neural network. This resulted in the discovery of the much celebrated double descent phenomena (Belkin et al., 2019). However, we have a weaker understanding of the effect of scaling the number of data points. Classical works such as Krogh Hertz (1991); Geman et al. (1992); Opper (2002) and more recent. work such as Gerace et al. (2020); Nakkiran et al. (2020); Nakkiran (2020); d' Ascoli al. (2020); Adlam Pennington (2020) show cither empirically or via thcoretical analysis that sample wise double descent exists. However, these were in the regime of supervised learning. On the other hand, motivation comes from understanding denoising neural networks. For MLM and SDAEs, denoising is pretraining procedure, in which case the generalization error would depend on the downstream task. As a first step, we shall instead look at the generalization error for denoising test data. The difference between the prior supervised learning setup and our denoising setup can be seen in Figure 1.
To understand the denoising setting, we empirically show that samplo-wise double descent exists for denoising feedforward neural networks (Section 3). We show that shrinking the training data Signal Noise Ratio (SNR) (i.e., increasing the amount of training data noise) for fixed test data SNR can mitigate this double

---

Published in Transactions on Machine Learning Research (04/2023)
Output
Learnt Model
X
1
Input
Output
Model
X
Input
+
Noise
θ
Ntrn
Generating
X
Model
Output
Input
Model
Input
Output
Noise
+
Target Output
Output
F
Denoising Loss
Loss
(a) Denoising Setup
(b) Supervised Learning Setup
Figure Figure showing the difference in the noise placement between the traditional supervised learning setup for which empirical and theoretical double descent. curves have been found versus our denoising setup for which we recover double descent curves.
descent. Moreover, show that the curve for the ratio of the best training data SNR to the test data SNR also has sample-wise double descent (Section 3). To theoretically understand the phenomena, at the simplest setting. Specifically, we look at the case when we have one-layer linear network, and we are denoising data that lies on line embedded in high dimensional space (Section 4). In this setting, we derive the exact asymptotics for the generalization error (Section 5). We show that the generalization error and optimal training noise level spike at the interpolation threshold. From the theoretical analysis, we see that the spike occurs due to the variance of the model increasing. We use the rank one result derive an approximation for general (low) rank data.
look
Contributions.
The main contributions of the paper are as follows.
We empirically show that when denoising data using a foodforward network, the curve for the generalization error versus the number of training data points Ntrn and the curve the ratio 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. Thus the noise level acts regularizer.
2. Assuming we have mean zero, bounded variance, and rotational invariant noise, we derive an analytical formula for the expected mean-squared generalization error for denoising data that lives in a one-dimensional linear subspace by a linear model. Further, we use the same method to present a heuristic for higher-rande rank data and experimentally determine the formula's accuracy for general low-rank data.
We show that sample-wise double descent exists for the generalization error and the amount of noise that should be added, even in this simple model.
1.1 Related work
Understanding deep neural networks is a currently active area of research with many exciting theoretical results. The discovery that fixed depth infinite width (under certain limits) neural networks can be thought of as kernel regression (Jacot al,, 2018) and the discovery of double descent for neural networks (Belkin et al., 2019) has sparked significant. research into understanding the generalization error in the linear regime
2

---

Published in Transactions on Machine Learning Research (04/2023)
(in parameters, not inputs). The exact asymptotic for the generalization error was first understood for ridge regression (Bartlett et al., 2020; Hastie et al., 2022; Belkin et al., 2020; Advani & Saxe, 2020; Mel & Ganguli, 2021; Dobriban & Wager, 2018). Following this, many papers have studied the situation for the Random Features model and the Neural Tangent Kernel (NTK) model (Jacot et al., 2020; Mci & Montanari, 2019; Ghorbani el. al., 2021; Adlam & Pennington, 2020; Geiger et al., 2020). Other recent work for supervised learning includes work on multiple descents (Derezinski al., 2020; d' d'Ascoli et al., 2020; Liang et al., 2020), transfer learning (Lampinen & Ganguli, 2019), and Gaussian mixture models (Loureiro al., 2021). However, to our knowledge, there has yet to be any work that looks at the problem for the denoising setup.
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 a revolutionary paper, Krizhevsky et al. (2012) showed that augmenting the dataset with noisy versions of the images greatly improved the accuracy. Another area where noise is useful is adversarial lcarning. Dong et al. (2021) shows epoch-wise double descent. for adversarial training. In recent theoretical work related to SDA Es, Pretorius et al. (2018) 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. Gransambandam & Chan (2020) looked at the problem of determining the optimal amount of noise that should be added. However, they studied this from the perspective of minimizing the variance the generalization error.
Additionally, there has been significant progress in understanding the Bayes optimal solution when denoising via matrix factorization (Lelarge & Miolane, 2017; Lesieur et al., 2017; Maillard et al., 2022; Troiani et al., 2022; Nadakuditi, 2014). It is important to note that these works do not think of the noise as regularizer and do not consider the effect of noise on parametric models such as neural networks.
2 Problem Set Up
Our goal is to understand the impact of training noise on the generalization error in the context of denoising neural networks. Concretely, suppose we have access to noisy data y1,-.. MN., RM such that Vi Itsr2; &s, where z, E RM is sampled from unknown data distribution D, & R M is sampled from some noise distribution Droise, and Otst E IR is known scalar which controls or models how noisy the data is. We study the classic denoising problem of recovering 2, from ys (James & Stein, 1992; Wiener, 1949; Banham & Katsoggelos, 1997; Benesty et al., 2010; Takeda et al., 2007; Buades et al., 2005). One approach to solving this problem is to learn a function that removes the noise from a set of examples, for instance, using a neural network (Tian et al., 2020). To this end, suppose the noise distribution Daoise is known, then given noiseless data x²" ...., , we can create noisy versions 3 OrrnzK + efra of our training data. Now consider neural network denoted f, which is trained to minimize the following Eg loss function
Nin
trn)
|
tra
f(fern
frm + 112
(1)
Ner
We are then interested in the following mean squared generalization error.
Nest la
1(0ist + 112
(2)
The major question we want to answer is the following. Given noisy test data, such that Best is known, what is the optimal value of 6m such that neural network trained using the loss function in Equation 1, minimizes the generalization error in Equation 2? We are also interested in the effect the number of training data points N has on the optimal Own-
3

---

Published in Transactions on Machine Learning Research (04/2023)
2.1 Signal to Noise Ratio (SNR)
A quantity of enter to us will be the SNR. To properly account for this, if Patta is the expected norm of the data points and Proise is the expected norm of the noise vectors, then we shall call
OeruPdata and Oiot= = Oest/idato
eer
Pnoise
Unoise
to be the training and test data signal to noise ratios.
3
Empirical Double Descent
10
d=
Gecensbatton
Doveritutttnoo
10.
23
20.0
15.0
275
500
10"
112
2C- Wemo
LCC- RERCM
(a) Rank 1 Data
(b) Non Linear Synthetic Data from a layer teacher network.
(c) MNIST
4x10"
mate ou
e
2xte
(d) Rank 1 Data
(e) Non Linear Synthetic Data from 2 layer teacher network.
(f) MNIST
Figure 2: Figure showing the empirical double descent phenomena for the generalization error versus 1/C (Number of training samples Ntrn /number of features M). The top row is for lincar (with respect to the inputs) network, and the bottom row is for a three-layer ReLU network with width equal to the dimension of the data. The networks were trained with the mean squared denoising error. Here the training data SNR. and the test data SNR both equal 0. The solid line in Figure (a) is our theoretical line from Theorem
We run two experiments better empirically understand the interaction between Ozees Nir, Orn and the generalization error (Eq. 2). First, we show that sample-wise double descent occurs for denoising neural networks empirically. That is, if we fix Cern, then as we vary Nern, we get that the Nir versus generalization error curve has double descent. Second, we explore the role of the amount of training noise and show that optimally picking Own can mitigate the previously seen double descent.
3.1 Double Descent for Denoising Networks
For our first experiment, we show that the Nist versus gencralization error curve has double descent in simple cases. To do this, we Irain two leedforward networks (one-layer and three-layer) on three different. datasets. The first data set is a line embedded in high-dimensional space. The second data set is a synthetic dataset using a teacher network. That is, the data is generated by sampling latent variables from a Gaussian distribution and then using the outputs from a randomly initialized untrained 2-layer neural network as our data. Finally, the third dataset is MNIST
4

---

Published in Transactions on Machine Learning Research (04/2023)
Figure 2 shows that if we train (one-layer and three-layer feedforward network to denoise data such that the training data signal to noise ratio (SNR) 0yr is the same SNR as that of the test data set (Otac), then double descent occurs in the curve for the denoising generalization error vs. the number of training samples. However, unlike other hyperparameters, such as the number of features and the number of training epochs, we cannot arbitrarily change the number of data points as we are limited by our data set. Hence it could be the case that our maximum number of data points corresponds to the peak of the generalization error curve. To get around this, we can look at the amount of noise we add to the training data. Note that we could have also added other forms of regularization, but the noise level is a natural hyper-parameter here.
3.2 Role of Training Noise Level
To see the effect of training data SNR Oern; for variety of different ratios 0grn / we compute the denoising generalization error versus the mumber of data points curve. Figures 3a and 3b show that if we optimally pick the ratio fest/ then double descent can be mitigated. We do this for the MNIST and CTFAR datasets. We create test data by taking the test data for each and then adding Gaussian noise. We fix the test SNR Orst to be 1 for both datasets. Hence we know the test data SNR. We then lake various different fractions of the training data and train a three-layer ReLU neural network (without bias) for various levels of training data SNR Ow.. For each pair of parameters (number of training data points and the level of training noise), we compute the generalization error averaged over twenty trials for MNIST and five trials for CIFAR. Here the test noise and training noise are resampled for each trial. The plots for the generalization error can be seen in Figures 3a (MNIST) and 3b (CIFAR10), and the plots for the optimal ratio can be seen in Figure
We see five interesting and exciting phenomena from this experiment."
1. For most values of the ratio 0tst/Oern: we see sample-wise double descent for the generalization error.
2. We see that the optimal denoising error does not occur when the train SNR is equal to the test SNR. We need to shrink the train SNR (i.e., increase the test to train SNR ratio). This shrinkage reminiscent of other shrinkage phenomena such as James & Stein (1992); Tibshirani (1996);
Nadakuditi (2014).
3. As seen in Figures 4a and 4b, the optimal ratio depends on the number of data points.
4. Figure 4 shows that the curve for the best 0 also has sample wise double descent.
5. Picking the optimal amount of noise can mitigate sample-wise double descent of the generalization error. This mitigation is reminiscent of how optimal regularization can mitigate double descent in the supervised setting (Nakkiran et al., 2020).
We postulate that spike in generalization error is due to the variance of the model increasing. Hence when we increase the amount of noise, we implicitly regularize the model (Bishop, 1995). This increased regularization results in decrease in the variance and improves the generalization error.
4 Theoretical Problem Assumptions
To be able to provide theoretical understanding of the five phenomena discovered in Section 3, we consider a simple model that can be theoretically analyzed.
4.1 Assumptions about the data
First, we detail assumptions about the data generation process. Specifically, we assume that the data lies in some low-dimensional linear space.
Assumption 1. Let U E Mxr such that the columns of U have unit norm and are pairwise orthogonal. To generate data, we sample latent variables VT E BR and Σ E Beer such that V has columns that have unit norm and are pairwise orthogonal and Σ is a diagonal matriz with non-negative entries on the diagonal such that || | = Then a data matrix X, which each column is a data point, given by X UEVT.
I Ottee forms regularization could remove some of these features. However, we look the effect. of the level of noise by itself.
5

---

Published in Transactions on Machine Learning Research (04/2023)
20.0
1.5 x
35
10"
Optimal
17.5
10x
Generaltzation Error
3.0
Generalization Error
15.0
1.05 x
25
ppn
0mm
10
10-a
Past
0at
20
95x
-15
5.0
9x10-1
10-4
25
10
2
0.0
0.5
10
1.5
2.0
25
NtmrM
Ntrr/M
(a) MNIST
(b) CIBAR
Figure 3: Figure showing the empirical denoising generalization error for a three-layer neural network with the width the same as the dimension of the data trained for various different values of 0 and number of training data points. Each neural network was trained for 1500 epochs, using MSE loss and gradient descent with a learning rate of 10-3. For MNIST, averaged over twenty trials, and for CIFAR1O, averaged over five trials.
20.0
17
17.5
Tain SNR/ Test SNR
16
Tain SNR/ Test SNR
12.5
10.0
5.0
25
10-2
10-1
10P
1/C = NtmmMM
1/C NtrnM
(a) MNIST
(b) CIFAR
Figure 4: Figure showing the sample-wise double descent for the empirically optimal amount of training noisc. The figure displays the ipli Otat/rrn ratio seen empirically versus 1/c= NtenMM. The ratios plotted here correspond to the ratio for the red line in Figure 3.
Hence, we see that we generate data that lives in a dimension subspace. Note that we make no assumptions about the distribution of the latent variables or Σ. We have two matrices, X Xten and X Xtats corresponding to the train and test data sets. Hence we have corresponding VT, E RexNNee VT E Rrx RestNest and Etrn. Enst- We make no other assumptions on U, Vtrns Eren Vistz Enst-
4.2 Assumptions about the noise
Nexi, we detail our assumptions about the noise added to the data. For that, we need the following definitions.
Definition 1. A matriz Z pmxx sampled from distribution is rotationally bi-invariant if for all orthogonal Un Rmxm and all orthogonal U2 E Raxn, UUZU, has the same distribution Z.
Another way to phrase rotational bi-invariance is VAEAVT is the SVD, then UA and VA are uniformly random orthogonal matrices and are independent of ΣA and each other.

---

Published in Transactions on Machine Learning Research (04/2023)
Definition 2. Let (0, be shape paramter. Then the Marchenko Pastur distribution with shape is the measure Pe supported on [e-, where C₁ = + vc)2 is such that
(1 y
do +u c>l
Me
c cs1
where has density
dv(x))
V(c - x)(x c_).
2nxc
With these definitions, we have the following assumptions about the noise matrices Atr Aest- Assumption 2. Let A E RMN such that A is sampled from a distribution Dooise such that
1. For all i,j, Droie [Aij] = =0
2. For all i, DDnou [AZ]] = 1/M.
3. For all i,, i1, and je such that i & is or 51 # j2, we have that Anjs and Absja are uncorrelated. That is, [ Aizial = ED,osso [Ai (Aizial
4. A is rotationally bi- bi-invariant.
5. With probability 1, A has full rank.
Assumption 3. Suppose M.N is a sequence of matrices that satisfy Assumptions such that M, N + oc with M/N c. Let XM ..... min(M be the eigenvalues and let PM.N = E, 6,M.. be the sum of dirac delta measures for the eigenvalues. Then we shall assume that μMMN converges weakly in probability to the Marchenko-Paste measure Pe with shape c.
X
M
From here onwards, we shall suppress the superscripts. While such assumptions on the noise may seem restrictive, this encompasses large family of noise distributions that include Gaussian noise.
Proposition (Proof in Appendix A). If B is random matria that has full rank with probability and its entries are independent, have mean 0, have variance 1/M, and bounded fourth moment, and P, Q are uniformly random orthogomal matrices. Then A = PBQ satisfies Assumptions 2 and 3.
Note that when we sample matrices as detailed in Assumption 1, we have that ||Xerall [|atell = 1. to account for this, let fts 0tn E R., be scalars that will scale the norms of Xtrns Xest so that we can control the SNR of the matrices.
Assumption 4. We assume that Ostt is fized and known and that we have control over Ownn.
Given data Xtrn, Xest satisfying Assumption 1, noise matrices Arm Ara satisfying Assumptions 2, 3, and Own, Bist that satisfy Assumption 4, then noisy data is given by Yum OvrnXenn Airo and Yist Oist Ats-
4.3 Assumption about the Model and Training Algorithm
Finally, we shall make assumptions about the donoiscr f from Equation 1.
Assumption 5. We shall assume f is linear model W that is the solution to the following least squares problem.
minw [10trnXenn W (0rmnin + Atro)
(3)
Yera
That is, given data Xtrn that satisfies Assumption 1, noise matrix Aurn that satisfies Assumptions 2, 3, Iern that satisfies Assumplion 4, and noisy data Ytrn OwrnXrm Atra, have that f(x) Wa: Otrn X yt trm.. T.
7

---

Published in Transactions on Machine Learning Research (04/2023)
Here for matrix T, I is the Moore-Penrose pseudoinverse. Note here that not assuming access to the denoised test data. We rewrite Equation for this denoiser and data generation model.
Oest (1ss Asst
Reest-error = ALA Atst
(4)
Nest
Remark 1. We analyze this setup instead of the standard Gaussion or Spherical data model since if both our data and noise are isotropic, then the denoising problem can be degenerate. Hence we assume that our data has a low rank.
Remark 2. While many double descent analyses look at the role of ridge regularization, in this case, since we are looking at the denoising setup, we look at the role of the amount of noise. However, our method con be adapted include a ridge regularizer. Note that Bishop (1995) shows that adding noise the input is equivalent to Tikhonov regularization.
4.4 Signal to Noise Ratio (SNR)
A quantity of interest us will be the SNR, given by || | Hence, we need normalize everything by ||||-- Due to assumptions, have that [[[[A|]] N. Hence, for any variables and constants, if it. has hat, then that refers to that variable constant normalized by VN. For example, given Itrn Xtrns and Arn, then we have that Oren
Otrn
Orn =: Pwrn-
|
|errll
VNim
5 Theoretical Results and Consequences
In this section, we analyze the model presented Section 4. The main theoretical result of the paper is sum- marized below in Theorem In Theorem 1, for 1, we exactly characterize the asymptotic generation error. 1 and c= M/Nten be fired. Let W be such that satisfies Assumption 5 for training data Oerns X Ytrn that satisfy Assumptions (1-5). Further suppose that θtrn is O(VNoru)- Then for test dala Orst; Xtst, Yest that salisfy Assumplions (1-5) such that Orst is O(vNest the mean squared generalization error (Equation 4) can written as follows. If < 1,
Theorem 1. Let
02
02 Nest
(0 ((mm)
Rrest-error
+ 0
+
(5)
Nese11 02
6)3
M(1+
02 Om
c)a(1 -c)
M
and if 1, have that
82 Riest-error Nis (1 + Og 1
@2 Nest
ca2
0
+
M(1 + 0gn
trn
( 1)
+o
M
(6)
The
62 Nest
o (++) error terms go as Nevn: M 20.
Theorem is only for rank one data. We do not have the exact generalization error for general low-rank data. consider the heuristic formulas in Equations 7, 8.3 Here, the ith term in the summation is the rank one formula for the rank one matrix dunny corresponding to the 8th singular value d, Here u, are the ith singular vectors.
However,
((0rmoo) trn + (Bernofrn))) + o(1)
(7)
Nest (1 + Pe
M(1 + (Oem of 2c) c)
(Otsr0f0t)2
M(1 + (Oer of frm (c + o
(8)
N1s + (tenofrnyzy
28cc Appendix B for details. More details for the heuristic be found in the Appendix D.I. Here provide assumptions under which this reasonable formula.
8

---

Published in Transactions on Machine Learning Research (04/2023)
01
011
02
0.10
02
0.
03
06
04
0.
0.08
04
05
06
0.4
NtnM
07
08
Enror
NtrrMM
08
07
Relative Error
0.
-0.06
09
11
11
12
12
13
14
04
13
14
15
15
16
16
17
0.02
17
18
18
19
19
2.0
2.
2
3
10
20
50
100
150
200
250
1
5
10
20
50
100
150
200
250
(a) Low SNR
(b) High SNR
Figure Figure showing the accuracy of the heuristic formula for low rank matrices. The figure shows the heatmap of the relative empirical error (jtrue generalization error predicted generalization errorl/ true generalization error) when changing and the rank of the data. Here M = 2500 and e is changed by changing Now. We average over ten trials for low SNR, and for high rank, we average over 100.
Before proceoding, we exporimentally determine the accuracy of our formula for general rank r data. To do so, we calculate the relative error. That is, if the empirical generalization error Remp and
theoretical predicition is Raheory: then calculate |Remp- Rtheory! Here for low SNR (0tm Oest O(1)),
[Rempl
sample "fTh o I.LD. from the squared standard Gaussian and for high SNR, multiply the previous by VNtmn, /Nsst (Bern: Pest are O ((vNrr)), (VVNss)) As can see from Figure 5, our formula is accurate for low rank data where we have relative error of around 0.01. However, we see that the approximation breaks down for higher rank data, especially near c=
5.1 Data Distributions
While Theorem is only for rank 1 data, the current setup has some general components. In particular, it shows the surprising result that there can be two different types of mismatch between the training data and the test data that do not affect the generalization error.
Noise Distribution Mismatch. The first lype of mismatch corresponds the distribution of the noise. Besides the general assumptions on the noise distribution, we note that the distribution for the entries of Aten and the distribution for the entries of Arst need not be the same. Our only restriction is that Atr and Aest satisfy
noise distribution assumptions independently. So, for example, Theorem would apply if we have that the entries of Atr are T.I.D. Gaussian with mean and variance 1/M and Atst is sampled by sampling P, Q uniformly from the space of orthogonal matrices and sampling B with L.LD, entries uniformly on 1-V6/M, V6/M] (so that entries have mean 0 and variance 1/M) and setting A PBQ.
Data Distribution Mismatch. The next type mismatch concerns the distribution of ((trn) and ( In particular, we are not assuming that they came from any distribution, just that they satisfy certain assumptions.
In the rank one case, note that due to assumptions, must have that ot a that our tth training data point is given by UVten where U is the fcature vector and V is a latent scalar variable. Hence in such a setup, we can imagine the entries of ytrn and Viat being drawn independently from some distribution. The only assumption we need to account for is that |||*r|| = || = 1. To account for this, suppose we first sample entries of Vitn in an L.I.D. manner from some distribution D that has mean and variance and that the entries of tisst are sampled from some distribution Dist that has mean and variance 1. Then if Ne Nest large, then due to the law of large numbers, have
Thus, we

---

Published in Transactions on Machine Learning Research (04/2023)
that with high probability Nern || + o(1) Nest || Thus, if we let Vin || ||
Vim
and Vlat Viat with Bern = Cernl/itrml and Deer = Beer |V || then we see that the Vs satisfy
V
the general assumptions and with high probability the Os satisfy the assumptions for Theorem 1.
5.2 Insights and Phenomena
7-
Generalization Error
0.04
3-
0.02
1
0.00
0.
0.5
10
1.5
2.0
25
30
0.0
0.5
1.0
1.5
2.0
2.5
30
M/Nttm
(a) Rank 1 Theory Generalization Error
(b) Rank 1 Thhory Test SNR / Optimal training SNR.
Figure 6: Plot showing the thcoretical double descent curves for the generalization error and the ratio of the lest SNR to the optimal training SNR. Here M 1000 and Ozst = and e was changed by changing Ntrn-
Now that we have Theorem 1, we extract a few insights. Specifically, we are interested in insights in the context of the experiments run in Section
5.2.1 Optimal Amount of Noise.
If we ignore the error term, we can differentiate the formula to get the following formula for the optimal training SNR. Here ++ = max (0,
02 2(1-c)
+
02
c<1
opt Spt--rn trn
Nest 2-0 (22-o)
N
2 Ci
(c 1)
e>1
Nest
Neen
Our theoretical model captures the surprising result that the optimal training SNR and the test SNR are unequal. Moreover, we see that the optimal training distribution depends on c. Further, the formula in Equation 9 also describes double descent curve for / @ versus curve shown in Figure 6b. Thus, see that our model captures phenomena 2, and 4 from Scction 3.
5.2.2 Double Descent Curves.
We have already seen that the optimal amount of training noise follows a double decent curve. This double descent is due to the double descent for the generalization error. To understand this phenomenon, first note that the first term gives the bias of our model in the formula in Theorem 1, and the second term gives the variance. We is the interpolation threshold (i.e., the point after which we have O training error). Hence, as we approach the interpolation threshold, the model's variance increases, increasing the generalization error. Thus our model captures phenomenon 1. Further we can see that decreasing 6yrn decreases the model's variance. Since the variance increases near the interpolation threshold, we try to mitigate this by incrcasing the amount of noise (or reducing 9.rn). Hence sample wise double descent for the optimal noise level occurs result. of trying to reduce the variance of the model. Thus, model captures the first. four phenomena
that the variance formulas have singularity at 1. Since have linear
model,
10

---

Published in Transactions on Machine Learning Research (04/2023)
Decompose into Bias and Variance
Derive a formula for W
Best Aest Xest
W W 11: + Eest [|[ Arst
Cern uh + Pr 11411 01
ukk A
e<
W
Oton uh + o 1Al1 T 0
us
c>
Variance
Estimate trace terms using Random Matrix Theory
Expand bias and variance into trace terms
(AA")(
+ - +o() p>q
p<9
0 B2
0 1rr.1 Tr h) +
04 hh]l Tr(h" 57)
Tr(ss))
T
12
2
Figure Figure showing the major steps used derive the formula for the generalization error.
observed in Section 3. Phenomena from Section 3 was that optimally picking the amount of training noise mitigated double descent. However, our theoretical model still has double descent even if we optimally pick the amount of training noise. This avenue for future work.
We also compare Theorem to Theorem 1 from Hastie et al. (2022). In Hastic et al. (2022). they assume that they have data 2; R M from some distribution D, and response y; = x! B + Es. where B E R M is fixed and & ~ x(0, Then they have the following risk
(x; D x00 (
This is the conditional excess risk given the training data. Under some assumptions, they show that
Rx + JoR
c<1
c>l
First, we note the similaritics between the two. In both cases, we see that the peak at c and is due term of the same order, i.c. both have (c - 11 and not 1)-1)-a for some other a >
However, there are differences. First, detailed in the introduction, they look at the supervised setting, whereas we look at the unsupervised setting, Second, they have input noise, whereas we have output noise. Third, they have zero bias in the under- pademeraaaetteized regime. However, we have non-zero bias term in both the over and under-parametent
regimes.
5.2.3 Noise a Regularizer.
Finally, we see that noise level explicitly regularizes [[]] Specifically, from Lemmas 1 and 3, the second term in Theorem 1 corresponds to |[W]|=- The formula shows that increasing the amount of noise, which corresponds to decreasing itmn, decreases ||W]]..
6 Proof of Theorem
We prove Theorem via the steps shown in Figure 7. The proofs for all of the lemmas have been moved Appendix C. Here we present a proof sketch that details the high-level ideas.
6.1 Step 1: Decompose the error into bias and variance terms.
First, we decompose the error. Since we are not in the supervised learning setup, we do not have standard definitions of bias/ variance. However, will call the following terms the bias/variance of the model.
11

---

Published in Transactions on Machine Learning Research (04/2023)
Lemma 1. If Aest has mean 0 entries and Asst is independent of Xtst and W, then
EA..lllltst WYalll PistBAnn Xtst
W Wetelll
E Ae W Ata 1
(10)
Bios
Variance
6.2 Step 2: Formula for W
In our current setup, W is the solution to a least-squares problem. Hence W = Oern trn tra Expanding this out, we get the following formula for W. Let be the left singular vector and vern, Uest the right singular vectors. Let & = vtrn A k = A U, (1 A t = -Urn (1 Alrn B = 1 + Oven A Alrn U, Ti = 66 || + +38, and T2 o (r..]|s|||| ||]| + +
Vt
fera uh + P2 I|cll2 ukt A
c<1
Proposition 2. If 3 +f 0 and Aurn has full rank then W
Bern uh + Pe 11ll1 us c>
For Gaussian noise, Atr has full rank with probabilily one, and 3 is random variable whose expected value equals 1, and the distribution is highly concentrated. Thus, Proposition 2 applies when Arn is isotropic Gaussian noise. Here we restricted ourselves to rank 1, as using Meyer (1973), we can expand formulas of the form (A + yy")² where z, are vectors. For the higher rank case, we apply the formula iteratively. This is the main difficulty of the method. Previous work on deriving asymptotics for the generalization error had noise on the output. Hence would take the pseudoinverse of a matrix that only depended on the data. However, in case, are taking the pscudoinverse of matrix that depends the noisc.
6.3 Step 3:
Decompose the terms into sum of various trace terms.
For the bias and variance lerms, we have the following two Lemmas.
B Xest Xia
if <
Lemma If is the solution to Equation 3, then Xest W Xtst
if
Lemma 3. If the entries of Aest are independent with mean 0, and variance 1/M, then we have that BA..[[/WW A [ Sx
Note that this did not need assumptions on W or Xtst- All that was needed were the assumptions on Asst- Thus, this holds more generally. This decomposition also follows from Bishop (1995). In light of Lemmas 1, 2, 3, and the fact that || lB 63 that the expected mcan squared gencralization error is given by,
11sestXsst
WY tst 1
82 0 + +
1 M
EA
E
|W]
Nest
Nest
where T; depends on whether a or c> 1. Finally, let us look at the ||W]] term.
Lemma 4. If 3 + 0 and Atrn has full vank, then we have that if c<l,
| 8 32 Tr(hT h) +
82 2B Tr KTT KT Atr))
t ||t|
Tr((A "okk Alr.)
2
and if c > 1, then we have that
02 32 Tr(
03 + fmm
|11113
0f |1/l1 Tr(ss*)
| 2
TT +
T2
6.4 Step 4:
Estimate using random matrix theory.
While the formula given by Lemmas 1, 3, and correct, we need simpler formula analyze the situation. Using ideas from random matrix theory, we can simplify the expression for [[] To do so, we first need prove Lemmas and 6. The main idea behind Lemmas 5 and is that due to the rotational invariance of A
12

---

Published in Transactions on Machine Learning Research (04/2023)
the expectation of the trace of products of various matrices derived from Aer is determined by the expected value of some function X of the eigenvalues of Atr- However, instead of directly computing this expected value, we note that for any matrix A that satisfies the noise assumptions, if we let M, - x0, with M/N + c, then the cigenvalue distribution converges to the Marchenko Pastur distribution (Marcenko & Pastur, 1967; Götze & Tikhomirov, 2011; 2003; 2004; 2005; Bai et al., 2003). Götze & Tikhomirov (2004) showed that the distribu- tion of the eigenvalues converged almost surely with rate of least O(N-1/2+)) for any c > 0. Thus, we can use the expected value of the x()) for À sampled from the Marchenko- Pastur distribution as an approximation.
Lemma 5. Suppose A an p by q matriz such that the entries of are independent and have mean 0, variance 1/4, and bounded fourth moment. Let Wp AAT and let W, = A. Let C p/g. Suppose Xps >g are a random eigenvalue of W Wg. Then
If < q, then E²
b 1-o + (1).
5. 1f p > q, then E
C-1
o(L)
A
I-
p < q, then
= (I-Ops + (1).
6. 1/p> > q, then E
[I-C-PP + ol).
C-2
p
3. p < q, then
= -- + (1)).
7. 1fp> q, then E
3-111+111
+ o())
X
(1-0-13
0a +++1
t0 2 +
4. 1f < q, then EE
(1-Cy ol))
8. 1f > q, then E o(1)
11-C
Lemma 6. Suppose A is an p by a malria such that the entries of are independent and have mewn 0, variance 1/q, and bounded fourth moment. Let C = p/q and let x, y be unit vectors in p, then
+ o(1)
1. B[TM)"(AA"))
p<d
1 ---0-T +
2. B[TH> (AA")"
(1-0) +(1
p< q
c- P + o(1)
p>g q
Using these technical lemmas, we can now deal with all of the terms in the expressions in Lemma 4. Lemma 7. Tf Atrn satisfies the noise assumptions, then have that
1. B[3/0mm]] = 1/0trn + o11) and Var(8/0emn)= [max M, M,N + o1)).
4. [[[K][]] I-c + o(1) and Var([|+|13)
c(2+c)
2. If c < 1, then ||[|/|| = c²
M(1 c) c)3 +o(1)
+ o(1 and
1-c
5. E[[|s = c-1
(2 c)
+ o(1) and Var(I|s|13)
Var(11//33 Nern (1 c)3 + o(1)
2 1
Me o()
3. If > 1, then | c-1
+ o(1) and
6. |[[|||]
e o(1), Var([lu]33 = 2 Nern
Var(11h/33- = 22cc-11 - + o(1.
o(1).
Nc 1)3
Lemma 8. Under the noise assumptions, we have that W[TT(TTK' RT Atr = 0 and Var( TT(h"TThhh KT Alrmn) = xs(c)/Ntrn, where Xa(c) = E[1 X is an eigenvalue for AAT and A is as in Lemma Lemma 9. Under the noise assumptions, we have that
à T TikT A (1- + +o11), Var (ar T TkkTat = x((c) M (1 - c)6
3 M
1 c²
where Xa(c) [E[L/*), X is eigenvalue for AAT and A is in Lemma 6.
Lemma 10. Under the same assumptions as Proposition 2, we have that Tr(h 5²) 0.
Lemmas 7, 8, 9, and 10 tell us that all of the terms are highly concentrated. Thus, even though such terms may not be uncorrelated, we can use the fact that [[[XY] - [[X] ( VVar())Var(Y), to treat the terms
13

---

Published in Transactions on Machine Learning Research (04/2023)
if they are uncorrelated. Since these variances have now been shown to be o(1), we have that for each of these terms [X[XY] B[
For example, since = + [412]1=]]++((1))) using Lemmas 1, 4, and 6, we have that E[Ti] = 1+ 1+0 c+)( Similarly, E|m]] = 1+0 +o(1). Finally, using these lemmas, we can simplify the expressions in Lemma 4 to get the formulas for the expected generalization error shown in Equations 5 and 6.
7 Conclusion
In this paper, we switch focus from a supervised setup to an unsupervised setup. Specifically, we look at the problem of denoising data. We empirically show five interesting phenomena our given setup. First, we see sample-wise double descent for the generalization error for denoising feedforward neural networks. Second, we see that, under certain circumstances, the optimal denoising error does not occur when the training data SNR is equal to the test data SNR. Third, we see that the optimal ratio depends on the number of data points. Fourth, see that curve also has sample-wise double descent, and fifth, picking the correct training noisc level mitigates sample-wise double descent of the generalization error. To provide theoretical analysis for this model, we look at theoretical model where our data has low rank. Here we derive the exact asymptotics for the generalization error for rank 1 data and a general noise model. Our analysis demonstrates that this simple model captures most of the phenomena seen empirically.
References
Ben Adlam and Jeffrey Pennington. The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization. In ICML, 2020.
Madhu S. Advani and Andrew M. Saxe. High-dimensional dynamics of generalization error in neural networks. Newral Networks, 132:428- 446, 2020.
Z. Bai, B. Miao, and J. Yao. Convergence rates of spectral distributions of large sample covariance matricos. SIAM J. Matrix Anal. Appl., 25:105 127, 2003.
Matthew R. Banham and Aggelos K. Katsaggelos. Digital Image Restoration. IEEE Signal Processing Mugazine, 14(2):24-41 41, 1997. doi: 10.1 00.119979.581663
P. Bartlett, Philip M. Long, G. Lugosi, and Alexander Tsigler. Benign Overfitting Linear Regression. Proceedings of the National Academy of Sciences, 117:30063 30070, 2020.
Mikhail Belkin, Daniel J. Hsu, Siyuan Ma, and Soumik Mandal. Reconciling Modern Machine-Learning Practice and the Classical Bias Variance Trade-off. Proceedings of the National Academy of Sciences, 116: 15849 - 15854, 2019.
Mikhail Belkin, Daniel J. Hsu, and Ji Xu. Two Models of Double Descent for Weak Features. SIAM J. Math. Data Sci., -111671180, 2020.
Jacob Benesty, Jingdong Chen, and Yiteng Huang. Study of the Widely Linear Wiener Filter for Noise Reduction. 2010 IEFE International Conference on Acoustics, Speech and Signal Processing, pp. 205-208, 2010.
Chris M. Bishop. Training with Noise is Equivalent to Tikhonov Regularization. Neural Computation, 7(1): 108 116, January 1995. ISSN 0899-7667.
Antoni Buades, Bartomeu Coll, and Jean-Michel Morel. A Non-local Algorithu for Image Denoising. 2005 IEEE Computer Sociely Conference Computer Vision and Pallern Recogrilion (CVPR 005, 2:60 65 vol.
2, 2005.
Michal Derezinski, Feynman T Liang, and Michael W Mahoney. Exact Expressions for Double Descent and Implicit Regularization Via Surrogate Random Design. In Advances Neural Information Processing Systems, volume 33, pp. 5164. Curran Associates, Inc., 2020. URL attp:://proceeding..eeee cttppp//000111177700000000777050
14

---

Published in Transactions on Machine Learning Research (04/2023)
J. Devlin, Ming-Wat Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In NAACI, 2019.
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics,
2018.
Chengyu Dong, Liyuan Liu, and Jingbo Shang. Double descent in adversarial training: An implicit label noise perspective. ArXiu, abs/2110.08135, 2021.
Stéphane d' Ascoli, Levent Sagun, and Giulio Biroli. Triple Descent and the Two Kinds of Overfitting: Where and Why Do They Appear? In Advances in Newral Information Processing Systems, volume 33, pp. 3058 3069. Curran Associates, Inc., 2020. URL sttps://procceeings. http:/eedddn..eeeee.....eeeeeeee #F006fffDafffdd400022222aaaaa Paairee-apprr.ppee pdf.
Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' d'Ascoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling Description of Generalization with Number of Parameters in Deep Learning. Journal of Statistical Mechonics: Theory and Experiment, 2020, 2020.
Stuart Geman, Elie Bienenstock, and René Doursat. Neural networks and the bias/ vaarince dilemma. Neural Computation, 4:1-58, 1992.
Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mezard, and Lenka Zdeborova. Generalisation Error in Learning with Random Features and the Hidden Manifold Model. In Proceedings of the 87th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Reseavch, pp. 3452 3462. PMLR, 13 18 Jul 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized Two-layers Neural Networks in High Dimension. The Annals of Statistics, 49(2):1029 1054, 2021. doi: URL https://doi. htttps:/ddi.oor//1... 20114420-A019990
Abhiram Guansambandam and S. Chan. One size fits all: Can we train one denoiser for all noise levels? In ICML, 2020.
F. Götze and A. Tikhomirov. Rate of convergence to the semi-cireular law. Probobility Theory and Related Fields, 127:228-21 276, 2003.
F. Götze and A. Tikhomirov. Rate of convergence in probability to the marchenko-pastur law. Bernoulli, 10: 503 548, 2004.
F. Götze and A. Tikhomirov. The rate of convergence for spectra of gue and lue matrix ensembles. Central European Journal of Mathematics, 16666-744, 2005.
F. Götze and A. Tikhomirov. On the rate of convergence to the marchenko-pann pastur distribution. ar arXio: Probability, 2011.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in High-Dimensional Ridgeless Least Squares Interpolation. The Annals of Statistics, 50(2):949 986, 2022. doi: 10.1214/
wttp///..1///1-...... 1001111/111--02115 21-A052133. URL http:://oo..org/1..11220
Geoffrey E. Hinton, Nitish Srivastava, A. Krizhevsky, llya Sutskever, and R. Salakhutdinov. Improving Neural Networks by Preventing Co-adaptation of Feature Detectors. ArXiv, abs/1207.0588 2012.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In Advances in Neural Information Processing Systems, vol- ume 31. Curran Associates, Inc., 2018. URL https://proceediigg. wtwpiiiins..errrssc.c.oooo neurips. /2///// .ddf.
Arthur Jacot, Berfin Simsok, Francesco Spadaro, Clement Hongler, and Franck Gabriel. Implicit Regularization of Random Feature Models. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4631-46 0641-4640. PMI.R, 13-18 Jul 2020.
15

---

Published in Transactions on Machine Learning Research (04/2023)
W. James and Charles Stein. Estimation with Quadratic Loss. In Breakthroughs in Statistics: Foundations
and Basic Theory, pp- 443 443-460, New York, NY, 1992. Springer New York. ISBN 978-1-4612-0919-55 doi:
30. URL https://doi http://///ii.og/1/0.... 001//00-0077/977----611199999990
Alex Krizhevsky, lyya Sutskever, and Geoffrey E. Hinton. Imagenet Classification with Deep Convolutional Neural Networks. Communications of the ACM, 60:84 90, 2012.
Anders Krogh and John Hertz. A simple weight decay improve generalization. In J. Moody, S. Hanson, and R.P. Lippmann (eds.), Advances in Neural Information Processing Systems, volume 4. SeefcrafffP0001111tffffffteeee pappaar.
1991. URL https://proceedings www.igg...uris.... cc/papprr/199/f1122
Andrew K. Lampinen and Surya Ganguli. An Analytic Theory of Generalization Dynamics and Transfer Learning in Deep Linear Networks. In International Conference Learning Represenlations, 2019. URL
pictps://operrvviie http::///pppaeeeeee.eeeeerrrrtrp 1ett//orrumm/dxxrMMMLCCCCC
Mare Lelarge and Léo Miolane. Fundamental Limits of Symmetric Low-Rank Matrix Estimation. In Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 1297-1301. PMLR, 07-10 Jul 2017.
Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová. Constrained Low-Rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications. Journal of Statistical Mechanics: Theory and Experiment, 2017(7):073400: jul 2017. doi: 00.1088/1742-5445//aaaa777 URL https: happ:://dxxddii / 10. 01188/1142--46//a77777
Tengyuan Liang, A. Rakhlin, and Xiyu Zhai. On the Multiple Descent of Minimum-Nore Interpolants and Restricted Lower Isometry of Kernels. In COLT, 2020.
Bruno Loureiro, Gabriele Sicuro, Cedric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborova. Learning Gaussian Mixtures with Generalized Linear Models: Precise Asymptotics in High-dimensions. In Advances in Neural Information Processing Systems, 2021. URL https://openrevee/ wtwprrreiwweeeeeeouueeerte net/forum?id=
j3eGyNMPvh.
Antoine Maillard, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. Perturbative Construction of Mcan-Ficld Equations in Eetensive-Rank Matrix Factorization and Denoising. Journal of Statistical Mechanics: Theory and Experiment, 0002333, aug 2022. doi: (0.1088/11442-5445/aaaaa 54c////44//c URL
https://dx dxx ww..doi.ooo orgioorg/10 10. 1088 111/1-1422--888 24222-5555///7744 ac7e4c
V. Marcenko and L. Pastur. Distribution of eigenvalues for some sets of random matrices. Mathematics of The Ussr-sbornik, 1:457-483, 1967.
Song Mci and A. Montanari. The generalization error of random features regression: Procise 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 Curves and a Hierarchy of Phase Transitions. In 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 stroce//proceeiings wwwrreceedingg.m...pp.o.m wwt....peee//v1///mmmm222. html.
Carl D. Meyer, Jr. Generalized inversion of modified matrices. STAM Journal on Applied Mathemalics, 24(3): 315 323, 1973. doi: 10.1137/0124033, URL https://doi.org/ 1111100.111111113533
R. R. Nadakuditi. OptShrink: An Algorithm for Improved Low-Rank Signal Matrix Denoising by Optimal, Data-Driven Singular Value Shrinkage. IEEE Transactions on Information Theory, 6005)03002-300 -0188, 2014. doi: 10. 10.1109/TTT. 200.TTTT..011.2116666
Preetum Nakkiran. More data can hurt for linear regression: Sample-wise double descent, 2020.
16

---

Published in Transactions on Machine Learning Research (04/2023)
Preetum Nakkiran, Prayaag Venkat, Sham M. Kakade, and Tengyu Ma. Optimal Regularization
Mitigate Double Descent. In International Conference on Learning Regresentations, 2020. URL https:
Manfred Opper. Statistical mechanics of learning Generalization. 2002.
Arnu Pretorius, Steve Kroon, and Herman Kamper. Learning Dynamics of Linear Denoising Autoencoders.
In International Conference on Machine Learning, pp. 4141 4150. PMLR, 2018.
N. R. Rao and A. Edelman. The polynomial method for random matrices. Foundations of Computational Mathematics, 8:649 702, 2008.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, 1lya Sutskever, and Ruslan Salakhutdinov. Dropout: A Simple Way to Prevent Neural Networks from Overfitting. Journal of Machine Learning Research, 15(56): 1929 1958, 2014. URL http://jmlr org/papers/vvl /ttp///vaaaaaaaaa..... html.
Takeda, Sina Farsiu, and P. Milanfar. Kernel Regression for Image Processing and Reconstruction. IEEE Transactions on Image Processing, 16:349 366, 2007.
C. Tian, Lunke Fei, Wenxian Zheng, Yanchen Xu, Wangmeng Zuo, and Chia-Wen Lin. Deep Learning on Image Denoising: An overview. Neural networks the official journal of the International Neural Network Sociely, 131:251 275, 2020.
Robert Tibshirani.
Regression Shrinkage and Sclection via the Lasso. Journal of the royal statistical society series b-melhodolooical, 58:267 288, 1996.
Emanuele Troiani, Vittorio Erba, Florent Krzakala, Antoine Maillard, and Lenka Zdeborov'a. Optimal Denoising of Rotationally Invariant Rectangular Matrices. ArXiv, Abs/2203.007522 2022.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, and Pierre-Antoine Manzagol. Stacked Denoising Autoencoders: Learning Useful Representations in Deep Network with a Local Denoising Criterion. Journal of Machine Learning Research, 11:3371-340S December 2010. ISSN 1532-4435.
Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. Regularization of Neural Networks using DropConnect. In Proceedings of the 30th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 1058 1068, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
Wiener. Eatrapolation, Interpolation, and Smoothing of Stationary Time Series, with Engineering Applications. MIT Press, 1949.
17

---

Published in Transactions on Machine Learning Research (04/2023)
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 matrir that has full rank with probability 1 and its entries are independent, have mean 0, 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. are a 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 linear combination of entries of where the coefficients (i.e., the entries from P,Q independent of B), have that each entry of B have mean O. Due to the orthogonal nature of P. Q, we have the variance for an entry of A is the same the variance of entry in B.
Thus, the only thing left to prove is that the entries of A are uncorrelated. To do this, we note that
0ij
Pabia
Consider two entries anj and Giajz. Then we have that
E Eliiy Aigizl = E
Σ Σ
ΣΣ
Pig Tra
1=1
Eip IPod Elbb Elqus 9kszl
M
N
Pigl
E
Σ
Thiis Okia
M
The second inequality follows from the fact that P. Q, B are independent from each other, and that fact that the entries of B are independent and have mean O. Hence the cross terms have expectation O. If we have that i i2 and j1 # j2, then we have that since Q is an orthogonal matrix
E Blakj Akial
E
Σ
qhj akjz
0.
Thus, the entrics are uncorrelated. Similarly when i # since P is orthogonal matrix, we get that the entries uncorrelated.
Convergence to Marchenko-Pastur. If we strengthened the uncorrelated condition, to the entries being independent. Then due to the mean and variance assumptions (along with an assumption that the fourth moment is bounded), would have convergence to Marchenko-Paste Pastur distribution. However, the independence along with the bi-invariance would then force our noise distribution to be i.i.d. Gaussian.
In general however, with relaxed assumption of the entries only being uncorrelated, convergence is not known. However, our case, we have a much simpler proof for matrices formed by Proposition 1, In our case, the noise matrices B satisfy the standard assumptions for convergence. We then multiply B by orthogonal matrices that are independent B. Hence this has no effect on the eigenvalue distribution. Thus, the eigenvalues distribution for these matrices also converge to the Marchenko-Paste distribution.
18

---

Published in Transactions on Machine Learning Research (04/2023)
B
Ridge Regularization
Here we are now interested in minimizing
PtenXtr W(OernXern Aerr)l + 1
This problem is equivalent to minimizing
Ovrn [ 0] - W (Oern [Xern 0] + [Arrn x(]
Thus using Aec = noise matrix. Note that Lemma. still applies. As does Proposition 2 but with Åer instead of Atrn and tten has appended zeros. Hence the rest of the proof is similar and we need to look at eigenvalues of AT A Aten instead of Afrn Atrn- Here we note that
[Atrn ATI. This the same problem as before but with different assumptions on the
AT ArAA AtrnAAr + 121.
Thus we have that the eigenvalues are shifted by n²2 We need to explicitly deal with this during calculation and will need to modify Lemma 5, and need to adjust our calculations accordingly.
C
Proofs
Due to our data generation assumptions that [Erra 1 = EEsellr = 1 for rank data, we have that frm = 1 1.
C.1 Step 1: Decompose into bias and Varaince
Lemma 1. If Atst has mean 0 entries and Aest is independent of Xest and W, then
BAuelll1ss WYsed BAn ll Xeet W Xesell
+ E EA W A 11
Bios
Variance
Proof. Using the fact that for any two matrices ||G H1 = ||G + | 2Tr H), we get that
11st WYsst 2 11est Xest W West Xest W Atst
= 2 Xest W Wiseell + | (W 2Tr - W Wost W Atse).
Then since the trace is linear, and Xest, W are independent of Aest, and Aist has mean O entries, we see that
E (Tr((Onst W Wost)Xeat) T W Atst)] = 0.
Thus, have the needed result.
C.2 Step Formula for Wopt
Proposition 2. Let h uf Alto & = Afr, u, = -1 Aer Atrn) u, = Urrn Atrn), B =
+ Oern A u, Og 1| + 82, and T2 0p s ||211| + 32. 1f # 0 and Atr has full rank then
Cera uh + 0 1el2 1|l12
uh* A
c<l
W opt
Ti
Oeea T3
uh
us
c>1
Proof. Let us first proof the case when c >>> 1. Here we know that u is arbitrary. Here we have that Aer has full rank. Thus, since > 1, we have that M Ntrns thus Arn has rank N Thus, the rows of Atra span
19

---

Published in Transactions on Machine Learning Research (04/2023)
the whole space. Thus, Utnn lives in the range of Abr Finally, since 0, we want Theorem 5 from Meyer (1973).
Here let us further define
O |ss12
Atmn Oernk and of Iern ||:l| s h
P2
B
and finally 72 0 || + _8. Then we have from Meyer (1973) that
(Atrn + Olrnuu = Alm + Oer
B
Alouh hht ST
B
72
In our case, only care about uvrn Cnvter(Ater (Aten + Orrnuwtrn).. Thus let us multiply this through and see what we get.
Pern
B
Orrn (Arrn + Oern Oern uo brn (Atm +
Ath ST
p242))
B
T2
OtnB
Orrn s||2
uh
us
Atmil 1TT +
Oernki oz
1
P 111111
0
|||11111111
Utrnth
+
us
uhugz
B
Then we have that
03
||||||11||
04
|||1
03
||ss||
Cq2
us
uh
(11)
52
T2.
T2
and
82 3 whuqh
03 8
1111
P 3
whus? T
uhuh.
(12)
Using that 3-1 Orrn T Almm u ternhu we get that
0 3 whugz
0 [11 1)
0trn - 1)
us²
wh.
(13)
Substituting back in and collecting like terms get that
(1
03 1
B(B -
Orrn Cer ( (Aern Otro " Orrnu
h+
T2
T2
|1A112
02 11 *|1111111
|
02 u
ST
3
T2.3
T2
We then simplify the constants as follows.
02
1212 8(3-1)
0z
B
+
8
T2
T2
T2
T2
and
|
|
||
|A//((B - 1) [11 0 [|mn|s|||[1[11 -63 1)
||
||
T2.3
BTz
.3T2
20

---

Published in Transactions on Machine Learning Research (04/2023)
This gives the result for >> 1.
If e < 1, then we have that M < Nenn. Thus, the rank of Arn is M the range of Atrn is the whole space. Thus, u lives in the range of Aemn. In this case, we then want Theorem 3 from Meyer (1973). In this case, we define
Og || 1t k and of Oern Ovrn|It|2 h² A h.
Then this case, we have that
Alro + Otrn &T
3 A
(Aemn + Oven Ovenuofyn)
PP
B
T
Then we simplify the equation as we did before!
C.3 Step 3: Expand into trace terms
Lemma 3. If the entries of Atst are independent with mean 0, and variance 1/M, then we have that
EA [|[ A ||
Nos Ner ||
Proof. To see this, we note we look A then this M by M, for which the expected value of the off diagonal entries is equal O, while the expected value of each diagonal entry is Nea/M That is, EA
(est Afsa] Mr MM
Then note that
W A1sell Tr(A WT WW(WWWA ATa)
Aest
Using the fact that the trace linear again, we see that
Nest Tr(F"W)
Nist M
E Tr(W" W Atst Aha)l Th(W"WE. A A Ahaa))
|| 1-
M
Lemma 2. If W is the solution to Equation 3, then
8 Xest
if <<> 1
Xea WX
Xest
ifc
T2
Proof. To see this, we have the following calculation when Ner M.
Ownn
P 1012
Xist W W = Xest
uhuutr
uk A uv
Owni ui
0 1t12 ukt Al unta
Xest
Al uote
TI
First, we note that 3 = + Pern o Almm u. Thus, we have that ou At. = 1. Thus, substituting this into the second term, we get that
3(3-1)
02 0tmnl1el12 ukt Alrnuu?
Xast WXet Xest
uois
For the third term, note that k Atrm u. Thus, have that kT Alr u kT ||. into the expression, we get that
Substituting this
3(3 -1
or |1112111:11 wota
Xest West Xist
T uuss
T1
T1
21

---

Published in Transactions on Machine Learning Research (04/2023)
Noting that Xest wist: get that
(1-8(5-1 [(3 -1
trn ||
Xest
Wtst Xist
T1
To simplify the constants, we note that = frrn || + B Thus, we get that
Ti +
8 |t| ||]11
For the case when New M, we note that the first term of W the same (mndulo replacing for 72) it is for the case when >> 1. Thus, we just need to deal with the last term. Here we see that the last term is
0 Scr 1 us ue
72
Here we note that s = -I- Air Arm Amm )u. Thus, in particular, s is the projection of onto the kernel of AT Thus, we have that u = s + 8, where 1 s. This then tells us that sf u ||||? Thus, for this term, we get that it is equal to
8 ||
X
T2
For this term note that - + 6....l1i ( P|]| Thus, doing the same simplification before, see that for the case when Ntrn M, we have that
Xist WXest
X
T2
In light of Lemma and the fact that Neatl? = Obse have that,
We see that we look the expected MSE, we
11a
W(Oret + Acst)ll
B
1
E A
W
Nist
Nest
Est
M
where Ti depends on whether < or e> 1.
Finally, let us look at the ||W]| term
Lemma 4. B # O and Arrn has full rank, then we have that if c < 1,
8 Pr 82 hr( +2 2 Fr
||t|
TT Atrn) 01 0t
TrihT TTT
TH( (r(()) Tokk Aira)
7
7
7
and if e 1, then have that
32
0 Ir
111133
Ofn |
|
Tr(hT
Tr( +
Tr(ss*).
TB
Proof. To deal with the term Tr) are again going to have to look at whether Nem is bigger than or smaller than M. First, let us start by looking at the case when Ner > M. Here we have that
|| Tr
Tr
(( (Oims wh +
02 @emlllt/?
u Almn.
)(1( (Berul uh +
0 1
uk? Alra))
TI
Ti
32
03 trm
||
04 Ofrulllll
Tr(he u² "hh) +
Tr(h" T "² "kk" Atrn)
Tr((Atrr)) Ko ukk? Atrm)
7
7f
of
02 02n 32
0
||
0t 1111 Tr( TT Alrm)
Tr(h h) 22
crm
Tr((Atr TKk Alrw).
7
7²
o
22

---

Published in Transactions on Machine Learning Research (04/2023)
Where the last inequality is true due to the fact that ||u]p = 1. How about when Non M. Then we have the following string of equalities instead.
| = Tr)
O0rn
uh + 0pmnlli |/0l13 us"
T
Otrn3 uh + ( us
= Tr
72
8²
Tr u² uh) +2 62
|1]113 B
0 |//l|
Tr(h T u uuu" +
Tr(su" us
T2
T2
g2
32
Tr(h" h) + 1 ||
Tr(h 22) + 0brnl1
/|// Tr(ss").
2
T2
C.4 Step Estimate using random matrix theory.
Lemma 5. Suppose A is by q matrix such that the entries of A are independent and have mewn 0, variance 1/q, and bounded fourth moment. Let Wp AA and let Wg = A A. Let C p/g. Suppose Xp= Xg are a random eigenvalue of W, p. Wa- Then
p < q, then
-- + o(1.
2. 1 < ς, then
= (1-C8s + d1))
P
8. I < q, then E
X = (1-O3E + o1).
4. 1f q, then IE
X (1-C) + (l).
5. 1fp q, then IE
A T-o + o(1)
C-1
6. 1 4, then E
X (1-0-p o().
G-2
-1400=1
1fp 4, then
X (1-0-15- + o(l).
(c #c
pf q, then
+ o())
(I-C 1y
Proof. Suppose A is an p by q matrix such that the entries of are independent and have mean 0, variance 1/g, and bounded fourth moment. Then we know that = = AA is an by p Wishart matrix with C. If send p. 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) = com2 - (1 - -- (1-c-2 c-2)m such that the zeros of L(m, 2) given by L(m(2), 2) are such that
m(z) - -F()) dF()) EA
[__2]
1 x
For the Marchenko-Pasiie Pastur distribution, we have that for O, we get that m(2) = 1/(1 cc) Thus, for Ap is eigenvalue value of W,, p: we have that
E
1-c + o(1).
For Ex [x=2 we need to calculate m' (0). Using the implicit function theorem, we know that
m²(=)= = -1 (1/0 (m(2),
0L
(m(2), (m(z),2)
Om
Oz
23

---

Published in Transactions on Machine Learning Research (04/2023)
Here that 0L/0m 2com + c+ 1. Thus, at (1/(1 c), this is equal to 1. Also 0l./az = cm2 + m. Again at (1/(1 c),0) this is equal to [I- + I-c [I-eTz- Thus, we have that
m m' (1-
Similarly, using the implicit function formulation, we can calculate m0(0) and m (0)
On the other hand if P, then Wy AAAAA 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, A A/C is a Wishart matrix with c 1/C Thus, for Ag is an cigenvalue value of W q. we have that
C- 1-c-++ (1).
E
Aq =
We can obtain the rest in similar manner from the previous results.
Lemma 6. Suppose A is an by matrix such that the entries of A are independent and have mewn 0,
variance 1/q, and bounded fourth moment. Let C p/g and let x, be unit vectors in p, then
- (1)
(AA")((
p<q
1110-11
9 c-
+
o()
p>q
"AA""
(1-C)3 +o(1)
1
p<9
(1- + +o()
C
p>q
+1( p<q
B[THY (ATAA))))) A)Ta)=
0
ol) p>4
1-
q (I- + o1() p<q
4. B[TH A) A)
(-- + ((1) p> 4
Proof. Let A = USVT be the SVD. Then we have that (A = U(E))tUT Then since A is bi-unitary invariant, we have that U is uniformly random unitary matrix. Thus, a = - uniformly random unit vector. Note with probability 1, the rank of is full and that the non-zcro cigenvalues AT and AAT are the same.
If p < q, then we have that
(A77))))) = Σ
o
Using Lemma 5, we have that E[[/o?] 1/(1-))0(1) Thus, we have that
(A77))() = Σ -1111111 1
1=1 pl-c -1-c+o11 +0()
On the other hand, if > 4, from Lemma 5, we have that -- +0(1. Thus,
E[Tr(> (AAT)="AAA) Σ1 C-1
p1 +
Similarly, if we had we looking at (AAT))AA ftx), we would have a 1/0 term instcad. Thus, if < q. we would have that E|Tr(H ( (1-C)3 + o11)
A similar caleulation holds for the others.
24

---

Published in Transactions on Machine Learning Research (04/2023)
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 Atrn satisfies the standard noise assumptions, then we have that
Po 1. B[3] = 1 + o(1) and (ar (mar((M.Nom))IIcc)) + t(().
c²
c2 c)
c <<> 1, then B[[||[[]] = c
+ o1) and Var([1h](3) = N1 - c]3 +1))
c2 - 1)
3. cf 1, then B[]||[]] c-1 + o(1) and Var(11h]]3)=
c
Nern 1)3 + +1))
4. B[[||1|] = - + o(1 and Var(I1a|13)= = (2 +c)
c
+0(1).
M(1 c)3
1
|]| c
o(1) and Var([|>||3) Me
+ o11
||||||]] - + o(1), Var([|t]()) = Ner
c + o11)
Lemma 11. /3 term.
Proof. First, we calculate the expected value of B. To do so, let Arn = UEVT be the SVD. Then since Atrn is bi-unitarily invariant, we have that U, V are uniformly random unitary matrices. Since u, Uhrn are fixed. We have that a = uirn V R and b == U u E RM are uniformly random unit vectors. In particular, we have that E[a:] = 0, E[b:] = O, Var(a:) = 1/Nrmn; Var(b;) = 1/M.
Thus, if o; are the singular values for Arn; then we have that
min(M Nern)
1
B = + Otrn
Σ
a,b.
Thus, if you take the expectation you get that
B
On the other hand, lets look at the variance. For the variance, need to compute B[3?]. Now if we let T v Atm Then we have that
B 1+ 12 27.
Thus, again we take the expectation, we get that
= 177
Again due to the fact that a, b are independent have have mean 0 entries, the cross terms in [T[ Thus, we have that
Min(M,Nerad
1
E T
Σ
a263
Otrn
E
Σ
M Ntrn
Now need to whether M Ntwn M < Ne Now to Lemma 5, we note that q M and Ntrn
Suppose we have that M > New, then in this case, we have that g > p. Thus, we have that
E
--c + o(1)
where C' C== pppg- Ntrn/M 1/c. Thus, we have that
E
=
1
1/c
+ o(1) = c
c-
+ +0()
25

---

Published in Transactions on Machine Learning Research (04/2023)
Thus, we have that
| Prrn M(c - 1)
c
+
1
M
Thus, we have
1
Var(3) 0 M - +
M
On the other hand, if M < Ntrn Then we have that q < p.
Thus, we have that
C-1
E
C- +ol)
where C = -pppqq- Ntrn/M 1/c. Thus, have that
E
o(1)
0
Thus, have that
c I--c - + t0(1))
B[T Orn Nem
+o
Ner c)
Nern
Thus, have
Var(B) = 0gr
+
Nern (1 c)
Nern
Lemma 12. ||]] term.
Proof. We want to do calculation similar to that Lemma Here we have that
|| = Tr(h" h) = Tr((A R Vvenn Alrn) Tr(virn Alrm (Alrn)) (ten) (erm)) = Tr(viru ( (Atrm Aera) ('rr))
To use Lemma 6, we note that A = Afrms M, p Ntrn Let us now suppose that M < Ne Then again taking the expectation, we see that
M ( c (1-c+ +0(1) = 1-c t()).
|||b||| =
Nom
For the expectation of ||A]]*, let Atr UVVT be the svd. Then - = VYtUT Let a uh V and note that is uniformly random unit vector. Thus, have that
|
For the expectation of [ we note that
M
|
1
az
Σ
-.
+
1
o.
0.
d=1
iF)
Taking the expectation of the first term, we get
M
Bia
Nern (Nern + 2) (1-c) c)3
3M
2
+
t((l)
=3
x3 Nira (1 + +o(1)
26

---

Published in Transactions on Machine Learning Research (04/2023)
Taking the expectation of the second term, get
2 B[aja]] = M(M - 1) Nern (Neen + 2) (1- + +o()) = (1 (1-c)²
c²
c²
c
M(M 1)B
+ (1).
Nen (1 c]
Thus, we have that
B[]||] (1 c)2 + (2
Nen (1 - c]s + +l()
Thus, the variance is
Var(I][]13) = c²
Ne (1 - cc3 (1).
For M > Nern; instead have that
Nern
+ ((1) (
[[||||]] Nton c-
c- +1(1.
For the expectation of |/]4, we note that
New N
N
7
0,0j
Taking the expectation of the first term, we get
Narn
NNrr
c²
Bla
N trn
1c- + (
=
Nern (c 1)3 + o(1).
Taking the expectation of the second term, we get
2
NNrn(Nirn - 1)B
Bla
Nern (Nem -
(c- 1)2 + o(11)
N2
trn
c²
+ +o(1).
(c
1)2
N - 1)2
Thus, we have that
c²
c²
+ cl 1(2c-1) 1)
||| (c 1)2
3
Nen (c 1)3
Nun - No
1)2 + +(1)
=
(c 1)2
N - 1)3 + o(1).
Thus, the variance is
Var(I1/13)= = 2
+ o(1)
Nc 1)3
Lemma 13. | term.
Proof. First note that l only appears in the formula when c < 1. Thus, we can focus on this case. As with h we have that
|| Tr(u" (A). yr Al,, u) = Tr(u" (Aur J'u).
Again using Lemma 6, with g = M, = Nern, A = Atrn y = u. Thus, since we have q == M < Nern P. we get that
||| --c +o(1).
27

---

Published in Transactions on Machine Learning Research (04/2023)
To calculate the variance, we need to calculate the expectation of | Here be again let A UEV? be the SVD. Then let b = UFu. u. Then we have that
||||| 2
0 1
Thus, that
M
|||||*
Σ
b
o
itj
Taking the expectation of the first term we get
d²
3c"
3
M (1 c)3 +o(1) =
M(1 c]3 + +0l1.
Taking the expectation of the second term we get
M(M - 1) c²
e²
c)2 o[1
+ o(1)
M (1
c]-
M(1 - 6)2
Thus, we have that
2
(2 +
B|||||
+ +
(1 c)-
M1 c)3
Thus, we have that
c2 +
Var(I|k|13)=
+ o11)
M(1 c)s
Lemma 14. || term.
Proof. First, note that only appears when M Non- Thus, only need deal with that casc. For this lerm, we note that (I - Aero A is a projection matrix outo uniformly random M - Ntrn dimensional subspace. Here be again let A = UEVT be the SVD. Then let b == UTu
New
I
||||||||| = EluTup u TT Aem Al. 24
E
bT
b = =1
M +o(1) = x(1)
Similarly, we have that
Nern
|||||
b2
Nern
Nirn
1
62
2
New
Nyn
New
1
61
6²bb
- 2
b2
1=1
28

---

Published in Transactions on Machine Learning Research (04/2023)
Taking the expectation, we get that
Nern
Nern
Nern
-||s|19-1+3
E
+
-2 Σ
+ o1)
M
M
M
i= l
i=1
3
Nirn (Ntra
- 1)
1 +
=1+
o(1)
cM
M
c
3
1
1
1
1 +
2
+
cM
6²
cM
c
1
1
+
2
+ (1)
cM
Thus, we have that
Var([|=|3) =
+ o(1)
cM
7
Lemma 15. ||4]22 term.
Proof. First, we note that only appears when M Nun. Thus, we only need deal with that case. For this term, we note that (I 11-Ag A,,,, is projection matrix onto uniformly random Nmm - M dimensional subspace. Then similar to ||s||2, we have that
M = 1
lM 0
[[][] =
Eluten Mern
"fo A Atrn Utrn]
E 1 - a
N + o(1) = 1 - o(1)
t=1
Similarly, we have that
M
|
1
2
[=1
M
=1+
2
2
1=1
1+
0
0.0
2
2
(
Taking the expectation, we get that
M
M
1
E
11+1 3
2 Σ
o(1)
Nrn
N2
N
1=1
i=1
3c
Nern (Nern - 1)
1
+
2c + o(1)
Ntrn
M
-1+ Ntrn
3c
+ 2
c
- 2c + o(1)
Num
(1 c)² +
+ o(1)
cM
Thus, we have that
Var(11113) = Ner
+ o(1)
29

---

Published in Transactions on Machine Learning Research (04/2023)
Now could just use the the fact that [[XY] - [[X] < v VVr(())aar() Another way to do this is via using big O in probability. Which is defined follows:
Definition 3. We save that a sequence of random variables Xn is Or(an), if there erists N such that for all e >>>>> 0, there erists constant L such that for all n 2 N, have that Pr[[Xn] > Lan] < <e.
Then the trace terms.
Lemma 8. Under standard noise assumptions, we have that
B[TrChT K. Atrr)]
and
Var Tr(h Atra)) = xa(c)/ (Nre)/Nrn>> + o(1)
where Xa(c)= = [E[//>,, X is an eigenvalue for AA and is as in Lemma 6.
Proof. First note that
Tr Al...) Tr((A) vern (A u² (A(rm)) (Alrn Vern).
Again let Aum = UEVT be the SVD. Then, we have the middle terms depending on Ayn simplifies to
(Almn) A Alr (EE
Thus, again letting b = uuu U and VT VT Vern. We see that
M
Σ
1 a,b o
Now if take the expectation, since a, are independent and mean 0, we see that
EA. [Tr(h ((,))
Let us also compute the variance. Here we have that
BTTrCK Al. )
Σ
E
E Ela
E + +0.
Now for the Marchenko Pastur distribution we have that the expectation of 1/x3 X3(c). where Xs is some function. Thus, have that
E(Tr(K? ReT A| Ner Xs(c) + o(1).
Lemma 9. Under standard noise assumptions, we have that
c²
Tr((Atm))) k kk Atrm) = (1-
+ o(1)
and
3
1 dt
Var( (Ai A = Xa(e) M (1-cft cjo o(1)
M
where xa(c) EE[1/4), X is eigenvalue for A AAT and A is in Lemma 6.
30

---

Published in Transactions on Machine Learning Research (04/2023)
Proof. Now using Lemma 6, that
e² (1 c)s
A (r((A k Alm! k
+ (1))
Similar to proofs before, we have that
E Aern (Tr((A)m)) RkT A! )
Σ
3 M
M2Xa(c) +
Σ
1
o(1).
M (1-c)6
ifs
Where Xa(c) = =[[1/>]] for the Marchenko Pastur distribution. Thus, we have that
c
Var(Tr((AAnm)) Rkk Atrn)) k M x((c)=
+ o(1).
M (1 - cjo
Lemma 10. Under the same assumptions Proposition 2, we have that Trh s²)) = 0.
Proof. Here note that h² (Atrn) U'ern Utrn and sf wf Aern Abrn) Thus, we have that
Tr(h"s 5²) = Tr((A)rn)) )T "tenu" - (Atra) vernul" (ArrnA)ra)")) Tr u) Tr(u (AtenAtro ( (erm)) vern) = -Tr(u Alm u) - -Tr(oinn Afro Aern
Tr(u, Al 4)m") Tr((o At Atrr
0
As we can see that if we take the expectation of [W]| over Atr since the variance of each of the terms is small, we can approximate E[XY] with [Y] Then we get the following.
If M < Nt we have that
0
2
H (1 - c)2 ²
E A [|]]]]]]
+
(1 + 0 e)² - c)
(1 0 2)
c)² (1 c)3
02 01 irn
c²
bsn c) )2( -c c)
On the other hand, M > N we have that
EA [|]]]
6zm
c
+ (1+
2
(1 + 02 Irn )2 c
) (c - 1)2 c
tra
c 0z (1 + 0g
c (1 + 02 )
02 c
1 02
Now combining everything logether, we get that
02
1 1.2 -2
1ist - W (1tss + Asst)ll
Nua o)2
(1+0) (11-))
c<l
E EArr
Nost
Nea 82
o)²
+
M 1+62 Dmn
1 a²
c-1
c>1
31

---

Published in Transactions on Machine Learning Research (04/2023)
C.5 Proof of Theorem
We can see that the main text has how to put all of the pieces logether to prove the main Theorem. We don't replicate that here.
C.6 Formula for copt-trn
As stated in the main text, only need to take the derivative. So, don't present that calculation here it is fairly straightforward.
D Generalizations
In this section we discuss some possible generalizations of the method.
D.1 Higher rank
Let present some heuristics for the higher rank formula. To do we shall need notation. Let X -i= u (nfm)).. Let A be the noise matrix. Then for S S define
A₃ A
of n
We shall now make some assumptions. Specifically, we assume that Uj ofmn and A, are all such that for in o i2, and for all we have that
E Elu AUA E(( A = 0.
Additionally, we assume that for all in, 12,J we have that B[(u!Tn) A AJusal O. We also assume that the variance of these terms goes 0 Nivn M go to infinity.
Lemma 16. With the given assumptions, we have that for all {,
o, frm
(1 (utraar A R of tra tr (u:"")"" A)-1 o, tm u AranT A) R ... Re of ",,",( (n (otras A
Proof. Write A₁ Aj-1 + of uy f 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 Tr (u A] are small.
Define h2 = (ogmaiT A/. kj = ofm ofm-Auus Alus, l = (1)T0)7(( - ALAs), 8j = of A₂ A,Al)uj, Bg =
+ ( Alus, (1) |1511211111 + 83, ()) = 111111, B3, and similarly pi P2 111 and
(1)
2 Now, we can write
X + = of fra ofm (u.to) + Ar-1
Then we have that
W u. (u + A,)
Σ
trn
( (a u Ar)
o
Expanding and using the lemmna, get that
gen (3)
uihs + (af (
Us At e<l
Wa tr TrnnT Ata
unh + (o (2
Er
of B
U; e>1
T
(c)
Where the second equality comes from the rank 1 results.
32

---

Published in Transactions on Machine Learning Research (04/2023)
Now that we have an approximation for W (given our assumptions), can now approximate the variance and bias terms again. Let W; denote the ith factor (corresponding to us) of W. First, for the bias, due to the orthogonality of the u's we get that
| W
Σ 2 ui(
W. Σ tst
of
F
Again, using our assumptions, we see that the terms in the j summation dropout besides when j = i. Then again using our rank result, we get that
2
Be
1 - WX 11?
Σ i=1
of
(2)
Tida
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 of ut, uiz. For the diagonal terms, we again use the rank results and get that
(0! Tr(hTh)))) +2 ()
(M RT((A)))AAAA
|WIP
Tr(NTT/ (T) +
(r
(7/0)2
and if c 1, then have that
p Tr(h? +
(o 1 (1) )2
Tr(h sf) + (a ( Tr(sis?).
| Σ
(T2 )0)
(72 (0)
The final step would be to estimate each of these terms using random matrix theory. However, unfortunately the A5 may not satisfy all of the needed conditions. However, we know that Aj is perturbation of A and A satisfics all of the needed conditions. Hence, if the perturbation is small, we can replace A, 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 Ay's with use our estimates from the rank 1 result. We then get our estimate for the generalization error for general rank r data.
(Otsrofot)2
22 (( (2n)2 + (Otrng!rn))) M(1 + (Dem ofr (1) o(1)
R(Otrn, Ozsts C, Etens Eest) Nlsel1 oD Pej2
(14)
and if c 1, we have that
(Otsoffa12 Nis + (D M + (Ormot
c(Oernofm33
R(fmm, Bests e, Etens Eist)
+
+ o())
(15)
In the experimental section, that for small values of r for bounded away from 1. This seems to be good estimate for the generalization error.
E
Experiments
Please see accompanying notebook for code to produce the data for all of the figures.
E.1 Low SNR and High SNR data
For low SNR data, we sample the times singular values from a squared standard Gaussian. We do this independently for all 2r singular values. We call this the low SNR region because 0 is not being scaled with the number data points. Hence as Nerns Nest + 0o, the SNR goes to 0.
For the high rank data, we sample 8 times singular values from squared Gaussian and then multiply by VNten / /Nst- Hence here the SNR does not go to 0 Nern, Nest oo.
33

---

Published in Transactions on Machine Learning Research (04/2023)
F Generalization Error versus Training noise level plots
F.1 More Tests for Rank
Here we provide more examples of and how our theoretical formula matches the experimental performance exactly.
Each empirical point the average over trials. These were run on a laptop with 8gb of RAM and an processors, The average time produce any of these plots is about 10 to 30 minutes.
Twenstol spriew Twet yre
Thars part
6x12
Eror cures
Troerticnl
64
Tmperis Reeat
010
604
6d6
026
010
016
017
0.6
6.01
311
011
014
000
008
0ds
6
a17
als
Sqaars ro Etheraa '3]
Squard sot Stradar
Squars root Suaeta "X]
(a) c= 0.1
(b) c 0.5
(c)
0.9
Usteral
Istrn
12x
Fndeceol Experial
2x10
Hetujat
2x
Teery predeter
164
10"
654 Sqar men qiaaeeaar
y0ize eciss oolrs Sepeemmenat (itees (2)
Scuare rot (11wer33
(d) c
(e) c=
(I) c c= Oest = 0.01
Figure Figures (a) (c) showing the accuracy of the formula for the expected mean squared error for C = 0.5, 0.9, 10 for fixed value of dre.. Figure (f) empirically verifies the existence of a regime where training pure noise is optimal. Here the red and green lines represent B[0²,t] and E(Oū,.) respectively. Each empirical data point is averaged over at least 50 trials.
F.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 2 data is of the following form. Let W Watta be some fixed matrix, then our data is generated by
= Ferlu[Waa.rllulii
Where different is sampled for the training and test data. the results for this can be seen in Figure 9. As can from the figure, have the exact same qualitative trend for that we saw before. That is, as goes from O to 1, we have that 8yn goes from dist to O, and then as - 00, we have that oer goes to infinity as well.
F.3 MNIST Data
We now look at the linear network with MNIST data.
34

---

Published in Transactions on Machine Learning Research (04/2023)
Oretrva Bry
0009
<00
400
54.00
0000
0t1
(a) C 0.3
(b) C == 0.5
(c) c 0.9
VSE
Qm
9m
(d) c= 2
c c= 10
Figure 9: Rank 2
Ntm 5000
Nrn 20000
5000
020
2000
X040
3003
090
30000
1200
Proptet
060
6:m
(a) c= 0.04
(b) c= 0.16
(c) C 0.784
Nin 700
Ntm 203
04
000
2.08
01
96m
0m
(d) c 1.12
(c) c 3.92
(1) = 39.2
Figure 10: MNIST
F.3.1 Non-linear Network
Here, we trained each network for 1500 epochs. During cach epoch we computed a 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. 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 a Telse P4 gpu. LRL is a model with a reLU at the end of the first layer only.
35

---

Published in Transactions on Machine Learning Research (04/2023)
2.15
85
2.0
0.5
10-
1.00
0.22
0.4
333
330
5.00
032
034
(a) 0.261
(b) c 0.784
(c) c 1.12
003312
883355
2002EL
883333
030215
619
031
035
013
012
011
0.3
(d) 1.57
(e)
3.92
Figure 11: MNIST LRL model
36


Reviews:
[{"review_id": "IK8n5okXB2", "reviewer": "Reviewer_pzdw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The empirical studies with general input matrices carried out in the paper for double descent and the noise setting are interesting contributions of the paper. \nThere are two weaknesses. One is the lack of an activation function in the network, and the other is the rank-1 restriction on the input matrix. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Double descent is an interesting phenomenon in overparameterized neural networks and deserves extensive investigations. In this paper, the authors carry out high-quality empirical studies with general input matrices and present some generalization analysis in the case of a rank-1 input matrix and Gaussian noise. This noise setting is interesting. But the network does not involve an activation function. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors should comment on difficulty in extending their theoretical results to more general input matrices and networks with activation functions. ", "broader_impact_concerns": "It would be more interesting if the authors could extend their theoretical results to more general input matrices and networks with activation functions. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2l9ICW66sU", "reviewer": "Reviewer_LAyJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This work studies a pretty interesting topic: the generalization of a denoising model. However, even before finishing my first pass, I noticed the following clear weaknesses in the paper:\n\n1. The writing could be improved. Too many typos. Also inconsistent tenses. The current writing quality really discourages me to spend more time reviewing the manuscript. \n\nWhile the topic sounds to be interesting, and also novel to my knowledge, I am not sure I fully understand the problem setting. The mathematics could also be made more clear.\n\n2. Could have emphasized that $\\\\theta$ is just a scalar instead of a matrix.\n3. On page 3 bottom, what is the \"expected norm of the noise distribution\"?\n4. In Section 4.1. If $U$, $V\\_{tst}$, and $\\\\Sigma\\_{tst}$ are all given and fixed, why should we care about denoising at all, as we already know the test data?\n5. Remark 1 on the bottom of page 6: could you please be more specific? What is degenerate and why degeneration causes a problem?\n6. Eq. (4), the expectation is taken over what randomness? \n7. Overall, I do not see why the current denoising problem formulation makes sense. Firstly I would encourage the authors to explain what is known and what is unknown. If the test data is already given why would people be interested in denoising it? Secondly, I would encourage the authors to provide some *specific* examples that connect the mathematical formulation (e.g., eqs (1) and (2)) to practical denoising procedures. \n\nI have more questions regarding the theoretical results. \n\n8. In equations (5) and (6), the $o(1/N\\_{tst})$ and $o(1/M)$ terms look suspicious. Could you please specify the hidden constants/factors?\n9. The condition that $\\\\theta\\_{tst}$ is $O(\\\\sqrt{N\\_{tst}})$ is also hard to interpret. First, please specify the hidden constants/factors. Second, it seems to suggest that $\\\\theta\\_{tst}$ could be a function of $N\\_{tst}$, then if $\\\\theta\\_{tst} = 1/{N\\_{tst}}$ for example, it is not clear which term in eq (5) is the leading term. \n10. When $c\\\\to 1$ the current bounds in eqs (5) and (6) are infinite. But this does not seem to be sharp. Note that under the assumption that $r=1$, the whole problem is effectively only a one-dimensional problem as $u$ is given. Then computing the eigenvalue of a (fixed) 1-dim projection of the noise matrix effectively reduces to computing the norm of a random vector. This is only a random variable and should be well-bounded (away from zero) no matter $c=1$ or not. So I do not think the test error should be unbounded when $c=1$.\n11. On page 11 top, could you be more specific about the technical difficulty? Note that the Sherman-Morrison-Woodbury formula gives you the formula of the form $(A+XT)\\^{\\\\dagger}$ for general matrix $A,X,Y$. I am not sure if it is necessary at all to restrict oneself to rank 1. \n\nGiven the above weaknesses, I am leaning toward rejecting the current version of the manuscript. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work considers the generalization error of a linear denoising model. For rank-1 data, it shows that the generalization error, as a function of the number of training samples, follows a double descent curve. In more general settings, experiments are conducted that also suggest a similar double descent curve. Moreover, the paper shows that the double descent phenomenon can be mitigated by optimally tuning the SNR in the denoising procedure. In other words, the generalization error of a denoising procedure with the optimally tuned SNR is a decreasing function of the number of training samples. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "First please polish the writing. Moreover, please consider commenting on my questions above to help me better understand the results. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CRCfpM5iYQ", "reviewer": "Reviewer_PutB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n- This paper gives a theoretical analyses under the rank-1 data and indicates how the optimal SNR affects the double descent curve.\n\nWeakness\n\n- The description on assumption is unclear.\n\n- In theorem 1, the assumption $\\theta_{trn} = O(\\sqrt{N_{trn}})$ does not make sense as the dimension of $\\theta_{trn}$ is the input dimension $d$.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper focuses on the double descent both empirically and theoretically of the denoising model. The main theorem provides an asymptotic result for the excess risk of the rank-one data, which borrows the techniques from random matrix theory.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In Figure 2, why does the phase transition not occur at 1?\n\n- I suggest the authors set the assumptions more formally and mathematically, and put the discussion in the remark. \n\n- The low-dimensional data assumption is ok for me. But I’m wondering that it  would be possible to consider the case that the target function is low-dimensional? This setting is more realistic. \n\n- The empirical validation on the approximation in Eqs. (7) and (8) is needed.\n\n- In theorem 1, how does the test error vary with N_{tst}, M? This requires more discussion. The comparison with previous work in double descent, e.g., least squares, random features, is needed. For example, when I saw the result in Theorem 1, it is similar to Hastie’s result. What is the same point and separation under these problem settings?\n", "broader_impact_concerns": "no", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is on the generalisation performance of denoising models. It demonstrates empirically that under certain conditions, the generalisation error follows a double descent curve and provides a simple model for the observed phenomenon.

This is a borderline paper and the reviewers have mixed opinions about it, 2 leaning to accept while 1 is leaning to reject, one reason being a perceived limited significance. 

However all reviewers indicate that the claims are backed up by evidence and that they think there would be some TMLR readers who would be interested in the topic even though the topic and problem setting are rather restricted and a better write-up could make the readers' life much easier.

In the hope that the studied phenomenon and mathematical analysis will be useful for other researchers, I recommend acceptance.

Some comments/questions to address for the camera-ready version:

- p3: typo: rations

- p3: "Our goal is to understand the impact of training noise impacts generalization error" 
  impact of training noise on ... ?

- Section 3 intro: ", we explore the role of the amount of training noise and show that
optimally picking theta_tst can mitigate the previously seen double descent."

Is this a typo, and it should be theta_train? Or otherwise, please explain how we can pick theta_test.


Decision: Accept (poster)