Global rates of convergence in log-concave density estimation

Introduction

However, statistical procedures based on log-concavity, in common with other methods based on shape constraints, present substantial computational and theoretical challenges and these have therefore also been the focus of much recent research. For instance, the maximum likelihood estimator of a log-concave density, first studied by Walther (2002) in the case $d=1$, and by Cule, Samworth and Stewart (2010) for general $d$, plays a central role in all of the procedures mentioned in the previous paragraph. Dümbgen, Hüsler and Rufibach (2011) developed a fast, Active Set algorithm for computing the estimator when $d=1$, and this is implemented in the R package logcondens (Rufibach and Dümbgen, 2006; Dümbgen and Rufibach, 2011). For general $d$, a slower, non-smooth optimisation method based on Shor’s $r$-algorithm is implemented in the R package LogConcDEAD (Cule et al., 2007; Cule, Gramacy and Samworth, 2009); see also Koenker and Mizera (2010) for an alternative approximation approach based on interior point methods. On the theoretical side, through a series of papers (Pal, Woodroofe, and Meyer, 2007; Dümbgen and Rufibach, 2009; Seregin and Wellner, 2010; Schuhmacher and Dümbgen, 2010; Cule and Samworth, 2010; Dümbgen et al., 2011), we now have a fairly complete understanding of the global consistency properties of the log-concave maximum likelihood estimator (even under model misspecification).

Results on the global rate of convergence in log-concave density estimation are, however, less fully developed, and in particular have been confined to the case $d=1$. For a fixed true log-concave density $f_{0}$ belonging to a Hölder ball of smoothness $\beta\in$, Dümbgen and Rufibach (2009) studied the supremum distance over compact intervals in the interior of the support of $f_{0}$. They proved that the log-concave maximum likelihood estimator $\hat{f}_{n}$ based on a sample of size $n$ converges in these metrics to $f_{0}$ at rate $O_{p}(\rho_{n}^{-\beta/(2\beta+1)})$, where $\rho_{n}:=n/\log n$; thus $\hat{f}_{n}$ attains the same rates in the stated regimes as other adaptive nonparametric estimators that do not satisfy the shape constraint. Very recently, Doss and Wellner (2015) introduced a new bracketing argument to obtain a rate of convergence of $O_{p}(n^{-4/5})$ in squared Hellinger distance in the case $d=1$, again for a fixed true log-concave density $f_{0}$.

The second main purpose of this paper is to provide bounds on the supremum risk with respect to the squared Hellinger loss function of a particular estimator, namely the log-concave maximum likelihood estimator $\hat{f}_{n}$. The empirical process theory for studying maximum likelihood estimators is well-known (e.g. van der Vaart and Wellner, 1996; van de Geer, 2000), but relies on obtaining a bracketing entropy bound, which therefore becomes our main challenge. A first step is to show that after standardising the data, and using the affine equivariance of the estimator, we can reduce the problem to maximising over a class $\mathcal{G}$ of log-concave densities having a small mean and covariance matrix close to the identity (cf. Lemma 16 in the Appendix). In Corollary 6 in Section 3.2, we derive an integrable envelope function for such classes, relying on certain properties of distributional limits of sequences of log-concave densities developed in Section 3.1.

The first part of Section 4 is devoted to developing the key bracketing entropy results for the class $\mathcal{G}$. In particular, we show that the $\epsilon$-bracketing number of $\mathcal{G}$ in Hellinger distance $h$, denoted $N_{[]}(\epsilon,\mathcal{G},h)$ and defined at the beginning of Section 4, satisfies

The second term on the right-hand side of (1), which dominates the first when $d\geq 3$, is somewhat unexpected in view of standard bracketing bounds for classes of convex functions on a compact domain taking values in $$(e.g. van der Vaart and Wellner, 1996; Guntuboyina and Sen, 2013), where only the first term on the right-hand side of (1) appears. Roughly speaking, it arises from the potential complexity of the domains of the log-densities. Moreover, for$d\leq 3$, we obtain matching upper bounds, up to a logarithmic factor when$d=2$. These upper bounds rely on intricate calculations of the bracketing entropy of classes of bounded, concave functions on an arbitrary closed, convex domain. Further details on these bounds can be found in Section 4.

In the second part of Section 4, we apply the bracketing entropy bounds described above to deduce that

It is interesting to note that the logarithmic penalties that appear in (2) when $d=2,3$ occur for different reasons. When $d=2$, the penalty arises from the logarithmic gap between the lower and upper bounds for the relevant bracketing entropy. When $d=3$, the bracketing bound is sharp up to multiplicative constants, and the logarithmic penalty is due to the divergence of the bracketing entropy integral that plays the crucial role in the empirical process theory. The bracketing entropy lower bound in (1) suggests (but does not prove) that the log-concave maximum likelihood estimator will be rate suboptimal for $d\geq 4$; indeed, Birgé and Massart (1993) give an example of a situation where the maximum likelihood estimator has a suboptimal rate of convergence agreeing with that predicted by the same empirical process theory from which we derive our rates.

All of our proofs are deferred to the Appendix, where we also give various auxiliary results. We conclude this section by highlighting some related research on the pointwise rate of convergence of the log-concave maximum likelihood estimator. Balabdaoui, Rufibach, and Wellner (2009) proved that in the case $d=1$, if $f_{0}(x_{0})>0$ and $f_{0}$ is twice continuously differentiable in a neighbourhood of $x_{0}$ with $\phi_{0}^{\prime\prime}(x_{0})<0$, where $\phi_{0}:=\log f_{0}$, then $n^{2/5}\{\hat{f}_{n}(x_{0})-f_{0}(x_{0})\}$ converges to a non-degenerate limiting distribution related to the ‘lower invelope’ of an integrated Brownian motion process minus a drift term. Seregin and Wellner (2010) also derived a minimax lower bound for estimation of $f_{0}(x_{0})$ with respect to absolute error loss of order $n^{-2/(d+4)}$, provided that $x_{0}$ is an interior point of the domain of $\log f_{0}$ and $\log f_{0}$ is locally strongly concave at $x_{0}$.

Minimax lower bounds

This metric is both affine invariant and particularly convenient for studying maximum likelihood estimators. Adopting a minimax approach, we define the supremum risk

Theorem 1 reveals that when $d\geq 3$, the minimax lower bound rate for global loss functions is different from that for interior point estimation established under the local strong log-concavity condition in Seregin and Wellner (2010).

Our proof relies on a variant of Assouad’s cube method; see, for example, van der Vaart (1998, p. 347) or Tsybakov (2009, pp. 118–9). We handle the cases $d=1$ and $d\geq 2$ separately. For $d=1$, we bound the risk below by the risk over a finite subset of $\mathcal{F}_{1}$ consisting of densities that are perturbations of a semicircle $y=(r^{2}-x^{2})^{1/2}$ (it is convenient to raise the semicircle to be bounded away from zero on its domain so that the squared Hellinger distance can be bounded above in terms of the squared $L_{2}$-distance). The perturbations are constructed by first dividing the upper portion of the semicircle into $K$ pairs of arcs, with each element of the pair being a reflection in the $y$-axis of the other. For each $\alpha=(\alpha_{1},\ldots,\alpha_{K})^{T}\in\{0,1\}^{K}$ and $k=1,\ldots,K$, if $\alpha_{k}=1$, the $\alpha$th perturbation function $f_{\alpha}$ replaces the arc in the $k$th pair corresponding to $x>0$ with a straight line joining its endpoints and retains the other arc in the pair; if $\alpha_{k}=0$, we reverse the roles of the two arcs in the pair. Each function $f_{\alpha}$ is concave on its support $[-r,r]$, and is contructed to be a density; Assouad’s lemma can therefore be applied.

For $d\geq 2$, we instead construct uniform densities on perturbations of a closed Euclidean ball $B$. We first start with a constant function on $B$, and find $K$ pairs of disjoint caps in $B$. For $\alpha=(\alpha_{1},\ldots,\alpha_{K})^{T}\in\{0,1\}^{K}$ and $k=1,\ldots,K$, if $\alpha_{k}=1$, the $\alpha$th perturbation function $f_{\alpha}$ is zero for the first element of the pair, and agrees with the constant function for the second; if $\alpha_{k}=0$, the roles of the two elements of the pair are again reversed. Since the resulting densities $\{f_{\alpha}:\alpha\in\{0,1\}^{K}\}$ are uniform on sets of the same volume, we can compute Hellinger distances between them and again apply Assouad’s lemma.

An inspection of our proof further reveals that a minimax lower bound can also be obtained for the $L_{2}^{2}$ loss function. Note that in this case, the loss function is not affine invariant, so it makes sense to restrict attention to log-concave densities $f$ with a lower bound on the determinant of the corresponding covariance matrix $\Sigma_{f}$. The result obtained is that there exist $c_{d}^{\prime}>0$ such that for every $n\geq d+1$ and every $\rho>0$,

Convergence and integrable envelopes

Despite these chastening examples, we can still make the following statements with regard to the situation where $\nu$ is degenerate.

Finally in this subsection, we show that even in the situation where $\nu$ is degenerate, the convergence in distribution of log-concave measures implies much stronger forms of convergence. Similar results were proved in Theorem 2.1 and Proposition 2.2 of Schuhmacher, Hüsler and Dümbgen (2011) under the stronger assumption that $\nu$ has a log-concave Radon–Nikodym derivative with respect to $\mu_{d}$.

We note for later use that as an immediate corollary of Proposition 4, if $\Sigma_{n}$ denotes the covariance matrix corresponding to $\nu_{n}$, and $\Sigma$ denotes the covariance matrix corresponding to $\nu$, then $\Sigma_{n}\rightarrow\Sigma$.

2 Integrable envelopes for classes of log-concave densities

For every $\xi\geq 0$ and $\eta\in(0,1)$ satisfying $\xi<(1-\eta)^{1/2}/4$ and for every $\|x\|\leq(1-\eta)^{1/2}/4-\xi$, we have

As an ancillary result, we can also give a precise envelope for the class of one-dimensional log-concave densities having mean zero and with no variance restriction. Let

While the envelope function here is not integrable, this result is reminiscent of the fact that $f(x)\leq 1/(2x)$ for all $x>0$, when $f$ is a convex density on $(0,\infty)$, which was proved and exploited in Groeneboom, Jongbloed and Wellner (2001).

Bracketing entropy bounds and global rates of convergence of the log-concave maximum likelihood estimator

Let $\eta_{d}>0$ be taken from Lemma 16 in the Appendix.

(i) There exist $\overline{K}_{1},\overline{K}_{2},\overline{K}_{3}\in(0,\infty)$ such that

for all $\epsilon>0$, where $\log_{++}(x):=\max(1,\log x)$.

Crucially, we can afford to be more liberal in the accuracy of our coverage as $k$ increases, because the contribution to the Hellinger distance is small when the log-density has a negative value of large magnitude. This enables us to show that the total number of brackets required to construct a bracketing set with Hellinger distance at most $\epsilon$ between the brackets is bounded above by an expression not depending on $k_{0}$. For the $(k_{0}+1)$th class, we can modify the brackets used for the $k_{0}$th class in a straightforward way.

We are now in a position to state our main result on the supremum risk of the log-concave maximum likelihood estimator for the squared Hellinger loss function.

Let $\hat{f}_{n}$ denote the log-concave maximum likelihood estimator based on a sample of size $n$. Then, for the squared Hellinger loss function,

The proof of this theorem first involves standardising the data and using affine equivariance to reduce the problem to that of bounding the supremum risk over the class of log-concave densities with mean vector 0 and identity covariance matrix. Writing $\hat{g}_{n}$ for the log-concave maximum likelihood estimator for the standardised data, we show in Lemma 16 in the Appendix that

As well as using various known results on the relationship between the mean vector and covariance matrix of the log-concave maximum likelihood estimator in relation to its sample counterparts, the main step here is to show that, provided none of the sample covariance matrix eigenvalues are too large, the only way an eigenvalue of the covariance matrix corresponding to the maximum likelihood estimator can be small is if an eigenvalue of the sample covariance matrix is small.

The other part of the proof of Theorem 9 is to control

This can be done by appealing to empirical process theory for maximum likelihood estimators, and using the Hellinger bracketing entropy bounds developed in Theorem 8.

Acknowledgements: The work of the second author was supported by an EPSRC Early Career Fellowship and a grant from the Leverhulme Trust. The authors are very grateful for helpful comments on an earlier draft from Charles Doss, Roy Han and Jon Wellner, as well as anonymous reviewers.

Appendix

For $k=1,\ldots,K$, we also define intervals

and set $R_{k,1}:=-R_{k,0}=\{-x:x\in R_{k,0}\}$. Writing $y_{k}:=r(1-\epsilon^{2})^{1/2}\cos\theta_{2k-1}$, for $k=1,\ldots,K$, we define auxiliary functions

Finally, then, we can define $\bar{\mathcal{F}}_{1}:=\{f_{\alpha}:\alpha=(\alpha_{1},\ldots,\alpha_{K})^{T}\in\{0,1\}^{K}\}$, where

Moreover, if $|\alpha_{k}-\beta_{k}|=1$, then

is a monotonically increasing function of $\theta\in[0,\pi/3]$. To check this, note that by differentiating under the integral, splitting the range of integration into two intervals of equal length, and then making the substitution $t\mapsto 2(1-\epsilon^{2})^{1/2}\sin\theta-t$ in the left interval, we find that

But $J((1-\epsilon^{2})^{1/2}\sin\theta,\theta)=J(\sin(\theta+\theta_{1}),\theta)=0$, and for $t\in[(1-\epsilon^{2})^{1/2}\sin\theta,\sin(\theta+\theta_{1})]$, we have

We deduce that $J(t,\theta)\geq 0$ for all $t\in[(1-\epsilon^{2})^{1/2}\sin\theta,\sin(\theta+\theta_{1})]$, and our desired monotonicity as a function of $\theta$ follows. Hence, for any $\alpha,\beta\in\{0,1\}^{K}$, we have

This calculation shows that, for the squared Hellinger loss function, we can take $\gamma:=\frac{31}{420}r^{3}\epsilon^{5}$ in condition (i) of Lemma 10.

We now turn to condition (ii). Since $h^{2}(f_{\alpha},f_{\beta})\leq L_{2}^{2}(f_{\alpha},f_{\beta})/(4c_{0})$ for all $f_{\alpha},f_{\beta}\in\bar{\mathcal{F}}_{1}$, it suffices to find an upper bound for $L_{2}^{2}(f_{\alpha},f_{\beta})$ when $\|\alpha-\beta\|_{0}=1$. Using our monotonicity property again, observe that in that case,

This shows that in condition (ii) of Lemma 10, we may take $C:=nr^{3}\epsilon^{5}/(2c_{0})$. From Lemma 10, and using the fact that $\lfloor\frac{\pi}{6\theta_{1}}\rfloor\epsilon\geq\frac{\pi}{24\arcsin(1/2)}=1/4$ for $\epsilon\leq 1/2$, we conclude that

The case $d\geq 2$: We again apply Lemma 10, but as described in Section 2 the construction of our finite subset $\bar{\mathcal{F}}_{d}$ of $\mathcal{F}_{d}$ is quite different, being based around uniform densities on perturbations of a Euclidean ball. Let

We can now define $\bar{\mathcal{F}}_{d}:=\{f_{\alpha}:\alpha=(\alpha_{1},\ldots,\alpha_{K})^{T}\in\{0,1\}^{K}\}$, where

Again, it remains to verify the conditions of Lemma 10. First, if $\alpha,\beta\in\{0,1\}^{K}$, then

For the squared Hellinger loss function, we may therefore take $\gamma:=\frac{4\times 15^{(d+1)/2}}{3^{1/2}\times 16^{(d+1)/2}\pi(d+1)^{1/2}}\epsilon^{d+1}$ in condition (i) of Lemma 10. On the other hand, if $\alpha=(\alpha_{1},\ldots,\alpha_{K})^{T},\beta=(\beta_{1},\ldots,\beta_{K})^{T}\in\{0,1\}^{K}$ satisfy $\|\alpha-\beta\|_{0}=1$, then

This shows that we may take $C:=\frac{2}{(d+1)^{1/2}}n\epsilon^{d+1}$ in condition (ii) of Lemma 10. We conclude from Lemma 10 that

2 Proofs from Section 3

Hence for $R>\|x^{*}\|$, we have $f_{n_{k(l)}}(x)<1/k(l)$ for all $x\in A_{R,\eta}$ and $l\geq l_{0}$. Since $A_{R,\eta}$ is open, we have for all $R>\|x^{*}\|$ and $\eta>0$ that

Thus $\mu_{d}(U_{n,\log\epsilon})\leq(M_{n}-\log\epsilon)^{d}\mu_{d}(U_{n,M_{n}-1})\leq(2M_{n})^{d}\mu_{d}(U_{n,M_{n}-1})$. But

If $\theta_{0}\in U$ and $\theta_{1}\in U^{\perp}$, then

so $\Theta=\Theta_{0}\oplus U^{\perp}$, where $\Theta_{0}$ contains 0. The fact that $\Theta_{0}$ is convex follows immediately from the convexity of the exponential function, while the fact that $\Theta_{0}$ is relatively open follows from the proof of Proposition 2.2 of Schuhmacher, Hüsler and Dümbgen (2011), once we note from Part 2 of Proposition 3 that $\nu$ has a log-concave Radon–Nikodym derivative with respect to $\mu_{k,U+a}$.

where the convergence follows from Proposition 2.2 and Theorem 2.1 of Schuhmacher, Hüsler and Dümbgen (2011).

It follows that for $K\geq\max\{2(a+\epsilon),a+9\epsilon\}$,

as $K\rightarrow\infty$. We deduce that the sequence $(e^{\theta^{T}X_{n}})$ is uniformly integrable, so the result follows by Theorem A on p.14 of Serfling (1980). ∎

for all $m$. Then, since the level sets of each $f_{n}$ are convex, for each $m$,

as $m\rightarrow\infty$. This contradicts the fact that each $f_{n}$ is a density, and establishes our claim.

But now, if $k\geq k_{0}$ and $x\in\bar{B}_{d}(0,R_{0})\setminus\bar{B}_{d}(x_{0},\delta)$, then we can set

Observe that $\|x_{1,k}-x_{0}\|=\delta/2$. Thus, for all $k\geq k_{0}$,

Now, for $\|x\|>R_{0}$, we can find $x_{2,k}\in\bar{B}_{d}(0,R_{0})\setminus B_{d}(0,R_{0})$ and $\lambda\in(0,1)$ such that $x_{2,k}=\lambda x_{0}+(1-\lambda)x$. Notice that

so $\lambda\geq 2(\|x\|-R_{0})/(2\|x\|+R_{0})$. It follows that for $k\geq k_{0}$,

Our claim is that this forces $\|x_{*}\|>1/4$. To see this, let $a:=\|x_{*}\|$, let $m\in[0,a]$ be such that $f_{1}^{*}(m)=\max_{x_{1}\in[0,a]}f_{1}^{*}(x_{1})=:M$ and let $\phi_{1}^{*}:=\log f_{1}^{*}$. Note that

Hence $\inf_{u\in[-2a,0]}f_{1}^{*}(u)\leq M/4$, and in fact this infimum must be attained when $u=-2a$, so $f_{1}^{*}(-2a)\leq M/4$. Now observe that

Here, we used (5.2), as well as $m\leq a$ and $\log M-\phi_{1}^{*}(-2a)\geq 2\log 2$ to obtain the final inequality. We deduce that

It follows that $\|x_{0}\|>(1-\eta)^{1/2}/4-\xi$, as required. ∎

Now let $x_{0}>0$ and suppose, for a contradiction, that $f^{*}\in\mathcal{F}_{1}^{0}$ satisfies $f^{*}(x_{0})>1/x_{0}$. We must have $f^{*}(0)<f^{*}(x_{0})$ (otherwise $\int_{0}^{x_{0}}f^{*}>1$), so writing $\phi^{*}:=\log f^{*}$, we have that

We deduce that $\phi^{*}(0)\geq\phi^{*}(x_{0})-1$. It follows that there exists $x^{*}\in(-\infty,0]$ such that $f^{*}(x)<\frac{1}{x_{0}}e^{-(x_{0}-x)/x_{0}}$ for $x<x^{*}$, and $f^{*}(x)>\frac{1}{x_{0}}e^{-(x_{0}-x)/x_{0}}$ for $x^{*}<x\leq x_{0}$. But then we have for every $x\leq x_{0}$ that

say, with strict inequality for every $x\leq x_{0}$ except possibly when $x=x_{0}$, since $F(x_{0})=1$. We deduce that

a contradiction. A similar argument handles the case $x_{0}<0$. ∎

3 Proofs from Section 4

Now let $\mathcal{F}_{y_{k}}(\mathcal{D}):=\{e^{\phi}:\phi\in\cup_{D\in\mathcal{D}}\Phi_{y_{k}}(D)\}$. Write

where $K_{d}$ and $K_{d}^{\circ}$ are the constants defined in Propositions 12 and 15 below respectively. Let

We claim that for $k=1,\ldots,k_{0}$ and $d=1,2,3$, we have

Moreover, when $d=1$ the cardinality of this bracketing set is

where we have used the facts that $e^{y_{0}/2}\epsilon^{1/2}\leq e^{y_{k_{0}-1}/2}\epsilon^{1/2}\leq\epsilon_{00}^{1/2}\leq 1$ and $2e^{y_{0}/4}\epsilon^{1/2}\log(1/\epsilon)\leq 8e^{y_{k_{0}-1}/4}\epsilon^{1/4}\leq 8\epsilon_{00}^{1/4}\leq 8$. When $d=2$, the cardinality is

Finally, when $d=3$, the cardinality of the bracketing set is

When $d=1$ the cardinality of this bracketing set is

as required. When $d=2$, the cardinality is

Finally, when $d=3$, the cardinality of the bracketing set is

This establishes the claim (7) by induction.

Since $k_{0}$ depends on $\epsilon$, it is important to observe that for all $k=1,\ldots,k_{0}$,

for all $\epsilon\in(0,\epsilon_{00}]$ and $d=1,2,3$. By a simple scaling argument, we deduce that for any $b>0$,

for all $\epsilon\in(0,b^{1/2}\epsilon_{00}]$.

We now show how to translate and scale brackets appropriately for other cubes. Let $A_{0,d},B_{0,d}>0$ be as in Corollary 6(a). Define

where $\|\mathbf{j}\|^{2}:=\sum_{k=1}^{d}j_{k}^{2}$. Note from Corollary 6(a) that

Note that to obtain the expression for $B_{2}$, we have used the fact that

using the definition of $j_{0}$ and $\epsilon_{01,d}$. Moreover, the cardinality of the bracketing set is

Since $\epsilon\in(0,\epsilon_{01,d}]$ was arbitrary, we conclude that

for all $\epsilon\in(0,\epsilon_{02,d}]$, where $\epsilon_{02,d}:=\epsilon_{01,d}(B_{1}+B_{2})$ and where

where, as in the proof of Proposition 12 below, we have used the fact that \log_{++}(a/\epsilon)\leq\bigl{\{}2+\frac{2\log_{++}(a)}{\log_{++}(e/a)}\bigr{\}}\log_{++}(1/\epsilon) for all $a,\epsilon>0$. Now let

and let $\overline{K}_{d}:=\overline{\overline{K}}_{d}h_{d}(\epsilon_{02,d})/h_{d}(\epsilon_{03,d})$. For $\epsilon\in(\epsilon_{02,d},\epsilon_{03,d}]$, we have

Finally, if $\epsilon>\epsilon_{03,d}$, we can use a single bracketing pair $\{f^{L},f^{U}\}$, with $f^{L}(x):=0$ and $f^{U}(x)$ defined to be the integrable envelope function from Corollary 6(a) with $\xi=1$ and $\eta=\eta_{d}$ there. Note that $h(f^{U},f^{L})\leq\epsilon_{03,d}$. This proves the upper bound.

Set $K:=\lfloor\frac{\zeta^{*}}{\arcsin(\epsilon^{1/2})}\rfloor$ and, for $k=0,1,\ldots,K$, let $w_{k}:=k\arcsin(\epsilon^{1/2})$, so that $\zeta^{*}-2\epsilon^{1/2}\leq w_{K}\leq\zeta^{*}$. We also define

For $k=1,\ldots,K$, we also define $R_{k,0}:=(r\sin w_{2k-2},r\sin w_{2k})$ and set $R_{k,1}:=-R_{k,0}=\{-x:x\in R_{k,0}\}$. Writing $y_{k}:=r(1-\epsilon)^{1/2}\cos w_{2k-1}$, for $k=1,\ldots,K$, we define auxiliary functions

We can now define $\mathcal{F}_{1}^{L}:=\{f_{\alpha}:\alpha=(\alpha_{1},\ldots,\alpha_{K})^{T}\in\{0,1\}^{K}\}$, where

and $\mathcal{F}_{1}^{L}\subseteq\mathcal{F}_{1}$. Now

since $\eta_{1}^{2}/400\leq\eta_{1}^{1/2}/(2^{1/2}\times 50)$. We also compute

Finally, since f_{\alpha}(x)\geq\bigl{\{}r^{2}(1-\epsilon)-x^{2}\bigr{\}}^{1/2}-r\cos w_{2K} for $|x|\leq r(1-\epsilon)^{1/2}\sin w_{2K}$, we have

Since the bracketing number at level $\epsilon$ is bounded below by the packing number at level $2\epsilon$, we can let $\epsilon_{11,1}:=\epsilon_{10,1}/8$, and conclude that

for $\epsilon\in(0,\epsilon_{11,1}]$, where $\underline{K}_{1}:=\frac{0.148}{8^{1/2}16}$.

Finally, we turn to the case $d\geq 2$. Set \epsilon_{10,d}:=\min\bigl{\{}10^{-4},\frac{\eta_{d}^{1/2}}{4(d+2)^{1/2}}\bigr{\}} and fix $\epsilon\in(0,\epsilon_{10,d}]$. Here, we recall the finite subset \bar{\mathcal{F}}_{d}=\bigl{\{}f_{\alpha}:\alpha\in\{0,1\}^{K}\bigr{\}} of uniform densities on closed, convex sets from the proof of Theorem 1 in the case $d\geq 2$, and set

where we have used the bound on $c_{K,\epsilon}$ from (5) and the fact that $\frac{\Gamma(1+d/2)}{\Gamma(\frac{1+d}{2})}\leq(d+1)^{1/2}/2^{1/2}$. Now, for any $j=1,\ldots,d$,

Finally, for $j,k\in\{1,\ldots,d\}$ with $j\neq k$, we have

We deduce from the Gerschgorin circle theorem (Gerschgorin, 1931; Gradshteyn and Ryzhik, 2007) that if $\Sigma_{\alpha,r}$ denotes the covariance matrix corresponding to $f_{\alpha,r}$, then

Setting $\epsilon_{d}:=\frac{1}{2}\frac{15^{(d+1)/4}}{10^{1/2}2^{(d+1)/2}16^{(d+1)/4}}\epsilon_{10,d}$, we conclude that

We can now apply Theorem 17 in Section 5.4.3, which provides an exponential tail inequality controlling the performance of a maximum likelihood estimator in Hellinger distance in terms of a bracketing entropy integral. It is an immediate consequence of Theorem 7.4 of van de Geer (2000), although our notation is slightly different (in particular her definition of Hellinger distance is normalised with a factor of $1/\sqrt{2}$) and we have used the fact (apparent from her proofs) that, in her notation, we may take $C=2^{13/2}$.

It follows from this and our bracketing entropy bound (Theorem 8) that

We now consider three different cases, assuming throughout that $n\geq d+1$ so that, with probability 1, the log-concave maximum likelihood estimator exists and is unique.

For $d=1$, we set $\delta_{n}:=2^{-1/2}M_{1}^{1/2}n^{-2/5}$, where M_{1}:=\max\bigl{\{}\bigl{(}\frac{2^{37/2}}{3}\bigr{)}^{8/5}\overline{K}_{1}^{4/5},2^{33}\bigr{\}}. Then

Moreover, $\delta_{n}\leq 2^{-17}M_{1}n^{-3/10}=2^{-16}n^{1/2}\delta_{n}^{2}$. We conclude by Theorem 17 that for $t\geq M_{1}$,

where the final bound follows because $tn^{1/5}/2^{28}\geq\log 2$.

For $d=2$, we set $\delta_{n}:=2^{-1/2}M_{2}^{1/2}n^{-1/3}\log^{1/2}n$, where M_{2}:=\max\bigl{\{}2^{23}\overline{K}_{2}^{2/3}5^{4/3}/3,2^{33}\bigr{\}}. Let $n_{0,2}$ be large enough that $\delta_{n}\leq 1/e$ for $n\geq n_{0,2}$. Then, for such $n$,

where we have used the fact that $2^{1/2}M_{2}^{-1/2}\log^{-1/2}n\leq n^{1/3}$ in the penultimate inequality. We conclude that for $n\geq n_{0,2}$ and $t\geq M_{2}$, we have

For $d=3$, the entropy integral diverges as $\delta\searrow 0$, so we cannot bound the bracketing entropy integral by replacing the lower limit with zero. Nevertheless, we can set $\delta_{n}:=2^{-1/2}M_{3}^{1/2}n^{-1/4}\log^{1/2}n$, where M_{3}:=\bigl{\{}2^{33/2}10\overline{K}_{3}^{1/2},2^{33}\bigr{\}}. For $t\geq M_{3}$, we have

Let $\rho_{n,1}^{2}:=n^{4/5}$, $\rho_{n,2}^{2}:=n^{2/3}(\log n)^{-1}$ and $\rho_{n,3}^{2}:=n^{1/2}(\log n)^{-1}$. We conclude that if $n\geq\max(n_{0},d+1)$ (and also $n\geq n_{0,2}$ when $d=2$), then

4 Auxiliary results

The following lemma is an immediate consequence of Assouad’s lemma as stated in, e.g. van der Vaart (1998, p. 347) or Tsybakov (2009, pp. 118–9).

for all $\alpha,\beta\in\{0,1\}^{K}$, where $\|\alpha-\beta\|_{0}$ denotes the Hamming distance between $\alpha$ and $\beta$

There exists $C\in(0,1)$ such that for every $\alpha,\beta\in\{0,1\}^{K}$ with $\|\alpha-\beta\|_{0}=1$, we have

Let $d\geq 2$. For any $\epsilon\in(0,1/2]$, we have

Notice that for any $x\in\mathcal{H}_{j}\cap\mathcal{S}_{1}$, we have

where $B(\frac{d-1}{2},\frac{1}{2}):=\int_{0}^{1}t^{\frac{d-1}{2}-1}(1-t)^{-1/2}\,dt$ denotes the beta function at $(\frac{d-1}{2},\frac{1}{2})$. Since $B(\frac{d-1}{2},\frac{1}{2})\leq\pi(d-1)^{-1/2}$ and $(1-t)^{-1/2}\geq 1$ for $t\in[0,1)$, the upper bound for $N_{2\epsilon}$ follows.

For the lower bound, observe that for any $x\in\mathcal{S}_{1}$, we can find $j^{*}\in\{1,\ldots,N_{2\epsilon}\}$ such that $\|x-x_{j^{*}}\|\leq 2\epsilon$. Thus, if for $j=1,\ldots,N_{2\epsilon}$, we let

Since $B(\frac{d-1}{2},\frac{1}{2})\geq(2\pi)^{1/2}(d-1)^{-1/2}$ and $(1-t)^{-1/2}\leq\{1-(4\epsilon^{2}-4\epsilon^{4})\}^{-1/2}$ for $t\in[0,4\epsilon^{2}-4\epsilon^{4}]$, the lower bound follows. ∎

4.2 Auxiliary results for the proof of Theorem 8

for all $\epsilon\in(0,\epsilon_{20,d}]$. Now set

Then, for $\epsilon\in(\epsilon_{20,d},a_{d})$,

For $\epsilon\geq a_{d}$, we can use the single bracketing pair $\{\psi^{L},\psi^{U}\}$ with $\psi^{L}(x):=0$ and $\psi^{U}(x):=1$ for $x\in D^{\prime}$, noting that $L_{1}(\psi^{U},\psi^{L})=\mu_{d}(D^{\prime})\leq a_{d}$. Thus, for $\epsilon\geq a_{d}$,

Since \log_{++}(a/\epsilon)\leq\bigl{\{}2+\frac{2\log_{++}(a)}{\log_{++}(e/a)}\bigr{\}}\log_{++}(1/\epsilon) for all $a,\epsilon>0$, the result therefore holds with

We now provide a bracketing entropy bound for classes of uniformly bounded concave functions on arbitrary domains in $^{d}$ when $d=1,2,3$. These results build on the work of Guntuboyina and Sen (2013), who study metric (as opposed to bracketing) entropy and rectangular domains, and a recent result of Gao and Wellner (2015), who study various special classes of domains, including $d$-dimensional simplices. For convenience, we state the result to which we will appeal below.

Some basic properties of the sets $\tensor*[_{\eta}]{D}{}$ and $D^{\eta]}$ are given below.

Let $D$, $\tensor*[_{\eta}]{D}{}$ and $D^{\eta]}$ be as above. Then

$\tensor*[_{\eta}]{D}{}$ and $D^{\eta]}$ are compact and convex.

If $0\leq\eta_{1}\leq\eta_{2}$, then $(\tensor*[_{\eta_{1}}]{D}{})^{\eta_{2}]}\subseteq D^{(\eta_{2}-\eta_{1})]}$ and $\tensor*[_{\eta_{1}}]{{(D^{\eta_{2}]})}}{}=D^{(\eta_{2}-\eta_{1})]}$.

If $\eta_{1},\eta_{2}>0$, then $\tensor*[_{\eta_{1}}]{{(\tensor*[_{\eta_{2}}]{D}{})}}{}=\tensor*[_{\eta_{1}+\eta_{2}}]{D}{}$ and $(D^{\eta_{1}]})^{\eta_{2}]}=D^{(\eta_{1}+\eta_{2})]}$.

(i) Certainly $\tensor*[_{\eta}]{D}{}$ is bounded because $\tensor*[_{\eta}]{D}{}\subseteq D$. To show $\tensor*[_{\eta}]{D}{}$ is closed, let $(x_{n})\in\tensor*[_{\eta}]{D}{}$ with $x_{n}\rightarrow x$, and suppose that $\|w-x\|\leq\eta$. Then, setting $w_{n}:=x_{n}+w-x$, we have $w_{n}\in D$ and $w_{n}\rightarrow w$, so $w\in D$ since $D$ is closed. We conclude that $x\in\tensor*[_{\eta}]{D}{}$, as required. To show $\tensor*[_{\eta}]{D}{}$ is convex, let $x_{1},x_{2}\in\tensor*[_{\eta}]{D}{}$ and $\lambda\in$, and suppose that $\|w-\{(1-\lambda)x_{1}+\lambda x_{2}\}\|\leq\eta$. Define $w_{1}:=x_{1}+w-(1-\lambda)x_{1}-\lambda x_{2}\in D$ and $w_{2}:=x_{2}+w-(1-\lambda)x_{1}-\lambda x_{2}\in D$. Then

so $(1-\lambda)x_{1}+\lambda x_{2}\in\tensor*[_{\eta}]{D}{}$, as required. Thus $\tensor*[_{\eta}]{D}{}$ is compact and convex.

For the second part, $D^{\eta]}$ is bounded, because

Now suppose that $(x_{n})$ is a sequence in $D^{\eta]}$ with $x_{n}\rightarrow x$, so we can write $x_{n}=y_{n}+\eta z_{n}$, where $y_{n}\in D$ and $\|z_{n}\|\leq 1$. Since $D$ and $\bar{B}_{d}(0,1)$ are compact, there exist $y\in D$, $z\in\bar{B}_{d}(0,1)$ and integers $1\leq n_{1}<n_{2}<\ldots$ such that $y_{n_{k}}\rightarrow y$ and $z_{n_{k}}\rightarrow z$. By uniqueness of limits, $x=y+\eta z$, so $x\in D^{\eta]}$, which shows that $D^{\eta]}$ is closed. Finally, if $x_{1},x_{2}\in D^{\eta]}$ and $\lambda\in$, then we can find $y_{1},y_{2}\in D$ and $z_{1},z_{2}\in\bar{B}_{d}(0,1)$ such that $x_{1}=y_{1}+\eta z_{1}$ and $x_{2}=y_{2}+\eta z_{2}$. But then since $D$ is convex and $\|(1-\lambda)z_{1}+\lambda z_{2}\|\leq(1-\lambda)\|z_{1}\|+\lambda\|z_{2}\|\leq 1$, we have

(ii) Let $x_{0}\in(\tensor*[_{\eta_{1}}]{D}{})^{\eta_{2}]}$. If $x_{0}\in D$, then certainly $x_{0}\in D^{(\eta_{2}-\eta_{1})]}$, so assume $x_{0}\notin D$. Then there exists $y_{0}\in\tensor*[_{\eta_{1}}]{D}{}$ such that $\eta_{1}<\|x_{0}-y_{0}\|\leq\eta_{2}$, and

Hence $x_{0}\in D^{(\eta_{2}-\eta_{1})]}$, so $(\tensor*[_{\eta_{1}}]{D}{})^{\eta_{2}]}\subseteq D^{(\eta_{2}-\eta_{1})]}$.

For the second part, suppose that $x\in\tensor*[_{\eta_{1}}]{{(D^{\eta_{2}]})}}{}$. If $x\in D$, then $x\in D^{(\eta_{2}-\eta_{1})]}$ and we are done; otherwise, let $z$ denote the orthogonal projection of $x$ onto $D$. Writing

we have that $\|y-x\|=\eta_{1}$, so $y\in D^{\eta_{2}]}$. Moreover, for every $t\in D$,

so $z$ is the orthogonal projection of $y$ onto $D$. We deduce that $\|x-z\|+\eta_{1}=\|y-z\|\leq\eta_{2}$, so $x\in D^{(\eta_{2}-\eta_{1})]}$.

Conversely, let $x\in D^{(\eta_{2}-\eta_{1})]}$. Then there exists $z\in D$ such that $\|x-z\|\leq\eta_{2}-\eta_{1}$. If $\|y-x\|\leq\eta_{1}$, then

so $y\in D^{\eta_{2}]}$. Hence $x\in\tensor*[_{\eta_{1}}]{{(D^{\eta_{2}]})}}{}$, as required.

(iii) Let $x\in\tensor*[_{\eta_{1}}]{{(\tensor*[_{\eta_{2}}]{D}{})}}{}$, and let $\|z-x\|\leq\eta_{1}+\eta_{2}$. If $\|z-x\|\leq\eta_{1}$, then $z\in\tensor*[_{\eta_{2}}]{D}{}\subseteq D$; otherwise, $\eta_{1}<\|z-x\|\leq\eta_{1}+\eta_{2}$. In that case,

satisfies $\|y-x\|\leq\eta_{1}$, so $y\in\tensor*[_{\eta_{2}}]{D}{}$. But then $\|z-y\|=\|z-x\|-\eta_{1}\leq\eta_{2}$, so $z\in D$. Hence $x\in\tensor*[_{\eta_{1}+\eta_{2}}]{D}{}$.

Conversely, suppose that $x\in\tensor*[_{\eta_{1}+\eta_{2}}]{D}{}$ and that $\|y-x\|\leq\eta_{1}$. If $\|z-y\|\leq\eta_{2}$, then $\|z-x\|\leq\eta_{1}+\eta_{2}$, so $z\in D$. Hence $y\in\tensor*[_{\eta_{2}}]{D}{}$ and $x\in\tensor*[_{\eta_{1}}]{{(\tensor*[_{\eta_{2}}]{D}{})}}{}$, as required.

For the second part, let $x\in(D^{\eta_{1}]})^{\eta_{2}]}$. Then there exists $y\in D^{\eta_{1}]}$ such that $\|y-x\|\leq\eta_{2}$, and $z\in D$ such that $\|z-y\|\leq\eta_{1}$. But then $\|z-x\|\leq\eta_{1}+\eta_{2}$, so $x\in D^{(\eta_{1}+\eta_{2})]}$.

Conversely, suppose that $x\in D^{(\eta_{1}+\eta_{2})]}$, so there exists $z\in D$ such that $\|z-x\|\leq\eta_{1}+\eta_{2}$. If $x\in D^{\eta_{1}]}$, then certainly $x\in(D^{\eta_{1}]})^{\eta_{2}]}$; otherwise, we have $\|z-x\|>\eta_{1}$, and can set

In that case, $\|y-z\|=\eta_{1}$, so $y\in D^{\eta_{1}]}$, and $\|x-y\|=\|x-z\|-\eta_{1}\leq\eta_{2}$, so $x\in(D^{\eta_{1}]})^{\eta_{2}]}$, as required.

(iv) If $x\in\tensor*[_{\eta}]{D}{}$, then for each $j=1,\ldots,m$, we have $w_{j}:=x+\eta b_{j}\in D$. Thus for each $j$,