Conider $X \in \mathbb{R}^d$ and $Y \in \{0,1\}$, and a joint distribution $p\_{XY}(x,y)$, and a set of $N$ i.i.d. samples $\{(X\_i,Y\_i)\}\_{i=1}^{N}$. Define $p\_{X0} = p\_{XY}(x,0)$ and $p\_{X1} = p\_{XY}(x,1)$. Define deterministic function $f: \mathbb{R}^d \mapsto \{0,1\}$. Define binary variable $Z\_i = \mathbb{1}\_{\{Y\_i \neq f(X\_i)\}}$, where $\mathbb{1}\_{\{\cdot\}}$ is an indicator function. Consider metric  

$$\Pr \left(\frac{1}{N}\sum\_{i=1}^{N} Z\_i \geq \mathbb{E} \left[Z\right] + \varepsilon \right) \:.$$ 
Concentration inequalities bounds it based on only $N$ and $\varepsilon$. Is there any upper bound that involves the KL distance or total variation of $p\_{X0}$ and $p\_{X1}$? 



Concentration inequality for sum of iid random variables that involve KL distance
Consider the sub-probability measures $\mu\_0$ and $\mu\_1$ defined by the conditions $\mu\_0(A):=P(Y=0,X\in A)$ and $\mu\_1(A):=P(Y=1,X\in A)$ for Borel sets $A\subseteq\mathbb R$, so that $\mu:=\mu\_0+\mu\_1$ is the probability distribution of $X$. Let 
\begin{equation\*}
 p:=p\_f:=P(Y\ne f(X))=EZ. 
\end{equation\*}
Then, by Chebyshev's inequality, 
\begin{equation\*}
 P\Big(\frac1n\sum\_{i=1}^n Z\_i \ge EZ + \varepsilon\Big)\le\frac{p(1-p)}{n\varepsilon^2}
 =\frac1{n\varepsilon^2}\,[\tfrac14-(p-\tfrac12)^2]. 
\end{equation\*}
So, it is enough to give a lower bound on $|p-\tfrac12|$ in terms of the total variation norm $\|\mu\_0-\mu\_1\|$. 


First here, it is easy to see that, without any restrictions on the function $f$ (and assuming such a mild condition as the probability measure $\mu$ being non-atomic), the only lower bound on $|p-\tfrac12|$ is the trivial one, $0$. Indeed, let 
\begin{equation}
 C\_0:=C\_{0,f}:=\{x\in\mathbb{R}^d\colon f(x)=0\},\quad 
 C\_1:=C\_{1,f}:=\{x\in\mathbb{R}^d\colon f(x)=1\}. \tag{0}
\end{equation}
Then $p=\mu\_0(C\_1)+\mu\_1(C\_0)$ and $\mu\_0(C\_0)+\mu\_0(C\_1)+\mu\_1(C\_0)+\mu\_1(C\_1)=1$, whence 
\begin{equation}
2(p-\tfrac12)=\mu\_0(C\_1)-\mu\_1(C\_1)+\mu\_1(C\_0)-\mu\_0(C\_0). \tag{1}
\end{equation}
Letting $f(x)=1$ for all $x$, we have $C\_0=\emptyset$, $C\_1=\mathbb{R}^d$, and hence 
$2(p-\tfrac12)=\mu\_0(\mathbb{R}^d)-\mu\_1(\mathbb{R}^d)=:\delta$. Vice versa, letting $f(x)=0$ for all $x$, we have $C\_1=\emptyset$, $C\_0=\mathbb{R}^d$, and hence 
$2(p-\tfrac12)=\mu\_1(\mathbb{R}^d)-\mu\_0(\mathbb{R}^d)=-\delta$. So, if $\mu$ is indeed non-atomic, then for some (bad enough classification rule) $f\colon \mathbb{R}^d \mapsto \{0,1\}$ we will have $2(p-\tfrac12)=\frac12\,\delta+\frac12\,(-\delta)=0$, so that $|p-\tfrac12|=0$. 


Now suppose that the classification rule $f\colon \mathbb{R}^d \mapsto \{0,1\}$ is chosen optimally, as follows:
\begin{equation\*}
 f(x)=f\_\*(x):=I\{g\_1(x)>g\_0(x)\}
\end{equation\*}
for all $x\in \mathbb{R}^d$, where $I$ is the indicator function and for each $i=1,2$ the function $g\_i$ is the density of $\mu\_i$ with respect to (say) the measure $\mu=\mu\_0+\mu\_1$. Then, by (1) and (0), 
\begin{equation\*}
2(p\_{f\_\*}-\tfrac12)=-|\mu\_0(C\_1)-\mu\_1(C\_1)|-|\mu\_1(C\_0)-\mu\_0(C\_0)|=-\|\mu\_0-\mu\_1\|,
\end{equation\*}
so that
\begin{equation\*}
2|p\_{f\_\*}-\tfrac12|=\|\mu\_0-\mu\_1\|. 
\end{equation\*}
(On the other hand, again by (1), 
\begin{equation\*}
2|p\_f-\tfrac12|\le|\mu\_0(C\_1)-\mu\_1(C\_1)|+|\mu\_1(C\_0)-\mu\_0(C\_0)|\le\|\mu\_0-\mu\_1\|
\end{equation\*}
for all $f$, which shows that the choice $f=f\_\*$ is indeed optimal in the sense that it maximizes $|p\_f-\tfrac12|$; moreover and more importantly, this choice of $f$ is also optimal in the sense that it minimizes the misclassification probability $p\_f$.) 
Thus, for $f=f\_\*$ we have indeed an upper bound in terms of the total variation norm $\|\mu\_0-\mu\_1\|$:  

\begin{equation\*}
 P\Big(\frac1n\sum\_{i=1}^n Z\_i \ge EZ + \varepsilon\Big)\le\frac{1-\|\mu\_0-\mu\_1\|^2}{4n\varepsilon^2}. 
\end{equation\*}
This bound can be vastly improved, again for $f=f\_\*$. E.g., bound (2.2) in [Hoeffding 1963](http://www.jstor.org/stable/2282952) yields  

\begin{equation\*}
 P\Big(\frac1n\sum\_{i=1}^n Z\_i \ge EZ + \varepsilon\Big)\le
 \exp\{-n\varepsilon^2 h(\|\mu\_0-\mu\_1\|)\}, 
\end{equation\*}
where $h(u):=\frac1u\,\ln\frac{1+u}{1-u}$, which is increasing from $2$ to $\infty$ in $u\in(0,1)$. 


