mlsanityData to 7 Oct 2026

Agnostic Learning of a Single Neuron with Gradient Descent

arXiv 2005.14426 ↗First posted 29 May 2020cs.LG math.OC stat.MLcited by 46

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 7; 2023: 11; 2024: 7; 2025: 5; 2026: 5.

46 papers.

Sort:

  1. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 184
  2. 2022A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Featurescited by 49
  3. 2021Early-stopped neural networks are consistentcited by 34
  4. 2022Random Feature Amplification: Feature Learning and Generalization in Neural Networkscited by 33
  5. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  6. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  7. 2021Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descentcited by 21
  8. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  9. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  10. 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
  11. 2021Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noisecited by 17
  12. 2021Learning a Single Neuron with Bias Using Gradient Descentcited by 17
34 more
  1. 2021Optimization-Based Separations for Neural Networkscited by 17
  2. 2023On Single Index Models beyond Gaussian Datacited by 17
  3. 2023Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputscited by 16
  4. 2023Agnostically Learning Single-Index Models using Omnipredictorscited by 16
  5. 2024Masks, Signs, And Learning Rate Rewindingcited by 15
  6. 2022Learning a Single Neuron for Non-monotonic Activation Functionscited by 13
  7. 2022Agnostic Learning of General ReLU Activation Using Gradient Descentcited by 12
  8. 2023Robustly Learning a Single Neuron via Sharpnesscited by 12
  9. 2024Agnostic Active Learning of Single Index Models with Linear Sample Complexitycited by 11
  10. 2021ReLU Regression with Massart Noisecited by 10
  11. 2023Differentially Private Non-convex Learning for Multi-layer Neural Networkscited by 10
  12. 2023Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuroncited by 8
  13. 2025Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributionscited by 8
  14. 2022Magnitude and Angle Dynamics in Training Single ReLU Neuronscited by 5
  15. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  16. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
  17. 2023How Graph Neural Networks Learn: Lessons from Training Dynamicscited by 3
  18. 2025Nearly Optimal Differentially Private ReLU Regressioncited by 3
  19. 2023The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learningcited by 2
  20. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  21. 2026Deep Networks Learn Deep Hierarchical Modelscited by 2
  22. 2023The Local Landscape of Phase Retrieval Under Limited Samplescited by 1
  23. 2024RedEx: Beyond Fixed Representation Methods via Convex Optimizationcited by 1
  24. 2025Joint Learning in the Gaussian Single Index Modelcited by 1
  25. 2026Interactive Learning of Single-Index Models via Stochastic Gradient Descentcited by 1
  26. 2021Painless step size adaptation for SGDcited by 0
  27. 2021Neurons learn slower than they thinkcited by 0
  28. 2021Dynamics of Local Elasticity During Training of Neural Netscited by 0
  29. 2024Disentangle Sample Size and Initialization Effect on Perfect Generalization for Single-Neuron Targetcited by 0
  30. 2025A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyondcited by 0
  31. 2025Block Coordinate Descent for Neural Networks Provably Finds Global Minimacited by 0
  32. 2026Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginalscited by 0
  33. 2026Robust Regression of General ReLUs with Queriescited by 0
  34. 2026Feature Learning for the High Dimensional Stationary Sch"odinger Equation with Deep Ritz Methodcited by 0