Bretagnolle–Huber inequality

In information theory, the Bretagnolle–Huber inequality bounds the total variation distance between two probability distributions and by a concave and bounded function of the Kullback–Leibler divergence . The bound can be viewed as an alternative to the well-known Pinsker's inequality: when is large (larger than 2 for instance.[1]), Pinsker's inequality is vacuous, while Bretagnolle–Huber remains bounded and hence non-vacuous. It is used in statistics and machine learning to prove information-theoretic lower bounds relying on hypothesis testing[2]  (Bretagnolle–Huber–Carol Inequality is a variation of Concentration inequality for multinomially distributed random variables which bounds the total variation distance.)

Formal statement

edit

Preliminary definitions

edit

Let   and   be two probability distributions on a measurable space  . Recall that the total variation between   and   is defined by

 

The Kullback-Leibler divergence is defined as follows:

 

In the above, the notation   stands for absolute continuity of   with respect to  , and   stands for the Radon–Nikodym derivative of   with respect to  .

General statement

edit

The Bretagnolle–Huber inequality says:

 

Alternative version

edit

The following version is directly implied by the bound above but some authors[2] prefer stating it this way. Let   be any event. Then

 

where   is the complement of  .

Indeed, by definition of the total variation, for any  ,

 

Rearranging, we obtain the claimed lower bound on  .

Proof

edit

We prove the main statement following the ideas in Tsybakov's book (Lemma 2.6, page 89),[3] which differ from the original proof[4] (see C.Canonne's note [1] for a modernized retranscription of their argument).

The proof is in two steps:

1. Prove using Cauchy–Schwarz that the total variation is related to the Bhattacharyya coefficient (right-hand side of the inequality):

 

2. Prove by a clever application of Jensen’s inequality that

 
  • Step 1:
First notice that
 
To see this, denote   and without loss of generality, assume that   such that  . Then we can rewrite
 
And then adding and removing   we obtain both identities.
Then
 
because  
  • Step 2:
We write   and apply Jensen's inequality:
 
Combining the results of steps 1 and 2 leads to the claimed bound on the total variation.

Examples of applications

edit

Sample complexity of biased coin tosses

edit

Source:[1]

The question is How many coin tosses do I need to distinguish a fair coin from a biased one?

Assume you have 2 coins, a fair coin (Bernoulli distributed with mean  ) and an  -biased coin ( ). Then, in order to identify the biased coin with probability at least   (for some  ), at least

 

In order to obtain this lower bound we impose that the total variation distance between two sequences of   samples is at least  . This is because the total variation upper bounds the probability of under- or over-estimating the coins' means. Denote   and   the respective joint distributions of the   coin tosses for each coin, then

We have

 

The result is obtained by rearranging the terms.

Information-theoretic lower bound for k-armed bandit games

edit

In multi-armed bandit, a lower bound on the minimax regret of any bandit algorithm can be proved using Bretagnolle–Huber and its consequence on hypothesis testing (see Chapter 15 of Bandit Algorithms[2]).

History

edit

The result was first proved in 1979 by Jean Bretagnolle and Catherine Huber, and published in the proceedings of the Strasbourg Probability Seminar.[4] Alexandre Tsybakov's book[3] features an early re-publication of the inequality and its attribution to Bretagnolle and Huber, which is presented as an early and less general version of Assouad's lemma (see notes 2.8). A constant improvement on Bretagnolle–Huber was proved in 2014 as a consequence of an extension of Fano's Inequality.[5]

See also

edit

References

edit
  1. ^ a b c Canonne, Clément (2022). "A short note on an inequality between KL and TV". arXiv:2202.07198 [math.PR].
  2. ^ a b c Lattimore, Tor; Szepesvari, Csaba (2020). Bandit Algorithms (PDF). Cambridge University Press. Retrieved 18 August 2022.
  3. ^ a b Tsybakov, Alexandre B. (2010). Introduction to nonparametric estimation. Springer Series in Statistics. Springer. doi:10.1007/b13794. ISBN 978-1-4419-2709-5. OCLC 757859245. S2CID 42933599.
  4. ^ a b Bretagnolle, J.; Huber, C. (1978), "Estimation des densités : Risque minimax", Séminaire de Probabilités XII, Lecture notes in Mathematics, vol. 649, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 342–363, doi:10.1007/bfb0064610, ISBN 978-3-540-08761-8, S2CID 122597694, retrieved 2022-08-20
  5. ^ Gerchinovitz, Sébastien; Ménard, Pierre; Stoltz, Gilles (2020-05-01). "Fano's Inequality for Random Variables". Statistical Science. 35 (2). arXiv:1702.05985. doi:10.1214/19-sts716. ISSN 0883-4237. S2CID 15808752.