NCSA Calendar
NCSA staff who would like to submit an item for the calendar can email newsdesk@ncsa.illinois.edu.
Theory Seminar: Dr. Shaddin Dughmi, "A Combinatorial Lens on Supervised Learning."
- Event Type
- Seminar/Symposium
- Sponsor
- Theory and Algorithms Research Area
- Location
- 3401 Siebel Center
- Date
- Dec 8, 2025 10:00 - 11:00 am
- Speaker
- Dr. Shaddin Dughmi
- Contact
- Allison Mette
- agk@illinois.edu
- Originating Calendar
- Siebel School Speakers Calendar
Abstract: I will describe some recent joint results on the theory of supervised learning which follow from connections to combinatorial optimization. First, I will examine whether there are "simple" algorithmic templates that are guaranteed to include near-optimal learners in settings with large or high dimensional label spaces. This will involve understanding various recipes for regularization, and whether one such recipe is universal for supervised learning. Second, I will show that in idealized semi-supervised settings, where the unlabeled data distribution is known or can be fully learned, the forms of regularization needed for learning become much simpler. Third, I will show that the difficulty of a supervised learning problem can be captured by its finite neighborhoods.
Key to all these results is a transductive view of learning which is highly combinatorial, and closely related to bipartite matching on infinite graphs. Our proofs leverage tools from matching theory and generalize them appropriately to derive insights into learning.