The geometry of hypothesis testing over convex cones:
Generalized likelihood tests and minimax radii
Yuting Wei†

Martin J. Wainwright†,?

Adityanand Guntuboyina†

arXiv:1703.06810v2 [] 26 Mar 2018

March 28, 2018
Department of Statistics† , and
Department of Electrical Engineering and Computer Sciences?
UC Berkeley, Berkeley, CA 94720

Abstract
We consider a compound testing problem within the Gaussian sequence model in which
the null and alternative are specified by a pair of closed, convex cones. Such cone testing
problem arises in various applications, including detection of treatment effects, trend detection
in econometrics, signal detection in radar processing, and shape-constrained inference in nonparametric statistics. We provide a sharp characterization of the GLRT testing radius up to a
universal multiplicative constant in terms of the geometric structure of the underlying convex
cones. When applied to concrete examples, this result reveals some interesting phenomena that
do not arise in the analogous problems of estimation under convex constraints. In particular,
in contrast to estimation error, the testing error no longer depends purely on the problem
complexity via a volume-based measure (such as metric entropy or Gaussian complexity); other
geometric properties of the cones also play an important role. In order to address the issue of
optimality, we prove information-theoretic lower bounds for the minimax testing radius again in
terms of geometric quantities. Our general theorems are illustrated by examples including the
cases of monotone and orthant cones, and involve some results of independent interest.

1

Introduction

Composite testing problems arise in a wide variety of applications and the generalized likelihood
ratio test (GLRT) is a general purpose approach to such problems. The basic idea of the likelihood ratiotest dates back to the early works of Fisher, Neyman and Pearson; it attracted further
attention following the work of Edwards [15], who emphasized likelihood as a general principle of
inference. Recent years have witnessed a great amount of work on the GLRT in various contexts,
including the papers [27, 37, 26, 18, 17]. However, despite the wide-spread use of the GLRT, its
optimality properties have yet to be fully understood. For suitably regular problems, there is a
great deal of asymptotic theory on the GLRT, and in particular when its distribution under the
null is independent of nuisance parameters (e.g., [3, 42, 39]). On the other hand, there are some
isolated cases in which the GLRT can be shown to dominated by other tests (e.g., [52, 33, 32, 26]).
In this paper, we undertake an in-depth study of the GLRT in application to a particular class
of composite testing problems of a geometric flavor. In this class of testing problems, the null
and alternative hypotheses are specified by a pair of closed convex cones C1 and C2 , taken to be
1

nested as C1 ⊂ C2 . Suppose that we are given an observation of the form y = θ + w, where w
is a zero-mean Gaussian noise vector. Based on observing y, our goal is to test whether a given
parameter θ belongs to the smaller cone C1 —corresponding to the null hypothesis—or belongs to
the larger cone C2 . Cone testing problems of this type arise in many different settings, and there
is a fairly substantial literature on the behavior of the GLRT in application to such problems (e.g.,
see the papers and books [8, 25, 40, 39, 41, 44, 35, 33, 34, 14, 47, 52], as well as references therein).

1.1

Some motivating examples

Before proceeding, let us consider some concrete examples so as to motivate our study.
Example 1 (Testing non-negativity and monotonicity in treatment effects). Suppose that we have
a collection of d treatments, say different drugs for a particular medical condition. Letting θj ∈ R
denote the mean of treatment j, one null hypothesis could be that none of treatments has any
effect—that is, θj = 0 for all j = 1, . . . , d. Assuming that none of the treatments are directly
harmful, a reasonable alternative would be that θ belongs to the non-negative orthant cone

K+ : = θ ∈ Rd | θj ≥ 0 for all j = 1, . . . , d .
(1)
This set-up leads to a particular instance of our general set-up with C1 = {0} and C2 = K+ . Such
orthant testing problems have been studied by Kudo [25] and Raubertas et al. [39], among other
people.
In other applications, our treatments might consist of an ordered set of dosages of the same
drug. In this case, we might have reason to believe that if the drug has any effect, then the
treatment means would obey a monotonicity constraint—that is, with higher dosages leading to
greater treatment effects. One would then want to detect the presence or absence of such a dose
response effect. Monotonicity constraints also arise in various types of econometric models, in
which the effects of strategic interventions should be monotone with respect to parameters such as
market size (e.g.,[13]). For applications of this flavor, a reasonable alternative would be specified
by the monotone cone

M : = θ ∈ Rd | θ1 ≤ θ2 ≤ · · · ≤ θd .
(2)
This set-up leads to another instance of our general problem with C1 = {0} and C2 = M . The
behavior of the GLRT for this particular testing problem has also been studied in past works,
including papers by Barlow et al. [3], and Raubertas et al. [39].
As a third instance of the treatment effects problem, we might like to include in our null
hypothesis the possibility that the treatments have some (potentially) non-zero effect but one that
remains constant across levels—i.e., θ1 = θ2 = · · · = θd . In this case, our null hypothesis is specified
by the ray cone

R : = θ ∈ Rd | θ = c1 for some c ∈ R .
(3)
Supposing that we are interested in testing the alternative that the treatments lead to a monotone
effect, we arrive at another instance of our general set-up with C1 = R and C2 = M . This
2

testing problem has also been studied by Bartholomew [4, 5] and Robertson et al. [43] among other
researchers.
In the preceding three examples, the cone C1 was linear subspace. Let us now consider two
more examples, adapted from Menendnez et al. [34], in which C1 is not a subspace. As before,
suppose that component θi of the vector θ ∈ Rd denotes the expected response of treatment i. In
many applications, it is of interest to test equality of the expected responses of a subset S of the
full treatment set [d] = {1, . . . , d}. More precisely, for a given subset S containing the index 1, let
us consider the problem of testing the the null hypothesis
n
o
C1 ≡ E(S) : = θ ∈ Rd | θi = θ1 ∀ i ∈ S, and θj ≥ θ1 ∀ j ∈
/S
(4)
versus the alternative C2 ≡ G(S) = {θ ∈ Rd | θj ≥ θ1 ∀ j ∈ [d]}. Note that C1 here is not a linear
subspace.
As a final example, suppose that we have a factorial design consisting of two treatments, each
of which can be applied at two different dosages (high and level). Let (θ1 , θ2 ) denote the expected
responses of the first treat at the low and high dosages, respectively, with the pair (θ3 , θ4 ) defined
similarly for the second treatment. Suppose that we are interesting in testing whether the first
treatment at the lowest level is more effective than the second treatment at the highest level. This
problem can be formulated as testing the null cone
C1 : = {θ ∈ R4 | θ1 ≤ θ2 ≤ θ3 ≤ θ4 } versus the alternative
C2 : = {θ ∈ R4 | θ1 ≤ θ2 , and θ3 ≤ θ4 }.

(5)

As before, the null cone C1 is not a linear subspace.
Example 2 (Robust matched filtering in signal processing). In radar detection problems [45], a
standard goal is to detect the presence of a known signal of unknown amplitude in the presence
of noise. After a matched filtering step, this problem can be reduced to a vector testing problem,
where the known signal direction is defined by a vector γ ∈ Rd , whereas the unknown amplitude
corresponds to a scalar pre-factor c ≥ 0. We thus arrive at a ray cone testing problem: the null
hypothesis (corresponding to the absence
of signal) is given C1 = {0}, whereas the alternative is

given by the positive ray cone R+ = θ ∈ Rd | θ = cγ for some c ≥ 0 .
In many cases, there may be uncertainty about the target signal, or jamming by adversaries,
who introduce additional signals that can be potentially confused with the target signal γ. Signal
uncertainties of this type are often modeled by various forms of cones, with the most classical choice
being a subspace cone [45]. In more recent work (e.g., [8, 20]), signal uncertainty has been modeled
using the circular cone defined by the target signal direction, namely

C(γ; α) : = θ ∈ Rd | hγ, θi ≥ cos(α) kγk2 kθk2 ,
(6)
corresponding to the set of all vectors θ that have angle at least α with the target signal. Thus, we
are led to another instance of a cone testing problem involving a circular cone.
Example 3 (Cone-constrained testing in linear regression). Consider the standard linear regression
model
y = Xβ + σZ,

where Z ∼ N (0, In ),
3

(7)

where X ∈ Rn×p is a fixed and known design matrix. In many applications, we are interested in
testing certain properties of the unknown regression vector β, and these can often be encoded in
terms of cone-constraints on the vector θ : = Xβ. As a very simple example, the problem of testing
whether or not β = 0 corresponds to testing whether θ ∈ C1 : = {0} versus the alternative that
θ ∈ C2 : = range(X). Thus, we arrive at a subspace testing problem. We note this problem is known
as testing the global null in the linear regression literature (e.g., [10]). If instead we consider the
case when the p-dimensional vector β lies in the non-negative orthant cone (1), then our alternative
for the n-dimensional vector θ becomes the polyhedral cone

P : = θ ∈ Rn | θ = Xβ for some β ≥ 0 .
(8)
The corresponding estimation problem with non-negative constraints on the coefficient vector β
has been studied by Slawski et al. [48] and Meinshausen [31]; see also Chen et al. [12] for a survey
of this line of work. In addition to these preceding two cases, we can also test various other types
of cone alternatives for β, and these are transformed via the design matrix X into other types of
cones for the parameter θ ∈ Rn .
Example 4 (Testing shape-constrained departures from parametric models). Our third example
is non-parametric in flavor. Consider the class of functions f that can be decomposed as
f=

k
X

aj φj + ψ.

(9)

j=1

Here the known functions {φj }kj=1 define a linear space, parameterized by the coefficient vector
a ∈ Rk , whereas the unknown function ψ models a structured departure from this linear parametric class. For instance, we might assume that ψ belongs to the class of monotone functions,
or the class of convex functions. Given a fixed collection of design points {ti }ni=1 , suppose that
we make observations of the form yi = f (ti ) + σgi for i = 1, . . . , n, where each gi is a standard
normal variable. Defining the shorthand notation θ : = f (t1 ), . . . , f (tn ) and g = (g1 , . . . , gn ),
our observations can be expressed in the standard form y = θ + σg. If, under the null hypothesis,
the function f satisfies the decomposition (9) with ψ = 0, then the vector θ must belong to the
subspace {Φa | a ∈ Rk }, where the matrix Φ ∈ Rn×k has entries Φij = φj (xi ).
Now suppose that the alternative is that f satisfies the decomposition (9) with some ψ that is
convex. A convexity constraint on ψ implies that we can write θ = Φa + γ, for some coefficients
a ∈ Rk and a vector γ ∈ Rn belonging to the convex cone
n
γ2 − γ1
γ3 − γ2
γn − γn−1 o
V ({ti }ni=1 ) : = γ ∈ Rn |
≤
≤ ··· ≤
.
(10)
t2 − t1
t3 − t2
tn − tn−1
This particular cone testing problem and other forms of shape constraints have been studied by
Meyer [35], as well as by Sen and Meyer [46].

1.2

Problem formulation

Having understood the range of motivations for our problem, let us now set up the problem more
precisely. Suppose that we are given observations of the form y = θ + σg, where θ ∈ Rd is a fixed
4

but unknown vector, whereas g ∼ N (0, Id ) is a d-dimensional vector of i.i.d. Gaussian entries and
σ 2 is a known noise level. Our goal is to distinguish the null hypothesis that θ ∈ C1 versus the
alternative that θ ∈ C2 \C1 , where C1 ⊂ C2 are a nested pair of closed, convex cones in Rd .
In this paper, we study both the fundamental limits of solving this composite testing problem,
as well as the performance of a specific procedure, namely the generalized likelihood ratio test, or
GLRT for short. By definition, the GLRT for the problem of distinguishing between cones C1 and
C2 is based on the statistic


supθ∈C1 Pθ (y)
T (y) : = −2 log
.
(11a)
supθ∈C2 Pθ (y)
It defines a family of tests, parameterized by a threshold parameter β ∈ [0, ∞), of the form
(
1 if T (y) ≥ β
φβ (y) : = I(T (y) ≥ β) =
(11b)
0 otherwise.
Thus far, our formulation of the testing problem allows for the possibility that θ lies in the
set C2 \C1 , but is arbitrarily close to some element of C1 . Thus, under this formulation, it is not
possible to make any non-trivial assertions about the power of the GLRT nor any other test in a
uniform sense. Accordingly, so as to be able to make quantitative statements about the performance
of different statements, we exclude a certain -ball from the alternative. This procedure leads to
the notion of the minimax testing radius associated this composite decision problem. This minimax
formulation was introduced in the seminal work of Ingster and co-authors [22, 23]; since then, it
has been studied by many authors (e.g., [16, 49, 28, 29, 2]).
For a given  > 0, we define the -fattening of the cone C1 as

B2 (C1 ; ) : = θ ∈ Rd | min kθ − uk2 ≤  ,
u∈C1

(12)

corresponding to the set of vectors in Rd that are at most Euclidean distance  from some element
of C1 . We then consider the testing problem of distinguishing between the two hypotheses
H0 : θ ∈ C1

and H1 : θ ∈ C2 \B2 (C1 ; ).

(13)

To be clear, the parameter  > 0 is a quantity that is used during the course of our analysis in
order to titrate the difficulty of the testing problem. All of the tests that we consider, including
the GLRT, are not given knowledge of . Let us introduce shorthand T (C1 , C2 ; ) to denote this
testing problem (13).
Obviously, the testing problem (13) becomes more difficult as  approaches zero, and so it is
natural to study this increase in quantitative terms. Letting ψ : Rd → {0, 1} be any (measurable)
test function, we measure its performance in terms of its uniform error
E(ψ; C1 , C2 , ) : = sup Eθ [ψ(y)] +

sup

Eθ [1 − ψ(y)],

θ∈C2 \B2 (;C1 )

θ∈C1

which controls the worst-case error over both null and alternative.
5

(14)

For a given error level ρ ∈ (0, 1), we are interested in the smallest setting of  for which either
the GLRT, or some other test ψ has uniform error at most ρ. More precisely, we define
n
o
OPT (C1 , C2 ; ρ) : = inf  | inf E(ψ; C1 , C2 , ) ≤ ρ , and
(15a)
ψ
n
o
GLR (C1 , C2 ; ρ) : = inf  | inf E(φβ ; C1 , C2 , ) ≤ ρ .
(15b)
β∈R

When the subspace-cone pair (C1 , C2 ) are clear from the context, we occasionally omit this dependence, and write OPT (ρ) and GLR (ρ) instead. We refer to these two quantities as the minimax
testing radius and the GLRT testing radius respectively.
By definition, the minimax testing radius OPT corresponds to the smallest separation  at which
there exists some test that distinguishes between the hypotheses H0 and H1 in equation (13) with
uniform error at most ρ. Thus, it provides a fundamental characterization of the statistical difficulty
of the hypothesis testing. On the other hand, the GLRT testing radius GLR (ρ) provides us with
the smallest radius  for which there exists some threshold —say β ∗ — for which the associated
generalized likelihood ratio test φβ ∗ distinguishes between the hypotheses with error at most ρ.
Thus, it characterizes the performance limits of the GLRT when an optimal threshold β ∗ is chosen.
Of course, by definition, we always have OPT (ρ) ≤ GLR (ρ). We write OPT (ρ)  GLR (ρ) to mean
that—in addition to the previous upper bound—there is also a lower bound OPT (ρ) ≥ cρ GLR (ρ)
that matches up to a constant cρ > 0 depending only on ρ.

1.3

Overview of our results

Having set up the problem, let us now provide a high-level overview of the main results of this
paper.
• Our first main result, stated as Theorem 1 in Section 3.1, gives a sharp characterization—
meaning upper and lower bounds that match up to universal constants—of the GLRT testing
radius GLR for cone pairs (C1 , C2 ) that are non-oblique (we discuss the non-obliqueness property
and its significance at length in Section 2.2). We illustrate the consequences of this theorem for
a number of concrete cones, include the subspace cone, orthant cone, monotone cone, circular
cone and a Cartesian product cone.
• In our second main result, stated as Theorem 2 in Section 3.2, we derive a lower bound that
applies to any testing function. It leads to a corollary that provides sufficient conditions for the
GLRT to be an optimal test, and we use it to establish optimality for the subspace cone and
circular cone, among other examples. We then revisit the Cartesian product cone, first analyzed
in the context of Theorem 1, and use Theorem 2 to show that the GLRT is sub-optimal for this
particular cone, even though it is in no sense a pathological example.
• For the monotone and orthant cones, we find that the lower bound established in Theorem 2 is
not sharp, but that the GLRT turns out to be an optimal test. Thus, Section 3.3 is devoted to a
detailed analysis of these two cases, in particular using a more refined argument to obtain sharp
lower bounds.
The remainder of this paper is organized as follows: Section 2 provides background on conic
6

geometry, including conic projections, the Moreau decomposition, and the notion of Gaussian width.
It also introduces the notion of a non-oblique pair of cones, which have been studied in the context
of the GLRT. In Section 3, we state our main results and illustrate their consequences via a series of
examples. Sections 3.1 and 3.2 are devoted, respectively, to our sharp characterization of the GLRT
and a general lower bound on the minimax testing radius. Section 3.3 explores the monotone and
orthant cones in more detail. In Section 4, we provide the proofs of our main results, with certain
more technical aspects deferred to the appendix sections.
Notation Here we summarize some notation used throughout the remainder of this paper. For
functions f (σ, d) and g(σ, d), we write f (σ, d) . g(σ, d) to indicate that f (σ, d) ≤ cg(σ, d) for
some constant c ∈ (0, ∞) that may only depend on ρ but independent of (σ, d), and similarly for
f (σ, d) & g(σ, d). We write f (σ, d)  g(σ, d) if both f (σ, d) . g(σ, d) and f (σ, d) & g(σ, d) are
satisfied.

2

Background on conic geometry and the GLRT

In this section, we provide some necessary background on cones and their geometry, including the
notion of a polar cone and the Moreau decomposition. We also define the notion of a non-oblique
pair of cones, and summarize some known results about properties of the GLRT for such cone
testing problems.

2.1

Convex cones and Gaussian widths

For a given closed convex cone C ⊂ Rd , we define the Euclidean projection operator ΠC : Rd → C
via
ΠC (v) : = arg min kv − uk2 .
u∈C

(16)

By standard properties of projection onto closed convex sets, we are guaranteed that this mapping
is well-defined. We also define the polar cone

C ∗ : = v ∈ Rd | hv, ui ≤ 0 for all u ∈ C .
(17)
Figure 1(b) provides an illustration of a cone in comparison to its polar cone. Using ΠC ∗ to denote
the projection operator onto this cone, Moreau’s theorem [36] ensures that every vector v ∈ Rd can
be decomposed as
v = ΠC (v) + ΠC ∗ (v),

and such that hΠC (v), ΠC ∗ (v)i = 0.

(18)

We make frequent use of this decomposition in our analysis.
Let S : = {u ∈ Rd | kuk2 = 1} denotes the Euclidean sphere of unit radius. For every set A ⊆ S ,
we define its Gaussian width as


W(A) : = E suphu, gi
where g ∼ N (0, Id ).
(19)
u∈A

7

This quantity provides a measure of the size of the set A; indeed, it can be related to the volume
of A viewed as a subset of the Euclidean sphere. The notion of Gaussian width arises in many
different areas, notably in early work on probabilistic methods in Banach spaces [38]; the Gaussian
complexity, along with its close relative the Rademacher complexity, plays a central role in empirical
process theory [50, 24, 6].
Of interest in this paper are the Gaussian widths of sets of the form A = C ∩ S , where C is
a closed convex cone. For a set of this form, using the Moreau decomposition (18), we have the
useful equivalence


W(C ∩ S ) = E sup hu, ΠC (g) + ΠC ∗ (g)i = EkΠC (g)k2 ,
(20)
u∈C∩S

where the final equality uses the fact that hu, ΠC ∗ (g)i ≤ 0 for all vectors u ∈ C, with equality
holding when u is a non-negative scalar multiple of ΠC (g).
For future reference, let us derive a lower bound on EkΠC gk2 that holds for every cone C strictly
larger than {0}. Take some non-zero vector u ∈ C and let R+ = {cu | c ≥ 0} be the ray that it
defines. Since R+ ⊆ C, we have kΠC gk2 ≥ kΠR+ gk2 . But since R+ is just a ray, the projection
ΠR+ (g) is a standard normal variable truncated to be positive, and hence
r
EkΠC gk2 ≥ EkΠR+ gk2 =

1
.
2π

(21)

This lower bound is useful in parts of our development.

2.2

Cone-based GLRTs and non-oblique pairs

In this section, we provide some background on the notion of non-oblique pairs of cones, and their
significance for the GLRT. First, let us exploit some properties of closed convex cones in order to
derive a simpler expression for the GLRT test statistic (11a). Using the form of the multivariate
Gaussian density, we have
T (y) = min ky − θk22 − min ky − θk22 = ky − ΠC1 (y)k22 − ky − ΠC2 (y)k22
θ∈C1

θ∈C2

= kΠC2 (y)k22 − kΠC1 (y)k22 ,

(22)
(23)

where we have made use of the Moreau decomposition to assert that
ky − ΠC1 (y)k22 = kyk22 − kΠC1 (y)k22 ,

and ky − ΠC2 (y)k22 = kyk22 − kΠC2 (y)k22 .

Thus, we see that a cone-based GLRT has a natural interpretation: it compares the squared
amplitude of the projection of y onto the two different cones.
When C1 = {0}, then it can be shown that under the null hypothesis (i.e., y ∼ N (0, σ 2 Id )), the
statistic T (y) (after rescaling by σ 2 ) is a mixture of χ2 -distributions (see e.g., [39]). On the other
hand, for a general cone pair (C1 , C2 ), it is not straightforward to characterize the distribution of
T (y) under the null hypothesis. Thus, past work has studied conditions on the cone pair under
8

which the null distribution has a simple characterization. One such condition is a certain nonobliqueness property that is common to much past work on the GLRT (e.g., [52, 33, 34, 21]). The
non-obliqueness condition, first introduced by Warrack et al. [52], is also motivated by the fact that
are many instances of oblique cone pairs for which the GLRT is known to dominated by other tests.
Menendez et al. [32] provide an explanation for this dominance in a very general context; see also
the papers [34, 21] for further studies of non-oblique cone pairs.
A nested pair of closed convex cones C1 ⊂ C2 is said to be non-oblique if we have the successive
projection property
ΠC1 (x) = ΠC1 (ΠC2 (x))

for all x ∈ Rd .

(24)

For instance, this condition holds whenever one of the two cones is a subspace, or more generally,
whenever there is a subspace L such that C1 ⊆ L ⊆ C2 ; see Hu and Wright [21] for details
of this latter property. To be clear, these conditions are sufficient—but not necessary—for nonobliqueness to hold. There are many non-oblique cone pairs in which neither cone is a subspace; the
cone pairs (4) and (5), as discussed in Example 1 on treatment testing, are two such examples. (We
refer the reader to Section 5 of the paper [34] for verification of these properties.) More generally,
there are various non-oblique cone pairs that do not sandwich a subspace L.
The significance of the non-obliqueness condition lies in the following decomposition result. For
any nested pair of closed convex cones C1 ⊂ C2 that are non-oblique, for all x ∈ Rd we have
and hΠC1 (x), ΠC2 ∩C1∗ (x)i = 0.

ΠC2 (x) = ΠC1 (x) + ΠC2 ∩C1∗ (x)

(25)

This decomposition follows from general theory due to Zarantonello [54], who proves that for nonoblique cones, we have ΠC2 ∩C1∗ = ΠC1∗ ΠC2 —in particular, see Theorem 5.2 in his paper.
An immediate consequence of the decomposition (25) is that the GLRT for any non-oblique
cone pair (C1 , C2 ) can be written as
T (y) = kΠC2 (y)k22 − kΠC1 (y)k22 = kΠC2 ∩C1∗ (y)k22
= kyk22 −

min

θ∈C2 ∩C1∗

ky − θk22 .

Consequently, we see that the GLRT for the pair (C1 , C2 ) is equivalent to—that is, determined by
the same statistic as—the GLRT for testing the reduced hypothesis

e0 : θ = 0 versus H
e1 : θ ∈ C2 ∩ C1∗ \B2 ().
H
(26)
Following the previous notation, write it as T ({0}, C2 ∩ C1∗ ; ) and we make frequent use of this
convenient reduction in the sequel.

3

Main results and their consequences

We now turn to the statement of our main results, along with a discussion of some of their consequences. Section 3.1 provides a sharp characterization of the minimax radius for the generalized
9

likelihood ratio test up to a universal constant, along with a number of concrete examples. In
Section 3.2, we state and prove a general lower bound on the performance of any test, and use it
to establish the optimality of the GLRT in certain settings, as well as its sub-optimality in other
settings. In Section 3.3, we revisit and study in details two cones of particular interest, namely the
orthant and monotone cones.

3.1

Analysis of the generalized likelihood ratio test

Let (C1 , C2 ) be a nested pair of closed cones C1 ⊆ C2 that are non-oblique (24). Consider the polar
cone C1∗ as well as the intersection cone K = C2 ∩ C1∗ . Letting g ∈ Rd denote a standard Gaussian
random vector, we then define the quantity
(
)

2
EkΠK gk2
2
δLR (C1 , C2 ) : = min EkΠK gk2 ,
.
(27)
max{0, inf hη, EΠK gi}
η∈K∩S

2 (C , C ) is a purely geometric object, depending on the pair (C , C ) via the new cone
Note that δLR
1
2
1
2
K = C2 ∩ C1∗ , which arises due to the GLRT equivalence (26) discussed previously.

Recall that the GLRT is based on applying a threshold, at some level β ∈ [0, ∞), to the likelihood
ratio statistic T (y); in particular, see equations (11a) and (11b). In the following theorem, we
study the performance of the GLRT in terms of the the uniform testing error E(φβ ; C1 , C2 , ) from
equation (14). In particular, we show that the critical testing radius for the GLRT is governed by
2 (C , C ).
the geometric parameter δLR
1
2
Theorem 1. There are numbers {(bρ , Bρ ), ρ ∈ (0, 1/2)} such that for every pair of non-oblique
closed convex cones (C1 , C2 ) with C1 strictly contained within C2 :
(a) For every error probability ρ ∈ (0, 0.5), we have
inf
β∈[0,∞)

2 (C , C ).
for all 2 ≥ Bρ σ 2 δLR
1
2

E(φβ ; C1 , C2 , ) ≤ ρ

(28a)

(b) Conversely, for every error probability ρ ∈ (0, 0.11], we have
inf
β∈[0,∞)

2 (C , C ).
for all 2 ≤ bρ σ 2 δLR
1
2

E(φβ ; C1 , C2 , ) ≥ ρ

(28b)

Remarks While our proof leads to universal values for the constants Bρ and bρ , we have made
no efforts to obtain the sharpest possible ones, so do not state them here. In any case, our main
interest is to understand the scaling of the testing radius with respect to σ and the geometric
parameters of the problem. In terms of the GLRT testing radius GLR previously defined (15b),
Theorem 1 establishes that
GLR (C1 , C2 ; ρ)  σ δLR (C1 , C2 ),

10

(29)

where  denotes equality up to constants depending on ρ, but independent of all other problem
parameters. Since GLR always upper bounds OPT for every fixed level ρ, we can also conclude from
Theorem 1 that
OPT (C1 , C2 ; ρ) . σ δLR (C1 , C2 ).
2 (C , C ) depends on the pair (C , C ) only via the new
It is worthwhile noting that the quantity δLR
1
2
1
2
∗
cone K = C2 ∩ C1 . Indeed, as discussed in Section 2.2, for any pair of non-oblique closed convex
cones, the GLRT for the original testing problem (13) is equivalent to the GLRT for the modified
testing problem T ({0}, K; ).
2 (C , C ) from equation (27) is defined via the minima of two
Observe that the quantity δLR
1
2
terms. The first term EkΠK gk2 is the (square root of the) Gaussian width of the cone K, and is
a familiar quantity from past work on least-squares estimation involving convex sets [51, 11]. The
Gaussian width measure the size of the cone K, and it is to be expected that the minimax testing
radius should grow with this size, since K characterizes the set of possible alternatives. The second
term involving the inner product hη, EΠK gi is less immediately intuitive, partly because no such
term arises in estimation over convex sets. The second term becomes dominant in cones for which
the expectation v ∗ : = E[ΠK g] is relatively large; for such cones, we can test between the null and
alternative by performing a univariate test after projecting the data onto the direction v ∗ . This
possibility only arises for cones that are more complicated than subspaces, since E[ΠK g] = 0 for
any subspace K.

Finally, we note that Theorem 1 gives a sharp characterization of the behavior of the GLRT up
to a constant. It is different from the usual minimax guarantee. To the best of our knowledge, it
is the first result to provide tight upper and lower control on the uniform performance of a specific
test.
3.1.1

Consequences for convex set alternatives

Although Theorem 1 applies to cone-based testing problems, it also has some implications for a
more general class of problems based on convex set alternatives. In particular, suppose that we are
interested in the testing problem of distinguishing between
H0 : θ = θ0 ,

versus

H1 : θ ∈ S,

(30)

where S is a not necessarily a cone, but rather an arbitrary closed convex set, and θ0 is some vector
such that θ0 ∈ S. Consider the tangent cone of S at θ0 , which is given by
TS (θ) : = {u ∈ Rd | there exists some t > 0 such that θ + tu ∈ S .

(31)

Note that TS (θ0 ) contains the shifted set S − θ0 . Consequently, we have
E(ψ; {0}, S − θ0 , ) ≤ Eθ=0 [ψ(y)] +

sup

Eθ [1 − ψ(y)] = E(ψ; {0}, TS (θ0 ), ),

θ∈TS (θ0 )\B2 (0;)

which shows that the tangent cone testing problem
H0 : θ = 0

versus H1 : θ ∈ TS (θ0 ),
11

(32)

is more challenging than the original problem (30). Thus, applying Theorem 1 to this cone-testing
problem (32), we obtain the following:
Corollary 1. For the convex set testing problem (30), we have
(
)

2
EkΠ
gk
2
TS (θ0 )
2OPT (θ0 , S; ρ) . σ 2 min EkΠTS (θ0 ) gk2 ,
.
max{0,
inf
hη, EΠTS (θ0 ) gi}

(33)

η∈TS (θ0 )∩S

This upper bound can be achieved by applying the GLRT to the tangent cone testing problem (32).
This corollary offers a general recipe of upper bounding the optimal testing radius. In Subsection 3.1.6, we provide an application of Corollary 1 to the problem of testing
H0 : θ = θ 0

versus

H1 : θ ∈ M,

where M is the monotone cone (defined in expression (2)). When θ0 6= 0, this is not a cone testing
problem, since the set {θ0 } is not a cone. Using Corollary 1, we prove an upper bound on the
optimal testing radius for this problem in terms of the number of constant pieces of θ0 .
In the remainder of this section, we consider some special cases of testing a cone K versus {0}
in order to illustrate the consequences of Theorem 1. In all cases, we compute the GLRT testing
radius for a constant error probability, and so ignore the dependencies on ρ. For this reason, we
adopt the more streamlined notation GLR (K) for the radius GLR ({0}, K; ρ).
3.1.2

Subspace of dimension k

Let us begin with an especially simple case—namely, when K is equal to a subspace Sk of dimension
k ≤ d. In this case, the projection ΠK is a linear operator, which can be represented by matrix
multiplication using a rank k projection matrix. By symmetry of the Gaussian distribution, we
have E[ΠK g] = 0. Moreover, by rotation invariance of the Gaussian distribution, the random vector
kΠK gk22 follows a χ2 -distribution with k degrees of freedom, whence
√
q
√
k
≤ EkΠK gk2 ≤
EkΠK gk22 = k.
2
Applying Theorem 1 then yields that the testing radius of the GLRT scales as
√
2GLR (Sk )  σ 2 k.

(34)

Here our notation  denotes equality up to constants independent of (σ, k); we have omitted dependence on the testing error ρ so as to simplify notation, and will do so throughout our discussion.
3.1.3

Circular cone

A circular cone in Rd with constant angle α ∈ (0, π/2) is given by Circd (α) : = {θ ∈ Rd | θ1 ≥
kθk2 cos(α)}. In geometric terms, it corresponds to the set of all vectors whose angle with the
12

standard basis vector e1 = (1, 0, . . . , 0) is at most α radians. Figure 1(a) gives an illustration of a
circular cone.

(a)

(b)

Figure 1. (a) A 3-dimensional circular cone with angle α. (b) Illustration of a cone versus its polar
cone.

Suppose that we want to test the null hypothesis θ = 0 versus the cone alternative K = Circd (α).
We claim that, in application to this particular cone, Theorem 1 implies that
√
2GLR (K)  σ 2 min
d, 1 = σ 2 ,
(35)
where  denotes equality up to constants depending on (ρ, α), but independent of all other problem
parameters.
In order to apply Theorem 1, we need to evaluate both terms that define the geometric quantity
LR (C1 , C2 ). On one hand, by symmetry of the cone K = Circd (α) in its last (d − 1)-coordinates,
we have EΠK g = βe1 for some scalar β > 0 and e1 denotes the standard Euclidean basis vector
with a 1 in the first coordinate. Moreover, for any η ∈ K ∩ S , we have η1 ≥ cos(α), and hence
δ2

inf hη, EΠK gi = η1 β ≥ cos(α)β = cos(α)kEΠK gk2 .

η∈K∩S

Next, we claim that kEΠK gk2  EkΠK gk2 . In order to prove this claim, note that Jensen’s
inequality yields
(a)

(b)

EkΠK gk2 ≥ kEΠK gk2 ≥ (EΠCircd (α) g)1 = E(ΠCircd (α) g)1 ≥ EkΠCircd (α) gk2 cos(α),

(36)

where in this argument, inequality (a) follows from simply fact that kxk2 ≥ |x1 | whereas inequality
2 (C , C ), the corre(b) follows from the definition of circular cone. Plugging into definition δLR
1
2
sponding second term equals to a constant. Therefore, the second term in the definition (27) of
2 (C , C ) is upper bounded by a constant, independent of the dimension d.
δLR
1
2
13

On the other hand, from known results on circular cones (see §6.3, [30]), there are constants
κj = κj (α) for j = 1, 2 such that κ1 d ≤ EkΠK gk22 ≤ κ2 d. Moreover, we have
(a)

(b)

EkΠK gk22 − 4 ≤ (EkΠK gk2 )2 ≤ EkΠK gk22 .
Here inequality (b) is an immediate consequence of Jensen’s inequality, whereas inequality (a)
follows from the fact that var(kΠK gk2 ) ≤ 4—see Lemma D.1 in Section 4.1
√ and the surrounding
discussion for details. Putting together the pieces, we see that EkΠK gk2  d for the circular cone.
Combining different elements of our argument leads to the stated claim (35).
3.1.4

A Cartesian product cone

We now consider a simple extension of the previous two examples—namely, a convex cone formed
by taking the Cartesian product of the real line R with the circular cone Circd−1 (α)—that is
K× : = Circd−1 (α) × R.

(37)

Please refer to Figure 2 as an illustration of this cone in three dimensions.

Figure 2: Illustration of the product cone defined in equation (37).

This example turns out to be rather interesting
√ because—as will be demonstrated in Section 3.2.3—the GLRT is sub-optimal by a factor d for this cone. In order to set up this later
analysis, here we use Theorem 1 to prove that
√
2GLR (K× )  σ 2 d.
(38)
Note that this result is strongly suggestive of sub-optimality on the part of the GLRT. More
concretely, the two cones that form K× are both “easy”, in that the GLRT radius scales as σ 2 for
each. For this reason, one√would expect that the squared radius of an optimal test would scale as
σ 2 —as opposed to the σ 2 d of the GLRT—and our later calculations will show that this is indeed
the case.
14

We now prove claim (38) as a consequence of Theorem 1. First notice that projecting to the
product cone K× can be viewed as projecting the first d − 1 dimension to circular cone Circd−1 (α)
and the last coordinate to R. Consequently, we have the following inequality
(a)

EkΠCircd−1 (α) gk2 ≤ EkΠK× gk2 ≤
=

q
q

EkΠK× gk22

EkΠCircd−1 (α) gk22 + E[gd2 ].

where inequality (a) follows by Jensen’s √
inequality. Making use of our previous calculations for
the circular cone, we have EkΠK× gk2  d. Moreover, note that the last coordinate of E[ΠK× g]
is equal to 0 by symmetry and the standard basis vector ed ∈ Rd , with a single one in its last
coordinate, belongs to K× ∩ S , we have
inf

η∈K× ∩S

hη, EΠK× (g)i ≤ hed , EΠK× (g)i = 0.

2 (C , C ), the corresponding second term equals infinity. Therefore,
Plugging into definition δLR
1
2
√
2 (C , C ) is achieved in the first term, and so is proportional to
d.
the minimum that defines δLR
1
2
Putting together the pieces yields the claim (38).

3.1.5

Non-negative orthant cone


Next let us consider the (non-negative) orthant cone given by K+ : = θ ∈ Rd | θj ≥ 0
Here we use Theorem 1 to show that
√
2GLR (K+ )  σ 2 d.

for j = 1, . . . , d .

(39)

2 (C , C ), it is straightforward to see that [Π
Turning to the evaluation of the quantity δLR
1
2
K+ (θ)]j =
1
max{0, θj }, and hence EΠK+ (g) = 2 E|g1 | 1 = √12π 1, where 1 ∈ Rd is a vector of all ones. Thus,
we have
r
d
kEΠK+ (g)k2 =
2π
r
q
d
2
and kEΠK+ (g)k2 ≤ EkΠK+ (g)k2 ≤
EkΠK+ (g)k2 =
,
2

where the second inequality follows from
√ Jensen’s inequality. So the first term in the definition of
2 (C , C ) is proportional to
quantity δLR
d. As for the second term, since the standard basis vector
1
2
e1 ∈ K+ ∩ S , we have
1
1
hη, EΠK gi ≤ he1 , √ 1i = √ .
η∈K+ ∩S
2π
2π
inf

2 (C , C ) lower bounded by a universal
Consequently, the second term in the definition of quantity δLR
1
2
constant times d. Combining these derivations yields the stated claim (39).

15

3.1.6

Monotone cone


As our final example, consider testing in the monotone cone given by M : = θ ∈ Rd | θ1 ≤ θ2 ≤
· · · ≤ θd . Testing with monotone cone constraint has also been studied in different settings before,
where it is known in some cases that restricting to monotone cone helps reduce the hardness of the
problem to be logarithmically dependent on the dimension (e.g., [7, 53]).
Here we use Theorem 1 to show that
2GLR (M )  σ 2

p
log d.

(40)

√
From known results on monotone cone (see §3.5, [1]), we know that EkΠM gk2  log d. So the
2 (C , C ). We claim that the second
only remaining detail is to control the second term defining δLR
1
2
term is actually infinity since
max{0,

inf hη, EΠM gi} = 0,

η∈M ∩S

which can be seen by simply noticing vectors

√1 1, − √1 1
d
d

(41)

∈ M ∩ S and

o
n 1
1
min h √ , EΠM gi, h− √ , EΠM gi ≤ 0.
d
d
Here 1 ∈ Rd denotes the vector of all ones. Combining the pieces yields the claim (40).
Testing constant versus monotone It is worth noting that the same GLRT bound also holds
for the more general problem of testing the monotone cone M versus the linear subspace L =
span(1) of constant vectors, namely:
p
2GLR (L, M )  σ 2 log d.
(42)
In particular, the following lemma provides the control that we need:
Lemma 1. For the monotone cone M and the linear space L = span(1), there is a universal
constant c such that
inf hη, EΠK gi ≤ c,

η∈K∩S

K : = M ∩ L⊥ .

See Appendix G.1 for the proof of this lemma.
Testing an arbitrary vector θ0 versus the monotone cone Finally, let us consider an
important implication of Corollary 1 in the context of testing departures in monotone cone. More
precisely, for a fixed vector θ0 ∈ M , consider the testing problem
H0 : θ = θ 0 ,

versus

16

H1 : θ ∈ M,

(43)

Let us define k(θ0 ) as the number of constant pieces of θ0 , by which we mean there exist integers
d1 , . . . , dk(θ0 ) with di ≥ 1 and d1 + · · · + dk(θ0 ) = d such that θ0 is a constant on each set Si : = {j :
Pi
Pi−1
t=1 di }, for 1 ≤ i ≤ k(θ0 ).
t=1 dt + 1 ≤ j ≤
We claim that Corollary 1 guarantees that the optimal testing radius satisfies
s


d
2
2
OPT (θ0 , M ; ρ) . σ k(θ0 ) log
.
k(θ0 )

(44)

Note that this upper bound depends on the structure of θ0 through how many pieces θ0 possesses,
which reveals the adaptive nature of Corollary 1.
√In order√to prove inequality (44), let us use shorthand k to denote k(θ0 ). First notice that both
1/ d, −1/ d ∈ TM (θ0 ), then
max{0,

inf
η∈TM (θ0 )∩S

hη, EΠTM (θ0 ) gi} ≤ 0,

2 (C , C ) equals to infinity. It only remains to calculate
which implies the second term for δLR
1
2
EkΠTM (θ0 ) gk2 . Since the tangent cone TM (θ0 ) equals to the Cartesian product of k monotone
cones, namely TM (θ0 ) = Md1 × · · · × Mdk , we have

EkΠTM (θ0 ) gk22 = EkΠMd1 gk22 + · · · + EkΠMdk gk22 = log(d1 ) + · · · + log(dk )
 
d
≤ k log
,
k
where the last step follows from convexity of the logarithm function. Therefore Jensen’s inequality
guarantees that
s
 
q
d
2
EkΠTM (θ0 ) gk2 ≤ EkΠTM (θ0 ) gk2 ≤ k log
.
k
Putting the pieces together, Corollary 1 guarantees that the claimed inequality (44) holds for the
testing problem (43).

3.2

Lower bounds on the testing radius

Thus far, we have derived sharp bounds for a particular procedure—namely, the GLRT. Of course,
it is of interest to understand when the GLRT is actually an optimal test, meaning that there is no
other test that can discriminate between the null and alternative for smaller separations. In this
section, we use information-theoretic methods to derive a lower bound on the optimal testing radius
OPT for every pair of non-oblique and nested closed convex cones (C1 , C2 ). Similar to Theorem 1,
this bound depends on the geometric structure of intersection cone K : = C2 ∩ C1∗ , where C1∗ is the
polar cone to C1 .
In particular, let us define the quantity
(
2

δOPT (C1 , C2 ) : = min EkΠK gk2 ,



)
2
EkΠK gk2
.
sup hη, EΠK gi
η∈K∩S

17

(45)

2 (C , C ) is the replacement of the infimum over K ∩ S with
Note that the only difference from δLR
1
2
a supremum, in the denominator of the second term. Moreover, since the supremum is achieved
EΠK g
at kEΠ
, we have supη∈K∩S hη, EΠK gi = kEΠK gk2 . Consequently, the second term on the
K gk2

2
EkΠK gk2
.
right-hand side of equation (45) can be also written in the equivalent form kEΠ
K gk2

With this notation in hand, are now ready to state a general lower bound for minimax optimal
testing radius:
Theorem 2. There are numbers {κρ , ρ ∈ (0, 1/2]} such that for every nested pair of non-oblique
closed convex cones C1 ⊂ C2 , we have
inf E(ψ; C1 , C2 , ) ≥ ρ
ψ

2 (C , C ),
whenever 2 ≤ κρ σ 2 δOPT
1
2

(46)

In particular, we can take κρ = 1/14 for all ρ ∈ (0, 1/2].
Remarks

In more compact terms, Theorem 2 can be understood as guaranteeing
OPT (C1 , C2 ; ρ) & σδOPT (C1 , C2 ),

where & denotes an inequality up to constants (with ρ viewed as fixed).
Theorem 2 is proved by constructing a distribution over the alternative H1 supported only on
those points in H1 that are hard to distinguish from H0 . Based on this construction, the testing
error can be lower bound by controlling the total variation distance between two marginal likelihood
functions. We refer our readers to our Section 4.2 for more details on this proof.
One useful consequence of Theorem 2 is in providing a sufficient condition for optimality of the
GLRT, which we summarize here:
Corollary 2 (Sufficient condition for optimality of GLRT). Given the cone K = C2 ∩ C1∗ , suppose
that there is a numerical constant b > 1, independent of K and all other problem parameters, such
that
sup hη, EΠK gi = kEΠK gk2 ≤ b
η∈K∩S

inf hη, EΠK gi.

η∈K∩S

(47)

Then the GLRT is a minimax optimal test—that is, GLR (C1 , C2 ; ρ)  OPT (C1 , C2 ; ρ).
It is natural to wonder whether the condition (47) is also necessary for optimality of the GLRT.
This turns out not to be the case. The monotone cone, to be revisited in Section 3.3.2, provides an
instance of a cone testing problem for which the GLRT is optimal while condition (47) is violated.
Let us now return to these concrete examples.
3.2.1

Revisiting the k-dimensional subspace

Let Sk be a subspace
√ of dimension k ≤ d. In our earlier discussion in Section 3.1.2, we established
that 2GLR (Sk )  σ 2 k. Let us use Corollary 2 to verify that the GLRT is optimal for this problem.
18

For a k-dimensional subspace K = Sk , we have EΠK g = 0 by symmetry; consequently, condition (47) holds in a trivial manner. Thus, we conclude that 2OPT (Sk )  2GLR (Sk ), showing that the
GLRT is optimal over all tests.
3.2.2

Revisiting the circular cone

Recall the circular cone K = {θ ∈ Rd | θ1 ≥ kθk2 cos(α)} for fixed 0 < α < π/2. In our earlier
discussion, we proved that 2GLR (K)  σ 2 . Here let us verify that this scaling is optimal over all
tests. By symmetry, we find that EΠK g = βe1 ∈ Rd , where e1 denotes the standard Euclidean
basis vector with a 1 in the first coordinate, and β > 0 is some scalar. For any vector η ∈ K ∩ S ,
we have η1 ≥ cos(α), and hence
inf hη, EΠK gi ≥ cos(α)β = cos(α)kEΠK gk2 .

η∈K∩S

1
Consequently, we see that condition (47) is satisfied with b = cos(α)
> 0, so that the GLRT is
optimal over all tests for each fixed α. (To be clear, in this example, our theory does not provide
a sharp bound uniformly over varying α.)

3.2.3

Revisiting the product cone

Recall from Section 3.1.4 our discussion of the Cartesian product cone K× = Circd−1 (α) × R. In
this section, we establish that
√ the GLRT, when applied to a testing problem based on this case, is
sub-optimal by a factor of d.
Let us first prove that the sufficient condition (47) is violated, so that Corollary 2 does
√ not
imply optimality of the GLRT. From our earlier calculations, we know that EkΠK× gk2  d. On
the other hand, we also know that EΠK× g is equal to zero in its last coordinate. Since the standard
basis vector ed belongs to the set K× ∩ S , we have
inf

η∈K× ∩S

hη, EΠK× gi ≤ hed , EΠK× gi = 0,

so that condition (47) does not hold.
From this calculation alone, we cannot conclude that the GLRT is sub-optimal. So let us now
compute the lower bound guaranteed by Theorem 2. From our previous discussion,
√ we know that
EΠK× g = βe1 for some scalar β > 0. Moreover, we also √
have kEΠK× gk2 = β  d; this scaling
follows because we have kEΠK× gk2 = kEΠCircd−1 (α) gk2  d − 1, where we have used the previous
inequality (36) for circular cone. Putting together the pieces, we find that Theorem 2 implies that
2OPT (K× ) & σ 2 ,
which differs from the GLRT scaling in a factor of

√

(48)

d.

Does there exist a test that achieves the lower bound (48)? It turns out that a simple truncation
test does so, and hence is optimal. To provide intuition for the test, observe that for any vector
19

θ ∈ K× ∩ S , we have θ12 + θd2 ≥ cos2 (α). To verify this claim, note that
d−1

X
1  2
θ12
2
2
θ
+
θ
≥
+
θ
≥
θj2 + θd2 = 1.
d
d
cos2 (α) 1
cos2 (α)
j=1

Consequently, the two coordinates (y1 , yd ) provide sufficient information for constructing a good
test. In particular, consider the truncation test


ϕ(y) : = I k(y1 , yd )k2 ≥ β ,
for some threshold β > 0 to be determined. This can be viewed as a GLRT for testing the standard
null against the alternative R2 , and hence our general theory guarantees that it will succeed with
separation 2 & σ 2 . This guarantee matches our lower bound (48), showing that
√ the truncation test
is indeed optimal, and moreover, that the GLRT is sub-optimal by a factor of d for this particular
problem.
We provide more intuition on why the the GLRT sub-optimal and use this intuition to construct
a more general class of problems for which a similar sub-optimality is witnessed in Appendix A.

3.3

Detailed analysis of two cases

This section is devoted to a detailed analysis of the orthant cone, followed by the monotone cone.
Here we find that the GLRT is again optimal for both of these cones, but establishing this optimality
requires a more delicate analysis.
3.3.1

Revisiting the orthant cone

Recall from Section 3.1.5 our discussion of the (non-negative) orthant cone
K+ : = {θ ∈ Rd | θj ≥ 0 for j = 1, . . . , d},
√
where we proved that 2GLR (K+ )  σ 2 d. Let us first show that the sufficient condition (47) does
not hold, so that Corollary 2 does not imply
optimality of the GLRT. As we have computed in our
√
Section 3.1.5, quantity EkΠK+ (g)k2  d and
1
1
hη, EΠK gi ≤ he1 , √ 1i = √ ,
η∈K+ ∩S
2π
2π
inf

where use the fact that EΠK+ (g) =

√1
2π

1. So that condition (47) is violated.

Does this mean the GLRT is sub-optimal? It turns out that the GLRT is actually optimal
over all tests, as we can demonstrate by proving a lower bound—tighter than the one given in
Theorem 2—that matches the performance of the GLRT. We summarize it as follows:
Proposition 1. There are numbers {κρ , ρ ∈ (0, 1/2]} such that for the (non-negative) orthant cone
K+ , we have
√
(49)
inf E(ψ; {0}, K+ , ) ≥ ρ
whenever 2 ≤ κρ σ 2 d.
ψ

20

See the Section B.1 for the proof of this proposition.
√
From Proposition 1, we see that the optimal testing radius satisfies 2OPT (K+ ) & σ 2 d. Compared
to the GLRT radius 2GLR (K+ ) established in expression (39), it implies the optimality of the GLRT.
3.3.2

Revisiting the monotone cone

Recall the monotone cone given by M : = {θ ∈ Rd | θ√1 ≤ θ2 ≤ · · · ≤ θd }. In our previous discussion
in Section 3.1.6, we established that 2GLR (M )  σ 2 log d. We also pointed out that this scaling
holds for a more general problem, namely, testing cone M versus linear subspace L = span(1). In
this section, we show that the GLRT is also optimal for both cases.
First, observe that Corollary 2 does not imply optimality of the GLRT. In particular, using
symmetry of the inner product, we have shown in expression (41) that
max{0, inf hη, EΠM gi} = 0,
η∈M ∩S

for cone pair (C1 , C2 ) = ({0}, M ). Also note that from Lemma 1 we know that for cone pair
(C1 , C2 ) = (span(1), M ), there is a universal constant c such that
inf hη, EΠK gi ≤ c,

η∈K∩S

In both cases, since EkΠK gk2 
fails to hold.

√

K : = M ∩ L⊥ .

log d, so that the sufficient condition (47) for GLRT optimality

It turns out that we can demonstrate a matching lower bound for 2OPT (M ) in a more direct
way by carefully constructing a prior distribution on the alternatives and control the testing error.
Doing so allows us to conclude that the GLRT is optimal, and we summarize our conclusions in
the following:
Proposition 2. There are numbers {κρ , ρ ∈ (0, 1/2]} such that for the monotone cone M and
subspace L = {0} or span(1), we have
p
inf E(ψ; L, M, ) ≥ ρ
whenever 2 ≤ κρ σ 2 log(ed).
(50)
ψ

See Section B.2 for the proof of this proposition.
Proposition 2, equipped with previous achievable results by GLRT (40), gives a sharp rate
characterization on the testing radius for both problems with regard to monotone cone:
H0 : θ = 0
and H0 : θ ∈ span(1)

versus H1 : θ ∈ M

H1 : θ ∈ M.
p
In both cases, the optimal testing radius satisfies 2OPT (L, M, ρ)  σ 2 log(ed). As a consequence,
the GLRT is optimal up to an universal constant. As far as we know, the problem of testing a zero
or constant vector versus the monotone cone as the alternative has not been fully characterized in
any past work.
21

versus

4

Proofs of main results

We now turn to the proofs of our main results, with the proof of Theorems 1 and 2 given in
Sections 4.1 and 4.2 respectively. In all cases, we defer the proofs of certain more technical lemmas
to the appendices.

4.1

Proof of Theorem 1

Since the cones (C1 , C2 ) are both invariant under rescaling by positive numbers, we can first prove
the result for noise level σ = 1, and then recapture the general result by rescaling appropriately.
Thus, we fix σ = 1 throughout the remainder of the proof so as to simplify notation. Moreover, let
us recall that the GLRT consists of tests of the form φβ (y) : = I(T (y) ≥ β), where the likelihood
ratio T (y) is given in equation (11a). Note here the cut-off β ∈ [0, ∞) is a constant that does not
depend on the data vector y.
By the previously discussed equivalence (26), we can focus our attention on the simpler problem
T ({0}, K; ), where K = C2 ∩ C1∗ . By the monotonicity of the square function for positive numbers,
the GLRT is controlled by the behavior of the statistic kΠK (y)k2 , and in particular how it varies
depending on whether y is drawn according to H0 or H1 .
Letting g ∈ Rd denote a standard Gaussian random vector, let us introduce the random variable
Z(θ) : = kΠK (θ + g)k2 for each θ ∈ Rd . Observe that the statistic kΠK (y)k2 is distributed according
to Z(0) under the null H0 , and according to Z(θ) for some θ ∈ K under the alternative H1 . The
Lemma D.1 which is stated and proved in Appendix D.1 guarantees random variables of the type
Z(θ) and hθ, ΠK gi are sharply concentrated around their expectations.
As shown in the sequel, using the concentration bound (73a), the study of the GLRT can be
reduced to the problem of bounding the mean difference
Γ(θ) : = E (kΠK (θ + g)k2 − kΠK gk2 )

(51)

for each θ ∈ K. In particular, in order to prove the achievability result stated in part (a) of
Theorem 1, we need to lower bound Γ(θ) uniformly over θ ∈ K, whereas a uniform upper bound
on Γ(θ) is required in order to prove the negative result in part (b).
4.1.1

Proof of GLRT achievability result (Theorem 1(a))

By assumption, we can restrict our attention to alternative distributions defined by vectors θ ∈ K
2 ({0}, K), where for every target level ρ ∈ (0, 1), constant
satisfying the lower bound kθk22 ≥ Bρ δLR
Bρ is chosen such that
(
!)
p
B 1/2
2
Bρ : = max 32π, inf B > 0 | 7
− √ ≥ −8 log(ρ/2)
.
e
(2 πB)1/4 + 16
1/2

x
√2 is strictly increasing and goes to infinity, so that the
Since function f (x) : = (27 πx)
1/4 +16 −
e
constant Bρ defined above is always finite.

22

We first claim that it suffices to show that for such vector, the difference (51) is lower bounded
as
1/2

Γ(θ) ≥

Bρ
2
− √ = f (Bρ ).
1/4
7
e
(2 πBρ ) + 16

(52)

Taking inequality (52) as given for the moment, we claim that the test
φτ (y) = I[kΠK (y)k22 ≥ τ ]

with threshold τ : = ( 21 f (Bρ ) + E[kΠK (g)k2 ])2

has uniform error probability controlled as
E(φτ ; {0}, K, ) : = E0 [φτ (y)] +

sup
θ∈K,kθk22 ≥2

Eθ [1 − φτ (y)] ≤ 2e−f

2 (B )/8
ρ

< ρ.

(53)

where the last inequality follows from the definition of Bρ .
Beginning with errors under the null H0 , we have


√
E0 [φτ (y)] = P0 (kΠK gk2 ≥ τ ) = P0 kΠK gk2 − E[kΠK gk2 ] ≥ f (Bρ )/2

Establishing the error control (53)

≤ exp(−f 2 (Bρ )/8),
where the final inequality follows from the concentration bound (73a) in Lemma D.1, as along as
f (Bρ ) > 0.
On the other hand, we have
h
i
1
Eθ [1 − φτ (y)] = P kΠK (θ + g)k2 ≤ f (Bρ ) + EkΠK gk2
2
θ∈K,kθk22 ≥2
h
i
1
= P kΠK (θ + g)k2 − EkΠK (θ + g)k2 ≤ f (Bρ ) − Γ(θ) ,
2
sup

where the last equality follows by substituting Γ(θ) = E[kΠK (θ + g)k2 ] − E[kΠK gk2 ]. Since the
lower bound (52) guarantees that 12 f (Bρ ) − Γ(θ) ≤ − 12 f (Bρ ), we find that
h
i
1
Eθ [1 − φτ (y)] ≤ P kΠK (θ + g)k2 − EkΠK (θ + g)k2 ≤ − f (Bρ )
2
θ∈K,kθk2 ≥2
sup

2

≤ exp(−f 2 (Bρ )/8),
where the final inequality again uses the concentration inequality (73a). Putting the pieces together
yields the claim (53).
The only remaining detail is to prove the lower bound (52) on the difference (51). To mainstream
our proof, we leave the proof of this detail to Appendix D.2.

23

4.1.2

Proof of GLRT lower bound (Theorem 1(b))

We divide our proof into two scenarios, depending on whether or not EkΠK gk2 is less than 128.
We focus on the case when EkΠK gk2 ≥ 128 and leave the other scenario to the Appendix E.1.
In this case, our strategy is to exhibit some θ ∈ H1 for which the expected difference Γ(θ) =
E (kΠK (θ + g)k2 − kΠK gk2 ) is small, which then leads to significant error when using the GLRT.
In order to do so, we require an auxiliary lemma (Lemma E.1) to suitable control Γ(θ) which is
stated and proved in Appendix E.2.
We now proceed to prove our main claim. Based on Lemma E.1, we claim that if 2 ≤
bρ LR ({0}, K) for a suitably small constant bρ such that
(
)
r
 1/4
p
p
bρ
2
1
bρ : = sup bρ > 0 | 12 bρ + 3 bρ
,
+ 24
≤
e
2e
16
δ2

then
Γ(θ) ≤

1
,
16

for some θ ∈ K, kθk2 ≥ .

(54)

We take inequality (54) as given for now, returning to prove it in our appendix E.4. In summary,
then, we have exhibited some θ ∈ H1 —namely, a vector θ ∈ K with kθk2 ≥ —such that Γ(θ) ≤
1/16. This special vector θ plays a central role in our proof.
We claim that the GLRT cannot succeed with error smaller than 0.11 no matter how the cut-off
β is chosen. We leave this calculation to Appendix E.3.

4.2

Proof of Theorem 2

We now turn to the proof of Theorem 2. As in the proof of Theorem 1, we can assume without
loss of generality that σ = 1. Since 0 ∈ C1 and K : = C2 ∩ C1∗ ⊆ C2 , it suffices to prove a lower
bound for the reduced problem of testing
H0 : θ = 0,

versus

H1 : kθk2 ≥ , θ ∈ K.

Let B(1) = {θ ∈ Rd | kθk2 < 1} denotes the open Euclidean ball of radius 1, and let B c (1) : =
Rd \B(1) denotes its complement.
We divide our analysis into two cases, depending on whether or not EkΠK gk2 is less than 7. In
both cases, let us set κρ = 1/14.
Case 1

Suppose that EkΠK gk2 < 7. In this case,
2
2 ≤ κρ δOPT
({0}, K) ≤ κρ EkΠK gk2 < 1/2.

Similar to our proof of Theorem 1(b), Case 1, by reducing to the simple verses simple testing
problem (85a), any test yields testing error no smaller than 1/2 if 2 < 1/2. So our lower bound
directly holds for the case when EkΠK gk2 < 7.
24

Case 2 Otherwise, suppose we have EkΠK gk2 ≥ 7. The following lemma provides a generic way
to lower bound the testing error.
Lemma 2. For every non-trivial closed convex cone K and probability measure Q supported on
K ∩ B c (1), the testing error is lower bounded as
q
1
inf E(ψ; {0}, K, ) ≥ 1 −
Eη,η0 exp(2 hη, η 0 i) − 1,
(55)
ψ
2
where Eη,η0 denotes expectation with respect to an i.i.d pair η, η 0 ∼ Q.
See Appendix F.1 for the proof of this claim.
We apply Lemma 2 with the probability measure Q defined as


ΠK g
Q(A) : = P
∈ A kΠK gk2 ≥ EkΠK gk2 /2 ,
EkΠK gk2 /2

(56)

for measurable set A ⊂ Rd where g denotes a standard d-dimensional Gaussian random vector
i.e., g ∼ N (0, Id ). It is easy to check that measure Q is supported on K ∩ B c (1). We make use of
Lemma F.1 in Appendix F.2 to control Eη,η0 exp(2 hη, η 0 i) and thus upper bounding the testing
error.
2 ({0}, K). By definition of δ 2 ({0}, K),
We now lower bound the testing error when 2 ≤ κρ δOPT
OPT
2 ({0}, K) implies that
the inequality 2 ≤ κρ δOPT


EkΠK gk2 2
2
2
 ≤ κρ EkΠK gk2
and  ≤ κρ
.
kEΠK gk2

The first inequality above implies, with κρ = 1/14, that 2 ≤ EkΠK gk2 /14 ≤ (EkΠK gk2 )2 /32 (note
that EkΠK gk2 ≥ 7). Therefore the assumption in Lemma F.1 is satisfied so that inequality (103)
gives
!
40κ2ρ E(kΠK gk22 )
1
2
0
.
(57)
Eη,η0 exp( hη, η i) ≤ 2 exp 5κρ +
a
(EkΠK gk2 )2
So it suffices to control the right hand side above. From the concentration result in Lemma D.1,
we obtain
1
(EkΠK gk2 )2
a = P(kΠK gk2 − EkΠK gk2 ≥ − EkΠK gk2 ) ≥ 1 − exp(−
) > 1 − exp(−6),
2
8
where the last step uses EkΠK gk2 ≥ 7, and
EkΠK gk22 = (EkΠK gk2 )2 + var(kΠK gk2 ) ≤ (EkΠK gk2 )2 + 4.
Here the last inequality follows from the fact that var(kΠK gk2 ) ≤ 4—see Lemma D.1. Plugging
these two inequalities into expression (57) gives
!

2
2
160κ
1
ρ
Eη,η0 exp(2 hη, η 0 i) ≤
exp 5κρ + 40κ2ρ +
,
1 − exp(−6)
(EkΠK gk2 )2
25

where the right hand side is less than 2 when κρ = 1/14 and EkΠK gk2 ≥ 7. Combining with
inequality (55) forces the testing error to be lower bounded as
q
1
1
∀ψ, E(ψ; {0}, K, ) ≥ 1 −
Eη,η0 exp(2 hη, η 0 i) − 1 ≥ > ρ,
2
2
which completes the proof of Theorem 2.

5

Discussion

In this paper, we have studied the the problem of testing between two hypotheses that are specified
by a pair of non-oblique closed convex cones. Our first main result provided a characterization,
sharp up to universal multiplicative constants, of the testing radius achieved by the generalized
likelihood ratio test. This characterization was geometric in nature, depending on a combination of
the Gaussian width of an induced cone, and a second geometric parameter. Due to the combination
of these parameters, our analysis shows that the GLRT can have very different behavior even for
cones that have the same Gaussian width; for instance, compare our results for the circular and
orthant cone in Section 3.1. It is worth noting that this behavior is in sharp contrast to the situation
for estimation problems over convex sets, where it is understood that (localized) Gaussian widths
completely determine the estimation error associated with the least-squares estimator [51, 11]. In
this way, our analysis reveals a fundamental difference between minimax testing and estimation.
Our analysis also highlights some new settings in which the GLRT is non-optimal. Although
past work [52, 33, 37] has exhibited non-optimality of the GLRT in certain settings, in the context of
cones, all of these past examples involve oblique cones. In Section 3.1.4, we gave an example of suboptimality which, to the best of our knowledge, is the first for a non-oblique pair of cones—namely,
the cone {0}, and a certain type of Cartesian product cone.
Our work leaves open various questions, and we conclude by highlighting a few here. First,
in Section 3.2, we proved a general information-theoretic lower bound for the minimax testing
radius. This lower bound provides a sufficient condition for the GLRT to be minimax optimal up
to constants. Despite being tight in many non-trivial situations, our information-theoretic lower
bound is not tight for all cones; proving such a sharp lower bound is an interesting topic for future
research. Second, as with a long line of past work on this topic [39, 34, 32, 52], our analysis is based
on assuming that the noise variance σ 2 is known. In practice, this may or may not be a realistic
assumption, and so it is interesting to consider the extension of our results to this setting.
We note that our minimax lower bounds are proved by constructing prior distributions on H0
and H1 and then control the distance between marginal likelihood functions. Following this idea, we
can also consider our testing problem in the Bayesian framework. Without any prior preference on
which hypothesis to take, we will let Pr(H0 ) = Pr(H1 ) = 1/2; thus the Bayesian testing procedure
makes decision based on quantity
R
Pθ (y)π1 (θ)dθ
m(y | H0 )
B01 : =
= Rθ∈C1
,
(58)
m(y | H1 )
θ∈C2 Pθ (y)π2 (θ)dθ
which is often called Bayesian factor in literature. Analyzing the behavior of this statistic is an
interesting direction to pursue in the future.
26

Acknowledgements
This work was partially supported by Office of Naval Research MURI grant DOD-002888, Air Force
Office of Scientific Research Grant AFOSR-FA9550-14-1-001, and National Science Foundation
Grants CIF-31712-23800 and DMS-1309356, NSF CAREER Grant DMS-16-54589

References
[1] D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp. Living on the edge: phase transitions
in convex programs with random data. Information and Inference, 3(3):224–294, 2014.
[2] Y. Baraud. Non-asymptotic minimax rates of testing in signal detection. Bernoulli, 8(5):577–
606, 2002.
[3] R. E. Barlow, D. J. Bartholomew, J. Bremner, and H. D. Brunk. Statistical inference under
order restrictions: The theory and application of isotonic regression. Wiley New York, 1972.
[4] D. Bartholomew. A test of homogeneity for ordered alternatives. Biometrika, 46(1/2):36–48,
1959.
[5] D. Bartholomew. A test of homogeneity for ordered alternatives. ii. Biometrika, 46(3/4):328–
335, 1959.
[6] P. L. Bartlett, O. Bousquet, S. Mendelson, et al. Local Rademacher complexities. The Annals
of Statistics, 33(4):1497–1537, 2005.
[7] T. Batu, R. Kumar, and R. Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In Proceedings of the thirty-sixth annual ACM symposium on Theory of
computing, pages 381–390. ACM, 2004.
[8] O. Besson. Adaptive detection of a signal whose signature belongs to a cone. In Proceedings
SAM Conference, 2006.
[9] C. Borell. The Brunn-Minkowski inequality in Gauss space. Inventiones mathematicae, 30:207–
216, 1975.
[10] P. Bühlmann. Statistical significance in high-dimensional linear models. Bernoulli, 19(4):1212–
1242, 2013.
[11] S. Chatterjee et al. A new perspective on least squares under convex constraint. The Annals
of Statistics, 42(6):2340–2381, 2014.
[12] D. Chen and R. J. Plemmons. Nonnegativity constraints in numerical analysis. The birth of
numerical analysis, 10:109–140, 2009.
[13] D. Chetverikov. Testing regression monotonicity in econometric models. Technical report,
UCLA, December 2012. arXiv:1212.6757.

27

[14] R. L. Dykstra and T. Robertson. On testing monotone tendencies. Journal of the American
Statistical Association, 78(382):342–350, 1983.
[15] A. W. F. Edwards. Likelihood. Cambridge University Press, Cambridge, 1972.
[16] M. S. Ermakov. Minimax detection of a signal in a gaussian white noise. Theory of Probability
& Its Applications, 35(4):667–679, 1991.
[17] J. Fan and J. Jiang. Nonparametric inference with generalized likelihood ratio tests. Test,
16(3):409–444, 2007.
[18] J. Fan, C. Zhang, and J. Zhang. Generalized likelihood ratio statistics and Wilk’s phenomenon.
The Annals of Statistics, pages 153–193, 2001.
[19] L. Goldstein, I. Nourdin, and G. Peccati. Gaussian phase transitions and conic intrinsic
volumes: Steining the Steiner formula. arXiv preprint arXiv:1411.6265, 2014.
[20] M. Greco, F. Gini, and A. Farina. Radar detection and classification of jamming signals
belonging to a cone class. IEEE Trans. Signal Processing, 56(5):1984–1993, May 2008.
[21] X. Hu and F. T. Wright. Likelihood ratio tests for a class of non-oblique hypotheses. Ann.
Inst. Statist. Math., 46(1):137–145, 1994.
[22] Y. I. Ingster. Minimax testing of nonparametric hypotheses on a distribution density in the
Lp -metrics. Theory of Probability and Its Applications, 31(2):333–337, 1987.
[23] Y. I. Ingster and I. A. Suslina. Nonparametric goodness-of-fit testing under Gaussian models,
volume 169. Springer Science and Business Media, 2012.
[24] V. Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Transactions
on Information Theory, 47(5):1902–1914, 2001.
[25] A. Kudo. A multivariate analogue of the one-sided test. Biometrika, 50(3/4):403–418, 1963.
[26] E. L. Lehmann. On likelihood ratio tests. In Selected Works of EL Lehmann, pages 209–216.
Springer, 2012.
[27] E. L. Lehmann and J. P. Romano. Testing statistical hypotheses. Springer Science and Business
Media, 2006.
[28] O. V. Lepski and V. G. Spokoiny. Minimax nonparametric hypothesis testing: the case of an
inhomogeneous alternative. Bernoulli, 5(2):333–358, 1999.
[29] O. V. Lepski and A. B. Tsybakov. Asymptotically exact nonparametric hypothesis testing in
sup-norm and at a fixed point. Probability Theory and Related Fields, 117(1):17–48, 2000.
[30] M. B. McCoy and J. A. Tropp. From Steiner formulas for cones to concentration of intrinsic
volumes. Discrete and Computational Geometry, 51(4):926–963, 2014.
[31] N. Meinshausen. Sign-constrained least squares estimation for high-dimensional regression.
Electronic Journal of Statistics, 7:1607–1631, 2013.
28

[32] J. Menéndez, C. Rueda, B. Salvador, et al. Dominance of likelihood ratio tests under cone
constraints. The Annals of Statistics, 20(4):2087–2099, 1992.
[33] J. A. Menéndez and B. Salvador. Anomalies of the likelihood ratio test for testing restricted
hypotheses. Annals of Statistics, 19(2):889–898, 1991.
[34] J. Menéndnez, C. Rueda, and B. Salvador. Testing non-oblique hypotheses. Communications
in Statistics - Theory and Methods, 21(2):471–484, 1992.
[35] M. C. Meyer. A test for linear versus convex regression function using shape-restricted regression. Biometrika, 90(1):223–232, 2003.
[36] J.-J. Moreau. Décomposition orthogonale d’un espace hilbertien selon deux cônes mutuellement
polaires. CR Acad. Sci. Paris, 255:238–240, 1962.
[37] M. D. Perlman, L. Wu, et al. The emperor’s new tests. Statistical Science, 14(4):355–369,
1999.
[38] G. Pisier. Probabilistic methods in the geometry of Banach spaces. Springer, 1986.
[39] R. F. Raubertas, C.-I. Charles Lee, and E. V. Nordheim. Hypothesis tests for normal
means constrained by linear inequalities. Communications in Statistics - Theory and Methods,
15(9):2809–2833, 1986.
[40] T. Robertson. Testing for and against an order restriction on multinomial parameters. Journal
of the American Statistical Association, 73(361):197–202, 1978.
[41] T. Robertson. On testing symmetry and unimodality. In Advances in Order Restricted Statistical Inference, pages 231–248. Springer, 1986.
[42] T. Robertson and E. J. Wegman. Likelihood ratio tests for order restrictions in exponential
families. The Annals of Statistics, pages 485–505, 1978.
[43] T. Robertson, F. T. Wright, and R. L. Dykstra. Order Restricted Statistical Inference. Wiley
Series in Probability and Mathematical Statistics, 1988.
[44] W. Robertson. On measuring the conformity of a parameter set to a trend, with applications.
The Annals of Statistics, 10(4):1234–1245, 1982.
[45] L. L. Scharf. Statistical signal processing: Detection, estimation and time series analysis.
Addison-Wesley, Reading, MA, 1991.
[46] B. Sen and M. Meyer. Testing against a linear regression model using ideas from shaperestricted estimation. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2017.
[47] A. Shapiro. Towards a unified theory of inequality constrained testing in multivariate analysis.
International Statistical Review/Revue Internationale de Statistique, pages 49–62, 1988.
[48] M. Slawski, M. Hein, et al. Non-negative least squares for high-dimensional linear models: Consistency and sparse recovery without regularization. Electronic Journal of Statistics,
7:3004–3056, 2013.
29

[49] V. G. Spokoiny. Adaptive and spatially adaptive testing a nonparametric hypothesis. Math.
Methods Statist, 7:245–273, 1998.
[50] S. A. Van de Geer. Applications of empirical process theory, volume 91. Cambridge University
Press Cambridge, 2000.
[51] A. W. Van Der Vaart and J. A. Wellner. Weak convergence. In Weak Convergence and
Empirical Processes, pages 16–28. Springer, 1996.
[52] G. Warrack and T. Robertson. A likelihood ratio test regarding two nested but oblique orderrestricted hypotheses. Journal of the American Statistical Association, 79(388):881–886, 1984.
[53] Y. Wei and M. J. Wainwright. Sharp minimax bounds for testing discrete monotone distributions. In IEEE International Symposium on Information Theory (ISIT), pages 2684–2688.
IEEE, 2016.
[54] E. H. Zarantonello. Projections on convex sets in Hilbert spaces and spectral theory. In
Contributions to nonlinear functional analysis, pages 237–424. Academic Press, 1971.

A

The GLRT sub-optimality

In this appendix, we first try to understand why the GLRT is sub-optimal for the Cartesian product
cone K× = Circd−1 (α) × R, and use this intuition to construct a more general class of problems for
which a similar sub-optimality is witnessed.

A.1

Why is the GLRT sub-optimal?

Let us consider tests with null C1 = {0} and a general product alternative of the form C2 = K× =
K × R, where K ⊆ Rd−1 is a base cone. Note that K = Circd−1 in our previous example.
Now recall the decomposition (22) of the statistic T that underlies the GLRT. By the product
nature of the cone, we have
q
T (y) = kΠK× yk2 = k(ΠK (y−d ), yd )k2 = kΠK (y−d )k22 + kyd k22 ,
where y−d : = (y1 , . . . , yd−1 ) ∈ Rd−1 is formed from the first d − 1 coordinates of y. Suppose that
we are interested in testing between the zero vector and a vector θ∗ = (0, . . . , 0, θd∗ ), non-zero only
in the last coordinate, which belongs to the alternative. With this particular choice, under the null
distribution, we have y = σg whereas under the alternative, we have y = θ∗ + σg. Letting E0 and

30

E1 denote expectations under these two Gaussian distributions, the performance of the GLRT in
this direction is governed by the difference
r
θ∗
1
E1 [T (y)] − E0 [T (y)] = E1 kΠK (g−d )k22 + k d + gd k22
σ
σ
q
−E0 kΠK (g−d )k22 + kgd k22 .
Note both terms in this difference involve a (d − 1)-dimensional “pure noise” component—namely,
the quantity kΠK (g−d )k22 defined by the sub-vector g−d : = (g1 , . . . , gd−1 )—with the only signal
lying the last coordinate. For many choices of cone K, the pure noise component acts as a strong
mask for the signal component, so that the GLRT is poor at detecting differences in the direction θ∗ .
Since the vector θ∗ belongs to the alternative, this leads to sub-optimality in its overall behavior.
Guided by this idea, we can construct a series of other cases where the GLRT is sub-optimal. See
Appendix A.2 for details.

A.2

More examples on the GLRT sub-optimality

Now let us construct a larger class of product cones for which the GLRT is sub-optimal. For a
given subset S ⊆ {1, . . . , d}, define the subvectors θS = (θi , i ∈ S) and θS c = (θj , j ∈ S c }, where S c
denotes the complement of S. For an integer ` ≥ 1, consider any cone K` ⊂ Rd with the following
two properties:
• its Gaussian width scales as EW(K` ∩ B(1)) 

√

d, and

• for some fixed subset {1, 2 . . . , d} of cardinality `, there is a scalar γ > 0 such that
kθS k2 ≥ γkθS c k2

for all θ ∈ K` .

As one concrete example, it is easy to check that the circular cone is a special example with ` = 1
and γ = 1/ tan(α). The following result applies to the GLRT when applied to testing the null
s = K × R.
C1 = {0} versus the alternative C2 = K×
Proposition A.1. For the previously described cone testing problem, the GLRT testing radius is
sandwiched as
√
2GLR  dσ 2 ,
whereas a truncation test can succeed at radius 2 

√

`σ 2 .

Proof. The claimed scaling of the GLRT testing radius follows as a corollary of Theorem 1 after a
2 (C , C ). In order to do so, we begin by observing that
direct evaluation of δLR
1
2
inf hη, EΠC2 gi ≤ hed , EΠc2 gi = 0,
√
EW(C2 ∩ B(1)) = EkΠC2 gk2  d

η∈C2 ×S

31

and

2 (C , C ) 
which implies that δLR
1
2
Theorem 1.

√

d, and hence implies the sandwich claim on the GLRT via

On the other hand, for some pre-selected β > 0, consider the truncation test


ϕ(y) : = I kyS k2 ≥ β ,
`
This test can be viewed as a GLRT for
√ testing the zero null against the alternative R , and hence it
2
2
will succeed with separation   σ `. Putting these pieces together, we conclude that the GLRT
is sub-optimal whenever ` is of lower order than d.

B

Proofs for Proposition 1 and 2

In this section, we complete the proofs of Propositions 1 and 2 in Sections B.1 and B.2, respectively.

B.1

Proof of Proposition 1

As in the proof of Theorem 1 and Theorem 2, we can assume without loss of generality that σ = 1
since K+ is invariant under rescaling by positive numbers. We split our proof into two cases,
depending on whether or not the dimension d is less than 81.
√
Case 1: First suppose that d < 81. If the separation is upper bounded as 2 ≤ κρ d, then setting
κρ = 1/18 yields
√
2 ≤ κρ d < 1/2.
Similar to our proof for Theorem 1(b) Case 1, if 2 < 1/2, every test yields testing error no smaller
than 1/2. It is seen by considering a simple verses simple testing problem (85a). So our lower
bound directly holds for the case when d < 81 satisfies.
Case 2: Let us consider the case when dimension d ≥ 81. The
√ idea is to make use of our Lemma 2
to show that the testing error is at least ρ whenever 2 ≤ κρ d. In order to apply Lemma 2, the
key is to construct a probability measure Q supported on set K ∩ B c (1) such that for i.i.d. pair
0
η, η 0 drawn from Q, quantity Eeλhη, η i can be well controlled. We claim that there exists such a
probability measure Q that

 
2 !
2
+
λ
1
0
where λ : = 2 .
(59)
Eη,η0 eλhη, η i ≤ exp exp √
− 1− √
d−1
d

32

√
Taking inequality (59) as given for now, letting κρ = 1/8, we have λ = 2 ≤ d/8. So the right
hand side in expression (59) can be further upper bounded as
! 
√
 !
 
 !

d λ
2
1 2
1 2
1 9 1
√
exp exp √
+√
− 1− √
− 1−
≤ exp exp
+ ·
4 8 8
9
d−1
d−1 d
d
< 2,
where we use the fact that d ≥ 81. As a consequence of Lemma 2, the testing error of every test
satisfies
q
1
1
Eη,η0 exp(2 hη, η 0 i) − 1 > ≥ ρ.
inf E(ψ; {0}, K+ , ) ≥ 1 −
ψ
2
2
Putting these two cases together, our lower bound holds for any dimension thus we complete the
proof of Proposition 1.
So it only remains to construct a probability measure Q such that the inequality (59) holds. We
begin by introducing some helpful notation. For an integer s to be specified, consider a collection
of vectors S containing all d-dimensional vectors with exactly
 s non-zero entries and each non-zero
√
d
entry equals to 1/ s. Note that there are in total M : = s vectors of this type. Letting Q be the
uniform distribution over this set of vectors namely
Q({η}) : =

1
,
M

η ∈ S.

(60)

Then we can write the expectation as
0

Eeλhη, η i =

1 X λhη, η0 i
e
.
M2 0
η,η ∈S

Note that the inner product hη, η 0 i takes values i/s, for integer i ∈ {0, 1, . . . , s} and given every

vector η and integer i ∈ {0, 1, . . . , s}, the number of η 0 such that hη, η 0 i = i/s equals to si d−s
s−i .
Consequently, we obtain
Ee

λhη, η 0 i

 −1 X

s  
s
d
s d − s λi/s X Ai z i
=
e
=
,
s
i
s−i
i!
i=0

(61)

i=0

where
z : = eλ/s and Ai : =

(s!(d − s)!)2
.
((s − i)!)2 d!(d − 2s + i)!

√
Let us set integer s : = b dc. We claim quantity Ai satisfies the following bound

1
2i 
Ai ≤ exp − (1 − √ )2 + √
d
d−1

33

for all i ∈ {0, 1, . . . , s}.

(62)

Taking expression (62) as given for now and plugging into inequality (61), we have
2
i
s

1  X (z exp( √d−1 ))
0
Eeλhη, η i ≤ exp − (1 − √ )2
i!
d
i=0



(a)
2
1 2
)
≤ exp − (1 − √ ) exp z exp( √
d
d−1



!
(b)
1 2
2+λ
≤ exp − 1 − √
+ exp √
,
d
d−1

P
xi
where step (a) follows from the standard power series expansion ex = ∞
i=0 i! and step (b) follows
√
√
by z = eλ/s and s = b dc > d − 1. Therefore it verifies inequality (59) and complete our
argument.
It is only left for us to check inequality (62) for Ai . Using the fact that 1 − x ≤ e−x , it is
guaranteed that
s

A0 =

X
((d − s)!)2
s
s
s
1
= (1 − )(1 −
) · · · (1 −
) ≤ exp(−s
).
d!(d − 2s)!
d
d−1
d−s+1
d−s+i

(63a)

i=1

√

Recall that integer s = b dc, then we can bound the sum in expression (63a) as
s

s
X
i=1

s

X1
s2
1
1
≥s
=
≥ (1 − √ )2 ,
d−s+i
d
d
d
i=1

which, when combined with inequality (63a), implies that A0 ≤ exp(−(1 −

√1 )2 ).
d

Moreover, direct calculations yield
Ai
(s − i + 1)2
,
=
Ai−1
d − 2s + i

1 ≤ i ≤ s.

(63b)

This ratio is decreasing with index i as 1 ≤ i ≤ s, thus is upper bounded by A1 /A0 , which implies
that
Ai
d
1
2
√
≤
= (1 + √
)2 ≤ exp( √
),
Ai−1
d−2 d+1
d−1
d−1
where the last inequality follows from 1 + x ≤ ex . Putting pieces together validates bound (62) thus
finishing the proof of Proposition 1.

B.2

Proof of Proposition 2

As in the proof of Theorem 1 and Theorem 2, we can assume without loss of generality that σ = 1
since L and M are both invariant under rescaling by positive numbers.
p
We split our proof into two cases, depending on whether or not log(ed) < 14.
34

Case 1:

First suppose

p
log(ed) < 14, so that the choice κρ = 1/28 yields the upper bound
p
2 ≤ κρ log(ed) < 1/2.

Similar to our proof of the lower bound in Theorem 1, by reducing to a simple testing problem (85a),
2
any test yields testing error
p no smaller than 1/2 if  < 1/2. Thus, we conclude that the stated
lower bound holds when log(ed) < 14.
p
Case 2: Otherwise, we may assume that log(ed) ≥ 14. In this case,
p we exploit Lemma 2 in
order to show that the testing error is at least ρ whenever 2 ≤ κρ log(ed). Doing so requires
constructing a probability measure QL supported on M ∩ L⊥ ∩ B c (1) such that the expectation
2
0
Ee hη, η i can be well controlled, where (η, η 0 ) are drawn i.i.d according to QL . Note that L can be
either {0} or span(1).
Before doing that, let us first introduce some notation. Let δ : = 9 and r : = 1/3 (note that
δ = r−2 ). Let
(
)
n
X
δ−1
(64)
m : = max n
b i (d + logδ d + 3)c < d .
δ
i=1

We claim that the integer m defined above satisfies:
3
d logδ (d)e + 1 ≤ m ≤ dlogδ de,
(65)
4
where dxe denotes the smallest integer that is greater than or equal to x. To see this, notice that
for t = d 34 logδ (d)e + 1, we have
t
t
X
X
δ−1
1
δ−1
(d + logδ d + 3) = (1 − t )(d + α)
b i (d + logδ d + 3)c ≤
i
δ
δ
δ
i=1

i=1

(i)

≤ d+α−

d + α (ii)
< d,
δ 2 d3/4

where we denote α : = logδ d + 3. The step (i) follows by definition that t = d 43 logδ (d)e + 1 while
p
step (ii) holds because as log(ed) ≥ 14, we have α = logδ d + 3 < d1/4 /δ 2 . On the other hand,
for t = dlogδ de, we have
t
t
X
X
δ−1
δ−1
b i (d + logδ d + 3)c ≥
(d + α) − t
δ
δi
i=1

i=1

1
)(d + α) − t
δt
d+α
>d+α−
− (logδ d + 1),
d
p
where the last step uses fact t = dlogδ de. Since when log(ed) ≥ 14, we have α = logδ d + 3 < d,
therefore (d + α)/d + logδ d + 1 ≤ 2 + logδ d + 1 = α, which guarantees that
= (1 −

t
X
δ−1
b i (d + logδ d + 3)c > d.
δ
i=1

35

We thereby established inequality (65).
We now claim that there exists a probability measure QL supported on M ∩ L⊥ ∩ B c (1) such
that
!

 

9λ/4 + 2
1 2
27λ
λhη, η 0 i
√
Eη,η0 ∼QL e
≤ exp exp √
− 1− √
+
, where λ : = 2 . (66)
m−1
m
32( m − 1)
Recall that we showed in inequality (65) that m ≥ d 34 logδ (d)e + 1. Setting κρ = 1/62 implies that
p
whenever 2 ≤ κρ log(ed), we have
s
r


p
1
1
4
3
1
3
1√
4
2
 ≤
log(ed) =
1 + log δ · logδ d ≤
log δ 1 + logδ d ≤
m.
(67)
62
62
3
4
62 3
4
36
So the right hand side in expression (66) can be made less than 2 by
 

9λ/4 + 2
1 2
27λ
√
exp √
− 1− √
+
m−1
m
32( m − 1)

 

√
√
9λ
m
2
1 2
27λ
m
√ √
≤ exp
+
− 1−
+ √ √
8
4 m m−1 7
32 m m − 1
 
2

1
27 8
9 8 2
+
− 1−
+
< log 2,
≤ exp
4 · 36 7 7
8
32 · 36 7
q
√
where we use the fact that m ≥ 1 + 34 logδ d ≥ 8. Lemma 2 thus guarantees the testing error to
be no less than
q
1
1
inf E(ψ; L, M, ) ≥ 1 −
Eη,η0 exp(2 hη, η 0 i) − 1 > ≥ ρ,
ψ
2
2


which leads to our result in Proposition 2.
Now it only remains to construct a probability measure QL with the right support such that
inequality (66) holds. To do this, we make use of a fact from the proof of Proposition 1 for the
orthant cone K+ ⊂ Rm . Recall that to establish Proposition 1, we constructed a probability
measure D supported on K+ ∩ S m ⊂ Rm such that if b, b0 are an i.i.d pair drawn from D, we have

 
 !
2+λ
1 2
λhb, b0 i
Eb,b0 ∼D e
≤ exp exp √
− 1− √
.
(68)
m−1
m
By construction, D is a uniform probability measure on the finite set S which consists of all vectors
√
√
in Rm which have s non-zero entries which are all equal to 1/ s where s = b mc.
Based on this measure D, let us define
p QL as in the following lemma and establish some of its
properties under the assumption that log(ed) ≥ 14.

36

Lemma B.1. Let G be the m × m lower triangular matrix given by


1
 r

1


 r2

r
1
G := 
.
 ..

..
.
.
 .
. 
.
rm−1 rm−2 · · ·
1

(69a)

There exists an d × m matrix F such that
F T F = Im

(69b)

and such that for every b ∈ S and η : = F Gb, we have
1. η ∈ M ∩ L⊥ ∩ B c (1) if L = {0}, and
2. η − η̄1 ∈ M ∩ L⊥ ∩ B c (1) if L = span(1), where η̄ =
η.

Pd

i=1 ηi /d

denotes the mean of the vector

See Appendix G.2 for the proof of this claim.
If L = {0}, let probability measure QL be defined as the distribution of η : = F Gb where b ∼ D.
Otherwise if L = span(1), let QL be the distribution of η − η̄1 where again η : = F Gb and b ∼ D.
From Lemma B.1 we know that QL is supported on M ∩ L⊥ ∩ B c (1). It only remains to verify
the critical inequality (66) to complete the proof of Proposition 2. Let η = F Gb and η 0 = F Gb0
with b, b0 being i.i.d having distribution D. Using the fact that F T F = Im , we can write the inner
product of η, η 0 as
hη, η 0 i = bT GT F T F Gb0 = hGb, Gb0 i.
The following lemma relates inner product hη, η 0 i to hb, b0 i, and thereby allows us to derive inequality (66) based on inequality (68). Recall that S consists of all vectors in Rm which have s non-zero
√
√
entries which are all equal to 1/ s where s = b mc.
Lemma B.2. For every b, b0 ∈ S, we have
hb, b0 i
r
+
,
2
(1 − r)
s(1 − r)2 (1 − r2 )
2r + r2
1
≥
−
.
(1 − r)2 s(1 − r2 )(1 − r)2

hGb, Gb0 i ≤

(70a)

kGbk22

(70b)

See Appendix G.3 for the proof of this claim.
We are now ready to prove inequality (66). We consider the two cases L = {0} and L = span(1)
separately.
√
√
For L = {0}, recall that r = 1/3 and s = b mc ≥ m − 1. Therefore as a direct consequence
of inequality (70a), we have


9λ
27λ
λhη, η 0 i
0
0
√
Eη,η∼Q e
≤ Eb,b ∼D exp
hb, b i +
.
(71)
4
32( m − 1)
37

Combining inequality (71) with (68) completes the proof of inequality (66).
Let us now turn to the case when L = span(1). The proof is essentially the same as for L = {0}
with only some minor changes. Again our goal is to check inequality (66). For this, we write
0

0

¯0

0

Eη,η0 ∼QL eλhη, η i = Eη,η0 ∼Q{0} eλhη−η̄1, η −η 1i ≤ Eη,η0 ∼Q{0} eλhη, η i .
Here the last step use the fact that hη − η̄1, η 0 − η̄ 0 1i = hη, η 0 i − dη̄ η̄ 0 ≤ hη, η 0 i where the last
inequality follows from the non-negativity of every entry of vectors η and η 0 (this non-negativity is
a consequence of the non-negativity of F and G from Lemma B.1 and non-negativity of vectors in
S).
Thus, we have completed the proof of Proposition 2.

C

Distances and their properties

Here we collect some background on distances between probability measures that are useful in
analyzing testing error. Suppose P1 and P2 are two probability measures on Euclidean space
(Rd , B) equipped with Lebesgue measure. For the purpose of this paper, we assume P1  P2 . The
total variation (TV) distance between P1 and P2 is defined as
Z
1
kP1 − P2 kTV : = sup |P1 (B) − P2 (B)| =
|dP1 − dP2 |.
(72a)
2
B∈B
A closely related measure of distance is the χ2 distance given by
Z
dP1
χ2 (P1 , P2 ) : = (
− 1)2 dP2 .
dP2

(72b)

For future reference, we note that the TV distance and χ2 distance are related via the inequality
1p 2
kP1 − P2 kTV ≤
χ (P1 , P2 ).
(72c)
2

D

Auxiliary proofs for Theorem 1 (a)

In this appendix, we collect the proofs of lemmas involved in the proof of Theorem 1(a).

D.1

Proof of Lemma D.1

Let us start with the statement with this lemma.
Lemma D.1. For a standard Gaussian random vector g ∼ N (0, Id ), closed convex cone K ∈ Rd
and vector θ ∈ Rd , we have


 t2 
P ± (Z(θ) − E[Z(θ)]) ≥ t ≤ exp −
,
and
(73a)
2




t2
,
(73b)
P ± (hθ, ΠK gi − Ehθ, ΠK gi) ≥ t ≤ exp −
2kθk22
38

where both inequalities hold for all t ≥ 0.
For future reference, we also note that tail bound (73a) implies that the variance is bounded as
Z ∞ 
Z ∞
√ 
P Z(θ) − E[Z(θ)] ≥ u du ≤ 2
e−u/2 du = 4.
(74)
var(Z(θ)) =
0

0

To prove Lemma D.1, given every vector θ, we claim that the function g →
7 kΠK (θ + g)k2 is
1-Lipschitz, whereas the function g 7→ hθ, ΠK gi is a kθk2 -Lipschitz function. From these claims,
the concentration results then follow from Borell’s theorem [9].
In order to establish the Lipschitz property, consider two vectors g, g 0 ∈ Rd . By the triangle
inequaliuty non-expansiveness of Euclidean projection, we have
kΠK (θ + g)k2 − kΠK (θ + g 0 )k2 ≤ kΠK (θ + g) − ΠK (θ + g 0 )k2 ≤ kg − g 0 k2 .
Combined with the Cauchy-Schwarz inequality, we conclude that
hθ, ΠK gi − hθ, ΠK g 0 i ≤ kθk2 kΠK g − ΠK g 0 k2 ≤ kθk2 kg − g 0 k2 ,
which completes the proof of Lemma D.1.

D.2

Proof of inequality (52)

To prove inequality (52), we make use of the following auxiliary Lemma D.2.
Lemma D.2. For every closed convex cone K and vector θ ∈ K, we have the lower bounds
Γ(θ) ≥

kθk22
2
−√ .
2kθk2 + 8EkΠK gk2
e

(75a)

Moreover, for any vector θ that also satisfies the inequality hθ, EΠK gi ≥ kθk22 , we have
Γ(θ) ≥ α2 (θ)
where α(θ) : = 1 − exp



−hθ, EΠK gi2
8kθk22



2
hθ, EΠK gi − kθk22
−√ ,
α(θ)kθk2 + 2EkΠK gk2
e

(75b)

.

We now use Lemma D.2 to prove the lower bound (52). Note that the inequality kθk22 ≥
2 ({0}, K) implies that one of the following two lower bounds must hold:
Bρ δLR

or

kθk22 ≥ Bρ EkΠK gk2 ,
p
hθ, EΠK gi ≥ Bρ EkΠK gk2 .

We will analyze these two cases separately.
39

(76a)
(76b)

Case 1 In order to show that the lower bound (76a)
p implies inequality (52), we will prove a
stronger result—namely, that the inequality kθk22 ≥ Bρ EkΠK gk2 /2 implies that inequality (52)
holds.
From the lower bound (75a) and the fact that, for each fixed a > 0, the function x 7→ x2 /(2x+a)
is increasing on the interval [0, ∞), we find that
p
Bρ EkΠK gk2 /2
2
Γ(θ) ≥ √ 1/4
−√ .
p
e
2Bρ + 8 EkΠK gk2
√
Further, because of general bound (21) that EkΠK gk2 ≥ 1/ 2π and the fact that the function
x 7→ x/(a + x) is increasing in x, we obtain
p
Bρ
2
Γ(θ) ≥
−√ ,
e
2(8πBρ )1/4 + 16
which ensures inequality (52).
Case 2 pWe now turn to the case when inequality (76b) is satisfied. We may assume the inequality
kθk22 ≥ Bρ EkΠK gk2 /2 is violated because otherwise, inequality (52) follows immediately. When
this inequality is violated, we have
p
p
hθ, EΠK gi ≥ Bρ EkΠK gk2 and kθk22 < Bρ EkΠK gk2 /2.
(77)
Our strategy is to make use of inequality (75b), and we begin by bounding the quantity
√ α
appearing therein. By combining inequality (77) and inequality (21)—namely, EkΠK gk2 ≥ 1/ 2π,
we find that
!
p
p !
Bρ EkΠK gk2
Bρ
α ≥ 1 − exp −
≥ 1 − exp − √
≥ 1/2, whenever Bρ ≥ 32π.
4
4 2π
Using expression (77), we deduce that
r
r
p
p
α2 Bρ EkΠK gk2
Bρ EkΠK gk2
2
2
p
p
−
−
Γ(θ) ≥
≥
.
e
e
α(4Bρ )1/4 + 4 EkΠK gk2
(26 Bρ )1/4 + 16 EkΠK gk2
where the second inequality uses the previously obtained lower bound α > 1/2, and the fact that
the function x 7→ x2 /(x + b) is increasing in x.
This completes the proof of inequality (52).
Proof of Lemma D.2 Now it is only left for us to prove Lemma D.2. We define the random
variable Z(θ) : = kΠK (θ + g)k2 − kΠK gk2 , as well as its positive and negative parts Z + (θ) =
max{0, Z(θ)} and Z − (θ) = max{0, −Z(θ)}, so that Γ(θ) = EZ(θ) = EZ + (θ) − EZ − (θ). Our strategy is to bound EZ − (θ) from above and then bound EZ + (θ) from below. The following auxiliary
lemma is useful for these purposes:

40

Lemma D.3. For every closed convex cone K ⊂ Rd and vectors x ∈ K and y ∈ Rd , we have:
kΠK (x + y)k2 − kΠK (y)k2 ≤ kxk2 ,

and

(78)

(i)
(ii)

max 2hx, yi + kxk22 , 2hx, ΠK yi − kxk22 ≤ kΠK (x + y)k22 − kΠK (y)k22 ≤ 2hx, ΠK yi + kxk22 .
(79)

We return to prove this claim in Appendix D.3.
Inequality (78) implies that Z(θ) ≥ −kθk2 and thus EZ − (θ) ≤ kθk2 P{Z(θ) ≤ 0}. The lower
kθk2 
bound in inequality (79) then implies that P{Z(θ) ≤ 0} ≤ P{hθ, gi ≤ −kθk22 /2} ≤ exp − 8 2 ,
whence




−kθk22
2
2
EZ − (θ) ≤ kθk2 exp
≤ sup ue−u /8 = √ .
8
e
u>0
Putting together the pieces, we have established the lower bound
2
EZ(θ) = EZ + (θ) − EZ − (θ) ≥ EZ + (θ) − √ .
e

(80)

The next task is to lower bound the expectation EZ + (θ). By the triangle inequality, we have
kΠK (θ + g)k2 ≤ kΠK (θ + g) − ΠK (g)k2 + kΠK (g)k2
≤ kθk2 + kΠK (g)k2 ,
where the second inequality uses non-expansiveness of the projection. Consequently, we have the
lower bound
+
+
kΠK (θ + g)k22 − kΠK gk22
kΠK (θ + g)k22 − kΠK gk22
+
≥E
.
(81)
EZ (θ) = E
kΠK (θ + g)k2 + kΠK gk2
kθk2 + 2kΠK gk2
Note that inequality (79)(i) implies two lower bounds on the difference kΠK (θ + g)k22 − kΠK gk22 .
We treat each of these lower bounds in turn, and show how they lead to inequalities (75a) and (75b).
Proof of inequality (75a):
imply that

Inequality (81) and the first lower bound term from inequality (79)(i)

+
2hθ, gi + kθk22
kθk22
EZ (θ) ≥ E
≥E
I{hθ, gi ≥ 0}.
kθk2 + 2kΠK gk2
kθk2 + 2kΠK gk2
+

Jensen’s inequality (and the fact that P{hθ, gi ≥ 0} = 1/2) now allow us to deduce
+

EZ (θ) ≥ P {hθ, gi ≥

0} kθk22


kθk2 +

2EkΠK gk2
P {hθ, gi ≥ 0}

and this gives inequality (75a).
41

−1
=

kθk22
2kθk2 + 8EkΠK gk2

Proof of inequality (75b): Putting inequality (81), the second term on the left hand side of
inequality (79)(i), along with the fact that hθ, EΠK gi ≥ kθk22 together guarantees that
+


2hθ, ΠK gi − kθk22
hθ, EΠK gi − kθk22
1
EZ (θ) ≥ E
≥E
I hθ, ΠK gi > hθ, EΠK gi .
kθk2 + 2kΠK gk2
kθk2 + 2kΠK gk2
2

Now introducing the event D : = hθ, ΠK gi > hθ, EΠK gi/2 , Jensen’s inequality implies that
+

EZ + (θ) ≥ P(D) E

hθ, EΠK gi − kθk22
K gk2
kθk2 + 2 EkΠ
P(D)

.

The concentration inequality (73b) from Lemma D.1 gives us that




1
hθ, EΠK gi2
.
P(D) ≥ P hθ, ΠK gi > hθ, EΠK gi ≥ 1 − exp −
2
8kθk22

(82)

(83)

Inequality (75b) now follows by combining inequalities (80), (82) and (83).

D.3

Proof of Lemma D.3

It remains to prove Lemma D.3. Inequality (78) is a standard Lipschitz property of projection
onto a closed convex cone. Turning to inequality (79), recall the polar cone K ∗ : = {z | hz, θi ≤
0, ∀ θ ∈ K}, as well as the Moreau decomposition (18)—namely, z = ΠK (z) + ΠK ∗ (z). Using this
notation, we have
kΠK (x + y)k22 − kΠK yk22 = kx + y − ΠK ∗ (x + y)k22 − ky − ΠK ∗ yk22
= kxk22 + 2hx, y − ΠK ∗ (x + y)i + ky − ΠK ∗ (x + y)k22 − ky − ΠK ∗ yk22 .
Since ΠK ∗ (y) is the closest point in K ∗ to y, we have ky − ΠK ∗ (x + y)k2 ≥ ky − ΠK ∗ (y)k2 , and
hence
kΠK (x + y)k22 − kΠK yk22 ≥ kxk22 + 2hx, y − ΠK ∗ (x + y)i.

(84)

Since x ∈ K and ΠK ∗ (x + y) ∈ K ∗ , we have hx, ΠK ∗ (x + y)i ≤ 0, and hence, inequality (84) leads
to the bound (i) in equation (79). In order to establish inequality (ii) in equation (79), we begin
by rewriting expression (84) as
kΠK (x + y)k22 − kΠK yk22 ≥ kxk22 + 2hx, y − ΠK ∗ yi + 2hx, ΠK ∗ y − ΠK ∗ (x + y)i.
Applying the Cauchy-Schwarz inequality to the final term above and using the 1-Lipschitz property
of z 7→ ΠK ∗ z, we obtain:
hx, ΠK ∗ y − ΠK ∗ (x + y)i ≥ −kxk2 kΠK ∗ y − ΠK ∗ (x + y)k2 ≥ −kxk22 ,
which establishes the upper bound of inequality (79).

42

Finally, in order to prove the lower bound in inequality (79), we write
kΠK (x + y)k22 − kΠK yk22
=kx + y − ΠK ∗ (x + y)k22 − kx + y − ΠK ∗ y − xk22
=kx + y − ΠK ∗ (x + y)k22 − kx + y − ΠK ∗ yk22 + 2hx, x + y − ΠK ∗ yi − kxk22 .
Since the vector ΠK ∗ (x + y) corresponds to the projection of x + y onto K ∗ , we have kx + y −
ΠK ∗ (x + y)k2 ≤ kx + y − ΠK ∗ yk2 and thus
kΠK (x + y)k22 − kΠK yk22 ≤ kxk22 + 2hx, ΠK yi,
which completes the proof of inequality (79).

E

Auxiliary proofs for Theorem 1 (b)

In this appendix, we collect the proofs of lemmas involved in the proof of Theorem 1(b), corresponding to the lower bound on the GLRT performance.

E.1

Proof for scenario EkΠK gk2 < 128

When EkΠK gk2 < 128, we begin by setting bρ =
then implies that
2 ≤

1
256 .

The assumed bound 2 ≤

1 2
256 δLR ({0}, K)

1 2
EkΠK gk2
1
δLR ({0}, K) ≤
< .
256
256
2

For every 2 ≤ 12 , we claim that E(φ; {0}, K, ) ≥ 1/2. Note that the uniform error E(φ; {0}, K, )
is at least as large as the error in the simple binary test
H0 : y ∼ N (0, Id )

versus

H1 : y ∼ N (θ, Id ),

(85a)

where θ ∈ K is any vector such that kθk2 = . We claim that the error for the simple binary
test (85a) is lower bounded as
inf E(ψ; {0}, {θ}, ) ≥ 1/2
ψ

whenever 2 ≤ 1/2.

(85b)

The proof of this claim is straightforward: introducing the shorthand Pθ = N (θ, Id ) and P0 =
N (0, Id ), we have
inf E(ψ; {0}, {θ}, ) = 1 − kPθ − P0 kTV .
ψ

Using the relation between χ2 distance and TV-distance in expression (72c) and the fact that
χ2 (Pθ , P0 ) = exp(2 ) − 1, we find that the testing error satisfies
1p
inf E(ψ; {0}, {θ}, ) ≥ 1 −
exp(2 ) − 1 ≥ 1/2,
whenever 2 ≤ 1/2.
ψ
2
(See Section C for more details on the relation between the TV and χ2 -distances.) This completes
the proof under the condition EkΠK gk2 < 128.
43

E.2

Proof of Lemma E.1

Let us first state Lemma E.1 and give a proof of it.
Lemma E.1. For any constant a ≥ 1 and for every closed convex cone K 6= {0}, we have
0 ≤ Γ(θ) ≤

2akθk22 + 4hθ, EΠK gi
+ bkθk2
EkΠK gk2

for all θ ∈ K,

(86a)

where
b : = 3 exp(−

(EkΠK gk2 )2
a2 kθk22
) + 24 exp(−
).
8
16

(86b)

In order to prove that Γ(θ) ≥ 0, we first introduce the convenient shorthand notation v1 : =
ΠK ∗ (θ + g) and v2 : = ΠK ∗ g. Recall that K ∗ denotes the polar cone of K defined in expression (17).
With this notation, the the Moreau decomposition (18) then implies that
kΠK (θ + g)k22 − kΠK gk22 = kθ + g − v1 k22 − kg − v2 k22
= kθk22 + 2hθ, g − v1 i + kg − v1 k22 − kg − v2 k22 .
The right hand side above is greater than kθk22 +2hθ, g −v1 i because kg −v1 k22 ≥ minv∈K ∗ kg −vk22 =
kg − v2 k22 . From the fact that Ehθ, gi = 0 and hθ, vi ≤ 0 for all v ∈ K ∗ , we have Γ(θ) ≥ 0.
Now let us prove the upper bound for expected difference Γ(θ). Using the convenient shorthand
notation Z(θ) : = kΠK (θ + g)k2 − kΠK gk2 , we define the event
1
B : = {kΠK gk2 ≥ EkΠK gk2 },
2

where g ∼ N (0, Id ).

Our proof is then based on the decomposition Γ(θ) = EZ(θ) = EZ(θ)I(B c ) + EZ(θ)I(B). In
particular, we upper bound each of these two terms separately.
Bounding E[Z(θ)I(B c )]: The analysis of this term is straightforward: inequality (78) from
Lemma D.3 guarantees that Z(θ) ≤ kθk2 , whence
EZ(θ)I(B c ) ≤ kθk2 P(B c ).
Bounding E[Z(θ)I(B)]:

(87)

Turning to the second term, we have

EZ(θ)I(B) ≤ EZ + (θ)I(B)
+
+
kΠK (θ + g)k22 − kΠK gk22
kΠK (θ + g)k22 − kΠK gk22
=E
I(B) ≤ E
I(B).
kΠK (θ + g)k2 + kΠK gk2
kΠK gk2
On event B, we can lower bound quantity kΠK gk2 with EkΠK gk2 /2 thus
+
+
kΠK (θ + g)k22 − kΠK gk22
kΠK (θ + g)k22 − kΠK gk22 I(B)
E
I(B) ≤ E
.
kΠK gk2
EkΠK gk2 /2
|
{z
}
: =T1

44

(88)

Next we use inequality (79) to bound the numerator of the quantity T1 , namely
+
+
E kΠK (θ + g)k22 − kΠK gk22 I(B) ≤ E 2hθ, ΠK gi + kθk22 I(B)
+
≤ E 2hθ, ΠK gi + akθk22 I(B),
for every constant a ≥ 1. To further simplify notation, introduce event C : = {θT ΠK g ≥ −akθk22 /2}
and by definition, we obtain
+

E 2hθ, ΠK gi + akθk22 I(B) = E 2hθ, ΠK gi + akθk22 I(B ∩ C)
≤ akθk22 + 2E[hθ, ΠK giI(B ∩ C)].

(89)

The right hand side of inequality (89) consists of two terms. The first term akθk22 is a constant, so
that we only need to further bound the second term 2Ehθ, ΠK giI(B ∩ C). We claim that
p
E[hθ, ΠK giI(B ∩ C)] ≤ Ehθ, ΠK gi + kθk2 EkΠK gk2 (6 P(C c ) + P(B c )/2).
(90)
Taking inequality (90) as given for the moment, combining inequalities (88), (89) and (90) yields
EZ + (θ)I(B) ≤ T1 ≤

p
2akθk22 + 4Ehθ, ΠK gi
+ kθk2 (24 P(C c ) + 2P(B c )).
EkΠK gk2

(91)

As a summary of the above two parts—namely inequalities (87) and (91), if we assume inequality (90), we have
Γ(θ) ≤

p
2akθk22 + 4Ehθ, ΠK gi
+ kθk2 (24 P(C c ) + 3P(B c )).
EkΠK gk2

(92)

Based on expression (92), the last step in proving Lemma E.1 is to control the probabilities P(C c ) and
P(B c ) respectively. Using the fact that hθ, ΠK gi = hθ, (g − ΠK ∗ g)i ≥ hθ, gi and the concentration
of hθ, gi, we have

and

a
a2 kθk22
a
),
P(C c ) = P(hθ, ΠK gi < − kθk22 ) ≤ P(hθ, gi < − kθk22 ) ≤ exp(−
2
2
8
1
(EkΠK gk2 )2
P(B c ) = P(kΠK gk2 < EkΠK gk2 ) ≤ exp(−
).
2
8

where the second inequality follows directly from concentration result in Lemma D.1 (73a). Substituting the above two inequalities into expression (92) yields Lemma E.1.
So it is only left for us to show inequality (90). To see this, first notice that
E[hθ, ΠK giI(B ∩ C)] = Ehθ, ΠK gi − Ehθ, ΠK giI(C c ∪ B c ).
The Cauchy-Schwarz inequality and triangle inequality allow us to deduce
−Ehθ, ΠK giI(C c ∪ B c ) = hθ, −E[ΠK gI(C c ∪ B c )]i
≤ kθk2 kE[ΠK gI(C c ∪ B c )]k2
n
o
≤ kθk2 kEΠK gI(C c )k2 + kEΠK gI(B c )k2 .
45

(93)

Jensen’s inequality further guarantees that
n
o
−Ehθ, ΠK giI(C c ∪ B c ) ≤ kθk2 E[kΠK gk2 I(C c )] + E[kΠK gk2 I(B c )] ,
|
{z
}
|
{z
}
: =T2

(94)

: =T3

By definition, on event B c , we have kΠK gk2 ≤ EkΠK gk2 /2, and consequently
T3 ≤

EkΠK gk2 P(B c )
.
2

(95)

Turning to the quantity T2 , applying Cauchy-Schwartz inequality yields
q
p
p
p
T2 ≤ EkΠK gk22 EI(C c ) = (EkΠK gk2 )2 + var(kΠK gk2 ) P(C c ).
The variance term can be bounded as in inequality (74) which says that var(kΠK gk2 ) ≤ 4.
√From inequality (21), for every non-trivial cone (K 6= {0}), we are guaranteed that EkΠK gk2 ≥
1/ 2π, and hence var(kΠK gk2 ) ≤ 8π(EkΠK gk2 )2 . Consequently, the quantity T2 can be further
bounded as
p
p
√
T2 ≤ 1 + 8πEkΠK gk2 P(C c ) ≤ 6EkΠK gk2 P(C c ).
(96)
Putting together inequalities (95), (96) and (94) yields
p
−E[hθ, ΠK giI(C c ∪ (C ∩ B c ))] ≤ kθk2 EkΠK gk2 (6 P(C c ) + P(B c )/2),
which validates claim (90) when combined with inequality (93). We finish the proof of Lemma E.1.

E.3

Calculate the testing error

The following lemma allows us to relate kΠK gk2 to its expectation:
Lemma E.2. Given every closed convex cone K such that EkΠK gk2 ≥ 128, we have
P(kΠK gk2 > EkΠK gk2 ) > 7/16.

(97)

See Appendix E.5 for the proof of this claim.
For future reference, we note that it is relatively straightforward to show that the random
variable kΠK gk2 is distributed as a mixture of χ-distributions, and indeed, the Lemma E.2 can be
proved via this route. Raubertas et al. [39] proved that the squared quantity kΠK gk22 is a mixture
of χ2 distributions, and a very similar argument yields the analogous statement for kΠK gk2 .
We are now ready to calculate the testing error for the GLRT given in equation (11b). Our
goal is to lower bound the error E(φβ ; {0}, K, ) uniformly over the chosen threshold β ∈ [0, ∞).
We divide the choice of β into three cases, depending on the relationship between β and EkΠK gk2 ,
EkΠK (θ + g)k2 . Notice this particular θ is chosen to be the one that satisfies inequality (54).
46

Case 1 First, consider a threshold β ∈ [0, EkΠK gk2 ]. It then follows immediately from inequality (97) that the type I error by its own satisfies
type I error = P0 (kΠK yk2 ≥ β) ≥ P(kΠK gk2 ≥ EkΠK gk2 ) ≥

7
.
16


Case 2 Otherwise, consider a threshold β ∈ EkΠK gk2 , EkΠK (θ + g)k2 . In this case, we again
use inequality (97) to bound the type I error, namely
type I error = P0 (kΠK yk2 ≥ β)
h
i
h
i
= P kΠK gk2 ≥ EkΠK gk2 − P kΠK gk2 ∈ [EkΠK gk2 , β)
≥

7
− max{fkΠK gk2 (x)(β − EkΠK gk2 )},
x
16

where we use fkΠK gk2 to denote the density function of the random variable kΠK gk2 As discussed
earlier, the random variable kΠK gk2 is distributed as a mixture of χ-distributions; in particular, see
Lemma E.2 above and the surrounding discussion for details. As can be verified by direct numerical
calculation, any χk variable has a density that bounded from above by 4/5. Using this fact, we
have
type I error ≥

(i) 7
(ii)
7
4
4
− (β − EkΠK gk2 ) ≥
− Γ(θ) > 3/8,
16 5
16 5


where step (i) follows by the assumption that β belongs to the interval EkΠK gk2 , EkΠK (θ + g)k2 ,
and step (ii) follows since Γ(θ) ≤ 1/16.

Case 3 Otherwise, given a threshold β ∈ EkΠK (g + θ)k2 , ∞ , we define the scalar x : = β −
EkΠK (g + θ)k2 . From the concentration inequality given in Lemma D.1, we can deduce that
type II error ≥ Pθ (kΠK yk2 ≤ β)


= 1 − P kΠK (θ + g)k2 − EkΠK (θ + g)k2 > β − EkΠK (θ + g)k2
≥ 1 − exp(−x2 /2).
At the same time,
type I error = P0 (kΠK yk2 ≥ β) = P(kΠK gk2 ≥ EkΠK gk2 ) − P(kΠK gk2 ∈ [EkΠK gk2 , β))
7
4
≥
− (β − EkΠK gk2 ),
16 5
where we again use inequality (97) and the boundedness of the density of kΠK gk2 . Recalling
that

we have defined x : = β − EkΠK (g + θ)k2 as well as Γ(θ) = E kΠK (θ + g)k2 − kΠK gk2 , we have
β − EkΠK gk2 = x + Γ(θ) ≤ x +

47

1
,
16

where the last step uses the fact that Γ(θ) ≤ 1/16. Consequently, the type I error is lower bounded
as
type I error ≥

7
4
31 4
− (x + 1/16) =
− x.
16 5
80 5

Combining the two types of error, we find that the testing error is lower bounded as
o
n 31 4
312
) ≥ 0.11.
inf ( − x)+ + 1 − exp(−x2 /2) = 1 − exp(−
x>0
80 5
2 × 642
Putting pieces together, the GLRT cannot succeed with error smaller than 0.11 no matter how
the cut-off β is chosen.

E.4

Proof of inequality (54)

Now let us turn to the proof of inequality (54). First notice that if the radius satisfies 2 ≤
2 ({0}, K), then there exists some θ ∈ H with kθk =  that satisfies
bρ δLR
1
2
p
kθk22 ≤ bρ EkΠK gk2 and hθ, EΠK gi ≤ bρ EkΠK gk2 .
(98)
p
Setting a = 4/ bρ ≥ 1 in inequality (86a) yields
p
8kθk22 / bρ + 4hθ, EΠK gi
+ bkθk2
Γ(θ) ≤
EkΠK gk2
2

kθk2

where b : = 3 exp(− (EkΠK8 gk2 ) ) + 24 exp(− bρ 2 ). Now we only need to bound the two terms in the
upper bound separately. First, note that inequality (98) yields
p
p
8kθk22 / bρ + 4hθ, EΠK gi
(99)
≤ 12 bρ .
EkΠK gk2
On the other hand, again by applying inequality (98), it is straightforward to verify the following
two facts that
q
(EkΠK gk2 )2
(EkΠK gk2 )2
kθk2 exp(−
) ≤ bρ EkΠK gk2 exp(−
)
8
8
 1/4
p
p
√
x2
2
,
≤ bρ max
x exp(− ) = bρ
8
e
x∈(0,∞)
r
bρ
kθk22
x2
and kθk2 exp(−
) ≤ sup x exp(− ) =
.
bρ
b
2e
ρ
x∈(0,∞)
Combining the above two inequalities ensures an upper bound for product bkθk2 and directly leads
to upper bound of quantity Γ(θ), namely
r
 1/4
p
p
bρ
2
+ 24
,
Γ(θ) ≤ 12 bρ + 3 bρ
e
2e
With the choice of bρ , we established inequality (54).
48

E.5

Proof of Lemma E.2

In order to prove this result, we first define random variable F : = kΠK gk22 − m, where m : =
EkΠK gk22 and σ̃ 2 : = var(F ). We make use of the Theorem 2.1 in Goldstein et al. [19] which shows
that the distribution of F and Gaussian distribution Z ∼ N (0, σ̃ 2 ) are very close, more specifically,
the Theorem says
16 √
8
.
m ≤
2
σ̃
EkΠK gk2
p
In the last inequality, we use the facts that σ̃ 2 ≥ 2m and EkΠK gk22 ≥ EkΠK gk2 .
kF − ZkTV ≤

(100)

It is known that the quantity kΠK gk22 is distributed as a mixture of χ2 distributions(see e.g.,
[39, 19])—in particular, we can write
law
kΠK gk22 =

VK
X

Xi = WK + VK ,

WK =

i=1

VK
X

(Xi − 1),

i=1

where each {Xi }i≥1 is an i.i.d. sequence χ21 variables, independent of VK . Applying the decomposition of variance yields
σ̃ 2 = var(VK ) + 2EkΠK gk22 ≥ 2m.
We can write the probability P(kΠK gk2 > EkΠK gk2 ) as
P(kΠK gk2 > EkΠK gk2 ) = P(kΠK gk22 − EkΠK gk22 > (EkΠK gk2 )2 − EkΠK gk22 ) ≥ P(F > 0).
So if EkΠK gk2 ≥ 128, then inequality (100) ensures that dT V (F, N ) ≤ 1/16, and hence
P(F > 0) ≥ P(Z > 0) − kF − ZkTV ≥

7
.
16

We finish the proof of Lemma E.2.

F

Auxiliary proofs for Theorem 2

In this appendix, we collect the proofs of various lemmas used in the proof of Theorem 2.

F.1

Proof of Lemma 2

For every probability measure Q supported on K ∩ B c (1), let vector θ be distributed accordingly
to measure Q then it is supported on K ∩ B c (). Consider a mixture of distributions,
P1 (y) = Eθ (2π)−d/2 exp(−

49

ky − θk22
).
2

(101)

Let us first control the χ2 distance between distributions P1 and P0 : = N (0, Id ). Direct calculations
yield
 2

2
P1
ky − θk22 kyk22
2
χ (P1 , P0 ) + 1 = EP0
= EP0 Eθ exp{−
+
}
P0
2
2

2
kθk22
= EP0 Eθ exp{hy, θi −
} .
2
Suppose random vector θ0 is an independent copy of random vector θ, then
kθk22 + kθ0 k22
}
2
kθ + θ0 k22 kθk22 + kθ0 k22
= Eθ,θ0 exp{
−
}
2
2
= Eθ,θ0 exp(hθ, θ0 i)

χ2 (P1 , P0 ) + 1 = EP0 Eθ,θ0 exp{hy, θ + θ0 i −

= E exp(2 hη, η 0 i),

(102)

where the second step uses the fact the moment generating function of multivariate normal distribution. As we know, the testing error is always bounded below by 1 − kP1 , P0 kTV , so by the relation
between the χ2 distance and TV distance, we have:
testing error ≥ 1 −

1p
E exp (2 hη, η 0 i) − 1,
2

which completes our proof.

F.2

Proof of Lemma F.1

Let us first provide a formal statement of Lemma F.1 and then prove it.
Lemma F.1. Letting η and η 0 denote an i.i.d pair of random variables drawn from the distribution
Q defined in equation (56), we have
 2

5 kEΠK gk22 404 E(kΠK gk22 )
1
2
0
Eη,η0 exp( hη, η i) ≤ 2 exp
+
,
(103)
a
(EkΠK gk2 )2
(EkΠK gk2 )4
where a : = P(kΠK gk2 ≥ 12 EkΠK gk2 ) and  > 0 satisfies the inequality 2 ≤ (EkΠK gk2 )2 /32.
To prove this result, we use Borell’s lemma [9] which states that for a standard Gaussian vector
Z ∼ N (0, Id ) and a function f : Rd → R which is L-Lipschitz, we have
E exp(af (Z)) ≤ exp(aEf (Z) + a2 L2 /2)
for every a ≥ 0.
Let g, g 0 be i.i.d standard normal vectors in Rd . Let
1
1
A(g) : = {kΠK gk2 > EkΠK gk2 } and A(g 0 ) : = {kΠK g 0 k2 > EkΠK g 0 k2 }
2
2
50

(104)

By definition of the probability measure Q in expression (56), we have
"
#


2 hΠ g, Π g 0 i
4
K
K
Eη,η0 exp(2 hη, η 0 i) = Eg,g0 exp
A(g) ∩ A(g 0 )
EkΠK gk2 EkΠK g 0 k2


1
42 hΠK g, ΠK g 0 i
0
I(A(g) ∩ A(g 0 )).
=
Eg,g exp
P(A(g) ∩ A(g 0 ))
EkΠK gk2 EkΠK g 0 k2
Using the independence of g, g 0 and non-negativity of the exponential function, we have


42 hΠK g, ΠK g 0 i
1
2
0
Eg,g0 exp
Eη,η0 exp( hη, η i) ≤
.
P(A(g))2
EkΠK gk2 EkΠK g 0 k2
|
{z
}

(105)

: =T1

To simplify the notation, we write λ : = 42 /(EkΠK gk2 )2 so that

T1 = Eg,g0 exp λhΠK g, ΠK g 0 i .

(106)

Now for every fixed value of g, the function h 7→ hΠK g, ΠK hi is Lipschitz with Lipschitz constant
equal to kΠK gk2 . This is because
|hΠK g, ΠK hi − hΠK g, ΠK h0 i| ≤ kΠK gk2 kΠK h − ΠK h0 k2 ≤ kΠK gk2 kh − h0 k2 ,
where we used Cauchy-Schwartz inequality and the non-expansive property of convex projection.
As a consequence of inequality (104) and Cauchy-Schwartz inequality, the term T1 can be upper
bounded as


λ2 kΠK gk22
0
T1 ≤ Eg exp λhΠK g, EΠK g i +
2
q
q

≤ Eg exp (2λhΠK g, EΠK g 0 i) Eg exp λ2 kΠK gk22 .
(107)
{z
}
|
{z
}|
: =T3

: =T2

We now control T2 , T3 separately. For T2 , note again that h 7→ hΠK h, EΠK g 0 i is a Lipschitz function
with Lipschitz constant equal to kEΠK g 0 k2 . Inequality (104) implies therefore that
q

T2 ≤ exp 2λhEΠK g, EΠK g 0 i + 2λ2 kEΠK g 0 k22 .
(108)
To control quantity T3 , we use a result from [1, Sublemma E.3] on the moment generating function
of kΠK gk2 which gives
s


2λ4 E(kΠK gk22 )
2
2
,
whenever λ < 1/4.
(109)
T3 ≤ exp λ E(kΠK gk2 ) +
1 − 4λ2
Because of the assumption that 2 ≤ (EkΠK gk2 )2 /32, we have λ ≤ 1/8 < 1/4. Therefore putting
all the pieces together as above, we obtain


1
λ2 E(kΠK gk22 ) λ4 E(kΠK gk22 )
2
0
2
2
Eη,η0 exp( hη, η i) ≤
exp (λ + λ )kEΠK gk2 +
+
P(A(g))2
2
1 − 4λ2

1
≤
exp 1.25λkEΠK gk22 + 2.5λ2 E(kΠK gk22 )
2
P(A(g))
 2

1
5 kEΠK gk22 404 E(kΠK gk22 )
=
exp
+
)
.
P(A(g))2
(EkΠK gk2 )4
(E(kΠK gk22 )
51

This completes the proof of inequality (103).

G

Auxiliary proofs for Proposition 2 and the monotone cone

In this appendix, we collect various results related to the monotone cone, and the proof of Proposition 2.

G.1

Proof of Lemma 1

So as to simplify notation, we define ξ = ΠK g, with j th coordinate denoted as ξj . Moreover, for a
given vector g ∈ Rd and integers 1 ≤ u < v ≤ d, we define the u to v average as
v

ḡuv : =

X
1
gj .
v−u+1
j=u

To demonstrate an upper bound for the inner product
enough to take η =

√1 (−1, 1, 0, . . . , 0)
2

inf

η∈K∩S d

hη, EΠK gi, it turns out that it is

∈ K ∩ S d and uses the fact that

1
hη, EΠK gi ≤ √ E(ξ2 − ξ1 ).
η∈K∩S d
2
inf

(110)

So it is only left for us to analyze E(ξ2 − ξ1 ) which actually has an explicit form based on the
explicit representation of projection to the monotone cone (see Robertson et al. [43], Chapter 1)
where
ξi = λi − λ̄,

λi = max min ḡuv .
u≤j v≥j

(111)

This is true because projecting to cone K = M ∩L⊥ can be written into two steps ΠK g = ΠL⊥ (ΠM g)
and projecting to subspace L⊥ only shifts the vector to be mean zero.
We claim that the difference satisfies
ξ2 − ξ1 ≤ max |ḡ2v | + max |ḡ1v |.
v≥2

v≥1

(112)

To see this, as a consequence of expression (111), we have
ξ2 − ξ1 = max{min ḡ1v , min ḡ2v } − min ḡ1v .
v≥2

v≥2

v≥1

The right hand side above only takes value in set {minv≥2 ḡ1v − g1 , 0, minv≥2 ḡ2v − minv≥1 ḡ1v }
where the last two values agree with bound (112) obviously while the first value can be written as
!
v
1
1
1X
gi − (1 − )g1 = min(1 − )(ḡ2v − g1 ) ≤ |ḡ2v | + |g1 |,
min ḡ1v − g1 = min
v≥2
v≥2
v≥2
v
v
v
i=2

52

which also agrees with inequality (112).
Next let us prove that for every j = 1, 2, we have
√
E max |ḡjv | < 20 2,

(113)

v≥j

and combine this fact with expressions (112) and (110) gives us

inf

η∈K∩S d

hη, EΠK gi ≤ 40 which

validates the conclusion in Lemma 1.
It is only left for us to verify inequality (113). First as we can partition the interval [j, d] into
k smaller intervals where each smaller interval is of length 2m except the last one, then
E max |ḡjv | = E max max |ḡjv | ≤
1≤m≤k v∈Im

j≤v≤d

k
X

E max |ḡjv |,

m=1

(114)

v∈Ik

where Im = [2m + j − 2, 2m+1 + j − 3], 1 ≤ m < k, the number of intervals k and length of Ik are
chosen to make those intervals sum up to d.
Given index 2m + j − 2 ≤ v ≤ 2m+1 + j − 3, random variables ḡjv are Gaussian distributed
with mean zero and variance 1/(v − j + 1). Suppose we have Gaussian random variable Xv with
2 = 1/(2m − 1) and the covariance satisfies cov(X , X 0 ) = cov(ḡ , ḡ 0 ).
mean zero and variance σm
v
jv jv
v
2
Since σm ≥ 1/(v − j + 1), the variable maxv∈Im |ḡjv | is stochastically dominated by the maximum
max2m ≤v≤2m+1 −1 |Xv |, and therefore
k
X
m=1

E max |ḡjv | ≤
v∈Im

k
X

E

m=1

max

2m ≤v≤2m+1 −1

|Xv |.

2
Applying the fact that
√ for t ≥ 2 number of Gaussian random variable i ∼ N (0, σ ), we have
E max1≤i≤t |i | ≤ 4σ 2 log t which gives
k
X
m=1

E max |ḡjv | ≤
v∈Im

k
X

p
p
4σm 2 log(2m ) = 4 2 log 2

m=1

The last step is to control the sum

m=1

Pk

m=1

q

m
2m −1 .

m=1

m
2m − 1

!
.

(115)

There are many ways to show that it is upper

bounded by some constant. One crude way is use the fact that
therefore we have
k r
X

k r
X

√
m
2m −1

≤ 2m/4 whenever m ≥ 5,

4 r
k r
4 r
k
X
X
X
X
1
m
m
m
m
=
+
<
+
m
m
m
m
m/4
2 −1
2 −1
2 −1
2 −1
2
m=1
m=5
m=1
m=5
r
4
X
m
2−5/4
<
+
< 6,
2m − 1 1 − 2−1/4
m=1

which validates inequality (113) when combined with inequalities (114) and (115). This completes
the proof of Lemma 1.
53

G.2

Proof of Lemma B.1

The proof of Lemma B.1 involves two parts. First, we define the matrices G, F . Then we prove
that the distribution of η has the right support where we make use of Lemma B.2.
As stated, matrix G is a lower triangular matrix satisfying (69a). Let us now specify the matrix
F . Recall that we denote δ : = r−2 and r : = 1/3. To define matrix F , let us first define a partition
of [d] into m consecutive intervals I1 , . . . , Im with m specified in expression (64) and the length
of each interval |Ii | = `i where `i is defined as
`i : = b
and `m : = d −

Pm−1
i=1

δ−1
(d + logδ d + 3)c,
δi

1 ≤ i ≤ m − 1,

(116)

`i .

Following directly from the definition (116), each length `i ≥ 1 and `i is a decreasing sequence
with regard to i. Also `i satisfies the following
δ−1
(d + logδ d + 3)c < d
and `i ≥ δ`i+1 , for 1 ≤ i ≤ m − 1,
(117)
δ
p
where the first inequality holds since as log(ed) ≥ 14, we have (δ − 1)(logδ d + 3) ≤ d and the
last inequality follows from the fact that babc ≥ abbc for positive integer a and b ≥ 0 (because abbc
is an integer that is smaller than ab).
`1 = b

We are now ready to define the d × m matrix F . We take

 √1
i ∈ Ij ,
`j
F (i, j) =
0
otherwise.

(118)

It is easy to check that matrix F satisfies F T F = Im which validates inequality (69b).
First we show that both η = F Gb and η − η̄1 belong to M. The i-th coordinate of η can be
written as
j
1 X j−t
ηi = p
r bt ,
`j t=1

∀ i ∈ Ij .

Therefore we can denote uj as the value of ηi for i ∈ Ij . To establish monotonicity, we only need
to compare the value in the consecutive blocks. Direct calculation of the consecutive ratio yields
s
p
P
`j
uj+1
r( jt=1 rj−t bt ) + bj+1
`j
p
=
≥ 1,
≥r
Pj
j−t b
uj
`j+1
`j+1
t
t=1 r
where we used the non-negativity of coordinates of vector b and the last inequality follows from inequality (117) and δ = r−2 . The monotonicity of η − η̄1 thus inherits directly from the monotonicity
of η.
To complete the proof of Lemma B.1, we only need to prove lower bounds on kηk2 and kη − η̄k2 .
For these, we shall use inequality (70b) of Lemma B.2.
54

Proof of the bound kηk2 ≥ 1:
ity (70b) in Lemma B.2, we have

Recall that r = 1/3 and as a direct consequence of inequal-

9
63
−
> 1.96,
(119)
4 32s
√
where the last step follows form the fact that s = b mc ≥ 7. Therefore, the norm condition holds
so η is supported on M ∩ LT ∩ B c (1).
hη, ηi = kGbk22 ≥

Proof of the bound kη − η̄1k2 ≥ 1:

The norm kη − η̄1k22 has the following decomposition where

kη − η̄1k22 = kηk22 − d(η̄)2 .
We claim that d(η̄)2 ≤ 0.2. If we take this for now, combining with inequality (119) which says
kηk22 is greater than 1.96, we can deduce that kη − η̄1k22 ≥ 1. So it suffices to verify the claim
d(η̄)2 ≤ 0.2. Recall that η = F Gb. Direct calculation yields
dη̄ = h1, ηi = 1T · F Gb =

m
X
k=1

bk

m p
X
`i ri−k .

|i=k {z

: =ak

}

Plugging into the definitions of r and `i guarantees that
r
m
m
q
X
X
(δ − 1)(d + logδ d + 3)
1
k
ak ≤
(δ
−
1)(d
+
log
d
+
3)δ
δ −i
=
δ
(i−k)/2
δi
δ
i=k
i=k
s
(d + logδ d + 3)
≤
,
(δ − 1)δ k−2
Pm −i
≤ δ −k+1 /(δ −
where the last step uses the summability of a geometric
sequence—namely
i=k δ
P
1). Now for every vector b, our goal is to control
ak bk . Recall that every vector b has s non-zero
P
√
√
entries which equal to 1/ s where s = b mc. Since ak decreases with k, this inner product
ak bk
is largest when the first s coordinates of b are non-zero, therefore
r
r
s
s
X
1
1
δ 2 (d + logδ d + 3) X 1
1
δ 2 (d + logδ d + 3) 1
√
√
dη̄ ≤
ak √ ≤ √
≤
,
k/2
δ−1
δ−1
s
s
s
δ
δ−1
k=1
k=1
and thus we have
d(η̄)2 ≤ √

1
(d + logδ d + 3)
δ2
81(d + logδ d + 3)
√
√
≤
< 0.2,
d
m−1
32d( m − 1)
(δ − 1)( δ − 1)2

where the last step uses
on M ∩ LT ∩ B c (1).

√

m ≥ 8. Therefore, the norm condition also holds so η − η̄1 is supported

Thus, we have completed the proof of Lemma B.1.

55

G.3

Proof of Lemma B.2

By definition of the matrix G, we have
hGb, Gb0 i =

m
X

(Gb)t (Gb0 )t =

t=1

=

m
X

(bt + rbt−1 + · · · + rt−1 b1 )(b0t + rb0t−1 + · · · + rt−1 b01 )

t=1
m X
t X
t
X

r2t−u−v bu b0v .

t=1 u=1 v=1

Switching the order of summation yields
0

hGb, Gb i =

m X
m
X
u=1 v=1

=

m X
m
X
u=1 v=1

m
X

bu b0v

r2t−u−v

t=max{u,v}

bu b0v r2 max{u,v} − r2m+2
ru+v
1 − r2

m m
m m
1 XX
1 XX
0 |u−v|
bu bv r
bu b0v r2m+2−u−v .
−
=
1 − r2
1 − r2
u=1 v=1
u=1 v=1
{z
} |
{z
}
|
: =∆1

(120)

: =∆2

We bound the two terms ∆1 and ∆2 separately.
√
Recall the fact that b, b0 belong to S, so there are exactly s = b mc non-zero entry in both
√
b and b0 and these entries equal to 1/ s. The summation defining ∆1 is not affected by the
permutation of coordinates, so that we can assume without loss of generality that the indices of
non-zero entries in b are indexed by {1, . . . , s}, and that the indices of non-zero entries in b0 are
indexed by {k, k + 1, . . . , k + s − 1} for some 1 ≤ k ≤ m + 1 − s.
We split our proof into two cases depending on whether k ≤ s or k > s.
Case 1 (k ≤ s):

The summation ∆1 can be written as
2

s(1 − r )∆1 = s

m X
m
X

bu b0v r|u−v|

=

u=1 v=1

s k+s−1
X
X

r|u−v| .

u=1 v=k

Direct calculation yields
s(1 − r2 )∆1 =

k−1 k+s−1
X
X

rv−u +

u=1 v=k
(1 − rs )(r

s X
u
X
u=k v=k

ru−v +

s k+s−1
X
X

rv−u

u=k v=u+1

−
s−k+1
r
r(s − k + 1) rk − rs+1
s−k+1
−
−
+
(1
−
r
)
+
(1 − r)2
1−r
(1 − r)2
1−r
(1 − r)2
1+r
rk (rs + rs+2 − 2)
=
(s − k + 1) +
.
1−r
(1 − r)2

=

rk )

56

Notice the following two facts that
hb, b0 i =

s−k+1
s

and

rk (rs + rs+2 − 2)
−2r
≤
< 0,
(1 − r)2
(1 − r)2

so that
1
−2r
1
hb, b0 i +
≤ ∆1 ≤
hb, b0 i.
2
2
2
(1 − r)
s(1 − r )(1 − r)
(1 − r)2
Case 2 (k > s):

(121)

The summation ∆1 satisfies the bounds
2

s(1 − r )∆1 = s

m X
m
X

bu b0v r|u−v|

=

u=1 v=1

s k+s−1
X
X
u=1 v=k

rv−u =

rk−s (1 − rs )2
.
(1 − r)2

Since k − s ≥ 1, we have hb, b0 i = 0 and consequently
∆1 ≤

1
r
hb, b0 i +
.
2
2
(1 − r)
s(1 − r )(1 − r)2

(122)

Combining inequalities (120), (121) and (122), we can deduce that
hGb, Gb0 i ≤ ∆1 ≤

r
1
hb, b0 i +
,
(1 − r)2
s(1 − r2 )(1 − r)2

which validates inequality (70a).
On the other hand, when b = b0 , the summation ∆2 is the largest when the non-zero entries of
b lie on coordinates m − s + 1, . . . , m. Thus we have
m
X

2

s(1 − r )∆2 ≤

m
X

r2m+2−u−v =

u=m−s+1 v=m−s+1

r2 (1 − rs )2
r2
<
.
(1 − r)2
(1 − r)2

Combining decomposition (120) with the inequalities (121), we can deduce that
hGb, Gbi ≤

1
2r
r2
−
−
,
(1 − r)2 s(1 − r2 )(1 − r)2 s(1 − r2 )(1 − r)2

where we use the fact that hb, bi = 1. This completes the proof of inequality (70b).

57

(123)

