REJOINDER: LATENT VARIABLE GRAPHICAL MODEL SELECTION VIA CONVEX OPTIMIZATION

Venkat Chandrasekaran, Pablo A. Parrilo, Alan S. Willsky2016

TL;DR

This paper is a rejoinder, a response to discussions on their previous work about selecting latent variable graphical models. They clarify their convex optimization approach for decomposing covariance matrices into sparse and low-rank components, highlighting its advantages in terms of provable statistical and computational guarantees compared to alternative methods like EM.

What Problem Does This Paper Address?

The authors are revisiting their previous work on "Latent Variable Graphical Model Selection Via Convex Optimization." The core problem they address is how to infer the structure of a graphical model when some variables are unobserved (latent). In high-dimensional settings, where the number of variables is large, this becomes particularly challenging. Their previous paper focused on a specific scenario: when the observed variables, conditioned on the latent variables, form a sparse graphical model. In this case, the covariance matrix of the observed variables can be decomposed into a sum of a sparse matrix (representing the conditional graphical structure) and a low-rank matrix (induced by marginalizing out the latent variables). The key challenge is to reliably decompose this sum into its sparse and low-rank components, which is crucial for model selection.

Methods

The authors' primary method, introduced in their prior work and defended here, is a convex optimization-based approach. Specifically, they formulate the problem of decomposing a concentration matrix (related to the inverse covariance matrix) into sparse and low-rank components as a regularized maximum-likelihood estimator. This estimator uses an $l_1$ norm penalty to encourage sparsity in one component and a trace norm penalty to encourage low-rank structure in the other. They emphasize that this formulation results in a convex program, which can be solved efficiently and guarantees finding the global optimum.

In this rejoinder, they discuss and compare their method to several alternative approaches proposed by other researchers:

  • EM-based methods: These methods, while showing promise experimentally, are criticized for their potential to get stuck in local optima due to the non-convexity of the underlying optimization problem.
  • Thresholding estimators: These methods involve applying $l_1$ norm thresholding followed by trace norm thresholding. The authors suggest this can be viewed as an iterative step within their own block coordinate descent procedure.
  • Dantzig selector-based reformulations: These approaches adapt methods from sparse model selection to the latent variable setting. The authors point out potential issues with additional constraints and the property of containing the lasso solution.

Datasets

Not discussed in the paper. The paper focuses on theoretical aspects and discusses experimental results from other researchers' work.

Key Insights and Ideas

  • Convexity is King: The authors strongly advocate for their convex optimization approach, emphasizing its ability to provide provable statistical and computational guarantees, a significant advantage over methods prone to local optima.
  • Decomposition is Key: The core idea is that the observed covariance matrix in this latent variable setting is a sum of a sparse and a low-rank matrix. Reliably separating these components is fundamental to inferring the underlying graphical structure.
  • Trade-offs in Regularization: Different regularization techniques (l1 norm for sparsity, trace norm for low-rank) are crucial for disentangling the components. The choice of these penalties directly influences the properties of the recovered components.
  • Global vs. Local: Latent variable modeling inherently requires global approaches because marginalization can introduce correlations between many observed variables, making purely local neighborhood-based methods ill-suited.
  • The Role of Sample Size: The authors discuss the necessity of having at least as many samples as variables ($n \ge p$) for consistent estimation of the low-rank component, a common theme in high-dimensional statistics.

Key Results

The paper is a rejoinder, so it doesn't present new experimental results. Instead, it:

  • Reiterates the strengths of their convex optimization approach: Provable statistical and computational guarantees.
  • Critiques alternative methods: Highlights potential drawbacks of EM (local optima) and discusses nuances of thresholding and Dantzig selector-based methods.
  • Discusses theoretical conditions: Explains the role of Fisher information-based conditions for identifiability and their connection to irrepresentability conditions in sparse model selection.
  • Addresses questions about rates and adaptivity: Discusses the possibility of improving estimation rates and achieving adaptivity (i.e., requiring fewer samples when there are no latent variables).

Limitations and Future Work

  • Non-Gaussian Models: The authors acknowledge that extending their methods to non-Gaussian latent variable models presents significant computational and algebraic challenges, as the underlying geometric structures are less understood.
  • Improving Rates: They suggest that further research could lead to faster estimation rates, particularly if the low-rank component has additional structure (e.g., a sparse factorization).
  • Adaptivity: Investigating whether their estimator can achieve adaptivity (i.e., perform as well as sparse graphical model selection when no latent variables are present) is an open question.
  • Software Development: They note the desire for better integration of advanced convex optimization solvers (like SDPT3) with statistical software packages like R.
  • Infimal Convolution: They propose a new norm formulation, the "sparse/low-rank decomposition as infimal convolution," which could offer a more unified way to analyze and potentially develop new regularizers.

Summary updated

Abstract

Rejoinder to "Latent variable graphical model selection via convex optimization" by Venkat Chandrasekaran, Pablo A. Parrilo and Alan S. Willsky [arXiv:1008.1290].
BibTeX
@misc{chandrasekaran2016rejoinder,
  author = {Venkat Chandrasekaran and Pablo A. Parrilo and Alan S. Willsky},
  title = {{REJOINDER: LATENT VARIABLE GRAPHICAL MODEL SELECTION VIA CONVEX OPTIMIZATION}},
  year = {2016},
}
Figure