Atmosphere Ocean Science Friday Seminar

---

Exact Sample Complexity of Probably Approximately Correct (PAC) Learners under Bounded Finite Support

Speaker: Siddhant Arora

Location: Warren Weaver Hall 1314

Date: Friday, September 12, 2025, 4 p.m.

Synopsis:

In 1931, Kurt Gödel demonstrated that in any sufficiently powerful, consistent, and effectively axiomatized formal system, there exist true statements that cannot be proved within the system. Nearly a century later, a 2019 paper in Nature by Ben-David et al. revealed that machine learning falls victim to this fate: the learnability of certain problems is undecidable within the standard axioms of mathematics, namely Zermelo–Fraenkel set theory with the axiom of choice (ZFC).

In this talk, we explore a variation of the problem posed by Ben-David et al., but with an added practical constraint. For this, we have something even stronger than decidability: an algorithm that can determine the exact number of samples required to achieve a specified accuracy (the “A” in PAC) with a given probability (the “P” in PAC).