Rows vs. Columns: Randomized Kaczmarz or Gauss-Seidel for Ridge Regression

Ahmed Hefny, Deanna Needell, Aaditya Ramdas

Abstract

The Kaczmarz and Gauss-Seidel methods aim to solve a linear $m \times n$ system $\boldsymbol{X} \boldsymbol{\beta} = \boldsymbol{y}$ by iteratively refining the solution estimate; the former uses random rows of $\boldsymbol{X}$ and the latter uses random columns. Interest in these methods was recently revitalized by proofs of linear convergence in expectation for randomized variants (RK and RGS). This paper considers ridge regression, which solves $(\boldsymbol{X}^* \boldsymbol{X} + \lambda\boldsymbol{I}) \boldsymbol{\beta} = \boldsymbol{X}^* \boldsymbol{y}$. We present particular variants of RK and RGS for this system and derive their convergence rates. We show that one should always use RGS (columns) when $m > n$ and RK (rows) when $n > m$. This difference is tied to the minimum eigenvalue of the related matrices $\boldsymbol{X}^* \boldsymbol{X} + \lambda\boldsymbol{I}_n$ and $\boldsymbol{X} \boldsymbol{X}^* + \lambda\boldsymbol{I}_m$.

Introduction

In large-scale machine learning, solving the ridge regression problem—minimizing $\|y - X\beta\|_2^2 + \lambda\|\beta\|_2^2$—is a fundamental task. When the dataset is too large for direct solvers, randomized iterative methods like Randomized Kaczmarz (RK) and Randomized Gauss-Seidel (RGS) offer efficient alternatives. RK updates the solution by projecting onto the hyperplane defined by a randomly selected row (data point), while RGS updates a single coordinate of the solution by selecting a random column (feature).

While these methods are well-studied for standard linear systems, their application to regularized systems introduces new dynamics. A key question arises: should we iterate over rows, columns, or perhaps a combination of both?

Theoretical Framework: Primal and Dual

The authors analyze ridge regression through two distinct lenses:

  1. The Primal Approach (RGS): This involves solving the system $(X^*X + \lambda I_n)\beta = X^*y$ directly. Each iteration updates a coordinate of $\beta$ based on a column of $X$.
  2. The Dual Approach (RK): This involves solving $(XX^* + \lambda I_m)\alpha = y$, where the final solution is recovered via $\beta = X^*\alpha$. Each iteration updates a coordinate of $\alpha$ based on a row of $X$.

Convergence Analysis

The core contribution of this work is a unified convergence analysis for both methods. By framing both as instances of Randomized Coordinate Descent on different objective functions, the authors derive explicit convergence rates.

Side-by-side convergence derivation for Randomized Kaczmarz (RK) and Randomized Gauss-Seidel (RGS).

As shown in the table above, both methods exhibit linear convergence in expectation. However, the rate of convergence—determined by the contraction factor in the final row—is highly sensitive to the dimensions of the data matrix $X$.

The "Shape" Rule: $m$ vs $n$

The convergence rate depends on the smallest eigenvalue of the respective system matrices. In the ridge regression setting, the regularization parameter $\lambda$ acts as a "floor" for these eigenvalues.

  • Overdetermined Systems ($m > n$): When there are more samples than features, the primal matrix $X^*X + \lambda I_n$ is typically better conditioned. The RGS method achieves a faster convergence rate because its contraction factor involves the smallest non-zero singular value of $X$ plus $\lambda$. In contrast, the RK method's rate is limited by $\lambda$ alone.
  • Underdetermined Systems ($n > m$): When there are more features than samples, the dual matrix $XX^* + \lambda I_m$ becomes better conditioned. Here, RK dominates for the same reasons RGS does in the overdetermined case.

The Suboptimality of Mixing

The authors also evaluate the Augmented Projection Method (IZ), which attempts to solve a larger system combining both row and column updates. Their analysis reveals that this "mixing" strategy is mathematically suboptimal. Specifically, they prove that under standard initializations (e.g., $\beta_0 = 0$), half of the iterations in the IZ method are effectively "wasted" because they attempt to satisfy constraints that are already satisfied by the structure of the problem. Consequently, a "pure" strategy—choosing either RK or RGS based on the data's shape—is always more computationally efficient.

Conclusion

The choice between Randomized Kaczmarz and Randomized Gauss-Seidel for ridge regression is not arbitrary. It is dictated by the geometry of the data. For "tall" data ($m > n$), RGS is the superior choice; for "wide" data ($n > m$), RK is preferred. This work provides the theoretical foundation for this heuristic, showing that the optimal path to convergence lies in respecting the inherent dimensionality of the problem.

Summary updated

Abstract

The Kaczmarz and Gauss-Seidel methods aim to solve a linear $m \times n$ system $\boldsymbol{X} \boldsymbolβ = \boldsymbol{y}$ by iteratively refining the solution estimate; the former uses random rows of $\boldsymbol{X}$ {to update $\boldsymbolβ$ given the corresponding equations} and the latter uses random columns of $\boldsymbol{X}$ {to update corresponding coordinates in $\boldsymbolβ$}. Interest in these methods was recently revitalized by a proof of Strohmer and Vershynin showing linear convergence in expectation for a \textit{randomized} Kaczmarz method variant (RK), and a similar result for the randomized Gauss-Seidel algorithm (RGS) was later proved by Lewis and Leventhal. Recent work unified the analysis of these algorithms for the overcomplete and undercomplete systems, showing convergence to the ordinary least squares (OLS) solution and the minimum Euclidean norm solution respectively. This paper considers the natural follow-up to the OLS problem, ridge regression, which solves $(\boldsymbol{X}^* \boldsymbol{X} + λ\boldsymbol{I}) \boldsymbolβ = \boldsymbol{X}^* \boldsymbol{y}$. We present particular variants of RK and RGS for solving this system and derive their convergence rates. We compare these to a recent proposal by Ivanov and Zhdanov to solve this system, that can be interpreted as randomly sampling both rows and columns, which we argue is often suboptimal. Instead, we claim that one should always use RGS (columns) when $m > n$ and RK (rows) when $m < n$. This difference in behavior is simply related to the minimum eigenvalue of two related positive semidefinite matrices, $\boldsymbol{X}^* \boldsymbol{X} + λ\boldsymbol{I}_n$ and $\boldsymbol{X} \boldsymbol{X}^* + λ\boldsymbol{I}_m$ when $m > n$ or $m < n$.
BibTeX
@misc{hefny2015rows,
  author = {Ahmed Hefny and Deanna Needell and Aaditya Ramdas},
  title = {{Rows vs. Columns: Randomized Kaczmarz or Gauss-Seidel for Ridge Regression}},
  year = {2015},
  eprint = {1507.05844},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1507.05844},
}
Figure