Learnable Function Class¶

A hypothesis class for which some learner can attain a uniform finite-sample population-risk guarantee under a declared statistical learning model.

Version: v4 · 2026-09-19 · History
Domain-specific #: 2170
Domain group: Formal Sciences
Origin domain: Experimental Design & Statistics
Subdomains: Statistical Learning Theory, Learnability Theory → Experimental Design & Statistics

Core Idea¶

A learnable function class is a collection of candidate prediction rules for which some learner can extract a population-risk guarantee from finite random samples under a declared statistical learning model. Learnability is therefore not an intrinsic property of a bare set of functions. It belongs to a package: example and output spaces, a hypothesis class, a loss, an admissible family of data-generating distributions or targets, a sampling rule, an algorithm and its allowed output range, and quantified tolerances for success.

How would you explain it like I'm…

No faithful explanation at this level. A child-level version collapses into 'see enough examples and you'll find the right answer'. That loses the real promise: with high probability, the result is approximately as good as the best rule in the chosen set. The promise must also hold uniformly across allowed data sources, relative to a declared setup.

Box of Learnable Guessing Rules

Imagine a box full of guessing rules, like 'say yes if the number is bigger than 7'. The box is learnable if some learning method, after seeing enough random examples, can almost always pick a rule that is nearly as good as the best rule in the box. It doesn't have to be perfect, and it doesn't have to work every single time, just with high chance. The same number of examples has to be enough no matter which allowed kind of data you are given. Whether a box counts as learnable also depends on the rules of the game, like how mistakes are scored.

PAC-Learnable Hypothesis Class

A learnable function class is a set of candidate prediction rules (hypotheses) for which some learning method can turn a finite random sample into a guarantee about future performance. In the agnostic PAC version, you fix an accuracy ε and a confidence δ. The class is learnable if some learner, given enough i.i.d. examples, outputs a rule whose true error is within ε of the best rule in the class, with probability at least 1−δ. The same sample-size bound must work for every allowed data distribution. Learnability is not a property of the set alone: it depends on the loss, the allowed distributions, the sampling, and the learner. Infinite classes can still be learnable. For example, threshold rules on the number line are learnable because their capacity to fit arbitrary labelings is limited.

A learnable function class is a hypothesis class H for which some learner can turn finite i.i.d. samples into a guarantee on population risk, within a declared statistical learning model. The model specifies the example and label spaces, the hypothesis class, a loss, the admissible family of distributions, the sampling rule, the learner and what it may output, and the tolerances. In agnostic PAC learning with a loss bounded in [0,1], H is learnable if there exist a learner A and a sample-complexity function m_H(ε, δ) such that for every admissible distribution D and every sample of size at least m_H(ε, δ), with probability at least 1 − δ over the sample, A's population risk is at most the best population risk in H plus ε. The probability is over the sample (and any learner randomness), the benchmark is the best hypothesis inside H, and the sample bound must hold uniformly over all admissible distributions. Realizable PAC learning assumes some target in H labels the data, so the benchmark error is zero. Proper learners must return a member of H; improper learners may return something outside it. In standard binary classification, finite VC dimension, uniform convergence, ERM learnability, and PAC learnability are equivalent (the fundamental theorem of statistical learning), but in more general learning problems learnability need not be characterized by uniform convergence.

Scope of Application¶

Binary classification. PAC and agnostic PAC learning are most transparent under zero–one loss. VC dimension characterizes distribution-free learnability under standard regularity assumptions, and finite-class bounds show how logarithmic hypothesis-count dependence arises.

Multiclass and structured prediction. Hypotheses return more than two labels or structured outputs. Learnability persists as the class-level question, while the capacity measure and loss-specific theorem change.

Regression and real-valued prediction. Squared, absolute, Lipschitz, or bounded losses require their own range, tail, and capacity assumptions. Pseudo-dimension, fat-shattering dimension, covering numbers, or Rademacher complexity may replace binary VC dimension.

Clarity¶

The abstraction turns “can this be learned?” into a typed question. It forces the analyst to name what varies (distribution or target), what is observed (a sample under a declared protocol), what competes (the hypotheses), what counts as error (the loss), what the learner may output, what success compares against, and how much evidence purchases a requested accuracy and confidence.

Manages Complexity¶

A hypothesis class can contain infinitely many functions and confront infinitely many possible data distributions. Learnability compresses that apparent twofold infinity into a sample-complexity function. Rather than test every future sample and every distribution, one proves a capacity bound or an impossibility result that controls them together.

Abstract Reasoning¶

Finite-class prediction. In the realizable finite binary setting, any consistent ERM has error at most \(\epsilon\) with confidence \(1-\delta\) once \(m\) is on the order of \((\ln|H|+\ln(1/\delta))/\epsilon\). With bounded loss in \([0,1]\), Hoeffding concentration plus a union bound yields uniform convergence for finite \(H\); ERM then has excess population risk at most \(\epsilon\) once \(m\) is on the order of \((\log |H|+\log(1/\delta))/\epsilon^2\) in the agnostic regime.

Knowledge Transfer¶

The full abstraction transfers literally across classification, regression, ranking, kernel learning, and other statistical learning problems. In every case one identifies a candidate rule class, a sample-generating protocol, a loss, a learner, a population comparator, accuracy/confidence parameters, and a complexity witness. The formulas vary, but the question remains: does finite evidence uniformly suffice for the declared problem family?

Relationships to Other Abstractions¶

Current abstraction Learnable Function Class Domain-specific

Parents (2) — outgoing typed relations

Learnable Function Class includes Function (Mapping) Prime

prime:function_mapping — proposed strict part relation. Hypotheses are the constituent input-to-output mappings collected in \(H\); the child adds statistical and class-level obligations.
Learnable Function Class presupposes Statistical Inference Prime

prime:statistical_inference — proposed strict presupposition. Learnability evaluates when finite samples suffice for population-risk selection, but the class property is not itself a subtype of an inference episode.

Hierarchy paths (4) — routes to 4 parentless roots

Learnable Function Class → presupposes Statistical Inference → is a kind of Inductive Reasoning

Show alternative paths (3)

Neighborhood in Abstraction Space¶

Learnable Function Class sits in a moderately populated region (53^rd percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Statistical Learning & Model Failure Modes (41 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25