Near-Optimal Sample Complexity of Deterministic Agnostic PAC Learning
Ben-David et al.
With deterministic labels, every class of VC dimension \(d\) and diameter \(K\) is learnable from \(\widetilde{O}(K^{1/3} d^{2/3}/\varepsilon)\) examples, and the bound is tight up to logarithms.
Source published · In the Daily Brief of 13 November 2026
Filed under Learning theory
The paper studies agnostic PAC learning when examples are labelled by an arbitrary deterministic function that need not belong to the concept class \(C\). The setting captures misspecification without random label noise and sits between the realisable and fully agnostic cases.
For a class with VC dimension \(d\) and finite diameter \(K\), earlier work improved the classical agnostic rate \(O(d/\varepsilon^2)\) to \(\widetilde{O}(K/\varepsilon)\) but left a wide gap to the lower bounds. The authors prove that every such class can be learned with \[ \widetilde{O}\left(\frac{K^{1/3} d^{2/3}}{\varepsilon}\right) \] examples, and construct classes for which this is tight up to logarithmic factors.
The upper bounds come from memorisation-based algorithms that exploit the deterministic labels. In the online version of the problem, the minimax regret is again partly governed by the diameter of the class.