Why a Stability Bound Needs More Than Stable Frequencies
A feature selected repeatedly under perturbations of the data may be more reproducible than one selected only once. But reproducibility is not the same as correctness: a null genomic feature can also be selected consistently, for example when the fitting procedure repeatedly encounters the same chance pattern. Stability selection combines repeated selection with a frequency threshold, and a false-selection bound can quantify one aspect of the resulting risk.
The bound is not automatic merely because a procedure uses subsamples. Its key ingredient is a bound on how often two paired selection sets overlap. In particular, selections that are independent only after conditioning on the same observed data need not satisfy the required overlap bound after averaging over that data. This distinction matters when interpreting a theoretical guarantee as a claim about an actual genomic analysis.
The set \(N\) and the meaning of “signal” must be specified for the scientific question. A false selection in this definition is a selected feature outside that target set; it is not automatically a false causal claim. In genomic prediction, for example, the target may be predictive features under a particular model, not causal genes.
The Bound and Its Overlap Condition
Consider two selection sets \(A(D)\) and \(B(D)\) generated by paired randomization of the selection procedure, with the same conditional marginal selection frequencies: for every feature \(j\), \(P(j\in A(D)\mid D)=P(j\in B(D)\mid D)=\pi_j(D)\). Define \(q(D)=E(|A(D)|\mid D)=E(|B(D)|\mid D)\), the conditional expected number selected by one base fit. A sufficient overlap condition is
This is an assumption about the paired selections, not a consequence of having a large number of features or using subsampling. It can hold in some designs, but it must be justified for the design being analyzed. The condition is stated for the overlap of all selected features; since the null-feature overlap cannot exceed total overlap, it also controls the null-feature overlap.
The commonly quoted form \(q^2/[p(2\tau-1)]\) therefore uses \(q\) as a fixed or conservative upper bound on the expected base-fit size in the relevant analysis. Replacing \(E[q(D)^2]\) by \(E[q(D)]^2\) without an additional condition is not generally valid: variation in \(q(D)\) can make \(E[q(D)^2]\) larger.
Why the Threshold Produces the Factor \(2\tau-1\)
The proof uses a basic probability inequality. For any two events \(C\) and \(F\), \(P(C\cap F)\geq P(C)+P(F)-1\). This follows because \(P(C\cup F)\leq 1\), while \(P(C\cup F)=P(C)+P(F)-P(C\cap F)\). Apply it, conditional on \(D\), to the events that feature \(j\) is selected by \(A(D)\) and by \(B(D)\). If \(j\) is stable, both marginal probabilities are at least \(\tau\), so its paired-selection probability is at least \(2\tau-1\).
Sum this inequality over the null features in the stable set. Conditional on \(D\), that set and \(N\) are fixed, so the sum of the corresponding paired-selection probabilities is the expected number of their members in \(A(D)\cap B(D)\). It cannot exceed the expected total overlap. The assumed overlap condition then gives the result.
Because \(2\tau-1>0\), division gives the stated conditional bound. Taking expectations over \(D\) gives the corresponding unconditional result. This argument does not require the two selection events for a feature to be independent; it requires their marginal frequencies and the stated upper bound on expected overlap.
Worked Examples and the Design Caveat
Worked Example: Interpreting a Bound for a Genomic Screen
Suppose a hypothetical analysis considers \(p=12{,}000\) genomic features. Assume the paired-selection overlap condition is justified, and that the conditional expected base-fit size is bounded by \(q(D)\leq 80\). Use threshold \(\tau=0.80\).
The denominator factor is \(2\tau-1=2(0.80)-1=0.60\). Substituting \(q_0=80\) and \(p=12{,}000\),
Under the stated conditions, the expected number of null features in the stable set is at most 0.8889. This is an expectation bound, not a claim that every run has fewer than one false selection, nor a guarantee that a particular selected feature is null with probability 0.8889. The realized count is an integer and can exceed the bound in some runs.
Worked Example: How a Higher Threshold Changes the Bound
In a second hypothetical analysis, let \(p=6{,}000\) and suppose \(q(D)\leq 60\), with the same overlap condition. Compare thresholds \(0.75\) and \(0.90\).
At \(\tau=0.75\), the factor is \(2(0.75)-1=0.50\), giving
At \(\tau=0.90\), the factor is \(2(0.90)-1=0.80\), so
The higher threshold tightens this bound while \(p\) and \(q\) stay fixed. It does not establish that the higher threshold is best overall: a stricter rule can also omit genuine signals. This bound addresses expected false selections, not the number of true features retained or predictive performance.
Worked Example: When Unconditional Independence Gives the Required Overlap
Consider a hypothetical setting with \(p=100\) features. Suppose \(A\) and \(B\) are independent selection sets unconditionally, have the same exchangeable distribution across all 100 features, and each selects exactly \(q=10\) features. Exchangeability means each feature has the same marginal probability of selection. Since each set has size 10, that probability is \(10/100=0.10\).
For any feature \(j\), unconditional independence gives \(P(j\in A\cap B)=0.10(0.10)=0.01\). Summing over 100 features,
Thus this particular design satisfies the overlap condition with equality. The calculation relies on unconditional independence and exchangeability over all \(p\) features. It is not a general proof for subsample fits performed on the same observed data.
Here is the critical counterexample. Let \(D\) determine a uniformly random subset \(T(D)\) of 10 features out of 100, and let both paired fits return exactly \(T(D)\). Conditional on \(D\), the fits are deterministic, hence conditionally independent; their selection sets are also exchangeable across features when \(D\) is averaged over. Yet \(A(D)=B(D)=T(D)\), so \(|A(D)\cap B(D)|=10\), whereas \(q(D)^2/p=10^2/100=1\). The required overlap condition fails by a factor of 10. Conditional independence given \(D\) did not imply the unconditional overlap inequality. Consequently, one must not invoke the bound for same-data subsampling solely on the grounds that separate random subsampling draws are independent conditional on the observed data.
Assumptions, Diagnostics, and Alternatives
A practical analysis should state which version of the conditions is being used. The direct route is to posit or establish the paired-overlap bound for the actual randomization scheme, together with the marginal-frequency and base-fit-size definitions above. A different sufficient route is the special unconditional design illustrated in the third example: independent, exchangeable selection sets with equal expected size \(q\). In that design, each feature has marginal probability \(q/p\), and expected overlap is \(p(q/p)^2=q^2/p\). These are features of that design, not automatic properties of two subsamples drawn from one data set.
The classical stability-selection discussion also motivates the overlap condition through assumptions about exchangeability of null variables and a base selector that is not systematically better than random guessing at identifying nulls. Such descriptions require care: exchangeability of null features is not exchangeability of all \(p\) features, and neither phrase by itself proves the paired-overlap inequality. The direct overlap condition makes explicit the mathematical property needed in the derivation. If a chosen theoretical formulation uses other assumptions to justify it, those assumptions must match the sampling design and be checked rather than inferred from the word “subsampling.”
Diagnostics cannot prove a population overlap condition from a single data set, but they can reveal warning signs. Across paired perturbations, inspect the distribution of intersection sizes and the number selected per fit; compare observed overlap with the scale \(q^2/p\) required by the proposed argument. Large overlap, strong clustering of selections, or a selection set that changes little across perturbations should prompt scrutiny of the design assumptions. In genomic data, correlated features can make selections move together or recur as groups. That dependence can affect overlap and exchangeability; it should not be dismissed as harmless merely because the model uses a penalty.
The selection-frequency summary alone is descriptive: it reports how often each feature is selected under the specified perturbations. The false-selection bound is a separate theoretical claim, conditional on its assumptions. Cross-validation, by contrast, is commonly used to assess predictive performance or choose a penalty; it does not by itself establish this PFER bound. Nor is PFER the false discovery rate: PFER is an expected count of false selections, whereas the false discovery rate concerns the expected proportion of selected features that are false, with a convention for an empty selected set. A small bound can be useful when the feature universe is large, but it may still be too loose to inform a particular study.
The bound also has limits. It is uninformative when \(q\) is large relative to \(p\), and it becomes weak as \(\tau\) approaches \(1/2\), because \(2\tau-1\) approaches zero. It controls an expectation rather than a realized error count, does not identify which selected features are false, and does not guarantee that selected features are causal or biologically validated. If frequencies are estimated from only finitely many subsamples, the empirical frequencies can differ from the ideal probabilities \(\pi_j(D)\); the theorem as derived is about those probabilities, so finite simulation error must be considered separately.
Common Mistakes
- Wrong: “The two fits use independently drawn subsamples, so their overlap has expectation \(q^2/p\).” Correction: Independent draws conditional on the same \(D\) can yield dependent selections after averaging over \(D\). Establish the required overlap condition for the actual design.
- Wrong: “A bound below one means this analysis cannot make a false selection.” Correction: It bounds an expectation. Some data sets can have multiple false selections even when the expected count is below one.
- Wrong: “A stable feature is therefore a true or causal feature.” Correction: Stability describes recurrence under the specified selection procedure; the PFER bound is conditional on assumptions and a definition of the null.
- Wrong: “The denominator uses the observed stable-set size.” Correction: The bound uses \(p\), the candidate-feature count, \(q\), the expected base-fit size or its upper bound, and \(\tau\), the stability threshold.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- For \(p=2{,}000\), \(q(D)\leq 40\), and \(\tau=0.75\), calculate the bound, assuming the overlap condition holds.
- Why does the derivation require \(\tau>1/2\)?
- Suppose paired fits have the same marginal frequencies and are conditionally independent given \(D\). Is that alone enough to use the bound? Explain.
- State the difference between PFER and the false discovery rate.
Solutions. (1) \(2\tau-1=0.50\), so \(E[V]\leq 40^2/[2{,}000(0.50)]=1{,}600/1{,}000=1.600\). (2) The proof divides by \(2\tau-1\), which must be positive; the paired-selection lower bound \(2\tau-1\) gives no positive guarantee at or below one half. (3) No. Conditional independence given \(D\) does not ensure the required overlap bound after averaging over the common data; the overlap condition must be justified for the relevant design. (4) PFER is the expected number of false selections; the false discovery rate is the expected proportion of selected features that are false, under its specified empty-set convention.