Zoom link: https://upenn.zoom.us/j/98220304722

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, it leads to a unified framework for designing convex calibrated surrogate losses — yielding Bayes consistent learning algorithms — for a wide variety of complex structured prediction problems. In “computational” learning theory, it leads to a unified framework for demonstrating efficient PAC learning algorithms for a broad class of learning problems with “realizable-statistic” conditional label distributions, including for example novel PAC learning results for multiclass learning where the ground truth comes from a generalized linear model. Along the way, I will describe a variety of tools we have developed, including 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.