Optimal Rates for the Regularized Least-Squares Algorithm III: Against Every Algorithm, a Single Distribution in P(b, c) Keeps the Expected Excess Risk above ℓ^(−cB/(cB+1)) for B > b (Theorem 3)Research Paper
Regularized least squares (RLS) in a reproducing kernel Hilbert space is a basic estimator of nonparametric regression and of kernel-based learning. Its learning rate is the speed at which the expected excess risk goes to zero as the sample size grows. A rate is useful only if it is known to be optimal, and optimality is a lower-bound statement about…