---
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.'
author:
- 'Alon Gonen[^1]'
- 'Francesco Orabona[^2]'
- 'Shai Shalev-Shwartz[^3]'
bibliography:
- 'bib.bib'
title: |
    Solving Ridge Regression using\
    Sketched Preconditioned SVRG
---

Introduction {#sec:intro}
============

Consider the *ridge regression* problem: $$\label{eq:ridge}
\min_{w \in \reals^d}\  \left\{L(w) = \frac{1}{n}\sum_{i=1}^n \frac{1}{2}(w^\top x_i-y_i)^2 + \frac{\lambda}{2} \|w\|^2\right\},$$ where $\lambda>0$ is a regularization parameter, $x_i\in{\mathbb{R}}^d$ and $y_i\in {\mathbb{R}}$ for $i=1,\cdots,n$ the training data. We focus on the large scale regime, where both $n$ and $d$ are large. In this setting, stochastic iterative methods such as SDCA [@shalev2013stochastic], SVRG [@johnson2013accelerating], and SAG [@roux2012stochastic] have become a standard choice for minimizing the objective $L$. Specifically, the overall complexity of a recent improved variant of SVRG due to [@xiao2014proximal] depends on the average condition number, which is defined as follows. Denote the empirical correlation matrix and its eigenvalue decomposition by $$\label{eq:covSpec}
C := \frac{1}{n} \sum_{i=1} ^n x_i x_i^\top = \sum_{i=1} ^d \lambda_i u_i u_i^\top~.$$ The average condition number of $C+\lambda I$ is defined as 