论文标题
并行学习的随机块 - 分节预处理
Randomized Block-Diagonal Preconditioning for Parallel Learning
论文作者
论文摘要
我们研究了基于梯度的优化方法，其中预处理矩阵具有块形式形式。这样的结构约束具有这样的优势：更新计算是块分离的，并且可以在多个独立任务中平行。我们的主要贡献是证明这些方法的收敛性可以通过随机化技术可以显着改善，该技术对应于在优化过程中跨任务的重新分配坐标。我们提供了一项理论分析，可以准确地表征重新分配的预期收敛增长，并在各种传统的机器学习任务上进行经验验证我们的发现。从实现的角度来看，块分离的模型非常适合并行化，如果可用共享内存，则可以非常有效地在现有方法的基础上实现随机化以改善收敛性。
We study preconditioned gradient-based optimization methods where the preconditioning matrix has block-diagonal form. Such a structural constraint comes with the advantage that the update computation is block-separable and can be parallelized across multiple independent tasks. Our main contribution is to demonstrate that the convergence of these methods can significantly be improved by a randomization technique which corresponds to repartitioning coordinates across tasks during the optimization procedure. We provide a theoretical analysis that accurately characterizes the expected convergence gains of repartitioning and validate our findings empirically on various traditional machine learning tasks. From an implementation perspective, block-separable models are well suited for parallelization and, when shared memory is available, randomization can be implemented on top of existing methods very efficiently to improve convergence.
