Randomized Block-Diagonal Preconditioning for Parallel Learning
This addresses the challenge of efficient parallel learning for practitioners, though it is incremental as it builds on existing block-diagonal preconditioning methods.
The paper tackles the problem of improving convergence in parallel gradient-based optimization by introducing a randomization technique that repartitions coordinates across tasks, leading to significant gains validated empirically on machine learning tasks.
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.