# Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks

arXiv: https://arxiv.org/abs/2005.14346 · HTML: https://mlsanity.com/paper/2005.14346/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2020.

## Built on by (most cited first, 9 of 9)

- [On the convex hull of convex quadratic optimization problems with indicators](https://mlsanity.com/paper/2201.00387/) (2022)
- [Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models](https://mlsanity.com/paper/2404.12592/) (2024)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)
- [Learning Directed Acyclic Graphs from Partial Orderings](https://mlsanity.com/paper/2403.16031/) (2024)
- [An Asymptotically Optimal Coordinate Descent Algorithm for Learning Bayesian Networks from Gaussian Models](https://mlsanity.com/paper/2408.11977/) (2024)
- [Scalable First-order Method for Certifying Optimal k-Sparse GLMs](https://mlsanity.com/paper/2502.09502/) (2025)
- [Learning Dynamic Bayesian Networks from Data: Foundations, First Principles and Numerical Comparisons](https://mlsanity.com/paper/2406.17585/) (2024)
- [Empirical Bayes for Dynamic Bayesian Networks Using Generalized Variational Inference](https://mlsanity.com/paper/2406.17831/) (2024)
- [Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators](https://mlsanity.com/paper/2608.01385/) (2026)

## Abstract (arXiv)

Bayesian Networks (BNs) represent conditional probability relations among a set of random variables (nodes) in the form of a directed acyclic graph (DAG), and have found diverse applications in knowledge discovery. We study the problem of learning the sparse DAG structure of a BN from continuous observational data. The central problem can be modeled as a mixed-integer program with an objective function composed of a convex quadratic loss function and a regularization penalty subject to linear constraints. The optimal solution to this mathematical program is known to have desirable statistical properties under certain conditions. However, the state-of-the-art optimization solvers are not able to obtain provably optimal solutions to the existing mathematical formulations for medium-size problems within reasonable computational times. To address this difficulty, we tackle the problem from both computational and statistical perspectives. On the one hand, we propose a concrete early stopping criterion to terminate the branch-and-bound process in order to obtain a near-optimal solution to the mixed-integer program, and establish the consistency of this approximate solution. On the other hand, we improve the existing formulations by replacing the linear "big-M" constraints that represent the relationship between the continuous and binary indicator variables with second-order conic constraints. Our numerical results demonstrate the effectiveness of the proposed approaches.