On polynomial time solvability of combinatorial Markov random fields

The problem of inferring Markov random fields (MRFs) with a sparsity or robustness prior can be naturally modeled as a mixed-integer program. This motivates us to study a general class of convex submodular optimization problems with indicator variables, which we show to be polynomially solvable in this paper. The key insight is that, possibly after … Read more

A note on quadratic constraints with indicator variables: Convex hull description and perspective relaxation

In this paper, we study the mixed-integer nonlinear set given by a separable quadratic constraint on continuous variables, where each continuous variable is controlled by an additional indicator. This set occurs pervasively in optimization problems with uncertainty and in machine learning. We show that optimization over this set is NP-hard. Despite this negative result, we … Read more

On the convex hull of convex quadratic optimization problems with indicators

We consider the convex quadratic optimization problem with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of a single positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of … Read more

Compact extended formulations for low-rank functions with indicator variables

We study the mixed-integer epigraph of a low-rank convex function with non-convex indicator constraints, which are often used to impose logical constraints on the support of the solutions. Extended formulations describing the convex hull of such sets can easily be constructed via disjunctive programming, although a direct application of this method often yields prohibitively large … Read more

A Graph-based Decomposition Method for Convex Quadratic Optimization with Indicators

In this paper, we consider convex quadratic optimization problems with indicator variables when the matrix Q defining the quadratic term in the objective is sparse. We use a graphical representation of the support of Q, and show that if this graph is a path, then we can solve the associated problem in polynomial time. This … Read more

Comparing Solution Paths of Sparse Quadratic Minimization with a Stieltjes Matrix

This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the “L0-path” where the discontinuous L0-function provides the exact sparsity count; the “L1-path” where the L1-function provides a convex surrogate of sparsity count; … Read more

Learning Optimal Prescriptive Trees from Observational Data

We consider the problem of learning an optimal prescriptive tree (i.e., a personalized treatment assignment policy in the form of a binary tree) of moderate depth, from observational data. This problem arises in numerous socially important domains such as public health and personalized medicine, where interpretable and data-driven interventions are sought based on data gathered … Read more

Single-neuron convexifications for binarized neural networks

Binarized neural networks are an important class of neural network in deep learning due to their computational efficiency. This paper contributes towards a better understanding of the structure of binarized neural networks, specifically, ideal convex representations of the activation functions used. We describe the convex hull of the graph of the signum activation function associated … Read more

Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees

In this paper, we study the problem of inferring time-varying Markov random fields (MRF), where the underlying graphical model is both sparse and changes sparsely over time. Most of the existing methods for the inference of time-varying MRFs rely on the regularized maximum likelihood estimation (MLE), that typically suffer from weak statistical guarantees and high … Read more

Strong Optimal Classification Trees

Decision trees are among the most popular machine learning (ML) models and are used routinely in applications ranging from revenue management and medicine to bioinformatics. In this paper, we consider the problem of learning optimal binary classification trees. Literature on the topic has burgeoned in recent years, motivated both by the empirical suboptimality of heuristic … Read more