We give a sketching-based iterative algorithm that computes a $1+\varepsilon$
approximate solution for the ridge regression problem $\min_x \|Ax-b\|_2^2
+\lambda\|x\|_2^2$ where $A \in 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 (Chowdhury et al.) by requiring that the
sketching matrix only has a weaker Approximate Matrix Multiplication (AMM)
guarantee that depends on $\varepsilon$, along with a constant subspace
embedding guarantee. The earlier work instead requires that the sketching
matrix has a subspace embedding guarantee that depends on $\varepsilon$. 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 =
\opnorm{A}$ 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.

提出了基于草图的迭代算法，用于解决均方误差损失函数加正则项的岭回归问题，针对早期工作中的子空间嵌入要求而使用更弱的近似矩阵乘法保证，为核岭回归提供了更快的算法，同时我们对均方误差损失函数的算法框架提出了切实可行的草图规模下限。