Sketching the Krylov subspace: faster computation of the entire ridge regularization path
Sketching the Krylov subspace: faster computation of the entire ridge regularization path
复制标题
绘制 Krylov 子空间：更快地计算整个岭正则化路径
DOI：
10.1007/s11227-023-05309-w
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Pilanci, Mert
中科院分区：
文献类型：
--
作者：
Wang, Yifei;Pilanci, Mert
我们提出了一种快速算法，用于在近线性时间内计算整个岭回归正则化路径。我们的方法构建了一个基础，在此基础上可以针对正则化参数的任何值立即计算岭回归的解。因此，可以通过交叉验证或其他风险估计策略来调整线性模型，从而显着提高效率。该算法基于通过正则化路径上的二项式分解迭代地绘制 Krylov 子空间。我们提供了各种草图矩阵的收敛分析，并表明它提高了最先进的计算复杂性。我们还提供了一种自适应估计草图尺寸的技术。该算法适用于超定问题和欠定问题。我们还提供了矩阵值岭回归的扩展。真实中型和大规模岭回归任务的数值结果说明了与需要超线性计算时间的标准基线相比，所提出的方法的有效性。
We propose a fast algorithm for computing the entire ridge regression regularization path in nearly linear time. Our method constructs a basis on which the solution of ridge regression can be computed instantly for any value of the regularization parameter. Consequently, linear models can be tuned via cross-validation or other risk estimation strategies with substantially better efficiency. The algorithm is based on iteratively sketching the Krylov subspace with a binomial decomposition over the regularization path. We provide a convergence analysis with various sketching matrices and show that it improves the state-of-the-art computational complexity. We also provide a technique to adaptively estimate the sketching dimension. This algorithm works for both the over-determined and under-determined problems. We also provide an extension for matrix-valued ridge regression. The numerical results on real medium and large-scale ridge regression tasks illustrate the effectiveness of the proposed method compared to standard baselines which require super-linear computational time.
正则化数据拟合的更清晰界限
DOI：
10.4230/lipics.approx-random.2017.27
发表时间：
2016
期刊：
2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
影响因子：
--
作者：
H. Avron;K. Clarkson;David P. Woodruff
通讯作者：
David P. Woodruff
影响因子：
8.6
作者：
Aaboud, M.;Aad, G.;Zwalinski, L.
通讯作者：
Zwalinski, L.