CAREER: Scalable learning with combinatorial structure

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Advances in science and technology increasingly rely on inference and prediction from data such as videos, molecules, networks, or sets of purchased goods. Such data consists of several elements that participate in a collective structure. Effective inference and prediction in turn rely on (i) concise and accurate representations of latent interdependence structure in data; and (ii) fast learning and optimization algorithms that can process modern large data sets. This CAREER project addresses these challenges by building new algorithmic foundations that open a wider set of mathematical tools for practical data analysis. In particular, this project explores and exploits key structural properties and representations. For example, a wide spectrum of important dependence structures (and consequently numerous learning tasks) are well captured by the ubiquitous combinatorial concept of submodular functions on sets, characterized by the property of diminishing returns. Building on this insight and other new tools, this research develops a suite of scalable optimization procedures with theoretical guarantees, as well as new tools for probabilistic modeling and fast inference. The resulting combinatorial learning methods are deployed in novel applications addressing the development of new materials, reducing environmental impact, in video analytics, and healthcare. Thereby, the proposed methods foster progress and deliver insights beyond computer science. Parts of this project are integrated into a new advanced graduate class and a new hands-on undergraduate class on data analytics that combines statistical modeling with computation, forming a core part of a new educational program. Undergraduate students are involved in the application part of the research, and selected results will serve to motivate high school students to pursue STEM careers. For the research community, the project includes interdisciplinary workshops and tutorials, and further the confluence of discrete optimization and machine learning. Educational materials, data and code are made publicly available. The research questions of this project include three main threads: 1) Developing a set of new, scalable optimization techniques with theoretical guarantees for combinatorial learning problems. The algorithms will combine combinatorial and continuous optimization, exploit suitable mathematical properties, relaxations, and compact representations, and will implement new ways to leverage data-dependent properties that distinguish practical cases from the worst case. 2) Extending insights from optimization to probabilistic modeling and inference. This transfer will enable new models and new, fast computational procedures for sampling and probabilistic inference that exploit similar properties as the optimization algorithms. 3) Real-world applications of the new models and algorithms. Via interdisciplinary collaborations, the third thread explores new applications of combinatorial learning methods to video analytics, instruction, healthcare, and materials design.