PaperlayerView exact revision on arXiv

Source-linked AI summary

Faster Kernel Ridge Regression Using Sketching and Preconditioning

Haim Avron, Kenneth L. Clarkson, David P. Woodruff

arXiv:1611.03220v4math.NAcs.DScs.LGcs.NA

TL;DR

Dense, ill-conditioned kernel systems make exact KRR costly, while direct random-feature approximations may require many features and still compromise performance. The paper uses random feature maps to precondition the kernel system, reporting effective training at up to one million examples.

  • Problem

    Dense, ill-conditioned KRR systems make direct solution costly, while direct random-feature approximations can require many features and still fall short of full-kernel test error.

    Source: §1 · p. 2

  • Method

    The method uses random feature maps to precondition the kernel matrix and iteratively solve the original system to high accuracy.

    Source: §1.1 · p. 2

  • Results

    The algorithm is highly effective on datasets with as many as one million training examples and often behaves like O(n^2).

    Source: §7 · p. 20

  • Takeaways & Limitations

    The approach trains high-quality models without compromising statistical capacity on datasets up to one million examples.

    Source: §1.1 · p. 3

    The algorithm requires Θ(n^2) memory to store the kernel matrices.

    Source: §7 · p. 20

Abstract

from arXiv · show

Kernel Ridge Regression (KRR) is a simple yet powerful technique for non-parametric regression whose computation amounts to solving a linear system. This system is usually dense and highly ill-conditioned. In addition, the dimensions of the matrix are the same as the number of data points, so direct methods are unrealistic for large-scale datasets. In this paper, we propose a preconditioning technique for accelerating the solution of the aforementioned linear system. The preconditioner is based on random feature maps, such as random Fourier features, which have recently emerged as a powerful technique for speeding up and scaling the training of kernel-based methods, such as kernel ridge regression, by resorting to approximations. However, random feature maps only provide crude approximations to the kernel function, so delivering state-of-the-art results by directly solving the approximated system requires the number of random features to be very large. We show that random feature maps can be much more effective in forming preconditioners, since under certain conditions a not-too-large number of random features is sufficient to yield an effective preconditioner. We empirically evaluate our method and show it is highly effective for datasets of up to one million training examples.

1 Introduction

KRR reduces regression to solving a linear system, but dense, ill-conditioned kernel matrices make direct and iterative solutions costly, while direct random-feature approximations can compromise model quality. The paper uses random features to precondition the system, analyzes when this works, and evaluates the approach at large scale.

1 Introduction

  • Dense kernel matrices make direct KRR solves Θ(n^3), while large condition numbers can require many iterative steps.The introduction notes that these costs are prohibitive even for modest datasets.Source: §1 · p. 2
  • Direct random-feature approximations can require many features and still fail to match full-kernel test error, motivating preconditioning instead.The paper reports cases where even s as large as n is insufficient to achieve the full kernel method’s test error rate.Source: §1 · p. 2, §1.1 · p. 2

1.1 Contributions

  • Random feature maps form a preconditioner for iterative solution of the original kernel system, preserving modeling capabilities apart from choosing KRR itself.The method is framed as a way to use sketching for high-accuracy solves rather than solving only an approximated system.Source: §1.1 · p. 2, §1 · p. 2
  • For the polynomial kernel, a feature count proportional to statistical dimension yields a constant-bounded relevant condition number under the paper’s conditions.The analysis is limited to the polynomial kernel and is described as likely pessimistic, while connecting preconditioner size to statistical dimension.Source: §1.1 · pp. 2–3
  • The distributed-memory implementation trains high-quality Gaussian- and polynomial-kernel models on datasets up to one million examples without compromising statistical capacity.On one million examples, the code solved the system to relatively high accuracy in about an hour on an EC2 cluster.Source: §1.1 · p. 3

1.2 Related Work

  • The paper contrasts its lower-rank approximation goal with methods that use high-rank approximations, and distinguishes its analysis and large-scale experiments from prior random-feature preconditioning work.Cutajar et al. also use random features as a preconditioner, but the paper says they provide no theoretical analysis and experiment only on small-scale, low-dimensional datasets.Source: §1.2 · p. 3

2 Preliminaries

The preliminaries establish notation and describe random feature maps as kernel approximations, including Fourier and TensorSketch constructions. They then introduce sketching and explain how random features can serve as sketches for preconditioning rather than direct approximate solves.

2.1 Basic Definitions and Notation

  • The paper fixes notation for positive (semi)definite matrices, the induced matrix norm, the kernel matrix, and the positive ridge parameter λ.Here n is the number of training examples, d their dimension, and K_ij = k(x_i,x_j).Source: §2.1 · p. 4

2.2 Random Feature Maps

  • Random features replace k(x,z) with ϕ(x)^Tϕ(z), enabling KRR training through an n-by-s feature matrix.The paper discusses random Fourier features for shift-invariant kernels and TensorSketch for polynomial kernels; TensorSketch features can be computed in O(q(nnz(x)+s log s)).Source: §2.2 · pp. 4–5

2.3 Fast Numerical Linear Algebra Using Sketching

  • Sketching embeds a high-dimensional space in a lower-dimensional one; in linear regression, an oblivious subspace embedding can preserve the regression guarantee.The sketch-and-solve approach has ϵ^-2 dependence, whereas sketch-to-precondition supports high accuracy with log(1/ϵ) dependence.Source: §2.3 · pp. 5–6

2.4 Random Feature Maps as Sketching

  • Random feature maps can sketch the span of kernel functions, and TensorSketch gives an oblivious subspace embedding in one case.The paper therefore treats random-features KRR as sketch-and-solve, then adopts sketch-to-precondition to avoid relying on that crude approximation alone.Source: §2.4 · p. 6

3 Random Features Preconditioning

The section uses random-feature matrices to precondition PCG for kernel ridge regression, then analyzes when the sketch yields fast convergence. For polynomial kernels, the feature count is tied to statistical dimension; extensions to other feature maps require an approximate multiplication property.

3.1 Algorithm

  • PCG solves (K + λI_n)c = y using ZZT + λI_n as a preconditioner, with Z formed from random-feature vectors.The method assumes s < n and uses the Woodbury formula with a Cholesky factorization of ZTZ + λI_s to apply the preconditioner.Source: §3.1 · p. 6

3.2 Analysis

  • With enough TENSORSKETCH features for a homogeneous polynomial kernel, PCG converges in O(1) iterations for a fixed threshold.The analysis bounds the relevant condition number by 3 with probability at least 1 − δ; the feature requirement depends on statistical dimension and can be o(n) when that dimension is o(n^1/2).Source: §3.2 · pp. 7–9

3.3 Other Kernels and Feature Maps

  • For other kernels, the convergence guarantee extends to feature maps that satisfy an approximate multiplication property.The theorem states a feature-count condition in terms of that property and statistical dimension.Source: §3.3 · p. 10
  • The approximate multiplication property is currently proved only for TENSORSKETCH.Source: §3.3 · p. 10

4 Multiple Level Sketching

This section composes sketches to reduce the dependence of preconditioner size on statistical dimension. For polynomial kernels, the resulting construction uses O(sλ(K) log(sλ(K))) columns in Z2, with an optional further dimension reduction.

4 Multiple Level Sketching

  • The method first computes s1 random features, then applies an SRHT to obtain Z2; composing sketches improves dependence on statistical dimension.The authors also discuss composing the initial map with the Johnson–Lindenstrauss transform.Source: §4 · p. 11
  • O(sλ(K) log(sλ(K))) columns in Z2 suffice for a good polynomial-kernel preconditioner using multiple-level sketching.Source: §4 · p. 11
  • The multiple-level sketching analysis assumes ||K||2 ≥ λ.The paper notes that if λ ≥ ||K||2, the condition number of K + λI_n is bounded by 2.Source: §4 · p. 12
  • A dense random projection can further reduce the dimension to O(sλ(K)).Source: §4 · p. 12

5 Adaptively Setting the Sketch Size

For the polynomial kernel with TENSORSKETCH, the section gives testable conditions for a preconditioner and an adaptive procedure that enlarges the sketch until those conditions are met.

5 Adaptively Setting the Sketch Size

  • When the stated conditions hold, Theorem 1’s guarantees follow; with sufficiently large sketch size, both conditions hold with probability at least 1 − δ.The theorem defines P using eigenvectors of ZZT with eigenvalues above 0.05λ.Source: §5 · p. 13
  • Theorem 1’s conditions imply Equation 4 with high probability, and tightening its constant sufficiently enforces conditions 1 and 2.The argument for condition 1 uses a contradiction involving bounds of 1.1λ and 1.05λ.Source: §5 · p. 14
  • The adaptive procedure starts with a small sketch, tests Z, and doubles s until it obtains a good enough preconditioner.The section states this occurs when s is large enough according to Theorem 1.Source: §5 · pp. 13–14
  • Condition 1 can be tested with power iteration, while condition 2 can be tested by constructing a subspace embedding using TENSORSKETCH.The text omits the technical details of the tests.Source: §5 · p. 14

6 Experiments

Experiments compare the proposed method with random-feature approaches and evaluate its performance, runtime, and resource use across datasets. Results include training models on up to one million examples, alongside comparisons of preconditioning choices, convergence, and stopping tolerances.

6 Experiments

  • Experiments used distributed-memory MPI and Elemental on EC2, combining Gaussian kernels with random Fourier features and polynomial kernels with TensorSketch; RLSC converted classification to regression.The study used standard classification and regression datasets.Source: §6 · p. 15

6.1 Comparison to the Random Features Method

  • On COVTYPE and extended MNIST-8M, the proposed method outperforms random-feature profiles in error-versus-data-size and error-versus-training-time comparisons.The random-feature profiles use s = 20,000, s = 2.26√nd, and s = 0.2n.Source: Figure 2 · p. 16, §6.1 · p. 16
  • Even with as many random features as training examples, the random-features method has higher error; when tuned for comparable performance, its runtime can exceed the proposed method's.The proposed method's optimal MNIST training time was under 2 minutes with the Gaussian kernel and under 4 minutes with the polynomial kernel.Source: §6.1 · p. 16

6.3 Additional Experimental Results

  • Setting the preconditioner regularization λp above the model regularization λ often improved preconditioner quality; λp = 10λ is suggested as a rule of thumb, without theoretical analysis.Table 2 reports runtime and resources for different preconditioner λ choices.Source: §6.3 · p. 17, Table 2 · p. 18

6.2 Resources and Running Time on a Cloud Service

  • The method trained high-quality models on datasets of up to one million examples in a few hours on EC2, though kernel bandwidth and regularization were not tuned to their best values.Table 1 reports running time and resources for classification and regression datasets.Source: §6.2 · p. 17, Table 1 · p. 18

6.3 Additional Experimental Results

  • Against a distributed block-ADMM random-features solver, the proposed method achieved better error rates, usually with better running times.The comparison used hinge loss for the ADMM solver and generally set its feature count to 25% of dataset size.Source: §6.3 · p. 17, Table 3 · p. 19
  • Preconditioning was faster in almost all cases and more robust: unpreconditioned CG failed in some cases, with errors worsening on MNIST-300K and YEARMSD.For MNIST-300K, error was 1.33% versus 0.92%; for YEARMSD, it was 5.25 × 10^-3 versus 4.58 × 10^-3.Source: §6.3 · p. 17, Table 4 · p. 19
  • Classification tolerance 10^-3 was only barely better than 10^-2 in test error, with a small runtime penalty; the authors report that 10^-2 seems sufficient in practice.Table 5 compares the two tolerance settings.Source: §6.3 · p. 17, Table 5 · p. 20

7 Conclusions

The proposed sketching-and-preconditioning solver has running time between O(n^2) and O(n^3), depending on the data, kernel, and feature map, and often behaves like O(n^2) empirically. It is effective on datasets with up to one million training examples, while its Θ(n^2) kernel-matrix storage is its main limitation.

7 Conclusions

  • The algorithm is empirically effective on datasets with as many as one million training examples.Source: §7 · p. 20
  • Its running time lies between O(n^2) and O(n^3), depending on the data, kernel, and feature map, and it often behaves like O(n^2).Source: §7 · p. 20
  • The main limitation is Θ(n^2) memory for storing kernel matrices; proposed larger-data approaches remain future work.The paper suggests out-of-core storage, boosting with smaller models, and using the solver within block coordinate descent, but leaves their exploration to future work.Source: §7 · p. 20
  • When training sets are not very large, the authors argue that fully leveraging available data to produce the best possible model remains important.They describe their algorithm and implementation as an effective way to do so.Source: §7 · p. 20

A Appendix - Proof of Theorem 5

The proof bounds the relevant condition number by 3 with probability at least 1 − δ. It uses a Cholesky-based transformation of the kernel and feature matrices to establish the preconditioned system's properties.

A Appendix - Proof of Theorem 5

  • The proof uses the Cholesky factor L of K + λI_n to transform the kernel matrix to K(Q,Q) = L^-1 K L^-T.Source: A Appendix - Proof of Theorem 5 · pp. 23–24
  • With probability at least 1 − δ, the relevant condition number is bounded by 3, yielding a PCG iteration guarantee for reducing error to an ε fraction of its initial value.The stated iteration bound is ⌈√κ ln(2/ε)/2⌉ iterations when the condition number is bounded by κ.Source: A Appendix - Proof of Theorem 5 · p. 24
  • The transformed feature matrix is ZQ = L^-1 Z, connecting the feature map to the Cholesky-based transformation.Source: A Appendix - Proof of Theorem 5 · p. 24
Loading 1611.03220v4…