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

Aug 6, 2026

An Optimal Agnostic PAC Algorithm

Let H⊆{−1,+1}XH\subseteq\{-1,+1\}^X be a class of finite VC dimension d≥1d\ge1. Writing LL for the binary risk and L∗=min⁡h∈HL(h)L^*=\min_{h\in H}L(h), we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size nn, for every 0<δ≤1/20<δ\le 1/2, with probability at least 1−δ1-δ, L(h^)≤L∗+7⋅108(L∗(d+log⁡(1/δ))n+d+log⁡(1/δ)n).L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right). This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed L∗L^*, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].
Nov 3, 2026

PAC Learning with Multiple Correct Answers

We study PAC learning when each example comes with a set of at most ℓ\ell correct labels and a prediction is correct if it belongs to this set. Training may reveal the full set, only whether a proposed label is correct (bandit feedback), or one correct label chosen by a demonstrator (demonstrations). Our main finding is that demonstrations can be much harder than full sets, and even than bandit feedback, both in which classes can be learned and in how many examples are needed. For finite label spaces, a generalized Natarajan dimension characterizes learnability from full sets and from bandit feedback, in both the realizable and the agnostic setting. From demonstrations, however, a class is realizably learnable if and only if the intersections of at most ℓ+1\ell+1 of its hypotheses are learnable from full sets. Already with three labels, this condition can fail for a class learnable from a single full-set example or even a single bandit answer. When the condition holds, we show that O~(ε−ℓ)\widetilde O(\varepsilon^{-\ell}) demonstrations suffice, and the exponent ℓ\ell cannot be improved in general, even for classes learnable from O~(1/ε)\widetilde O(1/\varepsilon) full sets or bandit answers. For countable label spaces and ℓ≥2\ell \geq 2, our packed dimension, which asks for many disjoint groups of at most ℓ+1\ell+1 hypotheses with no common label, characterizes full-set learnability, and demonstrations still reduce to intersections. Agnostic learning from demonstrations, already for finite label spaces, is not determined by the dimensions of the intersection class that characterize realizable learning. Finally, we show that the uniform bound ℓ\ell on the number of correct labels is essential. Without this bound, it is impossible to characterize learnability by any dimension determined by finite subclasses.
Sep 21, 2026

Adversarially Robust PAC Learning with Optimal VC Rates

We study the problem of adversarially robust PAC learning. In this framework, the learner observes independent samples from an unknown distribution over X×{0,1}\mathcal{X} \times \{0,1\}, as in classical PAC learning. However, given a perturbation map U:X→2X\mathcal{U} : \mathcal{X} \to 2^{\mathcal{X}} known to the learner, the goal is to output, with high probability, a predictor that correctly classifies every perturbation z∈U(x)z \in \mathcal{U}(x) of most future examples (x,y)(x,y) drawn from the same underlying distribution. We determine the optimal U\mathcal{U}-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class H\mathcal{H} of VC⁡\operatorname{VC} dimension dd, we prove upper bounds of O(d/ε+log⁡(1/δ)/ε)\mathcal{O} \big( d/ε+ \log(1/δ)/ε\big) in the realizable setting and O(d/ε2+log⁡(1/δ)/ε2)\mathcal{O} \big( d/ε^2 + \log(1/δ)/ε^2 \big) in the agnostic setting, together with an optimal first-order refinement of the latter. These bounds match the corresponding lower bounds for classical PAC learning. Consequently, and perhaps surprisingly, adversarial robustness incurs no additional distribution-free statistical cost, uniformly over all perturbation maps. Our bounds improve exponentially on those of [Montasser, Hanneke, and Srebro; COLT '19]. On the technical side, we present short and elementary proofs based on a new algorithmic principle that we call binomial-bagging. We believe that binomial-bagging and its analysis may be of independent interest.