Title: DEMYSTIFYING OVERCOMPLETE NONLINEAR AUTO-ENCODERS: FAST SGD CONVERGENCE TOWARDS SPARSE REPRESENTATION FROM RANDOM INITIALIZA-TION

Abstract: Auto-encoders are commonly used for unsupervised representation learning and for pre-training deeper neural networks. When its activation function is linear and the encoding dimension (width of hidden layer) is smaller than the input dimension, it is well known that auto-encoder is optimized to learn the principal components of the data distribution Oja (1982). However, when the activation is nonlinear and when the width is larger than the input dimension (overcomplete), auto-encoder behaves differently from PCA, and in fact is known to perform well empirically for sparse coding problems. We provide a theoretical explanation for this empirically observed phenomenon, when rectified-linear unit (ReLu) is adopted as the activation function and the hidden-layer width is set to be large. In this case, we show that, with significant probability, initializing the weight matrix of an auto-encoder by sampling from a spherical Gaussian distribution followed by stochastic gradient descent (SGD) training converges towards the ground-truth representation for a class of sparse dictionary learning models. In addition, we can show that, conditioning on convergence, the expected convergence rate is O( 1 t ), where t is the number of updates. Our analysis quantifies how increasing hidden layer width helps the training performance when random initialization is used, and how the norm of network weights influence the speed of SGD convergence.

1. INTRODUCTION:

Let x denote a vector in R d . An auto-encoder can be decomposed into two parts, encoder and decoder. The encoder can be viewed as a composition function s e • a e : R d → R n ; function a e : R d → R n is defined as a e (x) := W e x + b e with W e ∈ R n×d , b e ∈ R n W e and b e are the network weights and bias associated with the encoder. s e is a coordinate-wise activation function defined as s e (y) j := s(y j ) where s : R → R is typically a nonlinear function

The decoder takes the output of encoder and maps it back to R d . Let x e := s e (a e (x)). The decoding function, which we denote as x, is defined as Weight tying A folklore knowledge when training auto-encoders is that, it usually works better if one sets W d = W T e . This trick is called "weight tying", which is viewed as a trick of regularization, since it reduces the total number of free parameters. With tied weights, the classical auto-encoder is simplified as

x(s e (a e (x))) = s d (W T s e (W x + b e ) + b d )

In the rest of the manuscript, we focus on weight-tied auto-encoder with the following specific architecture:

xW,b (x) = W T s ReLu (a(x)) = W T s ReLu (W x + b) with s ReLu (y) i := max{0, y i } (1)

Here we abuse notation to use xW,b to denote the encoder-decoder function parametrized by weights W and bias b. In the deep learning community, s ReLu is commonly referred to as the rectified-linear (ReLu) activation.

Reconstruction error A classic measure of reconstruction error used by auto-encoders is the expected squared loss. Assuming that the data fed to the auto-encoder is i.i.d distributed according to an unknown distribution, i.e., x ∼ p(x), the population expected squared loss is defined as

L(W, b) := 1 2 E x∼p(x) x -xW,b (x) 2 (2)

Learning a "good representation" thus translates to adjusting the parameters (W, b) to minimize the squared loss function. The implicit hope is that the squared loss will provide information about what is a good representation. In other words, we have a certain level of belief that the squared loss characterizes what kind of network parameters are close to the parameters of the latent distribution p(x). This unwarranted belief leads to two natural questions that motivated our theoretical investigation:

• Does the global minimum (or any of global minima, if more than one) of L(W, b) correspond to the latent model parameters of distribution p(x)?

• From an optimization perspective, since L(W, b) is non-convex in W and is shown to have exponentially many local minima Safran & Shamir (2016) , one would expect a local algorithm like stochastic gradient descent, which is the go-to algorithm in practice for optimizing L(W, b), to be stuck in local minima and only find sub-optimal solutions. Then how should we explain the practical observation that auto-encoders trained with SGD often yield good representation?

Stochastic-gradient based training Stochastic gradient descent (SGD) is a scalable variant of gradient descent commonly used in deep learning. At every time step t, the algorithm evaluates a stochastic gradient g(•) of the population loss function with respect to the network parameters using back propagation by sampling one or a mini-batch of data points. The weight and bias update has the following generic form

W t+1 ← W t -η t w g t+1 (W t ), with Eg(W t ) = ∂L(W, b) ∂W (W t ) b t+1 ← b t -η t b g t+1 (b t ) with Eg(b t ) = ∂L(W, b) ∂b (b t )

where η t w and η t b are the learning rates for updating W and b respectively, typically set to be a small number or a decaying function of time t. The unbiased gradient estimate g(W t ) and g(b t ) can be obtained by differentiating the empirical loss function defined on a single or a mini-batch of size m, denoted by m :

EQUATION

Then the stochastic or mini-batch gradient descent update can be written as

EQUATION

Table 1 : Organization of notations: the "parameters" are those whose value determine the performance guarantee of auto-encoders; the "auxiliary" variables are only used to facilitate our analysis. Model Algorithm Analysis parameters auxiliary parameters auxiliary auxiliary k(dictionary size) x c (norm control)

W t δ d (dimension) W * c (learning rate b t τ s,1 , τ s,2 λ (incoherence) C j t o parameters) a t (•) g(•) , σ (noise)

n (width of hidden layer)

Max-norm regularization A common trick called "max-norm regularization" Srivastava et al. (2014) or "weight clipping" is used in training deep neural networks. 1 In particular, after each step of stochastic gradient descent, the updated weights is forced to satisfy

max i W i, 2 ≤ c

for some constant c. This means the row norm of the weights can never exceed the prefixed constant c. In practice, whenever W i, 2 > c, the max-norm constraint is enforced by projecting the weights back to a ball of radius c.

2. PRELIMINARIES:

In this section, we start by defining notations. Then we introduce a norm-controlled variant of SGD algorithm that operates on the auto-encoder architecture formalized in (1). Finally, we introduce assumptions on the data generating model.

General principle of notations:

We use the same notation for network parameters W, b, and for activation a(•), as in Section 1. We use s(•) as a shorthand for the ReLu activation function s ReLu (•).

We use capital letters, such as W or F , either to denote a matrix or an event; we use lower case letters, such as x, for vectors. W T denotes the transpose of W . We use W s, to denote the s-th row of W . When a matrix W is modified through time, we let W t denote the state of the matrix at time t, and W t s, for the state of the corresponding row. We use • for l 2 -norm of vectors and | • | for absolute value of real numbers. Matrix-vector multiplication between W and x (assuming their dimensions match) is denoted by W x. Inner product of vectors x and y is denoted by x, y .

Organization of notations Throughout the manuscript, we introduce notations that can be divided into "model", "algorithm", and "analysis" categories according to their utility. They are organized in Table 1 to help readers interpreting our results. For example, If a reader is interested in knowing how to apply our result to parameter tuning in training auto-encoders, then she might ignore the auxiliary notations and only refer to algorithmic parameters and model parameters in Table 1 , and examine how does the setting of the former is influenced by the latter in Theorem 1.

2.1. NORM-CONTROLLED SGD TRAINING:

We assume that the algorithm has access to i.i.d. samples from an unknown distribution p(x). This means the algorithm can access stochastic gradients of the population squared-loss objective in (2) via random samples from p(x). The norm-controlled SGD variant we analyze is presented in Algorithm 1 (it can be easily extended to the mini-batch SGD version, where for each update we sample more than one data points). It is almost the same as what is commonly used in practice: it random initializes the weight matrix by sampling unit spherical Gaussian, and at every step the algorithm moves towards the direction of the negative stochastic gradient with a linearly decaying learning rate.

However, there are two differences between Algorithm 1 and original SGD: first, we impose that the norm of the rows of W t be controlled; this is akin to the practical trick of "max-norm regularization" as explained in Section 1; second the update of bias is chosen differently than what is usually done in practice, which deserves additional explanation.

Comment on the setting of bias in Algorithm 1:

The stochastic gradient of bias b with respect to squared loss in (2) can be evaluated by sampling a single data point and differentiate against the empirical loss in (3), can be derived as

∂ (W, b; x)

∂b j = -∂s(a j ) ∂a j r, W j (derivation can be found in (6) of the Appendix)

Since the gradient is noisy, the generic form of SGD suggests modifying b t j using the update

b t+1 j ← b t j + η t b ∂s(a j ) ∂a j r, W j

for a small learning rate η t b to mitigate noise. This amounts to stepping towards the negative gradient direction and move a little. On the other hand, we can directly find the next update b t+1 j as the point that sets the gradient to zero, that is, we find b * j such that

∂ (W t , b t ; x ) ∂b (b * j ) = 0

The closed form solution to this is to choose

b * j = x 1 {a t (x )>0} , W t j ( 1 W t j 2 -1)

This strategy, which is essentially Newton's algorithm, should perform better than gradient descent if we have an accurate estimate of the true gradient, so it would likely benefit from evaluating the gradient using a mini-batch of data. If, on the other hand, the gradient is very noisy, then this method will likely not work as well as the original SGD update. Analyzing the evolvement of both W t and b t , which has dependent stochastic dynamic if we follow the original SGD update, would be a daunting task. Thus, to simplify our analysis, we assume in our analysis that we have access to

E x x 1 {a t (x )>0} , W t+1 j ( 1 W t+1 j 2 -1)

The substitute of W t+1 j for W t j is to further simplify our analysis. In practice, this update can be implemented by first updating W t j to W t+1 j , and then updating b t j using W t+1 j .

2.2. A SIMPLE SPARSE DICTIONARY LEARNING MODEL:

We assume that the data x we sample follows the dictionary learning model

x = (W * ) T s + where W * ∈ R k×d .

Here k is the size of the dictionary, which we assume to be at least two (otherwise, the model becomes degenerate), and the true value of k is unknown to the algorithm.

The rows of W * are the dictionary items;

W * j satisfies W * j = 1, ∀j ∈ [k]

Let the incoherence between dictionary items be defined as λ := max j,i =j,i,j∈[k] | W * j , W * i |, we assume that λ ≤ 1 8k . In our simplified model, the coefficient vector s ∈ {0, 1} k is assumed to be 1-sparse, with

P r(s j = 1) = 1 k E = 0 and E[ T ] = σ 2 I with σ 2 ≤ λ 2 √ 2d .

Finally, we assume that the noise has bounded norm2 : max

≤ √ 1-λ 2 6k .

Algorithm 

[n], W o s ← c z z , where z ∈ R d , z i ∼ N (0, 1) Initialization of b o : Sample x ∼ p(x); for all s ∈ [n], Find b * s such that ∂ (x;W o , 0) ∂b (b * s ) = 0 b o s ← b * s (version used in analysis: b o s ← E x x, W o s ( 1 c 2 -1)) while t ≤ t max do W t+1 ← W t -η t ∂ (x,W t ,b t )

∂W:

, where x ∼ p(x)

W t+1 j ← W t+1 j W t+1 j Draw a fresh sample x ∼ p; for all s ∈ [n], Find b * s such that ∂ (x ;W t ,b t ) ∂b (b * s ) = 0 b t+1 s ← b * s , or equivalently, b t+1 s ← x 1 {a t (x )>0} , W t+1 s ( 1 c 2 -1) ( version used in analysis b t+1 s ← E x x 1 {a t (x )>0} , W t+1 s ( 1 c 2 -1) ) end while Output: W tmax , b tmax

While auto-encoders are often related to PCA, the latter cannot reveal any information about the true dictionary under this model even in the complete case, where d = k, due to the isotropic property of the underlying distribution.

The data generating model can be equivalently viewed as a mixture model: for example, when s j = 1, it means x is of the form W * j + . When is Gaussian, the model coincides with mixture of Gaussians model, with the dictionary items being the latent locations of individual Gaussians. Thus, we adopt the concept from mixture models, and use x ∼ C j to indicate that x is generated from the j-th component of the distribution.

3. MAIN RESULTS:

To formally study the convergence property of Algorithm 1, we need a measure to gauge the distance between the learned representation at time t, W t , and the ground-truth representation, W * , which may have different number of rows. There are potentially different ways to go about this. The distance measure we use is

Θ(W t , W * ) := 1 k j∈[k] min s∈[n] ∆(W t s , W * j ) with ∆(W t s , W * j ) := 1 -( W t s W t s , W * j ) 2

Note that ∆(W t s , W * j ) is the squared sine of the angle between the two vectors, which decreases monotonically as their angle decreases, and equals zero if and only if the vectors align. Thus, min s∈[n] ∆(W t s , W * j ) can be viewed as the angular distance from the best approximation in the learned hidden representations of the network, to the ground-truth dictionary item W * j . And Θ(•, •) measures this distance averaged over all dictionary items.

Our main result provides recovery and speed guarantee of Algorithm 1 under our data model. Theorem 1. Suppose we have access to i.i.d. samples x ∼ p(x), where the distribution p(x) satisfies our model assumption in Section 2.2. Fix any δ ∈ (0, n e ). If we train auto-encoder with norm-controlled SGD as described in Algorithm 1, with the following parameter setting

• The row norm of weights set to be W

t s = c (∀s ∈ [n], ∀t) such that 3 2 ≤ c ≤ √ 6k • If the bias update at t is chosen such that b t+1 s = E x x 1 {a t (x )>0} , W t+1 s ( 1 c 2 -1)

• The learning rate of SGD is set to be η t := c t+to , with c > 2kc and

t o ≥ 192(c ) 2 B 2 λ 2 (ln n δ ) 2

Then Algorithm 1 has the following guarantees

• When random initialization with i.i.d. samples from N (0, 1) is used, the algorithm will be initialized successfully (see definition of successful initialization in Definition 1) with probability at least

1 -k exp{-n( λ √ 2 ) d-3 }.

• When random initialization with i.i.d. samples x ∼ p(x) is used, the algorithm will be initialized successfully with probability at least

(1 -k exp{- nλ 2 8kB })(1 -3 exp{- n 3 100k 2 })

• Conditioning on successful initialization, let Ω denote the sample space of all realizations of the algorithm's stochastic output, (W 1 , W 2 , . . . , ). Then at any time t, there exists a large subset of the sample space,

F t ⊂ Ω, with P r(F t ) ≥ 1 -δ, such that E[Θ(W t , W * )|F t ] ≤ ( t o + 1 t o + t + 1 ) 4 λ 2 2 + (c ) 2 B 3 (1 + 1 t o + 1 ) 2c kc +1 1 t o + t + 1

Interpretation The first statement of the theorem suggests that the probability of successful initialization increases as the width of hidden layer increases. In particular, when Gaussian initialization is used, in order to ensure a significantly large probability of successful initialization, the analysis suggests that the number of neurons required must scale as Ω(λ -d ) = Ω(k d ), which is exponential in the ambient dimension. When the neurons are initialized with samples from the unknown distribution, the analysis suggests that the number of neurons required scale as Ω( k λ 2 ) = Ω(k 3 ), which is polynomial in the number of dictionary size. Hence, our analysis suggests that, at least under our specific model, initializing with data is perhaps a better option than Gaussian initialization. The second statement suggests that conditioning on a successful initialization, the algorithm will have expected convergence towards W * , measured by Θ(•, •), of order O( 1 t ). If we examine of form of bound on the convergence rate, we see that the rate will be dominated by the second term, whose constant is heavily influenced by the choice of learning rate parameter c .

Explaining distributed sparse representation via gradient-based training:

The main advantage of gradient-based training of auto-encoders, as revealed by our analysis, is that it simultaneously updates all its neurons in parallel, in an independent fashion. During training, a subset of neurons will specialize at learning a single dictionary item: some of them will be successful while others may fail to converge to a ground-truth representation. However, since the update of each neuron is independent (in an algorithmic sense), when larger number of neurons are used (widening the hidden layer), it becomes more likely that each ground-truth dictionary will be learned by some neuron, even from random initialization.

4. RELATED WORKS:

Despite the simplicity of auto-encoders in comparison to other deep architectures, we still have a very limited theoretical understanding of them. For linear auto-encoders whose width n is less than than its input dimension d, the seminal work of Oja (1982) revealed their connection to online stochastic PCA. For non-linear auto-encoders, recent work Arpit et al. (2016) analyzed sufficient conditions on the activation functions and the regularization term (which is added to the loss function) under which the auto-encoder learns a sparse representation. Another work Rangamani et al. (2017) showed that under a class of sparse dictionary learning model (which is more general than ours) the ground-truth dictionary is a critical point (that is, either a saddle point or a local miminum) of the squared loss function, when ReLu activation is used. We are not aware of previous work providing global convergence guarantee of SGD for non-linear auto-encoders, but our analysis techniques are closely related to recent works Balsubramani et al. (2013) ; Ge et al. (2015) ; Tang & Monteleoni (2017) that are at the intersection of stochastic (non-convex) optimization and unsupervised learning.

PCA, k-means, and sparse coding The work of Balsubramani et al. (2013) provided the first convergence rate analysis of Oja's and Krasulina's update rule for online learning the principal component (stochastic 1-PCA) of a data distribution. The neural network corresponding to 1-PCA has a single node in the hidden layer without activation function. We argue that a ReLu activated width n auto-encoder can be viewed as a generalized, multi-modal version of 1-PCA. This is supported by our analysis: the expected improvement of each neuron, W t s , bears a striking similarity to that obtained in Balsubramani et al. (2013) . The training of auto-encoders also has a similar flavor to online/stochastic k-means algorithm Tang & Monteleoni (2017): we may view each neuron as trying to learn a hidden dictionary item, or cluster center in k-means terminology. However, there is a key difference between k-means and auto-encoders: the performance of k-means is highly sensitive to the number of clusters. If we specify the number of clusters, which corresponds to the network width n in our notation, to be larger than the true k, then running n-means will over-partition data from each component, and each learned center will not converge to the true component center (because they converge to the mean of the sub-component). For auto-encoders, however, even when n is much larger than k, the individual neurons can still converge to the true cluster center (dictionary item) thanks to the independent update of neurons. SGD training of auto-encoders is perhaps closest to a family of sparse coding algorithms Schnass (2015) ; Arora et al. (2015) . For the latter, however, a critical hyper-parameter to tune is the threshold at which the algorithm decides to cut off insignificant signals. Existing guarantees for sparse coding algorithms therefore depend on knowing this threshold. For ReLu activated auto-encoders, the threshold is adaptively set for each neuron s at every iteration as -b t s via gradient descent. Thus, they can be viewed as a sparse coding algorithm that self-tunes its threshold parameter.

5. ANALYSIS:

In our analysis, we define an auxiliary variable

φ(W t s , W * j ) := 1 -∆(W t s , W * j )

Note that φ(•, •) is the squared cosine of the angle between W t s and W * j , which increases as their angle decreases. Thus, φ can be thought as as measuring the angular "closeness" between two vectors; it is always bounded between zero and one and equals one if and only if the two vectors align.

Our analysis can be divided into three steps. We first define what kind of initialization enables SGD to converge quickly to the correct solution, and show that when the number of nodes in the hidden layer is large, random initialization will satisfy this sufficient condition. Then we derive expected the per-iteration improvement of SGD, conditioning on the algorithm's iterates staying in a local neighborhood (Definition 4). Finally, we use martingale analysis to show that the local neighborhood condition will be satisfied with high probability. Piecing these elements together will lead us to the proof of Theorem 1, which is in the Appendix.

5.1. PART I: PERFORMANCE GUARANTEE OF INITIALIZATION:

Covering guarantee from random initialization Intuitively, for each ground-truth dictionary item, we only require that at least one neuron is initialized to be not too far from it. Definition 1. If the rows of W o have fixed norm c > 0. Then we define the event of successful initialization as

F o * := min j∈[k] max i∈[n] W o i , W * j ≥ c 1 - λ 2 2 Lemma 1 (Random initialization with Gaussian variables). Suppose W o ∈ R n×d is constructed by drawing z i,j ∼ N (0, 1) for all i ∈ [n], j ∈ [d],

and setting W o i, = c zi zi . Then

P r{F o * } ≥ 1 -k exp{-n( λ √ 2 ) d-3 }

Lemma 2 (Random initialization with data points). Suppose W o ∈ R n×d is constructed by drawing X 1 , . . . , X n from the data distribution p(x), and setting

W o i,j = c Xi Xi , for all i ∈ [n]. If σ 2 ≤ λ W o 1 W o 2 W o 3 W o 4 W o 5 g 0 W * 1 W * 2 Figure 1:

The auto-encoder in this example has 5 neurons in the hidden layer and the dictionary has two items; in this case, g(1) = g(3) = 1, g(5) = 2, and the other two neurons do not learn any ground-truth (neurons mapped to 0 are considered useless). Under unique firing condition, which holds when the dictionary is sufficiently incoherent, the red dashed connection will not take place (each neuron is learning at most one dictionary item).

then

P r{F o * } ≥ (1 -k exp{- nλ 2 8kB })(1 -3 exp{- n 3 100k 2 }) Definition 2. Conditioning on F o , we can map the rows of W o to an dictionary item W * j , j ∈ [k], according to the following firing map 3 g : [n] → {0, 1, . . . , k} s.t. g(s) = j if W o s , W * j ≥ c √ 1 -λ 2 g(s) = 0 otherwise

Figure 1 provides an illustration of firing map g(•). Note that some rows in W o may not be mapped to any dictionary item, in which case we let g(s) = 0. This means such neurons are not close (in angular distance) to any ground-truth after random initialization. Also note that for some rows W o s , there might exist multiple j ∈ [k] such that g(s) = j according to our criterion in the definition. But when λ ≤ 1 2 , which is always the case by our model assumption on incoherence, Lemma 3 shows that the assignment must be unique, in which case the mapping is well defined. Lemma 3 (Uniqueness of firing). Suppose during training, the weight matrix has a fixed norm c. At time t, for any row of weight matrix W t s , we denote by τ s,1 := max j W t s c , W * j , and we denote by

τ s,2 := max j∈[k],j =1 | W t s c , W * j |. Then for any λ ≤ 1 2 , τ s,1 ≥ √ 1 -λ 2 =⇒ {τ s,2 < τ s,1 }.

Thus, for any s ∈ [n] with g(s) > 0, the uniqueness of firing condition holds and the mapping g is defined unambiguously. So we simplify notations on measure of distance and closeness as

∆ t s := ∆(W t s , W * g(s) ) φ t s := φ(W t s , W * g(s) )

5.2. PART II: THE EVOLVEMENT OF WEIGHTS AND BIAS DURING SGD TRAINING:

This section lower bounds the expected increase of φ t s after each SGD update, conditioning on F t . We first show that conditioning on F t , the firing of a neuron s with g(s) = j, will indicate that the data indeed comes from the j-th component, which is characterized by event E t . Definition 3. At step t, we denote the event of correct firing of W t as

E t := {∀0 ≤ i ≤ t, ∀s s.t. x ∼ C g(s) , W i s , x + b i s > 0} ∩{∀0 ≤ i ≤ t, ∀s s.t. g(s) > 0 and x ∼ C j , j = g(s), W i s , x + b i s < 0}

Definition 4. At step t, we denote the event of satisfying local condition of W t as

F t := {∀0 ≤ i ≤ t, ∀s ∈ [n] s.t. g(s) > 0, W i s , W * g(s) ≥ c 1 -λ 2 } Lemma 4 (Correctness of firing). If at t ≥ 0, if ∀j ∈ [k], the network parameters (W t s , b t s ) is chosen that satisfies b t s = E x1 {a t-1 s >0} , W t s ( 1 W t s 2 -1) with W t s = c s.t. such that 3 2 ≤ c ≤ √ 6k. Then for any t > 0, F t =⇒ E t .

Then we proceed to characterize the expected change of φ t s , conditioning on E t . Theorem 2. Suppose E t holds, then after one step of stochastic gradient descent update on W t , W t+1 satisfies version 1

E[φ t+1 s |E t ] ≥ φ t s {1 + 2η t k W t s (1 -φ t s )} -(η t ) 2 B

version 2

φ t+1 s ≥ φ t s {1 + 2η t k W t s (1 -φ t s )} -η t Z -(η t ) 2 B with E[Z|E t ] = 0 and |Z| ≤ B

for some constant B > 0 where B is a constant depending on the model parameter and the norm of rows of weight matrix.

5.3. PART III: CONVERGENCE OF MARTINGALES:

By Theorem 2, the sequence φ o s , φ 1 s , . . . , φ t s , . . . is a sub-martingale. One caveat of is that the expected increase of the cosine of angle between W t s and W * g(s) is conditional on E t , the correct firing condition. So showing that the correct firing event indeed holds is crucial to our overall convergence analysis. Since by Lemma 4, F t =⇒ E t , it suffices to show that F t holds. To this end, note that F t 's form a nested sequence

F o ⊃ F 1 ⊃ . . . F t ⊃ . . .

We denote the limit of this sequence as Theorem 3. Fix any δ ∈ (0, n e ). Suppose we choose η t = c t+to such that c > 2kc

F ∞ := lim t→∞ F t So F ∞ is the event that { W t s , W * j ≥ c(1 -δ o ), ∀t ≥ 0, ∀j ∈ [k]∀s ∈ [n] s.t. g(s) = j}

t o ≥ 192(c ) 2 B 2 (ln n δ ) 2 (1 + 1 (α -λ) 2 ) 2 Then conditioning on F o , we have P r(F ∞ ) = 1 -δ 6 OPEN PROBLEMS

There are several interesting questions that are not addressed here. First, as noted in our discussion in Section 2, the update of bias as analyzed in our algorithm is not exactly what is used in original SGD.

It would be interesting (and difficult) to explore whether the algorithm has fast convergence when b t is updated by SGD with a decaying learning rate. Second, our model assumption is rather strong, and it would be interesting to see whether similar results hold on a relaxed model, for example, where one may relax to 1-sparse constraint to m-sparse, or one may relax the finite bound requirement on the noise structure. Third, our performance guarantee of random initialization depends on a lower bound on the surface area of spherical caps. Improving this bound can improve the tightness of our initialization guarantee. Finally, it would be very interesting to examine whether similar result holds for activation functions other than ReLu, such as sigmoid function.

Nathan Srebro and Adi Shraibman. 

7. APPENDIX:

Derivation of stochastic gradients Upon receiving a data point x, the stochastic gradient with respect to W is a jacobian matrix whose (j * , i * )-th entry reads

∂ (W, b; x) ∂w j * i * = ∂ ∂w j * i * d i=1 1 2 [x i - n j=1 w ji s( d l=1 w jl x l + b j )] 2 = d i=1 {x i - n j=1 w ji s( d l=1 w jl x l + b j )}{- ∂ ∂w j * i * n j=1 w ji s( d l=1 w jl x l + b j )} = - d i=1 {x i - n j=1 w ji s( d l=1 w jl x l + b j )} ∂ ∂w j * i * w j * i s( d l=1 w j * l x l + b j * )

For i = i * , the derivative of the second term can be written using the chain rule as

w j * i ∂ ∂w j * i * s( d l=1 w j * l x l + b j * ) = w j * i ∂s(a j * ) ∂a j * x i *

where we let a j * := w j * l x l + b j * , which is the activation of the j * -th neuron upon receiving x in the hidden layer before going through the ReLu unit.

For i = i * , the derivative of the second term can be written using product rule and chain rule as

w j * i * ∂ ∂w j * i * s( d l=1 w j * l x l + b j * ) + s( d l=1 w j * l x l + b j * ) = w j * i * ∂s(a j * ) ∂a j * x i * + s(a j * ) Let r ∈ R d be the residual vector with r i := x i - n j=1 w ji s( d l=1 w jl x l + b j ). Then we have ∂ (W, b; x) ∂w j * i * = -{ d i=1 r i w j * i ∂s(a j * ) ∂a j * x i * + s(a j * )r i * }

In vector notation, the stochastic gradient of loss with respect to the j-th row of W can be written as

EQUATION

Similarly, we can obtain the stochastic gradient with respect to the j-th entry of the bias term as

EQUATION

Now let us examine the terms ∂s(aj ) ∂aj and r, W j . By property of ReLu function, ∂s(a j )

∂a j = 0 if a j <= 0 1 if a j > 0

Mathematically speaking, the derivative of ReLu at zero does not exist. Here we follow the convention used in practice by setting the derivative of ReLu at zero to be 0. In effect, the event {a j = 0} has zero probability, so what derivative to use at zero does not affect our analysis (as long as the derivative is finite).

Proof of main theorem. Consider any time t > 0. By Lemma 1 and 2, the probability of successfully initializing the network can be lower bounded by

P r(F o * ) ≥ 1 -k exp{-n( λ √ 2 ) d-3 } if the network is initialized with Gaussian variables or P r(F o * ) ≥ (1 -k exp{- nλ 2 8kB 2 })(1 -3 exp{- n 3 100k 2 }) if initialized with data Conditioning on F o

* and applying Theorem 3, we get that for all t ≥ 0, P r(F t ) ≥ P r(F ∞ ) ≥ 1 -δ Since F t =⇒ E t by Lemma 4, we can apply version 1 of Theorem 2 to get the expected increase in φ t s for any s such that g(s) > 0 as:

E[φ t s |F t-1 ] ≥ φ t-1 s {1 + 2η t-1 k W t-1 s (1 -φ t-1 s )} -(η t-1 ) 2 B Since by F o , ∀j ∈ [k],

there exists s ∈ [n] such that g(s) = j. Let s(j) be any s ∈ [n] such that g(s) = j. Then, the inequality above translates to

E[∆ t s(j) |F t-1 ] ≤ ∆ t-1 s(j) - 2η t-1 k W t s(j) ∆ t-1 s(j) (1 -∆ t-1 s(j) ) + (η t-1 ) 2 B = ∆ t-1 s(j) (1 - β t-1 t o + t -1 ) + (c ) 2 (t o + t -1) 2 B where 2 ≤ β t = 2c (1 -∆ t s(j) ) k W s(j) = 2c (1 -∆ t s(j) ) kc ≤ 2c kc

by our choice of c and by our assumption on the initial value ∆ o s(j) . Taking total expectation up to time t, conditioning on F t , and letting β denote a lower bound on β t , we get

E[∆ t s(j) |F t ] ≤ E[∆ t-1 s(j) |F t ](1 - β t-1 t o + t -1 ) + (c ) 2 (t o + t -1) 2 B ≤ E[∆ t-1 s(j) |F t-1 ](1 - β t o + t -1 ) + (c ) 2 (t o + t -1) 2 B

where the last inequality is by the same argument as that in Lemma 8. This has the exact same form as in Lemma D.1 of Balsubramani et al. (2013) . Applying it with u t := E[∆ t s(j) |F t ], a = β, and b = (c ) 2 B (note our t + t o matches their notion of t), we get

E[∆ t s(j) |F t ] ≤ ( t o + 1 t o + t + 1 ) β ∆ o s(j) + (c ) 2 B β -1 (1 + 1 t o + 1 ) β+1 1 t o + t + 1

By the upper bound on β t , we can choose β as small as 2c kc . So we can get an upper expressed in algorithmic and model parameters as

E[∆ t s(j) |F t ] ≤ ( t o + 1 t o + t + 1 ) 2c kc ∆ o s(j) + (c ) 2 B 2c kc -1 (1 + 1 t o + 1 ) 2c kc +1 1 t o + t + 1 ≤ ( t o + 1 t o + t + 1 ) 2c kc λ 2 2 + (c ) 2 B 2c kc -1 (1 + 1 t o + 1 ) 2c kc +1 1 t o + t + 1

The second inequality holds because by F o ,

∆ o s(j) = 1 -φ o s(j) ≤ 1 -(1 - λ 2 2 ) = λ 2 2

Finally,

E[Θ(W t , W * )|F t ] = 1 k j∈[k] E min s∈[n],g(s)=j ∆(W t s , W * j ) ≤ 1 k j∈[k]

E∆(W t s(j) , W * j )

≤ ( t o + 1 t o + t + 1 ) 2c kc λ 2 2 + (c ) 2 B 2c kc -1 (1 + 1 t o + 1 ) 2c kc +1 1 t o + t + 1 ≤ ( t o + 1 t o + t + 1 ) 4 λ 2 2 + (c ) 2 B 3 (1 + 1 t o + 1 ) 2c kc +1 1 t o + t + 1

where the last inequality is by our requirement that c > 2kc.

Proof of Lemma 1. Let u = z z , where z ∈ R d with z i ∼ N (0, 1). We know that u is a random vector on S d-1 , the d-dimensional unit sphere. For any fixed vector v ∈ S d-1 , we have

P r( u, v ≥ 1 -h) = P r(u ∈ S cap (v, h))

where S cap (v, h) is the surface of the spherical cap centered at v with height h. By property of spherical Gaussian, we know that u is uniformly distributed on S d-1 . So we can directly calculate the probability above as

P r(u ∈ S cap (v, h)) = µ(S cap (v, h)) µ(S d-1 )

where µ measures the area of surface. The latter ratio can be lower bounded (see Lemma 5 in the Appendix) as a function of d and h:

µ(S cap (v, h)) µ(S d-1 ) ≥ f (d, h) = ( h(2 -h)) d-1 2d h

Since for all row i ∈ [n], their entries are W o i = c z z , then for any ground-truth dictionary item W * j , j ∈ [k], we have

P r{max i∈[n] W o i , v ≥ c(1 -h)} = P r{∃i ∈ [n], s.t. W o i , v ≥ c(1 -h)} = 1 -P r{∀i ∈ [n], W o i , v < c(1 -h)} = 1 -Π n i=1 P r{ cu, v < c(1 -h)} = 1 -Π n i=1 P r{ u, v < 1 -h} ≥ 1 -Π n i=1 (1 -f (d, h)) ≥ 1 -exp -nf (d,h

) By union bound, this implies that

P r{∀j ∈ [k], max i∈[n] W o i , W * j ≥ c(1 -h)} ≥ 1 -k exp -nf (d,h)

Now by our choice of the form of lower bound on the inner product, we have

h = 1 -1 -ρ

substituting this into the function f (d, h), we get a nice form

( √ ρ) d-1 1 - √ 1 -ρ = ( √ ρ) d-1 1 -(1 -ρ) (1 + 1 -ρ) = ( √ ρ) d-3 (1 + 1 -ρ) ≥ ( √ ρ) d-3

Substituting this into the previous inequality written in terms of h and letting ρ = λ 2 2 completes the proof. For with a fixed norm, the picture illustrates one of the configurations where the maximal angle (θ) between data point X i (in red) and W * j is achieved.

Lemma 5 (Lower bound on surface area of spherical cap). Let S d-1 denote the d-dimensional hypersphere, and let S cap (ν, h) ⊂ S d-1 denote the surface of a hyper spherical cap centered at ν with height h. Let µ(•) denote measure of area of surface in d-dimensional Euclidean space. Let

f (h, d) := ( √ 2h -h 2 ) d-1 h 2d , then µ(S cap (ν, h)) µ(S d-1 ) ≥ f (h, d)

Proof. Let B d denote the d-dimensional unit ball in Euclidean space, and let B cap (ν, h) denote the spherical cap centered at ν with height h. Then applying Lemma 4.1 of Micciancio & Voulgaris (2010) , we get

V ol(B cap )(ν, h) V ol(B d ) > 2h -h 2 d-1 h 2d

where V ol(•) denotes measure of volume in R d . So this lower bounds the ratio between volumes between spherical cap and the unit ball. We show that we can use this to lower bound the ratio between surface areas between spherical cap and the unit ball. Since by ?, we know that the ratio between their area can be expressed exactly as

µ(S cap (ν, h)) µ(S d-1 ) = 1 2 I 2h-h 2 ( d -1 2 , 1 2 )

and the ratio between their volume

EQUATION

)

where I x (a, b) is the regularized incomplete beta function. By property of I x (a, b),

I x (a + 1, b) < I x (a, b) So we have µ(S cap (ν, h)) µ(S d-1 ) > µ(B cap )(ν, h) µ(B d ) > 2h -h 2 d-1 h 2d

Proof of Lemma 2. For any X i ∼ C j , for any j ∈ [k]. We first claim that

{ i 2 ≤ λ √ 2 } =⇒ { X i X i , W * j ≥ 1 - λ 2 2 } Proof of claim.

Let us consider the two-dimensional plane H determined by X i and W * j . Clearly, i = W * j -X i also lies in H. Let θ := ∠(X i , W * j ) denote the angle between X i and W * j . Note that cos θ = Xi Xi , W * j . Fix the norm of noise i . It is clear from elementary geometric insight that θ is maximized (and hence cos θ is minimized) when the line of X i is tangent to the ball centered at W * j with radius i . We can directly calculate the value of cos θ at this point (see Figure 2 ) as cos θ = 1i 2 , which finishes the proof of claim.

Now, we denote two events:

A := {min

j∈[k] i∈[n] 1 {Xi∈Cj } ≥ n 2k } and B := {max j∈[k] i∈[n] i 2 1 {Xi∈Cj } i∈[n] 1 {Xi∈Cj } ≤ λ √ 2 }

The probability of event A can be lower bounded by concentration inequality for multinomial distribution Devroye (1983) : Let n j := i∈[n] 1 {Xi∈Cj } . We get

Pr(¬A) = Pr(∃j ∈ [k], n j - n k ≤ - n 2k ) ≤ Pr( k j=1 |n j - n k | ≥ n 2k ) ≤ 3 exp{-n/25( n 2k ) 2 } = 3 exp{- n 3 100k 2 }

where the second inequality is by Lemma 3 of Devroye (1983) .

Pr(B|A) ≥ 1 -k Pr( 2 ≥ λ √ 2 )

where 2 is the empirical mean of i 2 for all X i , i ∈ [n] belonging to the same component C j for some j ∈ [k]. Conditioning on A, we know that the average is taken over at least n 2k samples for each component C j . By one-sided Hoeffding's inequality,

Pr( 2 ≥ λ √ 2 ) ≤ Pr( 2 ≥ E 2 + λ 2 √ 2 ) ≤ exp{- 2(n/2k)( λ 2 √ 2 ) 2 B } = exp{- nλ 2 8kB }

(note, we abuse notation B in the exponent as an upper bound on 2 , as in other parts of the analysis). Thus,

Pr{F o * } = Pr{min j∈[k] max i∈[n] X i X i , W * j ≥ 1 - λ 2 2 } ≥ Pr{max j∈[k] min i∈[n] i 2 ≤ λ √ 2 } ≥ Pr B ≥ Pr(B ∩ A) = Pr(B|A) Pr(A) ≥ (1 -k exp{- nλ 2 8kB })(1 -3 exp{- n 3 100k 2 })

Proof of Lemma 3. To simplify notation, we use τ 1 (τ 2 ) as a shorthand for τ s,1 (τ s,2 ). Let

j = arg max i∈[k] W t s , W * i . Then W t s , W * j = cτ 1 . If W t s and W * j align, then | W t s , W * j | = c| W * j , W * j | ≤ cλ ≤ cτ s,1

where the second inequality is by relation of λ and τ s,1 . If W t s and W * j do not align, then they determine a two-dimensional plane H. Let i ∈ [k] and i = j. We can decompose the unit vector W * i as

W * i = proj H (W * i ) + orth H (W * i ) θ W * j O W t s W t s proj H (W * i ) proj H (W * i ) λ proj H (W * i ) τ s,1

Figure 3 : The unit circle lies in H. The picture illustrates one of the possible configurations where the minimal angle (θ) between proj H (W * i ) and W t s is achieved.

where proj H (W * i ) is the orthogonal projection of W * i onto H. First, note that by orthogonality,

| proj H (W * i ), W * j | ≤ λ Since proj H (W * i ), W t s

, and W * j lie on the same plane, we can easily see via geometric insight (see Figure 3 ) that,

proj H (W * i ) proj H (W * i ) , W t s W t s ≤ λ proj H (W * i ) τ 1 + 1 - λ 2 proj H (W * i ) 2 1 -τ 2 1 Therefore, | W * i , W t s | ≤ c(λτ 1 + proj H (W * i ) 2 -λ 2 1 -τ 2 1 ) ≤ c(λτ 1 + 1 -λ 2 1 -τ 2 1 )c2λτ 1 Suppose τ 2 1 ≥ 1+λ 2 .

It can be verified that this implies

cτ 2 = | W * i , W t s | ≤ c 1 + λ 2 = cτ 1

Observing that τ 2 1 ≥ 1+λ 2 indeed holds provided λ ≤ 1 2 and τ 1 ≥ √ 1 -λ 2 completes the proof.

Proof of Lemma 4. Conditioning on F t , we show that E t holds by induction on 0 ≤ i ≤ t. We start by showing that E o holds.

Base case In this case:

b o s = E x, W o s ( 1 c 2 -1) Note that by our model assumption, E x, W o s = i∈[k] 1 k W o s , W * i

Since F o holds, we know that the firing of neuron s is unique. Let τ s,1 and τ s,2 as defined in Lemma 3.

Let x ∼ C j . Consider the case g(s) = j. In this case, Lemma 3 implies that

τ s,1 := max j W o s , W * j = W o s , W * j

We will repeatedly use the following relation, as proven by Lemma 6,

τ s,2 := max i =j | W o s , W * i |

We have

W o s x + b o s = (W o s ) T (W * j + ) + ( 1 c 2 -1) i∈[k] 1 k W o s , W * i Now, observe that 1 c 2 -1 < 0 and i∈[k] 1 k W o s , W * i ≤ c 1 k τ s,1 + c k -1 k τ s,2

So we get,

W o s x + b o s ≥ cτ s,1 -c + ( 1 c 2 -1)(c 1 k τ s,1 + c k -1 k τ s,2 ) ≥ cτ s,1 -c + ( 1 c 2 -1)(c 1 k τ s,1 + c k -1 k c2λτ s,1 ) = c{τ s,1 {1 -(1 - 1 c 2 )( 1 k + 2λ)} - } Since by our assumption, λ ≤ 1 8k , (1 -1 c 2 )( 1 k + 2λ) ≤ (1 -1 c 2 ) 5 4k ≤ 5 4k . Furthermore, since by our assumption, ≤ √ 1-λ 2 6k ≤ √ 1 -λ 2 (1 -5 4k ) ≤ (1 -5 4k )τ 1 we get W o s x + b o s ≥ 0. Consider the case g(s) = j , j = j. We first upper bound b o in this case. Since 1 c 2 -1 < 0, we would like to lower bound E x, W o s = i∈[k] 1 k W o s , W * i = 1 k    W o s , W * j + i =j W o s , W * i    ≥ 1 k    W o s , W * j -| i =j W o s , W * i |    ≥ 1 k cτ s,1 - k -1 k cτ s,2 ≥ 1 k cτ s,1 -c2λτ s,1

On the other hand,

W o s x ≤ | W o s , W * j + | ≤ c(τ s,2 + ) So W o s x + b o s ≤ c(τ s,2 + ) -(1 - 1 c 2 )cτ s,1 ( 1 k -2λ) ≤ c(2λτ s,1 + ) -(1 - 1 c 2 )cτ s,1 ( 1 k -2λ) ≤ 0

where the last inequality is by assumptions c > 3 2 and

≤ √ 1-λ 2 6k .

Case 0 < i ≤ t Suppose E i holds, we show that E i+1 holds for i ≤ t -1. Let x ∼ C j for any j ∈ [k] . Since E i holds, we know that ∀s s.t. g(s) > 0, a i s > 0 iff g(s) = j So for neurons W i+1 s with g(s) > 0 and g(s) = j, we know that these neurons are not updated, that is,

W i+1 s = W i s and b i+1 s = b i s

This means the two conditions in E i+1 on neurons g(s) = j = j.

For neurons W i+1

where the last inequality is by assumption

τ 2 s,1 ≥ 1 -λ 2 . It follows that (W i+1 s ) T x + b i+1 s > 0

holds by our assumptions that c ≤ √ 6k, and that ≤ √ 1-λ 2 6k . Finally, consider the case x ∼ C j for j = j, j ∈ [k]. Again, since F i+1 holds,

τ s,1 = (W i+1 s ) T W * j ≥ c 1 -λ 2

we can apply Lemma 3 to get

(W i+1 s ) T x + b i+1 s ≤ cτ s,2 + T W i+1 s + (W i+1 s ) T W * j ( 1 c 2 -1) ≤ cτ s,2 + c + cτ s,1 ( 1 c 2 -1) ≤ 0

where the last inequality holds similarly as in the base case.

Lemma 6. Let τ s,1 , τ s,2 be as defined in Lemma 3, and let λ be the incoherence parameter. If

τ 2 s,1 ≥ 1 -λ 2 , then τ s,2 ≤ cλτ s,1 .

Proof. Using the same argument as the proof of Lemma 3, we get

| W * i , W t s | ≤ c(λτ 1 + proj H (W * i ) 2 -λ 2 1 -τ 2 1 ) ≤ c(λτ 1 + 1 -λ 2 1 -τ 2 1 ) ≤ c2λτ 1

where the last inequality is by the relation between τ 1 and λ.

Proof of Theorem 2. We start by proving version 1. The proof of version 2 follows directly. Let x ∼ C j for any j ∈ [k]. We consider and any neuron s s.t. g(s) = j. Again, since E t holds, a t s > 0|x ∼ C j , g(s) = j We now examine E[φ t+1 s |x ∼ C j , g(s) = j, E t ]. To ease notation, we let w := W t s , w * := W * j , η := η t w , r := r t , a := a t s , and b := b t s in the proof.

φ t+1 s = ( W t+1 j , w * ) 2 W t+1 j 2 = ((w + η[ r, w x + ar]) T w * ) 2 w + η[ r, w x + ar] 2

The denominator reads

w 2 + 2η[(r T w)(x T w) + a(r T w)] + η 2 [(r t w) 2 x 2 + 2a(r T w)(x T r) + a 2 r 2 ] = w 2 (1 + 1 w 2 2η[(r T w)(x T w) + a(r T w)] + 1 w 2 η 2 [(r T w) 2 x 2 + 2a(r T w)(x T r) + a 2 r 2 ])

Let A(w) := (r T w)(x T w) + a(r T w) and B(w

) := (r T w) 2 x 2 + 2a(r T w)(x T r) + a 2 r 2 . 1 w + η[ r, w x + ar] 2 = 1 w 2 (1 + 1 w 2 2ηA(w) + 1 w 2 η 2 B(w)) = 1 -( 1 w 2 2ηA(w) + 1 w 2 η 2 B(w)) w 2 {1 -( 1 w 2 2ηA(w) + 1 w 2 η 2 B(w)) 2 } ≥ 1 -( 1 w 2 2ηA(w) + 1 w 2 η 2 B(w)) w 2

Let C(w * ) := (r T w)(x T w * ) + a(r T w * ). The numerator reads

(w T w * + η[(r T w)(x T w * ) + a(r T w * )]) 2 = (w T w * ) 2 + 2η(w T w * )C(w * ) + η 2 C(w * ) 2

Putting these together,

φ t+1 j ≥ 1 w 2 {(w T w * ) 2 + 2η(w T w * )C(w * ) + η 2 C(w * ) 2 }{1 -( 1 w 2 2ηA(w) + 1 w 2 η 2 B(w))} = 1 w 2 {(w T w * ) 2 + 2η(w T w * )C(w * ) - 1 w 2 2ηA(w)(w T w * ) 2 } (7) + 1 w 2 {η 2 C(w * ) 2 -4η 2 A(w)C(w * )(w T w * ) 3 w 2 -2η 3 A(w)C(w * ) w 2 -η 2 (w T w * ) 2 B(w) w 2 -2η 3 B(w)C(w * )(w T w * ) w 2 -η 4 B(w)C(w * ) w 2 }

Bounding major direction of improvement Now let us focus on line ( 7), which can be viewed as the major direction of change guided by the stochastic gradient, while the rest terms can be viewed as noise. It equals

φ t j + 2η (w T w * )C(w * ) w 2 - 1 w 2 φ t j 2ηA(w) = φ t j + 2η w 2 {(w T w * )C(w * ) -φ t j A(w)}

Note that both terms C(w * ) and A(w) are stochastic, since their value is determined by data we sampled from the model distribution. We continue with the key step of our analysis: bounding EC(w * ) and EA(w). Since

r T w = x T w -a w 2 and a = x T w + b (r T w)(x T w * ) = (x T w -a w 2 )(x T w * ) = (x T w -(x T w + b) w 2 )(x T w * ) = w T xx T w * -(x T w + b) w 2 (x T w * ) and a(r T w * ) = (x T w + b)(x T w * -a(w T w * )) So C(w * ) = (2 -w 2 )(w T xx T w * ) -a(x T w)(w T w * ) -b w 2 (x T w * ) + b(x T w * ) -ab(w T w * ) = (2 -w 2 )(w T xx T w * ) -(x T w) 2 (w T w * ) -b w 2 (x T w * ) + b(x T w * ) -2b(x T w)(w T w * ) -b 2 (w T w * )

Since b is chosen such that b = (w T w * )( 1 w 2 -1) conditioning on E t , after some calculation we get

E x {-2b(x T w)(w T w * ) -b w 2 (x T w * ) + b(x T w * )|Ω t } = 2(w T w * ) 3 (1 - 1 w 2 ) + (w T w * )(1 - 1 w 2 )( w 2 -1)

On the other hand, note that

E x [w T xx T w * |Ω t ] = w T Exx T w * = w T E(w * + )(w * + ) T w * = w T (w * (w * ) T + E T )w * = w T (w * (w * ) T + σI)w * = w T w * + σw T w *

where the second inequality is by the condition that x is drawn from the j-th component, and fourth inequality is due to our model assumption on the covariance structure of . Similarly,

E x [(x T w) 2 |Ω t ] = E x [w T xx T w|Ω t ] = w T (w * (w * ) T + σI)w = (w T w * ) 2 + σ w 2

Therefore, we can calculate the other part as

E x {(2 -w 2 )(w T xx T w * ) -(x T w) 2 (w T w * )|Ω t } = (2 -w 2 )(w T w * )(1 + σ) -[(w T w * ) 3 + σ(w T w * ) w 2 ]

Combining, we get

E x {C(w * )|Ω t } = (2 -w 2 )(w T w * )(1 + σ) -[(w T w * ) 3 + σ(w T w * ) w 2 ] +2(w T w * ) 3 (1 - 1 w 2 ) + (w T w * )(1 - 1 w 2 )( w 2 -1) -E x [b 2 (w T w * )|Ω t ]

Thus,

E x {C(w * )|Ω t } (w T w * ) w 2 = φ t j {(w T w * ) 2 [1 - 1 w 2 ] + 2σ -2σ w 2 + 1 w 2 } -E x [b 2 |Ω t ]φ t j

Now, we turn to the term A(w), which equals

A(w) = ((x -aw) T w)(x T w + a) = [x T w -(x T w + b) w 2 ](2x T w + b) = (2 -2 w 2 )(x T w) 2 + b(x T w)(1 -3 w 2 ) -b 2 w 2 So E x [A(w)|Ω t ] = (2 -2 w 2 )[(w T w * ) 2 + σ w 2 ] +(w T w * ) 2 (1 -3 w 2 )(1 - 1 w 2 ) -E x [b 2 w 2 |Ω t ]

This implies that

E x [A(w)|Ω t ] φ t j w 2 = (φ t j ) 2 ( 1 w 2 -2 + w 2 ) + σφ t j (2 -2 w 2 ) -E x [b 2 |Ω t ]φ t j

Finally, combining the derivation for expected values relevant to C(w * ) and A(w), we get

E x {C(w * )|Ω t } (w T w * ) w 2 -E x [A(w)|Ω t ] φ t j w 2 = 1 w 2 φ t j (1 -φ t j )

So the expectation of line ( 7) is

φ t s + 2η 1 w 2 φ t s (1 -φ t s )

Also, note that since the terms w, w * , x are all bounded, the noise term must be bounded by some constant B 1 . Therefore, we can get a lower bound on increase of conditional expectation

E[φ t+1 s |x ∼ C j , g(s) = j, E t ] ≥ φ t s + 2η 1 w 2 φ t s (1 -φ t s ) -η 2 B 1 Since P r(x ∼ C j ) = 1 k , we get E[φ t+1 s |g(s) = j, E t ] ≥ 1 k {φ t s + 2η 1 w 2 φ t s (1 -φ t s ) -η 2 B 1 } + k -1 k E[φ t+1 s |g(s) = j, E t , x ∼ C j , j = j] ≥ φ t s + 2η 1 k w 2 φ t s (1 -φ t s ) -η 2 B 1

where the last inequality holds because a t s (x) ≤ 0 for x ∼ C j and g(s) = j (j = j ) by E t , and for neuron s such that a t s (x) ≤ 0, the gradient evaluates to zero so those entries are not updated after t. Thus, since E t holds, we know that

W t+1 s = W t s |g(s) > 0, g(s) = j, and x ∼ C j version 2 Let Y := 1 w 2 (w T w * )C(w * ) - 1 w 4 A(w)(w T w * ) 2 Then, from the proof of version 1, we know that φ t+1 s ≥ φ t s + 2η t E[Y |E t , X ∼ C g(s) ]P r(X ∼ C g(s) ) -2η t E[Y |E t ] + 2η t Y + (η t ) 2 B 1 = φ t s + 2η t 1 w 2 φ t s (1 -φ t s ) + 2η t (Y -E[Y |E t ]) + (η t ) 2 B 1 So letting Z := Y -E[Y |E t ],

we know that E[Z|E t ] = 0 Again, since the terms w, w * , x are all bounded, there must exists B 2 ≥ |Z|. Letting B := max{B 1 , B 2 } finishes the proof.

Proof outline of Theorem 3. Conditioning on F o , note that F ∞ can be written as the union of events

∪ s∈[n],g(s)>0 { W t s , W * j ≥ c 1 -λ 2 , ∀t ≥ 0, ∀j ∈ [k] s.t. g(s) = j} We denote these individual events regarding neuron s by F ∞ s , that is, F ∞ s := { W t s , W * j ≥ c 1 -λ 2 , ∀t ≥ 0, ∀j ∈ [k] s.t. g(s) = j}

The proof strategy is to show that the individual probability can be lower bounded by δ n , and taking the union bound over all neurons. Since (F ∞ s ) c can be partitioned into a union of disjoint subsets

∪ ∞ t=0 (F t s \ F t+1 s

), where ), and show that their summation vanishes for t → ∞. The same approach is taken in Proposition 2 Tang & Monteleoni (2017), and our main idea is to adapt the analysis there to our case. Thanks to the special form of inequality obtained in Theorem 2, we can neatly re-write the statement of its version 2 in terms of ∆ t s as

F t s := { W t s , W * j ≥ c 1 -λ 2 , ∀0 ≤ i ≤ t, ∀j ∈ [k] s.t

EQUATION

Essentially, the sufficient condition for the analysis of Proposition 2 Tang & Monteleoni (2017) to work are

• The expected decrease on the objective function ∆ t s is of the form

∆ t+1 s ≤ ∆ t s {1 - β t t + t o } + 2 c t + t o Z + ( c t + t o ) 2 B (9) • β t ≥ 2, ∀t ≥ 0

• The noise terms Z, B are bounded, and E[Z|F t ] = 0.

By our choice of η t , the relation in (8) satisfies the special form in (9). Since conditioning on F t , we have we get that β t ≥ 2 always hold. On the other hand, here the noise terms are obviously bounded by our model assumption. Therefore, we only need to slightly adapt Proposition 2 Tang & Monteleoni (2017) for our purpose. The exact proof is included for completeness.

β t := 2c (1 -∆ t s ) k W t

Complete proof of Theorem 3. We consider each F t s individually. Since the proof for each s is exactly the same, we abuse the notation F t to let it denote F t s for any fixed s. Similarly, we let ∆ t denote ∆ t s . Conditioning on F t , we know that ∃β > 2 s.t. β ≤ β t . By Lemma 7, for any λ > 0, and any 0 ≤ i ≤ t -1, we have

E{e λ∆ i+1 |F i } ≤ E{e λ{(1-β i to +i )∆ i |F i } exp{ λ(c ) 2 B (t o + i) 2 + λ 2 (c ) 2 B 2 2(t o + i) 2 } ≤ E{e λ (1) ∆ i |F i-1 } exp{ λ(c ) 2 B (t o + i) 2 + λ 2 (c ) 2 B 2 2(t o + i) 2 }

where λ (1) = λ(1 -β to+i ), and the second inequality is by Lemma 8. For k ≥ 1, we define λ (0) := λ and λ (k) := Π k t=1 (1 -

β t o + (i -t + 1) )λ (0)

We can similarly get, for k = 0, . . . , i,

E{e λ (k) ∆ i-k+1 |F i-k } ≤ E{e λ (k+1) ∆ i-k |F i-(k+1) } exp{ λ (k) (c ) 2 B (t o + i -k) 2 + (λ (k) ) 2 (c ) 2 B 2 2(t o + i -k) 2 } Since ∀β > 0, k ≥ 1, λ (k) = λΠ k t=1 (1 - β t o + (i -t + 1) ) ≤ λ( t o + i -k + 1 t o + i ) β

Since the bound is shrinking as β increases and β ≥ 2,

λ (k) (t 0 + i -k) 2 ≤ ( t o + i -k + 1 t o + i ) 2 λ (t o + i -k) 2 ≤ 4λ (t o + i) 2

Recursively applying the relation until we get to the term

E{e λ (i) ∆ 1 |F o } ≤ E{e λ (i+1) ∆ o |F o } exp{ λ(c ) 2 B (t o + i) 2 + λ 2 (c ) 2 B 2 2(t o + i) 2 } = exp{λ (i+1) ∆ o } exp{ λ(c ) 2 B (t o + i) 2 + λ 2 ) 2 B 2 2(t o + i) 2 }

Combining all these recursive inequalities with the bound on λ (k) , we get )∆ = δ (i + 1) 2 Finally, we have

P r(∪ i≥1 F i \ F i+1 ) ≤ ∞ i=1 P r(F i \ F i+1 ) ≤ δ

Now recall that this holds for each s, that is, ∀s ∈ [n], P r(F ∞ s ) ≤ δ s substituting δ s = δ k for δ in the proof above, and taking the union bound completes the proof. Lemma 7 (Inequality of moment generating function). Suppose the conditions of Theorem 2 hold. Then conditioning on E t (F t ), we can upper bound the moment generating function of ∆ t+1 as E[e λ∆ t+1

|F t ] ≤ exp{λ∆ t (1 -

β t t + t o ) + λ(η t ) 2 B + λ 2 (η t ) 2 B 2 2 }

Proof. We apply the result of Theorem 2. Rewriting version 2 of Theorem 2 using ∆ t := 1 -φ t s , for any s ∈ [n], we get

∆ t+1 ≤ ∆ t - 2η t k W t s ∆ t (1 -∆ t ) + 2η t Z + (η t ) 2 B = ∆ t {1 - 2η t k W t s (1 -∆ t )} + 2η t Z + (η t ) 2 B

:

The name max-norm regularization was originally proposed as a technique for low-rank matrix factorizationSrebro & Shraibman (2005), where the definition is in fact not exactly the same as what is practiced in the deep learning community. We use the latter convention in our analysis.

This assumption can be easily relaxed to a probabilistic bound, e.g., by assuming the noise has sub-gaussian tails. We stick with this stronger assumption for simplicity

√ 2d ,

Note that the firing map g is only defined for the sake of analysis; the algorithm does not have access to this information.

Figures and Tables:

x(x e ) := s d (W d x e + b d ) with W d ∈ R d×n , b d ∈ R d , s d : R d → R d where (W d , b d ) and s d are the network parameters and the activation function associated with the decoder respectively. Suppose the activation functions are fixed before training. One can view x as a reconstruction of the original signal/data using the hidden representation parameterized by (W e , b e ) and (W d , b d ). The goal of training an auto-encoder is to learn the "right" network parameters, (W e , b e , W d , b d ), so that x has low reconstruction error.

shows that P r(F ∞ ) is in fact arbitrarily close to one, conditioning on F o . We note that there is a line of recent work that analyze the convergence of SGD on non-convex functionsBalsubramani et al. (2013);Ge et al. (2015);Tang & Monteleoni (2017), where similar technical difficulty arise: to show local improvement of the algorithm on a non-convex functions, one usually needs to lower bound the probability of the algorithm entering a "bad" region, which can be saddle pointsGe et al. (2015);Balsubramani et al. (2013) or the part of solution space outside of a local neighborhoodTang & Monteleoni (2017). Some variant of martingale concentration is usually used for obtaining such result. Here, since event F t can be equivalently interpreted as W t s remains within the local neighborhood of W * g(s) defined as {y : y, W * j ≥ c(1 -δ o )}, we employ a technique similar to that inTang & Monteleoni (2017)  to show that F t holds with high probability for all t.

Figure2: The unit circle lies in H. For with a fixed norm, the picture illustrates one of the configurations where the maximal angle (θ) between data point X i (in red) and W * j is achieved.

s) > 0 and our choice of δ o in F o . Since we also set c ≥ 2kc

1 Norm-controlled SGD training Input: width parameter n; norm parameter c; learning rate parameters c , t o , δ; total number of iterations, t max . Initialization of W o : For all s ∈

Table content: <table/>

Rank, trace-norm and max-norm. In Proceedings of the 18th Annual Conference on Learning Theory,COLT'05, pp. 545-560, Berlin, Heidelberg, 2005.

Table content: <table><tr><td>Springer-Verlag. ISBN 3-540-26556-2, 978-3-540-26556-6. doi: 10.1007/11503415 37. URL</td></tr><tr><td>http://dx.doi.org/10.1007/11503415_37.</td></tr><tr><td>Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.</td></tr><tr><td>Dropout: A simple way to prevent neural networks from overfitting. J. Mach. Learn. Res., 15</td></tr><tr><td>(1):1929-1958, January 2014. ISSN 1532-4435. URL http://dl.acm.org/citation.</td></tr><tr><td>cfm?id=2627435.2670313.</td></tr><tr><td>Cheng Tang and Claire Monteleoni. Convergence rate of stochastic k-means. In Aarti Singh and</td></tr><tr><td>Jerry Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and</td></tr><tr><td>Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 1495-1503, Fort Laud-</td></tr><tr><td>erdale, FL, USA, 20-22 Apr 2017. PMLR. URL http://proceedings.mlr.press/</td></tr><tr><td>v54/tang17b.html.</td></tr></table>

. g(s) = j}

Table content: <table><tr><td>We can define E t s similarly, and note we can easily show that</td></tr><tr><td>F t s =⇒ E t s</td></tr><tr><td>by going through Lemma 4 exactly the same. To lower bound P r(F ∞ s ), we upper bound the indi-vidual error probability P r(F t s \ F t+1 s</td></tr></table>

E{e λ∆ i+1|F i } ≤ e λ (i+1) ∆ 0 exp{ Let τ o := λ 2 . Then we can apply the conditional Markov's inequality, for any λ i > 0,P r(F i \ F i+1 ) = P r(∆ i+1 > τ o |F i ) = P r(e λi∆ i+1 > e λiτo |F i ) ≤ E[e λi∆ i+1 |F i ] e λiτoSince eventF o = {φ o ≥ 1 -λ 2 2 } implies ∆ o = 1 -φ o ≤ λ 2 2 = τo 2 , we have ( t o t o + i ) β ∆ o -τ o ≤ ∆ o -τ o ≤ τ o 2Combining this with the upper bound on E[e λi∆ i+1 |F i ], we getP r(F i \ F i+1 ) ≤ exp -λ i { Case 1: B > λiB 2 2 . Since t o ≥ 32(c ) 2 B

Table content: <table><tr><td colspan="3">Case 2: B ≤ λiB 2 2 . We get</td><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td>1 2</td><td>τ o -(B +</td><td>λ i B 2 2</td><td>)</td><td>4(c ) 2 i (t o + i) 2</td></tr><tr><td/><td/><td/><td/><td/><td/><td>≥ 2∆ -λ i B 2 4(c ) 2 i (t o + i) 2</td></tr><tr><td/><td/><td/><td/><td colspan="3">= 2∆ -</td><td>1 ∆</td><td>ln</td><td>(1 + i) 2 δ</td><td>4(c ) 2 B 2 i (t o + i) 2</td></tr><tr><td/><td colspan="4">≥ 2∆ -</td><td colspan="2">1 ∆</td><td>ln</td><td>(t o + i) 2 δ</td><td>4(c ) 2 B 2 (t o + i) (t o + i) 2</td></tr><tr><td>Now we show</td><td/><td/><td/><td/><td>1 ∆</td><td>ln</td><td>(t o + i) 2 δ</td><td>4(c ) 2 B 2 t o + i</td><td>≤ ∆</td></tr><tr><td>Since</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td colspan="5">t o + i ≥ t o ≥</td><td>192(c ) 2 B 2 τ 2 o</td><td>ln 2 1 δ</td></tr><tr><td colspan="7">ln 1 δ ≥ 1, and obviously, 16(c ) 2 B 2 ∆ 2 16(c ) 2 B 2 ( 1 2 τo) 2 ≥ 16(c ) 2 B 2 ( 1 2 τo) 2 b-1 , and get</td><td>≥ 1 3 , we can apply Lemma ?? with b = 2, C :=</td></tr><tr><td/><td>4(c ) 2 B 2 ∆ 2</td><td>ln</td><td colspan="4">(t o + i) 2 δ</td><td>:= 2C ln t + C ln</td><td>1 δ</td><td>&lt; t b-1 = t o + i</td></tr><tr><td colspan="2">Or equivalently, 1 ∆ ln (to+i) 2 δ</td><td colspan="4">4(c ) 2 B 2 to+i</td><td>≤ ∆. Thus, for both cases,</td></tr><tr><td/><td/><td colspan="5">2∆ -(B +</td><td>i-1 k=0 ( λ i B 2 2 ) (t o + i) 2 ≥= ∆ 4λ(c ) 2 B (t o + i) 2 + 4λ 2 (c ) 2 B 2 2(t o + i) 2 )} 4(c ) 2 i</td></tr><tr><td>This implies</td><td colspan="6">≤ exp{λ( P r(F i \ F i+1 ) ≤ e -1 t o t o + i ) β ∆ 0 + [λ(c ) 2 B + (1+i) 2 λ 2 (c ) 2 B 2 2 ∆ (ln δ</td><td>]</td><td>4i (t o + i) 2 }</td></tr><tr><td/><td/><td/><td/><td/><td/><td>τ o 2</td><td>-(B +</td><td>λ i B 2 2</td><td>)</td><td>4(c ) 2 i (t o + i) 2 }</td></tr><tr><td colspan="2">We choose λ i = 1 ∆ ln (i+1) 2 δ</td><td colspan="5">with ∆ = τo 4 , and show that τo 2 -(B + λiB 2 2 ) 4(c ) 2 i (to+i) 2 is lower bounded</td></tr><tr><td>by ∆.</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td>τo</td><td>, we get</td></tr><tr><td/><td/><td/><td>1 2</td><td colspan="3">τ o -(B +</td><td>λ i B 2 2</td><td>)</td><td>4(c ) 2 i (t o + i) 2 ≥ ∆</td></tr></table>

Peer review (iclr2018):
 The paper considers training single-hidden-layer auto-encoders, using stochastic gradient descent, for data generated from a noisy sparse dictionary model. The main result shows that under suitable conditions, the algorithm is likely to recover the ground-truth parameters. Although non-convex dictionary learning has been extensively studied for linear models, extending such convergence results to nonlinear models is interesting, and the result (if true) would be quite nice. Unfortunately (and unless I missed something), there appears to be a crucial bug in the argument, which requires that random initialization lead to dictionary elements sufficiently close to the ground truth. Specifically, definition 1 and lemma 1 give a bound on the success probability, which is exponentially small in the dimension d (as it should, since it essentially bounds the probability that an O(1)-norm random vector has .Omega(1) inner product with some fixed unit vector). However, the d exponent disappears when the lemma is used to prove the main theorem (bottom of pg. 10), as well as in the theorem statement, making it seem that the success probability is large. Of course, a result which holds with exponentially small probability is not very interesting. I should also say that I did not check the rest of the proof carefully. A few relatively more minor issues: - The paper makes the strong assumption that the data is generated from a 1-sparse dictionary model. In other words, each data point is simply a randomly-chosen dictionary element, plus zero-mean noise. With this model, dictionary learning is quite easy and could be solved directly by other methods (although I see the value of analyzing specifically the behavior of SGD on auto-encoders). - To make things go through, the paper makes a non-trivial assumption on how the bias terms are updated (not quite according to SGD). But unless I*m missing something, a bias term isn*t even needed to learn in their model, so wouldn*t it be simpler and more natural to just assume that the auto-encoder doesn*t have a bias term (i.e., x-> W*s(Wx))?.