Tree density estimation

We study the problem of estimating the density f(boldsymbol x) of a random vector boldsymbol X in mathbb Rd. For a spanning tree T defined on the vertex set 1,dots ,d, the tree density fT is a product of bivariate conditional densities. An optimal spanning tree minimizes the Kullback-Leibler divergence between f and fT. From i.i.d. data we identify an optimal tree T^* and efficiently construct a tree density estimate fn such that, without any regularity conditions on the density f, one has limn→ ∞ int |fn(boldsymbol x)-fT^*(boldsymbol x)|dboldsymbol x=0 a.s. For Lipschitz f with bounded support, mathbb E left int |fn(boldsymbol x)-fT^*(boldsymbol x)|dboldsymbol xright=Obig(n-1/4big), a dimension-free rate.