Strong minimax lower bounds for learning

DOI10.1023/A:1007454427662zbMATH Open0892.68083OpenAlexW3017128687MaRDI QIDQ1383192FDOQ1383192

Authors: András Antos, Gábor Lugosi 

Publication date: 2 April 1998

Published in: Machine Learning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1007454427662

Recommendations

• A general lower bound on the number of examples needed for learning
• Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model
• Lower bound methods and separation results for on-line learning models
• Publication:4952633
• General bounds on the number of examples needed for learning probabilistic concepts

zbMATH Keywords

Vapnik-Chervonenkis dimensionPAC learning

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Cited In (11)

• Minimax Bounds for Active Learning
• Lower bounds for the rate of convergence in nonparametric pattern recognition
• Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model
• Optimal third root asymptotic bounds in the statistical estimation of thresholds
• Strong convergence of least squares learning to rational expectations
• Ten More Years of Error Rate Research
• The true sample complexity of active learning
• Lower bounds on the rate of convergence of nonparametric regression estimates
• Obtaining minimax lower bounds: a review
• Refined error bounds for several learning algorithms
• Theory of Classification: a Survey of Some Recent Advances

This page was built for publication: Strong minimax lower bounds for learning

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