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

• 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? – Aryeh Kontorovich Nov 28 '17 at 17:06
• 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. – Jeff Nov 28 '17 at 17:22
• OK, let's consider another extreme: $p_{X0}=0$ everywhere. What kind of an improvement would you expect then? – Aryeh Kontorovich Nov 28 '17 at 17:26
• 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. – Jeff Nov 28 '17 at 17:49
• Indeed, there are results that show that classification becomes easier when the two classes are well-separated. But the inequality in your question is just a concentration result for a Bernoulli random variable, which is indifferent to the separation properties. – Aryeh Kontorovich Nov 28 '17 at 17:52

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 $$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}$$ 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 $$2(p-\tfrac12)=\mu_0(C_1)-\mu_1(C_1)+\mu_1(C_0)-\mu_0(C_0). \tag{1}$$ 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)$.
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.