# On the Optimality of Misspecified Spectral Algorithms

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 50 references that are in the map.
- First posted on arXiv 27 Mar 2023.

## Builds on (most cited first, 17 of 17)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks](https://mlsanity.com/paper/2002.02561/) (2020)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes](https://mlsanity.com/paper/1805.10074/) (2018)
- [Optimal Rates For Regularization Of Statistical Inverse Learning Problems](https://mlsanity.com/paper/1604.04054/) (2016)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces](https://mlsanity.com/paper/1801.06720/) (2018)
- [Optimal Rates for Regularized Conditional Mean Embedding Learning](https://mlsanity.com/paper/2208.01711/) (2022)
- [Distributed learning with regularized least squares](https://mlsanity.com/paper/1608.03339/) (2016)
- [Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms](https://mlsanity.com/paper/1801.07226/) (2018)
- [Analyzing the discrepancy principle for kernelized spectral filter learning algorithms](https://mlsanity.com/paper/2004.08436/) (2020)
- [Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration](https://mlsanity.com/paper/1905.10680/) (2019)
- [Optimal rates for the regularized learning algorithms under general source condition](https://mlsanity.com/paper/1611.01900/) (2016)
- [Statistical Optimality of Divide and Conquer Kernel-based Functional Linear Regression](https://mlsanity.com/paper/2211.10968/) (2022)
- [Optimal Learning Rates for Regularized Least-Squares with a Fourier Capacity Condition](https://mlsanity.com/paper/2204.07856/) (2022)

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

- [On the Asymptotic Learning Curves of Kernel Ridge Regression under Power-law Decay](https://mlsanity.com/paper/2309.13337/) (2023)
- [Kernel interpolation generalizes poorly](https://mlsanity.com/paper/2303.15809/) (2023)
- [Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum](https://mlsanity.com/paper/2402.01297/) (2024)
- [Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms](https://mlsanity.com/paper/2405.14778/) (2024)
- [Optimal Rate of Kernel Regression in Large Dimensions](https://mlsanity.com/paper/2309.04268/) (2023)
- [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 Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization](https://mlsanity.com/paper/2409.09745/) (2024)
- [A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression](https://mlsanity.com/paper/2410.17796/) (2024)
- [Generalization Ability of Wide Residual Networks](https://mlsanity.com/paper/2305.18506/) (2023)
- [On the Impacts of the Random Initialization in the Neural Tangent Kernel Theory](https://mlsanity.com/paper/2410.05626/) (2024)
- [Learning Curves of Stochastic Gradient Descent in Kernel Regression](https://mlsanity.com/paper/2505.22048/) (2025)
- [Optimal Rates and Saturation for Noiseless Kernel Ridge Regression](https://mlsanity.com/paper/2402.15718/) (2024)
- [Improving Adaptivity via Over-Parameterization in Sequence Models](https://mlsanity.com/paper/2409.00894/) (2024)
- [Regularized least squares learning with heavy-tailed noise is minimax optimal](https://mlsanity.com/paper/2505.14214/) (2025)
- [Spectral Algorithms in Misspecified Regression: Convergence under Covariate Shift](https://mlsanity.com/paper/2509.05106/) (2025)
- [On the Pinsker bound of inner product kernel regression in large dimensions](https://mlsanity.com/paper/2409.00915/) (2024)
- [Fixed-Gaussian Spectral Algorithms: Minimax Optimal Rates for Misspecified Learning and Transfer](https://mlsanity.com/paper/2501.10870/) (2025)
- [Random feature approximation for general spectral methods](https://mlsanity.com/paper/2506.16283/) (2025)
- [Spectral Algorithms on Manifolds through Diffusion](https://mlsanity.com/paper/2403.03669/) (2024)
- [A Kernel Perspective on Distillation-based Collaborative Learning](https://mlsanity.com/paper/2410.17592/) (2024)
- [Random Features for Operator-Valued Kernels: Bridging Kernel Methods and Neural Operators](https://mlsanity.com/paper/2603.00971/) (2026)
- [Random feature approximation for general spectral methods](https://mlsanity.com/paper/2308.15434/) (2023)
- [Diffusion-based Semi-supervised Spectral Algorithm for Regression on Manifolds](https://mlsanity.com/paper/2410.14539/) (2024)
- [Towards a Statistical Understanding of Neural Networks: Beyond the Neural Tangent Kernel Theories](https://mlsanity.com/paper/2412.18756/) (2024)
- [Sobolev norm inconsistency of kernel interpolation](https://mlsanity.com/paper/2504.20617/) (2025)
- [Adversarial Robustness of NTK Neural Networks](https://mlsanity.com/paper/2604.25965/) (2026)
- [When Kernel Ridge Regression Meets the H"older-Zygmund Class: Minimax Optimality and Failure of Properness](https://mlsanity.com/paper/2607.26065/) (2026)

## Abstract (arXiv)

In the misspecified spectral algorithms problem, researchers usually assume the underground true function fρ* ∈ [H]s, a less-smooth interpolation space of a reproducing kernel Hilbert space (RKHS) H for some s∈ (0,1). The existing minimax optimal results require |fρ*|_L∞<∞ which implicitly requires s > α0 where α0∈ (0,1) is the embedding index, a constant depending on H. Whether the spectral algorithms are optimal for all s∈ (0,1) is an outstanding problem lasting for years. In this paper, we show that spectral algorithms are minimax optimal for any α0-frac1β < s < 1, where β is the eigenvalue decay rate of H. We also give several classes of RKHSs whose embedding index satisfies  α0 = frac1β . Thus, the spectral algorithms are minimax optimal for all s∈ (0,1) on these RKHSs.