mlsanityData to 7 Oct 2026

Agnostic Learning of General ReLU Activation Using Gradient Descent

arXiv 2208.02711 ↗First posted 4 Aug 2022cs.LG cs.DS stat.MLcited by 12

Not on the map. Why?

Abstract (arXiv)

We provide a convergence analysis of gradient descent for the problem of agnostically learning a single ReLU function with moderate bias under Gaussian distributions. Unlike prior work that studies the setting of zero bias, we consider the more challenging scenario when the bias of the ReLU function is non-zero. Our main result establishes that starting from random initialization, in a polynomial number of iterations gradient descent outputs, with high probability, a ReLU function that achieves an error that is within a constant factor of the optimal error of the best ReLU function with moderate bias. We also provide finite sample guarantees, and these techniques generalize to a broader class of marginal distributions beyond Gaussians.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 20 of its 28 references that are in the map. First posted on arXiv 4 Aug 2022.

Builds on

20 of 28 references.

References · 20

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  3. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  5. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  6. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
  7. 2017How to Escape Saddle Points Efficientlycited by 284
  8. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  9. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  10. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 79
  11. 2017Learning ReLUs via Gradient Descentcited by 54
  12. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
8 more
  1. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  2. 2018Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networkscited by 44
  3. 2016Reliably Learning the ReLU in Polynomial Timecited by 36
  4. 2020On the Global Convergence of Training Deep Linear ResNetscited by 29
  5. 2016Efficient approaches for escaping higher order saddle points in non-convex optimizationcited by 23
  6. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  7. 2021Learning a Single Neuron with Bias Using Gradient Descentcited by 17
  8. 2019Learning Distributions Generated by One-Layer ReLU Networkscited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 4; 2025: 2; 2026: 3.

12 papers.

  1. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  2. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  3. 2023Robustly Learning a Single Neuron via Sharpnesscited by 12
  4. 2024Simplicity Bias of Two-Layer Networks beyond Linearly Separable Datacited by 11
  5. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  6. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
  7. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  8. 2025Robustly Learning Monotone Single-Index Modelscited by 2
  9. 2025A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercubecited by 1
  10. 2026Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginalscited by 0
  11. 2026Robust Regression of General ReLUs with Queriescited by 0
  12. 2026Feature Learning for the High Dimensional Stationary Sch"odinger Equation with Deep Ritz Methodcited by 0