A complete characterization of statistical query learning with applications to evolvability

DOI10.1016/J.JCSS.2011.12.024zbMATH Open1244.68045OpenAlexW2546502841MaRDI QIDQ439989FDOQ439989

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

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

zbMATH Keywords

evolvabilityagnostic learningcomplexity of learningstatistical query

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

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

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)