# Learning ReLUs via Gradient Descent

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2017.

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

- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learning](https://mlsanity.com/paper/2105.15134/) (2021)
- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attention](https://mlsanity.com/paper/2310.00535/) (2023)
- [Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels](https://mlsanity.com/paper/2103.01210/) (2021)
- [The Mechanism of Prediction Head in Non-contrastive Self-supervised Learning](https://mlsanity.com/paper/2205.06226/) (2022)
- [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)
- [Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron](https://mlsanity.com/paper/2302.10034/) (2023)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [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)
- [GradSign: Model Performance Inference with Theoretical Insights](https://mlsanity.com/paper/2110.08616/) (2021)
- [Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networks](https://mlsanity.com/paper/2305.06986/) (2023)
- [Learning a Single Neuron with Bias Using Gradient Descent](https://mlsanity.com/paper/2106.01101/) (2021)
- [On Single Index Models beyond Gaussian Data](https://mlsanity.com/paper/2307.15804/) (2023)
- [Masks, Signs, And Learning Rate Rewinding](https://mlsanity.com/paper/2402.19262/) (2024)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [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)
- [Towards Theoretically Inspired Neural Initialization Optimization](https://mlsanity.com/paper/2210.05956/) (2022)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samples](https://mlsanity.com/paper/2101.07150/) (2021)
- [Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron](https://mlsanity.com/paper/2303.02255/) (2023)
- [Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?](https://mlsanity.com/paper/2309.07452/) (2023)
- [A faster and simpler algorithm for learning shallow networks](https://mlsanity.com/paper/2307.12496/) (2023)

## Abstract (arXiv)

In this paper we study the problem of learning Rectified Linear Units (ReLUs) which are functions of the form max(0,<w,x>) with w denoting the weight vector. We study this problem in the high-dimensional regime where the number of observations are fewer than the dimension of the weight vector. We assume that the weight vector belongs to some closed set (convex or nonconvex) which captures known side-information about its structure. We focus on the realizable model where the inputs are chosen i.i.d.~from a Gaussian distribution and the labels are generated according to a planted weight vector. We show that projected gradient descent, when initialization at 0, converges at a linear rate to the planted model with a number of samples that is optimal up to numerical constants. Our results on the dynamics of convergence of these very shallow neural nets may provide some insights towards understanding the dynamics of deeper architectures.