Sharper Bounds for Regularized Data Fitting
Sharper Bounds for Regularized Data Fitting
复制标题
正则化数据拟合的更清晰界限
DOI：
10.4230/lipics.approx-random.2017.27
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
David P. Woodruff
中科院分区：
文献类型：
--
作者：
H. Avron;K. Clarkson;David P. Woodruff
我们研究了线性回归，低等级近似和规范相关分析的正则变体的矩阵草图方法。我们的主要重点是草图技术，该技术为正则问题保留目标函数价值，该领域在很大程度上尚未探索。我们在相当广泛的环境以及山脊正则化技术的特定环境中研究正则化。对于后者，应用于这些问题中的每个问题，我们显示算法资源界限，其中{\ em统计维度}出现在以前的等级出现的地方。统计维度总是小于等级，并且随着正则化的数量的增加而减小。特别是，对于山脊低级近似问题$ \ min_ {y，x} \ lvert yx -a \ rvert_f^2 + \ lambda \ lvert y \ rvert_f^2 + \ lambda \ lambda \ lavt其中$ y \ in \ mathbb {r}^{n \ times k} $和$ x \ in \ mathbb {r}^{k \ times d} $，我们给出一个近似算法\ [o（\ mathtt {\ mathtt { nnz}（a）） + \ tilde {o}（（（n + d）\ varepsilon^{ - 1} k \ min \ {k，\ varepsilon^{ - 1} \ mathtt {sd} *）\}）+ \ mathtt {poly}（\ mathtt {sd} _ \ lambda（y^*）（y^*）\ varepsilon^{ - 1}）\] \]，其中$ s _ {\ lambda}（y^*）（y^*）（y^*） le k $是$ y^*$，$ y^*$的统计维度是最佳$ y $，$ \ varepsilon $是一个错误参数，$ \ mathtt {nnz}（a）是$的数量$ a $的非零条目，即使$ \ lambda = 0 $，这也比先前的工作快。
我们还在更一般的环境中研究正则化。例如，我们获得了低级别近似问题的基于草图的算法）$是满足某些非常普遍的条件（主要是在正交转换下的不变性）的正规化功能。
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).