Worth Their Weight: Randomized and Regularized Block Kaczmarz Algorithms without Preprocessing
This work addresses a computational bottleneck in large-scale data algorithms for machine learning and scientific computing, offering an incremental improvement by eliminating preprocessing costs and enhancing stability.
The paper tackles the issue of expensive preprocessing in the randomized block Kaczmarz method for linear least-squares by analyzing uniform sampling, which leads to convergence to a weighted solution but with potential instability. They propose a regularized version called ReBlocK, which outperforms existing methods like RBK and minibatch SGD on inconsistent problems with rapidly decaying singular values, as shown in numerical experiments.
Due to the ever growing amounts of data leveraged for machine learning and scientific computing, it is increasingly important to develop algorithms that sample only a small portion of the data at a time. In the case of linear least-squares, the randomized block Kaczmarz method (RBK) is an appealing example of such an algorithm, but its convergence is only understood under sampling distributions that require potentially prohibitively expensive preprocessing steps. To address this limitation, we analyze RBK when the data is sampled uniformly, showing that its iterates converge in a Monte Carlo sense to a $\textit{weighted}$ least-squares solution. Unfortunately, for general problems the condition number of the weight matrix and the variance of the iterates can become arbitrarily large. We control these issues by incorporating regularization into the RBK iterations, yielding the regularized algorithm ReBlocK. Numerical experiments including examples arising from natural gradient optimization demonstrate that ReBlocK can outperform both RBK and minibatch stochastic gradient descent for inconsistent problems with rapidly decaying singular values.