mlsanityData to 14 Oct 2026

Learning Lipschitz Functions by GD-trained Shallow Overparameterized ReLU Neural Networks

arXiv 2212.13848 ↗First posted 28 Dec 2022cs.LG stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

We explore the ability of overparameterized shallow ReLU neural networks to learn Lipschitz, nondifferentiable, bounded functions with additive noise when trained by Gradient Descent (GD). To avoid the problem that in the presence of noise, neural networks trained to nearly zero training error are inconsistent in this class, we focus on the early-stopped GD which allows us to show consistency and optimal rates. In particular, we explore this problem from the viewpoint of the Neural Tangent Kernel (NTK) approximation of a GD-trained finite-width neural network. We show that whenever some early stopping rule is guaranteed to give an optimal rate (of excess risk) on the Hilbert space of the kernel induced by the ReLU activation function, the same rule can be used to achieve minimax optimal rate for learning on the class of considered Lipschitz functions by neural networks. We discuss several data-free and data-dependent practically appealing stopping rules that yield optimal rates.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 29 of its 54 references that are in the map. First posted on arXiv 28 Dec 2022.

Builds on

29 of 54 references.

References · 29

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  3. 2017Spectrally-normalized margin bounds for neural networkscited by 686
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  5. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  6. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  7. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
  8. 2017Size-Independent Sample Complexity of Neural Networkscited by 290
  9. 2021Deep learning: a statistical viewpointcited by 240
  10. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
  11. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  12. 2016Generalization Properties of Learning with Random Featurescited by 164
17 more
  1. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  2. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  3. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 121
  4. 2018Does data interpolation contradict statistical optimality?cited by 95
  5. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  6. 2013Early stopping and non-parametric regression: An optimal data-dependent stopping rulecited by 89
  7. 2020Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networkscited by 87
  8. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
  9. 2018Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenoncited by 44
  10. 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
  11. 2020Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Networkcited by 38
  12. 2021Subquadratic Overparameterization for Shallow Neural Networkscited by 26
  13. 2020Analyzing the discrepancy principle for kernelized spectral filter learning algorithmscited by 15
  14. 2021Deep Network Approximation in Terms of Intrinsic Parameterscited by 12
  15. 2021A spectral-based analysis of the separation between two-layer neural networks and linear methodscited by 7
  16. 2021Online nonparametric regression with Sobolev kernelscited by 5
  17. 2022Improved Convergence Guarantees for Shallow Neural Networkscited by 1

Built on by

Cited by year (2026 to 14 Oct)

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

5 papers.

  1. 2024Neural Network-Based Score Estimation in Diffusion Models: Optimization and Generalizationcited by 42
  2. 2024Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalizationcited by 8
  3. 2025Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classificationcited by 3
  4. 2023Fine-grained Analysis of Non-parametric Estimation for Pairwise Learningcited by 2
  5. 2026Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networkscited by 0