Bridging Computational and Statistical Theories of Machine Learning

Tutorial at COLT 2026
Monday June 29, 8:30–10:10 am

Tutorial Presenter

Shivani Agarwal

Tutorial 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, despite the names, 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.

This tutorial will present a variety of tools for 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, these tools lead to a unified framework for designing convex calibrated surrogate losses — yielding efficient Bayes consistent learning algorithms — for a wide variety of complex structured prediction 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 that will be discussed in the tutorial 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).

No background in either computational or statistical learning theory will be assumed. At the end of the tutorial, participants will be able to appreciate deep connections between the two strands of literature, and will be able to apply the tools discussed in the tutorial to construct learning algorithms and derive learning-theoretic guarantees for a wide variety of learning problems in both settings.

Target Audience and Prerequisite Knowledge

The target audience for the tutorial includes both seasoned researchers in machine learning and learning theory, and new members of the community such as beginning graduate students. The only background that will be assumed will be some exposure to basic machine learning problems and algorithms, and mathematical maturity.