Timezone: »

Empirical Bernstein Inequalities for U-Statistics
Thomas Peel · Sandrine Anthoine · Liva Ralaivola

Mon Dec 06 12:00 AM -- 12:00 AM (PST) @ None #None

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 [2]. 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 procedure 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.

Author Information

Thomas Peel (Aix-Marseille Université)
Sandrine Anthoine (Université Aix-Marseille I - CNRS)
Liva Ralaivola (LIF, IUF, Aix-Marseille University, CNRS)

More from the Same Authors