A complete characterization of statistical query learning with applications to evolvability
From MaRDI portal
Publication:439989
DOI10.1016/j.jcss.2011.12.024zbMath1244.68045MaRDI QIDQ439989
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
68Q32: Computational learning theory
68T05: Learning and adaptive systems in artificial intelligence
Related Items
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
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Correlation clustering
- Unconditional lower bounds for learning intersections of halfspaces
- 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
- Toward efficient agnostic learning
- Boosting and hard-core set construction
- New lower bounds for statistical query learning
- A general dimension for query learning
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
- What Can We Learn Privately?
- Efficient noise-tolerant learning from statistical queries
- Agnostically Learning Halfspaces
- On Agnostic Learning of Parities, Monomials, and Halfspaces
- A Characterization of Strong Learnability in the Statistical Query Model
- Characterizing Statistical Query Learning: Simplified Notions and Proofs
- A theory of the learnable
- Cryptographic limitations on learning Boolean formulae and finite automata
- Learning Boolean formulas
- On the Fourier spectrum of monotone functions
- 10.1162/153244302760200669
- A Complete Characterization of Statistical Query Learning with Applications to Evolvability
- Evolvability
- Noise-tolerant learning, the parity problem, and the statistical query model
- A simple polynomial-time rescaling algorithm for solving linear programs
