General lower bounds on the query complexity within the exact learning model

DOI10.1016/S0166-218X(99)00223-1MaRDI QIDQ1841883zbMATH OpenOpenAlexFDO

Authors Norbert Klasner, Hans Ulrich Simon

Publication date 20 March 2001

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00223-1

zbMATH Keywords

exact learning model

Mathematics Subject Classification ID

Computational learning theory (68Q32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• A new abstract combinatorial dimension for exact learning via queries
• New Computational Paradigms
• Complexity theoretic hardness results for query learning
• Learning via finitely many queries
• Oracles and queries that are sufficient for exact learning
• Lower bounds on learning random structures with statistical queries
• New lower bounds for statistical query learning
• scientific article; zbMATH DE number 2089365
• scientific article; zbMATH DE number 1301786
• scientific article; zbMATH DE number 1804113

Cites work

• scientific article; zbMATH DE number 67631 (Why is no real title available?)
• A combinatorial problem; stability and order for models and theories in infinitary languages
• General lower bounds on the query complexity within the exact learning model
• Learning from examples with unspecified attribute values.
• Lower bound methods and separation results for on-line learning models
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the density of families of sets
• Queries and concept learning
• Simulating access to hidden information while learning

Cited in

(10)

• Lower bound methods and separation results for on-line learning models
• How many queries are needed to learn one bit of information?
• On the Complexity of Learning Minimum Time-Bounded Turing Machines
• Algorithmic Learning Theory
• General lower bounds on the query complexity within the exact learning model
• General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
• A Lower Bound for Agnostically Learning Disjunctions
• A general lower bound on the number of examples needed for learning
• Structural analysis of polynomial-time query learnability
• scientific article; zbMATH DE number 1804094 (Why is no real title available?)

This page was built for publication: General lower bounds on the query complexity within the exact learning model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1841883)