2022/10/21 by Yifei Wang, Wang, Yifei, Mert Pilancı +1
Computer Science · Engineering · #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2210.12212
openalex publication_date 2022/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.
RidgeSketch: A Fast sketching based solver for large scale ridge regression