# Agnostic Learning of General ReLU Activation Using Gradient Descent

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

## Key facts

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

## Builds on (most cited first, 20 of 20)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [Learning ReLUs via Gradient Descent](https://mlsanity.com/paper/1705.04591/) (2017)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [Agnostic Learning of a Single Neuron with Gradient Descent](https://mlsanity.com/paper/2005.14426/) (2020)
- [Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks](https://mlsanity.com/paper/1802.06093/) (2018)
- [Reliably Learning the ReLU in Polynomial Time](https://mlsanity.com/paper/1611.10258/) (2016)
- [On the Global Convergence of Training Deep Linear ResNets](https://mlsanity.com/paper/2003.01094/) (2020)
- [Efficient approaches for escaping higher order saddle points in non-convex optimization](https://mlsanity.com/paper/1602.05908/) (2016)
- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [Learning a Single Neuron with Bias Using Gradient Descent](https://mlsanity.com/paper/2106.01101/) (2021)
- [Learning Distributions Generated by One-Layer ReLU Networks](https://mlsanity.com/paper/1909.01812/) (2019)

## Built on by (most cited first, 12 of 12)

- [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)
- [Robustly Learning a Single Neuron via Sharpness](https://mlsanity.com/paper/2306.07892/) (2023)
- [Simplicity Bias of Two-Layer Networks beyond Linearly Separable Data](https://mlsanity.com/paper/2405.17299/) (2024)
- [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)
- [Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise](https://mlsanity.com/paper/2411.06697/) (2024)
- [Robustly Learning Monotone Single-Index Models](https://mlsanity.com/paper/2508.04670/) (2025)
- [A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube](https://mlsanity.com/paper/2511.07244/) (2025)
- [Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals](https://mlsanity.com/paper/2605.21428/) (2026)
- [Robust Regression of General ReLUs with Queries](https://mlsanity.com/paper/2606.11130/) (2026)
- [Feature Learning for the High Dimensional Stationary Sch"odinger Equation with Deep Ritz Method](https://mlsanity.com/paper/2607.06369/) (2026)

## 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.