AI Glossary / AI and machine learning / Advanced
Learnable function class
Definition
A learnable function class is a set of candidate functions for which a learning procedure can achieve a specified generalization guarantee from data under stated assumptions. The precise meaning depends on the learning framework, loss function and allowed data distributions.
What it means
A function class might contain all threshold rules on a line, all linear classifiers in a fixed dimension or a family of regression functions. Learnability asks whether data can support reliable selection from that class, not whether one model happened to fit one dataset.
In probably approximately correct, or PAC, learning, a guarantee connects sample size with an accuracy tolerance and a failure probability. In an agnostic setting, the learner may aim to approach the best achievable risk within the class rather than assume a perfect target function exists there.
This is a mathematical property with carefully stated quantifiers. It is not a promise that a business dataset is sufficient, that computation is cheap or that the chosen inputs contain the needed information. Statistical learnability and computational efficiency are related but distinct questions.
How it works
The framework specifies inputs, outputs, a class of functions and a loss measuring prediction error. It also specifies how samples are generated, commonly assuming independent observations from one distribution.
A learnability statement asks whether an algorithm can use enough samples to obtain the required guarantee uniformly over the permitted distributions. For standard binary classification under suitable regularity assumptions, finite VC dimension characterizes distribution-free PAC learnability. Other settings use different complexity measures and may have different relationships between learnability and uniform convergence.
The guarantee's target matters. Realizable learning assumes the class contains a function consistent with the target setting. Agnostic learning allows unavoidable error and compares with the best function in the class. A practical application must check whether its data process resembles the assumptions, especially when observations are dependent, labels are noisy or conditions change over time.
Three practical examples
1. A theory course compares threshold functions with a much richer family to examine how hypothesis-class complexity affects sample requirements.
2. A researcher proves that a proposed class can be learned under a defined loss and distributional setting.
3. A modeling team uses learning-theory concepts to explain why allowing arbitrary rules can fit training data without supporting reliable predictions on new cases.
Think of it this way
Think of choosing a rule from a catalog. A manageable catalog lets observations rule out many poor choices, while an unrestricted catalog can invent a story for almost any sample. The limit is that learnability is defined mathematically; catalog size alone is not the only relevant measure, especially for infinite classes.
Worked example
Consider an illustrative realizable binary-classification PAC guarantee with accuracy tolerance epsilon = 0.05 and failure probability delta = 0.01. It says that, once the theorem's sample requirement and assumptions are met, the learning procedure returns a hypothesis with error at most 5% with probability at least 99% over the draw of the training sample.
The 99% refers to the procedure's success across possible training samples. It is not a 99% confidence score attached to every individual prediction. The 5% is the specified risk tolerance, not necessarily the observed training error.
This example explains the roles of epsilon and delta without asserting a sample size, because that depends on the class, algorithm and learning setting.
Illustrative case study
A fictional analytics team hears that its model family is learnable and assumes a small historical dataset is therefore enough. Review shows that the available records come from one unusual operating period and that the planned deployment covers different conditions.
The team separates the theoretical question from the data question. It documents the class and guarantee, then evaluates coverage of the intended population and collects more representative observations.
The case illustrates that learnability establishes the possibility of a guarantee under assumptions. It does not certify a particular dataset or remove the need to examine how examples were collected.
Common misconceptions and mistakes
- Learnable means easy to compute. A statistical guarantee may not provide an efficient algorithm.
- An infinite class cannot be learnable. Infinite classes can have controlled complexity, such as finite VC dimension.
- Fitting the training data proves learnability. Training fit alone says little about distribution-wide generalization.
Business use
This concept is most useful for understanding the limits of modeling claims and the role of complexity. Business readers should treat it as a theoretical foundation rather than a ready-made deployment certificate.
When a technical proposal cites learnability, ask which class, loss and data assumptions are involved. Distinguish an existence theorem from a practical algorithm and a sample bound from actual dataset quality. Use empirical evaluation to assess the deployed task while recognizing that a good benchmark result and a mathematical guarantee answer different questions.
People also ask
Can an infinite function class be learnable?
Yes. Complexity can be controlled even when the class contains infinitely many functions.
Does learnability mean zero error is possible?
No. In agnostic learning, the goal can be to approach the best risk within the class.
Does one theorem cover every kind of learning?
No. Binary classification, real-valued prediction, online learning and other settings require their own definitions and results.
Check your understanding
Why is “this class is learnable” incomplete without stating the learning framework and assumptions?
Answer: The guarantee depends on the loss, permitted distributions, sampling process and target notion of success; changing them can change the result.
Related terms
- PAC learning
- Generalization
- VC dimension
- Sample complexity
- Empirical risk minimization
- hypothesis class
- agnostic learning
Learn next
Read PAC learning and VC dimension. Write a guarantee in plain language, identifying the error tolerance, failure probability, target class and assumptions about the data.
More in AI and machine learning
- Leabra - Leabra is a computational neural-modeling framework that combines error-driven and associative learning with biologically motivated activation and...
- Leaf - A leaf is an end node of a decision tree: the terminal box where a case finally lands, carrying the tree's prediction for every case that arrives there.
- Learnable evolution model - The learnable evolution model, or LEM, is an evolutionary optimization approach that uses machine learning to generate promising new candidate solutions.
- Learning automaton - A learning automaton is an adaptive decision mechanism that selects actions, receives feedback from an environment and updates how it chooses future actions.
- Learning rate - Learning rate is the step-size dial of iterative training: how large an adjustment the model makes to its parameters at each update, trading speed of...
- Learning to rank - Learning to rank is the use of machine learning to order items according to relevance, preference or another defined criterion.
Sources
MIT, Learnability and VC Dimension, authored course material: https://gradml.mit.edu/supervised/learnability_and_vc/. Alon and colleagues, A Theory of PAC Learnability of Partial Concept Classes: https://arxiv.org/abs/2107.08444. The numerical tolerance example and analytics-team scenario are invented and do not assert a theorem-specific sample bound.
Previous: Learnable evolution model Next: Learned operator