agnostic learning

The original PAC model assumed the truth lives inside your hypothesis class — a comforting but unrealistic premise. Agnostic learning drops it. It admits the world may be noisy, the labels may not be a deterministic function of the inputs at all, and your class may simply be wrong. The honest goal becomes relative: do nearly as well as the best hypothesis your class can offer, whatever that best is, rather than chasing a perfection that may not exist.

Fix an arbitrary joint distribution over inputs and labels, and let the best achievable error within the class — the approximation error — be the infimum of true risk over the class. An algorithm agnostically PAC-learns the class if, with probability one minus delta, it outputs a hypothesis whose true risk is at most that best-in-class error plus epsilon, using a sample size polynomial in the accuracy and confidence. The total error thus splits into approximation error, the class's inherent limitation that no data can remove, and estimation error, the gap from finite samples that epsilon controls. This is the formal home of the bias–variance decomposition.

Agnostic learning is the realistic setting for almost all of machine learning, since no finite class captures reality exactly. Its sample complexity is again governed by capacity such as VC dimension or Rademacher complexity, but the rate degrades: the estimation error scales like the slow one-over-root-m rather than the realizable one-over-m, because you must estimate a nonzero optimal risk. Computationally, agnostic learning is often far harder than realizable learning — even agnostically learning simple classes like halfspaces is intractable under standard assumptions.