Variant of Greedy Randomized Gauss-Seidel Method for Ridge Regression

The variants of randomized Kaczmarz and randomized Gauss-Seidel algorithms are two effective stochastic iterative methods for solving ridge regression problems. For solving ordinary least squares regression problems, the greedy randomized Gauss-Seidel (GRGS) algorithm always performs better than the randomized Gauss-Seidel algorithm (RGS) when the system is overdetermined. In this paper, inspired by the greedy modification technique of the GRGS algorithm, we extend the variant of the randomized Gauss-Seidel algorithm, obtaining a variant of greedy randomized Gauss-Seidel (VGRGS) algorithm for solving ridge regression problems. In addition, we propose a relaxed VGRGS algorithm and the corresponding convergence theorem is established. Numerical experiments show that our algorithms outperform the VRK-type and the VRGS algorithms when $m > n$.