Source-linked AI summary
Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, Volkan Cevher
TL;DR
Earlier spectral-algorithm results left guarantees unclear for non-attainable cases under a general source assumption. This paper analyzes spectral algorithms under capacity and source conditions, establishing optimal convergence guarantees with high probability and, as a corollary, almost surely.
Problem
Earlier results often restricted analysis to universal consistency or attainable targets, while capacity-dependently optimal rates under a general source assumption remained unclear for non-attainable cases.
Source: §1 · p. 2Method
The paper analyzes spectral algorithms under a capacity assumption and a general source condition on the target function.
Source: §1 · p. 2, §4.1 · p. 6Results
The paper establishes high-probability optimal convergence results for spectral algorithms and obtains almost-sure convergence with optimal rates as a corollary.
Source: §1 · p. 2Takeaways & Limitations
The results extend prior guarantees to non-attainable targets and a broader class of norms under a more general source assumption.
Source: §1 · p. 2, §4.3 · p. 10The analysis assumes a source condition with φ=ψϑ, where ψ is operator monotone and ϑ is Lipschitz continuous.
Source: §4.1 · p. 6
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction frames least-squares regression over a Hilbert space and positions spectral algorithms as a common approach. It identifies gaps in earlier guarantees and states optimal convergence results under a capacity assumption and a general source condition.
1 Introduction
- The regression target fH is the projection of the regression function onto the closure of Hρ in L2 ρX.The regression problem is framed as expected-risk minimization over the hypothesis space.Source: §1 · pp. 1–2
- Spectral algorithms address least-squares regression by solving an empirical linear equation with a regularizing filter to limit overfitting.The paper identifies ridge regression, principal component regression, gradient methods, and iterated ridge regression as examples.Source: §1 · p. 2
- Earlier results often required universal consistency or attainable targets, and non-attainable-case rates could be capacity-dependently suboptimal.Whether capacity-dependently optimal rates were available under a general source assumption remained unclear.Source: §1 · p. 2
- The paper proves high-probability optimal convergence results for spectral algorithms under a capacity assumption and a general source condition, with almost-sure optimal rates as a corollary.The source condition characterizes target regularity in L2 ρX rather than in Hρ.Source: §1 · p. 2
2 Learning with Kernel Methods and Notations
This section presents kernel learning as a special case of the paper’s Hilbert-space setting and introduces operators used to express the learning problem.
2 Learning with Kernel Methods and Notations
- Kernel learning uses a reproducing kernel to define an RKHS, where function evaluation is represented by an inner product with a kernel section.The RKHS is formed by completing the span of kernel sections, and the reproducing property gives f(ξ)=⟨Kξ,f⟩K.Source: §2 · pp. 2–3
- The kernel-learning minimization problem reduces to the paper’s general regression problem under a corresponding probability measure.The passage defines ρ from the data measure µ to make this reduction.Source: §2 · p. 3
- The section introduces covariance operators T and L and states that they are positive trace-class, hence compact, under Assumption (3).The operator norm is defined for bounded maps from L2 ρX to H.Source: §2 · p. 3
- The sampling operator maps a parameter ω to its evaluations on the sample, using a normalized Euclidean norm on Rn.The operator is Sxω with entries ⟨ω,xi⟩H.Source: §2 · p. 3
3 Spectral/Regularized Algorithms
The section motivates regularization as a response to overfitting and a potentially nonexistent empirical covariance inverse, then defines spectral algorithms through filter functions.
3 Spectral/Regularized Algorithms
- Directly solving the empirical linear equation can overfit, and the empirical covariance operator may not have an inverse; spectral algorithms replace that inverse with a regularized alternative.The objective is estimated through empirical risk because expected risk cannot be computed exactly.Source: §3 · p. 4
- A spectral algorithm is generated by choosing a filter function, whose definition includes a qualification parameter and finite bounds.Different filter choices yield different regularization methods.Source: §3 · pp. 4–5
- The listed filter choices include spectral cut-off, gradient methods, and iterated ridge regression; ridge regression is the case l=1.The spectral cut-off filter is u^-1 for u≥λ and zero for u<λ.Source: §3 · p. 5
- The paper measures performance through excess risk and, when fH is attainable, relates the H-norm error to an L2 ρX error norm.It also considers a broader class of norms ∥L^-a(fzλ−fH)∥ρ when L^-a fH is well defined.Source: §3 · p. 5
4 Convergence Results
The section establishes high-probability convergence bounds for spectral algorithms under moment, source, and capacity assumptions, then derives optimal rates and compares their scope with prior results. The discussion emphasizes general source conditions, including non-attainable cases, while noting boundaries and trade-offs in the comparisons.
4.1 Assumptions
- The paper considers a source assumption with generalized index function φ = ψϑ, where ψ is operator monotone with ψ(0) = 0 and ψ(b) < ∞, while ϑ is Lipschitz continuous.The left-hand side of Assumption 3 is called the effective dimension; Assumption 3 is always true for γ = 1 and cγ = κ², while γ ∈ ]0, 1] allows better rates.Source: §4.1 · pp. 6–7
4.2 Main Results
- Theorem 4.2 gives high-probability convergence bounds in several norm variants, with an optimal data-dependent regularization choice obtained by balancing the bound terms.The theorem covers the source-condition cases stated in its two parts.Source: §4.2 · p. 7
- For 2ζ + γ > 1, Corollary 4.3's error bounds match minimax rates under the stated conditions.The paper identifies this optimality with the minimax rates from [21] for the cases ζ ≥ 1/2 and a = 0.Source: §4.2 · p. 8
- Corollary 4.4's high-probability results imply convergence in expectation and almost surely, and for ζ ≥ 1/2 also yield bounds in H-related norms.The paper states that the error bounds are minimax-optimal when ζ ≥ 1/2.Source: §4.2 · p. 8
4.3 Discussions
- The convergence results are developed for non-parametric regression with kernel methods and translated to regression over a general Hilbert space for comparison..Source: §4.3 · p. 9
- Corollary 4.4 covers 0 < ζ ≤ 1/2 and γ = 0 without requiring fH = fρ, but its upper bound has an extra logarithmic factor when 2ζ + γ ≤ 1.The discussion contrasts this with [13], whose corresponding upper bound lacks that extra factor.Source: §4.3 · p. 9
- The comparisons note that Corollary 4.4 provides optimal rates for 0 ≤ ζ ≤ 1/2 without condition (29), while the paper does not pursue bounds depending jointly on R and noise level.The authors state that such bounds should be easy to derive at least when ζ ≥ 1/2.Source: §4.3 · p. 10
- Compared with prior results, Theorem 4.2 allows general source assumptions and cases where fH may not lie in Hρ, covers broader norms, and does not require condition (29).It also yields a better expectation rate without a logarithmic factor when φ(u) = √u and can infer almost-sure convergence.Source: §4.3 · p. 10
5 Proofs
The proofs combine deterministic and probabilistic lemmas to establish the main convergence results and their corollaries. They include a new estimate covering both variance and approximation error.
5.1 Lemmas
- The deterministic estimates generalize [1, Proposition 7] and bound the true bias for the deterministic vector ωλ.The proof uses the source condition and spectral-theorem estimates.Source: §5.1 · pp. 10–12
- A probabilistic lemma improves earlier matrix and operator estimates by accounting for γ in the logarithmic factor without requiring a sufficiently large sample size.The passage attributes the lemma's proof to [13] and compares it with and Lemma 7.2 in.Source: §5.1 · p. 12
- The new probabilistic lemma estimates terms from both variance and approximation error, under a condition slightly weaker than the bounded-target condition required in [14] for gradient methods.The lemma is motivated by [14] [13].Source: §5.1 · p. 13
5.2 Proof of Main Results
- The main theorem proof combines the lemmas to obtain high-probability bounds for λ=n^-θ, θ∈[0,1], and handles operator-monotone, Lipschitz, and composite filter cases.The proof identifies estimates for the theorem's first and second parts under the respective filter cases.Source: §5.2 · pp. 15, 19, 20
- The corollary proofs derive their results from Theorem 4.2 and Corollary 4.4, and one almost-sure result follows by applying the Borel-Cantelli lemma.The proofs also use monotonicity properties of the index functions and filter functions.Source: §5.2 · pp. 20–21
A List of Notations
The notation list defines symbols for the regression setting, sampling operators, regularity and capacity parameters, and quantities used to describe the algorithm and its error.
Regression setting
- The list defines the probability measure, hypothesis space, sample size, expected risk, and function spaces used in the regression setting.It also names the regression function and the input-space bound.Source: A List of Notations · p. 23
Operators
- The sampling operator maps a vector in H to its sample evaluations in R^n, and the list also identifies its adjoint.The operator is defined by (Sxω)i=⟨ω,xi⟩H.Source: A List of Notations · p. 23
Algorithm and assumptions
- The list names the regularization filter and estimated vector and function, alongside constants and parameters for regularity, effective dimension, and the source condition.It also identifies Rλ(u) and a quantity defined by equation (35).Source: A List of Notations · pp. 23–24