  Bayesian networks are a class of popular graphical models that encode causal
and conditional independence relations among variables by directed acyclic
graphs (DAGs). We propose a novel structure learning method, annealing on
regularized Cholesky score (ARCS), to search over topological sorts, or
permutations of nodes, for a high-scoring Bayesian network. Our scoring
function is derived from regularizing Gaussian DAG likelihood, and its
optimization gives an alternative formulation of the sparse Cholesky
factorization problem from a statistical viewpoint, which is of independent
interest. We combine global simulated annealing over permutations with a fast
proximal gradient algorithm, operating on triangular matrices of edge
coefficients, to compute the score of any permutation. Combined, the two
approaches allow us to quickly and effectively search over the space of DAGs
without the need to verify the acyclicity constraint or to enumerate possible
parent sets given a candidate topological sort. The annealing aspect of the
optimization is able to consistently improve the accuracy of DAGs learned by
local search algorithms. In addition, we develop several techniques to
facilitate the structure learning, including pre-annealing data-driven tuning
parameter selection and post-annealing constraint-based structure refinement.
Through extensive numerical comparisons, we show that ARCS achieves substantial
improvements over existing methods, demonstrating its great potential to learn
Bayesian networks from both observational and experimental data.
