  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.
