gconcord 1.0.2

Unified CONCORD Package for Sparse Precision Matrix Estimation

gconcord

A Python package for sparse precision matrix estimation using the graphical CONCORD (CONvex CORrelation selection methoD) algorithm.

Overview

The graphical CONCORD algorithm is a sparse penalized maximum pseudo-likelihood estimator for the precision matrix (Khare et al., 2014; Ali et al., 2017). This package provides a unified implementation of multiple algorithmic approaches to solve the CONCORD optimization problem (Oh et al., 2014; Ali et al., 2017), combining high-performance C++ implementations with an intuitive Python interface.

Authors

Lixing Guo, Sang-Yun Oh

Features

• Multiple algorithm variants: Coordinate descent, ISTA, and Symmetric Lasso implementations
• Automatic algorithm selection: Intelligent defaults based on problem dimensions
• High performance: C++ backend with Eigen linear algebra library
• Flexible penalty parameters: Scalar or matrix-valued regularization
• Sparse matrix support: Memory-efficient storage via scipy.sparse
• Backward compatibility: Maintains compatibility with the original gconcord interface

Installation

From PyPI

pip install gconcord

From Source

git clone https://github.com/dddlab/gconcord.git
cd gconcord
pip install .

Requirements

• Python >= 3.7 (3.8+ required for Linux)
• NumPy >= 1.19.0
• SciPy >= 1.5.0
• C++14 compatible compiler (for building from source)

Platform Support

gconcord provides pre-built wheels for:

• Linux: x86_64 architecture (Python 3.8+)
• macOS: Intel (x86_64) and Apple Silicon (arm64) (Python 3.7+)
• Python: 3.7, 3.8, 3.9, 3.10, 3.11

Note: Python 3.7 is supported on macOS only due to compatibility constraints on Linux. Linux ARM64 (aarch64) support is not available in pre-built wheels.

The package is continuously tested on Ubuntu and macOS through GitHub Actions.

Quick Start

import numpy as np
import gconcord as gc

# Generate sample data
np.random.seed(42)
p = 50
A = np.random.randn(p, p)
S = A @ A.T + 0.1 * np.eye(p)  # Sample covariance matrix

# Estimate sparse precision matrix
result = gc.concord(S, lambda_param=0.1, max_iterations=500)

# Access results
omega = result['omega']  # Sparse precision matrix
print(f"Converged: {result['converged']}")
print(f"Iterations: {result['iterations']}")
print(f"Sparsity: {1 - omega.nnz / p**2:.2%}")

Usage

Basic Usage

The package provides three main functions:

concord() - Main interface for CONCORD algorithms

result = gc.concord(
    S,                      # Sample covariance matrix
    lambda_param=0.1,       # Regularization parameter
    algorithm='auto',       # Algorithm selection
    tolerance=1e-5,         # Convergence tolerance
    max_iterations=100      # Maximum iterations
)

symlasso() - Symmetric Lasso algorithms

result = gc.symlasso(
    S,
    lambda_param=0.1,
    algorithm='symlasso'    # or 'symlasso_iterates'
)

ccista() - Backward-compatible ISTA interface

omega, hist = gc.ccista(
    S,
    lambda1=0.1,
    epstol=1e-5,
    maxitr=100
)

Advanced Features

Matrix-valued penalties

# Custom penalty matrix
Lambda = np.ones((p, p)) * 0.1
np.fill_diagonal(Lambda, 0)  # Don't penalize diagonal
Lambda[0, 1] = Lambda[1, 0] = 0  # No penalty for specific edges

result = gc.concord(S, lambda_param=Lambda)

Algorithm-specific options

# Use high-dimensional variant with data matrix
data = np.random.randn(n, p)  # n samples, p features
result = gc.concord(data=data, lambda_param=0.1, algorithm='coordinate_high_dim')

# Save iteration history
result = gc.concord(S, lambda_param=0.1, save_iterates=True)
objectives = result['objective_values']

Algorithm Descriptions

Coordinate Descent Variants

• coordinate: Standard coordinate descent (concordC)
• coordinate_high_dim: High-dimensional variant with residual updates (concordC2)
• coordinate_blas: BLAS-optimized implementation (concordC3)

ISTA (Iterative Shrinkage-Thresholding Algorithm)

• Matrix-based proximal gradient method
• Adaptive step size with backtracking line search
• Suitable for small to medium problems

Symmetric Lasso

• symlasso: Standard symmetric lasso (symlassoC)
• symlasso_iterates: Variant that saves iteration history (symlassoC2)

Mathematical Formulation

GCONCORD solves the following optimization problem:

minimize_Ω  -log det(Ω) + tr(SΩ) + λ||Ω||₁
subject to  Ω ≻ 0

where:

• Ω is the precision matrix (inverse covariance)
• S is the sample covariance matrix
• λ controls the sparsity level
• ||·||₁ denotes the element-wise L1 norm

Performance Considerations

• For small problems, ISTA often converges fastest
• For medium problems, coordinate descent variants are recommended
• For high-dimensional problems (n < p), use coordinate_high_dim with data matrix
• The auto algorithm selection provides good defaults for most use cases

References

• Khare, K., Oh, S.-Y., and Rajaratnam, B. (2014). A convex pseudolikelihood framework for high dimensional partial correlation estimation with convergence guarantees. Journal of the Royal Statistical Society: Series B, 77(4), 803-825.

• Oh, S.-Y., Dalal, O., Khare, K., and Rajaratnam, B. (2014). Optimization methods for sparse pseudo-likelihood graphical model selection. Advances in Neural Information Processing Systems, 27.

• Ali, A., Khare, K., Oh, S.-Y., and Rajaratnam, B. (2017). Generalized pseudolikelihood methods for inverse covariance estimation. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics.

License

This project is licensed under the MIT License - see the LICENSE file for details.

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

Support

For questions and bug reports, please open an issue on GitHub.