mlsanityData to 7 Oct 2026

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

arXiv 2303.02255 ↗First posted 3 Mar 2023cs.LG math.OC stat.MLcited by 8

Not on the map. Why?

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.

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

Builds on

22 of 32 references.

References · 22

  1. 2019Benign Overfitting in Linear Regressioncited by 544
  2. 2020Benign overfitting in ridge regressioncited by 152
  3. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  4. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  5. 2019The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squarescited by 67
  6. 2017Learning ReLUs via Gradient Descentcited by 54
  7. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
  8. 2020Learning a Single Neuron with Gradient Methodscited by 50
  9. 2022Dimension free ridge regressioncited by 50
  10. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  11. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  12. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 37
10 more
  1. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  2. 2020Approximation Schemes for ReLU Regressioncited by 34
  3. 2019Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginalscited by 32
  4. 2021The Benefits of Implicit Regularization from SGD in Least Squares Problemscited by 32
  5. 2022The Power and Limitation of Pretraining-Finetuning for Linear Regression under Covariate Shiftcited by 25
  6. 2020On Uniform Convergence and Low-Norm Interpolation Learningcited by 24
  7. 2017When is a Convolutional Filter Easy To Learn?cited by 21
  8. 2022Learning a Single Neuron with Adversarial Label Noise via Gradient Descentcited by 20
  9. 2021Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regressioncited by 17
  10. 2022A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Modelscited by 11

Built on by

Cited by year

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

8 papers.

  1. 2023How Many Pretraining Tasks Are Needed for In-Context Learning of Linear Regression?cited by 93
  2. 2023Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Timecited by 20
  3. 2025Seesaw: Accelerating Training by Balancing Learning Rate and Batch Size Schedulingcited by 5
  4. 2025A Simplified Analysis of SGD for Linear Regression with Weight Averagingcited by 4
  5. 2025Nearly Optimal Differentially Private ReLU Regressioncited by 3
  6. 2024Improving Implicit Regularization of SGD with Preconditioning for Least Square Problemscited by 2
  7. 2025On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networkscited by 2
  8. 2024Dimension-free uniform concentration bound for logistic regressioncited by 1