# Robust density estimation with the ${\mathbb{L}}_{1}$-loss. Applications to
the estimation of a density on the line satisfying a shape constraint

Yannick BARAUD  ,  Hélène HALCONRUY  and  Guillaume MAILLARD  Department of
Mathematics, University of Luxembourg Maison du nombre 6 avenue de la Fonte
L-4364 Esch-sur-Alzette Grand Duchy of Luxembourg<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
(Date: June 24, 2022)

###### Abstract.

We solve the problem of estimating the distribution of presumed i.i.d.
observations for the total variation loss. Our approach is based on density
models and is versatile enough to cope with many different ones, including
some density models for which the Maximum Likelihood Estimator (MLE for short)
does not exist. We mainly illustrate the properties of our estimator on models
of densities on the line that satisfy a shape constraint. We show that it
possesses some similar optimality properties, with regard to some global rates
of convergence, as the MLE does when it exists. It also enjoys some adaptation
properties with respect to some specific target densities in the model for
which our estimator is proven to converge at parametric rate. More important
is the fact that our estimator is robust, not only with respect to model
misspecification, but also to contamination, the presence of outliers among
the dataset and the equidistribution assumption. This means that the estimator
performs almost as well as if the data were i.i.d. with density $p$ in a
situation where these data are only independent and most of their marginals
are close enough in total variation to a distribution with density $p$. We
also show that our estimator converges to the average density of the data,
when this density belongs to the model, even when none of the marginal
densities belongs to it. Our main result on the risk of the estimator takes
the form of an exponential deviation inequality which is non-asymptotic and
involves explicit numerical constants. We deduce from it several global rates
of convergence, including some bounds for the minimax ${\mathbb{L}}_{1}$-risks
over the sets of concave and log-concave densities. These bounds derive from
some specific results on the approximation of densities which are monotone,
convex, concave and log-concave. Such results may be of independent interest.

###### Key words and phrases:

Density estimation, robust estimation, shape constraint, total variation loss,
minimax theory

###### 1991 Mathematics Subject Classification:

Primary 62G07, 62G35; Secondary 62C20

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under grant agreement No 811017

##  1\. Introduction

Estimating a density under a shape constraint has been addressed by many
authors since the pioneer papers by Grenander (1956; 1981), Rao (1969),
Groeneboom (1985) and Birgé (1989) for estimating a nonincreasing density on
$(0,+\infty)$. It is well-known that this problem can elegantly be solved by
the Grenander estimator – see Grenander (1956)– which is the maximum
likelihood estimator (MLE for short) over the set of densities that satisfy
this monotonicity constraint on $(0,+\infty)$. Rao (1969) and Grenander (1956;
1981) established the local asymptotic properties of the Grenander estimator
while Groeneboom (1985) and Birgé (1989) studied its global estimation errors
for the ${\mathbb{L}}_{1}$-loss on some functional classes of interest. Birgé
proved that the uniform risk of the Grenander estimator over the set
${\mathscr{F}}(H,L)$, that consists of nonincreasing densities bounded by
$H>0$ and supported on $[0,L]$ with $L>0$, is of order $(\log(1+HL)/n)^{1/3}$.
Since this rate is optimal, the Grenander estimator performs almost as well
(apart maybe from numerical constants) as a minimax estimator over
${\mathscr{F}}(H,L)$ that would know the values of $H$ and $L$ in advance.
Even more surprising is the fact that the Grenander estimator can converge at
a parametric rate ($1/\sqrt{n}$) when the density is piecewise constant on the
elements of partition of $(0,+\infty)$ into a finite number of intervals – see
Grenander (1981), Groeneboom (1985) and Birgé (1989). As a consequence, the
Grenander estimator can nicely adapt to the specific features of the target
density even though these features are a priori unknown.

Because of these adaptation properties for estimating a monotone density, the
MLE has widely and almost exclusively been used to solve many other density
estimation problems under shape constraints. We refer to Groeneboom et al
(2001) for convex densities and to Balabdaoui and Wellner (2007) and Gao and
Wellner () for $k$-monotone ones. Although the construction of the MLE is not
based on any smoothness assumption in these cases, it still needs to have some
pieces of information on the support of the target density. It was already the
case for the monotonicity constraint since the left-endpoint of the support of
the density needed to be known to build the Grenander estimator. This kind of
prior information might, however, not be available in practice and a more
reasonable assumption would be that only an interval containing this support
be known. Unfortunately, under this weaker assumption the MLE does not exist
and the search of alternative estimators becomes necessary to solve this
issue.

To our knowledge, the first attempt to solve it dates back to Wegman, (1970).
He designed a MLE-type estimator restricted to a class of unimodal densities
that attain their modes on an interval of length not smaller than some
parameter ${\varepsilon}>0$. This parameter needs to be tuned by the
statistician and its choice influences the performance of the resulting
estimator. Wegman and Grenander estimators both converge at the same rate
except on an interval of length $\varepsilon$ around the mode. Birgé, (1997)
proposed a different approach based on data-driven choice of a Grenander
estimator among the collection of those associated to all possible modes. He
proved that the ${\mathbb{L}}_{1}$-risk of the selected estimator is the same
as that of the Grenander estimator that would know the value of the mode in
advance, up to an additional term of order $1/\sqrt{n}$.

The situation is different when the density is assumed to be log-concave on
${\mathbb{R}}$, or more generally on ${\mathbb{R}}^{d}$ with $d>1$. The
construction of the MLE is then free of any assumption on the support of the
density. The study the MLE on the set of log-concave densities has led to an
intensive work. We refer the reader to Dümbgen and K. Rufibach (2009), Doss
and Wellner (2016) , Cule and Samworth (2010), Kim and Samworth (2016) and
Feng et al (2021) as well as the references therein. Kim and Samworth (2016)
described the uniform rates of convergence of the MLE for the squared
Hellinger loss over the class of log-concave densities in dimension
$d\in\\{1,2,3\\}$ and they proved these rates to be minimax (up to a possible
logarithmic factor). Besides, as for the monotonicity constraint in dimension
one, the MLE also possesses for log-concave densities some adaptation
properties: it converges at parametric rate (for the Hellinger loss and up to
a possible logarithmic factor) when the logarithm of the target density is
piecewise affine on a suitable convex subset of ${\mathbb{R}}^{d}$ with
$d\in\\{1,2,3\\}$. This result was established by Kim et al (2018) when $d=1$
and extended to the dimensions $d\in\\{2,3\\}$ by Feng et al (2021). In
dimension $d\geqslant 4$, Kur et al. Kur et al., (2019) showed that the MLE
converges at a minimax rate - up to a logarithm factor - for the Hellinger
loss.

In the one dimensional case, our aim is to design a versatile estimation
strategy that can be applied to a wide variety of density models, including
some for which the MLE does not exist, and that automatically results in
estimators with good estimation properties. In particular, these estimators
should keep the nice minimax and adaptation properties of the MLE, when it
exists, for estimating a density under a shape constraint. They should also
remain stable with respect to a slight departure from the ideal situation
where the data are truly i.i.d. and their density satisfies the required
shape. In particular, the estimator should still perform well when the
equidistribution assumption is slightly violated and the data set contains a
small portion of outliers. It should also perform well when the shape of the
density is slightly different from what was originally expected, that is, when
the true density of the data does not satisfy the shape constraint but is
close enough (with respect to the ${\mathbb{L}}_{1}$-loss) to a density that
does satisfy it. In a nutshell, our aim is to build estimators that are
robust. Except for the Grenander estimator (which is a particular case of a
$\rho$-estimator — see Baraud and Birgé (2018)[Section 6]—, we are not aware
of any result that establishes such robustness properties for the MLE.

Actually, we are not aware of many robust strategies for estimating a density
under a shape constraint. For estimating concave and log-concave densities,
Chan et al (2014) proposed a piecewise linear estimator on a data-driven
partition of ${\mathbb{R}}$ into intervals. Their estimator is minimax optimal
on the sets of concave and log-concave densities and it enjoys some robustness
properties with respect to a departure (in ${\mathbb{L}}_{1}$-distance) of the
true density from the model. Their approach is based on the estimation
procedure described in Devroye and Lugosi (2001) and uses the fact that the
Yatracos class associated to the set of the densities that are piecewise
linear on a partition of the line into a fixed number of intervals is VC.
Despite the desirable properties described above, this estimator does not
possess some of the nice ones that makes the MLE so popular. For estimating a
log-concave density, the MLE converges at global rate of order $n^{-2/5}$ (for
the ${\mathbb{L}}_{1}$ and Hellinger distances) but, as already mentioned, it
also possesses some adaptation properties with respect to these densities the
logarithms of which are piecewise linear. The estimator proposed by Chan et al
does not possess such a property. Besides, their approach provides competitors
to the MLE for some specific density models only. Chan et al’s approach cannot
deal with the estimation of a monotone density on a half-line for example and
therefore cannot be used to provide a surrogate to the Grenander estimator.

In dimension one, Baraud and Birgé (2016)[Section 7] proposed to solve the
problem of robust estimation of a density under a shape constraint by using
$\rho$-estimation. Their results hold for the Hellinger loss while ours is for
the total variation one (TV-loss for short). The estimator we propose is more
specifically designed for this loss and quite surprisingly the risk bounds we
get for the TV-loss are slightly different from those obtained by Baraud and
Birgé for the Hellinger one. We do not know if $\rho$-estimators would satisfy
the same ${\mathbb{L}}_{1}$-risk bounds as those we establish here.

Our procedure shares some similarities with that proposed by Devroye and
Lugosi (2001). When the Yatracos class associated to density model is VC, the
risk bound we establish is similar to theirs except from the fact that we
provide explicit numerical constants. However, unlike them, we also consider
density models for which the Yatracos class is not VC, which is typically the
case for these models of densities that satisfy a shape constraint.
Nevertheless, it is likely that with the same techniques of proofs, we could
establish for Devroye and Lugosi’s estimators the similar results as those we
establish here for ours.

The theory of $\ell$-estimation introduced in Baraud (2021) provides a generic
way of building estimators that possess the robustness properties we are
looking for. Even though the present paper is in the same line, we modify
Baraud’s procedure and establish, for the modified $\ell$-estimator, risk
bounds with numerical constants that are essentially divided by a factor 2 as
compared to his. Another important difference with Baraud’s result lies in the
following fact. When the data are only independent with marginal densities
$p_{1}^{\star},\ldots,p_{n}^{\star}$, we measure the performance of our
density estimator $\widehat{p}$ in terms of its ${\mathbb{L}}_{1}$-distance
$\|p^{\star}-\widehat{p}\|$ between $\widehat{p}$ and the average of the
marginal densities $p^{\star}=n^{-1}\sum_{i=1}^{n}p_{i}^{\star}$. In contrast,
Baraud considered, as a loss function, the average of the
${\mathbb{L}}_{1}$-distances of $\widehat{p}$ to the $p_{i}^{\star}$, i.e. the
quantity $n^{-1}\sum_{i=1}^{n}\left\|{\widehat{p}-p_{i}^{\star}}\right\|$. As
a consequence, unlike Baraud, we can establish the convergence of our
estimator to $p^{\star}$, as soon as its belongs to the model, even in the
unfavourable situation where none of the marginals $p_{i}^{\star}$ belongs to
it.

The risk bounds we obtain hold for very general density models but our
applications focus on the estimation of a density on the line that satisfies a
shape constraint. In a nutshell, we establish the following results which are
to our knowledge new in the literature.

  * •

The procedure applies to a large variety of density model including some for
which the MLE does not exist (the set of all monotone densities on a half-
line, the set of all unimodal densities on ${\mathbb{R}}$, the set of all
convex densities on an interval, etc).

  * •

The global rates of convergence that we establish for our estimator are
optimal in all the models we consider.

  * •

The estimator possesses some adaptation properties: it converges at parametric
rate when the data are i.i.d. with a density that belongs to model and
satisfies some special properties. In particular, our estimator shares similar
adaptation properties as those established for the MLE under a monotonicity or
a log-concavity constraint. We also establish some adaptation properties on
density models on which the MLE does not even exist.

  * •

The estimator is robust with respect to model misspecification, contamination,
the presence of outliers and is robust with respect to a departure from the
equidistribution assumption we started from.

The paper is organized as follows. The statistical framework is described in
Section 2 and the construction of the estimator as well as its properties are
presented in Section 3. The more specific properties of our estimator for
estimating a mixture of densities that are monotone, convex or concave can be
found in Sections 4 and 5 respectively while the case of a log-concave density
is tackled in 6 respectively. These sections also contain some approximation
results which may be of independent interest and are central to our approach.
The proofs are postponed to Section 7.

##  2\. The statistical framework and main notations

Let $X_{1},\ldots,X_{n}$ be $n$ independent random variables and
$P_{1}^{\star},\ldots,P_{n}^{\star}$ their marginals on a measurable space
$({\mathscr{X}},{\mathscr{A}})$. Our aim is to estimate the $n$-tuple
${\mathbf{P}}^{\star}=(P_{1}^{\star},\ldots,P_{n}^{\star})$ from the
observation of ${\boldsymbol{X}}=(X_{1},\ldots,X_{n})$ on the basis of a
suitable model for ${\mathbf{P}}^{\star}$. More precisely, given a
$\sigma$-finite measure $\mu$ on $({\mathscr{X}},{\mathscr{A}})$ and a family
$\overline{\mathcal{M}}$ of densities with respect to $\mu$, we shall do as if
the $X_{i}$ were i.i.d. with a density that belongs to
$\overline{\mathcal{M}}$, even though this might not be true, and estimate
${\mathbf{P}}^{\star}$ by a $n$-tuple of the form
$(\widehat{P},\ldots,\widehat{P})$ where
$\widehat{P}=\widehat{P}({\boldsymbol{X}})=\widehat{p}\cdot\mu$ is a random
element of the set
$\overline{\mathscr{M}}=\\{P=p\cdot\mu,p\in\overline{\mathcal{M}}\\}$. We
refer to $\overline{\mathscr{M}}$ and $\overline{\mathcal{M}}$ as our
probability and density models respectively. For the sake of simplicity, we
abusively identify ${\mathbf{P}}^{\star}$ with the distribution $\bigotimes
P_{i}^{\star}$ of the observation ${\boldsymbol{X}}$.

The density models we have in mind are nonparametric and gather densities that
satisfy a given shape constraint: monotonicity on a half line, convexity on an
interval, log-concavity on the line, among other examples.

In order to evaluate the accuracy of our estimator, we use the TV-loss $d$ on
the set ${\mathscr{P}}$ of all probability measures on
$({\mathscr{X}},{\mathscr{A}})$. We denote by $\left\|{\cdot}\right\|$ the
${\mathbb{L}}_{1}$-norm on the set
${\mathbb{L}}_{1}({\mathscr{X}},{\mathscr{A}},\mu)$ that consists of the
equivalence classes of integrable functions on
$({\mathscr{X}},{\mathscr{A}},\mu)$. We recall that the TV-loss is a distance
defined for $P,Q\in{\mathscr{P}}$ by

(1)
$d\\!\left(P,Q\right)=\underset{A\in{\mathscr{A}}}{\sup}\left[{P(A)-Q(A)}\right]$

and if $P$ and $Q$ are absolutely continuous with respect to our dominating
measure $\mu$,

$d\\!\left(P,Q\right)=\frac{1}{2}\left\|{\frac{dP}{d\mu}-\frac{dQ}{d\mu}}\right\|.$

In general, whatever ${\mathbf{P}}^{\star}$, denote by $P^{\star}$ the uniform
mixture of the marginals:

$P^{\star}=\frac{1}{n}\sum_{i=1}^{n}P_{i}^{\star}.$

In particular, when the data are i.i.d., their common distribution is
$P^{\star}\in{\mathscr{P}}$.

The quantity $d\\!\left(P^{\star},P\right)$ is small as compared to 1 when
only a small portion of the marginals $P_{1}^{\star},\ldots,P_{n}^{\star}$ are
far away from $P$. Note that this quantity can be small even if none of the
$P_{i}^{\star}$ equals $P$.

Throughout this paper, we assume the following.

######  Assumption 1.

There exists a countable subset ${\mathcal{M}}$ of $\overline{\mathcal{M}}$
that is dense in $\overline{\mathcal{M}}$ for the ${\mathbb{L}}_{1}$-norm.

We recall that a subset of a separable metric space is separable. In
particular, when the space ${\mathbb{L}}_{1}({\mathscr{X}},{\mathscr{A}},\mu)$
is separable for the ${\mathbb{L}}_{1}$-norm, so is any subset
$\overline{\mathcal{M}}$ of densities on $({\mathscr{X}},{\mathscr{A}},\mu)$
and Assumption 1 is automatically satisfied. This is in particular the case
when
$({\mathscr{X}},{\mathscr{A}})=({\mathbb{R}}^{k},{\mathscr{B}}({\mathbb{R}}^{k}))$,
$k\geqslant 1$ and $\mu$ is the Lebesgue measure. If a family
$\overline{\mathcal{M}}$ of densities satisfies our Assumption 1, so does any
subset $\overline{\mathcal{D}}$ of $\overline{\mathcal{M}}$. The set
$\overline{\mathcal{D}}$ may in turn be associated to a subset ${\mathcal{D}}$
and a probability set ${\mathscr{D}}=\\{P=p\cdot\mu,\;p\in{\mathcal{D}}\\}$
that are both countable and respectively dense in
$(\overline{\mathcal{D}},\left\|{\cdot}\right\|)$ and
$\overline{\mathscr{D}}=\\{P=p\cdot\mu,\;p\in\overline{\mathcal{D}}\\}$ for
the total variation distance $d$. We may therefore write

$\inf_{P\in{\mathscr{D}}}d\\!\left(P^{\star},P\right)=\inf_{P\in\overline{\mathscr{D}}}d\\!\left(P^{\star},P\right).$

We shall repeatedly apply this equality to sets $\overline{\mathscr{D}}$ of
interest without any further notice. As a consequence, replacing a density
model $\overline{\mathcal{D}}$ by a countable and dense subset ${\mathcal{D}}$
changes nothing from the approximation point of view. Nevertheless, we prefer
to work with ${\mathcal{D}}$ rather than $\overline{\mathcal{D}}$ in order to
avoid some measurability issues that may result from the calculation of the
supremum of an empirical process indexed by $\overline{\mathcal{D}}$.

Throughout the present paper, we use the same kind of notations as
$\overline{\mathcal{D}},{\mathcal{D}},{\mathscr{D}},\overline{\mathscr{D}}$ in
order to distinguish between the density model, a countable and dense subset
of it and their corresponding probability models. Following these notations
${\mathscr{M}}=\\{P=p\cdot\mu,\;p\in{\mathcal{M}}\\}$. An interval $I$ of
${\mathbb{R}}$ is said to be nontrivial if its interior $\mathring{I}$ is not
empty or equivalently if its length is positive. Given
$a\in{\mathbb{R}}\cup\\{-\infty\\}$ and $b\in{\mathbb{R}}$, $(a,b|$ denotes
any of the intervals $(a,b)$ and $(a,b]$. When we say that $p$ is a density on
a (nontrivial) interval $I$, we mean that $p$ is a density that vanishes
outside $I$. The set of positive integers is denoted ${\mathbb{N}}^{\star}$
and $|A|$ is the cardinality of a set $A$. By convention,
$\sum_{\varnothing}=0$. For an integrable function $f$ on
$({\mathscr{X}}^{\otimes n},{\mathscr{A}}^{\otimes n})$,
${\mathbb{E}}[f({\boldsymbol{X}})]$ is the integral of $f$ with respect to the
probability measure $\bigotimes_{i=1}^{n}P_{i}^{\star}={\mathbf{P}}^{\star}$
while for $f$ on $({\mathscr{X}},{\mathscr{A}})$ and $S\in{\mathscr{P}}$,
${\mathbb{E}}_{S}[f(X)]$ is the integral of $f$ with respect to $S$. We use
the same conventions for $\mathop{\rm
Var}\nolimits\left(f({\boldsymbol{X}})\right)$ and $\mathop{\rm
Var}\nolimits_{S}\left(f(X)\right)$.

##  3\. An $\ell$-type estimator for the TV-loss

Let $\overline{\mathcal{M}}$ be a density model that satisfies our Assumption
1 for some ${\mathcal{M}}\subset\overline{\mathcal{M}}$. Given $P=p\cdot\mu$
and $Q=q\cdot\mu$ in ${\mathscr{M}}$, we define

(2) $t_{(P,Q)}=1\hskip-2.6pt{\rm l}_{q>p}-P(q>p)=P(p\geqslant
q)-1\hskip-2.6pt{\rm l}_{p\geqslant q}.$

Given the family ${\mathscr{T}}=\\{t_{(P,Q)},\,(P,Q)\in{\mathscr{M}}^{2}\\}$,
we define for $P,Q\in{\mathscr{M}}$ and ${\mathbf{x}}\in{\mathscr{X}}^{n}$

(3)
${\mathbf{T}}({\mathbf{x}},P,Q)=\sum_{i=1}^{n}t_{(P,Q)}(x_{i})=\sum_{i=1}^{n}\left[{1\hskip-2.6pt{\rm
l}_{q>p}(x_{i})-P(q>p)}\right]$

and

${\mathbf{T}}({\mathbf{x}},P)=\underset{Q\in{\mathscr{M}}}{\sup}{\mathbf{T}}({\mathbf{x}},P,Q).$

For ${\varepsilon}>0$, we finally define our estimator as any (measurable)
element $\widehat{P}=\widehat{p}\cdot\mu$ that belongs to the set

(4)
${\mathscr{E}}({\boldsymbol{X}})=\left\\{{P\in{\mathscr{M}},\,{\mathbf{T}}({\boldsymbol{X}},P)\leqslant\underset{P^{\prime}\in{\mathscr{M}}}{\inf}{\mathbf{T}}({\boldsymbol{X}},P^{\prime})+\varepsilon}\right\\}.$

We call $\widehat{P}$ and $\widehat{p}$ a TV-estimator on ${\mathscr{M}}$ and
${\mathcal{M}}$ respectively. The parameter ${\varepsilon}$ is introduced in
case a minimizer of $P\mapsto{\mathbf{T}}({\boldsymbol{X}},P)$ does not exist
on ${\mathscr{M}}$. Any ${\varepsilon}$-minimizer would do provided that
${\varepsilon}$ is not too large.

The construction of estimators from an appropriate family of test statistics
$t_{(P,Q)}$ is described in Baraud (2021) and our approach is in the same
line. In particular, we use the following key property on the family
${\mathscr{T}}$ (which can be compared to Assumption 1 in Baraud (2021)).

######  Lemma 1.

For all probabilities $P,Q\in{\mathscr{M}}$ and $S\in{\mathscr{P}}$,

(5)
$d\\!\left(P,Q\right)-d\\!\left(S,Q\right)\leqslant{\mathbb{E}}_{S}\left[{t_{(P,Q)}(X)}\right]\leqslant
d\\!\left(S,P\right).$

In particular,

(6)
$d\\!\left(P,Q\right)-d\\!\left(P^{\star},Q\right)\leqslant\frac{1}{n}\sum_{i=1}^{n}{\mathbb{E}}\left[{t_{(P,Q)}(X_{i})}\right]\leqslant
d\\!\left(P^{\star},P\right),$

where $P^{\star}=n^{-1}\sum_{i=1}^{n}P_{i}^{\star}$.

However, our family ${\mathscr{T}}$ does not satisfy the anti-symmetry
assumption, namely $t_{(P,Q)}=-t_{(Q,P)}$, which is required for Baraud’s
construction. The risk bound that we establish below cannot therefore be
deduced from Baraud (2021). In fact, for the specific problem we want to solve
here the anti-symmetry assumption can be relaxed which leads to an improvement
on the numerical constants that are involved in the risk bounds.

Our construction also shares some similarities with that proposed by Devroye
and Lugosi (2001)[Section 6.8 p.55]. However, a careful look at their
selection criterion shows that it is slightly different from ours. They
replace our function ${\mathbf{T}}(\cdot,P,Q)$ given by (3) by

${\mathbf{T}}_{\text{DL}}(\cdot,P,Q):{\mathbf{x}}\mapsto\left|{\sum_{i=1}^{n}\left[{1\hskip-2.6pt{\rm
l}_{q\geqslant p}(x_{i})-P(q\geqslant p)}\right]}\right|.$

Their approach leads to a set of estimators
${\mathscr{E}}_{\text{DL}}({\boldsymbol{X}})$ defined in the same way as (4)
for ${\mathbf{T}}_{\text{DL}}$ in place of ${\mathbf{T}}$ (with
${\varepsilon}=1$).

###### Proof of Lemma 1.

Let $P,Q\in{\mathscr{M}}$. Using the definition (2) of $t_{(P,Q)}$ and that of
the TV-loss given by (1), we obtain that for all $S\in{\mathscr{P}}$,

${\mathbb{E}}_{S}\left[{t_{(P,Q)}(X)}\right]=S(q>p)-P(q>p)\leqslant
d\\!\left(S,P\right),$

which is exactly the second inequality in (5). To establish the first one, we
use the fact that $d\\!\left(P,Q\right)=Q(q>p)-P(q>p)$. This leads to

$\displaystyle{\mathbb{E}}_{S}\left[{t_{(P,Q)}(X)}\right]$
$\displaystyle=S(q>p)-Q(q>p)+\left[{Q(q>p)-P(q>p)}\right]$
$\displaystyle\geqslant-d\\!\left(S,Q\right)+d\\!\left(P,Q\right).$

Finally, (6) results from the observation that

$\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[t_{(P,Q)}(X_{i})\right]=\mathbb{E}_{P^{\star}}\left[t_{(P,Q)}(X)\right].$

∎

###  3.1. Properties of the estimator

Our main result is based on the key notion of extremal point in a model.

######  Definition 1.

Let ${\mathcal{F}}$ be a class of real-valued functions on a set
${\mathscr{X}}$ with values in ${\mathbb{R}}$. We say that an element
$\overline{f}\in{\mathcal{F}}$ is extremal in ${\mathcal{F}}$ (or is an
extremal point of ${\mathcal{F}}$) with degree not larger than $D\geqslant 1$
if the classes of subsets

$\displaystyle{\mathscr{C}}^{>}({\mathcal{F}},\overline{f})$
$\displaystyle=\big{\\{}\\{x\in{\mathscr{X}}\,\big{|}\,q(x)>\overline{f}(x)\\},\;q\in{\mathcal{F}}\setminus\\{\overline{f}\\}\big{\\}}$

and

$\displaystyle{\mathscr{C}}^{<}({\mathcal{F}},\overline{f})$
$\displaystyle=\big{\\{}\\{x\in{\mathscr{X}}\,\big{|}\,q(x)<\overline{f}(x)\\},\;q\in{\mathcal{F}}\setminus\\{\overline{f}\\}\big{\\}}$

are both VC with dimension not larger than $D$.

Additionally, we say that $\overline{P}$ is an extremal point of
$\overline{\mathscr{M}}$ with degree not larger than $D\geqslant 1$ if there
exists $\overline{p}\in\overline{\mathcal{M}}$ such that
$\overline{P}=\overline{p}\cdot\mu$ and $\overline{p}$ is extremal in
$\overline{\mathcal{M}}$ with degree not larger than $D$. For each $D\geqslant
1$, we denote by $\overline{\mathcal{O}}(D)$ the set of extremal points
$\overline{p}$ in $\overline{\mathcal{M}}$ with degree not larger than $D$,
${\mathcal{O}}(D)$ a countable and dense subset of it, ${\mathscr{O}}(D)$ the
corresponding set of probability measures and
$\overline{\mathcal{O}}=\bigcup_{D\geqslant 1}\overline{\mathcal{O}}(D)$ the
set of all extremal points in $\overline{\mathcal{M}}$. Finally, let
${\mathcal{M}}$ be a countable and dense subset of $\overline{\mathcal{M}}$
containing $\bigcup_{D\geqslant 1}{\mathcal{O}}(D)$.

######  Theorem 1.

Let $\overline{\mathcal{M}}$ be a density model satisfying our Assumption 1
for which $\overline{\mathcal{O}}$ is nonempty. Any TV-estimator $\widehat{P}$
on ${\mathscr{M}}$ satisfies for all $\xi>0$ and all product distribution
${\mathbf{P}}^{\star}$, with a probability at least $1-e^{-\xi}$, for all
$D\geqslant 1$ and all $P\in\overline{\mathscr{O}}(D)$,

(7) $d\\!\left(P,\widehat{P}\right)\leqslant
2d\\!\left(P^{\star},P\right)+20\sqrt{\frac{5D}{n}}+\sqrt{\frac{2(\xi+\log
2)}{n}}+\frac{\varepsilon}{n}.$

In particular,

(8) $\displaystyle
d\\!\left(P^{\star},\widehat{P}\right)\leqslant\inf_{D\geqslant
1}\left[{3\inf_{P\in\overline{\mathscr{O}}(D)}d\\!\left(P^{\star},P\right)+20\sqrt{\frac{5D}{n}}}\right]+\sqrt{\frac{2(\log
2+\xi)}{n}}+\frac{\varepsilon}{n},$

with the convention $\inf_{\varnothing}=+\infty$. As a consequence of (7),

(9) $\mathbb{E}\left[d\\!\left(P,\widehat{P}\right)\right]\leqslant
2d\\!\left(P^{\star},P\right)+48\sqrt{\frac{D}{n}}+\frac{\varepsilon}{n}$

for all $D\geqslant 1$ and all $P\in\overline{\mathscr{O}}(D)$, moreover by
(8),

(10)
$\mathbb{E}\left[{d\\!\left(P^{\star},\widehat{P}\right)}\right]\leqslant\inf_{D\geqslant
1}\left\\{3\inf_{P\in\overline{\mathscr{O}}(D)}d\\!\left(P^{\star},P\right)+48\sqrt{\frac{D}{n}}\right\\}+\frac{\varepsilon}{n}.$

###### Proof.

The proof is postponed to Subsection 7.2. ∎

Let us now comment on this result.

In the favourable situation where the $X_{i}$ are i.i.d. with distribution
$P^{\star}$ in $\overline{\mathscr{O}}$, $\inf_{D\geqslant
1}\inf_{P\in\overline{\mathscr{O}}(D)}d\\!\left(P^{\star},P\right)=0$ and we
deduce from (10) that the estimator $\widehat{P}$ converges toward $P^{\star}$
at rate $1/\sqrt{n}$ for the total variation distance. More precisely, the
risk of the estimator is not larger than $48\sqrt{D/n}+{\varepsilon}/n$ when
$P^{\star}$ belongs to $\overline{\mathscr{O}}(D)$ for some $D\geqslant 1$.
Note that the result also holds when the data are independent only, provided
that $P^{\star}=n^{-1}\sum_{i=1}^{n}P_{i}^{\star}$ is extremal. This situation
may occur even when none of the marginals $P_{i}^{\star}$ is extremal or even
belongs to the model ${\mathscr{M}}$.

In the general case where the data are independent only and their marginals
write for all $i\in\\{1,\ldots,n\\}$ as

(11)
$P_{i}^{\star}=(1-\alpha_{i})\overline{P}+\alpha_{i}R_{i}=\overline{P}+\alpha_{i}\left({R_{i}-\overline{P}}\right)$

for some $\overline{P}\in\overline{\mathscr{O}}(D)$ with $D\geqslant 1$,
$\alpha_{1},\ldots,\alpha_{n}$ in $[0,1]$ and distributions
$R_{1},\ldots,R_{n}$ in ${\mathscr{P}}$, we deduce from (9) that

$\displaystyle\mathbb{E}\left[{d\\!\left(\overline{P},\widehat{P}\right)}\right]$
$\displaystyle\leqslant
2d\\!\left(P^{\star},\overline{P}\right)+48\sqrt{\frac{D}{n}}+\frac{\varepsilon}{n}$
$\displaystyle\leqslant\frac{2}{n}\sum_{i=1}^{n}\alpha_{i}+48\sqrt{\frac{D}{n}}+\frac{\varepsilon}{n}.$

As compared to the previous situation where
$P_{i}^{\star}=\overline{P}\in\overline{\mathscr{O}}(D)$, hence $\alpha_{i}=0$
for all $i$, we see that the risk bound we get only inflates by the additional
term $2\overline{\alpha}=(2/n)\sum_{i=1}^{n}\alpha_{i}$ and it remains thus of
the same order when $\overline{\alpha}$ is small enough as compared to
$\sqrt{D/n}$. Note that this situation may occur even when $\alpha_{i}>0$ for
all $i$, i.e. when none of the marginals $P_{i}^{\star}$ belongs to
$\overline{\mathscr{O}}(D)$. In order to be more specific, we may consider the
two following situations. In the first one, there exists some subset of the
data which are i.i.d. with distribution
$\overline{P}\in\overline{\mathscr{O}}(D)$ while the other part, corresponding
to what we shall call outliers, are independently drawn according to some
arbitrary distributions. In this case, there exists a subset
$S\subset\\{1,\ldots,n\\}$ such that $\alpha_{i}=1$ for $i\in S$ and
$\alpha_{i}=0$ otherwise in (11). Our procedure is stable with respect to the
presence of such outliers as soon as $\overline{\alpha}=|S|/n$ remains small
as compared to $\sqrt{D/n}$. In the other situation, which is called the
contamination case, the data are i.i.d., a portion $\alpha\in(0,1]$ of them
are drawn according to an arbitrary distribution $R$ while the other part
follows the distribution $\overline{P}\in\overline{\mathscr{O}}(D)$. Then (11)
holds with $\alpha_{i}=\alpha$ and $R_{i}=R$ for all $i\in\\{1,\ldots,n\\}$.
The risk bound we get remains of the stable under contamination as long as the
level $\overline{\alpha}=\alpha$ of contamination remains small as compared to
$\sqrt{D/n}$.

A bound similar to (8) has been established in Baraud (2021) for his
$\ell$-estimators. His inequality (48) can be reformulated in our context as

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}d\\!\left(P_{i}^{\star},\widehat{P}\right)\leqslant$
$\displaystyle\inf_{D\geqslant
1}\left[{6\inf_{P\in\overline{\mathscr{O}}(D)}\left[{\frac{1}{n}\sum_{i=1}^{n}d\\!\left(P_{i}^{\star},P\right)}\right]+40\sqrt{\frac{5D}{n}}}\right]+2\sqrt{\frac{2\xi}{n}}+\frac{2\varepsilon}{n}$
$\displaystyle\quad-\inf_{P\in\overline{\mathscr{M}}}\left[{\frac{1}{n}\sum_{i=1}^{n}d\\!\left(P_{i}^{\star},P\right)}\right].$

In comparison, equation (9) and the triangle inequality imply that

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}d\\!\left(P_{i}^{\star},\widehat{P}\right)$
$\displaystyle\leqslant\inf_{D\geqslant
1}\left[{3\inf_{P\in\overline{\mathscr{O}}(D)}\left[{\frac{1}{n}\sum_{i=1}^{n}d\\!\left(P_{i}^{\star},P\right)}\right]+20\sqrt{\frac{5D}{n}}}\right]$
$\displaystyle\quad+\sqrt{\frac{2(\log 2+\xi)}{n}}+\frac{\varepsilon}{n}$

If we omit the term
$\inf_{P\in\overline{\mathscr{M}}}\left[{\frac{1}{n}\sum_{i=1}^{n}d\\!\left(P_{i}^{\star},P\right)}\right]$
that appears in his inequality and $\log 2$ that appears in ours, all the
constants we get are divided by a factor 2 as compared to his.

When the Yatracos class $\\{\\{p>q\\},p,q\in\overline{\mathcal{M}}\\}$ is VC
with dimension not larger than $D\geqslant 1$, all the elements of
$\overline{\mathcal{M}}$ are extremal with degree not larger than $D$ and (10)
becomes

(12)
$\displaystyle{\mathbb{E}}\left[{d\\!\left(P^{\star},\widehat{P}\right)}\right]\leqslant
3\inf_{P\in\overline{\mathscr{M}}}d\\!\left(P^{\star},P\right)+48\sqrt{\frac{D}{n}}+\frac{\varepsilon}{n}.$

In the particular case of i.i.d. data with common distribution $P^{\star}$, an
inequality of the same flavour was established by Devroye and Lugosi
(2001)[Section 8.2] for their minimum distance estimate. Both inequalities
involve a constant 3 in front of the approximation term
$\inf_{P\in\overline{\mathscr{M}}}d\\!\left(P^{\star},P\right)$. In our
inequality the numerical constants are explicit.

In the next sections, we take advantage of the stronger inequality (8) to
consider density models $\overline{\mathcal{M}}$ for which the Yatracos
classes $\\{\\{p>q\\},p,q\in\overline{\mathcal{M}}\\}$ are not VC.

In the remaining part of this paper,
$({\mathscr{X}},{\mathscr{A}})=({\mathbb{R}},{\mathscr{B}}({\mathbb{R}}))$ and
$\mu$ is the Lebesgue measure on ${\mathbb{R}}$. Since
${\mathbb{L}}_{1}({\mathbb{R}},{\mathscr{B}}({\mathbb{R}}),\mu)$ is separable,
Assumption 1 is automatically satisfied. Each of the forthcoming sections is
devoted to the problem of estimating densities or a mixture of densities with
respect to $\mu$ under the assumption that they satisfy one of the following
shape constraint: monotonicity, concavity, convexity or $\log$-concavity.

##  4\. Estimating a piecewise monotone density

We denote by ${\mathcal{A}}(k)$ the class of nonempty subsets
$A\subset{\mathbb{R}}$ with cardinality not larger than $k\geqslant 1$. The
elements of $A$ provide a partition of ${\mathbb{R}}$ into $l=|A|+1\leqslant
k+1$ intervals $I_{1},\ldots,I_{l}$ the endpoints of which belong to $A$. We
denote by ${\mathbf{I}}(A)$ the set
$\\{\mathring{I}_{1},\ldots,\mathring{I}_{l}\\}$ of their interiors. Although
there exist several ways of partitioning ${\mathbb{R}}$ into intervals with
endpoints in $A$, the set ${\mathbf{I}}(A)$ is uniquely defined.

###  4.1. Piecewise monotone densities

######  Definition 2.

Let $k\geqslant 2$. A function $g$ on ${\mathbb{R}}$ is said to be
$k$-piecewise monotone if there exists $A\in{\mathcal{A}}(k-1)$ such that the
restriction of $g$ to each interval $I\in{\mathbf{I}}(A)$ is monotone. In
particular, there exist at most $k$ monotone functions $g_{I}$ on
$I\in{\mathbf{I}}(A)$ such that

$g(x)=\sum_{I\in{\mathbf{I}}(A)}g_{I}(x)1\hskip-2.6pt{\rm
l}_{I}(x)\quad\text{for all $x\in{\mathbb{R}}\setminus A$.}$

A $k$-piecewise monotone function $g$ associated to $A\in{\mathcal{A}}(k-1)$
may not be monotone on each element of a partition based on $A$. We only
require that $g$ be monotone on the interiors of these elements. The function

$\begin{array}[]{l|rcl}g:&{\mathbb{R}}&\longrightarrow&{\mathbb{R}}_{+}\\\
&x&\longmapsto&{\frac{1}{\sqrt{|x|}}1\hskip-2.6pt{\rm l}_{|x|>0}}\end{array}$

is 2-piecewise monotone, associated to $A=\\{0\\}\in{\mathcal{A}}(1)$, but $g$
is neither monotone on $(-\infty,0]$ nor on $[0,+\infty)$.

We denote by $\overline{\mathcal{M}}_{k}$ the set of $k$-piecewise monotone
densities. The sets $\overline{\mathcal{M}}_{k}$ are obviously increasing with
$k$ for the inclusion. The set $\overline{\mathcal{M}}_{2}$ contains the
unimodal densities on the line and in particular all the densities that are
monotone on a half-line and vanish elsewhere.

Of special interest are those densities in $\overline{\mathcal{M}}_{k}$ which
are also piecewise constant on a finite partition of ${\mathbb{R}}$ into
intervals. More precisely, for $D\geqslant 1$ let
$\overline{\mathcal{O}}_{D,k}$ be the subset of $\overline{\mathcal{M}}_{k}$
that consists of those densities that are constant on each element of a class
${\mathbf{I}}(A)$ with $A\in{\mathcal{A}}(D+1)$. The number $D$ is a bound on
the number of bounded intervals in the class, hence on the number of positive
values that a density in $\overline{\mathcal{O}}_{D,k}$ may take. The uniform
distribution on a nontrivial interval has a density that belongs to
$\overline{\mathcal{O}}_{1,2}$, and also to $\overline{\mathcal{O}}_{D,k}$ for
all $D\geqslant 1$ and $k\geqslant 2$. The sets $\overline{\mathcal{O}}_{D,k}$
with $D\geqslant 1$ and $k\geqslant 2$ are therefore nonempty. They satisfy
the following property which is a consequence of Proposition 3 of Baraud and
Birgé (2016).

######  Proposition 1.

For all $D\geqslant 1$ and $k\geqslant 2$, all the elements of
$\overline{\mathcal{O}}_{D,k}$ are extremal in $\overline{\mathcal{M}}_{k}$
with degree not larger than $3(k+D+1)$.

###### Proof.

The proof is postponed to Subsection 7.3. ∎

For all $D\geqslant 1$ and $k\geqslant 2$, let ${\mathcal{O}}_{D,k}$ be a
countable and dense subset of $\overline{\mathcal{O}}_{D,k}$ (for the
${\mathbb{L}}_{1}$-norm) and ${\mathcal{M}}_{k}$ a countable and dense subset
of $\overline{\mathcal{M}}_{k}$ that contains $\bigcup_{D\geqslant
1}{\mathcal{O}}_{D,k}$. It follows from Proposition 1 that the elements of
${\mathcal{O}}_{D,k}$ are also extremal in ${\mathcal{M}}_{k}$ with degree not
larger than $3(k+D+1)$ for all $D\geqslant 1$. We immediately deduce from
Theorem 1 the following result.

######  Theorem 2.

Let $k\geqslant 2$. Whatever the product distribution ${\mathbf{P}}^{\star}$
of the data, any TV-estimator $\widehat{P}$ on ${\mathscr{M}}_{k}$ satisfies

(13)
$\mathbb{E}\left[{d\\!\left(P^{\star},\widehat{P}\right)}\right]\leqslant\inf_{D\geqslant
1}\left[{3\inf_{P\in\overline{\mathscr{O}}_{D,k}}d\\!\left(P^{\star},P\right)+83.2\sqrt{\frac{D+k+1}{n}}}\right]+\frac{\varepsilon}{n}.$

Our approach solves the problem of estimating a nonincreasing density on a
half-line $I$ by taking $k=2$. For this specific problem, a bound of the same
flavour was established by Baraud (2021) (see Proposition 6) for his
$\ell$-estimator. When the data are i.i.d. with distribution $P^{\star}$, our
result shows better constants in the risk bound (13) as compared to Baraud’s.
In particular, the constant 3 in front of the approximation term
$\inf_{P\in\overline{\mathscr{O}}_{D,k}}d\\!\left(P^{\star},P\right)$ improves
on his constant 5. Our estimator (as well as Baraud’s) also improves on the
Grenander estimator since our construction does not require the prior
knowledge of the half-line $I$.

For general values of $k\geqslant 2$, the problem of estimating a
$k$-piecewise monotone density was also considered in Baraud and Birgé (2016).
The authors used a $\rho$-estimator and the Hellinger loss in place of the
total variation one to evaluate its risk— see their Corollary 2. Their bound
is similar to ours except from the fact that the quantity $\sqrt{(D+k+1)/n}$
appears there multiplied by a logarithmic factor. This logarithmic factor
turns out to be necessary when one deals with the Hellinger loss while it
disappears with the total variation one.

In order to specify further the risk bound given by (13), and see what
properties can be established on our estimator, let us consider different
assumptions on the distribution of the data. These assumptions can be done a
posteriori, since the estimator is solely based on the model
$\overline{\mathscr{M}}_{k}$ (or a dense subset of it). Such assumptions
enable us to bound the quantity

$A=\inf_{D\geqslant
1}\left[{3\inf_{P\in\overline{\mathscr{O}}_{D,k}}d\\!\left(P^{\star},P\right)+83.2\sqrt{\frac{D+k+1}{n}}}\right]$

that appear in the right-hand side of (13).

If the $X_{i}$ are not i.i.d. but only independent and their marginals are
close enough to a distribution of the form
$\overline{P}=\overline{p}\cdot\mu$, by the triangle inequality we may bound
$A$ by
$3d\\!\left(P^{\star},\overline{P}\right)+{\mathbb{B}}_{k,n}(\overline{p})$
where ${\mathbb{B}}_{k,n}(p)$ is defined for a density $p$ on the line by the
formulas

$\displaystyle{\mathbb{B}}_{k,n}(p)$ $\displaystyle=\inf_{D\geqslant
1}\left[{3\inf_{Q\in\overline{\mathscr{O}}_{D,k}}d\\!\left(P,Q\right)+83.2\sqrt{\frac{D+k+1}{n}}}\right]$
(14) $\displaystyle=\inf_{D\geqslant
1}\left[{\frac{3}{2}\inf_{q\in\overline{\mathcal{O}}_{D,k}}\left\|{p-q}\right\|+83.2\sqrt{\frac{D+k+1}{n}}}\right].$

This means that as long as $3d\\!\left(P^{\star},\overline{P}\right)$ remains
small as compared to ${\mathbb{B}}_{k,n}(\overline{p})$, the bound on
${\mathbb{E}}[d(P^{\star},\widehat{P})]$ would be almost the same as if the
$X_{i}$ were truly i.i.d. with distribution
$\overline{P}=\overline{p}\cdot\mu$. This property accounts for the robustness
of our approach.

If we apply a location-scale transformation to the data, that is, if in place
of the original data $X_{1},\ldots,X_{n}$ with density $\overline{p}$ we
observe the random variables $Y_{i}=\sigma X_{i}+m$ for $i\in\\{1,\ldots,n\\}$
with $(m,\sigma)\in{\mathbb{R}}\times(0,+\infty)$, the density
$\overline{p}_{m,\sigma}$ of the new data would satisfy
${\mathbb{B}}_{k,n}(\overline{p}_{m,\sigma})={\mathbb{B}}_{k,n}(\overline{p})$
since the set $\overline{\mathcal{O}}_{D,k}$ and the total variation distance
remain invariant under such a transformation. This means that the performance
of the TV-estimator is independent of the unit that is used to measure the
data.

In the remaining part this section, we provide upper bounds on the quantity
${\mathbb{B}}_{k,n}(p)$ for some densities $p\in\overline{\mathcal{M}}_{k}$ of
special interest.

###  4.2. Estimation of bounded and compactly supported $k$-piecewise monotone
densities

For $k\geqslant 3$, let $\overline{\mathcal{M}}_{k}^{\infty}$ be the subset of
$\overline{\mathcal{M}}_{k}$ that consists of the densities on ${\mathbb{R}}$
which coincide almost everywhere with a density of the form

(15) $p=\sum_{i=1}^{k-2}w_{i}p_{i}1\hskip-2.6pt{\rm l}_{(x_{i-1},x_{i})}$

where

  1. (i)

$(x_{i})_{i\in\\{0,\ldots,k-2\\}}$ is an increasing sequence of real numbers;

  2. (ii)

$w_{1},\ldots,w_{k-2}$ are nonnegative numbers such that
$\sum_{i=1}^{k-2}w_{i}=1$;

  3. (iii)

for $i\in\\{1,\ldots,k-2\\}$, $p_{i}$ is a monotone density on the interval
$I_{i}=(x_{i-1},x_{i})$ of length $L_{i}>0$ with variation

$V_{i}=\sup_{x\in I_{i}}p_{i}(x)-\inf_{x\in I_{i}}p_{i}(x)<+\infty.$

A density $p$ in $\overline{\mathcal{M}}_{k}^{\infty}$ is necessarily bounded
and compactly supported. A monotone density on ${\mathbb{R}}_{+}$ which is
bounded and compactly supported belongs to
$\overline{\mathcal{M}}_{3}^{\infty}$. A bounded unimodal density supported on
a compact interval belongs to $\overline{\mathcal{M}}_{4}^{\infty}$.

For $p\in\overline{\mathcal{M}}_{k}^{\infty}$, we set

(16)
$\boldsymbol{R}_{k,0}(p)=\inf\left[{\sum_{i=1}^{k-2}\sqrt{w_{i}\log\left({1+L_{i}V_{i}}\right)}}\right]^{2}$

where the infimum runs among all ways of writing $p$ under the form (15) a.e.
Note that we allow some of the $w_{i}$ to be zero in which case the
corresponding densities $p_{i}$ may be chosen arbitrarily and their choices do
not contribute to the value of $\boldsymbol{R}_{k,0}(p)$. For $k\geqslant 3$
and $R>0$, let $\overline{\mathcal{M}}_{k}^{\infty}(R)$ be the subset of
$\overline{\mathcal{M}}_{k}^{\infty}$ that gathers these densities $p$ for
which $\boldsymbol{R}_{k,0}(p)<R$. When a density $p$ belongs to
$\overline{\mathcal{M}}_{k}^{\infty}(R)$, we may therefore write $p$ under the
form (15) a.e. with $L_{i}$ and $V_{i}$ such that
$\left[{\sum_{i=1}^{k-2}\sqrt{w_{i}\log\left({1+L_{i}V_{i}}\right)}}\right]^{2}<R$.
The classes of sets $(\overline{\mathcal{M}}_{k}^{\infty})_{k\geqslant 3}$ and
$(\overline{\mathcal{M}}_{k}^{\infty}(R))_{k\geqslant 3}$ are both increasing
(for the inclusion): if $p\in\overline{\mathcal{M}}_{l}^{\infty}(R)$ with
$l<k$, we may write

$p=\sum_{i=1}^{l-2}w_{i}p_{i}1\hskip-2.6pt{\rm
l}_{(x_{i-1},x_{i})}\quad\text{a.e.\
with}\quad\left[{\sum_{i=1}^{l-2}\sqrt{w_{i}\log\left({1+L_{i}V_{i}}\right)}}\right]^{2}<R$

and alternatively

$p=\sum_{i=1}^{l-2}w_{i}p_{i}1\hskip-2.6pt{\rm
l}_{(x_{i-1},x_{i})}+\sum_{j=l-1}^{k-2}0\times 1\hskip-2.6pt{\rm
l}_{(x_{i}+j-l+1),x_{i}+j-l+2)}\ \text{a.e.}$

hence, $p\in\overline{\mathcal{M}}_{k}^{\infty}$ and

$\boldsymbol{R}_{k,0}(p)\leqslant\left[{\sum_{i=1}^{l-2}\sqrt{w_{i}\log\left({1+L_{i}V_{i}}\right)}+0}\right]^{2}<R.$

It is not difficult to check that the set
$\overline{\mathcal{M}}_{k}^{\infty}(R)$ is invariant under a location-scale
transformation.

######  Theorem 3.

Let $k\geqslant 3$ and $R>0$. If $p\in\overline{\mathcal{M}}_{k}^{\infty}(R)$,

(17) ${\mathbb{B}}_{k,n}(p)\leqslant
41.3\left({\frac{R}{n}}\right)^{1/3}+83.2\sqrt{\frac{2k}{n}}.$

This result is to our knowledge new in the literature. We deduce that the
minimax risk for the ${\mathbb{L}}_{1}$-norm over
$\overline{\mathcal{M}}_{k}^{\infty}(R)$ is not larger than $(R/n)^{1/3}\vee
kn^{-1/2}$ up to a positive multiplicative constant. For large enough values
of $n$, the bound is of order $(R/n)^{1/3}$ while for moderate ones and values
of $R$ which are close enough to 0, which means that the densities in
$\overline{\mathcal{M}}_{k}^{\infty}(R)$ are close to a mixture of $k-2$
uniform distributions, the bound is of order $\sqrt{k/n}$.

It is interesting to compare this result to that established in Baraud and
Birgé (2016)[page 3900] for their $\rho$-estimators. For the problem of
estimating a bounded unimodal density $p$ supported on an interval of length
$L$, which is an element of $\overline{\mathcal{M}}_{4}$, Baraud and Birgé
show that the Hellinger risk of the $\rho$-estimator is not larger than
$(\sqrt{L\left\|{p}\right\|_{\infty}}/n)^{1/3}\log n$ up to some numerical
constant. With our $\ell$-estimator, the bound we get is of order
$(\log(1+L\left\|{p}\right\|_{\infty})/n)^{1/3}$ and only depends
logarithmically on the quantity $L\left\|{p}\right\|_{\infty}$ (which is not
smaller than 1 since $p$ is a density).

###### Proof.

The proof of Theorem 3 is based on (14) and the following approximation
result. The complete proof is postponed to subsection 7.3. ∎

######  Proposition 2.

Let $V\geqslant 0$ and $I$ be a bounded interval of length $L>0$. For all
$D\geqslant 1$, there exists a partition ${\mathcal{J}}={\mathcal{J}}(D,L,V)$
of $I$ into $D\geqslant 1$ nontrivial intervals with the following properties.
For any monotone density $p$ on $I$ for which

$V_{I}(p)=\sup_{x\in\mathring{I}}p(x)-\inf_{x\in\mathring{I}}p(x)\leqslant V,$

the function $\overline{p}=\overline{p}({\mathcal{J}})$ defined by

$\overline{p}=\sum_{J\in{\mathcal{J}}}\overline{p}_{J}1\hskip-2.6pt{\rm
l}_{J}\quad\text{with}\quad\overline{p}_{J}=\frac{1}{\mu(J)}\int_{J}p\;d\mu,$

is a monotone density on $I$ that satisfies

(18)
$\int_{I}\left|{p-\overline{p}}\right|d\mu\leqslant\left[{(1+VL)^{1/D}-1}\right]\wedge
2\leqslant\frac{2\log\left({1+VL}\right)}{D}.$

###### Proof.

The proof is postponed to subsection 7.3. ∎

Although the result is hidden in his calculations, Birgé (1987) has
established a bound of the same flavour except from the fact that the
variation $V$ is replaced by a uniform bound on $p$. Unlike his, our bound
(18) allows to recover the fact that when $V=0$, i.e. when $p$ is constant on
$I$, the left-hand side equals 0 as expected. The combination of Theorem 2 and
Theorem 3 immediately leads to the following corollary:

######  Corollary 1.

Let $k\geqslant 3$. If $X_{1},\dots,X_{n}$ is a $n$ sample which density
$p\in\overline{\mathcal{M}}_{k}^{\infty}(R)$, then the TV-estimator
$\widehat{p}$ on ${\mathcal{M}}_{k}$ satisfies

(19) $\mathbb{E}\left[{\|p-\widehat{p}\|}\right]\leqslant
82.6\left({\frac{R}{n}}\right)^{1/3}+166.4\sqrt{\frac{2k}{n}}+\frac{2\varepsilon}{n}.$

###  4.3. Estimation of other $k$-piecewise monotone densities

Corollary 1 provides an upper bound on the ${\mathbb{L}}_{1}$-risk of the TV-
estimator for estimating a density $p\in\overline{\mathcal{M}}_{k}^{\infty}$.
A natural question is how the estimator performs when the density $p$ is
neither bounded nor supported on a compact interval. Since for such densities
we may write

(20)
${\mathbb{B}}_{k,n}(p)\leqslant\inf_{\overline{p}\in\overline{\mathcal{M}}_{k}^{\infty}}\left[{\frac{3}{2}\left\|{p-\overline{p}}\right\|+{\mathbb{B}}_{k,n}(\overline{p})}\right],$

an upper bound on ${\mathbb{B}}_{k,n}(p)$ can be obtained by combining Theorem
3 with an approximationt result showing how general densities in
$\overline{\mathcal{M}}_{k}$ can be approximated by elements of
$\overline{\mathcal{M}}_{k}^{\infty}$. In this section, we therefore study the
approximation properties of the set $\overline{\mathcal{M}}_{k}^{\infty}$ with
respect to possibly unbounded and non-compactly supported densities. We start
with the case of a monotone density on a half-line and introduce the following
definitions.

######  Definition 3.

Given a nonincreasing density $p$ on $(a,+\infty)$ with $a\in{\mathbb{R}}$, we
define $\widetilde{p}$ as the mapping on $(0,+\infty)$ given by

(21) $\widetilde{p}(y)=\inf\left\\{{x>0,\;p(a+x)<y}\right\\}\geqslant 0.$

We define the $x$-tail function $\tau_{x}(p,\cdot)$ associated to $p$ as

$\begin{array}[]{l|rcl}\tau_{x}(p,\cdot):&[0,+\infty)&\longrightarrow&{\mathbb{R}}_{+}\\\
&t&\longmapsto&\displaystyle{\int_{t}^{+\infty}p(a+x)d\mu(x)}\end{array},$

the $y$-tail function $\tau_{y}(p,\cdot)$ as

$\begin{array}[]{l|rcl}\tau_{y}(p,\cdot):&[0,+\infty)&\longrightarrow&{\mathbb{R}}_{+}\\\
&t&\longmapsto&\displaystyle{\int_{t}^{+\infty}\widetilde{p}(y)d\mu(y)}\end{array}$

and the tail function $\tau(p,\cdot)$ as

(22)
$\tau(p,t)=\inf_{s>0}\left[{\tau_{x}(p,st)+\tau_{y}(p,p(a+s))}\right]\quad\text{for
all $t\geqslant 1$}.$

When $p$ is a nondecreasing density on $(-\infty,-a)$ with $a\in{\mathbb{R}}$,
we define $\tau_{x}(p,\cdot)$, $\tau_{y}(p,\cdot)$ and $\tau(p,\cdot)$ as
respectively the $x$-tail, $y$-tail and tail functions of the nonincreasing
density $x\mapsto p(-x)$ .

Let us comment these definitions. When $p$ is a continuous decreasing density
from $(0,+\infty)$ onto $(0,+\infty)$, $\widetilde{p}$ is the reciprocal
function $p^{-1}$. By taking the symmetric of the graph $x\mapsto p(x)$ with
respect to the first diagonal, we easily see that $\widetilde{p}=p^{-1}$ is a
nonincreasing density on $(0,+\infty)$. This property remains true in the
general case as shown by the lemma below with the special value $B=0$. As a
consequence, $\tau_{y}(p,\cdot)$ can be interpreted as the tail of the
distribution function associated to the density $\widetilde{p}$ while
$\tau_{x}(p,\cdot)$ is that of $p(a+\cdot)$.

######  Lemma 2.

Let $p$ be a nonincreasing density on $(a,+\infty)$ with $a\in{\mathbb{R}}$
and $\widetilde{p}$ the mapping defined by (21). For all $B\geqslant 0$,

(23)
$\int_{0}^{+\infty}\left[{p(a+x)-B}\right]_{+}d\mu(x)=\int_{B}^{+\infty}\widetilde{p}(y)d\mu(y)=\tau_{y}(p,B).$

By changing $p$ into $x\mapsto p(-x)$, we also obtain that when $p$ is
nondecreasing on $(-\infty,-a)$,

$\int_{-\infty}^{0}\left[{p(-a+x)-B}\right]_{+}d\mu(x)=\int_{B}^{+\infty}\widetilde{p}(y)d\mu(y)=\tau_{y}(p,B)\quad\text{for
all $B\geqslant 0$.}$

###### Proof.

Let $y>0$. Since $p$ is nonincreasing density on $(a,+\infty)$, it necessarily
tends to 0 at $+\infty$. The set $I(y)=\left\\{{x>0,\;p(a+x)<y}\right\\}$ is
therefore a nonempty unbounded interval with endpoint
$\widetilde{p}(y)<+\infty$ by definition of $\widetilde{p}(y)$. In particular,

$(\widetilde{p}(y),+\infty)\subset I(y)\subset[\widetilde{p}(y),+\infty),$

and by taking the complementary of those sets we obtain that for all
$(x,y)\in(0,+\infty)\times(0,+\infty)$

$1\hskip-2.6pt{\rm l}_{x<\widetilde{p}(y)}\leqslant 1\hskip-2.6pt{\rm
l}_{p(a+x)\geqslant y}\leqslant 1\hskip-2.6pt{\rm
l}_{x\leqslant\widetilde{p}(y)}.$

Integrating these inequalities on $(0,+\infty)\times(B,+\infty)$ with respect
to $\mu\otimes\mu$ and using Fubini’s theorem, we obtain that

$\displaystyle\int_{B}^{+\infty}\widetilde{p}(y)d\mu(y)$
$\displaystyle=\int_{B}^{+\infty}\left[{\int_{0}^{+\infty}1\hskip-2.6pt{\rm
l}_{x<\widetilde{p}(y)}d\mu(x)}\right]d\mu(y)\leqslant\int_{B}^{+\infty}\left[{\int_{0}^{+\infty}1\hskip-2.6pt{\rm
l}_{p(a+x)\geqslant y}d\mu(x)}\right]d\mu(y)$
$\displaystyle=\int_{0}^{+\infty}\left[{\int_{B}^{+\infty}1\hskip-2.6pt{\rm
l}_{p(a+x)\geqslant
y}d\mu(y)}\right]d\mu(x)=\int_{a}^{+\infty}\left[{p(a+x)-B}\right]_{+}d\mu(x)$
$\displaystyle\leqslant\int_{B}^{+\infty}\left[{\int_{0}^{+\infty}1\hskip-2.6pt{\rm
l}_{x\leqslant\widetilde{p}(y)}d\mu(x)}\right]d\mu(y)=\int_{B}^{+\infty}\widetilde{p}(y)d\mu(y),$

which proves (23). ∎

It follows from (23) that if $p$ is a nonincreasing density on $(a,+\infty)$,
$\tau(p,t)$ also writes for all $t\geqslant 1$ as

$\tau(p,t)=\inf_{s>0}\left[{\int_{st}^{+\infty}p(a+x)d\mu(x)+\int_{0}^{s}\left[{p(a+x)-p(a+s)}\right]d\mu(x)}\right].$

It is not difficult to check that the mapping $\tau(p,\cdot)$ is nonincreasing
on $[1,+\infty)$, tends to 0 at $+\infty$ and is invariant under a location-
scale transformation, i.e. by changing $p$ into the density
$\sigma^{-1}p[\sigma^{-1}(\cdot-m)]$ on $(\sigma a+m,+\infty)$ with
$m\in{\mathbb{R}}$ and $\sigma>0$.

We consider the general situation where $p$ is an arbitrary element of
$\overline{\mathcal{M}}_{\ell}$ with $\ell\geqslant 2$. Changing the values of
$p$, if ever necessary, on a negligible set, which will not change the way it
can be approximated in ${\mathbb{L}}_{1}$-norm, we may assume with no loss of
generality that it writes as

(24) $p=w_{1}p_{1}1\hskip-2.6pt{\rm
l}_{(-\infty,x_{1})}+\sum_{i=2}^{\ell-1}w_{i}p_{i}1\hskip-2.6pt{\rm
l}_{(x_{i-1},x_{i})}+w_{\ell}p_{\ell}1\hskip-2.6pt{\rm
l}_{(x_{\ell-1},+\infty)}$

where $p_{1}$ and $p_{\ell}$ are monotone densities on $(-\infty,x_{1})$ and
$(x_{\ell-1},+\infty)$ respectively, $w_{1}=\int_{-\infty}^{x_{1}}pd\mu$,
$w_{\ell}=\int_{x_{\ell}}^{+\infty}pd\mu$ and when $\ell>2$,
$x_{1}<x_{2}<\ldots<x_{\ell-1}$ is an increasing sequence of real numbers, the
$p_{i}$ are monotone densities on $(x_{i-1},x_{i})$ and
$w_{i}=\int_{x_{i-1}}^{x_{i}}pd\mu$ for all $i\in\\{2,\ldots,\ell-1\\}$. For
$p$ written under the form (24), we set

(25)
$\tau_{\infty}(p,t)=\max_{i\in\\{1,\ldots,\ell\\}}\tau\left({p_{i},t}\right)\quad\text{for
all $t\geqslant 1$.}$

The mapping $t\mapsto\tau(p,t)$ is nonincreasing on ${\mathbb{R}}_{+}$ and
tends to 0 at $+\infty$.

######  Theorem 4.

Let $\ell\geqslant 2$, $k\geqslant 2\ell$ and $R\geqslant\ell\log 2$. If $p$
is a density of the form (24) a.e.,

(26)
$\inf_{\overline{p}\in\overline{\mathcal{M}}_{k}^{\infty}(R)}\left\|{p-\overline{p}}\right\|\leqslant
2\tau_{\infty}\left({p,\exp\left({\frac{R}{\ell}}\right)-1}\right).$

###### Proof.

The proof is postponed to Subsection 7.3. ∎

By combining Theorem 3 and Theorem 4 we obtain the following corollary.

######  Corollary 2.

Let $\ell\geqslant 2$ and $k\geqslant 2\ell$. If $p$ is a density of the form
(24) a.e.,

(27) ${\mathbb{B}}_{k,n}(p)\leqslant
44.3\left({\frac{\ell\log(1+r_{n})}{n}}\right)^{1/3}+83.2\sqrt{\frac{2k}{n}}$

where

(28) $r_{n}=\inf\left\\{{t\geqslant
1,\;\tau_{\infty}(p,t)\leqslant\left({\frac{\ell\log(1+t)}{n}}\right)^{1/3}}\right\\}$

and $\tau_{\infty}(p,\cdot)$ is defined by (25). Then, the TV-estimator
$\widehat{p}$ on ${\mathcal{M}}_{k}$ satisfies

(29) $\mathbb{E}\left[{\|p-\widehat{p}\|}\right]\leqslant
88.6\left({\frac{\ell\log(1+r_{n})}{n}}\right)^{1/3}+166.4\sqrt{\frac{2k}{n}}+\frac{2\varepsilon}{n}.$

###### Proof.

Since $\tau_{\infty}(p,\cdot)$ tends to 0 at $+\infty$, the set

${\mathcal{R}}=\left\\{{t\geqslant
1,\;\tau_{\infty}(p,t)\leqslant\left({\frac{\ell\log(1+t)}{n}}\right)^{1/3}}\right\\}$

is nonempty, $r_{n}$ is well-defined and for all $t>r_{n}\geqslant 1$,

$\tau_{\infty}(p,t)\leqslant\left({\frac{\ell\log(1+t)}{n}}\right)^{1/3}.$

Using (20), Theorems 3 and 4 with $R=\ell\log(1+t)>\ell\log 2$ we obtain that

$\displaystyle{\mathbb{B}}_{k,n}(p)$
$\displaystyle\leqslant\frac{3}{2}\inf_{\overline{p}\in\overline{\mathcal{M}}_{k}^{\infty}(R)}\left\|{p-\overline{p}}\right\|+\sup_{\overline{p}\in\overline{\mathcal{M}}_{k}^{\infty}(R)}{\mathbb{B}}_{k,n}(\overline{p})$
$\displaystyle\leqslant
3\tau_{\infty}\left({p,t}\right)+41.3\left({\frac{\ell\log(1+t)}{n}}\right)^{1/3}+83.2\sqrt{\frac{2k}{n}}$
$\displaystyle\leqslant
44.3\left({\frac{\ell\log(1+t)}{n}}\right)^{1/3}+83.2\sqrt{\frac{2k}{n}},$

and the result follows from the fact that $t$ is arbitrary in
$(r_{n},+\infty)$. ∎

######  Example 1.

Let $n\geqslant 2$, $\alpha\geqslant 0$, $\beta\geqslant-1$, $\gamma\in(0,1)$
and $q$ be the mapping defined by

$q(x)=\frac{2^{1-\gamma}}{x^{1-\gamma}}1\hskip-2.6pt{\rm
l}_{(0,2)}+\frac{2^{1+\alpha}\left({\log
2}\right)^{1+\beta}}{x^{1+\alpha}\left({\log
x}\right)^{1+\beta}}1\hskip-2.6pt{\rm l}_{[2,+\infty)}.$

When $(\alpha,\beta)\in(0,+\infty)\times[-1,+\infty)$ and when $\alpha=0$ and
$\beta>0$, $q$ is positive, integrable, nonincreasing function on
$(0,+\infty)$ and we may denote by $p$ the corresponding density, i.e. $p=cq$
for some $c>0$ depending on $\alpha,\beta$ and $\gamma$. The density $p$ may
be written is under the form (24) with $\ell=2$, $w_{1}=0$, $w_{2}=1$,
$a=x_{1}=0$ and $p_{2}=p$. Throughout this example, $C$ denotes a positive
number depending on $\alpha,\beta$ and $\gamma$ that may vary from line to
line.

It follows from Definition 3 that when $\alpha>0$, for all $t\geqslant 2$

$\displaystyle\frac{\tau_{x}(p,t)}{c2^{1+\alpha}\left({\log
2}\right)^{1+\beta}}$
$\displaystyle=\int_{t}^{+\infty}\frac{dx}{x^{1+\alpha}\left({\log
x}\right)^{1+\beta}}=\int_{\log t}^{+\infty}\frac{e^{-\alpha
s}}{s^{1+\beta}}ds\leqslant\frac{1}{\alpha t^{\alpha}\left({\log
t}\right)^{1+\beta}},$

and when $\alpha=0$ and $\beta>0$

$\displaystyle\frac{\tau_{x}(p,t)}{c2^{1+\alpha}\left({\log
2}\right)^{1+\beta}}$ $\displaystyle=\int_{\log
t}^{+\infty}\frac{1}{s^{1+\beta}}ds=\frac{1}{\beta\left({\log
t}\right)^{\beta}},$

For $y>c$, $\widetilde{p}:y\mapsto 2(c/y)^{1/(1-\gamma)}$, hence

$\tau_{y}(p,t)=\int_{t}^{+\infty}\widetilde{p}(y)d\mu(y)=\frac{2(1-\gamma)c^{1/(1-\gamma)}}{\gamma
t^{\gamma/(1-\gamma)}}\quad\text{for all $t\geqslant c$.}$

We deduce that for all $t\geqslant 1$ and $s\in[2/t,2]$, $p(s)\geqslant
p(2)=c$ and

$\displaystyle C^{-1}\tau_{\infty}(p,t)$
$\displaystyle\leqslant\begin{cases}\left[{{(st)^{\alpha}\left({\log(st)}\right)^{1+\beta}}}\right]^{-1}+s^{\gamma}&\text{when
$\alpha>0$ and $\beta\geqslant-1$}\\\
\left({\log(st)}\right)^{-\beta}+s^{\gamma}&\text{when $\alpha=0$ and
$\beta>0$}.\end{cases}$

Taking

$s=\begin{cases}2\left[{\left({t^{\alpha}\left({\frac{\log(1+t)}{\log
2}}\right)^{1+\beta}}\right)^{-\frac{1}{\alpha+\gamma}}\vee
t^{-1}}\right]&\text{when $\alpha>0$ and $\beta\geqslant-1$}\\\
2\left[{\left({\frac{\log(1+t)}{\log 2}}\right)^{-\frac{\beta}{\gamma}}\vee
t^{-1}}\right]&\text{when $\alpha=0$ and $\beta>0$}\end{cases}$

the value of which belongs to $[2/t,2]$, we obtain that for all $t\geqslant 1$

$\displaystyle C^{-1}\tau_{\infty}(p,t)$
$\displaystyle\leqslant\begin{cases}\left[{t^{\alpha}\left({\log(1+t)}\right)^{1+\beta}}\right]^{-\frac{\gamma}{\alpha+\gamma}}\vee
t^{-\gamma}&\text{when $\alpha>0$ and $\beta\geqslant-1$}\\\
\left({\log(1+t)}\right)^{-\beta}\vee t^{-\gamma}&\text{when $\alpha=0$ and
$\beta>0$}.\end{cases}$

If $\alpha>0$ and $\beta\geqslant-1$, by taking

$t=t_{n}=C^{\prime}n^{\frac{1}{3}\left({\frac{1}{\alpha}+\frac{1}{\gamma}}\right)}\log^{-\kappa}n\quad\text{with}\quad\kappa=\frac{1}{3}\left({\frac{1}{\alpha}+\frac{1}{\gamma}}\right)+\frac{1+\beta}{\alpha}$

for some constant $C^{\prime}>0$ large enough, we obtain that
$\tau_{\infty}(p,t_{n})\leqslant\left({2\log(1+t_{n})/n}\right)^{1/3}$ and
consequently, $r_{n}$ defined by (28) satisfies $r_{n}\leqslant t_{n}$.
Applying Corollary 2, we conclude that for all $k\geqslant 4$

${\mathbb{B}}_{k,n}(p)\leqslant C\left[{\left({\frac{\log
n}{n}}\right)^{1/3}+\sqrt{\frac{2k}{n}}}\right].$

If $\alpha=0$ and $\beta>1$, we take $t=t_{n}$ such that
$\log(1+t_{n})=C^{\prime}n^{1/(1+3\beta)}$ for some constant $C^{\prime}>0$
large enough, we obtain that

$\displaystyle\tau_{\infty}(p,t_{n})\leqslant
Cn^{\frac{-\beta}{1+3\beta}}\leqslant\left({\frac{2\log(1+t_{n})}{n}}\right)^{1/3},$

hence $r_{n}\leqslant t_{n}=C^{\prime}n^{1/(1+3\beta)}$ and we get that for
all $k\geqslant 4$

${\mathbb{B}}_{k,n}(p)\leqslant
C\left[{n^{\frac{-\beta}{1+3\beta}}+\sqrt{\frac{2k}{n}}}\right].$

##  5\. Convex-concave densities

###  5.1. Piecewise monotone convex-concave densities

In this section, our aim is to estimate a density on the line which is
piecewise monotone convex-concave in the sense defined below.

######  Definition 4.

A function $g$ is said to be convex-concave on an interval $I$ if it is either
convex or concave on $I$. For $k\geqslant 2$, a function $g$ on $\mathbb{R}$
is said to be $k$-piecewise monotone convex-concave if there exists
$A\in{\mathcal{A}}(k-1)$ such that the restriction of $g$ to the each interval
$I\in{\mathbf{I}}(A)$ is monotone and convex-concave. In particular, there
exist at most $k$ functions $\\{g_{I},\;I\in{\mathbf{I}}(A)\\}$, where $g_{I}$
is monotone and convex-concave on $I$ such that

$g(x)=\sum_{I\in{\mathbf{I}}(A)}g_{I}(x)1\hskip-2.6pt{\rm
l}_{I}(x)\quad\text{for all $x\in{\mathbb{R}}\setminus A$}.$

We denote by $\overline{{\mathcal{M}}}_{k}^{1}$ the set of $k$-piecewise
monotone convex-concave densities. The Laplace density $x\mapsto(1/2)e^{-|x|}$
belongs to $\overline{{\mathcal{M}}}_{2}^{1}$, the uniform density on a
(nontrivial) interval belongs to $\overline{{\mathcal{M}}}_{3}^{1}$, all
convex-concave densities on an interval belong to
$\overline{{\mathcal{M}}}_{4}^{1}$. A function
$g\in\overline{{\mathcal{M}}}_{k}^{1}$ associated to $A\in{\mathcal{A}}(k-1)$
admits left and right derivatives at any point $x\in{\mathbb{R}}\setminus A$.
These derivatives are denoted by $g_{l}^{\prime},g_{r}^{\prime}$ respectively.
More generally, when a function $f$ is continuous and convex-concave on a
nontrivial bounded interval $[a,b]$, we define

$f^{\prime}_{r}(z)=\lim_{x\downarrow z}\frac{f(x)-f(z)}{x-z}\quad\text{for all
$z\in[a,b)$}$

and

$f^{\prime}_{l}(z)=\lim_{x\uparrow z}\frac{f(x)-f(z)}{x-z}\quad\text{for all
$z\in(a,b]$}.$

These quantities are finite for all $z\in(a,b)$ and belong to
$[-\infty,+\infty]$ when $z\in\\{a,b\\}$. We say that $f$ admits a right
derivative at $a$ and a left derivative at $b$ when $f^{\prime}_{r}(a)$ and
$f^{\prime}_{l}(b)$ are finite respectively.

The role played by piecewise constant functions in the previous section is
here played by piecewise linear functions. For $D\geqslant 1$, let
$\overline{{\mathcal{O}}}_{D,k}^{1}$ be the subset of
$\overline{{\mathcal{M}}}_{k}^{1}$ that consists of those densities that are
left-continuous and affine on each interval of a class ${\mathbf{I}}(A)$ with
$A\in{\mathcal{A}}(D+1)$. For example, the left-continuous version of the
density of a uniform distribution on a nontrivial interval belongs to
$\overline{{\mathcal{O}}}_{1,3}^{1}$. The proposition below shows that the
elements of $\overline{{\mathcal{O}}}_{D,k}^{1}$ are extremal in
$\overline{{\mathcal{M}}}_{k}^{1}$.

######  Proposition 3.

Let $k\geqslant 2$, $D\geqslant 1$. If $p\in\overline{\mathcal{M}}_{k}^{1}$
and $q\in\overline{{\mathcal{O}}}_{D,k}^{1}$, the sets
$\\{x\in{\mathbb{R}},\,p(x)-q(x)>0\\}$ and
$\\{x\in{\mathbb{R}},\,p(x)-q(x)<0\\}$ are unions of at most $D+2k-1$
intervals. In particular, the elements of $\overline{{\mathcal{O}}}_{D,k}^{1}$
are extremal in $\overline{{\mathcal{M}}}_{k}^{1}$ with degree not larger than
$2(D+2k-1)$.

###### Proof.

The proof is postponed to Subsection 7.4. ∎

For all $D\geqslant 1$, $k\geqslant 2$, let ${\mathcal{O}}_{D,k}^{1}$ be a
countable and dense subset of $\overline{\mathcal{O}}_{D,k}^{1}$ (for the
${\mathbb{L}}_{1}$-norm) and ${\mathcal{M}}_{k}^{1}$ a countable and dense
subset of $\overline{{\mathcal{M}}}_{k}^{1}$ that contains
$\bigcup_{D\geqslant 1}\mathcal{O}_{D,k}^{1}$. By proposition 1, the elements
of ${\mathcal{O}}_{D,k}^{1}$ are also extremal in ${\mathcal{M}}_{k}^{1}$ with
degree no larger than $2(D+2k-1)$ for all $D\geqslant 1$. We deduce from
Theorem 1 the following result.

######  Theorem 5.

Let $k\geqslant 2$. Whatever the product distribution ${\mathbf{P}}^{\star}$
of the data, any TV-estimator $\widehat{P}$ on ${\mathscr{M}}_{k}^{1}$
satisfies

(30)
${\mathbb{E}}\left[d\\!\left(P^{\star},\hat{P}\right)\right]\leqslant\inf_{D\geqslant
1}\left\\{3\inf_{P\in\overline{{\mathscr{O}}}_{D,k}^{1}}d\\!\left(P^{\star},P\right)+68\sqrt{\frac{D+2k-1}{n}}\right\\}+\frac{\varepsilon}{n}.$

In the remaining part of this section we assume that the $X_{i}$ are i.i.d.
with a density $p\in\overline{\mathcal{M}}_{k}^{1}$, in which case, the right-
hand side of (30) writes as ${\mathbb{B}}_{k,n}^{1}(p)+{\varepsilon}/n$ with

(31) ${\mathbb{B}}_{k,n}^{1}(p)=\inf_{D\geqslant
1}\left[\frac{3}{2}\inf_{q\in\overline{{\mathcal{O}}}_{D,k}^{1}}\left\|{p-q}\right\|+68\sqrt{\frac{D+2k-1}{n}}\right].$

As we did in Section 4, our aim is to bound the quantity
${\mathbb{B}}_{k,n}^{1}(p)$ under some suitable additional assumptions on the
density $p$.

###  5.2. Approximation of a monotone convex-concave density by a piecewise
linear function

Let us now turn to the approximation of a monotone convex-concave density by a
convex-concave piecewise linear function. The approximation result that we
establish is actually true for a sub-density on an interval $[a,b]$, i.e. a
nonnegative function on $[a,b]$ the integral of which is not larger than 1. In
the remaining part of this chapter, we use the following convenient
definition.

######  Definition 5.

Let $D\geqslant 1$ and $f$ be a continuous function on a compact nontrivial
interval $[a,b]$. We say that $\overline{f}$ is a $D$-linear interpolation of
$f$ on $[a,b]$ if there exists a subdivision $a=x_{0}<\ldots<x_{D}=b$ such
that $\overline{f}(x_{i})=f(x_{i})$ and $\overline{f}$ is affine on
$[x_{i-1},x_{i}]$ for all $i\in\\{1,\ldots,D\\}$.

This definition automatically determines the values of $\overline{f}$ on
$[a,b]$ since $\overline{f}$ corresponds on $[x_{i-1},x_{i}]$ to the chord
that connects $(x_{i-1},f(x_{i-1}))$ to $(x_{i},f(x_{i}))$ for all
$i\in\\{1,\ldots,D\\}$. The function $\overline{f}$ is therefore continuous
and piecewise linear on a partition of $[a,b]$ into $D$ intervals and it
inherits of some of the features of the function $f$. For example, if $f$ is
nonnegative, increasing, decreasing, convex or concave, so is $\overline{f}$.
If $f$ is convex (respectively concave), $\overline{f}\geqslant f$
(respectively $\overline{f}\leqslant f$).

Given a continuous monotone convex-concave function $f$ with increment
$\Delta=(f(b)-f(a))/(b-a)$ on a bounded nontrivial interval $[a,b]$, we define
its linear index $\Gamma=\Gamma(f)$ as

$\Gamma=1-\frac{1}{2}\left({\frac{|p_{r}^{\prime}(a)|\wedge|p_{l}^{\prime}(b)|}{|\Delta|}+\frac{|\Delta|}{|p_{r}^{\prime}(a)|\vee|p_{l}^{\prime}(b)|}}\right),$

with the conventions $0/0=1$ and $1/(+\infty)=0$. Since $f$ is convex-concave,
monotone and continuous

$|p_{r}^{\prime}(a)|\wedge|p_{l}^{\prime}(b)|\leqslant|\Delta|\leqslant|p_{r}^{\prime}(a)|\vee|p_{l}^{\prime}(b)|\quad\text{and}\quad$

and

$\Delta=0\implies|p_{r}^{\prime}(a)|=|p_{l}^{\prime}(b)|=0.$

With our conventions, $\Gamma$ is well-defined and belongs to $[0,1]$. When
$f$ is affine, $\Delta=p_{r}^{\prime}(a)=p_{l}^{\prime}(b)$ and its linear
index is 0. In the opposite direction when $f$ is far from being affine, say
when for some $c\in(a,b)$ and $v>0$

$f(x)=\frac{v}{b-c}(x-c)_{+}\quad\text{for all $x\in[a,b]$}$

its linear index $\Gamma=1-(b-c)/[2(b-a)]$ increases to 1 as $c$ approaches
$b$.

######  Theorem 6.

Let $p$ be a monotone, continuous, convex-concave density on a bounded
interval $[a,b]$ of length $L>0$ with variation $V=|p(b)-p(a)|$ and linear
index $\Gamma\in[0,1]$. For all $D\geqslant 1$, there exists a $2D$-linear
interpolation $\overline{p}$ of $p$ such that

(32)
$\int_{a}^{b}\left|{p-\overline{p}}\right|d\mu\leqslant\frac{4}{3}\left[{\left({1+\sqrt{2LV\Gamma}}\right)^{1/D}-1}\right]^{2}.$

In particular, there exists a continuous convex-concave piecewise linear
density $q$ based on a partition of $[a,b]$ into $2D$ intervals that satisfies

(33) $\int_{a}^{b}\left|{p-q}\right|d\mu\leqslant
5.14\frac{\log^{2}\left({1+\sqrt{2LV\Gamma}}\right)}{D^{2}}.$

Since $\Gamma\in[0,1]$, (33) implies that

$\int_{a}^{b}\left|{p-q}\right|d\mu\leqslant
5.14\frac{\log^{2}\left({1+\sqrt{2LV}}\right)}{D^{2}}.$

Nevertheless, when $p$ is affine on $[a,b]$, $\Gamma=0$ and we recover the
fact that we may choose $\overline{p}$ and $q$ on $[a,b]$ such that
$\int_{a}^{b}\left|{p-\overline{p}}\right|d\mu=\int_{a}^{b}\left|{p-q}\right|d\mu=0$.

The fact that a bounded convex (or concave) function on a compact interval can
be approximated in ${\mathbb{L}}_{1}$ by piecewise affine functions at rate
$\mathcal{O}(1/D^{2})$ had already been established by Guérin et al., (2006).
What is novel in Theorem 6 is the fact that for probability densities the
approximation error depends logarithmically on the product $LV$.

###### Proof.

The proof is based on several preliminary approximation results whose
statements and proofs are postponed to Subsection 7.4. ∎

###  5.3. Estimation of $k$-piecewise monotone convex-concave bounded and
compactly supported densities

In this section, we consider a density $p\in\overline{\mathcal{M}}_{k}^{1}$,
with $k\geqslant 3$, that is of the form

(34) $p=\sum_{i=1}^{k-2}w_{i}p_{i}1\hskip-2.6pt{\rm l}_{(x_{i-1},x_{i})}$

where

  1. (i)

$(x_{i})_{i\in\\{0,\ldots,k-2\\}}$ is an increasing sequence of real numbers;

  2. (ii)

$w_{1},\ldots,w_{k-2}$ are nonnegative numbers such that
$\sum_{i=1}^{k-2}w_{i}=1$;

  3. (iii)

for $i\in\\{1,\ldots,k-2\\}$, $p_{i}$ is a monotone continuous convex-concave
density on the interval $[x_{i-1},x_{i}]$ of length $L_{i}>0$, with variation
$V_{i}=\left|{p_{i}(x_{i-1})-p(x_{i})}\right|<+\infty$ and linear index
$\Gamma_{i}\in[0,1]$.

For a density $p$ satisfying (34) we define

(35)
$\boldsymbol{R}_{k,1}(p)=\inf\left[{\sum_{i=1}^{k-2}\left({w_{i}\log^{2}\left({1+\sqrt{2L_{i}V_{i}\Gamma_{i}}}\right)}\right)^{1/3}}\right]^{3/2},$

where the infimum runs among all ways of writing $p$ under the form (34). We
denote by $\overline{\mathcal{M}}_{k,1}^{\infty}$ the class of all densities
of the form (34) a.e. and for $R>0$,
$\overline{\mathcal{M}}_{k,1}^{\infty}(R)$ the subset of those which satisfy
$\boldsymbol{R}_{k,1}(p)<R$.

Note that a concave (or convex) density on a (necessarily) compact interval
belongs to $\overline{\mathcal{M}}_{4}^{1}$.

The following result holds.

######  Theorem 7.

Let $k\geqslant 3$ and $R>0$. For all
$p\in\overline{\mathcal{M}}_{k,1}^{\infty}(R)$

(36) ${\mathbb{B}}_{k,n}^{1}(p)\leqslant
7.71\left[{15.06\left({\frac{R}{n}}\right)^{2/5}+8.82\sqrt{\frac{4k-5}{n}}}\right],$

where ${\mathbb{B}}_{k,n}^{1}(p)$ is defined by (31).

Theorem 7 implies, together with Theorem 5, that the TV-estimator converges at
rate $n^{-2/5}$ in total variation distance, whenever the underlying density
$p^{\star}$ is bounded, compactly supported and belongs to the class
$\overline{{\mathcal{M}}}_{k,1}^{\infty}$ of $k-$piecewise monotone convex-
concave densities. The rate $n^{-2/5}$ matches the minimax lower bound
established in Devroye and Lugosi (2001)[Section 15.5] for bounded convex
densities. This rate is therefore optimal.

To the best of our knowledge, Theorem 8 provides the sharpest known minimax
upper bound in this setting, including the case of a monotone, convex or
concave density on a compact interval. In comparison, Gao and Wellner, 2009b
proved that the MLE on the set of convex non-increasing densities on a given
interval achieves the rate $n^{-2/5}$ (for the Hellinger distance). Note that
the construction of the MLE requires that the support of the target density is
known while our TV-estimator assumes nothing.

Consider now the special case of a continuous, concave density on an interval
$[a,b]$ (which is necessarily bounded). A monotone continuous concave density
$p$ on a bounded interval $[a,b]$ with length $L>0$ belongs to
$\overline{\mathcal{M}}_{3}^{1}$. It necessarily satisfies
$L|p(a)-p(b)|/2\leqslant 1$, hence
$\boldsymbol{R}_{3,1}(p)\leqslant\log(1+\sqrt{2L|p(a)-p(b)|})\leqslant\log 3$.
If $p$ is not monotone but only continuous and concave on $[a,b]$, we may
write $p$ as $w_{1}p_{1}+w_{2}p_{2}$ where $p_{1}$ and $p_{2}$ are monotone
and concave densities on the intervals $[a,c]$ and $[c,a]$ respectively where
$c$ is a maximizer of $p$ in $(a,b)$. The density $p$ belongs to
$\overline{\mathcal{M}}_{4}^{1}$ and by applying the previous inequality to
the densities $p_{1}$ and $p_{2}$ successively and the inequality
$z^{1/3}+(1-z)^{1/3}\leqslant 2^{2/3}$ which holds for all $z\in[0,1]$, we
obtain that

$\displaystyle\boldsymbol{R}_{4,1}^{2/3}(p)$
$\displaystyle\leqslant\left({w_{1}\log^{2}(1+\sqrt{2(c-a)\left({p_{1}(c)-p_{1}(a)}\right)}}\right)^{1/3}$
$\displaystyle\quad+\left({w_{2}\log^{2}(1+\sqrt{2(b-c)\left({p_{2}(c)-p_{2}(b)}\right)}}\right)^{1/3}$
$\displaystyle\leqslant\left({w_{1}^{1/3}+w_{2}^{1/3}}\right)(\log
3)^{2/3}\leqslant(2\log 3)^{2/3}.$

We immediately deduce from Theorems 5 and 7 the following corollary.

######  Corollary 3.

If $X_{1},\ldots,X_{n}$ is a $n$-sample which density is concave on an
interval of ${\mathbb{R}}$, then the TV-estimator $\widehat{p}$ on
${\mathcal{M}}_{4}^{1}$ satisfies

${\mathbb{E}}\left[{\left\|{p-\widehat{p}}\right\|}\right]\leqslant\frac{320}{n^{2/5}}+\frac{451}{\sqrt{n}}+\frac{2{\varepsilon}}{n}.$

In particular,

$\adjustlimits{\inf}_{\widetilde{p}}{\sup}_{p}{\mathbb{E}}\left[{\left\|{p-\widetilde{p}}\right\|}\right]\leqslant\frac{320}{n^{2/5}}+\frac{451}{\sqrt{n}},$

where the supremum runs among all concave densities $p$ on an interval of
${\mathbb{R}}$ and the infimum over all density estimators $\widetilde{p}$
based on a $n$-sample with density $p$.

###### Proof of Theorem 7.

Let $p\in\overline{\mathcal{M}}_{k,1}^{\infty}(R)$. With no loss of generality
we may assume that $p$ is of the form (34) everywhere and choose a subdivision
$(x_{i})_{i\in\\{0,\ldots,k-2\\}}$ in such a way that

$\left[{\sum_{i=1}^{k-2}\left({w_{i}\log^{2}\left({1+\sqrt{2L_{i}V_{i}\Gamma_{i}}}\right)}\right)^{1/3}}\right]^{3/2}\leqslant
R.$

Let $D\geqslant k-2$ and $D_{1},\ldots,D_{k-2}$ be some positive integers to
be chosen later on that satisfy the constraint $\sum_{i=1}^{k-2}D_{i}\leqslant
D$. By Theorem 6, we may find for all $i\in\\{1,\ldots,k-2\\}$ a density
$q_{i}$ that is continuous and supported on $[x_{i-1},x_{i}]$, piecewise
linear on a partition of $[x_{i-1},x_{i}]$ into $2D_{i}$ intervals, that
satisfies

$\int_{x_{i-1}}^{x_{i}}\left|{p_{i}-q_{i}}\right|d\mu\leqslant
5.14\frac{\log^{2}\left({1+\sqrt{2L_{i}V_{i}\Gamma_{i}}}\right)}{D_{i}^{2}}.$

The function $q=\sum_{i=1}^{k-2}w_{i}q_{i}1\hskip-2.6pt{\rm
l}_{(x_{i-1},x_{i}]}$ is a density, that is left-continuous, convex-concave on
each interval $I\in{\mathbf{I}}(\\{x_{0},\ldots,x_{k-2}\\})$ and affine on
each interval of a partition
$(x_{0},x_{k-2}]=\bigcup_{i=1}^{k-2}(x_{i-1},x_{i}]$ into
$\sum_{i=1}^{k-2}2D_{i}\leqslant 2D$ intervals. It therefore belongs to
$\overline{\mathcal{O}}_{2D,k}$. Besides,

$\displaystyle\left\|{p-q}\right\|$
$\displaystyle\leqslant\sum_{i=1}^{k-2}w_{i}\int_{x_{i-1}}^{x_{i}}\left|{p_{i}-q_{i}}\right|d\mu\leqslant
5.14\sum_{i=1}^{k-2}\frac{w_{i}\log^{2}\left({1+\sqrt{2L_{i}V_{i}\Gamma_{i}}}\right)}{D_{i}^{2}}$

and it follows from (31) that

$\displaystyle{\mathbb{B}}_{k,n}^{1}(p)$
$\displaystyle\leqslant\frac{3}{2}\inf_{q\in\overline{{\mathcal{O}}}_{2D,k}^{1}}\left\|{p-q}\right\|+68\sqrt{\frac{2D+2k-1}{n}}$
$\displaystyle\leqslant
7.71\sum_{i=1}^{k-2}\frac{w_{i}\log^{2}\left({1+\sqrt{2L_{i}V_{i}\Gamma_{i}}}\right)}{D_{i}^{2}}+68\sqrt{\frac{2D+2k-1}{n}}.$

Let us set $c=68/7.71$, $s_{0}=[nR^{4}/(2c^{2})]^{1/5}$,

$s_{i}=\left[{w_{i}\log^{2}\left({1+\sqrt{2L_{i}V_{i}\Gamma_{i}}}\right)}\right]^{1/3}\quad\text{for
all $i\in\\{1,\ldots,k-2\\}$}$

and choose $D=s_{0}+k-2$ and

$D_{i}=\left\lceil\frac{s_{0}s_{i}}{\sum_{j=1}^{k-2}s_{j}}\right\rceil\geqslant\frac{s_{0}s_{i}}{\sum_{j=1}^{k-2}s_{j}}\vee
1\quad\text{for all $i\in\\{1,\ldots,k-2\\}$},$

so that $\sum_{i=1}^{k-2}D_{i}\leqslant D$. Then,

$\displaystyle{\mathbb{B}}_{k,n}^{1}(p)$ $\displaystyle\leqslant
7.71\left[{\sum_{i=1}^{k-2}\frac{s_{i}^{3}}{D_{i}^{2}}+c\sqrt{\frac{2D+2k-1}{n}}}\right]$
$\displaystyle\leqslant
7.71\left[{\frac{\left({\sum_{j=1}^{k-2}s_{j}}\right)^{3}}{s_{0}^{2}}+c\sqrt{\frac{2s_{0}+4k-5}{n}}}\right]$
$\displaystyle\leqslant
7.71\left[{\frac{R^{2}}{s_{0}^{2}}+c\sqrt{\frac{2s_{0}}{n}}+c\frac{\sqrt{4k-5}}{n}}\right]$
$\displaystyle=7.71\left[{2(2c^{2})^{2/5}\frac{R^{2/5}}{n^{2/5}}+c\frac{\sqrt{4k-5}}{n}}\right]$

which gives (36). ∎

##  6\. Log-concave densities

In this section, we consider the set $\overline{\mathcal{M}}^{\text{LC}}$ of
log-concave densities. With the convention $\exp(-\infty)=0$,
$\overline{\mathcal{M}}^{\text{LC}}$ is the set of densities of the form
$p=\exp\phi$ where the set $J=J(p)=\\{x\in{\mathbb{R}},\;p(x)>0\\}$ is an open
interval and the mapping $\phi:{\mathbb{R}}\to{\mathbb{R}}\cup\\{-\infty\\}$
is a continuous and concave function on $J$. Given some $D\geqslant 1$, a
subset of $\overline{\mathcal{M}}^{\text{LC}}$ of special interest is the set
$\overline{\mathcal{O}}_{D}^{\text{LC}}$ of those densities the logarithm of
which is either affine or takes the value $-\infty$ on the elements of a set
${\mathbf{I}}(A)$ with $A\in{\mathcal{A}}(D)$. Since a density
$p\in\overline{\mathcal{O}}_{D}^{\text{LC}}$ is log-concave, the logarithm of
$p$ may take the value $-\infty$ on the two unbounded elements of
${\mathbf{I}}(A)$ only. For example, the densities $x\mapsto 1\hskip-2.6pt{\rm
l}_{x>0}\exp(-x)$ and $x\mapsto(1/2)\exp(-|x|)$ of the exponential and Laplace
distributions belong to $\overline{\mathcal{O}}_{1}^{\text{LC}}$ while the
standard Gaussian density belongs to $\overline{\mathcal{M}}^{\text{LC}}$.

######  Proposition 4.

Let $D\geqslant 1$. The elements of $\overline{{\mathcal{O}}}_{D}^{\text{LC}}$
are extremal in $\overline{\mathcal{M}}^{\text{LC}}$ with degree not larger
than $2(D+2)$.

###### Proof.

The proof is postponed to Subsection 7.5. ∎

For all $D\geqslant 1$, let ${\mathcal{O}}_{D}^{\text{LC}}$ be a countable and
dense subset of $\overline{{\mathcal{O}}}_{D}^{\text{LC}}$ (for the
${\mathbb{L}}^{1}$-norm) and ${\mathcal{M}}^{\text{LC}}$ a countable and dense
subset of $\overline{{\mathcal{M}}}^{\text{LC}}$ that contains
$\bigcup_{D\geqslant 1}{\mathcal{O}}_{D}^{\text{LC}}$. We immediately deduce
from Theorem 1 together with Proposition 4 the following result.

######  Theorem 8.

Whatever the product distribution ${\mathbf{P}}^{\star}$ of the data, any TV-
estimator $\widehat{P}$ on ${\mathscr{M}}^{\text{LC}}$ satisfies

(37)
$\mathbb{E}\left[{d\\!\left(P^{\star},\widehat{P}\right)}\right]\leqslant\inf_{D\geqslant
1}\left[{3\inf_{P\in\overline{\mathscr{O}}_{D}^{\text{LC}}}d\\!\left(P^{\star},P\right)+48\sqrt{2}\sqrt{\frac{D+2}{n}}}\right]+\frac{\varepsilon}{n}.$

In the remaining part of this section we assume that the $X_{i}$ are i.i.d.
with a density $p\in\overline{\mathcal{M}}_{\text{LC}}$, in which case, the
right-hand side of (37) writes as ${\mathbb{B}}_{n}(p)+{\varepsilon}/n$ with

(38) $\displaystyle{\mathbb{B}}_{n}(p)$ $\displaystyle=\inf_{D\geqslant
1}\left[{\frac{3}{2}\inf_{q\in\overline{\mathcal{O}}_{D}^{\text{LC}}}\left\|{p-q}\right\|+48\sqrt{2}\sqrt{\frac{D+2}{n}}}\right]$

In particular, if $p$ belongs to $\overline{\mathcal{O}}_{D}^{\text{LC}}$ for
some $D\geqslant 1$, then ${\mathbb{B}}_{n}(p)\leqslant\sqrt{D/n}$, so that
$\hat{p}$ converges at the parametric rate. Thus, the TV-estimator shares the
_adaptivity_ property established for the MLE by Kim et al (2018) (and Feng et
al., (2021)), and by Baraud and Birgé (2016) for their $\rho-$estimator. As
compared to theirs, our upper bound does not involve logarithmic factors. This
difference is due to the fact that Baraud and Birgé’s results are established
for the Hellinger distance and these logarithmic factors are sometimes
necessary for such a loss.

As we did in Sections 4 and 5 , our aim is now to bound the quantity
${\mathbb{B}}_{n}(p)$. This can be done by using the following approximation
result.

######  Proposition 5.

Let $D\geqslant 6$. For all log-concave densities $p$,

$\inf_{q\in\overline{\mathcal{O}}^{\text{LC}}_{6D}}\left\|{p-q}\right\|\leqslant\frac{2}{D^{2}}.$

###### Proof.

The proof is postponed to Subsection 7.5. ∎

Combining (38) with Proposition 5, we deduce that for all $D\geqslant 6$

$\displaystyle{\mathbb{B}}_{n}(p)$ $\displaystyle=\inf_{D\geqslant
6}\left[{\frac{3}{2}\inf_{q\in\overline{\mathcal{O}}_{6D}^{\text{LC}}}\left\|{p-q}\right\|+48\sqrt{2}\sqrt{\frac{6D+2}{n}}}\right]$
$\displaystyle\leqslant\inf_{D\geqslant
6}\left[{\frac{3}{D^{2}}+48\sqrt{2}\sqrt{\frac{6D+2}{n}}}\right].$

By choosing

$D=\left\lceil\left({\frac{3n}{96^{2}}}\right)^{1/5}\right\rceil\vee
6\leqslant\left({\frac{6n}{2\times 96^{2}}}\right)^{1/5}+6,$

we obtain the following estimation result for log-concave densities.

######  Corollary 4.

If $X_{1},\ldots,X_{n}$ is a $n$-sample which density $p$ is log-concave on
${\mathbb{R}}$, then the TV-estimator $\widehat{p}$ on ${\mathcal{M}}^{LC}$
satisfies

${\mathbb{E}}\left[{\left\|{p-\widehat{p}}\right\|}\right]\leqslant\frac{300}{n^{2/5}}+\frac{837}{\sqrt{n}}+\frac{2\varepsilon}{n}.$

The shape-constrained TV-estimator attains the global convergence rate of
$n^{-2/5}$ on the class of log-concave densities, i.e. the same global rate as
the MLE — see Kim and Samworth, (2016).

### Acknowledgement

One of the authors thanks Lutz Dümbgen for asking if we could establish a
result with $d(P^{\star},\widehat{P})$ in place of
$n^{-1}\sum_{i=1}^{n}d(P_{i},\widehat{P})$ at a conference where a preliminary
version of this work was presented. His question spurred the authors to
improve their result and obtain this new version of Theorem 1.

##  7\. Proofs

###  7.1. Technical result

First, we need a way to approximate $p$ not just by nonnegative functions, but
by densities. The following lemma shows that this can be achieved with a
simple renormalization.

######  Lemma 3.

Let $p$ be a density on a measured space $(E,{\mathcal{E}},\nu)$ and $f$ a
nonnegative integrable function on $(E,{\mathcal{E}},\nu)$ which is not
$\nu$-a.e. equal to 0 on $E$. Then

$\int_{E}\left|p-\frac{f}{\int_{E}fd\nu}\right|d\nu\leqslant
2\left[{1\wedge\int_{E}|p-f|d\nu}\right].$

This inequality cannot be improved in general since equality holds when
$f=p1\hskip-2.6pt{\rm l}_{I}$ and $I$ is a measurable subset of $E$ on which
$p$ is not $\nu$-a.e. equal to 0.

###### Proof.

The fact that

$\int_{E}\left|p-\frac{f}{\int_{E}fd\nu}\right|d\nu\leqslant 2$

comes from the triangle inequality. Let us now prove that

$\int_{E}\left|p-\frac{f}{\int_{E}fd\nu}\right|d\nu\leqslant
2\int_{E}|p-f|d\nu.$

We first assume that $c=\int_{E}fd\nu\in(0,1]$. Since $f/c$ and $p$ are two
densities,

$\displaystyle\int_{E}\left|\frac{f}{c}-p\right|d\nu$
$\displaystyle=2\int_{I}\left[p-\frac{f}{c}\right]1\hskip-2.6pt{\rm
l}_{\\{cp\geqslant f\\}}d\nu\leqslant 2\int_{E}[p-f]1\hskip-2.6pt{\rm
l}_{\\{cp\geqslant f\\}}d\nu$ $\displaystyle\leqslant 2\int_{E}|p-f|d\nu.$

This proves the lemma when $c\in(0,1]$. let us now assume that $c>1$. The
previous case of the lemma applies to the density $f/c$ and the nonnegative
function $p/c$ the integral of which is not larger than 1. This yields

$\displaystyle\int_{E}\left|\frac{f}{c}-p\right|d\nu$ $\displaystyle\leqslant
2\int_{E}\left|\frac{f}{c}-\frac{p}{c}\right|d\nu=\frac{2}{c}\int_{I}|f-p|d\nu\leqslant
2\int_{E}|f-p|d\nu.$

∎

###  7.2. Proofs of Section 3

###### Proof of Theorem 1.

Let $D\geqslant 1$ such that $\overline{\mathcal{O}}(D)$ is not empty. Such an
integer $D$ exists since $\overline{\mathcal{O}}$ is nonempty. Let
$\overline{P}=\overline{p}\cdot\mu$ be an arbitrary point in
${\mathscr{O}}(D)$ with $\overline{p}\in{\mathcal{O}}(D)$. For
$P,Q\in{\mathscr{M}}$ and $\zeta\geqslant 0$, we set

$\displaystyle{\mathbf{Z}}_{+}({\boldsymbol{X}},P)$
$\displaystyle=\sup_{Q\in{\mathscr{M}}}\left[{{\mathbf{T}}({\boldsymbol{X}},P,Q)-{\mathbb{E}}\left[{{\mathbf{T}}({\boldsymbol{X}},P,Q)}\right]}\right]-\zeta$
$\displaystyle{\mathbf{Z}}_{-}({\boldsymbol{X}},P)$
$\displaystyle=\sup_{Q\in{\mathscr{M}}}\left[{{\mathbb{E}}\left[{{\mathbf{T}}({\boldsymbol{X}},Q,P)}\right]-{\mathbf{T}}({\boldsymbol{X}},Q,P)}\right]-\zeta$

and

${\mathbf{Z}}({\boldsymbol{X}},P)={\mathbf{Z}}_{+}({\boldsymbol{X}},P)\vee{\mathbf{Z}}_{-}({\boldsymbol{X}},P).$

Applying the first inequality of (6) with $P=Q$ and $Q=\overline{P}$, we infer
that for all $Q\in{\mathscr{M}}$,

$\displaystyle nd\\!\left(\overline{P},Q\right)$ $\displaystyle\leqslant
nd\\!\left(P^{\star},\overline{P}\right)+{\mathbb{E}}\left[{{\mathbf{T}}({\boldsymbol{X}},Q,\overline{P})}\right]$
$\displaystyle=nd\\!\left(P^{\star},\overline{P}\right)+{\mathbb{E}}\left[{{\mathbf{T}}({\boldsymbol{X}},Q,\overline{P})}\right]-{\mathbf{T}}({\boldsymbol{X}},Q,\overline{P})+{\mathbf{T}}({\boldsymbol{X}},Q,\overline{P})$
$\displaystyle\leqslant
nd\\!\left(P^{\star},\overline{P}\right)+{\mathbf{Z}}({\boldsymbol{X}},\overline{P})+{\mathbf{T}}({\boldsymbol{X}},Q,\overline{P})+\zeta$
$\displaystyle\leqslant
nd\\!\left(P^{\star},\overline{P}\right)+{\mathbf{Z}}({\boldsymbol{X}},\overline{P})+{\mathbf{T}}({\boldsymbol{X}},Q)+\zeta.$

In particular, the inequality applies to
$Q=\widehat{P}\in{\mathscr{E}}({\boldsymbol{X}})$ and using the fact that

${\mathbf{T}}({\boldsymbol{X}},\widehat{P})\leqslant\inf_{P\in{\mathscr{M}}}{\mathbf{T}}({\boldsymbol{X}},P)+\varepsilon\leqslant{\mathbf{T}}({\boldsymbol{X}},\overline{P})+\varepsilon,$

we deduce that

(39) $\displaystyle nd\\!\left(\overline{P},\widehat{P}\right)$
$\displaystyle\leqslant
nd\\!\left(P^{\star},\overline{P}\right)+{\mathbf{Z}}({\boldsymbol{X}},\overline{P})+{\mathbf{T}}({\boldsymbol{X}},\overline{P})+\zeta+\varepsilon.$

Using now the second inequality of (6) with $P=\overline{P}$, we obtain that

$\displaystyle{\mathbf{T}}({\boldsymbol{X}},\overline{P})$
$\displaystyle=\sup_{Q\in{\mathscr{M}}}{\mathbf{T}}({\boldsymbol{X}},\overline{P},Q)$
$\displaystyle\leqslant\sup_{Q\in{\mathscr{M}}}\left[{{\mathbf{T}}({\boldsymbol{X}},\overline{P},Q)-{\mathbb{E}}\left[{{\mathbf{T}}({\boldsymbol{X}},\overline{P},Q)}\right]-\zeta}\right]+\sup_{Q\in{\mathscr{M}}}{\mathbb{E}}\left[{{\mathbf{T}}({\boldsymbol{X}},\overline{P},Q)}\right]+\zeta$
$\displaystyle\leqslant{\mathbf{Z}}({\boldsymbol{X}},\overline{P})+nd\\!\left(P^{\star},\overline{P}\right)+\zeta,$

which with (39) lead to

(40) $nd\\!\left(\overline{P},\widehat{P}\right)\leqslant
2nd\\!\left(P^{\star},\overline{P}\right)+2\zeta+\varepsilon+2{\mathbf{Z}}({\boldsymbol{X}},\overline{P}).$

Let us now bound from above ${\mathbf{Z}}({\boldsymbol{X}},\overline{P})$. We
set for $P\in{\mathscr{M}}$

$\displaystyle{\mathbf{w}}(P)$
$\displaystyle={\mathbb{E}}\left[{\sup_{Q\in{\mathscr{M}}}\left[{{\mathbf{T}}({\boldsymbol{X}},P,Q)-{\mathbb{E}}\left[{{\mathbf{T}}({\boldsymbol{X}},P,Q)}\right]}\right]}\right]$
$\displaystyle\quad\vee{\mathbb{E}}\left[{\sup_{Q\in{\mathscr{M}}}\left[{{\mathbb{E}}\left[{{\mathbf{T}}({\boldsymbol{X}},Q,P)}\right]-{\mathbf{T}}({\boldsymbol{X}},Q,P)}\right]}\right].$

The functions $t_{(\overline{P},Q)}$ satisfy
$|t_{(\overline{P},Q)}(x)-t_{(\overline{P},Q)}(x^{\prime})|\leqslant 1$ for
all $Q\in{\mathscr{M}}$ and $x,x^{\prime}\in E$, hence

$\left|{{\mathbf{Z}}_{+}((x_{1},\ldots,x_{i},\ldots,x_{n}),\overline{P})-{\mathbf{Z}}_{+}((x_{1},\ldots,x_{i}^{\prime},\ldots,x_{n}),\overline{P})}\right|\leqslant
1$

for all ${\mathbf{x}}\in{\mathbf{E}}$, $x_{i}^{\prime}\in E$ and
$i\in\\{1,\ldots,n\\}$. Following the same lines as in the proof of Lemma 2 of
Baraud (2021) (with $\xi+\log 2$ in place of $\xi$), we deduce that with a
probability at least $1-(1/2)e^{-\xi}$,

(41) $\displaystyle{\mathbf{Z}}_{+}({\boldsymbol{X}},\overline{P})$
$\displaystyle\leqslant{\mathbb{E}}\left[{{\mathbf{Z}}_{+}({\boldsymbol{X}},\overline{P})}\right]+\sqrt{\frac{n(\xi+\log
2)}{2}}$
$\displaystyle={\mathbb{E}}\left[{\sup_{Q\in{\mathscr{M}}}\left[{{\mathbf{T}}({\boldsymbol{X}},\overline{P},Q)-{\mathbb{E}}\left[{{\mathbf{T}}({\boldsymbol{X}},\overline{P},Q)}\right]}\right]}\right]+\sqrt{\frac{n(\xi+\log
2)}{2}}-\zeta$ (42)
$\displaystyle\leqslant{\mathbf{w}}(\overline{P})+\sqrt{\frac{n(\xi+\log
2)}{2}}-\zeta.$

Arguing similarly, with a probability at least $1-(1/2)e^{-\xi}$,

(43) $\displaystyle{\mathbf{Z}}_{-}({\boldsymbol{X}},\overline{P})$
$\displaystyle\leqslant{\mathbf{w}}(\overline{P})+\sqrt{\frac{n(\xi+\log
2)}{2}}-\zeta.$

Putting (42) and (43) together and choosing
$\zeta={\mathbf{w}}(\overline{P})+\sqrt{n(\xi+\log 2)/2}$, we obtain that with
a probability at least $1-e^{-\xi}$,

${\mathbf{Z}}({\boldsymbol{X}},\overline{P})={\mathbf{Z}}_{+}({\boldsymbol{X}},P)\vee{\mathbf{Z}}_{-}({\boldsymbol{X}},P)\leqslant{\mathbf{w}}(\overline{P})+\sqrt{\frac{n(\xi+\log
2)}{2}}-\zeta\leqslant 0$

which with (40) lead to the bound

(44) $d\\!\left(\overline{P},\widehat{P}\right)\leqslant
2d\\!\left(P^{\star},\overline{P}\right)+\frac{2{\mathbf{w}}(\overline{P})}{n}+\sqrt{\frac{2(\xi+\log
2)}{n}}+\frac{\varepsilon}{n}.$

It remains now to control ${\mathbf{w}}(\overline{P})$. Since
$\overline{p}\in{\mathcal{O}}(D)\subset\overline{\mathcal{O}}(D)$, it is
extremal in $\overline{\mathcal{M}}\supset{\mathcal{M}}$ with degree not
larger than $D$, the classes
$\left\\{{\\{q<\overline{p}\\},\;q\in{\mathcal{M}}\setminus\\{\overline{p}\\}}\right\\}$
and
$\left\\{{\\{q>\overline{p}\\},\;q\in{\mathcal{M}}\setminus\\{\overline{p}\\}}\right\\}$
are both VC with dimensions not larger than $D$. We may therefore apply
Proposition 3.1 in Baraud (2016) with $\sigma=1$ and get

(45)
$\displaystyle{\mathbb{E}}\left[{\sup_{q\in{\mathcal{M}}\setminus\\{\overline{p}\\}}\left|{\sum_{i=1}^{n}\left({1\hskip-2.6pt{\rm
l}_{\overline{p}>q}(X_{i})-P_{i}^{\star}(\overline{p}>q)}\right)}\right|}\right]$
$\displaystyle\leqslant 10\sqrt{5nD},$

and

(46)
$\displaystyle{\mathbb{E}}\left[{\sup_{q\in{\mathcal{M}}\setminus\\{\overline{p}\\}}\left|{\sum_{i=1}^{n}\left({1\hskip-2.6pt{\rm
l}_{\overline{p}<q}(X_{i})-P_{i}^{\star}(\overline{p}<q)}\right)}\right|}\right]$
$\displaystyle\leqslant 10\sqrt{5nD}.$

These inequalities entail ${\mathbf{w}}(\overline{P})\leqslant 10\sqrt{5nD}$,
and we infer from (44) that

(47) $d\\!\left(\overline{P},\widehat{P}\right)\leqslant
2d\\!\left(P^{\star},\overline{P}\right)+20\sqrt{\frac{5D}{n}}+\sqrt{\frac{2(\xi+\log
2)}{n}}+\frac{\varepsilon}{n}.$

Since $\overline{P}$ is arbitrary in the set ${\mathscr{O}}(D)$ which is dense
on $\overline{\mathscr{O}}(D)$, we infer that equation (47) holds for all
$\overline{P}\in\overline{\mathscr{O}}(D)$, which yields (7). Hence, by the
triangle inequality,

$\displaystyle d\\!\left(P^{\star},\widehat{P}\right)$
$\displaystyle\leqslant\inf_{P\in\overline{\mathscr{O}}(D)}\left\\{d\\!\left(P^{\star},P\right)+d\\!\left(P,\widehat{P}\right)\right\\}$
$\displaystyle\leqslant
3\inf_{P\in\overline{\mathscr{O}}(D)}d\\!\left(P^{\star},P\right)+20\sqrt{\frac{5D}{n}}+\sqrt{\frac{2(\xi+\log
2)}{n}}+\frac{\varepsilon}{n}.$

With our convention that $\inf_{\varnothing}=+\infty$, the inequality is also
true when $\overline{\mathscr{O}}(D)=\varnothing$, hence for all values of
$D$, which leads to (8). Inequality (10) follows by integrating this deviation
bound with respect to $\xi$. ∎

###  7.3. Proofs of Section 4

###### Proof of Proposition 2.

We restrict ourselves to the case where $p$ is nonincreasing on $I$, the proof
in the other case is similar. Let $q$ be the function that coincides with $p$
on $\mathring{I}=(a,b)$ and satisfies $q(a)=\sup_{x\in(a,b)}p(x)$ and
$q(b)=\inf_{x\in(a,b)}p(x)$. Clearly, $p=q$ a.e. and satisfies
$V_{I}(p)=q(a)-q(b)=V_{I}(q)$. With no loss of generality, we may therefore
assume that $I=[a,b]$ and that $V_{I}(p)=p(a)-p(b)$, what we shall do now.

Since $p$ is nonincreasing in $I$, for all intervals $J\subset I$ with
endpoints $u<v$,

(48)
$\int_{J}\left|{p-\overline{p}_{J}}\right|d\mu\leqslant\frac{(v-u)(p(u)-p(v))}{2}.$

In particular, when $D=1$ it suffices to take ${\mathcal{J}}=\\{I\\}$ and the
result follows from (48) with $u=a$ and $v=b$ and the trivial inequality
$\int_{I}|p-\overline{p}_{J}|d\mu\leqslant 2$. It remains to prove the result
for $D\geqslant 2$ and since (18) is trivially true for $V=0$ we may also
assume that $V>0$.

Let us set $\eta=(1+VL)^{1/D}-1>0$, $x_{0}=a$ and for all
$j\in\\{1,\ldots,D\\}$,

$x_{j}=x_{j-1}+L\frac{(1+\eta)^{j}}{\sum_{k=1}^{D}(1+\eta)^{k}}=x_{0}+L\frac{(1+\eta)^{j}-1}{(1+\eta)^{D}-1}=x_{0}+\frac{(1+\eta)^{j}-1}{V}.$

Then, we obtain an increasing sequence of points
$a=x_{0}<x_{1}<\ldots<x_{D}=b=a+L$ and a partition ${\mathcal{J}}$ of $I$ into
$D$ intervals based on $\\{x_{0},\ldots,x_{D}\\}$. Using (48) and the facts
that $x_{j+1}-x_{j}=(1+\eta)(x_{j}-x_{j-1})>x_{j}-x_{j-1}$ for
$j\in\\{1,\ldots,D-1\\}$, we obtain

$\displaystyle\int_{I}\left|{p-\overline{p}}\right|d\mu$
$\displaystyle=\sum_{J\in{\mathcal{J}}}\int_{J}\left|{p-\overline{p}_{J}}\right|d\mu\leqslant\frac{1}{2}\sum_{j=1}^{D}(x_{j}-x_{j-1})[p(x_{j-1})-p(x_{j})]$
$\displaystyle=\frac{1}{2}\left[{p(x_{0})(x_{1}-x_{0})+\sum_{j=1}^{D-1}p(x_{j})\left[{(x_{j+1}-x_{j})-(x_{j}-x_{j-1})}\right]}\right]$
$\displaystyle\quad-\frac{p(x_{D})(x_{D}-x_{D-1})}{2}$
$\displaystyle\leqslant\frac{1}{2}\left[{V_{I}(p)(x_{1}-x_{0})+\eta\sum_{j=1}^{D-1}p(x_{j})(x_{j}-x_{j-1})}\right]$
$\displaystyle\quad+\frac{p(x_{D})\left[{(x_{1}-x_{0})-(x_{D}-x_{D-1})}\right]}{2}$
$\displaystyle\leqslant\frac{1}{2}\left[{V(x_{1}-x_{0})+\eta\sum_{j=1}^{D-1}\int_{x_{j-1}}^{x_{j}}pd\mu}\right]\leqslant\frac{1}{2}\left[{V(x_{1}-x_{0})+\eta}\right]=\eta.$

Together with the trivial bound
$\int_{I}\left|{p-\overline{p}}\right|d\mu\leqslant 2$, this last inequality
leads to (18). The second inequality derives from the fact that
$(e^{x}-1)\wedge 2\leqslant 2x/\log 3\leqslant 2x$ for all $x\geqslant 0$. ∎

###### Proof of Theorem 3.

Let $D,D_{1},\ldots,D_{k-2}$ be positive integers and $p$ a density in
$\overline{\mathcal{M}}_{k}^{\infty}(R)$. We may therefore write $p$ under the
form (15) with

$\left[{\sum_{i=1}^{k-2}\sqrt{w_{i}\log\left({1+L_{i}V_{i}}\right)}}\right]^{2}\leqslant
R.$

Applying Proposition 2 to the density $p_{i}$, with $I=I_{i}=(x_{i-1},x_{i})$,
$L=L_{i}=(x_{i}-x_{i-1})$, $V=V_{i}$ and $D=D_{i}\geqslant 1$ for each
$i\in\\{1,\ldots,k-2\\}$, we build a monotone density $\overline{p}_{i}$ on
$I_{i}$ which is piecewise constant on partition of $I_{i}$ into $D_{i}$
nontrivial intervals and that satisfies

$\int_{I_{i}}\left|{p_{i}-\overline{p}_{i}}\right|d\mu\leqslant\frac{2S_{i}}{D_{i}}\quad\text{with}\quad
S_{i}=\log\left({1+V_{i}L_{i}}\right).$

Let us now take $D_{i}=\left\lceil
D\sqrt{w_{i}S_{i}}/(\sum_{i=1}^{k-2}\sqrt{w_{i}S_{i}})\right\rceil\vee 1$ for
all $i\in\\{1,\ldots,k-2\\}$. Since

$\frac{D\sqrt{w_{i}S_{i}}}{\sum_{i=1}^{k-2}\sqrt{w_{i}S_{i}}}\vee 1\leqslant
D_{i}\leqslant\frac{D\sqrt{w_{i}S_{i}}}{\sum_{i=1}^{k-2}\sqrt{w_{i}S_{i}}}+1,$

the density $\overline{p}=\sum_{i=1}^{k-2}w_{i}\overline{p}_{i}$ satisfies

$\displaystyle\left\|{p-\overline{p}}\right\|$
$\displaystyle\leqslant\sum_{i=1}^{k-2}w_{i}\int_{I_{i}}\left|{p_{i}-\overline{p}_{i}}\right|d\mu\leqslant\sum_{i=1}^{k-2}\frac{2w_{i}S_{i}}{D_{i}}\leqslant\frac{2}{D}\left({\sum_{i=1}^{k-2}\sqrt{w_{i}S_{i}}}\right)^{2}\leqslant\frac{2R}{D}.$

Besides, the density $\overline{p}$ is $k$-piecewise monotone, supported on
$[x_{1},x_{k-2}]$ and piecewise constant on a partition of ${\mathbb{R}}$
consisting of at most $\sum_{i=1}^{k-2}D_{i}\leqslant D+k-2$ bounded
intervals. It therefore belongs to $\overline{\mathcal{O}}_{D+k-2,k}$.
Finally, let us choose

$D=\left\lceil\left({\frac{9R^{2}n}{83.2^{2}}}\right)^{1/3}\right\rceil\leqslant\left({\frac{9R^{2}n}{83.2^{2}}}\right)^{1/3}+1.$

Using the sub-additivity property of the square root, we deduce from (14) that

$\displaystyle{\mathbb{B}}_{k,n}(p)$
$\displaystyle\leqslant\frac{3R}{2D}+83.2\sqrt{\frac{D-1+2k}{n}}$
$\displaystyle\leqslant\frac{3^{1/3}\times
83.2^{2/3}}{2}\left({\frac{R}{n}}\right)^{1/3}+\frac{83.2}{\sqrt{n}}\sqrt{\left({\frac{9nR^{2}}{83.2^{2}}}\right)^{1/3}+2k}$
$\displaystyle\leqslant\left[{\frac{3^{1/3}\times 83.2^{2/3}}{2}+3^{1/3}\times
83.2^{2/3}}\right]\left({\frac{R}{n}}\right)^{1/3}+83.2\sqrt{\frac{2k}{n}},$

which is (17). ∎

###### Proof of Theorem 4.

Let us start with the following lemma where we show that the mapping
$\tau(p,\cdot)$ controls the ${\mathbb{L}}_{1}$-approximation error of a
monotone density $p$ by the elements of the class
$\overline{\mathcal{M}}_{3}^{\infty}(R)$.

######  Lemma 4.

Let $p$ be a density on ${\mathbb{R}}$, $B$ some positive number and $I$ a
subset of ${\mathbb{R}}$ on which the density $p$ is not a.e. equal to 0. The
density $p_{|I}^{\wedge B}=(p\wedge B)1\hskip-2.6pt{\rm
l}_{I}/\int_{I}(p\wedge B)d\mu$ satisfies,

(49) $\left\|{p-p_{|I}^{\wedge B}}\right\|\leqslant
2\left[{\int_{I}\left({p-B}\right)_{+}d\mu+\int_{I^{c}}pd\mu}\right].$

If $p$ is a monotone density on a half-line

(50)
$\inf_{\overline{p}\in\overline{\mathcal{M}}_{3}^{\infty}(R)}\left\|{p-\overline{p}}\right\|\leqslant
2\tau\left({p,\exp(R)-1}\right)\quad\text{for all $R\geqslant\log 2$.}$

Besides, if $p$ is a nonincreasing density on $(a,a+l)$ (respectively a
nondecreasing density on $(a-l,a)$) with $a\in{\mathbb{R}}$ and
$l\in(0,+\infty]$, we may restrict the infimum to the nonincreasing densities
on $(a,a+l)$ (respectively the nondecreasing densities on $(a-l,a)$) that
belong to $\overline{\mathcal{M}}_{3}^{\infty}(R)$.

###### Proof.

Since $p$ is not equal to 0 a.e. on $I$, $\int_{I}(p\wedge B)d\mu>0$ and
$p_{|I}^{\wedge B}$ is therefore a well-defined density on $I$. By Lemma 3,

$\displaystyle\int_{{\mathbb{R}}}\left|{p-p_{|I}^{\wedge B}}\right|d\mu$
$\displaystyle\leqslant 2\int_{{\mathbb{R}}}\left|{p-(p\wedge
B)1\hskip-2.6pt{\rm l}_{I}}\right|d\mu$
$\displaystyle=2\int_{I^{c}}pd\mu+2\int_{I}\left({p-B}\right)_{+}d\mu.$

Changing $p$ into $x\mapsto p(-x)$ if necessary and possibly changing the
value of $p$ at the endpoint of the half-line, we may assume with no loss of
generality that $p$ is a nonincreasing density on a half-line of the form
$(a,+\infty)$ with $a\in{\mathbb{R}}$. Let us now set

$l=\sup\\{z>0,\;p(a+z)>0\\}\in(0,+\infty]\quad\text{and}\quad
t=\exp(R)-1\geqslant 1.$

We first consider the case where $l=+\infty$. Given $s>0$, let us take
$B=p(a+s)>0$ and $I=(a,a+st)$. Since $p$ is nonincreasing on $(a,+\infty)$,
$p(x)\geqslant p(a+s)=B$ for all $x\in(a,a+s)\subset I$ and consequently

$\int_{I}(p\wedge B)d\mu\geqslant\int_{a}^{a+s}(p\wedge B)d\mu=sB.$

The density $\overline{p}_{s}=p_{|I}^{\wedge B}$ belongs to
$\overline{\mathcal{M}}_{3}^{\infty}$, is supported on an interval of length
not larger than $st$ and its variation on $I$ is not larger that

$\frac{B}{\int_{I}(p\wedge B)d\mu}-p(a+st)<\frac{B}{\int_{I}(p\wedge B)d\mu}.$

Hence, it follows from (16) that

$\displaystyle\boldsymbol{R}_{k,0}(\overline{p}_{s})<\log\left({1+\frac{tsB}{\int_{I}(p\wedge
B)d\mu}}\right)\leqslant\log(1+t)=R$

and consequently, $\overline{p}_{s}\in\overline{\mathcal{M}}_{3}^{\infty}(R)$.
Applying (49) and Lemma 2, we obtain that for all $s>0$

(51)
$\inf_{\overline{p}\in\overline{\mathcal{M}}_{3}^{\infty}(R)}\left\|{p-\overline{p}}\right\|\leqslant\left\|{p-\overline{p}_{s}}\right\|\leqslant
2\left[{\tau_{x}(p,st)+\tau_{y}\left({p,p(a+s)}\right)}\right]$

and we derive (50) from (22). Since for all $s>0$, $\overline{p}_{s}$ is a
density on $(a,+\infty)$, we may restrict the infimum to these densities in
$\overline{\mathcal{M}}_{3}^{\infty}(R)$ that satisfy this property.

Let us now turn to the case where $l<+\infty$ and define $s_{0}=l/t\leqslant
l$. Given $s\in(0,s_{0})$, we take $B=p(a+s)>0$ and $I=(a,a+st)$. Since
$st<l$, $p(a+st)>0$ and by arguing as before, we obtain that

$\inf_{\overline{p}\in\overline{\mathcal{M}}_{3}^{\infty}(R)}\left\|{p-\overline{p}}\right\|\leqslant
2\left[{\tau_{x}(p,st)+\tau_{y}\left({p,p(a+s)}\right)}\right]\quad\text{for
all $s\in(0,s_{0})$.}$

It follows from the monotonicity of $\tau_{y}(p,\cdot)$ that for all
$0<s<s_{0}\leqslant s^{\prime}$,

$\tau_{y}\left({p,p(a+s)}\right)\leqslant\tau_{y}\left({p,p(a+s_{0})}\right)\leqslant\tau_{y}\left({p,p(a+s^{\prime})}\right),$

and since the mapping $u\mapsto\tau_{x}(p,u)$ is continuous and nonincreasing,
for all $s^{\prime}\geqslant s_{0}$

$\displaystyle\inf_{s\in(0,s_{0})}\left[{\tau_{x}(p,st)+\tau_{y}\left({p,p(a+s)}\right)}\right]$
$\displaystyle\leqslant\inf_{s\in(0,s_{0})}\tau_{x}(p,st)+\tau_{y}\left({p,p(a+s^{\prime})}\right)=\tau_{x}(p,s_{0}t)+\tau_{y}\left({p,p(a+s^{\prime})}\right)$
$\displaystyle=0+\tau_{y}\left({p,p(a+s^{\prime})}\right)=\tau_{x}(p,s^{\prime}t)+\tau_{y}\left({p,p(a+s^{\prime})}\right).$

Consequently, (51) remains satisfied for all $s>0$. Since it is actually
enough to restrict the infimum to those $s\in(0,s_{0})$ and since for such
values of $s$ the density $\overline{p}_{s}=p_{|I}^{\wedge B}$ vanishes
outside $(a,a+s)\subset(a,a+l)$, we may restrict the infimum in (50) to those
densities in $\overline{\mathcal{M}}_{3}^{\infty}(R)$ that vanish outside
$(a,a+l)$. ∎

Let us set $\eta=\tau_{\infty}\left({p,\exp\left({R/\ell}\right)-1}\right)$.
Since $R/\ell\geqslant\log 2$, by applying Lemma 4 to the densities $p_{i}$,
we may find for all $i\in\\{1,\ldots,\ell\\}$ a density
$\overline{p}_{i}\in\overline{\mathcal{M}}_{3}^{\infty}(R/\ell)$ such that
$\|p_{i}-\overline{p}_{i}\|\leqslant
2\tau\left({p_{i},\exp(R/\ell)-1}\right)$. In particular, the density
$\overline{p}=\sum_{i=1}^{\ell}w_{i}\overline{p}_{i}$ satisfies

(52)
$\left\|{p-\overline{p}}\right\|\leqslant\sum_{i=1}^{\ell}w_{i}\left\|{p_{i}-\overline{p}_{i}}\right\|\leqslant\max_{i\in\\{1,\ldots,\ell\\}}\left\|{p_{i}-\overline{p}_{i}}\right\|\leqslant
2\eta.$

When $\ell>2$ and $i\in\\{2,\ldots,\ell-1\\}$, it follows from the definition
of $\overline{\mathcal{M}}_{3}^{\infty}(R/\ell)$ and Lemma 4 that we may
choose $\overline{p}_{i}$ in such a way that it vanishes outside an interval
$I_{i}=(x_{i,0},x_{i,1})\subset(x_{i-1},x_{i})$ with

$\log\left[{1+\left({x_{i,0}-x_{i,1}}\right)\left({\sup_{x\in
I_{i}}\overline{p}_{i}(x)-\inf_{x\in
I_{i}}\overline{p}_{i}(x)}\right)}\right]<\frac{R}{\ell}$

and $x_{i,0}=x_{i-1}$ when $p_{i}$ is nonincreasing and $x_{i,1}=x_{i}$ when
$p_{i}$ is nondecreasing. The mapping $\overline{p}_{1}$ is a nondecreasing
density on an interval of the form $I_{1}=(x_{1,0},x_{1,1})$ with
$x_{1,0}<x_{1,1}=x_{1}$ and

$\log\left[{1+\left({x_{1,1}-x_{1,0}}\right)\left({\sup_{x\in
I_{1}}\overline{p}_{1}(x)-\inf_{x\in
I_{1}}\overline{p}_{1}(x)}\right)}\right]<\frac{R}{\ell}.$

Similarly, $\overline{p}_{\ell}$ is a nonincreasing density on an interval of
the form $I_{\ell}=(x_{\ell,0},x_{\ell,1})$ with
$x_{\ell,0}=x_{\ell-1}<x_{\ell,1}$ and

$\log\left[{1+\left({x_{\ell,1}-x_{\ell,0}}\right)\left({\sup_{x\in
I_{\ell}}\overline{p}_{\ell}(x)-\inf_{x\in
I_{\ell}}\overline{p}_{\ell}(x)}\right)}\right]<\frac{R}{\ell}.$

The density $\overline{p}=\sum_{i=1}^{\ell}w_{i}\overline{p}_{i}$ also writes
as

$\overline{p}_{1}1\hskip-2.6pt{\rm
l}_{(x_{1,0},x_{1})}+\sum_{i=2}^{\ell-2}w_{i}\left[{\overline{p}_{i}1\hskip-2.6pt{\rm
l}_{I_{i}}+01\hskip-2.6pt{\rm l}_{(x_{i-1},x_{i})\setminus
I_{i}}}\right]+\overline{p}_{\ell}1\hskip-2.6pt{\rm
l}_{(x_{\ell-1},x_{\ell,1})}$

and may therefore be written under the form (15) when $k\geqslant 2\ell$.
Moreover, by Cauchy-Schwarz inequality

$\displaystyle\boldsymbol{R}_{k,0}(\overline{p})<\left[{\sum_{i=1}^{\ell}\sqrt{w_{i}\left({\frac{R}{\ell}}\right)}+0}\right]^{2}=\frac{R}{\ell}\left[{\sum_{i=1}^{\ell}\sqrt{w_{i}}}\right]^{2}\leqslant
R$

and consequently, $\overline{p}\in\overline{\mathcal{M}}_{k}^{\infty}(R)$. We
deduce from (52) that

$\displaystyle\inf_{q\in\overline{\mathcal{M}}_{k}^{\infty}(R)}\left\|{p-q}\right\|$
$\displaystyle\leqslant\left\|{p-\overline{p}}\right\|\leqslant 2\eta$

which is (26). ∎

###  7.4. Proofs of Section 5

###### Proof of Proposition 3.

The proof relies on the following lemma the proof of which is a direct
consequence of convexity and is therefore omitted.

######  Lemma 5.

Let $g$ be a convex and continuous function on a nontrivial interval $J$. The
set $\\{x\in J,\;g(x)<0\\}$ is an interval (possibly empty). The set $\\{x\in
J,\;g(x)>0\\}$ has one of the following forms: $\varnothing,J$,
$J\cap(-\infty,c_{0})$, $J\cap(c_{1},+\infty)$,
$[J\cap(-\infty,c_{0})]\cup[J\cap(c_{1},+\infty)]$ with $c_{0},c_{1}\in J$ and
$c_{0}<c_{1}$. In particular $\\{x\in J,\;g(x)>0\\}$ is the union of at most
two intervals.

When $g$ is continuous and concave on $J$, the same conclusion holds with
$\\{x\in J,\;g(x)>0\\}$ in place of $\\{x\in J,\;g(x)<0\\}$ and vice-versa.

Since $p$ belongs to $\overline{\mathcal{M}}_{k}^{1}$ and $q$ belongs to
$\overline{{\mathcal{O}}}_{D,k}^{1}$, there exists
$A=\\{a_{1},\ldots,a_{l}\\}$ with $l\in\\{1,\ldots,k-1\\}$ such that $p$ is
convex-concave on each element of ${\mathbf{I}}(A)$ and there exists a subset
$B\subset{\mathbb{R}}$ with cardinality not larger than $D+2$ such that $q$ is
left-continuous on ${\mathbb{R}}$ and affine on each element of
${\mathbf{I}}(B)$. Since $p$ and $q$ are densities, $p$ is necessarily convex
on the two unbounded intervals of ${\mathbf{I}}(A)$ and $q$ vanishes on the
two unbounded intervals of ${\mathbf{I}}(B)$.

We define $J_{1}=(-\infty,a_{1}]$, $J_{l+1}=(a_{l},+\infty)$ and when
$l\geqslant 2$, $J_{i}=(a_{i-1},a_{i}]$ for all $i\in\\{2,\ldots,l\\}$.
Besides, we set $I_{i}=\mathring{J}_{i}$ for all $i\in\\{1,\ldots,l+1\\}$. We
shall repeatedly use Lemma 5 with $g=p-q$ throughout the proof. Given
$\epsilon\in\\{\pm 1\\}$, we set

(53) $C_{\epsilon}=\left\\{{x\in{\mathbb{R}},\;\epsilon
g(x)>0}\right\\}=\bigcup_{i=1}^{l+1}\left\\{{x\in J_{i},\;\epsilon
g(x)>0}\right\\}.$

Our aim is to show that $C_{\epsilon}$ is the union of at most $D+2k-1$
intervals. The second part of the proposition is a consequence of Lemma 1 of
Baraud and Birgé (2016).

If $m_{1}=|B\cap I_{1}|=0$ then $q=0$ on $J_{1}$ (since it is left-
continuous), $g=p-0$ is continuous, monotone (nondecreasing) and convex on
$I_{1}$, $\\{x\in J_{1},\;g(x)<0\\}=\varnothing$ and $\\{x\in
J_{1},\;g(x)>0\\}$ is an interval.

If $m_{1}=|B\cap I_{1}|\geqslant 1$, we may partition $J_{1}$ into
$s=m_{1}+1\geqslant 2$ consecutive intervals $K_{1},\ldots,K_{s}$ that we may
choose to be of the form $(a,b]$, $a<b$, $a\in{\mathbb{R}}\cup\\{-\infty\\}$,
$b\in{\mathbb{R}}$. Since $p$ is continuous on $I_{1}$ and $q$ is left-
continuous, $g$ is continuous on $K_{1},\ldots,K_{s-1}$ and on
$\mathring{K}_{s}$. On $K_{1}$, $\\{x\in K_{1},\;g(x)<0\\}=\varnothing$ and
the set $\Lambda_{1,]}^{+}=\\{x\in K_{1},\;g(x)>0\\}$ is an interval which is
either empty or contains the right endpoint of $K_{1}$. When $s\geqslant 2$,
we may apply Lemma 5 to $g$ and the intervals $K_{i}$ with
$i\in\\{2,\ldots,s-1\\}$. We obtain that $\Lambda_{i}^{-}=\\{x\in
K_{i},\;g(x)<0\\}$ is an interval and $\\{x\in K_{i},\;g(x)>0\\}$ is of the
form $\Lambda_{i,(}^{+}\cup\Lambda_{i,]}^{+}$ where
$\Lambda_{i,(}^{+},\Lambda_{i,]}^{+}$ are two (possibly empty) intervals and
when they are not, $\inf\Lambda_{i,(}^{+}=\inf K_{i}$ and the right endpoint
of $K_{i}$ belongs to $\Lambda_{i,]}^{+}$. The set $\\{x\in K_{s},\;g(x)<0\\}$
writes as $\Lambda_{s}^{-}\cup\Lambda_{s,]}^{-}$ where
$\Lambda_{s}^{-},\Lambda_{s,]}^{-}$ are two possibly empty intervals and when
$\Lambda_{s,]}^{-}$ is not empty, it reduces to $\\{a_{1}\\}$. The set
$\\{x\in K_{s},\;g(x)>0\\}$ writes $\Lambda_{s,(}^{+}\cup\Lambda_{s}^{+}$
where $\Lambda_{s,(}^{+},\Lambda_{s}^{+}$ are two possibly empty intervals and
when they are not $\inf\Lambda_{s,(}^{+}=\inf K_{s}$ and
$\sup\Lambda_{s}^{+}=\sup K_{s}$. We conclude that

$\displaystyle\left\\{{x\in
J_{1},\;g(x)<0}\right\\}=\left[{\bigcup_{i=2}^{s-1}\Lambda_{i}^{-}}\right]\cup\left[{\Lambda_{s}^{-}\cup\Lambda_{s,]}^{-}}\right]$

and

$\displaystyle\left\\{{x\in J_{1},\;g(x)>0}\right\\}$
$\displaystyle=\Lambda_{1,]}^{+}\cup\left[{\bigcup_{i=2}^{s-1}\left({\Lambda_{i,(}^{+}\cup\Lambda_{i,]}^{+}}\right)}\right]\cup\left[{\Lambda_{s,(}^{+}\cup\Lambda_{s}^{+}}\right]$

are both the unions of at most $s=m_{1}+1$ intervals.

By arguing similarly, we obtain that on the interval $J_{l+1}$: the sets
$\\{x\in J_{l+1},\;\epsilon g(x)>0\\}$ with $\epsilon\in\\{\pm 1\\}$ are the
unions of at most $m_{l+1}+1$ intervals where $m_{l+1}=|B\cap J_{l+1}|$.

When $l\geqslant 2$, let us now consider an interval of the form
$J_{i}=(a_{i-1},a_{i}]$ with $i\in\\{2,\ldots,l\\}$ and set $m_{i}=|B\cap
I_{i}|$. If $m_{i}=0$, $g$ is continuous and convex-concave on $I_{i}$ and by
arguing as for $K_{s}$, we obtain that $\\{x\in J_{i},\;\epsilon g(x)>0\\}$ is
the union of at most 2 intervals whatever $\epsilon\in\\{\pm 1\\}$. If
$m_{i}\geqslant 1$, we may partition $I_{i}$ with $m_{i}+1$ intervals of the
form $(a,b]$ with $a<b$, $a,b\in{\mathbb{R}}$. On each of these intervals, $g$
is continuous and convex-concave and by applying Lemma 5 and arguing as
previously, we obtain that $\\{x\in J_{i},\;\epsilon g(x)>0\\}$ is a union of
at most $m_{i}+2$ intervals.

Using (53) and the facts that $\sum_{i=1}^{l+1}m_{i}\leqslant|B|\leqslant D+1$
and $l\leqslant k-1$, we conclude that the sets $C_{{\varepsilon}}$ are unions
of at most

$\displaystyle
m_{1}+1+m_{l+1}+1+\sum_{i=2}^{l}\left({m_{i}+2}\right)\leqslant|B|+2l\leqslant
D+2k-1$

intervals. ∎

###### Proof Theorem 6.

The proof is based on Lemma 6 and three preliminary approximation results
given in Proposition 6, Proposition 7 and Proposition 8, whose proofs follow
that one.

######  Proposition 6.

Let $f$ be a convex-concave continuous function on a bounded nontrivial
interval $[a,b]$ and $\ell_{f}$ be the linear function

(54) $\ell_{f}:x\mapsto f(a)+\frac{f(b)-f(a)}{b-a}\left({x-a}\right).$

The following results hold.

  1. (i)

If $f$ admits a right derivative $f^{\prime}_{r}(a)$ at $a$ and a left
derivative $f^{\prime}_{l}(b)$ at $b$,

(55)
$\int_{a}^{b}\left|{f-\ell_{f}}\right|d\mu\leqslant\frac{(b-a)^{2}}{8}\left|{f^{\prime}_{r}(a)-f^{\prime}_{l}(b)}\right|.$

  2. (ii)

If $f$ is strictly monotone on $[a,b]$ with $f^{\prime}_{r}(a)\neq 0$ and
$f^{\prime}_{l}(b)\neq 0$

(56)
$\int_{a}^{b}\left|{f-\ell_{f}}\right|d\mu\leqslant\frac{(f(b)-f(a))^{2}}{8}\left|{\frac{1}{f^{\prime}_{r}(a)}-\frac{1}{f^{\prime}_{l}(b)}}\right|,$

with the convention $1/(\pm\infty)=0$.

Since $\ell_{f}$ is the equation of the chord connecting $(a,f(a))$ to
$(b,f(b))$, it is clear that $\ell_{f}(x)=f(x)$ for all $x\in\\{a,b\\}$,
$\ell_{f}\geqslant f$ on $[a,b]$ when $f$ is convex on $[a,b]$ and
$\ell_{f}\leqslant f$ when $f$ is concave.

######  Proposition 7.

Let $p$ be a monotone, continuous and convex-concave sub-density on a bounded
interval $[a,b]$ of length $L>0$ with a right derivative $p^{\prime}_{r}(a)$
at $a$ and a left derivative $p^{\prime}_{l}(b)$ at $b$. For all $D\geqslant
1$, there exists a $D$-linear interpolation $\overline{p}$ of $p$ such that

(57)
$\int_{a}^{b}\left|{p-\overline{p}}\right|d\mu\leqslant\frac{4}{3}\left[{\left({1+L\sqrt{\left|{p^{\prime}_{l}(b)-p^{\prime}_{r}(a)}\right|}}\right)^{1/D}-1}\right]^{2}.$

######  Proposition 8.

Let $p$ be a strictly monotone, continuous, convex-concave sub-density with
variation $V=|p(a)-p(b)|$ on a nontrivial bounded interval $[a,b]$. Assume
furthermore that $p^{\prime}_{r}(a)$ and $p^{\prime}_{l}(b)$ are nonzero.
Then, for all $D\geqslant 1$ there exists a $D$-linear interpolation
$\overline{p}$ of $p$ on $[a,b]$ such that

(58)
$\int_{a}^{b}\left|{p-\overline{p}}\right|d\mu\leqslant\frac{4}{3}\left[{\left({1+V\sqrt{\left|{\frac{1}{p^{\prime}_{r}(a)}-\frac{1}{p^{\prime}_{l}(b)}}\right|}}\right)^{1/D}-1}\right]^{2}.$

######  Lemma 6.

If $F$ is a nondecreasing, differentiable, concave function on
${\mathbb{R}}_{+}$, the mapping

$\phi:u\mapsto\left[F\left({\sqrt{u}}\right)-F(0)\right]^{2}$

is concave on $\mathbb{R}_{+}$. In particular for all $D\geqslant 1$,

$F_{D}:u\mapsto\left[{\left({1+\sqrt{u}}\right)^{1/D}-1}\right]^{2}$

is concave on ${\mathbb{R}}_{+}$.

###### Proof.

For all $u>0$,

$\phi^{\prime}(u)=\frac{F\left({\sqrt{u}}\right)-F(0)}{\sqrt{u}}F^{\prime}(\sqrt{u})$

is the product of $u\mapsto[F\left({\sqrt{u}}\right)-F(0)]/\sqrt{u}$ and
$u\mapsto F^{\prime}(\sqrt{u})$ which are both nonnegative and nonincreasing
since $F$ is nondecreasing and concave. The function $\phi^{\prime}$ is
therefore nonincreasing and $\phi$ concave. ∎

Let’s turn to the proof of Theorem 6. We first introduce some mappings of
interest we will use in the proofs of of Theorem 6 and Proposition 7. Let
${\mathcal{V}}$ be the linear space of continuous functions $f$ on $[a,b]$
that admits a right derivative $f^{\prime}_{r}(a)$ at $a$ and a left
derivative $f^{\prime}_{l}(b)$ at $b$. Given $m\in{\mathbb{R}}$, we define
${\mathcal{T}}_{1}$ and ${\mathcal{T}}_{2}$ as the mappings defined on
${\mathcal{V}}$ by

(59) ${\mathcal{T}}_{1}:f\mapsto[x\mapsto
f(a+b-x)],\quad{\mathcal{T}}_{2}:f\mapsto[x\mapsto m-f(x)].$

Although ${\mathcal{T}}_{2}$ depends on the choice of $m$, we drop this
dependency in the notation for the sake of convenience. The mappings
${\mathcal{T}}_{j}$ are one-to-one from ${\mathcal{V}}$ onto itself, isometric
with respect to the ${\mathbb{L}}_{1}$-norm on ${\mathcal{V}}$ and they
satisfy for all $f\in{\mathcal{V}}$

(60) $\displaystyle\left|{f(a)-f(b)}\right|$
$\displaystyle=\left|{{\mathcal{T}}_{j}(f)(a)-{\mathcal{T}}_{j}(f)(b)}\right|$
(61) $\displaystyle\left|{f^{\prime}_{r}(a)-f^{\prime}_{l}(b)}\right|$
$\displaystyle=\left|{({\mathcal{T}}_{j}(f))^{\prime}_{r}(a)-({\mathcal{T}}_{j}(f))^{\prime}_{l}(b)}\right|$

and ${\mathcal{T}}_{j}^{-1}={\mathcal{T}}_{j}$ for all $j\in\\{1,2\\}$.
Let us now turn to the proof of Theorem 6 and assume first that $p$ is
nondecreasing, continuous and convex on $[a,b]$ so that
$p_{r}^{\prime}(a)\geqslant 0$. If $p$ is constant, the result is clear by
taking $\overline{p}=p$. We may therefore assume that $p(a)<p(b)$ and choose a
point $c\in(a,b)$ such that $p(c)>p(a)$. In particular,
$w_{1}=\int_{a}^{c}pd\mu>0$ and

$0<\frac{p(c)-p(a)}{c-a}\leqslant
p^{\prime}_{l}(c)\leqslant\frac{p(b)-p(c)}{b-c}<+\infty.$

The restriction $p_{1}$ of $p$ on the interval $[a,c]$ is nondecreasing,
continuous and convex and so is the density $p_{1}/w_{1}$. We may therefore
apply Proposition 7 to $p_{1}/w_{1}$ and find a $D$-linear interpolation
$\overline{p}_{1}$ of $p$ on $[a,c]$ that satisfies

(62) $\displaystyle\int_{a}^{c}\left|{p-\overline{p}_{1}}\right|d\mu$
$\displaystyle\leqslant\frac{4w_{1}}{3}\left[{\left({1+(c-a)\sqrt{\frac{p^{\prime}_{l}(c)-p^{\prime}_{r}(a)}{w_{1}}}}\right)^{1/D}-1}\right]^{2}.$

The restriction $p_{2}$ of $p$ to $[c,b]$ is increasing, continuous and convex
with nonzero right and left derivatives at $c$ and $b$ respectively. We may
therefore apply Proposition 8 to the density $p_{2}/w_{2}$ with
$w_{2}=\int_{c}^{b}pd\mu=1-w_{1}>0$ and find a $D$-linear interpolation
$\overline{p}_{2}$ of $p$ on $[c,b]$ that satisfies

(63)
$\displaystyle\int_{c}^{b}\left|{p-\overline{p}_{2}}\right|d\mu\leqslant\frac{4w_{2}}{3}\left[{\left({1+\frac{p(b)-p(c)}{\sqrt{w_{2}}}\sqrt{\frac{1}{p^{\prime}_{r}(c)}-\frac{1}{p^{\prime}_{l}(b)}}}\right)^{1/D}-1}\right]^{2}.$

We may choose $c\in(a,b)$ such that

$p^{\prime}_{l}(c)\leqslant\Delta\quad\text{and}\quad
p^{\prime}_{r}(c)\geqslant\Delta\quad\text{with}\quad\Delta=\frac{p(b)-p(a)}{b-a}.$

Then

$\displaystyle A$
$\displaystyle=(c-a)^{2}\left({p^{\prime}_{l}(c)-p^{\prime}_{r}(a)}\right)+(p(b)-p(c))^{2}\left({\frac{1}{p^{\prime}_{r}(c)}-\frac{1}{p^{\prime}_{l}(b)}}\right)$
$\displaystyle\leqslant(b-a)^{2}\left({\Delta-p^{\prime}_{r}(a)}\right)+(p(b)-p(a))^{2}\left({\frac{1}{\Delta}-\frac{1}{p^{\prime}_{l}(b)}}\right)$
(64)
$\displaystyle=2(b-a)(p(b)-p(a))\left[{1-\frac{1}{2}\left({\frac{p^{\prime}_{r}(a)}{\Delta}+\frac{\Delta}{p^{\prime}_{l}(b)}}\right)}\right]=2LV\Gamma.$

The function $\overline{p}=\overline{p}_{1}1\hskip-2.6pt{\rm
l}_{[a,c)}+\overline{p}_{2}1\hskip-2.6pt{\rm l}_{[c,b]}$ is a $2D$-linear
interpolation of $p$ on $[a,b]$. Since by Lemma 6 the function $F_{D}$ is
concave and increasing, we deduce from (64), (62) and (63) that

$\displaystyle\frac{3}{4}\left\|{p-\overline{p}}\right\|$
$\displaystyle\leqslant
w_{1}\int_{a}^{c}\left|{p-\overline{p}_{1}}\right|d\mu+w_{2}\int_{c}^{b}\left|{p-\overline{p}_{2}}\right|d\mu$
$\displaystyle\leqslant
w_{1}F_{D}\left({\frac{(c-a)^{2}\left({p^{\prime}_{l}(c)-p_{r}(a)}\right)}{w_{1}}}\right)$
$\displaystyle\quad+w_{2}F_{D}\left({\frac{(p(b)-p(c))^{2}}{w_{2}}\left({\frac{1}{p^{\prime}_{r}(c)}-\frac{1}{p^{\prime}_{l}(b)}}\right)}\right)$
$\displaystyle\leqslant F_{D}(A)\leqslant F_{D}(2LV\Gamma),$

which is (32).

The density $q=\overline{p}/\int_{a}^{b}\overline{p}d\mu$ is continuous
convex-concave on $[a,b]$ and piecewise linear on a partition of $[a,b]$ into
$2D$ intervals and it follows from Lemma 3 that

(65) $\int_{a}^{b}\left|{p-q}\right|d\mu\leqslant
2\left\\{{1\wedge\left[{\frac{4}{3}\left({\left({1+\sqrt{2LV\Gamma}}\right)^{1/D}-1}\right)^{2}}\right]}\right\\}.$

The mapping $z\mapsto(4/3)(e^{z}-1)^{2}$ is not larger than 1 if and only if
$z\leqslant z_{0}=\log(1+\sqrt{3/4})$ and for all $z\in[0,z_{0}]$,
$e^{z}-1\leqslant(e^{z_{0}}-1)z/z_{0}$. Consequently, for all $z\geqslant 0$

$\displaystyle
2\left\\{{1\wedge\left[{\frac{4}{3}\left({e^{z}-1}\right)^{2}}\right]}\right\\}$
$\displaystyle=\frac{8}{3}\left({e^{z_{0}\wedge
z}-1}\right)^{2}\leqslant\frac{8}{3}\left({\frac{e^{z_{0}}-1}{z_{0}}z}\right)^{2}\leqslant
5.14z^{2}.$

Applying this inequality with $z=D^{-1}\log\left({1+\sqrt{2LV\Gamma}}\right)$,
we deduce (33) from (65).

Theorem 6 is therefore proven for a nondecreasing, continuous convex density
$p$. In order to prove the result in the other cases, we use the
transformations ${\mathcal{T}}_{1}$ and ${\mathcal{T}}_{2}$ introduced above
and defined by (59). These transformations are isometric with respect to the
${\mathbb{L}}_{1}$-norm and they preserve the variation of a monotone
function. Note that they also preserve the linear index, i.e. for all
continuous convex-concave function $f$ on $[a,b]$ and $j\in\\{1,2\\}$,
$\Gamma(f)=\Gamma\left({{\mathcal{T}}_{j}(f)}\right)$. Applying
${\mathcal{T}}_{1}$ to nonincreasing continuous convex densities we establish
(33) and we extend it to all monotone concave continuous densities by applying
${\mathcal{T}}_{2}$. ∎

###### Proof of Proposition 6.

Let us first assume that $f$ is concave on $[0,1]$, admits a right derivative
at 0, a left derivative at 1 and satisfies $f(0)=0$ and $f(1)$=1. Let us show
that

(66)
$\int_{0}^{1}\left|{f-\ell_{f}}\right|d\mu\leqslant\frac{1}{2}\frac{\left({f_{r}^{\prime}(0)-1}\right)\left({1-f^{\prime}_{l}(1)}\right)}{f^{\prime}_{r}(0)-f^{\prime}_{l}(1)},$

with the convention $0/0=1$. If $f$ is linear on $[0,1]$, then
$f_{r}^{\prime}(0)=f^{\prime}_{l}(1)=1$ and the inequality is satisfied with
our convention. Otherwise, $f_{l}^{\prime}(1)<1=f(1)-f(0)<f_{r}^{\prime}(0)$
and since $f$ lies above its chord and under its tangents at 0 and 1,

$\ell_{f}(x)\leqslant
f(x)\leqslant\min\left\\{{f^{\prime}_{r}(0)x,1+f_{l}^{\prime}(1)(x-1)}\right\\}\quad\text{for
all $x\in[0,1]$}.$

Since $\ell_{f}(x)=x$, we deduce that for all $c\in[0,1]$

$\displaystyle\int_{0}^{1}\left|{f-\ell_{f}}\right|d\mu$
$\displaystyle\leqslant\int_{0}^{c}(f^{\prime}_{r}(0)-1)xd\mu+\int_{c}^{1}(1-f_{l}^{\prime}(1))(1-x)d\mu$
$\displaystyle=\frac{1}{2}\left[{(f^{\prime}_{r}(0)-1)c^{2}+(1-f_{l}^{\prime}(1))(1-c)^{2}}\right].$

The result follows by minimizing with respect to $c$, i.e. by taking
$c=(1-f_{l}^{\prime}(1))/(f_{r}^{\prime}(0)-f_{l}^{\prime}(1))\in(0,1)$. In
particular, we deduce from (67) that

$\displaystyle\int_{0}^{1}\left|{f-\ell_{f}}\right|d\mu\leqslant\frac{c(1-c)}{2}\left({f^{\prime}_{r}(0)-f^{\prime}_{l}(1)}\right)$

and since $c(1-c)\leqslant 1/4$, we obtain that

(67)
$\int_{0}^{1}\left|{f-\ell_{f}}\right|d\mu\leqslant\frac{1}{8}\left({f^{\prime}_{r}(0)-f^{\prime}_{l}(1)}\right).$

Note that the inequality also holds when
$f^{\prime}_{r}(0)=f^{\prime}_{l}(1)=1$.

When $f$ is increasing on $[0,1]$ and satisfies $0<1-f_{l}^{\prime}(1)<1$,
i.e. $f_{l}^{\prime}(1)\neq 0$, we also deduce from (67) and the convexity of
$z\mapsto 1/z$ on $(0,+\infty)$ that

$\displaystyle\int_{0}^{1}\left|{f-\ell_{f}}\right|d\mu$
$\displaystyle\leqslant\frac{1}{4}\frac{1}{\frac{1}{2}\left[{\left({\frac{1}{1-f^{\prime}_{l}(1)}-1}\right)+\left({1+\frac{1}{f^{\prime}_{r}(0)-1}}\right)}\right]}$
$\displaystyle\leqslant\frac{1}{4}\left[{\frac{1}{2}\left({\frac{1}{\frac{1}{1-f^{\prime}_{l}(1)}-1}+\frac{1}{1+\frac{1}{f^{\prime}_{r}(0)-1}}}\right)}\right]$
$\displaystyle=\frac{1}{8}\left[{\frac{1-f^{\prime}_{l}(1)}{f^{\prime}_{l}(1)}+\frac{f^{\prime}_{r}(0)-1}{f^{\prime}_{r}(0)}}\right]$

which leads to

(68)
$\int_{0}^{1}\left|{f-\ell_{f}}\right|d\mu\leqslant\frac{1}{8}\left({\frac{1}{f^{\prime}_{l}(1)}-\frac{1}{f^{\prime}_{r}(0)}}\right).$

Note that the inequality is still satisfied when $f^{\prime}_{r}(0)=+\infty$
with the convention $1/(+\infty)=0$.

Let us now turn to the proofs of (55) and (56). Note that (55) is clearly true
when $f$ is constant on $[a,b]$ and we may therefore assume that $f(a)\neq
f(b)$. We obtain (55) and (56) by applying (67) and (68) respectively to the
function

$g(x)=\frac{f(a+x(b-a))-f(a)}{f(b)-f(a)}$

when $f$ is concave and satisfies $f(b)>f(a)$ or when $f$ is convex and
satisfies $f(a)>f(b)$. In the other cases, one may use the function

$g(x)=\frac{f(b-x(b-a))-f(b)}{f(a)-f(b)}.$

∎

###### Proof of Proposition 7.

Let us first consider a function $g$ that is monotone, continuous and convex
on $[a,b]$ and that satisfies $g(a)=g_{r}^{\prime}(a)=0$ and
$0<\int_{a}^{b}gd\mu\leqslant 1$. Then $g$ is nonnegative and nondecreasing on
$[a,b]$. Since $\int_{a}^{b}gd\mu>0$, $g$ is not identically equal to 0 on
$[a,b]$ and consequently,

$g_{l}^{\prime}(b)\geqslant\frac{g(b)-g(a)}{b-a}>0.$

Let $q>1$ and

$x_{0}=a\quad\text{and}\quad
x_{i}=x_{i-1}+L\frac{q^{-i}}{\sum_{j=1}^{D}q^{-j}}\quad\text{for all
$i\in\\{1,\ldots,D\\}$},$

so that $x_{D}=b$ and
$\Delta_{i+1}=x_{i+1}-x_{i}=q^{-1}(x_{i}-x_{i-1})=q^{-1}\Delta_{i}$ for all
$i\in\\{1,\ldots,D-1\\}$ and

$\Delta_{D}=L\frac{q^{-D}(1-q^{-1})}{q^{-1}-q^{-(D+1)}}=L\frac{q-1}{q^{D}-1}.$

Let $g^{\prime}$ be any nondecreasing function on $[a,b]$ satisfying
$0=g_{r}^{\prime}(a)=g^{\prime}(a)$, $g_{l}^{\prime}(b)=g^{\prime}(b)$ and
$g_{l}^{\prime}(x)\leqslant g^{\prime}(x)\leqslant g_{r}^{\prime}(x)$ for all
$x\in(a,b)$. Since $g$ is convex, we may write

(69) $g(x)\geqslant g(x_{i})+g^{\prime}(x_{i})(x-x_{i})\quad\text{for all
$i\in\\{1,\ldots,D\\}$ and $x\in[a,b]$}.$

In particular, for all $i\in\\{1,\ldots,D-1\\}$

$\displaystyle\int_{x_{i}}^{x_{i}+1}\left({g(x_{i})+g^{\prime}(x_{i})(x-x_{i})}\right)d\mu(x)$
$\displaystyle=\left[{g(x_{i})+\frac{g^{\prime}(x_{i})\Delta_{i+1}}{2}}\right]\Delta_{i+1}$
$\displaystyle\leqslant\int_{x_{i}}^{x_{i}+1}gd\mu,$

hence,

(70) $g^{\prime}(x_{i})\Delta_{i+1}^{2}\leqslant
2\int_{x_{i}}^{x_{i}+1}(g-g(x_{i}))d\mu.$

Moreover, applying (69) with $x_{i}=x_{D}=b$ and using the facts that $g$ is
nonnegative and nonincreasing, we get

$\displaystyle 1\geqslant\int_{a}^{b}gd\mu$
$\displaystyle\geqslant\int_{a}^{b}\left({g(b)+g^{\prime}(b)(x-b)}\right)_{+}d\mu(x)$
$\displaystyle=\int_{b-g(b)/g^{\prime}(b)}^{b}\left({g(b)+g^{\prime}(b)(x-b)}\right)d\mu(x)=\frac{g^{2}(b)}{2g^{\prime}(b)},$

consequently

(71) $g(b)\leqslant\sqrt{2g^{\prime}(b)}.$

Let $g_{i}$ be the restriction of $g$ on the interval $[x_{i-1},x_{i}]$ and
$\overline{g}$ the function on $[a,b]$ that coincides on $[x_{i-1},x_{i}]$
with $\ell_{g_{i}}$ defined by (54) with $f=g_{i}$ for all
$i\in\\{1,\ldots,D\\}$. The function $\overline{g}$ is a $D$-linear
interpolation of $g$ on $[a,b]$ that satisfies

$\displaystyle\int_{a}^{b}\left|{g-\overline{g}}\right|d\mu$
$\displaystyle=\sum_{i=1}^{D}\int_{x_{i-1}}^{x_{i}}\left({\overline{g}-g}\right)d\mu$
$\displaystyle\leqslant\frac{1}{8}\sum_{i=1}^{D}\Delta_{i}^{2}\left({g_{l}^{\prime}(x_{i})-g_{r}^{\prime}(x_{i-1})}\right)$
$\displaystyle\leqslant\frac{1}{8}\sum_{i=1}^{D}\Delta_{i}^{2}\left({g^{\prime}(x_{i})-g^{\prime}(x_{i-1})}\right)$
$\displaystyle=\frac{1}{8}\left[{-\Delta_{1}^{2}g^{\prime}(a)+\Delta_{D}^{2}g^{\prime}(b)+\sum_{i=1}^{D-1}g^{\prime}(x_{i})\left({\Delta_{i}^{2}-\Delta_{i+1}^{2}}\right)}\right].$

Since $g^{\prime}(a)=0$ and $\Delta_{i}=q\Delta_{i+1}$ for all
$i\in\\{1,\ldots,D-1\\}$ we deduce that

(72)
$\int_{a}^{b}\left|{g-\overline{g}}\right|d\mu\leqslant\frac{1}{8}\left[{\Delta_{D}^{2}g^{\prime}(b)+(q^{2}-1)\sum_{i=1}^{D-1}g^{\prime}(x_{i})\Delta_{i+1}^{2}}\right].$

Using (70), (71) and the fact that $g$ is nondecreasing,

$\displaystyle\frac{1}{2}\sum_{i=1}^{D-1}g^{\prime}(x_{i})\Delta_{i+1}^{2}$
$\displaystyle\leqslant\sum_{i=1}^{D-1}\int_{x_{i}}^{x_{i+1}}(g-g(x_{i}))d\mu$
$\displaystyle=\int_{x_{1}}^{x_{D}}gd\mu-\sum_{i=1}^{D-1}\Delta_{i+1}g(x_{i})=\int_{x_{1}}^{x_{D}}gd\mu-q^{-1}\sum_{i=1}^{D-1}\Delta_{i}g(x_{i})$
$\displaystyle\leqslant\int_{x_{1}}^{x_{D}}gd\mu-q^{-1}\sum_{i=1}^{D-1}\int_{x_{i-1}}^{x_{i}}gd\mu=\int_{x_{1}}^{x_{D}}gd\mu-q^{-1}\int_{x_{0}}^{x_{D-1}}gd\mu$
$\displaystyle=(1-q^{-1})\int_{x_{1}}^{x_{D}}gd\mu+q^{-1}\int_{x_{D-1}}^{x_{D}}gd\mu-q^{-1}\int_{x_{0}}^{x_{1}}gd\mu$
$\displaystyle\leqslant(1-q^{-1})\times 1+q^{-1}\Delta_{D}g(b)\leqslant
1-q^{-1}+q^{-1}\sqrt{2\Delta_{D}^{2}g^{\prime}(b)}.$

It follows from (72) that

$\displaystyle\int_{a}^{b}\left|{g-\overline{g}}\right|d\mu$
$\displaystyle\leqslant\frac{1}{8}\left[{\Delta_{D}^{2}g^{\prime}(b)+2(q^{2}-1)\left({1-q^{-1}+q^{-1}\sqrt{2\Delta_{D}^{2}g^{\prime}(b)}}\right)}\right]$
$\displaystyle\leqslant\frac{(q-1)^{2}}{8}\left[{\frac{L^{2}g^{\prime}(b)}{(q^{D}-1)^{2}}+2\left({1+\frac{1}{q}}\right)\left({1+\frac{L\sqrt{2g^{\prime}(b)}}{q^{D}-1}}\right)}\right].$

Finally, choosing $q$ such that

$q^{D}-1=L\sqrt{g^{\prime}(b)}\quad\text{i.e.}\quad
q=\left({1+L\sqrt{g^{\prime}(b)}}\right)^{1/D}>1,$

we get that

$\displaystyle\int_{a}^{b}\left|{g-\overline{g}}\right|d\mu$
$\displaystyle\leqslant\frac{1+4(1+\sqrt{2})}{8}\left[{\left({1+L\sqrt{g^{\prime}(b)}}\right)^{1/D}-1}\right]^{2}$
(73)
$\displaystyle\leqslant\frac{4}{3}\left[{\left({1+L\sqrt{g^{\prime}(b)}}\right)^{1/D}-1}\right]^{2}.$

Let us now prove Proposition 7 in the case where $p$ is convex and
nondecreasing. Then $p^{\prime}_{r}(a)\geqslant 0$ and we may set
$\ell:x\mapsto p(a)+p_{r}^{\prime}(a)(x-a)$ and $g:x\mapsto p(x)-\ell(x)$. The
function $g$ is nonnegative, nondecreasing, continuous and convex on $[a,b]$