Theoretical properties of the log-concave maximum likelihood estimator of a multidimensional density

Introduction

Although work on shape-constrained density estimation dates back to the celebrated paper of Grenander (1956) on the estimation of a decreasing density on the positive half-line, it is in recent years that the area has enjoyed its most significant interest. This is partly because algorithmic and technological advances now allow the computation of estimators that would not previously have been feasible, and partly because statisticians now have more tools at their disposal for the study of the theoretical properties of these estimators.

The attraction of the use of these estimators is that, in contrast to alternative nonparametric density estimation methods such as those based on kernels or wavelets, they provide fully automatic procedures, with no smoothing parameters to choose. Such procedures are particularly desirable when the data are multidimensional, and the choice of (often multiple) smoothing parameters is particularly problematic.

The properties of the Grenander estimator are now quite well understood, thanks to the works of Marshall and Proschan (1965), Prakasa Rao (1969), Devroye (1987), Birgé (1989), van de Geer (1993) and Balabdaoui et al. (2009). Other examples of shape constraints on univariate densities that have been studied in the literature include convexity (Groeneboom, Jongbloed and Wellner, 2001; Dümbgen, Rufibach and Wellner, 2007) and $k$-monotonicity (Balabdaoui and Wellner, 2008). It is also known that a maximum likelihood estimator does not exist over the class of unimodal densities – cf. Birgé (1997).

In this paper, we study the statistical properties of the estimator. Importantly, our results do not assume that the underlying density is log-concave. To the best of our knowledge, such results have not been obtained before even for univariate data, but are of interest because in practice it is impossible to tell from a sample of data whether the assumption of log-concavity is satisfied. It is therefore natural to seek assurance that the estimator will behave sensibly if the condition is violated. In our main result (cf. Theorem 4 below), we prove under very mild conditions the existence and uniqueness of a log-concave density $f^{*}$ that minimises the Kullback–Leibler divergence from $f_{0}$ and show that there is an interval of values of $a$ for which

Convergence of log-concave densities

Notice in particular that if $X$ has density $f$, then Lemma 1 implies that the moment generating function of $X$ is finite in an open neighbourhood of the origin.

$f_{n}\rightarrow f$, $\mu$-almost everywhere

(a) This part of the proposition can be deduced from Theorems 2.8 and 2.10 of Dharmadhikari and Joag-Dev (1988). Their proof relies on a non-trivial correspondence between log-concave probability measures and log-concave densities, which in turn depends on several other facts about log-concavity – cf. Dharmadhikari and Joag-Dev (1988, pp.46–54). We give an alternative proof because it is perhaps a little more direct, and because it forms part of the proof of part (b) below.

Observe by the concavity of $\log f_{n_{k}}$ that if $x\in D_{k,\delta}$ then $2x_{0}-x\in B_{\delta}\setminus D_{k,\delta}$. It follows that $\mu(B_{\delta}\setminus D_{k,\delta})\geq\mu(B_{\delta})/2$. This means that we can apply Lebesgue’s differentiation theorem to choose $\delta>0$ small enough that for every $k$,

We conclude that $\liminf_{k}\int_{B_{\delta}}(f-f_{n_{k}})\geq\epsilon\mu(B_{\delta})/4$, a contradiction. Hence $\mu(E_{1})=0$.

Thus, without loss of generality, we may assume $f\leq\liminf_{n}f_{n}$. But by Fatou’s lemma,

so in fact we may assume $f=\liminf f_{n}$. Since $\liminf f_{n}$ is log-concave, this proves (a).

We may also assume that $|f(x)-f(x_{0})|\leq\epsilon/4$ for all $x\in B_{\delta}$. We conclude that for all $l$,

so $\limsup_{l}\int_{B_{\delta}}(f_{n_{k(l)}}-f)\leq-\frac{\epsilon}{8}\mu(B_{\delta})$, a contradiction.

Fix $a\in(0,a_{0})$, and let $\delta=a_{0}-a$. By Lemma 1, we can find $R>0$ such that \frac{1}{\|x\|}\{\phi(x)-\phi(0)\}\leq-\bigl{(}a+\frac{3\delta}{4}\bigr{)} for all $\|x\|\geq R/2$. We claim there exists $n_{0}$ such that

Now suppose that $f$ is continuous and let $\epsilon\in(0,1)$. Choose $R>0$ large enough that $f(x)+\sup_{n\geq n_{0}}f_{n}(x)\leq\epsilon e^{-a\|x\|}/2$ for all $\|x\|\geq R$. Then certainly,

Theoretical properties of the log-concave maximum likelihood estimator

There exists a constant $C>0$ such that, with probability one,

(a) Let $g(x)=\exp(-\|x\|+b)$, where the normalisation constant $b$ is chosen to ensure $g$ is a density, so that

The result follows immediately from this claim. To establish the claim, write $\phi=\log f$, and observe that

The first term on the right-hand side of (3.1) is zero, by the strong law of large numbers.

by Hoeffding’s inequality. The first Borel–Cantelli lemma then completes the proof of (a).

again by Hoeffding’s inequality. By the first Borel–Cantelli lemma, and arguing as in the proof of Lemma 3(a) above, we conclude that

Our next theorem is the main result in this paper and establishes desirable performance properties of the log-concave maximum likelihood estimator. We first recall that the Kullback–Leibler divergence of a density $f$ from $f_{0}$ is given by

Jensen’s inequality shows that the Kullback–Leibler divergence is non-negative, and equal to zero if and only if $f=f_{0}$ (almost everywhere). Thus in the case where $f_{0}$ is log-concave, Theorem 4 below shows that the log-concave maximum likelihood estimator $\hat{f}_{n}$ is strongly consistent in certain exponentially weighted total variation metrics. Convergence in exponentially weighted supremum norms also follows if $f_{0}$ is continuous. The theorem strengthens known results even in the univariate case, which include Corollary 1 of Pal, Woodroofe and Meyer (2007), where it was proved that $\hat{f}_{n}$ is strongly consistent in Hellinger distance, and Corollary 4.2 of Dümbgen and Rufibach (2009), where (weak) consistency of $\hat{f}_{n}$ in the unweighted total variation distance was established. (The observation that the mode of convergence in the univariate consistency result of Corollary 4.2 of Dümbgen and Rufibach (2009) could be strengthened was also made independently at around the same time in Schumacher, Hüsler and Dümbgen (2009).)

In the case where the model is misspecified, i.e. $f_{0}$ is not log-concave, we prove that the existence and uniqueness of a log-concave density $f^{*}$ that minimises the Kullback–Leibler divergence from $f_{0}$. Moreover, we show that the log-concave maximum likelihood estimator $\hat{f}_{n}$ converges in the same senses as in the previous paragraph to $f^{*}$. The natural practical interpretation is that provided $f_{0}$ is not too far from being log-concave, the estimator is still sensible.

We write $\log_{+}x=\max(\log x,0)$ and recall that $E$ denotes the support of $f_{0}$.

By the two integrability conditions, the log-concave density $g(x)=e^{-\|x\|+b}$ , where $b$ is a normalisation constant, satisfies $d_{KL}(f_{0},g)<\infty$. We can therefore pick a minimising sequence of log-concave densities $(f_{n})$ for the Kullback–Leibler divergence from $f_{0}$; in other words, the sequence $(f_{n})$ satisfies

Thus $\nu^{*}$ is absolutely continuous with respect to $\mu$, and we may write $f^{*}$ for its density with respect to $\mu$. By Proposition 2(a), $f^{*}$ is log-concave, and by Proposition 2(b), $f_{n_{k}}\rightarrow f^{*}$ almost everywhere. Finally, by Fatou’s lemma, we have

Thus $f^{*}$ does indeed minimise the Kullback–Leibler divergence from $f_{0}$ over the class of log-concave densities.

Suppose now that both $f_{1}^{*}$ and $f_{2}^{*}$ minimise the Kullback–Leibler divergence from $f_{0}$ over the class of log-concave densities. Defining

we see that $f^{*}$ is a log-concave density with

by the Cauchy–Schwarz inequality, with equality if and only if $f_{1}^{*}=f_{2}^{*}$, $\mu$-almost everywhere. This proves the claimed uniqueness property of $f^{*}$.

Combining this result with an application of the strong law of large numbers to the fourth term on the right-hand side of (3), we deduce that with probability one,

It follows by the monotone convergence theorem that with probability one,

Appendix

A log-concave density $f$ is bounded above and the version of $f$ that is closed attains its maximum.

for all $\|x\|>R$. Since $\phi$ is bounded (by Lemma 5), the result follows by choosing $b>\phi(0)$ sufficiently large. $\Box$

The following lemma is used in the proof of Theorem 4. The conclusion can be immediately strengthened using Proposition 2, and is stated in this way only for brevity.

as $b_{0}\rightarrow 0$. Here, the penultimate inequality uses (4.1). We deduce that the sequence $(f_{n})$ in the statement of the lemma satisfies the condition that there exists $C\geq 1$ such that

Then writing $B=\{x:f(x)\leq c\}$, we have for all $b\in(0,b_{0})$ that

We deduce that there exists $c>0$ such that

As in the proof of Theorem 4, we have from (4.2) that the sequence $(f_{n})$ is tight. Thus if $(f_{n_{k}})$ is an arbitrary subsequence of $(f_{n})$, then there exists a further subsequence $(f_{n_{k(l)}})$ and a log-concave density $f$ such that $\int|f_{n_{k(l)}}-f|\rightarrow 0$. But then, by the dominated and monotone convergence theorems,

with equality if and only if $f=f^{*}$ almost everywhere. By the hypothesis of the lemma, we must have $\int|f_{n_{k(l)}}-f^{*}|\rightarrow 0$. Since every subsequence of $(f_{n})$ has a further subsequence converging in total variation norm to $f^{*}$, we must have $\int|f_{n}-f^{*}|\rightarrow 0$. ∎

Acknowledgements: The second author is very grateful for helpful conversations with Richard Nickl and Michael Tehranchi.

References