Global Asymptotic Rates Under Randomization: Gauss-Seidel and Kaczmarz

Alireza Entezari, Arunava Banerjee

Current performance bounds for randomized iterative methods are often considered tight under per-iteration analyses, yet they are notoriously loose in practice. We derive asymptoti…