提出无需预处理的正则化块Kacz马尔兹算法,提升收敛稳定性。
Worth Their Weight: Randomized and Regularized Block Kaczmarz Algorithms without Preprocessing
- 均匀采样数据,通过正则化控制偏差与方差
- 在奇异值快速衰减问题上优于传统方法
- 适合处理不一致线性最小二乘问题
随着机器学习与科学计算中数据量持续增长,开发仅每次采样少量数据的算法变得愈发重要。在线性最小二乘问题中,随机块Kaczmarz方法(RBK)是此类算法的代表性方案,但其收敛性分析依赖于需昂贵预处理的采样分布。本文研究在均匀采样下的RBK,发现其迭代序列以蒙特卡洛意义收敛至加权最小二乘解。然而,对一般问题,该解的偏差与迭代方差可能无限增大。通过在迭代中引入正则化,我们提出正则化算法ReBlocK,可严格控制上述量。数值实验表明,在奇异值快速衰减的不一致问题上,ReBlocK性能优于RBK和小批量随机梯度下降。
原文摘要 · Abstract (English)
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 bias of the weighted least-squares solution and the variance of the iterates can become arbitrarily large. We show that these quantities can be rigorously controlled 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。