Probabilistic models provide a powerful means of quantifying uncertainty, modeling prior beliefs, and describing complex dependencies in data. These models are frequently used to make predictions in settings with limited training data such as in health care (medical diagnosis from symptoms), biology (inferring protein regulatory networks), computer vision (stereopsis), and natural language processing (parsing and text generation). Using these models requires performing probabilistic inference, which takes evidence about observed variables to draw conclusions about unobserved variables. Inference in these applications corresponds to a complex combinatorial optimization problem that at first glance appears to be extremely difficult to solve. However, practitioners have made significant strides in designing heuristic algorithms to perform real-world inference accurately and efficiently. This project focused on algorithms and theory for probabilistic inference problems in large-scale machine learning systems.

A major contribution of this project was bridging the gap between theory and practice for finding the most probable assignment of the unobserved variables (MAP inference) in a special case of probabilistic models (Potts models). Heuristics based on iterative techniques (alpha-expansion) and linear programming relaxations have been shown empirically to return solutions that are either globally optimal, or close to globally optimal. PIs David Sontag and Aravindan Vijayaraghavan with PhD students Hunter Lang (MIT) and Aravind Reddy (Northwestern) showed through both theoretical and empirical results published in a series of works (AISTATS 2018, AISTATS 2019, ICML 2021, AISTATS 2021) that variants of a natural notion called stability could explain the tractability of these instances in practice.

Specifically, for the alpha-expansion algorithm, we proved (in Lang et al., ICML 2021) that it always returns a globally optimal assignment for Potts models, with a catch: the returned assignment is only guaranteed to be optimal for an instance within a small perturbation of the original problem instance. Intuitively, we expect that for robust models used in applications, small perturbations to their parameters should have similar optimal assignments, which would imply that alpha-expansion provides near-optimal assignments for the original models. Moreover, for a linear programming relaxation, we proved that it is close to integral when the instance is close to stable or satisfies a condition called block stability (AISTATS 2019, AISTATS 2021). We then designed algorithms that can certify whether models satisfy these conditions. Using our new methods for certifying stability, we were able to demonstrate that several computer vision models indeed satisfy these stability conditions. Taken together, these results give a cohesive explanation for the good performance of the above heuristics in practice. 

Our results also suggested a monotonicity principle for algorithm design for the linear programming relaxation: we showed that the relaxation performs well when the input is generated as a simpler tractable part of the model and remaining factors are random but slightly biased toward the ground truth.

The project also led to theory-inspired improvements for emerging paradigms in machine learning like weak supervision, where one seeks to learn from imperfect labels that domain experts provide (e.g., that any review with the word ?great? should be labeled as positive sentiment). Under the assumption of conditional independence between the weak labels and the features, in joint work of the PIs with MIT PhD student Hunter Lang (published in NeurIPS 2022), we proved that there is a trade-off between the number of data points ?covered? by the weak labels and their noise rates. We then showed that we could use the popular ?cut statistic? heuristic to rank data points by a measure of the confidence in their weak labels; finally, we train the downstream classifier on the most confident of these. Surprisingly, we found that this technique improved the performance of every single weak supervision method previously published, often by large amounts. 

Other research highlights from this project include new theory and algorithms for clustering Euclidean instances that are stable (Dutta et al., NeurIPS ?17), new algorithms with provable guarantees for learning depth-2 neural networks (Awasthi et al., NeurIPS ?21), improved algorithms using ideas from co-training for prompt-based learning with large language models and unlabeled data (Lang et al., ICML ?22), as well as new algorithms and provable guarantees for human-AI interaction (Mozannar et al., AAAI '22) and self-supervised learning tasks that arise in healthcare (Agrawal et al., AISTATS ?22). 

The PIs also organized activities and workshops with the goal of reaching out to the broader scientific community interested in topics related to the project. PI Vijayaraghavan co-organized (along with Aleksander Madry and Daniel Hsu) the FOCS 2021 workshop on New Directions in Machine Learning. PI Vijayaraghavan also co-organized several day-long theory workshops at Northwestern University that got broad attendance from theory faculty, postdocs and students in many mid-west universities in and near Chicago. Two of these workshops were closely related to the topic of this project. These workshops were open to the public, and videos are publicly accessible on the website.

Last Modified: 01/20/2023
Modified by: Aravindan Vijayaraghavan