mlsanityData to 7 Oct 2026

Uniform Generalization Bounds for Overparameterized Neural Networks

arXiv 2109.06099 ↗First posted 13 Sep 2021cs.LG stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

An interesting observation in artificial neural networks is their favorable generalization error despite typically being extremely overparameterized. It is well known that the classical statistical learning methods often result in vacuous generalization errors in the case of overparameterized neural networks. Adopting the recently developed Neural Tangent (NT) kernel theory, we prove uniform generalization bounds for overparameterized neural networks in kernel regimes, when the true data generating model belongs to the reproducing kernel Hilbert space (RKHS) corresponding to the NT kernel. Importantly, our bounds capture the exact error rates depending on the differentiability of the activation functions. In order to establish these bounds, we propose the information gain of the NT kernel as a measure of complexity of the learning problem. Our analysis uses a Mercer decomposition of the NT kernel in the basis of spherical harmonics and the decay rate of the corresponding eigenvalues. As a byproduct of our results, we show the equivalence between the RKHS corresponding to the NT kernel and its counterpart corresponding to the Mat'ern family of kernels, showing the NT kernels induce a very general class of models. We further discuss the implications of our analysis for some recent results on the regret bounds for reinforcement learning and bandit algorithms, which use overparameterized neural networks.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 26 of its 49 references that are in the map. First posted on arXiv 13 Sep 2021.

Builds on

26 of 49 references.

References · 26

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2020Implicit Neural Representations with Periodic Activation Functionscited by 2,214
  4. 2018On Lazy Training in Differentiable Programmingcited by 671
  5. 2017Deep Neural Networks as Gaussian Processescited by 617
  6. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  7. 2018Gaussian Process Behaviour in Wide Deep Neural Networkscited by 314
  8. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  9. 2020Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networkscited by 200
  10. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 188
  11. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  12. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
14 more
  1. 2019Neural Tangents: Fast and Easy Infinite Neural Networks in Pythoncited by 149
  2. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  3. 2019The Convergence Rate of Neural Networks for Learned Functions of Different Frequenciescited by 134
  4. 2020On the linearity of large non-linear models: when and why the tangent kernel is constantcited by 129
  5. 2020Neural Thompson Samplingcited by 127
  6. 2020Deep Equals Shallow for ReLU Networks in Kernel Regimescited by 83
  7. 2020Mat'ern Gaussian processes on Riemannian manifoldscited by 82
  8. 2020On the Similarity between the Laplace and Neural Tangent Kernelscited by 76
  9. 2020Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHScited by 74
  10. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  11. 2020Sparse Gaussian Processes with Spherical Harmonic Featurescited by 43
  12. 2020Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Networkcited by 38
  13. 2021Batched Neural Banditscited by 22
  14. 2021A Short Note on the Relationship of Information Gain and Eluder Dimensioncited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 8; 2024: 1; 2025: 5; 2026: 1.

21 papers.

Sort:

  1. 2024PINNACLE: PINN Adaptive ColLocation and Experimental points selectioncited by 31
  2. 2022LieGG: Studying Learned Lie Group Generatorscited by 28
  3. 2023Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimensioncited by 26
  4. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  5. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  6. 2022Federated Neural Banditscited by 17
  7. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  8. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  9. 2023Delayed Feedback in Kernel Banditscited by 10
  10. 2022Wide Bayesian neural networks have a simple weight posterior: theory and accelerated samplingcited by 9
  11. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  12. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
9 more
  1. 2022Provably and Practically Efficient Neural Contextual Banditscited by 6
  2. 2023Adaptation to Misspecified Kernel Regularity in Kernelised Banditscited by 5
  3. 2023Training-Free Neural Active Learning with Initialization-Robustness Guaranteescited by 5
  4. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  5. 2025Determinant Estimation under Memory Constraints and Neural Scaling Lawscited by 3
  6. 2025Beyond ReLU: How Activations Affect Neural Kernels and Random Wide Networkscited by 3
  7. 2023Sparsity-depth Tradeoff in Infinitely Wide Deep Neural Networkscited by 0
  8. 2023Optimization dependent generalization bound for ReLU networks based on sensitivity in the tangent bundlecited by 0
  9. 2025Spectral Estimation with Free Decompressioncited by 0