PaperlayerView exact revision on arXiv

Source-linked AI summary

Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models

Han Liu, Kathryn Roeder, Larry Wasserman

arXiv:1006.3316v1stat.ML

TL;DR

High-dimensional graphical-model estimation makes data-dependent regularization selection difficult because standard criteria are unsuitable in that regime. The paper introduces StARS, which selects regularization through sparse, replicable subsample-derived graphs. StARS is theoretically partially sparsistent under mild conditions and empirically outperforms competing procedures on synthetic and microarray data.

  • Problem

    Choosing the regularization parameter is difficult in high-dimensional graph estimation, where AIC, BIC, and cross-validation are unsuitable despite working well in low dimensions.

  • Method

    StARS selects the regularization parameter directly from edge stability, using subsampling to find the least regularization producing a sparse and replicable graph.

  • Results

    StARS empirically outperforms existing techniques on both synthetic and microarray datasets and is partially sparsistent under mild conditions.

  • Takeaways & Limitations

    StARS provides a stability-based regularization-selection approach that is generally applicable to structure-estimation problems beyond graphical models.

  • Takeaways & Limitations

    StARS has efficiency loss in low dimensions because subsampling makes the effective sample size b rather than n, compared with AIC and BIC using all n observations.

Abstract

from arXiv · show

A challenging problem in estimating high-dimensional graphical models is to choose the regularization parameter in a data-dependent way. The standard techniques include $K$-fold cross-validation ($K$-CV), Akaike information criterion (AIC), and Bayesian information criterion (BIC). Though these methods work well for low-dimensional problems, they are not suitable in high dimensional settings. In this paper, we present StARS: a new stability-based method for choosing the regularization parameter in high dimensional inference for undirected graphs. The method has a clear interpretation: we use the least amount of regularization that simultaneously makes a graph sparse and replicable under random sampling. This interpretation requires essentially no conditions. Under mild conditions, we show that StARS is partially sparsistent in terms of graph estimation: i.e. with high probability, all the true edges will be included in the selected model even when the graph size diverges with the sample size. Empirically, the performance of StARS is compared with the state-of-the-art model selection procedures, including $K$-CV, AIC, and BIC, on both synthetic data and a real microarray dataset. StARS outperforms all these competing procedures.

1. Introduction

High-dimensional graph estimation is difficult because regularization selection is critical, while standard low-dimensional criteria perform poorly. StARS instead selects a sparse, stable graph through overlapping subsamples.

  • Motivation: Graphical models represent conditional independence relationships among variables, but estimating high-dimensional structures is statistically challenging.In gene-expression applications, the goal is to identify interactions among gene products.
  • Motivation: AIC, BIC, and cross-validation have good low-dimensional properties but are unsuitable for high-dimensional regularization selection.The paper’s simulations confirm poor performance with glasso.
  • StARS: StARS draws overlapping random subsamples, constructs a graph for each, and reduces regularization until variability becomes small but acceptable.The procedure begins with an empty, highly stable graph and controls dissonance across subsample-derived graphs.
  • StARS: The procedure is named StARS and is studied through simulations and theoretical analysis for graphical models.The approach can also be adapted to regression, classification, clustering, and dimensionality reduction.
  • Related work: Prior stability methods include clustering and graph-selection approaches, but the paper distinguishes StARS by its fundamental conception.The cited graph-selection approach creates a more stable regularization path, whereas StARS uses subsampling directly to guide selection.
  • Paper scope: The paper analyzes high-dimensional graph estimation, develops StARS, provides theory, and evaluates it on simulations and a gene microarray dataset.The microarray task constructs a gene regulatory network from natural variation in human gene-expression levels.

2. Estimating a High-dimensional Undirected Graph

The paper formulates undirected graph estimation through conditional independence and, under Gaussianity, the sparsity pattern of the inverse covariance matrix. Glasso estimates this structure along a regularization path, but finite-sample parameter choice remains difficult.

  • Graph representation: An undirected graph has one vertex per random variable, with edges encoding conditional independence relationships.The graph is inferred from i.i.d. observations.
  • Gaussian graphical models: For Gaussian data, an edge is absent exactly when the corresponding inverse covariance entry Ω_jk equals zero.Thus graph estimation reduces to estimating the sparsity pattern of Ω = Σ^-1.
  • Glasso: Glasso estimates the inverse covariance matrix by minimizing a regularized negative log-likelihood with positive regularization parameter λ.The sample covariance matrix enters the likelihood formulation.
  • Glasso: The estimated graph includes an edge exactly when the corresponding off-diagonal glasso estimate is nonzero.A fast algorithm computes the estimator across a grid of λ values using iterative lasso regressions.
  • Practical challenge: Existing theoretical guarantees for selected λ values are often asymptotic or have very large constants, limiting their practical guidance in finite samples.The cited results can recover the true graph with high probability under a suitable rate, but do not directly resolve finite-sample selection.

3. Regularization Selection

Regularization selection seeks a graph containing the true edges, favoring overselection in applications such as gene-network reconstruction. StARS selects a stability-controlled point along the glasso path using subsampling, with explicit trade-offs and limitations.

  • Selection goal: The selection goal is to choose a regularization value whose estimated edge set contains the true graph with high probability.The paper therefore favors overselection over underselection for applications such as gene regulatory network reconstruction.
  • Existing methods: AIC and BIC rely on fixed-dimension theory that does not apply when p > n and tend to select overly dense graphs in high dimensions.Estimating their degree of freedom is also not straightforward when p exceeds n.
  • Existing methods: K-fold cross-validation partitions data into training and validation sets, scores each candidate regularization value, and selects the minimum average validation score.For each grid value, glasso is fitted on K − 1 folds and evaluated on the retained fold.
  • StARS criterion: StARS increases Λ from the empty graph until graph variability reaches the selected stability boundary.At Λ = 0 the graph is empty and perfectly stable; increasing Λ generally makes the graph denser and less stable.
  • Stability measurement: StARS estimates edge disagreement across random subsamples and averages it over edges to measure total instability.For one edge, disagreement is interpreted through variability of its Bernoulli presence indicator.
  • StARS criterion: The instability measure is monotonized because stability at very large Λ can be an artifact of dense graphs.The monotonized measure uses the supremum over all smaller parameter values.
  • Trade-offs: StARS uses a default cut point β = 0.05, but subsampling reduces the effective sample size from n to the block size b.The authors report efficiency loss in low dimensions, while claiming high-dimensional graph-selection gains dominate it.

4. Theoretical Properties

Theoretical analysis establishes uniform convergence of StARS stability estimates and derives graph-selection guarantees under mild assumptions. These results permit high-dimensional scaling while ensuring the selected graph contains the true graph with high probability.

  • Uniform concentration: Theorem 4.1 gives uniform concentration of estimated stability quantities to their population means without assumptions on P.The result is obtained using U-statistic theory, Hoeffding’s inequality, and union bounds over regularization parameters and edges.
  • Uniform concentration: When b = c1√n, K = n^c2, and p ≤ exp(n^γ) for γ < 1/2, estimated total stability converges uniformly over the parameter grid.The stated scaling applies to the whole grid Gn.
  • Graph selection: StARS graph-selection theory applies to graph estimation procedures satisfying assumptions that control population stability and true-edge inclusion.The framework denotes the subsampled estimated edge set by bE(Λ) and treats ψ as a general graph estimation procedure.
  • Graph selection: Assumption (A1) requires low population instability for sufficiently sparse models, while (A2) requires sufficiently regularized estimated graphs to contain the true graph with high probability.The two assumptions define the threshold Λo and provide the conditions used for selection guarantees.
  • Graph selection: The subsampling block size balances competing requirements: larger b supports true-edge inclusion, whereas smaller b accelerates stability concentration.The paper suggests b = floor(10√n) as a practical balance between theoretical and empirical performance.
  • Graph selection: Under (A1) and (A2), b = floor(10√n), K = n^c1, and p ≤ exp(n^γ) for γ < 1/2, StARS is partially sparsistent.The selected parameter satisfies bΛs ≥ Λo, after which (A2) and a union bound yield the graph-selection result.

5. Experimental Results

Experiments compare StARS with K-CV, BIC, AIC, and an oracle on synthetic neighborhood and hub graphs, then apply StARS and BIC to gene-expression data. In high-dimensional settings, StARS outperforms competitors and produces a simpler, more informative microarray graph.

  • Synthetic Data: The evaluation compares StARS with 10-fold cross-validation, BIC, AIC, and an oracle procedure using precision, recall, and F1-score.The oracle selects the optimal regularization parameter using knowledge of the true graph.
  • Synthetic Data: Synthetic datasets cover low-dimensional (n = 800, p = 40) and high-dimensional (n = 400, p = 100) neighborhood and hub graphs.Experiments repeat each comparison 100 times and report averaged precision, recall, and F1-score with standard errors.
  • Synthetic Data: In high-dimensional settings, StARS clearly outperforms K-CV, BIC, and AIC for both neighborhood and hub graphs.For n = 400 and p = 100, the StARS graph is almost as good as the oracle, whereas competing graphs are overly dense.
  • Microarray Data: The microarray analysis uses n = 294 samples and a previously estimated subset of 324 genes.The data measure gene expression levels from immortalized B cells of human subjects.
  • Microarray Data: StARS produces a remarkably simple and informative microarray graph, while BIC, AIC, and K-CV select much denser graphs.The StARS graph exhibits cliques and hub genes, whereas association information may be buried in the dense BIC graph.

6. Conclusions

The paper presents StARS for selecting regularization in high-dimensional undirected graphs. StARS chooses the least regularization that makes graphs sparse and replicable, and it performs better than existing techniques on synthetic and microarray data.

  • Conclusions: StARS selects the regularization parameter directly from edge stability in high-dimensional undirected graphical models.Under mild conditions, the method is partially sparsistent; without those conditions, it retains a simple operational interpretation.
  • Conclusions: StARS uses the least amount of regularization that simultaneously makes a graph sparse and replicable under random sampling.This interpretation does not require the stated theoretical conditions.
  • Conclusions: StARS works significantly better than existing techniques on both synthetic and microarray datasets.The method is also described as applicable beyond graphical models, including regression, classification, density estimation, clustering, and dimensionality reduction.
Loading 1006.3316v1…