High-dimensional Asymptotics of Denoising Autoencoders
Authors: Hugo Cui
Lenka Zdeborova
Venue: NeurIPS 2023 spotlight (2023)
Keywords: statistical physics
replica method
autoencoder
exact asymptotics
TL;DR: We provide sharp asymptotics for the test error of non-linear denoising auto-encoders in high dimensions.

Abstract: We address the problem of denoising data from a Gaussian mixture using a two-layer non-linear autoencoder with tied weights and a skip connection. We consider the high-dimensional limit where the number of training samples and the input dimension jointly tend to infinity while the number of hidden units remains bounded. We provide closed-form expressions for the denoising mean-squared test error. Building on this result, we quantitatively characterize the advantage of the considered architecture over the autoencoder without the skip connection that relates closely to principal component analysis. We further show that our results capture accurately the learning curves on a range of real datasets.

High-dimensional Asymptotics of Denoising Autoencoders
Hugo Cui
Lenka Zdeborová
Statistical Physics of Computation Lab Department of Physics
Statistical Physics of Computation Lab Department of Physies EPFL, Lausanne, Switzerland
EPFL. Lausanne, Switzerland hugo cui @epfl.
Abstract
We address the problem of denoising data from a Gaussian mixture using a two- layer non-linear autoencoder with tied weights and skip connection. We consider the high-dimensional limit where the number of training samples and the input di- mension jointly tend to infinity while the number of hidden units remains bounded. We provide closed-form expressions for the denoising meaa-ssqaree test error. Building this result, quantitatively characterize the advantage of the sidered architecture over the autoencoder without the skip connection that relates closely to principal component analysis. We further show that results accurately capture the learning curves on range of real data sets.
Introduction
Machine learning techniques have a long history of success in denoising tasks. The recent break- through of diffusion--ased generation [1 has further revived the interest in denoising networks, demonstrating how they can also be leveraged, beyond denoising, for generative tasks. However, this rapidly expanding range of applications stands in sharp contrast to the relatively scarce theoretical un- derstanding denoising neural networks, even for the simplest instance thereof namely Denoising Auto Encoders (DAEs) 3]
Theoretical studies of autoencoders have hitherto almost exclusively focused on data compression tasks using Reconstruction Auto Encoders (RAEs), where the goal is to learn a concise latent representation the data. majority this body work addresses linear autoencoders 4 6
The authors of 8 g analyze the gradient-based training of non-linear autoencoders with online stochastic gradient descent or in population, thus implicitly assuming the availability of an infinite number of training samples. Furthermore, two-layer RAES were shown to learn to essentially perform Principal Component Analysis (PCA) [TO 11 [2], ie. to learn a linear model. Ref. [I3] shows that this is also true for infinite-width architectures. Learning in DAEs has been the object of thcoretical investigations only in the linear case 14], while the case of non-linea DAEs remains theoretically largely unexplored.
The present work considers the problem of denoising data sampled from Gaussian mixture by learning two-layer DAE with a skip connection and tied weights via empirical risk minimization. Throughout the manuscript, we consider the high-dimenssooal limit where the number of training samples
Main contributions-
the dimension d large (n, 2o) while remaining comparable, i.e. n/a = @11). Our main contributions are:
Leveraging the replica method, we provide sharp, closed-form formulae for the mean squared denoising test emrrr (MSE for DAES, function of the sample complexity and
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the problem parameters. We also provide a sharp characterization for other learning metrics including the weights norms, skip connection strength, and cosine similarity between the weights and the cluster means. These formulae encompass as a corollary the case of RAFs. We show that these formulae also describe quantitatively rather well the denoising MSE for real data sets, including MNIST [15] and FashionMNIST [16].
We find that PCA denoising (namely denoising by projecting the noisy data along the principal component of the training samples) is widely sub-optimal compared to the DAE, leading to MSE superior by a difference (d)) thereby establishing that DAEs do not simply learn to perform PCA.
Building on the formulae, we quantify the role of each component of the DAE architecture (skip connection and the bottleneck network) in its overall performance. We find that the two components have complementary effects in the denoising process -namely preserving the data nuances and removing the noise- and discuss how the training of the DAE results from a tradeoff between these effects.
The code used in the present manuscript can be found in the following repository
Related works Theory of autoencoders- Various aspects of RAES have been studied, for example, memorization (17), latent space alignment [18]. However, the largest body of work has been dedicated to the analysis gradient- graddeentbbased algorithms when training RAEs. Ref. [5] established that minimizing the training loss leads to learning the principal components of the data. Authors of have analyzed how a linear RAE learns these components during training. These studies were later extended to non-linear networks by [19 g 9 at the sacrifice of further assuming infinite number of training samples to be available -either by considering online stochastic gradient descent, the population loss. Refs. (20) [3] are able address finite sample complexity, but in exchange, have to consider infinite-width architectures, which [13 further shows, also tend to large extent to learn to perform PCA.
has proven a very valuable gateway access sharp asymptotic characterizations of learning metrics for high- dimensional machine learning problems. Past works have addressed -mmon others- single- [25
Exact asymptotics from the replica method- The replica method 21
22
23
24
26
33 While the approach has traditionally addressed convex problems, for which its prediction can be proven e.g. using the convex Gordon minimax theorem 34 the replica method allows average over all the global minimizers of the loss, and therefore also accommodates non-convex settings. Refs. [35]36] are two recent examples of its application to non-convex losses. In the present manuscript, leverage this versatility to study the minimization of the empirical risk of DAEs, whose non-convexity represents a considerable hurdle to many other types of analyses.
27 28 and multi-index models [29]. kernel methods (30
31
32
2 Setting
Data model of variance A,
We consider the problem of denoising data E Re corrupted by Gaussian white noise
v1 Ax. + VAg.
where we denoted 0 the noisy data point, and & NN Ia) the additive noise. The rescaling of the clean data point by a factor v1 A is a practical choice that entails loss of generality, and allows to easily interpolate between the noiseless case (A = O) and the case where the signal-to-noise ratio seamlessly connect with works
vanishes (A 1). Furthermore, it allows generative models, where the rescaling naturally follows from the way the data is corrupted by an Ornstein- Omstein-UUlenbeck Uhlenbeck process (1 (2] In the present work, we assume the clean data æ to be drawn from a Gaussian mixture distribution IP with K clusters
diffusion- based
K
x
( Ex).
The k-th th cluster is thus centered around μa Rd has covariance Σω 1 0, and relative weight Pk.

---

DAE model An algorithmic way to retrieve the clean data from the noisy data è is to build neural network taking the latter as an input and yielding the former as an output. A particularly natural choice for such network is an autoencoder architecture [3] The intuition is that the narrow hidden layer of an autoencoder forces the network to learn suceinet latent representation of the data, which is robust against noise corruption of the input. In this work, we analyze two-layer DAE. We further assume that the weights are tied. Additionally, mirroring modern denoising architectures like U-nets [37
38
39 40 41), we also allow for (trainable) skip-connection:
w
WE
fb = b
The DAE (2 is therefore parametrized by the scalar skip connection strength b E R and the weights Rexd with p the width of the DAE hidden layer. The normalization of the weight by vd in (2 is the natural choice which ensures for high dimensional settings d >> that the argument wea/va of the non-linearity (-) stays (1). Like [8). we focus on the case with p < d. The assumption of weight-tying affords a more concise theoretical characterization and thus clearer discussions. Note that it is also strategy with substantial practical history, dating back to
R it prevents the DAE from functioning in the linear region of its non-linearity (.). This choice of architecture is also motivated by particular case Tweedie's formula 42
(see eq. (79 in Appendix B). which will be
the object of further discussion in Section
We also consider two other simple architectures
2'
v
To(#) X Φ;
which correspond to the building blocks of the complete DAE architecture fo. 2 (hereafter referred to as the full DAF). Note that indeed fu,w гb + Uww- The part (.(()) is a DAE without skip connection (hereafter called the bottleneck network component), while re(-) correspond trainable rescaling of the input (hereafter called the rescaling component).
simple
) j==1 with clean To train the DAE 2). we assume the availability of a training set D {0" x samples x drawn i.i.d from P [ and the corresponding noisy samples T = x² + E (with the noises E" assumed mutually independent). The DAE is trained to recover the clean samples x from the noisy samples " by minimizing the empirical risk
R(b, w)
Σ 11at (o + g(w))
where g: IRpxd -> R.+ an arbitrary convex regularizing function. We denote by i, á the minimizers of the empirical risk (4) and by f fi the corresponding trained DAE (2). For future discussion, we also consider training independently the components (3) via empirical risk minimization, by which mean replacing fo.w by uh Te in (4). We similarly denote e (resp. é) the learnt weight of the bottleneck network (resp. rescaling) component and â ue (resp. f = ra). Note that generically, * u and à + b, and therefore * â + f, since b, ń result from their joint optimization as parts of the full DAE fo,w, while è (or Ū) are optimized independently. As discuss in Section 4 training the sole rescaling Te does not afford an expressive enough denoiser, while an independently learnt bottleneck network component uy essentially only learns to implement PCA. However, when
jointly trained as components of the full DAE fu.w (2), the resulting denoiser f is a genuinely non-linear model which yields much lower test error than PCA, and learns to leverage flexibly its two components balance the preservation of the data nuances and the removal of the noise.
Learning metrics
The performance of the DAE 2 trained with the loss 4 is quantified by its reconstruction (denoising) test MSE, defined as
x x fb (VI-Az Ax + VAE)|?
mse Ep
(5)
The expectations run over fresh test sample sampled from the Gaussian mixture PP TT. and new additive noise& & corrupting it. Note that an expectation over the train set is also included to make ; metric that does not depend on the particular realization of the train set. The denoising
3

---

test MSEs m,se,, mSee are defined similarly as the denoising test errors of the independently learnt components (3). Aside from the denoising MSE (5), another question of interest is how much the DAE manages to learn the structure of the data distribution, as described by the cluster means Pi: This is measured by the cosine similarity matrix 0 E R where for E [1.p] pl and E K].
w pA
0x
D
(6)
||
p
In other words, Oss measures the alignment of the i-th row úb of the trained weight matrix with the mean of the k th cluster p.g.
We analyze the optimization problem in the high-dimensional limit where the input dimension d and number of training samples n jointly tend to infinity, while their ratio a = 2/4 -hitherto referred to as the sample complexitysstas (1). The hidden layer width p. the noise level A, the number of clusters K and the norm of the cluster means || are also assumed to remain (1). This corresponds to a rich limit, where the number of parameters of the DAE is not large compared the number of samples like in 20 [3,, and therefore cannot trivially fit the train set, or simply memorize it [7]. Conversely, the number of samples n is not infinite like in S 9 19], and therefore importantly allows to study the effect of finite train set the representation learnt by the DAE.
Hiigh-dimensional limit
3 Asymptotic formulae for DAES
We now state the main result of the present work, namely the closed-form asymptotic formulae for the learning metrics y (5) and 0 (6) for DAE (2) learnt with the empirical loss 4 These characterizations are obtained by first recasting the optimization problem into an analysis of an associated probability measure, and then carrying out this analysis using the heuristic replica method, which we here employ in its replica-symin symmmtrrmmm formulation (see Appendix AA)
Assumption 3.1.
k=1 admit a common set of eigenvectors )er We further The covariances {E) K
note {A, 1d Ji=1 the eigenvalues of Σg. The eigenvalues {>/] and the projection of the cluster means on the eigenvectors {e, Ju are assumed to admit a well-defined joint distribution v as + oo - namely, for 7 = (7,...
R and T (TI,.., TK) E I
d K
8 (1+ - 71) 8 (vde, μe - TB) d+00 v (7)T). E11
Moreover, the marginals By (resp. 17) are assumed to have a well-defined first (resp. second) moment. Assumption 3.2. .(-) is &2 regularizer with strength X, i.e. g(-) 1/211-112
We are now in position
discuss the main result of this manuscript, which we state under Assumptions 3.1 and 3.2 for definiteness and clarity. These assumptions can actually be relaxed, as we further discuss after the result statement.
Conjecture 3.3. (Closed-form asymptotics for DAEs trained with empirical risk minimization) Under Assumptions 3.1 and 3.2 in the high- dighediimesional limit n, d -> oo with fixed ratio a. the denoising test MSE m 5 admits the expression
K
ph E, Tr Tr[yor (VI-Ame+ /o0-Smmm///001000000 82
inse / msse
(8)
K
2
Pi Eu,
+ o(1).
where the averages bear over independent Gaussian variables 2, u.u. NO0 Tp)) We denoted
K
(fwnstrrt + du.,ddeefn (e,(()))))
msee = ddi² + (1 (I-VI-Ae Ab)
ΣeL Pk Li-l
(9)

---

The learnt skip connection strength is
Σ Pk d2,(1)7
vI-
b
o11)
(10)
Σ Ple di,((1))1))
(1- A) A
The cosine similarity 0 66) admits the compact formula for i [1.p] and l E [1,
(mZ)):
0sk
(11)
VTa J d
where we have introduced the summary statistics
wir d
9 = lim Ep
d
9k:
lim
Ep
d
m.
d-000
lim ED
vd
(12)
Thus q. d. RPxP, my E RP. The existence of these limits is assumption of the replica method. The summary statistics 9: 9k. my can be determined as solutions of the system of equations
(prox)
$ 9e 17 m
22
VE -ppl $BE, Vo
prox
9
mkk
17
my app Vi=
(proxf)
Ok 19
mm}
602
prl.s, V-
prox*
VDq2
V-1
k=1
Σ
K
Pk 1211
VI VA 11 V-- (prox - (Vnzt) 5T-o (VT- Aprost + prox 82
k=1
-2
K
K
9k = [dv(y.))))
AI + 4+ + Σ
9+
Σ
+ Σ 1STTKK
Ty
j=1
1=1
K
Ve f ddll,, T)Tk
AIp + v. + Σ 15
5=1
m& J ddvls TTT
AI, + v
Σ
M,my
(13)
K
K Σ
= dd(()))
1lp + +
Σ
7; V3
i
+
+
Σ 1SJJK
/=1
1=1
K
V du(y,))
AIp +
+ Σ
13), qu. Vi, V, V E RpxP and my E IR, and the averages bear over finite-dmmensinall i.i.d Gaussians & 1 NO, Ip). Finally, prox proxyy are given the solutions of the finite-dimensional
optimization
Tr V/ VE (y-
692
1 Tr V-1 V-1
Agy&s) 22
&rox & 25
prox arginf Z.yER*
mk
(x-
20 x) ((1 v1 Ab)y bz) }
+ Tr go Ay + 002]
(14)
Conjecture 3.3 provides gateway to probe and characterize the asymptotic properties of the model 22) at the global optimum of the empirical risk 4 whereas a purely experimental study would not have been guaranteed to reach the global solution, and would suffer from finite-size effects. Equation
5

---

0.4
ma
12-
0.2
mise) - m54y) (inear)
0.0
0.8
0.4
-04
0.0
0.0
0.
0.4
3.6
0.8
1.0
0.0
0.2
0.4
0.5
0.8
1.0
1
Figure 1: a a==
P1,2 = 1/2, 11. = 0.09 Ta, p A 0.1, = Lanh(-); the cluster mean 141 -12 d4g
taken random Gaussian vector of norm 1. (left) In blue, the difference in MSE between the full DAE f and the rescaling component f Solid lines correspond to the sharp asymptotic characterization Conjecture 3.3 Dots represent numerical simulations for d 700, training the DAE using the Pytorch implementation of full-batch Adam, with learning rate 7j = 0.05 over 2000 epochs, averaged over 10 instances. Error bars represent one standard deviation. For completeness, the MSE of the oracle denoiser given as baseline in green, Section 4 The performance of linear DAE (a(x) = 2) is represented
dashed red. (right) Cosine similarity 0 (6) (green), squared weight norm || (red) and skip connection strength
(blue). Solid lines correspond to the formulae (2) and (10) of Conjecture B.3] dots are numerical simulations. For completeness, the cosine similarity of the first principal component of the clean train data (* 1=1 plotted dashed black.
(33 provides a closed-form expression for the summary statistics [12.. in terms the solutions the oow-imensiona. optimization (14). The latter can be loosely viewed an effective loss, subsuming the averaged effect of the finite training set. Further remark that while the regularization does not explicitly appear in the expression for the MSE (8). the statisties qu: mg in (8) depend thereon through (13). In fact, Assumptions 3.1 and 3.2 are not strictly necessary, and can be simultaneously relaxed to address arbitrary convex regularizer g(-) and generically non-commuting {Ex [Ex}/ ]k ]==1 but
at the price of more intricate formulae. For this reason, we choose to discuss here Conjecture 3.3 and defer discussion and detailed derivation of the generic asymptotically exact formulae Appendix see eq. (58). Let us mention that sharp asymptotic characterization of the train MSE can also be derived; for conciseness, we do not present it here and refer the interested reader to equation (68) in Appendix A Conjecture 3.3 encompasses as special cases the asymptotic characterization of the components r, 3
Corollary 3.4. (MSE of components) The test MSE of & (3) is given by msc; mssc 99. Further- more, the learnt value of its single parameter è is given by (10. The test MSE, cosine similarity and summary statistics of the bottleneck network à follow from Conjecture
3.3 by setting b 0.
The implications of Corollary sh4lshall be further discussed in Section and a full derivation is provided in Appendix [ Finally, remark that in the noiseless limit A 0, the denoising task reduces to reconstruction task, with the autoencoder being tasked with reproducing the clean data as an output when taking the same clean sample an input. Therefore Conjecture 3.3 also includes RAEs (by definition, without skip connection) as special case.
Corollary 3.5. (RAEs) ) In the n,d + oc limit, the MSE, cosine similarity and summary statistics for an RAE follow from Conjecture (.33)t setling the equation of V and taking the limit A, q,
in (14), removing the first term in the brackets in
Corollary 3.5 will be the object of further discussion in Section 4 A detailed derivation is presented in Appendix Note that Corollary 3.5 provides characterization RAEs as a function of the sample complexity a, where previous studies non-linear RAEs rely on the assumption of an infinite number available training samples [13 9.
Equations 110 and (12) of Conjecture 3.3 thus characterize the statistics of the learnt parameters b, rö of the trained DAE These summary statistics in turn, sufficient fully characterize the

---

learning metrics 5 and (6) via equations
8 and T We thus have reduced the
optimization 4 and the high- nigh-dimensional average over the train set D involved in the definition of the metrics (5) and (6) to a simpler system of equations over 4 + 6K variables (13) which can be solved numerically. It is important to note that all the summary statistics involved in (3) are finite ditensidiiiionnal as d - oc, and therefore Conjecture 3.3 is fully asymptotic characterization, in the sense that it does not involve any high-dimensional object. Finally, let us stress once more that the replica method employed in the derivation of these results should be viewed as strong heuristic, but does not constitute a rigorous proof. While Conjecture 3.3 is stated in full generality, we focus for definiteness in the rest of the manuscript the simple case r 1, K 2. which is found to already display all the interesting phenomenology discussed in this work, and leave the thorough exploration of r > K > 2 settings to future work. In the next paragraphs, of applications of Conjecture 3.3 to a simple binary isotropic mixture, and to real data sets.
give two examples
Example 1: Isotropic homoscedastic mixture We give as a first example the case of synthetic binary Gaussian mixture with K = 2. μ4 -22 E1, 0.09 x Ia. P1.2 = 1/2, using DAE with = -tanh and p 1. Since this simple case exhibits the key phenomenology discussed in the present work, we refer to it in future discussions. The MSE m
( evaluated from the solutions of the self-consistent equations (13) is plotted as the solid blue line in Fig. (left) and compared to numerical simulations corresponding to training the DAE 2 with the Pytorch implementation of the Adam optimizer [43] (blue dots), for sample complexity = 1 and & regularization (weight decay) À = 0.1. The agreement between the theory and simulation is compelling. The green solid line and corresponding green dots in Fig. (right) correspond to the replica prediction [II and simulations for the cosine similarity (6, and again display very good agreement. Note that for large noise levels, the DAE achieves a worse MSE than the rescaling -as shown by the positive value of mse;- m despite the former being a priori expressive enough to realize the latter. This in fact signals that the DAE overfits the training data. That such an overfitting is captured is strength of our analysis, which allows to cover the effect of limited sample complexity. Finally, this overfitting can be mitigated by increasing the weight decay X, see Fig. 9 in Appendix A
A particularly striking observation is that due to the non-convexity of the loss there is priori no guarantee that an Adam-optimized DAE should find a global minimum, as described by the Conjecture 3.3 rather than a local minimum. The compelling agreement between theory and simulations in Fig. [ttepinnggy suggests that aat least in this case- the loss landscape of DAES ( trained with the loss (4) for the data model ( should in some way be benign. Authors of [2] have shown, for linear RAEs, that there exists a unique global and local minimum for the square loss and no regularizer. Ref. [4] offers further insight for linear DAE in dimension d = 1, and shows that, aside from the global minima, the loss landscape only includes an unstable saddle point from which the dynamics easily escapes. Extending these works and intuitions to non-linear DAEs is an exciting research topic for future work.
Example 2: MNIST, FashionMNIST It reasonable to ask whether Conjecture 3.3 is restricted
to Gaussian mixtures (I). The answer is negative- in fact, Conjecture 3.3 also describes well a number of real data distributions. We provide such an example for MaShionMNIST [6] (from which, For each data set, samples sharing the same label were considered to belong to the same cluster. Note that we purposefully chose closely related classes, for which the clusters are expected to be closer, leading to an a priori harder- - and thus more interesting learning problem. The mean and covariance thereof were estimated numerically, and combined with Conjecture 3.3 The resulting denoising MSE predictions mse are plotted as solid lines in Fig. 2 and agree very well with numerical simulations of DAEs optimized over the real data sets using the Pytorch implementation of Adam 43 A full description of this experiment is given in Appendix [D]
for simplicity, we only kept boots and shoes) and MNIST [5] (1s and 7s), in Fig. 2
The observation that the MSES of real data sets are to such degree of accuracy captured by the equivalent Gaussian mixture strongly hints at the presence of Gaussian universality [44] This opens a gateway to future research, as Gaussian universality has hitherto been exclusively addressed in clas- sification and regression (rather than denoising) settings, see see e.g. 44 constitute a particularly intriguing setting for universality results, as Gaussian universality would signify that only second-order statistics of the data can be reconstructed using shallow autoencoder.
45 46)
Denoising tasks further
7

---

0.5
0.5
thoory MNIST
theory FashionMNIST
0.0
mse? mse;
mse) mser
-0.5
-1.0
-1.0
-1.5
-2.0
-2.5
-3.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
v
VA
Figure Difference in MSE between the full DAE (2) and the rescaling component for the MNIST data set (middle). of which for simplicity only Is and 7s were kept, and FashionMNIST (right), of which only boots and shoes were kept. In blue, theoretical predictions resulting from using Conjecture 3.3 with the empirically estimated covariances and means, see Appendix D for further details. red, numerical simulations of a DAE (p 1, a (anh) trained with n 784 training points, using the Pytorch implementation of full- batch Adam, with learning rate 1 0.05 and weight decay = 0.1 over 2000 epochs, averaged over N = 10 instances. Error bars represent one standard deviation. (left) illustration of the denoised images: (top left) original image, (top right)
noisy image, (bottom left) DAE f (2). (bottom right) rescaling
The role and importance of the skip connection.
Conjecture 3.3 for the full DAE f (2 and Corollary 3.4 for its components á (3) allow disentan- gle the contribution of each part, and thus to pinpoint their respective roles in the DAE architecture. We sequentially present a comparison of with i, and f with û. We remind that f. f and à result from independent optimizations over the same train set DD and that while f0. = the + has f * û f.
Full DAE and the rescaling component We start this section by observing that for noise levels A below a certain threshold, the full DAE f yields better MSE than the learnt rescaling f, as can be seen by the negative value of mss f msse Fig. T and Fig. 2 The improvement more sizeable intermediate noise levels A, and is observed for growing region of A as the sample complexity increases, see Fig. 3 (a). This lower MSE further translates into visible qualitative changes in the result of denoising. As can be seen from Fig 2 (left), the full DAE f 2 (bottom left) yields denoised images with sensibly higher definition and overall contrast, while a simple rescaling f (bottom right) leads to still largely blurred image.
We provide one more comparison: for the isotropic binary mixture (see Fig. T.. the DAE test error msee: in fact approaches the iiformation-theoreeee complexity increases. To see this, note that mnse* is given by the application of Tweedie's formula 42 that requires perfect knowledge of the cluster means μ4 and covariances Σ₁ is, therefore, an oracle denoiser. A sharp asymptotic characterization of the oracle denoiser is provided in Appendix B As can be observed from (a), the DAE MSE (2) approaches bbut does exactly converges to (see Appendix(C)- the oracle test error mnse* as the number of available training samples n grows, and is already sensibly close to the optimal value for a =
lowest achievable MSE mss* as the sample
DAEs with(out) skip connection We now turn our attention to comparing the full DAE
to
the bottleneck network component (3). follows from Conjecture B.3 and Corollary 3.4 that
leads to a higher MSE than the full DAE (2). with the gap being (d). More precisely,
( (du
K
Σ
PKYE
(1 (1-A)
1 d
msca msc;)
k=1
(15)
(s (sdu,()) Σ Pk
K
(1 +
kml
8

---

theory simmulations
0.08
0.1
mise m155;
mise mS3
-0.1
(mss))
-03
0.02
-0.4
-0.5
0.00
0.0
0.2
0.4
0.6
0.9
0.0
0.2
0.4
V.A 1.0
0.6
0.8
(a)
(b)
with tanh, p 1, and the rescaling f (3). Dashed: the same curve for the oracle denoiser. Different colours represent different sample complexities a (solid lines). (right) Difference in MSE between the bottleneck network 33) and the complete DAE
Figure (left) Solid lines: difference in MSE between the full DAE
In blue, the theoretical prediction (T3): in red, 1) trained with the Pytorch implementation of full-batch Adam, with learning rate = 0.05 and weight decay X = 0.1 over 2000 epochs, averaged over N 5 instances, for 700. In green, the MSE (minus the MSE of the complete DAE (2)) achieved by PCA. Error bars represent one standard deviation. The model and parameters the as in Fig.
numerical simulations for the bottleneck network (a tanh,
7
7
7
7
(a)
(b)
(c)
(d)
(c)
(1)
Figure 4: Illustration of the denoised image for the various networks and algorithms. (a) original
image (b) noisy image, for VA 0.2 (c) trained rescaling f (d) full DAE f 2 (e) bottleneck
network ú 3 (f) PCA. The DAE and training parameters are the same as Fig. see also Appendix D
The theoretical prediction 15)) compares excellently with numerical simulations; Fig (right). Strikingly, we find that PCA denoising yields an MSE almost indistinguishable from û, see Fig. 3 strongly suggesting that à essentially learns, also in the denoising setting. project the noisy data ã along the principal components of the training set. The last two images of Fig. Fig./respecca respectively correspond and PCA. which can indeed be observed lead visually near-identical results. This echoes the findings of [0] II [3 in the case of RAEs that bottleneck networks are limited by the PCA reconstruction performance conclusion that we also recover from Corollary 3.5 see
Appendix F Crucially however, also means that compared to the full DAE f 2 PCA is sizeably suboptimal, since msercA & msea m (d))
This last observation has an important consequence: in contrast to previously studied RAES 10 12 II 9 [33, the full DAE f does not simply learn to perform PCA. In contrast to bottleneck RAE networks g 9 3 the non-linear DAE hence does not reduce a linear model after training.
The non-linearity is important to improve the denoising MSE, see Fig. [ We stress this finding: trained alone, the bottleneck network á only learns to perform PCA; trained trainedJointly with the rescaling component as part of the full DAE ft, 2). it learns richer, non-linear representation. The full DAE 2 thus offers genuinely non-linear learning model and opens exciting research avenues for the theory of autoencoders, beyond linear (or effectively linear) cases. In the next paragraph, we explore further the interaction between the rescaling component and the bottleneck network.
A tradeoff between the rescaling and the bottleneck network Conjecture 3.3 alongside Corollary (3.4) and the discussion in Section 4 provide firm theoretical basis for the well-known empirical intuition (discussed e.g. in (38)) that skpp-conecttions allow better propagate information

---

from the input to the output of the DAE, thereby contributing to preserving intrinsic characteristics of the input. This effect clearly illustrated in F where the resulting denoised image of an MNIST by f. f. â and PCA are presented. While the bottleneck network perfectly eliminates the background noise and produces image with very good resolution, it essentially collapses the image to the cluster mean, and yields, like PCA, the average MNIST 7. As consequence, the denoised image bears little resemblance with the original image in particular, the horizontal bar of the 7 is lost in the process. Conversely, the rescaling é preserves the nuances of the original image, but the result is still largely blurred and displays overall poor contrast. Finally, the complete DAE (2) manages to preserve the characteristic features of the original data, while enhancing the image resolution by slightly overlaying the average thereupon.
The optimization of the DAE (4) is therefore described by a tradeoff between two competing effects namely the preservation of the input nuances by the skip connection, and the enhancement of the resolution/noise removal by the bottleneck network. This allows us to discuss the curious non- monotonicity of the cosine similarity 0 as a function of the noise level A, see Fig. F (left) While it may at first seem curious that the DAE seemingly does not manage to learn the data structure better for low A than for intermediate A (where the cosine similarity 0 is observed to be higher), this is actually due to the and there is therefore no incentive enhance the contrast by using the cluster means -which consequently learnt. This phase is thus characterized by large skip connection strength 8, and small cosine similarity 0 and weight norm [ F. Conversely, at high noise levels A, the nuances of the data already lost because of the noise. Hence the DAE does not rely on the skip connection component (whence the small values of i), and the only way to produce reasonably denoised data to collapse to the cluster mean using the network component (whence a large [
tradeoff. Indeed, for small A, the data is still substantially clean,
5 Conclusion
We consider the problem of denoising a high-ddiennsionl Gaussian mixture, by training a DAE via empirical risk minimization, in the limit where the number of training samples and the dimension are proportionally large. We provide a sharp asymptotic characterization of number of summary statisties of the trained DAE weight, average MSE, and cosine similarity with the cluster means. These results contain as corollary the case of RAEs. Building on these findings, we isolate the role of the skip connection and the bottleneck network in the DAE architecture and characterize the tradeoff between those two components in terms of preservation of the data nuances and noise removal thereby providing some theoretical insight into a longstanding practical intuition in machine learning.
We believe the present work also opens exciting research avenues. First, our real data experiments hint the presence of Gaussian universality. While this topic has gathered considerable attention in recent years, only clasiffication/reersssoo supervised learning tasks have been hitherto addressed. Which aspects of universality carry over to denoising tasks, and how they differ from the current understanding of supervised regression/classiiicate skip connection (2) provides an autoencoder model which does not just simply learn the principal components of the training set. It, therefore, affords a genuinely non-linear network model where richer learning settings can investigated.
is an important question. Second, the DAE with
Acknowledgements
We thank Eric Vanden-Eijnden for his wonderful lecture at the les Houches Summer School of July 2022, which inspired parts of this work. We thank Maria Refinetti and Sebastian Goldt for insightful discussions at the very early stages of this project.
References
[1] Yang Song, Jascha Narain Sohl-Dickstein Diederik P. Kingma, Abhishek Kumar, Stefano Er- mon, and Ben Poole. Score-based generative modeling through stochastic differential equations. International Conference on Learning Representations, 2021.
[2] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
10

---

[3] Pascal Vincent, H. Larochelle, Isabelle Lajoie, Yoshua Bengio, and Pierre-Antoing Manzagol. Stacked denoising autoencoders: Learning useful representations deep network with local denoising criterion. J. Mach. Learn. Res., 11:3371-3408, 2010.
[4] Reza Oftadeh, Jiayi Shen, Zhangyang Wang, and Dylan A. Shell. Eliminating the invariance on the loss landscape of linear autoencoders. In International Conference on Machine Learning. 2020.
[5] Daniel Kunin, Jonathan M. Bloom, Aleksandrina Goeva, and Cotton Seed. Loss landscapes of regularized linear autoencoders. In International Conference on Machine Learning, 2019.
[6] Xuchan Bao, James Lucas, Sushant Sachdeva, and Roger B Grosse. Regularized linear au- toencoders recover the principal components, eventually. Advances in Neural Information Processing Systems, 33:6971 1-6981, 2020.
[7] Gauthier Gidel, Francis R. Bach, and Simon Lacoste-Julien, Implicit regularization of discrete gradient dynamics in deep linear neural networks. In Neural Information Processing Systems, 2019.
[8] Maria Refinetti and Sehastian Goldt. The dynamics of representation learning shallow, non- linear autoencoders. In International Conference on Machine Learning, pages 18499-18519. PMLR, 2022.
[9] A. E. Shevchenko, Kevin Kögler, Hamed Hassani, and Marco Mondelli. Fundamental limits of two-layer autoencoders, and achieving them with gradient methods. ArXiv, 12//22221.1448.. 2022.
[10] Carl Eckart and G. Marion Young. The approximation of one matrix by another of lower rank. Psychometrika, 1:211-218, 1936.
[11] Hervé Bourlard and Yves Kamp. Auto-association by multilayer perceptrons and singular value decomposition. Biological Cybernetics, 59:291-294, 1988.
[12] Pierre Baldi and Kurt Hornik. Neural networks and principal component analysis: Learning from examples without local minima. Neural Networks, 2:53-58, 1989.
[13] Phan-Minh Nguyen. Analysis of feature learning in weight-tied autoencoders via the mean field lens. ArXiv, abs/2102.08373. 2021.
[14] Arnu Pretorius, Steve Kroon, and Herman Kamper. Learning dynamics of linear denoising autoencoders. In International Conference Machine Learning, 2018.
[15] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proc. IEEE, 86:2278-233 2224,, 1998.
[16] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. ArXiv, abs/1708.07747,, 2017.
[17] Adityanarayanan Radhakrishnan, Mikhail Belkin, and Caroline Uhler. Overparameterized neural networks implement associative memory. Proceedings of the National Academy of Sciences of the United States of America, 1 117:27162 - 27170, 2019.
[18] Saachi Jain, Adityanarayanan Radhakrishnan, and Caroline Uhler. A mechanism for producing aligned latent spaces with autoencoders. ArXiv, 15556100..1446, 2021.
[19] Thanh Van Nguyen, Raymond K. W. Wong, and Chinmay Hegde. On the dynamics of gradient descent for autoencoders. In International Conference on Artificial Intelligence and Statistics, 2019.
[20] Thanh Van Nguyen, Raymond K. W. Wong, and Chinmay Hegde. Benefits of jointly training autoencoders: An improved neural tangent kernel analysis. IEEE Transactions on Information Theory, 67:4669-4692, 2019.
[21] Giorgio Parisi. Towards mean field theory for spin glasses. Phys. Lett, 73(A):203-205. 1979.

---

[22] Giorgio Parisi. Order parameter for spin glasses. Phys. Rev. Lett. 10:1946-1949 1983.
[23] Lenka Zdeborová and Florent Krzakala. Statistical physics of inference: thresholds and algorithms. Advances Physics, 65:453 552, 2015.
[24] Marylou Gabrié. Mean-field inference methods for neural networks. Journal of Physics A: Mathematical and Theoretical, 53, 2019.
[25] Elizabeth Gardner and Bernard Derrida. Optimal storage properties of neural network models. Journal of Physics A: Mathematical and general, 21(1):271, 1988.
[26] Manfred Opper and David Haussler. Generalization performance of bayes optimal classification algorithm for learning perceptron. Physical Review Letters, 66(20):2677, 1991.
[27] Jean Barbier, Florent Krzakala. Nicolas Macris, Léo Miolane, and Lenka Zdeborová. Optimal errors and phase transitions in high nigh-dimensional generalized linear models. Proceedings of the National Academy of Sciences of the United States of America, 1 116:5451 - 54600, 2017.
[28] Benjamin Aubin, Florent Krzakala, Yue M. Lu, and Lenka Zdeborová. Generalization error in digeesiinnni perceptrons: Approaching bayes error with convex optimization. Advances in Neural Information Processing Systems, 33:121 18:11119112211 2020.
[29] Benjamin Aubin, Antoine Maillard, Jean Barbier, Florent Krzakala, Nicolas Macris, and Lenka Zdeborová. The committee machine: computational statistical gaps in learning two-layers neural network. Journal of Statistical Mechanics: Theory and Experiment, 2019, 2018.
[30] Rainer Dietrich, Manfred Opper, and Haim Sompolinsky. Statistical mechanics of support vector networks. Physical review letters, 82(14))2975, 1999.
[31] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, 2020.
[32] Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Generalisation error in learning with random features and the hidden manifold model. Journal of Statistical Mechanics: Theory and Experiment, 2021, 2020.
[33] Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Error rates for kernel classification under source and capacity conditions. ArXiv, abs/2201. 020/22001.26555... 2022.
[34] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592-5628, 2018.
[35] Jacob A. Zavatone- Veth, William Tong, and Cengiz Pehlevan. Contrasting random and learned features deep bayesian linear regression. Physical review. E, 105 6-1:041118, 2022.
[36] Hugo Cui, Florent Krzakala, and Lenka Zdeborová. Optimal learning of deep random networks of extensive-width. ArXiv, hbb//230.000355. 2023.
[37] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Computer-Assir Assiste Intervention-MIICAA 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18, pages 234-241. Springer, 2015.
[38] Xiao-Jiao Mao, Chunhua Shen, and Yubin Yang. Image restoration using convolutional auto- 2016.
encoders with symmetric skip connections. ArXiv,
[39] Tong Tong, Gen Li, Xiejie Liu, and Qinquan Gao. Image super-resolution using dense skip connections. In Proceedings of the IEEE international conference on computer vision, pages 4799-4807, 2017.
[40] Jiwon Kim, Jung Kwon Lee, and Kyoung Mu Lee. Accurate image super-resolution using very deep convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1646-1654, 2016.
12

---

[41] Jiwon Kim, Jung Kwon Lee, and Kyoung Mu Lee. Deeply-recursiv convolutional network for image super-resolution In Proceedings the IEEE conference on computer vision and pattern recognition, pages 1637-1645, 2016.
[42] Bradley Efron. Tweedie's s formula and selection bias. Journal of the American Statistical Association, 106:1602 1614, 2011.
[43] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, abs/1412.6980, 2014.
[44] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. The gaussian equivalence of generative models for learning with shallow neural networks. Mathematical and Scientific Machine Learning, 2020.
[45] Hong Hu and Yue Lu. Universality laws for high-dimensional learning with random features. IEEE Transactions on Information Theory, 1964, 2020.
[46] Andrea Montanari and Basil N Saced. Universality of empirical risk minimization. In Confer- ence on Learning Theory, pages 4310-4312. PMLR, 2022.
[47] Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with teacher-student model. Journal of Statistical Mechanics: Theory and Experiment, 2022, 2021.
[48] Bruno Loureiro, Gabriele Sicuro, Cédric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborová. Learning gaussian mixtures with generalised linear models: Precise asymp- totics in nigh-dimensions. In Neural Information Processing Systems, 2021.
13

---

A Derivation of Conjecture 3.3
In this section, we detail the derivation Conjecture
3.3
A.1 Derivation technique
In order to access sharp asymptotic characterizations for the metrics and summary statistics mse 5 (6. 0 and Ii the first step is to observe that any test function (i, b) of the learnt network parameters ui, b can be written as an average over limit probability distribution
/ dwddbypw b)e (R((.b))
ED (1ū 8)]
lim ED $0+00
(16)
7
where R(--)) is the empirical risk 4 and the corresponding probability density
P3 (w, b)
(17)
2
is known as the Boltzmann measure in statistical physics, with the parameter 3 typically referred to as the inverse temperature. The normalization called the partition function of Pa:
/
duvdbbe ddwdde--Rtten (
(18)
The idea of the replica method 22 23 24
building the expression [6], is compute the moment generating
function (also known as the free entropy) as
In EpZ"
Ep In
lim 6
(19)
With the moment generating function, it then becomes possible to compute averages like (16). The backbone of the derivation, which we detail in the following subsections, therefore lies in the computation of the replicated partition function Zp
A.2 Replicated partition function
For subsequent clarity, we shall introduce the variable
17" az 14g
(20)
if x belongs to the k-th cluster. By definition of the Gaussian mixture model, this is just Gaussian variable: 77 ~ (0, ) and the average over the data set {x"} reduces to averaging over the cluster index & and (n²) For notational brevity, we shall name in this appendix 5o what is called V in the main text (i.c., absorbing the variance in the definition of (.). The replicated partition function then reads
-B s(wu") a=t
ED
II
dw d
K
S p (xx( Jo (Mo(VT-Xin
n.
(21)
p=
One can expand the exponent (*)as
Waw
maivT (aa (o))t)) 322
2o
malvT tm)
wea((1 (oll-baTT-e I- 11 (m) - K.
vi
P(
1nl 20 nit 2 2ww.ttt/ttt........ ( went MInTEnt Te]
X
(22)

---

Therefore
1/4 |l
{
dpdP
E.,. Σ PEC
(2 dee En
1n
+s E a-l
(VT=an
1111 (
+, E 1/
2 (1-vT=2ha Puy nthulyt- 11pa,, EthulyT-ate ( -1
-=1
Patt (n.
wara we (vi a 02
- wa
) T wa ((1-bo (1-
va
via
(23)
The effective prior over the noises n7 & is Gaussian with means pag: Mhy and covariance C:
C Cen la
I") Ila
Pet. (e..nn.. E) N 17: S us:
(24)
Oee
C
Identifying the covariance components leads to
8
8
CEe A
+ 8
b
=
+ B Σ (v1- Ab, 1)
CET
3
by ba(v Ab, - 1). (25)
m
Note that all the sums indexed by a introduce terms of ((s). which can safely be neglected. Identifying the means leads to the following system of equations:
C
ME
-CE) My 3 Σ ba /1 Abo)uu
(26)
C. M4n + C 1gg = -3 Σ (1 vI bbab)) )b,)214
a=1
which is solved as
#gg 3 (C (CTT))
Σ
C ba VI Abo) + C vI Aba) pes
=0
By -B (Cml
(C
Σ
C 3E
vI Ab,) + C vI Aba)lla) pe.
(27)
Again, observe that ohj of (s) and will be safely neglected later in the derivation. Therefore
K
L 11
( Joee lig 2+ tuj ond ond uT
E (s,
Pk
det A det (C,j Cet (C,, 1121.)
T
walvi
Aln +m) 32
-20 waiVI Blay im)ie))
T wal(1 b. AMan 6.
va
va
vi
(28)
Pon: (n.
(a)
We are now in position to introduce the local fields:
x w.(E 11))
W., (n pn))
h Walt
X7
(29)
Vd
Vd
vd
with statisties
W. E m (AAA))
(AE = Cen
We, u O,
(XE25) A
w0, W
(30)

---

We used the leading order of the covariances
C Cs.m.nn. One therefore has to introduce the summary statisties:
Wa 2 ab d
Rexp,
S
Wa Dpug
RPP.,
* m
Wafkk
E
Rs.
(31)
Vd
Note that the local fields X thus follow a Gaussian distribution:
S* 0,
12)=0)) ~ N
(32)
AQ
EN
Going back to the computation, (a) can be rewritten as
e $ no Quae ( sa D IT Z )0
20 (ua) x c
aanga-vi-aaa -aae Sha badi)]
(33)
A.3 Reformulating saddle-point problem
Introducing Dirac functions enforcing the definitions of Qab, brings the replicated function in the following form:
K
K
EZ
ddQandQ.. db
II
IIII 1=
dm, dring
IIII
dS dš ab
ab
a=1
a.b
a,b
Qai -d
Σ St
Σ dm
ag
lesh
gosdRe
-8 g(w Σ Q.w.
& E D.w, +
En Saw.
dwae
c0022e 4 1ug1? & (vT 13?
ad
K
Pk
(a)
(34)
det E det (C, Cas O(53)) 7
quadd. +.2d
We introduced the trace, entropic and energetic potentials e. ... vy Since all the integrands scale exponentially (or faster) with d, this integral can be computed using saddle-point method. To proceed further, note that the energetic term encompasses two types of terms, scaling like sd? and sd. More precisely.
Zbb 1)2
Pk
det A C (a)
K
8
1 sd
Pk sd
In
V dat dot(C, (2)) Pk In(a)
Σ
Pk
|
2 (
bb
1)2
2
k=1
k=1
a=
0k ln
( (aderE,AAdel(C toad a In(a)
R e
(35)

---

Note that the saddle-point method involves intricate extremization over matrices Q₁ To make further progress, we assume the extremum realized at the Replica Symmetric (RS) fixed point
Va,
b b
va,
m mg m mis
(2 + dab +
Va, b,
Qab = (r- - 4) dab + 9:
Qas =
nk
Va,
Sab = (rk 9k )db + 9k
St
+ qx
8ab + 91
(36)
2
This is standard assumption known as the RS ansatz 21
Quadratic potential The quadratic potential V quaad. which correspond to the leading order term in d in the exponent, needs to be extremized first in the framework of our saddle-point analysis. Its expression be simplified
K
Σ
Pk In (vaet En det(C dct(c_)))3)))))
Σ
Pk In det (1 + ABsb²) (Is E&Bs(VI Ab =
As
K
Pk Tr
Ab² 2 En 66-11 - 1)²
2
Bds
Ab + (vI - Ab - 1)2 1 Σ
P Tr Σか
(37)
k=1
which is extremized for
K
1
Σ Pk Tr Ei
VI-A
d
b
Aml
(38)
K
Σ
Pk Tr Ex
(1 A) +4
This fixes the skip connection strength b.
Entropic potential parameters
We now turn to the entropic potential V. It is convenient to introduce the variance order
V ž
V/ = îr + qN-
(39)

---

The entropic potential can then be expressed as
BodV
/
II
Σ Ti -8 3Σa(w")-3
Tr | +m
E vami wi Mh
dwag
0.b
E-lo=l
Tr Ven Exw +
Σ Σ To
X e
k=1n=1
k-1ab
K
D II
D
k=1
/
dwe -By(w) I (oww" - + V +
vamau" 2 30000))) s
K
DE 0 D
k=1
DE
/ duve
-B((w) tw Vol++ Σ V.D. ow
{Σ
Vanaa T 2.00 )ow
Am)
(40)
Therefore
3V = / DEIn In I Sg(w) two Volst
Σ F. ow+
( Vamnu
(41)
For a matrix 3 E RPxd and tensors A, B E R & Rexd, we denoted (BOA) = Eis E A. and (AoB);
Ene Ad
Energetic potential In order to compute the energetic potential Vy one must first compute the inverse of the covariance S4g given by
22 = [st
0
(42)
1 12-1
A
straightforward to see that ST Q-1 share the same block structure as Sk. Q. and we shall name for clarity
(ST ab (Fx - . dub + qk.
(Q- (f 0 8ab q.
(43)
From the Sherman- Sherman-Morisson Morisson lemma, and noting
V = Tb 9k E R2
= r E RPXp,
(44)
one reaches
V-V (V + sq)--q/'"" qV
f = V/ (V, + sqi) - 9k. Vi-
(45)
i = -V + sq) -lgV-1
9r - (Vi + 891 -1 1/=
We will also need the expression of the determinants
det Sa = det V4 + 8 Tr [[]]
Q = s +sTr(V-1g]
(46)

---

One can finally proceed in analyzing the term (a):
dxpAap
(a) Rr (2TT)Px det Q det Sx A
4=1
- E (22) (fx 42) ( -cdo (x2) (f-
x
u-1
n.
DEDT
(2T) /det Q det S PM
RP
1/ dindlge V2 "n Vo o5
a 20 20 V JI v -- (0)
DEDm If N (N N (MriuRe, Vo) e- =(co)]
/ DED
N (Nri vi) e-(0))))))) 2(.))
(47)
where we noted with capital D integral over a p- dimensional Gaussian distribution .V(O. Ip). Therefore
K Σ
DEDm / N (M::VEnAe,AA) N (n e e-((x))
3
(48)
k=1
A.4
zero-temperature limit
In this subsection, we take the zero temperature oc limit. Rescaling
V t V,
BV + V.
g²g t 4
8
1
Vv t Ve,
BV,
Vx,
3 4s
Bin mrn
(49)
one has that
K Eか
K
K
102)
))
Tr
(OOL+
Σ
v/ 2
Q la + Σ
9k x Σ +
Σ
my
T
E,,,(
2d
(50)
where we introduced the Moreau enveloppe
(,)
inf
(velu E Fo )ow- (voLot kill
K nox.) ( /
t
x mune
+ g((e)
2
j.
(51)
Note that while this optimization problem is still cast in a space of dimension x d, for some regularizers g(-) including the usual 412 penalties, the Moreau enveloppe admits a compact analytical expression.
The energetic potential V also simplifies in this limit to
K V = Σ
(52)

---

Where
Mx(S,n) = =iinf Tr V-1 (y q3 - mk
092
1
Tr V-1 (x - vAyzs) 02
k
A
Tr go Ay + x)
20 Coovv Dy + 2) ((1 v1 -b-y bo) ) (53)
It is immediate to that the trace potential v, can be expressed
Tr [g] Tr[ov]
K
K Σ
V
+ 2
Σ
(Tr
Viga
Tr( Vil)
mgmn-
(54)
2
k=1
Putting these results together, the total free entropy reads
Tr V9
Tr(jV]
K
①
extr q.m, V. V.Gaamm. me.. Ae, M., to.)
Tr
-Tr/as
Vol)
mgfrk
2
k=1
k=1
Pk PREg,nMA(E.n) - B.)
K
K
82
Tt
V Ta
Σ
Vi & Ex
q
ll + Σ
Σx +
Σ
mitei
(55)
2d
where we remind that
Mr(5, n)
inf 22.9
TF Vi (y 9 m&
682
+ Tr V-1 (x g+g 027
20 - Ay + x) T ((1 - VT Ab)y bx) } (56)
+ +Tr[golVi Ay + 82
and
M,
inf
( -
x
K ( ) (Vore+ 2 noxz) a-1
K ((00)))
E (1 d x max?) ) r(())
m
(57)
20

---

A.5 Self-consistent equations
The extremization problem (58) can be recast as a system of self-consistent equations by requiring the gradient with respect to each summary statistic involved in 58) to be zero. This translates into:
du axp V (proxf.
q ma
82
V
Va appak VE
prox
96 "1
mk
"
mi applBen Vi=
(proxf
(58)
K
prrxx - q2tE) 602 V-1
q Σ PbBB,, V-1
V = Σ
9 -V-1 prox* q+ 5T - (v1 Aprox, + prox,)
82
k=1
V& = 1 E
prox, @ (gx @ ΣP,
(Ip @ Σx) Ex]
9h EE
prox, ExpOOx
mg V E
E [prox,,uss]
(59)
V = E prox, @ (9 Ia) =
q = E prox,proxx
We remind that the skip connection is fixed
K
d
Σ
Pk Tr Ei
VI-A
(60)
K
Pk Tr E3
+)+
A.6 Sharp asymptotic formulae for the learning metrics
The previous subsections have allowed to obtain sharp asymptotic characterization for a number of summary statistics of the probability (17). These statistics in turn sufficient asymptotically characterize the learning metrics discussed in the main text. We successively address the test MSE (5). cosine similarity (6) and training MSE.
MSE
The denoising MSE reads
( 16VI-A(me + +n) + bV va
T
/w(V] - A Alpa + n) + vDg)
Ek.n.
Ni +
Vd
Tr go (V--Smttt/ottt
msse
K
2
Pk
(0,1) u0
[=(VI-Am-ttaal---eew-- ( -VTVVn)
(61)
1=1
where
dAb2 + v1 2b)
Σ Pk (11eax)2 2 Tr Exs)
(62)
Cosine similarity
By the very definition of the summary statistics my.
2.
(mz))
0% =
(63)
21

---

theery
0.8
theory simulations
0.08
0.06
mse) Er
0.4
0.04
0.02
0.00
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.0
1.0
VA
tanh). Solid lines represent the sharp asymptotic formula (68: dots correspond simulation, training the DAE with the Pytorch implementation full-batch Adam, over 7 = 2000 epochs using learning rate 0.05 and weight decay À = 0.1. The data was averaged over N = 5 instances; error are smaller than the point size. (right) Generalization gap mse; <t- Solid lines correspond the asymptotic prediction of Conjecture 3.3 (for the test MSE) and of (68) (for the train MSE), while dots correspond to simulations. Error bars represent one standard deviation. The Gaussian mixture is the isotropic binary mixture, whose parameters are specified the caption of Fig. the main text.
Figure 5: (left) Training MSE for the full DAE 2 (p= 1.
Training error The replica formalism also allows to compute a sharp asymptotic characterization for the training MSE
= ED
1 nd
Σ
x
f( ||
(64)
We have skipped the discussion of this learning metric the main text for the sake of conciseness, but will now detail the derivation. Note that the training error é be deduced from the risk (4 and the average regularization
1 5 = Ep R b)] Ep [r(z)]
(65)
Note that in turn, from the definition of the free entropy, the average risk (training loss) be computed
1 10h Z
1 0Φ
Ep R(w 8)
lim 8
lim 8
(66)
3 08
3 03"
Doing so reveals
O(
deD quad
5m(vi (I Ab 1b-1)
= 2 lim
8-500
03
SN (Neiste, N (Anigks, v) (t)e 220)
msc.
lim
Σ
Pk
DE
(67)
8-+00
R2
SN (Neiote, Vv) N (Xnigh e-(()))))))))))))))))))))))))e ((,)
Taking the B > oc limit finally leads to
Tr gar( /1 Aprox, prox, )02]
MSC.
Pa E.n
20 Aprox, prox.) (oox))((1) T(1 v1 Ab)prox, bprox,)
(68)
The sharp asymptotic formula (68 agrees well with numerical simulations, Fig. 5 As intuitive, the generalization gap m j grows with the noise level A, as the learning problem grows harder.
22

---

A.7 Generic asymptotically exact formulae
This last result ends the derivation of the generic version of Conjecture 3.3 i.c not assuming Assumptions 3.1 and 3.2
asymptotically exact, but not firly asymptotic, as the equations (58) still involve high-dimensional quantities. In practice however, for standard regularizers r(-) like f or f2, the proximal prox, admits a simple fooed-form expression, and the average over E can be carried out analytically. The only high-dimensional operation left is then taking the trace of linear combinations of Σ₁ matrices (or the inverse of such combinations), which is numerically less demanding, and analytically much simpler, than the high dimensional optimization 4 and averages (5) involved in the original problem. We give in the next paragraph an example of how Assumption 3.T can be relaxed, for binary mixture with arbitrary (i.e. not necessarily jointly diagonalizable) covariances E1...
Importantly, note that the characterization (58) is, like the formulae in c.g.
Example: Anisotropic, heteroscedastic binary mixture As an illustration, we provide the equivalent of (58) for a binary mixture, with generically anisotropic and distinct covariances, for p = 1, thereby breaking free from Assumption 3.1 We index the clusters by +, rather than 1, 2 for notational convenience. We remind that
- inf 2x 1t (o (= (ile--/VV/+++ - (0 VI-V--- 1b11- bo))
M=(E,n)
(69)
Then the self-consistent equations
58)
simplify to
1 Tr q a
(A + V) + E, E+ + V-Σ.) (Tl + q + + + m2 m2ddpp))
(A++ + V, E + +VE )² mm
i Tr
V = 1 Tr
(A+ V4 E+ + +VEE
d
I Tr
[(+ 1.
-P V.
' ' (A EE++RLE. "( " E- +mpd
V4 = Tr Σ+ (A + 1) + E. + +V-E_
m = Pv. 1 Esn (prox - V - m) - (1 - (1-p) Eg,, (prox, - -V-- + m)]
i = a
( - VIV + - [1-))BBen(pros - vVV AC)2]
VI
V-
PEEn
E(proxt VTV o(V1 Aproxt + proxt )a
VOVaV
+(1 P)E..
E((pTox, -VVVAS) ViVAV
a(VII ( prox; }²]
(70)
④t ap VP BE. (proxt - -4+1 - mm)²
i- a(1 p) f) (prox, 77- + m
V. ap /i V, Eg,r (proxt /4+1/ m) 1)
V_ -a(1 p) o. Benn
Ee,. (prox, - +
These equations are, as previously discussed, asymptotically exact as d + xc. While they still involve traces over high-dimensiooal matrices Σg. this is very simple operation. We have therefore reduced the original high-dimensional optimization problem (4) to the much simpler one of computing traces like (70). Crucially, while these traces canmot be generally simplified without Assumption [3.1] they provide the benefit of simple and compact expression which bypasses the need of jointly diagonalizable covariances, and which can thus be readily evaluated for any covariance, like real-data covariances. This versatility is leveraged in Appendix D
A.8 End of the derivation: Conjecture
We finally provide the last step in the derivation of the fully asymptotic characterization of Conjecture 3.3 Assuming r(.) 1/2 (Assumption) 3.2) the Moreau envelope M, assumes a very simple expression, and no longer needs to
23

---

be written high-dimensiionll optimization problem. The resulting free energy can be compactly written as:
Tr [gg
-Tr[ev]
①
extr
Σ TT
VeOk
Tr(âa
Σ mgm
V. Me
g,m,
V2.
2
a
K
-1
K
K
82
+
ATpp Olp +
Vi & Σ/
④ Id +
q 2
Σx
+
d
Σ
(71)
2d
R=1
(+) is the only segment which still involves high-dimensional matrices, and is therefore not yet full asymptotic. Assuming Assumption 3.1 (+) can be massaged into
(+)
Σ Tr
(A+ (++V+At0 + xtto)"
(
q+
qN +
Σ
e T Hi
2d
1=1
k=1
ISkISK
d d=
1
du(7; Tr (A+V+
k
i
+
Qk
+
TyTamiiiK
(72)
2
k=1
1škjjKK
The fully asymptotic free energy thus becomes
Tr
V1
Tr(gV]
extr g.m. V.d.n, Age.m.. de M.
Σ (Tr [zgh
-Tr(aa V&l)
mgrn
2
K
Ph Mu(Enn)
K
+ du(t,))
(A+V+ -
i
Σ
Uh +
Σ
(73)
km
1SkjSK

---

Requiring the free energy to be extremized implies
Ô asp V (proxt,
82
9h 1 mk
k
V/2 xppa V
prox
4r 11
1/
mkk 11
ma = a. V
prox
9% 13 mk}
(74)
K
qtt) 82 V-1
q = Σ Pa PrB., V-1
Xroxx
k=1
V = a Σ PxBesn
K
9- v- (prox - -5b5 5- -a -Vr--prr + prox 82
Sproxt
==1
-2
K
9: s dulr, Th7
AIp + V
Σ
Yi
-+
Σ ISMKK
TyniMi
f=1
/=1
K
V& = f du(7)
AI + V +
Σ
73V/
1=1
k
K Σ Tym
m& f du((
AIp + v
Σ
73s 2/13
(75)
1=1
K Σ
9= T
Mlp + Σ T;
Tyniiim
j=l
1=1
K AIp + V + Σ 15
V = J 7)
3-1
which is exactly
13 This closes the derivation of Conjecture 3.3
As a final heuristic remark, observe that from 74) it is reasonable to expect that all the hatted statistics ÿk. Vk, m, q, V should be of order O(a:) a >> 1. As consequence, Vi- O(1/a) and q. m, [k, my should approach their a 00 limit as (a)). Therefore, the MSE (61) should also approach its a - oo limit as O(1a).
A.9 Additional comparisons
We close this appendix by providing further discussion on some points, including the role of the non-linearity (.),, the influence of the weight-tying assumption, and of the (an- (an-)isotropy and hattto/hhteroosscdsssttttii of the clusters.
The activation function The figures in the main text were generated using tanh. Several studies for RAEs, however, have highlighted that an auto-encoder would optimally seek to place itself in the linear region of its non- linearity, so to learn the principal components of the training data, at least in the non-linear untied weights case, e.g. 3. 8. In light of these findings, it is legitimate to wonder whether setting a linear activation d (zz) = x would not yield better MSE. Fig. shows that it is not the case. For the binary isotropic mixture (3).. the linear activations yield a worse performance than the tanh activation.
Weight-tying We have assumed that the weights of the DAE 2 were tied. While this assumption originates mainly for technical reasons in the derivation, note that it has been also used and discussed in practical setting (3 as way to prevent the DAE from going to the linear region of its non-linearity, by making the norm of the first layer weights very small, and that of the second layer very large to compensate (8) A full extension of Conjecture 3.3 to the case of the untied weight is a lengthy theoretical endeavour, which we leave for future work. However, note that fog. in the binary isotropic case, that untying the weights actually leads worse MSE than the DAE with tied weights. This is very interesting observation, as a DAE with untied weights obviously has the expressive power to implement a DAE with tied weights. Therefore, this effect should be mainly due to the untied landscape presenting local minima trapping the optimization. A full landscape analysis would present a very important future research topic. Finally, remark that this stands in sharp contrast to the observation of [8] for non-linear RABS, where weight-tying worsened the performance, as it prevents the RAE from implementing a linear principal component analysis.
25

---

0.6
tanh, tied
linear, tied
0.4
-
tanh, untied
msej mse;
0.2
-0.
-0.4
0.0
0.2
0.4
0.6
0.8
Figure 6: Same parameters as Fig. in the main text. a = 1, P1,2 1/2, E = = Ia. 1- = 1; the cluster
mean μ1 -12 was taken as a random Gaussian vector of norm 1. Difference in MSE between the full DAE 2 and the rescaling network f (3) for (.) tanh (blue) or a (x) x (red). Solid lines correspond to the sharp asymptotic
characterization (T3), which is particular case of Conjecture 3.3 Dots represent numerical simulations for d = 700, training the DAE using the Pytorch implementation of tull-batch Adam [43], with learning rate r = 0.05 over 2000 epochs, averaged over N 2 instances. Error bars represent one standard deviation. In dashed green, numerical simulations for the same architecture, but untied weights. The learning parameters were left unchanged.
An important conclusion from these two observations is that, in contrast to RAEs, the DAE 2 does not just implement a linear principal component analysis - weight tying, and the presence of non-linearity, which are obstacles for RAEs in reaching the PCA MSE, lead for DAEs 2 to a better MSE. The model (2) therefore constitutes model of genuinely non-linear algorithm, where the non-linearity is helpful and not undone during training. Further discussion be found in Section of the main text.
Heteroscedasticity, anisotropy Fig. I and in the main text all represent the isotropic, homoscedastic case. This simple model actually encapsulates all the interesting phenomenology. In this paragraph, discuss for completeness the generically heteroscedastic, anisotropic case. We consider a binary mixture, with covariances Σ Σ₂ independently drawn from the Wishart-Lagun Laguurre ensemble, with aspect ratios 5/7 and 6/6. Therefore, the clusters anisotropic, and eigendirections associated with the largest eigenvalues are more "stretched" (i.e. induce higher cluster variance). Furthermore, since the set of eigenvectors of Σ, Eg are independent, the two clusters stretched in different directions. To ease the comparison with Fig. (isotropic, homoscedastic), these Wishart matrices were further divided by 10, so that the trace is approximately 0.09 like in Fig- -- i.e.. the clusters have the same average extension. Fig. 7 presents the resulting metrics and summary statistics. Again, the agreement between the theory 3.3 and numerical simulation using Pytorch is compelling. Qualitatively, the observations made in Section 4 still hold true in the anisotropic heteroscedastic case:
The curve of the cosine similarity still displays a non-monotonic behaviour, signalling the preferential activation by the DAE of its skip connection at low A and of its network component at high A.
The skip connection strength b is higher small A and decreases, in connection the previous remark.
The norm of the weight matrix t overall increases with the noise level A, signalling increasing usage by the DAE its bottleneck network component, again in accordance to the previous remark.
Therefore, the generic case does not introduce qualitative changes compared to the isotropic case.
Strength of the weight decay X la regularization (weight decay) À = 0.1 was adopted in the main text. In fact, the value of the strength of the weight decay not found to sensibly influence the curves, and again, the qualitative phenomena discussed in Section 4are are observed for any value. F8g. shows, for an isotropic binary mixture, the MSE difference mss mseş (5) and the cosine similarity 0 (6) for regularization strength
0.1 and À 0.001. As can be observed, even reducing the regularization hundredfold does not change at all the qualitative picture in particular, the non-monotonicity of the cosine similarity, discussed in Section 4 - and very little the quantitative values. On the
26

---

mGG8 - m64
0.2
0.0
-02
-0.3
-0.4
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
V
0.1, tanh; the cluster mean μ4 - P2 was taken as a random Gaussian vector of norm 1. The cluster covariances were independently drawn from the Wishart-Laguerre ensemble, with aspect ratios 5/6 and 5/7, before being normalized by 10 to match the trace of the isotropic case in Fig. In particular, the eigenvectors and heteroscedastic. (left) In blue, the difference in MSE between the full DAE Solid lines correspond to the sharp asymptotic characterization of Conjecture 3.3 in its generic formulation (58). Dots represent numerical simulations for d 500, training the DAE using the Pytorch implementation of full-batch Adam 43]. with learning rate 7 = 0.05 over 2000 epochs, averaged over N = 5 instances Error bars represent one standard deviation. (right) Cosine similarity 0 (6) (green), squared weight norm || /a (red) and skip connection strength (blue). Solid lines correspond to the formulas (1I [2) and (10) of Conjecture 3.3] dots are numerical simulations. For completeness, the cosine similarity of the first principal component of the train set is plotted in dashed black.
Figure 7: a 21, 1/2pp 1,
independent, the mixture is totally anisotropic with different main variance directions
and the rescaling network / (3).
0.6
0,8
mse mse>
0.4
0.6
0.2
0.2
== 0.1
0.4
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
/A
V
Figure 8: Same parameters as Fig. in the main text. 1,K = 2, 1/2, Σ 0.09 x la,p= 1, (anh: the cluster mean μp = -/2 was taken as random Gaussian vector norm 1. Difference in MSE between the full DAE (2) and the rescaling network 33 for 0.1 (blue) or 0.001 (red). Lines correspond to the sharp asymptotic characterization (3) of Conjecture 3.3 Dots represent numerical simulations for d 700, training the DAE using the Pytorch implementation of full-batch Adam [43, with learning rate = 0.05 over 2000 epochs, averaged over N instances. (right) Cosine similarities. for > = 0.1 (green) and À 0.001 (orange); lines correspond to the asymptotic formulae of Conjecture 3.3 dots represent the numerical simulations.
27

---

0.3
0.1
0.2
05
0.0
-0.1
-0.
0.0
0.2
0.4
0.6
0.8
1.0
Figure 9: Like Fig. 1 of the main 0 = mean |41 = 22 was taken as random Gaussian vector of norm 1. (left) Solid lines correspond to the difference in MSE between the full DAE (2 and the rescaling component (3) as predicted by Conjecture 3.3 Different colors indicate different regularization strength A. For large noises A and insufficient regularization X, the DAE overfits the train set, leading to performances worse than the simple rescaling A, as signalled by positive values of mse msef. This effect is suppressed for larger regularizations A.
P1.2 -
2. Σ 0.09 x =..p=1,,(() ttanh.); the cluster
MYG4) MSR0)
theory
rise mSc:
0.010
simulations
0.008
0.004
0.00
0.0
0.2
0.4
0.5
0.8
1.0
0.0
0.2
0.4
0.5
0.8
1.0
0.09 - 1, = taah(-).. (left) Difference between the MSE of the DAE f and the MSE of the rescaling msse insep in the case of single Gaussian cluster. Solid lines correspond to the theoretical prediction of Conjecture 3.3 and dots to numerical simulations. the case of a single cluster, the bottleneck component of the DAE is not needed, and its presence leads to detrimental overfitting, signalled by the positive value of mse; msse.. (right) Difference between the MSE of the DAE f and the MSE of the bottleneck network û, divided by d. Like the K case (see Fig. (b)), this difference is of order Oz(d), and the MSE of PCA (green dots) is sensibly equal.
Figure 10: a L,
other hand, observe that at the level of the MSE increasing the weight decay helps palliate the overfitting at large noise levels A, as we further illustrate in Fig
K cluster We finally discuss the case of unstructured data, where the Gaussian mixture only has single cluster.
Analytically, this corresponds to setting the norm of the cluster mean || to zero in Conjecture 3.3) The bottleneck component, whose role is to learn the data structure denoising performance, is no longer needed when the data is unstructured. It presence actually leads the DAE to overfit, be observed in Fig I0 (left). Similarly, the PCA denoiser performs worse in the unstructured case, with an associated MSE remaining of order (d)) see Fig 10 (right).
given by the cluster mean-and leverage it improve the
28

---

B Tweedie baseline
B.1 Oracle denoiser
Tweedie's formula noise, as
42
provides the best estimator of a clean sample given noisy sample ă corrupted by Gaussian
A A
t(
VP
(76)
Note that this gives the Bayes-optimal estimator for the MSE, assuming perfect knowledge the clean data distribution P from which the so-called score VP has to be computed. Of course, this knowledge is inaccessible in general, where the only information on IP is provided in the form of the train set D. Therefore, Tweedie's 's formula does not give learning algorithm, but allows to give oracle lower-bound the achievable MSEs, any learning algorithm will yield a higher MSE than this information-theoretie baseline.
For generic Gaussian mixture ( Tweedie's formula reduces to the expression
Pk k Σx
ALd) Ald)-'a
(E + Ald) -1 (mx) N (i pak Ex + AlA)
f(x) = VI A
(77)
Σ MnN (r;; juks Ee Ala)
where noted
B4 = VI Apk
Σx = (1-1144 A)ΣE.
(78)
B.2
Oracle test MSE
In general, except in the complete homoscedastic case where all clusters have the same covariance, there is no closed-form asymptotic expression for the MSE achieved by the Tweedie denoiser. In the binary homoscedastic μ4 112 = nr, E1 Eg = T (see Fig. D. Tweedie's formula (77) reduces to the compact form
VI-
A
tanh ② -VI-A 62 - (P(1-)++A
((x)
(79)
02 A)+
02
A
A
Note that this is of the same form as the DAE architecture
2
The associated MSE reads
Au
VV- (VI Ax E
iise" E..
x (vI Ax +) +
(80)
02
A + + o
0²(1 - A + A
sharp asymptotic formula be found to be
mss
mse.
+
6
1(0.1)
(1- (1-A)+tV--Asx// A+
(02 A
2)
02(1-A +A
2A
(1-A)styI-aax A+(1-A)63
((1 (1-bv1--)))
(81)
0² -
02(1- A) + A
This is the theoretical characterization plotted in Figs. andd in the main text.
As discussed in the main text and illustrated Fig. Fig.3 left), the MSE of the DAE approaches the oracle MSE (8 as the sample complexity a grows. On the other hand, the DAE MSE does not exactly converges to the oracle MSE
co. Intuitively, this is because of the fact that while the form of the oracle (79) is that of a DAE, it does not have tied weights, like the considered architecture (2). The latter cannot therefore perfectly realize the oracle denoiser, whence small discrepancy, as more precisely numerically characterized in Fig.
29

---

8: 0==02
0
8, 0.8
-0,4
-0.5
10a
10'
10'
10a
10'
1.2 0.09 la.p 1, taah(-); the cluster mean μ1 422 was taken as a random Gaussian vector norm 1. Solid lines correspond to the difference MSE between the full DAE f and the rescaling component f as predicted by Conjecture 3.3 In dashed lines, the oracle MSE (8I). minus the rescaling MSE msee. Different colors correspond to different noise levels A. As the sample complexity becomes large, the denoiser MSE approaches the oracle baseline, but does not become exactly equal to as a - oc.
Figure 11: Like Fig. I of the main text, K = 2, P1,2
2
C Bayes-optimal MSE
C.1 Assuming imperfect prior knowledge
The Tweedie denoiser discussed in Appendix is oracle denoiser, in the sense that perfect knowledge of all the parameters 14g. Σx of the Gaussian mixture distribution (I) is assumed. Therefore, though the comparison of the DAE (2) MSE with the oracle Tweedie MSE mse* does provide useful intuition (see Fig. 3). importantly does not allow to disentangle which part of the MSE of the DAE is due to the limited expressivity of the architecture, and which is due to the limited availablility of training samples- which entails imperfect knowledge of the parameters {uu, ) of the Gaussian mixture distribution P (T.. In this appendix, we derive the MSE of the Bayes optimal estimator (with respect the MSE), assuming only knowledge of the distribution from which the parameters {μ4, Σ K k= are drawn. For simplicity and conciseness, we limit ourselves to the binary isotropic and homoscedastic mixture (see e.g. Fig.[] for which μ = - U22 = u and Σ, Eg = old, For definiteness, we assume μu ~ P Pu., with P,, = No, 14/a), so that with high probability || 1. We shall moreover assume for ease of discussion that is perfectly known. Thus, the centroid μ is the only unknown parameter.
C.2 Bayes-optimal denoiser without knowledge of cluster means
The corresponding Bayes-optimal denoiser then reads
( IE [=] D)
/du du JuE(ela pt u, D]
(82)
((p,a)
Where we have identified the oracle denoiser 779 and emphasized the dependence μ.. Note that this is slight
abuse of notation, as the true oracle t(μ²², .)) involves the ground truth centroid. Further note that Pu o. D) = Pp since knowledge of does not bring information about μa. Furthermore, note that the noisy part of the dataset D {T") ===1 brings only redundant information, one further has that
P( = P(uDD)
(83)
30

---

where we noted D {x* 1p== the clean part of the dataset. Thus
b(æ) = P(D) / du t(p, (
P(D) I dpe Up, (p))
1
2 ||=" -al2
20z 1| 1
2 (2
pm1
P(D) / du t(M, x) (2m/2) ?
1
c 2e lull
2
||
/ u0=et 20
cosh
(2ma2)44/
o²
2 1 1
VdP(D) I du t(u//a,, x)) (27/2) e bllull
200 |!ll
cosh
14 ay
(2
o2
7 f du 1(M/Va,
(84)
where we noted
Po(u) = 2 ||
cosh
1 xx
(85)
02vd
with the effective variance
(86)
0² +
Finally, the partition function Z is defined as the normalisation of Po. i.e.
Z
di (p)))).
(87)
One is now in a position to compute the MSE associated with the Bayes estimator b()):
msep
= Em (E x
- -(((4/Va, (I(4/Va,VT
-x
Ax + VAE)) pmPP
-mse - ED Σ
Rggp)((O 02(1 A)+ +
b.I Sinn n*
T(a bVI Woo bv33
VV-a -V1-3. In
tanh
d1(1-))+
ED
1
Σ
A
2
11
tanh
VT m R²
+ //T=0
14 +0V uTe Vi
Vi
2
02(1 - A)
A
s=1l
VT=x 14 +VT=an ai
Div MI
+Va
X tanh
02(1-a)44
A
VT -/ (1- 11
msse Ep
Σ
Eg-:(0.1) 02(1 - +
(a-bvI-Aiu u²) tanh
o7 2)
+ Ep
Σ
(6R11-
A
M1 p22
tanh
/ 2 liv2 احده Su
(P(1-A)+A
+
d
s=11
V1 20 +
x tanh
(88)
21 2/14
M
31

---

We have adopted the shortcuts
b A02
MLL 11
Ω
(89)
2)
A2
A4
88 shows that the inner averages involved in the Bayes MSE msee, only depend the overlaps mI2nt1.d for 141 M2 two independently sampled vectors from P,. Motivated by similar high-dimensional studies, is reasonable to expect these quantities to concentrate as d way to derive this assumption is to introduce a Fourier representation, and carry out the ED average using the replica method. We refer the interested reader to, for instance, Appendix H of (36, where such route is taken.
in the measure Ep (-),),, A more principle but much more painstaking-
C.3 Derivation
To compute the summary statistics of Pb, we again resort the replica method compute the moment- noment-generating function (free entropy), see also Appendix A
The replicated partition function reads
Mu 1
Ma n Vd
EpZ* =
/ II
d 262 11
II Σ 2
E
((OLL)
Il cosh
(90)
σ²
a=1
Introducing the order parameters
14 14b
Ha 1
9ab
ma
(91)
d
d
one reaches
-d Sardao -d -E mna agh
E EeoH Mot
Ep 2"
II
dab
dmn,din,
Il O=
djua z llaal ensh
a=1
godll
71
Σ
(tAala==i: (ga))s
II cosh
877 + oda
(92)
o²
g
The computation of rr, M V is rather standard and follows the main steps presented Appendix A assumes the replica symmetric ansatz (21 22
One again
Gab (r 0ab 4.
Ma
(93)
f + -
Lab
Sab + 4,
ma v..
(94)
2
Introducing as in Appendix
A the variances
V 9:
V Ñ + á.
(95)
one reaches
Vg - VÂ
V,
mm,
(96)
2
V In (1+ 102) (I+16?)
1
+ 02 + m
(97)
2
+ V222
V EnpoA(c,,))11 In /
σA m G2
dAN(>; /on. V) cosh
(98)
Therefore the free entropy reads
Vq-Ve Vg
mmn 1 In (1+ (1+V02) Ø2 mi
1
+
extr M.
+ V022
{ dawnsss VTn. V) cosh
ao + m G2
+ OF (EEE~/(O.L) In
(
(99)
32

---

1.0
Bayes
orade
PCA orade
mse - mse.
0.0
-0.2
0.4
0.2
Bayes
DAE
PCA
0.6
0.2
V/
VA
Figure 12: (Binary isotropic mixture, Σ1, 0.09 P1,2 1/2, and 141 -- M2. also Fig. (right) MSE (minus
the rescaling baseline mse,) for the DAE (p = 1, = tanh) 2 (blue), the oracle Tweedie denoiser (76) (green), the Bayes denoiser (TOT) (red), and the plug-in oracle-PCA denoiser (T03) (black). Solid lines correspond the theoretical formulae 3.3 (81) and (TOTD; simulations correspond to a DAE optimized using the Pytorch implementation Adam (weight decay A 0.1, learning rate 1 0.05, full batch, 2000 epochs, sample complexity 1). averaged over N = 10 instances, with error bars representing one standard deviation. (right) Cosine similarity (6) for the same algorithms, with identical color code.
The solution of this extremization problem is given by the set of self-consistent equations, imposing that gradients with respect all parameters be zero:
1+V82
6²
V a ov
E
tannh [o@nntm o²
r]
(1+th)) aa
4
(1+V82y2
1+V82
(100)
m dt Bny-i10,11 tann (oveytt
172
1+V82
This is simple optimization problem over 6 variables, which be solved numerically. One finally the obtained summary statistics to evaluate the Bayes optimal MSE:
A
msee
msse 2EpE:-NN0.1)
A) A (a-bvi-A)m) tanh
V/-amtt/1--Do/AA/AAY 220-0)+4
02
+ EDD
(
g tanh <1-Am+ 111-)1------ 201 2112
tanh V1-Am+ -
(101)
2012
where
q V Ω
q q+V
(102)
q
This completes the derivation the MSE of the Bayes estimator agnostic the cluster means.
C.4 simple plug-in denoiser
Another simple denoiser assuming only perfect knowledge of the variance a, but imperfect knowledge of is simply to plug the PCA estimate ÚACA of ft into the Tweedie oracle (76). i.c.
vI 2
A
a ('TAAAAVI (2(1-A)+A )
t(APCA, (1
tanh
x
ÍÚPCA
(103)
a² A) +
The performance of this plug-in in denoiser is plotted Fig. 12 and contrasted to the one the Bayes denoiser 6(-) IOT the oracle t(-) (8T) and the DAE 3.3 Strikingly, the performance of the PCA plug-in denoiser is sizeably identical to the one of the Bayes-optimal denoiser, both in terms of MSE and cosine similarity. is important to remind at this point that both the plug-in (103) and the Bayes denoiser (OOT still rely on perfect knowledge of the cluster variance and the noise level A, while the DAE 22 is agnostic to these parameters. Yet, these two denoisers make for a fairer comparison than the oracle (8I), they importantly take into account the finite training The DAE relatively close to the Bayes baseline for small noise levels A, while gap can be seen to open up for larger A.
33

---

3.0
3.0
2.5
2.5
1.5
1.0
0.5
0.0
0.0
0.6
V
V/
Figure 13: Cosine similarity 0 (6) (green), weight norm [| and skip connection strength for the MNIST dataset (left), of which for simplicity only 1s and 7s were kept, and FashionMNIST (right), of which only boots and shoes were kept. In solid lines, the theoretical predictions resulting from using Conjecture 3.3 in its generic formulation (58) with the empirically estimated covariances and means. Dots represent numerical simulations of a DAE (p 1, tanh) trained with n 784 training points, using the Pytorch implementation of full-batch Adam, with learning rate 77 0.05 over 2000 epochs, weight decay À = 0.1, averaged over N = 5 instances. Error bars represent one standard deviation. See Appendix D for full details on the preprocessing.
D Details on real data simulations
In this Appendix, we provide further details on the real data experiments presented in Fig. and Fig.
Preprocessing The original MNIST 15 and FashionMNIST 16 data-sets were flattened (vectorized), centered, and rescaled by 400 (MNIST) and 600 (FashionMNIST), For simplicity and case of discussion, for each data set, only two labels were kept, namely 1s and 7s for MNIST and boots and shoes for FashionMNIST.. Note that the visual similarity between the two selected classes should make the denoising problem more challenging.
Means and covariance estimation For each data-set, data from the same class were considered to belong to the same Gaussian mixture cluster. For simplicity, we kept the 1/2) for definiteness, For each cluster, the corresponding mean and covariance numerically evaluated from the empirical mean and covariance over the 6000 boots (shoes) in the FashionMNIST training set, and the 6265 is (7s) in the MNIST training set. The solid lines in Fig. correspdd to using those estimates in the asymptotic formulae of Conjecture 3.3 in their generie form 588 (see Appendix A for sample complexity and l regularization X 0.1.
number of training points in each cluster,
to
obtain balanced clusters (p1 =
The red points in Fig. were obtained from numerical simulations, by optimizing a = DAE with tanh activation using the Pytorch implementation of the full-batch Adam 43] optimizer, with weight decay À- = 0.1, learning rate y 0.05, over T 2000 epochs. For each value A, n 784 images were drawn without replacement from the data-set training set, corrupted by noise, and fed the DAE along with the clean image for training. The denoising test MSE, cosine similarity and summary statistics of the trained DAE were estimated after optimization using Tleest 1000 images randomly drawn from the test set (from which also only the relevant classes were kept, and equally represented- i.e. balanced). Each value was averaged over N = 10 instances of the train set, noise realization and test set. The obtained values furthermore found to be robust with respect to the choice of the optimizer, learning rate and number of epochs.
Pytorch simulations
D.1
Complementary simulations
Fig in the main text addresses the comparison of the theoretical prediction Conjecture 3.3 with simulations on the real data-set, at the level of the denoising test MSE (5). For completeness, we show here the same comparison for the other learning metrics and summary statistics, namely the cosine similarity (6), weights norm || and trained skip
connection strength b. Theoretical asymptotic characterization are again provided by Conjecture 3.3 (TO)
and (T)
34

---

They plotted as solid lines in Fig. and contrasted to numerical simulations (dots) the real data-sets, by training a p DAE (2) using the Pytorch implementation of the Adam optimizer. All experiment details are the same as Fig. of the main text, and can be found in the previous subsection. As can be observed, there is gap, for large noise levels A, between the theory and simulations the weights norm || ja (red). On the other hand, the matchings for the
cosine similarity 0 (green) and skip connection strength b (blue) are perfect. Overall, Conjecture (3.3) therefore captures well (with the exception of xhil /22 at large A) the main metries of the denoising problem on these two real data-sets. more thorough investigation of the possible Gaussian universality of the problem is left to future work.
E Derivation of Corollary 3.4
In this Appendix, we provide the derivation of Corollary 3.4
Rescaling component h We first provide a succinet derivation of the sharp asymptotic characterizations for the rescaling component h 3 Because this is only a scalar optimization problem over the single scalar parameter c of he. the derivation is simple and straightforward. The empirical loss reads
1 R(c) nd
Σ
xt c (Vi
Ar + v AE"))
||
nd
12
112
1
|
1
x
(x²)
T
(1 Ac)²
+ c
11
71
n1
" 1
|
(1 v1 Ac)²
+ +C8+0
1x !|
(1-v1 v1
2E
+c²
= v1 Σe)²
Pk (11m41 12+ TT Ex) +0A
(104)
Extremizing this last expression with respect to e leads to
K Ex
1/ {
Σ Pk
Tr
Ex
VT-A
Σ Pke duy (7)71)
VT-A
è
(105)
K
Σ Pk
Ir Ei
(1-
+
á
S
(1
(1-
which is exactly (00, stated in Corollary
3.4
The associated MSE can be then readily computed
mse EDE
x
à
(VI
Ax" + VV
K
= (1 v1 Ad)2
Pk (1 Tr Ex) + 82A
d
K
( (fde-tti2 +d d denliina)) + +EA
(1 V1 - Ac)² Σ ph
k=1
MSC
(106)
This completes the proof of the asymptotic characterization of the rescaling component
Bottleneck network component For å one needs to go through the derivation presented in Appendix[Ajby setting
b = 0 from the beginning. It is straightforward realize that the derivation goes through sensibly unaltered, and the only differing step is that the quadratic potential V Qquad. now constant. One therefore only needs set in all the formulae of Conjecture 3.3 to access sharp asymptotics for a. This concludes the derivation of Corollary 3.4
35

---

F Derivation of Corollary 3.5
We now turn to the derivation of Corollary 3.5 This corresponds to the limit A = O, where the input of the auto-encoder also the clean data point. In terms of equations, essentially, this means that all the integrals over &, Ag in the derivation of Conjecture 33.3as as presented in Appendix [ shouud be removed. For the sake of clarity, and because this is an important case of particular interest, we provide here complete, succinct but self-contained, derivation in the case RAEs, For technical reasons, we limit ourselves to &g regularization. Furthermore, note that the model of an RAE with a skip connection trivial, since such an architecture can achieve perfect reconstruction accuracy simply by setting the skip connection strength to and the weights to O. Therefore, we consider an RAE without skip connection
W
W
(
(107)
vd
Derivation
The derivation of asymptotic characterizations for the metrics mse (5). 0 (6) and summary statistics for the RAE 1077 follow the same lines as for the full DAE (2) as presented in Appendix As Appendix [A] the replicated partition function
the first step is to evaluate
Ep /II
dw
-B Σ )(w") ami
II
n
Bn
Σ am1
put
vi
Walug
(108)
The exponent (*) can be expanded as
we (ue 62
-20
we (we)
wa "allig +m)) +1mm)) +111 12p1
vid
vit
v/l
(109)
Therefore,
(x)() = Σ
K
PWC 4: 11 I
dn
in (x, tama)) - Swae T
(2:) & /dtt Σか
Pem.(m)
wowe (mal
02
20 mall
w., (at vd
(110)
The effective prior over the 77 is therefore Gaussian with dressed mean and covariance
Par. (n) N (m: C),
(111)
where
c-1= + Bslld,
1 -BsC
(112)
Observe that this mean is Oss) and can be safely neglected. Then
K
12 c-
(+)
=
/ddet Ei det(C)
k=1
T
Wi w
ue (Je +n)
vi
20
una (a(()))))
ua "maliy
(113)
Patt (n))
Again, like Appendix A
we introduce the local fields:
x w. (n - 11)
W. 1k
h
(114)
Vd
Vd

---

which have correlation
W2 Eg d
(115)
We used the leading order of the covariance C. One therefore has to introduce the order parameters:
Qub Wa W
ReXP,
S
W. SnWp
m
Wafk
E R..
(116)
vd
The distribution of the local fields X is then simply:
(A ~N (0,
(117)
Going back the computation, (a) can be rewritten
no Rea (0aa)(((+))))))------))))))))))) (2 (mb+a2)) (m (maaa))
(118)
Introducing Dirac functions enforcing the definitions of Qab, ma brings the replicated function the following form:
EZ
II db Il
dQuidQaa
II
dm
dma IIII
dSc ag
abe"
0.b
1= o=
1=1
d QubQas-d
-d
2 Sh.
L
e usc
1m a
g[w(w") Qasw, wa
St we E,w,
3 E Vn Vdw.,
K
dw.e
6m1
aBsdo
K
ad
e 2
!|
Σ
Pk
(a)
(119)
ddnt Ea dot(c-1)
gasd2 quund. 1
As in Appendix A we have introduced the trace, entropic and energetic potentials , Vw, Vy Since all the integrands scale exponentially (or faster) with d, this integral can be computed using a saddle-point method. To proceed further, note that the energetic term encompasses two types of terms, scaling like sal and sd. More precisely.
K
ad
K
ad
PR
1
(a)
1 sd
Pk In (ider En det dc)(c))))) + k=1
1
Σ Pk In(a)
ddte En dot((c (c-1))
sd
k=
sad?
In (a 1)5) tand
m In(a)
(120)
Remark that in contrast to Appendix A the quadratic term is constant with respect to the network parameters, and therefore one no longer needs to discuss extremization. Following Appendix A assume the RS ansatz
Va,
m = m,
t = vi
( Fx
Ya, b.
5k = (rk Sat + gk-
Sh. =
+
9k
dab + ÿk.
2
( 8
Ya, b.
Qan = - 0ab + Qah =
+ dab + g.
(121)
2
In the following, we sequentially simplify the potentials w.,, My, W, under this ansatz.
37

---

Entropic potential
It convenient introduce before proceeding the variance order parameters
f +
V% = fk + tk.
(122)
The entropic potential can then be expressed as
Bsdy m
=" Σ Tr Tr(Wia
++ 2 w]
E vanin ui De
d
a.6
1 Tr VV
2 Imm
x
K
D
DE
k=1
/
-Ba((0) 1 Tr Vww T+ Σ FewEew }
Vinan T + B. oo
dwe
K DE
DE
k=1
| duv
-Bg(w) -w Vell+ Σ V. ow ( Vamu
E. 0. sf ow
(123)
Therefore
3V
2 ʃ DEIn In I Jdwe Sg(w) tw Voa.t E
Prszy owo
K - 0
Sw
(124)
Energetic potential (a):
The inverse of S₁ can be computed like in Appendix A leading to the following expression for
πI dx
2 (22) (FL - (AS) Ae A Σ (+)
(a) =
JuP (2m²)
me// /dtt Sk
Dn
Ve din - t An 20 (x)
Rr
m// / SI (2x))
Rp
/ Dn [ N (Anigin. e- {(N))
Dyjin [ (2ni n, v) E (-))
(125)
where noted with capital D integral over, over.N(()) (0 Tp). Therefore
[ (2x: n. 2(.)
BV,
Σ Pk:
Dn
(126)
jgy
38

---

Zero-temperature limit
In this subsection, take the zero temperature 3 - limit. Rescaling
8 Vi Va.
BV4 t Vk.
f t qc-
Brik
mp
(127)
one has that
K
-1
K
K
82
Tr
V V +
Σ
Vi & Σ
② La +
Uk
2
Σか +
Σ
2d
B=M,
d
(128)
where we introduced the Moreau envelope
inf (=)
(Velot m hoz. You (vole EN hox.)
)/+
(1
g(2r)
(129)
For the case of l regularization, the Moreau envelope presents a simple expression, and the entropy potential assumes the simple form
( Allm (LloLL AOLo
K
K 1 + Σ
K
002
v = 2d
Tr
Σ
V 2
c
4 &
ΣS +
Σ
m&H
T
(130)
The energetic potential also simplifies in this limit to
K
V
Pk E,,,MM
(131)
where
1 inf
82
Mz
Tr
V
y
q 17
mk
+ Tr (T)g
-20 y V8.
(132)
2 a.y
Trace potential
is immediate to see that the trace potential can be expressed as
Vg qV
K Ve)) Σ
V =
Σ
[T
(r
Paok
Triās
mgmik
(133)
km
Then the total free entropy for RAFs 107 reads
Åq QV
1 K
extr
+
Σ
Tr
Vine
-Tr(hu Vxl)
mggn
9.m, Vig.mi, V. ma, Vv. 4u. Me, Vo 1K
2
k=1
Ma (1) 1 de((,,)
Tr (At
K
Tagk +
T
(134)
ISkjSK
Comparing to the free energy derived in Appendix A it is immediate just corresponds to removing the second term from the DAE MA, and setting = 0. The disappearance of the second
that the Moreau envelope Mg for the RAE term in the Moreau envelope has the effect to kill the V-dependence, resulting to V. These observations. in addition to the already taken limits A, b = 0, finish the derivation of Corollary 3.5
when extremizing with respect
39

---

0.6
1.5
theory
0.5
simulations
1.4
1.3
MSSNNA meee
0.3
1.2
0.2
11
1.0
0.1
0.9
0.0
0.7
-0.2
0.0
0 2.5
1/22, 1/2,,1,222211 0.3 x Ia. 1,0 = tanh; the cluster mean μ4 - U2 was taken random Gaussian vector of norm 1. (left) In blue. difference in test reconstruction MSE between the RAE (Corollary and the leading order term isse, (35 Solid lines correspond to the sharp asymptotic characterization of Corollary
Figure 14: a = = P1,
3.5
3.5
Dots represent numerical simulations for d = 700, training the RAE using the Pytorch implementation of
full-batch Adam, with learning rate 0.05 over 2000 epochs, weight decay À 0.1, averaged over N 10 instances.
Error bars represent one standard deviation. (right) Cosine similarity 0 (6) (green), squared weight norm || (red).
Solid lines correspond the theoretical characterization of Corollary 3.5 dots are numerical simulations. The cosine similarity with the cluster means of the principal component of the training samples is represented in blue crosses, and superimposes perfectly with the analogous curve learnt by the RAE.
F.2
Reconstruction MSE
Having obtained a sharp asymptotic characterization of the summary statistics for the RAE, we now turn to the learning metrics. It easy to see that the formula for the cosine similarity (6) carries over unchanged from the DAE case, Appendix A
We therefore focus on the test MSE:
10
20 + m7)
iSSRRAE Ek...
p4 + 17
Vd"
Vd
Σ Pk (11 2 Tr Ex)
(V..1)
Tr [Tr go (m² + /u==)
Emsee'
K
2
(. Ph. 0.0
[o (mi + /quu)] T (mz + vuuu)
(135)
F.3 RAES are limited by the PCA MSE
We close this Appendix by showing how the RAE Corollary 3.5 recovers the well-known Eckart- Eckart-Young Young theorem The difference mse mse for an RAE learning to reconstruct a binary, isotropic homoscedastic mixture (see Fig is
10
shown in Fig. 14 from a training set with sample complexity a Because msse msse, is essentially correction to the leading term isse., estimating this difference is slightly more challenging numerically, whence rather large error bars. Nevertheless, can be observed that the agreement between the theory (solid blue line) and the simulations (dots) gathered from training an similarity and learnt weight norm. the agreement perfect, see (.3) For comparison, the performance of PCA reconstruction (crosses) has been overlayed on the RAE curves. Importantly, observe that in terms of MSE, PCA reconstruction always leads to smaller MSE, in agreement with the well-known Eekart- Young theorem 100. From the cosine similarity, it can be seen that the RAE essentially learns the principal component of the train set, see the discussions in e.g. [12
RAE using the Pytorch ch implementation of Adam is still very good. In terms of cosine
We finally stress that, in contrast to all previous figures, the x axis in Fig 3.5 is the sample complexity a, rather than the noise level A. As matter of fact, while our result recover the well-known fact that the MSE of RAEs is limited (lower-bounded) by the PCA test error, Corollary 3.5 allows us to investigate how the RAE approaches the PCA
40

---

performance a function of the number of training samples, characterization which has importantly been missing from previous studies for non-linear RAEs g 9
41


Reviews:
[{"review_id": "7CF9Qnm0xZ", "reviewer": "Reviewer_zMEV", "summary": "The authors set out to characterize the non-linear behavior of denoising auto-encoders (DAEs), for Gaussian mixtures, in the high dimensional limit with the number of hidden units being fixed. The authors particularly tease out the role of the skip-connection, compared to the reconstruction auto-encoder (RAE) which is known to essentially perform principal component analysis (PCA).\n\nUsing the replica method, the authors obtain closed-form expressions for the mean-squared error (MSE), as well as the cosine-similarity (w.r.t cluster means). The obtained formulae are supported by experiments on both synthetic and real data sets, clearly highlighting the role of the sample complexity and the noise level.", "questions": "**Technical comments:**\n- L178: could you briefly explain the asymptotic dependence on $\\alpha$?\n- L212: could you elaborate on the choice of closely related classes?\n- I wonder how the method fairs with a mixture of more than 2 classes.\n  - Is it true that $K=2$ also for the MNIST experiments?\n\n**Presentation comments:**\n- L158: perhaps it helps to discuss this rationale before stating the assumptions.\n- Understandably, it is an essential part of the contribution to provide those closed-form expressions, but I wonder which subset of the readers would benefit from having Eqs.13 and 14 in the main paper.", "limitations": "Dedicating more space to help make the theoretical concepts and techniques employed more accessible, i.e., to a broader set of readers, would have been greatly appreciated.\n\nIt is a limitation of this reviewer that I'm unable to assess the full scale of the theoretical derivations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- Presents an effective characterization of (non-linear) DAE behavior on Gaussian mixtures, clearly explaining the role of the reconstruction and scaling components supported by compelling empirical evidence (also on real data).\n- Draws a number of important conclusions, pointing to fruitful directions of future work, e.g., L200, L218, L278.", "weaknesses": "One would wish the long sequence of mathematical expressions could be made less opaque.\n  - This is remedied by a seemingly complete and well-composed supplementary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work. We address below their questions:\n\n>One would wish the long sequence of mathematical expressions could be made less opaque.\n\nWe will add further discussion beneath (13) and (14) in the revised manuscript, and provide qualitative insights into their meaning and implications.\n\n>L178: could you briefly explain the asymptotic dependence on $\\alpha$\n\nThe characterization of Corollary 3.5 involves the sample complexity $\\alpha=n/d$, whereas previous studies typically assumed an infinite amount of available training data ($\\alpha\\to \\infty$). Our work therefore allows to characterize the learning metrics when learning from finite data sets. It can further be shown from Corollary $3.5$ that the mse of RAEs asymptotically converges to its infinite data limit $\\alpha \\to\\infty$ as $ O(\\frac{1}{\\alpha})$. We will add this computation and the relevant discussion in the supplementary material of the revised manuscript.\n\n>L212: could you elaborate on the choice of closely related classes?\n\nAs discussed in section (l.278-290), in order to have a good denoising performance, the DAE has to learn the data structure, given by the cluster mean $\\mu$. A priori, one expects the learning problem to be more challenging -and therefore more interesting- when the clusters are close and less distinguishable, i.e. when $\\mu$ is small. Our choice of closely related classes for the real data experiments stems from that qualitative intuition. We will include further discussion in the revised version of the manuscript.\n\n>I wonder how the method fairs with a mixture of more than 2 classes. Is it true that also for the MNIST experiments?\n\nWe indeed took for simplicity $K=2$ also in MNIST experiments, by retaining $2$ out of the $10$ classes, assuming that each class can be modelled by a Gaussian cluster. \n\nWhile we state the asymptotic formulae for any $K$ of order $1$, as the phenomenology of the results we obtain is already rich and novel for $K=2$, we left the exploration of the more general case for future work.\n\n>L158: perhaps it helps to discuss this rationale before stating the assumptions.\n\nWe agree that mentionning that assumptions 3.1 and 3.2 can be relaxed before stating them would improve the readability. We will take this into account in the revised manuscript.\n\n>Understandably, it is an essential part of the contribution to provide those closed-form expressions, but I wonder which subset of the readers would benefit from having Eqs.13 and 14 in the main paper.\n\n(13-14) have been included in the main paper so that the result statement is self-contained, thereby avoiding the need of referencing equations placed elsewhere in the manuscript. We believe that the inclusion of further discussion thereof, as suggested in the reviewer's previous remark, will provide further insight into these equations and justify their position in the main text.\n\n>Dedicating more space to help make the theoretical concepts and techniques employed more accessible, i.e., to a broader set of readers, would have been greatly appreciated.\n\nWe will devote further discussion to an explanation of the replica method, which we employ to derive the main result, so as to improve the readability for a broader audience.\n\n"}, {"review_id": "OrhU2gWWVm", "reviewer": "Reviewer_DrHV", "summary": "This paper presents theoretical results of the test error of 2-layer denoising auto-encoder. In a high-dimensional limit regime where data distribution follows from Mixture of Gaussian, closed-form expressions of the error are obtained. The results are further analyzed and supported by numerical experiments on real data sets.", "questions": "- (line 33) Usually we say the sample complexity is related to n, it is here a bit strange to say it is alpha \n- (line 89) What does this mean sigma(.) stays order 1 ? \n- (eq 13) is there a unique solution in this system of 10 equations of 10 variables ?\n- (line 219) regarding the Gaussian universality, do you need to perform any normalization on the data for this to hold ? The dimension of MNIST seems quite small, what is it in your mind for the universality to hold ? \n- (line 255) to clarify a previous point regarding PCA, does mse_f grows linearly with d ?  Do you have an idea of what is the relative error of MSE of DAE and PCA ?", "limitations": "- The main result is very specific, but this is quite normal in the literature .", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The main result (result 3.3) is highly non-trivial and provides a tight formula for the test error of the 2-layer denoising auto-encoder (DAE). \n- It shows that DAE can perform much better than PCA in terms of MSE error. \n- The role and importance of the skip connection is also highlighted in both theory and in practice, as well as the non-linearity in DAE.", "weaknesses": "- The optimal MSE error mse_o grows with the data dimension d (eq. 9), however the gap between mse_f and mse_o (eq 8) remains a constant, this suggests that the difference between DAE and PCA is not so significant in terms of the relative error of MSE, i.e. | mse_f - mse_o | / mse_o vs. | mse_PCA - mse_o | / mse_o. Thus it is still not very clear whether DAE brings something essentially different to PCA or not (I agree that at least they are different). \n- In the main result 3.3, it is not clear how the regularization term g is used, i.e. under Assumption 3.2, the parameter lambda does not appear in eq. (8), this is a bit strange to me .", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful questions, which we answer below:\n\n>The optimal MSE error $mse_o$ grows with the data dimension d (eq. 9), however the gap between $mse_f$ and $mse_o$ (eq 8) remains a constant, this suggests that the difference between DAE and PCA is not so significant in terms of the relative error of MSE, i.e. $| mse_f - mse_o | / mse_o$ vs. $| mse_PCA - mse_o | / mse_o$. Thus it is still not very clear whether DAE brings something essentially different to PCA or not (I agree that at least they are different).[...]to clarify a previous point regarding PCA, does $mse_f$ grows linearly with d ? Do you have an idea of what is the relative error of MSE of DAE and PCA ?\n\nThe difference between the mse achieved by the DAE $mse_{f}$ and the mse achieved by PCA is in fact significant and of order $\\Theta(d)$. As we explain in l.255, $| mse_{PCA} - mse_\\circ|=\\Theta(d)$ and  $| mse_{PCA} - mse_f|=\\Theta(d)$ , so both  relative errors $| mse_{PCA} - mse_\\circ|/mse_\\circ$.  and  $| mse_{PCA} - mse_f|/mse_f$ are $\\Theta(1)$. Therefore, both the DAE $\\hat{f}$ and the rescaling $\\hat{r}$ are considerably better than PCA. On the other hand, $|mse_{f} - mse_\\circ|=\\Theta(1)$, which hence implies $| mse_{f} - mse_\\circ|/ mse_\\circ=\\Theta(1/d)$. Note that this also means the improvement of the full DAE $\\hat{f}$ upon the rescaling MSE $mse_\\circ$ is subleading. It is in a sense a limitation of our theoretical model that the interesting phenomenology appears in the subleading order. At the same time, our real-data experiments show that the effects we predict from the theory are visible in real data, and correspond to visually significant changes (see images in Fig. 2 (left) and Fig. 4).\n\n>In the main result 3.3, it is not clear how the regularization term g is used, i.e. under Assumption 3.2, the parameter lambda does not appear in eq. (8), this is a bit strange to me .\n\nEquation (8) involves the summary statistics $m,q,V, m_k,q_k, V_k$, which in turn depend on $\\lambda$ through (13). We agree that a comment on this implicit dependence will improve the readability of the manuscript, and shall include one in the final version.\n\n>(line 33) Usually we say the sample complexity is related to n, it is here a bit strange to say it is alpha\n\nThe denomination of sample complexity for $\\alpha$ (which is equal to the number of samples $n$ normalized by the input dimension $d$) has been consistently used in the exact high-dimensional asymptotics literature. We will comment on it to avoid possible confusion for readers used to a different terminology. Since the two parameters are straightforwardly related by a factor $\\frac{1}{d}$, they essentially describe the same quantity, with $\\alpha$ presenting the advantage of being $ \\Theta(1)$ in the asymptotic limit considered. For the sake of clarity, we choose to keep this denomination, but will include an additional comment in l.130 when $\\alpha$ is introduced.\n\n>(line 89) What does this mean sigma(.) stays order 1 ?\n\nWhat we mean is that the argument of the function $\\sigma$ in (2), namely $\\frac{w\\tilde{x}}{\\sqrt{d}}$, is of order $1$ as $d\\to\\infty$. We will clarify the phrasing in the revised manuscript.\n\n>(eq 13) is there a unique solution in this system of 10 equations of 10 variables ?\n\nWhile at this point we do not have a proof of (13) having a single solution, in all the studied cases, only a single solution was found, up to symmetry. (Note that indeed if $\\sigma$ is odd, the function $f$ is invariant under $w\\to -w$. Therefore, for each fixed point of (13), the solution obtained by flipping the sign of $m$ is also a solution, but leads to the same learning metrics $\\theta$ and mse.) Further, this solution agrees with numerical experiments.\n\n>(line 219) regarding the Gaussian universality, do you need to perform any normalization on the data for this to hold ? The dimension of MNIST seems quite small, what is it in your mind for the universality to hold ?\n\nIn Fig.2, the datasets are indeed flattened, centered, as described in Appendix D. Since the components of the resulting vectors are comprised between $0$ and $255$ (as they correspond to color levels), we further divide them by $400$ so as to have components of order $1$. The precise value of this normalization was not found to impact the agreement between the theory and simulations. Note that the quantitative characterization of the generic conditions under which Gaussian universality holds for real datasets is still very much ongoing work in machine learning theory, even for supervised learning settings. Informally, in the present work, the intuition lies in the fact that the width of the hidden layer is finite, and thus much smaller than the input dimension, leading to some form of central limit theorem to hold. Finally, note that Gaussian universality has also been observed in dimension $784$ in supervised regression settings, see e.g. [47]."}, {"review_id": "72knn86zkB", "reviewer": "Reviewer_ZGsS", "summary": "The authors consider a two layer weight-tied denoising autoencoder with a skip connection in the regime of vanishing rate and samples proportional to the dimension. They heuristically derive an exact characterization of the optimal network parameters and the corresponding network performance in the the high-dimensional limit using the replica method. Their experiments show that their results match on synthetic data and are very close to the performance on more practical data.", "questions": "- Why do the limits in Line 152 exist? \n- In Figure 3 for high noise and low sample complexity the performance of the full DAE is worse than simply rescaling. Since the full network can also act as a rescaling network by setting $w=0$, this implies that during training the global optimum is not found. Can you elaborate on this?", "limitations": "- It should be stated more clearly that the way the replica method is carried out only serves as a strong heuristic and not a rigorous proof.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- Exact characterization of all quantities of interest in the high-dimensional limit. \n- Strong experimental validation of theoretical claims", "weaknesses": "- From a theoretical perspective there is a lack of rigor to this method\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments. We answer below their questions:\n\n>It should be stated more clearly that the way the replica method is carried out only serves as a strong heuristic and not a rigorous proof.\n\nThe reviewer is entirely correct about the heuristic nature of the result, and we will further emphasize this fact after the statement of result 3.1 in the final version of the manuscript.\n\n>Why do the limits in Line 152 exist?\n\nThis is used as an assumption in the replica computation, which has been verified in related settings in previous works, see e.g. [47]. We will state the main assumptions of the method, i.e. concentration of overlaps and the uniqueness of the replica limit, explicitly. \n\n>In Figure 3 for high noise and low sample complexity the performance of the full DAE is worse than simply rescaling. Since the full network can also act as a rescaling network by setting $w=0$\n, this implies that during training the global optimum is not found. Can you elaborate on this?\n\n Thank you for the question. While the full DAE can indeed act as a simple rescaling, it has access to a limited amount $n$ of training samples, and at the global optimum of the *empirical* loss, $w\\ne 0$. For large noise levels $\\Delta$, the DAE overfits the training data, leading to a performance worse than simple rescaling as the reviewer correctly observes in Fig. 1 and 3. Note that as the sample complexity $\\alpha$ increases, this overfitting disappears, as the empirical loss becomes closer to the population loss (see Fig. 3 (a)). The fact that our study captures this overfitting phenomenon is a strength of our analysis, which allows to cover the effect of a finite amount of training data. Finally, note that the overfitting can be mitigated by adjusting the strength $\\lambda$ of the regularization. In Fig. 1 of the attached pdf, we reproduce the same curve as Fig.1, for various $\\lambda$. Observe that the overfitting disappears for larger regularization --e.g.$\\lambda=0.8$ (instead of $\\lambda=0.1$ in Fig.1)--, at the expense of worsened performance for small noise levels $\\Delta$. We shall include this figure and additional discussion in the revised version of the manuscript."}, {"review_id": "Bko7K1GyYS", "reviewer": "Reviewer_pba7", "summary": "This paper studies the performance of denoising autoencoders (DAEs) in high-dimensional settings. The DAEs are trained on data sampled from a Gaussian mixture with $K$ components perturbed by isotropic Gaussian noise. The DAEs are one-layer networks with arbitrary activation functions, tied weights, and a skip connection. They are trained with an $L_2$-regularized loss function, and the high-dimensional limit is considered, where the ratio of the number of training points to the input dimension converges to a constant α.\n\nThe main results of the paper are formulas for the denoising test mean squared error (MSE) for the full DAE, as well as two simpler architectures: a \"bottleneck network\" in which the skip connection is removed, and a \"scalar linear network\" that simply rescales the input by a scalar. The final formulas involve complicated integrals and optimization problems, but they only depend on low-dimensional quantities, such as the number of neurons in the hidden layer and the number of components in the Gaussian mixture.\n\nThe authors use the derived asymptotic test error to analyze the role and importance of each component in the performance of DAEs. They find that the skip connection is essential for good performance and that DAEs can outperform other denoising methods, such as principal component analysis (PCA). \n\nTaking the noiseless limit, where the variance of the noise converges to zero, they can also derive the test error of reconstruction autoencoders, which are trained with noiseless inputs. ", "questions": "- It appears that all the experiments were conducted with a number of neurons $p = 1$. Could you please clarify if the empirical results align with the replica predictions when $p > 1$? Additionally, does the \"universality phenomenon\" manifest itself also in this case?\n\n- Based on Figure 3, it appears that the performance of the DAE approaches that of the oracle denoiser. Can this convergence be rigorously derived from equation (13)?\n\n- What happens when $K = 1$? Do the DAE, PCA, and bottleneck network exhibit similar performance in this scenario?", "limitations": "This theoretical paper does not possess any immediate potential negative societal impacts.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors managed to derive fairly complicated asymptotic formulas via the replica method from statistical physics. The empirical experiments seem to confirm the accuracy of their predictions. This provides yet another example of the successful application of the replica method and its surprisingly powerful nature.\nThis paper fills a gap in the literature and complements previous results that mainly focused on RAEs and the infinite data regime (optimization of the population loss).\n\nThe exact formulas derived in this paper are utilized to derive interesting non-trivial results, which can serve as stimuli for future research. Specifically:\n\na) The MSE obtained by training a DAE with gradient descent matches the asymptotic predictions, suggesting that while non-convex, the optimization problem has a favorable landscape.\n\nb) The exact formulas obtained for the Gaussian mixture predictions align with those obtained for a DAE trained on MNIST datasets, indicating the presence of universality phenomena.\n\nc) As α increases, the denoising MSE of the DAE approaches the asymptotic performance of the oracle denoiser (derived in the appendix).", "weaknesses": "The paper exhibits weaknesses similar to other papers in this field. The exact analytical formulas derived are somewhat obscure, and it seems that several of the observations made in the paper can be deduced directly from the results of the empirical experiments, without relying on the analytical formulas (e.g. the improved performance of the network with skip connections compared to the one without can be easily inferred). The authors should emphasize the results that their analytical formulas allow to obtain.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments. We answer their questions below:\n\n>The authors should emphasize the results that their analytical formulas allow to obtain.\n\nWe believe a strength of our analysis lies in the fact that it allows to characterize learning metrics at the global optima of the empirical risk, whereas there is a priori no guarantee that a purely experimental study can consistently reach them. Furthermore, our analytical formulae allow to probe the asymptotic behaviour of the learning problem, while a purely empirical approach would require to disentangle the finite size effects from the true asymptotic behaviour. Finally, the expressions further make it possible to establish the rates of convergence with the sample complexity of the learning metrics to their infinite data (population) $\\alpha\\to \\infty$ limit. We shall include this analysis in the final version of the manuscript. For enhanced clarity, we will also add this discussion on the insights afforded by our analytical formulae.\n\n>It appears that all the experiments were conducted with a number of neurons $p=1$ \n. Could you please clarify if the empirical results align with the replica predictions when \n$p>1$. Additionally, does the \"universality phenomenon\" manifest itself also in this case?\n\nWhile we state the asymptotic characterization in full generality, we indeed restrict the discussion of results to $p=1$ hidden units. This already presents a number of interesting and novel properties that we describe. Solving the equations for $p\\ge 2$ requires more analytical work, along the lines of e.g in [29]. We further anticipate that a richer phenomenology, such as a specialization transition like [29], will arise for $p\\ge2$, and a thorough exploration thereof warrants a full separate line of work that we are undertaking currently, and falls out of the scope of this first work where we introduce the model, framework and present the interesting observations for $p=1$.\n\n>Based on Figure 3, it appears that the performance of the DAE approaches that of the oracle denoiser. Can this convergence be rigorously derived from equation (13)?\n\nThank you for this question. While the oracle denoiser (B4) admits the functional form of a DAE, the corresponding encoder and decoder weights are proportional, but not strictly equal, and therefore cannot be realized exactly by the weight-tied DAE -- although the difference of performance is quantitatively small, see Fig. 3. In the final version of the manuscript, we shall provide a characterization of the $\\alpha\\to\\infty$ limit of the DAE performance, and characterize precisely the difference with the oracle performance.\n\n>What happens when $K=1$? Do the DAE, PCA, and bottleneck network exhibit similar performance in this scenario?\n\nThe $K=1$ corresponds to setting $||\\mu|| =0$ in our analytical characterization (Result 3.3). We shall include a discussion of this special case in the supplementary material of the final manuscript. In short, the oracle denoiser (B4) reduces for $K=1$ to a simple rescaling, so only the rescaling component of the DAE is actually needed. Indeed, as discussed in section 4, l.278-290, the role of the bottleneck component is to learn the data structure (as given by $\\mu$), which it leverages to improve the denoising performance. In the unstructured $K=1$ ($\\mu=0$) case, this component is not needed, and its presence actually causes the DAE to overfit the data, leading it to perform worse than the rescaling. Similarly, PCA denoising performs worse on unstructured data and leads to a mse worse by $\\Theta(d)$, like in the $K>1$ case. In Fig. 2 of the attached pdf, we reproduce Fig.1 (left) and Fig. 3 (b) for $K=1$, comparing the oracle, rescaling, DAE, bottleneck and PCA denoisers. This figure will be included in the supplementary material of the final manuscript.\n\n"}]

Author rebuttal:
We attach here a .pdf, containing additional figures which we refer to in the separate rebuttals.

Meta-review: Auto-encoders are often used in applications. Thus it is important to understand their theoretical properties. The authors managed to derive an asymptotic formula for the test error of 2-layer denoising auto-encoder with skip connections. The results are supported by numerical experiments.

In particular, they demonstrated that DAE can perform much better than PCA in terms of MSE. The MSE of DAE coincides with the asymptotic predictions, thus the optimisation problem demonstrates some good behaviour. The authors also identified situations when MSE for the denoising AE is close to the asymptotic performance of the oracle denoiser.

Overall, the results are interesting and describe some observed empirical behaviours of the DAE approach.
Decision: Accept (spotlight)