Collaborative Research: CIF: Small: Convexification-based Decomposition Methods for Large-Scale Inference in Graphical Models

Northwestern University, Evanston IL

Investigators

Abstract

Systems prevalent in modern society can be characterized by complex networks of interconnected components that generate massive amounts of data. The ability to make timely inferences using these data presents unprecedented opportunities to solve major societal problems. For example, advances in wearable technology are transforming the delivery of personalized healthcare and wellness programs. More broadly, wearables naturally create sensor networks over populations and the data from these networks can be harnessed to detect and/or prevent diseases, crimes or environmental hazards. Inference from such data can be naturally accomplished using graphical models. Unfortunately, existing technology for graphical models requires stringent assumptions that are seldom satisfied in modern applications. The goal of this project is to address these shortcomings by developing new computational methods that automatically infer the topology of a graphical model from high-dimensional data, identify and/or correct outliers and anomalies, and solve the estimation problems simultaneously. Furthermore, the proposed research will lead to innovative teaching material defining modern data science curricula and develop a diverse cadre of Ph.D. students with skills at the interface of discrete optimization, continuous optimization, and statistics. Inference problems with spurious data and unknown network topologies can be modeled as large-scale constrained mixed-integer convex optimization problems. To address the challenges posed by the presence of the combinatorial constraints, this project employs a combination of two key ideas. The first idea is to decompose the problem into progressively small problems, that can be solved in a decentralized and parallel fashion, by leveraging the Markov property inherent in graphical models. The second idea is the convexification of the combinatorial constraints, to diminish or prevent altogether the loss in quality from the decomposition of the problem. Unlike typical decomposition methods such as Lagrangian relaxation, which can lead to large duality gaps, this project will develop novel techniques based on convexification and Fenchel duality. In particular, the resulting method will account for the combinatorial restrictions and the nonlinear loss function concurrently, ultimately resulting in small or no duality gaps. The successful completion of the project will lead to significant advances in inference with spatio-temporal data, interpretable prediction, and identification of causal relationships. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.