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.
翻译:我们研究学习率如何影响解答$A x $approx b + varepsilon$的宽松随机卡兹马兹算法的性能,在这种算法中,$A x = b = 美元是一个连贯的线性系统,$\ varepsilon$具有独立的平均零随机条目。我们得出一个学习率表,该表根据某些情况下的预期差错优化了界限;与标准的随机卡茨马兹算法的指数趋同相反,我们优化的结合涉及一个指数值的兰伯特- W$的对等功能。