Sharper Bounds for Regularized Data Fitting
  We study matrix sketching methods for regularized variants of linear
regression, low rank approximation, and canonical correlation analysis. Our
main focus is on sketching techniques which preserve the objective function
value for regularized problems, which is an area that has remained largely
unexplored. We study regularization both in a fairly broad setting, and in the
specific context of the popular and widely used technique of ridge
regularization; for the latter, as applied to each of these problems, we show
algorithmic resource bounds in which the {\em statistical dimension} appears in
places where in previous bounds the rank would appear. The statistical
dimension is always smaller than the rank, and decreases as the amount of
regularization increases. In particular, for the ridge low-rank approximation
problem $\min_{Y,X} \lVert YX - A \rVert_F^2 + \lambda \lVert Y\rVert_F^2 +
\lambda\lVert X \rVert_F^2$, where $Y\in\mathbb{R}^{n\times k}$ and
$X\in\mathbb{R}^{k\times d}$, we give an approximation algorithm needing \[
O(\mathtt{nnz}(A)) + \tilde{O}((n+d)\varepsilon^{-1}k \min\{k,
\varepsilon^{-1}\mathtt{sd}_\lambda(Y^*)\})+
\mathtt{poly}(\mathtt{sd}_\lambda(Y^*) \varepsilon^{-1}) \] time, where
$s_{\lambda}(Y^*)\le k$ is the statistical dimension of $Y^*$, $Y^*$ is an
optimal $Y$, $\varepsilon$ is an error parameter, and $\mathtt{nnz}(A)$ is the
number of nonzero entries of $A$.This is faster than prior work, even when
$\lambda=0$.
  We also study regularization in a much more general setting. For example, we
obtain sketching-based algorithms for the low-rank approximation problem
$\min_{X,Y} \lVert YX - A \rVert_F^2 + f(Y,X)$ where $f(\cdot,\cdot)$ is a
regularizing function satisfying some very general conditions (chiefly,
invariance under orthogonal transformations).
