Adaptive Risk Bounds in Unimodal Regression
Sabyasachi Chatterjee and John Lafferty

arXiv:1512.02956v5 [math.ST] 9 May 2017

Department of Statistics
The University of Chicago
May 10, 2017

Abstract: We study the statistical properties of the least squares estimator in unimodal sequence estimation. Although closely related to isotonic regression, unimodal regression has
not been as extensively studied. We show that the unimodal least squares estimator is adaptive
in the sense that the risk scales as a function of the number of values in the true underlying
sequence. Such adaptivity properties have been shown for isotonic regression by Chatterjee
et al. (2015b) and Bellec (2016). A technical complication in unimodal regression is the nonconvexity of the underlying parameter space. We develop a general variational representation
of the risk that holds whenever the parameter space can be expressed as a finite union of convex
sets, using techniques that may be of interest in other settings.
Keywords and phrases: shape constrained inference, minimax bounds, isotonic regression,
unimodal regression.

1. Introduction
In this paper we investigate the statistical properties of the least squares estimator in unimodal
sequence estimation, where the sequence rises to a mode, and then decreases. Unimodal regression is a natural type of shape constrained inference problem. Although closely related to isotonic
regression, unimodal regression has not been as extensively studied. We analyze the least squares
estimator for unimodal regression, showing that the estimator is adaptive in the sense that the risk
scales as a function of the number of values in the true underlying sequence. When the sequence
has a relatively small number of values, the estimator achieves essentially parametric rates of convergence. Such adaptivity properties have been shown for isotonic regression in the recent literature
(Bellec, 2016; Chatterjee et al., 2015b). However, existing proof techniques for isotonic regression
do not directly extend to the unimodal setting—a technical complication is the non-convexity of
the underlying parameter space. We develop a general variational representation of the risk that
holds whenever the parameter space can be expressed as a finite union of convex sets, and employ
empirical process techniques that give good upper bounds. These techniques enable us to show
that the least squares estimator for unimodal regression, to a considerable extent, enjoys similar
adaptivity properties as the least squares estimator for isotonic regression.
In more detail, we consider the problem of unimodal regression where for design points x1 ≤
1

x2 · · · ≤ xn we observe
yi = f (xi ) + zi ,

for i = 1, . . . , n

where f : R → R is a unimodal function and the random errors zi are assumed to be independently
distributed as N (0, σ 2 ), with the variance σ 2 unknown. Our analysis also carries over to the case
when z is a mean zero error vector with independent entries and absolute value bounded by a
constant σ > 0. We consider the design points to be fixed but arbitrary, and hence the problem
of estimating the unimodal function f reduces to the problem of estimating an unknown vector
θ∗ ∈ Rn from observations
yi = θi∗ + zi ,

for i = 1, . . . , n

(1.1)

where θ∗ is constrained to lie in
Un := {θ ∈ Rn : θ1 ≤ θ2 ≤ · · · ≤ θm ≥ θm+1 · · · ≥ θn for some 1 ≤ m ≤ n}.

(1.2)

We refer to any vector in Un as a unimodal sequence; such a sequence first increases and then
decreases.
In this paper we are concerned with the statistical problem of estimating θ∗ ∈ Un from the data
y. This problem has interesting structure that we shall exploit. For any 1 ≤ m ≤ n, let us define
the set
Cm = {θ ∈ Rn : θ1 ≤ θ2 ≤ · · · ≤ θm ≥ θm+1 , · · · ≥ θn },
(1.3)
thus using the index m to indicate the mode of the sequence. Each set Cm ⊂ Rn is a closed convex
cone. When m = 1, the set C1 is the collection of decreasing sequences; when m = n, the set
S
Cn is the collection of increasing sequences. Since Un = nm=1 Cm , we see that the collection of
unimodal sequences can be written as a union of n closed convex cones, but is not itself a convex
set.
The least squares estimator (LSE) θb is defined as the minimizer of the squared Euclidean norm,
ky − θk2 , over θ ∈ Un ,
θb := arg min ky − θk2 .
(1.4)
θ∈Un

Since Un is not a convex set, the LSE θb may not be uniquely defined. In case there are multiple
minima, the LSE θb can be chosen arbitrarily over the set of minimizers. For each 1 ≤ m ≤ n since
Cm is a closed convex cone, we can define θbm as the unique projection of y onto Cm . Then the
LSE can also be written as
θb := arg min ky − θk2 .
(1.5)
θ∈{θb1 ,...,θbn }

The problem of computing a projection to the set of unimodal sequences has received considerable attention (Boyarshinov and Magdon-Ismail, 2006; Bro and Sidiropoulos, 1998; Stout, 2000,
2008). Stout (2008) shows that by using variations of the well-known pooled adjacent violators
(PAVA) algorithm for isotonic regression (Barlow et al., 1972; Grotzinger and Witzgall, 1984), one
2

can design an O(n) algorithm to compute a unimodal projection, and hence the LSE. Thus, there
is effectively no computational price to pay when fitting unimodal sequences rather than monotone sequences. At a high level, the contribution of the current paper is to show that there is also
essentially no statistical price to pay.
Compared with monotone or isotonic regression, the unimodal regression problem has received
relatively little attention in the statistics literature. Frisén (1986) presents several applications of
unimodal regression and introduces the least squares estimator, without analyzing its risk properties. Shoung and Zhang (2001) study the convergence of the mode of the LSE as an estimator of
the true mode of a unimodal function. For classes of unimodal functions indexed by a smoothness
parameter, the authors prove rates of convergence of the mode of the LSE and also show that the
rates are minimax optimal up to logarithmic factors, for a given smoothness class. Köllmann et al.
(2014) propose the use of a penalized estimator based on splines to estimate the underlying unimodal function, but without studying the risk properties of their estimator. Hence, apparently little
is known about the behavior of the LSE θb as an estimator of θ∗ . The problem of unimodal density estimation is actually more well studied than its regression counterpart (Bickel and Fan, 1996;
Birgé, 1997; Eggermont and LaRiccia, 2000; Meyer, 2001). A recent work worth mentioning here
is Balabdaoui and Jankowski (2015) where the authors study the estimation of discrete unimodal
probability mass functions.
The isotonic regression problem is closely related, except that the underlying sequence is assumed to be nondecreasing instead of unimodal. As is clear, with the mode known, fitting a least
squares unimodal sequence reduces to fitting an increasing sequence to the first part and a decreasing sequence to the second part. The risk properties of the LSE in the isotonic regression
problem are fairly well understood, having been intensively studied by a number of authors (Birgé
and Massart, 1993; Chatterjee et al., 2015b; Donoho, 1991; Meyer and Woodroofe, 2000; van de
Geer, 1990; Van de Geer, 1993; Wang, 1996; Zhang, 2002). In particular, Zhang (2002) shows the
existence of a universal positive constant C such that
(
)
2/3
2
∗
2
1
σ
V
(θ
)
σ
log
n
∗ b
∗
2
b ≤C
R(θ , θ) = Ekθ − θk
+
(1.6)
n
n
n
with V (θ∗ ) := θn∗ − θ1∗ . This result shows that the risk of θb scales as n−2/3 in the sequence length,
provided V (θ∗ ) is bounded from above by a constant. It can be proved that n−2/3 is the minimax
rate of estimation in this problem, see (Chatterjee et al., 2015b).
For a monotonic vector θ ∈ Rn we define s(θ) to be the cardinality of the set of values:
s(θ) = {θ1 , . . . , θn } .

(1.7)

Also let us define Mn = {θ ∈ Rn : θ1 ≤ · · · ≤ θn } to be the set of monotonic sequences. A
b in the isotonic regression problem has been proved by
complementary upper bound on R(θ∗ , θ)

3

Chatterjee et al. (2015b) who show that (for n > 1)

 ∗
en
kθ − θk2 σ 2 s(θ)
∗ b
+
log
.
R(θ , θ) ≤ 6 inf
θ∈Mn
n
n
s(θ)

(1.8)

This risk bound has recently been further improved by Bellec (2016), with the constant 6 being improved to 1, and with a removal of the assumption that the true underlying sequence θ∗ is isotonic,
yielding
 ∗

kθ − θk2 σ 2 s(θ)
en
∗ b
R(θ , θ) ≤ inf
+
log
.
(1.9)
θ∈Mn
n
n
s(θ)
The bounds (1.6) and (1.9) provide a nearly complete understanding of the global accuracy of
the LSE θb in isotonic sequence estimation. In particular, the risk of the LSE can never be larger
than the minimax rate (σ 2 V (θ∗ )/n)2/3 , while it can be the parametric rate (up to log factors) σ 2 /n,
up to logarithmic multiplicative factors, if θ∗ can be well-approximated by θ having small s(θ). In
fact, the sharp oracle inequality (1.9) also implies parametric rates for θ that is well approximated
by a piecewise constant sequence with not too many values. It also gives rates of convergence for
θb to the projection of θ∗ in the cone Mn in case θ∗ is not in Mn . So, in this sense, the LSE in
the isotonic regression problem is automatically adaptive to piecewise constant sequences. Such
automatic adaptivity properties are also seen in other shape constrained estimation problems such
as convex regression (Chatterjee et al., 2015b; Guntuboyina and Sen, 2013) and monotone matrix
estimation (Chatterjee et al., 2015a). The goal of the research leading to the current paper was to
extend the parameter space from isotonic to unimodal sequences and investigate whether the risk
bounds (1.6) and (1.9) continue to hold. The following section summarizes our findings.
2. Results
Our first result establishes minimaxity of the least squares estimator for unimodal sequence estimation.
Theorem 2.1. Fix any positive integer n and θ∗ ∈ Un . Let V (θ∗ ) = max1≤i≤n θi∗ − min1≤i≤n θi∗ .
There exists a universal constant C such that for any positive α > 0 we have the following upper
bound with probability not less than 1 − 2n−α ,
log n
1 b
kθ − θ∗ k2 ≤ Cσ 4/3 (V (θ∗ ) + σ)2/3 n−2/3 + (C + 24α)σ 2
.
n
n
This is the analog of (1.6) in unimodal regression. It shows that the least squares estimator θb
converges to θ∗ at the rate n−2/3 in mean squared error loss, uniformly for all unimodal sequences
θ∗ with V (θ∗ ) bounded. Since the minimax rate for the set of isotonic sequences with V (θ∗ ) ≤ C
is O(n−2/3 ), and unimodal regression is concerned with a larger parameter space than isotonic
regression, this establishes that the least squares estimator is minimax rate optimal.
Our next theorem says that the least squares estimator is adaptive to sequences that are piecewise
constant, in the sense that the risk scales according to the number of pieces of the true sequence
and has faster convergence rate than the worst case O(n−2/3 ) rate.
4

Theorem 2.2. Fix a positive integer n and θ∗ ∈ Un . Let m∗ be a mode for θ∗ , that is θ∗ ∈ Cm∗ . Let
∗
s1 equal the number of distinct values of (θ1∗ , . . . , θm
∗ ) and s2 equal the number of distinct values
∗
∗
of (θm∗ +1 , . . . , θn ). Fix any α > 0. Then the mean squared error satisfies




1 b
s1 + s2
en
log n
∗ 2
2
kθ − θ k ≤ 12σ
log
+ 48(α + 2)σ 2 (s1 + s2 )
(2.1)
n
n
s1 + s2
n
with probability at least 1 − 4/nα .
This theorem says that the mean squared error of the LSE scales for a unimodal sequence
scales like (s1 + s2 ) log n/n where s1 is the number of constant pieces of the part of θ∗ which is
nondecreasing and s2 is the number of constant pieces of the part of θ∗ which is nonincreasing.
Therefore s1 + s2 could be thought of as roughly the number of steps (going up and coming down)
in the sequence θ∗ .
As a consequence of the above theorem, when the true unimodal sequence has a bounded number of steps, the risk of the least squares estimator will decay at the parametric rate of convergence
O(1/n) up to log factors. As an illustration, if θ∗ is the vector of evaluations of the indicator function f (x) = I{0 ≤ x ≤ 1} at n (sorted) points on the real line, the risk of θb would decrease at the
parametric rate. The result shows that as long as s1 + s2 = o(n1/3 ), rates of convergence that are
faster than the global minimax rate are obtained.
Remark 2.1. Both Theorems 2.1 and 2.2 hold when the error vector is Gaussian with independent
entries, mean zero and variance σ 2 . They also hold when the error vector is composed of mean zero
independent entries with absolute value bounded by σ > 0. An important ingredient in our proofs
is the concentration result (Theorem 4.3) for Lipschitz functions of a Gaussian random vector. The
proof for bounded errors follow by using Ledoux’s concentration result (Theorem 4.4) for convex
Lipschitz functions of the error vector.
Remark 2.2. The same upper bound of Theorem 2.2 was obtained independently by Bellec (2016)
and Flammarion et al. (2016).
Remark 2.3. All our risk bounds are shown to hold with high probability. These bounds can then
be integrated to get bounds in expectation.
Remark 2.4. The rate of convergence in Theorem 2.1 scales with n in exactly the same way as
in isotonic regression, in spite of the fact that the parameter space is now a union of n convex
cones, each of which is comprised of at most two isotonic pieces. In particular, the risk bound in
Theorem 2.1 does not have a logarithmic factor of n.
Remark 2.5. No smoothness conditions are assumed of the underlying unimodal sequence. The
least squares estimator is fully automated and does not require any tuning parameters, as is often
the case for shape-constrained estimators.
Remark 2.6. Fitting the unimodal least squares estimator can provide a means of trading off
computational time for statistical risk accuracy in a concave regression problem. To explain, note
5

that the set of unimodal sequences contains the set of concave sequences. The latter has a minimax
rate of O(n−4/5 ), which is naturally faster than the rate in unimodal regression. However, to the
best of our knowledge, the running time for convex regression is at least quadratic, O(n2 ), whereas
runtime for unimodal regression is O(n). While the unimodal estimator will not be concave in
general, it will be close to the underlying concave sequence in an average `2 sense, for large n.
The worst case rate of convergence (Theorem 2.1) of the LSE for unimodal regression matches
that of isotonic regression, and the adaptive risk bound (Theorem 2.2) is almost as strong as the
adaptive risk bound (1.9) for isotonic regression. We say almost because Theorem 2.2 is useful
for θ∗ which is exactly piecewise constant with a few pieces but may not be useful when θ∗ is
very well approximable by a piecewise constant with a few pieces. Risk bounds which provide
such “continuity” of risk are often referred to as oracle inequalities. Previous proofs for oracle risk
bounds in shape constrained problems appear to rely heavily on the convexity of the parameter
space; thus these techniques do not readily apply to unimodal regression, where Un is nonconvex.
In particular, existing proof techniques first bound the statistical dimension (see Amelunxen et al.
(2014)) for a closed convex cone when θ∗ belongs to the lineality space of the cone (see Chatterjee
et al. (2015b)), and then derive risk bounds for Gaussian widths of the tangent cone at θ∗ (see
Proposition 1 in Bellec (2016) and Lemma 4.1 in Chatterjee et al. (2015a)). Such techniques rely
on the convexity of the parameter space and exploit the KKT conditions for the projection onto
closed convex sets. Our parameter space is not convex and hence we are unable to directly use
these results to prove oracle risk bounds.
The main complication in this problem is to handle the unknown mode location. Our analysis
reveals that even with the unknown mode, it is still possible to derive adaptive risk bounds for
piecewise constant unimodal sequences, when the number of steps is not too large. At a high level,
the main idea here is to show first that the risk depends on a local Gaussian width like term. This
fact is now known when the parameter space is convex and we are able to extend this observation
to our nonconvex parameter space. We analyze this local Gaussian width like term and by various
steps of refinement we show that this term scales like the mean squared error in isotonic regression
plus logarithmic terms.
3. LSE Slicing Lemma
In this section we show that the loss kθb − θ∗ k has a variational representation whenever the underlying vector θ∗ is known to belong to a parameter space C that can be expressed as a finite union of
convex “slices.” The lemma is a deterministic identity that generalizes Proposition 1.3 in Chatterjee (2014). For us, this lemma is directly applied in the proof of Theorem 2.2. This technique may
be of use in other contexts; for example the set of permutations arising in the analysis of pairwise
comparisons has this structure, see Shah et al. (2015), Chatterjee and Mukherjee (2016).
n
∗
Lemma 3.1. Let C = ∪M
m=1 Cm where each Cm ⊂ R is a closed convex set. Fix some θ ∈ C,

6

and let y = θ∗ + z. Define the function fθ∗ : R+ → R as
fθ∗ (t) =

hz, θ − θ∗ i −

sup

θ∈C:kθ−θ∗ k≤t

t2
.
2

(3.1)

If θb ∈ arg minθ∈C ky − θk2 is a least squares estimator over C then
kθb − θ∗ k ∈ arg max fθ∗ (t).

(3.2)

t≥0

Moreover, if t∗ satisfies fθ∗ (t) < 0 for all t ≥ t∗ , then
kθb − θ∗ k < t∗ .

(3.3)

Relations (3.2) and (3.3) are deterministic, and do not depend on any distributional properties of
the error vector z.
Proof. To prove (3.2), first note that we can write

θb ∈ arg min kzk2 + kθ − θ∗ k2 − 2hz, θ − θ∗ i
θ∈C

= arg max hz, θ − θ∗ i − kθ − θ∗ k2 /2 .

(3.4)
(3.5)

θ∈C

It follows from the second equation that
kθb − θ∗ k ∈ arg max
t>0

= arg max
t>0

hz, θ − θ∗ i −

sup

θ∈C:kθ−θ∗ k=t

max

1≤m≤M

t2
2

t2
sup
hz, θ − θ∗ i −
2
θ∈Cm :kθ−θ∗ k=t

= arg max max hm (t)
t>0

!

(3.6)

1≤m≤M

where we have defined the functions hm : R+ → R as
hm (t) =

hz, θ − θ∗ i −

sup

θ∈Cm :kθ−θ∗ k=t

t2
.
2

(3.7)

Now for each 1 ≤ m ≤ M define the functions gm : R+ → R as
gm (t) =

sup

hz, θ − θ∗ i.

(3.8)

θ∈Cm :kθ−θ∗ k≤t

If dm = infv∈Cm kθ∗ − vk is positive, then we define gm (t) = −∞ whenever t < dm . Since the
set Cm is closed convex, it can be shown that gm is a concave function of t. Such a calculation has
been done in the proof of Theorem 1 in Chatterjee (2014) but for sake of completeness we prove
7

the concavity of gm in Lemma A.4 in the appendix. Next, define functions fm : R+ → R according
to
t2
fm (t) = gm (t) − .
(3.9)
2
Then fm is strictly concave as a function of t whenever t ≥ dm . An application of the CauchySchwarz inequality shows that fm (t) decays to −∞ as t → ∞. These facts establish that fm (t) has
a unique maximizer.
Let tm be the unique maximizer of fm . We now show that tm is a unique maximizer of hm . It is
clear from the definitions that for all t ≥ 0 we have hm (t) ≤ fm (t). Recall that
fm (tm ) =

hz, θ − θ∗ i −

sup
θ∈Cm :kθ−θ∗ k≤tm

t2m
,
2

(3.10)

and let θe ∈ {θ ∈ Cm : kθ − θ∗ k ≤ tm } be a point where fm (tm ) is achieved. If it were the case
that kθe − θ∗ k = t0 < tm , then we would have fm (t0 ) > fm (tm ), contradicting the definition of tm .
Hence kθe − θ∗ k = tm , implying that fm (tm ) = hm (tm ). Therefore,
hm (x) ≤ fm (x) < fm (tm ) = hm (tm )

(3.11)

for any x 6= tm . This shows that tm is a unique maximizer of hm as well. Therefore we have shown
that
kθb − θ∗ k ∈ arg max max hm (t)
t>0

1≤m≤M

= arg max max fm (t)
t>0

1≤m≤M

= arg max fθ∗ (t),

(3.12)
(3.13)
(3.14)

t>0

thus proving (3.2).
It remains to prove (3.3). Since θ∗ ∈ C there exists 1 ≤ m∗ ≤ M such that θ∗ ∈ Cm∗ .
Now it is easy to see that fm∗ (0) = 0 and hence maxt≥0 fm∗ (t) ≥ 0. Because of this fact and
fθ∗ (t) = max1≤m≤M fm (t) we have
max fθ∗ (t) ≥ 0.
t≥0

(3.15)

This inequality combined with the representation formula (3.2) proves (3.3), finishing the proof of
the lemma.
4. Global Risk Bound
The goal of this section is to prove Theorem 2.1. We prove both Theorem 2.1 in this section and
Theorem 2.2 in the next section assuming Gaussian errors. The case of bounded errors will also
8

follow from our proofs. See Remark 4.1 for more details. Recall that for a subset F ⊆ Rn and
 > 0, the -covering number N (, F) is the minimum number of balls of radius  required to cover
F in the Euclidean norm. Throughout the following, C will represent a universal constant, whose
particular value might change from calculation to calculation. The following result follows from
the metric entropy results of monotone functions (Gao and Wellner, 2007); a proof can be found
in Lemma 4.20 in Chatterjee (2014). By symmetry, the same covering number bound holds for
nonincreasing sequences.
Theorem 4.1 (Gao-Wellner). Let M[a,b] = {v ∈ Rn : a ≤ v1 ≤ · · · ≤ vn ≤ b} denote the set of
monotone sequences of length n taking values between a and b. Also recall that k · k denotes the
standard Euclidean norm. Then for any  > 0,
√
C n(b − a)
log N (, M[a,b] , k · k) ≤
(4.1)

where C is a universal constant.
Throughout this section, z ∼ N (0, σ 2 In ) will denote a Gaussian random variable. We will
require the following chaining bound (see e.g., Van de Geer (2000)).
Theorem 4.2 (Chaining). For every θ∗ ∈ M and t > 0,
!
Z tp
∗
log N (, B(θ∗ , t)) d,
E
sup hz, θ − θ i ≤ 12σ
θ∈B(θ∗ ,t)

(4.2)

0

where B(θ∗ , t) denotes the standard Euclidean ball around θ∗ of radius t.
We will also require a standard Gaussian concentration inequality; the proof of the following
can be found in the argument after equation (2.35) in Ledoux (2001).
Theorem 4.3 (Gaussian concentration). Let f : Rn → R be a function that is L-Lipschitz, so that
|f (x) − f (y)| ≤ Lkx − yk for all x and y. Then for any t ≥ 0,


t2
P (f (z) ≤ E(f (z) + σt) ≤ exp − 2 .
(4.3)
2L
Remark 4.1. Our entire analysis can be done when z is a mean zero error vector of independent
entries with absolute value bounded by a constant σ > 0. This is done by invoking the following
concentration result whenever we have used the Gaussian concentration theorem for Lipschitz
functions. We have used the Gaussian concentration theorem for random variables which can be
seen as a supremum of linear functions of the error vector z and hence are convex functions of
z. This fact enables the application of Ledoux’s concentration result wherever we have applied
Theorem 4.3 .
A proof of the following theorem can be found in Boucheron et al. (2013).
9

Theorem 4.4 (Ledoux). If f : [−σ, σ]n → R is a convex Lipschitz function with Lipschitz constant
L and  is a mean zero random vector with independent entries in [−σ, σ], then we have
P(f () > u) ≤ exp(−u2 /8σ 2 L2 ).

(4.4)

Recall that Cm = {θ ∈ Rn : θ1 ≤ θ2 · · · ≤ θm ≥ θm+1 · · · ≥ θn } is the collection
of unimodal sequences with a mode at m. We now prove a key lemma controlling the term

E supθ∈Cm :kθ−θ∗ k≤t hz, θ − θ∗ i as a function of t whenever the underlying θ∗ is monotonic. This
will be crucial in finally proving Theorem 2.1.
The idea of the proof is as follows. The standard technique in empirical process theory of upper

bounding the expected Gaussian term E supθ∈Cm :kθ−θ∗ k≤t hz, θ−θ∗ i is to use the Dudley’s entropy
integral bound, as given in Theorem 4.2. This requires tight upper bounds on the covering number
for the set {θ ∈ Cm : kθ−θ∗ k ≤ t}. Now, upper bounds can be derived for the log-covering number
of bounded sequences in Cm using Theorem 4.1. However, a direct application of Theorem 4.1 to
cover the set {θ ∈ Cm : kθ − θ∗ k ≤ t} would give us loose bounds, as t can grow with n. Instead,
we carry out an extra peeling step. In particular, for any θ belonging to {θ ∈ Cm : kθ − θ∗ k ≤ t},
0
we define a truncated version θ belonging to the same set that is also bounded by a constant factor

L = C V (θ∗ ) + σ . Note that one can write



 

0
0
∗
∗
E
sup
hz, θ−θ i ≤ E
sup
hz, θ−θ i +E
sup
hz, θ −θ i .
θ∈Cm :kθ−θ∗ k≤t

0

θ∈Cm :kθ−θ∗ k≤t

θ0 ∈Cm :kθ0 −θ∗ k≤t,maxi |θi |≤L

(4.5)
The truncation is defined in such a way that the first term on the right side of the above inequality
is small enough for our purposes. The second term can be controlled by a direct application of
Dudley’s entropy integral inequality. This extra peeling step helps us to derive a tight risk bound.
The definition of these truncations forms a key part of our argument. We actually form a truncation θ0 of an arbitrary unimodal sequence θ ∈ Cm with respect to a fixed monotone sequence
θ∗ . The tails of θ are raised to θ1∗ − L over S1L ∪ S1R = S1 = {i : θi < θ1∗ − L}. In the interval
∗
S2 = {i : θi > θm
+L} around the mode m, the sequence is lowered to the level θn∗ +L. It is crucial
that we are able to choose L to be a constant factor while still maintaining the fact that the first
term on the right side of (4.5) is sufficiently small. Figure 1 shows a schematic of the construction
of our truncation θ0 of θ; the figure may be helpful in understanding the steps of the proof.
Lemma 4.1. Fix any nondecreasing sequence θ∗ ∈ Mn and let 1 ≤ m ≤ n. Then for all t ≥ 0,
!


q

t2
∗
1/4 1/2
∗
E
sup
hz, θ − θ i ≤ Cσ n t
V (θ ) + σ +
(4.6)
8
θ∈Cm :kθ−θ∗ k≤t
where V (θ∗ ) = max1≤i≤n θi∗ − min1≤i≤n θi∗ . The bound also holds, by symmetry, for any nonincreasing sequence θ∗ ∈ M−
n.
0

Proof. Let K = {θ ∈ Cm : kθ − θ∗ k ≤ t}, and define K ⊂ K as


0
∗
∗
K = θ ∈ K : max θi ≤ θn + L, min θi ≥ θ1 − L
1≤i≤n

1≤i≤n

10

(4.7)

θ
θ

θn∗ + L

0

θn∗

θ∗
θ1∗
θ1∗ − L
S1L

S1R

S2

F IGURE 1. The proof of Lemma 4.1 is based on a truncation θ0 of an arbitrary unimodal sequence θ ∈ Cm with respect
to a fixed monotone sequence θ∗ . The tails of θ are raised to θ1∗ − L over S1L ∪ S1R = S1 = {i : θi < θ1∗ − L}. In the
interval S2 = {i : θi > θn∗ + L} around the mode m, the sequence is lowered to the level θn∗ + L.

where L is a fixed positive number to be chosen later. For any θ ∈ K we will define a truncated
version of θ belonging to K 0 which will be denoted by θ0 . Then we will have the inequality
E sup hz, θ − θ∗ i ≤ E sup hz, θ − θ0 i + E sup hz, θ0 − θ∗ i.
θ∈K

(4.8)

θ0 ∈K 0

θ∈K

Fix an arbitrary θ ∈ K. Consider the sets S1 = {i : θi < θ1∗ − L} and S2 = {i : θi > θn∗ + L} and
define θ0 according to

∗


θ1 − L if i ∈ S1
θi0 =

θn∗ + L if i ∈ S2


θ
otherwise.
i

(4.9)

As indicated in Figure 1, S1 is the union of a left prefix S1L of {1, . . . , n} and a right suffix S1R .
It is then clear that min1≤i≤n θ10 ≥ θ1∗ − L and max1≤i≤n θi0 ≤ θn∗ + L Also, by construction of θ0 it
is unimodal, and we have the contractive property
|θi∗ − θi0 | ≤ |θi∗ − θi |

(4.10)

for any 1 ≤ i ≤ n. These facts show that θ0 ∈ K 0 .
We now proceed to control the first term on the right side of the inequality in (4.8). Using the

11

definition of θ0 , we have
n
X
X
X
zi (θi − θi0 )
zi (θi − θi0 ) +
zi (θi − θi0 ) =
i=1

≤

X

|zi |(θi0 − θi ) +

X

|zi |(θi − θi0 )

(4.12)

|zi |(θi0 − θi ) I{2j L < θ1∗ − θi ≤ 2j+1 L}

(4.13)

i∈S1

=

(4.11)

i∈S2

i∈S1

i∈S2

∞
XX
i∈S1 j=0

+

∞
XX

|zi |(θi − θi0 ) I{2j L < θi − θn∗ ≤ 2j+1 L}

(4.14)

i∈S2 j=0

≤

∞
X

2j+1 L

j=0

X

|zi | I{2j L < θ1∗ − θi ≤ 2j+1 L}

(4.15)

X

(4.16)

i∈S1

+

∞
X
j=0

2j+1 L

|zi | I{2j L < θi − θn∗ ≤ 2j+1 L}

i∈S2

where I denotes the indicator function and the last inequality follows from the inequalities
θi0 − θi ≤ θ1∗ − θi for i ∈ S1

(4.17)

θi − θi0 ≤ θi − θn∗ for i ∈ S2 .

(4.18)

We now note that for any θ ∈ K, since kθ − θ∗ k ≤ t,
t2
≡ vj .
(4.19)
22j L2
Also note that if i ∈ S1 then θ1∗ − θi > 2j L implies that θi∗ − θi > 2j L, since θ∗ is monotonic.
Therefore,

i ∈ S1 : 2j L < θ1∗ − θi ≤ vj .
(4.20)


i : 2j L < |θi − θi∗ |

≤

Now observe that since θ is unimodal, any set of the form {i : θi < a} for some number a is
necessarily a union of at most two intervals; see Figure 2. Therefore,


i ∈ S1 : 2j L < θ1∗ − θi ≤ 2j+1 L ⊆ i ∈ S1 : 2j L < θ1∗ − θi
(4.21)
⊆ {1, . . . , vj } ∪ {n − vj + 1, n − vj + 2, . . . , n},
since each interval must have size no greater than vj . Similarly, we have that

i ∈ S2 : 2j L < θi − θn∗ ≤ vj .

(4.22)

(4.23)

Since θ ∈ Cm is unimodal, any set of the form {i : θi > a} for some number a is necessarily an
interval containing m, if it is nonempty. Therefore, we have that


i ∈ S2 : 2j L < θi − θn∗ ≤ 2j+1 L ⊆ i ∈ S2 : 2j L < θi − θn∗
(4.24)

⊆ m − vj + 1, . . . , m + vj − 1 .
(4.25)
12

θ
θn∗ + 2j L
θ1∗

θ0

θn∗ + L

θ1∗ − L
θ∗

θ1∗ − 2j L
≤ vj

≤ 2vj


F IGURE 2. The set i ∈ S1 : 2j L < θ1∗ − θi is the union of at most two intervals.
no larger than vj .
 Each has size
j
The figure on the left indicates the left interval. Similarly, by unimodality, the set i ∈ S2 : 2 L < θi − θn∗ if it is
nonempty, is an interval of length no greater than 2vj .

We conclude that
n
X

∞
X

i=1

j=0

(θi − θi0 )zi ≤


2j+1 L 

m+vj −1

vj

X

X

|zi | +

i=1

i=m−vj +1

|zi | +

n
X


|zi | .

(4.26)

i=n−vj +1

Note that this upper bound does not depend on θ, and that θ was an arbitrary element of K. Thus,
p
using the fact E|zi | = σ 2/π and (4.19), we arrive at
!
p
p
∞
n
∞
X
X
p
4t2 σ 2/π X 1−j 16t2 σ 2/π
0
j+1
2
=
E sup
(θi − θi )zi ≤ 4Lσ 2/π
2 vj =
.
L
L
θ∈K i=1
j=0
j=0
(4.27)
We now set L = 128σ

p
2/π to finally obtain


t2
0
E sup hz, θ − θ i ≤ .
8
θ∈K

(4.28)

To control the second term on the right side of (4.8) we set A = K 0 and δ = 0 in the chaining
result (4.2) to obtain


Z tp
0
∗
E sup hz, θ − θ i ≤ 12σ
log N (, K 0 ) d.
(4.29)
θ0 ∈K 0

0

0

By definition of K we can now apply Theorem 4.1 with a = θ1∗ − L and b = θn∗ + L to obtain
p

√ V (θ∗ ) + 256σ 2/π
0
log N (, K ) ≤ C n
.
(4.30)

Using (4.29) and integrating the above expression gives us, for an appropriate constant C,


q

0
∗
1/4 1/2
E sup hz, θ − θ i ≤ Cσn t
V (θ∗ ) + σ .
(4.31)
θ0 ∈K 0

Combining the last equation with (4.28) and (4.8) finishes the proof of the lemma.
13

We now prove a lemma that controls the expected Gaussian supremum where the supremum is
taken over all unimodal sequences.
Lemma 4.2. Fix a positive integer n and a nondecreasing or nonincreasing sequence θ∗ . For all
t ≥ 0,
!


q
p

t2
∗
1/4 1/2
E
sup
hz, θ − θ i ≤ Cσ n t
V (θ∗ ) + σ + t log n + .
(4.32)
8
θ∈Un :kθ−θ∗ k≤t
Proof. We prove the lemma when θ∗ ∈ Mn is a nondecreasing sequence; the proof when θ∗ is
nonincreasing is analogous. For each 1 ≤ m ≤ n and t > 0 define the random variables
Xm (t) =

sup
θ∈Cm

hz, θ − θ∗ i.

(4.33)

:kθ−θ∗ k≤t

We first note that
sup
θ∈Un

hz, θ − θ∗ i = max Xm (t).
1≤m≤n

:kθ−θ∗ k≤t

(4.34)

Applying Lemma A.2 we see that the random variables Xm (t) are Lipschitz functions of z with
Lipschitz constant t. Hence, using the Gaussian concentration result given in Theorem 4.3 we get
for all x > 0 and all 1 ≤ m ≤ n,
 2
x
.
(4.35)
P (Xm (t) ≤ EXm (t) + tσx) ≤ exp −
2
A standard argument involving maxima of random variables with sub-Gaussian tails is given in
Lemma A.1. Using this lemma and the last equation we get that, for a universal constant C,
p
(4.36)
E max Xm (t) ≤ max EXm (t) + Cσt log n.
1≤m≤n

1≤m≤n

Applying Lemma 4.1 to the term maxm EXm (t) completes the proof of the lemma.
We are now ready to prove Theorem 2.1.
Proof of Theorem 2.1. We start with the basic inequality kθb − θ∗ k2 ≤ 2hz, θb − θ∗ i and rewrite it
as
1 b
1
kθ − θ∗ k ≤
hz, θb − θ∗ i.
(4.37)
∗
2
kθb − θ k
b among all θ ∈ U, maximizes the expression
This pointwise inequality follows from the fact that θ,
g(θ) = hz, θ − θ∗ i − kθ − θ∗ k2 /2.
b ≥ g(θ∗ ) = 0 which is equivalent to (4.37). Now, an application
Since θ∗ ∈ U, we then have g(θ)
of the Cauchy-Schwarz inequality to (4.37) implies
1 b
kθ − θ∗ k ≤ kzk.
2
14

(4.38)

Define the event A1 = {kzk2 < 5n}. By a standard tail inequality for chi squared random variables
(Laurent and Massart, 2000), one can show that
P (A1 ) ≥ 1 − exp(−n).

(4.39)

The following argument conditions on the event A1 throughout. For any t > 0 we can write
√
1 b
t
1
kθ − θ ∗ k ≤ +
hz, θb − θ∗ iI{t < kθb − θ∗ k < 5n}
2
2 kθb − θ∗ k
hz, θ − θ∗ i
t
sup √
≤ +
.
2 θ∈U :t<kθ−θ∗ k≤ 5n kθ − θ∗ k
|
{z
}

(4.40)
(4.41)

Ht

We will now control the random variable Ht defined above for any t ≥ 1. Writing Ht as
Ht ≤

sup √

0≤l<log2 (

hz, θ − θ∗ i
,
∗
5n) θ∈U :2l t<kθ−θ∗ k≤2l+1 t kθ − θ k
sup

we now claim that instead of dividing the inner product term by the variable factor kθ − θ∗ k, we
can instead divide by the constant factor 2l t. An application of Lemma ??, stated and proved in the
appendix, makes this precise and we can thus write
Ht ≤

sup √

0≤l<log2 ( 5n)

hz, θ − θ∗ i
2l t
θ∈U :2l t<kθ−θ∗ k≤2l+1 t

(4.42)

hz, θ − θ∗ i
2l+1
θ∈U :kθ−θ∗ k≤2l+1 t

(4.43)

hz, wl − wl∗ i

(4.44)

≤

2
sup
t 0≤l<log2 (√5n)

=

2
sup
t 0≤l<log2 (√5n)

sup

sup

sup

wl ∈U :kwl −wl∗ k≤t

where wl∗ = θ∗ /(2l+1 ). The random variables Wl = supwl ∈U :kwl −wl∗ k≤t hz, wl − wl∗ i are Lipschitz
functions of z with Lipschitz constant t as can be seen by applying Lemma A.2. Therefore for each
√
fixed integer 0 ≤ l ≤ log2 ( 5n) the Gaussian concentration result in Theorem 4.3 shows for any
x > 0,
P(Wl ≤ EWl + tσx) ≥ 1 − exp(−x2 /2).
Now define the event
A2 =

n

max√ Wl
0≤l≤log2 ( 5n)

≤

max√
0≤l≤log2 ( 5n)

o
EWl + tσx .

√
A union bound over 0 ≤ l ≤ log2 ( 5n) then gives us
√
P(A2 ) ≥ 1 − (1 + log2 ( 5n)) exp(−x2 /2).
15

√
Now, for any 0 ≤ l ≤ log2 ( 5n) we can break up supwl ∈U :kwl −wl∗ k≤t hz, wl − wl∗ i into two parts;
the first part where w∗ is increasing and then the second part where w∗ is decreasing. We apply
Lemma 4.2 to both the parts to obtain


q
p

t2
1/4 1/2
∗
EWl ≤ Cσ n t
V (wl ) + σ + t log n + .
8
Note that since wl∗ = θ∗ /2l+1 we have V (wl∗ ) ≤ V (θ∗ ) and hence we can write for all t ≥ 0,


q
p

t2
1/4 1/2
∗
V (θ ) + σ + t log n + .
max√ EWl ≤ Cσ n t
8
0≤l≤log2 ( 5n)
We thus conclude that conditioned on the event A2 , for all t ≥ 0,



 t2
p
p
2
1/4 1/2
Ht ≤
Cσ n t
(V (θ∗ ) + σ) + t log n + + tσx
t
8

 t
p
p
= Cσ n1/4 t−1/2 (V (θ∗ ) + σ) + log n + + 2σx.
4

(4.45)
(4.46)

Together with (4.41) we then obtain the upper bound

 t
p
p
1 b
t
kθ − θ∗ k ≤ + Cσ n1/4 t−1/2 (V (θ∗ ) + σ) + log n + + 2σx
2
2
4
for all t ≥ 0. Optimizing over t by setting
t = max{Cσ 2/3 (V (θ∗ ) + σ)1/3 n1/6 , 1}
then gives us the desired bound on kθb − θ∗ k. This bound holds on the set A1 ∩ A2 . For any fixed
α > 0, set
q
√
x = 2 log(1 + log2 ( 5n)) + 2α log n
to conclude that P (A2 ) ≥ 1 − n−α . Also by (4.39) we then can conclude P (A1 ∩ A2 ) ≥ 1 − n−α −
exp(−n) ≥ 1−2n−α . Finally, one can use the standard inequality (a+b+c)2 ≤ 3(a2 +b2 +c2 ) for
nonnegative numbers a, b, c to convert the bound on kθb−θ∗ k into a bound on kθb−θ∗ k2 , completing
the proof of the theorem.
5. Adaptive Risk Bound
The goal of this section is to prove Theorem 2.2. The main technical tool is Lemma 3.1, used to
show that the local Gaussian width term supθ∈Un :kθ−θ∗ k≤t hz, θ − θ∗ i scales only logarithmically
with n when the true θ∗ is piecewise constant with few pieces. This is the content of our next
lemma when θ∗ is monotone increasing or decreasing.

16

Lemma 5.1. Let θ∗ ∈ Rn be a monotone nondecreasing sequence in Mn with a constant number
of pieces s. Fix any α > 0. Then the following upper bound holds simultaneously for all t ≥ 0 with
probability not less than 1 − 2n−α :
r
 en 
p
∗
sup
hz, θ − θ i ≤ 2tσ s log
+ 2tσ 2s(α + 2) log n.
s
θ∈Un :kθ−θ∗ k≤t
Proof. Note that supθ∈Un :kθ−θ∗ k≤t hz, θ − θ∗ i = max1≤m≤n Xm (t) where Xm (t) is defined as
Xm (t) =

sup

hz, θ − θ∗ i.

θ∈Cm :kθ−θ∗ k≤t

First we control the term Xm (t) for each 1 ≤ m ≤ n. Fixing a mode location m we have
Xm (t) ≤

sup

∗
hz1:m , θ − θ1:m
i+

∗ k≤t
θ∈Mm :kθ−θ1:m

∗
hz(m+1):n , θ − θ(m+1):n
i (5.1)

sup

∗
−θ∈Mn−m :kθ−θ(m+1):n
k≤t

where it should be understood that the first term on the right side of the above inequality involves
the first m coordinates of the relevant vectors and the last term involves the last n − m coordinates
of the relevant vectors. Both the terms on the right side of the last inequality can be controlled
∗
have s1 constant pieces. Let
similarly so let us demonstrate how to control the first term. Let θ1:m
∗
us denote the blocks where θ1:m is constant by B1 , B2 , . . . , Bs1 . Note that these blocks necessarily
are intervals. For any vector a let aBi denote the |Bi | dimensional vector which is a restricted to
the coordinates in block Bi . Equipped with this notation we can now write
sup

hz1:m , θ −

∗ k≤t
θ∈Mm :kθ−θ1:m

∗
θ1:m
i

≤

s1
X

sup

sup
∗

α∈Rs+ :kαk≤t

=

sup

i=1 θ∈M|Bi | :kθBi −θBi k≤αi
s1
X

sup

α∈Rs+ :kαk≤t

=

sup


hzBi , vi

i=1 v∈M|Bi | :kvk≤αi
s1
X

αi

α∈Rs+ :kαk≤t

i=1

∗
i
hzBi , θBi − θB
i

sup


hzBi , vi



(5.2)
(5.3)
(5.4)

v∈M|Bi | :kvk≤1

where the middle equality is due to the fact that θ∗ is constant over the block Bi , and the second
equality follows since the space of monotonic sequences is a cone.
For notational convenience we denote δi (z) = supv∈M|B | :kvk≤1 hzBi , vi for 1 ≤ i ≤ m. Now
i
define the event
s1
\

Am,1 =
δi (z) ≤ Eδi (z) + σx
(5.5)
i=1

for some x > 0 that will be determined below. Note that δi (z) is a Lipschitz function of z with
Lipschitz constant one, as can be seen by applying Lemma A.2. Therefore, using the Gaussian
concentration result in Theorem 4.3 and a union bound we can conclude
P (Am,1 ) ≥ 1 − s exp(−x2 /2)
17

(5.6)

where we have used s1 ≤ s. On the event Am,1 , by (5.4) we will then have
sup

∗
i≤
hz1:m , θ − θ1:m

∗ k≤t
θ∈Mm :kθ−θ1:m

sup

s1
X

α∈Rs+ :kαk≤t i=1


αi Eδi (z) + σx .

Applying the Cauchy-Schwarz inequality to the equation then gives us on the event Am,1 ,
v
u s1
uX
√
∗
sup
hz1:m , θ − θ1:m i ≤ tt
Eδi (z)2 + tσx s1 .
∗ k≤t
θ∈Mm :kθ−θ1:m

i=1

It can now be shown that Eδi (z)2 equals σ 2 times the statistical dimension of the monotone cone of
dimension |Bi |. This equality is shown in the appendix in Lemma A.3. The statistical dimension of
the monotone cone in dimension d is defined to be EkΠM zk2 where z is a d-dimensional standard
Gaussian vector with independent entries and ΠM denotes the projection operator onto the cone of
nondecreasing sequences. Using known results (see Bellec (2016)) for the statistical dimension of
the monotone cone then gives us
Eδi (z)2 ≤ σ 2 log(e|Bi |)
from which we conclude
sup

∗
hz1:m , θ − θ1:m

∗ k≤t
θ∈Mm :kθ−θ1:m

v
u s1
uX
√
i ≤ tσ t
log(e|Bi |) + tσx s1 .
i=1

Since log is a concave function we can upper bound the term inside the square root by Jensen’s
inequality to write
!
s1
s1
s1
 en 
X
X
e X
log(e|Bi |)
≤ s1 log
|Bi | ≤ s log
log(e|Bi |) = s1
s1
s1 i=1
s
i=1
i=1
where we have used m ≤ n, s1 ≤ s and the fact that the function g(x) = x log(en/x) is increasing
for 1 ≤ x ≤ n. Therefore, conditioned on the event Am,1 we have
r
 en 
√
∗
sup
hz1:m , θ − θ1:m i ≤ tσ s log
+ tσx s.
∗ k≤t
s
θ∈Mm :kθ−θ1:m
It is crucial to note that since the event Am,1 does not depend on t, the above inequality holds
simultaneously for all t ≥ 0. To control the second term in the right side of (5.1) one can define an
analogous event Am,2 for which
P(Am,2 ) ≥ 1 − s exp(−x2 /2).

18

(5.7)

Therefore, by (5.1) we can conclude that on the event Am,1 ∩ Am,2 we have for all t ≥ 0,
r
 en 
√
+ 2tσx s.
Xm (t) ≤ 2tσ s log
s
Since the right side of the above equation does not depend on m, we can now assert that on the

T
event nm=1 Am,1 ∩ Am,2 we have for all t ≥ 0,
r
 en 
√
∗
sup
hz, θ − θ i ≤ 2tσ s log
+ 2tσx s.
s
θ∈Un :kθ−θ∗ k≤t
Note that (5.5) and (5.6) imply, by a simple union bound argument, that

P(∩nm=1 Am,1 ∩ Am,2 ) ≥ 1 − 2ns exp(−x2 /2) ≥ 1 − 2n2 exp(−x2 /2).
Setting x2 = 2(α + 2) log n thus finishes the proof of the lemma.
Using the above lemma, we can now complete the proof of Theorem 2.2.
Proof of Theorem 2.2. Just as in the proof of Theorem 2.1, the first step here also is to reduce to
the case when θ∗ is monotonic. To do this, again let 1 ≤ m∗ ≤ n be such that θ∗ ∈ Cm∗ . Let
θ∗ = (θ1∗ , θ2∗ ) where θ1∗ is an m∗ dimensional vector and θ2∗ is an n − m∗ dimensional vector. Break
up z similarly. Then we can write
sup
θ∈Un

hz, θ − θ∗ i ≤

:kθ−θ∗ k≤t

sup

hz1 , θ − θ1∗ i +

θ∈Um∗ :kθ−θ1∗ k≤t

sup

hz2 , θ − θ2∗ i.

(5.8)

θ∈Un−m∗ :kθ−θ2∗ k≤t

Let us first bound the first term on the righthand side; the second term can be bounded in exactly
the same way. Let us denote s1 to be the number of constant pieces of θ1∗ and s2 to be the number of
constant pieces of θ2∗ . Since θ1∗ is nondecreasing, we can use Lemma 5.1 to obtain with probability
not less than 1 − 2n−α , simultaneously for all t ≥ 0,
r
 em∗ 
p
∗
sup
hz1 , θ − θ1 i ≤ 2σt s1 log
+ 2σt 2s1 (α + 2) log n
(5.9)
s1
θ∈Mm∗ :kθ−θ1∗ k≤t
where we also use the fact that (m∗ ) ≤ n. The second term in the right side of (5.8) can be upper
bounded similarly. The last two displays then give us the upper bound, with probability not less
than 1 − 4n−α , for all t ≥ 0
s
r
 em∗ 
 e(n − m∗ ) 

∗
sup
hz, θ − θ i ≤2σt s1 log
+ 2σt s2 log
+
s1
s2
θ∈Un :kθ−θ∗ k≤t
√
√ p
2σt s1 + s2 2(α + 2) log n
Recall now the definition of the function fθ∗ : R+ → R as
fθ∗ (t) =

hz, θ − θ∗ i −

sup

θ∈Un :kθ−θ∗ k≤t

19

t2
.
2

(5.10)

Then on an event of probability not less than 1 − 4n−α , for all t ≥ 0 we have
s
r
 em∗ 
 e(n − m∗ ) 
√ p
t2
fθ∗ (t) ≤2σt s1 log
+ 2σt s2 log
+ 2 2σt 2(s1 + s2 )(α + 2) log n −
s1
s2
2
√ √
√
√
where we have also used s1 + s2 ≤ 2 s1 + s2 . Since the right side of the last display is a
quadratic in t, it can be verified that setting
s
r
 em∗ 
 e(n − m∗ ) 
√ p
t∗ = 2σ s1 log
+ 2σ s2 log
+ 2 2σ 2(s1 + s2 )(α + 2) log n
s1
s2
yields fθ∗ (t) < 0 for all t ≥ t∗ on an event of probability not less than 1 − 4n−α . A bound on (t∗ )2
can then be obtained by using the elementary inequality (a + b + c)2 ≤ 3(a2 + b2 + c2 ). The use
of Lemma 3.1 and an applications of Jensen’s inequality in the form




 ∗
e(n − m∗ )
en
em
+ s2 log
≤ (s1 + s2 ) log
s1 log
s1
s2
s1 + s2
then finishes the proof of the theorem.
6. Discussion
We have presented results on adaptivity of the least squares estimator in unimodal sequence estimation. Our results show that the risk is no worse than O(n−2/3 ) uniformly over all unimodal
sequences. More interestingly, we have shown that for the same least squares estimator, the risk
decays no slower than O s(θ∗ ) log n/n) where s(θ∗ ) is the number of “steps” in the true sequence.
Thus, the estimator achieves nearly parametric rates of convergence when the true sequence is simple. Our proof techniques exploit the structure of the space of unimodal sequences as a union of n
convex cones (Lemma 3.1), together with a peeling argument that bounds the log-covering number
of unimodal sequences in the neighborhood of a monotone sequence (Lemma 4.1).
Lemma 3.1 (the “LSE Slicing Lemma”) can potentially be used in any estimation problem
where the parameter space is a finite union of convex cones and the true mean vector has disjoint pieces lying in the intersection of these cones. It is the key ingredient used in our proof of
the adaptive risk bound in Theorem 2.2 for piecewise constant unimodal sequences. Using an appropriate approximation of any unimodal sequence by a piecewise constant unimodal sequence,
Theorem 2.2 and the slicing lemma could actually have been used to prove Theorem 2.1, but we
would have suffered an extra multiplicative log factor. We instead used a more direct peeling approach that resulted in tighter bounds.
A natural problem for further study is the multidimensional setting, observing that unimodality
generalizes as quasiconvexity in dimensions greater than one. It is also important to study oracle
inequalities, similar to those obtained for isotonic regression by Chatterjee et al. (2015a) and Bellec
20

(2016). As remarked in Section 2, however, existing proof techniques exploit convexity through
bounds on Gaussian widths and KKT conditions. Our Lemma 3.1 that exploits the structure as a
union of convex cones indicates such results may indeed be achievable, but we believe that new
proof techniques may be required. Before submitting the final version of this paper we became
aware of the fact that such oracle inequalities have recently appeared in Bellec (2015) and Flammarion et al. (2016).
Acknowledgements
The first author would like to thank Adityanand Guntuboyina and Bodhisattva Sen for helpful
discussions. Supported in part by NSF grant DMS-1513594 and ONR grant N00014-12-1-0762.
References
Amelunxen, D., Lotz, M., McCoy, M. B., and Tropp, J. A. (2014). Living on the edge: Phase
transitions in convex programs with random data. Information and Inference, 3(3):224–294.
Balabdaoui, F. and Jankowski, H. (2015). Maximum likelihood estimation of a unimodal probability mass function.
Barlow, R. E., Bartholomew, D. J., Bremner, J. M., and Brunk, H. D. (1972). Statistical inference
under order restrictions. The theory and application of isotonic regression. John Wiley & Sons,
London-New York-Sydney. Wiley Series in Probability and Mathematical Statistics.
Bellec, P. C. (2015). Sharp oracle inequalities for least squares estimators in shape restricted
regression. arXiv preprint arXiv:1510.08029.
Bellec, P. C. (2016). Sharp oracle inequalities for Least Squares estimators in shape restricted
regression. arXiv:1510.08029v2.
Bickel, P. J. and Fan, J. (1996). Some problems on the estimation of unimodal densities. Statistica
Sinica, 6(1):23–45.
Birgé, L. (1997). Estimation of unimodal densities without smoothness assumptions. The Annals
of Statistics, pages 970–981.
Birgé, L. and Massart, P. (1993). Rates of convergence for minimum contrast estimators. Probab.
Theory Related Fields, 97(1-2):113–150.
Boucheron, S., Lugosi, G., and Massart, P. (2013). Concentration inequalities: A nonasymptotic
theory of independence. Oxford university press.
Boyarshinov, V. and Magdon-Ismail, M. (2006). Linear time isotonic and unimodal regression in
the L1 and L∞ norms. Journal of Discrete Algorithms, 4(4):676–691.
21

Bro, R. and Sidiropoulos, N. (1998). Least squares algorithms under unimodality and nonnegativity constraints. J. Chemometrics, 12:223–247.
Chatterjee, S. (2014). A new perspective on least squares under convex constraint. The Annals of
Statistics, 42(6):2340–2381.
Chatterjee, S., Guntuboyina, A., and Sen, B. (2015a). On matrix estimation under monotonicity
constraints. arXiv preprint arXiv:1506.03430.
Chatterjee, S., Guntuboyina, A., Sen, B., et al. (2015b). On risk bounds in isotonic and other shape
restricted regression problems. The Annals of Statistics, 43(4):1774–1800.
Chatterjee, S. and Mukherjee, S. (2016). On estimation in tournaments and graphs under monotonicity constraints. arXiv:1603.04556.
Donoho, D. (1991). Gelfand n-widths and the method of least squares. Technical report, University
of California, Berkeley. Department of Statistics.
Eggermont, P. and LaRiccia, V. (2000). Maximum likelihood estimation of smooth monotone and
unimodal densities. Annals of Statistics, pages 922–947.
Flammarion, N., Mao, C., and Rigollet, P. (2016).
arXiv:1607.02435v1.

Optimal rates of statistical seriation.

Frisén, M. (1986). Unimodal regression. The Statistician, pages 479–485.
Gao, F. and Wellner, J. A. (2007). Entropy estimate for high-dimensional monotonic functions.
Journal of Multivariate Analysis, 98(9):1751–1764.
Grotzinger, S. and Witzgall, C. (1984). Projections onto order simplexes. Applied mathematics
and Optimization, 12(1):247–270.
Guntuboyina, A. and Sen, B. (2013). Global risk bounds and adaptation in univariate convex
regression. Probab. Theory Related Fields. accepted, available at http://arxiv.org/abs/1305.1648.
Köllmann, C., Bornkamp, B., and Ickstadt, K. (2014). Unimodal regression using bernstein–
schoenberg splines and penalties. Biometrics, 70(4):783–793.
Laurent, B. and Massart, P. (2000). Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pages 1302–1338.
Ledoux, M. (2001). The Concentration of Measure Phenomenon, volume 89 of Mathematical
Surveys and Monographs. American Mathematical Society.
Meyer, M. and Woodroofe, M. (2000). On the degrees of freedom in shape-restricted regression.
Ann. Statist., 28(4):1083–1104.

22

Meyer, M. C. (2001). An alternative unimodal density estimator with a consistent estimate of the
mode. Statistica Sinica, pages 1159–1174.
Shah, N. B., Balakrishnan, S., Guntuboyina, A., and Wainright, M. J. (2015). Stochastically transitive models for pairwise comparisons: Statistical and computational issues. arXiv preprint
arXiv:1510.05610.
Shoung, J.-M. and Zhang, C.-H. (2001). Least squares estimators of the mode of a unimodal
regression function. Annals of Statistics, pages 648–665.
Stout, Q. F. (2000). Optimal algorithms for unimodal regression. Ann Arbor, 1001:48109–2122.
Stout, Q. F. (2008). Unimodal regression via prefix isotonic regression. Computational Statistics
& Data Analysis, 53(2):289–297.
van de Geer, S. (1990). Estimating a regression function. Ann. Statist., 18(2):907–924.
Van de Geer, S. (1993). Hellinger-consistency of certain nonparametric maximum likelihood estimators. Ann. Statist., 21(1):14–44.
Van de Geer, S. (2000). Applications of Empirical Process Theory. Cambridge University Press.
Wang, Y. (1996). The l2 risk of an isotonic estimate. Comm. Statist. Theory Methods, 25:281–294.
Zhang, C.-H. (2002). Risk bounds in isotonic regression. Ann. Statist., 30(2):528–555.
Appendix A: Appendix
Lemma A.1. Let X1 , X2 . . . , Xn be random variables for which
 2

x
P Xi ≥ EXi + ax ≤ exp −
∀x ≥ 0
2
for every 1 ≤ i ≤ n and a > 0. Then


p
√ 
E max Xi ≤ max EXi + a
2 log n + 2π .
1≤i≤n

1≤i≤n

(A.1)

(A.2)

Proof. Let m = max1≤i≤n EXi . Define Yi = Xi − m. Then by (A.1) we have sub-Gaussian tail
behavior for every 1 ≤ i ≤ n,


x2
P(Yi ≥ x) ≤ exp − 2
∀x ≥ 0.
(A.3)
2a
Now by defining Zi = max{Yi , 0} we certainly have E max Yi ≤ E max Zi . Also for any x ≥ 0
we have P(max Zi ≥ x) = P(max Yi ≥ x). Using the tail integral formula for the expectation of a
23

nonnegative random variable we obtain
Z ∞
P(max Yi ≥ x) dx
E max Yi ≤
0


 
Z ∞
x2
min n exp − 2 , 1 dx
≤
2a
0


Z
∞
p
x2
= a 2 log n + √
n exp − 2 dx.
2a
a 2 log n
A standard fact about Gaussian tails give us the inequality


Z ∞
√ a
x2
exp
−
≤
2π ,
√
2a2
n
a 2 log n

(A.4)
(A.5)
(A.6)

(A.7)

which completes the proof of the lemma.
Lemma A.2. Let A ⊂ Rn be a closed set. Fix any θ∗ ∈ Rn and t > 0. Define the function
f : Rn → R as follows:
f (z) =
sup
hz, θ − θ∗ i.
(A.8)
θ∈A:kθ−θ∗ k≤t

Then f is a Lipschitz function of z with Lipschitz constant t.
Proof. Since the function hz, θ−θ∗ i is a continuous function of z and the set {θ ∈ A : kθ−θ∗ k ≤ t}
is compact, the supremum is attained, at θe say. Then we have
f (z) − f (z 0 ) = hz, θe − θ∗ i − f (z 0 )
≤ hz, θe − θ∗ i − hz 0 , θe − θ∗ i

(A.9)
(A.10)

= hz − z 0 , θe − θ∗ i
≤ kz − z 0 kkθe − θ∗ k

(A.11)

0

(A.13)

≤ tkz − z k.

(A.12)

The first inequality is because we set θ = θe instead of taking supremum over θ. The second
inequality is just the Cauchy Schwarz inequality, and the last inequality follows from the fact that
e
kθe − θ∗ k ≤ t by the choice of θ.
Lemma A.3. Let z be a standard d dimensional Gaussian vector with independent entries. Let
ΠM denote the projection operator onto the space M ⊂ Rd . Then we have the following pointwise
equality:
kΠM (z)k = sup hz, θi.
(A.14)
θ∈M:kθk≤1

Proof. We can use Lemma 3.1 to prove this equality. Here C = M and hence C is a convex set.
Take the zero vector in C. Then the least squares estimator θb is the same as ΠM (z) and Lemma 3.1
implies
!
t2
kΠM (z)k = arg max
sup hz, θi −
.
(A.15)
2
t≥0
θ∈M:kθk≤t
24

Now since the space M is a cone we can rewrite the last equation as
2

kΠM (z)k = arg max t
t≥0

sup

hz, θi −

θ∈M:kθk≤1

t
2

!
.

(A.16)

The right side above is the maximizer of a concave quadratic in t; differentiating with respect to t
to compute the maximizer finishes the proof.
Lemma A.4. Let g(t) : R+ → R be defined as
g(t) =

sup

ha, θi

θ∈C∩{v∈Rn :kvk≤t}

where C ⊂ Rn is a closed convex set and a is a fixed vector in Rn . Then g is a concave function.
Proof. We have to show that for any t1 , t2 > 0 and 0 ≤ λ ≤ 1 we have
g(λt1 + (1 − λ)t2 ) ≥ λg(t1 ) + (1 − λ)g(t2 ).

(A.17)

Let θ1 ∈ C ∩ {v ∈ Rn : kvk ≤ t1 } and θ2 ∈ C ∩ {v ∈ Rn : kvk ≤ t2 } be where the values
g(t1 ) and g(t2 ) are achieved. Such a θ1 and θ2 exist because C is closed and {v ∈ Rn : kvk ≤ t}
is closed and bounded. Now consider the point θ3 = λθ1 + (1 − λ)θ2 . Since C is convex, θ3 ∈ C
and since the Euclidean squared norm is a convex function we also have kθ3 k ≤ t. Now we have
λg(t1 ) + (1 − λ)g(t2 ) = ha, θ3 i ≤ g(λt1 + (1 − λ)t2 )

(A.18)

where the first equality is because of linearity of the inner product function and the last inequality
is because of feasibility of θ3 . This finishes the proof of the lemma.

25

