\section{Introduction}
Estimating a density under a shape constraint has been addressed by many authors since the pioneer papers by Grenander ~\citeyearpar{MR0093415,MR599175}, Rao~\citeyearpar{rao1969estimation}, Groeneboom~\citeyearpar{MR822052} and Birg\'e~\citeyearpar{MR1026298} 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~\citeyearpar{MR0093415}-- which is the maximum likelihood estimator (MLE for short) over the set of densities that satisfy this monotonicity constraint on $(0,+\infty)$. Rao~\citeyearpar{rao1969estimation} and  Grenander ~\citeyearpar{MR0093415,MR599175} established the local asymptotic properties of the Grenander estimator while  Groeneboom~\citeyearpar{MR822052} and  Birg\'e~\citeyearpar{MR1026298} studied its global estimation errors for the $\L_{1}$-loss on some functional classes of interest. Birg\'e 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 ~\citeyearpar{MR599175}, Groeneboom~\citeyearpar{MR822052} and Birg\'e~\citeyearpar{MR1026298}. As a consequence, the Grenander estimator can nicely {\em adapt} to the specific features of the target density even though these features are {\em a priori} unknown. 

Because of these {\em 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 {\em et al}~\citeyearpar{MR1891741} for convex densities and to Balabdaoui and Wellner ~\citeyearpar{MR2435342} and Gao and Wellner~\citeyearpar{MR2520591} 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 \cite{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. \cite{Birge_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 $\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\"umbgen and K. Rufibach~\citeyearpar{MR2546798}, Doss and Wellner~\citeyearpar{MR3485950} , Cule and Samworth~\citeyearpar{MR2645484}, Kim and Samworth~\citeyearpar{Kim2016} and Feng {\em et al}~\citeyearpar{Feng2021} as well as the references therein. Kim and Samworth~\citeyearpar{Kim2016} 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 {\em et al}~\citeyearpar{MR3845018} when $d=1$ and extended to the dimensions $d\in\{2,3\}$ by Feng {\em et al}~\citeyearpar{Feng2021}. In dimension $d\geqslant 4$, Kur \textit{et al.} \cite{Kur_2019optimality} 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 $\L_{1}$-loss) to a density that does satisfy it. In a nutshell, our aim is to build estimators that are {\em robust}. Except for the Grenander estimator (which is a particular case of a $\rho$-estimator --- see Baraud and Birg\'e~\citeyearpar{BarBir2018}[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 {\em et al}
~\citeyearpar{Chan2014EfficientDE} 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 $\L_{1}$-distance) of the true density from the model. Their approach is based on the estimation procedure described in Devroye and Lugosi~\citeyearpar{MR1843146} 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 $\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 {\em et al} does not possess such a property. Besides, their approach provides competitors to the MLE for some specific density models only.  Chan {\em 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\'e~\citeyearpar{MR3565484}[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\'e for the Hellinger one. We do not know if $\rho$-estimators would satisfy the same $\L_{1}$-risk bounds as those we establish here. 

Our procedure shares some similarities with that proposed by Devroye and Lugosi~\citeyearpar{MR1843146}. 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~\citeyearpar{BY-TEST} 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 $\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 $\L_{1}$-distances of $\widehat p$ to the $p_{i}^{\star}$, i.e.\ the quantity $n^{-1}\sum_{i=1}^{n}\norm{\widehat p-p_{i}^{\star}}$. 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. 
\begin{itemize}
\item 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).
\item The global rates of convergence that we establish for our estimator are optimal in all the models we consider.
\item 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.  
\item 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. 
\end{itemize}

The paper is organized as follows. The statistical framework is described in Section~\ref{sect-2} and the construction of the estimator as well as its properties are presented in Section~\ref{sec-ell-estimator}. The more specific properties of our estimator for estimating a mixture of densities that are monotone, convex or concave can be found in Sections~\ref{sect-kmono} and~\ref{sect-cvxcve} respectively while the case of a log-concave density is tackled in  ~\ref{sect-logcc} 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~\ref{sect-7}. 


\section{The statistical framework and main notations}\label{sect-2}
Let $\etc{X}$ 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 ${\bs{X}}=(X_{1},\ldots,X_{n})$ on the basis of a suitable {\em 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({\bs{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 ${\bs{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 $\norm{\cdot}$ the $\L_{1}$-norm on the set $\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 
\begin{equation}\label{TV_def_eq}
\dTV{P}{Q}=\underset{A\in{\mathscr{A}}}\sup\cro{P(A)-Q(A)}
\end{equation}
and if $P$ and $Q$ are absolutely continuous with respect to our dominating measure $\mu$, 
\[
\dTV{P}{Q}=\frac{1}{2}\norm{\frac{dP}{d\mu}-\frac{dQ}{d\mu}}.
\]
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 $\dTV{P^{\star}}{P}$ 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.
\begin{ass}\label{Ass00}
There exists a countable subset ${\mathcal{M}}$ of $\overline {\mathcal{M}}$ that is dense in $\overline {\mathcal{M}}$ for the $\L_{1}$-norm.  
\end{ass}
We recall that a subset of a separable metric space is separable. In particular, when the space $\L_{1}({\mathscr{X}},{\mathscr{A}},\mu)$ is separable for the $\L_{1}$-norm, so is any subset $\overline {\mathcal{M}}$ of densities on $({\mathscr{X}},{\mathscr{A}},\mu)$ and Assumption~\ref{Ass00} is automatically satisfied. This is in particular the case when $({\mathscr{X}},{\mathscr{A}})=({\mathbb{R}}^{k},{\mathscr{B}}({\mathbb{R}}^{k}))$, $k\ge 1$ and $\mu$ is the Lebesgue measure. If a family $\overline {\mathcal{M}}$ of densities satisfies our Assumption~\ref{Ass00}, 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}},\norm{\cdot})$ 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}}}\dTV{P^{\star}}{P}=\inf_{P\in \overline {\mathscr{D}}}\dTV{P^{\star}}{P}.
\]
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 {\em 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 {\em $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({\bs{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({\bs{X}})\right)$ and $\mathop{\rm Var}\nolimits_{S}\left(f(X)\right)$. 



\section{An $\ell$-type estimator for the TV-loss}\label{sec-ell-estimator}
Let $\overline {\mathcal{M}}$  be a density model that satisfies our  Assumption~\ref{Ass00} for some ${\mathcal{M}}\subset \overline {\mathcal{M}}$. Given $P=p\cdot \mu$ and $Q=q\cdot \mu$ in ${\mathscr{M}}$, we define
\begin{equation}\label{Non_symmetric_test_eq}
t_{(P,Q)}=1\hskip-2.6pt{\rm l}_{q>p}-P(q>p)=P(p\ge q)-1\hskip-2.6pt{\rm l}_{p\ge q}.
\end{equation}
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$ 
\begin{equation}\label{def-TPQ}
{\mathbf{T}}({\mathbf{x}},P,Q)=\sum_{i=1}^n t_{(P,Q)}(x_i)=\sum_{i=1}^{n}\cro{1\hskip-2.6pt{\rm l}_{q>p}(x_{i})-P(q>p)}
\end{equation}
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
\begin{equation}\label{def-EX}
{\mathscr{E}}({\bs{X}})=\ac{P\in{\mathscr{M}},\, {\mathbf{T}}({\bs{X}},P)\le \underset{P'\in{\mathscr{M}}}\inf {\mathbf{T}}({\bs{X}},P')+\varepsilon}.
\end{equation}
We call $\widehat P$ and $\widehat p$ a {\em TV-estimator} on ${\mathscr{M}}$ and ${\mathcal{M}}$ respectively. The parameter ${\varepsilon}$ is introduced in case a minimizer of $P\mapsto {\mathbf{T}}({\bs{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~\citeyearpar{BY-TEST} 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~\citeyearpar{BY-TEST}). 
\begin{lem}\label{bound_test_TV_lem}
For all probabilities $P,Q\in{\mathscr{M}}$ and $S\in{\mathscr{P}}$,
\begin{equation}
\dTV{P}{Q}- \dTV{S}{Q}\le {\mathbb{E}}_{S}\cro{t_{(P,Q)}(X)}\le \dTV{S}{P}.
\label{eq-SPQ}
\end{equation}
In particular, 
\begin{equation}\label{bound_test_TV_eq}
\dTV{P}{Q} - \dTV{P^{\star}}{Q}\leq \frac{1}{n}\sum_{i=1}^n{\mathbb{E}}\cro{t_{(P,Q)}(X_i)}\leq \dTV{P^{\star}}{P},
\end{equation}
where $P^{\star} = n^{-1}\sum_{i = 1}^n P_i^{\star}$.
\end{lem}
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~\citeyearpar{BY-TEST}. 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~\citeyearpar{MR1843146}[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~\eref{def-TPQ} by 
\[
{\mathbf{T}}_{\text{DL}}(\cdot, P,Q):{\mathbf{x}}\mapsto \ab{\sum_{i=1}^{n}\cro{1\hskip-2.6pt{\rm l}_{q\ge p}(x_{i})-P(q\ge p)}}.
\]
Their approach leads to a set of estimators ${\mathscr{E}}_{\text{DL}}({\bs{X}})$ defined in the same way as \eref{def-EX} for ${\mathbf{T}}_{\text{DL}}$ in place of ${\mathbf{T}}$ (with ${\varepsilon}=1$). 

\begin{proof}[Proof of Lemma~\ref{bound_test_TV_lem}]
Let $P,Q\in{\mathscr{M}}$. Using the definition \eqref{Non_symmetric_test_eq} of $t_{(P,Q)}$ and that of the TV-loss given by~\eref{TV_def_eq}, we obtain that for all $S\in{\mathscr{P}}$,
\[
{\mathbb{E}}_{S}\cro{t_{(P,Q)}(X)}=S(q>p)-P(q>p)\leq\dTV{S}{P},
\]
which is exactly the second inequality in~\eref{eq-SPQ}. To establish the first one, we use the fact that $\dTV{P}{Q}=Q(q>p)-P(q>p)$. This leads to 
\begin{align*}
{\mathbb{E}}_{S} \cro{t_{(P,Q)}(X)}
&=S(q>p)-Q(q>p)+\cro{Q(q>p)-P(q>p)}\\
&\ge -\dTV{S}{Q}+\dTV{P}{Q} .
\end{align*} 
Finally, \eref{bound_test_TV_eq} 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]. \]
\end{proof}

\subsection{Properties of the estimator}
Our main result is based on the key notion of \textit{extremal point} in a model.
\begin{df}
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\ge 1$ if the classes of subsets
\begin{align*}
    {\mathscr{C}}^{>}({\mathcal{F}},\overline{f}) &= \big\{\{x\in{\mathscr{X}}\,\big|\,q(x)>\overline{f}(x)\},\; q\in{\mathcal{F}}\setminus\{\overline{f}\}\big\}
\end{align*}
and 
\begin{align*}
    {\mathscr{C}}^{<}({\mathcal{F}},\overline{f}) &= \big\{\{x\in{\mathscr{X}}\,\big|\,q(x) < \overline{f}(x)\},\; q\in{\mathcal{F}}\setminus\{\overline{f}\}\big\}    
\end{align*}
are both VC  with dimension not larger than $D$. 
\end{df}
\noindent
Additionally, we say that $\overline P$ is {\em an extremal point} of $\overline {\mathscr{M}}$ with degree not larger than $D\ge 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\ge 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\ge 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\ge 1}{\mathcal{O}}(D)$. 

\begin{thm}\label{shape-estimation-th}
Let $\overline {\mathcal{M}}$ be a density model satisfying our Assumption~\ref{Ass00} 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 \geq 1$ and all $P \in  \overline {\mathscr{O}}(D)$,
\begin{equation} \label{inthm_ubd_dist_p_phat}
\dTV{P}{\widehat P} \leq 2\dTV{P ^{\star}}{P} + 20\sqrt{\frac{5D}{n}}+\sqrt{\frac{2(\xi +\log 2)}{n}}+\frac{\varepsilon}{n}.
\end{equation}
In particular,
\begin{align}
&\dTV{P ^{\star}}{\widehat P}\leq \inf_{D\ge 1}\cro{ 3\inf_{P\in \overline {\mathscr{O}}(D)}\dTV{P ^{\star}}{P} + 20\sqrt{\frac{5D}{n}}} +\sqrt{\frac{2(\log 2+\xi)}{n}}+\frac{\varepsilon}{n},\label{Thm1_risk_bound_deviation_eq}
\end{align}
with the convention $\inf_{\varnothing}=+\infty$.  As a consequence of \eqref{inthm_ubd_dist_p_phat},
\begin{equation} \label{inthm_ubd_expt_dist_p_phat}
    \mathbb{E}\left[ \dTV{P}{\widehat P} \right] \leq 2\dTV{P ^{\star}}{P} + 48\sqrt{\frac{D}{n}} +\frac{\varepsilon}{n}
\end{equation}
for all $D\geq 1$ and all $P \in \overline {\mathscr{O}}(D)$, moreover by \eqref{Thm1_risk_bound_deviation_eq},
\begin{equation}\label{Thm1_risk_bound_expecation_eq}
\mathbb{E}\cro{\dTV{P ^{\star}}{\widehat P}} \leq  \inf_{D\ge 1}\left\{ 3\inf_{P\in \overline {\mathscr{O}}(D)}\dTV{P ^{\star}}{P} + 48\sqrt{\frac{D}{n}} \right\}+\frac{\varepsilon}{n}.
\end{equation}
\end{thm}

\begin{proof}
The proof is postponed to Subsection \ref{subsect-proof-ell-estimator}.
\end{proof}

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\ge 1}\inf_{P\in \overline {\mathscr{O}}(D)}\dTV{P ^{\star}}{P}=0$ and we deduce from~\eref{Thm1_risk_bound_expecation_eq} 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\ge 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
\begin{equation}\label{eq-marginales}
P_{i}^{\star}=(1-\alpha_{i})\overline P+\alpha_{i} R_{i}=\overline P+\alpha_{i}\pa{R_{i}-\overline P}
\end{equation}
for some $\overline P\in \overline {\mathscr{O}}(D)$ with $D\ge 1$, $\alpha_{1},\ldots,\alpha_{n}$ in $[0,1]$ and distributions $R_{1},\ldots,R_{n}$ in ${\mathscr{P}}$, we deduce from~\eref{inthm_ubd_expt_dist_p_phat} that 
\begin{align*}
\mathbb{E}\cro{\dTV{\overline P}{\widehat P}}&\le 2\dTV{P ^{\star}}{\overline P} + 48\sqrt{\frac{D}{n}} +\frac{\varepsilon}{n}\\
&\le \frac{2}{n}\sum_{i=1}^{n}\alpha_{i}+ 48\sqrt{\frac{D}{n}} +\frac{\varepsilon}{n}.
\end{align*}
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 {\em 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 \eref{eq-marginales}. 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 {\em 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 \eref{eq-marginales} 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 \eref{Thm1_risk_bound_deviation_eq} has been established in Baraud~\citeyearpar{BY-TEST} for his $\ell$-estimators. 
His inequality~(48) can be reformulated in our context as  
\begin{align*}
\frac{1}{n} \sum_{i = 1}^n \dTV{P_i^{\star}}{\widehat P}\le & \inf_{D\ge 1}\cro{ 6\inf_{P\in \overline {\mathscr{O}}(D)} \cro{\frac{1}{n} \sum_{i = 1}^n \dTV{P_i ^{\star}}{P}} + 40\sqrt{\frac{5D}{n}}} +2\sqrt{\frac{2\xi}{n}}+\frac{2\varepsilon}{n}\\
&\quad -\inf_{P\in\overline {\mathscr{M}}}\cro{\frac{1}{n} \sum_{i = 1}^n \dTV{P_i ^{\star}}{P}}.
\end{align*}
In comparison, equation \eqref{inthm_ubd_expt_dist_p_phat} and the triangle inequality imply that
\begin{align*}
\frac{1}{n} \sum_{i = 1}^n \dTV{P_i^{\star}}{\widehat P}& \le \inf_{D\ge 1}\cro{ 3\inf_{P\in \overline {\mathscr{O}}(D)}\cro{\frac{1}{n} \sum_{i = 1}^n \dTV{P_i ^{\star}}{P}}+ 20\sqrt{\frac{5D}{n}}} \\
&\quad  +\sqrt{\frac{2(\log 2 + \xi)}{n}}+\frac{\varepsilon}{n} 
\end{align*}
If we omit the term $\inf_{P\in\overline {\mathscr{M}}}\cro{\frac{1}{n} \sum_{i = 1}^n \dTV{P_i ^{\star}}{P}}$ 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\ge 1$, all the elements of $\overline {\mathcal{M}}$ are extremal with degree not larger than $D$ and \eref{Thm1_risk_bound_expecation_eq} becomes
\begin{align}
{\mathbb{E}}\cro{\dTV{P ^{\star}}{\widehat P}}\leq 3\inf_{P\in \overline {\mathscr{M}}}\dTV{P ^{\star}}{P} +48\sqrt{\frac{D}{n}} +\frac{\varepsilon}{n}.\label{Thm1_risk_bound_deviation_eq2}
\end{align}
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~\citeyearpar{MR1843146}[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}}}\dTV{P ^{\star}}{P}$. In our inequality the numerical constants are explicit. 

In the next sections, we take advantage of the stronger inequality~\eref{Thm1_risk_bound_deviation_eq} 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 {\em Lebesgue measure} on ${\mathbb{R}}$. Since $\L_{1}({\mathbb{R}},{\mathscr{B}}({\mathbb{R}}),\mu)$ is separable, Assumption~\ref{Ass00} 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. 

\section{Estimating a piecewise monotone density}\label{sect-kmono}
We denote by ${\mathcal{A}}(k)$ the class of nonempty subsets $A\subset {\mathbb{R}}$ with cardinality not larger than $k\ge 1$. The elements of $A$ provide a partition of ${\mathbb{R}}$ into $l=|A|+1\le 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.  


\subsection{Piecewise monotone densities}

\begin{df}
Let $k\ge 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$.}
\]
\end{df}
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  
\[
\map{g}{{\mathbb{R}}}{{\mathbb{R}}_{+}}{x}{{\frac{1}{\sqrt{|x|}}1\hskip-2.6pt{\rm l}_{|x|>0}}}
\]
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\ge 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\ge 1$ and $k\ge 2$.  The sets  $\overline {\mathcal{O}}_{D,k}$ with $D\ge 1$ and $k\ge 2$ are therefore nonempty. They satisfy the following property which is a consequence of Proposition~3 of Baraud and Birg\'e~\citeyearpar{MR3565484}.
\begin{prop}\label{prop-VC-monotone}
For all $D\ge 1$ and $k\ge 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)$.
\end{prop}
\begin{proof}
The proof  is postponed to Subsection \ref{subsect-proof-kmono}.
\end{proof}

For all $D\ge 1$ and $k\ge 2$, let ${\mathcal{O}}_{D,k}$ be a countable and dense subset of $\overline {\mathcal{O}}_{D,k}$ (for the $\L_{1}$-norm) and ${\mathcal{M}}_{k}$ a countable and dense subset of $\overline {\mathcal{M}}_{k}$ that contains $\bigcup_{D\ge 1}{\mathcal{O}}_{D,k}$. It follows from Proposition~\ref{prop-VC-monotone} 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\ge 1$. We immediately deduce from Theorem~\ref{shape-estimation-th} the following result. 

\begin{thm}\label{thm-monotone}
Let $k\ge 2$. Whatever the product distribution ${\mathbf{P}}^{\star}$ of the data, any TV-estimator $\widehat P$ on ${\mathscr{M}}_{k}$ satisfies 
\begin{equation}\label{eq-Thm2}
\mathbb{E}\cro{\dTV{P ^{\star}}{\widehat P}} \leq  \inf_{D\ge 1}\cro{3\inf_{P\in\overline {\mathscr{O}}_{D,k}}\dTV{P ^{\star}}{P} + 83.2\sqrt{\frac{D+k+1}{n}}}+\frac{\varepsilon}{n}.
\end{equation}
\end{thm}


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~\citeyearpar{BY-TEST} (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~\eref{eq-Thm2} as compared to Baraud's.
In particular, the constant 3 in front of the approximation term $\inf_{P\in\overline {\mathscr{O}}_{D,k}}\dTV{P ^{\star}}{P}$ 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\ge 2$, the problem of estimating a $k$-piecewise monotone density was also considered in Baraud and Birg\'e~\citeyearpar{MR3565484}. 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~\eref{eq-Thm2}, 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 {\em 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\ge 1}\cro{3\inf_{P\in\overline {\mathscr{O}}_{D,k}}\dTV{P ^{\star}}{P} + 83.2\sqrt{\frac{D+k+1}{n}}}
\]
that appear in the right-hand side of~\eref{eq-Thm2}. 

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 $3\dTV{P ^{\star}}{\overline P}+{\mathbb{B}}_{k,n}(\overline p)$ where ${\mathbb{B}}_{k,n}(p)$ is defined for a density $p$ on the line by the formulas 
\begin{align}
{\mathbb{B}}_{k,n}(p)&=\inf_{D\ge 1}\cro{3\inf_{Q\in\overline {\mathscr{O}}_{D,k}}\dTV{P}{Q} + 83.2\sqrt{\frac{D+k+1}{n}}}\nonumber\\
&=\inf_{D\ge 1}\cro{\frac{3}{2}\inf_{q\in\overline {\mathcal{O}}_{D,k}}\norm{p-q}+ 83.2\sqrt{\frac{D+k+1}{n}}}.\label{eq-defB}
\end{align}
This means that as long as $3\dTV{P ^{\star}}{\overline P}$ 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. 


\subsection{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
\begin{equation}\label{def-mbark}
p=\sum_{i=1}^{k-2}w_{i}p_{i}1\hskip-2.6pt{\rm l}_{(x_{i-1},x_{i})}
\end{equation}
where 
\begin{listi}
\item $(x_{i})_{i\in\{0,\ldots,k-2\}}$ is an increasing sequence of real numbers;
\item $w_{1},\ldots,w_{k-2}$ are nonnegative numbers such that $\sum_{i=1}^{k-2}w_{i}=1$;
\item 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.
\]
\end{listi}
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 
\begin{equation}\label{def-Rp}
\bs{R}_{k,0}(p)=\inf \cro{\sum_{i=1}^{k-2}\sqrt{w_{i}\log\pa{1+L_{i}V_{i}}}}^{2}
\end{equation}
where the infimum runs among all ways of writing $p$ under the form~\eref{def-mbark} 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 $\bs{R}_{k,0}(p)$. For $k\ge 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 $\bs{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~\eref{def-mbark} a.e.\ with  $L_{i}$ and $V_{i}$ such that $\cro{\sum_{i=1}^{k-2}\sqrt{w_{i}\log\pa{1+L_{i}V_{i}}}}^{2}<R$. The classes of sets $(\overline{\mathcal{M}}_{k}^{\infty})_{k\ge 3}$ and $(\overline{\mathcal{M}}_{k}^{\infty}(R))_{k\ge 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 \cro{\sum_{i=1}^{l-2}\sqrt{w_{i}\log\pa{1+L_{i}V_{i}}}}^{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 
\[
\bs{R}_{k,0}(p)\le \cro{\sum_{i=1}^{l-2}\sqrt{w_{i}\log\pa{1+L_{i}V_{i}}}+0}^{2}< R.
\]
It is not difficult to check that the set $\overline {\mathcal{M}}_{k}^{\infty}(R)$ is invariant under a location-scale transformation.  


\begin{thm}\label{thm-3}
Let $k\geqslant 3$ and $R>0$. If $p\in\overline {\mathcal{M}}_{k}^{\infty}(R)$,  
\begin{equation}\label{eq-thm-3}
{\mathbb{B}}_{k,n}(p)\le 41.3\pa{\frac{R}{n}}^{1/3}+83.2\sqrt{\frac{2k}{n}}.
\end{equation}
\end{thm}


This result is to our knowledge new in the literature.  We deduce that the minimax risk for the $\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\'e~\citeyearpar{MR3565484}[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\'e show that the Hellinger risk of the $\rho$-estimator is not larger than $(\sqrt{L\norm{p}_{\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\norm{p}_{\infty})/n)^{1/3}$ and only depends logarithmically on the quantity $L\norm{p}_{\infty}$ (which is not smaller than 1 since $p$ is a density).  

\begin{proof}
The proof of Theorem \ref{thm-3} is based on \eqref{eq-defB} and the following approximation result. The complete proof is postponed to subsection \ref{subsect-proof-kmono}.
\end{proof}

\begin{prop}\label{prop-birge}
Let $V\ge 0$ and $I$ be a bounded interval of length $L>0$. For all $D\ge 1$, there exists a partition ${\mathcal{J}}={\mathcal{J}}(D,L,V)$ of $I$ into $D\ge 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)\le 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
\begin{equation}\label{eq-lem-birge}
\int_{I}\ab{p-\overline p}d\mu\le \cro{(1+VL)^{1/D}-1}\wedge 2\le \frac{2\log\pa{1+VL}}{D}.
\end{equation}
\end{prop}
\begin{proof}
The proof is postponed to subsection \ref{subsect-proof-kmono}.
\end{proof}

Although the result is hidden in his calculations, Birg\'e~\citeyearpar{MR902242} 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 \eref{eq-lem-birge} 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~\ref{thm-monotone} and Theorem~\ref{thm-3}  immediately leads to the following corollary:
\begin{cor}\label{cor-monotone}
Let $k\ge 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 
\begin{equation}\label{eq-cor-mon1}
\mathbb{E}\cro{\|p-\widehat{p}\|} \leq 82.6\pa{\frac{R}{n}}^{1/3}+166.4\sqrt{\frac{2k}{n}}+\frac{2\varepsilon}{n}.
\end{equation}
\end{cor}


\subsection{Estimation of other $k$-piecewise monotone densities}
Corollary~\ref{cor-monotone} provides an upper bound on the $\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
\begin{equation}\label{eq-fondmono}
{\mathbb{B}}_{k,n}(p)\le \inf_{\overline p\in \overline {\mathcal{M}}_{k}^{\infty}}\cro{\frac{3}{2}\norm{p-\overline p}+{\mathbb{B}}_{k,n}(\overline p)},
\end{equation}
an upper bound on ${\mathbb{B}}_{k,n}(p)$ can be obtained by combining Theorem~\ref{thm-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. 

\begin{df}\label{def-conjugate}
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    
\begin{equation}\label{def-ptilde}
\widetilde p(y)=\inf\ac{x>0,\; p(a+x)< y}\ge 0.
\end{equation}
We define the $x$-{\em tail function} $\tau_{x}(p,\cdot)$ associated to $p$ as 
\[
\map{\tau_{x}(p,\cdot)}{[0,+\infty)}{{\mathbb{R}}_{+}}{t}{\dps{\int_{t}^{+\infty}p(a+x)d\mu(x)}},
\]
the $y$-{\em tail function} $\tau_{y}(p,\cdot)$ as 
\[
\map{\tau_{y}(p,\cdot)}{[0,+\infty)}{{\mathbb{R}}_{+}}{t}{\dps{\int_{t}^{+\infty}\widetilde p(y)d\mu(y)}}
\]
and the {\em tail function} $\tau(p,\cdot)$ as 
\begin{equation}\label{eq-tail}
\tau(p,t)=\inf_{s>0}\cro{\tau_{x}(p,st)+\tau_{y}(p,p(a+s))}\quad \text{for all $t\ge 1$}.
\end{equation}
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)$ .
\end{df}
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)$.
\begin{lem}\label{lem-ty}
Let $p$ be a nonincreasing density on $(a,+\infty)$ with $a\in{\mathbb{R}}$ and $\widetilde p$ the mapping defined by \eref{def-ptilde}. For all $B\ge 0$, 
\begin{equation}\label{lem-ty-eq}
\int_{0}^{+\infty}\cro{p(a+x)-B}_{+}d\mu(x)=\int_{B}^{+\infty}\widetilde p(y)d\mu(y)=\tau_{y}(p,B).
\end{equation}
\end{lem}

By changing $p$ into $x\mapsto p(-x)$, we also obtain that when $p$ is nondecreasing on $(-\infty,-a)$, 
\[
\int_{-\infty}^{0}\cro{p(-a+x)-B}_{+}d\mu(x)=\int_{B}^{+\infty}\widetilde p(y)d\mu(y)=\tau_{y}(p,B)\quad \text{for all $B\ge 0$.}
\]

\begin{proof}
Let $y>0$. Since $p$ is nonincreasing density on $(a,+\infty)$, it necessarily tends to 0 at $+\infty$. The set $I(y)=\ac{x>0,\; p(a+x)<y}$ 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)}\le 1\hskip-2.6pt{\rm l}_{p(a+x)\ge y}\le 1\hskip-2.6pt{\rm l}_{x\le \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 
\begin{align*}
&\int_{B}^{+\infty}\widetilde p(y)d\mu(y)\\
&=\int_{B}^{+\infty}\cro{\int_{0}^{+\infty}1\hskip-2.6pt{\rm l}_{x<\widetilde p(y)}d\mu(x)}d\mu(y)\le \int_{B}^{+\infty}\cro{\int_{0}^{+\infty} 1\hskip-2.6pt{\rm l}_{p(a+x)\ge y}d\mu(x)}d\mu(y)\\
&=\int_{0}^{+\infty}\cro{\int_{B}^{+\infty} 1\hskip-2.6pt{\rm l}_{p(a+x)\ge y}d\mu(y)}d\mu(x)=\int_{a}^{+\infty}\cro{p(a+x)-B}_{+}d\mu(x)\\
&\le  \int_{B}^{+\infty}\cro{\int_{0}^{+\infty} 1\hskip-2.6pt{\rm l}_{x\le \widetilde p(y)}d\mu(x)}d\mu(y)=\int_{B}^{+\infty}\widetilde p(y)d\mu(y),
\end{align*}
which proves~\eref{lem-ty-eq}.
\end{proof}

It follows from \eqref{lem-ty-eq} that if $p$ is a nonincreasing density on $(a,+\infty)$, $\tau(p,t)$ also writes for all $t\ge 1$ as 
\[
\tau(p,t)=\inf_{s>0}\cro{\int_{st}^{+\infty}p(a+x)d\mu(x)+\int_{0}^{s}\cro{p(a+x)-p(a+s)}d\mu(x)}.
\]
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\ge 2$. Changing the values of $p$, if ever necessary, on a negligible set, which will not change the way it can be approximated in $\L_{1}$-norm, we may assume with no loss of generality that it writes as 
\begin{equation}\label{eq-formp00}
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)}
\end{equation}
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~\eref{eq-formp00}, we set 
\begin{equation}\label{eq-def-tau-infty}
\tau_{\infty}(p,t)=\max_{i\in\{1,\ldots,\ell\}}\tau\pa{p_{i},t}\quad \text{for all $t\ge 1$.}
\end{equation}
The mapping $t\mapsto \tau(p,t)$ is nonincreasing on ${\mathbb{R}}_{+}$ and tends to 0 at $+\infty$. 
\begin{thm}\label{thm-monogene}
Let $\ell\ge 2$, $k\ge 2\ell$ and $R\ge \ell\log 2$. If $p$ is a density of the form~\eref{eq-formp00} a.e., 
\begin{equation}\label{thm-monogene-eq0}
\inf_{\overline p\in \overline {\mathcal{M}}_{k}^{\infty}(R)}\norm{p-\overline p}\le 2\tau_{\infty}\pa{p,\exp\pa{\frac{R}{\ell}}-1}.
\end{equation}
\end{thm}
\begin{proof}
The proof  is postponed to Subsection \ref{subsect-proof-kmono}.
\end{proof}

\noindent
By combining Theorem \ref{thm-3} and Theorem \ref{thm-monogene} we obtain the following corollary.

\begin{cor}\label{cor-monogene}
Let $\ell\ge 2$ and $k\ge 2\ell$. If $p$ is a density of the form~\eref{eq-formp00} a.e.,
\begin{equation}\label{cor-monogene-eq0}
{\mathbb{B}}_{k,n}(p)\le 44.3\pa{\frac{\ell \log(1+r_{n})}{n}}^{1/3}+83.2\sqrt{\frac{2k}{n}}
\end{equation}
where 
\begin{equation}\label{def-rn}
r_{n}=\inf\ac{t\ge 1,\; \tau_{\infty}(p,t)\le \pa{\frac{\ell \log(1+t)}{n}}^{1/3}}
\end{equation}
and $\tau_{\infty}(p,\cdot)$ is defined by~\eref{eq-def-tau-infty}. Then, the TV-estimator $\widehat p$ on ${\mathcal{M}}_{k}$ satisfies 
\begin{equation}\label{eq-cor-mon2}
\mathbb{E}\cro{\|p-\widehat{p}\|} \leq 88.6\pa{\frac{\ell \log(1+r_{n})}{n}}^{1/3}+166.4\sqrt{\frac{2k}{n}}+\frac{2\varepsilon}{n}.
\end{equation}
\end{cor}

\begin{proof}
Since $\tau_{\infty}(p,\cdot)$ tends to 0 at $+\infty$, the set 
\[
{\mathcal{R}}=\ac{t\ge 1,\; \tau_{\infty}(p,t)\le \pa{\frac{\ell \log(1+t)}{n}}^{1/3}}
\]
is nonempty,  $r_{n}$ is well-defined and for all $t>r_{n}\ge 1$, 
\[
\tau_{\infty}(p,t)\le \pa{\frac{\ell \log(1+t)}{n}}^{1/3}.
\]
Using \eref{eq-fondmono}, Theorems~\ref{thm-3} and~\ref{thm-monogene} with $R=\ell\log(1+t)>\ell \log 2$ we obtain that
\begin{align*}
{\mathbb{B}}_{k,n}(p)&\le \frac{3}{2}\inf_{\overline p\in \overline {\mathcal{M}}_{k}^{\infty}(R)}\norm{p-\overline p}+\sup_{\overline p\in \overline {\mathcal{M}}_{k}^{\infty}(R)}{\mathbb{B}}_{k,n}(\overline p)\\
&\le 3\tau_{\infty}\pa{p,t}+41.3\pa{\frac{\ell \log(1+t)}{n}}^{1/3}+83.2\sqrt{\frac{2k}{n}}\\
&\le 44.3\pa{\frac{\ell \log(1+t)}{n}}^{1/3}+83.2\sqrt{\frac{2k}{n}},
\end{align*}
and the result follows from the fact that $t$ is arbitrary in $(r_{n},+\infty)$. 
\end{proof}

\begin{exa}
Let $n\ge 2$, $\alpha\ge 0$, $\beta\ge -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}\pa{\log 2}^{1+\beta}}{x^{1+\alpha}\pa{\log x}^{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~\eref{eq-formp00} 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~\ref{def-conjugate} that when $\alpha>0$, for all $t\ge 2$  
\begin{align*}
\frac{\tau_{x}(p,t)}{c2^{1+\alpha}\pa{\log 2}^{1+\beta}}&=\int_{t}^{+\infty}\frac{dx}{x^{1+\alpha}\pa{\log x}^{1+\beta}}=\int_{\log t}^{+\infty}\frac{e^{-\alpha s}}{s^{1+\beta}}ds\le \frac{1}{\alpha t^{\alpha}\pa{\log t}^{1+\beta}},
\end{align*}
and when $\alpha=0$ and $\beta>0$
\begin{align*}
\frac{\tau_{x}(p,t)}{c2^{1+\alpha}\pa{\log 2}^{1+\beta}}&=\int_{\log t}^{+\infty}\frac{1}{s^{1+\beta}}ds= \frac{1}{\beta\pa{\log t}^{\beta}},
\end{align*}
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\ge c$.}
\]
We deduce that for all $t\ge 1$ and $s\in [2/t,2]$, $p(s)\ge p(2)=c$ and 
\begin{align*}
C^{-1}\tau_{\infty}(p,t)&\le 
\begin{cases}
\cro{{(st)^{\alpha}\pa{\log(st)}^{1+\beta}}}^{-1}+s^{\gamma}& \text{when $\alpha>0$ and $\beta\ge -1$}\\
\pa{\log(st)}^{-\beta}+s^{\gamma}& \text{when $\alpha=0$ and $\beta>0$}.
\end{cases}
\end{align*}
Taking 
\[
s=
\begin{cases}
2\cro{\pa{t^{\alpha}\pa{\frac{\log(1+t)}{\log2}}^{1+\beta}}^{-\frac{1}{\alpha+\gamma}}\vee t^{-1}}& \text{when $\alpha>0$ and $\beta\ge -1$}\\
2\cro{\pa{\frac{\log(1+t)}{\log 2}}^{-\frac{\beta}{\gamma}}\vee t^{-1}}& \text{when $\alpha=0$ and $\beta>0$}
\end{cases}
\]
the value of which belongs to $[2/t,2]$, we obtain that for all $t\ge 1$ 
\begin{align*}
C^{-1}\tau_{\infty}(p,t)&\le 
\begin{cases}
\cro{t^{\alpha}\pa{\log(1+t)}^{1+\beta}}^{-\frac{\gamma}{\alpha+ \gamma}}\vee t^{-\gamma}& \text{when $\alpha>0$ and $\beta\ge -1$}\\
\pa{\log(1+t)}^{-\beta}\vee t^{-\gamma}& \text{when $\alpha=0$ and $\beta>0$}.
\end{cases}
\end{align*}
If $\alpha>0$ and $\beta\ge -1$, by taking 
\[
t=t_{n}=C'n^{\frac{1}{3}\pa{\frac{1}{\alpha}+\frac{1}{\gamma}}}\log^{-\kappa}n\quad \text{with}\quad \kappa=\frac{1}{3}\pa{\frac{1}{\alpha}+\frac{1}{ \gamma}}+\frac{1+\beta}{\alpha}
\]
for some constant $C'>0$ large enough, we obtain that $\tau_{\infty}(p,t_{n})\le \pa{2\log(1+t_{n})/n}^{1/3}$ and consequently, $r_{n}$ defined by~\eref{def-rn} satisfies $r_{n}\le t_{n}$. Applying Corollary~\ref{cor-monogene}, we conclude that  for all $k\ge 4$ 
\[
{\mathbb{B}}_{k,n}(p)\le C\cro{\pa{\frac{\log n}{n}}^{1/3}+\sqrt{\frac{2k}{n}}}.
\]

If $\alpha=0$ and $\beta>1$, we take $t=t_{n}$ such that $\log (1+t_{n})=C'n^{1/(1+3\beta)}$ for some constant $C'>0$ large enough, we obtain that  
\begin{align*}
\tau_{\infty}(p,t_{n})\le Cn^{\frac{-\beta}{1+3\beta}}\le \pa{\frac{2\log(1+t_{n})}{n}}^{1/3},
\end{align*}
hence $r_{n}\le t_{n}=C'n^{1/(1+3\beta)}$ and we get that for all $k\ge 4$
\[
{\mathbb{B}}_{k,n}(p)\le C\cro{n^{\frac{-\beta}{1+3\beta}}+\sqrt{\frac{2k}{n}}}.
\]
\end{exa}


\section{Convex-concave densities}\label{sect-cvxcve}

\subsection{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.

\begin{df} \label{def_cvx_cve}
A function $g$ is said to be convex-concave on an interval $I$ if it is either convex or concave on $I$. For $k\geq 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$}.
\]
\end{df}
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',g_r'$ respectively. More generally, when a function $f$ is continuous and convex-concave on a nontrivial bounded interval $[a,b]$, we define 
\[
f'_{r}(z)=\lim_{x\downarrow z}\frac{f(x)-f(z)}{x-z}\quad \text{for all $z\in [a,b)$}
\]
and 
\[
f'_{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'_{r}(a)$ and $f'_{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 \geq 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$.
\begin{prop} \label{prop_extr_cvx_cve}
Let $k\ge 2$, $D\ge 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)$.
\end{prop}

\begin{proof}
The proof is postponed to Subsection \ref{subsect-proof-cvxcve}.
\end{proof}

For all $D\geq 1$, $k\geq 2$, let ${\mathcal{O}}_{D,k}^1$ be a countable and dense subset of $\overline{\mathcal{O}}_{D,k}^1$ (for the $\L_1$-norm) and ${\mathcal{M}}_k^1$ a countable and dense subset of $\overline{{\mathcal{M}}}_k^1$ that contains $\bigcup_{D \geq 1} \mathcal{O}_{D,k}^1$.
By proposition~\ref{prop-VC-monotone}, 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 \geq 1$. We deduce from Theorem \ref{shape-estimation-th} the following result.
\begin{thm}\label{thm_or_ineq_cvx_cve}
Let $k\ge 2$. Whatever the product distribution ${\mathbf{P}}^{\star}$ of the data, any TV-estimator $\widehat P$ on ${\mathscr{M}}_{k}^{1}$ satisfies 
\begin{equation} \label{or-ineq_cvx_cve_extr_pts}
    {\mathbb{E}} \left[ \dTV{P^{\star}}{\hat{P}} \right] \leq \inf_{D \geq 1} \left\{ 3 \inf_{P \in \overline{{\mathscr{O}}}_{D,k}^1} \dTV{P^{\star}}{P} + 68 \sqrt{\frac{D+2k-1}{n}} \right\} + \frac{\varepsilon}{n}.
\end{equation}
\end{thm}

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~\eref{or-ineq_cvx_cve_extr_pts} writes as ${\mathbb{B}}_{k,n}^{1}(p)+{\varepsilon}/n$ with 
\begin{equation}\label{def-b1kn}
{\mathbb{B}}_{k,n}^1(p) = \inf_{D \geq 1} \left[ \frac{3}{2} \inf_{q \in \overline{{\mathcal{O}}}_{D,k}^1} \norm{p - q} + 68 \sqrt{\frac{D + 2k -1}{n}} \right]. 
\end{equation}
As we did in Section~\ref{sect-kmono}, our aim is to bound the quantity ${\mathbb{B}}_{k,n}^1(p)$ under some suitable additional assumptions on the density $p$. 

\subsection{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 {\em 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. 
\begin{df}\label{def-linear}
Let $D\ge 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\}$. 
\end{df}

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\ge f$ (respectively $\overline f\le 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}\pa{\frac{|p_{r}'(a)|\wedge |p_{l}'(b)|}{|\Delta|}+\frac{|\Delta|}{|p_{r}'(a)|\vee |p_{l}'(b)|}},
\]
with the conventions $0/0=1$ and $1/(+\infty)=0$. Since $f$ is convex-concave, monotone and continuous 
\[
|p_{r}'(a)|\wedge |p_{l}'(b)|\le |\Delta| \le |p_{r}'(a)|\vee |p_{l}'(b)| \quad \text{and}\quad 
\]
and 
\[
\Delta=0\implies |p_{r}'(a)|= |p_{l}'(b)|=0.
\]
With our conventions, $\Gamma$ is well-defined and belongs to $[0,1]$. When $f$ is affine, $\Delta=p_{r}'(a)=p_{l}'(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$. 

\begin{thm}\label{thm-approx-conv}
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\ge 1$, there exists a $2D$-linear interpolation $\overline p$ of $p$ such that 
\begin{equation}\label{eq-thm-approx-conv}
\int_{a}^{b}\ab{p-\overline p}d\mu\le \frac{4}{3}\cro{\pa{1+\sqrt{2LV\Gamma}}^{1/D}-1}^{2}.
\end{equation}
In particular, there exists a continuous convex-concave piecewise linear density $q$ based on a partition of $[a,b]$ into $2D$ intervals that satisfies
\begin{equation}\label{thm-approx-conv-01}
\int_{a}^{b}\ab{p-q}d\mu\le  5.14\frac{\log^{2}\pa{1+\sqrt{2LV\Gamma}}}{D^{2}}.
\end{equation}
\end{thm}

Since $\Gamma\in [0,1]$, \eref{thm-approx-conv-01} implies that 
\[
\int_{a}^{b}\ab{p-q}d\mu\le  5.14\frac{\log^{2}\pa{1+\sqrt{2LV}}}{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}\ab{p-\overline p}d\mu=\int_{a}^{b}\ab{p-q}d\mu=0$.

The fact that a bounded convex (or concave) function on a compact interval can be approximated in $\L_1$ by piecewise affine functions at rate $\mathcal{O}(1/D^2)$ had already been established by \cite{Guerin2006}. What is novel in Theorem \ref{thm-approx-conv} is the fact that for probability densities the approximation error depends logarithmically on the product $LV$. 

\begin{proof}
The proof is based on several preliminary approximation results whose statements and proofs are postponed to Subsection \ref{subsect-proof-cvxcve}.
\end{proof}

\subsection{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\ge 3$, that is of the form
\begin{equation}\label{def-mbark2}
p=\sum_{i=1}^{k-2}w_{i}p_{i}1\hskip-2.6pt{\rm l}_{(x_{i-1},x_{i})}
\end{equation}
where 
\begin{listi}
\item $(x_{i})_{i\in\{0,\ldots,k-2\}}$ is an increasing sequence of real numbers;
\item $w_{1},\ldots,w_{k-2}$ are nonnegative numbers such that $\sum_{i=1}^{k-2}w_{i}=1$;
\item 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}=\ab{p_{i}(x_{i-1})-p(x_{i})}<+\infty$ and linear index $\Gamma_{i}\in [0,1]$. 
\end{listi}
For a density $p$ satisfying~\eref{def-mbark2} we define 
\begin{equation}\label{def-Rp1}
\bs{R}_{k,1}(p)=\inf\cro{\sum_{i=1}^{k-2}\pa{w_{i}\log^{2}\pa{1+\sqrt{2L_{i}V_{i}\Gamma_{i}}}}^{1/3}}^{3/2},
\end{equation}
where the infimum runs among all ways of writing $p$ under the form~\eref{def-mbark2}. We denote by $\overline {\mathcal{M}}_{k,1}^{\infty}$ the class of all densities of the form ~\eref{def-mbark2} a.e.\ and for $R>0$, $\overline {\mathcal{M}}_{k,1}^{\infty}(R)$ the subset of those which satisfy $\bs{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. 
\begin{thm} \label{thm_cvx_cve}
Let $k\ge 3$ and $R>0$. For all $p\in  \overline {\mathcal{M}}_{k,1}^{\infty}(R)$
\begin{equation}\label{eq-cvx_cve}
{\mathbb{B}}_{k,n}^1(p) \le  7.71\cro{15.06\pa{\frac{R}{n}}^{2/5}+8.82\sqrt{\frac{4k-5}{n}}},
\end{equation}
where ${\mathbb{B}}_{k,n}^1(p)$ is defined by~\eref{def-b1kn}.
\end{thm}
Theorem \ref{thm_cvx_cve} implies, together with Theorem \ref{thm_or_ineq_cvx_cve}, 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~\citeyearpar{MR1843146}[Section~15.5]  for bounded convex densities. This rate is therefore optimal.

To the best of our knowledge, Theorem \ref{thm-log-concave} 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, \cite{Gao2009} 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\le 1$, hence $\bs{R}_{3,1}(p)\le  \log(1+\sqrt{2L|p(a)-p(b)|})\le \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}\le 2^{2/3}$ which holds for all $z\in [0,1]$, we obtain that
\begin{align*}
\bs{R}_{4,1}^{2/3}(p)&\le \pa{w_{1}\log^{2}(1+\sqrt{2(c-a)\pa{p_{1}(c)-p_{1}(a)}}}^{1/3}\\
&\quad + \pa{w_{2}\log^{2}(1+\sqrt{2(b-c)\pa{p_{2}(c)-p_{2}(b)}}}^{1/3}\\
&\le \pa{w_{1}^{1/3}+w_{2}^{1/3}}(\log 3)^{2/3}\le (2\log 3)^{2/3}.
\end{align*}
We immediately deduce from Theorems~\ref{thm_or_ineq_cvx_cve} and~\ref{thm_cvx_cve} the following corollary.  
\begin{cor}\label{cor-cvx_cve}
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}}\cro{\norm{p-\widehat p}}\le \frac{320}{n^{2/5}}+\frac{451}{\sqrt{n}}+\frac{2{\varepsilon}}{n}.
\]
In particular,
\[
\adjustlimits\inf_{\widetilde p}\sup_{p}{\mathbb{E}}\cro{\norm{p-\widetilde p}}\le \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$.
\end{cor}

\begin{proof}[Proof of Theorem~\ref{thm_cvx_cve}]
Let $p\in\overline {\mathcal{M}}_{k,1}^{\infty}(R)$. With no loss of generality we may assume that $p$ is of the form \eref{def-mbark2} everywhere and choose a subdivision $(x_{i})_{i\in\{0,\ldots,k-2\}}$ in such a way that 
\[
\cro{\sum_{i=1}^{k-2}\pa{w_{i}\log^{2}\pa{1+\sqrt{2L_{i}V_{i}\Gamma_{i}}}}^{1/3}}^{3/2}\le R.
\]

Let $D\ge 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}\le D$. By Theorem~\ref{thm-approx-conv}, 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}}\ab{p_{i}-q_{i}}d\mu\le  5.14\frac{\log^{2}\pa{1+\sqrt{2L_{i}V_{i}\Gamma_{i}}}}{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}\le 2D$ intervals.  It therefore belongs to $\overline {\mathcal{O}}_{2D,k}$. Besides,
\begin{align*}
\norm{p-q}&\le \sum_{i=1}^{k-2}w_{i}\int_{x_{i-1}}^{x_{i}}\ab{p_{i}-q_{i}}d\mu\le 5.14\sum_{i=1}^{k-2}\frac{w_{i}\log^{2}\pa{1+\sqrt{2L_{i}V_{i}\Gamma_{i}}}}{D_{i}^{2}}
\end{align*}
and it follows from~\eref{def-b1kn} that
\begin{align*}
{\mathbb{B}}_{k,n}^1(p) &\le \frac{3}{2} \inf_{q \in \overline{{\mathcal{O}}}_{2D,k}^1} \norm{p - q} + 68 \sqrt{\frac{2D + 2k -1}{n}}\\
&\le 7.71\sum_{i=1}^{k-2}\frac{w_{i}\log^{2}\pa{1+\sqrt{2L_{i}V_{i}\Gamma_{i}}}}{D_{i}^{2}}+68 \sqrt{\frac{2D + 2k -1}{n}}. 
\end{align*}
Let us set $c=68/7.71$, $s_{0}=[nR^{4}/(2c^{2})]^{1/5}$, 
\[
s_{i}=\cro{w_{i}\log^{2}\pa{1+\sqrt{2L_{i}V_{i}\Gamma_{i}}}}^{1/3}\quad \text{for all $i\in\{1,\ldots,k-2\}$}
\]
and choose $D=s_{0}+k-2$ and 
\[
D_{i}=\PES{\frac{s_{0}s_{i}}{\sum_{j=1}^{k-2}s_{j}}}\ge \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}\le D$. Then, 
\begin{align*}
{\mathbb{B}}_{k,n}^1(p) &\le 7.71\cro{\sum_{i=1}^{k-2}\frac{s_{i}^{3}}{D_{i}^{2}}+c \sqrt{\frac{2D + 2k -1}{n}}}\\
&\le  7.71\cro{\frac{\pa{\sum_{j=1}^{k-2}s_{j}}^{3}}{s_{0}^{2}}+c \sqrt{\frac{2s_{0}+4k-5}{n}}}\\
&\le 7.71\cro{\frac{R^{2}}{s_{0}^{2}}+c \sqrt{\frac{2s_{0}}{n}}+c\frac{\sqrt{4k-5}}{n}}\\
&=7.71\cro{2(2c^{2})^{2/5}\frac{R^{2/5}}{n^{2/5}}+c\frac{\sqrt{4k-5}}{n}}
\end{align*}
which gives \eref{eq-cvx_cve}. 
\end{proof}


\section{Log-concave densities}\label{sect-logcc}
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\ge 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}}$.
\begin{prop}\label{prop_extr_log_cve}
Let $D\ge 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)$.
\end{prop}
\begin{proof}
The proof is postponed to Subsection \ref{subsect-proof-logcc}.
\end{proof}

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 $\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 \ref{shape-estimation-th} together with Proposition \ref{prop_extr_log_cve} the following result. 
\begin{thm}\label{thm-log-concave}
Whatever the product distribution ${\mathbf{P}}^{\star}$ of the data, any TV-estimator $\widehat P$ on ${\mathscr{M}}^{\text{LC}}$ satisfies 
\begin{equation}\label{eq-Thm-log-concave}
\mathbb{E}\cro{\dTV{P ^{\star}}{\widehat P}} \leq  \inf_{D\ge 1}\cro{3\inf_{P\in\overline {\mathscr{O}}_{D}^{\text{LC}}}\dTV{P ^{\star}}{P} + 48\sqrt{2}\sqrt{\frac{D+2}{n}}}+\frac{\varepsilon}{n}.
\end{equation}
\end{thm}
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~\eref{eq-Thm-log-concave} writes as ${\mathbb{B}}_{n}(p)+{\varepsilon}/n$ with
\begin{align}
{\mathbb{B}}_n(p)
&=\inf_{D\ge 1}\cro{\frac{3}{2}\inf_{q\in\overline {\mathcal{O}}_{D}^{\text{LC}}}\norm{p-q} + 48\sqrt{2}\sqrt{\frac{D+2}{n}}}\label{def-Blc}
\end{align}
In particular, if $p$ belongs to $\overline {\mathcal{O}}_{D}^{\text{LC}}$ for some $D \ge 1$, then ${\mathbb{B}}_n(p) \leq \sqrt{D/n}$, so that $\hat{p}$ converges at the parametric rate. Thus, the TV-estimator shares the \emph{adaptivity} property established for the MLE by Kim et al~\citeyearpar{MR3845018} (and \cite{Feng2021}), and by Baraud and Birg\'e~\citeyearpar{MR3565484} 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\'e's results are established for the Hellinger distance and these logarithmic factors are sometimes necessary for such a loss. 

As we did in Sections~\ref{sect-kmono} and ~\ref{sect-cvxcve} , our aim is now to bound the quantity ${\mathbb{B}}_{n}(p)$. This can be done by using the following approximation result.
\begin{prop}\label{prop_log_cve_approx}
Let $D\ge 6$. For all log-concave densities $p$, 
\[
\inf_{q\in\overline {\mathcal{O}}^{\text{LC}}_{6D}}\norm{p-q}\le \frac{2}{D^{2}}.
\]
\end{prop}
\begin{proof}
The proof  is postponed to Subsection \ref{subsect-proof-logcc}.
\end{proof}

Combining \eref{def-Blc} with Proposition \ref{prop_log_cve_approx}, we deduce that  for all $D\ge 6$
\begin{align*}
{\mathbb{B}}_n(p)
&=\inf_{D\ge 6}\cro{\frac{3}{2}\inf_{q\in\overline {\mathcal{O}}_{6D}^{\text{LC}}}\norm{p-q} + 48\sqrt{2}\sqrt{\frac{6D+2}{n}}}\\
&\le \inf_{D\ge 6}\cro{\frac{3}{D^{2}} + 48\sqrt{2}\sqrt{\frac{6D+2}{n}}}.
\end{align*}
By choosing
\[
D=\PES{\pa{\frac{3n}{96^{2}}}^{1/5}}\vee 6\le \pa{\frac{6n}{2\times 96^{2}}}^{1/5}+6,
\]
we obtain the following estimation result for log-concave densities.

\begin{cor}
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 
\begin{equation*}
{\mathbb{E}}\cro{\norm{p-\widehat p}} \le \frac{300}{n^{2/5}}+\frac{837}{\sqrt{n}}+\frac{2\varepsilon}{n}.
\end{equation*}
\end{cor}


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  \cite{Kim2016}. 

\subsection*{Acknowledgement} {One of the authors thanks Lutz D\"umbgen 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~\ref{shape-estimation-th}}.

\section{Proofs}\label{sect-7}

\subsection{Technical result}\label{subsect-7.1}

 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.  

\begin{lem} \label{lem_l1_proj}
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 f d\nu}\right| d\nu \leq 2 \cro{1\wedge \int_E |p - f| d\nu}. 
\]
\end{lem}
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. 

\begin{proof}
The fact that 
\[
\int_E \left|p- \frac{f}{\int_E f d\nu}\right|d\nu\le 2
\]
comes from the triangle inequality. Let us now prove that 
\[
\int_E \left|p- \frac{f}{\int_E f d\nu}\right| d\nu \leq 2 \int_E |p - f| d\nu.
\]
We first assume that $c = \int_{E} f d\nu\in (0,1]$. Since $f/c$ and $p$ are two densities, 
\begin{align*}
\int_E \left|\frac{f}{c} - p \right| d\nu &= 2 \int_I \left[ p - \frac{f}{c} \right] 1\hskip-2.6pt{\rm l}_{\{c p \geq f\}} d\nu \leq 2 \int_E [p - f] 1\hskip-2.6pt{\rm l}_{\{c p \geq f\}} d\nu \\
&\leq 2 \int_E |p - f| d\nu. 
\end{align*}
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
\begin{align*}
\int_E \left| \frac{f}{c} - p \right|d\nu 
&\leq 2 \int_E \left|\frac{f}{c} - \frac{p}{c} \right| d\nu=\frac{2}{c}\int_I |f - p| d\nu \leq 2 \int_E|f - p| d\nu.
\end{align*}
\end{proof}

\subsection{Proofs of Section \ref{sec-ell-estimator}}\label{subsect-proof-ell-estimator}

\begin{proof}[Proof of Theorem \ref{shape-estimation-th}]
Let $D\ge 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\ge 0$, we set 
\begin{align*}
{\mathbf{Z}}_+({\bs{X}},P)&=\sup_{Q\in{\mathscr{M}}}\cro{{\mathbf{T}}({\bs{X}},P,Q)-{\mathbb{E}}\cro{{\mathbf{T}}({\bs{X}},P, Q)}}-\zeta\\
{\mathbf{Z}}_{-}({\bs{X}},P)&=\sup_{Q\in{\mathscr{M}}}\cro{{\mathbb{E}}\cro{{\mathbf{T}}({\bs{X}},Q,P)}-{\mathbf{T}}({\bs{X}},Q,P)}-\zeta
\end{align*}
and 
\[
{\mathbf{Z}}({\bs{X}},P)={\mathbf{Z}}_+({\bs{X}},P)\vee{\mathbf{Z}}_{-}({\bs{X}},P).
\]
Applying the first inequality of \eqref{bound_test_TV_eq} with $P=Q$ and $Q=\overline{P}$, we infer that for all $Q\in{\mathscr{M}}$, 
\begin{align*}
n\dTV{\overline{P}}{Q} 
&\leq n\dTV{P ^{\star}}{\overline{P}}+{\mathbb{E}}\cro{{\mathbf{T}}({\bs{X}},Q,\overline P)}\\
&=n\dTV{P ^{\star}}{\overline{P}}+{\mathbb{E}}\cro{{\mathbf{T}}({\bs{X}},Q,\overline P)}-{\mathbf{T}}({\bs{X}},Q,\overline P)+{\mathbf{T}}({\bs{X}},Q,\overline P)\\
&\leq n\dTV{P ^{\star}}{\overline{P}}+{\mathbf{Z}}({\bs{X}},\overline P)+{\mathbf{T}}({\bs{X}},Q,\overline P)+\zeta\\
&\leq n\dTV{P ^{\star}}{\overline{P}}+{\mathbf{Z}}({\bs{X}},\overline P)+{\mathbf{T}}({\bs{X}},Q)+\zeta.
\end{align*}
In particular, the inequality applies to $Q=\widehat P\in {\mathscr{E}}({\bs{X}})$ and using the fact that 
\[
{\mathbf{T}}({\bs{X}},\widehat P)\leq \inf_{P \in{\mathscr{M}}}{\mathbf{T}}({\bs{X}},P)+\varepsilon \leq {\mathbf{T}}({\bs{X}},\overline P)+\varepsilon,
\]
we deduce that 
\begin{align}
n\dTV{\overline{P}}{\widehat P}&\leq n\dTV{P ^{\star}}{\overline{P}}+{\mathbf{Z}}({\bs{X}},\overline P)+{\mathbf{T}}({\bs{X}},\overline P)+\zeta+\varepsilon.\label{eq-fond00}
\end{align}
Using now the second inequality of \eqref{bound_test_TV_eq} with $P=\overline P$, we  obtain that
\begin{align*}
{\mathbf{T}}({\bs{X}},\overline P)&=\sup_{Q\in{\mathscr{M}}}{\mathbf{T}}({\bs{X}},\overline P,Q)\\
&\leq \sup_{Q\in{\mathscr{M}}}\cro{{\mathbf{T}}({\bs{X}},\overline P,Q)-{\mathbb{E}}\cro{{\mathbf{T}}({\bs{X}},\overline P,Q)}-\zeta}+\sup_{Q\in{\mathscr{M}}}{\mathbb{E}}\cro{{\mathbf{T}}({\bs{X}},\overline P,Q)}+\zeta\\
&\leq {\mathbf{Z}}({\bs{X}},\overline P)+n\dTV{P ^{\star}}{\overline{P}}+\zeta,
\end{align*}
which with~\eref{eq-fond00} lead to 
\begin{equation}\label{eq-fond01}
n\dTV{\overline{P}}{\widehat P}\leq 2n\dTV{P ^{\star}}{\overline{P}} + 2\zeta+\varepsilon+2{\mathbf{Z}}({\bs{X}},\overline P).
\end{equation}
Let us now bound from above ${\mathbf{Z}}({\bs{X}},\overline P)$. We set for $P\in{\mathscr{M}}$
\begin{align*}
{\mathbf{w}}(P)&={\mathbb{E}}\cro{\sup_{Q\in{\mathscr{M}}}\cro{{\mathbf{T}}({\bs{X}},P,Q)-{\mathbb{E}}\cro{{\mathbf{T}}({\bs{X}},P, Q)}}}\\
&\quad \vee {\mathbb{E}}\cro{\sup_{Q\in{\mathscr{M}}}\cro{{\mathbb{E}}\cro{{\mathbf{T}}({\bs{X}},Q, P)}-{\mathbf{T}}({\bs{X}},Q,P)}}.
\end{align*}
The functions $t_{(\overline P,Q)}$ satisfy $|t_{(\overline P,Q)}(x)-t_{(\overline P,Q)}(x')|\le 1$ for all $Q\in{\mathscr{M}}$ and $x,x'\in E$, hence 
\[
\ab{{\mathbf{Z}}_{+}((x_{1},\ldots,x_{i},\ldots,x_{n}),\overline P)-{\mathbf{Z}}_{+}((x_{1},\ldots,x_{i}',\ldots,x_{n}),\overline P)}\leq 1
\]
for all ${\mathbf{x}}\in{\mathbf{E}}$, $x_{i}'\in E$ and $i\in\{1,\ldots,n\}$.  Following the same lines as in the proof of Lemma 2 of Baraud~\citeyearpar{BY-TEST} (with $\xi +\log 2$ in place of $\xi$), we deduce that with a probability at least $1-(1/2)e^{-\xi}$, 
\begin{align}
{\mathbf{Z}}_{+}({\bs{X}},\overline P)&\le {\mathbb{E}}\cro{{\mathbf{Z}}_{+}({\bs{X}},\overline P)}+\sqrt{\frac{n(\xi +\log 2)}{2}}\\
&={\mathbb{E}}\cro{\sup_{Q\in{\mathscr{M}}}\cro{{\mathbf{T}}({\bs{X}},\overline P,Q)-{\mathbb{E}}\cro{{\mathbf{T}}({\bs{X}},\overline P, Q)}}}+\sqrt{\frac{n(\xi +\log 2)}{2}}-\zeta\nonumber\\
&\le {\mathbf{w}}(\overline P)+\sqrt{\frac{n(\xi +\log 2)}{2}}-\zeta.\label{eq-thm1-007}
\end{align}
Arguing similarly, with a probability at least $1-(1/2)e^{-\xi}$, 
\begin{align}
{\mathbf{Z}}_{-}({\bs{X}},\overline P)&\le {\mathbf{w}}(\overline P)+\sqrt{\frac{n(\xi +\log 2)}{2}}-\zeta.\label{eq-thm1-007b}
\end{align}
Putting \eref{eq-thm1-007} and \eref{eq-thm1-007b} 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}}({\bs{X}},\overline P)={\mathbf{Z}}_+({\bs{X}},P)\vee{\mathbf{Z}}_{-}({\bs{X}},P)\le {\mathbf{w}}(\overline P)+\sqrt{\frac{n(\xi +\log 2)}{2}}-\zeta\le 0
\]
which with \eref{eq-fond01} lead to the bound
\begin{equation}\label{eq-thm1-final}
\dTV{\overline{P}}{\widehat P}\leq 2\dTV{P ^{\star}}{\overline{P}} + \frac{2{\mathbf{w}}(\overline P)}{n}+\sqrt{\frac{2(\xi +\log 2)}{n}}+\frac{\varepsilon}{n}.
\end{equation}
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 $\ac{\{q<\overline p\},\; q\in{\mathcal{M}}\setminus\{\overline p\}}$ and $\ac{\{q>\overline p\},\; q\in{\mathcal{M}}\setminus\{\overline p\}}$ are both VC with dimensions not larger than $D$. We may therefore apply Proposition 3.1 in Baraud~\citeyearpar{Bar2016} with $\sigma=1$ and get 
\begin{align}
{\mathbb{E}}\cro{\sup_{q\in{\mathcal{M}}\setminus\{\overline p\}}\ab{ \sum_{i=1}^{n}\pa{1\hskip-2.6pt{\rm l}_{\overline p>q}(X_{i})-P_i^{\star}(\overline p>q)}}}
&\leq 10\sqrt{5nD},\label{eq-Besup00}
\end{align}
and 
\begin{align}
{\mathbb{E}}\cro{\sup_{q\in{\mathcal{M}}\setminus\{\overline p\}}\ab{ \sum_{i=1}^{n}\pa{1\hskip-2.6pt{\rm l}_{\overline p<q}(X_{i})-P_i^{\star}(\overline p<q)}}}
&\leq 10\sqrt{5nD}.\label{eq-Besup01}
\end{align}
These inequalities entail ${\mathbf{w}}(\overline P)\leq 10\sqrt{5nD}$, and we infer from~\eref{eq-thm1-final} that 
\begin{equation} \label{eq_ubd_dist_pbar_phat}
  \dTV{\overline{P}}{\widehat P} \leq 2\dTV{P ^{\star}}{\overline{P}} + 20\sqrt{\frac{5D}{n}}+\sqrt{\frac{2(\xi +\log 2)}{n}}+\frac{\varepsilon}{n}.  
\end{equation}
Since $\overline P$ is arbitrary in the set ${\mathscr{O}}(D)$ which is dense on $\overline {\mathscr{O}}(D)$, we infer that equation \eqref{eq_ubd_dist_pbar_phat} holds for all $\overline P \in \overline {\mathscr{O}}(D)$, which yields \eqref{inthm_ubd_dist_p_phat}.
Hence, by the triangle inequality,
\begin{align*}
  \dTV{P ^{\star}}{\widehat P}  &\leq \inf_{P\in\overline {\mathscr{O}}(D)} \left\{ \dTV{P ^{\star}}{P} +  \dTV{P}{\widehat P} \right\} \\
  &\leq 3\inf_{P\in\overline {\mathscr{O}}(D)}\dTV{P ^{\star}}{P} + 20\sqrt{\frac{5D}{n}}+\sqrt{\frac{2(\xi +\log 2)}{n}}+\frac{\varepsilon}{n}.
\end{align*}
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 \eref{Thm1_risk_bound_deviation_eq}. Inequality \eref{Thm1_risk_bound_expecation_eq} follows by integrating this deviation bound with respect to $\xi$. 
\end{proof}


\subsection{Proofs of Section \ref{sect-kmono}}\label{subsect-proof-kmono}

\begin{proof}[Proof of Proposition \ref{prop-birge}]
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$, 
\begin{equation}\label{eq-lem-lulu}
\int_{J}\ab{p-\overline p_{J}}d\mu\le \frac{(v-u)(p(u)-p(v))}{2}.
\end{equation}
In particular, when $D=1$ it suffices to take ${\mathcal{J}}=\{I\}$ and the result follows from \eref{eq-lem-lulu} with $u=a$ and $v=b$ and the trivial inequality $\int_{I}|p-\overline p_{J}|d\mu\le 2$. It remains to prove the result for  $D\ge 2$ and since \eref{eq-lem-birge} 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 \eref{eq-lem-lulu} 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 
\begin{align*}
\int_{I}\ab{p-\overline p}d\mu&=\sum_{J\in{\mathcal{J}}}\int_{J}\ab{p-\overline p_{J}}d\mu\le \frac{1}{2}\sum_{j=1}^{D}(x_{j}-x_{j-1})[p(x_{j-1})-p(x_{j})]\\
&=\frac{1}{2}\cro{p(x_{0})(x_{1}-x_{0})+\sum_{j=1}^{D-1}p(x_{j})\cro{(x_{j+1}-x_{j})-(x_{j}-x_{j-1})}}\\
&\quad -\frac{p(x_{D})(x_{D}-x_{D-1})}{2}\\
&\le \frac{1}{2}\cro{V_{I}(p)(x_{1}-x_{0})+\eta\sum_{j=1}^{D-1}p(x_{j})(x_{j}-x_{j-1})}\\
&\quad +\frac{p(x_{D})\cro{(x_{1}-x_{0})-(x_{D}-x_{D-1})}}{2}\\
&\le  \frac{1}{2}\cro{V(x_{1}-x_{0})+\eta\sum_{j=1}^{D-1}\int_{x_{j-1}}^{x_{j}}pd\mu}\le \frac{1}{2}\cro{V(x_{1}-x_{0})+\eta}=\eta.
\end{align*}
Together with the trivial bound $\int_{I}\ab{p-\overline p}d\mu\le 2$, this last inequality leads to \eref{eq-lem-birge}. The second inequality derives from the fact that $(e^{x}-1)\wedge 2\le 2x/\log 3\le 2x$ for all $x\ge 0$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm-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~\eref{def-mbark} with 
\[
\cro{\sum_{i=1}^{k-2}\sqrt{w_{i}\log\pa{1+L_{i}V_{i}}}}^{2}\le R.
\]
Applying Proposition~\ref{prop-birge} 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}\ge 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}}\ab{p_{i}-\overline p_{i}}d\mu\le \frac{2S_{i}}{D_{i}}\quad \text{with}\quad S_{i}=\log\pa{1+V_{i}L_{i}}.
\]
Let us now take $D_{i}=\PES{D\sqrt{w_{i}S_{i}}/(\sum_{i=1}^{k-2}\sqrt{w_{i}S_{i}})}\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\le D_{i}\le \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 
\begin{align*}
\norm{p-\overline p}&\le \sum_{i=1}^{k-2}w_{i}\int_{I_{i}}\ab{p_{i}-\overline p_{i}}d\mu\le  \sum_{i=1}^{k-2}\frac{2w_{i}S_{i}}{D_{i}}\le \frac{2}{D}\pa{\sum_{i=1}^{k-2}\sqrt{w_{i}S_{i}}}^{2}\le \frac{2R}{D}.
\end{align*}
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}\le D+k-2$ bounded intervals. It therefore belongs to $\overline {\mathcal{O}}_{D+k-2,k}$. Finally, let us choose 
\[
D=\PES{\pa{\frac{9R^{2}n}{83.2^2}}^{1/3}}\le \pa{\frac{9R^{2}n}{83.2^2}}^{1/3}+1. 
\]
Using the sub-additivity property of the square root, we deduce from~\eref{eq-defB} that 
\begin{align*}
{\mathbb{B}}_{k,n}(p)&\le \frac{3R}{2D}+83.2\sqrt{\frac{D-1+2k}{n}}\\
&\le \frac{3^{1/3}\times 83.2^{2/3}}{2}\pa{\frac{R}{n}}^{1/3}+\frac{83.2}{\sqrt{n}}\sqrt{\pa{\frac{9nR^{2}}{83.2^{2}}}^{1/3}+2k}\\
&\le \cro{\frac{3^{1/3}\times 83.2^{2/3}}{2}+ 3^{1/3}\times83.2^{2/3}}\pa{\frac{R}{n}}^{1/3}+83.2\sqrt{\frac{2k}{n}},
\end{align*}
which is~\eref{eq-thm-3}.  
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm-monogene}]
Let us start with the following lemma where we show that the mapping $\tau(p,\cdot)$ controls the $\L_{1}$-approximation error of a monotone density $p$ by the elements of the class $\overline {\mathcal{M}}_{3}^{\infty}(R)$. 
\begin{lem}\label{lem-tronc}
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, 

\begin{equation}\label{lem-tronc-eq1}
\norm{p-p_{| I}^{\wedge B}}\le 2 \cro{\int_{I}\pa{p-B}_{+}d\mu+\int_{I^{c}}pd\mu}.
\end{equation}
If $p$ is a monotone density on a half-line
\begin{equation}\label{lem-tronc-eq2}
\inf_{\overline p\in\overline {\mathcal{M}}_{3}^{\infty}(R)}\norm{p-\overline p}\le 2\tau\pa{p,\exp(R)-1}\quad \text{for all $R\ge \log 2$.}
\end{equation}
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)$.
\end{lem}

\begin{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~\ref{lem_l1_proj}, 
\begin{align*}
\int_{{\mathbb{R}}}\ab{p-p_{| I}^{\wedge B}}d\mu&\le 2\int_{{\mathbb{R}}}\ab{p-(p\wedge B)1\hskip-2.6pt{\rm l}_{I}}d\mu\\
&= 2 \int_{I^{c}}pd\mu+2 \int_{I}\pa{p-B}_{+}d\mu.
\end{align*}
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\ge 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)\ge p(a+s)=B$ for all $x\in (a,a+s)\subset I$ and consequently
\[
\int_{I}(p\wedge B)d\mu\ge \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~\eref{def-Rp} that
\begin{align*}
\bs{R}_{k,0}(\overline p_{s})< \log\pa{1+\frac{tsB}{\int_{I}(p\wedge B)d\mu}}\le  \log(1+t)=R
\end{align*}
and consequently, $\overline p_{s}\in \overline {\mathcal{M}}_{3}^{\infty}(R)$. Applying~\eref{lem-tronc-eq1} and Lemma~\ref{lem-ty}, we obtain that for all $s>0$
\begin{equation}\label{eq-infs2}
\inf_{\overline p\in \overline {\mathcal{M}}_{3}^{\infty}(R)}\norm{p-\overline p}\le \norm{p-\overline p_{s}}\le 2\cro{\tau_{x}(p,st)+\tau_{y}\pa{p,p(a+s)}}
\end{equation}
and we derive~\eref{lem-tronc-eq2} from~\eref{eq-tail}. 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\le 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)}\norm{p-\overline p}\le 2\cro{\tau_{x}(p,st)+\tau_{y}\pa{p,p(a+s)}}\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}\le s'$, 
\[
\tau_{y}\pa{p,p(a+s)}\le \tau_{y}\pa{p,p(a+s_{0})}\le \tau_{y}\pa{p,p(a+s')},
\]
and since the mapping $u\mapsto \tau_{x}(p,u)$ is continuous and nonincreasing,  for all $s'\ge s_{0}$ 
\begin{align*}
&\inf_{s\in (0,s_{0})}\cro{\tau_{x}(p,st)+\tau_{y}\pa{p,p(a+s)}}\\
& \le \inf_{s\in (0,s_{0})}\tau_{x}(p,st)+\tau_{y}\pa{p,p(a+s')}=\tau_{x}(p,s_{0}t)+\tau_{y}\pa{p,p(a+s')}\\
&=0+\tau_{y}\pa{p,p(a+s')}=\tau_{x}(p,s't)+\tau_{y}\pa{p,p(a+s')}.
\end{align*}
Consequently, \eref{eq-infs2} 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~\eref{lem-tronc-eq2} to those densities in $\overline {\mathcal{M}}_{3}^{\infty}(R)$ that vanish outside $(a,a+l)$.
\end{proof}

Let us set $\eta=\tau_{\infty}\pa{p,\exp\pa{R/\ell}-1}$. Since $R/\ell\ge \log 2$, by applying Lemma~\ref{lem-tronc} 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}\|\le 2\tau\pa{p_{i},\exp(R/\ell)-1}$.  In particular, the density $\overline p=\sum_{i=1}^{\ell}w_{i}\overline p_{i}$ satisfies 
\begin{equation}\label{thm-monogene-eq1}
\norm{p-\overline p}\le \sum_{i=1}^{\ell}w_{i}\norm{p_{i}-\overline p_{i}}\le \max_{i\in\{1,\ldots,\ell\}}\norm{p_{i}-\overline p_{i}}\le 2\eta.
\end{equation}

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~\ref{lem-tronc} 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\cro{1+\pa{x_{i,0}-x_{i,1}}\pa{\sup_{x\in I_{i}}\overline p_{i}(x)-\inf_{x\in I_{i}}\overline p_{i}(x)}}< \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\cro{1+\pa{x_{1,1}-x_{1,0}}\pa{\sup_{x\in I_{1}}\overline p_{1}(x)-\inf_{x\in I_{1}}\overline p_{1}(x)}}< \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\cro{1+\pa{x_{\ell,1}-x_{\ell,0}}\pa{\sup_{x\in I_{\ell}}\overline p_{\ell}(x)-\inf_{x\in I_{\ell}}\overline p_{\ell}(x)}}< \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}\cro{\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}}}+\overline p_{\ell}1\hskip-2.6pt{\rm l}_{(x_{\ell-1},x_{\ell,1})}
\]
and may therefore be written under the form~\eref{def-mbark} when $k\ge 2\ell$. Moreover, by Cauchy-Schwarz inequality 
\begin{align*}
\bs{R}_{k,0}(\overline p)< \cro{\sum_{i=1}^{\ell}\sqrt{w_{i}\pa{\frac{R}{\ell}}}+0}^{2}=\frac{R}{\ell}\cro{\sum_{i=1}^{\ell}\sqrt{w_{i}}}^{2}\le R
\end{align*}
and consequently, $\overline p\in\overline {\mathcal{M}}_{k}^{\infty}(R)$. We deduce from~\eref{thm-monogene-eq1} that
\begin{align*}
\inf_{q\in \overline {\mathcal{M}}_{k}^{\infty}(R)}\norm{p-q}&\le \norm{p-\overline p}\le 2\eta
\end{align*}
which is \eref{thm-monogene-eq0}.
\end{proof}

\subsection{Proofs of Section \ref{sect-cvxcve}}\label{subsect-proof-cvxcve}
\begin{proof}[Proof of Proposition \ref{prop_extr_cvx_cve}]
The proof relies on the following lemma the proof of which is a direct consequence of convexity and is therefore omitted.
\begin{lem}\label{lem-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.
\end{lem}


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\ge 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~\ref{lem-5} with $g=p-q$ throughout the proof. Given $\epsilon \in\{\pm 1\}$, we set 
\begin{equation}\label{decomp-Ceps}
C_{\epsilon}=\ac{x\in{\mathbb{R}},\; \epsilon g(x)>0}=\bigcup_{i=1}^{l+1}\ac{x\in J_{i},\; \epsilon g(x)>0}.
\end{equation}
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\'e~\citeyearpar{MR3565484}. 

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}|\ge 1$, we may partition $J_{1}$ into $s=m_{1}+1\ge 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\ge 2$, we may apply Lemma~\ref{lem-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 
\begin{align*}
\ac{x\in J_{1},\; g(x)<0}=\cro{\bigcup_{i=2}^{s-1}\Lambda_{i}^{-}}\cup\cro{\Lambda_{s}^{-}\cup\Lambda_{s,]}^{-}}
\end{align*}
and 
\begin{align*}
\ac{x\in J_{1},\; g(x)>0}&=\Lambda_{1,]}^{+}\cup\cro{\bigcup_{i=2}^{s-1}\pa{\Lambda_{i,(}^{+}\cup\Lambda_{i,]}^{+}}}\cup\cro{\Lambda_{s,(}^{+}\cup\Lambda_{s}^{+}}
\end{align*}
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\ge 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}\ge 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~\ref{lem-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~\eref{decomp-Ceps} and the facts that $\sum_{i=1}^{l+1}m_{i}\le |B|\le D+1$ and  $l\le k-1$, we conclude that the sets $C_{{\varepsilon}}$ are unions of at most 
\begin{align*}
m_{1}+1+m_{l+1}+1+\sum_{i=2}^{l}\pa{m_{i}+2}\le |B|+2l\le  D+2k-1
\end{align*}
intervals.
\end{proof}

\begin{proof}[Proof Theorem \ref{thm-approx-conv}] The proof is based on Lemma \ref{lem_fun_cve} and three preliminary approximation results given in Proposition \ref{prop-approx-convexe}, Proposition \ref{prop-approx-con1} and Proposition \ref{prop-approx-con2}, whose proofs follow that one.

\begin{prop}\label{prop-approx-convexe}
Let $f$ be a convex-concave continuous function on a bounded nontrivial interval $[a,b]$ and $\ell_{f}$ be the linear function
\begin{equation}\label{def-lf}
\ell_{f}:x\mapsto f(a)+\frac{f(b)-f(a)}{b-a}\pa{x-a}.
\end{equation}
The following results hold.
\begin{listi}
\item\label{cas-conv1} If $f$ admits a right derivative $f'_{r}(a)$ at $a$ and a left derivative $f'_{l}(b)$ at $b$,
\begin{equation}\label{eq-approx-convexe}
\int_{a}^{b}\ab{f-\ell_{f}}d\mu\le \frac{(b-a)^{2}}{8}\ab{f'_{r}(a)-f'_{l}(b)}.
\end{equation}
\item\label{cas-conv2} If $f$ is strictly monotone on $[a,b]$ with $f'_{r}(a)\ne 0$ and $f'_{l}(b)\ne 0$
\begin{equation}\label{eq-approx-convexe-01}
\int_{a}^{b}\ab{f-\ell_{f}}d\mu\le \frac{(f(b)-f(a))^{2}}{8}\ab{\frac{1}{f'_{r}(a)}-\frac{1}{f'_{l}(b)}},
\end{equation}
with the convention $1/(\pm \infty)=0$.
\end{listi}
\end{prop}
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}\ge f$ on $[a,b]$ when $f$ is convex on $[a,b]$ and $\ell_{f}\le f$ when $f$ is concave. 

\begin{prop}\label{prop-approx-con1}
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'_{r}(a)$ at $a$ and a left derivative $p'_{l}(b)$ at $b$. For all $D\ge 1$, there exists a $D$-linear interpolation $\overline p$ of $p$ such that
\begin{equation}\label{eq-approx-monoconv01}
\int_{a}^{b}\ab{p-\overline p}d\mu\le \frac{4}{3}\cro{\pa{1+L\sqrt{\ab{p'_{l}(b)-p'_{r}(a)}}}^{1/D}-1}^{2}.
\end{equation}
\end{prop}

\begin{prop}\label{prop-approx-con2}
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'_{r}(a)$ and $p'_{l}(b)$ are nonzero. Then, for all $D\ge 1$ there exists a $D$-linear interpolation $\overline p$ of $p$ on $[a,b]$ such that
\begin{equation}\label{eq-cor-monoconv01}
\int_{a}^{b}\ab{p-\overline p}d\mu\le \frac{4}{3}\cro{\pa{1+V\sqrt{\ab{\frac{1}{p'_{r}(a)}-\frac{1}{p'_{l}(b)}}}}^{1/D}-1}^{2}.
\end{equation}
\end{prop}

\begin{lem} \label{lem_fun_cve}
If $F$ is a nondecreasing, differentiable, concave function on ${\mathbb{R}}_{+}$, the mapping 
\[
\phi: u \mapsto \left[ F\pa{\sqrt{u}} - F(0) \right]^2
\]
is concave on $\mathbb{R}_+$. In particular for all $D\ge 1$, 
\[
F_{D}:u\mapsto \cro{\pa{1+\sqrt{u}}^{1/D}-1}^{2}
\]
is concave on ${\mathbb{R}}_{+}$.
\end{lem}

\begin{proof}
For all $u>0$, 
\[
 \phi'(u) =  \frac{F\pa{\sqrt{u}} - F(0)}{\sqrt{u}}F'(\sqrt{u})
\]
is the product of $u\mapsto [F\pa{\sqrt{u}} - F(0)]/\sqrt{u}$ and $u\mapsto F'(\sqrt{u})$ which are both nonnegative and nonincreasing since $F$ is nondecreasing and concave. The function $\phi'$ is therefore nonincreasing and $\phi$ concave. 
\end{proof}

Let's turn to the proof of Theorem \ref{thm-approx-conv}. We first introduce some mappings of interest we will use in the proofs of of Theorem~\ref{thm-approx-conv} and Proposition~\ref{prop-approx-con1}.
Let ${\mathcal{V}}$ be the linear space of continuous functions $f$ on $[a,b]$ that admits a right derivative $f'_{r}(a)$ at $a$ and a left derivative $f'_{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 
\begin{equation}\label{def-ctj}
{\mathcal{T}}_{1}:f\mapsto [x\mapsto f(a+b-x)],\quad  {\mathcal{T}}_{2}:f\mapsto [x\mapsto m-f(x)].
\end{equation}
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 $\L_{1}$-norm on ${\mathcal{V}}$ and they satisfy for all $f\in{\mathcal{V}}$
\begin{align}
\ab{f(a)-f(b)}&=\ab{{\mathcal{T}}_{j}(f)(a)-{\mathcal{T}}_{j}(f)(b)}\label{prop1-ctj}\\
\ab{f'_{r}(a)-f'_{l}(b)}&=\ab{({\mathcal{T}}_{j}(f))'_{r}(a)-({\mathcal{T}}_{j}(f))'_{l}(b)}\label{prop2-ctj}
\end{align}
and ${\mathcal{T}}_{j}^{-1}={\mathcal{T}}_{j}$ for all $j\in\{1,2\}$. \\
Let us now turn to the proof of Theorem~\ref{thm-approx-conv} and assume first that $p$ is nondecreasing, continuous and convex on $[a,b]$ so that $p_{r}'(a)\ge 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}\le p'_{l}(c)\le \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~\ref{prop-approx-con1} to $p_{1}/w_{1}$ and find a $D$-linear interpolation $\overline p_{1}$ of $p$ on $[a,c]$ that satisfies
\begin{align}
\int_{a}^{c}\ab{p-\overline p_{1}}d\mu&\le \frac{4w_{1}}{3}\cro{\pa{1+(c-a)\sqrt{\frac{p'_{l}(c)-p'_{r}(a)}{w_{1}}}}^{1/D}-1}^{2}.\label{eq-approx-conv001}
\end{align}
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~\ref{prop-approx-con2} 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 
\begin{align}
\int_{c}^{b}\ab{p-\overline p_{2}}d\mu\le \frac{4w_{2}}{3}\cro{\pa{1+\frac{p(b)-p(c)}{\sqrt{w_{2}}}\sqrt{\frac{1}{p'_{r}(c)}-\frac{1}{p'_{l}(b)}}}^{1/D}-1}^{2}.\label{eq-approx-conv002}
\end{align}

We may choose $c\in (a,b)$ such that 
\[
p'_{l}(c)\le \Delta\quad \text{and}\quad p'_{r}(c)\ge \Delta\quad \text{with}\quad \Delta=\frac{p(b)-p(a)}{b-a}.
\]
Then 
\begin{align}
A&=(c-a)^{2}\pa{p'_{l}(c)-p'_{r}(a)}+(p(b)-p(c))^{2}\pa{\frac{1}{p'_{r}(c)}-\frac{1}{p'_{l}(b)}}\nonumber \\
&\le (b-a)^{2}\pa{\Delta-p'_{r}(a)}+(p(b)-p(a))^{2}\pa{\frac{1}{\Delta}-\frac{1}{p'_{l}(b)}}\nonumber\\
&=2 (b-a)(p(b)-p(a))\cro{1-\frac{1}{2}\pa{\frac{p'_{r}(a)}{\Delta}+\frac{\Delta}{p'_{l}(b)}}}=2LV\Gamma.\label{def-A-con}
\end{align}

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~\ref{lem_fun_cve} the function $F_{D}$ is concave and increasing, we deduce from~\eref{def-A-con}, ~\eref{eq-approx-conv001} and \eref{eq-approx-conv002} that
\begin{align*}
\frac{3}{4}\norm{p-\overline p}&\le w_{1}\int_{a}^{c}\ab{p-\overline p_{1}}d\mu+w_{2}\int_{c}^{b}\ab{p-\overline p_{2}}d\mu\\
&\le w_{1}F_{D}\pa{\frac{(c-a)^{2}\pa{p'_{l}(c)-p_{r}(a)}}{w_{1}}}\\
&\quad +w_{2}F_{D}\pa{\frac{(p(b)-p(c))^{2}}{w_{2}}\pa{\frac{1}{p'_{r}(c)}-\frac{1}{p'_{l}(b)}}}\\
&\le F_{D}(A)\le F_{D}(2LV\Gamma), 
\end{align*}
which is~\eref{eq-thm-approx-conv}. 

The density $q=\overline p/\int_{a}^{b}\overline pd\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~\ref{lem_l1_proj} that 
\begin{equation}\label{eq-approx-conv003}
\int_{a}^{b}\ab{p-q}d\mu\le 2\ac{1\wedge \cro{\frac{4}{3}\pa{\pa{1+\sqrt{2LV\Gamma}}^{1/D}-1}^{2}}}.
\end{equation}
The mapping $z\mapsto (4/3)(e^{z}-1)^{2}$ is not larger than 1 if and only if  $z\le z_{0}=\log(1+\sqrt{3/4})$ and for all $z\in [0,z_{0}]$, $e^{z}-1\le (e^{z_{0}}-1)z/z_{0}$. Consequently, for all $z\ge 0$
\begin{align*}
2\ac{1\wedge \cro{\frac{4}{3}\pa{e^{z}-1}^{2}}}&= \frac{8}{3}\pa{e^{z_{0}\wedge z}-1}^{2}\le \frac{8}{3}\pa{\frac{e^{z_{0}}-1}{z_{0}}z}^{2}\le 5.14z^{2}.
\end{align*}
Applying this inequality with $z=D^{-1}\log\pa{1+\sqrt{2LV\Gamma}}$, we deduce~\eref{thm-approx-conv-01} from ~\eref{eq-approx-conv003}. 

Theorem~\ref{thm-approx-conv} 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 ~\eqref{def-ctj}. These transformations are isometric with respect to the $\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\pa{{\mathcal{T}}_{j}(f)}$.
Applying ${\mathcal{T}}_{1}$ to nonincreasing continuous convex densities we establish \eref{thm-approx-conv-01}  and we extend it to all monotone concave continuous densities  by applying ${\mathcal{T}}_{2}$.
\end{proof}

\begin{proof}[Proof of Proposition \ref{prop-approx-convexe}]
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 
\begin{equation}\label{eq-approx-fc00}
\int_{0}^{1}\ab{f-\ell_{f}}d\mu\le \frac{1}{2}\frac{\pa{f_{r}'(0)-1}\pa{1-f'_{l}(1)}}{f'_{r}(0)-f'_{l}(1)}
,
\end{equation}
with the convention $0/0=1$. If $f$ is linear on $[0,1]$, then $f_{r}'(0)=f'_{l}(1)=1$ and the inequality is satisfied with our convention. Otherwise, $f_{l}'(1)< 1=f(1)-f(0)<f_{r}'(0)$ and since $f$ lies above its chord and under its tangents at 0 and 1, 
\[
\ell_{f}(x)\le f(x)\le\min\ac{f'_{r}(0)x,1+f_{l}'(1)(x-1)} \quad \text{for all $x\in [0,1]$}.
\]
Since $\ell_{f}(x)=x$, we deduce that for all $c\in [0,1]$
\begin{align*}
\int_{0}^{1}\ab{f-\ell_{f}}d\mu&\le \int_{0}^{c}(f'_{r}(0)-1)xd\mu+\int_{c}^{1}(1-f_{l}'(1))(1-x)d\mu\\
&=\frac{1}{2}\cro{(f'_{r}(0)-1)c^{2}+(1-f_{l}'(1))(1-c)^{2}}.
\end{align*}
The result follows by minimizing with respect to $c$, i.e.\ by taking $c=(1-f_{l}'(1))/(f_{r}'(0)-f_{l}'(1))\in (0,1)$. 
In particular, we deduce from \eref{eq-approx-fc01} that 
\begin{align*}
\int_{0}^{1}\ab{f-\ell_{f}}d\mu\le \frac{c(1-c)}{2}\pa{f'_{r}(0)-f'_{l}(1)}
\end{align*}
and since $c(1-c)\le 1/4$, we obtain that 
\begin{equation}\label{eq-approx-fc01}
\int_{0}^{1}\ab{f-\ell_{f}}d\mu\le \frac{1}{8}\pa{f'_{r}(0)-f'_{l}(1)}.
\end{equation}
Note that the inequality also holds when $f'_{r}(0)=f'_{l}(1)=1$. 

When $f$ is increasing on $[0,1]$ and satisfies $0<1-f_{l}'(1)<1$, i.e.\ $f_{l}'(1)\ne 0$, we also deduce from \eref{eq-approx-fc01} and the convexity of $z\mapsto 1/z$ on $(0,+\infty)$ that 
\begin{align*}
\int_{0}^{1}\ab{f-\ell_{f}}d\mu&\le \frac{1}{4}\frac{1}{\frac{1}{2}\cro{\pa{\frac{1}{1-f'_{l}(1)}-1}+\pa{1+\frac{1}{f'_{r}(0)-1}}}}\\
&\le \frac{1}{4}\cro{\frac{1}{2}\pa{\frac{1}{\frac{1}{1-f'_{l}(1)}-1}+\frac{1}{1+\frac{1}{f'_{r}(0)-1}}}}\\
&= \frac{1}{8}\cro{\frac{1-f'_{l}(1)}{f'_{l}(1)}+\frac{f'_{r}(0)-1}{f'_{r}(0)}}
\end{align*}
which leads to 
\begin{equation}\label{eq-approx-fc02}
\int_{0}^{1}\ab{f-\ell_{f}}d\mu\le \frac{1}{8}\pa{\frac{1}{f'_{l}(1)}-\frac{1}{f'_{r}(0)}}.
\end{equation}
Note that the inequality is still satisfied when $f'_{r}(0)=+\infty$ with the convention $1/(+\infty)=0$. 

Let us now turn to the proofs of~\eref{eq-approx-convexe} and~\eref{eq-approx-convexe-01}. Note that ~\eref{eq-approx-convexe} is clearly true when $f$ is constant on $[a,b]$ and we may therefore assume that $f(a)\ne f(b)$. We obtain \eref{eq-approx-convexe} and \eref{eq-approx-convexe-01} by applying \eref{eq-approx-fc01} and \eref{eq-approx-fc02} 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)}.
\]
\end{proof}


\begin{proof}[Proof of Proposition \ref{prop-approx-con1}]
Let us first consider a function $g$ that is monotone, continuous and convex on $[a,b]$ and that satisfies $g(a)=g_{r}'(a)=0$ and $0<\int_{a}^{b}gd\mu\le 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}'(b)\ge \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'$ be any nondecreasing function on $[a,b]$ satisfying $0=g_{r}'(a)=g'(a)$, $g_{l}'(b)=g'(b)$ and $g_{l}'(x)\le g'(x)\le g_{r}'(x)$ for all $x\in (a,b)$. Since $g$ is convex, we may write 
\begin{equation}\label{eq-approx-convexe2}
g(x)\ge g(x_{i})+g'(x_{i})(x-x_{i})\quad \text{for all $i\in\{1,\ldots,D\}$ and $x\in [a,b]$}.
\end{equation}
In particular,  for all $i\in\{1,\ldots,D-1\}$
\begin{align*}
\int_{x_{i}}^{x_{i}+1}\pa{g(x_{i})+g'(x_{i})(x-x_{i})}d\mu(x)&=\cro{g(x_{i})+\frac{g'(x_{i})\Delta_{i+1}}{2}}\Delta_{i+1}\\
&\le \int_{x_{i}}^{x_{i}+1}gd\mu, 
\end{align*}
hence,  
\begin{equation}\label{eq-approx-convexe3}
g'(x_{i})\Delta_{i+1}^{2}\le 2\int_{x_{i}}^{x_{i}+1}(g-g(x_{i}))d\mu.
\end{equation}
Moreover, applying~\eref{eq-approx-convexe2} with $x_{i}=x_{D}=b$ and using the facts that $g$ is nonnegative and nonincreasing, we get
\begin{align*}
1\ge \int_{a}^{b}gd\mu&\ge \int_{a}^{b}\pa{g(b)+g'(b)(x-b)}_{+}d\mu(x)\\
&=\int_{b-g(b)/g'(b)}^{b}\pa{g(b)+g'(b)(x-b)}d\mu(x)=\frac{g^{2}(b)}{2g'(b)},
\end{align*}
consequently
\begin{equation}\label{eq-approx-convexe4}
g(b)\le \sqrt{2g'(b)}.
\end{equation}

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 \eref{def-lf} 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 
\begin{align*}
\int_{a}^{b}\ab{g-\overline g}d\mu&=\sum_{i=1}^{D}\int_{x_{i-1}}^{x_{i}}\pa{\overline g-g}d\mu\\
&\le \frac{1}{8}\sum_{i=1}^{D} \Delta_{i}^{2}\pa{g_{l}'(x_{i})-g_{r}'(x_{i-1})}\\
&\le \frac{1}{8}\sum_{i=1}^{D} \Delta_{i}^{2}\pa{g'(x_{i})-g'(x_{i-1})}\\
&=\frac{1}{8}\cro{-\Delta_{1}^{2}g'(a)+\Delta_{D}^{2}g'(b)+\sum_{i=1}^{D-1}g'(x_{i})\pa{\Delta_{i}^{2}-\Delta_{i+1}^{2}}}.
\end{align*}
Since $g'(a)=0$ and $\Delta_{i}=q\Delta_{i+1}$ for all $i\in\{1,\ldots,D-1\}$ we deduce that 
\begin{equation}\label{eq-approx-convexe5}
\int_{a}^{b}\ab{g-\overline g}d\mu\le \frac{1}{8}\cro{\Delta_{D}^{2}g'(b)+(q^{2}-1)\sum_{i=1}^{D-1}g'(x_{i})\Delta_{i+1}^{2}}.
\end{equation}
Using \eref{eq-approx-convexe3}, \eref{eq-approx-convexe4} and the fact that $g$ is nondecreasing, 
\begin{align*}
\frac{1}{2}\sum_{i=1}^{D-1}g'(x_{i})\Delta_{i+1}^{2}&\le \sum_{i=1}^{D-1}\int_{x_{i}}^{x_{i+1}}(g-g(x_{i}))d\mu\\
&=\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})\\
&\le \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\\
&=(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\\
&\le (1-q^{-1})\times 1+q^{-1}\Delta_{D}g(b)\le  1-q^{-1}+q^{-1}\sqrt{2\Delta_{D}^{2}g'(b)}.
\end{align*}
It follows from \eref{eq-approx-convexe5} that 
\begin{align*}
&\int_{a}^{b}\ab{g-\overline g}d\mu\\
&\le \frac{1}{8}\cro{\Delta_{D}^{2}g'(b)+2(q^{2}-1)\pa{ 1-q^{-1}+q^{-1}\sqrt{2\Delta_{D}^{2}g'(b)}}}\\
&\le \frac{(q-1)^{2}}{8}\cro{\frac{L^{2}g'(b)}{(q^{D}-1)^{2}}+2\pa{1+\frac{1}{q}}\pa{1+\frac{L\sqrt{2g'(b)}}{q^{D}-1}}}.
\end{align*}
Finally, choosing $q$ such that
\[
q^{D}-1=L\sqrt{g'(b)}\quad \text{i.e.}\quad q=\pa{1+L\sqrt{g'(b)}}^{1/D}> 1,
\]
we get that
\begin{align}
\int_{a}^{b}\ab{g-\overline g}d\mu&\le \frac{1+4(1+\sqrt{2})}{8}\cro{\pa{1+L\sqrt{g'(b)}}^{1/D}-1}^{2}\nonumber\\
&\le \frac{4}{3}\cro{\pa{1+L\sqrt{g'(b)}}^{1/D}-1}^{2}.\label{eq-approx-convexe6}
\end{align}

Let us now prove Proposition~\ref{prop-approx-con1} in the case where $p$ is convex and nondecreasing. Then $p'_{r}(a)\ge 0$ and we may set $\ell:x\mapsto p(a)+p_{r}'(a)(x-a)$ and $g: x\mapsto p(x)-\ell(x)$. The function $g$ is nonnegative, nondecreasing, continuous and convex on $[a,b]$ and it satisfies $g(a)=g'_{r}(a)=0$. If $\int_{a}^{b}gd\mu=0$, then $p=\ell$ and we may choose $\overline p=p$. Otherwise $0<\int_{a}^{b}gd\mu\le 1$, since $\ell$ is nonnegative on $[a,b]$, and we may apply our previous result to $g$. This leads to a $D$-linear interpolation $\overline g$ of $g$ from which we may define $\overline p=\overline g-\ell(x)$ which is a $D$-linear interpolation of $p$ on $[a,b]$. Inequality~\eref{eq-approx-monoconv01} follows from~\eref{eq-approx-convexe6} and the facts that $\ab{p-\overline p}=\ab{g-\overline g}$ and $g'_{l}(b)=p'_{l}(b)-p'_{r}(a)$. \\

In order to prove Proposition~\ref{prop-approx-con1} in the other cases, we use transformations defined by \eqref{def-ctj}. We can note that if $\ell$ is a $D$-linear interpolation of $f$, ${\mathcal{T}}_{j}(\ell)$ is $D$-linear interpolation of ${\mathcal{T}}_{j}(f)$ (based on the same subdivision).

If $p$ is convex and nonincreasing, we apply the transformation ${\mathcal{T}}_{1}$. Then $g={\mathcal{T}}_{1}(p)$ is a convex, nondecreasing sub-density on $[a,b]$ and our previous result applies. We may find a $D$-linear interpolation $\overline g$ on $[a,b]$ such that 
\begin{equation}\label{eq-approx-convexe7}
\int_{a}^{b}\ab{g-\overline g}d\mu\le \frac{4}{3}\cro{\pa{1+L\sqrt{\ab{g_{l}'(b)-g_{r}'(a)}}}^{1/D}-1}^{2},
\end{equation}
and the function $\overline p={\mathcal{T}}_{1}(\overline g)$ is a $D$-linear interpolation of $p={\mathcal{T}}_{1}(g)$ that satisfies~\eref{eq-approx-monoconv01}. The result is therefore proven for all convex continuous monotone sub-density on $[a,b]$. 

If $p$ is a concave continuous sub-density, we apply the transformation ${\mathcal{T}}_{2}$ with $m=2S/(b-a)$ and $S=\int_{a}^{b}pd\mu\le 1$. Since $p$ is concave and monotone, $(p(a)\vee p(b))(b-a)/2\le S$, hence $p(x)\le m$ for all $x\in [a,b]$, and $g={\mathcal{T}}_{2}(p)=m-p$ is a monotone convex sub-density since 
\[
\int_{a}^{b}\pa{m-p}d\mu=\frac{2S}{b-a}\times (b-a)-S=S\le 1.
\]
Applying the previous result, we may find a $D$-interpolation $\overline g$ of $g$ that satisfies~\eref{eq-approx-convexe7} and $\overline p={\mathcal{T}}_{2}(\overline g)$ satisfies~\eref{eq-approx-monoconv01}. This completes the proof of Proposition~\ref{prop-approx-con1}.
\end{proof}


\begin{proof}[Proof of Proposition \ref{prop-approx-con2}]
We start with the following lemma. 
\begin{lem} \label{lem_sym_cvx_dec}
If $f$ and $g$ are two continuous increasing or decreasing functions from on interval $I$ onto an interval $J$,  
\begin{equation} \label{eq_sym_dist_L1}
  \int_I |f - g| d\mu = \int_J  |f^{-1} - g^{-1}| d\mu.  
\end{equation}
Moreover, if $\inf I=0$ and $f$ is nonnegative, continuous and decreasing
\[
\int_{J}f^{-1}d\mu\le \int_{I}fd\mu.
\]
\end{lem}

\begin{proof}
Let us first assume that $f,g$ are both increasing. For all $(t,y)\in I\times J$
\[
1\hskip-2.6pt{\rm l}_{g(t)\le y\le f(t)}+1\hskip-2.6pt{\rm l}_{f(t)\le y\le g(t)}=1\hskip-2.6pt{\rm l}_{f^{-1}(y)\le t\le g^{-1}(y)}+1\hskip-2.6pt{\rm l}_{g^{-1}(y)\le t\le f^{-1}(y)}.
\]
By integrating this equality on $I\times J$ and using Fubini's theorem, we obtain that 
\begin{align*}
\int_{I}\ab{f(t)-g(t)}d\mu(t)&=\int_{I}\cro{\int_{J}\cro{1\hskip-2.6pt{\rm l}_{g(t)\le y\le f(t)}+1\hskip-2.6pt{\rm l}_{f(t)\le y\le g(t)}}d\mu(y)}d\mu(t)\\
&=\int_{J}\cro{\int_{I}\cro{1\hskip-2.6pt{\rm l}_{f^{-1}(y)\le t\le g^{-1}(y)}+1\hskip-2.6pt{\rm l}_{g^{-1}(y)\le t\le f^{-1}(y)}}d\mu(t)}d\mu(y)\\
&=\int_{J}\ab{f^{-1}(y)-g^{-1}(y)}d\mu(y).
\end{align*}
When $f$ and $g$ are both decreasing, we may apply the above equality to $\overline f=f(-\cdot)$ and $\overline g=g(-\cdot)$ from $K=\{-x,\; x\in I\}$ to $J$ then $\overline f^{-1}=-f^{-1},\overline g^{-1}=-g^{-1}$ and the result follows from the facts 
\[
\int_{I}\ab{f-g}d\mu=\int_{K}\ab{\overline f-\overline g}d\mu \text{ and } \int_{J}\ab{\overline f^{-1}-\overline g^{-1}}d\mu=\int_{J}\ab{f^{-1}-g^{-1}}d\mu.
\]

Let us now turn to the  proof of the second part of the lemma. Since $\inf I=0$ and $f$ is decreasing and continuous from $I$ onto $J$, for all $t\in J$
\[
\mu\pa{\ac{x\in I,\; f(x)\ge t}}=\mu\pa{\ac{x\in I,\; x\le f^{-1}(t)}}=f^{-1}(t).
\]
Besides, $f$ being nonnegative, the interval $J\subset {\mathbb{R}}_{+}$ and it follows from Fubini's theorem that
\begin{align*}
\int_{J}f^{-1}(t)d\mu(t)&=\int_{J}\mu\pa{\ac{x\in I,\; f(x)\ge t}}d\mu(t)\\
&=\int_{J}\cro{\int_{I}1\hskip-2.6pt{\rm l}_{t\le f(x)}d\mu(x)}d\mu(t)=\int_{I}\cro{\int_{J}1\hskip-2.6pt{\rm l}_{t\le f(x)}d\mu(t)}d\mu(x)\\
&\le \int_{I}\cro{\int_{0}^{+\infty}1\hskip-2.6pt{\rm l}_{t\le f(x)}d\mu(t)}d\mu(x)=\int_{I}
f(x)d\mu(x).
\end{align*}
\end{proof}

Let us now turn to the proof of~\eref{eq-cor-monoconv01}. We first claim that it is sufficient to establish ~\eref{eq-cor-monoconv01} when $p$ is decreasing. If $p$ were increasing, we could apply the result to $q={\mathcal{T}}_{1}(p)$ defined by~\eref{def-ctj}, which is then decreasing, and find a $D$-linear interpolation of $q$ on $[a,b]$ that satisfies 
\[
\int_{a}^{b}\ab{q-\overline q}d\mu\le \frac{4}{3}\cro{\pa{1+V\sqrt{\ab{\frac{1}{q'_{r}(a)}-\frac{1}{q'_{l}(b)}}}}^{1/D}-1}^{2}.
\]
We then conclude by using the facts that ${\mathcal{T}}_{1}$ is an $\L_{1}$-isometry, the function $\overline p={\mathcal{T}}_{1}(\overline q)$ which is a $D$-linear interpolation of $p$, and $q'_{r}(a)=-p_{l}'(b)$ and  $q'_{l}(b)=-p_{r}'(a)$. 

We may therefore assume that $p$ is decreasing and changing $p$ into $p(\cdot-a)$, which amounts to translate the sub-density $p$, we may also assume with no loss of generality that $a=0$. By Lemma~\ref{lem_sym_cvx_dec}, $s=p^{-1}$ is then a sub-density on $[p(b),p(0)]$ which is furthermore decreasing, continuous and convex-concave. 
Since the right and left derivatives of $p$ at $0$ and $b$ respectively are not zero, $s$ admits a right derivative at $p(b)$ and a left derivative at $p(0)$ given by $1/p'_{l}(b)$ and $1/p'_{r}(0)$ (with our convention $1/(+\infty)=0$. We may therefore apply Proposition~\ref{prop-approx-con1} and find a $D$-linear interpolation $\overline s$ of $s$ on $[p(b),p(0)]$ that satisfies 
\[
\int_{p(b)}^{p(0)}\ab{s-\overline s}d\mu\le \frac{4}{3}\cro{\pa{1+V\sqrt{\ab{\frac{1}{p'_{r}(0)}-\frac{1}{p'_{l}(b)}}}}^{1/D}-1}^{2}.
\]
Since $s$ is continuous and decreasing from $[p(b),p(0)]$ onto $[0,b]$, so is $\overline s$, and we may set $\overline p=\overline s^{-1}:[0,b]\to [p(b),p(0)]$. The function $\overline p$ is a $D$-linear interpolation of $p$ on $[0,b]$ and we conclude by using the equality $\int_{p(b)}^{p(0)}\ab{s-\overline s}d\mu=\int_{0}^{b}\ab{p-\overline p}d\mu$ which is a consequence of Lemma~\ref{lem_sym_cvx_dec}.
\end{proof}

\subsection{Proofs of Section \ref{sect-logcc}}\label{subsect-proof-logcc}

\begin{proof}[Proof of Proposition \ref{prop_extr_log_cve}]
Let $p=\exp \phi\in \overline {\mathcal{M}}^{\text{LC}}$, $\overline p=\exp \overline \phi \in \overline{{\mathcal{O}}}_{D}^{\text{LC}}$ and $A\in{\mathcal{A}}(D)$ associated to $\overline p$. There exists a partition ${\mathcal{I}}$ of ${\mathbb{R}}$ into at most $D+1$ intervals such that the restriction of $\overline \phi$ to $I$ with $I\in {\mathcal{I}}$  is either affine or takes the value $-\infty$. Let $J$ be the interval $\{\phi>-\infty\}$. Let $I\in{\mathcal{I}}$, either $\overline \phi$ is finite on $I$ and $I\cap J\cap \{\phi>\overline \phi\}$ is an interval since $\phi-\overline \phi$ is a concave function on the interval $I\cap J$ when it is not empty. Otherwise, $\overline \phi$ takes the value $-\infty$ on $I$ and $I\cap J\cap \{\phi>\overline \phi\}=I\cap J$ remains an interval.  The set $I\cap J^{c}\cap \{\phi>\overline \phi\}$ is empty since $\phi$ takes the value $-\infty$ on $J^{c}$. Hence 
\[
I\cap \ac{\phi>\overline \phi}=\pa{I\cap J\cap \ac{\phi>\overline \phi}}\cup \pa{I\cap J^{c}\cap \ac{\phi>\overline \phi}}
\]
is an interval and 
\[
\ac{p>\overline p}=\ac{\phi>\overline \phi}=\bigcup_{I\in {\mathcal{I}}}\pa{I\cap \ac{\phi>\overline \phi}}
\]
the union of at most $D+1$ intervals. 


Let us now turn to the set $\{\phi<\overline \phi\}$ and define $K=(a,b)$ as the open interval $\{\phi>-\infty\}\cap\{\overline \phi>-\infty\}$ with $a\in{\mathbb{R}}\cup\{-\infty\}$, $b\in{\mathbb{R}}\cup\{+\infty\}$, $a\le b$. If $K=\varnothing$, i.e. $a=b$, ${\mathbb{R}}=\{\phi=-\infty\}\cup\{\overline \phi=-\infty\}$ are disjoint and 
\[
\{\phi<\overline \phi\}=\{\overline \phi>-\infty\}
\]
is an interval. Otherwise $K$ is not empty, $\psi=\phi-\overline \phi$ is a continuous function on $K$ which is either concave on the whole interval $K$ or only piecewise concave on each element of $I\cap K$ with $I\in{\mathbf{I}}(A\cap K)$ when $A\cap K\ne \varnothing$. In any case, 
\[
\ac{x\in K,\; \phi(x)<\overline \phi(x)}=\ac{x\in K,\; \phi(x)-\overline \phi(x)<0}
\]
is a union of at most $|A\cap K|$ intervals plus, possibly, an additional one with endpoint $a$ and another one with endpoint $b$. If $b< +\infty$, either $\overline \phi(b)=-\infty$ or $\phi(b)=-\infty$ and the set $\{x\ge b,\; \phi(x)<\overline \phi(x)\}$ is either empty or is an interval that contains $b$. We may argue similarly to establish that $\{x\le a,\; \phi(x)<\overline \phi(x)\}$ is either empty or an interval that contains $a$. This means that the set 
\[
\ac{\phi<\overline \phi}=\pa{K\cap \ac{\phi<\overline \phi}}\cup \pa{K^{c}\cap  \ac{\phi<\overline \phi}}
\]
is a union of at most $|A\cap K|+2\le D+2$ intervals. We conclude by using Lemma~1 of Baraud and Birg\'e~\citeyearpar{MR3565484}.
\end{proof}

\begin{proof}[Proof of Proposition \ref{prop_log_cve_approx}]
Let us first assume that $p=\exp\phi>0$ on ${\mathbb{R}}$. Then $\phi$ is continuous, concave on ${\mathbb{R}}$ and since $p$ is integrable, $\phi$ tends to $-\infty$ at $\pm \infty$ and reaches its maximum at a point $m\in{\mathbb{R}}$. 
The sets $\overline {\mathcal{M}}^{\text{LC}}$ and $\overline {\mathcal{O}}_{D}^{\text{LC}}$ are both location and scale invariant and the $\L_{1}$-distance between two densities remains unchanged under such transformations. By changing $p$ into 
\[
x\mapsto \sigma p\pa{m+\sigma x}=\exp\cro{\phi\pa{m+\sigma x}+\log \sigma}
\]
with $\sigma=1/p(m)$, if ever necessary, we may assume with no loss of generality that $m=0$ and $0<\phi(x)\le \phi(0)=0$ for all $x\in{\mathbb{R}}$, what we shall do.
We use the following approximation result.
\begin{prop}\label{prop-guer1}
Let $D$ be some positive integer and $f$ a convex-concave function on a non-trivial interval $[a,b]$ such that 
\[
\Delta=\frac{f(b)-f(a)}{b-a}\ne 0.
\]
\begin{listi}
\item If $f$ admits a right derivative at $a$ and a left derivative at $b$, there exists a $D$-linear interpolation $\ell_{1}$ of $f$ such that 
\begin{align}
\int_{a}^{b}\ab{f-\ell_{1}}d\mu&\le \frac{(b-a)^{2}}{2D^{2}}\frac{\ab{f_{r}'(a)-\Delta}\ab{\Delta-f'_{l}(b)}}{\ab{f'_{r}(a)-f'_{l}(b)}}\label{prop-guer1a}\\
&\le \frac{(b-a)^{2}}{8D^{2}}\ab{f'_{r}(a)-f'_{l}(b)}.\nonumber
\end{align}

\item If $\phi$ is strictly monotone on $[a,b]$ with $f_{r}'(a)\ne 0$ and $f_{r}'(b)\ne 0$, there exists a $D$-linear interpolation $\ell_{2}$ of $f$
\begin{equation}
\int_{a}^{b}\ab{f-\ell_{2}}d\mu\le \frac{\pa{f(a)-f(b)}^{2}}{8D^{2}}\ab{\frac{1}{f'_{r}(a)}-\frac{1}{f'_{l}(b)}}\label{prop-guer1b}
\end{equation}
with the convention $1/\pm \infty=0$.
\end{listi}
\end{prop}

\begin{proof}
If $f$ is a concave function on $[0,1]$ satisfying $f(0)=0$ and $f(1)=1$, with a right derivative at 0 and a left derivative at 1, Gu\'erin {\em et al}~\citeyearpar{Guerin2006} proved that there exist a $D$-linear interpolation $\ell$ of $f$ on $[0,1]$ such that 
\begin{equation}\label{eq-guer1}
\int_{0}^{1}\ab{f-\ell}d\mu\le \frac{1}{2D^{2}}\frac{\pa{f'_{r}(0)-1}\pa{1-f_{l}'(1)}}{f'_{r}(0)-f'_{l}(1)}.
\end{equation}
The results established in Proposition~\ref{prop-guer1} are deduced from~\eref{eq-guer1} by arguing as in the proof of Proposition~\ref{prop-approx-convexe}.
\end{proof}

Let $t=2.3$, $a_{0}=b_{0}=0$ and $a_{1},b_{1}$ be numbers such that $a_{1}<0<b_{1}$ and $|\phi(a_{1})|=|\phi(b_{1})|=t>0$. Since $\phi$ is concave,  
\[
\phi(x)\ge t\pa{\frac{x}{|a_{1}|}\wedge \frac{-x}{b_{1}}}\quad \text{for $x\in [a_{1},b_{1}]$.}
\]
In particular, 
\begin{align*}
1&=\int_{{\mathbb{R}}}e^{\phi}d\mu>\int_{a_{1}}^{0}e^{tx/|a_{1}|}d\mu+\int_{0}^{b_{1}}e^{-tx/b_{1}}d\mu,
\end{align*}
and consequently, 
\begin{align}
1>\frac{\pa{|a_{1}|+b_{1}}\pa{1-e^{-t}}}{t},\text{i.e.}\quad |a_{1}|+b_{1}\le  \frac{t}{1-e^{-t}}.\label{eq-lc00b}
\end{align}
Let us now define for all $j\ge 2$, 
\[
a_{j}=\inf\ac{x\le a_{1}, \phi(x)\ge -jt}\quad \text{and}\quad b_{j}=\sup\ac{x\ge b_{1}, \phi(x)\ge -jt}.
\]
Since $\phi$ is continuous, concave and tends to $-\infty$ at $\pm \infty$, $a_{j}$ and $b_{j}$ exist, satisfy $\phi(a_{j})=\phi(b_{j})=-jt$ and for all $j\ge 1$. 

Let $J\ge 2$ and $D_{1},\ldots,D_{J}$ be positive integers. Applying Proposition~\ref{prop-guer1} to $\phi$, we can find two $D_{1}$-linear interpolations $\ell_{1}^{-}$ and $\ell_{1}^{+}$ of $\phi$ on $[a_{1},0]$ and $[0,b_{1}]$ respectively that satisfy \eref{prop-guer1a} and for all $j\in\{2,\ldots,J\}$, we can find two $D_{j}$-linear interpolations $\ell_{j}^{-}$ and $\ell_{j}^{+}$ of $\phi$ on $[a_{j},a_{j-1}]$ and $[b_{j-1},b_{j}]$ respectively that satisfy \eref{prop-guer1b}. The function
\[
\overline \phi=\sum_{i=1}^{J}\cro{\ell_{j}^{-}1\hskip-2.6pt{\rm l}_{[a_{j},a_{j-1})}+\ell_{j}^{+}1\hskip-2.6pt{\rm l}_{[b_{j-1},b_{j})}}+(-\infty)1\hskip-2.6pt{\rm l}_{{\mathbb{R}}\setminus [a_{J},b_{J}]}
\]
is $(2\sum_{j=1}^{J}D_{j})$-linear interpolation of $\phi$ on $[a_{J},b_{J}]$ and the function $\overline p=\exp \overline \phi$ is integrable and satisfies 
\[
1\ge p(x)=e^{\phi(x)}\ge \overline p=e^{\overline \phi(x)}\quad \text{for all $x\in {\mathbb{R}}$}.
\]

Since $\phi$ is concave and nondecreasing on $[a_{1},0]$, $\phi'_{l}(0)\ge 0$ and 
\begin{align*}
0&\le \frac{a_{1}^{2}}{\phi'_{r}(a_{1})-\phi_{l}'(0)}\pa{\phi'_{r}(a_{1})-\frac{\phi(0)-\phi(a_{1})}{|a_{1}|}}\pa{\frac{\phi(0)-\phi(a_{1})}{|a_{1}|}-\phi'_{l}(0)}\\
&\le \frac{a_{1}^{2}}{\phi'_{r}(a_{1})-\phi_{l}'(0)}\pa{\phi'_{r}(a_{1})-\frac{t}{|a_{1}|}}\pa{\frac{t}{|a_{1}|}-\phi'_{l}(0)}\\
&\le \frac{a_{1}^{2}}{\phi'_{r}(a_{1})}\pa{\phi'_{r}(a_{1})-\frac{t}{|a_{1}|}}\frac{t}{|a_{1}|}=t\pa{|a_{1}|-\frac{t}{\phi_{r}'(a_{1})}}.
\end{align*}
By arguing similarly on the interval $[0,b_{1}]$ and using the fact that $\phi'_{r}(0)\le 0$,  we obtain that 
\begin{align*}
0&\le \frac{b_{1}^{2}}{\phi_{r}'(0)-\phi_{l}'(b)}\pa{\phi'_{r}(0)-\frac{\phi(b_{1})-\phi(0)}{b_{1}}}\pa{\frac{\phi(b_{1})-\phi(0)}{b_{1}}-\phi'_{l}(b_{1})}\\
&\le  t\pa{b_{1}-\frac{t}{|\phi_{l}'(b_{1})|}}.
\end{align*}

Applying Proposition~\ref{prop-guer1}-(i), we obtain that 
\begin{align}
&\int_{a_{1}}^{b_{1}}\ab{\phi-\overline \phi}d\mu\le \frac{t}{2D_{1}^{2}}\cro{\pa{|a_{1}|-\frac{t}{\phi_{r}'(a_{1})}}+\pa{b_{1}-\frac{t}{|\phi_{l}'(b_{1})|}}}.\label{eq-lc001}
\end{align}

Applying Proposition~\ref{prop-guer1}-(ii) on the intervals $[a_{j},a_{j-1}]$ and $[b_{j-1},b_{j}]$ respectively with $j\in\{2,\ldots,J\}$, we obtain that 
\begin{align}
\int_{a_{j}}^{a_{j-1}}\ab{\phi-\overline \phi}d\mu&\le \frac{t^{2}}{8 D_{j}^{2}}\pa{\frac{1}{\phi'_{l}(a_{j-1})}-\frac{1}{\phi'_{r}(a_{j})}}\label{eq-lc002a}\\
\int_{b_{j-1}}^{b_{j}}\ab{\phi-\overline \phi}d\mu&\le \frac{t^{2}}{8 D_{j}^{2}}\pa{\frac{1}{\phi'_{l}(b_{j})}-\frac{1}{\phi'_{r}(b_{j-1})}}. \label{eq-lc002b}
\end{align}
Choosing $K=\sqrt{t/(1-e^{-t})}$, 
\[
D_{1}=\PES{KD\sqrt{t/2}}\quad \text{and for all $j\ge 2$}\quad D_{j}=\PES{KDe^{-(j-1)t/2}\sqrt{t/8}},
\]
we deduce from \eref{eq-lc001} that 
\begin{align}
\int_{a_{1}}^{b_{1}}\ab{p-\overline p}d\mu &=\int_{a_{1}}^{b_{1}}e^{\phi}\pa{1-e^{-(\phi-\overline \phi)}}d\mu\le e^{\phi(0)}\int_{a_{1}}^{b_{1}}\pa{\phi-\overline \phi}d\mu\nonumber\\
&\le \frac{t}{2D_{1}^{2}}\cro{\pa{|a_{1}|-\frac{t}{\phi_{r}'(a_{1})}}+\pa{b_{1}-\frac{t}{|\phi_{l}'(b_{1})|}}}\nonumber\\
&\le \frac{1}{K^{2}D^{2}}\cro{\pa{|a_{1}|-\frac{t}{\phi_{r}'(a_{1})}}+\pa{b_{1}-\frac{t}{|\phi_{l}'(b_{1})|}}}\label{eq-lc003a}
\end{align}
and from \eref{eq-lc002a} and \eref{eq-lc002b} that for all $j\in\{2,\ldots,J\}$, 
\begin{align}
&\int_{a_{j}}^{a_{j-1}}\ab{p-\overline p}d\mu+\int_{b_{j-1}}^{b_{j}}\ab{p-\overline p}d\mu\nonumber \\
&\le e^{\phi(a_{j-1})}\int_{a_{j}}^{a_{j-1}}\pa{\phi-\overline \phi}d\mu+e^{\phi(b_{j-1})}\int_{b_{j-1}}^{b_{j}}\pa{\phi-\overline \phi}d\mu\nonumber\\
&\le \frac{e^{-(j-1)t}t^{2}}{8 D_{j}^{2}}\cro{\frac{1}{\phi'_{l}(a_{j-1})}-\frac{1}{\phi'_{r}(a_{j})}+\frac{1}{\phi'_{l}(b_{j})}-\frac{1}{\phi'_{r}(b_{j-1})}}\nonumber\\
&\le \frac{1}{K^{2}D^{2}}\cro{\frac{t}{\phi'_{l}(a_{j-1})}-\frac{t}{\phi'_{r}(a_{j})}+\frac{t}{\phi'_{l}(b_{j})}-\frac{t}{\phi'_{r}(b_{j-1})}}.\label{eq-lc003b}
\end{align}

Summing up the inequalities \eref{eq-lc003a} and \eref{eq-lc003b} for $j\in\{1,\ldots,J\}$ and using the fact that $\phi_{r}'(x)\le \phi'_{l}(x)$ for all $x\in{\mathbb{R}}$, we obtain 
\begin{align}
\int_{a_{J}}^{b_{J}}\ab{p-\overline p}d\mu
&\le \frac{1}{K^{2}D^{2}}\cro{|a_{1}|+b_{1}-\frac{1}{\phi'_{r}(a_{J})}-\frac{1}{\phi'_{l}(b_{J})}}.\label{eq-lc004a}
\end{align}

For $j\ge J+1$ and $x\in [a_{j},a_{j-1}]$, $\overline p(x)=0\le p(x)\le \phi(a_{j-1})+\phi'_{l}(a_{j-1})(x-a_{j-1})$ and consequently, 
\begin{align*}
\int_{a_{j}}^{a_{j-1}}\ab{p-\overline p}d\mu&\le \int_{a_{j}}^{a_{j-1}}\exp\pa{\phi(a_{j-1})+\phi'_{l}(a_{j-1})(x-a_{j-1})}d\mu\\
&\le \frac{e^{-t(j-1)}}{\phi_{l}'(a_{j-1})}\pa{1-e^{-\phi'_{l}(a_{j-1})(a_{j-1}-a_{j})}}\le \frac{e^{-t(j-1)}}{\phi_{l}'(a_{j-1})}\le \frac{e^{-t(j-1)}}{\phi_{l}'(a_{J})}.
\end{align*}
Similarly, using that $\overline p(x)=0\le p(x)\le \phi(b_{j-1})+\phi'_{r}(b_{j-1})(x-b_{j-1})$ for all $x\in [b_{j-1},b_{j}]$ with $j\ge J+1$ we obtain that
\begin{align*}
\int_{b_{j-1}}^{b_{j}}\ab{p-\overline p}d\mu&\le \int_{b_{j-1}}^{b_{j}}\exp\pa{\phi(b_{j-1})+\phi'_{r}(b_{j-1})(x-b_{j-1})}d\mu\\
&\le \frac{e^{-t(j-1)}}{\phi_{r}'(b_{j-1})}\le \frac{e^{-t(j-1)}}{\phi_{r}'(b_{J})}.
\end{align*}
We deduce that 
\begin{align*}
\int_{{\mathbb{R}}\setminus [a_{J},b_{J}]}\ab{p-\overline p}d\mu &=\sum_{j\ge J+1}\cro{\int_{a_{j}}^{a_{j-1}}\ab{p-\overline p}d\mu+\int_{b_{j-1}}^{b_{j}}\ab{p-\overline p}d\mu}\\
&\le \cro{\frac{1}{\phi_{l}'(a_{J})}+\frac{1}{\phi_{r}'(b_{J})}}\sum_{j\ge J+1}e^{-t(j-1)}\\
&=\cro{\frac{1}{\phi_{l}'(a_{J})}+\frac{1}{\phi_{r}'(b_{J})}}\frac{e^{-tJ}}{1-e^{-t}}.
\end{align*}
Let us choose $J$ such that 
\[
J=\PES{\frac{1}{t}\log\pa{\frac{K^{2}D^{2}}{1-e^{-t}}}}\ge \pa{\frac{1}{t}\log\pa{\frac{K^{2}D^{2}}{1-e^{-t}}}}.
\]
Note that $J\ge 2$ since $D\ge 6>D_{0}=e^{t}\sqrt{1-e^{-t}}/K$. With this choice of $J$
\begin{align}
\int_{{\mathbb{R}}\setminus [a_{J},b_{J}]}\ab{p-\overline p}d\mu &\le \cro{\frac{1}{\phi_{l}'(a_{J})}+\frac{1}{\phi_{r}'(b_{J})}}\frac{1}{K^{2}D^{2}}.\label{eq-lc004b}
\end{align}
Adding inequalities \eref{eq-lc004a} and \eref{eq-lc004b}, using \eref{eq-lc00b} and Lemma~\ref{lem_l1_proj} we obtain that the density $q=\overline p/\int_{{\mathbb{R}}}\overline pd\mu$ satisfies
\begin{align*}
\int_{{\mathbb{R}}}\ab{p-q}d\mu\le 2\int_{{\mathbb{R}}}\ab{p-\overline p}d\mu\le \frac{2\pa{|a_{1}|+b_{1}}}{K^{2}D^{2}}\le \frac{2t}{(1-e^{-t})K^{2}D^{2}}=\frac{2}{D^{2}}
\end{align*}
and belongs to $\overline {\mathcal{O}}^{\text{LC}}_{D'}$ with 
\begin{align*}
D'&\le 2\sum_{j=1}^{J}D_{j}+1\le KD\sqrt{2t}\cro{1+\frac{1}{2}\sum_{j=2}^{J}e^{-(j-1)t/2}}+2J+1\\
&\le D\cro{K\sqrt{2t}\pa{1+\frac{e^{-t/2}}{2(1-e^{-t/2})}}+\frac{2}{tD_{0}}\log\pa{\frac{K^{2}D_{0}^{2}}{1-e^{-t}}}+\frac{3}{D_{0}}}\\
&\le 6D.
\end{align*}
Consequently, 
\[
\inf_{q\in \overline {\mathcal{O}}^{\text{LC}}_{6D}}\int_{{\mathbb{R}}}\ab{p-q}d\mu\le \frac{2}{D^{2}}.
\]
This inequality, which holds for all positive log-concave densities, extend to nonnegative ones by using the fact that the set gathering of the former are dense in the set gathering the latter for the $\L_{1}$-norm. 
\end{proof}

\bibliographystyle{apalike}
