Estimation of Rényi Entropy and Mutual Information Based on Generalized Nearest-Neighbor Graphs

Introduction

In a naïve approach to Rényi entropy and mutual information estimation, one could use the so called “plug-in” estimates. These are based on the obvious idea that since entropy and mutual information are determined solely by the density $f$ (and its marginals), it suffices to first estimate the density using one’s favorite density estimate which is then “plugged-in” into the formulas defining entropy and mutual information. The density is, however, a nuisance parameter which we do not want to estimate. Density estimators have tunable parameters and we may need cross validation to achieve good performance.

The entropy estimation algorithm considered here is direct—it does not build on density estimators. It is based on $k$-nearest-neighbor (NN) graphs with a fixed $k$. A variant of these estimators, where each sample point is connected to its $k$-th nearest neighbor only, were recently studied by Goria et al. (2005) for Shannon entropy estimation (i.e. the special case $\alpha=1$) and Leonenko et al. (2008) for Rényi $\alpha$-entropy estimation. They proved the weak consistency of their estimators under certain conditions. However, their proofs contain some errors, and it is not obvious how to fix them. Namely, Leonenko et al. (2008) apply the generalized Helly-Bray theorem, while Goria et al. (2005) apply the inverse Fatou lemma under conditions when these theorems do not hold. This latter error originates from the article of Kozachenko and Leonenko (1987), and this mistake can also be found in Wang et al. (2009b).

The first main contribution of this paper is to give a correct proof of consistency of these estimators. Employing a very different proof techniques than the papers mentioned above, we show that these estimators are, in fact, strongly consistent provided that the unknown density $f$ has bounded support and $\alpha\in(0,1)$. At the same time, we allow for more general nearest-neighbor graphs, wherein as opposed to connecting each point only to its $k$-th nearest neighbor, we allow each point to be connected to an arbitrary subset of its $k$ nearest neighbors. Besides adding generality, our numerical experiments seem to suggest that connecting each sample point to all its $k$ nearest neighbors improves the rate of convergence of the estimator.

The second major contribution of our paper is that we prove a finite-sample high-probability bound on the error (i.e. the rate of convergence) of our estimator provided that $f$ is Lipschitz. According to the best of our knowledge, this is the very first result that gives a rate for the estimation of Rényi entropy. The closest to our result in this respect is the work by Tsybakov and van der Meulen (1996) who proved the root-$n$ consistency of an estimator of the Shannon entropy and only in one dimension.

The third contribution is a strongly consistent estimator of Rényi mutual information that is based on NN graphs and the empirical copula transformation (Dedecker et al., 2007). This result is proved for $d\geq 3$ Our result for Rényi entropy estimation holds for $d=1$ and $d=2$, too. and $\alpha\in(1/2,1)$. This builds upon and extends the previous work of Póczos et al. (2010) where instead of NN graphs, the minimum spanning tree (MST) and the shortest tour through the sample (i.e. the traveling salesman problem, TSP) were used, but it was only conjectured that NN graphs can be applied as well.

There are several advantages of using $k$-NN graph over MST and TSP (besides the obvious conceptual simplicity of $k$-NN): On a serial computer the $k$-NN graph can be computed somewhat faster than MST and much faster than the TSP tour. Furthermore, in contrast to MST and TSP, computation of $k$-NN can be easily parallelized. Secondly, for different values of $\alpha$, MST and TSP need to be recomputed since the distance between two points is the $p$-th power of their Euclidean distance where $p=d(1-\alpha)$. However, the $k$-NN graph does not change for different values of $p$, since $p$-th power is a monotone transformation, and hence the estimates for multiple values of $\alpha$ can be calculated without the extra penalty incurred by the recomputation of the graph. This can be advantageous e.g. in intrinsic dimension estimators of manifolds (Costa and Hero, 2003), where $p$ is a free parameter, and thus one can calculate the estimates efficiently for a few different parameter values.

The fourth major contribution is a proof of a finite-sample high-probability error bound (i.e. the rate of convergence) for our mutual information estimator which holds under the assumption that the copula of $f$ is Lipschitz. According to the best of our knowledge, this is the first result that gives a rate for the estimation of Rényi mutual information.

The toolkit for proving our results derives from the deep literature of Euclidean functionals, see, (Steele, 1997; Yukich, 1998). In particular, our strong consistency result uses a theorem due to Redmond and Yukich (1996) that essentially states that any quasi-additive power-weighted Euclidean functional can be used as a strongly consistent estimator of Rényi entropy (see also Hero and Michel 1999). We also make use of a result due to Koo and Lee (2007), who proved a rate of convergence result that holds under more stringent conditions. Thus, the main thrust of the present work is showing that these conditions hold for $p$-power weighted nearest-neighbor graphs. Curiously enough, up to now, no one has shown this, except for the case when $p=1$, which is studied in Section 8.3 of (Yukich, 1998). However, the condition $p=1$ gives results only for $\alpha=1-1/d$.

All proofs and supporting lemmas can be found in the appendix. In the main body of the paper, we focus on clear explanation of Rényi entropy and mutual information estimation problems, the estimation algorithms and the statements of our converge results.

Additionally, we report on two numerical experiments. In the first experiment, we compare the empirical rates of convergence of our estimators with our theoretical results and plug-in estimates. Empirically, the NN methods are the clear winner. The second experiment is an illustrative application of mutual information estimation to an Independent Subspace Analysis (ISA) task.

The paper is organized as follows: In the next section, we formally define Rényi entropy and Rényi mutual information and the problem of their estimation. Section 3 explains the ‘generalized nearest neighbor’ graphs. This graph is then used in Section 4 to define our Rényi entropy estimator. In the same section, we state a theorem containing our convergence results for this estimator (strong consistency and rates). In Section 5, we explain the copula transformation, which connects Rényi entropy with Rényi mutual information. The copula transformation together with the Rényi entropy estimator from Section 4 is used to build an estimator of Rényi mutual information. We conclude this section with a theorem stating the convergence properties of the estimator (strong consistency and rates). Section 6 contains the numerical experiments. We conclude the paper by a detailed discussion of further related work in Section 7, and a list of open problems and directions for future research in Section 8.

The Formal Definition of the Problem

For $\alpha=1$ they are defined by the limits $H_{1}=\lim_{\alpha\to 1}H_{\alpha}$ and $I_{1}=\lim_{\alpha\to 1}I_{\alpha}$. In fact, Shannon (differential) entropy and the Shannon mutual information are just special cases of Rényi entropy and Rényi mutual information with $\alpha=1$.

Generalized Nearest-Neighbor Graphs

The basic tool to define our estimators is the generalized nearest-neighbor graph and more specifically the sum of the $p$-th powers of Euclidean lengths of its edges.

For $p\geq 0$ let us denote by $L_{p}(V)$ the sum of the $p$-th powers of Euclidean lengths of its edges. Formally,

where $E(NN_{S}(V))$ denotes the edge set of $NN_{S}(V)$. We intentionally hide the dependence on $S$ in the notation $L_{p}(V)$. For the rest of the paper, the reader should think of $S$ as a fixed but otherwise arbitrary finite non-empty set of integers, say, $S=\{1,3,4\}$.

The following is a basic result about $L_{p}$. The proof can be found in the appendix.

Let $\mathbf{X}_{1:n}=(\mathbf{X}_{1},\mathbf{X}_{2},\dots,\mathbf{X}_{n})$ be an i.i.d. sample from the uniform distribution over the $d$-dimensional unit cube $^{d}$. For any $p\geq 0$ and any finite non-empty set $S$ of positive integers there exists a constant $\gamma>0$ such that

The value of $\gamma$ depends on $d,p,S$ and, except for special cases, an analytical formula for its value is not known. This causes a minor problem since the constant $\gamma$ appears in our estimators. A simple and effective way to deal with this problem is to generate a large i.i.d. sample $\mathbf{X}_{1:n}$ from the uniform distribution over $^{d}$ and estimate $\gamma$ by the empirical value of $L_{p}(\mathbf{X}_{1:n})/n^{1-p/d}$.

An Estimator of Rényi Entropy

The following theorem is our main result about the estimator $\widehat{H}_{\alpha}$. It states that $\widehat{H}_{\alpha}$ is strongly consistent and gives upper bounds on the rate of convergence. The proof of theorem is in the appendix.

Moreover, if $f$ is Lipschitz then for any $\delta>0$ with probability at least $1-\delta$,

Copulas and Estimator of Mutual Information

A particularly clever choice is $h_{j}=F_{j}$ for all $1\leq j\leq d$, where $F_{j}$ is the cumulative distribution function (c.d.f.) of $X^{j}$. With this choice, the marginal distribution of $h_{j}(X^{j})$ is the uniform distribution over $$assuming that$F_{j}$, the c.d.f. of$X^{j}$, is continuous. Looking at the definition of$H_{\alpha}$and$I_{\alpha}$ we see that

In other words, calculation of mutual information can be reduced to the calculation of entropy provided that marginal c.d.f.’s $F_{1},F_{2},\dots,F_{d}$ are known. The problem is, of course, that these are not known and need to be estimated from the sample. We will use empirical c.d.f.’s $(\widehat{F}_{1},\widehat{F}_{2},\dots,\widehat{F}_{d})$ as their estimates. Given an i.i.d. sample $\mathbf{X}_{1:n}=(\mathbf{X}_{1},\mathbf{X}_{2},\dots,\mathbf{X}_{n})$ from distribution $\mu$ and with density $f$, the empirical c.d.f’s are defined as

Let us call the maps $\mathbf{F}$, $\widehat{\mathbf{F}}$ the copula transformation, and the empirical copula transformation, respectively. The joint distribution of $\mathbf{F}(\mathbf{X})=(F_{1}(X^{1}),F_{2}(X^{2}),\ldots,F_{d}(X^{d}))$ is called the copula of $\mu$, and the sample $(\widehat{\mathbf{Z}}_{1},\widehat{\mathbf{Z}}_{2},\ldots,\widehat{\mathbf{Z}}_{n})=(\widehat{\mathbf{F}}(\mathbf{X}_{1}),\widehat{\mathbf{F}}(\mathbf{X}_{2}),\ldots,\widehat{\mathbf{F}}(\mathbf{X}_{n}))$ is called the empirical copula (Dedecker et al., 2007). Note that $j$-th coordinate of $\widehat{\mathbf{Z}}_{i}$ equals

where $\operatorname{rank}(x,A)$ is the number of element of $A$ less than or equal to $x$. Also, observe that the random variables $\widehat{\mathbf{Z}}_{1},\widehat{\mathbf{Z}}_{2},\ldots,\widehat{\mathbf{Z}}_{n}$ are not even independent! Nonetheless, the empirical copula $(\widehat{\mathbf{Z}}_{1},\widehat{\mathbf{Z}}_{2},\ldots,\widehat{\mathbf{Z}}_{n})$ is a good approximation of an i.i.d. sample $(\mathbf{Z}_{1},\mathbf{Z}_{2},\ldots,\mathbf{Z}_{n})=(\mathbf{F}(\mathbf{X}_{1}),\mathbf{F}(\mathbf{X}_{2}),\dots,\mathbf{F}(\mathbf{X}_{n}))$ from the copula of $\mu$. Hence, we estimate the Rényi mutual information ${I}_{\alpha}$ by

where $\widehat{H}_{\alpha}$ is defined by (5). The following theorem is our main result about the estimator $\widehat{I}_{\alpha}$. It states that $\widehat{I}_{\alpha}$ is strongly consistent and gives upper bounds on the rate of convergence. The proof of this theorem can be found in the appendix.

Moreover, if the density of the copula of $\mu$ is Lipschitz, then for any $\delta>0$ with probability at least $1-\delta$,

Experiments

In this section we show two numerical experiments to support our theoretical results about the convergence rates, and to demonstrate the applicability of the proposed Rényi mutual information estimator, $\widehat{I}_{\alpha}$.

In our first experiment (Fig. 1), we demonstrate that the derived rate is indeed an upper bound on the convergence rate. Figure 1a-1c show the estimation error of $\widehat{I}_{\alpha}$ as a function of the sample size. Here, the underlying distribution was a 3D uniform, a 3D Gaussian, and a 20D Gaussian with randomly chosen nontrivial covariance matrices, respectively. In these experiments $\alpha$ was set to $0.7$. For the estimation we used $S=\{3\}$ (kth) and $S=\{1,2,3\}$ (knn) sets. Our results also indicate that these estimators achieve better performances than the histogram based plug-in estimators (hist). The number and the sizes of the bins were determined with the rule of Scott (1979). The histogram based estimator is not shown in the 20D case, as in this large dimension it is not applicable in practice. The figures are based on averaging 25 independent runs, and they also show the theoretical upper bound (Theoretical) on the rate derived in Theorem 3. It can be seen that the theoretical rates are rather conservative. We think that this is because the theory allows for quite irregular densities, while the densities considered in this experiment are very nice.

2 Application to Independent Subspace Analysis

Further Related Works

As it was pointed out earlier, in this paper we heavily built on the results known from the theory of Euclidean functionals (Steele, 1997; Redmond and Yukich, 1996; Koo and Lee, 2007). However, now we can be more precise about earlier work concerning nearest-neighbor based Euclidean functionals: The closest to our work is Section 8.3 of Yukich (1998), where the case of $NN_{S}$ graph based $p$-power weighted Euclidean functionals with $S=\{1,2,\ldots,k\}$ and $p=1$ was investigated.

Nearest-neighbor graphs have first been proposed for Shannon entropy estimation by Kozachenko and Leonenko (1987). In particular, in the mentioned work only the case of $NN_{S}$ graphs with $S=\{1\}$ was considered. More recently, Goria et al. (2005) generalized this approach to $S=\{k\}$ and proved the resulting estimator’s weak consistency under some conditions on the density. The estimator in this paper has a form quite similar to that of ours:

Here $\psi$ stands for the digamma function, and $\mathbf{e}_{i}$ is the directed edge pointing from $\mathbf{X}_{i}$ to its $k^{th}$ nearest-neighbor. Comparing this with (5), unsurprisingly, we find that the main difference is the use of the logarithm function instead of $|\cdot|^{p}$ and the different normalization. As mentioned before, Leonenko et al. (2008) proposed an estimator that uses the $NN_{S}$ graph with $S=\{k\}$ for the purpose of estimating the Rényi entropy. Their estimator takes the form

where $\Gamma$ stands for the Gamma function, $C_{k}=\left[\frac{\Gamma(k)}{\Gamma(k+1-\alpha)}\right]^{1/(1-\alpha)}$ and $V_{d}=\pi^{d/2}\Gamma(d/2+1)$ is the volume of the $d$-dimensional unit ball, and again $\mathbf{e}_{i}$ is the directed edge in the $NN_{S}$ graph starting from node $\mathbf{X}_{i}$ and pointing to the $k$-th nearest node. Comparing this estimator with (5), it is apparent that it is (essentially) a special case of our $NN_{S}$ based estimator. From the results of Leonenko et al. (2008) it is obvious that the constant $\gamma$ in (5) can be found in analytical form when $S=\{k\}$. However, we kindly warn the reader again that the proofs of these last three cited articles (Kozachenko and Leonenko, 1987; Goria et al., 2005; Leonenko et al., 2008) contain a few errors, just like the Wang et al. (2009b) paper for KL divergence estimation from two samples. Kraskov et al. (2004) also proposed a $k$-nearest-neighbors based estimator for the Shannon mutual information estimation, but the theoretical properties of their estimator are unknown.

Conclusions and Open Problems

We have studied Rényi entropy and mutual information estimators based on $NN_{S}$ graphs. The estimators were shown to be strongly consistent. In addition, we derived upper bounds on their convergence rate under some technical conditions. Several open problems remain unanswered:

Our method can be used for estimation of Shannon entropy and mutual information by simply using $\alpha$ close to $1$. The open problem is to come up with a way of choosing $\alpha$, approaching $1$, as a function of the sample size $n$ (and $d,p$) such that the resulting estimator is consistent and converges as rapidly as possible. An alternative is to use the logarithm function in place of the power function. However, the theory would need to be changed significantly to show that the resulting estimator remains strongly consistent.

In the proof of consistency of our mutual information estimator $\widehat{I}_{\alpha}$ we used Kiefer-Dvoretzky-Wolfowitz theorem to handle the effect of the inaccuracy of the empirical copula transformation. Our particular use of the theorem seems to restrict $\alpha$ to the interval $(1/2,1)$ and the dimension to values larger than $2$. Is there a better way to estimate the error caused by the empirical copula transformation and prove consistency of the estimator for a larger range of $\alpha$’s and $d=1,2$?

Finally, it is an important open problem to prove bounds on converge rates for densities that have higher order smoothness (i.e. $\beta$-Hölder smooth densities). A related open problem, in the context of of theory of Euclidean functionals, is stated in Koo and Lee (2007).

Acknowledgements

This work was supported in part by AICML, AITF (formerly iCore and AIF), NSERC, the PASCAL2 Network of Excellence under EC grant no. 216886 and by the Department of Energy under grant number DESC0002607. Cs. Szepesvári is on leave from SZTAKI, Hungary.

References

Appendix A Quasi-Additive and Very Strong Euclidean Functionals

The basic tool to prove convergence properties of our estimators is the theory of quasi-additive Euclidean functionals developed by Yukich (1998); Steele (1997); Redmond and Yukich (1996); Koo and Lee (2007) and others. We apply this machinery to the nearest neighbor functional $L_{p}$ defined in equation (3).

$L_{p}$ is a quasi-additive Euclidean functional of power $p$ if it satisfies axioms (A1)–(A7) below.

$L_{p}$ is a very strong Euclidean functional of power $p$ if it satisfies axioms (A1)–(A9) below.

For all $V\subseteq^{d}$ and a partition $\{Q_{i}~{}:~{}1\leq i\leq m^{d}\}$ of $^{d}$ into $m^{d}$ subcubes of side $1/m$

For all finite $V,V^{\prime}\subseteq^{d}$,

For a set $\mathcal{U}_{n}$ of $n$ points drawn i.i.d. from the uniform distribution over $^{d}$,

Axiom (A2) is translation invariance, axiom (A3) is scaling. First part of (A5) is subadditivity of $L_{p}$ and second part is super-additivity of $L^{*}_{p}$. Axiom (A6) is smoothness and we call (A7) quasi-additivity. Axiom (A8) is a strengthening of (A7) with an explicit rate. Axiom (A9) is the add-one bound. The axioms in Koo and Lee (2007) are slightly different, however it is a routine to check that they are implied by our set of axioms.

We will use two fundamental results about Euclidean functionals. The first is (Redmond and Yukich, 1996, Theorem 2.2) and the second is essentially (Koo and Lee, 2007, Theorem 4).

where $\gamma:=\gamma(L_{p},d)$ is a constant depending only on the functional $L_{p}$ and $d$.

where $\gamma$ is the constant from Theorem 6.

Theorem 7 differs from its original statement (Koo and Lee, 2007, Theorem 4) in two ways. First, our version is restricted to Lipschitz densities. Koo and Lee prove a generalization of Theorem 7 for $\beta$-Hölder smooth density functions. The coefficient $\beta$ then appears in the exponent of $n$ in the rate. However, their result holds only for $\beta$ in the interval $(0,1]$ which does not make it very interesting. The case $\beta=1$ corresponds to Lipschitz densities and is perhaps the most important in this range. Second, Theorem 7 has slight improvement in the rate. Koo and Lee have an extraneous $\log(n)$ factor which we remove by “correcting” their axiom (A8).

In the next section, we prove that the nearest neighbor functional $L_{p}$ defined by (3) is a very strong Euclidean functional. First, in section B, we provide a boundary functional $L_{p}^{*}$ for $L_{p}$. Then, in section C, we verify that $(L_{p},L_{p}^{*})$ satisfy axioms (A1)–(A9). Once the verification is done, Theorem 1 follows from Theorem 6.

Theorem 2 will follow from Theorem 7 and a concentration result. We prove the concentration result in Section D and finish that section with the proof of Theorem 2. Proof of Theorem 3 requires more work—we need to deal with the effect of empirical copula transformation. We handle this in Section E by employing the classical Kiefer-Dvoretzky-Wolfowitz theorem.

We start by constructing the nearest neighbor boundary functional $L_{p}^{*}$. For that we will need to introduce an auxiliary graph, which we call the nearest-neighbor graph with boundary. This graph is related to $NN_{S}$ and will be useful later.

More precisely, we define the edges from $\mathbf{x}\in V$ as follows: Let $\mathbf{b}\in\partial B$ be the boundary point closest to $\mathbf{x}$. (If there are multiple boundary points that are the closest to $\mathbf{x}$ we choose one arbitrarily.) If $(\mathbf{x},\mathbf{y})\in E(NN_{S}(V))$ and $\|\mathbf{x}-\mathbf{y}\|\leq\|\mathbf{x}-\mathbf{b}\|$ then $(\mathbf{x},\mathbf{y})$ also belongs to $E(NN^{*}_{S}(V,B))$. For each $(\mathbf{x},\mathbf{y})\in E(NN_{S}(V))$ such that $\|\mathbf{x}-\mathbf{y}\|>\|\mathbf{x}-\mathbf{b}\|$ we create in $NN^{*}_{S}(V,B)$ one copy of the edge $(\mathbf{x},\mathbf{b})$. In other words, there is a bijection between edge sets $E(NN_{S}(V))$ and $E(NN^{*}_{S}(V,B))$. An example of a graph $NN_{S}(V)$ and a corresponding graph $NN_{S}^{*}(V)$ are shown in Figure 3.

Analogously, we define $L^{*}_{p}(V,B)$ as the sum of $p$-powered edges of $NN^{*}_{S}(V,B)$. Formally,

We will need some basic geometric properties of $NN^{*}_{S}(V,B)$ and $L^{*}_{p}(V,B)$. By construction, the edges of $NN^{*}_{S}(V,B)$ are shorter than the corresponding edges of $NN_{S}(V)$. As an immediate consequence we get the following proposition.

For any cube $B$, any $p\geq 0$ and any finite set $V\subset B$, $L^{*}_{p}(V,B)\leq L_{p}(V)$.

It is easy to see that the nearest neighbor functional $L_{p}$ and its boundary functional $L_{p}^{*}$ satisfy axioms (A1)–(A3). Axiom (A4) is verified by Proposition 8. It thus remains to verify axioms (A5)–(A9) which we do in subsections C.1, C.2 and C.3. We start with two simple lemmas.

Suppose, by contradiction, that the in-degree of $\mathbf{x}$ is larger than $kB$. Then, by pigeonhole principle, there is a cone $Q(\mathbf{x},\mathbf{u})$ containing $k+1$ vertices of the graph with an incoming edge to $\mathbf{x}$. Denote these vertices $\mathbf{y}_{1},\mathbf{y}_{2},\dots,\mathbf{y}_{k+1}$ and assume that they are indexed so that $\|\mathbf{x}-\mathbf{y}_{1}\|\leq\|\mathbf{x}-\mathbf{y}_{2}\|\leq\dots\leq\|\mathbf{x}-\mathbf{y}_{k+1}\|$.

By a simple calculation, we can verify that $\|\mathbf{x}-\mathbf{y}_{k+1}\|>\|\mathbf{y}_{i}-\mathbf{y}_{k+1}\|$ for all $1\leq i\leq k$. Indeed, by the law of cosines

where the sharp inequality follows from that $\mathbf{y}_{k+1},\mathbf{y}_{i}\in Q(\mathbf{x},\mathbf{u})$ and so the angle between vectors $(\mathbf{x}-\mathbf{y}_{i})$ and $(\mathbf{x}-\mathbf{y}_{k+1})$ is strictly less than $60^{\circ}$, and the second inequality follows from $\|\mathbf{x}-\mathbf{y}_{i}\|\leq\|\mathbf{x}-\mathbf{y}_{k+1}\|$. Thus, $\mathbf{x}$ cannot be among the $k$ nearest-neighbors of $\mathbf{y}_{k+1}$ which contradicts the existence of the edge $(\mathbf{y}_{k+1},\mathbf{x})$. ∎

For any $p\geq 0$ and finite $V\subset^{d}$, $L_{p}(V)\leq O(\max(|V|^{1-p/d},1))$.

An elegant way to prove the lemma is with the use of space-filling curves.There is an elementary proof, too, based on a discretization argument. However, this proof introduces an extraneous logarithmic factor when $p=d$. Since Peano (1890) and Hilbert (1891), it is known that there exists a continuous function $\bm{\psi}$ from the unit interval $$onto the cube$^{d}$(i.e. a surjection). For obvious reason$\bm{\psi}$is called a space-filling curve. Moreover, there are space-filling curves which are$(1/d)$-Hölder; see Milne (1980). In other words, we can assume that there exists a constant$C>0$ such that

Since $\bm{\psi}$ is a surjective function we can consider a right inverse $\bm{\psi}^{-1}:^{d}\to$ i.e. a function such that $\bm{\psi}(\bm{\psi}^{-1}(x))=x$ and we let $W=\bm{\psi}^{-1}(V)$. Let $0\leq w_{1}<w_{2}<\dots<w_{|V|}\leq 1$ be the points of $W$ sorted in the increasing order. We construct a “nearest neighbor” graph $G$ on $W$. For every $1\leq j\leq|V|$ and every $i\in S$ we create a directed edge $(w_{j},w_{j+i})$, where the addition $i+j$ is taken modulo $|V|$. It is not hard to see that the total length of the edges of $G$ is

To see more clearly why (15) holds, note that every line segment $[w_{i},w_{i+1}]$, $1\leq i<|V|$ belongs to at most $O(k^{2})$ edges and the total length of the line segments is $\sum_{i=1}^{|V|-1}(w_{i+1}-w_{i})\leq 1$.

Let $H$ be a graph on $V\subset^{d}$ isomorphic to $G$, where for each edge $(w_{i},w_{j})\in E(G)$ there is a corresponding edge $(\bm{\psi}(w_{i}),\bm{\psi}(w_{j}))\in E(H)$. By the construction of $H$

Hölder property of $\bm{\psi}$ implies that

If $p\geq d$ then $|x-y|^{p/d}\leq|x-y|$ since $|x-y|\in$ and thus

Chaining the last inequality with (16), (17) and (15) we obtain that $L_{p}(V)\leq O(1)$ for $p\geq d$.

If $0<p<d$ we use the inequality between arithmetic and $(p/d)$-mean. It states that for positive numbers $a_{1},a_{2},\dots,a_{n}$

In our case $a_{i}$’s are the edge length of $G$ and $n\leq k|V|$, and we have

Combining the last inequality with (16), (17) and (15) we get that $L_{p}(V)\leq O(|V|^{1-p/d})$ for $0<p<d$.

Finally, for $p=0$, $L_{p}(V)\leq k|V|=O(|V|)$. ∎

For $p\geq 0$ and finite disjoint $V,V^{\prime}\subset^{d}$, $|L_{p}(V^{\prime}\cup V)-L_{p}(V^{\prime})|\leq O(\max(|V|^{1-p/d},1))$.

For $p\geq d$ the lemma trivially follows from the growth bound $L_{p}(V^{\prime})=O(1)$, $L_{p}(V^{\prime}\cup V)=O(1)$. For $0\leq p<d$, we need to prove two inequalities:

We start with the first inequality. We use the obvious property of $L_{p}$ that $L_{p}(V^{\prime}\cup V)\leq L_{p}(V^{\prime})+L_{p}(V)+O(1)$. Combined with the growth bound (Lemma 10) for $V$ we get

Let $U\subseteq V^{\prime}$ be the set of vertices $\mathbf{x}$ such that in $NN_{S}(V^{\prime}\cup V)$ there exists an edge from $\mathbf{x}$ to a vertex $V$. Using the two observations and the growth bound we have

The term is $L_{p}(V^{\prime}\setminus U,V^{\prime})$ can be upper bounded by $L_{p}(V^{\prime}\cup V)$ since by the choice of $U$ the graph $NN_{S}(V^{\prime}\setminus U,V^{\prime})$ is a subgraph of $NN_{S}(V^{\prime}\cup V)$. The term $O(|U|^{1-p/d})$ is at most $O(|V|^{1-p/d})$ since $|U|$ is upper bounded by the number of edges of $NN_{S}(V^{\prime}\cup V)$ ending in $V$ and, in turn, the number of these edges is by the in-degree lemma at most $O(|V|)$. ∎

For $p\geq 0$ and finite $V,V^{\prime}\subset^{d}$,

where $V^{\prime}\Delta V$ denotes the symmetric difference.

For $p\geq 0$ and finite disjoint $V,V^{\prime}\subset^{d}$,

The proof of the lemma is identical to the proof of Lemma 11 if we replace $L_{p}(\cdot)$ by $L_{p}^{*}(\cdot,^{d})$, $NN_{S}^{*}(\cdot)$ by $NN_{S}(\cdot,^{d})$, $L_{p}(\cdot,\cdot)$ by $L_{p}^{*}(\cdot,\cdot,^{d})$ and $NN_{S}(\cdot,\cdot)$ by $NN_{S}^{*}(\cdot,\cdot,^{d})$. We, of course, need to explain what $NN_{S}^{*}(V,W,^{d})$ and $L_{p}^{*}(V,W,)$ mean. For $V\subseteq W$, we define $NN_{S}^{*}(V,W,^{d})$ as the subgraph of $NN_{S}^{*}(W,^{d})$, where the edges starting in $W\setminus V$ are removed, and $L_{p}^{*}(V,W,^{d})$ is the sum the $p$-th powers of Euclidean lengths of edges of $NN_{S}^{*}(V,W,^{d})$. ∎

For $p\geq 0$ and finite $V,V^{\prime}\subset^{d}$,

where $V^{\prime}\Delta V$ denotes the symmetric difference.

The corollary is proved in exactly the same way as Corollary 12, where $L_{p}(\cdot)$ is replaced by $L_{p}^{*}(\cdot,^{d})$. ∎

C.2 Subadditivity and Superadditivity

Consider a subcube $Q_{i}$ which contains at least $k+1$ points. Using the “$L_{p}(W,W^{\prime})$ notation” from the proof of Lemma 11

Let $R$ be the union subcubes that contain at most $k$ points. Clearly $|V\cap R|\leq km^{d}$. Then

where we have used the second part of (18). The proof is finished by applying the growth bound $L_{p}(V\cap R)\leq O(\max(|V\cap R|^{1-p/d},1))\leq O(\max(m^{d-p},1))$. ∎

We construct a new graph $\hat{G}$ by modifying the graph $NN^{*}_{S}(V,^{d})$. Consider any edge $(\mathbf{x},\mathbf{y})$ such that $\mathbf{x}\in Q_{i}$ and $\mathbf{y}\not\in Q_{i}$ for some $1\leq i\leq m^{d}$. Let $\mathbf{z}$ be the point where $\partial Q_{i}$ and the line segment from $\mathbf{x}$ to $\mathbf{y}$ intersect. In $\hat{G}$, we replace $(\mathbf{x},\mathbf{y})$ by $(\mathbf{x},\mathbf{z})$. Note that the all edges of $\hat{G}$ lie completely in one of the subcubes $Q_{i}$ and they are shorter or equal to the corresponding edges in $NN^{*}_{S}(V,^{d})$.

Let $\hat{L}_{i,p}$ be the sum of $p$-th powers of the Euclidean length of the edges of $\hat{G}$ lying in $Q_{i}$. Since edges in $\hat{G}$ are shorter than in $NN^{*}_{S}(V,^{d})$, $\sum_{i=1}^{m^{d}}\hat{L}_{p,i}\leq L^{*}_{p}(V,^{d})$. To finish the proof it remains to show that $L^{*}_{p}(V\cap Q_{i},Q_{i})\leq\hat{L}_{i,p}$ for all $1\leq i\leq m^{d}$.

For any edge $(\mathbf{x},\mathbf{z})$ in $\hat{G}$ from $\mathbf{x}\in V\cap Q_{i}$ to $\mathbf{z}\in\partial Q_{i}$, the point $\mathbf{z}\in\partial Q_{i}$ is not necessarily the closest to $\mathbf{x}$. Therefore, any edge in $NN^{*}_{S}(V\cap Q_{i},Q_{i})$ is shorter than the corresponding edge in $\hat{G}$. ∎

C.3 Uniformly Distributed Points

Axiom (A7) is a direct consequence of axiom (A8). Hence, we are left with verifying axioms (A8) and (A9). In this section, $\mathcal{U}_{n}$ denotes a set of $n$ points chosen independently uniformly at random from $^{d}$.

Assume $\mathbf{X}_{1},\mathbf{X}_{2},\dots,\mathbf{X}_{n}$ are chosen i.i.d. uniformly at random from $^{d}$. Let $k$ be a fixed positive integer. Let $Z$ be the distance from $\mathbf{X}_{1}$ to $k$-th nearest-neighbor in $\{\mathbf{X}_{2},\mathbf{X}_{3},\dots,\mathbf{X}_{n}\}$. For any $p\geq 0$,

The last inequality follows from the obvious bound $\operatorname{\mathbf{Vol}}(B(\mathbf{X}_{1},u)\cap^{d})\leq\operatorname{\mathbf{Vol}}(B(\mathbf{X}_{1},u))$ and that for $u\in[0,\sqrt{d}]$ the intersection $B(\mathbf{X}_{1},u)\cap^{d}$ contains a cube of side at least $\frac{u}{2\sqrt{d}}$. To simplify this complicated integral, we note that $\operatorname{\mathbf{Vol}}(B(\mathbf{X}_{1},u))=\operatorname{\mathbf{Vol}}(B(\mathbf{X}_{1},1))u^{d}$ and make substitution $s=(\frac{u}{2\sqrt{d}})^{d}$. The last integral can be bounded by a constant multiple of

Since $\binom{n-1}{j}=O(n^{j})$ and the sum consists of only constant number of terms, it remains to show that the inner integral is $O(n^{-p/d-j})$. We can express the inner integral using the gamma function. Then, we use the asymptotic relation $\binom{n}{\epsilon}=\Theta(n^{\epsilon})$ for generalized binomial coefficients $\binom{a}{b}=\frac{\Gamma(a+1)}{\Gamma(b+1)\Gamma(a-b+1)}$ to upper-bound the result:

Let $\mathbf{X}_{1},\mathbf{X}_{2},\dots,\mathbf{X}_{n},\mathbf{X}_{n+1}$ be i.i.d. points from the uniform distribution over $^{d}$. We couple $\mathcal{U}_{n}$ and $\mathcal{U}_{n+1}$ in the obvious way $\mathcal{U}_{n}=\{\mathbf{X}_{1},\mathbf{X}_{2},\dots,\mathbf{X}_{n}\}$ and $\mathcal{U}_{n+1}=\{\mathbf{X}_{1},\mathbf{X}_{2},\dots,\mathbf{X}_{n+1}\}$. Let $Z$ be the distance from $\mathbf{X}_{n+1}$ to $k$-th closest neighbor in $\mathcal{U}_{n}$. The inequality

holds since $|S|Z^{p}$ accounts for the edges from $\mathbf{X}_{n+1}$ and since the edges from $\mathcal{U}_{n}$ are shorter (or equal) in $NN_{S}(\mathcal{U}_{n+1})$ than the corresponding edges in $\mathcal{U}_{n+1}$. Taking expectations and using Lemma 17 we get

To show the other direction of the inequality, let $Z_{i}$ be the distance from $\mathbf{X}_{i}$ its $(k+1)$-the nearest point in $\mathcal{U}_{n+1}$. (Recall that $k=\max S$.) Let $N(j)=\{\mathbf{X}_{i}~{}:~{}(\mathbf{X}_{i},\mathbf{X}_{j})\in E(NN_{S}(\mathcal{U}_{n+1}))\}$ be the incoming neighborhood of $\mathbf{X}_{j}$. Now if we remove $\mathbf{X}_{j}$ from $NN_{S}(V)$, the vertices in $N(j)$ lose $\mathbf{X}_{j}$ as their neighbor and they need to be connected to a new neighbor in $\mathcal{U}_{n+1}\setminus\{\mathbf{X}_{j}\}$. This neighbor is not farther than their $(k+1)$-th nearest-neighbor in $\mathcal{U}_{n+1}$. Therefore,

Summing over all $j=1,2,\dots,n+1$ we have

The double sum on the right hand side is simply the sum over all edges of $NN_{S}(\mathcal{U}_{n+1})$ and so we can write

The proof is finished by dividing through by $(n+1)$. ∎

The first inequality follows from Proposition 8 by taking expectation. The proof of the second inequality is much more involved. Consider the (random) subset of points $\hat{\mathcal{U}}_{n}\subseteq\mathcal{U}_{n}$ which are connected to the boundary in $NN^{*}_{S}(\mathcal{U}_{n},^{d})$ by at least one edge. We use the notation $L_{p}(W,W^{\prime})$ for any $W\subseteq W^{\prime}$ and its two properties expressed by Eq. (18) and a third obvious property $L_{p}(W,W^{\prime})\leq L_{p}(W^{\prime})$. We have

where in the last step we have used that $L_{p}(\mathcal{U}_{n}\setminus\widehat{\mathcal{U}}_{n},\mathcal{U}_{n})\leq L^{*}_{p}(\mathcal{U}_{n},^{d})$ which holds since the edges from vertices $\mathcal{U}_{n}\setminus\widehat{\mathcal{U}}_{n}$ are the same in both graphs $NN_{S}(\mathcal{U}_{n})$ and $NN^{*}_{S}(\mathcal{U}_{n},^{d})$. If we take expectation, we get

The second key component that we need is that the expected sum of $p$-th powers of lengths of edges of $NN_{S}^{*}(\mathcal{U}_{n},^{d})$ that connect points in $\mathcal{U}_{n}$ to $\partial^{d}$ is “small”. More precisely, for any point $\mathbf{x}\in^{d}$ let $\mathbf{b}_{\mathbf{x}}\in\partial^{d}$ be the boundary point closest to $\mathbf{x}$. We show that

If $p\geq d-1$ then $L_{p}(\widehat{\mathcal{V}}_{n})=O(1)$. Therefore, for any $p\geq 0$

We construct a nearest-neighbor graph $\widehat{G}$ on $\widehat{\mathcal{U}}_{n}$ by lifting $NN_{S}(\widehat{\mathcal{V}}_{n})$. For every edge, $(\mathbf{b}_{\mathbf{X}},\mathbf{b}_{\mathbf{Y}})$ in $NN_{S}(\widehat{\mathcal{V}}_{n})$ we create an edge $(\mathbf{X},\mathbf{Y})$. Clearly, $L_{p}(\widehat{U}_{n})$ is at most the sum of $p$-the powers of the edges lengths of $\widehat{G}$. By triangle inequality, for any $p>0$

In-degrees and out-degrees of $\widehat{G}$ are $O(1)$ and so if we sum over all edges of $(\mathbf{X},\mathbf{Y})$ of $\widehat{G}$ and take expectation, we get

Appendix D Concentration and Estimator of Entropy

In this section, we show that if $\mathcal{V}_{n}$ is a set of $n$ points drawn i.i.d. from any distribution over $^{d}$ then $L_{p}(\mathcal{V}_{n})$ is tightly concentrated. That is, we show that with high probability $L_{p}(\mathcal{V}_{n})$ is within $O(n^{1/2-p/(2d)})$ its expected value. We use this result at the end of this section to give a proof of Theorem 2.

It turns out that in order to derive the concentration result, the properties of the distribution generating the points are irrelevant (even the existence of density is not necessary). The only property that we exploit is smoothness of $L_{p}$. As a technical tool, we use the isoperimetric inequality for Hamming distance and product measures. This inequality is, in turn, a simple consequence of Talagrand’s isoperimetric inequality, see e.g. Dubhashi and Panconesi (2009); Alon and Spencer (2000); Talagrand (1995). To phrase the isoperimetric inequality, we use Hamming distance $H(\mathbf{x}_{1:n},\mathbf{y}_{1:n})$ between two tuples $\mathbf{x}_{1:n}=(\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{n})$, $\mathbf{y}_{1:n}=(\mathbf{y}_{1},\mathbf{y}_{2},\dots,\mathbf{y}_{n})$ which is defined as the number of elements in which $\mathbf{x}_{1:n}$ and $\mathbf{y}_{1:n}$ disagree.

Let $A\subset\Omega^{n}$ be a subset of an $n$-fold product of a probability space equipped with a product measure. For any $t\geq 0$ let $A_{t}=\left\{\mathbf{x}_{1:n}\in\Omega^{n}~{}:~{}\exists\mathbf{y}_{1:n}\in\Omega^{n}\ \text{s.t.}\ H(\mathbf{x}_{1:n},\mathbf{y}_{1:n})\leq t\right\}$ be an expansion of $A$. Then, for any $t\geq 0$,

where $\overline{A_{t}}$ denotes the complement of $A_{t}$ with respect to $\Omega^{n}$.

Let $\mathcal{V}_{n}$ consists of $n$ points drawn i.i.d. from an absolutely continuous probability distribution over $^{d}$, let $0\leq p\leq d$. For any $t>0$,

where $M(\cdot)$ denotes the median of a random variable.

Let $\Omega=^{d}$ and $\mathcal{V}_{n}=\{\mathbf{X}_{1},\mathbf{X}_{2},\dots,\mathbf{X}_{n}\}$, where $\mathbf{X}_{1},\mathbf{X}_{2},\dots,\mathbf{X}_{n}$ are independent. To emphasize that we are working in a product space, we use the notations $L_{p}(\mathbf{x}):=L_{p}(\{x_{1},x_{2},\dots,x_{n}\})$, $L_{p}(\mathbf{X}_{1:n}):=L_{p}(\mathcal{V}_{n})=L_{p}(\{\mathbf{X}_{1},\mathbf{X}_{2},\dots,\mathbf{X}_{n}\})$ and $M:=M(L_{p}(\mathbf{X}_{1:n}))$. Let $A=\{\mathbf{x}\in\Omega^{n}~{}:~{}L_{p}(\mathbf{x})\leq M\}$. By smoothness of $L_{p}$ there exists a constant $C>0$ such that

Therefore, $L_{p}(\mathbf{x})>M+t$ implies that $\mathbf{x}\in\overline{A_{(t/C)^{d/(d-p)}}}$. Hence for a random $\mathbf{X}_{1:n}=(\mathbf{X}_{1},\mathbf{X}_{2},\dots,\mathbf{X}_{n})$

by the isoperimetric inequality. Similarly, we set $B=\overline{A}$ and note that by smoothness we have also the reversed inequality

Therefore, $L_{p}(\mathbf{x})<M+t$ implies that $\mathbf{x}\in\overline{B_{(t/C)^{d/(d-p)}}}$. By the same argument as before

The theorem follows by the union bound and the fact that $\Pr[A]=\Pr[B]=1/2$. ∎

For conciseness let $L_{p}=L_{p}(\mathcal{V}_{n})$ and $M=M(L_{p}(\mathcal{V}_{n}))$. We have

Putting these pieces together we arrive at what we wanted to prove:

By scaling and translation, we can assume that the support of $\mu$ is contained in the unit cube $^{d}$. The first part of the theorem follows immediately from Theorem 6. To prove the second part observe from (23) that for any $\delta>0$ with probability at least $1-\delta$,

It is easy to see that if $0<p\leq d-1$ then $-1/2+p/(2d)<-\frac{d-p}{d(2d-p)}<0$, and if $d-1\leq p<d$ then $-1/2+p/(2d)<-\frac{d-p}{d(d+1)}<0$. Now using (24), Theorem 7 and the triangle inequality, we have that for any $\delta>0$ with probability at least $1-\delta$,

To finish the proof of (7) exploit the fact that $\log(1\pm x)=\pm O(x)$ for $x\to 0$. ∎

Appendix E Copulas and Estimator of Mutual Information

The goal of this section is to prove Theorem 3 on convergence of the estimator $\widehat{I}_{\alpha}$. The main additional problem that we need to deal with in the proof is the effect of the empirical copula transformation. A version of the classical Kiefer-Dvoretzky-Wolfowitz theorem due to Massart gives a convenient way to do it; see e.g. Devroye and Lugosi (2001).

As a simple consequence of the Kiefer-Dvoretzky-Wolfowitz theorem, we can derive that $\widehat{\mathbf{F}}$ is a good approximation of $\mathbf{F}$.

The following corollary is an obvious consequence of this lemma:

Let $a_{1},a_{2},\ldots,a_{m}$ and $b_{1},b_{2},\ldots,b_{m}$ be real numbers. Let $a_{(1)}\leq a_{(2)}\leq\ldots\leq a_{(m)}$ and $b_{(1)}\leq b_{(2)}\leq\ldots\leq b_{(m)}$ be the same numbers sorted in ascending order. Then, $|a_{(i)}-b_{(i)}|\leq\max_{j}|a_{j}-b_{j}|$, for all $1\leq i\leq m$.

The proof is left as an exercise for the reader. ∎

Let $k=\max S$, $A=\{\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{n}\}$ and $B=\{\mathbf{y}_{1},\mathbf{y}_{2},\dots,\mathbf{y}_{n}\}$. Let $w_{A}(i,j)=\|\mathbf{x}_{i}-\mathbf{x}_{j}\|^{p}$ and $w_{B}(i,j)=\|\mathbf{y}_{i}-\mathbf{y}_{j}\|^{p}$ be the edge weights defined by $A$ and $B$ respectively. Let $a^{i}_{(j)}$ be the $p$-th power of the distance from $\mathbf{x}_{i}$ to its $j$-th nearest-neighbor in $A$, for $1\leq i\leq n$ ,$1\leq j\leq n-1$. Similarly, let $b^{i}_{(j)}$ be the $p$-th power of the distance from $\mathbf{y}_{i}$ to its $j$-th nearest-neighbor in $B$. Note that for any $i$, if we sort the real numbers $w_{A}(i,1),\ldots,w_{A}(i,i-1),w_{A}(i,i+1),\ldots,w_{A}(i,n)$, then we get $a^{i}_{(1)}\leq a^{i}_{(2)}\leq\ldots\leq a^{i}_{(n-1)}$. Similarly for $w_{B}$’s and $b^{i}_{(j)}$’s. Using these notations we can write

The third inequality follows from Proposition 27. It remains to bound $|w_{A}(i,j)-w_{B}(i,j)|$. We consider two cases:

Case $0<p<1$. Using $|u^{p}-v^{p}|\leq|u-v|^{p}$ valid for any $u,v\geq 0$ and the triangle inequality

Case $p\geq 1$. Consider the function $f(u)=u^{p}$ on interval $[0,\sqrt{d}]$. On this interval $|f^{\prime}(u)|\leq pd^{(p-1)/2}$ and so $f$ is Lipschitz with constant $pd^{(p-1)/2}$. In other words, for any $u,v\in[0,\sqrt{d}]$, $|u^{p}-v^{p}|\leq pd^{(p-1)/2}|u-v|$. Thus

where the second inequality follows from (26). ∎

It follows immediately from Corollary 26 and Lemma 28 that with probability at least $1-\delta$,

We are now ready to give the proof of Theorem 3.

Let $g$ denote the density of the copula of $\mu$. The first part follows from (6), Corollary 29 and a standard Borel-Cantelli argument with $\delta=1/n^{2}$. Corollary 29 puts the restrictions $d\geq 3$ and $1/2<\alpha<1$.

The second part can be proved along the same lines. From (7) we have that for any $\delta>0$ with probability at least $1-\delta$,

Hence using the triangle inequality again, and exploiting that $(\log(1/\delta))^{1/2-p/(2d)}<(\log(1/\delta))^{1/2}$ if $0<p$, $\delta<1$, we have that with probability at least $1-\delta$,

To finish the proof exploit that when $x\to 0$ then $\log(1\pm x)=\pm O(x)$. ∎