HOST Algorithm: A New Paradigm for Efficient Gaussian DAG Learning

The Statistical-Computational Gap in Gaussian DAG Learning

Directed acyclic graphs (DAGs) are a fundamental tool for modeling causal and dependency structures among variables, with wide applications in causal inference, gene regulatory networks, economic modeling, and beyond. Yet in high-dimensional settings, learning the structure of Gaussian DAGs has long been plagued by a frustrating dilemma — what researchers call the "statistical-computational gap."

On one side, methods with sharp sample complexity tend to rely on computationally expensive subset search and require a predefined indegree bound as prior information. On the other side, algorithms that run in polynomial time typically fall short on sample efficiency. In short, being both fast and statistically sharp has historically been out of reach.

A new paper on arXiv (arXiv:2610.02785v1) introduces an algorithm called HOST, which aims to fundamentally bridge this gap.

The Core Idea Behind HOST: Hold-Out Scoring and Convex Regression

The name HOST stands for Hold-Out Scoring, which directly reflects its technical approach. It replaces the expensive subset search found in traditional methods with nodewise hold-out scoring combined with convex regression — and it does so without requiring an externally supplied indegree bound. This frees the algorithm from strong reliance on prior structural information, making it applicable in a much broader range of settings.

Key Insight: Ordering Only Requires One-Sided Error Control

One of the most illuminating contributions of this paper is a counterintuitive observation: recovering the correct variable ordering does not require uniformly small estimation errors in the ordering scores — it only requires "one-sided control" over those errors.

This is a subtle but elegant statistical idea. Conventionally, we strive for estimators with consistently small errors. But for the specific task of ordering, what matters is the direction of the error, not its absolute magnitude. HOST exploits this insight to reduce the problem to one that can be solved in polynomial time.

The "Favorable Bias" of Hold-Out Samples

More concretely, in the ordering phase, HOST leverages the fact that when hold-out samples are used to estimate scores, the ordering scores are "inflated in expectation" — and crucially, this inflation occurs precisely for candidate nodes that should not yet be selected. In other words, the bias is directionally favorable.

This design allows the algorithm to reliably distinguish which nodes should be ordered earlier and which should be deferred, enabling it to approximate the correct ordering without resorting to subset search.

From Ordering to Parent Set Recovery

Once the ordering is established, HOST enters its second phase: recovering the parent set of each node. The strategy here is to recursively strip indirect effects from the total effects between pairs of nodes, leaving behind only the direct parent-child dependencies.

This step echoes the classical causal inference idea of distinguishing direct from indirect effects. By recursively peeling away indirect contributions, HOST can precisely reconstruct the graph structure given a known ordering — without enumerating all possible parent set combinations.

Theoretical Guarantees and Empirical Performance

The paper provides clear theoretical results: under appropriate conditions, HOST can exactly recover a DAG with $p$ nodes and maximum indegree $d$ in polynomial time, with a sample complexity of order $d\log p$.

The $d\log p$ sample complexity is precisely the sharp rate achieved by prior methods that relied on subset search — and HOST reaches this level without sacrificing polynomial runtime. This is the key evidence that HOST genuinely bridges the statistical-computational gap.

On the empirical side, the paper reports that HOST is competitive with existing methods in graph recovery quality, while achieving superior runtime scaling. This means HOST's computational advantage becomes increasingly pronounced as problem size grows.

Significance and Outlook

HOST's contribution goes beyond delivering a faster algorithm — it offers a new perspective on the problem itself: in structure learning tasks, a carefully designed estimation bias with a controlled direction can sometimes be more useful than pursuing unbiased or uniformly small errors.

For researchers and practitioners who need to perform causal structure discovery on large-scale, high-dimensional data, HOST provides a viable option that requires no prior indegree assumptions while offering both theoretical guarantees and computational efficiency. That said, the paper's guarantees rest on certain conditions whose satisfaction in real-world data — as well as the algorithm's robustness to departures from the Gaussian assumption — remain important directions for future investigation.