Sharp oracle inequalities for Least Squares estimators in shape restricted regression

Introduction

The error of an estimator $\boldsymbol{\hat{\mu}}$ of ${\boldsymbol{\mu}}$ is given by $\|\boldsymbol{\hat{\mu}}-{\boldsymbol{\mu}}\|^{2}$. Let also $|\cdot|_{\infty}$ be the infinity norm and $|\cdot|_{2}$ be the Euclidean norm, so that $\frac{1}{n}|\cdot|_{2}^{2}=\|\cdot\|^{2}$.

Model misspecification allows that the true parameter ${\boldsymbol{\mu}}$ does not belong to $K$. There is a large literature on the performance of the LS estimator in isotonic and convex regression, that is, when the set $K$ is the set of all nondecreasing sequences or the set of convex sequences. Some of these results are reviewed in the following subsections.

Let ${\mathcal{S}_{n}^{\uparrow}}$ be the set of all nondecreasing sequences, defined by

The set ${\mathcal{S}_{n}^{\uparrow}}$ is a closed convex cone. Two quantities are useful to describe the performance of the LS estimator $\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$. First, define the total variation by

If ${\boldsymbol{u}}=(u_{1},\dots,u_{n})^{T}\in{\mathcal{S}_{n}^{\uparrow}}$, its total variation is simply $V({\boldsymbol{u}})=u_{n}-u_{1}$. Second, for ${\boldsymbol{u}}=(u_{1},\dots,u_{n})^{T}\in{\mathcal{S}_{n}^{\uparrow}}$, let $k({\boldsymbol{u}})\geq 1$ be the integer such that $k({\boldsymbol{u}})-1$ is the number of inequalities $u_{i}\leq u_{i+1}$ that are strict for $i=1,\dots,n-1$ (the number of jumps of ${\boldsymbol{u}}$).

Previous results on the performance of the LS estimator $\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$ can be found in , where risk bounds or oracle inequalities with leading constant strictly greater than 1 are derived. Two types of risk bounds or oracle inequalities have been obtained so far. If, ${\boldsymbol{\mu}}=(\mu_{1},...,\mu_{n})^{T}\in{\mathcal{S}_{n}^{\uparrow}}$, it is known that for some absolute constant $c>0$,

and $c\leq 12.3$, cf. . If ${\boldsymbol{\mu}}\in{\mathcal{S}_{n}^{\uparrow}}$, the following oracle inequality was proved in :

The risk bounds (1.6) and (1.7) hold under the assumption that ${\boldsymbol{\mu}}\in{\mathcal{S}_{n}^{\uparrow}}$, which does not allow for any model misspecification. We will see below that this assumption can be dropped. The oracle inequality (1.6) implies that the LS estimator achieves the rate $n^{-2/3}$ while (1.7) yields a parametric rate (up to logarithmic factors) if ${\boldsymbol{\mu}}$ is well approximated by a piecewise constant sequence with not too many pieces. Let us note that the bound (1.7) can be used to obtain that $\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$ converges at the rate $n^{-2/3}$ up to logarithmic factors, thanks to the approximation argument given in [4, Lemma 2].

Mimimax lower bounds that match (1.6) and (1.7) up to logarithmic factors have been obtained in . If $D>0$ is a fixed parameter and $\log(en)^{3}\sigma^{2}\leq nD^{2}$, the bound (1.6) yields the rate $(D\sigma^{2})^{2/3}n^{-2/3}$ for the risk of $\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$. By the lower bound [4, Corollary 5], this rate is minimax optimal over the class $\{{\boldsymbol{\mu}}\in{\mathcal{S}_{n}^{\uparrow}}:V({\boldsymbol{u}})\leq D\}$ if $\log(en)^{3}\sigma^{2}\leq nD^{2}$. Proposition 4 in shows that there exist absolute constants $c,c^{\prime}>0$ such that for any estimator $\boldsymbol{\hat{\mu}}$,

Together, (1.7) and (1.8) establish that for any $k=1,...,n$, the minimax rate over the class $\{{\boldsymbol{\mu}}\in{\mathcal{S}_{n}^{\uparrow}}:k({\boldsymbol{\mu}})\leq k\}$ is of order $\sigma^{2}k/n$ up to logarithmic factors.

2 Convex regression with equispaced design points

If $n\geq 3$, define the set of convex sequences $\mathcal{S}_{n}^{\textsc{c}}$ by

For ${\boldsymbol{u}}=(u_{1},\dots,u_{n})^{T}\in\mathcal{S}_{n}^{\textsc{c}}$, let $q({\boldsymbol{u}})\in\{1,...,n-1\}$ be the smallest integer $q$ such that there exists a partition $(T_{1},...,T_{q})$ of $\{1,...,n\}$ and real numbers $a_{1},...,a_{q}$ satisfying

The performance of the LS estimator over convex sequences has been recently studied in , where it was proved that if ${\boldsymbol{\mu}}\in\mathcal{S}_{n}^{\textsc{c}}$, the estimator $\boldsymbol{\hat{\mu}}=\boldsymbol{\hat{\mu}}^{\textsc{ls}}(\mathcal{S}_{n}^{\textsc{c}})$ satisfies

for some absolute constant $C>0$. If ${\boldsymbol{\mu}}\in\mathcal{S}_{n}^{\textsc{c}}$ and $nR_{\boldsymbol{\mu}}^{2}\geq\log(en)^{5/4}\sigma^{2}$ where $R_{\boldsymbol{\mu}}$ defined in 4.4 below is a constant that depends only on ${\boldsymbol{\mu}}$, then the estimator $\boldsymbol{\hat{\mu}}=\boldsymbol{\hat{\mu}}^{\textsc{ls}}(\mathcal{S}_{n}^{\textsc{c}})$ satisfies

for some absolute constant $C>0$. The bound (1.12) yields an almost parametric rate if ${\boldsymbol{\mu}}$ can be well approximated by a piecewise affine sequence with not too many pieces. If $\bar{R}>0$ is a fixed parameter and $n\bar{R}^{2}\geq\log(en)^{5/4}\sigma^{2}$, the bound (1.13) yields the rate $(\bar{R}^{2}\sigma^{8})^{1/5}n^{-4/5}\log(en)$, which is minimax optimal over the class $\{{\boldsymbol{\mu}}\in\mathcal{S}_{n}^{\textsc{c}}:R_{\boldsymbol{\mu}}\leq\bar{R}\}$ up to logarithmic factors .

The above results hold in convex regression for equispaced design points. The following subsection introduces the notation that will be used to study convex regression with non-equispaced design points.

3 Non-equispaced design points in convex regression

For any ${\boldsymbol{u}}=(u_{1},...,u_{n})^{T}\in{\mathcal{K}}^{C}_{x_{1},...,x_{n}}$, we say that ${\boldsymbol{u}}$ is piecewise affine with $k$ pieces if there exist real numbers $a_{1},...,a_{k}$ and a partition $(T_{1},...,T_{k})$ of $\{1,..,n\}$ such that

The performance of the LS estimator $\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{K}}^{C}_{x_{1},...,x_{n}})$ is also studied in in the case where the design points are almost equispaced: The bounds (1.12) and (1.13) both hold if $\mathcal{S}_{n}^{\textsc{c}}$ is replaced with ${\mathcal{K}}^{C}_{x_{1},...,x_{n}}$ and if $C>0$ is a constant that depends on the ratio

and this constant $C$ becomes arbitrarily large as this ratio tends to infinity.

Although (1.13) and (1.12) provide an accurate picture of the performance of the LS estimator for equispaced (or almost equispaced) design points, it is not known whether these bounds continue to hold for other design points. A goal of the present paper is to fill this gap. Section 4 shows that the oracle inequality (1.12) holds irrespective of the design points, while the nonparametric rate of the LS estimator can be as slow as $n^{-2/3}$ for some worst-case design points.

It is clear that a convex function is unimodal in the sense that it is first non-increasing and then nondecreasing. The following subsection introduces the set of unimodal sequences, and Section 4.2 studies the relationship between convex regression and unimodal regression.

4 Unimodal regression

The convex set $K_{m}$ is the set of all unimodal sequences with mode at position $m$ and

is the set of all unimodal sequences. The set $\mathcal{U}$ is non-convex. For all ${\boldsymbol{u}}\in\mathcal{U}$, let $k({\boldsymbol{u}})$ be the smallest integer $k$ such that ${\boldsymbol{u}}$ is piecewise constant with $k$ pieces, i.e., the smallest integer $k$ such that there exists a partition $(T_{1},...,T_{k})$ of $\{1,...,n\}$ such that for all $l=1,...,k$,

the sequence ${\boldsymbol{u}}_{T_{l}}$ is constant, and

the set $T_{l}$ is convex in the sense that if $a,b\in T_{l}$ then $T_{l}$ contains all integers between $a$ and $b$.

If ${\boldsymbol{u}}\in{\mathcal{S}_{n}^{\uparrow}}$, this definition of $k({\boldsymbol{u}})$ coincides with that defined above.

As the inclusion ${\mathcal{S}_{n}^{\uparrow}}\subset\mathcal{U}$ holds, the lower bound (1.8) implies that for any estimator $\boldsymbol{\hat{\mu}}$,

Chatterjee and Lafferty 2015 recently obtained an adaptive risk bound of the form

where $C>0$ is an absolute constant. This risk bound does not match the lower bound (1.21) because of the exponent $3/2$.

5 Organisation of the paper

Section 1.6 recalls properties of closed convex set and closed convex cones.

General oracle inequalities. In Section 2 we establish general tools that yield sharp oracle inequalities: 2.2 and 2.3.

Sharp bounds in isotonic regression. In Section 3 we apply results of Section 2 to the isotonic LS estimator. We obtain an adaptive risk bound that is tight with sharp numerical constants.

On the relationship between unimodal and convex regression. Section 4 studies the role of the design points in univariate convex regression: Although the nonparametric rate is of order $n^{-4/5}$ for equispaced design points, this rate can be as slow as $n^{-2/3}$ for some worst-case design points that are studied in Section 4, whereas the adaptive risk bound (1.12) holds for any design points. The relation between convex regression and unimodal regression is discussed in Section 4.2: Although convexity brings more structure than unimodality, for some worst-case design points this extra structure is uninformative and the nonparametric rates of unimodal regression and convex regression are both $n^{-2/3}$. Section A.1 studies unimodal regression and improves some of the results of on the performance of the unimodal LS estimator.

Comparison of different misspecification errors. In Section 5 we compare different quantities that represent the estimation error when the model is misspecified. In particular, Section 5 explains that if $K$ is a closed convex set and ${\boldsymbol{\mu}}\notin K$, the sharp oracle inequalities obtained in Sections 2, 3 and 4 yield upper bounds on the estimation error $\|\boldsymbol{\hat{\mu}}^{\textsc{ls}}(K)-\Pi_{K}({\boldsymbol{\mu}})\|$. If ${\boldsymbol{\mu}}\notin K$, the LS estimator consistently estimates the projection of the true parameter ${\boldsymbol{\mu}}$ onto $K$ for $K={\mathcal{S}_{n}^{\uparrow}}$ and $K=\mathcal{S}_{n}^{\textsc{c}}$.

Some proofs are delayed to Appendices A and B.

6 Preliminary properties of closed convex sets

Inequality (1.23) can be rewritten as follows

which is a consequence of the cosine theorem. The LS estimator over $K$ is exactly the projection of $\mathbf{y}$ onto $K$, i.e., $\boldsymbol{\hat{\mu}}^{\textsc{ls}}(K)=\Pi_{K}(\mathbf{y})$. In this case, (1.24) yields that for all ${\boldsymbol{u}}\in K$,

Inequality (1.25) can be interpreted in terms of strong convexity: the LS estimator $\boldsymbol{\hat{\mu}}^{\textsc{ls}}(K)$ solves an optimization problem where the function to minimize is strongly convex with respect to the norm $\|\cdot\|$. Strong convexity grants inequality (1.25), which is stronger than the inequality

Define the statistical dimension of the cone $K$ by

We refer the reader to [1, Proposition 3.1] for straightforward proofs of the equivalence between the definitions (1.29) and the properties (1.30), (1.31) and (1.28). An exact formula is available for the statistical dimension of ${\mathcal{S}_{n}^{\uparrow}}$. Namely, it is proved in [1, (D.12)] that

The following upper bound on the statistical dimension of the cone ${\mathcal{K}}^{C}_{x_{1},...,x_{n}}$ is derived in :

for some constant $c>0$ that depends on the ratio (1.18). In 4.1, we derive a tighter bound independent of the design points.

General tools to derive sharp oracle inequalities

In this section, we develop two general tools to derive sharp oracle inequalities for the LS estimator over a closed convex set.

If $K$ is a closed convex cone, then $\mathcal{T}_{K,{\boldsymbol{u}}}=\{{\boldsymbol{v}}-t{\boldsymbol{u}}|{\boldsymbol{v}}\in K,t\geq 0\}$.

where ${\boldsymbol{g}}=(1/\sigma){\boldsymbol{\xi}}$.

Let $\boldsymbol{\hat{\mu}}=\boldsymbol{\hat{\mu}}^{\textsc{ls}}(K)$. Then (1.25) yields

where ${\boldsymbol{\hat{\theta}}}$ is defined by ${\boldsymbol{\hat{\theta}}}=(1/|\boldsymbol{\hat{\mu}}-{\boldsymbol{u}}|_{2})(\boldsymbol{\hat{\mu}}-{\boldsymbol{u}})$ if $\boldsymbol{\hat{\mu}}\neq{\boldsymbol{u}}$ and ${\boldsymbol{\hat{\theta}}}={\boldsymbol{0}}$ otherwise. By construction we have ${\boldsymbol{\hat{\theta}}}\in\mathcal{T}_{K,{\boldsymbol{u}}}$ and $|{\boldsymbol{\hat{\theta}}}|_{2}^{2}\leq 1$. Using the simple inequality $2ab-b^{2}\leq a^{2}$ with $a=\sup_{{\boldsymbol{\theta}}\in\mathcal{T}_{K,{\boldsymbol{u}}}:|{\boldsymbol{\theta}}|_{2}\leq 1}{\boldsymbol{\xi}}^{T}{\boldsymbol{\theta}}$ and $b=|\boldsymbol{\hat{\mu}}-{\boldsymbol{u}}|_{2}$, we obtain

The equality (1.28) completes the proof. ∎

Applying this concentration inequality to the cone $L=\mathcal{T}_{K,{\boldsymbol{u}}}$ yields the following Corollary.

Furthermore, for all $x>0$ with probability at least $1-e^{-x}$ we have

In the well-specified case, a similar upper bound was derived in [14, Theorem 3.1]. Oymak and Hassibi 2013 also proved a worst-case lower bound that matches the upper bound.

If $K\subset V$ where $V$ is a subspace of dimension $d_{V}$, then by monotonicity of the statistical dimension (1.31) we have $\delta(\mathcal{T}_{K,{\boldsymbol{u}}})\leq\delta(V)=d_{V}$. In this case, (2.2) shows that the constant 4 in [16, Proposition 3.1] can be reduced to 1.

2 Localized Gaussian widths

In this section, we develop yet another technique to derive sharp oracle inequalities for LS estimators over closed convex sets. This technique is associated with localized Gaussian widths rather than statistical dimensions of tangent cones. The result is given in 2.3 below. Recently, other general methods have been proposed , but these methods did not provide oracle inequalities with leading constant 1.

Then for any $x>0$, with probability greater than $1-e^{-x}$,

The proof of 2.3 is related to the isomorphic method and the theory of local Rademacher complexities in regression with random design .

Let $t=t_{*}({\boldsymbol{u}})$ and $\boldsymbol{\hat{\mu}}=\boldsymbol{\hat{\mu}}^{\textsc{ls}}(K)$ for brevity. The concentration inequality for suprema of Gaussian processes [5, Theorem 5.8] yields that on an event $\Omega(x)$ of probability greater than $1-e^{-x}$,

On the one hand, if $|\boldsymbol{\hat{\mu}}-{\boldsymbol{u}}|_{2}\leq t$, then by (2.3) on $\Omega(x)$ we have

On the other hand, if $|\boldsymbol{\hat{\mu}}-{\boldsymbol{u}}|_{2}>t$, then $\alpha\coloneqq t/|\boldsymbol{\hat{\mu}}-{\boldsymbol{u}}|_{2}$ belongs to $(0,1)$. If ${\boldsymbol{v}}=\alpha\boldsymbol{\hat{\mu}}+(1-\alpha){\boldsymbol{u}}$ then $\alpha(\boldsymbol{\hat{\mu}}-{\boldsymbol{u}})={\boldsymbol{v}}-{\boldsymbol{u}}$, by convexity of $K$ we have ${\boldsymbol{v}}\in K$ and by definition of $\alpha$ it holds that $|{\boldsymbol{v}}-{\boldsymbol{u}}|_{2}=t$. On $\Omega(x)$,

where we used $2ab-b^{2}\leq a^{2}$ with $b=t/\alpha$ and $a=Z/t$. Thus (2.9) holds on $\Omega(x)$ for both cases $|\boldsymbol{\hat{\mu}}-{\boldsymbol{u}}|_{2}\leq t$ and $|\boldsymbol{\hat{\mu}}-{\boldsymbol{u}}|_{2}>t$. Finally, inequality $(u+v)^{2}\leq 2u^{2}+2v^{2}$ yields that $(t+\sigma\sqrt{2x})^{2}\leq 2t^{2}+4\sigma^{2}x$. ∎

Note that condition (2.8) does not depend on the true vector ${\boldsymbol{\mu}}$, but only depends on the vector ${\boldsymbol{u}}$ that appears on the right hand side of the oracle inequality. The left hand side of (2.8) is the Gaussian width of ${\mathcal{C}}$ localized around ${\boldsymbol{u}}$. This differs from the recent analysis of Chatterjee 2014 where the Gaussian width localized around ${\boldsymbol{\mu}}$ is studied. An advantage of considering the Gaussian width localized around ${\boldsymbol{u}}$ is that the resulting oracle inequality (2.9) is sharp, i.e., with leading constant 1. Chatterjee 2014 proved that the Gaussian width localized around ${\boldsymbol{\mu}}$ characterizes a deterministic quantity $t_{\boldsymbol{\mu}}$ such that $|\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{C}})-{\boldsymbol{\mu}}|_{2}$ concentrates around $t_{\boldsymbol{\mu}}$. This result from grants both an upper bound and a lower bound on $|\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{C}})-{\boldsymbol{\mu}}|_{2}$, but it does not imply nor is implied by a sharp oracle inequality such as (2.9) above. Thus, the result of is of a different nature than (2.9).

A strategy to find a quantity $t_{*}$ that satisfies (2.8) is to use metric entropy results together with Dudley integral bound, although Dudley integral bound may not be tight [5, Section 13.1, Exercises 13.4 and 13.5].

Sharp bounds in isotonic regression

We study in this section the performance of $\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$ using the general tools developed in the previous section. We first apply 2.2. To do so, we need to bound from above the statistical dimension of the tangent cone $\mathcal{T}_{{\mathcal{S}_{n}^{\uparrow}},{\boldsymbol{u}}}$. In fact, it is possible to characterize the tangent cone $\mathcal{T}_{{\mathcal{S}_{n}^{\uparrow}},{\boldsymbol{u}}}$ and to obtain a closed formula for its statistical dimension.

Let ${\boldsymbol{u}}\in{\mathcal{S}_{n}^{\uparrow}}$ and let $k=k({\boldsymbol{u}})$. Let $(T_{1},...,T_{k})$ be a partition of $\{1,...,n\}$ such that ${\boldsymbol{u}}$ is constant on each $T_{j},j=1,...,k$. Then

Let $\mathcal{T}_{{\mathcal{S}_{n}^{\uparrow}},{\boldsymbol{u}}}=\mathcal{T}$ for brevity. If ${\boldsymbol{u}}$ is constant, then it is clear that $\mathcal{T}={\mathcal{S}_{n}^{\uparrow}}$ so we assume that ${\boldsymbol{u}}$ has at least one jump, i.e., $k({\boldsymbol{u}})\geq 2$. As ${\mathcal{S}_{n}^{\uparrow}}$ is a cone we have $\mathcal{T}=\{{\boldsymbol{v}}-t{\boldsymbol{u}}|t\geq 0,{\boldsymbol{v}}\in{\mathcal{S}_{n}^{\uparrow}}\}$. Thus the inclusion $\mathcal{T}_{{\mathcal{S}_{n}^{\uparrow}},{\boldsymbol{u}}}\subset{\mathcal{S}^{\uparrow}}_{|T_{1}|}\times...\times{\mathcal{S}^{\uparrow}}_{|T_{k}|}$ is straightforward. For the reverse inclusion, let ${\boldsymbol{x}}\in{\mathcal{S}^{\uparrow}}_{|T_{1}|}\times...\times{\mathcal{S}^{\uparrow}}_{|T_{k}|}$ and let $\varepsilon>0$ be the minimal jump of the sequence ${\boldsymbol{u}}$, that is, $\varepsilon=\min_{i=1,...,n-1:u_{i+1}>u_{i}}(u_{i+1}-u_{i})$. If $t=|{\boldsymbol{x}}|_{\infty}/(4\varepsilon)$ then the vector ${\boldsymbol{v}}\coloneqq t{\boldsymbol{u}}+{\boldsymbol{x}}$ belongs to ${\mathcal{S}_{n}^{\uparrow}}$, which completes the proof. ∎

Using (1.30) and (1.33) we obtain $\delta(\mathcal{T}_{{\mathcal{S}_{n}^{\uparrow}},{\boldsymbol{u}}})=\sum_{j=1}^{k({\boldsymbol{u}})}\sum_{t=1}^{|T_{j}|}\frac{1}{t}\leq\sum_{j=1}^{k({\boldsymbol{u}})}\log(e|T_{j}|)$. By Jensen’s inequality, this quantity is bounded from above by $k({\boldsymbol{u}})\log(en/k({\boldsymbol{u}}))$. Applying 2.2 leads to the following result.

Furthermore, for any $x>0$ we have with probability greater than $1-\exp(-x)$

Let us discuss some features of 3.2 that are new. First, the estimator $\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$ satisfies oracle inequalities both in deviation with exponential probability bounds and in expectation, cf. (3.3) and (3.2), respectively. Previously known oracle inequalities for the LS estimator over ${\mathcal{S}_{n}^{\uparrow}}$ were only proved in expectation.

Second, both (3.2) and (3.3) are sharp oracle inequalities, i.e., with leading constant 1. Although sharp oracle inequalities were obtained using aggregation methods , this is the first known sharp oracle inequality for the LS estimator $\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$.

Third, the assumption ${\boldsymbol{\mu}}\in{\mathcal{S}_{n}^{\uparrow}}$ is not needed, as opposed to the result of .

Last, the constant $1$ in front of $\frac{\sigma^{2}k({\boldsymbol{u}})}{n}\log\frac{en}{k({\boldsymbol{u}})}$ in (3.2) is optimal for the LS estimator. To see this, assume that there exists an absolute constant $c<1$ such that for all ${\boldsymbol{\mu}}\in{\mathcal{S}_{n}^{\uparrow}}$ and $\boldsymbol{\hat{\mu}}=\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$,

Set ${\boldsymbol{\mu}}=0$. Thanks to (1.33), the left hand side of the above display is bounded from below by $\sigma^{2}\log(n)/n$ while while the right hand side is equal to $c\sigma^{2}\log(en)/n$. Thus, it is impossible to improve the constant in front of $\frac{\sigma^{2}k({\boldsymbol{u}})}{n}\log\frac{en}{k({\boldsymbol{u}})}$ for the estimator $\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$. However, it is still possible that for another estimator $\boldsymbol{\hat{\mu}}$, (3.4) holds with $c<1$ or without the logarithmic factor. We do not know whether such an estimator exists.

We now highlight the adaptive behavior of the estimator $\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$. Let ${\boldsymbol{u}}^{*}\in{\mathcal{S}_{n}^{\uparrow}}$ be a minimizer of the right hand side of (3.2). Let $k=k({\boldsymbol{u}}^{*})$ and let $(T_{1},...,T_{k})$ be a partition of $\{1,...,n\}$ such that ${\boldsymbol{u}}^{*}$ is constant on all $T_{j}$, $j=1,..,k$. Given $T_{1},...,T_{k}$, consider the piecewise constant oracle

where $W_{T_{1},...,T_{k}}$ is the linear subspace of all sequences that are constant on all $T_{j}$, $j=1,...,k$. This subspace has dimension $k$, so the estimator $\boldsymbol{\hat{\mu}}^{\textsc{oracle}}$ satisfies

Thus, (3.2) can be interpreted in the sense that without the knowledge of $T_{1},...,T_{k}$, the performance of $\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$ is similar to that of $\boldsymbol{\hat{\mu}}^{\textsc{oracle}}$ up to the factor $\log(en/k)$. Of course, the knowledge of $T_{1},...,T_{k}$ is not accessible in practice, so $\boldsymbol{\hat{\mu}}^{\textsc{oracle}}$ is an oracle that can only serve as a benchmark. This adaptive behavior of $\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$ was observed in .

The following results are direct consequences of 2.3, Dudley integral bound and the entropy bounds from .

The novelty of 3.3 is twofold. First, the leading constant is $1$. Although model misspecification was considered in , no oracle inequalities were obtained. Second, the above sharp oracle inequality holds in deviation, whereas the previous work derived upper bounds on the expected squared risk in the well-specified case. Note that one can derive sharp oracle inequality in expectation by integration of (3.7).

Convex regression and arbitrary design points

The goal of this section is to study univariate convex regression for non-equispaced design points.

We now present a new argument to bound from above the statistical dimension of the cone of convex sequences.

Let $n\geq 3$. Let $x_{1}<...<x_{n}$ be real numbers and consider the cone ${\mathcal{K}}^{C}_{x_{1},...,x_{n}}$ defined in (1.15). Let ${\boldsymbol{g}}\sim\mathcal{N}({\boldsymbol{0}},I_{n\times n})$. Then

Let $K={\mathcal{K}}^{C}_{x_{1},...,x_{n}}$ for brevity. A convex sequence ${\boldsymbol{u}}=(u_{1},...,u_{n})\in K$ is first non-increasing and then nondecreasing, that is, there exists $m\in\{1,...,n\}$ such that $u_{1}\geq u_{2}\geq...\geq u_{m}\leq u_{m+1}\leq...\leq u_{n}$, hence the sequence ${\boldsymbol{u}}$ is unimodal. Thus, if $K_{m},m=1,...,n$ are the sets defined in (1.19), then $K\subset\mathcal{U}=\cup_{m=1,...,n}K_{m}$. Using (1.30), (1.31) and (1.33) we obtain

Using (2.5) and the union bound, for all $x>0$, we have with probability at least $1-e^{-x}$ the inequality $|\Pi_{K}({\boldsymbol{g}})|_{2}^{2}\leq\max_{m=1,...,n}\delta(K_{m})^{1/2}+\sqrt{2(x+\log n)}$. As $(a+b)^{2}\leq 2a^{2}+2b^{2}$, on the same event of probability at least $1-e^{-x}$ we have

Integration of this probability bound completes the proof. ∎

Remarkably, this bound on the statistical dimension does not depend on the design points $x_{1},...,x_{n}$. Furthermore, the bound (4.1) improves upon (1.34) as the exponent $5/4$ is reduced to 1. (4.1)

Let $n\geq 3$, and let ${\boldsymbol{u}}$ be an element of the cone ${\mathcal{K}}^{C}_{x_{1},...,x_{n}}$ defined in (1.15). The statistical dimension of the tangent cone at ${\boldsymbol{u}}$ satisfies

Let $q=q({\boldsymbol{u}})$. Let $(T_{1},...,T_{q})$ be a partition of $\{1,...,n\}$ such that ${\boldsymbol{u}}$ is affine on each $T_{j},j=1,...,q$. Let ${\boldsymbol{x}}\in{\mathcal{K}}^{C}_{x_{1},...,x_{n}}$. A convex sequence minus an affine sequence is convex, thus for all $j=1,...,q$, $({\boldsymbol{x}}-{\boldsymbol{u}})_{T_{j}}$ is convex in the sense that it belongs to ${\mathcal{K}}^{C}_{x_{i}:i\in T_{j}}$. Thus

Using (1.31), (1.30), 4.1 and Jensen’s inequality we have

Combining 2.2 and 4.2 yields the following.

with probability greater than $1-\exp(-x)$.

2 Worst-case design points in convex regression and the rate n−2/3n^{-2/3}

The nonparametric rate for estimation of convex sequences is of order $n^{-4/5}$ for equispaced design points. This was established in using metric entropy bounds. The following result combines the metric entropy bounds from with 2.3.

Thanks to the metric entropy bounds of , 4.4 holds for equispaced design points or design points that are almost equispaced in the sense that the ratio (1.18) is bounded from above by a numerical constant. It is natural to ask whether the nonparametric rate $n^{-4/5}$ can be achieved by the LS estimator for any design points. The following result provides a negative answer: There exist design points such that no estimator can achieve a better rate than $n^{-2/3}$. This rate $n^{-2/3}$ is substantially slower than the nonparametric rate $n^{-4/5}$ achieved by the LS estimator in convex regression with equispaced design points.

Let $V>0$. There exists design points $x_{1}<...<x_{n}$ that depend on $V$ such that for any estimator $\boldsymbol{\hat{\mu}}$,

The intuition behind this result is the following. Let ${\boldsymbol{\mu}}=(\mu_{1},...,\mu_{n})^{T}\in{\mathcal{S}_{n}^{\uparrow}}$ be strictly increasing and let $\epsilon\coloneqq\frac{1}{2}\wedge\min_{i=2,...,n-1}\frac{\mu_{i+1}-\mu_{i}}{\mu_{i}-\mu_{i-1}}$. If we define the design points $x_{1}<...<x_{n}$ by $x_{i}=-\epsilon^{i}$ for all $i=1,...,n$ then ${\boldsymbol{\mu}}\in K^{C}_{x_{1},...,x_{n}}$ (this statement is made rigorous in the proof of 4.5). That is, for any strictly increasing sequence ${\boldsymbol{\mu}}$, there are geometrically spaced design points $x_{1}<...<x_{n}$ such that ${\boldsymbol{\mu}}=(f(x_{1}),...,f(x_{n}))^{T}$ for some convex function $f$. As explained in the following proof, this observation yields that the minimax lower bound over ${\mathcal{S}_{n}^{\uparrow}}$ implies a minimax lower bound over ${\mathcal{K}}^{C}_{x_{1},...,x_{n}}$ for a specific choice of design points $x_{1},...,x_{n}$.

For any ${\boldsymbol{u}}\in{\mathcal{S}_{n}^{\uparrow}}$, let $V({\boldsymbol{u}})=u_{n}-u_{1}$. It was proved in [4, Proposition 4 and Corollary 5] that for some integer $M\geq 2$, there exist ${\boldsymbol{\mu}}_{0},...,{\boldsymbol{\mu}}_{M}\in{\mathcal{S}_{n}^{\uparrow}}$ such that $V(\boldsymbol{\hat{\mu}}_{j})\leq V$ and

for all distinct $j,k\in\{0,...,M\}$ and some absolute constant $C>0$. The quantity $\frac{n}{2\sigma^{2}}\|{\boldsymbol{\mu}}_{j}-{\boldsymbol{\mu}}_{0}\|$ is Kullback-Leibler divergence from $\mathcal{N}({\boldsymbol{\mu}}_{j},\sigma^{2}I_{n\times n})$ to $\mathcal{N}({\boldsymbol{\mu}}_{0},\sigma^{2}I_{n\times n})$.

Define ${\boldsymbol{v}}=(v_{1},...,v_{n})^{T}$ by $v_{i}=iV/n$ for all $i=1,...,n$ so that $V({\boldsymbol{v}})\leq V$ and ${\boldsymbol{v}}$ is strictly increasing. We define ${\boldsymbol{u}}^{0},...,{\boldsymbol{u}}^{M}$ by ${\boldsymbol{u}}^{j}={\boldsymbol{\mu}}_{j}+{\boldsymbol{v}}$ so that ${\boldsymbol{u}}^{0},...,{\boldsymbol{u}}^{M}$ are strictly increasing. Furthermore, since ${\boldsymbol{\mu}}_{j}-{\boldsymbol{\mu}}_{k}={\boldsymbol{u}}^{j}-{\boldsymbol{u}}^{k}$ it is clear that (4.12) still holds if ${\boldsymbol{\mu}}_{j},{\boldsymbol{\mu}}_{k}$ are replaced by ${\boldsymbol{u}}^{j},{\boldsymbol{u}}^{k}$. Applying [17, Theorem 2.7] yields that for any estimator $\boldsymbol{\hat{\mu}}$,

Let $\epsilon\coloneqq\frac{1}{2}\wedge\min_{j=1,...,M}\min_{i=2,...,n-1}\frac{u^{j}_{i+1}-u^{j}_{i}}{u^{j}_{i}-u^{j}_{i+1}}$. Since the sequences ${\boldsymbol{u}}^{0},...,{\boldsymbol{u}}^{M}$ are strictly increasing we have $\epsilon>0$. Define the design points $x_{1}<...<x_{n}$ by $x_{i}=-\epsilon^{i}$ for all $i=1,...,n$. Then for all $j=0,...,M$ we have

for all $i=2,...,n-1$, and by (1.15) this implies that ${\boldsymbol{u}}^{j}\in{\mathcal{K}}^{C}_{x_{1},...,x_{n}}$. It remains to show that $V({\boldsymbol{u}}^{j})\leq 2V$, which is a consequence of $V({\boldsymbol{\mu}}_{j})\leq V$ and $V({\boldsymbol{v}})\leq V$. ∎

If the practitioner can choose the design points, then geometrically spaced design points should be avoided.

Any convex function is unimodal so that the inclusion ${\mathcal{K}}^{C}_{x_{1},...,x_{n}}\subset\mathcal{U}$ holds for any design points $x_{1}<...<x_{n}$. Intuitively, this inclusion means that convexity brings more structure than unimodality. 4.6 below shows that the convex LS enjoys essentially the same risk bounds and oracle inequalities those satisfied by the unimodal LS estimator in A.4 and A.5.

The proofs of 4.6 and 4.7 are given in Section A.3. 4.7 shows that the convex LS estimator achieves a rate of order $n^{-2/3}$ for any design points. Together, 4.7 and 4.5 establish that this rate is minimal over all design points and all univariate convex functions with bounded total variation. To make this precise, define the minimax quantity

for some absolute constant $C>0$. On the other hand, 4.5 and Markov inequality yield that $\mathfrak{R}(V)\geq C^{\prime}\sigma^{2}(\frac{V}{\sigma n})^{2/3}$ for some absolute constant $C^{\prime}>0$. In summary,

This establishes that the nonparametric rate of univariate convex regression over all possible design points is of order $n^{-2/3}$ provided that $V\geq\sigma$. This rate is substantially slower than the rate $n^{-4/5}$ observed by Guntuboyina and Sen 2013 for equispaced design points. In summary, there is no hope to achieve the nonparametric rate $n^{-4/5}$ for any univariate design points.

As a convex function is unimodal, the inclusion ${\mathcal{K}}^{C}_{x_{1},...,x_{n}}\subset\mathcal{U}$ holds. The convex constraints that define ${\mathcal{K}}^{C}_{x_{1},...,x_{n}}$ are more restrictive than the unimodal constraint, i.e., convexity brings more structure than unimodality. For equispaced design points, the extra structure brought by convexity yields a nonparametric rate of order $n^{-4/5}$ which is faster than the unimodal nonparametric rate $n^{-2/3}$. However, for some worst-case design points, this extra structure is uninformative from a statistical standpoint: The nonparametric rates of convex and unimodal regression are of the same order $n^{-2/3}$.

Estimation of the projection of the true parameter

is small, either in expectation or with high probability. If ${\boldsymbol{\mu}}\notin K$, we say that the model is misspecified. In that case, several natural quantities are of interest to assess the performance of an estimator $\boldsymbol{\hat{\mu}}$. The regret of order 1 and the regret of order 2 of an estimator $\boldsymbol{\hat{\mu}}$ are defined by

If $\boldsymbol{\hat{\mu}}\in K$, it is clear that $R_{1}(\boldsymbol{\hat{\mu}})\geq 0,R_{2}(\boldsymbol{\hat{\mu}})\geq 0$ and that $R_{1}(\boldsymbol{\hat{\mu}})^{2}\leq R_{2}(\boldsymbol{\hat{\mu}})$ by using the basic inequality $(a-b)^{2}\leq|a^{2}-b^{2}|$ for all $a,b\geq 0$.

If the set $K$ is closed and convex and $\boldsymbol{\hat{\mu}}$ is valued in $K$, another quantity of interest is the estimation error with respect to the projection of ${\boldsymbol{\mu}}$ onto $K$:

The triangle inequality yields $|\|\boldsymbol{\hat{\mu}}-{\boldsymbol{\mu}}\|-\min_{{\boldsymbol{u}}\in K}\|{\boldsymbol{u}}-{\boldsymbol{\mu}}\||\leq\|\boldsymbol{\hat{\mu}}-\Pi_{K}({\boldsymbol{\mu}})\|$. Furthermore, if $\boldsymbol{\hat{\mu}}$ is valued in $K$ and $K$ is convex, then (1.24) with $\mathbf{y}$ replaced by ${\boldsymbol{\mu}}$ and ${\boldsymbol{u}}$ replaced by $\boldsymbol{\hat{\mu}}$ can be rewritten as

Thus, if $K$ is convex, for any estimator $\boldsymbol{\hat{\mu}}$ valued in $K$ we have $R_{1}^{2}(\boldsymbol{\hat{\mu}})\leq\|\boldsymbol{\hat{\mu}}-\Pi_{E}({\boldsymbol{\mu}})\|^{2}\leq R_{2}(\boldsymbol{\hat{\mu}})$. The following Proposition sums up the relationship between the quantity (5.3) and the regrets of order 1 and 2 in the case of a closed convex set $K$.

Estimation of $\Pi_{K}({\boldsymbol{\mu}})$ by the LS estimator $\boldsymbol{\hat{\mu}}^{\textsc{ls}}(K)$ has been considered in [19, Section 4] for $K={\mathcal{S}_{n}^{\uparrow}}$, and in [11, Section 6] for $K=\mathcal{S}_{n}^{\textsc{c}}$. 5.1 above shows that for any quantity $r(K)$ and any estimator $\boldsymbol{\hat{\mu}}$ valued in a closed convex set $K$, we have

i.e., a sharp oracle inequality with leading constant 1 automatically implies an upper bound on the estimation error with respect to the projection of ${\boldsymbol{\mu}}$ onto $K$. For instance, if $K={\mathcal{S}_{n}^{\uparrow}}$, 3.2 and 3.3 with ${\boldsymbol{u}}=\Pi_{K}({\boldsymbol{\mu}})$ imply the following. If $\boldsymbol{\hat{\mu}}=\boldsymbol{\hat{\mu}}^{\textsc{ls}}({\mathcal{S}_{n}^{\uparrow}})$ and ${\boldsymbol{\pi}}=\Pi_{{\mathcal{S}_{n}^{\uparrow}}}({\boldsymbol{\mu}})$ then

provided that (4.10) holds with ${\boldsymbol{u}}$ replaced by ${\boldsymbol{\pi}}$.

Finally, the following Corollary is an outcome of 5.1, 2.1, and 2.3.

then for all $x>0$, with probability at least $1-e^{-x}$ we have

These results highlight a major advantage of oracle inequalities with leading constant 1 over oracle inequalities with leading constant strictly greater than 1 such that (1.7). Indeed, oracle inequalities with leading constant 1 yield an upper bound on the estimation error $\|\boldsymbol{\hat{\mu}}^{\textsc{ls}}(K)-\Pi_{K}({\boldsymbol{\mu}})\|$ for any closed convex set $K$.

Appendix A From unimodal to convex regression

In this section, we develop the tools needed to study unimodal regression and to prove 4.6 and 4.7 in convex regression. 4.6 and 4.7 are similar to A.4 and A.5 in unimodal regression. Their proofs share the same fundamental argument.

The following result improves the risk bound (1.22) by reducing the exponent $3/2$ to $1$, proving that the lower bound (1.21) is actually tight.

Let ${\boldsymbol{\mu}}\in\mathcal{U}$ and let $k=k({\boldsymbol{\mu}})$. If ${\boldsymbol{\xi}}\sim\mathcal{N}({\boldsymbol{0}},\sigma^{2}I_{n\times n})$ then for all $x$,

holds with probability at least $1-e^{-x}$.

Let $\mathcal{T}_{m,{\boldsymbol{u}}}$ be the tangent cone of $K_{m}$ at some ${\boldsymbol{u}}\in\mathcal{U}$, that is,

For any ${\boldsymbol{u}}\in\mathcal{U}$, define the set $\mathcal{W}_{\boldsymbol{u}}$ and the random variable $Y_{\boldsymbol{u}}$ by

Our proof of A.1 relies on an upper bound on the statistical dimension of the above tangent cones and the concentration of of the random variable $Y_{\boldsymbol{u}}$.

Let ${\boldsymbol{u}}\in\mathcal{U}$ and $x>0$. With probability at least $1-e^{-x}$ we have $Y_{\boldsymbol{u}}\leq\sigma\max_{m=1,...,n}\delta(\mathcal{T}_{m,{\boldsymbol{u}}})+\sigma\sqrt{2(x+\log n)}$.

If ${\boldsymbol{u}}\in\mathcal{U}$ then $\max_{m=1,...,n}\delta(\mathcal{T}_{m,{\boldsymbol{u}}})\leq(k({\boldsymbol{u}})+1)\log(\frac{en}{k({\boldsymbol{u}})+1})$.

Lemma A.2 and Lemma A.3 are proved in Section A.2 below. Lemma A.2 is proved using the union bound and (2.5) applied to the cones $\mathcal{T}_{1,{\boldsymbol{u}}},...,\mathcal{T}_{n,{\boldsymbol{u}}}$, while Lemma A.3 is a straightforward consequence of (1.30), (1.31) and (1.33). The two Lemmas above yield that

Let $\boldsymbol{\hat{\mu}}=\boldsymbol{\hat{\mu}}^{\textsc{ls}}(\mathcal{U})$ and $\hat{R}=|\boldsymbol{\hat{\mu}}-{\boldsymbol{\mu}}|_{2}$. Inequality (1.26) with ${\boldsymbol{u}}={\boldsymbol{\mu}}$ can be rewritten as $\hat{R}^{2}\leq 2{\boldsymbol{\xi}}^{T}(\boldsymbol{\hat{\mu}}-{\boldsymbol{\mu}})$. It is clear that $(1/\hat{R})(\boldsymbol{\hat{\mu}}-{\boldsymbol{\mu}})$ has norm 1 and belongs to $\mathcal{V}_{*}\coloneqq\cup_{m=1,...,n}\mathcal{T}_{m,{\boldsymbol{\mu}}}$. Thus

The concentration inequality (A.4) completes the proof. ∎

During the writing of the revision of the present article in which A.1 was introduced, we became aware of a similar result by Flammarion et al. 2016 obtained independently in the context of statistical seriation. Interestingly, A.1 and the result of Flammarion et al. 2016 are proved using different techniques. A.1 is an outcome of the concentration inequality (2.5) and of upper bounds on the statistical dimension of tangent cones, while Flammarion et al. 2016 prove an oracle inequality using metric entropy bounds and the variational representation studied in . An advantage of the proof presented above is that the numerical constants of A.1 are explicit and reasonably small.

The proof of A.1 can be slightly modified to yield an oracle inequality. The following Theorems recover the results of Flammarion et al. 2016.

Let $\boldsymbol{\hat{\mu}}=\boldsymbol{\hat{\mu}}^{\textsc{ls}}(\mathcal{U})$ and let ${\boldsymbol{u}}$ be a minimizer of the right hand side. We first prove that almost surely,

Let $\hat{R}\coloneqq|\boldsymbol{\hat{\mu}}-{\boldsymbol{\mu}}|_{2}$ and $R\coloneqq|{\boldsymbol{u}}-{\boldsymbol{\mu}}|_{2}$. The vector ${\boldsymbol{\theta}}\coloneqq\frac{\boldsymbol{\hat{\mu}}-{\boldsymbol{u}}}{\hat{R}+R}$ belongs to the set $\mathcal{W}_{\boldsymbol{u}}$ defined in (A.3) and ${\boldsymbol{\theta}}$ has norm at most one because of the triangle inequality $|\boldsymbol{\hat{\mu}}-{\boldsymbol{u}}|_{2}\leq\hat{R}+R$. Inequality (1.26) can be rewritten as $\hat{R}^{2}-R^{2}\leq 2{\boldsymbol{\xi}}^{T}(\boldsymbol{\hat{\mu}}-{\boldsymbol{u}})$ and thus

We have proved (A.7). Applying (A.4) completes the proof of the Theorem. ∎

The oracle inequality of A.4 is sharp (that is, it has leading constant 1), but it is an oracle inequality with respect to the loss $\|\cdot\|$ rather than to the squared loss $\|\cdot\|^{2}$. An oracle inequality with respect to the loss $\|\cdot\|^{2}$ is stronger than an oracle inequality with respect to the loss $\|\cdot\|$. Indeed, if an estimator $\boldsymbol{\hat{\mu}}$ satisfies $\|\boldsymbol{\hat{\mu}}-{\boldsymbol{\mu}}\|^{2}\leq\min_{{\boldsymbol{u}}\in E}\|{\boldsymbol{u}}-{\boldsymbol{\mu}}\|^{2}+\varepsilon$ for some set $E$ and some $\varepsilon>0$, then the inequality $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for all $a,b\geq 0$ yields $\|\boldsymbol{\hat{\mu}}-{\boldsymbol{\mu}}\|\leq\min_{{\boldsymbol{u}}\in E}\|{\boldsymbol{u}}-{\boldsymbol{\mu}}\|+\varepsilon^{1/2}$.

An oracle inequality similar to that of A.4 can be obtained for the nonparametric rate $n^{-2/3}$.

with probability at least $1-e^{-x}$, where $V(\cdot)$ is defined in (1.5).

Let $\boldsymbol{\hat{\mu}}=\boldsymbol{\hat{\mu}}^{\textsc{ls}}(\mathcal{U})$ and let ${\boldsymbol{u}}$ be a minimizer of the right hand side of the oracle inequality. Define

where $c>0$ is the absolute constant from (B.1). Define the random variables $Z_{1},...,Z_{m}$ by

We will prove that the oracle inequality of the Theorem holds on the event

Let $\hat{R}=|\boldsymbol{\hat{\mu}}-{\boldsymbol{\mu}}|_{2}$ and let $R=|{\boldsymbol{u}}-{\boldsymbol{\mu}}|_{2}$. If $|\boldsymbol{\hat{\mu}}-{\boldsymbol{u}}|_{2}\leq t$ then by the triangle inequality $\hat{R}-R\leq|{\boldsymbol{u}}-\boldsymbol{\hat{\mu}}|_{2}\leq t$ and the oracle inequality of the Theorem holds. On the other hand, if $|\boldsymbol{\hat{\mu}}-{\boldsymbol{u}}|_{2}>t$ then using (1.26) and the triangle inequality we have

On the event (A.12), the right hand side of the previous display is bounded from above by $2t+2(2+\sqrt{2})\sqrt{x+\log(en)}$ and the oracle inequality of the Theorem holds.

It remains to bound the probability of the event (A.12). By the concentration inequality for suprema of Gaussian processes and the union bound over $m=1,...,n$, we have with probability at least $1-e^{-x}$, for all $m=1,...,n$,

For all $m=1,...,n$, the variable $Z_{m}$ defined in (A.11) satisfies

The proof of Lemma A.6 is given in Section A.2. This proves that the event (A.12) has probability at least $1-e^{-x}$. ∎

A.2 Proof of Lemma A.2, Lemma A.3 and Lemma A.6

Using (1.28) we have $Y_{\boldsymbol{u}}=\max_{m=1,...,n}|\Pi_{\mathcal{T}_{m,{\boldsymbol{u}}}}({\boldsymbol{\xi}})|_{2}$. We apply (2.5) to $L=\mathcal{T}_{m,{\boldsymbol{u}}}$ for all $m=1,...,n$. The union bound completes the proof. ∎

Let $m=1,...,n$, $k=k({\boldsymbol{u}})$ and let $(T_{1},...,T_{k})$ be a partition of $\{1,...,n\}$ such that ${\boldsymbol{u}}$ is constant on each $T_{l}$ and $T_{l}$ is convex for all $l=1,...,k$. Let $l^{*}\in\{1,...,k\}$ be the unique integer such that $m\in T_{l^{*}}$, and let $T^{*}=T_{l^{*}}$. Let ${\boldsymbol{v}}\in K_{m}$. Then for all $l<l^{*}$, the sequence $({\boldsymbol{v}}-{\boldsymbol{u}})_{T_{l}}$ is non-increasing and for all $l>l^{*}$, the sequence $({\boldsymbol{v}}-{\boldsymbol{u}})_{T_{l}}$ is nondecreasing. Furthermore, if $A=T^{*}\cap\{1,...,m\}$ and $B=T^{*}\cap\{m+1,...,n\}$, the sequence $({\boldsymbol{v}}-{\boldsymbol{u}})_{A}$ is non-increasing and the sequence $({\boldsymbol{v}}-{\boldsymbol{u}})_{B}$ is nondecreasing. We have proved the inclusion

Using Jensen’s inequality with the fact that $|A|+|B|+\sum_{l=1,...,k:l\neq l^{*}}|T_{l}|=n$, we obtain $\delta(\mathcal{T}_{m,{\boldsymbol{u}}})\leq(k+1)\log\frac{en}{k+1}$. ∎

Let $m=1,...,n$ be fixed. As ${\boldsymbol{u}}\in\mathcal{U}$, there exists $m_{\boldsymbol{u}}\in\{1,...,n\}$ such that ${\boldsymbol{u}}\in K_{m_{\boldsymbol{u}}}$. Define $k\coloneqq\min(m,m_{\boldsymbol{u}})$ and $j\coloneqq\max(m,m_{\boldsymbol{u}})$. Let $T\coloneqq\{1,...,k\}$, $E\coloneqq\{k+1,...,j-1\}$ and $S\coloneqq\{j,...,n\}$. Then for all ${\boldsymbol{v}}\in K_{m}$, by definition of $T,E$ and $S$ we have

By definition of the statistical dimension and using the fact that the maximum of two positive numbers is bounded from above by their sum, we have that (A.21) is bounded from above by $\delta(\mathcal{S}^{\uparrow}_{|E|})^{1/2}+\delta(\mathcal{S}^{\downarrow}_{|E|})^{1/2}\leq 2\log(e|E|)^{1/2}\leq 2\log(en)^{1/2}$. We now bound (A.19) from above, while (A.20) can be bounded similarly. For all ${\boldsymbol{v}}\in K_{m}$ such that $|{\boldsymbol{v}}-{\boldsymbol{u}}|_{2}>t$, if $\alpha=t/|{\boldsymbol{v}}-{\boldsymbol{u}}|_{2}$ we have

and $\alpha\in$. By convexity we have ${\boldsymbol{\theta}}=\alpha{\boldsymbol{v}}_{T}+(1-\alpha){\boldsymbol{u}}_{T}\in\mathcal{S}^{\downarrow}_{|T|}$ and

By (B.1), the previous display is bounded from above by $t/2$. Finally, we have

A.3 Proofs of 4.6 and 4.7

Let ${\boldsymbol{u}}\in\mathcal{U}$ be a unimodal sequence. Define the random variable

Appendix B Proof of 3.3 and 4.4

The following result is established in Chatterjee 2014.

There exists an absolute constant $c>0$ such that the following holds. Let ${\boldsymbol{u}}\in{\mathcal{S}_{n}^{\uparrow}}$ and ${\boldsymbol{\xi}}\sim\mathcal{N}({\boldsymbol{0}},\sigma^{2}I_{n\times n})$. Then