  We study how the learning rate affects the performance of a relaxed
randomized Kaczmarz algorithm for solving $A x \approx b + \varepsilon$, where
$A x =b$ is a consistent linear system and $\varepsilon$ has independent mean
zero random entries. We derive a learning rate schedule which optimizes a bound
on the expected error that is sharp in certain cases; in contrast to the
exponential convergence of the standard randomized Kaczmarz algorithm, our
optimized bound involves the reciprocal of the Lambert-$W$ function of an
exponential.
