# Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 32 references that are in the map.
- First posted on arXiv 3 Mar 2023.

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

- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares](https://mlsanity.com/paper/1904.12838/) (2019)
- [Learning ReLUs via Gradient Descent](https://mlsanity.com/paper/1705.04591/) (2017)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Dimension free ridge regression](https://mlsanity.com/paper/2210.08571/) (2022)
- [Learning a Single Neuron with Gradient Methods](https://mlsanity.com/paper/2001.05205/) (2020)
- [Agnostic Learning of a Single Neuron with Gradient Descent](https://mlsanity.com/paper/2005.14426/) (2020)
- [Uniform Convergence of Gradients for Non-Convex Learning and Optimization](https://mlsanity.com/paper/1810.11059/) (2018)
- [Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression](https://mlsanity.com/paper/2110.06198/) (2021)
- [Tight Hardness Results for Training Depth-2 ReLU Networks](https://mlsanity.com/paper/2011.13550/) (2020)
- [Approximation Schemes for ReLU Regression](https://mlsanity.com/paper/2005.12844/) (2020)
- [Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals](https://mlsanity.com/paper/1911.01462/) (2019)
- [The Benefits of Implicit Regularization from SGD in Least Squares Problems](https://mlsanity.com/paper/2108.04552/) (2021)
- [The Power and Limitation of Pretraining-Finetuning for Linear Regression under Covariate Shift](https://mlsanity.com/paper/2208.01857/) (2022)
- [On Uniform Convergence and Low-Norm Interpolation Learning](https://mlsanity.com/paper/2006.05942/) (2020)
- [When is a Convolutional Filter Easy To Learn?](https://mlsanity.com/paper/1709.06129/) (2017)
- [Learning a Single Neuron with Adversarial Label Noise via Gradient Descent](https://mlsanity.com/paper/2206.08918/) (2022)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/2210.12082/) (2022)

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

- [How Many Pretraining Tasks Are Needed for In-Context Learning of Linear Regression?](https://mlsanity.com/paper/2310.08391/) (2023)
- [Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Time](https://mlsanity.com/paper/2306.16361/) (2023)
- [Seesaw: Accelerating Training by Balancing Learning Rate and Batch Size Scheduling](https://mlsanity.com/paper/2510.14717/) (2025)
- [A Simplified Analysis of SGD for Linear Regression with Weight Averaging](https://mlsanity.com/paper/2506.15535/) (2025)
- [Improving Implicit Regularization of SGD with Preconditioning for Least Square Problems](https://mlsanity.com/paper/2403.08585/) (2024)
- [Nearly Optimal Differentially Private ReLU Regression](https://mlsanity.com/paper/2503.06009/) (2025)
- [On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks](https://mlsanity.com/paper/2508.14338/) (2025)
- [Dimension-free uniform concentration bound for logistic regression](https://mlsanity.com/paper/2405.18055/) (2024)

## Abstract (arXiv)

This paper considers the problem of learning a single ReLU neuron with squared loss (a.k.a., ReLU regression) in the overparameterized regime, where the input dimension can exceed the number of samples. We analyze a Perceptron-type algorithm called GLM-tron (Kakade et al., 2011) and provide its dimension-free risk upper bounds for high-dimensional ReLU regression in both well-specified and misspecified settings. Our risk bounds recover several existing results as special cases. Moreover, in the well-specified setting, we provide an instance-wise matching risk lower bound for GLM-tron. Our upper and lower risk bounds provide a sharp characterization of the high-dimensional ReLU regression problems that can be learned via GLM-tron. On the other hand, we provide some negative results for stochastic gradient descent (SGD) for ReLU regression with symmetric Bernoulli data: if the model is well-specified, the excess risk of SGD is provably no better than that of GLM-tron ignoring constant factors, for each problem instance; and in the noiseless case, GLM-tron can achieve a small risk while SGD unavoidably suffers from a constant risk in expectation. These results together suggest that GLM-tron might be preferable to SGD for high-dimensional ReLU regression.