An optimal scheduled learning rate for a randomized Kaczmarz algorithm
This work addresses an incremental improvement in optimization methods for linear algebra problems, specifically for researchers in numerical analysis and machine learning.
The authors tackled the problem of optimizing the learning rate schedule for a relaxed randomized Kaczmarz algorithm to solve linear systems with noise, deriving a schedule that minimizes an expected error bound, which involves the reciprocal of the Lambert-W function of an exponential, contrasting with the exponential convergence of the standard algorithm.
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.