# Tree density estimation

László Györfi1, Aryeh Kontorovich2, Roi Weiss3

1Department of Computer Science and Information Theory, Budapest University of
Technology and Economics, Budapest, Hungary  2Department of Computer Science,
Ben-Gurion University of the Negev, Beer-Sheva, Israel  3Department of
Computer Science, Ariel University, Shomron, Israel

###### Abstract

We study the problem of estimating the density $f({\mathbf{x}})$ of a random
vector ${{\mathbf{X}}}$ in ${\mathbb{R}}^{d}$. For a spanning tree $T$ defined
on the vertex set $\\{1,\dots,d\\}$, the tree density $f_{T}$ is a product of
bivariate conditional densities. An optimal spanning tree minimizes the
Kullback-Leibler divergence between $f$ and $f_{T}$. From i.i.d. data we
identify an optimal tree $T^{*}$ and efficiently construct a tree density
estimate $f_{n}$ such that, without any regularity conditions on the density
$f$, one has
$\lim_{n\to\infty}\int|f_{n}({\mathbf{x}})-f_{T^{*}}({\mathbf{x}})|d{\mathbf{x}}=0$
a.s. For Lipschitz $f$ with bounded support,
${\mathbb{E}}\left\\{\int|f_{n}({\mathbf{x}})-f_{T^{*}}({\mathbf{x}})|d{\mathbf{x}}\right\\}=O\big{(}n^{-1/4}\big{)}$,
a dimension-free rate.

###### Index Terms:

density estimation; tree identification; Kruskal’s algorithm; consistency;
rate of convergence

##  I Introduction

A natural strategy for mitigating the curse of dimensionality in estimating
probability distributions is to employ low-complexity family of approximation
distributions. For discrete distributions, Chow and Liu [5] suggested a family
of tree-based approximations and gave an efficient maximum-likelihood
estimator based on Kruskal’s optimal spanning tree algorithm [14]. We stress
that this approach makes no structural assumptions about the sampling
distribution, but rather constitutes a modeling choice. Consequently, in this
paradigm, the goal is to approximate the optimal-tree distribution from the
data, without any guarantees on how well the latter approximates the true
sampling distribution.

Extensions of the Chow-Liu approach to continuous distributions were studied
by Bach and Jordan [1] and by Liu et al. [16] under various assumptions. They
contructed approximation tree densities, which are products of bivariate
conditional marginals. A principal contribution of this paper is to introduce
identification and estimation procedures for which strong consistency can be
established without any regularity conditions on the underlying sampling
density. Our second contribution is to obtain risk rates under mild
assumptions.

By way of a motivating example, Horváth et al. [12] examine a model of sensor
networks, consisting of $d\gg 1$ sensors. The goal here is to estimate an
approximation to the $d$-dimensional density of the sensors’ measurements. In
the special case of a linear sensor layout, the joint distribution is
naturally modeled via a Markov chain. In this case, the density is a product
of bivariate conditional densities. In general, we do not assume that the true
density has this special form, and instead seek the best approximating product
of bivariate conditional densities. Thus, out of the possible $\binom{d}{2}$
bivariate conditional densities, an approximation of the true density depends
only on $d-1$ bivariate conditional densities. Furthermore, any approximation
has bounded complexity: it is given by a spanning tree.

### Formal setup.

Let ${{\mathbf{X}}}=(X_{1},\dots,X_{d})\in{\mathbb{R}}^{d}$ be a
$d$-dimensional random vector with probability density $f({\mathbf{x}})$. We
denote the index set by $V=\\{1,\dots,d\\}$, the densities of the one- and
two-dimensional marginals by $f_{i}(x_{i})$ and $f_{i,j}(x_{i},x_{j})$,
respectively, for $i,j\in V$, $i\neq j$. A spanning tree $T$ on the vertex set
$V$ is an undirected graph $T=(V,E)$, where $|E|=d-1$; we denote the set of
all spanning trees by ${\cal T}$. Given the one- and two-dimensional
marginals, a $T\in{\cal T}$ induces a joint density on ${\mathbf{X}}$ as
follows:

$\displaystyle f_{T}({\mathbf{x}})=\prod\limits_{(i,j)\in
T}\frac{f_{i,j}(x_{i},x_{j})}{f_{i}(x_{i})f_{j}(x_{j})}\prod_{i=1}^{d}f_{i}(x_{i}).$
(1)

Any vertex $k\in V$ may be arbitrarily designated as the root of $T$. Once the
root is fixed, any $i\in V\setminus\left\\{k\right\\}$ has a unique parent
$j(i)=j_{T}(i)\in V$ (the reader is referred to Cormen et al. [6] for the
relevant graph-theoretic background, including spanning trees and Kruskal’s
algorithm). The parent notation enables expressing (1) more compactly:

$\displaystyle f_{T}({\mathbf{x}})=\prod\limits_{i\neq k}f_{i|j(i)}(x_{i}\mid
x_{j(i)})f_{k}(x_{k}),$ (2)

where $k$ is the designated root and the conditional densities are given by

$\displaystyle f_{i|j(i)}(x_{i}\mid
x_{j(i)})=\frac{f_{i,j(i)}(x_{i},x_{j(i)})}{f_{j(i)}(x_{j(i)})}.$

As in Devroye and Györfi [7], we consider the $L_{1}$ risk

$\displaystyle\|f-f_{n}\|=\int|f({\mathbf{x}})-f_{n}({\mathbf{x}})|d{\mathbf{x}};$
(3)

this choice of metric is amply motivated therein.

This paper investigates the problem of finding a spanning tree $T$ on the
vertex set $V$ and establishing that its induced probability density
$f_{T}({\mathbf{x}})$ approximates the true density $f({\mathbf{x}})$
optimally or nearly so, under some criterion. There are several candidates for
a goodness-of-fit measure, perhaps the most natural of which is the $L_{1}$
metric:

$\displaystyle{\cal T}_{L_{1}}=\left\\{\bar{T}\in{\cal
T}:\|f-f_{\bar{T}}\|=\min_{T\in{\cal T}}\|f-f_{T}\|\right\\}$

(${\cal T}$ being a finite set, the minimum is always achieved). The
shortcoming of the $L_{1}$ criterion is that minimizing it over $T\in{\cal T}$
appears to be a computationally hard problem, with no known efficient
approximation algorithm. Therefore, in line with the original Liu-Chow
approach, we adopt the Kullback-Leibler (KL) divergence as our goodness-of-fit
criterion. The KL-divergence between $f({\mathbf{x}})$ and
$f_{T}({\mathbf{x}})$ is defined by

$\displaystyle\operatorname{KL}(f,f_{T})=\int
f({\mathbf{x}})\log\frac{f({\mathbf{x}})}{f_{T}({\mathbf{x}})}d{\mathbf{x}},$

while the set of optimal spanning trees is

$\displaystyle{\cal T}_{\operatorname{KL}}=\left\\{T^{*}\in{\cal
T}:\operatorname{KL}(f,f_{T^{*}})=\min_{T}\operatorname{KL}(f,f_{T})\right\\}.$

Our goal is to identify a spanning tree $T^{*}$ belonging to the set ${\cal
T}_{\operatorname{KL}}$ and to estimate a best tree density $f_{T^{*}}$ from
data.

To present the Chow-Liu approach, let us assume, for the moment, that the
density $f$ is known. Consider the undirected complete graph defined on the
set of vertices $V$. The edges of the graph are weighted by the mutual
information of the two-dimensional marginal probability distributions
corresponding to the two vertices connected. One can check that

$\displaystyle\operatorname{KL}(f,f_{T})=\sum_{i=1}^{d}H(X_{i})-\sum_{(i,j)\in
T}I(X_{i},X_{j})-H({\mathbf{X}}),$ (4)

where $I(X_{i},X_{j})$ is the mutual information defined by

$\displaystyle I(X_{i},X_{j})=\int\int
f_{i,j}(x_{i},x_{j})\log\frac{f_{i,j}(x_{i},x_{j})}{f_{i}(x_{i})f_{j}(x_{j})}dx_{i}dx_{j},$
(5)

and $H(\cdot)$ denotes the differential entropy of a random variable or a
random vector [1], defined by $H({\mathbf{X}})=H(f)=\int
f({\mathbf{x}})\log\frac{1}{f({\mathbf{x}})}d{\mathbf{x}}$. Thus,
$\operatorname{KL}(f,f_{T})$ is minimal when we take edges from the complete
graph along the spanning tree having the maximum weight, i.e., $T^{*}\in{\cal
T}_{\operatorname{KL}}$ such that

$\displaystyle T^{*}\in\mathop{\rm arg\,max}_{T}\left(\sum_{(i,j)\in
T}I(X_{i},X_{j})\right).$

An optimal spanning tree $T^{*}$ can be obtained by applying Kruskal’s
algorithm [14] to the weighted complete graph on $V$ described above. The
latter is a simple method for constructing an optimum spanning tree in an
undirected weighted graph, with time complexity $O(d^{2}\log d)$. To choose a
tree of maximum total edge weight, we first index the $d(d-1)/2$ edges
according to decreasing weights $\\{b_{i}\\}$, so that $b_{i}\geq b_{j}$
whenever $i<j$. We then start by selecting $b_{1}$ and $b_{2}$, and add
$b_{3}$ if $b_{3}$ does not form a cycle with $b_{1}$ and $b_{2}$. We continue
to consider edges of successively higher indices, selecting an edge whenever
it does not form a cycle with the set previously selected, and rejecting it
otherwise. In general $T^{*}$ is not unique; it is, however, when all of the
$I(X_{i},X_{j})$ are distinct for $i\neq j$. Furthermore, $T^{*}$ depends only
on the ordering of the set of mutual informations, $\\{I(X_{i},X_{j}),i\neq
j\\}$.

In the setting of this paper, the density $f$ is not known. Instead, $n$
independent copies of ${\mathbf{X}}$ (the “data”) are drawn:

$\displaystyle{\cal D}_{n}=({\mathbf{X}}^{1},\dots,{\mathbf{X}}^{n}).$

Tan et al. [19] studied in detail the case when ${\mathbf{X}}$ has a
multivariate normal distribution. In this case
$I(X_{i},X_{j})=-\frac{1}{2}\log(1-\rho_{ij}^{2})$ where $-1\leq\rho_{ij}\leq
1$ is the correlation coefficient. In their paper the density $f$ is not
arbitrary, it is a tree density $f_{T}$ and an empirical identification
algorithm of this tree $T$ is introduced. If the covariance matrix for the
density $f=f_{T}$ has full rank, then the identification error probability has
exponential rate of convergence. Section 8 in Bach and Jordan [1] is on
stationary Gaussian time series, for which $\rho_{ij}=r_{|i-j|}$ with some
$r_{1},\dots,r_{d-1}$. If $|r_{1}|>|r_{j}|$ for all $j>1$, then the optimal
spanning tree $T^{*}$ is a chain consisting of the edges
$(1,2),(2,3),\dots,(d-1,d)$. Interestingly, the correlations $r_{j}$ for $j>1$
don’t matter. For general density, this particular spanning tree $T^{*}$
appears, when $X_{1},\dots,X_{d}$ is a Markov chain.

Liu et al. [16] considered a more general problem: namely, the forest density
estimate. For identifying the best forest and for estimating the corresponding
forest density, they proposed a kernel-based approach. If the bivariate and
univariate densities are Hölder continuous and they are bounded away from zero
(called strong density assumption), then under the additional assumption that
$I(X_{i},X_{j})$ are finite and distinct for $i\neq j$, the identification of
the best forest is consistent. Note that the strong density assumption
excludes many densities of interest, including Gaussian densities. In
addition, Liu et al. [16] give bounds on the rate of convergence of forest
density estimate in terms of KL-divergence. For example, in case of Lipschitz
density that satisfies the strong density condition, they show that the excess
KL-risk is of order

$\displaystyle O\left(\ln n/n^{1/4}\right),$

see Theorem 9 therein.

### Paper overview and main results.

The main aim of this paper is to avoid the strong density assumption and the
assumption that the $I(X_{i},X_{j})$, $i\neq j$, are distinct. We introduce a
tree estimate $T_{n}$ and a corresponding tree-density estimate $f_{n}$ such
that without any regularity condition on the density $f$ one has that

$\displaystyle\lim_{n\to\infty}\int|f_{n}({\mathbf{x}})-f_{T_{n}}({\mathbf{x}})|d{\mathbf{x}}=0$

a.s. (Theorem 1). Furthermore, for Lipschitz continuous $f$ with bounded
support,

$\displaystyle{\mathbb{E}}\left\\{\int|f_{n}({\mathbf{x}})-f_{T_{n}}({\mathbf{x}})|d{\mathbf{x}}\right\\}=O\left(n^{-1/4}\right)$

independently on the dimension $d$, (Theorem 2).

For a best spanning tree $T^{*}$, we have an approximation error:

$\displaystyle\|f-f_{T^{*}}\|.$

Pinsker’s inequality implies an upper bound:

$\displaystyle\|f-f_{T^{*}}\|^{2}/2\leq\operatorname{KL}(f_{T^{*}},f),$

therefore

$\displaystyle\|f-f_{T^{*}}\|\leq\sqrt{2\operatorname{KL}(f_{T^{*}},f)}.$

Using the formula (4), we can estimate $\operatorname{KL}(f_{T^{*}},f)$. For
the identification step, the term $\sum_{(i,j)\in T^{*}}I(X_{i},X_{j})$ is
already estimated, while we can estimate $\sum_{i=1}^{d}H(X_{i})$ and
$H({\mathbf{X}})$ by Kozachenko-Leonenko algorithm. If $\bar{T}$ and $T^{*}$
stand for $L_{1}$-optimal tree and for KL-optimal tree, respectively, then the
previous argument implies a bound on the excess approximation error:

$\displaystyle 0$
$\displaystyle\leq\|f-f_{T^{*}}\|-\|f-f_{\bar{T}}\|\leq\sqrt{2\operatorname{KL}(f_{T^{*}},f)}-\|f-f_{\bar{T}}\|\leq\sqrt{2\operatorname{KL}(f_{\bar{T}},f)}-\|f-f_{\bar{T}}\|.$
(6)

For perfect approximation, we have $\|f-f_{\bar{T}}\|=0$, which yields
$\operatorname{KL}(f_{\bar{T}},f)=0$, and so (6) implies $\|f-f_{T^{*}}\|=0$,
too.

It is important to characterize the distribution of ${\mathbf{X}}$, where

$\displaystyle\operatorname{KL}(f,f_{T^{*}})=\min_{T}\operatorname{KL}(f,f_{T})$

is small. For example, if there is a permutation of the components of
${\mathbf{X}}$ such that in this ordering the components form a first order
Markov process, then $\operatorname{KL}(f_{T^{*}},f)=0$. In general, if
$\operatorname{KL}(f_{T^{*}},f)=0$, then without any regularity condition on
the underlying density, our algorithm identifies such perfect spanning tree
$T^{*}$.

An important application of this setup is the example of sensor network, where
the sensors are geographically (arbitrary, squared lattice, hexagonal lattice,
etc.) distributed. We can assume that the mutual information of the
neighboring sensors are dominating, and therefore one has to estimate only
$c\cdot d$ mutual information $I(X_{i},X_{j})$ (instead of $\binom{d}{2}$),
where $c\approx 4$. In the Gaussian case mentioned above the correlation
matrix has only $c\cdot d$ non negligible elements. In this sense the
correlation matrix is sparse.

##  II The identification of the best spanning tree $T^{*}$

Using the data ${\cal D}_{n}$, we shall construct estimates
$I_{n}(X_{i},X_{j})$. Based on these estimates, introduce the empirically best
spanning tree $T_{n}$:

$\displaystyle T_{n}=\mathop{\rm arg\,max}_{T}\left(\sum_{(i,j)\in
T}I_{n}(X_{i},X_{j})\right).$ (7)

In order to have universally consistent identification of a best tree, we need
consistent mutual information estimates without any regularity assumption on
the underlying density.

Let $(X,Y)$ be a random vector taking values in ${\mathbb{R}}^{2}$ with
probability density function $f_{XY}(x,y)$ and with marginal densities
$g_{X}(x)$, $g_{Y}(y)$. The aim is to estimate the mutual information

$\displaystyle I(X,Y)=\int\int
f_{X,Y}(x,y)\log\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}dxdy$

such that the estimate is strongly consistent without any regularity condition
on the density $f_{X,Y}$. Assume having the i.i.d. data
$(X_{1},Y_{1}),\dots,(X_{n},Y_{n})$. Several estimates of mutual information
have been considered. Most of them are based on density estimates, from which
the consistency of differential entropies estimates is derived.

Györfi and van der Meulen [10] considered histogram-based consistent
estimators for differential entropy, which in turn can be used to estimate the
mutual information. The histogram based estimate of mutual information is
defined as follows: Let ${\cal P}_{n}$ and ${\cal Q}_{n}$ be finite or
infinite partitions of ${{\mathbb{R}}}$, and denote by $\mu_{n}$ the empirical
distribution of $(X_{1},Y_{1}),\dots,(X_{n},Y_{n})$:

$\displaystyle\mu_{n}(A\times
B)=\frac{1}{n}\sum_{i=1}^{n}{\mathbb{I}}_{\\{X_{i}\in A,Y_{i}\in B\\}},$

Set

$\displaystyle
I_{n}(X,Y)=I_{n}(\mu_{n},\mu_{n,1}\times\mu_{n,2})=\sum_{A\in\mathcal{P}_{n},B\in\mathcal{Q}_{n}}\mu_{n}(A\times
B)\log\frac{\mu_{n}(A\times B)}{\mu_{n,1}(A)\mu_{n,2}(B)},$ (8)

where

$\displaystyle\mu_{n,1}(A)=\mu_{n}(A\times{\mathbb{R}})$

and

$\displaystyle\mu_{n,2}(B)=\mu_{n}({\mathbb{R}}\times B).$

Barron, Györfi, and van der Meulen [3] showed the following: if ${\cal
P}_{n}={\cal Q}_{n}$ is the uniform partition with bin width
$h^{\prime}_{n}\to 0$, $nh^{\prime 2}_{n}\to\infty$ and $I(X,Y)<\infty$, then

$\displaystyle\lim_{n\rightarrow\infty}I_{n}(X,Y)=I(X,Y)$ (9)

a.s. Wang, Kulkarni, and Verdú [21] and Silva and Narayanan [18] introduced
and studied data-driven, partitioning-based estimate of the mutual
information.

Let us now return to the problem of identifying $T^{*}\in{\cal
T}_{\operatorname{KL}}$. Construct estimates $I_{n}(X_{i},X_{j})$ as in (8)
and select $T_{n}$ according to (7). For identifying $T^{*}$, one has to
generate $\binom{d}{2}$ mutual information estimate, therefore we have to use
a mutual information estimate of small computational complexity. The estimate
(8) has the smallest computational complexity among the algorithms mentioned
before. The error of the tree density estimate has two components: error of
the identification and the error of the bivariate density estimates. It will
turn out that the second error dominates the first one.

##  III Estimating the best tree density

In this section we study the estimation problem of a best approximating
density $f_{T^{*}}$. The aim is to introduce a density estimate $f_{n}$ such
that

$\displaystyle\lim_{n}\int|f_{T^{*}}({\mathbf{x}})-f_{n}({\mathbf{x}})|d{\mathbf{x}}=0$

a.s. without any regularity conditions on the density $f$ of ${\mathbf{X}}$.

One may estimate the original density $f$, for example by the ordinary
histogram rule with bin width $h_{n}>0$, for which the consistency conditions
are $nh_{n}^{d}\to\infty$ and $h_{n}\to 0$. In applications where $d$ is
large, we typically do not have a sufficiently large sample, i.e.,
$nh_{n}^{d}$ is not sufficiently large. This is the main motivation why the
estimation of the best approximating density $f_{T^{*}}$ is considered.

For a spanning tree $T_{n}$, we construct the density estimate $f_{n}$ by
estimating the conditional densities $f_{i\mid j(i)}(x_{i}\mid x_{j(i)})$. As
in Györfi and Kohler [9], we estimate the conditional densities by the ratio
of histograms. For $1\leq k\leq n$ denote the $k$th sample vector by
${\mathbf{X}}_{k}=(X^{(k)}_{1},\dots,X^{(k)}_{d})$ and let $\mu_{n,i,j(i)}$
and $\mu_{n,j(i)}$ be the empirical distributions for the samples
$((X^{(1)}_{i},X^{(1)}_{j(i)}),\dots,(X^{(n)}_{i},X^{(n)}_{j(i)}))$ and
$(X^{(1)}_{j(i)},\dots,X^{(n)}_{j(i)})$, respectively, i.e.,

$\displaystyle\mu_{n,i,j(i)}(A\times
B)=\frac{1}{n}\sum_{k=1}^{n}{\mathbb{I}}_{\\{X^{(k)}_{i}\in
A,X^{(k)}_{j(i)}\in B\\}}$

and

$\displaystyle\mu_{n,j(i)}(B)=\frac{1}{n}\sum_{k=1}^{n}{\mathbb{I}}_{\\{X^{(k)}_{j(i)}\in
B\\}}.$

To simplify the analysis, we renumber the vertex set $V=\\{1,\dots,d\\}$ such
that for any $1\leq i<d$, the vertex subset $\\{i,\dots,d\\}$ corresponds to a
subtree of $T_{n}$ with $i$ being a leaf and its parent satisfies $j(i)>i$. In
particular, $d$ is the root of the tree and the vertices are ordered by their
distance from the root. Let ${\cal P}_{n}$ denote uniform partitions of
${\mathbb{R}}$ with bin width $h_{n}$. For $x_{i}\in A\in{\cal P}_{n}$,
$x_{j(i)}\in B\in{\cal P}_{n}$ and $i=1,\dots,d-1$, put

$\displaystyle f_{n,i\mid j(i)}(x_{i}\mid x_{j(i)})$
$\displaystyle=\frac{\mu_{n,i,j(i)}(A\times B)}{h_{n}\mu_{n,j(i)}(B)}$

with $0/0=0$ by definition and for $x_{d}\in A\in{\cal P}_{n}$,

$\displaystyle f_{n,d}(x_{d})$ $\displaystyle=\frac{\mu_{n,{d}}(A)}{h_{n}},$

where $d$ is the root of the spanning tree $T_{n}$. Set

$\displaystyle f_{n}({\mathbf{x}})$ $\displaystyle=\prod_{i<d}f_{n,i\mid
j(i)}(x_{i}\mid x_{j(i)})f_{n,d}(x_{d}).$ (10)

##  IV Consistency and rate of convergence

Our first result is the density-free strong consistency:

######  Theorem 1.

Assume that all $I(X_{i},X_{j})$ are finite for $i\neq j$. If
$h^{\prime}_{n}\to 0$, $nh^{\prime 2}_{n}\to\infty$, $h_{n}\to 0$ and
$nh_{n}^{2}/\log n\to\infty$, then

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{I}}_{T_{n}\in{\cal
T}_{\operatorname{KL}}}=1$ (11)

a.s., i.e., almost surely,

$\displaystyle T_{n}\in{\cal T}_{\operatorname{KL}}$

for all sufficiently large sample size $n$. Furthermore,

$\displaystyle\lim_{n\to\infty}\int|f_{n}({\mathbf{x}})-f_{T_{n}}({\mathbf{x}})|d{\mathbf{x}}=0$

a.s.

Notice that the dimension $d$ does not appear in any of the conditions above,
which allows for a dimension-free consistency.

The consistency result of Theorem 1 holds without any regularity conditions on
the density $f$. Without such conditions, the rate at which the $L_{1}$ error
converges to zero can be arbitrarily slow [7]. So in order to obtain non-
trivial rates of convergence, one needs to impose some regularity condition on
$f$.

We say that a function $g:{\mathbb{R}}^{k}\to{\mathbb{R}}$ satisfies the
_Lipschitz condition_ with respect to the Euclidean norm $\|\cdot\|$ if for
all ${\mathbf{x}},{\mathbf{x}}^{\prime}\in{\mathbb{R}}^{k}$,

$|g({\mathbf{x}})-g({\mathbf{x}}^{\prime})|\leq
L\|{\mathbf{x}}-{\mathbf{x}}^{\prime}\|.$

######  Theorem 2.

If ${\mathbf{X}}$ is bounded, the one-dimensional marginals $\\{f_{i}\\}$ and
the two-dimensional marginals $\\{f_{i,j}\\}$ satisfy the Lipschitz condition,
and $nh^{\prime 2}_{n}\to\infty$, then

$\displaystyle{\mathbb{E}}\left\\{\int|f_{n}({\mathbf{x}})-f_{T_{n}}({\mathbf{x}})|d{\mathbf{x}}\right\\}=O\left(1/\sqrt{nh_{n}^{2}}\right)+O(h_{n})+O({h^{\prime}}^{\gamma}_{n})+O\left(\frac{1}{n{h^{\prime}}_{n}^{2}}\right)$
(12)

with all $\gamma>0$.

######  Remark 1.

The rate of convergence in the theorem is dimension-free, which means that it
does not depend on $d$. Note that the constants hidden in the $O$-notation of
the last two terms in (12) depend on the density $f$ beyond the Lipschitz
constant (i.e., on $\delta>0$ of (13) — the minimum gap in the distinct mutual
information values of different $X_{i},X_{j}$). Thus, the bound is not in the
minimax sense.

For the choice

$\displaystyle h_{n}=c_{1}\cdot n^{-1/4}$

and

$\displaystyle h^{\prime}_{n}=c_{2}\cdot
n^{-1/4}\quad\mbox{and}\quad\gamma=2,$

$nh^{\prime 2}_{n}\to\infty$ and so (12) has the form

$\displaystyle{\mathbb{E}}\left\\{\int|f_{n}({\mathbf{x}})-f_{T_{n}}({\mathbf{x}})|d{\mathbf{x}}\right\\}=O\left(n^{-1/4}\right)+O\left(n^{-1/2}\right)=O\left(n^{-1/4}\right)$

such that the density estimation error $O\left(n^{-1/4}\right)$ dominates the
identification error $O\left(n^{-1/2}\right)$. The upper bound
$O\left(n^{-1/4}\right)$ on the rate of convergence cannot be improved. For
$d=2$, where there is no tree identification problem, this rate is a minimax
lower bound for Lipschitz class and the ordinary histogram achieves this rate,
see Lemma 3 below. A simple embedding argument entails that this also holds
for $d>2$ when $\operatorname{KL}(f,f_{T^{*}})=0$.

######  Remark 2.

Recall that Liu et al. [16] give bounds in a similar setup in terms of the KL-
divergence. In the case of Lipschitz density that satisfies the strong density
condition, they show that the excess KL-risk is of order $O\left(\ln
n/n^{1/4}\right)$. In Theorem 2 above we consider the $L^{1}$ loss. The strong
density condition is avoided due to two technical ingredients: (a) the
analysis of the approximation error $J_{n,1}$ in the proof of Proposition 3
and (b) the inclusion of the marginal density term in the loss of the
conditional density estimation (i.e., (22)).

##  V Proof of Theorem 1

Because of

$\displaystyle\int|f_{T_{n}}({\mathbf{x}})-f_{n}({\mathbf{x}})|d{\mathbf{x}}$
$\displaystyle\leq 2{\mathbb{I}}_{T_{n}\notin{\cal
T}_{\operatorname{KL}}}+\sum_{T^{*}\in{\cal
T}_{\operatorname{KL}}}{\mathbb{I}}_{T_{n}=T^{*}}\int|f_{T^{*}}({\mathbf{x}})-f_{n}({\mathbf{x}})|d{\mathbf{x}},$

the proof of Theorem 1 is decomposed into two propositions.

######  Proposition 1.

Assume that all $I(X_{i},X_{j})$ are finite for $i\neq j$. If $nh^{\prime
2}_{n}\to\infty$ and $h^{\prime}_{n}\to 0$, then (11) holds.

###### Proof.

The event $\\{T_{n}\notin{\cal T}_{\operatorname{KL}}\\}$ means that the
orderings of $\\{I_{n}(X_{i},X_{j}),i\neq j\\}$ and of
$\\{I(X_{i},X_{j}),i\neq j\\}$ are distinct. Put

$\displaystyle\delta$
$\displaystyle=\min_{(i,j)\neq(u,v),|I(X_{i},X_{j})-I(X_{u},X_{v})|>0}|I(X_{i},X_{j})-I(X_{u},X_{v})|.$
(13)

Then,

$\displaystyle\\{T_{n}\notin{\cal T}_{\operatorname{KL}}\\}$
$\displaystyle\subset\cup_{(i,j)\neq(u,v),I(X_{i},X_{j})-I(X_{u},X_{v})>0}\\{I_{n}(X_{i},X_{j})-I_{n}(X_{u},X_{v})<0\\}$
$\displaystyle\subset\cup_{(i,j)}\\{|I_{n}(X_{i},X_{j})-I(X_{i},X_{j})|\geq\delta/2\\}.$

Under the conditions of the proposition, (9) implies that

$\displaystyle\lim_{n\to\infty}I_{n}(X_{i},X_{j})=I(X_{i},X_{j})$ (14)

a.s., for all $i\neq j$, from which the proposition follows. $\Box$

######  Proposition 2.

If $nh_{n}^{2}/\log n\to\infty$ and $h_{n}\to 0$, then

$\displaystyle\lim_{n\to\infty}{\mathbb{I}}_{T_{n}=T^{*}}\int|f_{n}({\mathbf{x}})-f_{T^{*}}({\mathbf{x}})|d{\mathbf{x}}=0$
(15)

a.s.

###### Proof.

In the proof of this proposition we apply the strong pointwise consistency of
the ordinary histogram. Choose a sequence of partitions ${\cal P}_{n}$ of
${\mathbb{R}}^{d}$ such that the cells of ${\cal P}_{n}$ are shifted versions
of $[0,h_{n}]^{d}$ with bin width $h_{n}$, $n=1,2,\dots$. Assume i.i.d. data

$\displaystyle{\cal D}_{n}=({\mathbf{X}}_{1},\dots,{\mathbf{X}}_{n})$

and let $\mu_{n}$ denote the empirical distribution for ${\cal D}_{n}$. If
$A_{n}({\mathbf{x}})$ is the cell of ${\cal P}_{n}$ into which ${\mathbf{x}}$
falls, then the histogram estimate is defined by

$\displaystyle
f_{n,h_{n}}({\mathbf{x}})=\frac{\mu_{n}(A_{n}({\mathbf{x}}))}{h_{n}^{d}}.$

######  Lemma 1.

If $h_{n}\to 0$ and $nh_{n}^{d}/\log n\to\infty$, then

$\displaystyle\lim_{n\to\infty}f_{n,h_{n}}({\mathbf{x}})=f({\mathbf{x}})$ (16)

a.s. for $\lambda$-almost all ${\mathbf{x}}$, where $\lambda$ is the Lebesgue
measure.

###### Proof.

Set

$\displaystyle\bar{f}_{h_{n}}({\mathbf{x}})$
$\displaystyle={\mathbb{E}}\left\\{\frac{\mu_{n}(A_{n}({\mathbf{x}}))}{h_{n}^{d}}\right\\}=\frac{\mu(A_{n}({\mathbf{x}}))}{h_{n}^{d}}.$

The consistency of the bias term
$\bar{f}_{h_{n}}({\mathbf{x}})-f({\mathbf{x}})$ follows from the generalized
Lebesgue density theorem [22, Theorem 7.16]: Let $B_{n}({\mathbf{x}})$ denote
the smallest cube centered at ${\mathbf{x}}$ and containing
$A_{n}({\mathbf{x}})$. If there is a constant $c>0$ such that

$\displaystyle\lambda(B_{n}({\mathbf{x}}))\leq c\lambda(A_{n}({\mathbf{x}})),$
(17)

then $h_{n}\to 0$ implies that

$\displaystyle\bar{f}_{h_{n}}({\mathbf{x}})$
$\displaystyle=\frac{\mu(A_{n}({\mathbf{x}}))}{\lambda(A_{n}({\mathbf{x}}))}\to
f({\mathbf{x}})$

for $\lambda$-almost all ${\mathbf{x}}$. Obviously, (17) is satisfied with
$c=2^{d}$. For $\varepsilon>0$, Bernstein’s inequality implies

$\displaystyle{\mathbb{P}}\\{|f_{n,h_{n}}({\mathbf{x}})-\bar{f}_{h_{n}}({\mathbf{x}})|>\varepsilon\\}$
$\displaystyle={\mathbb{P}}\\{|\mu_{n}(A_{n}({\mathbf{x}}))-\mu(A_{n}({\mathbf{x}}))|>\varepsilon
h_{n}^{d}\\}$ $\displaystyle\leq
2e^{-\frac{n\varepsilon^{2}h_{n}^{2d}}{2\mu(A_{n}({\mathbf{x}}))+2\varepsilon
h_{n}^{d}/3}}$
$\displaystyle=2e^{-\frac{n\varepsilon^{2}h_{n}^{d}}{2\bar{f}_{h_{n}}({\mathbf{x}})+2\varepsilon/3}}.$

For $nh_{n}^{d}/\log n\to\infty$, this yields

$\displaystyle\sum_{n=1}^{\infty}{\mathbb{P}}\\{|f_{n,h_{n}}({\mathbf{x}})-\bar{f}_{h_{n}}({\mathbf{x}})|>\varepsilon\\}$
$\displaystyle<\infty$

if the sequence $\bar{f}_{h_{n}}({\mathbf{x}})$ is bounded, and by referring
to the Borel-Cantelli lemma the proof of the variance term is complete, i.e.,

$\displaystyle|f_{n,h_{n}}({\mathbf{x}})-\bar{f}_{h_{n}}({\mathbf{x}})|$
$\displaystyle\to 0$

a.s. $\Box$

We now complete the proof of Proposition 2. First, we claim that $f_{T^{*}}$
is a density, i.e.,

$\displaystyle\int f_{T^{*}}({\mathbf{x}})d{\mathbf{x}}$ $\displaystyle=1.$
(18)

Indeed, the representation (2) implies that

$\displaystyle\int f_{T^{*}}({\mathbf{x}})d{\mathbf{x}}$
$\displaystyle=\int\dots\int f_{T^{*}}(x_{1},\dots,x_{d})dx_{1}\dots dx_{d}$
$\displaystyle=\int\dots\int\prod_{i=1}^{d-1}f_{i\mid j(i)}(x_{i}\mid
x_{j(i)})f_{d}(x_{d})dx_{1}\dots dx_{d}.$

For the vertex set $\\{1,\dots,d\\}$, $1$ is a leaf, therefore $j(1)>1$. Thus,

$\displaystyle\int f_{T^{*}}({\mathbf{x}})d{\mathbf{x}}$
$\displaystyle=\int\dots\int\left(\int f_{1\mid j(1)}(x_{1}\mid
x_{j(1)})dx_{1}\right)\prod_{i=2}^{d-1}f_{i\mid j(i)}(x_{i}\mid
x_{j(i)})f_{d}(x_{d})dx_{2}\dots dx_{d}$
$\displaystyle=\int\dots\int\prod_{i=2}^{d-1}f_{i\mid j(i)}(x_{i}\mid
x_{j(i)})f_{d}(x_{d})dx_{2}\dots dx_{d}.$

(18) follows by induction. Similarly, one can check that $f_{n}$ is also a
density, i.e.,

$\displaystyle\int f_{n}({\mathbf{x}})d{\mathbf{x}}$ $\displaystyle=1.$

For $x_{i}\in A\in{\cal P}_{n}$, $x_{j(i)}\in B\in{\cal P}_{n}$ and
$i=1,\dots,d-1$, put

$\displaystyle g_{n}(x_{i},x_{j(i)})$
$\displaystyle=\frac{\mu_{n,i,j(i)}(A\times B)}{h_{n}^{2}}$

and

$\displaystyle f_{n,j(i)}(x_{j(i)})$
$\displaystyle=\frac{\mu_{n,d}(B)}{h_{n}}.$

Put

$D=\\{{\mathbf{x}}:0<f_{T^{*}}({\mathbf{x}})<\infty\\}.$

If ${\mathbf{x}}\in D$, then $0<f_{i\mid j(i)}(x_{i}\mid x_{j(i)})<\infty$ and
so $0<f_{j(i)}(x_{j(i)})$. Then, Lemma 1 implies

$\displaystyle f_{n,i\mid j(i)}(x_{i}\mid x_{j(i)})$
$\displaystyle=\frac{g_{n}(x_{i},x_{j(i)})}{f_{n,j(i)}(x_{j(i)})}\to f_{i\mid
j(i)}(x_{i}\mid x_{j(i)})$

a.s. for $\lambda$-almost all ${\mathbf{x}}\in D$. Thus,

$\displaystyle f_{n}({\mathbf{x}})$ $\displaystyle\to f_{T^{*}}({\mathbf{x}})$
(19)

a.s. for $\lambda$-almost all ${\mathbf{x}}\in D$. The proof is completed by
referring to the fact that pointwise consistency implies $L_{1}$ consistency:

$\displaystyle\int|f_{n}({\mathbf{x}})-f_{T^{*}}({\mathbf{x}})|d{\mathbf{x}}$
$\displaystyle=2\int(f_{T^{*}}({\mathbf{x}})-f_{n}({\mathbf{x}}))_{+}d{\mathbf{x}}+\int
f_{n}({\mathbf{x}})d{\mathbf{x}}-\int f_{T^{*}}({\mathbf{x}})d{\mathbf{x}}$
$\displaystyle=2\int(f_{T^{*}}({\mathbf{x}})-f_{n}({\mathbf{x}}))_{+}d{\mathbf{x}}$
$\displaystyle=2\int_{D}(f_{T^{*}}({\mathbf{x}})-f_{n}({\mathbf{x}}))_{+}d{\mathbf{x}}$
$\displaystyle\to 0$

a.s., where we used (19) and the dominated convergence theorem. $\Box$

##  VI Proof of Theorem 2

Again, the proof of Theorem 2 is decomposed into two propositions.

######  Proposition 3.

If ${\mathbf{X}}$ is bounded, the one-dimensional marginals $\\{f_{i}\\}$ and
the two-dimensional marginals $\\{f_{i,j}\\}$ satisfy the Lipschitz condition,
and $n{h^{\prime}}_{n}^{2}\to\infty$, then

$\displaystyle{\mathbb{P}}\\{T_{n}\notin{\cal T}_{\operatorname{KL}}\\}$
$\displaystyle\leq
O({h^{\prime}}^{\gamma}_{n})+O\left(\frac{1}{n{h^{\prime}}_{n}^{2}}\right)$

with all $\gamma>0$.

###### Proof.

With the notation of Proposition 1,

$\displaystyle{\mathbb{P}}\\{T_{n}\notin{\cal T}_{\operatorname{KL}}\\}$
$\displaystyle\leq\max_{(i,j)\neq(u,v)}{\mathbb{I}}_{I(X_{i},X_{j})-I(X_{u},X_{v})>0}{\mathbb{P}}\\{I_{n}(X_{i},X_{j})-I_{n}(X_{u},X_{v})<0\\}$
$\displaystyle\leq\sum_{(i,j)}{\mathbb{P}}\\{|I_{n}(X_{i},X_{j})-I(X_{i},X_{j})|\geq\delta/2\\}.$

Therefore, we have to bound the rate of convergence of

$\displaystyle{\mathbb{P}}\\{|I_{n}(X,Y)-I(X,Y)|\geq 5\varepsilon\\}$

where $X=X_{i}$ and $Y=X_{j}$ with $i\neq j\in\\{1,\dots,d\\}$ and
$\varepsilon=\delta/10$. We show, that under the condition
$n{h^{\prime}}_{n}^{2}\to\infty$,

$\displaystyle{\mathbb{P}}\\{|I_{n}(X,Y)-I(X,Y)|\geq 5\varepsilon\\}$
$\displaystyle=O\left({h^{\prime}}^{\gamma}_{n}\right)+3e^{-n(\varepsilon+o(1))}+O\left(\frac{1}{n{h^{\prime}}_{n}^{2}}\right).$
(20)

Consider the decomposition

$\displaystyle I(X,Y)-I_{n}(X,Y)$
$\displaystyle=I(\mu,\mu_{1}\times\mu_{2})-I_{n}(\mu_{n},\mu_{n,1}\times\mu_{n,2})=J_{n,1}+J_{n,2}+J_{n,3},$

where

$\displaystyle J_{n,1}$
$\displaystyle=I(\mu,\mu_{1}\times\mu_{2})-I_{n}(\mu,\mu_{1}\times\mu_{2})$
$\displaystyle J_{n,2}$
$\displaystyle=I_{n}(\mu,\mu_{1}\times\mu_{2})-I_{n}(\mu_{n},\mu_{1}\times\mu_{2})$
$\displaystyle J_{n,3}$
$\displaystyle=I_{n}(\mu_{n},\mu_{1}\times\mu_{2})-I_{n}(\mu_{n},\mu_{n,1}\times\mu_{n,2})=I_{n}(\mu_{n,1},\mu_{1})+I_{n}(\mu_{n,2},\mu_{2}).$

To bound the approximation term $J_{n,1}$, note that

$\displaystyle J_{n,1}\geq 0,$

because the mutual information is a KL-divergence, and
$I_{n}(\mu,\mu_{1}\times\mu_{2})$ is a KL-divergence restricted to a product
of partitions. Thus, instead of looking at $|J_{n,1}|$, it is enough to upper
bound $J_{n,1}$. Let
$\bar{f}_{X,Y}(x,y)=\frac{1}{h_{n}^{2}}\int\int_{A_{n}(x,y)}f_{X,Y}(x^{\prime},y^{\prime})dx^{\prime}dy^{\prime}=\frac{\mu(A_{n}(x,y))}{h_{n}^{2}}$,
where $A_{n}(x,y)$ is the cell of the product partition into which $(x,y)$
falls, and similarly $\bar{g}_{X}$ and $\bar{g}_{Y}$ for the marginals $g_{X}$
and $g_{Y}$. We have that

$\displaystyle J_{n,1}$ $\displaystyle=\int\int
f_{X,Y}(x,y)\log{\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}}-\int\int\bar{f}_{X,Y}(x,y)\log{\frac{\bar{f}_{X,Y}(x,y)}{\bar{g}_{X}(x)\bar{g}_{Y}(y)}}$
$\displaystyle=\int\int
f_{X,Y}(x,y)\log{\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}}dxdy-\int\int
f_{X,Y}(x,y)\log{\frac{\bar{f}_{X,Y}(x,y)}{\bar{g}_{X}(x)\bar{g}_{Y}(y)}}dxdy$
$\displaystyle\quad+\int\int
f_{X,Y}(x,y)\log{\frac{\bar{f}_{X,Y}(x,y)}{\bar{g}_{X}(x)\bar{g}_{Y}(y)}}dxdy-\int\int\bar{f}_{X,Y}(x,y)\log{\frac{\bar{f}_{X,Y}(x,y)}{\bar{g}_{X}(x)\bar{g}_{Y}(y)}}dxdy.$

The second line in the last equation is zero while the first one is

$\displaystyle
D_{KL}(f_{X,Y},\bar{f}_{X,Y})-D_{KL}(g_{X},\bar{g}_{X})-D_{KL}(g_{Y},\bar{g}_{Y})\leq
D_{KL}(f_{X,Y},\bar{f}_{X,Y}).$

Since $J_{n,1}\geq 0$, it is left to show that
$D_{KL}(f_{X,Y},\bar{f}_{X,Y})=O({h^{\prime}_{n}})$. To this end, applying the
Lipschitz condition one gets that

$\displaystyle D_{KL}(f_{X,Y},\bar{f}_{X,Y})\leq
D_{\chi^{2}}(f_{X,Y},\bar{f}_{X,Y})$
$\displaystyle=\int\frac{(f_{X,Y}(x,y)-\bar{f}_{X,Y}(x,y))^{2}}{\bar{f}_{X,Y}(x,y)}dx{dy}$
$\displaystyle\leq
Lh_{n}^{\prime}\int\frac{|f_{X,Y}(x,y)-\bar{f}_{X,Y}(x,y)|}{\bar{f}_{X,Y}(x,y)}dxdy.$

Therefore,

$\displaystyle D_{KL}(f_{X,Y},\bar{f}_{X,Y})$ $\displaystyle\leq
Lh_{n}^{\prime}\int\frac{f_{X,Y}(x,y)+\bar{f}_{X,Y}(x,y)}{\bar{f}_{X,Y}(x,y)}dxdy=Lh_{n}^{\prime}\int\frac{\bar{f}_{X,Y}(x,y)+\bar{f}_{X,Y}(x,y)}{\bar{f}_{X,Y}(x,y)}dxdy=2CLh_{n}^{\prime},$

where $C$ is the Lebesgue measure of the support of $\bar{f}$. Thus,

$\displaystyle{\mathbb{I}}_{J_{n,1}\geq\varepsilon}$ $\displaystyle\leq
J_{n,1}^{\gamma}/\varepsilon^{\gamma}\leq
2^{\gamma}C^{\gamma}L^{\gamma}{h^{\prime}}^{\gamma}_{n}/\varepsilon^{\gamma}.$

For KL-divergence restricted to finite partitions, Tusnády [20], Kallenberg
[13], Quine and Robinson [17], Barron [2] proved exponential, large deviation-
type inequalities, [8, Section 3.1]. From Gretton and Györfi [8, Equation
(13)], the boundedness of $X$ and $Y$ and $nh^{\prime}_{n}\to\infty$ yield

$\displaystyle{\mathbb{P}}\\{I_{n}(\mu_{n,1},\mu_{1})>\varepsilon\\}$
$\displaystyle=e^{-n(\varepsilon+o(1))}$

and

$\displaystyle{\mathbb{P}}\\{I_{n}(\mu_{n,2},\mu_{2})>\varepsilon\\}$
$\displaystyle=e^{-n(\varepsilon+o(1))}.$

We have that

$\displaystyle J_{n,2}$
$\displaystyle=I_{n}(\mu,\mu_{1}\times\mu_{2})-I_{n}(\mu_{n},\mu)+I_{n}(\mu_{n},\mu)-I_{n}(\mu_{n},\mu_{1}\times\mu_{2})$
$\displaystyle=J_{n,4}-I_{n}(\mu_{n},\mu),$

where

$\displaystyle
J_{n,4}=\sum_{A\in\mathcal{P}_{n},B\in\mathcal{Q}_{n}}(\mu(A\times
B)-\mu_{n}(A\times B))\log\frac{\mu(A\times B)}{\mu_{1}(A)\mu_{2}(B)},$

Again, the boundedness of $X$ and $Y$ and $n{h^{\prime}}_{n}^{2}\to\infty$
yield

$\displaystyle{\mathbb{P}}\\{I_{n}(\mu_{n},\mu)>\varepsilon\\}$
$\displaystyle=e^{-n(\varepsilon+o(1))}.$

The Cauchy-Schwarz inequality implies that

$\displaystyle\operatorname{Var}(J_{n,4})$
$\displaystyle\leq|\mathcal{P}_{n}|\cdot|\mathcal{Q}_{n}|\sum_{A\in\mathcal{P}_{n},B\in\mathcal{Q}_{n}}\operatorname{Var}\left(\mu_{n}(A\times
B)\log\frac{\mu(A\times B)}{\mu_{1}(A)\mu_{2}(B)}\right)$
$\displaystyle\leq\frac{|\mathcal{P}_{n}|\cdot|\mathcal{Q}_{n}|}{n}\sum_{A\in\mathcal{P}_{n},B\in\mathcal{Q}_{n}}\mu(A\times
B)\left(\log\frac{\mu(A\times B)}{\mu_{1}(A)\mu_{2}(B)}\right)^{2}.$

Therefore, Chebyshev’s inequality implies

$\displaystyle{\mathbb{P}}\\{|J_{n,4}|\geq\varepsilon\\}$
$\displaystyle\leq\operatorname{Var}(J_{n,4})/\varepsilon^{2}=O\left(\frac{1}{nh_{n}^{\prime
2}}\right),$

where we used the fact that under the conditions of the proposition

$\displaystyle\sum_{A\in\mathcal{P}_{n},B\in\mathcal{Q}_{n}}\mu(A\times
B)\left(\log\frac{\mu(A\times B)}{\mu_{1}(A)\mu_{2}(B)}\right)^{2}$
$\displaystyle\to\int\int
f_{X,Y}(x,y)\left(\log\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}\right)^{2}dxdy<\infty.$

The last inequality is proved in the following lemma. $\Box$

######  Lemma 2.

If $X,Y$ are bounded and the density $f_{X,Y}$ satisfies the Lipschitz
condition, then

$\displaystyle I(X,Y)^{2}\leq\int\int
f_{X,Y}(x,y)\left(\log\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}\right)^{2}dxdy<\infty.$
(21)

###### Proof.

By Jensen’s inequality

$\displaystyle\int\int
f_{X,Y}(x,y)\left(\log\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}\right)^{2}dxdy$
$\displaystyle\geq\left(\int\int
f_{X,Y}(x,y)\log\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}dxdy\right)^{2}=I(X,Y)^{2}.$

To show the second inequality in (21), let $L>0$ be the Lipschitz constant of
$f_{X,Y}$ and note that for any $(x,y)\in{\mathbb{R}}^{2}$,

$\displaystyle g_{X}(x)$
$\displaystyle=\int_{-\infty}^{\infty}f_{X,Y}(x,y^{\prime})dy^{\prime}\geq\int_{y-\frac{f_{X,Y}(x,y)}{L}}^{y+\frac{f_{X,Y}(x,y)}{L}}f_{X,Y}(x,y^{\prime})dy^{\prime}\geq\int_{-\frac{f_{X,Y}(x,y)}{L}}^{\frac{f_{X,Y}(x,y)}{L}}(f_{X,Y}(x,y)-L|y^{\prime}|)dy^{\prime}=\frac{f_{X,Y}(x,y)^{2}}{L}.$

Similarly, $g_{Y}(y)\geq\frac{f_{X,Y}(x,y)^{2}}{L}$. We write

$\displaystyle\int\int
f_{X,Y}(x,y)\left(\log\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}\right)^{2}dxdy$
$\displaystyle=\int\int
g_{X}(x)g_{Y}(y)\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}\left(\log\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}\right)^{2}dxdy$

and split the integral’s domain into those $x,y$ satisfying
$\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}<1$ and those for which
$\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}\geq 1$. Since $t\log^{2}t$ is bounded
for $0\leq t\leq 1$, the integral over the first domain is bounded. For the
second domain, since $\log^{2}t$ is monotonic increasing for $t\geq 1$, we use
the bounds $g_{X}(x)\geq\frac{f_{X,Y}(x,y)^{2}}{L}$ and
$g_{Y}(y)\geq\frac{f_{X,Y}(x,y)^{2}}{L}$ above to get

$\displaystyle\int\int_{\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}\geq
1}f_{X,Y}(x,y)\left(\log\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}\right)^{2}dxdy$
$\displaystyle\leq\int\int_{\frac{f_{X,Y}(x,y)}{g_{X}(x)g_{Y}(y)}\geq
1}f_{X,Y}(x,y)\left(\log\frac{L^{2}}{f_{X,Y}(x,y)^{3}}\right)^{2}dxdy$
$\displaystyle\leq\int\int
f_{X,Y}(x,y)\left(\log\frac{L^{2}}{f_{X,Y}(x,y)^{3}}\right)^{2}dxdy$
$\displaystyle=9L^{2/3}\int\int\frac{f_{X,Y}(x,y)}{L^{2/3}}\left(\log\frac{f_{X,Y}(x,y)}{L^{2/3}}\right)^{2}dxdy.$

Since $f_{X,Y}$ is Lipschitz in a bounded domain, it is bounded, and since
$t\log^{2}t$ is bounded when $t\geq 0$ is bounded, the last integral is
bounded as well. $\Box$

######  Proposition 4.

If ${\mathbf{X}}$ is bounded, the one-dimensional marginals $\\{f_{i}\\}$ and
the two-dimensional marginals $\\{f_{i,j}\\}$ satisfy the Lipschitz condition,
then

$\displaystyle{\mathbb{E}}\left\\{{\mathbb{I}}_{T_{n}=T^{*}}\int|f_{n}({\mathbf{x}})-f_{T^{*}}({\mathbf{x}})|d{\mathbf{x}}\right\\}=O\left(1/\sqrt{nh_{n}^{2}}\right)+O(h_{n}).$

###### Proof.

Here we apply the rate of convergence for the histogram estimation rule given
in Lemma 3 below. Recall that we renumber the vertex set $V=\\{1,\dots,d\\}$
such that for any $1\leq i<d$, the vertex subset $\\{i,\dots,d\\}$ corresponds
to a subtree of $T^{*}$ with $i$ being a leaf and $j(i)>i$, and so $d$ is the
root of the subtree and the subtree vertices are ordered by their distance
from the root. For the sake of simplicity we use the abbreviation

$\displaystyle f(x_{i}\mid x_{j(i)})$ $\displaystyle=f_{i\mid j(i)}(x_{i}\mid
x_{j(i)})$

and

$\displaystyle f_{n}(x_{i}\mid x_{j(i)})$ $\displaystyle=f_{n,i\mid
j(i)}(x_{i}\mid x_{j(i)}).$

If a void product is defined to be $1$, then we have the decomposition

$\displaystyle f_{n}({\mathbf{x}})-f_{T^{*}}({\mathbf{x}})$
$\displaystyle=\prod_{i=1}^{d-1}f_{n}(x_{i}\mid
x_{j(i)})f_{n}(x_{d})-\prod_{i=1}^{d-1}f(x_{i}\mid x_{j(i)})f(x_{d})$
$\displaystyle=\sum_{k=1}^{d-1}\prod_{i=1}^{k-1}f_{n}(x_{i}\mid
x_{j(i)})[f_{n}(x_{k}\mid x_{j(k)})-f(x_{k}\mid
x_{j(k)})]\prod_{i=k+1}^{d-1}f(x_{i}\mid x_{j(i)})f(x_{d})$
$\displaystyle\quad+\prod_{i=1}^{d-1}f_{n}(x_{i}\mid
x_{j(i)})[f_{n}(x_{d})-f(x_{d})].$

Thus,

$\displaystyle|f_{n}({\mathbf{x}})-f_{T^{*}}({\mathbf{x}})|$
$\displaystyle\leq\sum_{k=1}^{d-1}\prod_{i=1}^{k-1}f_{n}(x_{i}\mid
x_{j(i)})|f_{n}(x_{k}\mid x_{j(k)})-f(x_{k}\mid
x_{j(k)})|\prod_{i=k+1}^{d-1}f(x_{i}\mid x_{j(i)})f(x_{d})$
$\displaystyle\quad+\prod_{i=1}^{d-1}f_{n}(x_{i}\mid
x_{j(i)})|f_{n}(x_{d})-f(x_{d})|.$

For $k\leq d-1$, we have that

$\displaystyle\int\dots\int\prod_{i=1}^{k-1}f_{n}(x_{i}\mid
x_{j(i)})|f_{n}(x_{k}\mid x_{j(k)})-f(x_{k}\mid
x_{j(k)})|\prod_{i=k+1}^{d-1}f(x_{i}\mid x_{j(i)})f(x_{d})dx_{1}\dots dx_{d}$
$\displaystyle=\int\dots\int|f_{n}(x_{k}\mid x_{j(k)})-f(x_{k}\mid
x_{j(k)})|\prod_{i=k+1}^{d-1}f(x_{i}\mid x_{j(i)})f(x_{d})dx_{k}\dots dx_{d},$

while

$\displaystyle\int\dots\int\prod_{i=1}^{d-1}f_{n}(x_{i}\mid
x_{j(i)})|f_{n}(x_{d})-f(x_{d})|dx_{1}\dots dx_{d}$
$\displaystyle=\int|f_{n}(x_{d})-f(x_{d})|dx_{d}.$

This last term is easier, because according to the rate of convergence theorem
of the standard histogram the conditions of the theorem imply

$\displaystyle{\mathbb{E}}\int|f_{n}(x_{d})-f(x_{d})|dx_{d}=O\left(1/\sqrt{nh_{n}}\right)+O(h_{n}),$

(cf. Lemma 3 below). The problem left is to show that for $k\leq d-1$,

$\displaystyle\int\dots\int{\mathbb{E}}\\{|f_{n}(x_{k}\mid
x_{j(k)})-f(x_{k}\mid x_{j(k)})|\\}\prod_{i=k+1}^{d-1}f(x_{i}\mid
x_{j(i)})f(x_{d})dx_{k}\dots dx_{d}$
$\displaystyle=O\left(1/\sqrt{nh_{n}^{2}}\right)+O(h_{n})$

By the ordering of the variables, $k<j(k)$ and the unique path from the root
$d$ up to vertex $j(k)$ contains only vertices from $\\{j(k)+1,\dots,d\\}$,
ordered by their distance from $d$. Let $d=j_{1}>j_{2}>\dots>j_{r}=j(k)$ be
this path. Then,

$\displaystyle\int\dots\int{\mathbb{E}}\\{|f_{n}(x_{k}\mid
x_{j(k)})-f(x_{k}\mid x_{j(k)})|\\}\prod_{i=k+1}^{d-1}f(x_{i}\mid
x_{j(i)})f(x_{d})dx_{k}\dots dx_{d}$
$\displaystyle=\int\dots\int{\mathbb{E}}\\{|f_{n}(x_{k}\mid
x_{j(k)})-f(x_{k}\mid x_{j(k)})|\\}dx_{k}$ $\displaystyle\qquad\qquad\times
f(x_{j_{r}}\mid x_{j_{r-1}})f(x_{j_{r-1}}\mid x_{j_{r-2}})\dots
f(x_{j_{2}}\mid x_{j_{1}})f(x_{j_{1}})dx_{j_{1}}\dots dx_{j_{r}}$
$\displaystyle=\int\int{\mathbb{E}}\\{|f_{n}(x_{k}\mid x_{j(k)})-f(x_{k}\mid
x_{j(k)})|\\}f(x_{j(k)})dx_{k}dx_{j(k)}$
$\displaystyle=\int{\mathbb{E}}\left\\{\int|f_{n}(x_{k}\mid
x_{j(k)})-f(x_{k}\mid x_{j(k)})|f(x_{j(k)})dx_{k}\right\\}dx_{j(k)}.$ (22)

Lemma 4 below implies that for any $x_{j(k)}$,

$\displaystyle\int|f_{n}(x_{k}\mid x_{j(k)})-f(x_{k}\mid
x_{j(k)})|f(x_{j(k)})dx_{k}$
$\displaystyle=\int\left|\frac{g_{n}(x_{k},x_{j(k)})}{f_{n}(x_{j(k)})}-\frac{f(x_{k},x_{j(k)})}{f(x_{j(k)})}\right|f(x_{j(k)})dx_{k}$
$\displaystyle\leq
2\int\frac{|g_{n}(x_{k},x_{j(k)})-f(x_{k},x_{j(k)})|f(x_{j(k)})}{\max\\{f_{n}(x_{j(k)}),f(x_{j(k)})\\}}dx_{k}$
$\displaystyle\leq 2\int|g_{n}(x_{k},x_{j(k)})-f(x_{k},x_{j(k)})|dx_{k},$

where we used the fact that

$\frac{f(x_{j(k)})}{\max\\{f_{n}(x_{j(k)}),f(x_{j(k)})\\}}\leq 1.$

Thus, (22) is bounded from above by

$\displaystyle
2\int{\mathbb{E}}\left\\{\int|g_{n}(x_{k},x_{j(k)})-f(x_{k},x_{j(k)})|\right\\}dx_{k}dx_{j(k)}$
$\displaystyle=O\left(1/\sqrt{nh_{n}^{2}}\right)+O(h_{n}),$

where the last equality is by Lemma 3. $\Box$

######  Lemma 3.

[4, 7]. For the notation of Lemma 1, assume that $h_{n}\to 0$ and
$nh_{n}^{d}\to\infty$. If ${\mathbf{X}}$ is bounded and $f$ is Lipschitz
continuous, then

$\displaystyle{\mathbb{E}}\left\\{\int|f_{n,h_{n}}({\mathbf{x}})-f({\mathbf{x}})|d{\mathbf{x}}\right\\}$
$\displaystyle=O\left(1/\sqrt{nh_{n}^{d}}\right)+O(h_{n}).$

######  Lemma 4.

Let $g,h:{\mathbb{R}}\to{\mathbb{R}}$ be nonnegative with $\tilde{g}=\int
g(x)dx<\infty$ and $\tilde{h}=\int h(x)dx<\infty$. Then,

$\displaystyle\int\left|\frac{g(x)}{\tilde{g}}-\frac{h(x)}{\tilde{h}}\right|dx\leq
2\int\frac{\left|g(x)-h(x)\right|}{\max\\{\tilde{g},\tilde{h}\\}}dx.$

###### Proof.

This was proven for the $\ell_{2}$ norm in Lee et al. [15, Lemma 3.1], but the
argument works for any norm. We have

$\displaystyle\int\left|\frac{g(x)}{\tilde{g}}-\frac{h(x)}{\tilde{h}}\right|dx$
$\displaystyle\leq\int\left|\frac{g(x)}{\tilde{g}}-\frac{g(x)}{\tilde{h}}\right|dx+\int\left|\frac{g(x)}{\tilde{h}}-\frac{h(x)}{\tilde{h}}\right|dx$
$\displaystyle=\left|\frac{1}{\tilde{g}}-\frac{1}{\tilde{h}}\right|\tilde{g}+\frac{1}{\tilde{h}}\int\left|g(x)-h(x)\right|dx$
$\displaystyle=\frac{\left|\tilde{h}-\tilde{g}\right|}{\tilde{h}}+\frac{1}{\tilde{h}}\int\left|g(x)-h(x)\right|dx$
$\displaystyle\leq\frac{2}{\tilde{h}}\int\left|g(x)-h(x)\right|dx.$

By symmetry,

$\displaystyle\int\left|\frac{g(x)}{\tilde{g}}-\frac{h(x)}{\tilde{h}}\right|dx$
$\displaystyle\leq\frac{2}{\tilde{g}}\int\left|g(x)-h(x)\right|dx$

as well. The claim now follows. $\Box$

##  VII Acknowledgment

We thank the anonymous referees for a number of suggestions and corrections,
including catching a substantive mistake in an earlier version and suggesting
a way of fixing it.

## References

  * Bach and Jordan [2003] Francis R. Bach and Michael I. Jordan.  Beyond independent components: Trees and clusters.  _J. Mach. Learn. Res._ , 4:1205–1233, 2003.  URL http://jmlr.org/papers/v4/bach03a.html.
  * Barron [1989] Andrew R. Barron.  Uniformly Powerful Goodness of Fit Tests.  _The Annals of Statistics_ , 17(1):107 – 124, 1989.  doi: 10.1214/aos/1176347005.  URL https://doi.org/10.1214/aos/1176347005.
  * Barron et al. [1992] Andrew R. Barron, László Györfi, and Edward C. van der Meulen.  Distribution estimation consistent in total variation and in two types of information divergence.  _IEEE Transactions on Information Theory_ , 38(5):1437–1454, 1992.  doi: 10.1109/18.149496.
  * Beirlant and Györfi [1998] Jan Beirlant and László Györfi.  On the $l_{1}$-error in histogram density estimation: the multidimensional case.  _Journal of Nonparametric Statistics_ , 9(2):197–216, 1998.
  * Chow and Liu [1968] Chao-Kong Chow and Chao-Ning Liu.  Approximating discrete probability distributions with dependence trees.  _IEEE Transactions on Information Theory_ , 14(3):462–467, 1968.  doi: 10.1109/TIT.1968.1054142.
  * Cormen et al. [2009] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  _Introduction to algorithms_.  MIT Press, Cambridge, MA, third edition, 2009.  ISBN 978-0-262-03384-8.
  * Devroye and Györfi [1985] Luc Devroye and László Györfi.  _Nonparametric density estimation: the $L{{}_{1}}$ view_.  Wiley Series in Probability and Mathematical Statistics: Tracts on Probability and Statistics. John Wiley & Sons, Inc., New York, 1985.  ISBN 0-471-81646-9.
  * Gretton and Györfi [2010] Arthur Gretton and László Györfi.  Consistent nonparametric tests of independence.  _J. Mach. Learn. Res._ , 11:1391–1423, 2010.  URL http://portal.acm.org/citation.cfm?id=1859897.
  * Györfi and Kohler [2007] László Györfi and Michael Kohler.  Nonparametric estimation of conditional distributions.  _IEEE Transactions on Information Theory_ , 53(5):1872–1879, 2007.  doi: 10.1109/TIT.2007.894631.
  * Györfi and van der Meulen [1987] László Györfi and Edward C. van der Meulen.  Density-free convergence properties of various estimators of entropy.  _Computational Statistics & Data Analysis_, 5(4):425–436, 1987.  ISSN 0167-9473.  doi: https://doi.org/10.1016/0167-9473(87)90065-X.  URL https://www.sciencedirect.com/science/article/pii/016794738790065X.
  * Han et al. [2020] Yanjun Han, Jiantao Jiao, Tsachy Weissman, and Yihong Wu.  Optimal rates of entropy estimation over lipschitz balls.  _The Annals of Statistics_ , 48:3228–3250, 2020.
  * Horváth et al. [2020] Gábor Horváth, Edith Kovács, Roland Molontay, and Szabolcs Nováczki.  Copula-based anomaly scoring and localization for large-scale, high-dimensional continuous data.  _ACM Trans. Intell. Syst. Technol._ , 11(3):26:1–26:26, 2020.  doi: 10.1145/3372274.  URL https://doi.org/10.1145/3372274.
  * Kallenberg [1985] Wilbert C. M. Kallenberg.  On Moderate and Large Deviations in Multinomial Distributions.  _The Annals of Statistics_ , 13(4):1554 – 1580, 1985.  doi: 10.1214/aos/1176349755.  URL https://doi.org/10.1214/aos/1176349755.
  * Kruskal [1956] Joseph B. Kruskal.  On the shortest spanning subtree of a graph and the traveling salesman problem.  _Proceedings of the American Mathematical Society_ , 7(1):48–50, 1956.  URL http://www.jstor.org/stable/2033241.
  * Lee et al. [2014] James R. Lee, Shayan Oveis Gharan, and Luca Trevisan.  Multiway spectral partitioning and higher-order cheeger inequalities.  _J. ACM_ , 61(6):37:1–37:30, 2014.  doi: 10.1145/2665063.  URL https://doi.org/10.1145/2665063.
  * Liu et al. [2011] Han Liu, Min Xu, Haijie Gu, Anupam Gupta, John D. Lafferty, and Larry A. Wasserman.  Forest density estimation.  _J. Mach. Learn. Res._ , 12:907–951, 2011.  URL http://dl.acm.org/citation.cfm?id=2021032.
  * Quine and Robinson [1985] Malcolm P. Quine and John Robinson.  Efficiencies of Chi-Square and Likelihood Ratio Goodness-of-Fit Tests.  _The Annals of Statistics_ , 13(2):727 – 742, 1985.  doi: 10.1214/aos/1176349550.  URL https://doi.org/10.1214/aos/1176349550.
  * Silva and Narayanan [2010] Jorge Silva and Shrikanth Narayanan.  Nonproduct data-dependent partitions for mutual information estimation: Strong consistency and applications.  _IEEE Transactions on Signal Processing_ , 58(7):3497–3511, 2010.  doi: 10.1109/TSP.2010.2046077.
  * Tan et al. [2010] Vincent Y. F. Tan, Animashree Anandkumar, and Alan S. Willsky.  Learning gaussian tree models: Analysis of error exponents and extremal structures.  _IEEE Transactions on Signal Processing_ , 58(5):2701–2714, 2010.  doi: 10.1109/TSP.2010.2042478.
  * Tusnády [1977] Gábor Tusnády.  On Asymptotically Optimal Tests.  _The Annals of Statistics_ , 5(2):385 – 393, 1977\.  doi: 10.1214/aos/1176343804.  URL https://doi.org/10.1214/aos/1176343804.
  * Wang et al. [2005] Qing Wang, S.R. Kulkarni, and Sergio Verdú.  Divergence estimation of continuous distributions based on data-dependent partitions.  _IEEE Transactions on Information Theory_ , 51(9):3064–3074, 2005.  doi: 10.1109/TIT.2005.853314.
  * Wheeden and Zygmund [1977] Richard L. Wheeden and Antoni Zygmund.  _Measure and integral_.  Pure and Applied Mathematics, Vol. 43. Marcel Dekker, Inc., New York-Basel, 1977.  ISBN 0-8247-6499-4.  An introduction to real analysis.