论文标题
素描Krylov子空间：整个山脊正规化路径的更快计算
Sketching the Krylov Subspace: Faster Computation of the Entire Ridge Regularization Path
论文作者
论文摘要
我们提出了一种快速算法，用于在几乎线性的时间内计算整个脊回归正规化路径。我们的方法构建了一个基础，可以立即计算出脊回归解决方案的任何值。因此，线性模型可以通过交叉验证或其他风险估计策略进行调整，并具有更高的效率。该算法基于迭代性绘制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.
