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

Abstract

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.

Updating acknowledgments; Journal version

References in corpus (4)

• Distributed learning with regularized least squares
• On the Sample Complexity of Subspace Learning
• Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms
• Optimal rates for the regularized learning algorithms under general source condition

Cited by in corpus (22)

• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• On Fast Leverage Score Sampling and Optimal Learning
• Convergence analysis of Tikhonov regularization for non-linear statistical inverse learning problems
• Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
• On regularized polynomial functional regression
• Implicit Regularization of Accelerated Methods in Hilbert Spaces
• Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration
• Kernel Conjugate Gradient Methods with Random Projections
• Error Scaling Laws for Kernel Classification under Source and Capacity Conditions
• Beating SGD Saturation with Tail-Averaging and Minibatching
• Inverse learning in Hilbert scales
• Fast rates in structured prediction
• Stochastic Gradient Descent in Hilbert Scales: Smoothness, Preconditioning and Earlier Stopping
• Nonparametric approximation of conditional expectation operators
• Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces
• Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay
• Overcoming the curse of dimensionality with Laplacian regularization in semi-supervised learning
• Comparing Classes of Estimators: When does Gradient Descent Beat Ridge Regression in Linear Models?
• Online nonparametric regression with Sobolev kernels
• Data splitting improves statistical performance in overparametrized regimes
• Reducing training time by efficient localized kernel regression
• Sobolev Norm Learning Rates for Conditional Mean Embeddings