Learnability of Complex Objects in Modern AI

As machine learning and AI systems become increasingly pervasive in high-stakes domains, building theoretical foundations to understand and analyze their behavior has become more elusive, yet more pressing than ever before. Modern AI systems learn sophisticated structures that far exceed the analytical reach of classic learning theory.

In this talk, I will present work from my group on the learnability of complex objects within modern AI settings. First, I will discuss new frameworks for training verifiers that can flag off-track inference. These learned verifiers help mitigate catastrophic failure modes of LLMs (e.g., they can appear convincing while being wrong) and, more generally, enhance the reasoning capabilities of current LLM generators.

I will then discuss the learnability of another class of complex objects: algorithms for tasks like pricing or partitioning that are intractable within traditional frameworks. I will present general sample complexity results via dual-function classes applicable to a variety of learning-augmented algorithms.