PaperlayerView exact revision on arXiv

Source-linked AI summary

The Graphical Lasso: New Insights and Alternatives

Rahul Mazumder, Trevor Hastie

arXiv:1111.5479v2stat.MLcs.LG

TL;DR

Graphical lasso is useful for sparse precision estimation but can behave unexpectedly because its updates target the covariance matrix through the dual problem. This paper explains that behavior and proposes primal alternatives, concluding that dp-glasso is faster than glasso while preserving positive-definite precision estimates.

  • Problem

    Estimating a sparse positive-definite precision matrix is difficult when n ≪ p, while glasso can return a precision estimate that is not the exact inverse of its covariance estimate and may fail with warm starts.

  • Method

    The paper analyzes glasso through its dual block-coordinate ascent formulation and develops primal block-coordinate algorithms p-glasso and dp-glasso targeting Θ.

  • Results

    dp-glasso is faster than glasso and maintains a positive-definite precision matrix throughout its iterations, including when iterations stop early.

  • Takeaways & Limitations

    The paper concludes that dp-glasso is superior from several points of view for solving the graphical lasso problem.

  • Takeaways & Limitations

    Glasso warm starts are not guaranteed to converge unless the new starting point is dual-feasible; sufficiently large λ gaps can cause failure.

Abstract

from arXiv · show

The graphical lasso \citep{FHT2007a} is an algorithm for learning the structure in an undirected Gaussian graphical model, using $\ell_1$ regularization to control the number of zeros in the precision matrix ${\BΘ}={\BΣ}^{-1}$ \citep{BGA2008,yuan_lin_07}. The {\texttt R} package \GL\ \citep{FHT2007a} is popular, fast, and allows one to efficiently build a path of models for different values of the tuning parameter. Convergence of \GL\ can be tricky; the converged precision matrix might not be the inverse of the estimated covariance, and occasionally it fails to converge with warm starts. In this paper we explain this behavior, and propose new algorithms that appear to outperform \GL. By studying the "normal equations" we see that, \GL\ is solving the {\em dual} of the graphical lasso penalized likelihood, by block coordinate ascent; a result which can also be found in \cite{BGA2008}. In this dual, the target of estimation is $\BΣ$, the covariance matrix, rather than the precision matrix $\BΘ$. We propose similar primal algorithms \PGL\ and \DPGL, that also operate by block-coordinate descent, where $\BΘ$ is the optimization target. We study all of these algorithms, and in particular different approaches to solving their coordinate sub-problems. We conclude that \DPGL\ is superior from several points of view.

1 Introduction

The paper frames graphical lasso as a regularized approach to estimating sparse precision matrices and covariance structure when maximum-likelihood estimation is unavailable or poorly behaved. It revisits glasso’s properties and develops a unified analysis motivating alternative algorithms.

  • Motivation: Graphical lasso estimates a Gaussian covariance matrix through its sparse precision matrix Θ = Σ^-1.A zero precision-matrix entry implies conditional independence between the corresponding variables given the rest.
  • Motivation: Regularization is especially important when n ≪ p, because the ordinary maximum-likelihood estimate does not exist.Even when the MLE exists for p ≤ n, it is often poorly behaved.
  • Optimization problem: The optimization problem is a semidefinite program whose regularization controls sparsity in the estimated precision matrix.The paper’s algorithms operate either on Θ or on its inverse W = Θ^-1.
  • Paper contribution: The paper analyzes glasso’s properties and proposes alternative algorithms using a unified and more elementary framework.Some conclusions re-derive or extend results associated with earlier work.

2 Review of the glasso algorithm.

The review shows that glasso updates covariance-related quantities through blockwise lasso subproblems, but its precision updates are not a standard block-coordinate descent on the primal objective. Consequently, the primal objective can be non-monotone even while the dual objective increases monotonically.

  • Glasso updates: The stationarity conditions use subgradient signs for zero and nonzero precision entries, with w_ii = s_ii + λ.These conditions connect the precision-matrix optimization to the blockwise updates.
  • Glasso updates: Glasso cycles through columns and solves a lasso subproblem for each block using the previous round as a warm start.The procedure rearranges the target column, updates covariance entries, stores the resulting coefficients, and later recovers Θ’s diagonal and full matrix.
  • Observed behavior: The primal objective sequence produced by glasso is non-monotone, contrary to the behavior expected from primal block-coordinate descent.Figure 1 identifies zero crossings in successive primal-objective differences.
  • Problem with the updates: Glasso updates only w_12 even though changing θ_12 changes the full working covariance matrix W.The dependence of W_11 on θ_12 is therefore not fully incorporated during the update.
  • Dual interpretation: Glasso is actually performing block-coordinate ascent on the dual problem, whose optimization variable is the covariance matrix W.The dual objective rises monotonically, explaining the observed discrepancy in objective behavior.

3 A Corrected glasso block coordinate-descent algorithm

The corrected primal graphical lasso maintains the inverse relationship between Θ and W throughout block updates. It uses rank-one covariance updates, preserving positive definiteness and exact inversion at additional computational cost.

  • Corrected block update: p-glasso maintains W = Θ^-1 throughout the iterations and updates the entire working covariance after each precision block update.The covariance changes are implemented through simple rank-one updates.
  • Computational cost: O(p^2) operations are required for the rank-one updates associated with each block.This is the stated cost for the paired covariance updates.
  • Computational cost: p-glasso incurs additional O(p^2) work before and after each block update compared with glasso.The extra work enforces the exact inverse relationship between Θ and W.
  • Guarantees: After every row or column update, p-glasso keeps both Θ and W positive definite and satisfies ΘW = I_p for λ > 0.The algorithm is presented as the primal graphical lasso, or p-glasso.

4 What is glasso actually solving?

The paper establishes that glasso performs block-coordinate ascent on the dual graphical-lasso problem, optimizing covariance-related variables rather than Θ directly. Each block update is itself obtained through a dual box-constrained quadratic program.

  • The dual optimization variable is W = Θ^-1, so glasso operates on the covariance matrix rather than directly on Θ.
  • The dual formulation has the same optimal solution as the primal formulation because strong duality holds.
  • During a block update, only w12 is optimized while W11 remains fixed, unlike a direct Θ update that changes the full working covariance structure.
  • glasso performs block-coordinate ascent on the box-constrained SDP dual of the primal graphical-lasso problem.
  • Each glasso block step solves a box-constrained QP through the QP's Lagrange dual.

5 A New Algorithm — dp-glasso

dp-glasso is a primal coordinate-descent alternative that updates Θ directly using a box-constrained QP. It avoids the main computational and structural drawbacks associated with the original primal block formulation.

  • The primal block formulation requires constructing Θ^-1_11 at every row/column update, costing O(p^2).
  • A modification of the ℓ1-regularized QP yields a box-constrained QP with attractive computational properties.
  • By strong duality, the new box-constrained QP is equivalent to the original lasso block problem, while its sparse Θ11 avoids O(p^2) updating after each block.
  • Tight convergence criteria or thresholding may be needed because computed θ12 values need not be exactly sparse.
  • dp-glasso operates on the precision matrix Θ, paralleling what glasso does for the dual covariance formulation.

6 Computational Costs in Solving the Block QPs

The computational cost of solving the block subproblems depends on the formulation, regularization level, sparsity, and convergence behavior. Although dense box-QP updates can be expensive, sparsity and boundary effects improve dp-glasso's practical efficiency.

  • For the ℓ1-regularized QP, a sweep costs O(qκ) when the solution has κ nonzeros, because zero coordinates can be skipped.
  • For a dense box-QP matrix, one full coordinate cycle costs O(q^2), since every coordinate update changes a length-q gradient.
  • When the box-QP matrix is sparse with κq nonzeros, the average per-column cost falls to O(κq).
  • For large λ, Θ11 becomes sparse, making glasso and dp-glasso have similar costs despite their different subproblem formulations.
  • For smaller λ, many box-QP coordinates reach the boundaries {−λ, λ}, reducing how often those coordinates require updates.
  • Overall complexity is difficult to characterize precisely because outer cycles and inner QP iterations vary with the problem and warm starts.

7 glasso: Positive definiteness, Sparsity and Exact Inversion

glasso preserves positive definiteness for its working covariance but not necessarily for its separately retained precision estimate, which may also fail to equal the covariance inverse before convergence. The primal alternatives are designed to return sparse positive definite precision matrices during intermediate iterations.

  • Before asymptotic convergence, glasso's retained Θ need not equal W^-1, as illustrated by the squared Frobenius-norm error across iterations.
  • The estimated precision matrix Θ produced by glasso need not remain positive definite along iterations, as shown by its minimum eigenvalue.
  • Approximate solutions may be sufficient when computational accuracy is impractical, provided Θ is sparse and positive definite.
  • Although glasso maintains a positive definite covariance matrix, its non-inverse precision estimate may be indefinite.
  • Replacing Θ with the exact inverse W^-1 restores inversion but can produce a dense matrix, while thresholding may destroy positive definiteness.
  • dp-glasso maintains positive definite Θ after each update, while exact covariance estimates can be recovered by tracking Θ^-1 separately.
  • Unlike glasso, dp-glasso and p-glasso return sparse positive definite precision matrices even when row/column iterations stop prematurely.

8 Warm Starts and Path-seeking Strategies

The paper distinguishes warm-start behavior between dual glasso and primal p-glasso/dp-glasso algorithms. Dual glasso warm starts require dual feasibility for guaranteed convergence, whereas any positive-definite warm start guarantees convergence for the primal methods.

  • Warm-start motivation: Warm starts reuse the solution at λ_i as an initial guess for a typically decreasing sequence λ_1 > λ_2 > ... > λ_K.This continuation strategy can improve efficiency, but its convergence properties depend on the formulation being optimized.
  • Dual glasso: Glasso operates on the dual covariance formulation, so a warm start must be positive definite and satisfy ∥Z−S∥∞≤λ to preserve positive definiteness.Without the feasibility condition, a row/column update need not maintain positive definiteness of W.
  • Dual glasso: For a lower λ′, glasso is not guaranteed to converge when the supplied warm start is not dual feasible, although convergence is usually observed when λ′ is close to λ.The paper gives a numerical example where a warm-start update produces negative eigenvalues in the working covariance matrix.
  • Primal methods: Any positive-definite warm start guarantees that every p-glasso or dp-glasso row/column update preserves positive definiteness of the working precision matrix.This guarantee follows from the unconstrained primal formulation and applies to both primal algorithms.
  • Implementation trade-offs: Maintaining exact inverse pairs after each block update costs O(p^2) extra operations, while p-glasso initialization from W = S + λI can cost O(p^3).The algorithms can use separate working matrices without requiring the supplied Θ and W to be inverses.

9 Experimental Results & Timing Comparisons

Experiments compare glasso and dp-glasso across synthetic covariance models and a microarray dataset using regularization paths over λ. Primal-Warm is consistently the fastest reported method, while glasso warm starts do not reliably improve convergence.

  • Experimental design: Each synthetic setting solves twenty λ values spaced linearly on the log-scale, beginning from λ values defined relative to λmax.λmax is the smallest tuning value producing a diagonal solution.
  • Synthetic experiments: Primal-Warm outperforms all other algorithms across the eight p > n synthetic scenarios, while convergence slows as λ decreases and sparsity falls.The non-sparse end of the path is described as less statistically interesting when p > n.
  • Synthetic experiments: Glasso warm starts do not consistently accelerate convergence, and the prescribed warm-start version is not guaranteed to converge.The paper specifically notes cases where warm starts fail to provide a speedup and reports no failure in the presented experiments.
  • Synthetic experiments: The optimal λ under the ∥·∥1 error selects sparser models than the optimal λ under the ∥·∥F error, with larger dp-glasso gains at the latter choice.The comparison is based on distances between estimated and population precision matrices.
  • Timing comparisons: For both Type-1 and Type-2 covariance models, dp-glasso with warm starts is consistently the clear timing winner.For fixed p, total path time generally decreases as n increases; Type-2 versus Type-1 speed differences vary with p and covariance structure.

10 Conclusions

The conclusions explain glasso’s behavior by identifying it as dual block-coordinate ascent on the covariance matrix rather than primal optimization of the precision matrix. The paper introduces p-glasso and dp-glasso, with dp-glasso offering a less expensive primal alternative and stronger empirical performance.

  • Conclusions: Glasso solves the dual graphical lasso problem by block-coordinate ascent, with covariance W as its optimization variable instead of precision Θ.Its block updates are themselves solved through dual lasso problems.
  • Conclusions: Across Type-1, Type-2, and microarray experiments, dp-glasso with warm starts consistently outperforms the competing algorithmic variants.The reported comparisons include path timings and, for the microarray example, accuracy.
  • Conclusions: During glasso iterations, the working precision matrix may not be positive definite and may not equal the inverse of the working covariance matrix.Tight convergence is therefore needed for the final precision estimate to be a proper inverse covariance.
  • Conclusions: The paper develops p-glasso and dp-glasso as primal algorithms that optimize with respect to Θ rather than W.p-glasso maintains W = Θ−1 at every step, whereas dp-glasso solves a box-QP for each block update.
  • Conclusions: p-glasso requires an O(p^3) operation per full sweep to maintain W = Θ−1, making dp-glasso the less expensive primal alternative.The paper reports that dp-glasso has attractive sparsity properties at both ends of the regularization path.

A.1 Examples: Non-Convergence of glasso with warm-starts

The examples show that glasso can fail to converge when a covariance estimate from a larger λ is used as a warm-start at a smaller λ.

  • A.1 Examples: Non-Convergence of glasso with warm-starts: Glasso warm-starts can fail to converge when moving from a larger λ to a much smaller λ.Example 1 uses λ′ = λ × 0.01, while Example 2 uses λ′ = λ × 0.1.
  • A.1 Examples: Non-Convergence of glasso with warm-starts: In Example 1, the working covariance matrix obtains a smallest eigenvalue of −0.002896128 after the first row/column update.The example uses (n, p) = (2, 5) and λ = 0.9 × q.
  • A.1 Examples: Non-Convergence of glasso with warm-starts: In Example 2, with (n, p) = (10, 50), the working covariance matrix has negative eigenvalues after the first row/column update.The warm-start is taken from the solution at λ = 0.9 × max_i≠j |s_ij| and applied at λ′ = λ × 0.1.

B Further Experiments and Numerical Studies

The numerical studies compare primal and dual glasso variants across problem sizes, covariance models, and regularization paths. DP-glasso with warm starts performs best overall, especially at the path extremes.

  • B Further Experiments and Numerical Studies: The experiments compare Primal-Cold, Primal-Warm, Dual-Cold, and Dual-Warm across p ∈ {300, 500, 800, 1000} and τ ∈ {1, 4}.Each p, τ combination uses twenty λ values on a geometric scale, with five runs averaged.
  • B Further Experiments and Numerical Studies: DP-glasso with warm starts performs best overall, especially at the extremes of the regularization path.For p = 1000, performances are comparable in the central path region, although DP-glasso still dominates there.
  • B Further Experiments and Numerical Studies: Figure 4 reports convergence times in seconds for four glasso and DP-glasso variants across twenty log-scale λ values.The horizontal axis is indexed by the proportion of zeros in the solution.
Loading 1111.5479v2…