An Optimal Agnostic PAC Algorithm

Markus Engelund Mathiasen; Jian Qian; Nikita Zhivotovskiy

cs.LGAug 6, 2026

An Optimal Agnostic PAC Algorithm

Authors: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Organizations: Department of Computer Science, Aarhus University · Division of Artificial Intelligence and Data Science, School of Computing and Data Science, The University of Hong Kong · Department of Statistics, University of California, Berkeley

Abstract

Let $H\subseteq\{-1,+1\}^X$ be a class of finite VC dimension $d\ge1$ . Writing $L$ for the binary risk and $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 $n$ , for every $0<δ\le 1/2$ , with probability at least $1-δ$ ,

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^*$ , matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

Explore similar work

Adversarially Robust PAC Learning with Optimal VC Rates
Sep 21, 2026Steve Hanneke, Amirreza ShaeiriOptimal Sample Complexity Distributional Learning
The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences
Aug 5, 2026Elad Aigner-Horev, Daniel Rosenberg, Roi WeissOptimal Sample Complexity Distributional Learning
Bagging Robustly Learns VC Classes with Linear Sample Complexity
Aug 13, 2026Omar MontasserEmpirical Risk Minimization Decision Trees

Sep 21, 2026 · stat.MLJ/K move · Enter open · S save

Adversarially Robust PAC Learning with Optimal VC Rates

Steve Hanneke, Amirreza Shaeiri

We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distribution over

\mathcal{X} \times \{0,1\}

, as in classical PAC learning. However, given a perturbation map

\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 \emph{every} perturbation

z \in \mathcal{U}(x)

of most future examples

(x,y)

drawn from the same underlying distribution. We determine the \emph{optimal}

\mathcal{U}

-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class

\mathcal{H}

\operatorname{VC}

dimension

d

, we prove upper bounds of

\mathcal{O} \big( d/ε+ \log(1/δ)/ε\big)

in the realizable setting and

\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 \emph{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 \emph{binomial-bagging}. We believe that binomial-bagging and its analysis may be of independent interest.

Optimal Sample Complexity Distributional Learning

Open paper Ask about it PDF

Abstract

Explore similar work

Adversarially Robust PAC Learning with Optimal VC Rates

The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences

Bagging Robustly Learns VC Classes with Linear Sample Complexity