Faster kernel ridge regression using sketching and preconditioning
From MaRDI portal
Publication:4588937
DOI10.1137/16M1105396zbMATH Open1379.65008arXiv1611.03220OpenAlexW2568875900MaRDI QIDQ4588937FDOQ4588937
Authors: Haim Avron, Kenneth L. Clarkson, David P. Woodruff 
Publication date: 6 November 2017
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1611.03220
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
Nonparametric regression and quantile regression (62G08) Preconditioners for iterative methods (65F08)
Cites Work
- Fast dimension reduction using Rademacher series on dual BCH codes
- Learning Bounds for Kernel Regression Using Effective Data Dimensionality
- Faster least squares approximation
- Finding frequent items in data streams
- Multicategory proximal support vector machine classifiers
- Revisiting the Nyström method for improved large-scale machine learning
- Elemental, a new framework for distributed memory dense matrix computations
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Title not available (Why is that?)
- Convergence rates of kernel conjugate gradient for random design regression
- Randomized sketches for kernels: fast and optimal nonparametric regression
- Sketching as a tool for numerical linear algebra
- Hierarchically compositional kernels for scalable nonparametric learning
- LSRN: A parallel iterative solver for strongly over- or underdetermined systems
- Compressed matrix multiplication
- Optimal Approximate Matrix Product in Terms of Stable Rank
- A fast summation tree code for Matérn kernel
- Sharper bounds for regularized data fitting
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
- Randomized numerical linear algebra: Foundations and algorithms
- On data preconditioning for regularized loss minimization
- 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
- \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
- \textsf{StreaMRAK} a streaming multi-resolution adaptive kernel algorithm
- Conjugate gradients for kernel machines
- Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
- Sketching for principal component regression
- Experimental design for nonparametric correction of misspecified dynamical models
- 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
Uses Software
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)
