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