Taming combinatorial explosion with new optimization-induced priors

Oregon Convention Center 

Combinatorial structures are commonplace in statistical applications, such as those involving phylogenetic trees, gene expression networks, or flow network control. In combinatorial models, as the parameter is often a high-dimensional integer vector under heavy constraints, it has been tremendously challenging to conduct statistical inference in such a discrete space with combinatorial explosion. To tackle this issue, we propose to exploit integer linear programming as a mapping to induce useful probability distributions on combinatorial space. Taking a Bayesian approach, we assign a precursor prior (such as multivariate Gaussian) to a real-valued vector, then transform the distribution onto the vertex set of an integral polytope. We can efficiently estimate the posterior using the graph-accelerated Metropolis-adjusted Langevin algorithm. This framework leads to straightforward model specification, principled uncertainty quantification, and flexible model-based extension. I will illustrate its application in a capacity control problem for traffic network data.