IFML Seminar: 11/6/26 - Bridging Computational and Statistical Theories of Machine Learning

Abstract: There are two broad strands of literature on the theoretical underpinnings of machine learning. “Computational“ learning theory traces its origins to theoretical computer science, with an influential paper being Valiant’s 1984 paper on probably approximately correct (PAC) learning. “Statistical” learning theory dates back even further, and traces its origins to statistical decision theory, with an influential paper being Cover and Hart’s 1967 paper on asymptotic analysis of nearest neighbor classification. The fundamental questions asked in both strands of literature are closely related, and indeed, both strands generally involve both computational and statistical aspects. Nevertheless, the vocabulary and tools used in these two strands of literature are often vastly different, making them feel like two different worlds. 

In this talk, I will describe our work on bridging these two worlds, leading to a unified framework for studying large classes of learning problems in both settings — with novel results in both. In “statistical“ learning theory, the tools we have developed lead to a unified framework for designing convex calibrated surrogate losses — yielding efficient Bayes consistent learning algorithms — for a wide variety of complex learning problems. In “computational” learning theory, these tools lead to a unified framework for demonstrating efficient PAC learning algorithms for a broad class of learning problems with ‘realizable-statistic’ conditional label distributions, yielding for example novel PAC learning results for multiclass learning where the ground truth comes from a generalized linear model. Some of the concrete tools I will discuss include the notions of ‘Bayes-sufficient statistics’, ‘strongly proper losses’, and ‘realizable-statistic models’, the latter being a flexible class of intermediate PAC learning models that interpolates between the realizable and agnostic settings. 

This talk includes work published at NeurIPS 2025, as well as previous and ongoing work.

Bio: Shivani Agarwal is Associate Professor of Computer and Information Science and (by courtesy) of Statistics and Data Science at the University of Pennsylvania. Her research interests are primarily in the computational, mathematical, and statistical foundations of machine learning and data science, including theory and algorithms; they also include applications of machine learning, particularly in the life sciences, as well as connections between machine learning and other disciplines such as social choice theory, econometrics, and psychology, particularly related to statistical ranking and choice modeling. She has served as Action Editor for the Journal of Machine Learning Research and Associate Editor for the Journal of Artificial Intelligence Research and the Harvard Data Science Review, and served as Program Co-Chair for the Annual Conference on Learning Theory (COLT) in 2020. She has also served as Lead PI and Director of the NSF-funded Penn Institute for Foundations of Data Science (PIFODS) and Co-Director of the Penn Research in Machine Learning (PRiML) forum, as well as Co-Director of the Indo-US Joint Center for Advanced Research in Machine Learning, Game Theory, and Optimization. Prior to her current position, she was a Radcliffe Fellow at Harvard and a Ramanujan Fellow at the Indian Institute of Science, and taught as a postdoctoral lecturer at MIT. She received her PhD in computer science from the University of Illinois, Urbana-Champaign.

Zoom link: https://utexas.zoom.us/j/89110047398