# Agnostic Learning of a Single Neuron with Gradient Descent

arXiv: https://arxiv.org/abs/2005.14426 · HTML: https://mlsanity.com/paper/2005.14426/

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2020.

## Built on by (most cited first, 30 of 46)

- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Features](https://mlsanity.com/paper/2206.01717/) (2022)
- [Random Feature Amplification: Feature Learning and Generalization in Neural Networks](https://mlsanity.com/paper/2202.07626/) (2022)
- [Early-stopped neural networks are consistent](https://mlsanity.com/paper/2106.05932/) (2021)
- [Gradient-Based Feature Learning under Structured Data](https://mlsanity.com/paper/2309.03843/) (2023)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent](https://mlsanity.com/paper/2106.13792/) (2021)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)
- [Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise](https://mlsanity.com/paper/2101.01152/) (2021)
- [Learning a Single Neuron with Bias Using Gradient Descent](https://mlsanity.com/paper/2106.01101/) (2021)
- [Optimization-Based Separations for Neural Networks](https://mlsanity.com/paper/2112.02393/) (2021)
- [On Single Index Models beyond Gaussian Data](https://mlsanity.com/paper/2307.15804/) (2023)
- [Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs](https://mlsanity.com/paper/2306.06479/) (2023)
- [Agnostically Learning Single-Index Models using Omnipredictors](https://mlsanity.com/paper/2306.10615/) (2023)
- [Masks, Signs, And Learning Rate Rewinding](https://mlsanity.com/paper/2402.19262/) (2024)
- [Learning a Single Neuron for Non-monotonic Activation Functions](https://mlsanity.com/paper/2202.08064/) (2022)
- [Agnostic Learning of General ReLU Activation Using Gradient Descent](https://mlsanity.com/paper/2208.02711/) (2022)
- [Robustly Learning a Single Neuron via Sharpness](https://mlsanity.com/paper/2306.07892/) (2023)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Differentially Private Non-convex Learning for Multi-layer Neural Networks](https://mlsanity.com/paper/2310.08425/) (2023)
- [Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron](https://mlsanity.com/paper/2303.02255/) (2023)
- [Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions](https://mlsanity.com/paper/2502.06443/) (2025)
- [Magnitude and Angle Dynamics in Training Single ReLU Neurons](https://mlsanity.com/paper/2209.13394/) (2022)
- [Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals](https://mlsanity.com/paper/2411.14349/) (2024)
- [Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models](https://mlsanity.com/paper/2411.05708/) (2024)
- [How Graph Neural Networks Learn: Lessons from Training Dynamics](https://mlsanity.com/paper/2310.05105/) (2023)
- [Nearly Optimal Differentially Private ReLU Regression](https://mlsanity.com/paper/2503.06009/) (2025)

## Abstract (arXiv)

We consider the problem of learning the best-fitting single neuron as measured by the expected square loss mathbbE(x,y)~ D[(σ(w^top x)-y)2] over some unknown joint distribution D by using gradient descent to minimize the empirical risk induced by a set of i.i.d. samples S~ Dn. The activation function σ 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 mathsfOPT, we show that gradient descent achieves population risk O(mathsfOPT)+ε in polynomial time and sample complexity when σ is strictly increasing. For the ReLU activation, our population risk guarantee is O(mathsfOPT1/2)+ε. When labels take the form y = σ(v^top x) + xi for zero-mean sub-Gaussian noise xi, we show that the population risk guarantees for gradient descent improve to mathsfOPT + ε. Our sample complexity and runtime guarantees are (almost) dimension independent, and when σ 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.