Faster kernel ridge regression using sketching and preconditioning
From MaRDI portal
Publication:4588937
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
- scientific article; zbMATH DE number 6276143 (Why is no real title available?)
- 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
- LSRN: A parallel iterative solver for strongly over- or underdetermined systems
- Learning Bounds for Kernel Regression Using Effective Data Dimensionality
- 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
(26)- Randomized sketches for kernel CCA
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Solution of the EEG inverse problem by random dipole sampling
- On data preconditioning for regularized loss minimization
- Randomized numerical linear algebra: Foundations and algorithms
- On nonparametric randomized sketches for kernels with further smoothness
- Sharper bounds for regularized data fitting
- Iterative kernel regression with preconditioning
- An accelerator for kernel ridge regression algorithms based on data partition
- Randomized sketches for kernels: fast and optimal nonparametric regression
- \textsf{StreaMRAK} a streaming multi-resolution adaptive kernel algorithm
- \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
- Sparse random feature maps for the item-multiset kernel
- Training very large scale nonlinear SVMs using alternating direction method of multipliers coupled with the hierarchically semi-separable kernel approximations
- Conjugate gradients for kernel machines
- Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
- Experimental design for nonparametric correction of misspecified dynamical models
- Sketching for principal component regression
- A literature survey of matrix methods for data science
- Randomized Low-Rank Approximation of Monotone Matrix Functions
- M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
- Randomized Nyström Preconditioning
- Semi-Infinite Linear Regression and Its Applications
- RidgeSketch: a fast sketching based solver for large scale ridge regression
- Learning in high-dimensional feature spaces using ANOVA-based fast matrix-vector multiplication
- Kernel conjugate gradient methods with random projections
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)
