An efficient parallel block coordinate descent algorithm for large-scale precision matrix estimation using graphics processing units
From MaRDI portal
Publication:2135867
Abstract: Large-scale sparse precision matrix estimation has attracted wide interest from the statistics community. The convex partial correlation selection method (CONCORD) developed by Khare et al. (2015) 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. In this paper, 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. Specifically, we establish a nontrivial correspondence between scheduling the updates of the off-diagonal elements in CONCORD-CD and coloring the edges of a complete graph. 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 In addition, CONCORD-PCD is tailored to single-instruction multiple-data (SIMD) parallelism. A numerical study shows that the SIMD-parallelized PCD algorithm implemented in graphics processing units (GPUs) boosts the CONCORD-CD algorithm multiple times.
Recommendations
- Gaussian graphical models parallel estimation via coordinate descent neighborhood selection
- ADMM algorithmic regularization paths for high-dimensional sparse precision matrix estimation
- Partial correlation screening for estimating large precision matrices, with applications to classification
- Efficient distributed estimation of high-dimensional sparse precision matrix
- Fast algorithms for sparse inverse covariance estimation
Cites work
- A constrained \(\ell _{1}\) minimization approach to sparse precision matrix estimation
- A convex pseudolikelihood framework for high dimensional partial correlation estimation with convergence guarantees
- A survey of graph coloring -- its types, methods and applications
- Basic Linear Algebra Subprograms for Fortran Usage
- Computer science today. Recent trends and developments
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Emergence of Scaling in Random Networks
- Estimating sparse precision matrix: optimal rates of convergence and adaptive estimation
- Fused lasso regression for identifying differential correlations in brain connectome graphs
- High-dimensional graphs and variable selection with the Lasso
- scientific article; zbMATH DE number 6378086 (Why is no real title available?)
- Model selection and estimation in the Gaussian graphical model
- Parallel coordinate descent methods for big data optimization
- Partial correlation estimation by joint sparse regression models
- QUIC: quadratic approximation for sparse inverse covariance estimation
- Sparse inverse covariance estimation with the graphical lasso
- Sparse matrix inversion with scaled Lasso
- The graphical lasso: new insights and alternatives
- The Joint Graphical Lasso for Inverse Covariance Estimation Across Multiple Classes
- The Structure and Function of Complex Networks
Cited in
(5)- Partial correlation screening for estimating large precision matrices, with applications to classification
- A Hierarchically Blocked Jacobi SVD Algorithm for Single and Multiple Graphics Processing Units
- pcdconcord
- An efficient GPU-parallel coordinate descent algorithm for sparse precision matrix estimation via scaled Lasso
- Parallel block coordinate descent methods with identification strategies
This page was built for publication: An efficient parallel block coordinate descent algorithm for large-scale precision matrix estimation using graphics processing units
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2135867)
