A0265
Title: An efficient parallel block coordinate descent algorithm for large-scale precision matrix estimation using GPUs
Authors: Young-Geun Choi - Sookmyung Women University (Korea, South)
Seunghwan Lee - Inha University (Korea, South)
Donghyeon Yu - Inha University (Korea, South) [presenting]
Abstract: Large-scale sparse precision matrix estimation has attracted wide interest from the statistics community. The convex partial correlation selection method (CONCORD) has recently been credited with some theoretical properties for estimating sparse precision matrices. The CONCORD obtains its solution by a coordinate descent algorithm (CONCORD-CD) based on the convexity of the objective function. However, since a coordinate-wise update in CONCORD-CD is inherently serial, a scale-up is nontrivial. We propose a novel parallelization of CONCORD-CD, namely, CONCORD-PCD. CONCORD-PCD partitions the off-diagonal elements into several groups and updates each group simultaneously without harming the computational convergence of CONCORD-CD. We guarantee this by employing the notion of edge coloring in graph theory. It turns out that CONCORD-PCD simultaneously updates off-diagonal elements in which the associated edges are colorable with the same color. As a result, the number of steps required for updating off-diagonal elements reduces from $p(p-1)/2$ to $p-1$ (for even $p$) or $p$ (for odd $p$), where $p$ denotes the number of variables. We prove that the number of such steps is irreducible. A numerical study shows that the SIMD-parallelized PCD algorithm implemented in graphics processing units (GPUs) boosts the CONCORD-CD algorithm multiple times.
