Sketching Algorithms and Lower Bounds for Ridge Regression
  We give a sketching-based iterative algorithm that computes $1+\varepsilon$
approximate solutions for the ridge regression problem $\min_x \|{Ax-b}\|_2^2
+\lambda\|{x}\|_2^2$ where $A \in \mathbb{R}^{n \times d}$ with $d \ge n$. Our
algorithm, for a constant number of iterations (requiring a constant number of
passes over the input), improves upon earlier work of Chowdhury et al., by
requiring that the sketching matrix only has a weaker Approximate Matrix
Multiplication (AMM) guarantee that depends on $\epsilon$, along with a
constant subspace embedding guarantee. The earlier work instead requires that
the sketching matrix have a subspace embedding guarantee that depends on
$\epsilon$. For example, to produce a $1+\varepsilon$ approximate solution in
$1$ iteration, which requires $2$ passes over the input, our algorithm requires
the OSNAP embedding to have $m= O(n\sigma^2/\lambda\varepsilon)$ rows with a
sparsity parameter $s = O(\log(n))$, whereas the earlier algorithm of Chowdhury
et al., with the same number of rows of OSNAP requires a sparsity $s =
O(\sqrt{\sigma^2/\lambda\varepsilon} \cdot \log(n))$, where $\sigma =
\|{A}\|_2$ is the spectral norm of the matrix $A$. We also show that this
algorithm can be used to give faster algorithms for kernel ridge regression.
Finally, we show that the sketch size required for our algorithm is essentially
optimal for a natural framework of algorithms for ridge regression by proving
lower bounds on oblivious sketching matrices for AMM. The sketch size lower
bounds for AMM may be of independent interest.
