mlsanityData to 14 Oct 2026

Optimal Rate of Kernel Regression in Large Dimensions

arXiv 2309.04268 ↗First posted 8 Sep 2023stat.ML cs.LG math.STcited by 11

Not on the map. Why?

Abstract (arXiv)

We perform a study on kernel regression for large-dimensional data (where the sample size n is polynomially depending on the dimension d of the samples, i.e., nasymp dγ for some γ >0 ). We first build a general tool to characterize the upper bound and the minimax lower bound of kernel regression for large dimensional data through the Mendelson complexity varepsilonn2 and the metric entropy barvarepsilonn2 respectively. When the target function falls into the RKHS associated with a (general) inner product model defined on mathbbSd, we utilize the new tool to show that the minimax rate of the excess risk of kernel regression is n-1/2 when nasymp dγ for γ =2, 4, 6, 8, cdots. We then further determine the optimal rate of the excess risk of kernel regression for all the γ>0 and find that the curve of optimal rate varying along γ exhibits several new phenomena including the multiple descent behavior and the periodic plateau behavior. As an application, For the neural tangent kernel (NTK), we also provide a similar explicit description of the curve of optimal rate. As a direct corollary, we know these claims hold for wide neural networks as well.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 42 of its 79 references that are in the map. First posted on arXiv 8 Sep 2023.

Builds on

42 of 79 references.

References · 42

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2014ImageNet Large Scale Visual Recognition Challengecited by 8,498
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  5. 2018On Lazy Training in Differentiable Programmingcited by 675
  6. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  7. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  8. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 573
  9. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  10. 2019Benign Overfitting in Linear Regressioncited by 549
  11. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
  12. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
30 more
  1. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  2. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  3. 2019On the Inductive Bias of Neural Tangent Kernelscited by 177
  4. 2020Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networkscited by 166
  5. 2019Linearized two-layers neural networks in high dimensioncited by 155
  6. 2020Benign overfitting in ridge regressioncited by 153
  7. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
  8. 2019Harmless interpolation of noisy data in regressioncited by 121
  9. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  10. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 91
  11. 2013Early stopping and non-parametric regression: An optimal data-dependent stopping rulecited by 89
  12. 2021Learning with invariances in random features and kernel modelscited by 89
  13. 2020Deep Equals Shallow for ReLU Networks in Kernel Regimescited by 85
  14. 2018Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spacescited by 59
  15. 2022Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regressioncited by 45
  16. 2020How benign is benign overfitting?cited by 40
  17. 2020Kernel regression in high dimensions: Refined analysis beyond double descentcited by 39
  18. 2020Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Networkcited by 38
  19. 2022Benign, Tempered, or Catastrophic: A Taxonomy of Overfittingcited by 36
  20. 2021How rotational invariance of common kernels prevents generalization in high dimensionscited by 32
  21. 2023On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domainscited by 31
  22. 2023Generalization Ability of Wide Neural Networks on ℝcited by 30
  23. 2023On the Optimality of Misspecified Spectral Algorithmscited by 28
  24. 2021The Three Stages of Learning Dynamics in High-Dimensional Kernel Methodscited by 22
  25. 2022Precise Learning Curves and Higher-Order Scaling Limits for Dot Product Kernel Regressioncited by 22
  26. 2021Learning with convolution and pooling operations in kernel methodscited by 21
  27. 2023On the Optimality of Misspecified Kernel Ridge Regressioncited by 20
  28. 2023Kernel interpolation generalizes poorlycited by 16
  29. 2023Strong inductive biases provably prevent harmless interpolationcited by 10
  30. 2022Kernel Methods and Multi-layer Perceptrons Learn Linear Models in High Dimensionscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 6; 2025: 2; 2026: 3.

11 papers.

  1. 2024Optimal Rates of Kernel Ridge Regression under Source Condition in Large Dimensionscited by 11
  2. 2024Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decaycited by 11
  3. 2024The phase diagram of kernel interpolation in large dimensionscited by 9
  4. 2024High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularizationcited by 4
  5. 2025Learning Curves of Stochastic Gradient Descent in Kernel Regressioncited by 4
  6. 2024On the Pinsker bound of inner product kernel regression in large dimensionscited by 2
  7. 2025On the Saturation Effects of Spectral Algorithms in Large Dimensionscited by 2
  8. 2024Towards a Statistical Understanding of Neural Networks: Beyond the Neural Tangent Kernel Theoriescited by 0
  9. 2026Learning Curves and Benign Overfitting of Spectral Algorithms in Large Dimensionscited by 0
  10. 2026Large Dimensional Kernel Ridge Regression: Extending to Product Kernelscited by 0
  11. 2026Benign Overfitting for General Norms and Distributionscited by 0