mlsanityData to 7 Oct 2026

On the Optimality of Misspecified Spectral Algorithms

arXiv 2303.14942 ↗First posted 27 Mar 2023math.ST cs.LG stat.THcited by 28

Not on the map. Why?

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.

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

Builds on

17 of 50 references.

References · 17

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  3. 2020Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networkscited by 200
  4. 2017Sobolev Norm Learning Rates for Regularized Least-Squares Algorithmcited by 113
  5. 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 95
  6. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
  7. 2016Optimal Rates For Regularization Of Statistical Inverse Learning Problemscited by 68
  8. 2013Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Ratescited by 64
  9. 2018Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spacescited by 59
  10. 2022Optimal Rates for Regularized Conditional Mean Embedding Learningcited by 50
  11. 2016Distributed learning with regularized least squarescited by 42
  12. 2018Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithmscited by 22
5 more
  1. 2020Analyzing the discrepancy principle for kernelized spectral filter learning algorithmscited by 15
  2. 2019Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Accelerationcited by 12
  3. 2016Optimal rates for the regularized learning algorithms under general source conditioncited by 11
  4. 2022Statistical Optimality of Divide and Conquer Kernel-based Functional Linear Regressioncited by 8
  5. 2022Optimal Learning Rates for Regularized Least-Squares with a Fourier Capacity Conditioncited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 14; 2025: 6; 2026: 3.

28 papers.

Sort:

  1. 2023On the Asymptotic Learning Curves of Kernel Ridge Regression under Power-law Decaycited by 19
  2. 2023Kernel interpolation generalizes poorlycited by 16
  3. 2024Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrumcited by 13
  4. 2024Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithmscited by 12
  5. 2023Optimal Rate of Kernel Regression in Large Dimensionscited by 10
  6. 2024Optimal Rates of Kernel Ridge Regression under Source Condition in Large Dimensionscited by 9
  7. 2024Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decaycited by 8
  8. 2024The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimizationcited by 6
  9. 2024A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regressioncited by 6
  10. 2023Generalization Ability of Wide Residual Networkscited by 5
  11. 2024On the Impacts of the Random Initialization in the Neural Tangent Kernel Theorycited by 5
  12. 2024Optimal Rates and Saturation for Noiseless Kernel Ridge Regressioncited by 3
16 more
  1. 2025Regularized least squares learning with heavy-tailed noise is minimax optimalcited by 3
  2. 2025Learning Curves of Stochastic Gradient Descent in Kernel Regressioncited by 3
  3. 2025Spectral Algorithms in Misspecified Regression: Convergence under Covariate Shiftcited by 3
  4. 2024Improving Adaptivity via Over-Parameterization in Sequence Modelscited by 2
  5. 2025Fixed-Gaussian Spectral Algorithms: Minimax Optimal Rates for Misspecified Learning and Transfercited by 2
  6. 2025Random feature approximation for general spectral methodscited by 2
  7. 2024Spectral Algorithms on Manifolds through Diffusioncited by 1
  8. 2024On the Pinsker bound of inner product kernel regression in large dimensionscited by 1
  9. 2024A Kernel Perspective on Distillation-based Collaborative Learningcited by 1
  10. 2023Random feature approximation for general spectral methodscited by 0
  11. 2024Diffusion-based Semi-supervised Spectral Algorithm for Regression on Manifoldscited by 0
  12. 2024Towards a Statistical Understanding of Neural Networks: Beyond the Neural Tangent Kernel Theoriescited by 0
  13. 2025Sobolev norm inconsistency of kernel interpolationcited by 0
  14. 2026Random Features for Operator-Valued Kernels: Bridging Kernel Methods and Neural Operatorscited by 0
  15. 2026Adversarial Robustness of NTK Neural Networkscited by 0
  16. 2026When Kernel Ridge Regression Meets the H"older-Zygmund Class: Minimax Optimality and Failure of Propernesscited by 0