Concentration inequality for sum of iid random variables that involve KL distance 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}$? 
 A: 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 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)$. 
A: Too long for a comment so turning into an answer.
In order to exploit the structure in the marginal distribution over $X$ for better generalization, you need a "smart" learning algorithm that knows something about this structure. In your example of two Gaussians, the learner would estimate the means of $p_{X0}$ and $p_{X1}$, and the more well-separated these are, the better of a generalization guarantee one can give. The random variable $Z_i$ is just a Bernoulli random variable, however, and its empirical mean exploits nothing about the structure of the marginal distribution of $X$, and hence the latter cannot be used to obtain sharper concentration bounds.
