Solving Ridge Regression using Sketched Preconditioned SVRG

[edit]

Alon Gonen, Francesco Orabona, Shai Shalev-Shwartz ;
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:1397-1405, 2016.

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.

Related Material