Concentration Inequalities for the Missing Mass and for Histogram Rule Error

Part of Advances in Neural Information Processing Systems 15 (NIPS 2002)

Bibtex Metadata Paper


Luis E. Ortiz, David McAllester


This paper gives distribution-free concentration inequalities for the miss- ing mass and the error rate of histogram rules. Negative association meth- ods can be used to reduce these concentration problems to concentration questions about independent sums. Although the sums are independent, they are highly heterogeneous. Such highly heterogeneous independent sums cannot be analyzed using standard concentration inequalities such as Hoeffding’s inequality, the Angluin-Valiant bound, Bernstein’s in- equality, Bennett’s inequality, or McDiarmid’s theorem.