Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm

Abstract

Learning rates for least-squares regression are typically expressed in terms of $L_2$-norms. In this paper we extend these rates to norms stronger than the $L_2$-norm without requiring the regression function to be contained in the hypothesis space. In the special case of Sobolev reproducing kernel Hilbert spaces used as hypotheses spaces, these stronger norms coincide with fractional Sobolev norms between the used Sobolev space and $L_2$. As a consequence, not only the target function but also some of its derivatives can be estimated without changing the algorithm. From a technical point of view, we combine the well-known integral operator techniques with an embedding property, which so far has only been used in combination with empirical process arguments. This combination results in new finite sample bounds with respect to the stronger norms. From these finite sample bounds our rates easily follow. Finally, we prove the asymptotic optimality of our results in many cases.

accepted manuscript in J. Mach. Learn. Res

References in corpus (3)

• Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
• Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
• Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms

Cited by in corpus (14)

• Kernel regression in high dimensions: Refined analysis beyond double descent
• Minimax Linear Estimation of the Retargeted Mean
• Convergence Guarantees for Gaussian Process Means With Misspecified Likelihoods and Smoothness
• Kernel Methods for Unobserved Confounding: Negative Controls, Proxies, and Instruments
• On the convergence of PINNs
• A Spectral Analysis of Dot-product Kernels
• Stochastic Gradient Descent Meets Distribution Regression
• Stochastic Gradient Descent in Hilbert Scales: Smoothness, Preconditioning and Earlier Stopping
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization
• How isotropic kernels perform on simple invariants
• Recovery of a Time-Dependent Bottom Topography Function from the Shallow Water Equations via an Adjoint Approach
• Online nonparametric regression with Sobolev kernels
• Sobolev Norm Learning Rates for Conditional Mean Embeddings
• Reducing training time by efficient localized kernel regression