# 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? 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? 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. 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 \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)$.
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.