Agnostic Learning of a Single Neuron with Gradient Descent

We consider the problem of learning the best-fitting single neuron as measured by the expected square loss \E_{(x,y)\sim \mathcal{D}}[(\sigma(w \top x)-y) 2] over some unknown joint distribution \mathcal{D} by using gradient descent to minimize the empirical risk induced by a set of i.i.d. The activation function \sigma is an arbitrary Lipschitz and non-decreasing function, making the optimization problem nonconvex and nonsmooth in general, and covers typical neural network activation functions and inverse link functions in the generalized linear model setting. In the agnostic PAC learning setting, where no assumption on the relationship between the labels y and the input x is made, if the optimal population risk is \mathsf{OPT}, we show that gradient descent achieves population risk O(\mathsf{OPT}) \eps in polynomial time and sample complexity when \sigma is strictly increasing. When labels take the form y \sigma(v \top x) \xi for zero-mean sub-Gaussian noise \xi, we show that the population risk guarantees for gradient descent improve to \mathsf{OPT} \eps . Our sample complexity and runtime guarantees are (almost) dimension independent, and when \sigma is strictly increasing, require no distributional assumptions beyond boundedness.