# Hoeffding's inequality for conditional probability

I am currently reading the paper Functional Classification in Hilbert Spaces by Biau, Bunea and Wegkamp, and there is one step in the proof of Theorem 1 that is not clear to me. I give below a simplified version of the steps of the proof that I do not understand, but the original calculations can be found in Section V-B, page 7 of the original paper.

To briefly introduce the notations, we are dealing with a binary classification problem. The dataset is made of $$n$$ i.i.d. pairs $$(X_i,Y_i) \in \mathcal X \times \left\{0,1\right\}$$ and we denote by $$\hat\phi_n$$ the classifier which belongs to a certain hypothesis class and is a function of the data. Lastly, $$L$$ and $$\hat L$$ are respectively the true and empirical losses of the classifier $$\hat\phi_n$$, i.e. $$L:= \mathbb P\left(\hat\phi_n(X)\ne Y\ |\ (X_i,Y_i),1\le i\le n\right) \quad \text{ and }\quad \hat L :=\frac{1}{n}\sum_{i=1}^n\mathbf 1\left\{\hat\phi_n(X_i)\ne Y_i\right\}$$ The inequality I'm having trouble with is the following : \begin{align} \mathbb P\left(L-\hat L\ge \varepsilon\right) &= \mathbb E \mathbb P\left(L-\hat L\ge \varepsilon\ |\ (X_i,Y_i),1\le i\le n\right) \\ &\le \exp\left(-2n\varepsilon^2\right) \end{align} The first line is clearly true by the law of total expectation, and I understand that the second line is a direct application of Hoeffding's inequality since, conditional on the data, $$n\hat L$$ is a sum of i.i.d Bernoulli variables of parameter $$L$$. My issue is that I don't know how to formalize Hoeffding's inequality in this case where the probability is conditional on a sigma algebra, since it then becomes a random variable. Should I maybe show that Hoeffding's inequality holds for the conditional probability conditional on any event in $$\sigma\left((X_i,Y_i),1\le i \le n\right)$$ ?

In summary, my question is the following : How to formally derive Hoeffding's inequality for conditional probability with respect to a sigma algebra ?

Many thanks in advance for the help.

Update : First off, I noticed I got confused with the notations and $$\hat\phi_n$$ is, in fact, dependent on the data (in the paper at least), I fixed the mistake.

Regarding my question, I attempted to prove Hoeffding's inequality for conditional probability by following the proof of the original inequality and adapting it. So let $$X_i$$ be independent r.v.'s respectively bounded in $$[a_i,b_i]$$, $$S_n = \sum_{i=1}^n X_i$$ and $$\mathcal F$$ be a sigma-algebra :
By conditional Markov inequality, we have \begin{align} \mathbb P\left(S_n-\mathbb E S_n \ge \varepsilon \ \vert\ \mathcal F\right)&\le e^{-s\varepsilon}\mathbb E \left[e^{s(S_n-\mathbb E S_n)} \ \vert\ \mathcal F\right]\\ &=e^{-s\varepsilon}\mathbb E \left[\exp\left(s\left(\sum_{i=1}^n X_i - \mathbb E X_i\right)\right) \ \vert\ \mathcal F\right] \\ &= e^{-s\varepsilon} \prod_{i=1}^n\mathbb E \left[e^{s\left( X_i - \mathbb E X_i\right)} \ \vert\ \mathcal F\right] \text{ (by independence)}\\ \end{align} To conclude, I then have to prove/apply a conditional version of Hoeffding's lemma, but sadly that doesn't seem to work since $$\mathbb E\left[X_i - \mathbb E[X_i]\ \vert \ \mathcal F\right]\ne 0$$ in general. I however believe it's still possible to upper bound this conditional expectation and get a similar, but weaker version of the lemma for conditional probability, but that would yield a different result (I haven't done the calculation yet).

Am I on the right track ?

• Am I correct that you are using $L$ to refer to $L(k,d)$, as defined in the beginning of section V-B? I ask because their definition of $L(k,d)$ is also conditional on the data $(X_i,Y_i)_{i=1}^n$. They say $$L(k,d)=\Bbb P\{\phi_{\ell,k,d}({\bf X}^{(d)}\neq Y)\mid ({\bf X}_i,Y_i),1\le i\le n\}$$ I think this is an important detail you have left out. Jan 24, 2022 at 21:17
• @MikeEarnest yes you are correct, I initially left it out thinking it didn't make much difference but I added it in now ! Jan 25, 2022 at 9:06

After looking at the problem again, I figured out what was wrong in my "conditional Hoeffding inequality" proof attempt : In the paper's setting, $$L$$ is not equal to $$\mathbb E[\hat L]$$ but rather $$L = \mathbb E[\hat L\color{red}{\ \vert \mathcal F}]$$ (by definition of conditional probability).
Therefore, the "true" conditional Hoeffding inequality I want to prove is in fact (with the same notations) : $$\mathbb P\left(S_n-\mathbb E [S_n\color{red}{\ \vert \mathcal F}] \ge \varepsilon \ \vert \mathcal F\right)\le \exp\left(\frac{-2\varepsilon}{\sum_{i=1}^n(b_i-a_i)^2}\right)$$ If I proceed similarly as in my initial attempt, I have \begin{align}\mathbb P\left(S_n-\mathbb E [S_n\color{red}{\ \vert \mathcal F}] \ge \varepsilon \ \vert \mathcal F\right)&\le e^{-s\varepsilon} \prod_{i=1}^n\mathbb E \left[e^{s\left( X_i - \mathbb E [X_i\color{red}{\ \vert \mathcal F}]\right)}\ \vert \mathcal F\right] \end{align} \tag1 And all I need to conclude is, once again, a conditional version of Hoeffding's lemma. But thankfully $$\mathbb E\left[X_i - \mathbb E[X_i\ \vert \mathcal F]\ \vert \ \mathcal F\right]=0$$ and by monotonicity of $$\mathbb E[\cdot\ \vert \mathcal F]$$ and convexity of $$\exp$$, one can follow the steps of the original proof to conclude that $$\mathbb E \left[e^{s\left( X_i - \mathbb E [X_i\color{red}{\ \vert \mathcal F}]\right)}\ \vert \mathcal F\right] \le \exp\left(\frac{s^2(b_i-a_i)^2}{8}\right)\ \ \forall\ 1\le i\le n$$
Finally, as in the original proof, plugging this inequality in $$(1)$$ and letting $$s =\frac{4\varepsilon}{\sum_{i=1}^n(b_i-a_i)^2}$$ gives the desired result.
• Don’t you need the $X_i$ to be conditionally independent given $\mathcal{F}$ instead of being independent? Aug 17, 2022 at 12:56