- This event has passed.
AMS Weekly Seminar | Ellen Vitercik
February 20 @ 1:30 pm - 2:30 pm
Location: Gilman 50
When: February 20th at 1:30 p.m.
Title: Size generalization in learning-augmented optimization
Abstract: When designing algorithms for computational problems in practice, there is often ample data about the application domains in which the algorithms will be used. This data can be harnessed via machine learning to optimize algorithmic performance. This talk showcases a prime example of this algorithmic pipeline for online Bayesian bipartite matching (OBBM). OBBM is a critical computational challenge across online marketplaces, including rideshare, crowdsourcing, and digital advertising. While the optimal policy requires exponential space, we demonstrate that a graph neural network (GNN) can be trained to emulate it, resulting in a polynomial-time policy that outperforms standard benchmarks. We also provide theoretical guarantees that affirm the suitability of GNNs for this task. Notably, our approach exhibits strong size generalization: although we train on small graphs, the learned policy generalizes to much larger graphs. We conclude by exploring how the phenomenon of size generalization extends to other contexts, including combinatorial algorithm selection, highlighting its broader significance.
This talk is on joint work with Vaggos Chatziafratis, Alexandre Hayderi, Ishani Karmarkar, Yingxi Li, Amin Saberi, and Anders Wikum.
Bio: Ellen Vitercik is an Assistant Professor at Stanford University with a joint appointment between the Management Science & Engineering department and the Computer Science department. Her research revolves around machine learning theory, discrete optimization, and the interface between economics and computation. Before joining Stanford, she spent a year as a Miller Postdoctoral Fellow at UC Berkeley and received a PhD in Computer Science from Carnegie Mellon University. Her research has been recognized with a Schmidt Sciences AI2050 Early Career Fellowship, an NSF CAREER award, the SIGecom Doctoral Dissertation Award, and the CMU School of Computer Science Distinguished Dissertation Award, among other honors.
Zoom link: https://wse.zoom.us/j/93287142219?pwd=z9fqWnRMzmzS0SGijRiie5yN3kHRSZ.1