Computational Learning Theory

E822917

academic discipline area of theoretical computer science subfield of computer science subfield of machine learning

Computational Learning Theory is a branch of computer science and mathematics that studies the design and analysis of algorithms that can learn patterns or functions from data, often using formal models of learning and complexity.

Try in SPARQL Jump to: Surface forms Statements Referenced by

Observed surface forms (2)

Surface form	Occurrences
Vapnik–Chervonenkis theory	1
computational learning theory	1

Statements (76)

Predicate	Object
instanceOf	academic discipline ⓘ area of theoretical computer science ⓘ subfield of computer science ⓘ subfield of machine learning ⓘ
aimsTo	characterize when efficient learning is possible ⓘ provide guarantees on generalization error ⓘ understand tradeoffs between data, computation, and accuracy ⓘ
emergedIn	1980s ⓘ
fieldOfStudy	active learning ⓘ agnostic learning ⓘ boosting theory ⓘ computational complexity of learning ⓘ formal models of learning ⓘ generalization theory ⓘ learning algorithms ⓘ learning in the presence of noise ⓘ online learning ⓘ sample complexity ⓘ statistical learning theory ⓘ
hasInfluentialConference	ALT NERFINISHED ⓘ COLT NERFINISHED ⓘ NeurIPS NERFINISHED ⓘ
hasInfluentialJournal	Journal of Machine Learning Research NERFINISHED ⓘ Machine Learning journal NERFINISHED ⓘ
hasInfluentialResearcher	Leslie Valiant NERFINISHED ⓘ Nick Littlestone NERFINISHED ⓘ Noga Alon NERFINISHED ⓘ Robert Schapire NERFINISHED ⓘ Shai Ben-David NERFINISHED ⓘ Vladimir Vapnik NERFINISHED ⓘ Yoav Freund NERFINISHED ⓘ
hasKeyConcept	No Free Lunch theorem NERFINISHED ⓘ Occam’s razor in learning ⓘ PAC learning NERFINISHED ⓘ Rademacher complexity NERFINISHED ⓘ VC dimension NERFINISHED ⓘ compression schemes for learning ⓘ concept class ⓘ empirical risk minimization ⓘ hypothesis class ⓘ margin bounds ⓘ mistake bounds ⓘ online regret bounds ⓘ risk minimization ⓘ sample complexity bounds ⓘ structural risk minimization ⓘ uniform convergence ⓘ
hasKeyModel	PAC model NERFINISHED ⓘ agnostic PAC model ⓘ distribution-free learning model ⓘ mistake-bound model ⓘ online learning model ⓘ query learning model ⓘ statistical query model ⓘ
hasKeyProblem	learnability of Boolean functions ⓘ learnability of linear separators ⓘ learnability of neural networks ⓘ learning DNF formulas ⓘ learning decision trees ⓘ learning under distributional assumptions ⓘ learning with membership queries ⓘ
relatedTo	artificial intelligence ⓘ machine learning ⓘ statistics ⓘ theoretical computer science ⓘ
studies	analysis of learning algorithms ⓘ design of learning algorithms ⓘ learnability of function classes ⓘ limits of efficient learning ⓘ tradeoff between data and computation in learning ⓘ
usesConcept	combinatorics ⓘ complexity theory ⓘ information theory ⓘ optimization ⓘ probability theory ⓘ statistics ⓘ

Referenced by (3)

Full triples — surface form annotated when it differs from this entity's canonical label.

Theoretical Computer Science → hasSubfield → Computational Learning Theory ⓘ

Probably Approximately Correct learning (PAC learning) → field → Computational Learning Theory ⓘ

subject surface form: Probably Approximately Correct learning

this entity surface form: computational learning theory

Vladimir Vapnik → knownFor → Computational Learning Theory ⓘ

this entity surface form: Vapnik–Chervonenkis theory