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 any $A$? 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 \le 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.
Introduction
The Gauss-Seidel (G-S) method is a pillar of numerical linear algebra, favored for its simplicity: to solve $Ax=b$, one updates one variable at a time using one equation. However, G-S has a major "Achilles' heel"—it only reliably converges if the matrix $A$ is symmetric positive definite (SPD) or diagonally dominant. For a general matrix $A$, the standard G-S algorithm and its cousin, Successive Over-Relaxation (SOR), can easily diverge.
While row-action methods like the Randomized Kaczmarz (RK) algorithm exist, they update the entire vector $x$ at once. G-S is distinct because it updates only a single coordinate, which is often more computationally efficient in distributed settings or for specific hardware architectures. This paper introduces the Doubly Stochastic Gauss-Seidel (DSGS) algorithm, the first G-S variant provably guaranteed to converge linearly for any feasible linear system, regardless of the matrix's properties.
Methodology
The core innovation is the Doubly Stochastic approach. In traditional G-S, variable $x_i$ is "locked" to equation $i$. The authors break this bond through two key mechanisms:
- Unlocking Pairs: At each step, the algorithm selects a pair $(i, j)$, where $i$ is the index of an equation and $j$ is the index of a variable.
- Non-Uniform Sampling: Instead of picking pairs uniformly at random—which can still lead to divergence—they use a specific probability distribution: $p_{ij} = a_{ij}^2 / \|A\|_F^2$. This ensures that variables are more likely to be updated using equations where they have a high "influence" (larger coefficients).
The algorithm also introduces a stepsize control $\alpha$. For a system with $n$ variables, a stepsize of $\alpha = 1/n$ is shown to be optimal for convergence. This framework generalizes to linear feasibility problems ($Ax \le b$) and over-parameterized machine learning models, where it manifests as a Doubly Stochastic Gradient Descent (DSGD) variant.
Experimental Evaluation
The authors evaluated DSGS using synthetically generated random matrices of varying sizes (e.g., $40 \times 20$ to $80 \times 140$) and condition numbers ($10^1$ to $10^3$).
Key Results: * Provable Linear Convergence: Rigorous proofs show that DSGS converges at a linear rate for any feasible system. * Iteration Efficiency: In numerical tests, DSGS frequently required fewer iterations than Randomized Kaczmarz (RK) and Randomized Gauss-Seidel (RGS) to reach an error level of $10^{-10}$. For a $40 \times 30$ system, DSGS took ~17k iterations vs. ~29k for RK. * Robustness: While all algorithms slow down as the condition number increases, DSGS maintained a consistent edge in iteration counts across different scenarios.
Discussion and Conclusion
The most striking insight is that a deterministic algorithm that diverges on a specific problem can be made to converge globally and linearly simply by adding the right kind of randomness. By allowing any equation to update any variable, the algorithm gains the flexibility to navigate the optimization landscape more effectively than the rigid mapping of classical G-S.
In distributed systems, DSGS is highly efficient, requiring significantly less communication than methods that update the entire vector. While there is some CPU overhead in sampling from a 2D distribution, the reduction in iteration count and communication makes it a compelling alternative for large-scale linear systems and over-parameterized ML models. Future work may address the behavior of DSGS on inconsistent systems where no solution exists.
Summary updated