Characterizing Statistical Query Learning: Simplified Notions and Proofs

DOI10.1007/978-3-642-04414-4_18zbMath1262.68072MaRDI QIDQ3648752

Balázs Szörényi

Publication date: 1 December 2009

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

Full work available at URL: https://doi.org/10.1007/978-3-642-04414-4_18

Mathematics Subject Classification ID

62G08: Nonparametric regression and quantile regression

62H30: Classification and discrimination; cluster analysis (statistical aspects)

68Q32: Computational learning theory

Related Items

Polynomial‐time universality and limitations of deep learning, A complete characterization of statistical query learning with applications to evolvability, On the Evolution of Monotone Conjunctions: Drilling for Best Approximations

Cites Work

• Unnamed Item
• The complexity of learning concept classes with polynomial general dimension
• General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
• New lower bounds for statistical query learning
• Learning by distances
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Efficient noise-tolerant learning from statistical queries
• A Characterization of Strong Learnability in the Statistical Query Model
• 10.1162/153244302760200669
• A Complete Characterization of Statistical Query Learning with Applications to Evolvability