Learning ReLUs via Gradient Descent
In this paper we study the problem of learning Rectified Linear Units (ReLUs) which are functions of the form x ↦ max(0, ⟨w, x⟩) with w ∈ R d denoting the weight vector. We study this problem in the high-dimensional regime where the number of observations are fewer than the dimension of the weight vector. We assume that the weight vector belongs to some closed set (convex or nonconvex) which captures known side-information about its structure. We focus on the realizable model where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to a planted weight vector. We show that projected gradient descent, when initialized at 0, converges at a linear rate to the planted model with a number of samples that is optimal up to numerical constants. Our results on the dynamics of convergence of these very shallow neural nets may provide some insights towards understanding the dynamics of deeper architectures.
### Summary
The paper proves that projected gradient descent in a single-layer ReLU network converges to the global minimum linearly: ||w_t-w^*||/||w_0-w^*||=(1/2)^t with high probability. The analysis assumes the input samples are iid Gaussian and the output is realizable, i.e. the target value y_k for input x_k is constructed via y_k=ReLU(w^*.x_k). The paper studies a regression setting and uses least squares as the loss function.
### Pros and Cons
To the best of my knowledge, the result is novel; I am not aware of any proof of "convergence to global optimum" for the nonconvex loss resulted by fitting to a ReLu function via least squares. On top of that, the analysis considers a nonconvex regularization term with little assumptions on it. Of course, there still a clear gap between the results of this paper and models used in practice: notably, relaxing the Gaussian iid input assumption, and extending to multilayer setup. However, this result may become a stepping stone toward that goal.
### Proofs
I followed the building blocks of the proof at the coarse level, and the logic makes sense. However, I did not check at a very detailed level. I was wondering if the authors could include a simple simulation to confirm the correctness of the result? Given that the data is very simple (iid Gaussian) and the network is a single layer ReLU, using a very simple regularization scheme, it seems to take a few lines of Matlab to verify the empirical convergence rate and compare that with the result. In fact, I wonder why this is not attempted by the authors already?
### Regularization
The authors state that the result holds true regardless of regularization R being convex or nonconvex. What if R is such that it creates two far apart and disjoint regions, one containing the origin (initialization) and the other containing w^*. Wouldn't this create a problem for projected gradient descent initialized by w=0 to reach w^*?
 
### Minor Comments
1. There are typos, please proof read.
2. What is the meaning of A in L_A (Eq 5.12)?
3. What is the value of the constant gamma in line 180, or otherwise how is it related to other constants or quantities in the paper?