The Kaczmarz algorithm was first introduced in 1937 to solve large systems of linear equations. Existing works on the convergence analysis of the randomized Kaczmarz algorithm typically provide exponential rates of convergence, with the base tending to one as the condition number of the system increases. Results of this kind do not work well for large systems of linear equations, and do not apply to the online algorithms on Hilbert spaces for machine learning. In this talk, we provide a condition number-free analysis, which leads to polynomial rates of weak convergence for the randomized Kaczmarz algorithm. We also show the applications to kernel-based machine learning.

学术海报.pdf