Approximation by log-concave distributions, with applications to regression

Introduction

Log-concave distributions, that is, distributions with a Lebesgue density the logarithm of which is concave, are an interesting nonparametric model comprising many parametric families of distributions. Bagnoli and Bergstrom (2005) give an overview of many interesting properties and applications in econometrics. Indeed, these distributions have received a lot of attention among statisticians recently as described in the review by Walther (2009). The nonparametric maximum likelihood estimator was studied in the univariate setting by Pal, Woodroofe and Meyer (2007), Rufibach (2006), Dümbgen, Hüsler and Rufibach (2007), Balabdaoui, Rufibach and Wellner (2009) and Dümbgen and Rufibach (2009). These references contain characterizations of the estimators, consistency results and explicit algorithms. Extensions of one or more of these aspects to the multivariate setting are presented by Cule, Samworth and Stewart (2010), Cule and Samworth (2010), Koenker and Mizera (2010), Seregin and Wellner (2010) and Schuhmacher and Dümbgen (2010). Both Cule and Samworth (2010) and Schuhmacher, Hüsler and Dümbgen (2009) show that multivariate log-concave distributions are a very well-behaved nonparametric class. For instance, moments of arbitrary order are continuous statistical functionals with respect to weak convergence.

(provided this exists and is unique). Even if $Q$ fails to have a density within $\mathcal{F}$, one may view $\hat{f}_{n}$ as an estimator of the approximating density

Since the sequence of empirical measures $\hat{Q}_{n}$ converges weakly to $Q$ almost surely, this entails strong consistency of the Grenander estimator $f(\cdot|\hat{Q}_{n})$ in total variation distance.

Some additional properties of $f(\cdot|Q)$ will be established as well. We show that the mapping $Q\mapsto f(\cdot|Q)$ is continuous with respect to Mallows distance [Mallows (1972)] $D_{1}(\cdot,\cdot)$, also known as a Wasserstein, Monge–Kantorovich or Earth Mover’s distance. Precisely, let $Q$ satisfy the properties just mentioned, and let $(Q_{n})_{n}$ be a sequence of probability distributions converging to $Q$ in $D_{1}$; in other words,

as $n\to\infty$. Then $f(\cdot|Q_{n})$ is well defined for sufficiently large $n$ and

This entails strong consistency of the maximum likelihood estimator $\hat{f}_{n}$, because $(\hat{Q}_{n})_{n}$ converges almost surely to $Q$ with respect to Mallows distance $D_{1}(\cdot,\cdot)$. In addition we show that $Q\mapsto\max_{f\in\mathcal{F}}\int\log(f)\,dQ$ is convex and upper semicontinuous with respect to weak convergence.

In Section 3 we apply these results to the following type of regression problem: suppose that we observe independent real random variables $Y_{1}$, $Y_{2},\ldots,Y_{n}$ such that

Many proofs and technical arguments are deferred to Section 4. A longer and more detailed version of this paper is the technical report by Dümbgen, Samworth and Schuhmacher (2010), referred to as [DSS 2010] hereafter. It contains all proofs, additional examples and plots, a detailed description of our algorithms and extensive simulation studies. There we also indicate potential applications to change-point analyses.

Log-concave approximations

The next theorem provides a complete characterization of all distributions $Q\in\mathcal{Q}$ with real profile log-likelihood $L(Q)$. To state the result we first define the convex support of a distribution $Q\in\mathcal{Q}$ and collect some of its properties.

is itself closed and convex with $Q(\operatorname{csupp}(Q))=1$. The following three properties of $Q$ are equivalent:

$\operatorname{csupp}(Q)$ has nonempty interior;

For any $Q\in\mathcal{Q}$, the value of $L(Q)$ is real if and only if

In that case, there exists a unique function

This function $\psi$ satisfies $\int e^{\psi(x)}\,dx=1$ and

Let $P$ be the approximating probability measure with $P(dx)=e^{\psi(x)}\,dx$. It satisfies the following (in)equalities:

The profile log-likelihood $L$ is convex on $\mathcal{Q}^{1}$. Precisely, for arbitrary $Q_{0},Q_{1}\in\mathcal{Q}^{1}$ and $0<t<1$,

The two sides are equal and real if and only if $Q_{0},Q_{1}\in\mathcal{Q}_{o}\cap\mathcal{Q}^{1}$ with $\psi(\cdot|Q_{0})=\psi(\cdot|Q_{1})$.

Furthermore, suppose that $Q$ has a density $g$ on an open set $U$ such that $\psi>\log g$ on this set. Then

2 The one-dimensional case

For the case of $d=1$ one can generalize Theorem 2.4 of Dümbgen and Rufibach (2009) as follows: for a function $\phi\in\Phi(1)$ let

One consequence of this theorem is that the c.d.f. $F$ of $\psi(\cdot|Q)$ follows the c.d.f. $G$ of $Q$ quite closely in that

Let $Q$ be a rescaled version of Student’s distribution $t_{2}$ with density and distribution function

respectively. The best approximating log-concave distribution is the Laplace distribution with density and distribution function

respectively. To verify this claim, note that by symmetry it suffices to show that

Indeed the integral on the left-hand side equals

for all $x\leq 0$. Clearly this expression is zero for $x=0$, and elementary considerations show that it is nonpositive for all $x\leq 0$. Numerical calculations reveal that $|F-G|$ is smaller than $0.04$ everywhere.

Suppose that $Q$ has a continuous but not log-concave density $g$. Nevertheless one can say the following about the approximating log-density $\psi=\psi(\cdot|Q)$:

Suppose that $\log g$ is concave on an interval $(-\infty,a]$ with $g(a)>0$ and $\psi(a)\leq\log g(a)$. Then there exists a point $a^{\prime}\in[-\infty,a]$ such that $\psi$ is linear on $(a^{\prime},a]$ and $\psi=\log g$ on $(-\infty,a^{\prime}]$.

Suppose that $\log g$ is differentiable everywhere, convex on a bounded interval $[a,b]$ and concave on both $(-\infty,a]$ and $[b,\infty)$. Then there exist points $a^{\prime}\in(-\infty,a]$ and $b^{\prime}\in[b,\infty)$ such that $\psi$ is linear on $[a^{\prime},b^{\prime}]$ while $\psi=\log g$ on $(-\infty,a^{\prime}]\cup[b^{\prime},\infty)$.

Suppose that $\log g$ is convex on an interval $(-\infty,a]$ such that $-\infty<\log g(a)\leq\psi(a)$. Then $\psi$ is linear on $(-\infty,a]$.

Let us illustrate part (ii) of Remark 2.11 with a numerical example. Figure 1 shows the bimodal

3 Continuity in Q𝑄Q

For the applications to regression problems to follow we need to understand the properties of both $Q\mapsto L(Q)$ and $Q\mapsto\psi(\cdot|Q)$ on $\mathcal{Q}^{1}\cap\mathcal{Q}_{o}$. Our first hope was that both mappings would be continuous with respect to the weak topology. It turned out, however, that we need a somewhat stronger notion of convergence, namely, convergence with respect to Mallows distance $D_{1}$ which is defined as follows: for two probability distributions $Q,Q^{\prime}\in\mathcal{Q}^{1}$,

where the infimum is taken over all pairs $(X,X^{\prime})$ of random vectors $X\sim Q$ and $X^{\prime}\sim Q^{\prime}$ on a common probability space. It is well known that the infimum in $D_{1}(Q,Q^{\prime})$ is a minimum. The distance $D_{1}$ is also known as Wasserstein, Monge–Kantorovich or Earth Mover’s distance. An alternative representation due to Kantorovič and Rubinšteĭn (1958) is

A good starting point for more detailed information on Mallows distance is Chapter 7 of Villani (2003).

Before presenting the main results of this section we mention two useful facts about the convex support of distributions.

Moreover, if $(Q_{n})_{n}$ is a sequence in $\mathcal{Q}$ converging weakly to $Q$, then

This lemma implies that the set $\mathcal{Q}_{o}$ is an open subset of $\mathcal{Q}$ with respect to the topology of weak convergence. The supremum $h(Q,x)$ is a maximum over closed halfspaces and is related to Tukey’s halfspace depth [Donoho and Gasko (1992), Section 6]. For a proof of Lemma 2.13 we refer to [DSS 2010]. Now we are ready to state the main results of this section.

Let $(Q_{n})_{n}$ be a sequence of distributions in $\mathcal{Q}_{o}$ converging weakly to some $Q\in\mathcal{Q}_{o}$. Then

Moreover, $\liminf_{n\to\infty}L(Q_{n})<L(Q)$ if and only if

This result already entails continuity of $L(\cdot)$ on $\mathcal{Q}_{o}\cap\mathcal{Q}^{1}$ with respect to Mallows distance $D_{1}$. The next theorem extends this result to $L\dvtx\mathcal{Q}^{1}\to(-\infty,\infty]$:

Let $(Q_{n})_{n}$ be a sequence of distributions in $\mathcal{Q}^{1}$ such that $\lim_{n\to\infty}D_{1}(Q_{n},Q)=0$ for some $Q\in\mathcal{Q}^{1}$. Then

In case of $Q\in\mathcal{Q}_{o}\cap\mathcal{Q}^{1}$, the probability densities f:=\exp\mbox{{}\circ{}}\psi(\cdot|Q) and f_{n}:=\exp\mbox{{}\circ{}}\psi(\cdot|Q_{n}) are well defined for sufficiently large $n$ and satisfy

Applications to regression problems

We propose to estimate $(\psi,\mu)$ by a maximizer of

maximizes $\hat{\Lambda}(\phi,m)$ over all $(\phi,m)\in\Phi\times\mathcal{M}$ satisfying the additional constraint that \exp\mbox{{}\circ{}}\phi defines a probability density with mean zero.

Define $\mathbf{x}:=(x_{i})_{i=1}^{n}$ and $m(\mathbf{x}):=(m(x_{i}))_{i=1}^{n}$. Then we may write

and this representation is our key to proving the existence of $(\hat{\psi},\hat{\mu})$. Before doing so we state a simple inequality of independent interest, which follows from Jensen’s inequality and elementary considerations:

For any distribution $Q\in\mathcal{Q}^{1}(1)$,

where $\operatorname{Med}(Q)$ is a median of $Q$ while $\mu(Q)$ denotes its mean $\int xQ(dx)$.

The constraint $\mathbf{Y}\notin\mathcal{M}(\mathbf{x})$ excludes situations with perfect fit. In that case, the Dirac measure $\delta_{0}$ would be the most plausible error distribution.

The maximum likelihood estimator $(\hat{\psi},\hat{\mu})$ need not be unique in general. Nevertheless we will prove it to be consistent under certain regularity conditions. A key point here is Fisher consistency in the following sense: note that the expectation measure of the empirical distribution $\hat{Q}_{m(\mathbf{x})}$ equals

with equality if and only if $\mu-m$ is constant on $\{x_{1},x_{2},\ldots,x_{n}\}$. This follows from a more general inequality which is somewhat reminiscent of Anderson’s lemma [Anderson (1955)]:

Let $Q\in\mathcal{Q}_{o}(d)\cap\mathcal{Q}^{1}(d)$ and $R\in\mathcal{Q}^{1}(d)$. Then $Q\star R\in\mathcal{Q}_{o}\cap\mathcal{Q}^{1}$ and

2 Consistency

In this subsection we consider a triangular scheme of independent observations $(x_{ni},Y_{ni})$, $1\leq i\leq n$, with fixed design points $x_{ni}\in\mathcal{X}_{n}$ and

where $\mu_{n}$ is an unknown regression function in $\mathcal{M}_{n}$ and $\varepsilon_{n1},\varepsilon_{n2},\ldots,\varepsilon_{nn}$ are unobserved independent random errors with mean zero and unknown distribution $Q_{n}\in\mathcal{Q}_{o}(1)\cap\mathcal{Q}^{1}(1)$. Two basic assumptions are:

$D_{1}(Q_{n},Q)\to 0$ for some distribution $Q\in\mathcal{Q}_{o}(1)\cap\mathcal{Q}^{1}(1)$.

We write $(\hat{\psi}_{n},\hat{\mu}_{n})$ for a maximizer of $L(\phi,\hat{Q}_{n,m})$ over all pairs $(\phi,m)\in\Phi\times\mathcal{M}_{n}$ such that $\int e^{\phi(x)}\,dx=1$ and $\int xe^{\phi(x)}\,dx=0$, where $\hat{Q}_{n,m}$ stands for the empirical distribution of the residuals $Y_{ni}-m(x_{ni})$, $1\leq i\leq n$. We also need to consider its expectation measure

It is also convenient to metrize weak convergence. In Theorem 3.6 below we utilize the bounded Lipschitz distance: for probability distributions $Q,Q^{\prime}$ on the real line let

Let assumptions (A.1) and (A.2) be satisfied. Suppose further that: {longlist}[(A.2)]

Then, with f_{n}:=\exp\mbox{{}\circ{}}\psi(\cdot|Q_{n}) and \hat{f}_{n}:=\exp\mbox{{}\circ{}}\hat{\psi}_{n}, the maximum likelihood estimator $(\hat{f}_{n},\hat{\mu}_{n})$ of $(f_{n},\mu_{n})$ exists with asymptotic probability one and satisfies

We know already that assumption (A.1) is satisfied for multiple linear regression and isotonic regression. Assumption (A.2) is a generalization of assuming a fixed error distribution for all sample sizes. The crucial point, of course, is assumption (A.3). In our two examples it is satisfied under mild conditions:

The proof of Theorem 3.7 is given in Section 4. For the proof of Theorem 3.8, which uses similar ideas and an additional approximation argument, we refer to [DSS 2010].

3 Algorithms and numerical results

Extensive simulation studies in [DSS 2010] suggest that $(\hat{\psi},\hat{\mu})$ provides rather accurate estimates even if $n$ is only moderately large. For various skewed error distributions, $\hat{\mu}$ may be considerably better than the corresponding least squares estimator. As an example consider the simple linear regression model with observations

where $X_{1},\ldots,X_{n}$ are independent design points from the $\operatorname{Unif}$ distribution and $\varepsilon_{1},\ldots,\varepsilon_{n}$ are independent errors from a centered gamma distribution with shape parameter $r$ and variance $1$. Note that the distribution of $(\hat{\psi},\hat{\theta}-\theta)$ does not depend on $c$ or $\theta$. Monte Carlo estimation of the root mean squared error based on 1000 simulations of this model gives 0.023 for the estimator $\hat{\theta}$ versus 0.118 for the least squares estimator of $\theta$ if $r=1$, and 0.095 versus 0.113 for the same comparison if $r=3$.

4 A data example

A familiar task in econometrics is to model expenditure ($Y$) of households as a function of their income ($X$). Not only the mean curve (Engel curve) but also quantile curves play an important role. A related application are growth charts in which, for instance, $X$ is the age of a newborn or infant and $Y$ is its height or weight.

Interestingly, neither linear nor quadratic nor cubic regression yield convincing fits to these data. Polynomial regression of degree four or cubic splines with knot points at, say, $4.1$, $4.3$, $4.5$, $4.7$, $4.9$ seem to fit the data quite well. Moreover, exact Monte Carlo goodness-of-fits test, assuming the regression function to be a cubic spline and based on a Kolmogorov–Smirnov statistic applied to studentized residuals, revealed the regression errors $\varepsilon_{i}$ to be definitely non-Gaussian.

Figure 3 shows the data and estimated $\beta$-quantile curves for $\beta=0.1$, $0.25$, $0.5$, $0.75$, $0.9$, based on our additive regression model. Note that the estimated $\beta$-quantile curve is simply the estimated mean curve plus the $\beta$-quantile of the estimated error distribution. On the left-hand side, we only assumed $\mu$ to be nondecreasing, on the right-hand side we fitted the aforementioned spline model. In both cases the fitted quantile curves are similar to the quantile curves in Figure 2 but with fewer irregularities such as big jumps which may be artifacts due to sampling error.

Proofs

For the proof of Theorem 2.2 we need an elementary bound for the Lebesgue measure of level sets of log-concave distributions:

Another key ingredient for the proofs of Theorems 2.2 and 2.15 is a lemma on pointwise limits of sequences in $\Phi$:

is nonempty. Then there exist a subsequence $(\phi_{n(k)})_{k}$ of $(\phi_{n})_{n}$ and a function $\phi\in\Phi$ such that $C\subseteq\operatorname{dom}(\phi)=\{\phi>-\infty\}$ and

Proof of Theorem 2.2 Suppose first that $\int\|x\|Q(dx)=\infty$. Since any $\phi\in\Phi$ is majorized by $x\mapsto a-b\|x\|$ for suitable constants $a$ and $b>0$, this entails that $L(Q)=-\infty$.

For the remainder of this proof suppose that $\int\|x\|Q(dx)<\infty$ and that $\operatorname{csupp}(Q)$ has nonempty interior. Since the concave function $h(x)=-\|x\|$ satisfies $\int h\,dQ>-\infty$, we have $L(Q)>-\infty$. When maximizing $L(\phi,Q)$ over all $\phi\in\Phi$ we may and do restrict our attention to functions $\phi\in\Phi$ such that $\int e^{\phi(x)}\,dx=1$ (see end of Section 1) and $\operatorname{dom}(\phi)=\{\phi>-\infty\}\subseteq\operatorname{csupp}(Q)$. For if $\operatorname{dom}(\phi)\not\subset\operatorname{csupp}(Q)$, replacing $\phi(x)$ with $-\infty$ for all $x\notin\operatorname{csupp}(Q)$ would also increase $L(\phi,Q)$ strictly. Let $\Phi(Q)$ be the family of all $\phi\in\Phi$ with these properties.

as $M\to\infty$ for any fixed $c>0$. But Lemma 2.1 entails that for sufficiently large $c$ and sufficiently small $\delta>0$,

If $\phi_{n}(x_{o})<M_{n}$, then $x_{o}$ is not an interior point of the closed, convex set $\{\phi_{n}\geq\phi_{n}(x_{o})\}$. Hence

with $h(Q,x_{o})<1$ defined in Lemma 2.13. In the case of $\phi_{n}(x_{o})=M_{n}$ these inequalities are true as well. Thus

which establishes (5). Combining (5) with $\phi_{n}\leq M_{*}$, we may deduce from Lemma 3.3 of Schuhmacher, Hüsler and Dümbgen (2009) that there exist constants $a$ and $b>0$ such that

Since the boundary of $\operatorname{csupp}(Q)$ has Lebesgue measure zero, it follows from dominated convergence that $\int e^{\psi(x)}\,dx=1$. Moreover, applying Fatou’s lemma to the nonnegative functions $x\mapsto a-b\|x\|-\phi_{n(k)}(x)$ yields

In our proofs of Theorems 2.7 and 2.15 we utilize a special approximation scheme for functions in $\Phi$:

For any function $\phi\in\Phi$ with nonempty domain and any parameter $\varepsilon>0$ set

Proof of Theorem 2.7 Let $P$ be the distribution corresponding to $F$. Suppose first that $\phi=\psi(\cdot|Q)$. Then it follows from (4) and Fubini’s theorem that

It remains to be shown that $\int_{-\infty}^{x}(F-G)(t)\,dt\geq 0$ for $x\in\mathcal{S}(\phi)$. Suppose first that $x\in\operatorname{interior}(\operatorname{dom}(\phi))$. Note that $\phi^{\prime}:=\phi^{\prime}(\cdot+)$ is nonincreasing on the interior of $\operatorname{dom}(\phi)$ with

Moreover, $x\in\mathcal{S}(\phi)$ implies that $\phi^{\prime}(x-\delta)>\phi^{\prime}(x+\delta)$ for all $\delta>0$ satisfying $x\pm\delta\in\operatorname{interior}(\operatorname{dom}(\phi))$. For such $\delta>0$ we define

When $x\in\mathcal{S}(\phi)$ is the left or right endpoint of $\operatorname{dom}(\phi)$, we define $\Delta(s):=(s-x)^{+}$ and conclude analogously that $\int_{-\infty}^{x}(F-G)(t)\,dt\geq 0$.

Since $\int(F-G)(t)\,dt=0$, we may continue with

where the first displayed inequality follows from log-concavity of $P$ with log-density $\phi$. Thus $\phi=\psi$.

Theorem 2.14 and the second part of Theorem 2.15 are a consequence of the following result:

Let $(Q_{n})_{n}$ be a sequence of distributions in $\mathcal{Q}_{o}$ such that $Q_{n}\to_{w}Q\in\mathcal{Q}_{o}$, $L(Q_{n})\to\lambda\in[-\infty,\infty]$ and $\int\|x\|Q_{n}(dx)\to\gamma\in[0,\infty]$ as $n\to\infty$. Then $\gamma\geq\int\|x\|Q(dx)$, and $\lambda>-\infty$ if and only if $\gamma<\infty$. Moreover,

In the latter case, the densities f:=\exp\mbox{{}\circ{}}\psi(\cdot|Q) and f_{n}:=\exp\mbox{{}\circ{}}\psi(\cdot|Q_{n}) are well defined for sufficiently large $n$ and satisfy

Before presenting the proof of this result, let us recall two elementary facts about weak convergence and unbounded functions:

If the stronger statement $\lim_{n\to\infty}\int h\,dQ_{n}=\int h\,dQ<\infty$ holds, then

Proof of Theorem 4.4 The asserted inequality $\gamma\geq\int\|x\|Q(dx)$ follows from the first part of Lemma 4.5 with $h(x):=\|x\|$.

Suppose that $\gamma<\infty$. Then with $\phi(x):=-\|x\|$,

In other words, $\lambda=-\infty$ entails that $\gamma=\infty$.

This can be verified as follows: since $L(Q_{n})=\int\psi_{n}\,dQ_{n}\leq M_{n}$, the sequence $(M_{n})_{n}$ satisfies $\liminf_{n\to\infty}M_{n}\geq\lambda$. With similar arguments as in the proof of Theorem 2.2 one can deduce that $(M_{n})_{n}$ is bounded from above, provided that

Another key property of the functions $\psi_{n}$ is that

by virtue of Lemma 2.13. Combining (5) with (7) we may again deduce that there exist constants $a$ and $b>0$ such that

Thus $\lambda<L(Q)$ if $\gamma>\int\|x\|Q(dx)$.

By monotone convergence, applied to the functions $\psi^{(1)}-\psi^{(\varepsilon)}$, and dominated convergence, applied to \exp\mbox{{}\circ{}}\psi^{(\varepsilon)},

Note that the probability densities f=\exp\mbox{{}\circ{}}\psi and f_{n}=\exp\mbox{{}\circ{}}\psi_{n} obviously satisfy

In particular, $(f_{n})_{n}$ converges to $f$ almost everywhere w.r.t. Lebesgue measure, whence $\int|f_{n}(x)-f(x)|\,dx\to 0$.

where $B_{k}:=I-uu^{\top}+kuu^{\top}$ is a real, $d\times d$ matrix and $a_{k}:=-kru$. Note that $\det(B_{k})=k$ and $\phi_{k}(x)=\log(k)-\|x\|$ for $x\in H$. Thus

and the right-hand side tends to infinity as $\|\mathbf{v}\|\to\infty$. Thus it follows from Lemma 3.1 that

Our goal is to show that $(\hat{f}_{n},\hat{\mu}_{n})$, viewed as a function of $\bolds{\varepsilon}_{n}$ and thus fixed, too, is well defined for sufficiently large $n$ with

Note that we replaced $f_{n}$ with f=\exp\mbox{{}\circ{}}\psi(\cdot|Q) because $\int|f_{n}(x)-f(x)|\,dx$ tends to .

where $\hat{M}_{n}:=\hat{Q}_{n,\hat{\mu}_{n}}$ and $\hat{R}_{n}:=R_{(\mu_{n}-\hat{\mu}_{n})(\mathbf{x}_{n})}$.

Note first that $\check{\mu}_{n}:=\mu_{n}+\int t\hat{Q}_{n}(dt)$ belongs to $\hat{\mathcal{M}}_{n}$, whence

Since $(\hat{R}_{n})_{n}$ is tight, to verify (13) we may consider a subsequence $(\hat{R}_{n(k)})_{k}$ that converges weakly to some distribution $R$ as $k\to\infty$. Then $\hat{M}_{n(k)}\to_{w}Q\star R$, so

by Theorems 2.14 and 3.5. Because of (14) we even know that $L(\hat{M}_{n(k)})\to L(Q\star R)=L(Q)$ as $k\to\infty$. Consequently, we may deduce from Theorems 2.14 and 3.5 that

Hence $\int|t|\hat{R}_{n(k)}(dt)$ is not greater than

as $k\to\infty$. As $r\uparrow\infty$, the limit on the right-hand side converges to $\int|t|R(dt)=|a|$. Consequently, $\lim_{k\to\infty}D_{1}(\hat{R}_{n(k)},R)=0$. But then $0=\lim_{k\to\infty}\int t\hat{R}_{n(k)}(dt)$ coincides with $\int tR(dt)=a$.

In our proofs of Theorems 3.7 and 3.8 we utilize a simple inequality for the bounded Lipschitz distance in terms of the Kolmogorov–Smirnov distance,

of two distributions $Q,Q^{\prime}\in\mathcal{Q}(1)$:

Let $Q$ and $Q^{\prime}$ be distributions on the real line. Then for arbitrary $r>0$,

Proof of Theorem 3.7 A key insight is that the empirical distributions $\hat{Q}_{n,m}$ are close to their expectations $Q_{n,m}$ with respect to Kolmogorov–Smirnov distance, uniformly over all $m\in\mathcal{M}_{n}$. Namely,

for some universal constant $C$ [see Pollard (1990), Theorems 2.2 and 3.5, and van der Vaart and Wellner (1996), Theorem 2.6.4 and Lemma 2.6.16].

Acknowledgments

Constructive comments by an Associate Editor and two referees are gratefully acknowledged.

References