Refined error bounds for several learning algorithms

MaRDI QIDQ2834450zbMATH OpenFDO

Authors Steve Hanneke

Publication date 22 November 2016

Published in Journal of Machine Learning Research (JMLR) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.07146, http://jmlr.csail.mit.edu/papers/v17/15-655.html

zbMATH Keywords

active learningminimax analysisPAC learningsample complexitystatistical learning theory

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: This article studies the achievable guarantees on the error rates of certain learning algorithms, with particular focus on refining logarithmic factors. Many of the results are based on a general technique for obtaining bounds on the error rates of sample-consistent classifiers with monotonic error regions, in the realizable case. We prove bounds of this type expressed in terms of either the VC dimension or the sample compression size. This general technique also enables us to derive several new bounds on the error rates of general sample-consistent learning algorithms, as well as refined bounds on the label complexity of the CAL active learning algorithm. Additionally, we establish a simple necessary and sufficient condition for the existence of a distribution-free bound on the error rates of all sample-consistent learning rules, converging at a rate inversely proportional to the sample size. We also study learning in the presence of classification noise, deriving a new excess error rate guarantee for general VC classes under Tsybakov's noise condition, and establishing a simple and general necessary and sufficient condition for the minimax excess risk under bounded noise to converge at a rate inversely proportional to the sample size.

Recommendations

• scientific article; zbMATH DE number 1445318
• Strong minimax lower bounds for learning
• Minimax analysis of active learning
• Rates of convergence in active learning
• Improved bounds on the sample complexity of learning

Cited in

(7)

• Estimated cost for solving generalized learning with errors problem via embedding techniques
• Learning parities in the mistake-bound model
• Estimation of the hardness of the learning with errors problem with a restricted number of samples
• New Algorithms for Learning in Presence of Errors
• Erratum (“Fast and Robust Learning by Reinforcement Signals: Explorations in the Insect Brain” by Ramón Huerta and Thomas Nowotny, Neural Computation, August 2009, Vol. 21, No. 8: 2123–2151)
• The relationship between agnostic selective classification, active learning and the disagreement coefficient
• Stable sample compression schemes: new applications and an optimal SVM margin bound

This page was built for publication: Refined error bounds for several learning algorithms

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