An Optimal Agnostic PAC Algorithm

In statistical learning theory, the agnostic PAC (Probably Approximately Correct) model aims to bound the excess risk of a learner relative to the best possible hypothesis in a class $H$ with VC dimension $d$. While optimal rates were known for the realizable case (where the best risk $L^* = 0$) and the standard agnostic case (where $L^$ is bounded away from zero), the intermediate rates—and whether a single algorithm could achieve the optimal bound for all $L^$—remained an open problem.

The authors develop a new learner based on the one-inclusion graph algorithm, a technique originally used for realizable learning. They introduce a novel class-dependent edge isoperimetric inequality on the Boolean cube, which allows them to control the induced edge counts in the one-inclusion graph using projected Rademacher widths. By combining this with a suffix averaging technique—which adapts a reverse and forward martingale analysis—they construct a randomized predictor that achieves the optimal minimax excess risk. Finally, they derandomize this predictor to obtain a deterministic learner that does not require prior knowledge of $L^*$ or the confidence parameter $\delta$.

The paper proves that for any hypothesis class $H$ with VC dimension $d$, there exists a learner such that for any distribution, sample size $n$, and confidence $\delta$, the excess risk is bounded by $O(\sqrt{L^(d + \log(1/\delta))/n} + (d + \log(1/\delta))/n)$. This result settles the sample complexity of agnostic PAC learning, confirming that the minimax rate is achieved by a single algorithm across all values of $L^$.