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.
This paper shows that an idealized version of stochastic gradient descent converges when learning autoencoders with ReLu non-linearities under strong sparsity assumptions. Convergence rates are also determined. The result is another one in the emerging line of proving convergence guarantees for non-convex optimization problems arising in machine learning, and aims to explain certain phenomena experienced in practice.
The paper is generally nicely written, providing intuitions, but there are several typos (both in the text and in the math, e.g., missing indices), which should also be corrected.
On the negative side, while the proof technique in general looks plausible, there seem to be some mistakes in the derivations, which must be corrected before the paper can be accepted. Also, the assumptions in the in the paper seem quite restrictive, and their implications are not discussed thoroughly. 
The assumptions are the following:
1. The input data is coming from a mixture distribution, in the form x=w_I + eps, where {w_1,...,w_k} is a collection of unit vectors, I is uniform in {1,...,K}, eps is some noise (independent for each sample). 
2. The maximum norm of the noise is O(1/k).
3. The number n of hidden neurons in the autoencoder is Omega(k) (this is not explicitly assumed but is necessary to make the probability of "incorrect" initialization small as well as the results to hold).
Under these assumptions it is shown that the weights of the autoencoder converge to the centers {w_1,...,w_k} (i.e., for any i the autoencoder has at least one weight converging to w_i). The rate of convergence depends on the coherence of the vectors w_i: the less coherent they are the faster the convergence is.
First notice that some assumptions are missing from the main statement, as the error probability delta is certainly connected to the probability of incorrect initialization: when n=1<k, the convergence result clearly cannot hold. This comes from the mistake that in Theorem 3 you state the bound for the probability P(F^\infty) instead of the conditional probability P(F^\infty|E_o) (this is present everywhere in the proof). Theorem 3 should also depend on delta_o, which is used in the definition of F^\infty. 
Theorem 2 also seems incorrect. Intuitively, the question is why it cannot happen that two neurons contribute to reproducing a given w_i, and so neither of their weights converge to w_i: E.g., assuming that {w_1,...,w_k,w_1',...,w_k'} form an orthogonal system and the noise is 0, the weight matrix of size n=2k defined as W_{2i-1,*}^T = 1/sqrt{2}(w_i + w'_i) and W_{2i,*}^T=1/sqrt{2}(w_i - w'_i), i \in [k], with 0 bias can exactly recover any x=w_i (indeed, W_{2j-1,*} x= W_{2j,*} x = 1/sqrt{2}, while the other products are 0, and so W^T W x = W^T W w_j = 1/sqrt{2}(W_{2j-1,*}+W_{2j,*})^T = w_j). Then SGD does not change the weights and hence cannot recover the original weights {w_i }, in particular, it cannot increase the coherence in any step, contradicting Theorem 2. This counterexample can be extended even to the situation when k>d, as--in fact--we only need that the existence of a single j such that w_j and w'_j are orthogonal and also orthogonal to the other basis vectors.
The assumptions are also very strange in the sense that the norm of the noise is bounded by O(1/k), thus the more modes the input distribution has the more separable they become. What motivates this scaling? Furthermore, the parameters of the algorithm for which the convergence is claimed heavily depend on the problem parameters, which are not known. How can you instantiate the algorithm then (accepting the ideal definition of b)? What are the consequences?
Given the above, at this point I cannot recommend the paper for acceptance. However, if the above problems are resolved, I would be very happy to see the paper at the conference.
Other comments
-----------------------
- Add a short derivation why the weights of the autoencoder should converge to the w_i.
- Definition 3: C_j is not defined in the main text.
- While it is mentioned multiple times that the interesting regime is d<n, this is actually never used, nor needed (personally, I have never seen such an autoencoder--please give some references). What is really needed is n>k, which is natural if one wants to preserve the information, and also k>d for a rich family of distributions.
- The area of the spherical cap is well understood (up to multiplicative constants), and better bounds than yours are readily available: with a cap of height 1-t, for sqrt{2/d}<t<1, the relative surface of the cap is between P/6 and P/2 where 
P=1/(t \sqrt{d}) (1-t^2)^{(d-1)/2}; see, e.g., A. Brieden, P. Gritzmann, R. Kannan, V. Klee, L. Lovasz, and M. Simonovits. Deterministic and randomized polynomial-time approximation of radii. Mathematika. A Journal of Pure and Applied Mathematics, 48(1-2):63–105, 2001. 
- The notation section should be brought forward (or referred the fist time the notation is actually used).
- Instead of unit spherical Gaussian you could simply say uniform distribution on the unit sphere
- While Algorithm 1 is called "norm-controlled SGD training," it does not control the norm at all.