An Optimal Agnostic PAC Algorithm

Overview§

This paper resolves a long-standing question in agnostic PAC learning: it provides a single algorithm whose excess risk is optimal not only with respect to the VC dimension $d$ and sample size $n$, but also with respect to the irreducible noise level $L^*$. The guarantee is, for any $0 < \delta \leq 1/2$:

$$ L(\hat h) \leq L^ + 7 \cdot 10^8 \left( \sqrt{\frac{L^(d+\log(1/\delta))}{n}} + \frac{d+\log(1/\delta)}{n} \right). $$

This exactly matches the lower bounds by Devroye et al., up to universal constants.

Algorithm and Key Ideas§

The optimal bound requires the learner to interpolate between two regimes. When $L^$ is large, the extra risk is of order $\sqrt{d/n}$, the classical minimax rate. When $L^$ is small, the rate collapses to roughly $\sqrt{L^ d/n} + d/n$, which is much faster. A naive ERM on the whole class $H$ always pays the $\sqrt{d/n}$ price because it ignores $L^$.

The proposed algorithm uses a localized search: it first estimates the noise level on a subsample, then restricts attention to hypotheses whose empirical error on that subsample is within a small radius of the observed best. This restriction can only remove bad hypotheses when $L^*$ is small, thereby decreasing the effective complexity. Concretely, the algorithm:

1. Splits the data into several folds.
2. Computes an initial empirical risk minimizer on one fold to anchor the search.
3. Builds a 'plausible set' of hypotheses with empirical error below a data-dependent threshold.
4. Runs constrained ERM over that set on a separate fold.
5. Uses a final holdout fold to choose among the candidate hypotheses.

The threshold is selected via a 'ghost sample' argument that accounts for both the estimation error of the anchor and the complexity of the class. This yields a self-bounding inequality that depends on $L^*$.

Implementation Sketch§

A simplified Python/PyTorch-style pseudocode of the algorithm is below. In practice, the exact thresholds and sample splits follow the paper's constants.

def optimal_agnostic_learner(X, y, H, d, delta, n):
    n1 = n // 3
    n2 = n // 3
    n3 = n - n1 - n2
    S1, S2, S3 = split(X, y, [n1, n2, n3])
    
    g0 = empirical_risk_minimizer(H, S1)
    r0 = empirical_risk(g0, S1)
    threshold = r0 + 10 * sqrt((d + log(1/delta)) / n1)
    
    # Localized hypothesis class
    H_cand = [h for h in H if empirical_risk(h, S1) <= threshold]
    
    g1 = empirical_risk_minimizer(H_cand, S2)
    g_best = argmin([empirical_risk(g, S3) for g in [g0, g1]])
    return g_best

This pseudo-code captures the essential structure; the real algorithm uses a multi-level split to handle the adaptivity without knowing $L^*$ in advance.

Conclusion§

The paper is a purely theoretical contribution: it settles the sample complexity of agnostic PAC learning for VC classes. The result is important for practitioners because it establishes that an adaptive learner can strictly outperform ERM at low noise, and it gives a template for constructing 'noise-adaptive' methods in other settings.