mlsanityData to 14 Oct 2026

Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces

arXiv 1801.06720 ↗First posted 20 Jan 2018stat.ML cs.LG math.FAcited by 59

Not on the map. Why?

Abstract (arXiv)

In this paper, we study regression problems over a separable Hilbert space with the square loss, covering non-parametric regression over a reproducing kernel Hilbert space. We investigate a class of spectral/regularized algorithms, including ridge regression, principal component regression, and gradient methods. We prove optimal, high-probability convergence results in terms of variants of norms for the studied algorithms, considering a capacity assumption on the hypothesis space and a general source condition on the target function. Consequently, we obtain almost sure convergence results with optimal rates. Our results improve and generalize previous results, filling a theoretical gap for the non-attainable cases.

Key facts. Cited by 59 papers in the map (data through 14 Oct 2026). First posted on arXiv 20 Jan 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 9; 2022: 8; 2023: 15; 2024: 12; 2025: 10; 2026: 5.

59 papers.

Sort:

  1. 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 96
  2. 2022Optimal Rates for Regularized Conditional Mean Embedding Learningcited by 50
  3. 2023The SSL Interplay: Augmentations, Inductive Bias, and Generalizationcited by 40
  4. 2023On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domainscited by 31
  5. 2023Generalization Ability of Wide Neural Networks on ℝcited by 30
  6. 2022Learning linear operators: Infinite-dimensional regression as a well-behaved non-compact inverse problemcited by 28
  7. 2023On the Optimality of Misspecified Spectral Algorithmscited by 28
  8. 2023Generalization in Kernel Regression Under Realistic Assumptionscited by 27
  9. 2021Learning the optimal Tikhonov regularizer for inverse problemscited by 26
  10. 2023Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithmcited by 22
  11. 2023On the Optimality of Misspecified Kernel Ridge Regressioncited by 20
  12. 2023On the Asymptotic Learning Curves of Kernel Ridge Regression under Power-law Decaycited by 19
38 more
  1. 2022Error Scaling Laws for Kernel Classification under Source and Capacity Conditionscited by 17
  2. 2024On the Saturation Effect of Kernel Ridge Regressioncited by 13
  3. 2024Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithmscited by 12
  4. 2021Fast rates in structured predictioncited by 11
  5. 2022Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descentcited by 11
  6. 2023Optimal Rate of Kernel Regression in Large Dimensionscited by 11
  7. 2024Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decaycited by 11
  8. 2023Marginal Density Ratio for Off-Policy Evaluation in Contextual Banditscited by 9
  9. 2022Statistical Optimality of Divide and Conquer Kernel-based Functional Linear Regressioncited by 8
  10. 2024Nonparametric Instrumental Regression via Kernel Methods is Minimax Optimalcited by 8
  11. 2021Sobolev Norm Learning Rates for Conditional Mean Embeddingscited by 7
  12. 2021Data splitting improves statistical performance in overparametrized regimescited by 6
  13. 2021Radial Basis Function Approximation with Distributively Stored Data on Spherescited by 6
  14. 2021Online nonparametric regression with Sobolev kernelscited by 5
  15. 2021Comparing Classes of Estimators: When does Gradient Descent Beat Ridge Regression in Linear Models?cited by 5
  16. 2023Generalization Ability of Wide Residual Networkscited by 5
  17. 2023Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalizationcited by 5
  18. 2024Overcoming Saturation in Density Ratio Estimation by Iterated Regularizationcited by 5
  19. 2021From inexact optimization to learning via gradient concentrationcited by 4
  20. 2025Learning Curves of Stochastic Gradient Descent in Kernel Regressioncited by 4
  21. 2022Dimensionality Reduction and Wasserstein Stability for Kernel Regressioncited by 3
  22. 2022A Case of Exponential Convergence Rates for SVMcited by 3
  23. 2024Optimal Rates and Saturation for Noiseless Kernel Ridge Regressioncited by 3
  24. 2024Improving Adaptivity via Over-Parameterization in Sequence Modelscited by 3
  25. 2025Divergence of Empirical Neural Tangent Kernel in Classification Problemscited by 3
  26. 2025Turbocharging Gaussian Process Inference with Approximate Sketch-and-Projectcited by 3
  27. 2025Regularized least squares learning with heavy-tailed noise is minimax optimalcited by 3
  28. 2025Spectral Algorithms in Misspecified Regression: Convergence under Covariate Shiftcited by 3
  29. 2022Optimal Learning Rates for Regularized Least-Squares with a Fourier Capacity Conditioncited by 2
  30. 2023Adaptive Distributed Kernel Ridge Regression: A Feasible Distributed Learning Scheme for Data Siloscited by 2
  31. 2024Spectrally Transformed Kernel Regressioncited by 2
  32. 2024On the Pinsker bound of inner product kernel regression in large dimensionscited by 2
  33. 2025Fixed-Gaussian Spectral Algorithms: Minimax Optimal Rates for Misspecified Learning and Transfercited by 2
  34. 2025On the Saturation Effects of Spectral Algorithms in Large Dimensionscited by 2
  35. 2025Random feature approximation for general spectral methodscited by 2
  36. 2023On regularized polynomial functional regressioncited by 1
  37. 2024Generalization error of spectral algorithmscited by 1
  38. 2025Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr"om Methodcited by 1

50 most cited of 59 All 59 (JSON)