Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm

Simon Fischer; Ingo Steinwart

Source-linked AI summary

Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm

Simon Fischer, Ingo Steinwart

arXiv:1702.07254v3Feb 23, 2017stat.ML

TL;DR

Least-squares learning rates are usually stated in L2, leaving stronger-norm guarantees largely unavailable when the regression function is outside the hypothesis space. This paper combines integral-operator techniques with an embedding property to derive stronger-norm finite-sample bounds and rates, including hard-learning settings. It obtains first L∞ rates in that setting and proves minimax optimality for many [H]γ-norm cases.

Problem
Least-squares regression lacks learning-rate guarantees in norms stronger than L2, particularly when the regression function is not contained in the hypothesis space.
Method
The paper combines integral-operator techniques with an RKHS embedding property to derive finite-sample bounds and learning rates on a continuous scale of stronger norms.
Results
The paper obtains the first L∞-norm learning rates in the hard-learning scenario and proves minimax optimality of [H]γ-norm rates whenever optimal L2 rates are known.
Takeaways & Limitations
For Sobolev/Besov RKHSs, the stronger norms correspond to fractional Sobolev or Besov norms, allowing estimation of the target and some derivatives without changing the algorithm.
Takeaways & Limitations
The paper does not resolve the outstanding problem of establishing the relevant optimal rates in every setting.

Abstract

from arXiv · show

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.

1. Introduction

The paper extends least-squares learning-rate analysis from L2 to a continuous scale of stronger norms, including hard-learning settings where the regression function lies outside the hypothesis space. It combines integral-operator and embedding techniques to obtain improved bounds, derivative-related Sobolev interpretations, and optimality results.

Problem setup: Least-squares support vector machines construct a predictor by minimizing empirical squared loss plus RKHS-norm regularization.The hypothesis space is an RKHS H, and λ > 0 is the regularization parameter.
Research gap: The paper studies learning rates in norms from a continuous scale of Hilbert spaces [H]γ between H and L2.The scale is arranged so that [H]0 = L2 and [H]1 = H for the introduction.
Research gap: Existing empirical-process techniques handled only L2 rates, while integral-operator methods covered continuous γ-scales but rarely the hard-learning case f* not in H.The paper identifies the combination of embedding properties with integral-operator techniques as underused.
Approach: The authors combine the integral-operator technique with an RKHS embedding property to extend and improve stronger-norm learning rates in hard learning scenarios.The embedding property improves a bound on the L∞-norm of the regularized population predictor.
Results: The results include the first L∞ learning rates for the hard-learning scenario and recover previously obtained optimal L2 rates.They also extend prior results from f* ∈ H to f* outside H and obtain faster convergence under a suitable embedding property.
Results: For Sobolev/Besov RKHSs, the intermediate norms coincide with classical Besov spaces and admit an interpretation in terms of derivatives.The paper proves minimax optimality of these [H]γ-norm rates whenever the corresponding optimal L2 rates are known.

2. Preliminaries

The preliminaries define the regression setting, RKHS-to-L2 operators, their spectral structure, and intermediate power spaces used to formulate stronger-norm rates.

Regression setting: The input space is measurable, the output space is R, and ν = PX denotes the marginal distribution on X.The regression function is specified through a regular conditional probability and is uniquely determined only ν-almost everywhere.
RKHS and operators: The paper fixes a separable RKHS H over X with a bounded measurable kernel and studies its relation to L2(ν).The embedding Iν maps f ∈ H to its L2(ν) equivalence class and need not be injective.
RKHS and operators: The operators Tν = IνSν on L2(ν) and Cν = SνIν on H are self-adjoint, positive semidefinite, and trace class.Their spectral theorem yields eigenvalues and eigenfunctions whose L2(ν) classes form an orthonormal basis.
Power spaces: Power spaces [H]α interpolate between L2(ν) and H and are defined through fractional integral operators and interpolation spaces.For α = 1, the norm agrees with the RKHS norm on the orthogonal complement of ker Iν.
Power spaces: For Sobolev/Besov RKHSs with essentially uniform marginal distributions, these interpolation spaces are related to familiar Besov spaces with equivalent norms.This supplies the functional-space interpretation used later for stronger-norm learning rates.

3. Main Results

The paper derives γ-learning rates for regularized least-squares methods in stronger-than-L2 norms under embedding, eigenvalue-decay, source, and moment conditions. It also establishes matching lower rates in many settings, while identifying unresolved optimality when α > β.

Assumptions: The embedding condition links the marginal distribution and RKHS, implies polynomial eigenvalue decay of order 1/α, and is independent of the regression function.The assumptions describe distribution–hypothesis-space interplay rather than the conditional response distribution.
γ-Learning Rates: The main theorem analyzes LS-SVM convergence in γ-power norms for 0 ≤ γ < β under (EMB), (EVD), (SRC), and (MOM).The regularization sequence and resulting rates depend on the regimes defined by β + p relative to α.
γ-Learning Rates: When β + p ≤ α, the recommended regularization scale is λ_n ≍ (n/log^r(n))^-1/α.The corresponding high-probability bound holds for sufficiently large n with probability at least 1 − 4e^-τ.
γ-Learning Rates: When β + p > α, the recommended regularization scale is λ_n ≍ n^-1/(β+p).The theorem again provides a sufficiently-large-sample bound with probability at least 1 − 4e^-τ.
γ-Learning Rates: The regularization sequence does not depend on γ, so convergence holds simultaneously for all γ-power norms with 0 ≤ γ < β.For γ = 0, these norms coincide with the L2(ν)-norm.
Optimality: Under (EVD+), the lower-rate theorem shows that no learning method can achieve a faster decay than the stated γ-learning rates.When the upper and lower rates coincide, the LS-SVM rates are optimal; optimality remains unresolved in the α > β case described in the text.

4. Example: Besov RKHSs

The Besov-RKHS example instantiates the general learning-rate theory under domain, marginal-distribution, source, moment, and smoothness conditions. It yields optimal L2 and stronger-norm rates, extending to bounded derivatives when the target is sufficiently smooth.

Besov RKHS construction: For r > d/2, Besov spaces have continuous bounded representatives, and for r > j + d/2 these representatives have bounded derivatives through order j.This embedding supplies the regularity needed to interpret stronger norms and derivative estimates.
Besov learning rates: The resulting L2-learning rate is independent of the chosen Besov RKHS, provided r > s in addition to r > d/2.The case t = 0 corresponds to L2-norm learning.
Optimality: For s > d/2, the Besov learning rates are asymptotically optimal because they match the corresponding lower rates.The lower-rate result covers all learning methods under the stated assumptions.

5. Comparison

The paper compares its learning rates with prior integral-operator and empirical-process results. Incorporating the embedding property yields rates that match or improve existing bounds and are optimal in the stated cases.

Literature comparison: The comparison covers prior results for L2-learning and general γ-learning rates, ignoring logarithmic terms for clarity.Table 1 summarizes rates, while Figure 1 plots polynomial-rate exponents over target smoothness.
Literature comparison: The authors’ rates are never worse than marked prior rates and are at least sometimes better under the compared parameter ranges.The compared results use either integral-operator or empirical-process techniques.
Integral operator techniques: Both prior integral-operator articles omit embedding properties, whereas the authors improve their rates when (EMB) holds with α < 1 and β + p < 1.The improvement is stated for the γ-learning rates of Lin et al.
Besov RKHS example: For Besov RKHSs, the authors require only r > s to attain the fastest known L2-rate n^-s/(s+d/2), whereas prior results additionally require r ≤ s + d/2.Without that prior constraint, the earlier results yield the slower rate n^-s/r, which worsens as r increases.
Empirical process techniques: Empirical-process methods recover the authors’ L2-rate with (EMB), but they do not yet provide general γ-learning rates.The influence of clipping in some prior results is unclear and may explain omitted logarithmic factors.
Summary: The paper recovers best-known, often optimal L2-rates, improves prior γ-rates under its conditions, and proves γ-rate optimality whenever optimal L2-rates are known.The improvement assumes (EMB) for some 0 < α < 1 together with (SRC), (EVD), and β + p < 1.

6. Proofs

This section develops the operator and embedding tools used in the proofs. It establishes relations among embedding, eigenvalue decay, effective dimension, γ-power norms, and the hypothesis-space norm.

Embedding properties: The authors give an alternative proof of the L∞-embedding theorem that does not require ν-completeness of the measurable space.The proof also extends to σ-finite measures and possibly unbounded kernels when the RKHS is compactly embedded into L2(ν).
Embedding and eigenvalues: The embedding condition implies eigenvalue summability and, directly, the eigenvalue-decay condition (EVD) with p = α.With uniformly bounded eigenfunctions, (EVD) for 0 < p < 1 implies (EMB) for every α > p.
Effective dimension: The effective dimension Nν(λ) connects eigenvalue decay with its asymptotic behavior as λ approaches zero.This quantity is used in the statistical analysis of least-squares support-vector machines.
Spectral tools: The proofs use spectral decompositions, Parseval identities, and operator powers of Cν + λ to control approximation and estimation terms.These representations underpin the later finite-sample error bounds.
γ-power norms: Spectral representations characterize the γ-power norm in relation to the H-norm, with equality when γ < 1 or when f is orthogonal to ker Iν.For γ = 1, the relevant quantity coincides with the H-norm under the orthogonality condition.

6.5 Lemma

The lemmas connect effective dimension and embedding assumptions to operator and function-norm bounds. These bounds provide the ingredients for controlling regularization and empirical deviations.

Effective dimension: The effective dimension is represented through the trace of a regularized covariance operator and is bounded using eigenvalue information.The displayed identity expresses the trace in terms of μ_i/(μ_i + λ) and Nν(λ).
Embedding bounds: Embedding assumptions yield L∞-type bounds for regularized kernel sections and related operator quantities.The paper explicitly identifies inequality (27) as the point where (EMB) provides the benefit.
Approximation bounds: The approximation bounds distinguish the cases γ ≤ β and γ > β when estimating the regularized target in γ-power norms.The γ > β case additionally uses an auxiliary spectral inequality.
Error control: The error control theorem bounds the estimation error under bounded-kernel and moment assumptions with high probability.For γ = 1, the left-hand side becomes the H-norm difference between empirical and population regularized solutions.
Concentration tools: The operator estimates rely on Hilbert-Schmidt representations, Bernstein-type concentration, and the embedding-based supremum bounds.The analysis controls empirical covariance deviations and related regularized operators.

6.10 Lemma

This section proves the main upper bounds and constructs lower-bound distributions. The proof combines approximation estimates with high-probability error control, while the lower-bound argument uses difficult-to-learn distributions.

Upper-bound proof: Theorem 6.8 supplies a high-probability bound for the empirical-to-population regularized estimator under the paper’s structural assumptions.Its proof decomposes the error into several factors and controls them with operator estimates.
Main learning-rate proof: The main theorem is obtained by choosing λ_n according to the cases β + p ≤ α and β + p > α, then combining approximation and estimation bounds.The proof verifies the sample-size condition and shows the remaining bracketed factor is bounded.
Lower bounds: The lower-bound construction assumes (EMB) and (EVD+) and produces probability measures that are difficult to distinguish for learning procedures.The construction applies a multiple-hypothesis lower-bound proposition using Kullback–Leibler divergence.
Lower bounds: The lower-bound result applies across specified β and γ ranges and establishes unavoidable error scales for measurable procedures.The probability measures may depend on ε, while a single marginal distribution ν with the required properties suffices.

6.12 Theorem (Lower Bound)

The lower-bound proof constructs many bounded Sobolev-compatible regression functions and associated Gaussian probability measures, then uses separation and divergence bounds to show learning is difficult for any measurable method.

Lower-bound reduction: The associated measures satisfy common-marginal and moment requirements, while the Kullback–Leibler calculation controls their pairwise statistical distinguishability.The proof then applies a measurable selector Ψ and the general reduction scheme to obtain the lower bound for an arbitrary learning method.
Probability-model construction: The construction uses Gaussian conditional distributions Pf(·|x)=N(f(x), σ̄^2) with common marginal ν on X.The measures are identified up to ν-almost-sure equality of their regression functions.
Probability-model construction: The Gaussian model satisfies the required moment condition with σ=L=σ̄.The proof reduces the condition to E|Z|^m≤m!/2 for a standard normal variable and verifies it for even and odd moments.
Candidate-function construction: Binary-string functions fω provide candidates with ∥fω∥β≤B and ∥fω∥L∞(ν)≤B∞ whenever m≤Uε^-u.Without the uniform boundedness requirement, the same construction supports u=p.
Lower-bound reduction: Choosing εn=τn^-r and Mn→∞ yields a distribution that remains difficult to learn for the considered method.For sufficiently large n, the selector-based argument establishes the required lower-bound inequality.

A. Auxiliary Results and Concentration Inequalities

The auxiliary results introduce the scalar function fλ,α(t)=t^α/(λ+t) for λ>0 and 0≤α≤1.

The function fλ,α(t)=t^α/(λ+t) is defined on [0,∞) for λ>0 and 0≤α≤1.

A.1 Lemma

The lemma characterizes monotonicity and supremum behavior of fλ,α across the endpoint and fractional cases.

For α=0, fλ,α is decreasing, while for α=1 it is increasing.
For 0<α<1, the supremum is attained at t*=λα/(1−α).
The proof uses the derivative to locate the unique critical point and bounds the resulting factor through g(α)=α^α(1−α)^(1−α).The cited argument states that g is bounded by 1 and has minimum 1/2 at α=1/2.
The lemma is used as an auxiliary analytic result alongside a Hilbert-space Bernstein inequality attributed to Pinelis and Sakhanenko.

A.2 Theorem (Bernstein’s Inequality)

This section introduces Bernstein-type concentration tools for Hilbert-space-valued and Hilbert–Schmidt-operator-valued random variables.

For τ≥1 and n≥1, the stated result provides a concentration inequality for the squared norm of a centered Hilbert-space-valued random variable.Its proof bounds moments of ξ−E_Pξ and invokes a proposition of Caponnetto and De Vito.
A separate Bernstein-type inequality is introduced for Hilbert–Schmidt operator-valued random variables.The cited version comes from Minsker-related work and is also connected to Tropp’s introduction.

A.3 Theorem

The theorem assumes a bounded self-adjoint Hilbert-Schmidt random operator whose second moment is dominated by a positive semidefinite trace-class operator. Its concentration inequality follows by applying a cited lemma to a centered variable.

The random operator is self-adjoint, Hilbert-Schmidt valued, and almost surely bounded in operator norm by B.
The covariance-type condition requires EP(ξ2) ≼ V, with V self-adjoint, positive semidefinite, and trace class.
The concentration inequality is established by applying Lemma 26 from [17] to the centered variable ξ − EPξ with δ = 2e^−τ.
The proof uses the bounds ∥ξ − EPξ∥ ≤ 2B and EP(ξ − EPξ)2 ≼ EP(ξ2) ≼ V.
The parameter β from Lemma 26 is subsequently bounded to complete the concentration argument.