A complete characterization of statistical query learning with applications to evolvability

DOI10.1016/J.JCSS.2011.12.024MaRDI QIDQ439989zbMATHOpenAlexFDO

Authors Vitaly Feldman

Publication date 17 August 2012

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.2011.12.024

zbMATH Keywords

evolvabilityagnostic learningcomplexity of learningstatistical query

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational learning theory (68Q32)

Recommendations

• A Characterization of Strong Learnability in the Statistical Query Model
• Characterizing statistical query learning: simplified notions and proofs
• scientific article; zbMATH DE number 2089365
• New lower bounds for statistical query learning
• General bounds on statistical query learning and PAC learning with noise via hypothesis boosting

Cites work

• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 7051290 (Why is no real title available?)
• scientific article; zbMATH DE number 5485575 (Why is no real title available?)
• 10.1162/153244302760200669
• A Characterization of Strong Learnability in the Statistical Query Model
• A Complete Characterization of Statistical Query Learning with Applications to Evolvability
• A general dimension for query learning
• A polynomial-time algorithm for learning noisy linear threshold functions
• A simple polynomial-time rescaling algorithm for solving linear programs
• A theory of the learnable
• Agnostically Learning Halfspaces
• Boosting and hard-core set construction
• Characterizing statistical query learning: simplified notions and proofs
• Correlation clustering
• Cryptographic limitations on learning Boolean formulae and finite automata
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Efficient noise-tolerant learning from statistical queries
• Evolvability
• General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
• Learning Boolean formulas
• New lower bounds for statistical query learning
• Noise-tolerant learning, the parity problem, and the statistical query model
• On agnostic learning of parities, monomials, and halfspaces
• On the Fourier spectrum of monotone functions
• Specification and simulation of statistical query algorithms for efficiency and noise tolerance
• Toward efficient agnostic learning
• Unconditional lower bounds for learning intersections of halfspaces
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• What can we learn privately?

Cited in

(4)

• A Characterization of Strong Learnability in the Statistical Query Model
• On the complexity of random satisfiability problems with planted solutions
• Statistical active learning algorithms for noise tolerance and differential privacy
• On the evolution of monotone conjunctions: drilling for best approximations

Describes a project that uses

Uses Software

• SuLQ

This page was built for publication: A complete characterization of statistical query learning with applications to evolvability

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