arrow
Volume 14, Issue 3
Variant of Greedy Randomized Gauss-Seidel Method for Ridge Regression

Li-Xiao Duan & Guo-Feng Zhang

Numer. Math. Theor. Meth. Appl., 14 (2021), pp. 714-737.

Published online: 2021-06

Export citation
  • Abstract

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$.

  • AMS Subject Headings

65F10, 62J07, 68W20

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{NMTMA-14-714, author = {Duan , Li-Xiao and Zhang , Guo-Feng}, title = {Variant of Greedy Randomized Gauss-Seidel Method for Ridge Regression}, journal = {Numerical Mathematics: Theory, Methods and Applications}, year = {2021}, volume = {14}, number = {3}, pages = {714--737}, abstract = {

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$.

}, issn = {2079-7338}, doi = {https://doi.org/10.4208/nmtma.OA-2020-0095}, url = {http://global-sci.org/intro/article_detail/nmtma/19195.html} }
TY - JOUR T1 - Variant of Greedy Randomized Gauss-Seidel Method for Ridge Regression AU - Duan , Li-Xiao AU - Zhang , Guo-Feng JO - Numerical Mathematics: Theory, Methods and Applications VL - 3 SP - 714 EP - 737 PY - 2021 DA - 2021/06 SN - 14 DO - http://doi.org/10.4208/nmtma.OA-2020-0095 UR - https://global-sci.org/intro/article_detail/nmtma/19195.html KW - Randomized algorithms, ridge regression, greedy randomized Gauss-Seidel, randomized Kaczmarz, iterative method. AB -

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$.

Li-Xiao Duan & Guo-Feng Zhang. (2021). Variant of Greedy Randomized Gauss-Seidel Method for Ridge Regression. Numerical Mathematics: Theory, Methods and Applications. 14 (3). 714-737. doi:10.4208/nmtma.OA-2020-0095
Copy to clipboard
The citation has been copied to your clipboard