"Mixed-Integer Convex Optimization for Statistical Learning: A Tale of Two C(omplex)ities"Küçükyavuz, SimgeMany statistical learning problems involving sparsity and other structural constraints can be formulated as mixed-integer convex optimization problems involving indicator variables and penalties or constraints on these indicators. As motivation, the first part of this talk will focus on two statistical learning problems from probabilistic graphical models. The first is learning directed acyclic graphs (DAGs) from continuous observational data, also known as the causal discovery problem. The second is the real-time inference of Gaussian hidden Markov models from data affected by outlier noise. Current state-of-the-art structure learning methods for these problems face significant limitations: (i) they lack optimality guarantees and often yield suboptimal solutions; (ii) they rely on the restrictive assumption of homoscedastic noise or no outliers. We propose computationally efficient mixed-integer convex optimization frameworks to address these shortcomings. Numerical experiments demonstrate that our method outperforms existing algorithms and is robust to noise heteroscedasticity or outliers. In the second part of the talk, we address the challenge of weak continuous relaxations inherent in natural mixed-integer convex formulations for such structured learning problems, which hinder the performance of branch-and-bound-based solvers. We develop novel methods to strengthen these formulations by deriving a convex hull description of the associated mixed-integer set in an extended space. Notably, this approach reduces the convexification of these problems to the characterization of a polyhedral set in the extended formulation. Our new theoretical framework unifies several previously established results and provides a foundation for applying polyhedral methods to strengthen the formulations of such mixed-integer nonlinear sets. |
« back