Nonparametric estimation of multivariate convex-transformed densities

Introduction and background

Because the class of multivariate log-concave densities contains the class of multivariate normal densities and is preserved under a number of important operations (such as convolution and marginalization), it serves as a valuable nonparametric surrogate or replacement for the class of normal densities. Further study of the class of log-concave densities from this perspective has been undertaken by Schuhmacher, Hüsler and Duembgen (2009).

Such generalizations of log-concave densities and log-concave measures based on means of order $r$ have been introduced by a series of authors, sometimes with differing terminology, apparently starting with Avriel (1972), and continuing with Borell (1975), Brascamp and Lieb (1976), Prékopa (1973), Rinott (1976) and Uhrin (1984). A nice summary of these connections is given by Dharmadhikari and Joag-Dev (1988). These authors also present results concerning the preservation of $r$-concavity under a variety of operations, including products, convolutions and marginalization.

Despite the longstanding and current rapid development of the properties of such classes of densities on the probability side, very little has been done from the standpoint of nonparametric estimation, especially when $d\geq 2$.

Here is an outline of the rest of the paper. All of our main results are presented in Section 2. Section 2.1 gives definitions and basic properties of the transformations involved. Section 2.2 establishes existence of the maximum likelihood estimators for both increasing and decreasing transformations $h$ under suitable conditions on the function $h$. In Section 2.3, we give statements concerning consistency of the estimators, both in the Hellinger metric and in uniform metrics under natural conditions. In Section 2.4, we present asymptotic minimax lower bounds for estimation in these classes under natural curvature hypotheses. We conclude the section with a brief discussion of conjectures concerning attainability of the minimax rates by the maximum likelihood estimators. All of the proofs are given in Section 3.

Supplementary material and some proofs omitted here are available in Seregin and Wellner (2010). There, we also summarize a number of definitions and key results from convex analysis in an Appendix, Section A. We use standard notation from convex analysis; see “Notation” for a (partial) list.

2 Convex-transformed density estimation

Main results

the function $h(y)$ is $o(|y|^{-\alpha})$ for some $\alpha>d$ as $y\to-\infty$;

if $y_{\infty}<+\infty$, then $h(y)\asymp(y_{\infty}-y)^{-\beta}$ for some $\beta>d$ as $y\uparrow y_{\infty}$;

the function $h$ is continuously differentiable on the interval $(y_{0},y_{\infty})$.

Note that the assumption (I.1) is satisfied if $y_{0}>-\infty$.

the function $h(y)$ is $o(y^{-\alpha})$ for some $\alpha>d$ as $y\to+\infty$;

if $y_{\infty}>-\infty$, then $h(y)\asymp(y-y_{\infty})^{-\beta}$ for some $\beta>d$ as $y\downarrow y_{\infty}$;

if $y_{\infty}=-\infty$, then $h(y)^{\gamma}h(-Cy)=o(1)$ for some $\gamma,C>0$ as $y\to-\infty$;

the function $h$ is continuously differentiable on the interval $(y_{\infty},y_{0})$.

Note that the assumption (D.1) is satisfied if $y_{0}<+\infty$. We now define the decreasing class of densities $\mathcal{P}(h)$.

For a monotone transformation $h$, we denote by $\mathcal{G}(h)$ the class of all closed proper convex functions $g$ such that $h\circ g$ belongs to a monotone class $\mathcal{P}(h)$. The following lemma allows us to compare models defined by increasing or decreasing transformations $h$.

Consider two decreasing (or increasing) models $\mathcal{P}(h_{1})$ and $\mathcal{P}(h_{2})$. If $h_{1}=h_{2}\circ f$ for some convex function $f$, then $\mathcal{P}(h_{1})\subseteq\mathcal{P}(h_{2})$.

The argument below is for a decreasing model. For an increasing model, the proof is similar. If $f(x)>f(y)$ for some $x<y$, then $f$ is decreasing on $(-\infty,x)$, $f(-\infty)=+\infty$ and therefore $h_{2}$ is constant on $(f(x),+\infty)$, and we can redefine $f(y)=f(x)$ for all $y<x$. Thus, we can always assume that $f$ is nondecreasing.

For any convex function $g$, the function $f\circ g$ is also convex. Therefore, if $p=h_{1}\circ g\in\mathcal{P}(h_{1})$, then $p=h_{2}\circ f\circ g\in\mathcal{P}(h_{2})$.

In this section, we discuss several examples of monotone models. The first two families are based on increasing transformations $h$.

This increasing model is defined by $h(y)=e^{y}$. Limit points are $y_{0}=-\infty$ and $y_{\infty}=\infty$. Assumption (I.1) holds for any $\alpha>d$. These classes of densities were considered by An (1998), who established several useful preservation properties. In particular, log-convexity is preserved under mixtures [An (1998), Proposition 3] and under marginalization [An (1998), Remark 8, page 361].

We now consider some models based on decreasing transformations $h$.

This decreasing model is defined by the transform $h(y)=e^{-y}$. Limit points are $y_{0}=+\infty$ and $y_{\infty}=-\infty$. Assumption (D.1) holds for any $\alpha>d$. Assumption (D.3) holds for any $\gamma>C>0$.

Many parametric models are subsets of this model: in particular, uniform, Gaussian, gamma, beta, Gumbel, Fréchet and logistic densities are all log-concave.

This family of decreasing models is defined by the transforms $h(y)=y_{+}^{-s}$ for $s>d$. Limit points are $y_{0}=+\infty$ and $y_{\infty}=0$. Assumption (D.1) holds for any $\alpha\in(d,s)$. Assumption (D.2) holds for $\beta=s$. As noted in Section 1, the model $\mathcal{P}(y_{+}^{1/r})=\mathcal{P}(y_{+}^{-s})$ (with $r=-1/s<0$) corresponds to the class of $r$-concave densities. From Lemma 2.5, we have the following inclusion:

The models defined by power transformations include some parametric models with heavier-than-exponential tails. Several examples, including the multivariate generalizations of Pareto, Student-$t$, and $F$-distributions are discussed in Borell (1975)—none of these families are log-concave; see Johnson and Kotz (1972) and Seregin and Wellner (2010) for explicit computations.

Borell (1975) developed a framework which unifies log-concave and power-convex densities and gives an interesting characterization for these classes. Here, we briefly state the main result.

holds for all $\varnothing\neq A,B\subseteq C$ and all $\theta\in(0,1)$. We define $\mathcal{M}^{\circ}_{s}(C)$ as a subfamily of $\mathcal{M}_{s}(C)$ which consists of probability measures such that the affine hull of its support has dimension $d$. Here, $\mu_{*}$ is the inner measure corresponding to $\mu$ and the cases $s=0,\infty$ are defined by continuity.

One of the main results of Borell (1975), Prékopa (1973) and Rinott (1976) is as follows.

Theorem 2.11 provides a special case of what has come to be known as the Borell–Brascamp–Lieb inequality; see, for example, Dharmadhikari and Joag-Dev (1988) and Brascamp and Lieb (1976). The current terminology is apparently due to Cordero-Erausquin, McCann and Schmuckenschläger (2001).

2 Existence of the maximum likelihood estimators

is the maximum likelihood estimator of $p$ over the class $\mathcal{P}(h)$, assuming it exists and is unique. We also write $\hat{g}_{n}$ for the MLE of $g$. We first state our main results concerning existence and uniqueness of the MLEs for the classes $\mathcal{P}(h)$.

Suppose that $h$ is an increasing transformation satisfying assumptions (I.1)–(I.3). The MLE $\hat{p}_{n}$ then exists almost surely for the model $\mathcal{P}(h)$.

Suppose that $h$ is a decreasing transformation satisfying assumptions (D.1)–(D.4). The MLE $\hat{p}_{n}$ then exists almost surely for the model $\mathcal{P}(h)$ if

Uniqueness of the MLE is known for the log-concave model $\mathcal{P}(e^{-y})$; see, for example, Dümbgen and Rufibach (2009) for $d=1$ and Cule, Samworth and Stewart (2010) for $d\geq 1$. For a brief further comment, see Section 2.5.

3 Consistency of the maximum likelihood estimators

Once existence of the MLEs is ensured, our attention shifts to other properties of the estimators: our main concern in this subsection is consistency. While, for a decreasing model, it is possible to prove consistency without any restrictions, for an increasing model, we need the following assumptions about the true density $h\circ g_{0}$:

the function $g_{0}$ is bounded by some constant $C<y_{\infty}$;

Note that for $d=1$, the assumption (I.5) follows from assumption (I.4) and integrability of $\log(1/x)$ at zero. This assumption is also true if $P$ has finite marginal densities.

Our main results about increasing models are as follows.

For an increasing model $\mathcal{P}(h)$, where $h$ satisfies assumptions (I.1)–(I.3) and for the true density $h\circ g_{0}$ which satisfies assumptions (I.4)–(I.6), the sequence of MLEs $\{\hat{p}_{n}=h\circ\hat{g}_{n}\}$ is Hellinger consistent: $H(\hat{p}_{n},p_{0})=H(h\circ\hat{g}_{n},h\circ g_{0})\to_{a.s.}0$.

The results about decreasing models can be formulated in a similar way.

For a decreasing model $\mathcal{P}(h)$, where $h$ satisfies assumptions (D.1)–(D.4), the sequence of MLEs $\{\hat{p}_{n}=h\circ\hat{g}_{n}\}$ is Hellinger consistent:

4 Local asymptotic minimax lower bounds

In this section, we establish local asymptotic minimax lower bounds for any estimator of several functionals of interest on the family $\mathcal{P}(h)$ of convex-transformed densities. We start with several general results following Jongbloed (2000) and then apply them to estimation at a fixed point and to mode estimation.

First, we define minimax risk as in Donoho and Liu (1991).

where $t_{n}$ ranges over all possible estimators of $Tp$ based on $X_{1},\ldots,X_{n}$.

The main result (Theorem 1) in Jongbloed (2000) can be formulated as follows.

Let $\{p_{n}\}$ be a sequence of densities in $\mathcal{P}$ such that $\limsup_{n\to\infty}\sqrt{n}H(p_{n},p)\leq\tau$ for some density $p$ in $\mathcal{P}$. Then,

It will be convenient to reformulate this result in the following form.

Suppose that for any $\varepsilon>0$ small enough, there exists $p_{\varepsilon}\in\mathcal{P}$ such that for some $r>0$, $\lim_{\varepsilon\to 0}\varepsilon^{-1}|Tp_{\varepsilon}-Tp|=1$ and

There then exists a sequence $\{p_{n}\}$ such that

where $R_{1}$ is the risk which corresponds to $l(x)=|x|$.

Corollary 2.21 shows that for a fixed change in the value of the functional $T$, a family $p_{\varepsilon}$ which is closer to the true density $p$ with respect to Hellinger distance provides a sharper lower bound. This suggests that for the functional $T$ which depends only on the local structure of the density, we would like our family $\{p_{\varepsilon}\}$ to deviate from $p$ also locally. Below, we formally define such local deviations.

We call a family of measurable functions $\{p_{\varepsilon}\}$ a deformation of a measurable function $p$ if $p_{\varepsilon}$ is defined for any $\varepsilon>0$ small enough, $\lim_{\varepsilon\to 0}\mathop{\operatorname{ess}\sup}|p-p_{\varepsilon}|=0$ and there exists a bounded family of real numbers $r_{\varepsilon}$ and a point $x_{0}$ such that

If, in addition, we have $\lim_{\varepsilon\to 0}r_{\varepsilon}=0$, then we say that $\{p_{\varepsilon}\}$ is a local deformation at $x_{0}$.

Since, for a deformation $p_{\varepsilon}$, we have $\mu[{\operatorname{supp}}|p_{\varepsilon}(x)-p(x)|]>0$ for every $\varepsilon>0$, there exists $\delta>0$ such that $\mu\{x\dvtx|p_{\varepsilon}(x)-p(x)|>\delta\}>0$ and thus the $L_{r}$-distance from $p_{\varepsilon}$ to $p$ is positive for all $\varepsilon>0$. Note that this is always true if $p$ and $p_{\varepsilon}$ are continuous at $x_{0}$ and $p_{\varepsilon}(x_{0})\neq p(x_{0})$.

We can now state our lower bound for estimation of the convex-transformed density value at a fixed point $x_{0}$. This result relies on the properties of strongly convex functions, as described in Appendix S.A.4, and can be applied to both increasing and decreasing classes of convex-transformed densities.

where the constant $C(d)$ depends only on the dimension $d$.

If, in addition, $g$ is twice continuously differentiable at $x_{0}$ and $\nabla^{2}g(x_{0})$ is positive definite, then, by Lemma S.A.22, we have $\operatorname{curv}_{x_{0}}g=\det(\nabla^{2}g(x_{0}))$.

and the analog of Corollary 2.21 then has the following form.

Suppose that for any $\varepsilon>0$ small enough, there exists $p_{\varepsilon}\in\mathcal{P}$ such that for some $r>0$,

There then exists a sequence $\{p_{n}\}$ such that

The construction of a lower bound for the functional $T$ is similar to the procedure we presented for estimation of $p=h\circ g$ at a fixed point $x_{0}$. Again, we use two opposite deformations: one is local and changes the functional value, the other is a convex combination with a fixed deformation and negligible-in-Hellinger-distance computation. However, in this case, the minimax rate also depends on the growth rate of $g$.

where the constant $C(d)$ depends only on the dimension $d$, and the metric $s(x,y)$ is defined as $\|x-y\|$.

If, in addition, $g$ is twice continuously differentiable at $x_{0}$ and $\nabla^{2}g(x_{0})$ is positive definite, then, by Lemma S.A.22, we have $\operatorname{curv}_{x_{0}}g=\det(\nabla^{2}g(x_{0}))$ and $g$ is locally Hölder continuous at $x_{0}$ with exponent $\gamma=2$ and any constant $L>\|\nabla^{2}g(x_{0})\|$.

Since $\operatorname{curv}_{x_{0}}g>0$, there exists a constant $C$ such that $C\|x-x_{0}\|^{2}\leq|g(x)-g(x_{0})|$ and thus we have $\gamma\in(0,2]$.

5 Conjectures concerning uniqueness of MLEs

There exist counterexamples to uniqueness for nonconvex transformations $h$ which satisfy assumptions (D.1)–(D.4). They suggest that uniqueness of the MLE does not depend on the tail behavior of the transformation $h$, but rather on the local properties of $h$ in neighborhoods of the optimal values $\hat{g}_{n}(X_{i})$. We conjecture that uniqueness holds for all monotone models if $h$ is convex and $h/|h^{\prime}|$ is nondecreasing convex. Further work on these uniqueness issues is needed.

6 Conjectures about rates of convergence for the MLEs

We conjecture that the (optimal) rate of convergence $n^{2/(d+4)}$ appearing in Theorem 2.23 for estimation of $f(x_{0})$ will be achieved by the MLE only for $d=2,3$. For $d=4$, we conjecture that the MLE will come within a factor $(\log n)^{-\gamma}$ (for some $\gamma>0$) of achieving the rate $n^{1/4}$, but for $d>4$, we conjecture that the rate of convergence will be the suboptimal rate $n^{1/d}$. This conjectured rate-suboptimality raises several interesting further issues:

Can we find alternative estimators (perhaps via penalization or sieve methods) which achieve the optimal rates of convergence?

For interesting subclasses, do maximum likelihood estimators remain rate-optimal?

Proofs

for $y<+\infty$, the sublevel sets $\operatorname{lev}_{y}g$ are bounded and we have

The sublevel set $\operatorname{lev}_{y}g$ has the same dimension as $\mathop{\operatorname{dom}}g$ [Theorem 7.6 in Rockafellar (1970)], which is $d$. By Lemma S.A.1, this set is bounded when $y<y_{0}$. Therefore, it is enough to prove that $\operatorname{lev}_{y_{0}}g$ is bounded for $y_{0}<+\infty$.

Since $h\circ g$ is a density, we have $\inf g<y_{0}$. If $g$ is constant on $\mathop{\operatorname{dom}}g$, then, for all $y\in[\inf g,+\infty)$, we have $\operatorname{lev}_{y}g=\operatorname{lev}_{\inf g}h$ and it is therefore bounded. Otherwise, we can choose $\inf h\leq y_{1}<y_{2}<y_{0}$. Then, $\mu[\operatorname{lev}_{y_{2}}g]<\infty$ and, by Lemma S.A.3, we have $\mu[\operatorname{lev}_{y_{0}}g]<\infty$. The argument above shows that $\operatorname{lev}_{y_{0}}g$ is also bounded.

2. This follows from the fact that $g$ is continuous and $\operatorname{lev}_{y}g$ is bounded and nonempty for $y>\inf g$.

Using the Fubini–Tonelli theorem, we have, with $L_{a}^{c}\equiv(\operatorname{lev}_{a}g)^{c}$,

By assumption (D.1), the function $-[h\log h](y)$ is decreasing to zero as $y\to+\infty$ and we have $0<-[h\log h](y)<Cy^{-d-\alpha^{\prime}}$ for $C$ large enough and $\alpha^{\prime}\in(0,\alpha)$ as $y\rightarrow+\infty$.

By Lemma 3.1, the level sets $\operatorname{lev}_{y}g$ are bounded and since $h\circ g\in\mathcal{P}(h)$, we have $\inf g>y_{\infty}$. Therefore, the integral exists if and only if the integral

for some $a>y_{\infty}$. Choosing $a$ large enough and using Lemma 3.2 for the decreasing transformation $h_{1}(y)=y^{-d-\alpha^{\prime}}$, we obtain

By Lemma S.A.3, we have $\mu(\operatorname{lev}_{y}g)=O(y^{d})$ and therefore the last integral is finite.

Let $B$ be a ball such that $K\subset B$. Let $c$ be such that $h(c)=1/\mu[B]$. The function $g\equiv c+\delta(\cdot\mathop{|}B)$ then belongs to $\mathcal{G}(h)$.

2 Proofs for existence results

If an MLE for the model $\mathcal{P}(h)$ exists, then it maximizes the functional

Here are the corresponding results for decreasing transformations $h$.

The bounds provided by the following key lemma are the remaining preparatory work for proving existence of the MLE in the case of increasing transformations.

By Lemma S.1.1, we have $h\circ g(X_{i})\leq\frac{d!}{d^{d}V({X_{i}})}$, which gives the upper bounds $C(X_{i},X,\varepsilon)$. By assumption, we have

which gives the uniform lower bound $c(X_{i},X,\varepsilon)$ for all $X_{i}\in X$. Since, by Lemma S.1.1, $g(0)\geq g(X_{i})$, we also obtain $c(0,X,\varepsilon)$.

If $y_{\infty}=+\infty$, then, for a fixed $y\in(c,+\infty)$, we have

If $y_{\infty}<+\infty$, then for a fixed $y\in(c,y_{\infty}]$, we have

Thus, there exists $s_{0}\in(c,y_{\infty})$ such that $T(s_{0})>1$. This implies that $g(0)<s_{0}$. Since $s_{0}$ depends only on $X_{a}$ and $\min c(X_{i},X,\varepsilon)$, this gives an upper bound $C(0,X,\varepsilon)$.

Since we have only a finite number of possible choices for $X_{a}$, we have obtained $c(x_{0},X,\varepsilon)$, which completes the proof.

Before proving existence of the MLE for a decreasing transformation family, we need two lemmas.

Consider a decreasing model $\mathcal{P}(h)$. Let $\{g_{k}\}$ be a sequence of convex functions from $\mathcal{G}(h)$ and let $\{n_{k}\}$ be a nondecreasing sequence of positive integers $n_{k}\geq n_{d}$ such that for some $\varepsilon>-\infty$ and $\rho>0$, the following is true:

There then exists $m>y_{\infty}$ such that $g_{k}\geq m$ for all $k$.

For given observations $X=(X_{1},\ldots,X_{n})$ such that $n\geq n_{d}$, there exist constants $m>y_{\infty}$ and $M$ which depend only on observations $X$ and $\varepsilon$ such that for any $g\in\mathcal{N}(h,X,\varepsilon)$, we have $m\leq g(x)\leq M$ on $\operatorname{conv}(X)$.

An arbitrary sequence of functions $\{g_{k}\}$ from $\mathcal{N}(h,X,\varepsilon)$ satisfies the conditions of Lemma 3.11 with $n_{k}\equiv n$ and the same $\varepsilon$ and $\rho$ constructed above. Therefore, the sequence $\{g_{k}\}$ is bounded below by some constant greater than $y_{\infty}$. Thus, the family of functions $\mathcal{N}(h,X,\varepsilon)$ is uniformly bounded below by some $m>y_{\infty}$.

Consider any $g\in\mathcal{N}(h,X,\varepsilon)$. Let $M_{g}$ be the supremum of $g$ on $\mathop{\operatorname{dom}}h$. By Theorem 32.2 in Rockafellar (1970), the supremum is obtained at some $X_{M}\in X$ and therefore $M_{g}<y_{0}$. Let $m_{g}$ be the minimum of $g$ on $X$. We have $h(m_{g})^{n-1}h(M_{g})\geq e^{n\varepsilon}$ and

Thus, we have obtained an upper bound $M$ which depends only on $m$ and $X$.

Finally, we have to add the “almost surely” clause since we assumed that the points $X_{i}$ are in general position.

3 Proofs for consistency results

We begin with proofs for some technical results which we will use in the consistency arguments for both increasing and decreasing models. The main argument for proving Hellinger consistency proceeds along the lines of the proof given in the case of $d=1$ by Pal, Woodroofe and Meyer (2007) and in the log-concave case for $d>1$ by Schuhmacher and Duembgen (2010).

Consider a monotone model $\mathcal{P}(h)$. Suppose that the true density $h\circ g_{0}$ and the sequence of MLEs $\{\hat{g}_{n}\}$ have the following properties:

for $\varepsilon>0$ small enough. The sequence of the MLEs is then Hellinger consistent: $H(h\circ\hat{g}_{n},h\circ g_{0})\to_{a.s.}0$.

The next lemma allows us to obtain pointwise consistency once Hellinger consistency is proved.

Let us denote by $L^{0}_{a}$ and $L^{k}_{a}$ the sublevel sets $L^{0}_{a}=\operatorname{lev}_{a}g_{0}$ and $L^{n}_{a}=\operatorname{lev}_{a}\hat{g}_{n}$, respectively. Consider $\Omega_{0}$ such that $\Pr[\Omega_{0}]=1$ and $H^{2}(h\circ\hat{g}_{n}^{\omega},h\circ g_{0})\to 0$, where $\hat{g}_{n}^{\omega}$ is the MLE for $\omega\in\Omega_{0}$. For all $\omega\in\Omega_{0}$, we have

We need a general property of the bracketing entropy numbers.

Finally, we prove consistency for decreasing models. We need a general property of convex sets.

Let $D$ be a convex compact set. By Theorem 8.4.2 in Dudley (1999), the class $\mathcal{A}\cap D$ has a finite set of $\varepsilon$-brackets. Since the class $\mathcal{A}$ is invariant under rescaling, the result follows from Lemma 3.15.

For a decreasing model $\mathcal{P}(h)$, the sequence of MLEs $\hat{g}_{n}$ is almost surely uniformly bounded below.

We will apply Lemma 3.11 to the sequences $\hat{g}_{n}$ and $\{n\}$. By the strong law of large numbers and Lemma 3.4, we have

Choose some $a\in(0,d/n_{d})$. Then, for any set $S$ such that $\mu[S]=\rho\equiv a/h(\min g_{0})$, where $\min g_{0}$ is attained by Lemma 3.1, we have

Now, let $A_{n}=\operatorname{lev}_{a_{n}}\hat{g}_{n}$ be sets such that $\mu[A_{n}]=\rho$. Then, by Lemma 3.16, we have

By Lemma 3.17, we have $\inf\hat{g}_{n}\geq A$ for some $A>y_{\infty}$. Therefore, by Lemma 3.2 applied to the decreasing transformation $\log[\varepsilon+h(y)]-\log\varepsilon$, it follows that

The closure $\bar{A}$ is compact and thus, for $n$ large enough, we have, with probability one, ${\sup_{\bar{A}}}|\hat{g}_{n}-g_{0}|<\delta$, which implies that ${\sup_{\bar{A}}}|h\circ\hat{g}_{n}-h\circ g_{0}|<\varepsilon$ since the range of values of $g_{0}$ on $\bar{A}$ is $[m,a]$. The set $\partial A$ is compact and therefore $\hat{g}_{n}$ attains its minimum $m_{n}$ on this set at some point $x_{n}$. By construction,

We have $x_{0}\in A\cap\operatorname{lev}_{a-\delta}\hat{g}_{n}$ and $\hat{g}_{n}\geq m_{n}>a-\delta$ on $\partial A$. Thus, by convexity, we have $\operatorname{lev}_{a-\delta}\hat{g}_{n}\subset A$ and for $x\notin\bar{A}$, we have

This shows that for any $\varepsilon>0$ small enough, we will have

with probability one as $n\to\infty$. This concludes the proof.

4 Proofs for lower bound results

We will use the following lemma for computing the Hellinger distance between a function and its local deformation.

In order to apply Corollary 2.21, we need to construct deformations so that they still belong to the class $\mathcal{G}$. The following lemma provides a technique for constructing such deformations.

Note that $g_{\theta,\delta}$ is not a local deformation of $g$. {pf*}Proof of Theorem 2.23 Our statement is nontrivial only if the curvature $\operatorname{curv}_{x_{0}}g>0$ or, equivalently, there exists a positive definite $d\times d$ matrix $G$ such that the function $g$ is locally $G$-strongly convex. Then, by Lemma S.A.17, this means that there exists a convex function $q$ such that, in some neighborhood $O(x_{0})$ of $x_{0}$, we have

The plan of the proof is as follows: we introduce families of functions $\{D_{\varepsilon}(g;x_{0},v)\}$ and $\{D_{\varepsilon}^{*}(g;x_{0})\}$ and prove that these families are local deformations. Using these deformations as building blocks, we construct two types of deformations, $\{h\circ g^{+}_{\varepsilon}\}$ and $\{h\circ g^{-}_{\varepsilon}\}$, of the density $h\circ g$, which belong to $\mathcal{P}(h)$. These deformations represent positive and negative changes in the value of the function $g$ at the point $x_{0}$. We then approximate the Hellinger distances using Lemma 3.18. Finally, applying Corollary 2.21, we obtain lower bounds which depend on $G$. We complete the proof by taking the supremum of the obtained lower bounds over all $G\in\mathcal{SC}(g;x_{0})$. Under the mild assumption of strong convexity of the function $g$, both deformations give the same rate and structure of the constant $C(d)$. However, it is possible to obtain a larger constant $C(d)$ for the negative deformation if we assume that $g$ is twice differentiable. Note that, by the definition of $\mathcal{P}(h)$, the function $g$ is a closed proper convex function.

Let us define a function $D_{\varepsilon}(g;x_{0},v_{0})$ for a given $\varepsilon>0$, $x_{0}\in\mathop{\operatorname{dom}}g$ and $v_{0}\in\partial g(x_{0})$ as follows: $D_{\varepsilon}(g;x_{0},v_{0})(x)=\max(g(x),l_{0}(x)+\varepsilon)$, where $l_{0}(x)=\langle v_{0},x-x_{0}\rangle+g(x_{0})$ is a support plane to $g$ at $x_{0}$ (see Figure 1). Since $l_{0}+\varepsilon$ is a support plane to $g+\varepsilon$, we have $g\leq D_{\varepsilon}(g;x_{0},v_{0})\leq g+\varepsilon$ and thus $\mathop{\operatorname{dom}}D_{\varepsilon}(g;x_{0},v_{0})=\mathop{\operatorname{dom}}g$. As a maximum of two closed convex functions, $D_{\varepsilon}(g;x_{0},v_{0})$ is a closed convex function. For a given $x_{1}$, we have $D_{\varepsilon}(g;x_{0},v_{0})(x_{1})=g(x_{1})$ if and only if

see Figure 2. Both functions $D_{\varepsilon}(g;x_{0},v_{0})$ and $D^{*}_{\varepsilon}(g;x_{0})$ are convex by construction and, as the next lemma shows, have similar

properties. However, the argument for $D^{*}_{\varepsilon}(g;x_{0})$ is more complicated.

$D^{*}_{\varepsilon}(g;x_{0})$ is a closed proper convex function such that $g-\varepsilon\leq D^{*}_{\varepsilon}(g;x_{0})\leq g$ and $\mathop{\operatorname{dom}}D^{*}_{\varepsilon}(g;x_{0})=\mathop{\operatorname{dom}}g$;

if $v_{0}\in\partial g(x_{0})$, then $x_{0}\in\partial g^{*}(v_{0})$ and $D_{\varepsilon}(g;x_{0},v_{0})=(D^{*}_{\varepsilon}(g^{*};v_{0}))^{*}$.

Therefore, $v\in\partial g(x_{1})$. In particular,

We can represent $D_{\varepsilon}^{*}(g^{*};x_{0})$ as the maximal convex minorant of $g$ defined by $g=\min(g,g(x_{0})-\varepsilon+\delta(\cdot|x_{0}))$. For $x\in\mathop{\operatorname{dom}}g$, by Lemma S.A.10, $g^{*}(v_{0})+g(x_{0})=\langle v_{0},x_{0}\rangle$. Thus,

for some $v\in\partial g(x_{0})$. By Lemma S.A.7, we have

Therefore, for the point $x_{1}$ in the neighborhood $O(x_{0})$ where the decomposition (16) is true, condition (17) is equivalent to

Since $\langle w_{0},x_{1}-x_{0}\rangle+q(x_{0})$ is a support plane to $q(x)$, the inequality (17) is satisfied if $2^{-1}(x_{1}-x_{0})^{T}G(x_{1}-x_{0})\geq\varepsilon$, which is the complement of an open ellipsoid $B_{G}(x_{0},\sqrt{2\varepsilon})$ defined by $G$ with center at $x_{0}$. For $\varepsilon$ small enough, this ellipsoid will belong to the neighborhood $O(x_{0})$. Since $|D_{\varepsilon}(g;x_{0},v_{0})-g|\leq\varepsilon$, this proves that the family $D_{\varepsilon}(g;x_{0},v_{0})$ is a local deformation.

In the same way, the condition (18) is equivalent to

or $2^{-1}(x_{1}-x_{0})^{T}G(x_{1}-x_{0})+q(x_{0})-\varepsilon\geq\langle w_{1},x_{0}-x_{1}\rangle+q(x_{1})$, which is satisfied if we have $2^{-1}(x_{1}-x_{0})^{T}G(x_{1}-x_{0})\geq\varepsilon$. Since $|D_{\varepsilon}^{*}(g;x_{0})-g|\leq\varepsilon$, this proves that the family $D_{\varepsilon}^{*}(g;x_{0})$ is also a local deformation. Thus, we have proven the following.

For $r>0$ small enough, $h^{\prime}\circ g(x)$ is nonzero and the decomposition (16) is true on $B(x_{0};r)$. Let us fix some $v_{0}\in\partial g(x_{0})$, some $x_{1}\in B(x_{0};r)$ such that $x_{1}\neq x_{0}$ and some $y_{1}\in\partial g(x_{1})$. We fix $\delta$ such that equation (14) of Lemma 3.19 is true for the transformation $\sqrt{h}$ and $r=2$, and also $x_{0}\notin\overline{B_{G}(x_{1};\sqrt{2\delta})}$. Then, by Lemma 3.21, for all $\varepsilon>0$ small enough, the support sets $\operatorname{supp}[D_{\varepsilon}(g;x_{0},v_{0})-g]$ and $\operatorname{supp}[D_{\delta}^{*}(g;x_{1})-g]$ do not intersect; that is, these two deformations do not interfere.

We can now prove Theorem 2.23. The argument below is identical for $g^{+}_{\varepsilon}$ and $g^{-}_{\varepsilon}$, so we will give the proof only for $g^{+}_{\varepsilon}$. We define deformations $g^{+}_{\varepsilon}$ and $g^{-}_{\varepsilon}$ by means of the following lemma.

For all $\varepsilon>0$ small enough, there exist $\theta_{\varepsilon}^{+},\theta_{\varepsilon}^{-}\in(0,1)$ such that the functions $g^{+}_{\varepsilon}$ and $g^{-}_{\varepsilon}$ defined by

Next, we will show that $\theta_{\varepsilon}^{+}$ goes to zero fast enough so that $g^{+}_{\varepsilon}$ is very close to $D_{\varepsilon}(g;x_{0},v_{0})$. Since supports do not intersect, we have

where both integrals have the same sign. For the first integral, by Lemma 3.18, we have

The second integral is monotone in $\theta^{+}_{\varepsilon}$ and, by Lemma 3.19, we have

Thus, we have $\theta_{\varepsilon}^{+}=O(\varepsilon^{1+d/2})$ and

where $S(0,1)$ is the $d$-dimensional sphere of radius $1$.

For the second part, by Lemma 3.19, we obtain

Taking the supremum over all $G\in\mathcal{SC}(g;x_{0})$, we obtain the statement of the theorem.

5 Indications of proofs for conjectured rates

for all (small) $\epsilon>0$, for a constant $K$ depending only on $C$ and $d$. Then, after an argument to transfer this covering number bound to a bracketing entropy bound for $\mathcal{P}(h)$ with respect to Hellinger distance $H$, it follows from oscillation bounds for empirical processes [cf. van der Vaart and Wellner (1996), Theorems 3.4.1 and 3.4.4] that rates of convergence of $\hat{p}_{n}$ with respect to Hellinger distance are determined by $r_{n}^{2}\phi(1/r_{n})\asymp\sqrt{n}$ with

Assuming that the bound of (20) can be carried over to $\log N_{[]}(\epsilon,\mathcal{P}(h),H)$ sufficiently closely, routine calculations show that the expected rates of convergence of $\hat{p}_{n}$ to $p_{0}=h(g_{0})$ with respect to Hellinger distance $H$ are

Based on these heuristics, we expect that the MLE $\hat{p}_{n}$ will be rate efficient if $d\leq 3$, but rate inefficient (not attaining the optimal rate $n^{2/(d+4)}$) if $d\geq 4$.

Case 1: $d\leq 3$. In this case, we find that

where $M_{1}\equiv(K(1+L)^{d/2})^{1/2}/(1-d/4)$. Solving the relation $r_{n}^{2}\phi(1/r_{n})\asymp\sqrt{n}$ for $r_{n}$ yields $r_{n}=n^{2/(d+4)}$ up to a constant.

Case 2: $d=4$. In this case, we find that

where $M_{2}\equiv(K(1+L)^{d/2})^{1/2}$. Solving the relation $r_{n}^{2}\phi(1/r_{n})\asymp\sqrt{n}$ for $r_{n}$ yields $r_{n}=(n/(\log n)^{2})^{1/4}$ up to a constant.

Case 3: $d>4$. In this case, we calculate

where $M_{3}\equiv(K(1+L)^{d/2})^{1/2}/(d/4-1)$. Solving the relation $r_{n}^{2}\phi(1/r_{n})\asymp\sqrt{n}$ for $r_{n}$ yields $r_{n}=n^{1/d}$ up to a constant.

Acknowledgments

This research is part of the Ph.D. dissertation of the first author at the University of Washington. We would like to thank two referees for a number of helpful suggestions.

[id=supp] \snameSupplement \stitleOmitted Proofs and Some Facts from Convex Analysis \slink[doi]10.1214/10-AOS840 \sdatatype.pdf \sfilenameConvexTransfSupp-v4.pdf \sdescriptionIn the supplement, we provide omitted proofs and some basic facts from convex analysis used in this paper.

References