Adaptive Row Selection Meets Asynchrony in Randomized Kaczmarz

Abstract

Randomized Kaczmarz is a natural fit for large sparse least-squares and tomographic reconstruction, and adaptive row selection can reduce iteration counts. However, deploying adaptive selection on a shared-memory machine means sampling from a residual that lock-free workers are concurrently modifying, often using stale data. We present the first systematic study of this regime: residual-weighted and greedy Kaczmarz under asynchronous execution, measured across 339 runs on a 96-core node with realized (not injected) delays. Four findings carry directly to practice. (i) Stability is governed by a boundary ${\ell }^{\ast }(T)$ between sampling aggressiveness and thread count; below it, more aggressive sampling is strictly better, so one should tune to just inside the cliff. (ii) Threshold-greedy selection (the standard accelerated rule) is unstable at high thread counts, diverging almost immediately. (iii) Under-relaxation buys back the cliff at a predictable cost, giving a usable safety knob. (iv) Consistent-snapshot reads admit a rare, scheduling-dependent divergence that live (inconsistent) reads never exhibited; live reads also cost less per step, making them the right default. We validate the implementation against published sequential results and outline the distributed two-level sampler these measurements motivate.