Generalized Pseudolikelihood Methods for Inverse Covariance Estimation

Alnur Ali, Kshitij Khare, Sang-Yun Oh, Bala RajaratnamAISTATS 2017

TL;DR

The authors introduce PseudoNet, a novel pseudolikelihood-based estimator for sparse inverse covariance matrices. By incorporating an "elastic net" style penalty (combining $\ell_1$ and $\ell_2$ regularization), PseudoNet ensures a unique solution, avoids the "saturation" problem where the number of edges is capped by the sample size, and provides a faster, more accurate way to map out complex dependencies in high-dimensional data.

What Problem Does This Paper Address?

In many fields—from finance to genomics—researchers need to understand the relationship between variables. The inverse covariance matrix (or precision matrix) is the gold standard for this, as its zero entries represent conditional independence between variables. However, when the number of variables ($p$) is much larger than the number of observations ($n$), estimating this matrix is notoriously difficult.

Existing methods like the Graphical Lasso (GLasso) or pseudolikelihood approaches (SPACE, CONCORD) face several hurdles:

  1. Saturation: Many Lasso-based methods "saturate" in high dimensions, meaning they can only identify at most $n$ connections per variable. This is a physical limit of the math, not the data.
  2. Uniqueness and Convergence: Some methods don't guarantee a unique solution or fail to converge to a single point, making results hard to interpret.
  3. The "Diagonal" Gap: Theoretical proofs for existing methods often assume we already have accurate estimates of the matrix's diagonal entries, but they don't provide a reliable way to calculate them when $p > n$.

Methods

PseudoNet addresses these gaps by defining a new convex optimization problem. Its objective function includes:

  • A Log-Determinant Term: Specifically for the diagonal entries.
  • An $\ell_1$ Penalty: To encourage sparsity (forcing unimportant connections to zero).
  • A Squared Frobenius Norm ($\ell_2$) Penalty: This is the "secret sauce." It makes the objective strictly convex, ensuring a unique solution and preventing saturation.

The authors also contribute:

  • A Fast Algorithm: A proximal gradient method that converges at a geometric (linear) rate.
  • Screening Rules: Mathematical "shortcuts" that allow the algorithm to ignore variables that are guaranteed to be zero at the solution, speeding up computation by up to 90%.
  • Two-Step Diagonal Estimation: A new method to obtain the accurate diagonal estimates required for consistency proofs in high-dimensional settings.

Datasets

The paper evaluates PseudoNet using three types of data:

  1. Synthetic Data: Randomly generated sparse, diagonally dominant matrices ($p=1000$ and $p=3000$) to test accuracy and support recovery (finding the "true" edges).
  2. Finance Data: Closing prices for the 30 stocks in the Dow Jones Industrial Average (DJIA) from 1995 to 2012. This was used for a minimum-variance portfolio optimization task.
  3. Wind Power Data: Real-world energy data (detailed further in the paper's supplement) to demonstrate performance on non-Gaussian distributions.

Key Insights and Ideas

  • The Power of the $\ell_2$ Penalty: Just as the Elastic Net improved upon the Lasso for standard regression, adding the squared Frobenius norm to pseudolikelihood estimation stabilizes the result. It allows the model to select more than $n$ variables, which is crucial when the underlying network is dense but samples are scarce.
  • Breaking the Saturation Barrier: The authors prove that while SPACE and CONCORD are mathematically limited in how many edges they can find, PseudoNet has no such hard limit.
  • Stability in Crisis: In the finance application, PseudoNet was notably more stable than its competitors. During the 2008–2009 financial crisis, a portfolio based on PseudoNet preserved significantly more wealth than those based on CONCORD or standard sample covariance.

Key Results

  • Estimation Error: PseudoNet consistently outperformed CONCORD across various sample sizes and matrix norms.
  • Speed: Thanks to the screening rules and the nature of the objective function, PseudoNet's wall-clock time was generally lower and more stable than CONCORD.
  • Portfolio Optimization: In the DJIA experiment, PseudoNet achieved the lowest risk in 5 out of 8 estimation horizons and the highest Sharpe ratio (a measure of risk-adjusted return) in 4 out of 8 cases.
  • Theoretical Guarantee: The authors proved that PseudoNet is "consistent," meaning that as you get more data, the estimate is guaranteed to converge to the true underlying matrix at a rate of $\sqrt{\log p / n}$.

Limitations and Future Work

  • Tuning Parameter Sensitivity: Like all penalized methods, PseudoNet relies on tuning parameters ($\lambda_1, \lambda_2$). While the authors provide screening rules to make searching the parameter grid faster, choosing the optimal parameters in a completely unsupervised way remains a challenge.
  • Non-Gaussianity: While the authors show PseudoNet works well on non-Gaussian data (like wind power), the theoretical consistency proofs still rely on certain regularity conditions that are easiest to satisfy under near-Gaussian assumptions.
  • Computational Scaling: While much faster than previous iterations, very large-scale problems (e.g., $p > 10,000$) would likely require further distributed optimization techniques.

Summary updated

BibTeX
@inproceedings{ali2017generalized,
  author = {Alnur Ali and Kshitij Khare and Sang-Yun Oh and Bala Rajaratnam},
  title = {{Generalized Pseudolikelihood Methods for Inverse Covariance Estimation}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
}
Figure