A Theory of the Learnable.

Valiant, L. G. (1984). A Theory of the Learnable. Communications of the ACM, 27(11), 1134-1142.

Type

Journal article

Intellectual base

Primary research

Year

1984

DOI

10.1145/1968.1972

Link

https://doi.org/10.1145/1968.1972

Cited from

philosophy, systems_cybernetics

Cited by

3 citations across 3 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Inductive Reasoning
  • Contemporary machine-learning theory, rooted in Valiant's PAC framework

    This sourceValiant theory of the learnable PAC framework computational learning.

• Intrinsic Ceiling vs Input
  • the sample-complexity and model-capacity framework from statistical learning (Bayes error, PAC bounds) was adopted in econometrics, psychological-measurement theory, and clinical-trial design;

    This sourceIntroduces the PAC-learning framework relating model capacity (achievable-error ceiling) to sample complexity (the input to approach it), adopted across statistics and related fields.

Domain-specific

• Sample complexity
  • Valiant's PAC formulation made this relation explicit by treating learnability as the existence of an algorithm whose sample and computational requirements are polynomial in the relevant parameters.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:237444770c9f · see in the full table