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.
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.
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) — more general patterns this builds on
-
Learnable Function Class is part of 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 (5) — routes to 5 parentless roots
- Learnable Function Class → Statistical Inference → Inductive Reasoning
- Learnable Function Class → Function (Mapping)
- Learnable Function Class → Statistical Inference → Uncertainty
- Learnable Function Class → Statistical Inference → Probability → Measure → Set and Membership
- Learnable Function Class → Statistical Inference → Probability → Measure → Aggregation → Micro Macro Linkage
Neighborhood in Abstraction Space¶
Learnable Function Class sits in a sparse region of the domain-specific corpus (69th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (1565 abstractions)
Nearest neighbors
- Statistical Model — 0.85
- Empirical Measure — 0.85
- Particle Filter — 0.85
- Quantification (machine learning) — 0.84
- Optimality criterion — 0.84
Computed from structural-signature embeddings · 2026-09-08