# Solving Ridge Regression using Sketched Preconditioned SVRG

arXiv: https://arxiv.org/abs/1602.02350 · HTML: https://mlsanity.com/paper/1602.02350/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2016.

## Built on by (most cited first, 15 of 15)

- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [Robust, randomized preconditioning for kernel ridge regression](https://mlsanity.com/paper/2304.12465/) (2023)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions](https://mlsanity.com/paper/2106.12231/) (2021)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Revisiting Matrix Sketching in Linear Bandits: Achieving Sublinear Regret via Dyadic Block Sketching](https://mlsanity.com/paper/2410.10258/) (2024)
- [Decoupling Variance and Scale-Invariant Updates in Adaptive Gradient Descent for Unified Vector and Matrix Optimization](https://mlsanity.com/paper/2602.06880/) (2026)
- [Improving Implicit Regularization of SGD with Preconditioning for Least Square Problems](https://mlsanity.com/paper/2403.08585/) (2024)
- [Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients](https://mlsanity.com/paper/2404.14758/) (2024)
- [Faster Randomized Methods for Orthogonality Constrained Problems](https://mlsanity.com/paper/2106.12060/) (2021)
- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)
- [Sharpened Lazy Incremental Quasi-Newton Method](https://mlsanity.com/paper/2305.17283/) (2023)
- [On the Noise Sensitivity of the Randomized SVD](https://mlsanity.com/paper/2305.17435/) (2023)
- [The Advantages of Fresh Sketching for Ridge Regression](https://mlsanity.com/paper/2609.38565/) (2026)

## Abstract (arXiv)

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.