Learning ReLUs via Gradient Descent
This provides theoretical insights into training shallow neural networks, which may help understand deeper architectures, but it is incremental as it builds on existing optimization frameworks.
The paper tackles the problem of learning ReLU activation functions in high-dimensional settings with fewer observations than dimensions, assuming the weight vector lies in a structured set and data is Gaussian with realizable labels. It shows that projected gradient descent from zero initialization converges linearly to the true model with a sample complexity optimal up to constants.
In this paper we study the problem of learning Rectified Linear Units (ReLUs) which are functions of the form $max(0,<w,x>)$ with $w$ 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 initialization 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.