arXiv: 1510.08029

Sharp oracle inequalities for Least Squares
estimators in shape restricted regression
Pierre C. Bellec

∗

arXiv:1510.08029v3 [math.ST] 8 Aug 2016

ENSAE,
3 avenue Pierre Larousse,
92245 Malakoff Cedex, France.
Abstract: The performance of Least Squares (LS) estimators is studied in isotonic, unimodal and convex regression. Our results have the form of sharp oracle
inequalities that account for the model misspecification error. In isotonic and unimodal regression, the LS estimator achieves the nonparametric rate n−2/3 as well
as a parametric rate of order k/n up to logarithmic factors, where k is the number
of constant pieces of the true parameter.
In univariate convex regression, the LS estimator satisfies an adaptive risk
bound of order q/n up to logarithmic factors, where q is the number of affine
pieces of the true regression function. This adaptive risk bound holds for any
design points. While Guntuboyina and Sen [11] established that the nonparametric
rate of convex regression is of order n−4/5 for equispaced design points, we show
that the nonparametric rate of convex regression can be as slow as n−2/3 for
some worst-case design points. This phenomenon can be explained as follows:
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 .

1. Introduction
Assume that we have the observations
Yi = µi + ξi ,

i = 1, ..., n,

where µ = (µ1 , ..., µn )T ∈ Rn is unknown, ξ = (ξ1 , ..., ξn )T is a noise vector with ndimensional Gaussian distribution N (0, σ 2 In×n ) where σ > 0 and In×n is the n × n
identity matrix. We will also use the notation g := (1/σ)ξ so that y = µ + ξ =
µ + σg and g ∼ N (0, In×n ). Denote by Eµ and Pµ the expectation and the probability
with respect to the distribution of the random variable y = µ + ξ. The vector y =
(Y1 , ..., Yn )T is observed and the goal is to estimate µ. The estimation error is measured
with the scaled norm k · k defined by
n

kuk2 =

1X 2
u ,
n i=1 i

u = (u1 , ..., un )T ∈ Rn .

The error of an estimator µ̂ of µ is given by kµ̂ − µk2 . Let also | · |∞ be the infinity
norm and | · |2 be the Euclidean norm, so that n1 | · |22 = k · k2 .
This paper studies the Least Squares (LS) estimator in shape restricted regression
under model misspecification. The LS estimator over a nonempty closed set K ⊂ Rn
is defined by
µ̂ls (K) ∈ argmin ky − uk2 .
u∈K

∗

This work was supported by GENES and by the grant Investissements d’Avenir (ANR-11-IDEX0003/Labex Ecodec/ANR-11-LABX-0047).
1

/

2

Model misspecification allows that the true parameter µ 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.
1.1. Isotonic regression
Let Sn↑ be the set of all nondecreasing sequences, defined by
Sn↑ := {u = (u1 , ..., un )T ∈ Rn : ui ≤ ui+1 ,

i = 1, ..., n − 1}.

The set Sn↑ is a closed convex cone. Two quantities are useful to describe the performance
of the LS estimator µ̂ls (Sn↑ ). First, define the total variation by
V (θ) := max θi − min θi ,
i=1,...,n

i=1,...,n

θ = (θ1 , ..., θn )T ∈ Rn .

(1.1)

If u = (u1 , . . . , un )T ∈ Sn↑ , its total variation is simply V (u) = un − u1 . Second, for
u = (u1 , . . . , un )T ∈ Sn↑ , let k(u) ≥ 1 be the integer such that k(u) − 1 is the number
of inequalities ui ≤ ui+1 that are strict for i = 1, . . . , n − 1 (the number of jumps of u).
Previous results on the performance of the LS estimator µ̂ls (Sn↑ ) can be found in
[13, 19, 7, 8], 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, µ = (µ1 , ..., µn )T ∈ Sn↑ , it is known [13, 19, 7, 8] that for some
absolute constant c > 0,
2/3

V (µ)
cσ 2 log(en)
(1.2)
+ cσ 2
Eµ kµ̂ls (Sn↑ ) − µk2 ≤
n
σn
and c ≤ 12.3, cf. [19]. If µ ∈ Sn↑ , the following oracle inequality was proved in [7]:


σ 2 k(u)
en
ls
2
↑
2
.
(1.3)
log
Eµ kµ̂ (Sn ) − µk ≤ 6 min ku − µk +
↑
n
k(u)
u∈Sn
The risk bounds (1.2) and (1.3) hold under the assumption that µ ∈ Sn↑ , which does
not allow for any model misspecification. We will see below that this assumption can
be dropped. The oracle inequality (1.2) implies that the LS estimator achieves the
rate n−2/3 while (1.3) yields a parametric rate (up to logarithmic factors) if µ is well
approximated by a piecewise constant sequence with not too many pieces. Let us note
that the bound (1.3) can be used to obtain that µ̂ls (Sn↑ ) 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.2) and (1.3) up to logarithmic factors have
been obtained in [7, 4]. If D > 0 is a fixed parameter and log(en)3 σ 2 ≤ nD2 , the
bound (1.2) yields the rate (Dσ 2 )2/3 n−2/3 for the risk of µ̂ls (Sn↑ ). By the lower bound
[4, Corollary 5], this rate is minimax optimal over the class {µ ∈ Sn↑ : V (u) ≤ D}
if log(en)3 σ 2 ≤ nD2 . Proposition 4 in [4] shows that there exist absolute constants
c, c′ > 0 such that for any estimator µ̂,
sup
↑
µ∈Sn
:k(µ)≤k

Pµ (kµ̂ − µk2 ≥ cσ 2 k/n) ≥ c′ .

(1.4)

Together, (1.3) and (1.4) establish that for any k = 1, ..., n, the minimax rate over the
class {µ ∈ Sn↑ : k(µ) ≤ k} is of order σ 2 k/n up to logarithmic factors.

/

3

1.2. Convex regression with equispaced design points
If n ≥ 3, define the set of convex sequences Snc by
Snc := {u = (u1 , . . . , un )T ∈ Rn : 2ui ≤ ui+1 + ui−1 , i = 2, . . . , n − 1}.
For u = (u1 , . . . , un )T ∈ Snc , let q(u) ∈ {1, ..., n − 1} be the smallest integer q such that
there exists a partition (T1 , ..., Tq ) of {1, ..., n} and real numbers a1 , ..., aq satisfying
ui = aj (i − l) + ul ,

i, l ∈ Tj ,

j = 1, ..., q.

The quantity q(u) is the smallest integer q such that u is piecewise affine with q pieces.
If x1 < ... < xn are equispaced design points in R, i.e., xi = (i − 1)(x2 − x1 ) + x1 ,
i = 2, ..., n, then
Snc = {u ∈ Rn , u = (f (x1 ), ..., f (xn ))T for some convex function f : R → R}.
The performance of the LS estimator over convex sequences has been recently studied
in [11, 7], where it was proved that if µ ∈ Snc , the estimator µ̂ = µ̂ls (Snc ) satisfies

5/4 !!
en
σ 2 q(u)
2
2
log
(1.5)
Eµ kµ̂ − µk ≤ C minc ku − µk +
u∈Sn
n
q(u)
2
for some absolute constant C > 0. If µ ∈ Snc and nRµ
≥ log(en)5/4 σ 2 where Rµ
defined in Corollary 4.4 below is a constant that depends only on µ, then the estimator
µ̂ = µ̂ls (Snc ) satisfies

2

Eµ kµ̂ − µk ≤ C

!4/5
p
Rµ σ 2
log(en)
n

(1.6)

for some absolute constant C > 0. The bound (1.5) yields an almost parametric rate if
µ can be well approximated by a piecewise affine sequence with not too many pieces.
If R̄ > 0 is a fixed parameter and nR̄2 ≥ log(en)5/4 σ 2 , the bound (1.6) yields the rate
(R̄2 σ 8 )1/5 n−4/5 log(en), which is minimax optimal over the class {µ ∈ Snc : Rµ ≤ R̄}
up to logarithmic factors [11].
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.
1.3. Non-equispaced design points in convex regression
If x1 < ... < xn are non-equispaced design points in R, define the cone
KxC1 ,...,xn := {u ∈ Rn , u = (f (x1 ), ..., f (xn ))T for some convex function f : R → R}.
This can be rewritten as
n
KxC1 ,...,xn := u ∈ Rn :

ui −ui−1
xi −xi−1

≤

ui+1 −ui
xi+1 −xi , i

o
= 2, ..., n − 1 .

(1.7)

/

4

For any u = (u1 , ..., un )T ∈ KxC1 ,...,xn , we say that u is piecewise affine with k pieces if
there exist real numbers a1 , ..., ak and a partition (T1 , ..., Tk ) of {1, .., n} such that
ui = aj (xi − xl ) + ul ,

i, l ∈ Tj ,

j = 1, ..., k.

If u = (f (x1 ), ..., f (xn ))T for some convex function f : R → R and f is a piecewise affine
function with k pieces, then u is piecewise affine with k pieces. For any u ∈ KxC1 ,...,xn ,
let q(u) ≥ 1 be the smallest integer such that u is piecewise affine with q(u) pieces.
The quantity q(u) ≥ 1 satisfies


ui+1 − ui
ui − ui−1
<
q(u) − 1 ≤ i = 2, ..., n − 1 :
.
xi − xi−1
xi+1 − xi
The performance of the LS estimator µ̂ls (KxC1 ,...,xn ) is also studied in [11] in the case
where the design points are almost equispaced: The bounds (1.5) and (1.6) both hold
if Snc is replaced with KxC1 ,...,xn and if C > 0 is a constant that depends on the ratio
maxi=2,...,n (xi − xi−1 )
,
mini=2,...,n (xi − xi−1 )

(1.8)

and this constant C becomes arbitrarily large as this ratio tends to infinity.
Although (1.6) and (1.5) 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.5) 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.
1.4. Unimodal regression
Let m = 1, ..., n. A sequence u ∈ Rn is unimodal with mode at position m if and only
if u{1,...,m} is non-increasing and u{m,...,n} is nondecreasing. Define the convex set
Km := {u = (u1 , ..., un )T ∈ Rn : u1 ≥ ... ≥ um ≤ um−1 ≤ ... ≤ un }.

(1.9)

The convex set Km is the set of all unimodal sequences with mode at position m and
U := ∪m=1,...,n Km
is the set of all unimodal sequences. The set U is non-convex. For all u ∈ U, let k(u) be
the smallest integer k such that u is piecewise constant with k pieces, i.e., the smallest
integer k such that there exists a partition (T1 , ..., Tk ) of {1, ..., n} such that for all
l = 1, ..., k,
• the sequence uTl is constant, and
• the set Tl is convex in the sense that if a, b ∈ Tl then Tl contains all integers
between a and b.

/

5

If u ∈ Sn↑ , this definition of k(u) coincides with that defined above.
As the inclusion Sn↑ ⊂ U holds, the lower bound (1.4) implies that for any estimator
µ̂,
sup
Pµ (kµ̂ − µk2 ≥ cσ 2 k/n) ≥ c′ > 0.
(1.10)
µ∈U :k(µ)≤k

Chatterjee and Lafferty [6] recently obtained an adaptive risk bound of the form

3/2 
1
Cσ 2 
ls
2
k(u) log(en)
≥1− ,
(1.11)
P kµ̂ (U) − µk ≤
n
n
where C > 0 is an absolute constant. This risk bound does not match the lower bound
(1.10) because of the exponent 3/2.
1.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: Corollary 2.2 and Theorem 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.5) 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 . Appendix A.1 studies
unimodal regression and improves some of the results of [6] 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
/ K, the
particular, Section 5 explains that if K is a closed convex set and µ ∈
sharp oracle inequalities obtained in Sections 2 to 4 yield upper bounds on the
estimation error kµ̂ls (K) − ΠK (µ)k. If µ ∈
/ K, the LS estimator consistently
estimates the projection of the true parameter µ onto K for K = Sn↑ and K = Snc .
Some proofs are delayed to Appendices A and B.
1.6. Preliminary properties of closed convex sets
We recall here several properties of convex sets that will be used in the paper. Given
a closed convex set K ⊂ Rn , denote by ΠK : Rn → K the projection onto K. For all
y ∈ Rn , ΠK (y) is the unique vector in K such that
(u − ΠK (y))T (y − ΠK (y)) ≤ 0,

u ∈ K.

(1.12)

/

6

Inequality (1.12) can be rewritten as follows
kΠK (y) − yk2 + ku − ΠK (y)k2 ≤ ku − yk2 ,

y ∈ Rn , u ∈ K,

(1.13)

which is a consequence of the cosine theorem. The LS estimator over K is exactly the
projection of y onto K, i.e., µ̂ls (K) = ΠK (y). In this case, (1.13) yields that for all
u ∈ K,
kµ̂ls (K) − yk2 ≤ ku − yk2 − ku − µ̂ls (K)k2 .
(1.14)
Inequality (1.14) can be interpreted in terms of strong convexity: the LS estimator
µ̂ls (K) solves an optimization problem where the function to minimize is strongly
convex with respect to the norm k · k. Strong convexity grants inequality (1.14), which
is stronger than the inequality
kµ̂ls (U) − yk2 ≤ ku − yk2

for all u ∈ U,

(1.15)

which holds for any closed set U ⊂ Rn .
Now, assume that K is a closed convex cone. In this case, (1.12) implies that for all
y ∈ Rn , ΠK (y) is the unique vector in K such that
ΠK (y)T y = |ΠK (y)|22

and ∀θ ∈ K, θ T y ≤ θT ΠK (y).

(1.16)

The property (1.16) readily implies that for any v ∈ Rn we have
|ΠK (v)|2 =

sup

v T θ.

(1.17)

θ∈K:|θ|2 ≤1

Define the statistical dimension of the cone K by




δ(K) := E |ΠK (g)|22 = E g T ΠK (g) = E 


sup
θ∈K:|θ|2 ≤1

!2 
gT θ  ,

(1.18)

where g ∼ N (0, In×n ). The Gaussian width of a closed convex cone K is defined by
w(K) = E[supv∈K:|v|2 =1 g T v] where g ∼ N (0, In×n ). For any closed convex cone K,
the relation w2 (K) ≤ δ(K) ≤ w2 (K) + 1 is established in [1, Propsition 10.2]. The
following properties of δ(·) will be useful for our purpose. If K ⊂ Rq , C ⊂ Rp are two
closed convex cones, then K × C is a closed convex cone in Rq+p and
δ(K × C) = δ(K) + δ(C).

(1.19)

The statistical dimension δ(·) is monotone in the following sense: If K, L are two closed
convex cones in Rn then
K ⊂ L ⇒ δ(K) ≤ δ(L).
(1.20)
We refer the reader to [1, Proposition 3.1] for straightforward proofs of the equivalence
between the definitions (1.18) and the properties (1.19), (1.20) and (1.17). An exact
formula is available for the statistical dimension of Sn↑ . Namely, it is proved in [1, (D.12)]
that
n
X
1
δ(Sn↑ ) =
,
(1.21)
k
k=1

and this formula readily implies that

log(n) ≤ δ(Sn↑ ) ≤ log(en).

(1.22)

/

7

The following upper bound on the statistical dimension of the cone KxC1 ,...,xn is derived
in [11]:
(1.23)
δ(KxC1 ,...,xn ) ≤ c(log(en))5/4 ,
for some constant c > 0 that depends on the ratio (1.8). In Theorem 4.1, we derive a
tighter bound independent of the design points.
2. 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.
2.1. Statistical dimension of the tangent cone
Let µ ∈ Rn , let K be a closed convex subset of Rn and let u ∈ Rn . Define the tangent
cone at u by
(2.1)
TK,u := closure {t(v − u) : t ≥ 0, v ∈ K}
If K is a closed convex cone, then TK,u = {v − tu|v ∈ K, t ≥ 0}.

Proposition 2.1. Let µ ∈ Rn , let K be a closed convex subset of Rn and let u ∈ K.
Then almost surely
kµ̂ls (K) − µk2 − ku − µk2 ≤

σ2
|ΠTK,u (g)|22
n

(2.2)

where g = (1/σ)ξ.
Proof. Let µ̂ = µ̂ls (K). Then (1.14) yields
|µ̂ − µ|22 − |u − µ|22 ≤ 2ξ T (µ̂ − u) − |µ̂ − u|22 = 2ξT θ̂|µ̂ − u|22 − |µ̂ − u|22

(2.3)

where θ̂ is defined by θ̂ = (1/|µ̂ − u|2 )(µ̂ − u) if µ̂ 6= u and θ̂ = 0 otherwise. By
construction we have θ̂ ∈ TK,u and |θ̂|22 ≤ 1. Using the simple inequality 2ab − b2 ≤ a2
with a = supθ∈TK,u :|θ|2 ≤1 ξ T θ and b = |µ̂ − u|2 , we obtain
|µ̂ − µ|22 − |u − µ|22 ≤ 2ξT (µ̂ − u) − |µ̂ − u|22 ≤



sup
θ∈TK,u :|θ|22 ≤1

θT ξ

2

.

The equality (1.17) completes the proof.
By definition of the statistical dimension, δ(TK,u ) := E|ΠTK,u (g)|22 so that (2.2)
readily yields a sharp oracle inequality in expectation. Bounds with high probability
are obtained as follows. Let L ⊂ Rn be a closed convex cone. By (1.17) we have
|ΠL (g)|2 = supx∈L:|x|2 ≤1 xT g. Thus, by the concentration of suprema of Gaussian
processes [5, Theorem 5.8] we have
√
P(|ΠL (g)|2 > E|ΠL (g)|2 + 2x) ≤ e−x ,
and by Jensen’s inequality we have (E|ΠL (g)|2 )2 ≤ δ(L). Combining these two bounds,
we obtain
√
P(|ΠL (g)|2 ≤ δ(L)1/2 + 2x) ≥ 1 − e−x .
(2.4)

Applying this concentration inequality to the cone L = TK,u yields the following Corollary.

/

8

Corollary 2.2. Let µ ∈ Rn , let K be a closed convex subset of Rn , let u ∈ K and let
TK,u be defined in (2.1). If ξ ∼ N (0, σ 2 In×n ) then


σ2
E kµ̂ls (K) − µk2 ≤ ku − µk2 +
δ(TK,u ).
n

Furthermore, for all x > 0 with probability at least 1 − e−x we have
kµ̂ls (K) − µk2 − ku − µk2 ≤

√ 2
σ2
σ2 
δ(TK,u )1/2 + 2x ≤
(2δ(TK,u ) + 4x) .
n
n

In the well-specified case, a similar upper bound was derived in [14, Theorem 3.1].
Oymak and Hassibi [14] also proved a worst-case lower bound that matches the upper
bound.
The survey [1] provides general recipes to bound from above the statistical dimension
of cones of several types. For instance, the statistical dimension of Sn↑ is given by the
exact formula (1.21). Bounds on the statistical dimension of a closed convex cone K
can be obtained using metric entropy results, as σ 2 δ(K)/n = E0 kΠK (ξ)k2 is the risk
of the LS estimator µ̂ls (K) when the true vector is 0. This technique is used in [11] to
derive the bound (1.23).
If K ⊂ V where V is a subspace of dimension dV , then by monotonicity of the
statistical dimension (1.20) we have δ(TK,u ) ≤ δ(V ) = dV . In this case, (2.2) shows
that the constant 4 in [16, Proposition 3.1] can be reduced to 1.
2.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 Theorem 2.3 below. Recently, other general methods have been proposed [7, 15, 18],
but these methods did not provide oracle inequalities with leading constant 1.
Theorem 2.3. Let K be a closed convex subset of Rn , let µ ∈ Rn . Assume that
ξ ∼ N (0, σ 2 In×n ) and that for some u ∈ K, there exists t∗ (u) > 0 such that
sup

E

v∈K: |v−u|2 ≤t∗ (u)

ξ T (v − u) ≤

t∗ (u)2
.
2

Then for any x > 0, with probability greater than 1 − e−x ,
√
(t∗ (u) + σ 2x)2
2t2 (u) + 4σ 2 x
ls
2
2
kµ̂ (K) − µk − ku − µk ≤
≤ ∗
.
n
n

(2.5)

(2.6)

The proof of Theorem 2.3 is related to the isomorphic method [2] and the theory of
local Rademacher complexities in regression with random design [3, 12].
Proof. Let t = t∗ (u) and µ̂ = µ̂ls (K) for brevity. The concentration inequality for
suprema of Gaussian processes [5, Theorem 5.8] yields that on an event Ω(x) of probability greater than 1 − e−x ,
√
√
Z :=
sup
ξ T (v − u) ≤ E[Z] + tσ 2x ≤ t2 /2 + tσ 2x.
v∈K: |v−u|2 ≤t

/

9

On the one hand, if |µ̂ − u|2 ≤ t, then by (2.3) on Ω(x) we have
√
√
|µ̂ − µ|22 − |u − µ|22 ≤ 2ξT (µ̂ − u) − |µ̂ − u|22 ≤ 2Z ≤ t2 + 2tσ 2x ≤ (t + σ 2x)2 .
On the other hand, if |µ̂ − u|2 > t, then α := t/|µ̂ − u|2 belongs to (0, 1). If v =
αµ̂ + (1 − α)u then α(µ̂ − u) = v − u, by convexity of K we have v ∈ K and by
definition of α it holds that |v − u|2 = t. On Ω(x),
2ξT (µ̂ − u) − |µ̂ − u|22 = (2/α)ξ T (v − u) − t2 /α2 ,

≤ (2/α)Z − t2 /α2 = (2t/α)(Z/t) − t2 /α2 ,
√
≤ (Z/t)2 ≤ (t + σ 2x)2 ,

where we used 2ab − b2 ≤ a2 with b = t/α and a = Z/t. Thus (2.6) holds on Ω(x) for
both cases √
|µ̂ − u|2 ≤ t and |µ̂ − u|2 > t. Finally, inequality (u + v)2 ≤ 2u2 + 2v 2 yields
that (t + σ 2x)2 ≤ 2t2 + 4σ 2 x.
Note that condition (2.5) does not depend on the true vector µ, but only depends on
the vector u that appears on the right hand side of the oracle inequality. The left hand
side of (2.5) is the Gaussian width of C localized around u. This differs from the recent
analysis of Chatterjee [8] where the Gaussian width localized around µ is studied. An
advantage of considering the Gaussian width localized around u is that the resulting
oracle inequality (2.6) is sharp, i.e., with leading constant 1. Chatterjee [8] proved that
the Gaussian width localized around µ characterizes a deterministic quantity tµ such
that |µ̂ls (C) − µ|2 concentrates around tµ . This result from [8] grants both an upper
bound and a lower bound on |µ̂ls (C) − µ|2 , but it does not imply nor is implied by
a sharp oracle inequality such as (2.6) above. Thus, the result of [8] is of a different
nature than (2.6).
A strategy to find a quantity t∗ that satisfies (2.5) 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].
3. Sharp bounds in isotonic regression
We study in this section the performance of µ̂ls (Sn↑ ) using the general tools developed
in the previous section. We first apply Corollary 2.2. To do so, we need to bound from
above the statistical dimension of the tangent cone TSn↑ ,u . In fact, it is possible to
characterize the tangent cone TSn↑ ,u and to obtain a closed formula for its statistical
dimension.
Proposition 3.1. Let u ∈ Sn↑ and let k = k(u). Let (T1 , ..., Tk ) be a partition of
{1, ..., n} such that u is constant on each Tj , j = 1, ..., k. Then
TSn↑ ,u = S ↑ |T1 | × ... × S ↑ |Tk | .
Proof. Let TSn↑ ,u = T for brevity. If u is constant, then it is clear that T = Sn↑ so
we assume that u has at least one jump, i.e., k(u) ≥ 2. As Sn↑ is a cone we have
T = {v − tu|t ≥ 0, v ∈ Sn↑ }. Thus the inclusion TSn↑ ,u ⊂ S ↑ |T1 | × ... × S ↑ |Tk | is
straightforward. For the reverse inclusion, let x ∈ S ↑ |T1 | × ... × S ↑ |Tk | and let ε > 0 be
the minimal jump of the sequence u, that is, ε = mini=1,...,n−1:ui+1 >ui (ui+1 − ui ). If
t = |x|∞ /(4ε) then the vector v := tu+x belongs to Sn↑ , which completes the proof.

/

10

Pk(u) P|Tj | 1 Pk(u)
Using (1.19) and (1.22) we obtain δ(TSn↑ ,u ) = j=1
t=1 t ≤
j=1 log(e|Tj |). By
Jensen’s inequality, this quantity is bounded from above by k(u) log(en/k(u)). Applying Corollary 2.2 leads to the following result.
Theorem 3.2. For all n ≥ 2 and any µ ∈ Rn ,


en
σ 2 k(u)
LS
2
↑
2
.
log
Eµ kµ̂ (Sn ) − µk ≤ min ku − µk +
↑
n
k(u)
u∈Sn
Furthermore, for any x > 0 we have with probability greater than 1 − exp(−x)


2σ 2 k(u)
4σ 2 x
en
kµ̂LS (Sn↑ ) − µk2 ≤ min ku − µk2 +
+
log
.
↑
n
k(u)
n
u∈Sn

(3.1)

(3.2)

Let us discuss some features of Theorem 3.2 that are new. First, the estimator
µ̂ls (Sn↑ ) satisfies oracle inequalities both in deviation with exponential probability
bounds and in expectation, cf. (3.2) and (3.1), respectively. Previously known oracle
inequalities for the LS estimator over Sn↑ were only proved in expectation.
Second, both (3.1) and (3.2) are sharp oracle inequalities, i.e., with leading constant
1. Although sharp oracle inequalities were obtained using aggregation methods [4], this
is the first known sharp oracle inequality for the LS estimator µ̂ls (Sn↑ ).
Third, the assumption µ ∈ Sn↑ is not needed, as opposed to the result of [7].
2
en
log k(u)
in (3.1) is optimal for the LS estimator.
Last, the constant 1 in front of σ k(u)
n
To see this, assume that there exists an absolute constant c < 1 such that for all µ ∈ Sn↑
and µ̂ = µ̂ls (Sn↑ ),


en
cσ 2 k(u)
.
(3.3)
log
Eµ kµ̂ − µk2 ≤ min ku − µk2 +
↑
n
k(u)
u∈Sn
Set µ = 0. Thanks to (1.22), the left hand side of the above display is bounded from
below by σ 2 log(n)/n while while the right hand side is equal to cσ 2 log(en)/n. Thus,
2
en
log k(u)
for the estimator
it is impossible to improve the constant in front of σ k(u)
n
ls
↑
µ̂ (Sn ). However, it is still possible that for another estimator µ̂, (3.3) 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 µ̂ls (Sn↑ ). Let u∗ ∈ Sn↑ be
a minimizer of the right hand side of (3.1). Let k = k(u∗ ) and let (T1 , ..., Tk ) be a
partition of {1, ..., n} such that u∗ is constant on all Tj , j = 1, .., k. Given T1 , ..., Tk ,
consider the piecewise constant oracle
µ̂oracle ∈

argmin ky − uk2 ,

u∈WT1 ,...,Tk

where WT1 ,...,Tk is the linear subspace of all sequences that are constant on all Tj ,
j = 1, ..., k. This subspace has dimension k, so the estimator µ̂oracle satisfies
Eµ kµ̂oracle − µk2 =

min

u∈WT1 ,...,Tk

ku − µk2 +

σ2 k
σ2 k
≤ ku∗ − µk2 +
.
n
n

Thus, (3.1) can be interpreted in the sense that without the knowledge of T1 , ..., Tk ,
the performance of µ̂ls (Sn↑ ) is similar to that of µ̂oracle up to the factor log(en/k). Of

/

11

course, the knowledge of T1 , ..., Tk is not accessible in practice, so µ̂oracle is an oracle
that can only serve as a benchmark. This adaptive behavior of µ̂ls (Sn↑ ) was observed
in [7].
The following results are direct consequences of Theorem 2.3, Dudley integral bound
and the entropy bounds from [10, 8].
Corollary 3.3. There exists an absolute constant c > 0 such that the following holds.
Let n ≥ 2 and µ ∈ Rn . Assume that ξ ∼ N (0, σ 2 In×n ). Then for any x > 0, with
probability greater than 1 − exp(−x),
"

2/3 #
σ + V (u)
4σ 2 x
ls
2
2
↑
2
kµ̂ (Sn ) − µk ≤ min ku − µk + 2cσ
+
,
(3.4)
↑
σn
n
u∈Sn
where V (·) is defined in (1.1).
The novelty of Corollary 3.3 is twofold. First, the leading constant is 1. Although
model misspecification was considered in [19, 11], 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.4).
4. Convex regression and arbitrary design points
The goal of this section is to study univariate convex regression for non-equispaced
design points.
4.1. Parametric rate for any design if µ has few affine pieces
We now present a new argument to bound from above the statistical dimension of the
cone of convex sequences.
Theorem 4.1. Let n ≥ 3. Let x1 < ... < xn be real numbers and consider the cone
KxC1 ,...,xn defined in (1.7). Let g ∼ N (0, In×n ). Then
i
h
(4.1)
δ(KxC1 ,...,xn ) = E |ΠKCx ,...,xn (g)|22 ≤ 8 log(en).
1

KxC1 ,...,xn

for brevity. A convex sequence u = (u1 , ..., un ) ∈ K is first
Proof. Let K =
non-increasing and then nondecreasing, that is, there exists m ∈ {1, ..., n} such that
u1 ≥ u2 ≥ ... ≥ um ≤ um+1 ≤ ... ≤ un , hence the sequence u is unimodal. Thus,
if Km , m = 1, ..., n are the sets defined in (1.9), then K ⊂ U = ∪m=1,...,n Km . Using
(1.19), (1.20) and (1.22) we obtain
↑
↓
δ(Km ) ≤ δ(Sm
× Sn−m
) ≤ log(em) + log(e(n − m)) ≤ 2 log(en).

By (1.17), almost surely we have
0 ≤ |ΠK (g)|2 =

sup
u∈K:|u|2 ≤1

gT u ≤

max

sup

m=1,...,n u∈K :|u| ≤1
m
2

gT u =

max |ΠKm (g)|2 .

m=1,...,n

Using (2.4) and the union bound, for all x > 0, we have
p with probability at least
1−e−x the inequality |ΠK (g)|22 ≤ maxm=1,...,n δ(Km )1/2 + 2(x + log n). As (a+b)2 ≤
2a2 + 2b2 , on the same event of probability at least 1 − e−x we have
|ΠK (g)|22 ≤ 2 max δ(Km ) + 4(x + log n) ≤ 4 log(en) + 4(x + log n).
m=1,...,n

/

12

Integration of this probability bound completes the proof.
Remarkably, this bound on the statistical dimension does not depend on the design
points x1 , ..., xn . Furthermore, the bound (4.1) improves upon (1.23) as the exponent
5/4 is reduced to 1. (4.1)
Proposition 4.2. Let n ≥ 3, and let u be an element of the cone KxC1 ,...,xn defined in
(1.7). The statistical dimension of the tangent cone at u satisfies


en
δ(TKCx ,...,xn ,u ) ≤ 8q(u) log
.
1
q(u)
Proof. Let q = q(u). Let (T1 , ..., Tq ) be a partition of {1, ..., n} such that u is affine
on each Tj , j = 1, ..., q. Let x ∈ KxC1 ,...,xn . A convex sequence minus an affine sequence
is convex, thus for all j = 1, ..., q, (x − u)Tj is convex in the sense that it belongs to
KxCi :i∈Tj . Thus
TKCx ,...,xn ,u ⊂ C := KxCi :i∈T1 × KxCi :i∈T2 × ... × KxCi :i∈Tq .
1

Using (1.20), (1.19), Theorem 4.1 and Jensen’s inequality we have


 
q
q


X
X
e
en


8 log(e|Tj |) ≤ 8q log
|Tj | = 8q log
.
δ TKCx ,...,xn ,u ≤ δ(C) ≤
1
q
q
j=1
j=1
Combining Corollary 2.2 and Proposition 4.2 yields the following.
Theorem 4.3. Let n ≥ 3 and µ ∈ Rn . Let x1 < ... < xn be real numbers. Then for
any x > 0, the estimator µ̂ = µ̂LS (KxC1 ,...,xn ) satisfies
kµ̂ − µk2 ≤



16σ 2 q(u)
4σ 2 x
en
ku − µk2 +
+
log
C
n
q(u)
n
u∈Kx1 ,...,xn
min

with probability greater than 1 − exp(−x).
Theorem 4.3 does not depend on the design points x1 , ..., xn . In particular, Theorem 4.3 and the corresponding result in expectation hold for non-equispaced design
points and design points that can be arbitrarily close to each other. This improves
upon the oracle inequality (1.5) proved in [11, 7] where C is strictly greater than 1
and depends on the design points through the ratio (1.8). Thanks to Corollary 2.2,
these oracle inequalities hold in deviation with exponential probability bounds and in
expectation for any µ ∈ Rn , whereas previously known oracle inequalities from [11, 7]
only hold in expectation under the additional assumption that µ ∈ KxC1 ,...,xn .
4.2. Worst-case design points in convex regression and the rate n−2/3
The nonparametric rate for estimation of convex sequences is of order n−4/5 for equispaced design points. This was established in [11] using metric entropy bounds. The
following result combines the metric entropy bounds from [11] with Theorem 2.3.

/

13

Corollary 4.4. There exist absolute constants κ, C > 0 such that the following holds.
Let n ≥ 3 and µ ∈ Rn . Assume that ξ ∼ N (0, σ 2 In×n ). Then for any x > 0, with
probability greater than 1 − exp(−x),
ls

kµ̂

(Snc )

#
2/5
C Ru σ 4
log(en)
16σ 2 x
.
+
− µk ≤ minc ku − µk +
4/5
u∈Sn
n
n
2

"

2

where Ru = max(σ, min({ku − τ k, τ ∈ Rn and τ is affine})), and the minimum on the
right hand side is taken over all u ∈ Snc such that
2
nRu
≥ κ log(en)5/4 ,

(4.2)

Thanks to the metric entropy bounds of [11], Corollary 4.4 holds for equispaced
design points or design points that are almost equispaced in the sense that the ratio
(1.8) 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.
Theorem 4.5. Let V > 0. There exists design points x1 < ... < xn that depend on V
such that for any estimator µ̂,
 2 1/3 !
V
2
2
sup
Pµ kµ̂ − µk ≥ Cσ
≥ c,
σ 2 n2
↑
µ∈KC
∩Sn
: µn −µ1 ≤2V
x1 ,...,xn

where c, C > 0 are absolute constants.
The intuition behind this result is the following. Let µ = (µ1 , ..., µn )T ∈ Sn↑ be
−µi
strictly increasing and let ǫ := 12 ∧ mini=2,...,n−1 µµii+1
−µi−1 . If we define the design points
x1 < ... < xn by xi = −ǫi for all i = 1, ..., n then µ ∈ KxC1 ,...,xn (this statement
is made rigorous in the proof of Theorem 4.5). That is, for any strictly increasing
sequence µ, there are geometrically spaced design points x1 < ... < xn such that
µ = (f (x1 ), ..., f (xn ))T for some convex function f . As explained in the following proof,
this observation yields that the minimax lower bound over Sn↑ implies a minimax lower
bound over KxC1 ,...,xn for a specific choice of design points x1 , ..., xn .
Proof of Theorem 4.5. For any u ∈ Sn↑ , let V (u) = un − u1 . It was proved in [4,
Proposition 4 and Corollary 5] that for some integer M ≥ 2, there exist µ0 , ..., µM ∈ Sn↑
such that V (µ̂j ) ≤ V and
Cσ 2
kµj − µk k ≥
4



V2
σ 2 n2

1/3

,

log M
n
kµj − µ0 k ≤
2
2σ
16

(4.3)

for all distinct j, k ∈ {0, ..., M } and some absolute constant C > 0. The quantity
n
2
2
2σ2 kµj − µ0 k is Kullback-Leibler divergence from N (µj , σ In×n ) to N (µ0 , σ In×n ).
T
Define v = (v1 , ..., vn ) by vi = iV /n for all i = 1, ..., n so that V (v) ≤ V and v is
strictly increasing. We define u0 , ..., uM by uj = µj + v so that u0 , ..., uM are strictly
increasing. Furthermore, since µj − µk = uj − uk it is clear that (4.3) still holds if

/

14

µj , µk are replaced by uj , uk . Applying [17, Theorem 2.7] yields that for any estimator
µ̂,
 2 1/3 !
V
2
2
≥ c,
sup Puj kµ̂ − µk ≥ Cσ
σ 2 n2
j=0,...,M
where c, C > 0 are absolute constants.
Let ǫ :=

1
2

∧ minj=1,...,M mini=2,...,n−1

uji+1 −uji
uji −uji+1

. Since the sequences u0 , ..., uM are

strictly increasing we have ǫ > 0. Define the design points x1 < ... < xn by xi = −ǫi
for all i = 1, ..., n. Then for all j = 0, ..., M we have
uj − uji
xi+1 − xi
= ǫ ≤ i+1
xi − xi−1
uji − uji+1
for all i = 2, ..., n − 1, and by (1.7) this implies that uj ∈ KxC1 ,...,xn . It remains to show
that V (uj ) ≤ 2V , which is a consequence of V (µj ) ≤ V and V (v) ≤ 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 KxC1 ,...,xn ⊂ U holds for any
design points x1 < ... < xn . Intuitively, this inclusion means that convexity brings
more structure than unimodality. Theorem 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 Theorems A.4 and A.5.
Theorem 4.6. Let µ ∈ Rn and let x1 < ... < xn be any real numbers. Then for all
x > 0, with probability at least 1 − 2e−x , the estimator µ̂ = µ̂ls (KxC1 ,...,xn ) satisfies



p
σ  q
en
kµ̂ − µk ≤ min ku − µk ∨ √ 2 (k(u) + 1) log( k(u)+1 ) + 3σ 2(x + log n) .
u∈U
n

Theorem 4.7. There exists an absolute constant c > 0 such that the following holds.
Let µ ∈ Rn and let x1 < ... < xn be any real numbers. Then for all x > 0, with
probability at least 1 − 2e−x , the estimator µ̂ = µ̂ls (KxC1 ,...,xn ) satisfies
"

kµ̂ − µk ≤ min ku − µk + 2cσ
u∈U



σ + V (u)
σn

1/3 #

+

2(2 +

√ p
2)σ x + log(en)
√
.
n

The proofs of Theorems 4.6 and 4.7 are given in Appendix A.3. Theorem 4.7 shows
that the convex LS estimator achieves a rate of order n−2/3 for any design points.
Together, Theorems 4.5 and 4.7 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
R(V ) :=

sup

inf

sup

x1 <...<xn µ̂ µ∈KC
x1 ,...,xn : V (µ)≤V

Eµ [kµ̂ − µk2 ],

V > 0,

where the first supremum is taken over all x1 , ..., xn ∈ R such that x1 < ... < xn and
the infimum is taken over all estimators that may depend on x1 , ..., xn (for instance,
the convex LS estimator µ̂ls (KxC1 ,...,xn )) depends on the design points). The quantity
R(V ) represents the minimax risk over all possible univariate design points, and over

/

15

all convex sequences. By taking u = µ in Theorem 4.7 and by integration, we obtain
that
2/3

σ+V
ls
2
2
C
sup
sup
Eµ [kµ̂ (Kx1 ,...,xn ) − µk ] ≤ Cσ
σn
x1 <...<xn µ∈KC
x ,...,x : V (µ)≤V
1

n

for some absolute constant C > 0. On the other hand, Theorem 4.5 and Markov
V 2/3
)
for some absolute constant C ′ > 0. In
inequality yield that R(V ) ≥ C ′ σ 2 ( σn
summary,

 2/3
2/3
σ+V
V
′ 2
2
Cσ
≤ R(V ) ≤ Cσ
.
σn
σn

This establishes that the nonparametric rate of univariate convex regression over all
possible design points is of order n−2/3 provided that V ≥ σ. This rate is substantially
slower than the rate n−4/5 observed by Guntuboyina and Sen [11] 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 KxC1 ,...,xn ⊂ U holds. The convex
constraints that define KxC1 ,...,xn 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 .
5. Estimation of the projection of the true parameter
Let K be a subset of Rn . If the unknown regression vector µ lies in K, we say that
the model is well-specified. If µ ∈ K, an estimator µ̂ enjoys good performance if the
squared error
kµ̂ − µk2
is small, either in expectation or with high probability. If µ ∈
/ K, we say that the
model is misspecified. In that case, several natural quantities are of interest to assess
the performance of an estimator µ̂. The regret of order 1 and the regret of order 2 of
an estimator µ̂ are defined by
R2 (µ̂) := kµ̂ − µk2 − min ku − µk2 ,
u∈K

R1 (µ̂) := kµ̂ − µk − min ku − µk.
u∈K

If µ̂ ∈ K, it is clear that R1 (µ̂) ≥ 0, R2 (µ̂) ≥ 0 and that R1 (µ̂)2 ≤ R2 (µ̂) by using the
basic inequality (a − b)2 ≤ |a2 − b2 | for all a, b ≥ 0.
If the set K is closed and convex and µ̂ is valued in K, another quantity of interest
is the estimation error with respect to the projection of µ onto K:
kµ̂ − ΠK (µ)k2 .

(5.1)

The triangle inequality yields |kµ̂−µk−minu∈K ku−µk| ≤ kµ̂−ΠK (µ)k. Furthermore,
if µ̂ is valued in K and K is convex, then (1.13) with y replaced by µ and u replaced
by µ̂ can be rewritten as
kµ̂ − ΠK (µ)k2 ≤ kµ̂ − µk2 − kµ − ΠK (µ)k2 ,

for all µ̂ ∈ K.

/

16

Thus, if K is convex, for any estimator µ̂ valued in K we have R12 (µ̂) ≤ kµ̂−ΠE (µ)k2 ≤
R2 (µ̂). The following Proposition sums up the relationship between the quantity (5.1)
and the regrets of order 1 and 2 in the case of a closed convex set K.
Proposition 5.1 (Misspecification inequalities). Let µ ∈ Rn and let K ⊂ Rn be a
closed convex set. Then minu∈K ku − µk = kΠK (µ) − µk and for any µ̂ ∈ K, the
following holds almost surely
2

(kµ̂ − µk − kΠK (µ) − µk) ≤ kµ̂ − ΠK (µ)k2 ≤ kµ̂ − µk2 − kΠK (µ) − µk2 .

Estimation of ΠK (µ) by the LS estimator µ̂ls (K) has been considered in [19, Section
4] for K = Sn↑ , and in [11, Section 6] for K = Snc . Proposition 5.1 above shows that for
any quantity r(K) and any estimator µ̂ valued in a closed convex set K, we have
kµ̂ − µk2 ≤ kΠK (µ) − µk2 + r(K) implies

kµ̂ − ΠK (µ)k2 ] ≤ r(K),

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 µ onto K. For instance,
if K = Sn↑ , Theorem 3.2 and Corollary 3.3 with u = ΠK (µ) imply the following. If
µ̂ = µ̂ls (Sn↑ ) and π = ΠSn↑ (µ) then


σ 2 k(π)
en
2
P kµ̂ − πk ≤
≥ 1 − e−x ,
log
n
k(π)
!

2/3
2
σ
+
V
(π)
4σ
x
P kµ̂ − πk2 ≤ 2cσ 2
≥ 1 − e−x ,
+
σn
n
for any µ ∈ Rn , where c > 0 is an absolute constant and V (·) is the total variation
defined in (1.1). That is, in the misspecified case, the LS estimator µ̂ls (Sn↑ ) estimates π
at the parametric rate if π has few constant pieces, and at the nonparametric rate n−2/3
otherwise. Similar conclusions can be drawn in convex regression from Theorem 4.3 and
Corollary 4.4. If µ̂ = µ̂ls (Snc ) and π = ΠSnc (µ) we have


en
4σ 2 x
16σ 2 q(π)
≥ 1 − e−x ,
log
+
P kµ̂ − πk2 ≤
n
q(π)
n
!
2/5
C Rπ σ 4
log(en) 16σ 2 x
2
P kµ̂ − πk ≤
≥ 1 − e−x ,
+
n
n4/5
provided that (4.2) holds with u replaced by π.
Finally, the following Corollary is an outcome of Proposition 5.1, Proposition 2.1,
and Theorem 2.3.
n
Corollary 5.2. Let K be
√ a closed convex set and let µ ∈ R . Then almost surely,
ls
kµ̂ (K) − ΠK (µ)k ≤ (σ/ n)|ΠTK,ΠK (µ) (g)|2 where g = (1/σ)ξ. Furthermore, if t∗ > 0
is such that
t2
E
sup
ξ T (v − ΠK (µ)) ≤ ∗ ,
2
v∈K: |v−ΠK (µ)|2 ≤t∗

then for all x > 0, with probability at least 1 − e−x we have
√
|µ̂ls (K) − ΠK (µ)|2 ≤ (t∗ + σ 2x).
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.3). Indeed, oracle inequalities with leading constant 1 yield an upper bound on the
estimation error kµ̂ls (K) − ΠK (µ)k for any closed convex set K.

/

17

Appendix A: From unimodal to convex regression
In this section, we develop the tools needed to study unimodal regression and to prove
Theorems 4.6 and 4.7 in convex regression. Theorems 4.6 and 4.7 are similar to Theorems A.4 and A.5 in unimodal regression. Their proofs share the same fundamental
argument.
A.1. Sharp oracle inequalities in unimodal regression
The following result improves the risk bound (1.11) by reducing the exponent 3/2 to
1, proving that the lower bound (1.10) is actually tight.
Theorem A.1. Let µ ∈ U and let k = k(µ). If ξ ∼ N (0, σ 2 In×n ) then for all x,

p
2σ q
en
) + 2(x + log n)
kµ̂ls (U) − µk ≤ √
(k + 1) log( k+1
n

holds with probability at least 1 − e−x .

Let Tm,u be the tangent cone of Km at some u ∈ U, that is,
Tm,u := closure{t(x − u)|t ≥ 0, x ∈ Km }.
For any u ∈ U, define the set Wu and the random variable Yu by
Yu :=

Wu := ∪m=1,...,n Tm,u ,

sup

ξ T v.

(A.1)

v∈Wu :|v|2 ≤1

Our proof of Theorem A.1 relies on an upper bound on the statistical dimension of the
above tangent cones and the concentration of of the random variable Yu .
Lemma A.2. Let u ∈ U p
and x > 0. With probability at least 1 − e−x we have Yu ≤
σ maxm=1,...,n δ(Tm,u ) + σ 2(x + log n).
en
).
Lemma A.3. If u ∈ U then maxm=1,...,n δ(Tm,u ) ≤ (k(u) + 1) log( k(u)+1

Lemma A.2 and Lemma A.3 are proved in Appendix A.2 below. Lemma A.2 is proved
using the union bound and (2.4) applied to the cones T1,u , ..., Tn,u , while Lemma A.3
is a straightforward consequence of (1.19), (1.20) and (1.22). The two Lemmas above
yield that


q
p
en
P Yu ≤ σ (k(u) + 1) log( k(u)+1
) + σ 2(x + log n) ≥ 1 − e−x .
(A.2)

We a now ready to prove Theorem A.1.

Proof of Theorem A.1. Let µ̂ = µ̂ls (U) and R̂ = |µ̂−µ|2 . Inequality (1.15) with u = µ
can be rewritten as R̂2 ≤ 2ξT (µ̂ − µ). It is clear that (1/R̂)(µ̂ − µ) has norm 1 and
belongs to V∗ := ∪m=1,...,n Tm,µ . Thus
R̂ =

R̂2
R̂

≤

2ξT (µ̂ − µ)
R̂

≤2

sup
v∈Wµ :|v|2 ≤1

The concentration inequality (A.2) completes the proof.

ξ T v ≤ 2Yµ .

/

18

During the writing of the revision of the present article in which Theorem A.1 was
introduced, we became aware of a similar result by Flammarion et al. [9] obtained
independently in the context of statistical seriation. Interestingly, Theorem A.1 and the
result of Flammarion et al. [9] are proved using different techniques. Theorem A.1 is an
outcome of the concentration inequality (2.4) and of upper bounds on the statistical
dimension of tangent cones, while Flammarion et al. [9] prove an oracle inequality
using metric entropy bounds and the variational representation studied in [8, 6]. An
advantage of the proof presented above is that the numerical constants of Theorem A.1
are explicit and reasonably small.
The proof of Theorem A.1 can be slightly modified to yield an oracle inequality. The
following Theorems recover the results of Flammarion et al. [9].
Theorem A.4. Let µ ∈ Rn . Furthermore, if ξ ∼ N (0, σ 2 In×n ) then for all x > 0, we
have


p
2σ q
ls
en
kµ̂ (U) − µk ≤ min ku − µk + √
(k(u) + 1) log( k(u)+1 ) + 2(x + log n)
u∈U
n
with probability at least 1 − e−x .

Proof of Theorem A.4. Let µ̂ = µ̂ls (U) and let u be a minimizer of the right hand side.
We first prove that almost surely,


2Yu
.
(A.3)
kµ̂ls (U) − µk ≤ min ku − µk + √
u∈U
n
Let R̂ := |µ̂−µ|2 and R := |u−µ|2 . The vector θ :=

µ̂−u
R̂+R

belongs to the set Wu defined

in (A.1) and θ has norm at most one because of the triangle inequality |µ̂−u|2 ≤ R̂+R.
Inequality (1.15) can be rewritten as R̂2 − R2 ≤ 2ξT (µ̂ − u) and thus
R̂ − R =

R̂2 − R2
R̂ + R

≤

2ξT (µ̂ − u)
R̂ + R

= 2ξT θ ≤ 2Yu .

We have proved (A.3). Applying (A.2) completes the proof of the Theorem.
The oracle inequality of Theorem A.4 is sharp (that is, it has leading constant
1), but it is an oracle inequality with respect to the loss k · k rather than to the
squared loss k · k2 . An oracle inequality with respect to the loss k · k2 is stronger than
an oracle inequality with respect to the loss k · k. Indeed, if an estimator µ̂ satisfies
2
kµ̂ − µk2 √
≤ min√
u∈E ku − µk + ε for some set E and some ε > 0, then the inequality
√
a + b ≤ a + b for all a, b ≥ 0 yields kµ̂ − µk ≤ minu∈E ku − µk + ε1/2 .
An oracle inequality similar to that of Theorem A.4 can be obtained for the nonparametric rate n−2/3 .
Theorem A.5. There exists an absolute constant c > 0 such that the following holds.
Let µ ∈ Rn . If ξ ∼ N (0, σ 2 In×n ) then for all x > 0, we have
"
√ p

1/3 #
2(2 + 2)σ x + log(en)
σ + V (u)
ls
√
kµ̂ (U) − µk ≤ min ku − µk + 2cσ
+
u∈U
σn
n
with probability at least 1 − e−x , where V (·) is defined in (1.1).

/

19

Proof. Let µ̂ = µ̂ls (U) and let u be a minimizer of the right hand side of the oracle
inequality. Define
1/3

V (u)
n1/6 ,
(A.4)
t := cσ 1 +
σ
where c > 0 is the absolute constant from (B.1). Define the random variables Z1 , ..., Zm
by
2ξT (v − u)
,
m = 1, ..., n.
(A.5)
sup
Zm :=
v∈Km :|v−u|2 >t |v − u|2
We will prove that the oracle inequality of the Theorem holds on the event
p
p
max Zm ≤ t + 2σ log(en) + 2(x + log n).
m=1,...,n

(A.6)

Let R̂ = |µ̂ − µ|2 and let R = |u − µ|2 . If |µ̂ − u|2 ≤ t then by the triangle inequality
R̂ − R ≤ |u − µ̂|2 ≤ t and the oracle inequality of the Theorem holds. On the other
hand, if |µ̂ − u|2 > t then using (1.15) and the triangle inequality we have
R̂ − R =

R̂2 − R2
R̂ + R

≤

2ξT (µ̂ − u)
R̂ + R

≤

2ξT (µ̂ − u)
≤ max 2Zm .
m=1,...,n
|µ̂ − u|2

On the event (A.6),
√ p the right hand side of the previous display is bounded from above
by 2t + 2(2 + 2) x + log(en) and the oracle inequality of the Theorem holds.
It remains to bound the probability of the event (A.6). 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,
p
p
Zm ≤ E[Zm ] + σ 2(x + log n),
max Zm ≤ max E[Zm ] + σ 2(x + log n).
m=1,...,n

m=1,...,n

It remains to bound E[Zm ] from above.

Lemma A.6. For all m = 1, ..., n, the variable Zm defined in (A.5) satisfies
p
E[Zm ] ≤ t + 2 log(en).

The proof of Lemma A.6 is given in Appendix A.2. This proves that the event (A.6)
has probability at least 1 − e−x .

A.2.

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

Proof of Lemma A.2. Using (1.17) we have Yu = maxm=1,...,n |ΠTm,u (ξ)|2 . We apply
(2.4) to L = Tm,u for all m = 1, ..., n. The union bound completes the proof.
Proof of Lemma A.3. Let m = 1, ..., n, k = k(u) and let (T1 , ..., Tk ) be a partition
of {1, ..., n} such that u is constant on each Tl and Tl is convex for all l = 1, ..., k.
Let l∗ ∈ {1, ..., k} be the unique integer such that m ∈ Tl∗ , and let T ∗ = Tl∗ . Let
v ∈ Km . Then for all l < l∗ , the sequence (v − u)Tl is non-increasing and for all
l > l∗ , the sequence (v − u)Tl is nondecreasing. Furthermore, if A = T ∗ ∩ {1, ..., m}
and B = T ∗ ∩ {m + 1, ..., n}, the sequence (v − u)A is non-increasing and the sequence
(v − u)B is nondecreasing. We have proved the inclusion
↓
↓
↓
↑
↑
↑
Tm,u ⊂ C := S|T
× ... × S|T
× S|A|
× S|B|
× S|T
× ... × S|T
.
1|
k|
l∗ −1 |
l∗ +1 |

/

20

where for all integer q ≥ 1, Sq↑ is the cone of nondecreasing sequences in Rq and Sq↓ is
the cone of non-increasing sequences in Rq . Using (1.20), (1.19) and (1.22) we obtain
X
δ(Tm,u ) ≤ δ(C) ≤ log(e|A|) + log(e|B|) +
log(e|Tl |).
l=1,...,k:l6=l∗

Using Jensen’s inequality with the fact that |A|+|B|+
en
δ(Tm,u ) ≤ (k + 1) log k+1
.

P

l=1,...,k:l6=l∗

|Tl | = n, we obtain

Proof of Lemma A.6. Let m = 1, ..., n be fixed. As u ∈ U, there exists mu ∈ {1, ..., n}
such that u ∈ Kmu . Define k := min(m, mu ) and j := max(m, mu ). Let T := {1, ..., k},
E := {k + 1, ..., j − 1} and S := {j, ..., n}. Then for all v ∈ Km , by definition of T, E
and S we have
↓
↓
v T ∈ S|T
| , uT ∈ S|T | ,

↑
↑
v S ∈ S|S|
, uS ∈ S|S|
,

↑
↓
(v − u)E ∈ S|E|
∪ S|E|
.

Thus, the quantity E[Zm ] is bounded from above by
E

sup

(1/|v − u|2 ) ξTT (v − u)T

(A.7)

(1/|v − u|2 ) ξTS (v − u)S

(A.8)

v∈Km :|v−u|2 >t

+ E

sup

v∈Km :|v−u|2 >t

+ E

max

sup

↓
↑
} x∈L:|x|2 ≤1
,S|E|
L∈{S|E|

ξ TE x.

(A.9)

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.9) is bounded
↑
↓
from above by δ(S|E|
)1/2 + δ(S|E|
)1/2 ≤ 2 log(e|E|)1/2 ≤ 2 log(en)1/2 . We now bound
(A.7) from above, while (A.8) can be bounded similarly. For all v ∈ Km such that
|v − u|2 > t, if α = t/|v − u|2 we have
(1/|v − u|2 )ξ TT (v − u)T = (α/t)ξ TT (v − u)T = (1/t)ξ TT (αv + (1 − α)u − u)T
↓
and α ∈ [0, 1]. By convexity we have θ = αv T + (1 − α)uT ∈ S|T
| and

|θ − uT |2 = α|v T − uT |2 ≤ α|v − u|2 = t.
Thus, (A.7) is bounded from above by
1
E
sup
ξ T (θ − uT ).
t θ∈S ↓ :|θ−uT |2 ≤t T
|T |

By (B.1), the previous display is bounded from above by t/2. Finally, we have
p
E[Zm ] ≤ (A.7) + (A.8) + (A.9) ≤ t/2 + t/2 + 2 log(en).
A.3.

Proofs of Theorems 4.6 and 4.7

Proof of Theorem 4.6. Let u ∈ U be a unimodal sequence. Define the random variable
G := ξ T (u − µ)/|u − µ|2

if u 6= µ and G = 0 otherwise.

(A.10)

/

21

Let Yu be defined in (A.1). Let R̃ := |µ̂ − µ|2 and R := |u − µ|2 . We first prove that
almost surely,


2Yu + G
√
(A.11)
kµ̂ − µk ≤ max ku − µk,
n
It is enough to prove that R̃ > R implies R̃ ≤ 2Yu + G. Assume that R̃ > R. Inequality
(2.3) yields R̃2 ≤ ξ T (µ̂ − µ) and thus
R̃2 ≤ ξT (µ̂ − µ) =

ξT (µ̂ − u)
|µ̂ − u|2 + G|u − µ|2 ≤ Yu |µ̂ − u|2 + GR.
|µ̂ − u|2

where we used that µ̂ ∈ U since a convex sequence is unimodal. We have R < R̃ and
by the triangle inequality, |µ̂ − u|2 ≤ R̃ + R < 2R̃, which proves that R̃2 ≤ 2Yu R̃ + GR̃.
Dividing by R̃ completes the proof of (A.11).
We now prove the oracle
p inequality. Since G is centered Gaussian with variance at
most σ 2 we have P(G > σ 2(x + log n)) ≤ e−x /n ≤ e−x . The concentration inequality
(A.2) and the union bound completes the proof.
Proof of Theorem 4.7. Let u be a minimizer of the right hand side. Let R̃ := |µ̂ − µ|2
and R := |u − µ|2 . Define t > 0 by (A.4) and define the random variables Z1 , ..., Zn by
(A.5). We first prove that almost surely,


R̃ ≤ max R + t, 2 max Zm + G .
(A.12)
m=1,...,n

It is enough to prove that R̃ > R + t implies R̃ ≤ 2 maxm=1,...,n Zm + G. If R̃ > R + t
then by the triangle inequality, |µ̂ − u|2 ≥ R̃ − R > t + R − R = t, so that by (2.3) we
have


ξ T (µ̂ − u)
ξ T (u − µ)
T
2
R̃ ≤ ξ (µ̂ − µ)
|µ̂ − u|2 +
R≤
max Zm |µ̂ − u|2 + GR,
m=1,...,n
|µ̂ − u|2
|u − µ|2
where G is the random variable (A.10). If R̃ > R + t we have R ≤ R̃ and |µ̂ − u|2 ≤
R̃ + R ≤ 2R̃, so that dividing both sides of the previous display by R̃ yields that
R̃ ≤ 2 maxm=1,...,n Zm + G. The proof of (A.12) is complete.
We now prove the probability
pestimate. Since G is centered Gaussian with variance
at most σ 2 we have P(G > σ 2(x + log(en))) ≤ e−x /(en) ≤ e−x . In the proof of
Theorem A.5, we showed that the event (A.6) has probability at least 1 − e−x . The
union bound completes the proof.
Appendix B: Proof of Corollary 3.3 and Corollary 4.4
The following result is established in Chatterjee [8].
Lemma B.1 ([8]). There exists an absolute constant c > 0 such that the following
holds. Let u ∈ Sn↑ and ξ ∼ N (0, σ 2 In×n ). Then
E

sup
↑
θ∈Sn
:|θ−u|2 ≤1

ξ T (θ − u) ≤

t2
2

1/3

V (u)
n1/6 .
for all t ≥ cσ 1 +
σ

Proof of Corollary 3.3. Combining (B.1) and Theorem 2.3 completes the proof.

(B.1)

/

22

Proof of Corollary 4.4. Let u be a minimizer of the right hand side of the oracle inequality of Corollary 4.4. By rescaling we may assume that σ = 1. Let R = Ru . As
in the proof of Corollary 3.3, we apply Theorem 2.3. Let r > 0. Let S(u, r) = {v ∈
Snc , kv − uk ≤ r}. By Dudley entropy bound (cf. [5, Corollary 13.2]), we obtain
E

ξT (v − u)
√
≤ 12
n
v∈S(u,r)
sup

Z

0

r

p
log M (ǫ, S(u, r), k · k)dǫ,

≤ κ̄ log(en)5/8 r3/4 (r2 + R2 )1/8 ,

where κ̄ > 0 is an absolute constant, M (ǫ, S(u, r), k · k) is the ǫ-entropy of S(u,
√r) in
the k · k norm, and the second inequality is proved in [11, (25)]. The constant 1/ n on
the left hand side due to the fact that the Gaussian process is normalized
√ with respect
to the√metric k · k, i.e., for all vectors v, v ′ , kv − v ′ k2 = E[(ξ T (v − v ′ )/ n)2 ]. Let now
t = r n. After rearranging, the previous inequality becomes
E
Let

T

sup
c : |v−u|2 ≤t
v∈Sn
2

5/8 1/8 3/4

ξ (v − u) ≤ κ̄ log(en)

n

t



t2
+ R2
n

1/8

.

(B.2)

4/5 p

t∗ = 2κ̄21/8
log(en)R1/5 n1/10 ,

and choose the absolute constant κ := 4κ̄2 21/4 . With this choice of κ and t∗ , (4.2) is
equivalent to t2∗ /n ≤ R2 . Thus, for t = t∗ , the right hand side of (B.2) does not exceed
3/4

κ̄21/8 log(en)5/8 n1/8 t∗

≤ t2∗ /2.

Applying Theorem 2.3 completes the proof of Corollary 4.4.
Acknowledgement. The author thanks Alexandre Tsybakov for helpful comments
and Philippe Rigollet for informing him of the unimodal regression result of Flammarion et al. [9]. This work was supported by GENES and by the French National
Research Agency (ANR) under the grants IPANEMA (ANR-13-BSH1-0004-02), and
Labex ECODEC (ANR - 11-LABEX-0047).
References
[1] Dennis Amelunxen, Martin Lotz, Michael B McCoy, and Joel A Tropp. Living on
the edge: Phase transitions in convex programs with random data. Information
and Inference, 2014.
[2] Peter L Bartlett and Shahar Mendelson. Empirical minimization. Probability
Theory and Related Fields, 135(3):311–334, 2006.
[3] Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson.
Local
rademacher complexities. Ann. Statist., 33(4):1497–1537, 08 2005. . URL
http://dx.doi.org/10.1214/009053605000000282.
[4] Pierre C. Bellec and Alexandre B. Tsybakov. Sharp oracle bounds for monotone
and convex regression through aggregation. Journal of Machine Learning Research,
16:1879–1892, 2015. URL http://jmlr.org/papers/v16/bellec15a.html.
[5] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, 2013.

/

23

[6] Sabyasachi Chatterjee and John Lafferty. Adaptive risk bounds in unimodal regression. arXiv preprint arXiv:1512.02956, 2015.
[7] Sabyasachi Chatterjee, Adityanand Guntuboyina, and Bodhisattva Sen. On risk
bounds in isotonic and other shape restricted regression problems. arXiv preprint
arXiv:1311.3765, 2013. To appear in Annals of Statistics.
[8] Sourav Chatterjee.
A new perspective on least squares under convex constraint.
Ann. Statist., 42(6):2340–2381, 12 2014.
.
URL
http://dx.doi.org/10.1214/14-AOS1254.
[9] Nicolas Flammarion, Cheng Mao, and Philippe Rigollet. Optimal rates of statistical seriation. arXiv preprint, 2016.
[10] Fuchang Gao and Jon A. Wellner.
Entropy estimate for highdimensional monotonic functions.
Journal of Multivariate Analysis, 98(9):1751 – 1764, 2007.
ISSN 0047-259X.
.
URL
http://www.sciencedirect.com/science/article/pii/S0047259X06001412.
[11] Adityanand Guntuboyina and Bodhisattva Sen. Global risk bounds and adaptation in univariate convex regression. Probability Theory and Related Fields, pages
1–33, 2013.
[12] Vladimir Koltchinskii. Local rademacher complexities and oracle inequalities
in risk minimization.
Ann. Statist., 34(6):2593–2656, 12 2006. .
URL
http://dx.doi.org/10.1214/009053606000001019.
[13] Mary Meyer and Michael Woodroofe. On the degrees of freedom in shape-restricted
regression. Annals of Statistics, pages 1083–1104, 2000.
[14] Samet Oymak and Babak Hassibi. Sharp mse bounds for proximal denoising.
arXiv preprint arXiv:1305.2714, 2013.
[15] Yaniv Plan, Roman Vershynin, and Elena Yudovina. High-dimensional estimation
with geometric constraints. arXiv preprint arXiv:1404.3749, 2014.
[16] A.B. Tsybakov. Aggregation and minimax optimality in high-dimensional estimation. In Proceedings of the International Congress of Mathematicians, Seoul, 2014.
To appear.
[17] Alexandre B. Tsybakov. Introduction to nonparametric estimation. Springer, New
York, 2009.
[18] Roman Vershynin. Estimation in high dimensions: a geometric perspective. arXiv
preprint arXiv:1405.5103, 2014.
[19] Cun-Hui Zhang. Risk bounds in isotonic regression. The Annals of Statistics, 30
(2):528–555, 2002.

