Faster Kernel Ridge Regression Using Sketching and Preconditioning

DOI10.1137/16M1105396zbMath1379.65008arXiv1611.03220OpenAlexW2568875900MaRDI QIDQ4588937

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

Publication date: 6 November 2017

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.03220

zbMATH Keywords

preconditioningnonparametric regressionkernel ridge regressionrandom features

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Preconditioners for iterative methods (65F08)

Related Items

Randomized numerical linear algebra: Foundations and algorithms, \textsf{StreaMRAK} a streaming multi-resolution adaptive kernel algorithm, Experimental Design for Nonparametric Correction of Misspecified Dynamical Models, Semi-Infinite Linear Regression and Its Applications, Sharper Bounds for Regularized Data Fitting, 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, Sketching for Principal Component Regression, Kernel conjugate gradient methods with random projections, Learning in high-dimensional feature spaces using ANOVA-based fast matrix-vector multiplication, Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning, Estimating Leverage Scores via Rank Revealing Methods and Randomization

Uses Software

• Elemental
• Blendenpik
• LSRN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Faster least squares approximation
• Fast dimension reduction using Rademacher series on dual BCH codes
• Finding frequent items in data streams
• Randomized sketches for kernels: fast and optimal nonparametric regression
• Convergence rates of Kernel Conjugate Gradient for random design regression
• LSRN: A Parallel Iterative Solver for Strongly Over- or Underdetermined Systems
• Computational Advertising: Techniques for Targeting Relevant Ads
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Elemental
• Optimal Approximate Matrix Product in Terms of Stable Rank
• Sharper Bounds for Regularized Data Fitting
• A Fast Summation Tree Code for Matérn Kernel
• Learning Bounds for Kernel Regression Using Effective Data Dimensionality
• Compressed matrix multiplication
• Multicategory proximal support vector machine classifiers