{'fraction_non_alphanumeric': 0.058794274099381566, 'fraction_numerical': 0.016887947065692167, 'mean_word_length': 3.9047619047619047, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Benefits of Jointly Training Autoencoders: An Improved Neural Tangent Kernel Analysis

A remarkable recent discovery in machine learning has been that deep neural networks can achieve impressive performance (in terms of both lower training error and higher generalization capacity) in the regime where they are massively over-parameterized. Consequently, over the past year, the community has devoted growing interest in analyzing optimization and generalization properties of over-parameterized networks, and several breakthrough works have led to important theoretical progress. However, the majority of existing work only applies to supervised learning scenarios and hence are limited to settings such as classification and regression. In contrast, the role of over-parameterization in the unsupervised setting has gained far less attention. In this paper, we study the gradient dynamics of two-layer over-parameterized autoencoders with ReLU activation. We make very few assumptions about the given training dataset (other than mild non-degeneracy conditions). Starting from a randomly initialized autoencoder network, we rigorously prove the linear convergence of gradient descent in two learning regimes, namely: (i) the weakly-trained regime where only the encoder is trained, and (ii) the jointly-trained regime where both the encoder and the decoder are trained. Our results indicate the considerable benefits of joint training over weak training for finding global optima, achieving a dramatic decrease in the required level of over-parameterization. We also analyze the case of weight-tied autoencoders (which is a commonly used architectural choice in practical settings) and prove that in the over-parameterized setting, training such networks from randomly initialized points leads to certain unexpected degeneracies.


Introduction
Deep neural networks have achieved great success in a variety of applications such as image and speech recognition, natural language processing, and gaming AI. Remarkably, neural networks that achieve the state-of-the-art performance in each of these tasks are all massively over-parameterized, with far more weight parameters than the sample size of training data or the input dimension. Such networks can gain impressive performance in terms of both (near) zero training error and high generalization capacity, which seemingly contradicts the conventional wisdom of bias-variance tradeoffs. Surprising enough is the fact that (stochastic) gradient descent or its variants can effectively find global and generalizable solutions. Explaining this phenomenon has arguably become one of the fundamental tasks for demystifying deep learning.
As a consequence, there has been growing interest in understanding the power of the gradient descent for over-parameterized networks. Over the past several months, a specific line of research [Li and Liang, 2018, Allen-Zhu et al., 2018, Zou et al., 2018, Du et al., 2018, Oymak and Soltanolkotabi, 2019, Arora et al., 2019a, Zou and Gu, 2019 has led to exciting theoretical progress. In particular, the seminal work of Du et al. [2018] shows that gradient descent on two-layer neural networks with ReLU activation provably converges to some global minimum at a geometric rate, provided a sufficiently large number of neurons that is of polynomial order in the sample size. The key idea that leads to this result is the following: once the network is sufficiently wide, gradient descent does not change the individual weights much, but results in a nonnegligible change in the network output that exponentially reduces the training loss with iteration count. This line of thinking has been subsequently refined and linked to the stability of a special kernel, called the neural tangent kernel (NTK) [Jacot et al., 2018]. Arora et al. [2019a] shows that the minimum eigenvalue of the limiting kernel governs both the algorithmic convergence and the generalization performance.
Despite these exciting results, the majority of existing work has focused on supervised settings and hence are limited to tasks such as classification and regression. In contrast, the role of over-parameterization in the unsupervised setting (for tasks such as reconstruction, denoising, and visualization) has gained much less attention. An early example of over-parameterization in unsupervised learning can be traced back to learning over-complete dictionaries with sparse codes [Olshausen and Field, 1997]. Another example is the problem of learning mixtures of k well-separated spherical Gaussians, where Dasgupta and Schulman [2007] showed that initializing with O(k log k) centers enables expectation-maximization to correctly recover the k components.
Interesting (but limited) progress has been made towards understanding over-parameterization for autoencoders, a popular class of unsupervised models based on neural networks. Zhang et al. [2019] provided an empirical study of training highly over-parameterized autoencoders using a single sample. They empirically showed that when learned by gradient descent, autoencoders with different architectures can exhibit two inductive biases: memorization (i.e., learning the constant function) and generalization (i.e., learning the identity mapping) depending on the non-linearity and the network depth. Radhakrishnan et al. [2019] showed that over-parameterized autoencoder learning is empirically biased towards functions that concentrate around the training samples and hence exhibits memorization. Buhai et al. [2019] empirically showed that over-parameterization benefits learning in recovering generative models with single-layer latent variables (including the sparse coding model).
None of the above papers have rigorously studied the training dynamics of autoencoder models. The loss surface of autoencoder training was first characterized in Rangamani et al. [2017]. Subsequently, Nguyen et al. [2019] proved that under-parameterized (and suitably initialized) autoencoders performed (approximate) proper parameter learning in the regime of asymptotically many samples, building upon techniques in provable dictionary learning; cf. Arora et al. [2015], Nguyen et al. [2018].
Our Contributions. In this paper, we provide the first rigorous analysis of gradient dynamics of overparameterized, shallow (two-layer) autoencoders. We study different training schemes and establish upper bounds on the level of over-parameterization under which (standard) gradient descent, starting from randomly initialized weights, can linearly converge to global optima provided the training dataset obeys some mild assumptions. Our specific contributions are as follows: 1. First, we show how to extend the results in Du et al. [2018] to the setting of over-parameterized twolayer autoencoders. This involves developing a version of NTK for multiple outputs, which can be done in a straightforward manner by lifting the kernel matrix of a single output into a higher-dimensional space via Kronecker products.
trained case is significantly better compared with the weakly-trained case.
4. Finally, we study a special family of autoencoders for which the encoder and decoder are weight-tied, i.e., the two layers share the same weights (this is a common architectural choice in practical applications). For the weight-tied case, we show that even without any training, O(d/ǫ) hidden units are able to achieve ǫ test error where d is the input dimension. Indeed, as the number of hidden unit increases, the autoencoder approximately recovers an identity map. Since the identity map is not particularly meaningful, we speculate that training of weight-tied autoencoders under over-parameterization may lead to unexpected degeneracies.
Techniques. Our analysis essentially builds upon the technique of Du et al. [2018] for analyzing the global convergence of gradient descent using the neural tangent kernel. The special case of autoencoder networks is somewhat more complicated since we now have to deal with multiple outputs, but the use of Kronecker products enables us to derive concise NTK's for our setting. The work of Du et al. [2018] and subsequent papers study the weakly-trained case for the supervised setting where the second layer is fixed. We derive analogous bounds for the autoencoder setting. Moreover, we derive a new result for the jointly-trained case and obtain a significantly improved bound on the requisite level of over-parameterization. Our result is based on three key insights: (i) the Stein identity applied with ReLU enables us to exactly derive the limiting kernel with respect to the decoder's weights and link to the weakly-trained case; (ii) thanks to the linear decoder , the corresponding kernel is smooth, and the improved smoothness allows gradient descent to move greater amount from the initial point; and (iii) with this improved smoothness, we can derive a sharper characterization of the descent trajectory length in Frobenius norm instead of column-wise Euclidean norm.

Overview of main results
Notation. We use uppercase letters to denote matrices, and lowercase for vectors or scalars. An expectation is the notation C which represents a generic scalar constant, whose value can change from line to line. A vector is interpreted as a column vector by default. We denote by x i ∈ R d the i th -column (or sample) of the data matrix X, and W = [w 1 , . . . , w m ] ∈ R d×m denotes a weight matrix. Whenever necessary, we distinguish between the weight vector w r at different algorithmic steps using an explicit w r (t) indexed by the step t. For a matrix A = [a 1 , . . . , a m ] ∈ R d×m , vec(A) = [a 11 , . . . , a d1 , . . . , a 1m , . . . a dm ] ⊤ vectorizes the matrix A by stacking its columns. The symbol ⊗ denotes the Kronecker product. We use N (·) and Unif(·) to denote the Gaussian and uniform distributions respectively. We simply write E w instead of E w∼N (0,I) for brevity. Throughout the paper, we refer to an arbitrary δ ∈ (0, 1) as the failure probability of some event under consideration.

Two-layer autoencoders
Our goal is to analyze the dynamics of learning two-layer autoencoders with gradient descent. We focus on the two-layer autoencoder architecture with the rectified linear unit (ReLU), defined by φ(z) = max(z, 0) for any z ∈ R. In below, when φ is applied to a vector or a matrix, the ReLU function is applied element-wisely. Given an input sample x ∈ R d , the autoencoder returns a reconstruction u ∈ R d of x, given by where W = [w 1 , . . . , w m ] and A = [a 1 , . . . , a m ] are weight matrices of the first (encoder) and second (decoder) layers respectively. We do not consider bias terms in this work. However, in principle, the bias vector for the hidden layer can be regarded as the last column of W with the last dimension of x always being 1.
Remark 2.1 (Choice of scaling factor). Notice that we have scaled the output with 1/ √ md, where 1/ √ m is the factor for the first layer and 1/ √ d for the second layer. Such scaling has been utilized in mathematical analyses of supervised networks [Jacot et al., 2018] as well as of autoencoders [Li and Nguyen, 2018]. Since the ReLU is homogeneous to scaling, such factors can technically be absorbed into the corresponding weight matrices W and A, but we find that keeping such factors explicit is crucial to understand the asymptotic behavior of neural network training as the network widths (i.e., m in this case) go to infinity.
Let us now set up the problem. Suppose that we are given n training samples X = [x 1 , x 2 , . . . , x n ]. We assume that each weight is randomly and independently initialized. Then, we train the autoencoder via gradient descent over the usual squared-error reconstruction loss: Depending on which weight variables are being optimized, we consider three training regimes: • Weakly-trained case: This corresponds to the regime where the loss function (2.1) is optimized over the weights W while keeping A fixed. A different form of weak training is to fix the encoder and optimize (2.1) over A. Indeed, this practice is perhaps a folklore: it corresponds to standard kernel regression where the global convergence depends on the Hessian associated with random ReLU features. We do not pursue this case any further since kernel methods are well understood, but note in passing that the Hessian will eventually show up in our analysis.
• Jointly-trained case: This corresponds to the regime that (2.1) is optimized over both W and A. This case matches practical neural network training, and performs better than the weakly trained case. We will show that the contrast between weakly-trained and jointly-trained cases arises due to the nature of the different NTK's and our analysis may pave the way to better understanding of autoencoder training.
• Weight-tied case: Weight-tying is another common practice in training autoencoders. Here, one sets the encoder and decoder weights to be the same, i.e., A = W , and optimizes (2.1) over the common variables W . We study this problem from the perspective of over-parameterization and show that this case leads to somewhat unexpected degeneracies.
Throughout the paper, unless otherwise specified, we make the following assumptions: Assumption 1. All training samples are normalized, i.e., x i = 1 for i = 1, . . . , n.
We gather the training samples into the data matrix X = [x 1 , x 2 , . . . , x n ] and define λ n X ⊤ X . Assumption 1 implies that X F = √ n and hence 1 ≤ λ n ≤ n. We regard λ n as a parameter that depends on the data geometry. For certain families of matrices (e.g., those with independent Gaussian entries), λ n ∼ O(max(n/d, 1)), which can be o(n) depending on how large n is in terms of d. We note that throughout our analysis, X is regarded as fixed,and we will focus on the randomness in the weights.
Assumption 2. Consider a random vector w ∼ N (0, I) and define The matrix E w [ X ⊤ X] is the so-called Gram matrix from the kernel induced by the ReLU transformation and has been extensively studied in Xie et al. The above assumptions are relatively mild, which are in sharp contrast with assuming a specific generative model for the data (e.g., dictionary models, mixture of Gaussians [Nguyen et al., 2019, Buhai et al., 2019) that have so far been employed to analyze autoencoder gradient dynamics.

Results
We adopt the framework introduced in Du et al. [2018]. Our proofs proceed generally as follows: (i) We will consider the continuous flow of the autoencoder outputs U (t) = [u 1 (t), u 2 (t), . . . , u n (t)] ∈ R d×n corresponding to the samples in X at time t. This continuous flow can be morally viewed as the execution of gradient descent with infinitesimal learning rate. This enables us to write: where K(t) is a kernel matrix.
(ii) From this characterization, we can infer that the spectrum of K(t) governs the dynamics of the outputs.
To derive explicit convergence bounds, we will first prove that K(0) has positive minimum eigenvalue with high probability. This is achieved via using concentration arguments over the random initialization. Then, we will upper-bound the movement of each individual weight vector from the initial guess and hence bound the deviation of K(t) from K(0) in terms of spectral norm.
(iii) By discretizing the continuous-time analysis, we will obtain analogous bounds for gradient descent with a properly chosen step size and show that gradient descent linearly converges to a global solution.
Our results are informally stated in the following theorems: Theorem 2.1 (Informal version of Theorems 4.1 and 4.2). Consider an autoencoder that computes output where the weight vectors are initialized with independent vectors w r ∼ N (0, I) and a r ∼ Unif{−1, 1} d for all r ∈ [m]. For any δ ∈ (0, 1) and m ≥ C n 5 d 4 λn λ 4 0 δ 3 for some large enough constant C, the gradient descent over W linearly converges to a global minimizer with probability at least 1 − δ over the randomness in the initialization.
Theorem 2.2 (Informal version of Theorems 5.1 and 5.2). Consider an autoencoder that computes output u = 1 √ md Aφ(W ⊤ x) where the weight vectors are initialized with independent vectors w r ∼ N (0, I) and a r ∼ Unif{−1, 1} d for all r ∈ [m]. For any δ ∈ (0, 1) and m ≥ C ndλ 3 n λ 4 0 δ 2 for some large enough constant C, the gradient descent jointly over W and A linearly converges to a global minimizer with probability at least 1 − δ over the randomness in the initialization.
Comparisons with existing work. We summarize the quantitative implications of our results in Table 1 We emphasize that the factor d in our bounds arises due to the fact that our network produces highdimensional outputs (dimension d in the case of autoencoders) while the previous works have focused on scalar outputs. Note also that the input dimension d is implicitly hidden in λ 0 and λ n .
For weakly-trained networks with a single output, we (slightly) improve the order of over-parameterization: For the jointly-trained regime, we obtain a significantly improved bound over Du et al. [2018, Theorem 3.3]. Our result is consistent with Oymak and Soltanolkotabi [2019, Theorem 6.3], but we have both layers jointly trained; the proof technique in Oymak and Soltanolkotabi [2019, Theorem 6.3] is different from ours (bounding Jacobian perturbations), and does not seem to be easily extended to the jointly trained case.
Let us better understand the intuition behind the bounds in Table 1 in terms of the dimension d and the sample size n. We emphasize that in the fairly typical regime of machine learning where n ≥ d and λ n ∼ n/d, the level of over-parameterization for the single output is moderate (of order n 4 /d 3 ). Since autoencoders have an output dimension d, the factor-d in the bounds is natural in the jointly-trained case by characterizing the trajectory length by Frobenius norm. This is consistent with the result in Zou and Gu [2019]. Our bound is different from that in Zou and Gu [2019] in that we make assumption on the minimum eigenvalue λ 0 while they assume a lower bound on the sample separation ∆. A direct universal comparison between the two bounds is difficult; however, Oymak and Soltanolkotabi [2019] shows an upper bound λ 0 ≥ ∆/100n 2 . Finally, we note that initializing A with i.i.d. Rademacher entries keeps our analysis in line with previous work, and an extension to Gaussian random initialization of A should be straightforward.

Regime
Reference   Table 1]. Here, d is the input dimension, n is the training size, λ0 is the smallest eigenvalue of the Gram matrix, λn is the maximum eigenvalue of the covariance matrix and C is some sufficiently large constant. ∆ is the smallest distance between any pair of distinct training points.

NTK for general autoencoders
Let us first derive the neural tangent kernels for general autoencoders (possibly deep and with more than 2 layers) with multiple outputs in a compact form. Given n i.i.d samples X = [x 1 , x 2 , . . . , x n ] and the autoencoder f (θ, x), we consider minimizing the squared-error reconstruction loss: where θ is a vector that stacks all the network parameters (e.g. W and A) and . . , m denotes the corresponding output. The evolution of gradient descent over L(θ) with an infinitesimally small learning rate is represented by the following ordinary differential equation (ODE): The time-dependent NTK for autoencoders can be characterized as follows: where K(t) is an nd × nd positive semi-definite kernel matrix whose (i, j)-th block of size d × d is: Proof. Note that in the supervised learning setting with a single output, the (i, j)-th block is a single scalar equal to the inner product of two gradients. We prove this using simple calculus. The gradient of the loss over the parameters θ is where ∂u i /∂θ denotes the Jacobian matrix of the output vector u i with respect to θ. Combining with (3.1), the continuous-time dynamics of the prediction for each sample i ∈ [n] is specified as Vectorizing dU(t) dt , we get One can easily verify that K(t) is positive semi-definite.
If the parameters θ(0) are assumed to be stochastic, then the (deterministic) neural tangent kernel (NTK) is defined as: Note that K ∞ is time-independent. If the network is randomly initialized and its width is allowed to grow infinitely large, K(t) converges to K ∞ , and remains constant during training. Our goal is to show that if the width is sufficiently large (not necessarily infinite), then K(t) ≈ K(0) ≈ K ∞ , and the gradient dynamics are governed by the spectrum of K ∞ .

NTK for two-layer autoencoders
Let us now specialize to the case of two-layer autoencoders with ReLU activation. Since we consider the two training regimes, including the weakly-trained and jontly-trained, we first give the expression of a few base kernels whose appropriate compositions produce the final kernel for each individual case. The precise derivation of each regime is given in the next few sections.
Again, we consider the reconstruction loss: where the weights are independently initialized such that: Here the minimization can be either over the encoder weights W , or the decoder weights A, or both W and A. Let us denote If we fix A and optimize the loss L(W, A) over W , we get If we fix W and optimize the loss L(W, A) over A, we get Writing these kernels in Kronecker product form allows us to clearly visualize the connection to the supervised learning case, and enables characterization of their spectrum. Intuitively, in the jointly-trained case, since both W and A depend on t, an invocation of the chain rule leads to the sum G(t) + H(t) being the "effective" kernel that governs the dynamics. In the infinite-width limit where m → ∞, the NTKs in the corresponding training regimes reduce to compositions of the following fixed deterministic kernels: To derive the above expressions, we require independence between the initial choices W (0) and A(0) and an invocation of the Stein identity in Lemma A.1 for a Gaussian vector w: . . , n. In fact, both the kernel forms G(t), H(t) have appeared in previous work (cf. Du et al. [2018], Oymak and Soltanolkotabi [2019], but the relation H ∞ = G ∞ has not been observed for ReLU networks to the best of our knowledge. Somewhat curiously, we will show that the crucial component of the time-dependent kernel in the jointlytrained regime, H(t) (within H(t) + G(t)), is better-behaved than the corresponding kernel in the weaklytrained regime, G(t), thanks to its better Lipschitz smoothness, even though the respective limiting kernels are the same. This improved smoothness allows us to derive a much better bound on kernel perturbations with respect to changing weights, and this results in a significant improvement in the level of over-parameterization (Theorem 2.2).

Weakly-trained Autoencoders
We now analyze various training regimes; these will follow from different compositions of the above NTK's. In each of the analyses, we will first set up the corresponding NTK, study the gradient dynamics with infinitesimal step size (gradient flow), and then appropriately discretize the flow to get our final results.

Gradient flow
Consider the weakly-trained regime with the objective function: where the corresponding minimization is only performed over W . Suppose that the weight matrices W and A are randomly initialized such that are drawn independently for each all (i, j). After the initialization, we keep A fixed throughout and apply gradient descent learning over W with step size η: Let us derive the neural tangent kernel for this training regime. We first calculate the gradient of for any x ∈ R d , it is convenient to compute the gradient with respect to each column w r . The gradient ∇ wr L(W ) of the loss in (4.1) over w r is given by: where J r (u i ) 2 denotes the Jacobian matrix of the output vector u i with respect to w r : Let us consider the gradient flow for the weight vector w r (t) via the following ODE: Using (4.2) and (4.4), the continuous-time dynamics of the prediction for each sample i ∈ [n] is: Vectorizing dU(t) dt , we get the equation that characterizes the dynamics of U (t): 2 Note that φ(z) is differentiable everywhere except at z = 0, at which the derivative will be considered as 0.
then we can write K(t) in Kronecker form: Since W (0) and A(0) are randomly initialized, in the limit as m → ∞, K(0) converges to the NTK: where the last step follows from the independence of w(0) and a(0).
In other words, the NTK kernel is strictly positive definite. We want to bound the minimum eigenvalue of K(0) at the initialization W (0) and prove Now, we state the main theorem for the convergence of the gradient flow: Theorem 4.1 (Linear convergence of gradient flow, weakly-trained regime). Suppose Assumptions 1 and 2 hold. Suppose at initialization that the weights are independently drawn such that w r ∼ N (0, I) and To prove this theorem, we use the auxiliary results from Lemmas 4.1, 4.2 and 4.3.

The proof of this Lemma is given in Appendix B.
Remark 4.1. Compared with the results in Du et al. [2018], Song and Yang [2019], our bound exposes the dependence on the data X through the spectral norm of X and the dimension d. When λ n is much smaller than n, our bound improves over these aforementioned results. For example, if the training samples are drawn from certain distributions (e.g., Gaussians, or from sparsely used dictionary models), the bound can be as low as m ∼ O(d).
The next step in our analysis is to upper bound the spectral norm of the kernel perturbation, K(t) − K(0) , with high probability.
For any δ ∈ (0, 1) and some R > 0, with probability at least 1 − δ: One may ask why not to directly bound K(t) − K(0) for each time t but need the supremum over the ball near each w r . Basically, since w(t) depends on W (0) and A(0), directly working on K(t) − K(0) is difficult. The uniform bound (4.6) allows us to overcome this dependence when applied to K(t) − K(0).
Note that in this lemma we use K(w) to indicate that the kernel K is being evaluated at the weight vectors w r and ignore the time index t. In this Lemma, we use X(w r ) to denote X r evaluated at w r .
Proof. For simplicity of notation, we use sup w to represent the supremum in (4.6), and sup wr to represent sup { wr: wr −wr ≤R} . To prove this lemma, we work on the Frobenius norm instead of the spectral norm. Let us first write The last step follows from the fact that |x ⊤ i x j | ≤ 1 due to Cauchy-Schwartz. Therefore, since a r a ⊤ r F = a r 2 = d. Now we take expectation over the random vector w r 's on both sides: Next, we bound E w [sup wr |z ijr |]. By definition of z ijr , (4.7) The last step follows from the results in [Du et al., 2018, Lemma 3.2]. So we get Therefore, Finally, by Markov's inequality, with probability at least 1 − δ: and t ≥ 0 with probability at least 1 − δ. We have λ min (K(t)) > λ 0 2 Proof. This is the direct consequence of Lemma 4.1 and Lemma 4.2. Since w r (t) − w r (0) ≤ R = λ0δ 8n 2 d with probability at least 1 − δ for all t ≥ 0, then with probability at least 1 − 2δ. Using Weyl's inequality, we can bound: In what follows, we show that w r (t) − w r (0) ≤ R with high probability if m is sufficiently large.
Also, for each r = 1, 2, . . . , m: Proof. For all s ∈ [0, t), we have by the assumption λ min (K(s)) ≥ λ 0 /2. Therefore, the loss at time s is upper-bounded by which decays exponentially with time s at rate λ 0 /d.
To upper bound the movement of the weights w r (t) − w r (0) , we use the above result while expanding the derivative of w r (s) over time 0 ≤ s < t: where the last step follows from a r 2 = d, X 2 = λ n and Eq. (4.8). From the differential equation, w r (s) is continuous for all s ∈ [0, t), and so is w r (s) − w r (0) . Consequently, we can take the limit for t ′ → t: since exp −λ 0 s/d is continuous at s = t. Therefore, we finish the proof.
Proof. We prove this using Markov's inequality. We use the independence between A(0) and W (0) to derive expressions for the expectation. In this proof, the expectations are evaluated over W (0) and A(0).
where in the fourth step we use E[A(0) ⊤ A(0)] = dI, and in the last step we use the independence of the columns of W (0). Using Markov, we get: with probability at least 1 − δ.
Proof of Theorem 4.1. If the following condition holds

Gradient descent
The above result for gradient flow can be viewed as a convergence rate for gradient descent in the weaklytrained regime with infinitesimally small step size. We now derive a convergence rate for gradient descent with finite step sizes. then with probability at least 1 − δ the gradient descent on W with step size η = Θ( λ0 ndλn ), for k = 0, 1, . . .
We will prove Theorem 4.2 by induction. The base case when k = 0 is trivially true. Assume Eq. (4.9) holds for k ′ = 0, 1, . . . , k, then we show it holds for k ′ = k + 1. To this end, we first prove w r (k + 1) − w r (0) is small enough; then we use that property to bound X − U (k + 1) Lemma 4.5. If (4.9) holds for k ′ = 0, 1, . . . k, then we have for all r ∈ [m], Proof. We use the expression of the gradient in (4.2), which is: Then, the difference of the weight vector w r is: where the third step and the fourth step follow from the facts that X r (k ′ ) ≤ X = √ λ n and a r = √ d.

The last step follows because
Now, let us derive the form of X − U (k + 1). First, we compute the difference of the prediction between two consecutive steps, similar to deriving dui(t) dt . For each i ∈ [n], we have (4.10) We split the right hand side into two parts: v 1,i represents the terms that the activation pattern does not change and v 2,i represents the remaining term that pattern may change. Formally speaking, for each i ∈ [n], we define Then, we can formally define v 1,i and v 2,i as follows: We write v 1 = (v ⊤ 1,1 , v ⊤ 1,2 , . . . , v ⊤ 1,n ) ⊤ and do the same for v 2 , so In order to analyze v 1 ∈ R n , we define K and K ⊥ ∈ R nd×nd as follows: Next, we write φ(z) = z½[z ≥ 0] to make use the definition of S i and expand the form of ∇ wr L(W (k)): Then, we can write v 1 as: and expand X − U (k + 1) 2 F : We can further expand the second term above using (5.19) as below: We define and bound the following quantities and bound them in Claims B.1, B.2, B.3 and B.4.
Proof of Theorem 4.2. We are now ready to prove the induction hypothesis. What we need to is to prove holds for k ′ = k + 1 with probability at least 1 − δ. In fact, with probability at least 1 − δ where the last step follows from Claim B.1, B.2, B.3, and B.4.
Lower bound on the level of over-parameterization m. We require for any δ ∈ (0, 1) that where the first bound on R comes from the gradient descent whereas the second is required in Lemma 4.2.
By Claim 4.1 that X − U (0) F ≤ 2n δ with probability at least 1 − δ, then we require m ≥ C n 5 λ n d 4 λ 4 0 δ 3 , for a sufficiently large constant C > 0 so that the descent holds with probability 1 − δ.
We give proofs for Claims B.1, B.2, B.3, and B.4 in Appendix B.

Jointly-trained Autoencoders
In the previous section, we analyzed the gradient dynamics of a two-layer autoencoder under the weaklytrained regime. We now analyze the jointly-trained regime where the loss is optimized over both sets of layer weights. For consistency of our presentation, we reuse some key notations in this section; for example, K(t), U (t) have the same interpretation as before but possess a different closed form.

Gradient flow
The loss function we consider for this jointly-trained regime is the same: The difference is that the optimization is now taken over both weights W and A. To make the comparison easier, the matrices W and A are randomly initialized in the same way such that are drawn independently for each pair (i, j). W and A are then updated using gradient descent with step size η: Similar to the previous case, we derive the gradients of L(W, A) with respect the column w r of W and a r of A. The gradient ∇ wr L(W, A) is the same in (4.2) in Section 4.1 whereas ∇ ar L(W, A) is standard: Consider two ODEs, one for each weight vector over the continuous time t: dw r (t) dt = −∇ wr L(W (t), A(t)), (5.6) da r (t) dt = −∇ ar L(W (t), A(t)). (5.7) Using (5.4), (5.5), (5.6) and (5.7), the continuous-time dynamics of the predicted output, u i (t), for sample x i is given by: In these expresssions, we skip the dependence of the weight vectors on time t and simply write them as w r and a r . Vectorizing dU(t) dt , we get to the key equation that characterizes the dynamics of U (t): (5.8) In the above equation, G(t) is a size-nd × nd matrix of the form: is a size-nd × nd matrix: Let us emphasize again that G(t) is precisely the kernel that governs the dynamics for the weakly-trained case. On the other hand, H(t) is a Kronecker form of the Hessian of the loss function derived with respect to A, using the features produced at the output of the ReLU activations. As shown in Section 3, assuming randomness and independence of W (0) and A(0), we can prove that H(0) and G(0) converge to the same NTK as m → ∞. More specifically, we have (5.11) and Therefore, the neural tangent kernel for the jointly-trained autoencoder is given by: Denote the time-dependent kernel K(t) = G(t) + H(t). Since both G(t) and H(t) are positive semi-definite, we only focus on H(t) for reasons that will become clear shortly.
Since G(t) is also positive definite with high probability (Section 4.1), the flow convergence can be also boosted by the positive definiteness of G ∞ . By Assumption 2, Since G(0) is positive semi-definite, in order to bound the minimum eigenvalue of K(0), all we need is to bound that of H(0). Importantly, we observe that the smoothness of the kernel H(t) is much better as a function of the deviation of the weights from the initialization. This allows the weights to change with a larger amount than merely using G(t), and enables us to significantly reduce the number of parameters required for the gradient to reach a global optimum.
Our main result for gradient flow of the jointly-trained autoencoder is given by: Theorem 5.1 (Linear convergence of gradient flow, jointly-trained regime). Suppose Assumptions 1 and 2 hold. The initial weights are independently drawn such that w r ∼ N (0, I) and a r ∼ Unif({−1, 1} d ) for all r ∈ [m]. If m ≥ C nλ 3 n d λ 4 0 δ 2 for some large enough constant C, then with probability at least 1 − δ, Remark 5.1. We initialize the second-layer weights A with independent Rademacher entries. This is for convenience of analysis because such A has constant-norm columns. However, similar results should easily follow for initialization with more practical schemes (for example, i.i.d. Gaussians).
We will first state and prove a few auxiliary results in Lemmas 5.1, 5.2, and 5.6 and then use them to prove Theorem 5.1.
4 . Remark 5.2. Let us compare with Lemma 4.2. Note that compared with that bound, O(n 2 dR w ) on the kernel perturbation, here the spectral norm bound on H(t) − H(0) is significantly better in two ways: (i) the bound scales with 1/ √ m, which later determines the over-parameterization and (ii) the movement is now characterized by the total W (t)−W (0) F . This is possible due to the smoothness of the ReLU activation, which is the reason why we focus on H(t) instead of G(t).
Proof. We apply the triangle inequality and use the Lipschitz property of the rectified linear unit to bound the difference. Recall that Then, we can upper bound the perturbation as follows: In the third step, we use the fact that the ReLU function is 1-Lipschitz and φ(X ⊤ W (t) ≤ X W (t) . The last step follows by W (t) − W (0) F ≤ R w . Using the condition and Weyl's inequality, one can easily show that λ min (K(t)) ≥ λ min (H(t)) > λ 0 /2.
We haved proved that as long as the weight matrix W (t) do not change much over t, the minimum eigenvalue of K(t) stays positive. Next, we show that this implies the exponential decay of the loss with iteration, and give a condition under which the weights do not change much.
Proof. For s ∈ [0, t), we have Then, one can bound the entire weight matrix as follows: In the second step, we use the fact CD F ≤ C F D for any matrices C, D, and X 2 = λ n . The last step follows from A(s) ≤ A(0) + R a and Lemma 5.3. Using the same continuity, we have Lemma 5.5. Fix t > 0. Suppose λ min (K(s)) ≥ λ0 2 and W (s) − W (0) F ≤ R w for all 0 ≤ s < t, then for r = 1, 2, . . . , m Proof. For s ∈ [0, t), we use the gradient derived in (5.5) and (5.7) to obtain: Then, one can write The last step follows from Lemma 5.3. Now, we integrate out s: which is what we need.
Lemma 5.6. If R ′ w < R w and R ′ a < R a , then for all t ≥ 0, we have (i) λ min (K(t)) ≥ λ0 2 ; and for all r ∈ [m], Proof. Suppose on the contrary that (5.14) is not an empty set. Therefore, t 0 inf T exists. Using the same contuinity argument as in Lemma 4.3, one can verify that t 0 > 0. First, if λ min (K(t 0 )) ≤ λ0 2 , then by Lemma 5.2, W (t 0 ) − W (0) F > R w > R ′ w , which is a contradiction because it violates the minimality of t 0 .
The other two cases are similar, so we will prove one of them. If it holds true that The definitions of t 0 and T implies that for any s ∈ [0, t 0 ), λ min (K(s)) ≥ λ0 2 and A(s) − A(0) F ≤ R ′ a . Then, Lemma 5.4 leads to: which is a contradiction. Therefore, we have finish the proof.
Proof of Theorem 5.1. With the results, we can can prove the Theorem. From Lemma 5.
We only need the conditions R ′ w = R ′ a ≤ R w = R a to satisfy for this to work. The conditions are Note that X −U (0) 2 F ≤ 3n/2δ with probability at least 1−δ. Also, using a standard bound on sub-Gaussian matrices, we have W (0) ≤ 2 √ m + √ d and A(0) ≤ 2 √ m + √ d with probability at least 1 − 2 exp(−m).
Then if we have the order of m ≥ Ω ndλ 3 n λ 4 0 δ 2 . Therefore, we finished the proof for the gradient flow Theorem.

Gradient descent
As above, we will now appropriately discretize the gradient flow to obtain a convergence result for gradient descent with finite step size for the jointly-trained regime.
Theorem 5.2. Suppose Assumptions 1 and 2 hold. At initialization, suppose the weights are independently drawn from w r ∼ N (0, I) and a r ∼ Unif({−1, 1} d ) for all r ∈ [m]. If m ≥ C nλ 3 n d λ 4 0 δ 2 for some large enough constrant C, then with probability at least 1 − δ the gradient descent on W with step size η = Θ( λ0 nλn ), We will prove 5.2 by induction. The base case when k = 0 is trivially true. Assume holds for k ′ = 0, 1, . . . , k and we want to show (5.15) for k ′ = k + 1. First, we prove that W (k + 1) − W (0) F and A(k + 1) − A(0) F are small enough, and we then use that to bound X − U (k + 1) 2 F . In this section, we define and assume that First, we show the following auxiliary lemma.
Proof. We prove this by induction. Clearly, both hold when k ′ = 0. Assuming that both hold for k ′ ≤ k. We will prove both hold for k ′ = k + 1.
We use the expression of the gradients over w r and a r in (5.4) and (5.5): Then, the difference of the weight matrix W is: where the third step and fourth step follow from X r (k ′ ) ≤ X = √ λ n and the induction hypothesis Similarly, we bound the difference of the weight matrix A between time k + 1 and 0: where the third step and fourth step follow from the facts that φ( F in terms of the step k. Recall the update rule in (5.2) and (5.3) that where the gradients is given above. Next, we compute the difference of the prediction between two consecutive steps, a discrete version of dui(t) dt . For each i ∈ [n], we have For a particular r, if the activation pattern does not change, we can write the inside term as: where the first part corresponds to kernel G(t) and the second part corresponds to the H(t) shown up in the gradient flow analysis. With this intuition, we split the right hand side into two parts. v 1,i represents the terms that the pattern does not change and v 2,i represents the remaining term that pattern may changes.
In order to analyze v 1 ∈ R n , we provide definition of G, G ⊥ ∈ R nd×nd and H, H ⊥ ∈ R nd×nd , Using the fact that φ(z) = z½[z ≥ 0] and the definition of S i , we expand the forms of the gradients in 5.4 and 5.5 and get: where v 3 will be treated as a perturbation: Then, we can write v 1 as: (5.19) in which K(k) = G(k) + H(k) -the discrete NTK kernel and K ⊥ (k) = H ⊥ (k) + G ⊥ (k). Lastly, we come to the main prediction dynamics in discrete time for vec(U (k + 1) − U (k)) as: Using this equation, we can rewrite X − U (k + 1) 2 2 in terms of X − U (k) as follows: We define and upper bound each of the following terms Notice that C 1 can be upper bounded in terms of λ min (K(k)) ≥ λ min (H(k)), which is ensured as long as the movement in the weight is sufficiently small (shown in Lemma 5.7.) C 2 can be upper bounded also using the kernel with bound on its spectral norm.
Proof of Theorem 5.2. We will prove Theorem 5.2 by induction. The base case when k = 0 is trivially true. Assume that the claim holds for k ′ = 0, 1, . . . , k and we want to show that (5.15) also holds for k ′ = k + 1.
For k ′ = k + 1, we have Now, we invoke the bound for each of these terms from Claims C.4, C.5, C.6, C.7 and C.8 in Appendix C and Lemma5.7. Then, we want to choose η and R w such that If we set η = λ0 64nλn and use X − U (0) F ≤ C √ n, we have the two dominating terms are This implies that Lower bound on m. We require for any δ ∈ (0, 1) that where the first bound on R w comes from the result on gradient descent and the condition in Lemma 5.2, whereas the second bound is required by the above Claims. By Claim 4.1 that X − U (0) F ≤ 2n δ for arbitrary δ ∈ (0, 1), then we require m ≥ C ndλ 3 n λ 4 0 δ 2 for a sufficiently large constant C > 0 so that the claim holds with probability 1 − δ.

Weight-tied Autoencoders
We conclude with the case of training two-layer autoencoders whose weights are shared (i.e., A = W ). This is a common architectural choice in practice, and indeed previous theoretical analysis for autoencoders [Rangamani et al., 2017, Nguyen et al., 2019, Li and Phan-Minh, 2019 have focused on this setting. We will show that somewhat surprisingly, allowing the network to be over-parameterized in this setting leads to certain degeneracies. First, we prove: Lemma 6.1. Let x be any fixed sample. The weight W is randomly initialized such that w r ∼ N (0, σ 2 I) independently for r = 1, 2, . . . , m, then Particularly, when x = 1, σ 2 = 2, then For an arbitrary small ǫ > 0, the expected reconstruction loss is at most ǫ if m ≥ Ω(d/ǫ).
Remark 6.1. This Lemma has a few interesting implications. First, when σ 2 = 2 , then which does not exceed ǫ if m ≥ 3d/ǫ for ǫ > 0. Provided that the data samples are normalized, if m is sufficiently large, even with random initialization the reconstruction loss is very close to zero without any need for training. Therefore, mere over-parameterization already gets us to near-zero loss; the autoencoder mapping 1 m W φ(W ⊤ x) ≈ x for any unit-norm x. It suggests that training of weight-tied autoencoders under high levels of over-parameterization may be degenerated.
Proof. We will use E wr as a shorthand for E wr∼N (0,σ 2 I) . We expand the reconstruction loss: Because φ is ReLU and the distribution of w r is symmetric, we have: since E w [ww ⊤ ] = I. Then, by the independence of the columns in W (more details or split up, one more step), Now, we compute the last term: Due to the normalization x = 1, we can also write 1 σ w = ux + v such that x T v = 0, then u = w, x ∼ N (0, 1) and v ∼ N (0, I − xx T ) are conditionally independent given x. Note that since the conditional distribution of u is unchanged with respect to x, this implies that u is independent of x; as a result, u and v are (unconditionally) independent.
Also, denote α q = E z∼N (0,1) [z q ½(z ≥ 0)] for the exact value . Using Stein's Lemma, we can compute the 2 , which are all positive. Write φ(z) = max(0, z) = ½(z ≥ 0)z, and Changing variables by scaling the variance: Combining with (6.2): The second result directly follows from the Lemma with the specific values of x , σ plugged in.

A Useful Facts
Lemma A.1 (Stein's Lemma). For a random vector w ∈ R d such that w ∼ N (0, I) and function h(w) :

Proof.
A direct application of the Stein's lemma (Lemma A.1). Denote h(w) = ½[ w, x (i) ≥ 0, w, x (j) ≥ 0]w, here k = d. and the derivative of h(w) with respect to w is Then use the Stein's lemma with the independence of those entries in w, we have the result.
This result is borrowed from the proof of [Song and Yang, 2019, Claim 4.10].

B.2 Proof of supporting claims
To prove the bounds in Claims B.1, B.2, B.3, and B.4, we use the bound w r (k + 1) − w r (0) ≤ R ′ for all r ∈ [m] in Lemma 4.5. In what follows, we assume R ′ < R, which is the weight movement allowed to achieve Lemma 4.2. This assumption holds with high probility as long as m is large enough.
). Then we have with probability at least 1 − δ.
Proof. All we need is to bound K(k) ⊥ . A simple upper bound is with probability 1 − n exp(−mR) where the last step follows from Lemma A.4. Then, with that same probability K(k) ⊥ ≤ K(k) ⊥ F ≤ 4ndR, and Claim B.3. Let C 3 = −2vec(X − U (k)) ⊤ v 2 , then with probability at least 1 − n exp(−mR) Proof. We have C 3 ≤ 2 X − U (k) F v 2 . Using the Lipschitz property of φ, we have with probability 1 − n exp(−mR). The sixth step we use ∇ wr L(W (k)) = 1 √ md X r (k)(X − U (k)) ⊤ a r ≤ √ λ n √ m X − U (k) F , and the last step follows from from Lemma A.4 that m r=1 ½[r ∈ S ⊥ i ] ≤ 4mR with probability at least 1 − n exp(−mR). Substitute the bound into C 3 , then we finish the proof.
Claim B.4. Let C 4 = U (k + 1) − U (k) 2 F . Then we have Proof. Previously in Lemma 4.5, we proved that Expand the form of U (k + 1) − U (k) and use the Lipschitz of ReLU to get ≤ n 2 η 2 X − U (k) 2 F . Therefore, we finish the proof.

C.1 Concentration of H(0)
We re-state and prove the concentration of H(0) in Lemma 5.1. φ(X ⊤ w r (0))φ(w r (0) ⊤ X). Let us use w r to mean w r (0) and denote the r th -random matrix as Z r = φ(X ⊤ w r )φ(w ⊤ r X). We use Lemma B.7 of Zhong et al. [2017] and verify the required conditions by the next results.
Proof. We bound this by re-iterating the proof of Claim C.6: with probability at least 1 − 3 exp(−m).