To conduct a more in-depth investigation of randomized solvers for general linear systems, we adopt a unified randomized batch-sampling Kaczmarz framework with per-iteration costs as low as cyclic block methods, and develop a general analysis technique to establish its convergence guarantee. With concentration inequalities, we derive new expected linear convergence rate bounds. The analysis applies to any randomized non-extended block Kaczmarz methods with static stochastic samplings. In addition, the new rate bounds are scale-invariant which eliminate the dependence on the magnitude of the data matrix. In most experiments, the new bounds are significantly tighter than existing ones and better reflect the empirical convergence behavior of block methods. Within this new framework, the batch-sampling distribution, as a learnable parameter, provides the possibility for block methods to achieve efficient performance in specific application scenarios, which deserves further investigation.

翻译：为更深入研究一般线性系统的随机求解器，我们采用统一的随机批量采样Kaczmarz框架，其单次迭代计算成本与循环块方法相当，并发展了一种通用分析技术以建立其收敛性保证。利用集中不等式，我们推导出新的期望线性收敛速率界。该分析适用于任何采用静态随机采样的随机非扩展块Kaczmarz方法。此外，新的速率界具有尺度不变性，消除了对数据矩阵幅值的依赖。在多数实验中，新界显著优于现有界，且能更好反映块方法的实际收敛行为。在此新框架下，作为可学习参数的批量采样分布，为块方法在特定应用场景中实现高效性能提供了可能性，值得进一步深入研究。