AF:Small:A Combinatorial Lens on Learning

Despite its undeniable practical success, machine learning remains poorly understood in many respects. Even some of the most fundamental theoretical questions are not settled. These questions include what is learnable, what does the optimal learning algorithm look like, and what are the characteristics of a problem that enable, or prohibit, learning.

This project will explore a new mathematical lens with which to view machine learning, one based in combinatorics, optimization, and the theory of matching in graphs. This perspective promises to unlock answers to the aforementioned questions during the course of this project, and in doing so deepen our understanding of machine learning and guide the search for better algorithmic approaches.

In addition to these research goals, the project will include a substantial educational and outreach component. Through research mentoring and new course offerings, the principal investigator will train students at the high-school, undergraduate, and graduate levels in the mathematical fundamentals of machine learning. The principal investigator will also disseminate the ideas and findings of this project through survey articles, tutorials, and presentations, as well as by organizing meetings and workshops to bring together researchers around these fundamental questions.

The starting point for this project is the following simple, yet powerful, observation: supervised classification problems can be viewed as a bipartite matching problem on a large, often infinite, graph. This fact follows by re-imagining the one-inclusion graph (OIG) algorithm, an abstraction of optimal learning from the early days of the field, as solving a matching problem.

This new perspective allows us to draw on powerful results and tools from combinatorics and optimization to understand the structure of optimal matchings in this graph, and consequently the structure of optimal learning algorithms. Furthermore, generalizing this matching problem beyond classification promises structural and algorithmic insights into supervised learning writ large.

This project will tackle the following questions through this new lens: (a) What are the algorithmic recipes for optimal supervised learning? (b) Does this lens help explain the success of common algorithmic approaches, or prescribe new ones? (c) Can we derive structural characterizations of learnability that apply broadly to supervised learning?

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.