Adaptive Sampling Under Low Noise Conditions

Abstract : We survey recent results on efficient margin-based algorithms for adaptive sampling in binary classification tasks. Using the so-called Mammen-Tsybakov low noise condition to parametrize the distribution of covariates, and assuming linear label noise, we state bounds on the convergence rate of the adaptive sampler to the Bayes risk. These bounds show that, excluding logarithmic factors, the average risk converges to the Bayes risk at rate $N^{-(1+a)(2+a)/2(3+a)}$ where N denotes the number of queried labels, and a is the nonnegative exponent in the low noise condition. For all $a > \sqrt3-1$ this convergence rate is asymptotically faster than the rate $N^{-(1+a)/(2+a)}$ achieved by the fully supervised version of the base adaptive sampler, which queries all labels. Moreover, for a growing to infinity (hard margin condition) the gap between the semi- and fully-supervised rates becomes exponential.
Type de document :
Communication dans un congrès
41èmes Journées de Statistique, SFdS, Bordeaux, 2009, Bordeaux, France, France. 2009
Domaine :

Littérature citée [11 références]

https://hal.inria.fr/inria-00386698
Contributeur : Conférence Jds2009 <>
Soumis le : vendredi 22 mai 2009 - 09:13:40
Dernière modification le : lundi 25 mai 2009 - 07:01:59
Document(s) archivé(s) le : jeudi 10 juin 2010 - 23:38:13

Fichier

p128.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

• HAL Id : inria-00386698, version 1

Citation

Nicolò Cesa-Bianchi. Adaptive Sampling Under Low Noise Conditions. 41èmes Journées de Statistique, SFdS, Bordeaux, 2009, Bordeaux, France, France. 2009. 〈inria-00386698〉

Métriques

Consultations de la notice

70

Téléchargements de fichiers