Global Asymptotic Rates Under Randomization: Gauss-Seidel and Kaczmarz
This work addresses a fundamental issue in numerical analysis and optimization for researchers and practitioners, providing tighter theoretical guarantees that better match empirical observations.
The paper tackles the theory-practice gap in performance bounds for randomized iterative methods like Gauss-Seidel and Kaczmarz, deriving asymptotic bounds that narrow this gap and quantifying the role of relaxation to improve performance, resolving an open problem from 2007.
Current performance bounds for randomized iterative methods are often considered tight under per-iteration analyses, yet they are notoriously loose in practice. We derive asymptotic performance bounds that narrow this theory-practice gap, leveraging a new technique for bounding the spectral radii of operators arising in randomized iterations and a connection we establish to Perron-Frobenius theory for noncommutative algebras. The asymptotic analysis also uncovers and quantifies the previously unexplained role of relaxation in improving performance, thereby resolving an open problem posed by Strohmer and Vershynin in 2007.