PaperlayerView exact revision on arXiv

Source-linked AI summary

Variable selection in high-dimensional linear models: partially faithful distributions and the PC-simple algorithm

Peter Bühlmann, Markus Kalisch, Marloes H. Maathuis

arXiv:0906.3204v3stat.ME

TL;DR

High-dimensional linear models require variable selection when covariates greatly outnumber observations. The paper introduces partial faithfulness and a simplified PC algorithm for selection; its examples show consistency under stated conditions, including cases where the Lasso is inconsistent.

  • Problem

    The paper addresses variable selection in high-dimensional linear models where the number of covariates greatly exceeds the sample size.

    Source: §1 · p. 1

  • Method

    The PC-simple algorithm uses partial faithfulness in efficient hierarchical testing to select variables in high-dimensional linear models.

    Source: §1 · pp. 1–2

  • Results

    In a high-dimensional example satisfying (D1)–(D5), the PC-simple algorithm is consistent while the Lasso is inconsistent.

    Source: Discussion of the conditions of… · p. 10

  • Takeaways & Limitations

    The paper establishes PC-simple consistency under design-matrix assumptions different from coherence conditions for penalty-based methods.

    Source: §1 · p. 2

    Assumption (D4) is restrictive because it does not allow small nonzero low-order partial correlations.

    Source: Discussion of the conditions of… · p. 10

Abstract

from arXiv · show

We consider variable selection in high-dimensional linear models where the number of covariates greatly exceeds the sample size. We introduce the new concept of partial faithfulness and use it to infer associations between the covariates and the response. Under partial faithfulness, we develop a simplified version of the PC algorithm (Spirtes et al., 2000), the PC-simple algorithm, which is computationally feasible even with thousands of covariates and provides consistent variable selection under conditions on the random design matrix that are of a different nature than coherence conditions for penalty-based approaches like the Lasso. Simulations and application to real data show that our method is competitive compared to penalty-based approaches. We provide an efficient implementation of the algorithm in the R-package pcalg.

1. INTRODUCTION

The paper proposes variable selection through partial faithfulness, a framework typically weaker than linear faithfulness. It develops the PC-simple algorithm and proves consistency under design-matrix assumptions different from coherence conditions used by penalty-based methods.

1. INTRODUCTION

  • Bayesian variable-selection methods using Markov chain Monte Carlo are typically very expensive for truly high-dimensional problems.The introduction also describes a substantial literature on computationally feasible penalty-based estimators.Source: §1 · p. 1
  • Partial faithfulness is typically weaker than linear faithfulness and arises under a simple assumption on regression-coefficient structure that excludes adversarial cases.The paper gives this result under assumption (C2) and Theorem 1.Source: §1 · p. 1
  • Partial faithfulness supports the PC-simple algorithm, an efficient hierarchical testing simplification of the PC algorithm for directed acyclic graphs.The approach is presented as fundamentally different from penalty-based schemes.Source: §1 · pp. 1–2
  • The paper proves PC-simple consistency for high-dimensional variable selection under design-matrix assumptions different from penalty-based coherence conditions.The algorithm also generalizes correlation screening, yielding consistency under different assumptions and reasoning than Fan & Lv (2008).Source: §1 · p. 2

2. MODEL AND NOTATION

The model is a random-design linear regression with a sparse coefficient vector, and the target is the set of covariates with nonzero coefficients. The assumptions include positive-definite covariate covariance and a condition on the nonzero coefficients.

2. MODEL AND NOTATION

  • The target active set A contains the indices of nonzero regression coefficients, and its size p_eff is the model's effective dimension.The paper seeks to identify A from independent observations distributed as (X, Y).Source: §2 · p. 2
  • Assumption (C1) requires the covariate covariance matrix Σ_X to be strictly positive definite, supporting identification of the regression parameters from the joint distribution.The paper states β can be recovered from covariances of Y with the covariates using Σ_X^-1.Source: §2 · p. 2
  • Assumption (C2) restricts the nonzero coefficients to realizations from an absolutely continuous distribution, while zero coefficients may arise arbitrarily.Once realized, the nonzero coefficients are treated as fixed; (C2) is not necessary for the paper's main results.Source: §2 · pp. 2–3

3. LINEAR FAITHFULNESS AND PARTIAL FAITHFULNESS

The section defines partial faithfulness as a condition linking zero partial correlations between a covariate and response to a zero coefficient. It relates this condition to graphical faithfulness and uses examples to show that the graphical condition is sufficient in some cases but not necessary.

Partial faithfulness

  • Partial faithfulness requires that a zero partial correlation between Y and X(j), conditional on some subset excluding j, implies zero partial correlation conditional on all other covariates.In the linear model under (C1), this corresponds to the implication that such a zero partial correlation implies β_j = 0.Source: Partial faithfulness · p. 3
  • Under (C1) and (C2), partial faithfulness holds almost surely with respect to the distribution generating the nonzero regression coefficients.The condition (C2) is sufficient but not necessary for the paper's main results.Source: Partial faithfulness · p. 3
  • Under partial faithfulness, β_j is nonzero exactly when every partial correlation between Y and X(j), conditional on any subset of other covariates, is nonzero.This gives active variables the stated strong interpretation in terms of partial correlations.Source: Partial faithfulness · p. 3

Relationship between linear faithfulness and partial faithfulness

  • Linear Y-faithfulness requires d-separation to match zero partial correlations only between Y and covariates; full linear faithfulness also covers covariate pairs.Linear faithfulness implies linear Y-faithfulness, while partial faithfulness is not itself a graphical concept.Source: Relationship between linear… · p. 4
  • If a distribution is linearly Y-faithful to a DAG where Y is childless, partial faithfulness follows.The paper notes that distributions are typically linearly Y-faithful to several DAGs, and the theorem applies if Y is childless in at least one.Source: Relationship between linear… · p. 4
  • Example 1 violates partial faithfulness: β1 = 1, yet Y and X(1) have zero marginal correlation and nonzero partial correlation given X(2).The example attributes the zero marginal correlation to parameter cancellation; the distribution is not linearly Y-faithful to a DAG where Y is childless.Source: Relationship between linear… · pp. 4–5
  • Example 2 is partially faithful despite not being linearly faithful to its displayed DAG, showing linear Y-faithfulness can be strictly weaker than linear faithfulness.Example 3 is also partially faithful although no DAG makes its distribution linearly Y-faithful, so Theorem 2's condition is not necessary.Source: Relationship between linear… · p. 5

4. THE PC-SIMPLE ALGORITHM

The population PC-simple algorithm progressively screens covariates using marginal and higher-order partial correlations, while limiting conditioning sets to variables retained at the previous step. Its sample version tests estimated partial correlations and can handle problems with thousands of covariates.

Population version of the PC-simple algorithm

  • Successive screening removes a covariate when a partial correlation vanishes for a conditioning set among previously retained covariates, while preserving the true active set.The algorithm begins with marginal correlation screening, then increases the conditioning-set order.Source: Population version of the PC-simple… · pp. 6–7
  • Under (C1) and partial faithfulness, the population PC-simple algorithm identifies the true active set at its stopping step.The stopping step is mreach, where the candidate active set has size at most m.Source: Population version of the PC-simple… · p. 7
  • Unlike the full PC algorithm, PC-simple tests only response–covariate pairs and conditions on variables in the response neighborhood.This restriction focuses the search on associations between Y and each covariate.Source: Population version of the PC-simple… · p. 7

Sample version of the PC-simple algorithm

  • The sample version replaces population partial correlations with estimated ones and tests them using Fisher’s Z-transform, with significance level α as its only tuning parameter.Sample partial correlations can be calculated recursively.Source: Sample version of the PC-simple… · pp. 7–8
  • PC-simple screens many correlations at once rather than greedily, has an upper complexity bound of O(p peff), and is reported usable with thousands of covariates.Its screening is more sophisticated than marginal or limited-order partial-correlation approaches described in the passage.Source: Sample version of the PC-simple… · p. 8

5. ASYMPTOTIC RESULTS IN HIGH DIMENSIONS

The PC-simple algorithm is consistent for variable selection in high-dimensional partially faithful linear models under assumptions (D1)–(D5). The discussion highlights restrictive partial-correlation requirements and shows how correlation screening can retain active variables under a different set of assumptions.

Consistency of the PC-simple algorithm

  • Under assumptions (D1)–(D5), the PC-simple algorithm consistently selects variables as the dimension grows with sample size.The theorem allows a sequence of significance levels α_n tending to zero.Source: Consistency of the PC-simple algorithm · pp. 8–9

Discussion of the conditions of Theorem 4

  • Assumptions (D2) and (D3) permit polynomial dimension growth and impose sparsity, while partial faithfulness and partial-correlation conditions are more critical.The assumptions are virtually impossible to check in practice, except for (D2).Source: Discussion of the conditions of… · p. 9, Consistency of the PC-simple algorithm · p. 9
  • Condition (D4) excludes small nonzero low-order partial correlations, and the authors identify near partial faithfulness as a more realistic but unanalyzed alternative.Condition (D4) controls type II errors across the algorithm’s many tests.Source: Discussion of the conditions of… · p. 10
  • In a high-dimensional example with three active variables and independent noise covariates, the PC-simple algorithm is consistent while the Lasso is inconsistent.The example assumes the design satisfies (C1) and (D5,(ii)).Source: Discussion of the conditions of… · p. 10

Asymptotic behavior of correlation screening

  • Correlation screening can overestimate the active set under partial faithfulness and assumptions different from those used by Fan and Lv (2008).The screening result requires no sparsity assumption, but the screened set can still be nearly as large as the full variable set.Source: Asymptotic behavior of correlation… · p. 11

6. NUMERICAL RESULTS

Simulations compare PC-simple with penalty-based methods, both across tuning choices and under prediction-optimal tuning; a riboflavin gene-expression dataset illustrates how their selections overlap and differ.

Analysis for simulated data

  • Computing time for PC-simple over 10 α values is about the same order of magnitude as a full Lasso or Elastic Net solution path.The authors conclude this makes PC-simple feasible for high-dimensional problems.Source: Analysis for simulated data · p. 12
  • At low false-positive rates, PC-simple dominates in low-dimensional simulations; in high dimensions, Lasso performs best, but PC-simple is never significantly outperformed through α=0.05.The reported comparison uses ROC curves; increasing covariate correlation worsens Elastic Net performance in low-dimensional settings, while PC-simple and Lasso vary little.Source: Analysis for simulated data · pp. 11–12, Figure 2 · p. 12

Prediction optimal tuned methods for simulated data

  • With prediction-optimal tuning, PC-simple-based methods have the lowest false-positive rates, at the cost of lower true-positive rates and higher mean squared errors.The comparison uses PC-simple followed by Lasso or adaptive Lasso coefficient estimation, alongside Lasso, adaptive Lasso, and relaxed Lasso.Source: Prediction optimal tuned methods for… · p. 13, Figure 3 · p. 14

Real data: riboflavin production by Bacillus subtilis

  • In the riboflavin gene-expression data, PC-simple selections overlap significantly with Lasso and Elastic Net selections, yet are more distinct from them than Lasso and Elastic Net are from each other.Table 1 reports selected-variable counts and pairwise overlaps; the data contain 4,088 gene-expression covariates and 71 individuals.Source: Real data: riboflavin production by… · p. 14, Table 1 · p. 15

APPENDIX

The appendix establishes partial-faithfulness and graph-based results, then supports finite-sample recovery with bounds for estimated partial correlations and the PC-simple algorithm.

Partial faithfulness

  • Under (C1) and (C2), partial faithfulness holds almost surely because nonzero coefficients almost surely imply nonzero partial correlations for every conditioning set.The proof excludes coefficient configurations that produce exact cancellation; under (C2), those configurations have Lebesgue measure zero.Source: Proofs · p. 15

Graph-based justification

  • Linear Y-faithfulness to a graph where Y is childless implies partial faithfulness, because an active covariate must have a direct edge to Y that conditioning on other covariates cannot block.The proof uses the nonzero partial correlation given all other covariates to establish nonzero partial correlations under every subset of that conditioning set.Source: Proofs · pp. 15–16

Finite-sample bounds

  • For Gaussian data under (D5mn), estimated partial correlations satisfy an exponential error bound for conditioning sets up to order m_n=o(n).The appendix uses this bound to control errors in the estimated Z-transformed partial correlations and the finite-sample algorithm.Source: Proofs · pp. 16–17

Finite-sample consistency

  • Under the stated assumptions, a bounded-iteration PC-simple procedure recovers the active set with probability 1−O{exp(−Cn^1−2d)}→1.The result assumes the iteration bound is at least m_reach,n and is O(n^1−b), with the stated design and partial-correlation conditions.Source: Proofs · p. 17

Correlation screening

  • The correlation-screening error bound does not require sparsity, but it does require a lower bound on nonzero marginal correlations.This is the stated condition used for the screening result.Source: Proofs · pp. 18–19
Loading 0906.3204v3…