Learning theory Papers

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.

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.