ArXiv

An Optimal Agnostic PAC Algorithm

2026-08-06 · 17:57 UTC ·Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy ·0 min read

Authors: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy
Categories: cs.LG, cs.AI, cs.DS, math.ST
arXiv: https://arxiv.org/abs/2608.06363v1
PDF: https://arxiv.org/pdf/2608.06363v1

Brief

The authors construct an agnostic PAC algorithm for binary classes H⊂{−1,+1}^X of VC dimension d≥1 that attains the statistically optimal excess-risk rate. From n samples and any 0<δ≤1/2 their learner achieves a high-probability bound with a universal constant 7·10^8: L(ĥ)−L* = O(√(L*(d+log(1/δ))/n)+(d+log(1/δ))/n). This matches the 1996 lower bounds of Devroye, Györfi, and Lugosi, settling sample complexity up to constants. (ArXiv: authors Mathiasen, Qian, Zhivotovskiy; 18 pages; posted 2026-08-06.)

Why it matters

The authors construct an agnostic PAC learner for H⊂{−1,+1}^X with VC dimension d≥1 that, from n i.i.d. samples and for every 0<δ≤1/2, satisfies with probability ≥1−δ: L(ĥ) ≤ L* + 7·10^8(√(L*(d+log(1/δ))/n) + (d+log(1/δ))/n).

Key details

The bound matches the minimax lower bounds of Devroye, Györfi, and Lugosi (A Probabilistic Theory of Pattern Recognition, 1996), so the paper settles agnostic PAC sample complexity up to universal constants for every fixed L*.

Source evidence

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].

Comment: 18 pages