Sketching the Krylov subspace: faster computation of the entire ridge regularization path

作     者：Wang, Yifei Pilanci, Mert 

作者机构：Stanford Univ Dept Elect Engn 350 Jane Stanford Way Stanford CA 94305 USA 

出 版 物：《JOURNAL OF SUPERCOMPUTING》 (超高速计算杂志)

年 卷 期：2023年第79卷第16期

页      面：18748-18776页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation (NSF) [ECCS- 2037304, DMS-2134248] NSF CAREER award [CCF-2236829] U.S. Army Research Office Early Career Award [W911NF-21-1-0242] Stanford Precourt Institute Hong Kong SAR 

主　　题：Ridge regression Randomized algorithms Kernel ridge regression 

摘      要：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.