A complete characterization of statistical query learning with applications to evolvability
From MaRDI portal
Publication:439989
DOI10.1016/j.jcss.2011.12.024zbMath1244.68045OpenAlexW2546502841MaRDI 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
Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)
Related Items (3)
On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ On the Evolution of Monotone Conjunctions: Drilling for Best Approximations ⋮ Statistical active learning algorithms for noise tolerance and differential privacy
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
This page was built for publication: A complete characterization of statistical query learning with applications to evolvability
