# Optimal Rate of Kernel Regression in Large Dimensions

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

## 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 (most cited first, 30 of 42)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [On the Inductive Bias of Neural Tangent Kernels](https://mlsanity.com/paper/1905.12173/) (2019)
- [Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks](https://mlsanity.com/paper/2006.13198/) (2020)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [Harmless interpolation of noisy data in regression](https://mlsanity.com/paper/1903.09139/) (2019)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces](https://mlsanity.com/paper/1801.06720/) (2018)
- [Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression](https://mlsanity.com/paper/2204.10425/) (2022)
- [How benign is benign overfitting?](https://mlsanity.com/paper/2007.04028/) (2020)
- [Kernel regression in high dimensions: Refined analysis beyond double descent](https://mlsanity.com/paper/2010.02681/) (2020)
- [Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network](https://mlsanity.com/paper/2007.02486/) (2020)

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

- [Optimal Rates of Kernel Ridge Regression under Source Condition in Large Dimensions](https://mlsanity.com/paper/2401.01270/) (2024)
- [Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay](https://mlsanity.com/paper/2401.01599/) (2024)
- [The phase diagram of kernel interpolation in large dimensions](https://mlsanity.com/paper/2404.12597/) (2024)
- [High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularization](https://mlsanity.com/paper/2406.03171/) (2024)
- [Learning Curves of Stochastic Gradient Descent in Kernel Regression](https://mlsanity.com/paper/2505.22048/) (2025)
- [On the Pinsker bound of inner product kernel regression in large dimensions](https://mlsanity.com/paper/2409.00915/) (2024)
- [On the Saturation Effects of Spectral Algorithms in Large Dimensions](https://mlsanity.com/paper/2503.00504/) (2025)
- [Towards a Statistical Understanding of Neural Networks: Beyond the Neural Tangent Kernel Theories](https://mlsanity.com/paper/2412.18756/) (2024)
- [Learning Curves and Benign Overfitting of Spectral Algorithms in Large Dimensions](https://mlsanity.com/paper/2604.23212/) (2026)
- [Large Dimensional Kernel Ridge Regression: Extending to Product Kernels](https://mlsanity.com/paper/2605.14524/) (2026)
- [Benign Overfitting for General Norms and Distributions](https://mlsanity.com/paper/2609.33675/) (2026)

## 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.