Skip to yearly menu bar Skip to main content


Randomized Block-Diagonal Preconditioning for Parallel Learning

Celestine Mendler-D√ľnner · Aurelien Lucchi

Keywords: [ Convex Optimization ] [ Parallel and Distributed Learning ] [ Optimization - Large Scale, Parallel and Distributed ]


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 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.

Chat is not available.