High-dimensional consistency of Gaussian PC structure learning

Since $q_n=O(n^{1-b})$ with $b>0$, eventually $n-q_n-3>0$, so [F1] makes every sample statistic in the capped search defined almost surely. The sample procedure terminates for every answer sequence: it processes at most $q_n+1$ finite levels, each with finitely many pair-and-subset tests, and its finite orientation phase either stops at a conflict or cycle, or directs at most $\left(\genfrac{}{}{0px}{}{p_n}{2}\right)$ edges. Since $c_n\le M<1$, take $t=c_n\mathrm{/}4\le 1$ in [F4]. For every tested triple $(i,j,S)$, the probability that $\mathrm{\mid }g({\widehat{\rho }}_{ij\mid S})-g({\rho }_{ij\mid S})\mathrm{\mid }>c_n\mathrm{/}4$ is at most $C_M\exp (-c_M(n-\mathrm{\mid }S\mathrm{\mid }-1)c_n^2\mathrm{/}16)$. For large $n$, $q_n\mathrm{/}n\to 0$ and $n-q_n-1\ge n\mathrm{/}2$, so each such probability is at most $C_M\exp (-c_M^{\mathrm{\prime }}n{c}_n^2)$ for a constant $c_M^{\mathrm{\prime }}>0$.

For any nonedge of $G_n$, label its endpoints $i,j$ so that $j$ is not a descendant of $i$, as acyclicity permits, and put $S={\mathrm{pa}}_{G_n}(i)$. This set excludes both endpoints and has size at most $q_n$. A path entering $i$ is blocked at its first internal vertex, a conditioned parent and noncollider. A path initially leaving $i$ has a first reversal, since $j$ is not a descendant. At that reversal is a collider reached by a directed path from $i$; it has no descendant in $S$, since otherwise a directed path back through a parent would close a directed cycle through $i$. Thus every such path is blocked by [F10], and $S$ d-separates $i,j$.

There are at most $N_n=\left(\genfrac{}{}{0px}{}{p_n}{2}\right){\sum }_{\mathrm{\ell }=0}^{q_n}\left(\genfrac{}{}{0px}{}{p_n-2}{\mathrm{\ell }}\right)\le p_n^2(q_n+1)p_n^{q_n}\le p_n^{q_n+3}$ distinct pair-and-set tests, since $q_n\le p_n-1$ and $q_n+1\le p_n$. A union bound, which requires no independence between tests, shows that the event $E_n$ on which every test of size at most $q_n$ has Fisher-transform error at most $c_n\mathrm{/}4$ has failure probability at most $C_M\exp \text{\hspace{0.17em}⁣}((q_n+3)\log p_n-c_M^{\mathrm{\prime }}n{c}_n^2)\mathrm{.}$ The assumptions imply $n{c}_n^2\ge C_0{n}^{1-2d}$ eventually and $(q_n+3)\log p_n=O(n^{1-b}\log n)=o(n^{1-2d})$, because $2d<b$. Thus, after reducing the positive constant in the exponent, $\mathbb{P}(E_n^c)\le \exp (-C{n}^{1-2d})$ for all sufficiently large $n$.

On $E_n$, if ${\rho }_{ij\mid S}=0$, then [F1] gives $\mathrm{\mid }g({\widehat{\rho }}_{ij\mid S})\mathrm{\mid }\le c_n\mathrm{/}4$. By [F3], this is the population conditional-independence case. Hence $T_{ij\mid S}\le \sqrt{n}{c}_n\mathrm{/}4<\sqrt{n}{c}_n\mathrm{/}2$, so the test declares independence. If ${\rho }_{ij\mid S}\mathrm{\ne }0$, then [F2] and the lower-bound hypothesis give $\mathrm{\mid }{\rho }_{ij\mid S}\mathrm{\mid }\ge c_n$, and $\mathrm{\mid }g({\rho }_{ij\mid S})\mathrm{\mid }\ge \mathrm{\mid }{\rho }_{ij\mid S}\mathrm{\mid }$ because $\mathrm{\mid }\mathrm{atanh}(r)\mathrm{\mid }\ge \mathrm{\mid }r\mathrm{\mid }$ for $\mathrm{\mid }r\mathrm{\mid }<1$. Therefore $\mathrm{\mid }g({\widehat{\rho }}_{ij\mid S})\mathrm{\mid }\ge 3c_n\mathrm{/}4$. Since $(n-\mathrm{\mid }S\mathrm{\mid }-3)\mathrm{/}n\ge (n-q_n-3)\mathrm{/}n\to 1$, for all sufficiently large $n$ we have $\sqrt{(n-\mathrm{\mid }S\mathrm{\mid }-3)\mathrm{/}n}>2\mathrm{/}3$, so $T_{ij\mid S}>\sqrt{n}{c}_n\mathrm{/}2$ and the test declares dependence. By [F3] these are exactly the dependent cases.

On $E_n$ the capped sample PC search makes the same decisions as the uncapped perfect-oracle procedure through level $q_n$. True edges are never removed, because [F8] excludes d-separation for their endpoints and [F7] makes every such test dependent. For each nonedge, step 1.2 supplies a separating parent set of size at most $q_n$. Its parent edges remain, so while the nonedge remains the endpoint has enough neighbors to prevent stopping before the separator's level. At that level either an earlier set deletes the nonedge or the parent set is tested and deletes it. Thus every nonedge is removed no later than level $q_n$. Thus by completion of that level the sample search and the perfect-oracle run have the exact skeleton and the same separating records. The oracle run cannot need another level: on an exact skeleton of maximum degree at most $q_n$, no remaining edge can have an endpoint with the $q_n+1$ other neighbors required to advance after level $q_n$. If either run stops earlier by its ordinary degree condition, their identical decisions make both stop; otherwise both stop after level $q_n$, the sample run by its cap. Their collider and R1–R3 orientations therefore agree. The oracle orientations are consistent with $G_n$ by [F5], so neither a conflict nor a directed cycle occurs on $E_n$. Hence the failure branch is never used on $E_n$, and [F5] identifies the oracle run's output, hence the sample output, as the CPDAG of $G_n$.

The only failure event is contained in $E_n^c$, whose probability has the bound from step 2.1. Step 4.1 identifies the output on $E_n$ as the CPDAG. This proves the stated consistency bound. The threshold uses $c_n$, so the theorem does not provide a data-driven choice of that parameter.