Faster kernel ridge regression using sketching and preconditioning
From MaRDI portal
Abstract: 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.
Recommendations
- Randomized sketches for kernels: fast and optimal nonparametric regression
- On nonparametric randomized sketches for kernels with further smoothness
- Randomized Nyström features for fast regression: an error analysis
- Conjugate gradients for kernel machines
- RidgeSketch: a fast sketching based solver for large scale ridge regression
Cites work
- A fast summation tree code for Matérn kernel
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Compressed matrix multiplication
- Convergence rates of kernel conjugate gradient for random design regression
- Elemental, a new framework for distributed memory dense matrix computations
- Fast dimension reduction using Rademacher series on dual BCH codes
- Faster least squares approximation
- Finding frequent items in data streams
- Hierarchically compositional kernels for scalable nonparametric learning
- scientific article; zbMATH DE number 6276143 (Why is no real title available?)
- Learning Bounds for Kernel Regression Using Effective Data Dimensionality
- LSRN: A parallel iterative solver for strongly over- or underdetermined systems
- Multicategory proximal support vector machine classifiers
- Optimal Approximate Matrix Product in Terms of Stable Rank
- Randomized sketches for kernels: fast and optimal nonparametric regression
- Revisiting the Nyström method for improved large-scale machine learning
- Sharper bounds for regularized data fitting
- Sketching as a tool for numerical linear algebra
Cited in
(37)- Kernel conjugate gradient methods with random projections
- Randomized sketches for kernel CCA
- Randomized sketches for kernels: fast and optimal nonparametric regression
- Learning in high-dimensional feature spaces using ANOVA-based fast matrix-vector multiplication
- \textsf{StreaMRAK} a streaming multi-resolution adaptive kernel algorithm
- On nonparametric randomized sketches for kernels with further smoothness
- On data preconditioning for regularized loss minimization
- Experimental design for nonparametric correction of misspecified dynamical models
- Two‐level preconditioning for Ridge Regression
- Conjugate gradients for kernel machines
- Sharper bounds for regularized data fitting
- Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Semi-Infinite Linear Regression and Its Applications
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Sketching for principal component regression
- An accelerator for kernel ridge regression algorithms based on data partition
- Randomized numerical linear algebra: Foundations and algorithms
- Sparse random feature maps for the item-multiset kernel
- A literature survey of matrix methods for data science
- M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
- Training very large scale nonlinear SVMs using alternating direction method of multipliers coupled with the hierarchically semi-separable kernel approximations
- Solution of the EEG inverse problem by random dipole sampling
- Randomized Nyström Preconditioning
- Randomized Low-Rank Approximation of Monotone Matrix Functions
- Iterative kernel regression with preconditioning
- \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
- Randomized Kaczmarz methods with beyond-Krylov convergence
- Embrace rejection: kernel matrix approximation by accelerated randomly pivoted Cholesky
- Two-sided preconditioned CGLS for the solution of factorized linear systems
- Scalable inference for nonparametric stochastic approximation in reproducing kernel Hilbert spaces
- A very sketchy talk (invited talk)
- Title not available (Why is no real title available?)
- Higher-order reduced rank regression
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
This page was built for publication: Faster kernel ridge regression using sketching and preconditioning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4588937)
