Agnostic PAC Learning

Classic PAC ("probably approximately correct") learning theory makes a convenient but unrealistic assumption: that some hypothesis in your model class gets the true labeling exactly right, with zero error. Real financial data never satisfies that — no linear model perfectly predicts stock returns, no finite decision tree perfectly predicts credit defaults, because the true relationship has genuine noise no model in any reasonable class could eliminate. Agnostic PAC learning is the more honest version of the theory: it drops the assumption that a perfect hypothesis exists, and instead promises only to get close to the best available hypothesis in your class, whatever error that best hypothesis is stuck with.

The analogy: hitting the best possible score, not a perfect one

In a game where the maximum possible score, even played flawlessly, is capped at 85 out of 100 because of an unavoidable element of luck built into the rules, it would be a strange promise to guarantee a player "you'll get 100." A realistic promise is "you'll get within a few points of 85, the true ceiling, with high probability, given enough practice rounds." Classic PAC learning implicitly promises the impossible "you'll hit 100"; agnostic PAC learning promises the honest, achievable "you'll get close to whatever the actual best-in-class score is" — even if that best score is a mediocre 85.

The formal statement

Let $R(h)$ be a hypothesis $h$'s true error, and $h^* = \arg\min_{h \in \mathcal{H}} R(h)$ the best hypothesis available in the class $\mathcal{H}$ — not necessarily error-free. A class is agnostically PAC-learnable if there's an algorithm that, given enough samples $n$, outputs a hypothesis $\hat{h}$ satisfying, with probability at least $1-\delta$:

$$R(\hat{h}) \le R(h^*) + \epsilon$$

In words: the returned hypothesis's true error is within $\epsilon$ of the best possible error achievable inside the class, not within $\epsilon$ of zero. If $\mathcal{H}$ has finite VC dimension $d$, this is achievable via Empirical Risk Minimization (just pick the hypothesis with lowest training error) with $n = O\!\left(\frac{d + \ln(1/\delta)}{\epsilon^2}\right)$ samples — the same sample complexity shape as the realizable case, just without the (false) promise that $R(h^*) = 0$.

Worked example 1: a class with an irreducible floor

A linear classifier is used on data where the true relationship is genuinely nonlinear, so the best linear separator, $h^*$, still misclassifies 12% of points no matter how it's tuned — $R(h^*) = 0.12$. With enough training data and $\epsilon = 0.03$, agnostic PAC learning guarantees, with high confidence, a learned classifier $\hat{h}$ with true error at most $0.12 + 0.03 = 0.15$. It does not, and cannot, guarantee anything near $0.03$ overall — the 12% floor is baked into the class's own limitation (linear boundaries on nonlinear data), not something more data can fix.

Worked example 2: more data narrows the gap to $h^*$, not to zero

Training the same linear classifier with $n=500$ examples might yield a learned hypothesis with true error $0.12 + 0.09 = 0.21$ (a loose $\epsilon = 0.09$ gap from limited data). Increasing to $n=50{,}000$ tightens that gap to roughly $\epsilon = 0.01$, giving true error close to $0.12 + 0.01 = 0.13$. More data reliably closes the gap to $h^*$ — but no amount of additional data pushes the learned model's error below $R(h^*) = 0.12$, because that floor is a property of the hypothesis class itself, not of how little data was used.

Watch the test error above flatten out at a non-zero floor as complexity or data increases past a point — that floor is exactly $R(h^*)$, the best any hypothesis in a fixed class could ever do.

What this means in practice

Every real quant model lives in the agnostic setting: markets are noisy enough that no finite model class contains a zero-error predictor, so "how much data before this model is reliable" is really asking "how much data closes the gap to the best this model class can do," not "how much data until error hits zero." A model plateauing at a disappointing error rate despite mountains of additional data is a strong signal the ceiling is coming from model misspecification (Underfitting and Model Misspecification), not from insufficient data — and the fix is a richer hypothesis class, not more rows.