Agnostic Learning

Learning without believing the truth sits in your class. Agnostic guarantees compete with the best available function instead of the Bayes truth, paying only approximation plus estimation error.

The truth sits outside the class while ERM lands within 0.12 of the best-in-class predictor on 2000 samples

Why Does This Exist?

Realisable theory assumes the truth $f^*$ lives in the class $F$ : a true hyperplane, a true tree, a true network. Real data never cooperates. The truth is richer than any tractable class, labels carry noise no function captures, and the best available predictor still errs. Guarantees that assume realisability go vacuous the moment the model is misspecified, which is always.

Agnostic learning drops the assumption. It competes with the best in class: excess risk $P(\hat{f}) - \inf_{f \in F} P(f)$ (gap to the class optimum, not to zero) decays like $\sqrt{d/n}$ for VC classes regardless of where truth sits. Approximation error $\inf_F P - P^*$ (how far the class stands from Bayes) is accepted as irreducible; estimation controls the rest. This is the honest accounting behind every ERM guarantee quoted on real data.

Prerequisite in one paragraph. You need empirical risk minimisation (pick the training-best function) and the Bayes error $P^*$ (the irreducible floor). Excess risk splits into approximation plus estimation. Background is in sampling distributions and hypothesis testing.

Think of It Like This

Best restaurant in town versus best in the world

A food critic who demands the world's best meal starves in most towns. A smart critic reviews the best in town against its peers: the gap to local best is the review, while the gap from local best to world best is disclosed as travel, not cooking failure.

Agnostic bounds review the local best. Estimation error is the kitchen gap between your pick and the town's best; approximation error is the travel gap to the world truth. Realisable theory pretends the town holds the world champion and blames the kitchen for the travel gap.

Where the analogy stops: restaurant gaps are tasted directly while approximation error is unobservable without knowing truth. The bound controls only the kitchen gap; the travel gap needs domain knowledge.

How It Actually Works

Fix class $F$ with VC dimension $d$ and any distribution $D$ . ERM $\hat{f}$ satisfies $P(\hat{f}) - \inf_F P \lesssim \sqrt{(d + \log(1/\delta))/n}$ with high chance, where $P$ is population risk and $n$ sample size. No realisability, no margin, no noise condition. Total error adds approximation: $P(\hat{f}) - P^* = (\inf_F P - P^*) + (P(\hat{f}) - \inf_F P)$ .

Worked example

Take $d = 50$ , $n = 2000$ , $\delta = 0.05$ . Then $(d + \ln 20)/n = (50 + 3.0)/2000 = 0.0265$ , root $\approx 0.163$ , refined to $0.12$ with standard constants in the diagram. So ERM lands within $0.12$ of the best of its $50$ -dimensional class on any distribution, even when truth is a depth- $10$ tree outside it.

Suppose the class best errs at $0.20$ while Bayes errs at $0.12$ : approximation $0.08$ , estimation $0.12$ , total below $0.32$ . Doubling to $n = 8000$ halves estimation to $0.06$ but leaves approximation $0.08$ untouched. At that point buy a richer class, not more data: the diagram truth sits outside precisely to show the floor data cannot fix.

Watch Out For

Comparing agnostic bounds across different classes

An estimation bound of $0.12$ on linear models and $0.20$ on trees does not crown linear: their approximation errors differ. The tree may sit $0.15$ closer to truth and win overall. Ranking classes by estimation alone repeats the realisability mistake in new clothes.

Fix: always add a validation estimate of total error. Bounds rank estimation; data ranks totals.

Expecting fast rates without further assumptions

Agnostic ERM gets $1/\sqrt{n}$ in general. Fast $1/n$ needs Bernstein or margin conditions that misspecification often breaks. Demanding $0.03$ from $2{,}000$ samples agnostically and blaming the optimiser misses that the rate itself forbids it.

Fix: quote $1/\sqrt{n}$ agnostically. Upgrade only with verified low-noise structure.

The Quick Version

Agnostic learning competes with the class best, not Bayes truth, so misspecification is allowed.
ERM excess risk decays as $\sqrt{d/n}$ on any distribution; at 50 dimensions and 2000 samples within 0.12.
Total error splits into approximation (class vs truth) plus estimation (pick vs class best).
More data shrinks estimation only; approximation needs a richer class.
Never rank classes by estimation bounds alone, and expect slow rates without extra structure.