Variant of greedy randomized Kaczmarz for ridge regression

• Published in: Applied numerical mathematics 2019-09, Vol.143, p.223-246
• Main Authors: Liu, Yong, Gu, Chuan-Qing
• Format: Article
• Language: English
• Subjects: Greedy randomized Kaczmarz; Randomized coordinate descent; Randomized Kaczmarz; Ridge regression
• ISSN: 0168-9274; 1873-5460
• DOI: 10.1016/j.apnum.2019.04.008

The variants of randomized Kaczmarz (RK) and randomized Gauss-Seidel (RGS) are distinct iterative algorithms for ridge regression. Theoretical convergence rates for these two algorithms were provided by a simple side-by-side analysis in recent work. Considering that greedy randomized Kaczmarz (GRK) algorithm converges faster than the RK algorithm in both theory and experiments, we extend the GRK algorithm for ordinary least squares (OLS) regression to ridge regression and establish the corresponding convergence theory for the resulting algorithm and, furthermore, we study the GRK algorithm with relaxation for ridge regression and prove that it also converges with expected exponential rate in this paper. In addition, we propose an accelerated GRK algorithm with relaxation for ridge regression by executing more rows that corresponding to the larger entries of the residual vector simultaneously at each iteration. Numerical results show that the GRK algorithm with and without relaxation for ridge regression perform much better in iteration steps than the variants of RK and RGS algorithms, and the accelerated GRK algorithm with relaxation significantly outperforms all other algorithms in terms of both iteration counts and computing times. •We extend GRK algorithm to ridge regression and establish the convergence theory for the resulting algorithm.•We construct a relaxed GRK algorithm for ridge regression and establish the corresponding convergence theory.•We propose an accelerated GRK algorithm that with relaxation by updating more active rows for ridge regression.•Accelerated GRK algorithm with relaxation significantly outperforms all other algorithms in iteration counts and CPU times.