Title: ON RANDOM DEEP WEIGHT-TIED AUTOENCODERS: EXACT ASYMPTOTIC ANALYSIS, PHASE TRANSI-TIONS, AND IMPLICATIONS TO TRAINING

Abstract: We study the behavior of weight-tied multilayer vanilla autoencoders under the assumption of random weights. Via an exact characterization in the limit of large dimensions, our analysis reveals interesting phase transition phenomena when the depth becomes large. This, in particular, provides quantitative answers and insights to three questions that were yet fully understood in the literature. Firstly, we provide a precise answer on how the random deep weight-tied autoencoder model performs "approximate inference" as posed by Scellier et al. (2018) , and its connection to reversibility considered by several theoretical studies. Secondly, we show that deep autoencoders display a higher degree of sensitivity to perturbations in the parameters, distinct from the shallow counterparts. Thirdly, we obtain insights on pitfalls in training initialization practice, and demonstrate experimentally that it is possible to train a deep autoencoder, even with the tanh activation and a depth as large as 200 layers, without resorting to techniques such as layer-wise pre-training or batch normalization. Our analysis is not specific to any depths or any Lipschitz activations, and our analytical techniques may have broader applicability.

1. INTRODUCTION:

The autoencoder is a cornerstone in machine learning, first as a response to the unsupervised learning problem (Rumelhart & Zipser (1985) ), then with applications to dimensionality reduction (Hinton & Salakhutdinov (2006) ), unsupervised pre-training (Erhan et al. (2010) ), and also as a precursor to many modern generative models (Goodfellow et al. (2016) ). Its reconstruction power is well utilized in applications such as anomaly detection (Chandola et al. (2009) ) and image recovery (Mousavi et al. (2015) ). With the surge of deep learning, thousands of papers have studied multilayer variants of this architecture, but theoretical understanding has been limited, since analyzing the learning dynamics of a highly nonlinear structure is typically a difficult problem even for the shallow autoencoder. To get around this, we tackle the task with a critical assumption: the weights are random and the autoencoder is weight-tied. One enjoys much analytical tractability from the randomness assumption, whereas weight tying enforces the random autoencoder to perform "autoencoding". We also study this in the high-dimensional setting, where all dimensions are comparably large and ideally jointly approaching infinity. We consider the simplest setting: vanilla autoencoders (i.e., ones with fully connected layers only) and their reconstruction capability. This is done for the sake of understanding the effect of depth, while we note our techniques may have broader applicability.

The aforementioned assumptions are not without justifications. There is a growing literature on deep neural networks with random weights, (Li & Saad (2018) ; Giryes et al. (2016) ; Poole et al. (2016) ; Schoenholz et al. (2016) ; Gabrié et al. (2018) ; Amari et al. (2018) ) to name a few, revealing certain properties of deep feedforward networks 1 . Several recent works have also studied random multilayer feedforward networks through the lens of statistical inference (Manoel et al. (2017) ; Reeves (2017) ; Fletcher et al. (2018) ). The idea of weight tying is considered in the important paper Vincent et al. (2010) with an empirical finding that autoencoders with and without weight tying perform comparably, and has become standard in autoencoders. Similar features of random connection and symmetry also appear in other neural models (Lillicrap et al. (2016) ; Scellier et al. (2018) ). Finally the high-dimensional setting is common in recent statistical learning advances (Bühlmann & Van De Geer (2011)) , and not too far from the actual practice where many large datasets have dimensions of at least a few hundreds and are harnessed by large-scaled models.

We seek quantitative answers to three specific questions that are motivated by previous works:

• In exactly what way does the (vanilla) random weight-tied autoencoder perform "approximate inference"? This term is coined in Scellier et al. (2018) in connection with the theoretical results in Arora et al. (2015) , which implicitly studies the said model. In particular, Arora et al. (2015) proves an upper bound on xx2 , where x and x are the input and the output of the network, but is limited in the number of layers and specific to the ReLU activation. This direction has been recently extended by Gilbert et al. (2017) . In our work, we establish precisely what this approximate inference is by obtaining a general and asymptotically exact characterization 2 of x, for any number of layers and any Lipschitz continuous activations (Theorem 1 and Section 3.3). Theorem 1 is the key theoretical result of our work and lays the foundation for all analyses that follow.

• In what way is the deep autoencoder different from the shallow counterpart? Li & Saad (2018) ; Poole et al. (2016) reveal this in terms of the candidate function space and expressivity for feedforward networks. It is unclear how these notions are applicable to weighttied autoencoders, which seek replication of the input rather than a generic mapping. In this work, we show that the deep autoencoder exhibits a higher order of sensitivity to perturbations of the parameters (Section 3.4). • Does it have any implications to the training practice? Many recent works 3 Glorot & Bengio (2010); He et al. (2015) ; Schoenholz et al. (2016) ; Pennington et al. (2017) ; Yang & Schoenholz (2017); Xiao et al. (2018) ; Chen et al. (2018) ; Hayou et al. (2018) ; Hanin & Rolnick (2018) ; Hanin (2018) ; Burkholz & Dubatovka (2018) demonstrate a connection between the study of random networks, or ones at initialization, and their trainability. Note that these works either do not study weight-tied structures, or assume the analysis of the untying case for weight-tied structures. In our work, we derive and experimentally verify insights on how (not) to initialize deep weight-tied autoencoders, demonstrating that it is possible to train them without resorting to techniques such as greedy layer-wise pretraining, drop-out and batch normalization (Section 3.5). Specifically we experiment with 200-layer autoencoders.

No prior works have attempted all three tasks. The quantitative difference between weight-tied and weight-untied networks is in fact not negligible, yet the analysis is non-trivial due to the weight tying constraint (Arora et al. (2015) ; Chen et al. (2018) ). To address this issue and obtain Theorem 1, we apply the Gaussian conditioning technique, which first appears in the studies of TAP equations in spin glass theory (Bolthausen (2014) ) and is extensively used in the approximate message passing algorithm literature (Bayati & Montanari (2011) ; Javanmard & Montanari (2013) ; Berthier et al. (2017) ). This should be contrasted with untied random networks, whose analysis is typically more straightforward. More importantly, the difference is not only analytical: the overall picture of deep random weight-tied autoencoders is rich and drastically different from that of feedforward networks. An analysis in the limit of infinite depth reveals three fundamental equations governing the picture (Section 3.1), which displays multiple phase transition phenomena (Section 3.2).

Finally let us quickly mention other recent theoretical works on autoencoders: Arora et al. (2014) ; Arpit et al. (2015) ; Rangamani et al. (2017) ; Nguyen et al. (2018) studying the learned autoencoders in specific settings, Baldi (2012) ; Alain & Bengio (2014) ; Bengio et al. (2013) taking a framework where the encoder and the decoder are generic mappings, and Le Roux & Bengio (2008) ; Sutskever & Hinton (2008) ; Montufar & Ay (2011) exploring representational properties of related architectures. These works head in different directions from ours.

2. SETTING AND MAIN THEOREM:



2.1. SETTING AND ASSUMPTIONS:

Consider the following 2L-layers autoencoder with weight tying:

x = ϕ 0 W 1 ϕ 1 ...ϕ L-1 W L ϕ L (W L σ L-1 (...σ 1 (W 1 σ 0 (x) + b 1 ) + ...) + b L ) + v L + ... + v 1 .

Here x ∈ R n0 is the input, W ∈ R n ×n -1 is the weight, b ∈ R n is the encoder bias, and v ∈ R n -1 is the decoder bias, for = 1, ..., L. Also ϕ : R → R and σ : R → R are the activations (where for a vector u ∈ R n and a function ϕ : R → R, we write ϕ (u) to denote the vector (ϕ (u 1 ) , ..., ϕ (u n )) ). It is usually the case in practice that σ 0 (u) = u the identity function.

We introduce some convenient quantities inductively:

x 0 = x, x = W σ -1 (x -1 ) + b , = 1, ..., L, xL = W L ϕ L (x L ) + v L , x = W ϕ (x +1 ) + v , = L -1, .

.., 1. Note that x = ϕ 0 (x 1 ). See Fig. 5 of Appendix A.1 for a schematic diagram. We assume weights are random. Specifically we generate the weights and biases according to

(W ) ij ∼ N 0, σ 2 W, n -1 i.i.d., (b ) i ∼ N 0, σ 2 b, i.i.d., (v ) i ∼ N 0, σ 2 v, i.i.d.

independently of each other. The scaling of the variances accords with the literature and actual practice (Glorot & Bengio (2010) ; Vincent et al. (2010) ). We also consider the asymptotic highdimensional regime, indexed by n:

n = n (n) , n n -1 → α > 0 and n → ∞ as n → ∞, ∀ .

Here σ W, , σ b, , σ v, and α are finite constants independent of n. We enforce σ W, > 0, but allow σ b, and σ v, to be zero. We assume that all activations are Lipschitz continuous, and the encoder activations σ 's are non-trivial in the sense that for any τ > 0, E z σ (τ z)

2:

> 0 where z ∼ N (0, 1). We also assume that 1 n0 σ 0 (x) 2 tends to a finite and strictly positive constant as n → ∞. We refer to Appendix A.1 for more clarifications of notations.

2.2. MAIN THEOREM:

We motivate our main result via a simplified shallow autoencoder:

x = W ϕ (W x) = m i=1 w i ϕ w i x , where W ∈ R m×n , w i ∈ R n . Notice

x is a sum of independent terms, and by Stein's lemma (cf. Appendix E.2), E {x} ∝ E m i=1 ϕ w i x /m x. One thus expects x ≈ c 1 x + c 2 z for scalars c 1 , c 2 and z ∼ N (0, I n ), for large n and m. It is then important to specify exactly c 1 and c 2 . Theorem 1 formalizes this intuition with precise formulas for the scalars.

We now define some scalar sequences, which will then be related to the (vector) quantities of the autoencoders in Theorem 1. First we define {τ } =1,...,L and {τ } =0,...,L inductively:

τ 2 0 = 1 n 0 σ 0 (x) 2 , τ 2 = τ 2 + σ 2 b, , = 1, ..., L, τ 2 1 = σ 2 W,1 τ 2 0 , τ 2 = σ 2 W, E z σ -1 (τ -1 z) 2 , = 2, ..., L,

for z ∼ N (0, 1). Next, we define {γ , ρ } =2,...,L+1 inductively:

γ L+1 = 1 τ 2 L E z1 {τ L z 1 ϕ L (τ L z 1 )} , ρ L+1 = E z1 ϕ L (τ L z 1 ) 2 , γ = 1 τ 2 -1 E z1,z2 τ -1 z 1 ϕ -1 α σ 2 W, γ +1 σ -1 (τ -1 z 1 ) + α σ 2 W, ρ +1 + σ 2 v, z 2 , ρ = E z1,z2 ϕ -1 α σ 2 W, γ +1 σ -1 (τ -1 z 1 ) + α σ 2 W, ρ +1 + σ 2 v, z 2 2 , = L -1, ..., 2,

for z 1 , z 2 ∼ N (0, 1) independently. With these sequences defined, we can state the main theorem. Its statement uses the relational operator ∼ =, which is defined formally in Appendix A.1. Roughly speaking, a n ∼ = b n means a n and b n are asymptotically equal in distribution as n → ∞. Theorem 1. Consider the settings and assumptions as in Section 2.1, and the sequences {τ , τ } and {γ , ρ } defined as above. Then in the limit n → ∞:

(a) {τ } describes the behavior of the encoder output x :

x ∼ = τ z, = 1, ..., L, for z ∼ N (0, I n ).

(b) {τ , γ , ρ } describes the behavior of the decoder output x :

x ∼ = α σ 2 W, γ +1 σ -1 (τ -1 z 1 ) + α σ 2 W, ρ +1 + σ 2 v, z 2 , = 2, ..., L,

for z 1 , z 2 ∼ N 0, I n -1 independently. One can replace τ -1 z 1 with x -1 in the above, with z 2 independent of x -1 , in which case the statement also holds for = 1 with x 0 = x.

(c) For the autoencoder's output x,

x ∼ = ϕ 0 α 1 σ 2 W,1 γ 2 σ 0 (x) + α 1 σ 2 W,1 ρ 2 + σ 2 v,1 z 2 , for z 2 ∼ N (0, I n0 ) independent of x.

The proof of the theorem, as well as an outline of the key ideas, are in Appendix A. The theorem says that x , x and x admit simple descriptions which are tracked by scalar sequences {τ , γ , ρ }. Hence we can learn about the autoencoder by analyzing {τ , γ , ρ }, which is generally a simpler task than studying x , x and x directly. Numerical simulations in Appendix B suggest that, although the theorem's statement is in the infinite dimension limit, the agreement is already good for dimensions of a few hundreds. We note that while the theorem assumes Gaussian biases, the same proof technique allows to obtain a similar result with a more relaxed condition on the biases. Remark 2. While the theorem is specific to W following the Gaussian distribution, simulations in Appendix B suggest that the conclusion holds for a much broader class of distributions. We conjecture that it should hold so long as each W has i.i.d. entries and is independent of each other, its distribution has bounded k-th moment for some sufficiently large k, and the activations as well as the input x satisfy certain mild regularity conditions. Remark 3. We comment on the range of ρ and γ . We have ρ ≥ 0, which is obvious, and if

ϕ -1 ∞ ≤ C, then ρ ≤ C 2 . By Stein's lemma (cf. Appendix E.2), γ L+1 = E z {ϕ L (τ L z 1 )} , γ = α σ 2 W, γ +1 E z1,z2 ϕ -1 α σ 2 W, γ +1 σ -1 (τ -1 z 1 ) + α σ 2 W, ρ +1 + σ 2 v, z 2 σ -1 (τ -1 z 1 )

. If the activations are non-decreasing, then γ ≥ 0. Furthermore, if the activations are Lipschitz, then |γ | ≤ Cc for some constants C and c.

3. AN ANALYSIS AT INFINITE DEPTH:

In the following, we adopt a semi-rigorous approach, with an emphasis on the overall picture.

3.1. INFINITE DEPTH SIMPLIFICATION:

We make several analytical simplifications. First consider α

= α > 0, σ 2 W, = σ 2 W > 0, σ 2 b, = σ 2

b ≥ 0, ϕ = ϕ and σ = σ all independent of , except for ϕ L which is chosen separately (but we shall see that the specific choice of ϕ L is largely immaterial). We also assume that σ 2 v, = 0, and σ 0 and ϕ 0 are the identity4 . We introduce a parameter τ ≥ 0, whose role will be clear shortly, and which satisfies:

EQUATION

for z ∼ N (0, 1). Note that this implies σ 2 W ≤ σ 2 W,max = τ 2 /E σ (τ z) 2 . If this cannot be satisfied, we set τ 2 = +∞. In addition, let β = ασ 2 W > 0. With these, let us consider the following two fixed point equations:

EQUATION

for z 1 , z 2 ∼ N (0, 1) independently. Then Eq. ( 1), ( 2) and (3) together form the fundamental equations for deep random weight-tied autoencoders, in either one of the following senses:

Interpretation 1. For 1 L, in the limit L → ∞ (and → ∞ at a pace sufficiently slow compared to L), we have τ → τ , γ → γ and ρ → ρ, where τ is a stable fixed point solution to τ 2 = T τ 2 , and (γ, ρ) is then jointly a stable fixed point solution to γ = G (γ, ρ) and ρ = R (γ, ρ). In light of Theorem 1, (τ , γ, ρ) describes the behavior of an intermediate x :

x ∼ = S sig σ (x -1 ) + S var z, S sig = βγ, S var = βρ, where z ∼ N 0, I n -1 independent of x -1 , and x -1 ∼ = τ z for z ∼ N 0, I n -1 . If the convergences τ → τ , γ → γ and ρ → ρ are fast, then the majority of the intermediate layers are well approximately described by the above, in the regime of large L.

Interpretation 2. Suppose that for τ0 = x / √ n 0 , we impose the constraint

τ 2 0 = E σ (τ z) 2 .

This should be interpreted as follows: starting with a chosen τ , we normalize the input data x according to τ 2 0 = E σ (τ z) 2 ; then we choose σ 2 W ≤ σ 2 W,max and σ 2 b according to Eq. ( 1). Under this constraint, it is easy to see that τ = τ for all ≥ 1, and hence the norm of the input to each of the encoder's hidden layers is preserved by Claim (a) of Theorem 1. We then have that as L → ∞, at small ≥ 2 (i.e., at the layers near the two ends of the autoencoder), γ → γ and ρ → ρ, where (γ, ρ) is jointly a stable fixed point of γ = G (γ, ρ) and ρ = R (γ, ρ). The autoencoder's output is then, in this limit,

x ∼ = S sig x + S var z, S sig = βγ, S var = βρ, for z ∼ N (0, I n0 ) independent of x.

In either cases, we see that x or x is a composition of a signal component and a Gaussian variation component. Their respective strengths S sig and S var admit simple expressions, thanks to the infinite-L simplification 5 . We note that G and R do not take σ 2 b as a parameter. We refer to Appendix C.1 for the computation of γ and ρ. Fig. 1 shows that our asymptotic simplification is quite accurate already for L on the order of a few tens.

We also remark that the equation τ 2 = T τ 2 is known in the signal propagation analysis of random feedforward networks (Poole et al. (2016) ), but the equations γ = G (γ, ρ) and ρ = R (γ, ρ) are new. We also observe that in these equations, there is the presence of α (through β), which is typically missing from such analyses. Hence unlike untied structures, one may expect to see architectural constraints in analyses of weight-tied structures.

3.2. PHASE TRANSITION OF THE FIXED POINT:

With the infinite depth simplification, one question is on the existence of the solutions to Eq. ( 2) and (3), and how these fixed points look like. (Eq. ( 1) is well-studied, cf. Poole et al. (2016) ; Hayou et al. (2018) , and we will not analyze it here.) We note that γ = 0 is always a solution to Eq. (2), in biases. In addition, it is a common practice to initialize an untrained neural network (hence a random one) with zero biases (Goodfellow et al. (2016) ). This assumption also helps making the analysis more tractable. Other assumptions seem restrictive, but can be relaxed without affecting the analysis that follows, and hence are made for ease of presentation. For example, the assumption α = α for all may be relaxed to α = α for most such that 1 L. 5 Recall we consider the limit of n → ∞ before taking L → ∞. Without a proof, we expect that our results hold for L = o (log n), so practically this means 1 L Ω (log n). 

= E σ (τ z) 2 .

From left to right: α = 0.9, α = 1.0 and α = 1.5.

The gaps decrease exponentially with the depth L. The color intensity varies with ρ ∈ [0.1, 1] with equal spacings, where the darkest curve corresponds to ρ = 0.1, and the lightest is ρ = 1. From left to right: ϕ, σ are ReLU; ϕ is ReLU, σ is tanh; ϕ, σ are tanh; ϕ is tanh, σ is ReLU. A fixed point is an intersection between this mapping and the identity line (black dashed).

which case Eq. (3) also has a solution, for instance, when ϕ (0) = 0 such as ReLU or tanh (which admits ρ = 0). However γ = 0 is trivial, since it implies S sig is zero. We will be interested in the existence of non-trivial and stable fixed points. To ease visualization, for the moment, let us consider Eq. (2) only. Fig. 2 shows γ → G (γ, ρ) for different ρ, β, ϕ and σ for τ 2 = 1. For a given ϕ and σ, depending on β and ρ, one may observe one or more fixed points, one of which is at γ = 0 and can be stable or unstable. When γ = 0 is the only fixed point but is unstable, we have γ = ∞ as the "stable solution" to Eq. ( 2). The solution landscape changes drastically with β; for instance, when σ = ϕ = tanh, γ = 0 is the only and stable fixed point when β is small, but it becomes unstable and a new fixed point at γ > 0 emerges when β is sufficiently large. This hints at certain phase transition behaviors as β varies.

In Appendix C.2, we perform a detailed analysis of Eq. ( 2) and (3), supported by several rigorously proven properties. In the following, by an initialization for γ and ρ, we mean γ L+1 and ρ L+1 as in Section 2.2, and by convergence to γ and ρ, we mean the convergences as in Section 3.1. We highlight some results from the analysis for specific pairs of ϕ and σ:

ReLU ϕ and σ. We have two phase transitions at β = 2 and at β = 4. When β < 2, with any initialization, we have convergence to γ = 0 and ρ = 0. When 2 < β < 4, we have, with certain initializations, convergence to γ = 0 and divergence to ρ = +∞, and with certain other initializations, divergence to γ = +∞ and ρ = +∞. These include almost all possible initializations. When β ≥ 4, with any non-zero initialization, we have divergence to γ = +∞ and ρ = +∞.

ReLU ϕ and tanh σ. We have two phase transitions at β = 2 and β = β 0 (τ ) ∈ (2, ∞). When β < 2 , with any initialization, we have convergence to γ = 0 and ρ = 0. When 2 < β < β 0 , with any non-zero initialization, we have convergence to γ = 0 and divergence to ρ = +∞. When β > β 0 , with any non-zero initialization, we have divergence to γ = +∞ and hence ρ = +∞. We have two phase transitions at β = 1 and β = β 0 (τ ) > 1. When β ≤ 1, we have convergence to γ = ρ = 0. When 1 < β < β 0 , with any non-zero initialization, we have convergence to γ = 0 and ρ ∈ (0, 1). When β > β 0 , with any non-zero initialization, we have convergence to γ > 0 and ρ ∈ (0, 1). For τ > 0, γ cannot grow to +∞ as β varies. We note that β 0 → 1 if τ 2 → 0, and in the case α = 1, this implies σ 2 W → 1. With respect to Eq. ( 1), we then have σ 2 b → 0. An illustration is given in Fig. 3 .

0 0.5 1 1.5 2 β 0 1 2 3 4 γ ρ γ/ √ ρ 0 1 2 3 4 β 0 0.2 0.4 0.6 γ ρ γ/ √ ρ 0 1 2 3 4 5 β 0 0.2 0.4 0.6 γ ρ γ/ √ ρ

tanh ϕ and ReLU σ.

We have a picture similar to the case ϕ = σ = tanh, with a crucial difference that one cannot have β 0 be close to 1. An illustration is given in Fig. 3 . γ and ρ thus exhibit phase transitions, depend crucially on the choice of activations (especially the decoder activation ϕ), and can be trivialized (i.e., being zero or infinity) as in the case of ReLU ϕ and σ. It is remarkable that the above pictures are general for many other activations, as suggested by our analysis. In the next sections, we explore the implications of these behaviors.

3.3. APPROXIMATE INFERENCE AT INFINITE DEPTH:

Theorem 1 gives a quantitatively exact sense of how the random weight-tied autoencoder performs "approximate inference". Here we will be interested in stronger notions. A first question is: does it explain reversibility? Reversibility, as mathematically formalized in previous works Arora et al. (2015) ; Gilbert et al. (2017) , quantitatively concerns with how small the quantity E = xx 2 /n 0 is. The smaller it is, the better the decoder "reverses" the encoder. This formalized notion is an attempt to give a theoretical understanding of empirical findings that the input could be reproduced from the values of hidden layers of a trained feedforward network. Let us now consider the infinite depth simplification under Interpretation 2 of Section 3.1. We have E (S sig -1) 2 τ 2 0 + S 2 var . As such, for E ≈ 0 with high probability, one must have S sig ≈ 1 and S var ≈ 0, hence ρ ≈ 0.

Consequently, E ϕ (σ (τ z 1 )) 2 ≈ 0. For τ > 0, E ϕ (σ (τ z 1 )) 2

= 0 is impossible for any non-trivial activations (unless the activation outputs zero almost everywhere). Strikingly, in light of Section 3.2, when ϕ and σ are both ReLU, we have that S sig and S var are either 0 or +∞, in which case E ≥ τ 2 0 and can become unbounded. While this does not contradict the results in Arora et al. (2015) (which also concerns with ReLU activations, but with specific choices of the biases and limited depth, and hence is in a different setting), our discussion suggests that random weight-tied models may be insufficient to explain reversibility.

A second question is: does the model perform signal recovery? In this case, we are interested in whether x ∼ = cx for some constant c not necessarily 1. Similar to the above, this requires S var = 0, hence ρ = 0, and E ϕ (βγσ (τ z 1 )) 2 = 0. For non-trivial ϕ and σ, this requires ϕ (0) = 0 and γ = 0. Many activations do not conform with the former, and the latter implies x ∼ = 0 undesirably. This provides a negative answer to the question.

A critic may argue that in expectation, E {x} ≈ S sig x, and as per Section 3.2, there are cases where γ > 0 and hence S sig > 0. Yet in fact, this in-expectation property can already be observed in the simple setting of linear shallow autoencoders (Arora et al. (2015) ). What is ignored in such argument is that in many cases, S var > 0 whenever S sig > 0, in light Section 3.2. Our analysis hence mitigates the shortcoming of the in-expectation approach, and gives a more precise understanding of what the random weight-tied autoencoder can and cannot achieve when the depth becomes large.

3.4. COMPARISON WITH THE SHALLOW CASE:

Our result also allows for the case of L = 1 a shallow autoencoder. In particular, taking a parallel setting with Section 3.1 (in particular, Interpretation 2), by Theorem 1,

x ∼ = S sig x + S var z, S sig = βγ, S var = βρ, in which, with ϕ hid being the activation in the hidden layer,

γ = 1 τ 2 E {τ zϕ hid (τ z)} , ρ = E ϕ hid (τ z) 2 .

Some observations follow. In the shallow case, γ > 0 and ρ > 0 and both are bounded regardless of the parameters, except for trivial edge cases such as τ 2 = 0 or ϕ hid (•) = 0. Furthermore, γ and ρ are independent of β, for a fixed τ . As such, there is no phase transition in γ and ρ as β changes. We also have S sig (β) ∝ β and S var (β) ∝ √ β. Hence, the signal component dominates with S sig /S var ∝ √ β. Again this happens regardless of parameter choices.

In comparison with the infinite depth case, for ϕ = σ = tanh or ϕ = tanh and σ being the ReLU, as observed from Fig. 3 , in certain regimes, γ, ρ and γ/ √ ρ can grow (sublinearly) with β, and hence S sig (β) = Ω (β)6 , S var (β) = Ω √ β , and the signal component dominates with S sig /S var = Ω √ β . In particular, near the phase transition of γ, S sig /S var = Ω β 1.5 . Recalling that β = ασ 2 W , this implies for the infinite depth case, as compared to the shallow one, firstly a slight perturbation in σ 2 W may result in a larger perturbation in the signal's strength, and secondly an architecture using larger α may gain more in terms of amplification of the signals. In short, the deep autoencoder is more sensitive to slight changes in the parameters. As evident in Section 3.2, the case ϕ being the ReLU also exhibits extreme sensitivity, in that it is possible for a slight perturbation in β to drastically change γ and ρ. As suggested by Fig. 1 , it should be the case already for L about a few tens. It is, however, at the expense of much care in the selection of parameters, since there are continuous regimes in which the infinite depth diminishes S sig and S var to zero or boost them to infinity, a situation that never occurs in the shallow case. Remark 4. Sensitivity to perturbations is implied by expressivity, a notion put forth in Poole et al. (2016) in the study of random feedforward networks. Hence we expect that sensitivity is a common feature of various types of deep neural networks.

3.5. IMPLICATIONS TO TRAINING INITIALIZATION:

We examine the implications of Interpretation 1 in Section 3.1 to trainability of the weight-tied autoencoder. We first state our hypothesis, then test it with experiments.

The hypothesis. Since the majority of intermediate layers can be described approximately by γ and ρ (as well as τ ) and the random weight-tied autoencoder is in fact one at initialization, appropriate values of γ, ρ and τ (by a suitable choice of σ 2 W and σ 2 b ) should lead to better trainability. In particular, if one of them is ∞, we expect numerical errors or too large values resulting in quick saturation, both of which render the autoencoder untrainable. If γ = ρ = 0 in a neighborhood of the chosen σ 2 W and σ 2 b , we expect that the progress is slowed down in the beginning. If such pitfalls are avoided, the autoencoder is expected to show a faster progress.

Our analysis in Section 3.2 shows that those pitfalls can occur for a wide range of parameters. If the hypothesis is true, σ 2 W and σ 2 b must then be chosen carefully when L is large. As a special remark on the case ϕ is the ReLU, when α = 1, the hypothesis suggests taking σ 2 W = 2 and σ 2 b = 0. This coincides with the celebrated He initialization (He et al. (2015) ), which however considers feedforward networks only. Interestingly this does require σ to be the ReLU; for instance, σ can be tanh, in which case the argument in (He et al. (2015) ) is not applicable.

We shall also examine edge of chaos (EOC) initializations (Schoenholz et al. (2016) Here "-" indicates a positive finite value that depends on the choice of ϕ L (for which we choose the ReLU), but its exact value is irrelevant for our purpose. "EOC" indicates whether the scheme is an EOC initialization with respect to σ, and "xx" indicates an EOC scheme that is found to be the better one among all EOC initializations with Gaussian weights (Pennington et al. (2017) ). "Trainable" indicates better trainability in the beginning as predicted by our theory. "Slowed" indicates γ = ρ = 0 in a neighborhood. "Inf" indicates either γ → ∞ or ρ → ∞. The schemes with ϕ = tanh should be reflected against Fig. 3 .

Experiments. Table 1 lists several initialization schemes with α = 1, which are chosen such that the hypothesis can be tested separately for each pair ϕ and σ. We perform simple experiments on a weight-tied vanilla autoencoder as described in Section 3.1: L = 100, all hidden dimensions of 400, identity input activation σ 0 , and decoder biases initialized to zero. This sets α = α = 1 for ≥ 2; here α 1 = 1 is irrelevant in light of Interpretation 1. We train the autoencoder on the MNIST dataset with mini-batch gradient descent with a batch size of 250 and without regularizations, for 5 × 10 5 iterations (equivalent to 2500 epochs). We perform the experiments in two settings:

• Setting 1: The output activation ϕ 0 is tanh, MNIST images are normalized to [-1, +1], and the learning rate is fixed at 5 × 10 -3 . This is standard for MNIST.

• Setting 2: ϕ 0 is the identity, MNIST images are unnormalized (i.e., normalized to [0, +1]), and the learning rate is fixed at 3 × 10 -3 . This is common for regression.

These learning rates are chosen so that the learning dynamics is typically smooth, in light of recent works Mei et al. (2018) ; Smith & Le (2018) . We use the normalized 2 2 loss xx 2 / x 2 , and are primarily interested in this loss as a quality measure, since we only focus on trainability7 . We also do not apply techniques such as greedy layer-wise pre-training, drop-out or batch normalization. The results are plotted in Fig. 4 . See also Appendix D.1 for visualization of the reconstructions, and Appendix D.2 for the evolution over a broader range of parameters. Note that we plot the evolution in the logarithmic scale of time, since it is typically smooth and revealing on this scale, as found in prior works Baity-Jesi et al. (2018) ; Mei et al. (2018) and also evident from the plots.

Discussion. The results are in good agreement with our hypothesis. (Recall we test the hypothesis separately for each pair ϕ and σ, for which the involved schemes share the same architecture and only differ in the initialization.) Note that as predicted, in Setting 2, Scheme 3 and 6 are trapped with numerical errors, and in Setting 1, they saturate quickly at a high loss. As such, we do not include the results of Scheme 3 and 6 in Fig. 4 . 2 / x 2 of the schemes from Table 1 . Left: the setting with ϕ 0 = tanh (Setting 1). Right: the setting where ϕ 0 is the identity (Setting 2).

We see from the figure that Scheme 2, 5, 8, 10 and 14 show much slower progresses, by a factor of 3 to 10 times in terms of training iterations to reach the same loss. Hence a good amount of training time can be saved by an appropriate initialization. Interestingly Scheme 5 is in fact a special EOC initialization that Pennington et al. (2017) found to be the better one among all EOC schemes with Gaussian weights for tanh activation. This last observation shows that having good signal propagation through the encoder is far from being a sufficient condition for trainability.

Among the schemes, only Scheme 1 and 4 in Setting 1 and only Scheme 1, 4 and 7 in Setting 2 have their eventual trained networks produce meaningful reconstructions, whereas the rest always output some "average" of the training set regardless of the input, at the end of 5 × 10 5 iterations (see Appendix D.1). It is unclear whether this is a bad local minimum, or whether these schemes take much longer to show further progresses. An explanation is beyond our current theory, and it is an open question how to create a scheme with meaningful trainability. Remarkably all the schemes that show slower initial progresses (Scheme 2, 5, 8, 10 and 14) are among those that could not yield meaningful reconstructions.

We observe that in Setting 2, the tanh network under Scheme 7 is best performing in terms of the reconstruction loss, and its progress does not seem to reach a plateau after 5 × 10 5 iterations. In both settings, Scheme 4, which is a hybrid of ReLU and tanh activations, shows slight improvements over Scheme 1, which is a purely ReLU network. This extends the conclusion in Pennington et al. (2017) to the context of weight-tied autoencoders: reasonable training at a large depth is possible even for the notoriously difficult tanh activation, and this necessarily requires careful initializations.

Overall we see that our experiments confirm the hypothesis, showing an intimate connection between the phase transition behaviors found by our theory and trainability of the autoencoders.

4. DISCUSSION:

This paper has shown quantitative answers to the three questions posed in Section 1. This feat is enabled by an exact analysis via Theorem 1. The theorem is stated in a general setting, allowing varying activations, weight variances, etc, but our analyses in Section 3 have made several simplifications. This leaves a question of whether these simplifications can be relaxed, and how the picture changes accordingly, for instance, when the parameters vary across layers, similar to Yang & Schoenholz (2018) . Many other questions also remain. For example, what would be the covariance structure between the outputs of two distinct inputs? How does the network's Jacobian matrix look like? These questions have been answered in the feedforward case (Poole et al. (2016) ; Pennington et al. ( 2017)), but we believe answering them is more technically involved in our case. We have also seen that an autoencoder that shows initial progress may not necessarily produce meaningful reconstruction eventually after training, and hence much more work is needed to understand the training dynamics far beyond initialization. Recent works Mei et al. (2018) ; Rotskoff & Vanden-Eijnden (2018); Sirignano & Spiliopoulos (2018) ; Chizat & Bach (2018) have made progresses in this direction for shallow networks.

Greg Yang and Sam S Schoenholz. Deep mean field theory: Layerwise variance and width variation as methods to control gradient explosion. 2018.

Greg Yang and Samuel Schoenholz. Mean field residual networks: On the edge of chaos. In Advances in neural information processing systems, pp. 7103-7114, 2017. A PROOF OF THEOREM 1

EQUATION

In the following, we give an outline of the proof of Theorem 1, and the complete proof. First, we start with a few notations and definitions.

A.1 DEFINITIONS AND NOTATIONS

We recall the setting in Section 2.1 (see also Fig. 5 for a schematic diagram of the autoencoder). We define {g : R n -1 → R n -1 } =1,...,L inductively as follows:

g L (u) = W L ϕ L (W L σ L-1 (u) + b L ) + v L , g (u) = W ϕ (g +1 (W σ -1 (u) + b )) + v , = L -1, ..., 1.

It is easy to see that x = g (x -1 ) for = 1, ..., L. Essentially g 's represent the autoencoding mappings computed by the inner layers.

We use bold-face letters (e.g. x, W ) to denote vectors or matrices. We use C throughout to denote an arbitrary (and immaterial) constant that is independent of the dimensions. For two vectors x and y, x, y denotes their inner product. We use I for the identity matrix, and I n to emphasize its dimensions n × n. We use • to denote the usual Euclidean norm, • ∞ the infinity norm, and M 2 the maximum singular value of a matrix M . For a sigma-algebra F and two random variables X and Y , X|F A sequence of functions φ n : R n → R is uniformly pseudo-Lipschitz if there exists a constant C, independent of n, such that for any x, y ∈ R n ,

|φ n (x) -φ n (y)| ≤ C 1 + x √ n + y √ n x -y √ n .

A sequence of functions φ n : R n → R n is uniformly Lipschitz if there exists a constant C, independent of n, such that for any x, y ∈ R n , φ n (x) -φ n (y) ≤ C xy . These definitions are adopted from Berthier et al. (2017) . For two sequences of random variables X n ∈ R and Y n ∈ R indexed by n, we write X n Y n to mean that X n -Y n → 0 in probability. The same meaning holds when Y n is deterministic. For two sequences of random vectors X n ∈ R n and Y n ∈ R n indexed by n, we write X n ∼ = Y n if for any sequences of uniformly pseudo-Lipschitz test functions

φ n : R n → R, φ n (X n ) E {φ n (Y n )} (

and hence in this context, we do not need X n and Y n to be defined on a joint probability space).

A.2 OUTLINE OF THE PROOF OF THEOREM 1:

We state several results that are key to prove Theorem 1. Proposition 5. Consider the asymptotic setting n → ∞, with some sequence m = m (n) such that m/n → α > 0 as n → ∞. Let ϕ : R → R and σ : R → R be Lipschitz continuous scalar functions. Consider a sequence of uniformly Lipschitz functions g : R m → R m , and sequences of

vectors b ∈ R m , v ∈ R n , u ∈ R n such that b 2 m ≤ C, 0 < c ≤ σ (u) 2 n ≤ C, v 2 n ≤ C

for all sufficiently large n. Let us define

f (u) = W ϕ (g (W σ (u) + b)) + v, where W ∈ R m×n with W ij ∼ N 0, σ 2 W /n i.i.d. for σ W > 0. Let γ = E z 1 mτ 2 τ z, ϕ (g (τ z + b)) , ρ = E z 1 m ϕ (g (τ z + b)) 2 , τ 2 = σ 2 W σ (u) 2 n ,

for z ∼ N (0, I m ). Then:

f (u) ∼ = ασ 2 W γσ (u) + ασ 2 W ρz + v, where z ∼ N (0, I n ) (independent of u, b and v).

Here the randomness is solely due to W .

A corollary follows from this proposition. Corollary 6. Consider the same setting as in Proposition 5. Further assume that b ∼ N 0, σ 2 b I m , v ∼ N 0, σ 2 v I n and u ∼ N 0, σ 2 u I n , independent of each other and of W . Then:

f (u) ∼ = ασ 2 W γσ (σ u z) + ασ 2 W ρ + σ 2 v z ,

for z, z ∼ N (0, I n ) independently. In particular, for φ : R → R Lipschitz continuous,

EQUATION

)

EQUATION

)

in which

γ = E z 1 mτ 2 τ z, ϕ (g (τ z)) , ρ = E z 1 m ϕ (g (τ z)) 2 , τ 2 = σ 2 W E z1 σ (σ u z 1 ) 2 +σ 2 b ,

where z ∼ N (0, I m ), and z 1 , z 2 are independently distributed as N (0, 1).

In a nutshell, the proposition and the corollary consider a random weight-tied "autoencoder" with a single hidden layer, with a mapping g in the middle. Since g is not a separable function (i.e., g does not apply entry-wise), this is different from the usual shallow autoencoder, a case that has been investigated in Pennington & Worah (2017) ; Louart et al. (2018) with techniques and objectives different from ours. By understanding this structure, one can understand the random weight-tied multi-layer autoencoder. Indeed, for each , the proposition applies with u being x -1 , f (u) being x and g being g +1 . In other words, this studies the mapping g . One can start with g L , then progressively move to outer layers g L-1 , g L-2 , etc, and hence analyze the autoencoder completely by repeating the same procedure L times. We note that in doing so, at each step, one requires certain information about the inner layers to perform calculations for the outer layers, and this is worked out in Corollary 6 via a simple recursive relation. In particular, the left-hand sides of Eq. ( 4) and Eq.

(5) play the role of ρ and γ of the outer layer, whereas their right-hand sides involve ρ and γ from the inner layers. It is also important to note that the assumption that the weights at different layers are independent is crucial in making u, g and (W , b, v) to be independent, allowing the proposition to be applicable at all steps. This is the idea behind the proof of Theorem 1.

We quickly mention the key proof technique for Proposition 5. The main technical challenge in working with the weight-tied structure W h (W u), for some h : R m → R m and W ∈ R m×n Gaussian, is that whereas y = W u is Gaussian with zero mean thanks to independence between u and W , W h (y) is not since y is correlated with W . It is observed in Bolthausen (2014) that conditioning on a linear constraint y = W u (or the sigma-algebra F generated by y and u), one has that W is distributed as a conditional projection component plus an independent Gaussian component:

W |F d = E {W |F} + W P ⊥ u , where P ⊥

u is an appropriate projection. Here E {W |F} is what propagates the information about u. In addition, W is Gaussian and independent of F, and hence exact calculations can be then worked out. We note that the assumption W is Gaussian is crucial for this identity to hold.

A.3 PROOF OF PROPOSITION 5:

We state the Gaussian Poincaré inequality, which will be used multiple times throughout the proof. We remark that the use of the Gaussian Poincaré inequality is unlikely to lead to a tight nonasymptotic result, but is sufficient for our asymptotic analysis. Theorem 7 (Gaussian Poincaré inequality). For z ∼ N 0, σ 2 I n and φ : R n → R continuous and weakly differentiable, there exists a universal constant C such that Var {φ (z)} ≤ Cσ 2 E ∇φ (z)

2 .

Now we are ready for the proof.

Step 1.

We perform Gaussian conditioning. Let y = W σ (u). Let F be the sigma-algebra generated by y and u. Conditioning on F is equivalent to conditioning on the linear constraint y = W σ (u). Following Bayati & Montanari (2011) , we have

W |F d = W P σ(u) + W P ⊥ σ(u) ,

where W d = W and is independent of F, P σ(u) = σ (u) σ (u) / σ (u) 2 the projection onto σ (u), and P ⊥ σ(u) = I -P σ(u) the corresponding orthogonal projection. As such, since ϕ (g

(y + b)) is F-measurable, f (u) |F d = 1 σ (u) 2 W σ (u) , ϕ (g (y + b)) σ (u) + P ⊥ σ(u) W ϕ (g (y + b)) + v = 1 σ (u) 2 y, ϕ (g (y + b)) σ (u) + P ⊥ σ(u) W ϕ (g (y + b)) + v.

For a sequence of uniformly pseudo-Lipschitz functions φ n : R n → R:

EQUATION

Up to this point, there is no need for the asymptotics n → ∞. The rest of the proof focuses on Φ n .

Step 2. We show that τ , γ and ρ are uniformly bounded as n → ∞. This is trivial for τ , and we note τ > 0. Consider ρ. We have for any

r ∈ R m , 1 √ m ϕ (g (r + b)) ≤ 1 √ m ϕ (g (r + b)) -ϕ (g (0)) + 1 √ m ϕ (g (0)) ≤ C √ m r + b + 1 √ m ϕ (g (0)) ≤ C √ m r + C √ m b + 1 √ m ϕ (g (0)) ≤ C √ m r + C (7)

for sufficiently large m. It is then easy to see that ρ is uniformly bounded. Regarding γ,

|γ| τ ≤ E z 1 m z ϕ (g (τ z + b)) ≤ E z 1 m z 2 ρ = √ ρ,

by Cauchy-Schwarz inequality. Therefore γ is also uniformly bounded.

Step 3. We analyze the first term in Φ n . Notice that y d = τ z for some z ∼ N (0, I m ). In addition, the mapping y → y, ϕ (g (y + b)) /m is uniformly pseudo-Lipschitz, by noticing that

1 m y 1 , ϕ (g (y 1 + b)) - 1 m y 2 , ϕ (g (y 2 + b)) ≤ 1 m ϕ (g (y 1 + b)) y 1 -y 2 + 1 m y 2 ϕ (g (y 1 + b)) -ϕ (g (y 2 + b)) ,

along with the fact that y → ϕ (g (y + b)) is uniformly Lipschitz, and Eq. ( 7). As such, by Theorem 7,

Var 1 m y, ϕ (g (y + b)) ≤ Cτ 2 m E 1 + 1 √ m y + 1 √ m b 2 ≤ 3Cτ 2 m E 1 + 1 m y 2 + 1 m b 2 = O 1 m ,

which tends to 0 as n → ∞. By Chebyshev's inequality, we thus have

1 m y, ϕ (g (y + b)) E 1 m y, ϕ (g (y + b)) = E 1 m τ z, ϕ (g (τ z + b)) = γτ 2 .

Step 4. We analyze the second term in Φ n . We have:

P ⊥ σ(u) W ϕ (g (y + b)) = W ϕ (g (y + b)) - σ (u) σ (u) 2 σ (u) , W ϕ (g (y + b)) . (8)

Note that the mapping y → 1 m ϕ (g (y + b))

2 is uniformly pseudo-Lipschitz by a similar argument. Hence again by Theorem 7, Var 1 m ϕ (g (y + b))

2 = O (1/m), which yields 1 m ϕ (g (y + b)) 2 E 1 m ϕ (g (y + b)) 2 = E 1 m ϕ (g (τ z + b)) 2 = ρ.

Recall that W is independent of F, and as such, there exists a random variable z ∼ N (0, 1) independent of y such that

1 n σ (u) , W ϕ (g (y + b)) = 1 n √ n σ (u) ϕ (g (y + b)) σ W z 1 n σ (u) √ αρσ W z ,

which converges to 0 in probability, where we have used the fact that ρ is uniformly bounded from

Step 2. Furthermore, there also exists a random vector z ∼ N (0,

EQUATION

)

Step 5. We finish the proof. From the definition of uniform pseudo-Lipschitz functions and Eq. ( 8) and ( 9), we obtain:

Φ n -φ n ασ 2 W γσ (u) + ασ 2 W ρz + v ≤ C 1 + | y, ϕ (g (y + b)) | σ (u) 2 + ασ 2 W |γ| σ (u) √ n + P ⊥ σ(u) 2 W 2 ϕ (g (y + b)) √ n + ασ 2 W ρ z √ n + 2 v √ n × y, ϕ (g (y + b)) σ (u) 2 -ασ 2 W γ σ (u) √ n + 1 √ n ϕ (g (y + b)) - √ αρ σ W z √ n + √ n σ (u) 1 n σ (u) , W ϕ (g (y + b)) .

Here notice that P ⊥ σ(u) 2

= 1, and as a standard fact from the random matrix theory, W 2 ≤ c α, σ 2 W a constant with high probability (see e.g. Vershynin (2012) ). Furthermore, 1

√ n z ≤ C with high probability due to the law of large numbers. Combining with the facts from Step 2, 3 and 4, it is then easy to see that

EQUATION

)

Finally, since γ and ρ are uniformly bounded from Step 2, it is easy to show that the mapping

z → φ n ασ 2 W γσ (u) + ασ 2 W ρz + v

is uniformly pseudo-Lipschitz. Hence by Theorem 7,

Var φ n ασ 2 W γσ (u) + ασ 2 W ρz + v = O 1 n , which yields φ n ασ 2 W γσ (u) + ασ 2 W ρz + v E φ n ασ 2 W γσ (u) + ασ 2 W ρz + v .

Together with Eq. ( 6) and ( 10), this completes the proof.

A.4 PROOF OF COROLLARY 6:

By Proposition 5, for any sequence of uniformly pseudo-Lipschitz φ n : R n → R:

φ n (f (u)) E z φ n ασ 2 W γσ (u) + ασ 2 W ρz + v , for z ∼ N (0, I n ) independent of u, v and b, in which γ = γ (τ , b) = E z 1 mτ 2 τ z, ϕ (g (τ z + b)) , ρ = ρ (τ , b) = E z 1 m ϕ (g (τ z + b)) 2 , τ 2 = τ 2 (u) = σ 2 W σ (u) 2 n ,

for z ∼ N (0, I m ) independent of u and b. It is easy to see that τ 2 τ 2 = τ 2 -σ 2 b . For any t ∈ (0, ∞), the mapping b → γ (t, b) is uniformly pseudo-Lipschitz, and hence by Theorem 7,

Var b {γ (t, b)} = O (1/m), which yields γ (t, b) E b {γ (t, b)}. Recall τ is independent of b. As such, γ (τ , b) E b {γ (τ , b)}. Furthermore, the mapping t → E b {γ (t, b)} is continuous and hence E b {γ (τ , b)} E b {γ (τ, b)}.

Performing a similar argument for ρ (τ , b), we thus have:

ρ ρ, γ E z,b 1 mτ 2 τ z, ϕ (g (τ z + b)) .

We note by Stein's lemma,

E z,b { τ z, ϕ (g (τ z + b)) } = τ 2 E z div (ϕ • g) τ 2 + σ 2 b z , E z,b { b, ϕ (g (τ z + b)) } = σ 2 b E z div (ϕ • g) τ 2 + σ 2 b z . Also notice that E z,b { τ z + b, ϕ (g (τ z + b)) } = E z τ 2 + σ 2 b z, ϕ g τ 2 + σ 2 b z .

Direct algebras then yield

E z,b 1 mτ 2 τ z, ϕ (g (τ z + b)) = γ,

and hence γ γ. Therefore,

φ n (f (u)) E z φ n ασ 2 W γσ (u) + ασ 2 W ρz + v ≡ h (u, v) .

The mapping (u, v) → h (u, v) is uniformly pseudo-Lipschitz and hence by Theorem 7,

Var u,v {h (u, v)} = O (1/n), which implies h (u, v) E u,v,z φ n ασ 2 W γσ (u) + ασ 2 W ρz + v = E z,z φ n ασ 2 W γσ (σ u z) + ασ 2 W ρ + σ 2 v z

which follows from the fact that u, v and z are independent and normally distributed. The first claim is hence proven.

Eq. ( 4) follows immediately from the above. The proof of Eq. ( 5) is similar and hence omitted.

A.5 PROOF OF THEOREM 1:

The following lemma states that, roughly speaking, g is uniformly Lipschitz (indexed by n) with high probability. First, recall that W = W (n) is indexed by n, and one can easily construct a joint probability space on which the sequence {W (n)} n≥1 is defined. The exact construction is immaterial, so long as for each n, the marginal distribution satisfies the setting in Section 2.1. We work in this joint space in the following. Lemma 8. For each = 1, ..., L, there exists a finite constant c > 0 such that P E N → 0 as N → ∞, where the event E N is defined as

E N = sup (n,u1,u2)∈D g (u 1 ) -g (u 2 ) u 1 -u 2 > c , D = {n > N, u 1 , u 2 ∈ R n -1 , u 1 = u 2 } . Proof. Consider = L. Recall that g L (u) = W L ϕ L (W L σ L-1 (u) + b L ) + v L .

Then for any u 1 and u 2 , > 0 such that P W 2 2 > η ≤ e -c n (see e.g. Vershynin (2012) ). As such, using this fact for = L, by the union bound,

g L (u 1 ) -g L (u 2 ) = W L ϕ L (W L σ L-1 (u 1 ) + b L ) -W L ϕ L (W L σ L-1 (u 2 ) + b L ) ≤ W L 2 ϕ L (W L σ L-1 (u 1 ) + b L ) -ϕ L (W L σ L-1 (u 2 ) + b L ) (i) ≤ C W L 2 W L σ L-1 (u 1 ) -W L σ L-1 (u 2 ) ≤ C W L 2 2 σ L-1 (u 1 ) -σ L-1 (u 2 ) (ii) ≤ C W L 2 2 u 1 -u 2 ,

P E N L ≤ n>N e -c L n ≤ ∞ u=N e -c L u du = 1 c L e -c L N ,

which proves the claim for = L. To see the claim for general , we have from a similar calculation:

g (u 1 ) -g (u 2 ) ≤ W 2 g +1 (W σ -1 (u 1 ) + b ) -g +1 (W σ -1 (u 2 ) + b ) ≤ C L-+1 L r= W r 2 2 u 1 -u 2 .

Therefore,

sup (n,u1,u2)∈D g (u 1 ) -g (u 2 ) u 1 -u 2 ≤ C L-+1 L r= η r

with probability at least

1 - n>N L r= e -c r N ≥ 1 - L c e -c N , c = min 1≤ ≤L c ,

by the union bound. This proves the claim.

Lemma 9. For each ≥ 0, τ +1 and τ +1 are finite and strictly positive. Furthermore,

1 n σ (x ) 2 τ 2 +1 /σ 2 W, +1 , and x +1 ∼ = τ +1 z for z ∼ N 0, I n +1 .

Proof. We prove the lemma by induction. The claim is trivially true for = 0 by assumption. Assume the claim for some ≥ 0. Due to independence, conditioning on x ,

x +1 |x d = σ 2 W, +1 n σ (x ) 2 + σ 2 b, +1 z, where z ∼ N 0, I n +1 independent of x . Since 1 n σ (x ) 2 τ 2 +1 /σ 2 W, +1 , we then have x +1 ∼ = τ 2 +1 + σ 2 b, +1 z = τ +1 z, which implies 1 n +1 σ +1 (x +1 ) 2 → E z σ +1 (τ +1 z ) 2

for z ∼ N (0, 1). By the induction hypothesis, τ +1 > 0. Hence by assumption, the right-hand side is finite and strictly positive. One also recognizes that it is equal to τ 2 +2 /σ 2 W, +2 . Since σ W, +2 is strictly positive and finite, so is τ +2 , and hence so is τ +2 . This completes the proof.

We are now ready for the proof of Theorem 1. Claim (a) of the theorem, which follows directly from Lemma 9, is just a forward pass through the encoder and hence is the same as in the case of random feedforward networks (without weight tying) Poole et al. (2016) . For = 2, ..., L, let H denote the following three claims:

EQUATION

: 1 n -1 τ 2 -1 τ -1 z -1 , ϕ -1 (g (τ -1 z -1 )) γ ,

for z 1 , z 2 , ∼ N 0, I n -1 independently, and z -1 ∼ N 0, I n -1 independent of g , with the understanding that g L+1 is the identity. We prove them by induction, and Claim (b) then follows immediately. We first note that with high probability, for any ,

1 n b 2 and 1 n -1 v 2 are

bounded by the law of large numbers. Consider H L . Note that x L-1 is independent of g L , and that

1 n L-1 σ L-1 (x L-1 )

2 converges to a finite non-zero constant in probability by Lemma 9. Hence by Corollary 6, with g being the identity, f being g L , u being x L-1 (recalling xL = g L (x L-1 )) and φ being ϕ L-1 , and the fact x L-1 ∼ = τL-1 z -1 from Claim (a), H L is proven.

Assuming H +1 for some , we prove H . Recall that g +1 is independent of Θ = {W , b , v , x -1 , z -1 }, and g is independent of x -1 and z -1 . Also from Claim (a), x -1 ∼ = τ -1 z -1 . Consider some N ∈ N and let E N +1 denote the event as defined in Lemma 8. On the event ¬E N +1 (the complement of E N +1 ), by Corollary 6, with respect to the randomness of Θ ,

x ∼ = α σ 2 W, γσ -1 (τ -1 z 1 ) + α σ 2 W, ρ + σ 2 v, z 2 , 1 n -1 ϕ -1 (g (τ -1 z -1 )) 2 E z1,z2 ϕ -1 α σ 2 W, γσ -1 (τ -1 z 1 ) + α σ 2 W, ρ + σ 2 v, z 2 2 , 1 n -1 z -1 , ϕ -1 (g (τ -1 z -1 )) E z1,z2 z 1 φ α σ 2 W, γσ -1 (τ -1 z 1 ) + α σ 2 W, ρ + σ 2 v, z 2 , in which γ = E z 1 n τ 2 τ z , ϕ (g +1 (τ z )) , ρ = E z 1 n ϕ (g +1 (τ z )) 2 .

Note that here γ and ρ are functions of g +1 and hence random, and z ∼ N (0, I n ) independent of g +1 . On the event ¬E N +1 , with the fact that τ is finite and non-zero by Lemma 9, we have the mapping

z → 1 n τ 2 τ z , ϕ (g +1 (τ z )) ≡ h (z )

is uniformly pseudo-Lipschitz, and hence applying Theorem 7, one obtains that

Var z {h (z )} = O 1 n ,

with the right-hand side independent of g +1 for n > N . Consequently, due to Lemma 8 and Chebyshev's inequality, for any > 0,

P |h (z ) -γ| > , ¬E N +1 = E P z {|h (z ) -γ| > } I ¬E N +1 ≤ E 1 2 Var z {h (z )} I ¬E N +1 = o n (1) (1 -o N (1)) = o n (1) ,

where o n (1) → 0 as n → ∞. On the other hand, since z is independent of g +1 , invoking H +1 ,

P {|h (z ) -γ +1 | > } = o n (1) .

As such,

P {|γ -γ +1 | > } ≤ P {|h (z ) -γ +1 | > } + P {|h (z ) -γ| > } ≤ P {|h (z ) -γ +1 | > } + P |h (z ) -γ| > , ¬E N +1 + P E N +1 = o n (1) + o n (1) + o N (1) .

Letting n → ∞ then N → ∞, we then have γ γ +1 . Similarly, we also have ρ ρ +1 . It is then easy to deduce H , recalling the definitions of γ and ρ .

The claim that τ -1 z 1 can be replaced with x -1 in the expression for x in Claim (b) can be recognized easily by doing the same replacement in the proof of Corollary 6 and the above proof.

The proof of Claim (c) is similar. We omit these repetitive steps.

B NUMERICAL VERIFICATION OF THEOREM 1:

We perform simple simulations to verify Theorem 1 at finite dimensions. In particular, we simulate a random weight-tied autoencoder, as described in Section 2.1, with L = 50, σ 2 W, = 2.312, σ 2 b, = 0.211, σ 2 v, = 0, ϕ = σ = tanh, identity ϕ 0 and σ 0 , α = 1, and consequently n = n 0 , for an input x ∈ R n0 whose first half of the entries are +1 and the rest are -1. Then we compute the following:

γ +1 = x , σ -1 (x -1 ) α σ 2 W, σ -1 (x -1 ) 2 , ρ +1 = 1 α σ 2 W, 1 n -1 x 2 - α 2 σ 4 W, γ2 +1 n -1 σ -1 (x -1 ) 2 -σ 2 v,

.

We also compute {γ , ρ } =2,...,L+1 as in Section 2.2, and γ and ρ as in Section 3.1. Theorem 1 predicts that γ γ and ρ ρ . Section 3.1 also asserts that γ ≈ γ and ρ ≈ ρ for L. Fig. 6 shows the results for n 0 = 500 and n 0 = 2000. We observe a quantitative agreement already for n 0 = 500, and this improves with larger n 0 .

Next we verify the normality of the variation component in x. We compute

ẑ = x -α 1 σ 2 W,1 γ2 x α 1 σ 2 W,1 ρ2 + σ 2 v,1

.

Its empirical distribution should be close to N (0, 1), in light of Theorem 1. We make this comparison in Fig. 7 , and again observe good agreement already for n 0 = 500.

Finally we re-simulate the autoencoder with different distributions of the weights W . In particular, we try with the Bernoulli distribution, the uniform distribution, and the Laplace distribution, with their means and variances adjusted to zero and σ 2 W, /n -1 respectively. The results for n 0 = 2000 are plotted in Fig. 8 and 9 . We observe good quantitative agreements between the simulations for these non-Gaussian distributions and the prediction as in Theorem 1, although the theorem is proven only for Gaussian weights. • if βE {σ (τ z 1 )} ≥ 2, there is only one fixed point at γ = 0, which is unstable.

(d) Assume σ is non-zero on a set of positive Lebesgue measure, and that σ is an odd function.

Then for any ρ, the mapping γ → G (γ, ρ) is a straight line through the point (0, 0). Furthermore, if βE {σ (τ z 1 )} = 2, there is only one fixed point at γ = 0, which is stable for βE {σ (τ z 1 )} < 2 and unstable for βE {σ (τ z 1 )} > 2; if βE {σ (τ z 1 )} = 2, any γ is a fixed point.

(e) Assume σ is odd, and consider β > 2. Given γ ≥ 0, we have R (γ, ρ) > ρ for all ρ ≥ 0.

The proposition suggests the following picture. First consider σ is ReLU. Since E {σ (τ z 1 )} = P (τ z 1 ≥ 0) = 0.5, we have two phase transitions at β = 2 and at β = 4. In particular, based on Proposition 10:

• When β < 2, with any initialization, we have convergence to γ = 0 and ρ = 0. This is based on Claim (a) and (c). • When β ∈ (2, 4), with certain initializations, we have convergence to γ = 0 and divergence to ρ = +∞; with certain other initializations, we have divergence to γ = +∞ and ρ = +∞. This excludes a special initialization at the unstable fixed point, which is a singleton and essentially a rare case. This is based on Claim (a), (b) and (c). • When β ≥ 4, with any non-zero initialization, we have divergence to γ = +∞ and hence ρ = +∞. This is based on Claim (b) and (c).

Now we consider σ is tanh. Let β 0 = β 0 (τ ) = 2/E {σ (τ z 1 )}, and it is easy to see that β 0 > 2 since σ = tanh. The following picture is then expected:

• When β < 2, with any initialization, we have convergence to γ = ρ = 0. This is based on Claim (a) and (d).

• When β ∈ (2, β 0 ), with any non-zero initialization, we have convergence to γ = 0 and divergence to ρ = +∞. This is based on Claim (a) and (d).

• When β > β 0 , with any non-zero initialization, we have divergence to γ = +∞ and ρ = +∞. This is based on Claim (b) and (d).

• When β = β 0 , we have that γ is unchanged from the initialization. Since β 0 > 2, we then have divergence to ρ = +∞. This is based on Claim (b) and (e).

One crucial property of the ReLU is that it is unbounded at infinity and its derivative at infinity is bounded away from zero. This allows γ and ρ to grow to infinity. This is a stark contrast to the case ϕ is bounded, for instance, ϕ = tanh as we shall see.

C.2.2 THE CASE OF tanh ϕ:

We state a result that is relevant to ϕ = tanh. Proposition 11. Assume that ϕ thrice-differentiable with ϕ (0) = 0, ϕ (0) = κ, and ϕ (k) ∞ ≤ C for k = 0, ..., 3, where ϕ (k) is the k-th derivative of ϕ. Assume σ is Lipschitz continuous, nondecreasing. Then: (a) γ = 0 and ρ = 0 is a fixed point. Furthermore, assuming that σ is non-zero on a set of positive Lebesgue measure, ϕ is non-zero almost everywhere and τ ∈ (0, ∞), we have if ρ = 0, it must be that γ = 0; in other words, if γ > 0, then ρ > 0. (c) Given γ = 0, if β < 1/κ 2 , ρ = 0 is a stable fixed point, and if β > 1/κ 2 , ρ = 0 is unstable.

(d) Consider τ ∈ (0, ∞). Assume that

• σ is positive on a set of positive Lebesgue measure, and E {σ (τ z)} > 0 for z ∼ N (0, 1), • either case 1: σ (u) = 0 for u ≤ 0, and ∆ ρ (u, t) < 0 for u, t, ρ > 0, or case 2: σ is an odd function, and ∆ ρ (u, t) < ∆ ρ (-u, t) for u, t, ρ > 0, in which ∆ ρ (u, t) = ϕ βu + √ βρt -ϕ βu -√ βρt , • ϕ satisfies E {zϕ (z)} → +∞ for z ∼ N 0, s 2 and s → ∞, • ϕ satisfies E {zI (z)} > 0 for z is any Gaussian with zero mean and non-zero variance, and I (u) = ϕ (u) + uϕ (u).

Then for any given ρ > 0, there exists β * = β * (ρ, τ ) > 0 finite such that if β ≤ β * , then γ = 0 is the only fixed point of the equation γ = G (γ, ρ) and is stable; if β > β * , γ = 0 is unstable, and there is one more fixed point at γ > 0 finite, which is stable.

(e) Consider τ ∈ (0, ∞). The same conclusion as in Claim (c) holds for ρ = 0 with β * = 1/ (κE {σ (τ z 1 )}), assuming

• σ is positive on a set of positive Lebesgue measure, and E {σ (τ z)} > 0 for z ∼ N (0, 1), • ϕ (u) < 0 for u > 0, and either case 1: σ (u) = 0 for u ≤ 0 , or case 2: ϕ and σ are odd functions.

The assumption ϕ (k) ∞ ≤ C for k = 0, ..., 3 is not critical, only serves to ensure integrability of various terms in the proof and is likely relaxable, but is made for simplicity. The following lemma establishes certain properties of the tanh function. Lemma 12. Consider ϕ = tanh. Then:

(a) For ∆ (u, t) = ϕ (u + t) -ϕ (u -t), we have ∆ (u, t) < 0 for u, t > 0, and ∆ (u, t) < ∆ (-u, t) for u, t > 0.

(b) lim s→∞ E {zϕ (z)} = +∞ for z ∼ N 0, s 2 .

(c) E {zI (z)} > 0 for z ∼ N 0, s 2 , s = 0, and I (u) = ϕ (u) + uϕ (u).

Now let us consider ϕ = σ = tanh. Note that tanh (u) ∈ (0, 1) for any u = 0, tanh (0) = 1 and E tanh (τ z 1 ) < 1 unless τ = 0. By Lemma 12, Proposition 11 applies. The following picture is suggested based on Proposition 11:

• When β < 1, we have convergence to γ = ρ = 0. This is based on Claim (c) and (e).

• The phase transition for ρ locates at β = 1, above which we have convergence to ρ ∈ (0, 1) given a non-zero initialization, and below which ρ = 0. Here ρ < 1 since tanh is bounded by 1. This is based on Claim (a), (b), and (c). • The phase transition of γ locates at some β > 1, above which we have convergence to γ > 0 given a non-zero initialization, and below which γ = 0. For τ > 0, γ cannot grow to +∞ as β varies. This is based on Claim (a), (b) and (d).

The proposition also suggests that the two phase transitions are close to each other if E {σ (τ z 1 )} ≈ 1. This requires that τ 2 ≈ 0, and σ 2 W ≈ 1 in the case α = 1. With respect to Eq. ( 1), we then have σ 2 b ≈ 0. Remarkably this is reminiscent of the context of random feedforward networks with tanh activations, in which (Pennington et al. (2017) ) finds that an initialization at σ 2 W ≈ 1 and σ 2 b ≈ 0 works better than most edge-of-chaos initialization schemes with Gaussian weights.

We also expect from the proposition a similar picture for σ being the ReLU, with a crucial difference. In this case, E {σ (τ z 1 )} = 0.5, and therefore one cannot have that the two phase transitions being close to each other.

Interestingly Claim (a) implies that the phase transition of ρ never occurs before that of γ, regardless of the specific ϕ and σ. One way for the phase transitions to be close to each other is, as above, taking ϕ = σ = tanh and τ 2 ≈ 0. Claim (a), (c) and (e) of the proposition also suggests that if E {σ (τ z 1 )} > ϕ (0), then γ and ρ will share the exact same location of the phase transitions, below which they are zero and above which they are positive.

C.3 PROOFS FOR SECTION C.2:

Proof of Proposition 10. Let θ = βγσ (τ z 1 ) + √ βρz 2 for brevity.

Claim (a). We have G (0, ρ) = 0 and R (0, 0) = 0. Simple calculations yield R (0, ρ) = βρ/2. Claim (a) is then immediate.

Claim (b).:

To study ρ in the case γ → ∞, we calculate:

1 ρ R (γ, ρ) = 1 ρ E +∞ z=-γσ(τ z1) √ β/ρ βγσ (τ z 1 ) + βρz 2 φ (z) dz = βE β ρ γσ (τ z 1 ) φ β ρ γσ (τ z 1 ) + 1 + β ρ γ 2 σ (τ z 1 ) 2 Φ β ρ γσ (τ z 1 )

where φ

(u) = 1 √ 2π exp -u 2 /2 and Φ (u) = u t=-∞ φ (t) dt the Gaussian PDF and CDF. Recall that we must have 1 ρ R (γ, ρ) = 1 unless ρ = ∞. Also notice that φ (∞) = 0 and Φ (+∞) = 1. Since σ is positive on a set of positive Lebesgue measure, if γ 2 /ρ → ∞ as γ → ∞, 1 ρ R (γ, ρ) → ∞, and hence it must be that ρ → ∞ when γ → ∞.

Claim (c). We compute the first partial derivative ∂ γ G (γ, ρ), using the fact ϕ (u) = δ (u = 0) (in the distributional sense) for the ReLU:

∂ γ G (γ, ρ) = βE {ϕ (θ) σ (τ z 1 )} + β 2 γE {ϕ (θ) σ (τ z 1 ) σ (τ z 1 )} = βE {ϕ (θ) σ (τ z 1 )} + β 2 γE {δ (θ = 0) σ (τ z 1 ) σ (τ z 1 )} = βE {ϕ (θ) σ (τ z 1 )} + β 2 γE 1 √ 2π exp - βγ 2 σ (τ z 1 ) 2 2ρ σ (τ z 1 ) σ (τ z 1 ) ,

where in the last step, we use the fact that z 1 and z 2 are independent. Hence some algebras yield the second partial derivative:

∂ 2 γ G (γ, ρ) = 2 π β 2 E σ (τ z 1 ) σ (τ z 1 ) exp - βγ 2 σ (τ z 1 ) 2 2ρ 1 - βγ 2 2ρ σ (τ z 1 ) 2 (i) = 2 π β 2 E {I (σ (τ z 1 )) σ (τ z 1 )} (ii) = 2 π β 2 τ E {I (σ (τ z 1 )) z 1 }

where in step (i), we define

I (u) = 1 2 u 2 exp - βγ 2 2ρ u 2 ,

in step (ii), we use Stein's lemma. Recall τ ∈ (0, ∞). Since σ (u) = 0 for all u ≤ 0, we have I (σ (τ z)) = 0 for z ≤ 0. In addition, I (u) > 0 almost everywhere and σ is non-zero on a set of positive Lebesgue measure. It follows that ∂ 2 γ G (γ, ρ) > 0. Therefore for any fixed ρ, the mapping γ → G (γ, ρ) is strictly convex. Notice that G (0, ρ) = 0. Hence it cannot be that there is a stable fixed point at γ > 0.

Next we have:

∂ γ G (+∞, ρ) = lim γ→+∞ βE {ϕ (βγσ (τ z 1 )) σ (τ z 1 )} = βE {σ (τ z 1 )} , ∂ γ G (0, ρ) = βE ϕ βρz 2 σ (τ z 1 ) = 1 2 βE {σ (τ z 1 )} .

Recall that γ → G (γ, ρ) is strictly convex. As such, when βE {σ (τ z 1 )} ≤ 1, there is only one fixed point at γ = 0, which is stable. When βE {σ (τ z 1 )} ∈ (1, 2), there are two: one at γ = 0, which is stable, and the other at γ > 0, which is unstable. When βE {σ (τ z 1 )} ≥ 2, there is only one fixed point at γ = 0, which is unstable.

Claim (d).:

In the case that σ is an odd function, u → I (u) is even and hence z → I (σ (τ z)) is even. Then from the calculation of Claim (c), it is easy to see that ∂ 2 γ G (γ, ρ) = 0. Also, G (0, ρ) = 0. Therefore for each ρ, the mapping γ → G (γ, ρ) is a straight line which passes through the point (0, 0). Since ∂ γ G (0, ρ) = 1 2 βE {σ (τ z 1 )}, the claim is then immediate. Claim (e). We recall the formula for R (γ, ρ) derived in the proof of Claim (b). Since σ is odd, φ is even and Φ -0.5 is odd, we have

1 ρ R (γ, ρ) = βE β ρ γσ (τ z 1 ) φ β ρ γσ (τ z 1 ) + 1 + β ρ γ 2 σ (τ z 1 ) 2 Φ β ρ γσ (τ z 1 ) - 1 2 + E β 2 1 + β ρ γ 2 σ (τ z 1 ) 2 = E β 2 1 + β ρ γ 2 σ (τ z 1 ) 2 .

Then if β > 2, we always have R (γ, ρ) > ρ.

Proof of Proposition 11. Let θ = βγσ (τ z 1 ) + √ βρz 2 for brevity.

Claim (a). The fact γ = ρ = 0 is a fixed point is obvious by assumption. Note that in order that R (γ, 0) = 0, one must have E ϕ (βγσ (τ z 1 )) 2 = 0. By assumption, this requires γ = 0.

Claim (b). The fact that 0 ≤ ρ ≤ C is obvious. Note that |γ| = 1 τ 2 E τ z 1 ϕ βγσ (τ z 1 ) + βρz 2 ≤ C τ E {|z 1 |} = C τ 2 π ,

which yields the claim.

Claim (c). We have:

∂ ρ R (γ, ρ) = β ρ E {ϕ (θ) ϕ (θ) z 2 } (i) = βE ϕ (θ) 2 + ϕ (θ) ϕ (θ) ,

where (i) is due to Stein's lemma. As such, ∂ ρ R (0, 0) = βκ 2 . The claim is then immediate.

Consider ρ > 0. We have:

∂ γ G (γ, ρ) = βE {ϕ (θ) σ (τ z 1 )} + β 2 γE {ϕ (θ) σ (τ z 1 ) σ (τ z 1 )} ,

and therefore,

EQUATION

where we use Stein's lemma and the fact z 1 and z 2 are independent. Notice that, for βρ > 0, by Stein's lemma,

E z2 ϕ a + βρz 2 = 1 √ βρ E z2 z 2 ϕ a + βρz 2 = 1 √ 2πβρ +∞ t=0 ϕ a + βρt -ϕ a -βρt t exp - t 2 2 dt.

Consider case 1. Since σ (u) = 0 for all u ≤ 0,

∂ 2 γ G (γ, ρ) = β 2 2πτ √ βρ +∞ z=0 +∞ t=0 ∆ ρ (γσ (τ z) , t) tzσ (τ z) 2 exp - z 2 + t 2 2 dtdz.

Since ∆ ρ (u, t) < 0 for any u > 0 and t > 0, and by the assumption that σ is positive on a set of positive Lebesgue measure (which cannot intersect with (-∞; 0] since σ (u) = 0 for all u ≤ 0), we have ∂ 2 γ G (γ, ρ) < 0 for γ > 0. In case 2, since σ is an odd function,

∂ 2 γ G (γ, ρ) = β 2 2πτ √ βρ +∞ z=0 +∞ t=0 [∆ ρ (γσ (τ z) , t) -∆ ρ (-γσ (τ z) , t)] tzσ (τ z) 2 exp - z 2 + t 2 2 dtdz.

Since ∆ ρ (u, t) < ∆ ρ (-u, t) for u > 0 and t > 0 and σ (u) ≥ 0 for u ≥ 0 (for σ being odd and non-decreasing), we again have ∂ 2 γ G (γ, ρ) < 0 for γ > 0. As such, the mapping γ → G (γ, ρ), for ρ > 0, is strictly concave on (0, ∞).

Next we have:

∂ γ G (0, ρ) = βE ϕ βρz 2 σ (τ z 1 ) = βE ϕ βρz 2 E {σ (τ z 1 )} ,

since z 1 and z 2 are independent. Notice that by Stein's lemma,

∂ β βE ϕ βρz 2 = 1 2 E I βρz 2 = 1 2βρ E βρz 2 I βρz 2 .

By assumption, we thus have that βE ϕ √ βρz 1 and hence ∂ γ G (0, ρ) are increasing in β. Furthermore, ∂ γ G (0, ρ) → 0 when β → 0, and

lim β→∞ ∂ γ G (0, ρ) (i) = E {σ (τ z 1 )} lim β→∞ 1 ρ E βρz 2 ϕ βρz 2 (ii) = +∞

where (i) is by Stein's lemma, and (ii) is by assumption. Therefore, there must exist

β * = β * (ρ, τ ) > 0 finite such that ∂ γ G (0, ρ) = 1 at β = β * , ∂ γ G (0, ρ) < 1 for β < β * and ∂ γ G (0, ρ) > 1 for β > β * . Since γ → G (γ, ρ

) is strictly concave on (0, ∞) and γ = 0 is a fixed point by Claim (a), β * is the threshold as in the claim.

Claim (e). Consider ρ = 0, in which case:

∂ 2 γ G (γ, 0) = β 2 τ √ 2π +∞ z=-∞

ϕ (βγσ (τ z)) zσ (τ z) 2 exp -z 2 2 dz.

Consider case 1. Since σ (u) = 0 for all u ≤ 0,

∂ 2 γ G (γ, 0) = β 2 τ √ 2π +∞ z=0

ϕ (βγσ (τ z)) zσ (τ z) 2 exp -z 2 2 dz.

Since ϕ (u) < 0 for u > 0 and σ is positive on a set of positive Lebesgue measure (which cannot intersect (-∞; 0] since σ (u) = 0 for all u ≤ 0), it is easy to see that ∂ 2 γ G (γ, 0) < 0 for γ > 0. In case 2, since ϕ and σ are odd, the mapping z → ϕ (βγσ (τ z)) is odd, and hence

∂ 2 γ G (γ, 0) = 2β 2 τ √ 2π +∞ z=0 ϕ (βγσ (τ z)) zσ (τ z) 2 exp - z 2 2 dz.

Again we have ∂ 2 γ G (γ, 0) < 0 for γ > 0. As such, γ → G (γ, ρ) is strictly concave on (0, ∞). Notice that ∂ γ G (0, 0) = βκE {σ (τ z 1 )}, linearly increasing in β. This proves the claim with β * = 1/ (κE {σ (τ z 1 )}).

Proof of Lemma 12. We prove the first claim: ∆ ρ (u, t) = tanh 2 (u -t) -tanh 2 (u + t) .

Since tanh 2 is even and increasing on (0, +∞), ∆ ρ (u, t) < 0 for u, t > 0 and ∆ ρ (u, t) > 0 for u > 0 and t < 0. Simple algebra yields ∆ ρ (-u, t) -∆ ρ (u, t) = 2∆ ρ (u, -t) .

Hence ∆ ρ (u, t) < ∆ ρ (-u, t) for u > 0 and t > 0. To see the second claim, for z ∼ N (0, 1), lim In Fig. 10 , 11, 12 and 13, we show the reconstructions of several images by the trained networks after 5 × 10 5 training iterations, under the schemes from Table 1 , in the experiments of Section 3.5. We draw 10 digit images from the MNIST test set, as well as 3 letter images from the EMNIST Letters test set (Cohen et al. (2017) ). Note that the networks are not trained with any letter images from the EMNIST data set. The reconstruction quality is visually imperfect even after intensive training, which is entirely expected for vanilla autoencoders and regression problems.

Observe that for the schemes that yield meaningful reconstructions, they output recognizable digits for digit images, while for letter images, most of their reconstructions are hardly recognizable as letters. As such, the trained networks of these schemes do not simply approximate the identity function, but rather capture some low-dimensional structures of the data. An exception is Scheme 7 under Setting 2, which is not surprising since it is a purely tanh network and tanh is almost identity near zero.

D.2 VISUALIZATION OF THE EVOLUTION:

We show the evolution of the test reconstruction loss on the plane σ 2 W , σ 2 b , in conjunction with the experiments of Section 3.5. To make the computation more manageable, we opt for L = 50 with less iterations, while maintaining other parameters the same as in Section 3.5. The results are shown in Fig. 14 and 15. Several patterns emerge in good agreement with our hypotheses. Firstly, for ϕ = ReLU, the evolution starts earliest near σ 2 W = 2, shows almost no progress or is numerically unstable when σ 2 W 2, and is much slower when σ 2 W 2. Secondly, for ϕ = tanh, the evolution is much slower when σ 2 W 1. Intriguingly the evolution is almost insensitive to σ 2 b . W , σ 2 b at different iterations, as described in Appendix D.2, in Setting 2 (i.e., ϕ 0 is the identity). The description is similar to Fig. 14 . White indicates either a very large value or a numerical error, which are due to the fact that the chosen learning rate is not sufficiently small. Note that in this setting with ϕ = ReLU, the training process is trapped in numerical errors for σ 2 W > 2 as we expect, and hence the test loss at σ 2 W > 2 is not plotted.

E MISCELLANIES E.1 EDGE OF CHAOS INITIALIZATION:

We quickly review the edge of chaos (EOC) initialization (Schoenholz et al. (2016) ). For an activation σ, any σ 2 W , σ 2 b such that there exists a finite τ ≥ 0 for which

τ 2 = σ 2 W E σ (τ z) 2 + σ 2 b , σ 2 W = 1/E σ (τ z)

2 is said to be an EOC initialization scheme, where z ∼ N (0, 1). This is based on the order-to-chaos phenomenon found in (Poole et al. (2016) ). For ReLU σ, σ 2 W = 2 and σ 2 b = 0 is the only EOC initialization (Hayou et al. (2018) ) and coincides with the He initialization (He et al. (2015) ). For σ = tanh, there can be multiple pairs that form EOC initialization. (Pennington et al. (2017) ) argues that a better EOC scheme should be closer to dynamical isometry and suggests taking σ 2 W ≈ 1.05 and σ 2 b ≈ 2.01 × 10 -5 for σ = tanh. The EOC initialization is applicable to feedforward networks.

E.2 USEFUL FACTS:

We state several useful facts, which are used in various places throughout. First, for a Gaussian matrix W and an independent vector u, we have W u is also Gaussian. In particular, if entries of W are i.i.d. N 0, s 2 , then W u ∼ N 0, s 2 u 2 I . The second fact is Stein's lemma:

Lemma 13 (Stein's). E {zf (z)} = E {f (z)} for z ∼ N (0, 1) and f : R → R weakly differentiable whenever the expectations are defined.

:

Roughly speaking, we prove that x ∼ = c1x + c2z, for c1 and c2 scalars and z an independent Gaussian vector. It is then straightforward to deduce xx 2 . This quantity is hence meaningful when c1 = 1.

Many of these works refer to the random network framework as the mean-field analysis. Here we avoid using the term "mean-field" since it is also used to refer to the analysis of the learned infinitely-wide neural networks(Mei et al. (2018)), which is a different setting.

The assumption σ 2 v, = 0 aligns well with several recent theoretical analyses of the autoencoders(Arpit et al. (2015);Rangamani et al. (2017);Gilbert et al. (2017); Nguyen et al. (2018)) which disregard the decoder's

By f (β) = Ω(g(β)) in a certain range of β, we mean d dβ [f (β)/g(β)] ≥ 0 on this range.

The chosen loss is slightly different from the traditional 2 2 loss xx 2 . On one hand, we found from our experiments that these two losses perform comparably, with the normalized loss typically yielding slight improvements, provided that the learning rates are scaled appropriately. On the other hand, the normalized loss allows ease for interpretation.

Figures and Tables:

Figure2: The mapping γ → G (γ, ρ) for τ 2 = 1 and β = 5 (blue), β = 2.7 (red), β = 0.8 (green). The color intensity varies with ρ ∈ [0.1, 1] with equal spacings, where the darkest curve corresponds to ρ = 0.1, and the lightest is ρ = 1. From left to right: ϕ, σ are ReLU; ϕ is ReLU, σ is tanh; ϕ, σ are tanh; ϕ is tanh, σ is ReLU. A fixed point is an intersection between this mapping and the identity line (black dashed).

Figure 3: γ and ρ versus β, as solved with Eq. (2) and (3). The vertical dotted line is β = σ 2 W,max . From left to right: (1) ϕ = σ = tanh and τ 2 = 0.0259, (2) ϕ = σ = tanh and τ 2 = 1.2, and (3) ϕ = tanh, σ is the ReLU, and τ 2 = 0.2.

Scheme 2, 5,  8, 10, 14

Figure 5: Schematic diagram of the weight-tied autoencoder as described in Section 2.1. Left: the encoder. Center: the decoder. Right: dimensions of the corresponding vectors.

Y means that for any integrable function φ and any F-measurable bounded random variable Z, E {φ (X) Z} = E {φ (Y ) Z}. We write X d = Y when F is the trivial sigma-algebra.

where steps (i) and (ii) are because ϕ L and σ L-1 are Lipschitz. It is a standard fact in the random matrix theory that, for each = 1, ..., L, there exist finite constants η = η α , σ 2

Figure 6: The agreement among γ , γ and γ, and among ρ , ρ and ρ, for = 2, ..., 51 and Gaussian weights. The setting is described in Appendix B. We take a single run for the simulation of the autoencoder. Here n 0 = 500 (left) and n 0 = 2000 (right).

Figure 7: Quantile-quantile plots for the empirical distribution of ẑ, described in Appendix B, versus the standard Gaussian distribution. Here n 0 = 500 (left) and n 0 = 2000 (right).

If ϕ is bounded, then 0 ≤ ρ ≤ C, and |γ| ≤ C/τ .

{szϕ (sz)} = lim s→∞ E {s |z|} = +∞.To see the third claim, since I is odd,E {zI (z)} = 2E z tanh (z) + z 1 -tanh (z)

Figure10: The reconstructions by the schemes from Table1, as described in Appendix D.1, in Setting 1 (i.e., ϕ 0 = tanh). From the top row: original images, reconstructions from Scheme 1, 4 and 2. We omit the reconstructions from other schemes, since they are almost identical to those of Scheme 2. For each digit/letter category, the image is selected from the test set by ranking the reconstruction loss, averaged across Scheme 1 and 4, and picking one at the 75% percentile.

Figure 11: Description similar to Fig. 10. The chosen images are the 25% percentile.

Figure 12: Description similar to Fig. 10. The setting is Setting 2 (i.e., identity ϕ 0 ). The reconstructions are of Scheme 1, 4, 7 and 2. The chosen images are the 75% percentile. The ranking is by averaging over Scheme 1, 4, and 7.

Figure 13: Description similar to Fig. 10. The setting is Setting 2 (i.e., identity ϕ 0 ). The reconstructions are of Scheme 1, 4, 7 and 2. The chosen images are the 25% percentile. The ranking is by averaging over Scheme 1, 4, and 7.

Figure 14: The test loss for various pairs σ 2 W , σ 2 b at different iterations, as described in Appendix D.2, in Setting 1 (i.e., ϕ 0 = tanh). The horizontal axis is σ 2 b , and the vertical axis is σ 2 W . First row: ϕ = σ = ReLU; second row: ϕ = ReLU and σ = tanh; third row: ϕ = σ = tanh; fourth row: ϕ = tanh and σ = ReLU. Red indicates higher loss, and black indicates lower loss. White indicates a numerical error.

Figure 15: The test loss for various pairs σ 2W , σ 2 b at different iterations, as described in Appendix D.2, in Setting 2 (i.e., ϕ 0 is the identity). The description is similar to Fig.14. White indicates either a very large value or a numerical error, which are due to the fact that the chosen learning rate is not sufficiently small. Note that in this setting with ϕ = ReLU, the training process is trapped in numerical errors for σ 2 W > 2 as we expect, and hence the test loss at σ 2 W > 2 is not plotted.

Figure 1: The gaps |γ 2 -γ| and |ρ 2 -ρ| versus the depth L, where γ 2 and ρ 2 (which are dependent on L) are as in Section 2.2, and γ and ρ (the infinite-L limits of γ 2 and ρ 2 ) are from Eq.

Table content: <table><tr><td>(2) and</td></tr><tr><td>(3). Here all activations are tanh, τ 2 = 1.2, σ 2 b = 0.211, σ 2 W = 2.312 &lt; σ 2 W,max ≈ 2.806, and</td></tr><tr><td>τ 2 0 ≈ 0.4276, which satisfies τ 2 0</td></tr></table>

; Pennington  et al. (2017)) (see Appendix E.1). The EOC initialization enables better signal propagation in deep feedforward networks, and in our context, is relevant to the encoder part with the activation σ. List of initialization schemes for each pair of ϕ and σ, for α = 1.

Table content: <table><tr><td>No.</td><td>ϕ</td><td>σ</td><td>σ 2 W</td><td>σ 2 b</td><td>τ 2</td><td colspan="2">EOC Trainable Slowed Inf</td></tr><tr><td>1</td><td colspan="2">ReLU ReLU</td><td>2.0</td><td>0.0</td><td>-</td><td>x</td><td>x</td></tr><tr><td>2</td><td colspan="2">ReLU ReLU</td><td>1.0</td><td>0.1</td><td>0.2</td><td/><td>x</td></tr><tr><td>3</td><td colspan="2">ReLU ReLU</td><td>2.5</td><td>0.0</td><td>∞</td><td/><td>x</td></tr><tr><td>4</td><td colspan="2">ReLU tanh</td><td>2.0</td><td>0.0</td><td>0.618</td><td/><td>x</td></tr><tr><td>5</td><td colspan="2">ReLU tanh</td><td colspan="3">1.05 2.01 × 10 -5 0.0259</td><td>xx</td><td>x</td></tr><tr><td>6</td><td colspan="3">ReLU tanh 2.505</td><td>0.3</td><td>1.460</td><td/><td>x</td></tr><tr><td>7</td><td>tanh</td><td>tanh</td><td colspan="3">1.05 2.01 × 10 -5 0.0259</td><td>xx</td><td>x</td></tr><tr><td>8</td><td>tanh</td><td>tanh</td><td>0.5</td><td>0.0136</td><td>0.0259</td><td/><td>x</td></tr><tr><td>9</td><td>tanh</td><td colspan="2">tanh 2.312</td><td>0.211</td><td>1.2</td><td>x</td><td>x</td></tr><tr><td>10</td><td>tanh</td><td>tanh</td><td>0.5</td><td>0.986</td><td>1.2</td><td/><td>x</td></tr><tr><td>11</td><td>tanh</td><td>tanh</td><td>1.0</td><td>0.771</td><td>1.2</td><td/><td>x</td></tr><tr><td>12</td><td colspan="2">tanh ReLU</td><td>2.0</td><td>0.0</td><td>-</td><td>x</td><td>x</td></tr><tr><td>13</td><td colspan="2">tanh ReLU</td><td>1.0</td><td>0.1</td><td>0.2</td><td/><td>x</td></tr><tr><td>14</td><td colspan="2">tanh ReLU</td><td>0.5</td><td>0.15</td><td>0.2</td><td/><td>x</td></tr></table>

Peer review (iclr2019):
 Building on the recent progresses in the analysis of random high-dimensional statistics problem and in particular of message passing algorithm, this paper analyses the performances of weighted tied auto-encoder. Technically, the paper is using the state evolution formalism. In particular the main theorem uses the analysis of the multi-layer version of these algorithm, the so-called state evolution technics, in order to analyse the behaviour of optimal decoding in weight-tied decoder. It is based on a clever trick that the behaviour of the decoding is similar to the one of the reconstruction on a multilayer estimation problem. This is a very orginal use of these technics. The results are 3-folds: (i) a deep analysis of the limitation of weight-tied DAE, in the random setting, (ii) the demonstration of the sensitivity to perturbations and (iii) a clever method for initialisation that to train a DAE. Pro: a rigorous work, a clever use of the recent progresses in rigorous analysis of random neural net, and a very deep answer to interesting questions, and Con: I do not see much against the paper. A minor comment: the fact that the DAE is "weight-tied" is fundamental in this analysis. It actually should be mentioned in the title!