Empirical Bernstein Inequalities for U-StatisticsReportar como inadecuado

Empirical Bernstein Inequalities for U-Statistics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

* Corresponding author 1 LATP - Laboratoire d-Analyse, Topologie, Probabilités 2 LIF - Laboratoire d-informatique Fondamentale de Marseille - UMR 6166 3 QARMA - éQuipe AppRentissage et MultimediA Marseille LIF - Laboratoire d-informatique Fondamentale de Marseille

Abstract : We present original empirical Bernstein inequalities for U-statistics with bounded symmetric kernels q. They are expressed with respect to empirical estimates of either the variance of q or the conditional variance that appears in the Bernstein-type inequality for U-statistics derived by Arcones. Our result subsumes other existing empirical Bernstein inequalities, as it reduces to them when U-statistics of order 1 are considered. In addition, it is based on a rather direct argument using two applications of the same non-empirical Bernstein inequality for U-statistics. We discuss potential applications of our new inequalities, especially in the realm of learning ranking-scoring functions. In the process, we exhibit an efficient pro- cedure to compute the variance estimates for the special case of bipartite ranking that rests on a sorting argument. We also argue that our results may provide test set bounds and particularly interesting empirical racing algorithms for the problem of online learning of scoring functions.

Keywords : Bernstein Inequality U-Statistics Ranking Empirical Inequalities

Autor: Thomas Peel - Sandrine Anthoine - Liva Ralaivola -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados