Fano's inequality for random variables

Sebastien Gerchinovitz (1) , Pierre Ménard (1) , Gilles Stoltz (2)

1 IMT - Institut de Mathématiques de Toulouse UMR5219
2 GREGH - Groupement de Recherche et d'Etudes en Gestion à HEC

We extend Fano's inequality, which controls the average probability of (disjoint) events in terms of the average of some Kullback-Leibler divergences, to work with arbitrary [0,1]-valued random variables. Our simple two-step methodology is general enough to cover the case of an arbitrary (possibly continuously infinite) family of distributions as well as [0,1]-valued random variables not necessarily summing up to 1. Several novel applications are provided, in which the consideration of random variables is particularly handy. The most important applications deal with the problem of Bayesian posterior concentration (minimax or distribution-dependent) rates and with a lower bound on the regret in non-stochastic sequential learning. We also improve in passing some earlier fundamental results: in particular, we provide a simple and enlightening proof of the refined Pinsker's inequality of Ordentlich and Weinberger and derive a sharper Bretagnolle-Huber inequality.

Domaines: Théorie [stat.TH]; Théorie de l'information [cs.IT]

Sebastien Gerchinovitz, Pierre Ménard, Gilles Stoltz. Fano's inequality for random variables. 2017. ⟨hal-01470862v1⟩