New lower bounds for statistical query learning

DOI10.1016/j.jcss.2004.10.003zbMath1105.68053OpenAlexW2006412101MaRDI QIDQ1780448

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

PAC learningSingular-value decompositionKL-divergenceLower-bound statistical query

Mathematics Subject Classification ID

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

Related Items (4)

Polynomial‐time universality and limitations of deep learning ⋮ A complete characterization of statistical query learning with applications to evolvability ⋮ Unconditional lower bounds for learning intersections of halfspaces ⋮ Characterizing Statistical Query Learning: Simplified Notions and Proofs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Matrix Analysis
• A theory of the learnable
• Efficient noise-tolerant learning from statistical queries
• On Information and Sufficiency

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