Optimal Instance-Dependent Sample Complexity for Agnostic PAC Learning

In a preprint submitted on August 6, 2026, Markus Engelund Mathiasen, Jian Qian, and Nikita Zhivotovskiy give a deterministic, generally improper agnostic PAC learner whose excess-risk bound scales, up to universal constants, as

$$\sqrt{\frac{L^*(d+\log(1/\delta))}{n}}+\frac{d+\log(1/\delta)}{n},$$

where $d$ is the VC dimension and $L^*$ is the best risk in the concept class. This matches known lower bounds at every fixed value of $L^*$ and settles the optimal sample complexity of agnostic PAC learning up to universal constants.

The authors trace the proof through several stages of AI-assisted work. OpenAI GPT-5.5 Pro first studied simple VC classes; GPT-5.6 Sol in Ultra mode then helped with the rectangle case, leading the authors to the general random-restriction argument. They also report a reproducibility experiment in which GPT-5.6 Sol in Pro mode received a compressed prompt in 16 independent runs: 11 runs produced essentially correct proof outlines and completed the remaining argument. The theorem and exposition are presented under the authors' responsibility.