Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks

Area of Science:

• Artificial Intelligence
• Machine Learning
• Computational Statistics

Background:

• Bayesian Networks (BNs) model conditional probability relationships using directed acyclic graphs (DAGs) for knowledge discovery.
• Learning sparse DAG structures from continuous data is crucial but computationally challenging.
• Existing optimization solvers struggle with provably optimal solutions for medium-sized BN structure learning problems.

Purpose of the Study:

• To develop computationally efficient and statistically sound methods for learning sparse Bayesian Network structures.
• To address the limitations of current optimization solvers in handling mixed-integer programming formulations for BN learning.
• To improve the performance and scalability of Bayesian Network structure learning algorithms.

Main Methods:

• Formulating BN structure learning as a mixed-integer program with a convex quadratic loss and regularization.
• Proposing an early stopping criterion for branch-and-bound to find near-optimal solutions and establishing their consistency.
• Replacing linear "big-M" constraints with second-order conic constraints in the optimization formulation.

Main Results:

• The proposed early stopping criterion yields consistent, near-optimal solutions for BN structure learning.
• The reformulation using second-order conic constraints improves the tractability of the optimization problem.
• Numerical results validate the effectiveness and efficiency of the developed computational and statistical approaches.

Conclusions:

• The study presents effective computational and statistical strategies for learning sparse Bayesian Network structures.
• The novel optimization techniques enhance the practical applicability of Bayesian Networks in knowledge discovery.
• The findings contribute to more efficient and accurate methods for inferring complex probabilistic relationships from data.