VC dimension and distribution-free learnability
Research context
postgraduate concept · established · As of 2026-10-10
VC dimension is the largest size of a point set on which a binary hypothesis class realizes every labeling.
Key knowledge
VC dimension is the largest size of a point set on which a binary hypothesis class realizes every labeling. Finite VC dimension characterizes distribution-free PAC learnability of binary classes under the standard measurability assumptions. Representative agnostic uniform-convergence bounds scale as (d log(1/epsilon)+log(1/delta))/epsilon², up to universal constants; realizability can improve epsilon dependence. This is a class/loss/sample-model theorem, not a generic guarantee for every neural network task.
Conditions and scope
- Binary zero-one classification and the relevant measurability assumptions are specified; d is the class's VC dimension.
- This displayed order is a sufficient representative bound, not the sharp minimax rate or a numerical constant recommendation.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Author checked this English statement, displayed equation where present and stated hypotheses against these source locations: Chapters 2–6 PAC/VC, 11 validation, 13 regularization, 14 stochastic gradient and 23 PCA. The check is bounded to the recorded claims; no complete proof reconstruction, software proof replay or universal literature completeness is claimed.
2026-10-10 · Author source-body/statement/equation/domain check, with graph associations scoped individually. Separate independent content/source/inventory review is required before branch closure.
Entry details
Permanent link to this entry ↗- Record identity
- research-info-vc-sample-complexity
- Revision
- research.1
- Structured reference record
- Postgraduate & research reference