HOST
An algorithm for structure learning in Gaussian directed acyclic graphs (DAGs) that uses node-wise held-out scoring and convex regression as substitutes for traditional subset search. It requires no prior upper bound on in-degree, achieves sample complexity of order d log p in polynomial time, and is designed to close the statistical-computational gap.
Timeline (last 90 days)
The HOST algorithm replaces the expensive subset search in traditional methods with node-wise holdout scoring combined with convex regression, and requires no externally provided in-degree upper bound.
The HOST algorithm is proposed in the arXiv paper (arXiv:2610.02785v1) for efficiently learning Gaussian DAGs.
Recovering the correct variable ordering does not require the estimation errors of the ordering scores to be uniformly small everywhere, but only requires one-sided control of these errors.
When holdout samples are used for score estimation, the ordering scores are inflated in expectation, and this inflation occurs for candidate nodes that should not yet be selected, so the direction of the bias is favorable for correct ordering.
After determining the ordering, HOST recovers the parent set of each node by recursively stripping indirect effects from the total effect between pairs of nodes.
Under appropriate conditions, HOST can exactly recover a DAG with p nodes and maximum in-degree d in polynomial time with sample complexity of order d·log p.
The d·log p sample complexity is the advantageous order possessed by previous sharp methods that relied on subset search, and HOST achieves this level without sacrificing polynomial runtime.
Experiments report that HOST is competitive with existing methods in graph recovery quality while exhibiting superior scalability in runtime.
The guarantees in the HOST paper are established under appropriate conditions, and the robustness of the algorithm to deviations from the Gaussian assumption still requires further exploration.
In structure learning tasks, a carefully designed estimation bias with a controllable direction is sometimes more useful than pursuing unbiased or uniformly small errors.
All Facts (10)
The HOST algorithm replaces the expensive subset search in traditional methods with node-wise holdout scoring combined with convex regression, and requires no externally provided in-degree upper bound.
50%UnverifiedThe HOST algorithm is proposed in the arXiv paper (arXiv:2610.02785v1) for efficiently learning Gaussian DAGs.
50%UnverifiedRecovering the correct variable ordering does not require the estimation errors of the ordering scores to be uniformly small everywhere, but only requires one-sided control of these errors.
50%UnverifiedWhen holdout samples are used for score estimation, the ordering scores are inflated in expectation, and this inflation occurs for candidate nodes that should not yet be selected, so the direction of the bias is favorable for correct ordering.
50%UnverifiedAfter determining the ordering, HOST recovers the parent set of each node by recursively stripping indirect effects from the total effect between pairs of nodes.
50%UnverifiedUnder appropriate conditions, HOST can exactly recover a DAG with p nodes and maximum in-degree d in polynomial time with sample complexity of order d·log p.
50%UnverifiedThe d·log p sample complexity is the advantageous order possessed by previous sharp methods that relied on subset search, and HOST achieves this level without sacrificing polynomial runtime.
50%UnverifiedExperiments report that HOST is competitive with existing methods in graph recovery quality while exhibiting superior scalability in runtime.
50%UnverifiedThe guarantees in the HOST paper are established under appropriate conditions, and the robustness of the algorithm to deviations from the Gaussian assumption still requires further exploration.
50%UnverifiedIn structure learning tasks, a carefully designed estimation bias with a controllable direction is sometimes more useful than pursuing unbiased or uniformly small errors.
50%