Agnostic Learning of a Single Neuron with Gradient Descent

Abstract

We consider the problem of learning the best-fitting single neuron as measured by the expected square loss ${\mathbb{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. samples $S\sim {\mathcal{D}}^n$. 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})+\epsilon$ in polynomial time and sample complexity when $\sigma$ is strictly increasing. For the ReLU activation, our population risk guarantee is $O({\mathsf{OPT}}^{1/2})+\epsilon$. 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}+\epsilon$. Our sample complexity and runtime guarantees are (almost) dimension independent, and when $\sigma$ is strictly increasing, require no distributional assumptions beyond boundedness. For ReLU, we show the same results under a nondegeneracy assumption for the marginal distribution of the input.

arXiv comment31 pages, 3 tables. This version improves the risk bound from O(OPT^1/2) to O(OPT) for strictly increasing activation functions

References in corpus (9)

• Contextual Bandit Algorithms with Supervised Learning Guarantees
• Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
• When is a Convolutional Filter Easy To Learn?
• Reliably Learning the ReLU in Polynomial Time
• Learning One-hidden-layer ReLU Networks via Gradient Descent
• Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds
• Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals
• Tight Sample Complexity of Learning One-hidden-layer Convolutional Neural Networks
• Statistical-Query Lower Bounds via Functional Gradients

Cited by in corpus (5)

• Statistical-Query Lower Bounds via Functional Gradients
• Early-stopped neural networks are consistent
• The Connection Between Approximation, Depth Separation and Learnability in Neural Networks
• Painless step size adaptation for SGD
• Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron