Optimal estimation of Gaussian (poly)trees

Yuhao Wang, Ming Gao, Wai Ming Tai, Bryon Aragam, Arnab Bhattacharyya

Introduction

Directed Acyclic Graphs (DAGs) serve as the fundamental framework for causal inference, enabling researchers to map complex dependencies in fields ranging from genetics to social sciences. Despite their ubiquity, the computational and statistical limits of learning these structures from observational data have long been a subject of intense study. While learning undirected Markov Random Fields is well-understood, a significant gap persisted regarding the optimal sample complexity for the simplest directed models: Gaussian trees and polytrees. This research addresses this gap by providing the first optimal algorithms and matching sample complexity bounds for learning these structures across three distinct statistical scenarios.

Problem Formulation

The study categorizes the learning problem into three specific regimes, each representing a different level of alignment between the underlying data and the tree model:

  1. Non-realizable (Agnostic): When the true data-generating distribution is not a tree, the goal is to find the best possible tree approximation (minimizing KL divergence).
  2. Realizable: When the data is generated by a Gaussian tree, the goal is to learn the distribution itself within a specific error margin.
  3. Faithful: Under the assumption that the distribution perfectly reflects the graph's structure (faithfulness), the goal is to recover the exact causal graph (specifically, the Completed Partially Directed Acyclic Graph, or CPDAG).

Methodology

The authors bridge the gap between theory and practice by adapting two primary algorithmic frameworks and establishing information-theoretic lower bounds.

Algorithmic Frameworks

  • Modified Chow-Liu Algorithm: Traditionally utilized for undirected trees, the authors adapt this maximum-weight spanning tree approach to the directed setting. By using estimated mutual information as edge weights, the algorithm identifies the optimal tree-structured distribution.
  • PC-Tree Algorithm: This is a specialized refinement of the classic PC algorithm. While the standard PC algorithm is often computationally prohibitive due to its exhaustive testing of conditioning sets, PC-Tree exploits the inherent properties of trees. It limits testing to marginal independence and conditional independence given only a single adjacent node, significantly reducing complexity.

Theoretical Optimality

To prove that these algorithms are optimal, the authors employ Fano’s inequality to construct "hard" ensembles of distributions. These constructions demonstrate that no algorithm, regardless of computational power, could succeed with fewer samples than those required by the proposed methods.

Key Insights: The Phase Transition

A pivotal finding of this research is the "Phase Transition" between distribution learning and structure learning. The results reveal that identifying the causal structure of a system is often significantly "cheaper" in terms of data requirements than learning the full probability distribution.

In the Realizable case, the sample complexity scales linearly with the number of nodes ($d$). However, in the Faithful case, the complexity drops to a logarithmic scale ($\\log d$). This suggests that if a researcher's primary objective is to uncover the skeleton of causal relationships rather than the precise parameters of the distribution, the data requirements are much less demanding than previously assumed.

Results and Performance

The paper establishes the following optimal sample complexities ($n$):

Setting Sample Complexity ($n$) Objective
Non-realizable $\\tilde{\\Theta}\\left(\\frac{d^2}{\\epsilon^2}\\right)$ Best tree approximation
Realizable $\\tilde{\\Theta}\\left(\\frac{d}{\\epsilon}\\right)$ Learn the tree distribution
Faithful $\\Theta\\left(\\frac{\\log d}{c^2}\\right)$ Recover the exact graph (CPDAG)

Note: $c$ represents the signal strength or faithfulness parameter.

Experimental evaluations using synthetic Gaussian trees (up to $d=100$) confirmed these theoretical bounds. The PC-Tree algorithm demonstrated superior performance over classical baselines such as the standard PC algorithm and Greedy Equivalence Search (GES), particularly in terms of Structural Hamming Distance (SHD) and Precise Recovery Rate (PRR) as the graph scale increased. Robustness tests also indicated that the algorithms maintain efficacy under non-Gaussian noise settings, such as Uniform and Laplace distributions.

Limitations and Future Directions

While this work closes the gap for directed trees, several challenges remain:

  • Beyond Trees: The current optimal bounds apply to trees and polytrees (where the skeleton is acyclic). Extending these results to general DAGs with cycles in their undirected skeleton is a necessary next step.
  • Latent Variables: The model assumes all variables are observed. In many real-world scenarios, hidden confounders exist, necessitating the integration of latent variable models into the optimal complexity framework.
  • Non-Parametric Extensions: While the algorithms show robustness to non-Gaussian noise, the core proofs are grounded in Gaussian properties. Developing fully non-parametric optimal bounds remains an open area for research.

Summary updated

BibTeX
@inproceedings{wang2024optimal,
  author = {Yuhao Wang and Ming Gao and Wai Ming Tai and Bryon Aragam and Arnab Bhattacharyya},
  title = {{Optimal estimation of Gaussian (poly)trees}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
}
Figure