PAC learning: realizable and agnostic guarantees
Research context
postgraduate concept · established · As of 2026-10-10
PAC learning bounds population risk with probability at least 1−delta from iid samples.
Key knowledge
PAC learning bounds population risk with probability at least 1−delta from iid samples. In realizable binary classification it targets risk at most epsilon when the class contains a zero-error rule. Agnostic learning instead targets excess risk at most epsilon above the best rule in the class. Neither definition says the world is in the model or permits replacing iid samples with arbitrary dependent deployment data.
Conditions and scope
- Hypothesis class, zero-one loss, sample law, epsilon/delta and realizable versus agnostic setting are declared.
- Computationally efficient learning is an additional requirement beyond statistical sample complexity.
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-pac-realizable-agnostic
- Revision
- research.1
- Structured reference record
- Postgraduate & research reference