Residual-Weighted Randomized Jacobi: Sharpened Bounds via Residual Concentration and Asynchronous Extension

Technical Summary: Residual-Weighted Randomized Jacobi: Sharpened Bounds via Residual Concentration and Asynchronous Extension

Problem Statement
The paper addresses the convergence analysis of randomized stationary methods for solving symmetric positive definite (SPD) linear systems $Ax = b$. While uniform random sampling is simple to implement and analyze, it treats all components as equally important, potentially wasting updates on components with negligible residual mass. Conversely, greedy methods like Gauss–Southwell selection are efficient per iteration but require global sorting or priority maintenance, which is costly and awkward in asynchronous or distributed settings. The authors investigate a middle ground: residual-weighted sampling, where component $j$ is selected with probability proportional to $|r_j|^\ell$ (where $r$ is the residual). This family interpolates between uniform sampling ($\ell \to 0$) and greedy selection ($\ell \to \infty$). The core challenge is to quantify the convergence benefits of this adaptive bias, particularly in asynchronous settings where the residual used for sampling may be stale.

Methodology
The authors develop a theoretical framework centered on the Inverse Participation Ratio (IPR) of the residual, defined as $\nu_2(r) = n \|r\|_4^4 / \|r\|_2^4$. The IPR measures the "concentration" of the residual: it equals 1 for a uniform residual and grows toward $n$ as the residual concentrates on fewer components.

1. Synchronous Analysis:

   • The authors first establish a baseline worst-case bound for power-weighted sampling with any $\ell > 0$, showing it matches the standard uniform randomized Jacobi bound.
   • For the specific case of $\ell = 2$ (sampling proportional to squared residuals), they derive a sharpened one-step convergence bound. They prove that the expected per-step progress is amplified by exactly the factor $\nu_2(r)$ relative to the uniform baseline. This bound is tight when the residual is non-uniform.
   • The IPR is shown to be computable online at $O(n)$ cost, serving as a per-iteration diagnostic.

2. Asynchronous Extension:

   • The analysis is extended to asynchronous power-weighted Jacobi using the Avron–Druinsky–Gupta (ADG) framework.
   • The authors identify three obstacles unique to residual-dependent sampling: (1) the coupling between stale residuals and sampling probabilities breaks the independence-of-delays assumption; (2) the cross-term bounds lose the favorable $1/n$ scaling of uniform sampling; and (3) the progress lemma requires a two-sided bound.
   • To overcome these, they assume a uniform bound on the IPR trajectory ($\nu_{min} \le \nu_2(\tilde{r}^{(j)}) \le \nu_{max}$) throughout an epoch.
   • The resulting convergence theorem (Theorem 10) shows that the progress coefficient is amplified by $\nu_{min}$, while the allowable delay window is constrained by $\nu_{max}$. The bound is structurally analogous to ADG's epoch-reduction theorem but reflects a tradeoff: residual concentration accelerates progress but increases interference.

3. Read Mode Analysis:

   • The paper investigates the impact of consistent reads (snapshotting the residual) versus inconsistent reads (reading values atomically as needed).
   • Theoretically, consistent reads are the standard "easy" case for ADG analysis. However, the authors hypothesize that for power-weighted sampling, consistent reads amplify thread collisions because multiple threads may sample the same high-residual component based on the same stale snapshot, leading to destructive "pile-up" overshoots.

Key Contributions

1. Adaptivity Spectrum: The paper positions residual-weighted sampling between fixed randomized methods and fully greedy relaxation, providing a continuous parameter $\ell$ to control aggressiveness without sorting.
2. Worst-Case Guarantee: It proves that power-weighted sampling never performs worse than uniform sampling in the worst case.
3. IPR-Sharpened Bound: For $\ell=2$, it derives a convergence bound where the contraction factor is explicitly amplified by the IPR ($\nu_2$), providing a theoretical separation between uniform and residual-weighted sampling whenever the residual is non-uniform.
4. Asynchronous Convergence Theorem: It extends the ADG framework to residual-dependent sampling, establishing an epoch-based convergence result under a uniform IPR trajectory assumption.
5. Empirical Discovery on Read Modes: The paper reports a counter-intuitive finding: in high-concurrency settings, consistent reads destabilize power-weighted sampling, while inconsistent reads remain stable. The authors attribute this to the IPR amplifying both progress and collision rates; inconsistent reads provide a "feedback-damping" mechanism where the second read of the residual absorbs the collision effect.

Results

• Numerical Experiments: Experiments on three SPD problems (Laplacian, Poisson with localized forcing, and FEM mass matrix) show that the IPR remains significantly above 1 (typically in the range 4–6) throughout the iteration trajectory, even for smooth problems.
• Convergence Speed: On shared-memory hardware (96 threads), power-weighted sampling ($\ell=2$) converges measurably faster than uniform or cyclic sampling, particularly on the Poisson problem where residual concentration is high.
• Concurrency Insensitivity: The IPR trajectory is found to be essentially insensitive to thread count (varying by less than 3% across 1 to 128 threads), validating the assumption of a structural IPR bound used in the asynchronous theorem.
• Read Mode Stability: Hardware experiments confirm the theoretical prediction: consistent reads lead to divergence on all test problems at high concurrency, whereas inconsistent reads remain stable. Quadrupling the problem size ($n$) rescues consistent reads for problems where $\nu_2$ is bounded (Laplacian, FEM) but fails for problems where $\nu_2$ scales with $n$ (Poisson), confirming the collision probability scaling.

Significance and Claims
The paper claims to provide the first rigorous convergence analysis for residual-weighted randomized Jacobi that quantifies the benefit of residual non-uniformity via the IPR. It demonstrates that the IPR acts as a dual lever: it amplifies expected progress but also amplifies the risk of thread collisions in asynchronous settings.

The authors modestly note that their asynchronous theorem relies on a global IPR bound and that the cross-term analysis introduces a $\sqrt{n}$ scaling loss compared to uniform sampling, meaning the result is a complementary bound rather than a strict generalization of the uniform theory. The primary practical contribution is the identification of inconsistent reads as the necessary execution mode for stable, high-concurrency power-weighted sampling, and the proposal of the IPR as a structural diagnostic for both convergence speed and algorithmic safety. The paper concludes that while the theoretical bounds are conservative, the empirical gains in convergence speed and the stability of inconsistent reads make the method a viable candidate for scalable asynchronous solvers.