Timezone: »

 
Poster
Randomized Block-Diagonal Preconditioning for Parallel Learning
Celestine Mendler-Dünner · Aurelien Lucchi

Thu Jul 16 12:00 PM -- 12:45 PM & Fri Jul 17 12:00 AM -- 12:45 AM (PDT) @
in Poster Session 45 »

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.

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

Author Information

Celestine Mendler-Dünner (University of California, Berkeley)
Aurelien Lucchi (ETH Zurich)

More from the Same Authors