stat.MLNov 9, 2026

Near-Optimal Sample Complexity of Deterministic Agnostic PAC Learning

Authors: Shai Ben-David, Steve Hanneke, Farnam Mansouri, Amirreza Shaeiri

Organizations: David Cheriton School of Computer Science University of Waterloo & Vector Institute Waterloo, ON, Canada · Department of Computer Science Purdue University West Lafayette, IN, USA

Abstract

We study the problem of agnostic PAC learning under deterministic labels, where the examples are labeled by an arbitrary deterministic function, which need not belong to the concept class CC. This model captures misspecification without stochastic label noise and lies between the realizable and fully agnostic settings. Prior work showed that, when CC has finite diameter KK and VC dimension dd, deterministic labels can improve the sample complexity upper bound from the classical agnostic guarantee O(d/ε2)O(d/\varepsilon^2) to O~(K/ε)\widetilde{O}(K/\varepsilon), but left a large gap between upper and lower bounds. Our main result sharpens this picture. We prove that every class of VC dimension dd and finite diameter KK is learnable with sample complexity O~(K1/3 d2/3ε)\widetilde{O}\left( \frac{K^{1/3} \, d^{2/3}}{\varepsilon} \right), and we construct classes for which this bound is tight up to logarithmic factors. We also study the online analogue of this problem and show that the minimax regret is again partly controlled by the diameter of the class. Technically, our upper bounds are obtained via memorization-based learning algorithms that exploit the deterministic label structure.

Explore similar work

CardsList
  1. An Optimal Agnostic PAC Algorithm

    Aug 6, 2026Markus Engelund Mathiasen, Jian Qian, Nikita ZhivotovskiyPAC LearningStatistical Learning Theory

  2. PAC Learning with Multiple Correct Answers

    Nov 3, 2026Steve Hanneke, Farnam Mansouri, Alireza F. Pour +2PAC LearningStatistical Learning Theory

  3. Adversarially Robust PAC Learning with Optimal VC Rates

    Sep 21, 2026Steve Hanneke, Amirreza ShaeiriSample ComplexityAdversarial Robustness