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}$?

1$\begingroup$ Suppose $p_{X0}=p_{X1}$. Presumably, this is the "best" case, in which both the total variation and the KL are zero. What sort of an improved bound would you expect in this case? $\endgroup$– Aryeh KontorovichNov 28, 2017 at 17:06

1$\begingroup$ In that very special case (not sure if we can call it "best"), perhaps nothing. I am actually interested in $p_{X0} \neq p_{X1}$ or even $p_{X0} \gg p_{X1}$, in which the bound may be improved. $\endgroup$– JeffNov 28, 2017 at 17:22

1$\begingroup$ OK, let's consider another extreme: $p_{X0}=0$ everywhere. What kind of an improvement would you expect then? $\endgroup$– Aryeh KontorovichNov 28, 2017 at 17:26

1$\begingroup$ Let's consider this toy example. $p_{X0} \sim \mathcal{N}(0,\Sigma)$ and $p_{X1} \sim \mathcal{N}(\mu,\Sigma)$ be multivariate normal distributed for some constant vector $\mu$ and covariance matrix $\Sigma$. Now, I would expect to concentrate faster when we increase $\ \mu \_2^2$, like when we increase "distance" of two distributions. $\endgroup$– JeffNov 28, 2017 at 17:49

1$\begingroup$ Indeed, there are results that show that classification becomes easier when the two classes are wellseparated. But the inequality in your question is just a concentration result for a Bernoulli random variable, which is indifferent to the separation properties. $\endgroup$– Aryeh KontorovichNov 28, 2017 at 17:52
2 Answers
Consider the subprobability 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(1p)}{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 nonatomic), 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 nonatomic, 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*}
2p_{f_*}\tfrac12=\\mu_0\mu_1\.
\end{equation*}
(On the other hand, again by (1),
\begin{equation*}
2p_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}{1u}$, which is increasing from $2$ to $\infty$ in $u\in(0,1)$.
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 wellseparated 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.