An optimal scheduled learning rate for a randomized Kaczmarz algorithm

Autor:	Marshall, Nicholas F., Mickelin, Oscar
Rok vydání:	2022
Předmět:	Mathematics - Numerical Analysis Computer Science - Machine Learning Mathematics - Classical Analysis and ODEs Mathematics - Probability
Druh dokumentu:	Working Paper
Popis:	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. Comment: 19 pages, 7 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2202.12224 Zobrazit plný text záznamu View this record from Arxiv