A sharp lower bound for agnostic learning with sample compression schemes

MaRDI QIDQ7034386zbMATH OpenFDO

Authors Steve Hanneke, Aryeh Kontorovich

Publication date 31 January 2025

Full work available at URL https://proceedings.mlr.press/v98/hanneke19b.html

zbMATH Keywords

agnostic learningcompression schemeslower boundsuniform convergence

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Learning and adaptive systems in artificial intelligence (68T05)

Cites work

• scientific article; zbMATH DE number 3795074 (Why is no real title available?)
• scientific article; zbMATH DE number 3795075 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• Learnability and the Vapnik-Chervonenkis dimension
• Neural Network Learning
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• PAC-Bayesian compression bounds on the prediction error of learning algorithms for classification
• Predicting \(\{ 0,1\}\)-functions on randomly drawn points
• Sample Compression Schemes for VC Classes
• Sharper bounds for Gaussian and empirical processes
• Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
• The optimal sample complexity of PAC learning
• Theory of statistics

Cited in

(1)

• Stable sample compression schemes: new applications and an optimal SVM margin bound

This page was built for publication: A sharp lower bound for agnostic learning with sample compression schemes

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