Some connections between learning and optimization

DOI10.1016/j.dam.2004.06.005zbMath1075.68630OpenAlexW1977837160MaRDI QIDQ1885804

Martin Anthony

Publication date: 12 November 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.06.005

zbMATH Keywords

OptimizationLearningComputational complexity of learning

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Combinatorial optimization (90C27) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• Equivalence of models for polynomial learnability
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• The densest hemisphere problem
• Sharper bounds for Gaussian and empirical processes
• Toward efficient agnostic learning
• Hardness results for neural network approximation problems
• A general lower bound on the number of examples needed for learning
• Robust trainability of single neurons
• General bounds on the number of examples needed for learning probabilistic concepts
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• Computational limitations on learning from examples
• Cryptographic limitations on learning Boolean formulae and finite automata
• Neural Network Learning
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: Some connections between learning and optimization