Yusu Wang (UC San Diego)

1:00pm - 2:00pm PT Friday, November 1, 2024

Title and Abstract

Size (OOD) generalization of neural models via Algorithmic alignment

Extensive literature on classical algorithm design has led to the development of many elegant frameworks. With the recent surge in the capabilities of modern AI, a natural question arises: can we combine traditional algorithmic ideas with neural networks to create more powerful frameworks that can adapt to data? In particular, when can a neural model with bounded complexity in fact generalize to problem instances of arbitrary size? This is the problem of size generalization, which is a special case of out of distribution (OOD) generalization. In this talk, I will present three examples of achieving such size generalization by “aligning” the neural models with algorithmic structures: (1) a mixed neural algorithmic framework for the (NP hard) Steiner tree problem, (2) neural approximation of Wasserstein distances between point sets (discrete measures), and (3) a neural Bellman-Ford model for computing shortest path. The last example (the neural Bellman-Ford model) shows a particularly interesting phenomenon: It turns out that we can construct a set of only a constant number of small graphs, such that if the neural Bellman-Ford model (even when over-parameterized) has low loss over these graphs, then this model will probably generalize to arbitrary graphs with positive weights.

Bio

Yusu Wang is currently Professor in the Halicioglu Data Science Institute (HDSI) at University of California, San Diego, where she also serves as the Director for the NSF National AI Institute TILOS. Prior to joining UCSD, she was Professor in the Computer Science and Engineering Department at the Ohio State University. She obtained her PhD degree from Duke University in 2004 where she received the Best PhD Dissertation Award in the CS Department. From 2004-2005, she was a post-doctoral fellow at Stanford University. Yusu Wang primarily works in geometric and topological data analysis (with a textbook on Computational Topology for Data Anaysis), geometric deep learning and representation learning. She received DOE Early Career Principal Investigator Award in 2006, and NSF Career Award in 2008. She is on the editorial boards for SIAM Journal on Computing (SICOMP) and Journal of Computational Geometry (JoCG). She is a member of the Computational Geometry Steering Committee, as well as a member of the AATRN Advisory Committee. She also serves in the SIGACT CATCS committee and AWM Meetings Committee.