Solving Ridge Regression using Sketched Preconditioned SVRG

2016/02/07 by Alon Gonen, Francesco Orabona, Gonen, Alon +3 · 1 citation
Computer Science · Engineering · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1602.02350

openalex publication_date 2016/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We develop a novel preconditioning method for ridge regression, based on recent linear sketching methods. By equipping Stochastic Variance Reduced Gradient (SVRG) with this preconditioning process, we obtain a significant speed-up relative to fast stochastic methods such as SVRG, SDCA and SAG.

Citations

• Un-regularizing: approximate proximal point and faster stochastic\n algorithms for empirical risk minimization
• Randomized Block Krylov Methods for Stronger and Faster Approximate\n Singular Value Decomposition
• On Data Preconditioning for Regularized Loss Minimization

Cited by

• Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure

Related

• Faster Kernel Ridge Regression Using Sketching and Preconditioning
• Sketching the Krylov Subspace: Faster Computation of the Entire Ridge Regularization Path
• Fast Ridge Regression with Randomized Principal Component Analysis and Gradient Descent
• Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
• Robust, randomized preconditioning for kernel ridge regression