New lower bounds for statistical query learning

DOI10.1007/3-540-45435-7_16MaRDI QIDQ3046709zbMATH OpenFDO

Authors Ke Yang

Publication date 12 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2375/23750229.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational learning theory (68Q32)

Recommendations

• New lower bounds for statistical query learning
• A Characterization of Strong Learnability in the Statistical Query Model
• Lower bounds on learning random structures with statistical queries
• General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
• Characterizing statistical query learning: simplified notions and proofs

Cited in

(10)

• General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
• New lower bounds for statistical query learning
• General lower bounds on the query complexity within the exact learning model
• On using extended statistical queries to avoid membership queries
• A Characterization of Strong Learnability in the Statistical Query Model
• Characterizing statistical query learning: simplified notions and proofs
• A complete characterization of statistical query learning with applications to evolvability
• On learning correlated Boolean functions using statistical queries (extended abstract)
• Dealing with range anxiety in mean estimation via statistical queries
• Lower bounds on learning random structures with statistical queries

This page was built for publication: New lower bounds for statistical query learning

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