EMPIRICAL RISK LANDSCAPE ANALYSIS FOR UNDER- STANDING DEEP NEURAL NETWORKS
This work aims to provide comprehensive landscape analysis of empirical risk in deep neural networks (DNNs), including the convergence behavior of its gradient, its stationary points and the empirical risk itself to their corresponding population counterparts, which reveals how various network parameters determine the convergence performance. In particular, for an l-layer linear neural network consisting of d i neurons in the i-th layer, we prove the gradient of its empirical risk uniformly converges to the one of its population risk, at the rate of
Here d is the total weight dimension, s is the number of nonzero entries of all the weights and the magnitude of weights per layer is upper bounded by r. Moreover, we prove the one-to-one correspondence of the non-degenerate stationary points between the empirical and population risks and provide convergence guarantee for each pair. We also establish the uniform convergence of the empirical risk to its population counterpart and further derive the stability and generalization bounds for the empirical risk. In addition, we analyze these properties for deep nonlinear neural networks with sigmoid activation functions. We prove similar results for convergence behavior of their empirical risk gradients, non-degenerate stationary points as well as the empirical risk itself. To our best knowledge, this work is the first one theoretically characterizing the uniform convergence of the gradient and stationary points of the empirical risk of DNN models, which benefits the theoretical understanding on how the neural network depth l, the layer width d i , the network size d, the sparsity in weight and the parameter magnitude r determine the neural network landscape.
Overall, this work seems like a reasonable attempt to answer the question of how the empirical loss landscape relates to the true population loss landscape.  The analysis answers:
1) When empirical gradients are close to true gradients
2) When empirical isolated saddle points are close to true isolated saddle points
3) When the empirical risk is close to the true risk.
The answers are all of the form that if the number of training examples exceeds a quantity that grows with the number of layers, width and the exponential of the norm of the weights with respect to depth, then empirical quantities will be close to true quantities.  I have not verified the proofs in this paper (given short notice to review) but the scaling laws in the upper bounds found seem reasonably correct. 
Another reviewer's worry about why depth plays a role in the convergence of empirical to true values in deep linear networks is a reasonable worry, but I suspect that depth will necessarily play a role even in deep linear nets because the backpropagation of gradients in linear nets can still lead to exponential propagation of errors between empirical and true quantities due to finite training data.  Moreover the loss surface of deep linear networks depends on depth even though the expressive capacity does not.   An analysis of dynamics on this loss surface was presented in Saxe et. al. ICLR 2014 which could be cited to address that reviewer's concern.  However, the reviewer's suggestion that the results be compared to what is known more exactly for simple linear regression is a nice one. 
Overall, I believe this paper is a nice contribution to the deep learning theory literature. However,  it would even better to help the reader with more intuitive statements about the implications of their results for practice, and the gap between their upper bounds and practice, especially given the intense interest in the generalization error problem.   Because their upper bounds look similar to those based on Rademacher complexity or VC dimension (although they claim theirs are a little tighter) - they should put numbers in to their upper bounds taken from trained neural networks, and see what the numerical evaluation of their upper bounds turn out to be in situations of practical interest where deep networks show good generalization performance despite having significantly less training data than number of parameters.  I suspect their upper bounds will be loose, but still  - it would be an excellent contribution to the literature to quantitatively compare theory and practice with bounds that are claimed to be slightly tigher than previous bounds.  Even if they are loose - identifying the degree of looseness could inspire interesting future work.