A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems

Meisam Razaviyayn, Mingyi Hong, Navid Reyhanian, Zhi-Quan Luo

TL;DR

This paper introduces the Doubly Stochastic Gauss-Seidel (DSGS) algorithm, the first Gauss-Seidel variant provably guaranteed to converge linearly for any feasible linear system $Ax=b$, regardless of the matrix's properties. By "unlocking" the traditional fixed pairing of equations to variables and using a clever non-uniform randomization scheme to pick update pairs, the authors transform a historically finicky algorithm into a robust tool for linear systems, feasibility problems, and over-parameterized machine learning.

What Problem Does This Paper Address?

The Gauss-Seidel (G-S) method is a pillar of numerical linear algebra, favored for its simplicity: to solve $Ax=b$, you update 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 or SOR) can easily diverge.

The authors ask a fundamental question: Can we design a G-S type algorithm that is linearly convergent for any matrix $A$?

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.

Methods

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.

  1. 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.
  2. Non-Uniform Sampling: Instead of picking pairs at random (which the authors show can still lead to divergence), they use a specific probability distribution: $$p_{ij} = \frac{a_{ij}^2}{\|A\|_F^2}$$ This means you are more likely to update a variable using an equation where that variable has a high "influence" (a larger coefficient).

  3. Stepsize Control: They introduce a stepsize $\alpha$. For a system with $n$ variables, a stepsize of $\alpha = 1/n$ is shown to be optimal for convergence.

  4. Generalization: They extend this logic to:
  5. Linear Feasibility ($Ax \le b$): The "Double Stochastic Alternating Projection" algorithm.
  6. Over-Parameterized ML: A "Doubly Stochastic Gradient Descent" (DSGD) for models where the number of parameters exceeds the number of data points (common in deep learning), where the global minimum loss is zero.

Datasets

The authors evaluated their algorithms using synthetically generated random matrices:

  • Over-determined systems: Matrices of sizes such as $40 \times 20$, $60 \times 30$, and $80 \times 40$.
  • Under-determined systems: Matrices of sizes such as $40 \times 100$ and $80 \times 140$.
  • Varying Condition Numbers: They used Singular Value Decomposition (SVD) to manually scale singular values, testing the algorithm's robustness against ill-conditioned matrices (condition numbers $10^1$ to $10^3$).

Key Insights and Ideas

  • Randomization as a Stabilizer: 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.
  • The Power of "Unlocking": By allowing any equation to update any variable, the algorithm gains the flexibility to navigate the optimization landscape more effectively than the rigid, one-to-one mapping of classical G-S.
  • Importance of Non-Uniformity: Uniformly picking pairs $(i, j)$ is insufficient. The probability must be weighted by the magnitude of the coefficients ($a_{ij}^2$) to ensure that the updates actually move the system toward the solution.
  • Distributed Efficiency: The authors note that in a distributed system, DSGS is highly efficient. It only requires a central controller to broadcast a single scalar (the residual of one equation) to one node, which then updates one coordinate. This requires significantly less communication than methods that update the entire vector.

Key Results

  • Provable Linear Convergence: The authors provide rigorous proofs that DSGS converges at a linear rate (the error drops exponentially) 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 example, in a $40 \times 30$ system, DSGS took ~17k iterations vs. ~29k for RK.
  • Robustness to Ill-Conditioning: While all algorithms slow down as the condition number increases, DSGS maintained a consistent edge in iteration counts across different condition numbers.
  • ML Application: For over-parameterized models, the DSGD variant showed faster convergence in terms of iterations compared to standard stochastic coordinate descent methods.

Limitations and Future Work

  • CPU Time Overhead: While DSGS wins on iteration count, it is not always the fastest in terms of wall-clock time. The overhead of sampling from a 2D probability distribution (picking a pair $i, j$) is higher than picking just a row or just a column.
  • Feasibility Requirement: The current proofs assume the system is consistent (has at least one solution). The behavior of DSGS on inconsistent systems (where $Ax=b$ has no solution) is a suggested area for future study.
  • Hyperparameter Sensitivity: The optimal stepsize $\alpha$ depends on the number of variables $n$, which is easy to know, but the convergence rate itself is tied to the matrix's condition number, which is harder to calculate upfront.

Summary updated

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 {\it 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 {\it 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 $A x\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.
BibTeX
@article{razaviyayn2019linearly,
  author = {Meisam Razaviyayn and Mingyi Hong and Navid Reyhanian and Zhi-Quan Luo},
  title = {{A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems}},
  journal = {Math. Program.},
  year = {2019},
  doi = {10.1007/s10107-019-01404-0},
}

Loading related content...

Figure