New lower bounds for statistical query learning

DOI10.1016/J.JCSS.2004.10.003MaRDI QIDQ1780448zbMATH OpenOpenAlexFDO

Authors Ke Yang

Publication date 13 June 2005

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2004.10.003

zbMATH Keywords

KL-divergencePAC learningSingular-value decompositionLower-bound statistical query

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2089365
• 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
• scientific article; zbMATH DE number 2080649

Cites work

• scientific article; zbMATH DE number 3701942 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 2080649 (Why is no real title available?)
• scientific article; zbMATH DE number 3241743 (Why is no real title available?)
• A theory of the learnable
• Efficient noise-tolerant learning from statistical queries
• Matrix Analysis
• On Information and Sufficiency
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis

Cited in

(10)

• A Characterization of Strong Learnability in the Statistical Query Model
• scientific article; zbMATH DE number 2080649 (Why is no real title available?)
• General lower bounds on the query complexity within the exact learning model
• A complete characterization of statistical query learning with applications to evolvability
• General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
• Characterizing statistical query learning: simplified notions and proofs
• Polynomial‐time universality and limitations of deep learning
• Lower bounds on learning random structures with statistical queries
• Unconditional lower bounds for learning intersections of halfspaces
• scientific article; zbMATH DE number 2089365 (Why is no real title available?)

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 Q1780448)