Abstract
Consider the classical problem of solving a general linear system of equations Ax= b. It is well known that the (successively over relaxed) Gauss–Seidel scheme and many of its variants may not converge when A is neither diagonally dominant nor symmetric positive definite. Can we have a linearly convergent G–S type algorithm that works for anyA? In this paper we answer this question affirmatively by proposing a doubly stochastic G–S algorithm that is provably linearly convergent (in the mean square error sense) for any feasible linear system of equations. The key in the algorithm design is to introduce a nonuniform double stochastic scheme for picking the equation and the variable in each update step as well as a stepsize rule. These techniques also generalize to certain iterative alternating projection algorithms for solving the linear feasibility problem Ax≤ b with an arbitrary A, as well as high-dimensional minimization problems for training over-parameterized models in machine learning. Our results demonstrate that a carefully designed randomization scheme can make an otherwise divergent G–S algorithm converge.
| Original language | English (US) |
|---|---|
| Journal | Mathematical Programming |
| DOIs | |
| State | Published - Jan 1 2019 |
Fingerprint
Keywords
- Gauss–Seidel algorithm
- Linear systems of equations
- Nonuniform block coordinate descent algorithm
- Over-parameterized optimization
Cite this
A linearly convergent doubly stochastic Gauss–Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems. / Razaviyayn, Meisam; Hong, Mingyi; Reyhanian, Navid; Luo, Zhi Quan.
In: Mathematical Programming, 01.01.2019.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - A linearly convergent doubly stochastic Gauss–Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems
AU - Razaviyayn, Meisam
AU - Hong, Mingyi
AU - Reyhanian, Navid
AU - Luo, Zhi Quan
PY - 2019/1/1
Y1 - 2019/1/1
N2 - Consider the classical problem of solving a general linear system of equations Ax= b. It is well known that the (successively over relaxed) Gauss–Seidel scheme and many of its variants may not converge when A is neither diagonally dominant nor symmetric positive definite. Can we have a linearly convergent G–S type algorithm that works for anyA? In this paper we answer this question affirmatively by proposing a doubly stochastic G–S algorithm that is provably linearly convergent (in the mean square error sense) for any feasible linear system of equations. The key in the algorithm design is to introduce a nonuniform double stochastic scheme for picking the equation and the variable in each update step as well as a stepsize rule. These techniques also generalize to certain iterative alternating projection algorithms for solving the linear feasibility problem Ax≤ b with an arbitrary A, as well as high-dimensional minimization problems for training over-parameterized models in machine learning. Our results demonstrate that a carefully designed randomization scheme can make an otherwise divergent G–S algorithm converge.
AB - Consider the classical problem of solving a general linear system of equations Ax= b. It is well known that the (successively over relaxed) Gauss–Seidel scheme and many of its variants may not converge when A is neither diagonally dominant nor symmetric positive definite. Can we have a linearly convergent G–S type algorithm that works for anyA? In this paper we answer this question affirmatively by proposing a doubly stochastic G–S algorithm that is provably linearly convergent (in the mean square error sense) for any feasible linear system of equations. The key in the algorithm design is to introduce a nonuniform double stochastic scheme for picking the equation and the variable in each update step as well as a stepsize rule. These techniques also generalize to certain iterative alternating projection algorithms for solving the linear feasibility problem Ax≤ b with an arbitrary A, as well as high-dimensional minimization problems for training over-parameterized models in machine learning. Our results demonstrate that a carefully designed randomization scheme can make an otherwise divergent G–S algorithm converge.
KW - Gauss–Seidel algorithm
KW - Linear systems of equations
KW - Nonuniform block coordinate descent algorithm
KW - Over-parameterized optimization
UR - http://www.scopus.com/inward/record.url?scp=85066914389&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85066914389&partnerID=8YFLogxK
U2 - 10.1007/s10107-019-01404-0
DO - 10.1007/s10107-019-01404-0
M3 - Article
AN - SCOPUS:85066914389
JO - Mathematical Programming
JF - Mathematical Programming
SN - 0025-5610
ER -