Jonathan Shafer (MIT) – From Learning Theory to Cryptography: Provable Guarantees for AI

Title: From Learning Theory to Cryptography: Provable Guarantees for AI

Abstract:

Ensuring that AI systems behave as intended is a central challenge in contemporary AI. This talk offers an exposition of provable mathematical guarantees for learning and security in AI systems.

Starting with a classic learning-theoretic perspective on generalization guarantees, we present two results quantifying the amount of training data that is provably necessary and sufficient for learning: (1) In online learning, we show that access to unlabeled data can reduce the number of prediction mistakes quadratically, but no more than quadratically [NeurIPS23, NeurIPS25 Best Paper Runner-Up]. (2) In statistical learning, we discuss how much labeled data is actually necessary for learning—resolving a long-standing gap left open by the celebrated VC theorem [COLT23].

Provable guarantees are especially valuable in settings that require security in the face of malicious adversaries. The main part of the talk adopts a cryptographic perspective,  showing how to: (1) Utilize interactive proof systems to delegate data collection and AI training tasks to an untrusted party [ITCS21, COLT23, NeurIPS25]. (2) Leverage random self-reducibility to provably remove backdoors from AI models, even when those backdoors are themselves provably undetectable [STOC25].

The talk concludes with an exploration of future directions concerning generalization in generative models, and AI alignment against malicious and deceptive AI.