Convergence of the randomized kaczmarz algorithm in Hilbert space

Abstract

The randomized Kaczmarz algorithm recently draws much attention. Existing results on anal-ysis suffer from condition numbers of the linear equation systems. Although the randomized Kacz-marz algorithm has a natural generalization to Hilbert spaces (which covers online learning algo-rithms for a particular instance), the existing analysis does not. Although the large-scale linear equation system is an ideal scenario for the randomized Kaczmarz algorithm to outperform direct solvers, it is also a scenario the existing analysis is not satisfactory. In this research, we introduce the regularity assumption widely adopted in learning theory and obtain the polynomial convergence rate of the randomized Kaczmarz algorithm in Hilbert space under noise-free setting. We find that by nature, the randomized Kaczmarz algorithm converges weakly. Meanwhile, with noisy data, we study the relaxation method and obtain a strong convergence arbitrarily close to the minimax optimal rate. The result applies to online gradient descent learning algorithms and significantly improves the existing learning rate in literature.