Title: Consistency Guarantees for Permutation-Based Causal Inference Algorithms,
Abstract: Bayesian networks, or directed acyclic graph (DAG) models, are widely used to
represent complex causal systems. Since the basic task of learning a Bayesian
network from data is NP-hard, a standard approach is greedy search over the
space of DAGs or Markov equivalent DAGs. Since the space of DAGs on p nodes and
the associated space of Markov equivalence classes are both much larger than
the space of permutations, it is desirable to consider permutation-based
searches. We here provide the first consistency guarantees, both uniform and
high-dimensional, of a permutation-based greedy search. Geometrically, this
search corresponds to a simplex-type algorithm on a sub-polytope of the
permutohedron, the DAG associahedron. Every vertex in this polytope is
associated with a DAG, and hence with a collection of permutations that are
consistent with the DAG ordering. A walk is performed on the edges of the
polytope maximizing the sparsity of the associated DAGs. We show based on
simulations that this permutation search is competitive with standard
approaches.