Optimal Rates for Regularized Least Squares Regression

By Ingo Steinwart, Don R. Hush, Clint Scovel. 2009

332 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistical Learning Theory

Citations in the corpus

Learning Theory for Distribution Regression (2014, methodology): “The question of optimal rates has also been addressed for the semi-supervised KRR setting (Caponnetto, 2006, Theorem 1), and for clipped KRR estimators (Steinwart et al., 2009) with integral operators of rapidly decaying spectrum.”
Sharp analysis of low-rank kernel matrix approximations (2012, neutral): “See also Steinwart et al. (2009).”
Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates (2013, methodology): “On the statistical side, a line of past work (van de Geer, 2000; Zhang, 2005; Caponnetto and De Vito, 2007; Steinwart et al., 2009; Hsu et al., 2012) has provided bounds on the estimation error of (cid:98) f as a function of N and λ .”
Quasi-oracle estimation of heterogeneous treatment effects (2017, background): “Thesharpest regret bounds for (10) given Assumptions 2 and 3 are due to Mendelson and Neeman (2010) (see also Steinwart, Hush, and Scovel (2009)), and scale as where the (cid:101) O -notation hides logarithmic factors.”
Distributed Learning with Regularized Least Squares (2016, methodology): “The results in (Caponnetto and De Vito, 2007; Steinwart et al., 2009; Zhang et al., 2015) showed that if N ( λ ) Nλ = O (1), then the optimal learning rates of algorithm (2) with m = 1 can be obtained in the sense that the upper and lower bounds for max f ρ K E f D,λ − f ρ k ρ are asymptomatically…”
Learning with SGD and Random Features (2018, methodology): “The above learning rate is the same achieved by an exact kernel ridge regression (KRR) estimator [11, 37, 38], which has been proved to be optimal in a minimax sense [11] under the same assumptions.”
Mercer’s Theorem on General Domains: On the Interaction between Measures, Kernels, and RKHSs (2012, background): “It has been recently discovered in [20, 37] that the statistical analysis of SVMs can be tightened for RKHSs that allow a refined control of the ‖ ·‖∞-norm of their functions in the sense of (39).”
On the Equivalence between Quadrature Rules and Random Features (2015, methodology): “We have: When r = 1 / 2, we get a result in the RKHS norm, but with no decay to zero; the RKHS norm · k F would allow a control in L ∞ -norm, but as noticed by Steinwart et al. (2009); Mendelson and Neeman (2010), such a control may be obtained in practice with r much smaller.”
Kernel ridge vs. principal component regression: Minimax bounds and the qualification of regularization operators (2017, background): “This approach leads to the study of oracle inequalities (Zhang, 2005; Zhang et al., 2013; Koltchinskii, 2006; Steinwart et al., 2009; Hsu et al., 2014), which we do not pursue in detail here.”
Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning (2014, methodology): “Even in this case, optimal rates can be achieved only when the regularization is chosen in a problem dependent way [12, 17, 27, 32].”
Estimating conditional quantiles with the help of the pinball loss (2011, methodology): “Recall that (5) was first used in [6] to establish an oracle inequality for SVMs using the hinge loss, while [7, 18, 25] consider (5) for SVMs using the least-squares loss.”
Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance (2019, unknown): “Assumption 6 is commonly made in least-squares regression [8, 35, 5] and is equivalent to requiring that, when expressing θ⋆ with respect to the eigenbasis of H(θ⋆), i.”
Random Design Analysis of Ridge Regression (2011, unknown): “If there exists σ ≥ 0 such that var(y2i ) ≤ σ 2 for all i = 1, 2, . . . , n, then E[‖β̂λ − β‖2Σ ] ≤ ∑ j λ j ( λ j λ + 1)2 β2j + σ 2 n ∑ j ( λ j λ j + λ )2 with equality iff var(yi ) = σ 2 for all i = 1, 2, . . . , n. Remark 5 (Effect of approximation error in fixed design) Observe that approx(xi )…”
Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model (2021, background): “The classical way of studying the performance of kernel methods [50, 51] is then to directly analyse the performance of convex learning in this space.”