Source-linked AI summary
Sparse Inverse Covariance Selection via Alternating Linearization Methods
Katya Scheinberg, Shiqian Ma, Donald Goldfarb
TL;DR
The paper addresses sparse inverse covariance estimation for recovering conditional independencies in Gaussian graphical models. It proposes an alternating linearization method that exploits the objective’s structure, with closed-form subproblems and an O(1/ε) iteration guarantee. Experiments report that the practical algorithm outperforms competitive methods on synthetic and real problems.
Problem
Estimating sparse inverse covariance matrices recovers Gaussian graphical-model structure, but the cardinality formulation is NP-hard and scalable optimization methods face high computational costs.
Method
ALM solves the primal SICS problem by alternating linearizations that exploit its structure and yield closed-form subproblems.
Results
ALM obtains an ε-optimal solution in O(1/ε) iterations and, in experiments, significantly outperforms PSM and VSM.
Takeaways & Limitations
The method provides a first-order approach with complexity guarantees for sparse inverse covariance selection and strong performance on synthetic and real data.
Takeaways & Limitations
Because the gradient Lipschitz bound can be very large, the theoretical convergence-rate guarantee is practical only in a small neighborhood of the optimum.
Abstract
from arXiv · showhide
Gaussian graphical models are of great interest in statistical learning. Because the conditional independencies between different nodes correspond to zero entries in the inverse covariance matrix of the Gaussian distribution, one can learn the structure of the graph by estimating a sparse inverse covariance matrix from sample data, by solving a convex maximum likelihood problem with an $\ell_1$-regularization term. In this paper, we propose a first-order method based on an alternating linearization technique that exploits the problem's special structure; in particular, the subproblems solved in each iteration have closed-form solutions. Moreover, our algorithm obtains an $ε$-optimal solution in $O(1/ε)$ iterations. Numerical experiments on both synthetic and real data from gene association networks show that a practical version of this algorithm outperforms other competitive algorithms.
1 Introduction
Gaussian graphical models recover conditional-independence structure through sparse inverse covariance estimation, but the resulting optimization is challenging at scale. The paper proposes ALM as a structured first-order alternative with complexity guarantees and strong empirical performance.
- Zero entries in Σ^-1 encode conditional independencies, so learning the graph reduces to estimating a sparse inverse covariance matrix.
- Replacing the NP-hard cardinality penalty with an ℓ1 penalty yields a numerically tractable convex optimization problem.
- Interior-point methods solve SICS in polynomial time, but their per-iteration cost and memory requirements are prohibitively high for large problems.
- ALM solves the primal SICS problem by alternatingly minimizing objective terms and directly promoting sparsity through the primal ℓ1 penalty.
- ALM has a theoretically justified complexity framework, unlike Yuan’s method, while numerical tests report that it outperforms PSM and VSM.
2 Alternating Linearization Methods
The paper develops alternating linearization methods for minimizing sums of convex functions, with alternating approximations, convergence guarantees, and an O(1/ε) iteration bound. The resulting algorithms use simple subproblem updates and a skipping step to preserve convergence.
- Alternating Linearization Methods: ALM splits a sum of two convex functions by alternatingly minimizing one term plus an approximation to the other.The method linearizes one function and adds a quadratic prox term to construct the approximation.
- Alternating Linearization Methods: Each ALM iteration solves two subproblems by minimizing quadratic upper approximations together with the other convex function.The first approximation uses a linearization and prox term; the second similarly approximates the other function.
- Alternating Linearization Methods: Algorithm 2 adds a skipping step that replaces xk+1 with yk when the required upper-approximation condition fails.When the condition holds, Algorithm 2 agrees with symmetric ADAL; under smoothness, it agrees with Algorithm 1 without skipping.
- Alternating Linearization Methods: Algorithm 2 converges to an optimal solution in function value and requires O(1/ε) iterations for an ε-optimal solution.The bound applies under the stated range for μ and Lipschitz continuity of ∇f.
- Alternating Linearization Methods: An accelerated variant could achieve O(1/√ε) iterations with nearly unchanged per-iteration effort, but it performed worse than Algorithm 2 on SICS.The accelerated method is not presented because its practical performance on SICS was inferior.
3 ALM for SICS
For SICS, ALM addresses the difficult combination of a log-determinant data-fit term and an ℓ1 sparsity term through alternating updates. Its spectral and shrinkage subproblems provide practical updates, while the theoretical rate is limited by the gradient Lipschitz bound.
- 3 ALM for SICS: SICS combines fitting the observed covariance with obtaining a sparse inverse covariance matrix.The formulation uses f(X) = −log det(X) + ⟨Σ̂, X⟩ and g(X) = ρ∥X∥1, with X constrained to be positive definite.
- 3 ALM for SICS: The practical algorithm cannot generally enforce positive definiteness on Y because constrained minimization is harder and line searches substantially degrade performance.Consequently, the resulting Y iterates may not be positive definite.
- 3 ALM for SICS: The theoretical convergence-rate guarantee is practical only near the optimum because the gradient Lipschitz bound 1/α^2 can be very large.Restricting μ below α^2 is impractical because μ determines the iteration step size.
- 3 ALM for SICS: The X-update uses a spectral decomposition, while the Y-update uses elementwise shrinkage for the ℓ1 penalty.The spectral step costs O(n^3), whereas shrinkage costs O(n^2).
- 3 ALM for SICS: The X iterates remain positive definite inverse covariance matrices, while the Y iterates approach sparsity through alternating gradient and subgradient updates.The updates also interpret each step as imposing a Gaussian prior centered at the current estimate from the other sequence.
4 Numerical Experiments
The experiments evaluate ALM against PSM and VSM on synthetic and real gene-expression data, measuring accuracy, runtime, and sparsity. ALM is faster and more accurate in the reported tests, while producing essentially the same sparsity patterns.
- Experimental setup: ALM, PSM, and VSM have roughly the same per-iteration complexity, making iteration-count comparisons meaningful.The experiments use specified stopping criteria and parameter settings for each algorithm.
- Experiments on synthetic data: ALM outperforms PSM and VSM in accuracy and CPU time on randomly generated SICS problems, with the gap increasing as ρ increases.The synthetic comparisons use data generated from sparse inverse covariance matrices and report CPU times in seconds.
- Experiments on synthetic data: For ρ = 1.0 and n = 2000, ALM reaches Dgap = 9.58e-4 in about 1 hour and 15 minutes, versus about 3 hours and 25 minutes for PSM and 10 hours and 23 minutes for VSM.The competing methods achieve similar accuracy in this comparison.
- Experiments on real data: On five real gene-expression datasets, ALM is much faster and provides more accurate solutions than PSM and VSM.The datasets cover lymph node status, estrogen receptor, Arabidopsis thaliana, leukemia, and hereditary breast cancer.
- Solution sparsity: When ρ ≥ 0.5, all three algorithms produce exactly the same sparsity patterns, while their ROC curves are also almost identical.Slight sparsity differences occur only when ρ is very small.
5 Appendix
The appendix establishes convergence properties for the alternating linearization framework. It shows non-increasing objective sequences and an O(1/ε) iteration bound for obtaining an ε-optimal solution.
- Proof structure: The proof combines inequalities for iterations with and without skipping, using the relations x_{n+1} = y_n when skipping occurs.The index sets I and I^c separate iterations according to whether skipping occurs.
- Convergence: Algorithm 2 produces sequences F(y_n) and F(x_n) that are non-increasing.This follows from the preceding inequalities in the convergence proof.
- Iteration complexity: Algorithm 2 converges to the optimal solution in function value, requiring O(1/ε) iterations for an ε-optimal solution.The bound is stated for the number of iterations needed to achieve the specified function-value accuracy.