Randomized sketches for kernels: Fast and optimal non-parametric regression

Yun Yang; Mert Pilanci; Martin J. Wainwright

Source-linked AI summary

Randomized sketches for kernels: Fast and optimal non-parametric regression

Yun Yang, Mert Pilanci, Martin J. Wainwright

arXiv:1501.06195v1Jan 25, 2015stat.MLcs.DScs.LGstat.CO

TL;DR

Standard KRR has O(n^3) time and O(n^2) space costs, motivating scalable approximations that retain minimax optimality. The paper uses randomized kernel-matrix sketches and proves that Gaussian and randomized orthogonal-system sketches achieve minimax risk with dimensions proportional to statistical dimension, up to logarithmic factors for ROS sketches.

Problem
Standard KRR is statistically attractive but computationally prohibitive at scale because its time and space complexities are O(n^3) and O(n^2).
Method
The paper projects the kernel matrix into an m-dimensional random subspace and computes approximate KRR through an m-dimensional quadratic program.
Results
Gaussian and randomized orthogonal-system sketches achieve minimax risk when the sketch dimension is proportional to the kernel’s statistical dimension, with additional logarithmic factors for ROS sketches.
Takeaways & Limitations
Randomized sketching provides fast, minimax-optimal approximations to KRR for non-parametric regression over the studied kernel classes.
Takeaways & Limitations
For Nyström-based alternatives, whether leverage scores can be approximated more efficiently remains an open question for achieving statistical optimality in sampling dimension.

Abstract

from arXiv · show

Kernel ridge regression (KRR) is a standard method for performing non-parametric regression over reproducing kernel Hilbert spaces. Given $n$ samples, the time and space complexity of computing the KRR estimate scale as $\mathcal{O}(n^3)$ and $\mathcal{O}(n^2)$ respectively, and so is prohibitive in many cases. We propose approximations of KRR based on $m$-dimensional randomized sketches of the kernel matrix, and study how small the projection dimension $m$ can be chosen while still preserving minimax optimality of the approximate KRR estimate. For various classes of randomized sketches, including those based on Gaussian and randomized Hadamard matrices, we prove that it suffices to choose the sketch dimension $m$ proportional to the statistical dimension (modulo logarithmic factors). Thus, we obtain fast and minimax optimal approximations to the KRR estimate for non-parametric regression.

1 Introduction

The paper addresses KRR’s prohibitive O(n^3) time and O(n^2) space costs by using randomized kernel-matrix sketches. It shows that projection dimensions tied to statistical dimension can preserve minimax optimality.

Motivation: O(n^3) time and O(n^2) space make standard KRR difficult to use for large-scale non-parametric regression.The paper motivates approximate KRR methods that retain statistical minimax guarantees.
Sketching approach: Random projections reduce the kernel problem to an m-dimensional quadratic program with O(m^3) time and O(m^2) space.For suitable projections, constructing the approximate kernel matrix adds O(n^2 log(m)) preprocessing time.
Research question: The central question is how small m can be while the sketched KRR estimate remains minimax optimal.The analysis connects this choice to the kernel matrix’s statistical dimension, which measures effective degrees of freedom.
Main contribution: The paper confirms that several random projection classes can preserve minimax optimality when their dimension is proportional to statistical dimension.The introduction presents this as the paper’s main contribution and relates it to earlier constrained least-squares results.
Results roadmap: The paper develops a general sketch condition, then derives consequences for particular randomized sketch matrices.Theorem 2 gives a sufficient condition, while Corollary 1 specializes it to selected sketch families.

2 Problem formulation and background

This section frames nonparametric regression in RKHSs, introduces KRR and its computational bottlenecks, and develops sketched alternatives whose statistical guarantees are tied to kernel complexity measures.

2.1 Regression in reproducing kernel Hilbert spaces: The regression objective is to estimate the unknown function from n samples, with prediction quality measured here by squared L2(Pn) error.The setup uses samples from a nonparametric regression model and evaluates an estimate through its empirical prediction error.
2.1 Regression in reproducing kernel Hilbert spaces: RKHSs model regularity in the unknown regression function, while KRR combines least-squares fitting with a squared Hilbert-norm penalty.The RKHS is generated by a positive semidefinite kernel, and KRR estimates the function through a convex program.
2.2 Kernel ridge regression and its sketched form: Standard KRR solves an n-dimensional quadratic program, requiring O(n^3) computation and O(n^2) storage because the kernel matrix is generally dense.The representer theorem reduces the Hilbert-space optimization to a finite-dimensional problem, but the resulting scaling remains prohibitive for large datasets.
2.2 Kernel ridge regression and its sketched form: The sketched estimator restricts the KRR parameter to an m-dimensional subspace generated by the row span of a sketch matrix S, with m ≪ n.The approximation is obtained by solving the resulting sketched program and then outputting the corresponding function estimate.
2.2 Kernel ridge regression and its sketched form: The sketched quadratic program uses m-dimensional matrices and vectors and can be solved with computational complexity O(m^3).The sketched kernel matrix can also be computed in parallel across its columns.
2.2 Kernel ridge regression and its sketched form: The paper analyzes sub-Gaussian, randomized orthogonal-system, and row-subsampling sketches, including Gaussian, Bernoulli, DFT, Hadamard, and Nyström-related constructions.ROS sketches sample and rescale rows of a randomized orthonormal system, while subsampling sketches use rows of the identity matrix.
2.3 Kernel complexity measures and statistical guarantees: Kernel complexity is characterized through eigenvalues of the empirical kernel matrix and a critical radius defined using a truncated rescaled eigenvalue sum.The critical radius exists uniquely for every kernel class and is used to describe statistical guarantees.
2.3 Kernel complexity measures and statistical guarantees: For regular kernel classes, the critical radius lower-bounds the prediction error achievable by any estimator and provides the minimax benchmark for sketched regression.The statistical dimension controls a bias-variance tradeoff, while the paper notes that the critical-radius/statistical-dimension scaling holds for the kernels considered, aside from pathological examples.

3 Main results and their consequences

The paper proves that sketched KRR can retain minimax risk under a K-satisfiable sketch, and that Gaussian and ROS sketches achieve this with dimensions tied to statistical dimension. Experiments support the theory and show that Gaussian and ROS sketches can outperform Nyström under irregular designs.

Corollaries for randomized sketches: Gaussian and ROS sketches require projection dimension proportional to statistical dimension, with additional logarithmic factors for ROS sketches.This probabilistic result supplies practical randomized constructions without computing the kernel eigendecomposition.
General conditions for sketched kernel optimality: A K-satisfiable sketch yields a sketched KRR estimate achieving the minimax risk with high probability.The condition is deterministic for fixed design and sketch, while probabilistic guarantees arise when analyzing randomized sketches.
Corollaries for randomized sketches: A finite-rank Dth-order polynomial kernel needs sketch size of order D+1, independent of sample size.For the Gaussian kernel, the statistical dimension scales as √log n, while the first-order Sobolev kernel scales as n^1/3.
Comparison with Nyström-based approaches: Gaussian and ROS sketches track original KRR closely under regular and irregular designs, whereas Nyström performs very poorly for the irregular design.The paper attributes the Nyström behavior to the preceding degeneracy example, where sampling can ignore informative rows or columns.
Comparison with Nyström-based approaches: Nyström sampling may require substantially more columns than the statistical dimension, and an efficient leverage-score approximation remains open.For the first-order Sobolev kernel, the stated requirement is n^2/3 log n versus statistical dimension n^1/3.

4 Proofs

The proof establishes minimax optimality by separately controlling estimation and approximation errors under a suitable sketch condition. It uses eigenspace partitioning and K-satisfiability to construct a feasible sketched solution with the required bounds.

Two technical lemmas control the estimation and approximation errors, and together with the main upper bound yield the theorem.
The proof assumes σ = 1 for notational simplicity, with the general statement recovered by rescaling.
The analysis splits into cases according to whether the transformed error norm ∥K b∆∥2 is at most 1.
The remaining bounds combine operator-norm estimates, triangle inequalities, and the K-satisfiability condition to establish the target inequality.
For m > d_n, the transformed sketch is partitioned into leading and trailing eigenspaces, and K-satisfiability controls both blocks.
The two inequalities in (28a) and (28b) are combined to prove the preceding claim.

5 Discussion

The discussion summarizes a general sketching theorem for KRR and specializes it to Gaussian and randomized orthogonal-system sketches. These results show that sketch sizes proportional to the statistical dimension suffice for minimax risk under the stated conditions.

The main theorem gives sufficient conditions on any sketch matrix for sketched KRR to achieve the minimax risk over the underlying kernel class.
The paper specializes the general result to Gaussian random matrices and randomized orthogonal systems.
For these sketch classes, the required sketch size is proportional to the statistical dimension, up to the stated logarithmic factors.

A Subsampling sketches yield Nystr¨om approximation

The appendix shows that subsampling sketches produce the Nyström approximation in the dual formulation of sketched KRR. The sketched and original KRR solutions are connected through equivalent constrained quadratic programs and their dual variables.

The original KRR quadratic program can be rewritten as an equivalent constrained quadratic program.
The sketched KRR program admits an analogous constrained quadratic-program formulation and dual representation.
The sketched kernel matrix is eK = KST(SKST)^−1SK, a rank-m matrix that links the sketched primal and dual solutions.
For a sub-sampling sketch, eK is the Nyström approximation, so sketched KRR corresponds to applying Nyström approximation to the original KRR dual formulation.

B.1 Proof of Theorem 1

The proof of the minimax lower bound reduces kernel regression to a Gaussian normal sequence model constrained by an ellipsoid. A packing of this ellipsoid and Fano’s inequality then lower-bound the estimation error.

The kernel matrix eigendecomposition transforms the regression problem into a normal sequence model with Gaussian observations.
The RKHS norm constraint becomes the ellipsoid constraint ∥D^−1/2θ∗∥2 ≤ 1.
The lower bound targets the Euclidean error ∥eθ − θ∗∥2 for any estimator of the transformed parameter.
A δ/2-packing of the constrained ellipsoid is constructed, and a random index selects one of the corresponding regression problems.
Fano’s inequality and mutual-information bounds convert the packing into a lower bound on estimation error.
Independent Gaussian vectors generate the packing, with tail bounds and a union bound ensuring the required separation with positive probability.
Choosing log M = d_n/64 makes the construction probability positive and completes the packing argument.

B.2 Proof of Lemma 3

The proof establishes the two inequalities in bound (23) using concentration for Gaussian Lipschitz functions, rescaling, and a peeling argument. It also characterizes the relevant constraint set through an eigendecomposition of the kernel matrix.

Top inequality in the bound (23): The top inequality is reduced to controlling the event Zn(δn) > 2δn^2.A Gaussian concentration bound gives P[Zn(δn) ≥ 2δn^2] ≤ e^{-nδn^2}.
Bottom inequality in the bound (23): For shell events, the proof rescales vectors whose kernel norm exceeds δn and combines shell-specific bounds through a union bound.The argument uses the lower bound ∥K e∆∥2 ≥ um within each shell before summing the resulting probabilities.
Constraint representation: The kernel matrix decomposition K = U^TDU transforms the constraints into ∥D^-1/2β∥2 ≤ 1 and ∥β∥2 ≤ δ.Here β = DU∆, and the constrained vectors lie in an ellipse determined by D.
Proof tools: The proof uses standard inequalities and Gaussian distributional facts to control intermediate terms.Cauchy–Schwarz and Jensen’s inequality justify successive steps in the bounds.
Bottom inequality in the bound (23): The bottom inequality is proved by decomposing violations into shells indexed by um = 2mδn.The event E is expressed as a union of events E(um, um+1), enabling separate tail bounds for each shell.

B.3 Proof of Corollary 1

The proof of Corollary 1 verifies that the lower bound on sketch dimension guarantees K-satisfiability for Gaussian and ROS sketches with high probability.

Corollary 1: Under lower bound (16a), Gaussian and ROS sketches are K-satisfiable with probability at least φ(m, dn, n).This is stated as Lemma 5 and supplies the guarantee needed by Theorem 2.
Proof strategy: The proof separates the verification into the two inequalities defining K-satisfiability.Each inequality is handled in a separate subsequent proof subsection.

B.3.1 Proof of inequality (i):

The proof of inequality (i) bounds the operator norm associated with the sketch by discretizing the sphere and applying concentration results for Gaussian and ROS sketches.

Discretization: A 1/2-cover of Sdn−1 with N ≤ e2dn elements reduces the operator-norm bound to finitely many inner products.The discretization yields |||Q|||op ≤ 4 maxj,k=1,...,N ⟨vj, Qvk⟩.
Gaussian case: For Gaussian sketches, standard sub-exponential bounds control the discretized inner products under the assumed lower bound on m.The vectors are represented through evj = U1vj, with eQ = STS − Idn.
ROS case: For ROS sketches, the corresponding probability bound follows from results of Krahmer and Ward and the same lower-bound condition on m.The proof explicitly invokes the assumed lower bound on m in the final step.

B.3.2 Proof of inequality (ii):

The proof of inequality (ii) analyzes Gaussian and ROS sketches separately, using sphere covers, Gaussian concentration, and matrix Chernoff bounds.

Covering argument: A 1/2-cover of Sm−1 with log M ≤ 2m reduces the analysis to finitely many covered directions.The cover is applied to the ellipse defined by the constraint ∥Dv∥2 ≤ 1.
Gaussian case: For each covered direction, Zj is represented through the Gaussian supremum V(g) = m^-1/2 supv∈E ⟨g, v⟩.Gaussian concentration is then applied after establishing the relevant Lipschitz behavior.
Gaussian case: The resulting per-direction tail bound is combined over the M covered directions using a union bound.The proof states P[Zj ≥ c0(1 + ǫ)δn] ≤ e^-c2m for each j before the final aggregation.
ROS case: For ROS sketches, the sketch has the form S = PH diag(r), with P a scaled partial identity and H an orthonormal bounded-entry matrix.The representation uses Rademacher variables r ∈ {−1, 1}n and |Hij| ≤ c/√n.
ROS case: The ROS argument bounds the sketch vectors with high probability using concentration for convex Lipschitz functions and then applies matrix Chernoff bounds.The proof first controls maxi∈[m] ∥vi∥2 and bounds |||E[v1v1^T]|||op ≤ δn^2.
ROS case: The ROS probability estimate completes the proof of the second inequality.The final claim follows from the preceding concentration and matrix-Chernoff calculations.