PaperlayerView exact revision on arXiv

Source-linked AI summary

A convex pseudo-likelihood framework for high dimensional partial correlation estimation with convergence guarantees

Kshitij Khare, Sang-Yun Oh, Bala Rajaratnam

arXiv:1307.5381v3stat.MEstat.COstat.ML

TL;DR

Sparse high-dimensional graphical model selection needs methods that do not rely on Gaussianity yet have established convergence guarantees. The paper introduces CONCORD, a convex pseudo-likelihood method, and reports global convergence guarantees alongside competitive model-selection and timing results.

  • Problem

    Existing pseudo-likelihood methods do not provide provable convergence guarantees, leaving the existence and computability of their estimators uncertain.

    Source: §1 · p. 3, §3 · p. 10

  • Method

    CONCORD minimizes a convex pseudo-likelihood objective composed of quadratic forms by coordinate-wise descent and places graphical pseudo-likelihood methods in a unifying framework.

    Source: §7 · p. 29

  • Results

    CONCORD's coordinate-wise algorithm is rigorously shown to converge to a global minimum, and it is reported to run an order of magnitude faster than Glasso in higher dimensions with better model-selection performance.

    Source: §1 · p. 4, §7 · p. 30

  • Takeaways & Limitations

    The authors characterize CONCORD as competitive in model-selection accuracy, timing, and application relevance while providing provable convergence guarantees.

    Source: §5.2 · p. 23

    For the compared alternatives, SPACE convergence depends on an unverified contour condition, while Symmetric lasso lacks general coordinate-descent guarantees when n < p.

    Source: §2.2 · p. 7, §2.3 · p. 9

Abstract

from arXiv · show

Sparse high dimensional graphical model selection is a topic of much interest in modern day statistics. A popular approach is to apply l1-penalties to either (1) parametric likelihoods, or, (2) regularized regression/pseudo-likelihoods, with the latter having the distinct advantage that they do not explicitly assume Gaussianity. As none of the popular methods proposed for solving pseudo-likelihood based objective functions have provable convergence guarantees, it is not clear if corresponding estimators exist or are even computable, or if they actually yield correct partial correlation graphs. This paper proposes a new pseudo-likelihood based graphical model selection method that aims to overcome some of the shortcomings of current methods, but at the same time retain all their respective strengths. In particular, we introduce a novel framework that leads to a convex formulation of the partial covariance regression graph problem, resulting in an objective function comprised of quadratic forms. The objective is then optimized via a coordinate-wise approach. The specific functional form of the objective function facilitates rigorous convergence analysis leading to convergence guarantees; an important property that cannot be established using standard results, when the dimension is larger than the sample size, as is often the case in high dimensional applications. These convergence guarantees ensure that estimators are well-defined under very general conditions, and are always computable. In addition, the approach yields estimators that have good large sample properties and also respect symmetry. Furthermore, application to simulated/real data, timing comparisons and numerical convergence is demonstrated. We also present a novel unifying framework that places all graphical pseudo-likelihood methods as special cases of a more general formulation, leading to important insights.

1 Introduction

High-dimensional covariance estimation is difficult when the sample size cannot support the order-p^2 parameters, motivating methods that exploit sparse inverse covariance structure. The introduction presents CONCORD as a convex pseudo-likelihood approach with convergence guarantees and places existing graphical pseudo-likelihood methods in a unifying framework.

1 Introduction

  • When p/n is large, the sample covariance can estimate the order-p^2 covariance parameters poorly, motivating sparse inverse covariance estimation.Zeros in the inverse covariance matrix correspond to zero partial correlations and define a partial correlation graph.Source: §1 · p. 2
  • SPACE accounts for symmetry and has reported high-dimensional consistency, but its convergence is not established and examples show it can fail to converge.The introduction also notes that convergence of the Symmetric lasso is unclear.Source: §1 · p. 3
  • The introduction presents CONCORD as a jointly convex objective composed of quadratic forms, optimized by coordinate-wise descent.When n < p, the objective may not be strictly convex, so a unique global minimum may not exist.Source: §1 · p. 3
  • CONCORD's coordinate-wise descent is shown to converge to a global minimum regardless of problem dimension, and its estimators are asymptotically consistent under regularity assumptions matching Peng et al. (2009).The paper also reports that its estimator is well-defined and always computable.Source: §1 · p. 4
  • A comparison of graphical model selection methods reports that CONCORD retains attractive properties of existing algorithms while adding rigorous convergence guarantees.The paper also frames these pseudo-likelihood methods as special cases of a unifying formulation for comparing their strengths and weaknesses.Source: §1 · p. 4

2 The SPACE algorithm and convergence properties

This section examines the SPACE algorithm and the convergence behavior of SPACE, Symmetric lasso, and SPLICE. It identifies convergence gaps in these methods, including empirical SPACE failures and nonconvexity in the latter two objectives.

2.1 The SPACE algorithm

  • SPACE iteratively estimates partial correlations and partial covariances corresponding to the inverse covariance matrix.The algorithm is introduced as an iterative procedure by Peng et al. (2009).Source: §2.1 · p. 5, §2.2 · p. 6

2.2 Convergence Properties of SPACE

  • With weights wi = ωii, SPACE is an iterative partial minimization procedure, but convergence depends on whether every objective contour contains finitely many stationary points.The paper says this condition is unclear; with wi = 1, SPACE does not appear to have an iterative partial minimization interpretation.Source: §2.2 · pp. 5, 7
  • In one example, successive SPACE iterates alternate between two matrices with different sparsity patterns, establishing nonconvergence in that case.The paper also points to a similar example with uniform weights in the supplement.Source: §2.2 · p. 7
  • SPACE can fail to converge with either partial-variance or uniform weights, and simulations suggest nonconvergence worsens as the condition number of Ω increases.The reported simulations use 100 datasets and assess nonconvergence within 1500 iterations; Table 2 summarizes selected penalty settings.Source: §2.2 · pp. 7–8, Table 2 · p. 8

2.3 Symmetric lasso

  • The Symmetric lasso objective is nonconvex in its stated parameterization, and when n < p its coordinate-wise descent lacks general convergence guarantees.Its objective is jointly convex in Ω, but the paper notes that strict convexity is absent when n < p.Source: §2.3 · p. 9

2.4 The SPLICE algorithm

  • SPLICE alternates optimization over B and D, but its objective is not jointly convex and convergence or a global optimum is not established.The paper states that a proof of convergence is unavailable for the proposed algorithm.Source: §2.4 · pp. 9–10

3 CONCORD: A convex pseudo-likelihood framework for sparse partial covariance estimation

CONCORD targets sparse partial covariance estimation with a jointly convex pseudo-likelihood objective, retaining symmetry and other attractive properties of regression-based methods. The section develops its coordinate-wise optimization, computational cost, and a framework unifying five pseudo-likelihood formulations.

3 CONCORD: A convex pseudo-likelihood framework for sparse partial covariance estimation

  • CONCORD offers a jointly convex pseudo-likelihood approach while aiming to preserve the computational efficiency, simplicity, and symmetry of existing regression-based methods.The motivation also notes that SPACE and Symmetric lasso lack general convergence guarantees, particularly when n < p.Source: §3 · pp. 10–11

3.1 The CONCORD objective function

  • Replacing the penalty on partial correlations with one on partial covariances yields a jointly convex objective built from quadratic forms.The objective is convex but need not be strictly convex; its formulation is used to establish convergence guarantees.Source: §3.1 · p. 12

3.2 A coordinatewise minimization algorithm for minimizing Qcon(Ω)

  • Coordinate-wise updates minimize the objective one matrix entry at a time, with closed-form updates used to construct the estimated partial covariance or correlation graph.The resulting zeros in the estimated partial covariance matrix define the graph.Source: §3.2 · p. 13

3.4 A unifying framework for pseudo-likelihood based graphical model selection

  • CONCORD, SPACE1, SPACE2, SYMLASSO, and SPLICE can all be represented as special cases of a generalized pseudo-likelihood framework.Their negative pseudo-likelihoods have a matrix form, up to reparameterization.Source: §3.4 · p. 16

Gaussian log-likelihood function

  • CONCORD approximates the Gaussian likelihood using concentration matrix Ω² and an approximation to its log-determinant term.The paper reports that the correction to the objective's n term leads to better estimates of Ω in supplemental analysis.Source: Gaussian log-likelihood function · p. 18

4 Convergence of CONCORD

The section addresses convergence of CONCORD's coordinate-wise algorithm when the objective may not be strictly convex and standard results do not guarantee convergence. Under a positive-diagonal condition on the sample covariance, the iterates converge to a global minimum.

4 Convergence of CONCORD

  • When n < p, Qcon(Ω) may not be strictly convex, so existing coordinate-wise minimization results do not guarantee convergence of the iterates.Those results guarantee stationary cluster points under conditions, but not a unique cluster point or convergence of the sequence.Source: §4 · p. 18
  • If every diagonal entry Sii is positive, CONCORD's coordinate-wise iterates converge to a global minimum of Qcon(Ω).The theorem allows the global minimum to be non-unique.Source: §4 · p. 18
  • In the illustrated example, CONCORD converges while SPACE does not; SPACE's successive-estimate differences become constant on the log-scaled plot.The two matrices in the example have different sparsity patterns.Source: §4 · p. 19, Figure 1 · p. 19

5 Applications

Applications compare CONCORD with other covariance and graph estimation methods in simulations, breast-cancer data, and portfolio optimization. The results report strong model-selection and timing performance, and competitive portfolio outcomes across estimation horizons.

5.1.1 Timing Comparison

  • In low-penalty, high-dimensional settings, CONCORD was faster than competitors by orders of magnitude; for p = 3000 with n = 600 or 900, it was around ten times faster than Glasso.In the p = 1000 simulation, SPACE1 and SPACE2 were much slower than CONCORD and Glasso; for p = 3000, only Glasso and CONCORD were compared.Source: §5.1.1 · p. 20, Table 3 · p. 21

5.1.2 Model selection comparison

  • CONCORD had higher AUC than Glasso in all 150 datasets and recovered sparsity more accurately with less variation.The simulations used multivariate-t data and compared ROC-based model selection performance.Source: §5.1.2 · pp. 21–22, Table 4 · p. 22

5.2 Application to breast cancer data

  • Breast-cancer hub lists largely overlap, but CONCORD uniquely identifies TPX2 among the top ten; the authors describe it as competitive in accuracy, timing, application relevance, and convergence guarantees.CONCORD also identifies additional genes when considering larger hub lists.Source: §5.2 · p. 23

5.3 Application to portfolio optimization

  • The portfolio application compares covariance estimators through minimum-variance portfolio strategies over a sustained period, because this task requires estimating only the covariance matrix.The authors identify the setting as useful for comparing covariance estimation methods.Source: §5.3 · p. 24

5.3.1 Minimum variance portfolio rebalancing

  • Periodic rebalancing recomputes weights from the previous Nest days of returns, then holds them constant through each investment period.The paper presents rebalancing as a standard response to non-stationarity in financial time series.Source: §5.3.1 · p. 25

5.3.2 Application to the Dow Jones Industrial Average

  • Across estimation horizons, CONCORD performs uniformly well on Sharpe ratios, has the lowest short side for most horizons, and shows competitive or better wealth growth.Trading costs are also lowest for most horizons, and are comparable with CondReg at Nest = 35 or 40.Source: Table 5 · p. 26, §5.3.2 · p. 26, Figure 2 · p. 27

6 Large sample properties

The large-sample analysis studies CONCORD’s off-diagonal estimates as dimension grows with sample size, conditional on suitably accurate diagonal estimates. Its consistency framework uses regularity assumptions and notes a boundary in obtaining diagonal estimates when p exceeds n.

6 Large sample properties

  • The analysis fixes diagonal entries at suitably accurate estimates while assessing off-diagonal estimation as p varies with n.The estimates of diagonal and off-diagonal entries may be obtained from the same dataset.Source: §6 · pp. 27–28
  • The consistency framework assumes bounded eigenvalues, sub-Gaussian observations, and an incoherence condition, alongside accurate diagonal estimates.The paper relates the incoherence condition to conditions used for high-dimensional model-selection consistency.Source: §6 · pp. 27–28
  • For p > n, the cited prior work provides no general recipe for estimating the diagonal entries, limiting direct use of this consistency framework.The paper nevertheless treats the framework as useful for assessing estimator behavior as n and p increase.Source: §6 · pp. 27–28

7 Conclusion

CONCORD is presented as a regression-based graphical model selection method with a convex penalized pseudo-likelihood objective and rigorous convergence guarantees. The conclusion reports favorable theoretical and empirical properties while noting trade-offs with Glasso.

7 Conclusion

  • CONCORD formulates graphical model selection as a convex objective composed of quadratic forms and minimizes it by coordinate-wise descent with closed-form iterates.The objective is treated as a penalized pseudo-likelihood.Source: §7 · p. 29
  • Rigorous convergence analysis establishes well-defined, symmetric partial-correlation estimates that are always computable, with consistency as sample size and dimension grow.Source: §7 · p. 29
  • Simulations show competitive graphical model selection accuracy and timing; applications to biomedical and finance data yield novel findings.The paper also introduces a framework unifying graphical pseudo-likelihood methods.Source: §7 · p. 29
  • CONCORD avoids a Gaussianity assumption, has lower per-iteration computational complexity than Glasso, and is reported faster by an order of magnitude at higher dimensions with better model selection performance.When multivariate Gaussianity is compelling, the paper suggests using both methods as potentially complementary.Source: §7 · pp. 29–30

Supplemental Section

The supplemental passage introduces Qsym in terms of the data matrix, a vector of diagonal parameters, and the off-diagonal part of Ω. It specifies the diagonal parameters as reciprocals of Ω's diagonal entries.

Supplemental Section

B Proof of Lemma 3

The proof passages show that the SPLICE objective is not convex, while identifying convexity in a fixed-variable form. They also specify a soft-thresholding operator and the positive-root choice used in a solution.

B Proof of Lemma 3

  • The SPLICE objective Q_spl(B,D)=L_spl(B,D)+λP is not convex, as shown by its behavior when varying d_jj.Source: B Proof of Lemma 3 · p. 35
  • For fixed C, L*_spl(B,C) is convex in B; the proof also uses a nonnegative diagonal term derived from A=G′G.Source: B Proof of Lemma 3 · p. 36

C Proof of Lemma 4

D Proof of Lemma 5

The proof passages describe residual vectors used in the derivation and show that updates to off-diagonal or diagonal entries affect only a limited number of those vectors. Each stated residual update takes O(n) operations.

D Proof of Lemma 5

  • The proof identifies ω_iiY_k as an n-vector of residuals after regressing the ith variable on the rest.Source: D Proof of Lemma 5 · p. 37

E Proof of Lemma 6

F Proof of Lemma 7

The proof compares pseudo-likelihood formulations through residual-norm expressions. The correction factor improves parameter estimation in the numerical example.

F Proof of Lemma 7

  • The appendix derives residual-norm expressions for CONCORD, two SPACE variants, and SPLICE to compare their objective formulations.The derivations reparameterize the objectives and establish equivalences among the expressions.Source: F Proof of Lemma 7 · pp. 38–39

G Effect of correction factor

  • The correction-factor objective is updated using formulas analogous to those in the preceding proof.The supplemental section applies the correction in the CONCORD update formulas.Source: G Effect of correction factor · p. 39

G.1 Numerical example

  • The numerical example compares unpenalized CONCORD estimates with estimates from the uncorrected update formulas.The example uses data generated with n = 1000.Source: §G.1 · p. 40
  • The correction-factor estimate performs better in parameter estimation than the uncorrected estimate.The correction addresses the appearance of n rather than n/2 in the CONCORD objective.Source: §G.1 · p. 40

H Proof of Theorem 1

The proof treats CONCORD as cyclic coordinatewise minimization and establishes convergence of its iterates. The accompanying appendices describe the gene and portfolio applications, rebalancing setup, cross-validation, and performance measures.

H Proof of Theorem 1

  • The CONCORD iterates converge by viewing the algorithm as cyclic coordinatewise minimization and applying a convergence result for that objective class.The proof establishes bounded level sets and coordinate bounds before concluding convergence.Source: H Proof of Theorem 1 · pp. 40–42

I Application to breast cancer data

  • Table 6 lists the top 10 hub genes identified by CONCORD, SYMLASSO, SPACE1, and SPACE2.A plus sign marks genes among a method’s most highly connected genes.Source: Table 6 · p. 42

J.1 Constituents of Dow Jones Industrial Average

  • Table 7 reports Dow Jones component stocks’ realized returns, realized risks, and Sharpe ratios, using a 5% risk-free rate.Source: Table 7 · p. 43

J.2 Investment periods

  • The investment-period appendix tabulates the periods used in the portfolio analysis.The periods are presented in YY/MM/DD format.Source: Table 8 · p. 44

J.3 Details of minimum variance portfolio rebalancing

  • At each period’s start, the strategy estimates covariance from the preceding Nest returns, computes portfolio weights, and holds them through that period.The process repeats at the next holding period.Source: §J.3 · p. 45

J.4 Details of cross-validation

  • Cross-validation selects the penalty parameter by minimizing out-of-sample predictive risk across folds within an estimation horizon.The procedure is described for ℓ1-regularized estimators including Glasso and CONCORD.Source: §J.4 · pp. 45–46

J.5 Performance metrics

  • The portfolio evaluation reports returns, risk, Sharpe ratio, turnover, short-side size, and results across estimation horizons.Table 9 presents realized returns with risks in parentheses; Table 10 summarizes average turnovers.Source: §J.5 · pp. 46–47, Table 9 · p. 48, Table 10 · p. 48

K Proof of Theorem 2

The appendix establishes consistency and existence properties for CONCORD, studies convexity of SYMLASSO, gives settings satisfying the incoherence condition, and documents a non-convergent SPACE example.

K Proof of Theorem 2

  • CONCORD has a minimizer by convexity, and its diagonal estimates are bounded away from zero and infinity with high probability under the stated assumptions.The proof transfers the relevant SPACE consistency results with appropriate modifications, establishing CONCORD consistency.Source: K Proof of Theorem 2 · pp. 48, 50

L Joint convexity of the SYMLASSO in the Ωparameterization

M Examples where the Incoherence condition (A3) is satisfied

  • The incoherence condition holds when true correlations are sufficiently small and also for tridiagonal precision matrices under the lemma’s conditions.The tridiagonal result assumes unit diagonal entries and equal nonzero off-diagonal entries.Source: M Examples where the Incoherence… · pp. 54–56

N Non-convergence of SPACE

  • With uniform weights, SPACE iterates can alternate between matrices with different sparsity patterns and therefore yield different partial correlation graphs.The example uses n = 4 observations and λ = 0.2.Source: N Non-convergence of SPACE · p. 57
Loading 1307.5381v3…