arXiv:1605.09456v3 [] 9 Feb 2017

Concentration of the empirical level sets
of Tukey’s halfspace depth
Victor-Emmanuel Brunel,
Victor-Emmanuel Brunel
Department of Mathematics
Massachusetts Institute of Technology
77 Massachusetts Avenue,
Cambridge, MA 02139-4307, USA
e-mail: vebrunel@math.mit.edu
Abstract: Tukey’s halfaspace depth has attracted much interest in data
analysis, because it is a natural way of measuring the notion of depth
relative to a cloud of points or, more generally, to a probability measure.
Given an i.i.d. sample, we investigate the concentration of upper level sets
of the Tukey depth relative to that sample around their population version.
We show that under some mild assumptions on the underlying probability
measure, concentration occurs at a parametric rate and we deduce moment
inequalities at that same rate. In a computational prospective, we study
the concentration of a discretized version of the empirical upper level sets.
AMS 2000 subject classifications: Primary 62H11.
Keywords and phrases: Tukey depth, level set, multivariate quantiles,
convex body, support function, semi-infinite linear programming.

1. Preliminaries and notation
1.1. Preliminary
Tukey’s halfspace depth or, in short, Tukey depth, introduced by Tukey [Tuk75],
has attracted much attention in multivariate data analysis, as a tool for understanding and describing which data are relevant in a given cloud of points. For
a finite multivariate sample, Tukey depth at any given point x is the minimum
proportion of points of the sample enclosed in a closed halfspace containing
x. Tukey depth, together with other notions of statistical depths (see [ZS00b]
for general definitions) has been studied and used extensively especially for description or graphical representation of data [LPS99], robust [DG92, ACG94] or
nonparametric (e.g., [LS93]) inference, bootstrap [YS97], supervised classification [GC05a, GC05b], etc... When the sample consists of i.i.d. random points,
we call it empirical Tukey depth and it has a population analog (one can find
formal definitions of the population Tukey depth in Euclidean spaces in [RR99]
and extensions to infinite dimensional Banach spaces in [DGC11]). Consistency
and limit theorems for the empirical Tukey depth are well-known (see [Mas04],
for instance, where the author tackles the asymptotic properties of the empirical
Tukey depth seen as a stochastic process).
1
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

2

In this work, we are interested in the upper level sets of Tukey depth (we
drop the qualifying upper in the sequel). These sets are nested and the center
of gravity of the deepest one is called the Tukey median. On the opposite, the
convex hull of a sample of n points is the largest bounded empirical level set.
Convergence and concentration of this random polytope has attracted a lot
of attention in convex and stochastic geometry (see [Bru14], [Fre13] and the
references therein).
We show concentration of the level sets of the empirical Tukey depth of a
given and fixed (independent of the sample size) level around the corresponding
level sets of the population Tukey depth and we prove that the speed of convergence is parametric, i.e., of the order n´1{2 . Similar questions have already been
tackled in earlier works. Consistency of the empirical level sets was proven in
[HW97, ZS00a] for general notions of statistical depth, including Tukey depth.
In [Kim00], the author shows that for all ε P p0, 1q, with probability 1 ´ ε, the
empirical depth level set is sandwiched between two population level sets whose
levels are at a distance of order n´1{2 from each other. However, the constants
are not explicit and the way they depend on ε cannot be derived from the results,
which, in turn, do not yield moment inequalities. In [HW97, ZS00a, Kim00], the
proofs are based on the global behavior of the stochastic process defined by the
empirical depth, indexed by the ambient Euclidean space. Hence, the results in
these works are based on global and very strong assumptions on the underlying probability measure. In our work, we focus on Tukey depth and only make
local assumptions that guarantee some local continuity properties of the underlying distribution. We show that these assumptions are very weak, in the sense
that they are satisfied by a broad class of distributions, including most commonly used ones. Not only we achieve the same (parametric) rate as obtained
in [Kim00], but our main result allows us to derive moment inequalities with a
parametric rate.
Our approach is based on a polyhedral representation of the level sets of the
population and empirical Tukey depths. As we will see in Lemma 1, which is
a refinement of Theorem 2 in [KM12], these level sets can also be written as
multivariate quantile sets, defined as convex regions that satisfy infinitely many
linear constraints. It is because of such a multivariate quantile representation
that the level sets of Tukey depth have also attracted attention in multivariate
quantile regression (see [Cha96, HPvS10] and the references therein). With this
approach, we reduce the problem to that of estimating the support function of
the population level sets. We believe that the techniques we use in our proofs
could be useful in other problems related to support function estimation. For
instance, in [Gun12], the support function of an unknown convex set is observed
up to some noise; We believe that our proof method could be used in order
to bound from above the risk for estimation of the unknown convex set in
Hausdorff distance, whereas the measure of the risk used in [Gun12] does not
have a natural, geometric interpretation.
Computation of the empirical Tukey depth level sets for samples of n points
is a challenging problem. In dimension 2, they can be computed in Opn2 q (see
[MRR` 03]). A naive computation of the Tukey depth at one point would require
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

3

to explore infinitely many halfspaces, which is not feasible. In higher dimensions,
there is no practical and efficient way to compute the level sets of the Tukey
depth. This is why we define a proxy for the empirical level sets, based on a
discretized version of the Tukey depth. We show that they are consistent and still
concentrate at the same parametric speed as the original ones. In practice, the
number of operations required to compute this proxy grows exponentially with
the dimension of the ambient space, but it can still be useful if the dimension
is not too large.
Before going further into details, we introduce some notation. In this paper,
d ě 2 and n ě 1 are fixed integers, unless stated otherwise. The Euclidean norm
in Rd is denoted by | ¨ | and the dot product between two vectors x and y is
denoted by xx, yy. The pd ´ 1q-dimensional unit sphere is S d´1 “ tu P Rd : |u| “
1u. For u P S d´1 , uK stands for the hyperplane in Rd that is orthogonal to u. If
k is a positive integer, a P Rk and R ě 0, Bk pa, Rq (resp. Bk1 pa, Rq) stands for
the closed (resp. open) Euclidean ball in Rk with center a and radius R. When
k “ d, we drop the subscript k.
The complement of a set A is denoted by AA . The symmetric difference between two sets A and B in Rd is denoted by A△B. For k ě 1, if A is a measurable set in Rk (equipped with the Lebesgue measure), we denote by Volk pAq its
k-dimensional volume, i.e., its Lebesgue measure in Rk .
˝

For A Ď Rd , the interior of A is denoted by A: this is the largest open set
included in A. The collection of closed halfspaces in Rd is denoted by H. For
u P S d´1 and t P R, we define the closed halfspace Hu,t “ tx P Rd : xu, xy ď tu.
The Hausdorff distance between two sets K, K 1 Ď Rd is
dH pK, K 1 q “ inftε ą 0 : K Ď K 1 ` εBp0, 1q and K 1 Ď K ` εBp0, 1qu,
where we set infpHq “ 8. If K is a convex body (i.e., convex and compact), its
support function hK is defined as hK puq “ maxxu, xy, u P Rd .
xPK

The cardinality of a finite set I is denoted by #I. For x P R, we denote by
rxs the smallest integer larger or equal to x.
Throughout the paper, X, X1 , X2 , . . . are independent, identically distributed
(i.i.d.) random variables defined on a probability space pΩ, F , Pq, taking values
in Rd . Their common probability distribution is denoted by µ and is defined
onřthe Borel σ-algebra of Rd . The empirical distribution µn is defined by µn “
n
1
d
i“1 δXi , where δa is the Dirac measure at the point a P R .
n
For two positive sequences pan qně1 and pbn qně1 , we write an “ Opbn q when
the ratio an {bn is bounded uniformly in n ě 1. For two positive sequences of
random variables pAn qně1 and pBn qně1 , we write An “ OP pBn q when for all
δ ą 0, there exists Mδ ą 0 such that PrAn ą Mδ Bn s ď δ, @n ě 1.
Section 2 is devoted to general results about Tukey depth level sets. Our main
theorems are given in Section 3 and the proofs are deferred to Section 4. The
rest of this section is dedicated to important definitions.

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

4

1.2. Definitions
The Tukey depth associated with a probability measure ν in Rd is the function
Dν pxq “

inf

HPH:xPH

νpHq,

@x P Rd .

We refer to Dµ as the population Tukey depth and to Dµn as the empirical
Tukey depth.
In this work, we are interested in comparing the level sets of Dµ and Dµn . Let
α P p0, 1q be fixed. The α-level set of Dµ is defined as Gµ “ tx P Rd : Dµ pxq ě
(
αu and we denote by Ĝ the α-level set of Dµn : Ĝ “ x P Rd : Dµn pxq ě α .
We study how fast Ĝ concentrates around Gµ , i.e., how fast the stochastic
convergence of dH pĜ, Gµ q to zero is. As intermediate tools and for independent
interest, we introduce the following sets associated with µ:
1. The multidimensional p1 ´ αq-quantile set of µ:
Let X be a random variable with probability distribution µ. For u P Rd , let
qu5 and qu7 be the lower and upper p1 ´ αq-quantile of xu, Xy, respectively:
qu5 “ inftt P R : Prxu, Xy ď ts ě 1 ´ αu

and

qu7 “ suptt P R : Prxu, Xy ě ts ě αu.

The corresponding lower and upper multidimensional p1 ´ αq-quantile sets
of µ are defined as
GηMQ “ tx P Rd : xu, xy ď quη , @u P S d´1 u,
č
2. The α-floating body of µ: GFB “
H.

η P t5, 7u.

(1)

HPH:µpHqě1´α

As we will see in Lemma 1 below, these sets are other representations of
the Tukey depth level sets. The representation in terms of multidimensional
quantile sets is particularly convenient for our purposes because it characterizes
the Tukey depth level sets through linear constraints. We make the floating body
part of our analysis because it plays an important role for random polytopes.
Barany and Larman [BL88] proved that if µ is the uniform distribution in a
convex and compact set of volume 1, then the expected missing volume of the
convex hull of X1 , . . . , Xn behaves aymptotically as the missing volume of the
p1{nq-floating body of µ. Fresen [Fre13] proved that if µ is log-concave, the
convex hull of X1 , . . . , Xn approximates the p1{nq-floating body of µ with high
probability. For very small values of α, even smaller than 1{n, when the empirical
level set would be a very poor estimator of Gµ , [He16] defines and studies an
estimator that extends univariate estimators from extreme value theory.
2. Tukey depth level sets
We start with a simple lemma that shows the relationships between the sets
defined above: The Tukey depth level sets, the lower and upper multidimensional
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

5

quantile sets and the floating bodies. This lemma is a refinement of Theorem 2
in [KM12] but we include its proof at the end for the sake of completeness.
Lemma 1. GFB “ G5MQ Ď G7MQ “ Gµ .
In particular, if µ satisfies some continuity property, e.g., Assumption 1 below,
then qu5 “ qu7 for all unit vectors u, so the inclusion becomes an equality and all
four sets are equal.
[KM12] provides an interesting discussion about the multivariate quantile
representation of Gµ : In brief, the knowledge of Gµ does not imply the knowledge
of all univariate quantiles qu7 , u P S d´1 . Indeed, some of the linear constraints
that define G7MQ may not be active, i.e., there may be some unit vectors u for
which xu, xy ă qu7 , @x P G7MQ . This fact constitutes the main difficulty in the
proof of Theorem 2 below, where we use the support function of G7MQ . For
u P S d´1 , it is clear that the linear constraint “xu, xy ď qu7 ” is active if and only
if hGµ puq “ qu7 . If that constraint is not active, then hGµ puq ă qu7 . In that case,
not only Gµ provides no information about qu7 , as discussed in [KM12], but qu7
alone does not give any information about hGµ puq, and we need to understand
how hGµ puq depends on the qv7 ’s that correspond to active constraints.
For its independent interest, we may ask the following question: For which
distributions µ are all the linear constraints that determine G7MQ active ? First,
we have the following proposition about polyhedral representations of convex
sets.
Proposition 1. Let ptu quPRd Ď R be positively homogeneous, i.e., tλu “ λtu , @λ ě
0, u P Rd and define the convex set G “ tx P Rd : xu, xy ď tu , @u P S d´1 u. As˝

sume that G ‰ H. Then, the following statements are equivalent:

(i) All the linear constraints that define G are active;
(ii) For all u P S d´1 , hG puq “ tu ;
(iii) The family ptu quPRd is subadditive, i.e., tu`v ď tu ` tv , @u, v P Rd .

As a consequence of this lemma, the upper quantiles qu7 , u P S d´1 , are completely determined by Gµ if and only if the family pqu7 quPRd is sublinear, i.e.,
subadditive and positively homogeneous.
Open question 1. For what distributions µ are the upper quantiles qu7 , u P Rd ,
sublinear, no matter the value of α P p0, 1q ?
A Gaussian distribution has sublinear upper quantiles, as a consequence of
the triangle inequality for symmetric positive semidefinite matrices. If µ is the
Gaussian distribution with centroidam and covariance matrix Σ, then for all
u P S d´1 , qu7 “ xu, my ` Φ´1 p1 ´ αq Σpu, uq, where Φ is the cumulative distribution function of the univariate standard a
Gaussian distribution. The triangle
inequality ensures that the map u P Rd ÞÑ Σpu, uq is sublinear, yielding sublinearity of pqu7 quPRd .
As a generalization of Gaussian distributions, and because they are known to
be rigid (see [LV07] for examples of this rigidity), we may ask if a log-concave
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

6

probability measure have sublinear upper quantiles.
Open question 2. Assume that µ is log-concave. Is it true that the upper
quantiles qu7 , u P Rd are sublinear, no matter the value of α P p0, 1q ?
Remark 1. The multidimensional quantile sets are convex sets. Thus, they
fail to capture the structure of complex probability measures, such as mixtures.
The floating body (also called convex floating body in the convex geometry literature, see [SW90]) is defined as an intersection of closed halfspaces, i.e., the
complement of the union of open halfspaces. Instead, one could think of an
prq
r-convex floating body, using the notion of r-convexity (see [ML93]): GFB “
¨
˛A
ď
prq
˝
B 1 pa, rq‚ and its empirical analog ĜFB can be defined simiaPRd :µpB 1 pa,rqqăα

prq

larly, by replacing µ with µn . When r “ 8, GFB “ GFB . An asymptotic analysis
prq
of ĜFB would require a different approach than ours, but seems to be relevant
in order to describe more complex probability measures. In [PL08], r-convexity
is exploited to estimate the support of probability distributions while relaxing
convexity and even connectivity assumptions. We leave this question for further
work.
The next result shows that unless µ has atoms, the level set Gµ is empty
when α is too large.
Theorem 1. Let α ą 1{2. Then, either Gµ is empty or it contains exactly one
point. In the latter case, i.e., if Gµ “ txu for some x P Rd , then x is an atom
of µ: µptxuq ą 0.
On the one hand, if µ has an atom x with µptxuq ą 1{2, then Dµ pxq ě
µptxuq ą 1{2, hence, Gµ ‰ H for α “ µptxuq ą 1{2. On the other hand, it is
known ([DG92], Lemma 6.3) that Gµ is always nonempty when α ě 1{pd ` 1q.
The following two examples show that very general probability measures µ can
satisfy Gµ ‰ H for large values of α ď 1{2, independent of the dimension d,
and yet have no atoms:

• If µ is centrally symmetric, i.e., satisfies µpx ` Aq “ µpx ´ Aq for all Borel
set A Ď Rd , where x is the center of symmetry of µ, then Dµ pxq ě 1{2,
hence, Gµ is nonempty for all α P r0, 1{2s.
• If µ is log-concave, then any closed halfspace H containing the centroid of
µ satisfies µpHq ě e´1 (see Lemma 5.12 in [LV07]). Hence, the depth of
the centroid of µ is at least e´1 , which implies that Gµ is non empty for
α as large as e´1 « .37.
3. Concentration of the empirical Tukey depth level sets
Consider the following assumptions, where we let ε, L, r, R be fixed positive
numbers satisfying ε ă r ď R
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

7

Assumption 1.
• For all u P S d´1 , the cumulative distribution function
Fu of xu, Xy is continuous on rqu7 ´ ε, qu7 ` εs.
• Fu pt1 q ´ Fu ptq ě Lpt1 ´ tq, for all u P S d´1 and all t, t1 P R with qu7 ´ ε ď
t ď t1 ď qu7 ` ε.
Assumption 2. There exists a P Rd such that Bpa, rq Ď Gµ Ď Bpa, Rq.

Assumption 1 ensures that qu5 “ qu7 for all u P S d´1 , hence, that G5MQ “ G7MQ
and that the cumulative distribution functions Fu are not too flat around their
quantiles qu5 “ qu7 .
By Lemma 1, Ĝ can also be written as the empirical upper multidimensional
p1 ´ αq-quantile set associated with X1 , . . . , Xn :
Ĝ “ tx P Rd : xu, xy ď q̂u7 , @u P S d´1 u,
(2)
!
)
where, for u P Rd , q̂u7 “ sup t P R : #ti “ 1, . . . , n : xu, Xi y ě tu ě nα

is the upper empirical p1 ´ αq-quantile of xu, X1 y, . . . , xu, Xny. For the sake of
notation, we will write q̂u instead of q̂u7 in the sequel.
As a consequence of Lemma 1, in order to show concentration of Ĝ around
Gµ , one can compare their polyhedral representations given by (2) and G7MQ ,
which are written in terms of linear constraints. This is essential in the proof
of our next theorem, which uses semi-infinite linear programming as one of its
main ingredients.
Next theorem asserts that if Assumptions 1 and 2 are both satisfied, then Ĝ
concentrates around Gµ at a parametric speed. In particular, that speed depends
on the dimension d only through multiplicative constants.
Theorem 2. Let µ satisfy Assumptions 1 and 2. Then, the random set Ĝ
satisfies the following deviation inequality:
„

?
2 2
Cx
P dH pĜ, Gµ q ą ?
ď Ae´L x {2`10 5pd`1qx ,
n
a
?
10 5pd ` 1q
R 1 ` ε{r
for all x ě 0 with
ď x ă ε n, where C “
and A “
L
r 1 ´ ε{r
e´250pd`1q .

Note that in Theorem 2, if n is not large enough, the domain for x will be
empty. The constants depend on d and the parameters ε, r, R, L. These parameters are hard to compute in practice, for a given distribution µ. However, we
give simple asymptotic consequences of Theorem 2 below.
First, a truncated version of Ĝ has its expected error converging to zero at
the speed n´1{2 :
Corollary 1. Define the random set
#
Ĝ X B 1 p0, log nq if Ĝ ‰ H
˚
Ĝ “
t0u otherwise.
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

8

Let µ satisfy Assumptions 1 and” 2 and assume,
ı in addition,
´
¯that |a| ď τ for some
˚
k
´k{2
τ ą 0. Then, for all k ą 0, E dH pĜ , Gµ q “ O n
. The multiplicative
constants in these asymptotic comparisons depend on d, r, R, ε, L, τ and k only.
Remark 2.
• In Corollary 1, the upper bounds are uniform on the class of
probability measures µ that satisfy both Assumptions 1 and 2 with |a| ď
τ . Hence, Corollary 1 gives an upper bound for the rate of the minimax
risk in estimation of Gµ on that class of probability measures, and this
rate is parametric. Note that the assumption |a| ď τ could be dropped
in Corollary 1, but then the multiplicative constants in the asymptotic
comparisons would also depend on a and we would loose uniformity of the
upper bounds.
• The threshold log n in the definition of G̃ is arbitrary and could be replaced
with any sequence that grows to infinity at most polynomially in n.
Define the maximal depth α˚µ of µ as max Dµ pxq. Consider the two following

assumptions:

xPRd

Assumption 3. The probability measure µ is absolutely continuous with respect
to the Lebesgue measure, its density f is continuous and positive everywhere and
there exist C ą 0 and ν ą d ´ 1 such that |f pxq| ď C p1 ` |x|q´ν , @x P Rd .
In the sequel, if µ has a density f with respect to the Lebesgue measure, we
call the support of µ the set of vectors x P Rd for which f pxq ą 0.
Assumption 4. The probability measure µ is absolutely continuous with respect
to the Lebesgue measure, its support is bounded and convex and its density is
uniformly continuous on its support.
Assumptions 3 and 4 are sufficient but not necessary for next corollary. However, they include a lot of useful distributions. For example, any log-concave
distribution in Rd with positive density satisfies Assumption 3: A log-concave
density is continous on its support and decays exponentially fast when |x| Ñ 8.
If µ has a density of the form f pxq “ hpxx, Σxyq, where Σ is a d ˆ d symmetric
positive definite matrix and h is a positive continuous function that satisfies
hptq ď Cp1 ` |t|q´ν for all t P R, with ν ą d ´ 1, then µ satisfies Assumption 3
as well. If µ is the uniform distribution on a compact, convex set in Rd , then it
satisfies Assumption 4.
Corollary 2. Let µ satisfy either Assumption 3 or Assumption
´
¯ 4. Suppose that
´1{2
˚
α P p0, αµ q, independently of n. Then, dH pĜ, Gµ q “ OP n
.

Remark 3.
• Corollary 2 shows that the rate of convergence of the empirical level sets is parametric.
• Surprisingly, if µ is the uniform distribution on a compact, convex set K
in Rd , the rate does not depend on the smoothness of the boundary of K.
This is paradoxical, since it is known that if α “ 1{n, Ĝ is the convex
hull of X1 , . . . , Xn , which converges to K at a rate that depends on the
smoothness of the boundary of K (see [BL88]). However, in [BL88]:
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

9

– α “ 1{n depends on n. In our work, α does not depend on n and
hence, the floating body GFB “ Gµ is bounded away from the boundary
of K, which attenuates the effect of its smoothness.
– Convergence is towards the support K itself, not towards the floating body of µ. When α “ 1{n, it is not clear whether the convergence
of the distance between the empirical and the population p1{nq-convex
bodies depends on the smoothness of the boundary of K. By the triangle inequality, dH pĜ, Kq ď dH pĜ, Gµ q`dH pGµ , Kq. The p1{nq-floating
body Gµ converges to K at a speed that depends on the smoothness of
the boundary of K [BL88, SW90], but to the best of our knowledge, it
is not known whether the speed of convergence of dH pĜ, Gµ q depends
on the smoothness of K too.
• [Kim00] obtained the parametric rate n´1{2 for general measures of statistical depth, under quite strong assumptions on µ which rule out many
important distributions, as compared to ours (e.g., compactly supported
densities). In addition, they do not compare Ĝ to Gµ directly, but to level
sets of Dµ with levels α ˘ M n´1{2 , for some M ą 0, leaving out a deterministic bias. Yet, we believe that they could achieve the same rate as
ours. However, unlike Theorem 2, their result is not informative about the
tail of the distribution of dH pĜ, Gµ q, because of implicit dependency of the
constant M on the probability level (see [Kim00], Theorem 1).
Computation of Ĝ is a hard problem. Its concentration around Gµ is a question of its own geometric and probabilistic interest, but it also has important
statistical implications. For instance, as we saw in Corollary 1, it provides a
benchmark for the minimax risk for estimation of Gµ based on an i.i.d. sample.
However, if Ĝ is too hard to compute, this does not have much of a practical
interest. Computation of the Tukey depth Dµn at a single point is equivalent to
the problem of finding a hemisphere that contains the largest number of points
positioned on the unit sphere, which is NP hard in high dimension [JP78]. However, in fixed dimension, some deterministic and random algorithms to compute
an approximate or exact value of the Tukey depth have been suggested (see
[RR96, RS98, DM16] and the references therein). For the actual computation
of the Tukey depth level sets relative to a point cloud in dimension 2, we refer to [MRR` 03]. These sets are polygons, hence, their computation reduces
to finding either their vertices or their faces. To our knowledge, there are no
algorithms to compute these sets exactly when d ě 3. Here, we define a random
approximation of Ĝ that can be computed exactly, yet in an exponential time
in d. Lemma 1 gives a representation of Ĝ through infinitely many linear constraints. By selecting a finite number of these constraints, using a collection of
unit vectors that are well spread on the unit sphere, one can obtain a suitable
approximation of Ĝ.
Our random approximation is obtained by sampling random vectors on the
(
unit sphere. If M is a positive integer, denote by G̃M “ x P Rd : xUj , xy ď q̂Uj , @j “ 1, . . . , M ,
where U1 , . . . , UM are i.i.d. uniform random variables on S d´1 , independent of
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

10

X1 , . . . , Xn . The following theorem shows that a certain choice of M leads to
an estimator that of Gµ that concentrates as fast as Ĝ.
Theorem 3. Let µ satisfy Assumptions 1 and 2 and assume that the quantiles
pqu7 quPRd are subadditive. Then, for all M ě 1, the random set G̃M satisfies the
following deviation inequality:

„
Cx ` 4R
?
P dH pG̃M , Gµ q ą
n
˙
ˆ
?
2 2
M
´L x {2`10 5pd`1qLx
d
ď Ae
` pd{2q log n ,
` 6 exp ´
2d8pd´1q{2 nd´1
a
?
for all real number x with 10 5pd ` 1q ď x ă ε n, where c11 , c12 and c13 are
positive constants that depend on d, r, R, ε, L and ρ only.
The explicit values of the constants can be easily derived from the proof.
Remark 4. In Theorem 3, we assume that the population quantiles are subadditive, which, by Proposition 1, ensures that they are completely characterized
by the knowledge of Gµ . How strong this assumption is is an open question (see
Open questions 1 and 2).
Theorem 3 yields the following asymptotic upper bound for a truncated version of G̃M , if M is chosen large enough.
Corollary 3. Define the random set G̃˚M as
#
G̃M X Bp0, log nq if G̃M ‰ H,
˚
ĜM “
t0u otherwise.
Let k ą 0. Recall the notation and assumptions of Theorem 3. If, in addition,
d ` k d´1
n
log n, G̃˚M satisfies
|a| ď τ for some τ ą 0, then for M ą 2d8pd´1q{2
2
”
ı
´
¯
E dH pG̃˚M , Gµ qk “ O n´k{2 . The multiplicative constants in this asymptotic
comparison depend on d, r, R, ε, L and k only.
In addition, the following stochastic upper bound holds under subadditivity
of the population quantiles and either Assumption 3 or Assumption 4 :
Corollary 4. Let α P p0, α˚µ q and µ satisfy either Assumption 3 or Assumption
` ? ˘
4. Then, if the quantiles pqu7 quPRd are subadditive, dH pG̃, Gµ q “ OP 1{ n .
4. Proofs

4.1. Preliminary lemmas in convex geometry and semi-infinite
linear programming
Lemma 2. Let K, L be two convex sets. Then, K Ď L ðñ hK puq ď
hL puq, @u P S d´1 . In particular, K is bounded if and only if the restriction
of its support function to the unit sphere is bounded.
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

11

Proof: The first part of the lemma follows from directly from the definition
of the support function. For the second part, note that the support function of
a ball centered at the origin with radius R ě 0 is constant, equal to R on the
unit sphere. Hence, hK puq ď R, @u P S d´1 ðñ K Ď Bp0, Rq, which proves
the second part of the lemma.

In the next two lemmas, we let φ : S d´1 Ñ R and K “ tx P Rd : xu, xy ď
tu , @u P S d´1 u.
Lemma 3. The set K is convex and compact.
Proof: If K is empty, then it is convex and compact. Assume that K is
nonempty. It is closed and convex, as the intersection of closed halfspaces. Let us
show that K is bounded, which will end the proof. Since hK is convex, it is continuous on the interior of its domain (the domain of hK is tu P Rd : hK puq ă 8u.
For all u P S d´1 , hK puq ď tu ă 8, yielding that hK is continuous on S d´1 . Since
S d´1 is compact, the restriction of hK on the sphere needs to be bounded. Hence,

by Lemma 2, K is bounded.
˝

Lemma 4. If φ is continuous and x P Rd , then x P K ðñ xu, xy ă φpuq, @u P
S d´1 .
˝

Proof: Let x P K. Then, B 1 px, ηq Ď K for some η ą 0. Let u P S d´1 . Then,
x ` ηu P K, yielding xu, x ` ηuy ď φpuq. Hence, xu, xy ď φpuq ´ η ă φpuq
and this has to be true for all u P S d´1 . Now, let x P Rd satisfying xu, xy ă
φpuq, @u P S d´1 . The map u P S d´1 ÞÑ φpuq ´ xu, xy is continuous and positive
on the compact S d´1 , hence, there exists η ą 0 such that for all u P S d´1 ,
˝

φpuq ´ xu, xy ě η. Then, it is easy to verify that B 1 px, ηq Ď K, yielding x P K.

When a convex set is defined through a collection of linear inequalities indexed by the unit sphere, the support function at a given unit u0 vector can be
interpreted as the value of a semi-infinite linear program. The following lemma
states that under a continuity assumption, u0 needs to lie in the convex cone
spanned by the constraints that are active at a point x˚ that is a solution of that
linear program. Note that when the number of linear constraints is infine, the
existence of active constraints is not granted, as the following example shows.
Let u0 P S d´1 and G “ tx P Rd : xu, xy ď 1, @u P S d´1 ztu0 u, xu0 , xy ď 2u.
Then, since it is also true that G “ B 1 p0, 1q, the value of the semi-infinite linear
program maxtxu0 , xy : x P Gu is 1, uniquely attained at x˚ “ u0 . Yet, no
constraint is active at x˚ .
Lemma 5. Let φ be a continuous function on S d´1 and let K “ tx P Rd :
˝

xu, xy ď φpuq, @u P S d´1 u. Assume that K ‰ H. For all u0 P S d´1 , there exists
x˚ P K such that hK pu0 q “ xu0 , x˚ y. Moreover, there exists I Ď S d´1 such that
• #I ď d,
• xu, x˚ y “ φpuq, @u P I,
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

• u0 “

ÿ

uPI

12

λu u, for some nonnegative numbers λu , u P I.

Proof: By Lemma 3, K is compact, which grants the existence of x˚ , since
K ‰ H. Let I ˚ “ tu P S d´1 : xu, x˚ y “ φpuqu be the set of active constraints at
x˚ and let us prove that I ˚ is not empty. The rest will follow using Theorem 2
in [LS07] (Slater’s condition is satisfied since we assume that K has nonempty
interior).
If I ˚ was empty, then
@u P S d´1 , xu, x˚ y ă φpuq.

(3)

Since the function u P S d´1 ÞÑ φpuq ´ xu, x˚ y is continuous and positive on the
compact S d´1 , there is a positive number η such that φpuq ´ xu, x˚ y ě η, @u P
S d´1 . Hence, for all u P S d´1
xu, x˚ ` ηu0 y “ xu, x˚ y ` ηxu, u0 y
ď φpuq ´ η ` ηxu, u0 y

ď φpuq ´ η ` η “ φpuq,

yielding that x˚ ` ηu0 P K. This contradicts the maximality of hK pu0 q, since
xu0 , x˚ ` ηu0 y ą xu0 , x˚ y “ hK pu0 q.

In the next two lemmas, for any map ζ : S d´1 Ñ R, we denote by Gζ “ tx P
R : xu, xy ď ζpuq, @u P S d´1 u
d

Lemma 6. Let φ and φ̂ be two continuous functions on S d´1 . Assume that Gφ
and Gφ̂ have nonempty interiors. Let R ą r ą 0 and assume that B 1 p0, rq Ď

Gφ Ď B 1 p0, Rq. Let η “ maxuPS d´1 |φ̂puq ´ φpuq|. If η ă r, then dH pGφ̂ , Gφ q ď
ηR 1 ` η{r
.
r 1 ´ η{r

Let u0 P S d´1 . By Lemma 5, there exist x P Gφ , x̂ P Gφ̂ , I, Iˆ Ď S d´1
with #I ď d, #Iˆ ď d, such that hGφ pu0 q “ xu0 , xy, hGφ̂ pu0 q “ xu0 , x̂y, xu, xy “
ř
ř
φpuq, @u P I, xv, x̂y “ φ̂pvq, @v´ P ¯
Iˆ and u0 “ uPI λu u “ vPIˆ λ̂v v, for some
ě 0. Note that necessarily, for all u P I
nonnegative families pλu quPI , λ̂v
Proof:

vPIˆ

ˆ φpuq “ hG puq and φ̂pvq “ hG pvq. Then,
and v P I,
φ
φ̂
hGφ̂ pu0 q “ hGφ̂
“

ÿ

uPI

˜

ÿ

uPI

λu u

¸

λu xu, xy ` η

ď

ÿ

uPI

ÿ

uPI

λu hGφ̂ puq ď

ÿ

uPI

λu “ xu0 , xy ` η

λu φ̂puq ď

ÿ

uPI

ÿ

uPI

λu pφpuq ` ηq

λu “ hGφ pu0 q ` η

ÿ

λu .

uPI

(4)

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

13

In a similar fashion, we have that
hGφ pu0 q ď hGφ̂ pu0 q ` η

ÿ

(5)

λ̂v .

vPIˆ

By Lemma 2 and since B 1 p0, rq Ď Gφ Ď B 1 p0, Rq, r ď hGφ puq ď R, for all
ÿ
ÿ
ÿ
u P S d´1 , yielding R ě xu0 , xy “
λu xu, xy “
λu hGφ puq ě r
λu . Hence,
uPI

ÿ

uPI

uPI

R
λu ď
and by (4),
r
uPI

hGφ̂ pu0 q ď hGφ pu0 q `

ηR
.
r

(6)

On the other hand,
ÿ

vPIˆ

λ̂v xu, x̂y “ xu0 , x̂y “ hGφ̂ pu0 q ď hGφ pu0 q `

where the third inequality comes from (6). In addition,
ÿ

vPIˆ

λ̂v pφpvq ´ ηq ě

ÿ

vPIˆ

ηR
ηR
ďR`
,
r
r

ÿ

vPIˆ

λ̂v xu, x̂y “

λ̂v pr ´ ηq,yielding, together with (7),
ÿ

vPIˆ

λ̂v ď

(7)

ÿ

vPIˆ

λ̂v φ̂pvq ě

R 1 ` η{r
.
r 1 ´ η{r

(8)

Finally, (4), (5) and (8) yield
|hGφ pu0 q ´ hGφ̂ pu0 q| ď

R 1 ` η{r
.
r 1 ´ η{r

Since (9) is true for any arbitrary u0 P S d´1 , Lemma 6 is proven.
Definition 1. Let δ ą 0. A δ-net of the sphere S
that sup inf |u ´ v| ď δ.

d´1

is a subset N Ď S

(9)

d´1

such

uPS d´1 vPN

Lemma 7. Let δ P p0, 1q and N be a δ-net of S d´1 . Let φ and φ̂ : Rd Ñ R,
and assume that φ is sublinear. Let r ă R be two positive numbers and assume
that B 1 p0, rq Ď Gφ Ď B 1 p0, Rq. Let η “ maxuPN |φpuq ´ φ̂puq|. If η ă r, then
ηR 1 ` η{r
2Rδ
dH pGφ , GN
qď
`
.
φ̂
r 1 ´ η{r 1 ´ δ
Proof: Before starting the proof, let us recall the following important property for support functions. If K Ď B 1 p0, M q is a convex set, with M ą 0, then
its support function is M -Lipschitz.
d
Let GN
φ “ tx P R : xu, xy ď φpuq, @u P N u. By the triangle inequality,
N
N
dH pGφ , GN
q ď dH pGφ , GN
φ q ` dH pGφ , Gφ̂ q.
φ̂

(10)

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

14

By Proposition 1, φpuq “ hGφ puq, @u P S d´1 . Hence, φpuq ď R, @u P S d´1 .
˚
˚
Let x P GN
φ with x ‰ 0 and let u “ x{|x|. Then, |u ´ u | ď δ for some u P N ,
˚
˚
˚
yielding |x| “ xu, xy “ xu , xy ` xu ´ u , xy ď φpu q ` δ|x| ď R ` δ|x|. Hence,
R
1
and GN
is R{p1 ´ δq|x| ď
φ Ď B p0, R{p1 ´ δqq. This entails that hGN
φ
1´δ
d´1
N
Lipschitz. Now, let u0 P S
. On the one hand, since Gφ Ď Gφ , hGφ pu0 q ď
hG N
pu
q.
On
the
other
hand,
if
u˚ P N satisfies |u0 ´ u˚ | ď δ, then
0
φ
Rδ
Rδ
Rδ
ď φpu˚ q `
“ hGφ pu˚ q `
1´δ
1´δ
1´δ
Rδ
Rδ
˚
ď hGφ pu0 q ` R|u0 ´ u | `
ď hGφ pu0 q ` Rδ `
1´δ
1´δ
Rδp2 ´ δq
2Rδ
ď hGφ pu0 q `
,
“ hGφ pu0 q `
1´δ
1´δ

hG N
pu0 q ď hGN
pu˚ q `
φ
φ

where we used the fact that hGφ is R-Lipschitz. Therefore,
dH pGφ , GN
qď
φ̂

2Rδ
.
1´δ

(11)

N
N
Since B 1 p0, rq Ď Gφ Ď GN
φ , Gφ has nonempty interior. So does Gφ̂ , since

it is clear that B 1 p0, r ´ ηq Ď GN
, using the facts that φpuq ě r, @u P S d´1 ,
φ̂
by Lemma 2 and that η ă r. Hence, using similar arguments as in the proof of
Lemma 6,
ηR 1 ` η{r
N
.
(12)
dH pGN
φ , Gφ̂ q ď
r 1 ´ η{r
Thus, (10), (11) and (12) yield the desired result.



Lemma 8. Let K Ď Rd be a convex set with nonempty interior. Let A “
˝

tpu, tq P S d´1 ˆ R : ptu ` uK q X K ‰ Hu. Then, a pair pu, tq P S d´1 ˆ R is in A
if and only if there exists η ą 0 satisfying
˝

psu ` uK q X K ‰ H,
Proof:

@s P rt ´ η, t ` ηs.

(13)

Let pu, tq P S d´1 ˆ R.
˝

Assume that pu, tq P A. Then, there exists η ą 0 such that pu, sq P A, for
all s P rt ´ 2η, t ` 2ηs. Let s P rt ´ 2η, t ` 2ηs. Since pu, sq P A, the affine
˝

˝

hyperplane su ` uK intersects K. It actually needs to intersect K. Indeed, K
is also the relative interior of K, since K has nonempty interior. Hence, for the
affine hyperplane su ` uK to intersect K but not its interior, it has to be a
supporting hyperplane of K. This contradicts the fact that K has elements on
both sides of su ` uK .
˝
Now, assume that pu, tq P A for some η ą 0. Then, the affine hyperplane
˝

tu ` uK intersects the interior of K and let x P ptu ` uK q X K. Let η ą 0 be
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

15

˝

such that B 1 px, ηq Ď K. Let δ “ η{p1 ` |x|q and pv, sq P S d´1 ˆ R with both
|v ´ u| ď δ and |s ´ t| ď δ. Since x P xv, xyv ` v K , the affine hyperplane sv ` v K
intersects B 1 p0, xq if and only if |s ´ xv, xy| ď η, which holds by our choice of δ.

Lemma 9. Let k be a positive integer and K be a compact and convex set in
˝

Rk such that 0 P K. Let u P S k´1 and let pun qně1 a sequence of unit vectors in
Rk that converges to u. Let pxn qně1 be a sequence in Rk that converges to zero
and pUn qně1 be a sequence of isometries in Rk that converges to the identity.
Then, as n Ñ 0,
˘
˘
``
K
1. Volk´1 pK ` xn q X uK
n △pK X u˘n q ÝÑ 0;
˘
``
K
2. Volk´1 Un pKq X uK
n △pK X un q ÝÑ 0.
Proof: For u P S k´1 , set pK puq “ maxtλ ě 0 : λu P Ku. This is the (multi˝

plicative) inverse of the gauge of K. Since 0 P K, there exists m ą 0 such that
Bk1 p0, mq Ď K, yielding pK puq ě m for all u P S k´1 .
First statement of the lemma: For n ě 1, write xn “ λn un ` vn , with λn P R
and vn P uK
n and denote by Kn “ K ` λn un . Then, by the triangle inequality,
˘
˘
``
K
Volk´1 pK ` xn q X uK
n △pK X un q ď
˘
˘
``
K
Volk´1 pKn ` vn q X uK
n △pKn X un q
˘
˘
``
K
(14)
` Volk´1 pK ` λn un q X uK
n △pK X un q .
Since vn P uK
n , the first term on the right hand side of (14) is equal to
``
˘
˘
K
Volk´1 pKn X uK
n q ` vn △pKn X un q .

(15)

˘
`
K
It is easy to see that dH pKn X uK
n q ` vn , Kn X un ď |vn |, which is less than one
if n is large enough. Hence, using the same argument as in the proof of Lemma
1 in [Bru13], there is a positive constant
˘ on n such that
` C that does not depend
K
(15) is bounded from above by CdH pKn X uK
q
`
v
,
K
X
u
n
n
n
n . Therefore, the
first term of the right hand side of (14) goes to zero as n goes to infinity. Let
n ě 1 be large enough so λn ă m. Set αn “ pK pun q and βn “ pK p´un q.
Suppose that λn ě 0 (the case λn ă 0 would be handled similarly). Then, by
convexity of K,
αn
βn
pK ` λn un q Ď K Ď
pK ` λn un q .
αn ` λn
βn ´ λn

(16)

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

16

Since 0 P K, it is true that for all λ P R and v P S k´1 , pλKq X v K “ λpK X v K q.
Using this fact together with (16) yields
˘
`
K
pK ` λn un q X uK
n △pK X un q Ď
˙
˙
ˆˆ
αn ` λn
K
pK X uK
q
zpK
X
u
q
n
n
αn
ˆ
ˆ
˙˙
βn ´ λn
K
Y pK X uK
qz
pK
X
u
q
.
(17)
n
n
βn
Since 0 P K, the volume of the set in the right hand side of (17) is bounded
from above by
¸
˜ˆ
ˆ
˙k´1
˙k´1
βn ´ λn
αn ` λn
´1`
´ 1 Volk´1 pK X uK
n q,
αn
βn
which goes to zero as n goes to infinity, since K is bounded and αn and βn are
bounded away from zero (they are at not smaller than m). This ends the proof
of the first statement of the lemma.
Second statement of the lemma: Since the convex set K is bounded, its gauge
function is Lipschitz on S k´1 and it is bounded away from zero on S k´1 . Hence,
its (multiplicative) inverse pK is also Lipschitz on S k´1 . Let L be the corresponding Lipschitz constant. Let tn “ }Un ´ Ik }, where Ik is the identity map in Rk
and we define the norm of any linear map A : Rk Ñ Rk by }A} “ max |Apvq|.
vPS k´1

Then, since Un converges to the identity, tn goes to zero as n goes to infinity.
m
Define cn “
. Note that 0 ď cn ď 1. Then, let us show that for all
m ` Ltn
n ě 1,
cn K Ď Un pKq.
(18)

Let x P K and set y “ Un´1 pcn xq. If x “ 0, then y “ 0 yielding y P K by
assumption, which proves (18). If x ‰ 0, then y ‰ 0 and let v “ y{|y|. In order
to prove that y P K, it is enough to show that
|y| ď pK pvq.

(19)

Since Un is an isometry, |y| “ cn |x| and since x P K, |x| ď pK px{|x|q. Therefore,
|y| “ cn |x| ď cn pK px{|x|q “ cn pK pUn pvqq ď cn pK pvq ` cn L|Un pvq ´ v|
ď cn pK pvq ` cn Ltn “ pK pvq ` cn Ltn ´ p1 ´ cn qpK pvq ď pK pvq ` cn tn L ´ p1 ´ cn qm
“ pK pvq,

by definition of cn . This proves (19) and hence, (18). As a consequence, since
K
K
0 P K, cn pK X uK
n q “ pcn Kq X un Ď Un pKq X un , yielding
˘˘
`
` ´1
˘˘
`
`
K
K
ď Volk´1 pK X uK
Volk´1 pK X uK
n qz cn pK X un q
n qz Un pKq X un
ď p1 ´ c´pk´1q
qVolk´1 pK X uK
n
n q,

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

17

which goes to zero as n Ñ 8,``since K is bounded
and˘cn Ñ 1. In a similar
˘
zpK
X
uK
fashion, we prove that Volk´1 Un pKq X uK
n q also goes to zero as
n
n Ñ 8, which ends the proof of the second statement of the lemma.

Lemma 10. Let M be a positive integer and let U1 , . . . , UM be i.i.d. uniform random variables on S d´1 . Let δ P p0, 1s and let C be the event satisfied
when the collection tU1 , . . . , UM u is a δ-net of the sphere (see Definition 1).
˜
ˆ ˙pd´1q{2 ¸M
δ
ď
Then, the complement C A of C satisfies PrC A s ď #N 1 ´
4
˙˙
ˆ
ˆ
M δ d´1
1
.
6d exp ´
` d log
pd´1q{2
δ
2d8
Proof: Let N be a pδ{2q-net of S d´1 . By a simple volume argument, it is
possible to choose N satisfying #N ď p6{δqd , which we assume in the sequel. If C
is not satisfied, there exists u P S d´1 for which |u ´ Uj | ą δ, for all j “ 1, . . . , M .
Hence, if v P N is such that |u ´ v| ď δ{2, one has, for all j “ 1, . . . , M , by the
triangle inequality, |v ´ Uj | ě |u ´ Uj | ´ |u ´ v| ě δ ´ δ{2 ě δ{2. Therefore,
using the union bound and mutual independence of the Uj ’s,

„
M
ÿ „
δ
δ
.
P |v ´ U1 | ą
PrC A s ď P Dv P N , |v ´ Uj | ą , @j “ 1, . . . , M ď
2
2
vPN
(20)

„
δ
is the ratio of the surface area of a spherical
For any v P S d´1 , P |v ´ U1 | ď
2
cap of the unit sphere and the total surface area of the unit sphere. The height
of this cap is h “ δ 2 {8 ă 1. Then,
„

˙
ˆ
δ
d´1 1
1
P |v ´ U1 | ď
,
“ I2h´h2
,
(21)
2
2
2
2
şx a´1
t p1 ´ tqb´1 dt
, for x P r0, 1s and a, b ą 0. If b ď 1, one
where Ix pa, bq “ ş01
ta´1 p1 ´ tqb´1 dt
0
żx
żx
ż1
xa
a´1
b´1
a´1
has
t p1 ´ tq
dt ě
t
dt “
and a
ta´1 p1 ´ tqb´1 dt “ pa `
a
0
0
0
ż1
ż1
b
a`b
. Hence, Ix pa, bq ě
xa
bq
ta p1 ´ tqb´1 dt ď pa ` bq p1 ´ tqb´1 dt “
b
a
`
b
0
0

„
δ
and (21) yields, with x “ 2h´h2 , a “ d´1
ě
and
b
“
1{2,
that
P
|v
´
U
|
ď
1
2
2
1
p2h ´ h2 qpd´1q{2 . Since h ă 1, 2h ´ h2 ě h “ δ 2 {8, hence,
2d

„
δ d´1
δ
ě
P |v ´ U1 | ď
.
(22)
2
2d8pd´1q{2

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

18

Together with (22), (20) implies
PrC As ď #N

˜

ˆ
ˆ ˙pd´1q{2 ¸M
ˆ ˙˙
M δ d´1
δ
1
d
ď 6 exp ´
,
1´
` d log
pd´1q{2
4
δ
2d8

which ends the proof of Lemma 10.



4.2. Preliminary lemmas for empirical and population quantiles
Lemma 11. Let µ satisfy Assumption 1. Then, the map u P S d´1 ÞÑ qu7 is
continuous.
Proof:
proof.

For notation’s sake, we write qu instead of qu7 in the sequel of the

Step 1: Denote by Φpu, tq “ Prxu, Xy ď ts, u P S d´1 , t P R. (We first show that
Φ is continuous A “ pu, tq P S d´1 ˆ R : qu ´ ε ă t ă qu ` ε .
Let pu, tq P A and pup , tp qpě1 be a sequence in A that converges to pu, tq as p
goes to infinity. Let η be an arbitrary positive number. We show that if p is large
enough, then |Φpup , tp q ´ Φpu, tq| ď` 2η, which will
˘ prove our statement. First,
note that |Φpup , tp q ´ Φpu, tq| ď µ Hu,t △Hup ,tp . Let R ą 0 satisfy Pr|X| ą
Rs ď η. Then,
˘
˘
`
`
µ Hu,t △Hup ,tp ď µ Bp0, Rq X pHu,t △Hup ,tp q ` µpRd zBp0, Rqq
˘
`
ď µ Bp0, Rq X pHu,t △Hup ,tp q ` η.
It is easy to check that

˘
`
˘ `
Bp0, Rq X pHu,t △Hup ,tp q Ď Hu,tp `R|up ´u| zHu,t Y Hu,t zHu,tp ´R|up ´u| ,

which entails
˘
`
µ Bp0, Rq X pHu,t △Hup ,tp q
ď |Fu ptp ` R|up ´ u|q ´ Fu ptq| ` |Fu ptq ´ Fu ptp ´ R|up ´ u|q| .
(23)
Since pup , tp q ÝÝÝÑ pu, tq and qu ´ε ă t ă qu `ε, one has qu ´ε ď tp ´R|up ´u| ď
pÑ8

tp ` R|up ´ u| ď qu ` ε for all large `enough p. Hence, since Fu˘ is continuous on
rqu ´ ε, qu ` εs, (23) implies that µ Bp0, Rq X pHu,t △Hup ,tp q ď η if p is large
enough, which ends the the proof of the continuity of Φ on A.
Step 2: Let u P S d´1 and pup qpě1 be a sequence of unit vectors converging
to u as p goes to infinity. Let us show that qup converges to qu . If this was
not the case, there would be a positive number η and an increasing sequence
of positive integers ppk qkě1 satisfying |qupk ´ qu | ě η, @k ě 1. Let us assume
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

19

that qupk ě qu ` η for an infinite number of indices k ě 1. The case when
qupk ď qu ´ η for an infinite number of indices k ě 1 would be handled similarly.
For the sake of notation, we renumber the sequence and assume that for k ě 1,
quk ě qu ` η. Without loss of generality, assume that η ă ε. Hence, for all k ě 1,
1 ´ α “ Fuk pquk q ě Fuk pqu ` ηq

“ Fu pqu ` ηq ` Φpuk , qu ` ηq ´ Φpu, qu ` ηq
ě Fu pqu q ` Lη ` Φpuk , qu ` ηq ´ Φpu, qu ` ηq
“ 1 ´ α ` Lη ` Φpuk , qu ` ηq ´ Φpu, qu ` ηq.

(24)

The fact that Fv pqv q “ 1 ´ α, @v P S d´1 , is a consequence of the continuity and
strict monotony of Fv in a neighborhood of qv , for all v P S d´1 . Since η ă ε,
pu, qu `ηq P A, so by the first part of the proof, Φpuk , qu `ηq´Φpu, qu `ηq ÝÝÝÑ
kÑ8

0. Thus, by letting k grow to infinity in (24), we get that Lη ď 0, which is a
contradiction. Hence, we have proved that qup ÝÝÝÑ qu , which ends the proof.
pÑ8



Lemma 12. Let µ be a probability measure on Rd that satisfies either Assumption 3 or 4 and let K be its support. For u P S d´1 , let fu and Fu be, respectively,
the density and the cumulative distribution function of xu, Xy, where X is a random variable with distribution µ. Let A “ tpu, tq P S d´1 ˆ R : ptu ` uK q X K ‰
Hu. Define φpu, tq “ fu ptq and Φpu, tq “ Fu ptq, for all pu, tq P A. Then,
˝

• φ and Φ are continuous on A;
˝

• @pu, tq P A, φpu, tq ą 0 and 0 ă Φpu, tq ă 1.
Proof: Note Φpu, tq “

żt

´8

φpu, sq ds, for all pu, tq P A, where we set φpu, sq

to zero if pu, sq R A. Hence, by dominated convergence, continuity of φ will
automatically yield that of Φ. Let pu, tq P A and consider an arbitrary sequence
pun , tn qně1 of elements of A that converges to pu, tq.
Let µ satisfy Assumption 3. In this case, the second statement is trivial since f
is continuous and positive everywhere. Hence, we only prove the first statement.

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

20

Let ǫ ą 0 and R ą 0. For all n ě 1,
ˇż
ˇ
ż
ˇ
ˇ
ˇ
ˇ
|φpun , tn q ´ φpu, tq| “ ˇ
f ptu ` vq dv ˇ
f ptn un ` vq dv ´
ˇ uKn
ˇ
uK
ˇ
ˇ
ˇż
ˇ
ż
ˇ
ˇ
ˇ
ď ˇˇ
f
ptu
`
vq
dv
f
pt
u
`
vq
dv
´
n n
K
K
ˇ
vPun :
vPu :
ˇ |v|ďR
ˇ
|v|ďR
ż
ż
f ptu ` vq dv
f ptn un ` vq dv `
`
K
K
vPun :
|v|ąR

vPu :
|v|ąR

ˇ
ˇ
ˇż
ˇ
ż
ˇ
ˇ
ˇ
ďˇ
f ptu ` vq dv ˇˇ
f ptn un ` vq dv ´
K
vPuK
:
vPu
:
n
ˇ |v|ďR
ˇ
|v|ďR
ż
ż
p1 ` |v|q´ν dv.
p1 ` |v|q´ν dv `
`C
K
K
vPun :
|v|ąR

vPu :
|v|ąR

(25)

d
For n ě 1, let Un be an isometry in
ˇ R such that Un pun q “ u. Then, the first
ˇ
ˇż
ˇ
ˇ
ˇ
`
˘
´1
ˇ,
f
pt
u
`
U
pvqq
´
f
ptu
`
vq
dv
term in (25) can also be written as ˇˇ
n
n
n
K
ˇ
vPu :
ˇ |v|ďR
ˇ
which converges to zero by dominated convergence. Hence, for large n, the first
term in (25) is smaller than ǫ.
Using polar coordinates,
both the second and third terms in (25) can be
ż

rewritten as C 1

8

R

xd´2 p1 ` xq´ν dx, for some positive constant C 1 that does

not depend on n or R. Hence, both the second and third terms in (25) are
bounded from above by C 2 R´pν´d`1q , for some positive constant C 2 that does
not depend on R or n. Hence, if R was chosen large enough, both these terms
are smaller than ǫ. Finally, we have proved that φpun , tn q Ñ φpu, tq, as n Ñ 8.

Let µ satisfy Assumption 4. Let ǫ ą 0. For n ě 1, write
ż
|φpun , tn q ´ φpu, tq| ď
|f ptn un ` vq ´ f ptu ` vq| dv
uK
n

ˇż
ˇ
ż
ˇ
ˇ
ˇ
ˇ
`ˇ
f ptu ` vq dv ´
f ptu ` vq dv ˇ .
ˇ uKn
ˇ
uK

(26)

K
Let Bn “ tv P uK
n : tn un ` v P Ku and Dn “ tv P un : tu ` v P Ku. The first integral in (26) can be decomposed as
ż
|f ptn un ` vq ´ f ptu ` vq| dv
Bn XDn
ż
|f ptn un ` vq ´ f ptu ` vq| dv.
(27)
`
Bn △Dn

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

21

Recall that f is uniformly continuous on K and Vold´1 pBn X Dn q is bounded
uniformly in n, by boundedness of K. Hence, if n is large enough, the first
integral in (27) is smaller than ǫ. For the second integral, since f is uniformly
continuous on the bounded set K and vanishes everywhere else, it is bounded
and the integral is bounded from above by psupK f qVold´1 pBn △Dn q. The latter
converges to zero as n goes to infinity, thanks to Lemma 9. Hence, it becomes
smaller than ǫ if n is large enough, so the first term in (26) is at most 2ε for large
values of n. For n ě 1, let Un be an isometry in Rd such that Un pun q “ u and
such that Un converges to the identity, as n goes to infinity. Then, the second
term in the right hand side of (26) can be written as
ˇż
ˇ
ˇ
`
˘ ˇ
´1
ˇ
ˇ.
f
ptu
`
U
pvqq
´
f
ptu
`
vq
dv
(28)
n
ˇ
ˇ
uK

`
˘
Let Ku “ pK ´ tuq X uK and Kun “ Un´1 pK ´ tuq X uK . Since the integrand
pnq
vanishes outside of Ku Y Ku , the integral inside the absolute value in (28) can
be decomposed as the sum of two integrals: One on Ku X Kun and the other on
Ku △Kun . Since Un converges to the identity as n goes to infinity, Un´1 pvq Ñ v as
n Ñ 8, for all v P Rd . Since f is uniformly continuous on K and K is bounded,
f is bounded. Hence, by dominated convergence, uniform continuity of f on K
together with the fact that Vold´1 pKu X Kun q is bounded uniformly in n implies
that the first term goes to zero as n Ñ 8. Since f pxq “ 0 for x R K, f is
bounded on Rd . Hence, by Lemma 9, the second term goes to zero as n Ñ 8,
since Un converges to the identity. This ends the proof of the first statement of
the lemma.
For the second statement, first note that K needs to have a nonempty interior.
Otherwise, since it is convex, it would be included in a hyperplane, i.e., there
would exist u P S d´1 and t P R such that xu, xy “ t, @x P K. Hence, xu, Xy “ t
almost surely, which contradicts the fact that X has a density with respect to
˝

the Lebesgue measure in Rd . Let pu, tq P A. By Lemma 8, there exists η ą 0 such
˝

that both pt ` ηqu ` uK and pt ´ ηqu ` uK intersect K. Hence, by convexity of
˝

˝

K, psu ` uK q X K ‰ H, yielding that the pd ´ 1q-dimensional Lebesgue measure
of psu ` uK q X K needs to be positive, for all s P rt ´ η{2, t ` η{2s. Therefore,
fu is positive on this interval, yielding φpu, tq ą 0 and 0 ă Φpu, tq ă 1.


Lemma 13. Let µ be a probability measure on Rd that satisfies either Assumption 3 or 4 and let X be a random variable with distribution µ. Denote by Fu
the cumulative distribution function of xu, Xy. Let β P p0, 1q. For u P S d´1 , let
qu be the β-quantile of xu, Xy, defined as in Lemma 11 (with β “ 1 ´ α). Then,
• For all u P S d´1 , qu is the unique real number t that satisfies Fu ptq “ β;
• The map u P S d´1 ÞÑ qu is continuous.

Proof: Let K be the support of µ and let A “ tpu, tq P S d´1 ˆ R : ptu ` uK q X
K ‰ Hu.
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

22

Let u P S d´1 . Since µ is absolutely continuous with respect to the Lebesgue
measure, so is the distribution of xu, Xy. Hence, Fu is continuous on R, which
yields that Fu pqu q “ β. In addition, if fu is the density of xu, Xy, then fu is
positive in a neighborhood of qu . Indeed, since K is convex, the support of
fu is an interval. Since Fu pqu q “ β P p0, 1q and Fu is continuous, there is a
neighborhood of qu on which Fu ptq P p0, 1q, i.e., there is a neighborhood of qu
that is included in the support of fu . In particular, Fu is strictly increasing on
this neighborhood, which shows the uniqueness of qu .
Let u P S d´1 and let pun qně1 be an arbitrary sequence of unit vectors that
converges to u. Suppose that qun does not converge to qu . Then, there exists
η ą 0 and a subsequence of un (renamed un after renumbering) such that
|qun ´ qu | ě η, for all n ě 1. Assume that for an infinite number of indices n,
qun ě qu ` η. The case when qun ď qu ´ η for an infinite number of indices
n would be handled similarly. Thus, up to renumbering the sequence again,
assume that qun ě qu ` η, for all n ě 1. By a similar argument as in the end of
˝

the proof of Lemma 12, for all pu, tq P A, pu, tq P A if and only if 0 ă Fu ptq ă 1.
˝

˝

Hence, pu, qu q P A. Hence, there exists ξ ą 0 such that pv, tq P A for all v P S d´1
and t P R with |v ´ u| ď ξ and |qu ´ t| ď ξ. By Lemma 12, since φ is continuous
˝

and positive on A, there is a positive constant c such that φpv, tq ě c ą 0 for all
pv, tq P S d´1 ˆ R with |v ´ u| ď ξ and |qu ´ t| ď ξ. Assume that ξ ď η, without
loss of generality. Then,
β “ Fun pqun q “ Φpun , qun q ě Φpun , qu ` ηq ě Φpun , qu ` ξq “ Φpun , qu q `
ě Φpun , qu q ` cξ Ñ β ` cξ,

żξ

φpun , tq dt

0

as n goes to infinity. This is a contradiction, since β ` cξ ą β. Hence, qun needs

to converge to qu as n Ñ 8 and Lemma 13 is proven.
Lemma
14. Let µ satisfy Assumption 1. Then, for all n ě 1 and z P R with
?
10 5pd`1q
?
ď z ă ε,
L n
P

„

sup |q̂u ´

uPS d´1

qu7 |



´
a
? ¯
ď z ě 1 ´ A exp ´L2 z 2 n{2 ` 10 5pd ` 1qLz n ,

where A “ e´250pd`1q .
Proof:
Let C0 “ tpu, tq P S d´1 ˆ R : qu7 ´ ε ď t ď qu7 ` εu and Cr0 “
tpu, tq P C0 : u P Qd´1 ˆ Q, t P Qu. Denote by H0 “ tHu,t : pu, tq P C0 u and
r 0 “ tHu,t : pu, tq P Cr0 u.
H

Step 1:

We first show that

sup |µn pHq ´ µpHq| “ sup |µn pHq ´ µpHq| almost surely.

HPH0

(29)

r0
HPH

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

23

If pu, tq P S d´1 , denote by F̂u ptq “ µn pHu,t q, i.e., the empirical cumulative
distribution function of xu, Xy. Then,
sup |µn pHq ´ µpHq| “ sup |F̂u ptq ´ Fu ptq|

HPH0

pu,tqPC0

“ max

˜

Hence, it suffices to prove that

sup pF̂u ptq ´ Fu ptqq, sup pFu ptq ´ F̂u ptqq .

pu,tqPC0

pu,tqPC0

sup pF̂u ptq ´ Fu ptqq “

pu,tqPC0

sup pFu ptq ´ F̂u ptqq “

and that

pu,tqPC0

¸

sup pF̂u ptq ´ Fu ptqq

pu,tqPCr0

sup pFu ptq ´ F̂u ptqq. The first statement

pu,tqPCr0

follows from two facts. First, Cr0 is dense in C0 . Second, pu, tq ÞÑ F̂u ptq is lower
semicontinuous and pu, tq P C0 ÞÑ F̂u ptq is continuous on C0 , as proved in Step
1 of the proof of Lemma 11, yielding that pu, tq P C0 ÞÑ F̂u ptq ´ Fu ptq is lower
semicontinuous on C0 . For the second statement, note that for all u P S d´1 ,
F̂u ptq ´
continuity of Fu on the segment rqu7 ´ ε, qu7 ` εs implies that
sup
Fu ptq “

sup
7
7
`ε
´εătăqu
qu

7
7
`ε
´εătăqu
qu

Ĝu ptq ´ Gu ptq, where Gu ptq “ Prxu, Xy ě t and Ĝu ptq “

n
1 ÿ
1xu,Xi yět . Then, the same argument as above yields the second statement,
n i“1

and proves (29). In particular, the random variable

sup |F̂u ptq ´ Fu ptq| is

pu,tqPC0

measurable and the probability term in the statement of the lemma is well
defined.
Step 2: Let u P S d´1 . By definition of q̂u , the following holds for all t P R,
where, as we recall, H´u,´t is the halfspace H “ tx P Rd : xu, xy ě tu:
• If t ă q̂u , then µn pH´u,´t q ě α,
• If t ą q̂u , then µn pH´u,´t q ă α.

Assume that for some u P S d´1 , |q̂u ´ qu7 | ą z. Then, either q̂u ą qu7 ` z or
q̂u ă qu7 ´ z. If q̂u ą qu7 ` z, let H “ H´u,´pqu7 `zq P H0 . Then, µn pHq ě α.

Hence, by Assumption 1, µpHq “ Prxu, Xy ě qu7 ` zs “ 1 ´ Fu pqu7 ` zq ď
1 ´ Fu pqu7 q ´ Lz “ α ´ Lz, yielding that µn pHq ´ µpHq ě Lz. If q̂u ă qu7 ´ z a
similar reasoning yields |µpHq ´ µn pHq ě Lz for H “ H´u,´pqu7 ´zq P H0 . Hence,
using (29), it follows that
ﬀ
«
„

P

sup |q̂u ´ qu7 | ą z ď P

uPS d´1

sup |µn pHq ´ µpHq| ě Lz .

(30)

r0
HPH

r0 Ď H, it has VapnikNow, denote by S “ sup |µn pHq ´ µpHq|. Since H
r0
HPH

Chervonenkis dimension at most d ` 1. Moreover, it is a countable class of sets,
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

so Proposition 3.1 in [Bar16] yields ErSs ď
?
10 5pd`1q
?
,
2.5 in [Kol11], if Lz ě
n

?

10

5pd`1q
?
.
n

24

Therefore, by Theorem

«

ﬀ
a
10 5pd ` 1q
?
PrS ě Lzs ď P S ´ ErSs ě Lz ´
n
´
a
? ¯
ď A exp ´L2 z 2 n{2 ` 10 5pd ` 1qLz n ,

where A “ e´250pd`1q . Lemma 14 follows from (30) and (31).

(31)


Lemma 15. Let f1 , . . . , fn be n real valued continuous functions defined on a
topological space E and k P t1, . . . , nu. For x P E, denote by fpkq pxq the k-th
smaller number in the list f1 pxq, . . . , fn pxq. Then, fpkq is continuous.
Proof: Write fpkq pxq “ min max fj pxq, where Pk is the collection of all subsets
JPPk jPJ

of t1, . . . , nu of size k. Continuity of fpkq follows from continuity of the maximum
and minimum of finitely many continuous functions.

4.3. Proofs of the main theorems
Proof of Lemma 1: Let us first show that G5MQ “ GFB . Let x P G5MQ and
H P H satisfying µpHq ě 1 ´ α. Write H “ Hu,t , for some u P S d´1 and t P R.
Then, µpHq “ Prxu, Xy ď ts ě 1 ´ α, which yields t ě qu5 . Since x P G5MQ ,
xu, xy ď qu5 and, hence, x P H. Therefore, G5MQ Ď GFB . Now, let x P GFB and
u P S d´1 . Let H “ Hu,qu5 . By definition of qu5 and since Fu is right continuous,
µpHq “ Fu pqu5 q ě 1 ´ α, so x P H. Hence, x P G5MQ and thus, GFB Ď G5MQ . This
ends the proof of the equality G5MQ “ GFB .
Inclusion G5MQ Ď G7MQ follows from the inequalities qu5 ď qu7 , for all u P S d´1 .
Now, let us prove that G7MQ “ Gµ . For x P G7MQ , we show that Dµ pxq ě α,
i.e., that any closed halfspace H containing x needs to satisfy µpHq ě α. Let
H be such a halfspace and write H “ Hu,t for some u P S d´1 and t P R. Then,
7
7
xu, xy ď t,so x´u, xy ě ´t. Since x P G7MQ , x´u, xy ď q´u
, hence, ´t ď q´u
.
Therefore,
µpHq “ Prxu, Xy ď ts “ 1 ´ Prxu, Xy ą ts “ 1 ´ Prx´u, Xy ă ´ts
7
ě 1 ´ Prx´u, Xy ă q´u
s ě 1 ´ p1 ´ αq “ α.

Thus, x P Gµ , and hence, G7MQ Ď Gµ . Now, let x P Gµ and u P S d´1 . Since
x P H´u,x´u,xy and Dµ pxq ě α, µpH´u,x´u,xy q ě α, i.e., Prx´u, Xy ď x´u, xys ě
α. Hence, Prxu, Xy ă xu, xys ď 1 ´ α,which, by definition of qu7 , implies that

xu, xy ď qu7 . So, x P G7MQ . Therefore, G7MQ “ Gµ .

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

25

Proof of Proposition 1
• (i) ñ (ii): Assume that all the constraints are active and let u P S d´1 .
First, by definition of the support function, hG puq ď tu . Second, since
the constraint corresponding to u is active, there exists x˚ P G such that
xu, x˚ y “ tu , yielding tu ď hG puq, hence, tu “ hG puq.
• (ii) ñ (i): Let u P S d´1 . By Lemma 3, G is compact, yielding the existence
of x˚ P G satisfying hG puq “ xu, x˚ y. Hence, the constraint corresponding
to u is active.
• (ii) ñ (iii) is a direct consequence of the sublinearity of support functions.
• (iii) ñ (ii): Assume that the family ptu quPRd is sublinear and let u0 P S d´1 .
Since u P Rd ÞÑ tu is sublinear and positively homogeneous, it is convex.
˝

Hence, it is continuous on the interior of its domain, here, Rd . Since G ‰
H, Lemma 5 yields the existence of x˚ P G satisfying hG pu0 q “ xu0 , x˚ y
řd
and of u1 , . . . , ud P S d´1 , λ1 , . . . , λd ě 0 satisfying u0 “ i“1 λi ui and, for
d
ÿ
i “ 1, . . . , d, xui , x˚ y “ tui . Hence, hG pu0 q “ xu0 , x˚ y “
λi xui , x˚ y “
i“1

d
ÿ

i“1

λi tui ě tu0 , by positive homogeneity and sublinearity of v ÞÑ tv . Since,

in addition, hG pu0 q ď tu0 by definition of the support function, hG pu0 q ď
tu0 .

Proof of Theorem 1 Let α be greater than 1{2 and assume that Gµ is
nonempty. Let x P Gµ : We prove that µptxuq ą 0.
Let E be an affine hyperplane passing through x. Let H1 and H2 be the two
distinct halfspaces whose common boundary is E. Since x P Gµ , Dµ pxq ě α.
In particular, since both H1 and H2 contain x, µpHj q ě α, j “ 1, 2. Hence,
1 ě µpH1 Y H2 q “ µpH1 q ` µpH2 q ´ µpEq ě 2α ´ µpEq, which implies that
µpEq ě 2α ´ 1.
Let k P t1, . . . , du. Assume it is known that any affine subspace E of dimension
k, containing x, satisfies µpEq ě 2α´1. Let F be an affine subspace of dimension
k ´ 1, containing x. Let G be the linear subspace of vectors that are orthogonal
to F . Let p ě 2 be an integer and let u1 , . . . , up be unit vectors in G, such that
no two of them are collinear. For i “ 1, . . . , p, set Ei “ F č
` Rui “ tf ` λui :
f P F, λ P Ru. Then, for all I Ď t1, . . . , pu with #I ě 2,
Ei “ F and as a
iPI

consequence of the inclusion-exclusion principle,
¸
˜ p
ˆ ˙
p
p
ÿ
ÿ
ď
j p
p´1q
µpF q ě pp2α ´ 1q ´ pp ´ 1qµpF q,
µpEi q ´
Ei “
1ěµ
j
j“2
i“1
i“1

p
1
p2α ´ 1q ´
. Since p is an arbitrary integer, we can
p´1
p´1
let it go to infinity and we get µpF q ě 2α ´ 1.

yielding µpF q ě

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

26

By induction, this proves that µptxuq ě 2α ´ 1 ą 0 and this must hold for
all x P Gµ . Since Gµ is convex, it cannot contain more than one point. Indeed,
if x, y P Gµ , then rx, ys Ď Gµ , yielding µptzuq ě 2α ´ 1, for all z P rx, ys. Hence,
if x ‰ y, then µprx, ysq “ 8, which is impossible.

Proof of Theorem 2 Without loss of generality, let us assume that a “ 0 in
Assumption 2: translating the measure µ and the sample points does not affect
the Haussdorf distance between Gµ and Ĝ. For the sake of notation, we write
d´1
qu “ qu5 “ qu7 for
a all u P S ?.
Let z P r10 5pd ` 1q{pL nq, εq and let the event A “ t|q̂u ´ qu | ď z, @u P
d´1
S
u hold. Since B 1 p0, rq Ď Gµ , it is true that qu ě r, @u P S d´1 . Hence, for all
u P S d´1 , q̂u ě qu ´ z ě r ´ ε ą 0, yielding that B 1 p0, r ´ εq Ď Ĝ, hence, that
Ĝ has a nonempty interior. So does Gµ , since it contains B 1 p0, rq.
By Lemmas 11 and 15, the maps u ÞÑ qu and u ÞÑ q̂u are continuous. Indeed,
q̂u is the rnp1 ´ αq ` 1s-th order function of xu, X1 y, . . . , xu, Xn y. Note that
1`t
is nondecreasing. Thus, by Lemma 6, dH pĜ, Gµ q ď
the map t P r0, 1q ÞÑ
1´t
zR 1 ` z{r
R 1 ` ε{r
ď Cz, where C “
. Hence, if AA stands for the complement
r 1 ´ z{r
r 1 ´ ε{r
of the event A, then
“ ‰
PrdH pĜ, Gµ q ą Czs ď P AA .
(32)

a
?
?
10 5pd ` 1q
ď x ă ε n.
Write z “ x{ n, for some real number x satisfying
L
By Lemma 14,
´
¯
a
“ ‰
P AA ď A exp ´L2 x2 {2 ` 10 5pd ` 1qLx .
(33)
The desired result is a consequence of (32) and (33).



Proof of Corollary 1 The proof is based on a consequence of Funini’s theorem which ensures that if Z is a nonnegative random variable, then
ż8
ErZ k s “ k
tk´1 P rZ ą ts dt,
(34)
0

for all positive number k.
First, note that for all k ą 0,
”
ı
”
ı
”
ı
E dH pĜ˚ , Gµ qk “ E dH pĜ˚ , Gµ q1Ĝ‰H ` E dH pĜ˚ , Gµ qk 1Ĝ“H ,

(35)

where 1 stands for the indicator function.
˚
By definition of
ı second term in the right hand side of (35) is equal
” Ĝ , the

to dH pt0u, Gµ qk P Ĝ “ H . First, it is clear that dH pt0u, Gµ q ď |a| ` R ď τ ` R.

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

27

ı
”
“ ‰
Second, as we saw in the proof of Theorem 2, P Ĝ “ H ď P AA where we

set z “ ε{2. Hence, by (33),
”
ı
´
¯
E dH pĜ˚ , Gµ qk 1Ĝ“H “ O n´k{2 ,

(36)

with multiplicative constants that depend on d, ε, R, L and τ only.
For the first term of (35), note that if Ĝ ‰ H, then, since Ĝ˚ Ď B 1 p0, log nq
and Gµ Ď B 1 pa, Rq, dH pĜ˚ , Gµ q ď |a| ` log n ` R ď τ ` log n ` R. Denote by
B “ τ ` log n ` R. Then, if we set Z “ dH pĜ, Gµ q,
”
ı
“
‰
E dH pĜ˚ , Gµ qk 1Ĝ‰H ď E Z k 1ZďB .
(37)

In the following, we set k “ 1. General values of k would be handled similarly,
using (34). Using (37) and (34) with k “ 1,
˚

ErdH pĜ , Gµ q1Ĝ‰H s ď

żB
0

”
ı
P dH pĜ, Gµ q ą t dt.
10C

a
5pd ` 1q
?
, where we
L n

Split the integral in three integrals. First, from 0 to
a
10C 5pd ` 1q
?
bound the integrand by 1. Second, from
to ε, where we use the
L n
bound provided by Theorem 2. Third, in the remaining interval, where, using
monotonicity,?we bound the integrand using the upper bound given in Theorem
2 with x “ ε n. Then,
´
¯
ErdH pĜ˚ , Gµ q1Ĝ‰H s “ O n´1{2 ,
(38)
with multiplicative constants that depend on d, ε, r, R and L only. Together with
(36), (38) yields the desired result.

Proof of Corollary 2 It is enough to prove that if µ satisfies either Assumption 3 or 4, then it satisfies both Assumptions 1 and 2, for some values of ε, L, r
and R. Hence, Theorem 2 will apply and yield the desired result.
Let X be a random variable in Rd with probability measure µ. If u P S d´1 ,
denote by fu the density of xu, Xy and by Fu its cumulative
distribution funcż
tion. For u P S d´1 and t P R, let φpu, tq “ fu ptq “

uK

f ptu ` vq dv, where the

integral is evaluated with respect to the pd ´ 1q-dimensional Lebesgue measure
on uK .
Let K be the support of µ and let A “ tpu, tq P S d´1 ˆR : ptu`uKqXK ‰ Hu.
˝

Note that A is included in the support of φ. Thus, by Lemma 12, φ is continuous
˝

on A.
From now on, we assume that µ satisfies either Assumption 3 or 4. For u P
S d´1 , since Fu is continuous, qu7 “ qu5 : Denote this value by qu . Let αmax “
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

28

max Dµ pxq. This quantity is well defined, since Dµ is upper semicontinuous and
xPRd

quasi-concave (see [Mas04]). Let T P Rd satisfy Dµ pT q “ αmax . Since µ has a
connected support and is absolutely continuous with respect to the Lebesgue
measure, such a point exists and is unique (see [Mas04] or Prop. 3.5 in [MT94]).
Let α1 and α2 be positive numbers such that α1 ă α ă α2 ă αmax . For u P S d´1 ,
p1q
p2q
denote by qu the p1 ´ α1 q-quantile of Fu and by qu the p1 ´ α2 q-quantile of
p1q
p2q
Fu . By Lemma 13, qu , qu and qu are continuous functions of u. In addition,
for all u P S d´1 , xu, T y ă qup2q ă qu ă qup1q , by definition of the quantiles and by
the first part of Lemma 13. Hence, since S d´1 is compact, there exist positive
numbers r, R and ε with ε ă r ă R and such that for all u P S d´1 ,
xu, T y ` r ď qup1q ď qu ´ ε ď qu ` ε ď qup2q ď xu, T y ` R.

(39)

In particular, the first and last inclusions of (39) imply that BpT, rq Ď Gµ Ď
BpT, Rq. Hence, µ satisfies Assumption 2. In addition, by a similar argument as
in the proof of Lemma 13, the intermediate inclusions show that the compact
set B “ tpu, tq : u P S d´1 , qu ´ ε ď t ď qu ` εu is included in the interior of A.
Hence, by Lemma 12, φ is continuous on and positive on B, thus, it is bounded
from below by a positive constant L on B, yielding Fu pt1 q ´ Fu ptq ě Lpt1 ´ tq,
for all u P S d´1 and t, t1 P R such that qu ´ ε ď t ď t1 ď qu ` ε. This, together
with continuity of Fu , for all u P S d´1 , shows that µ satisfies Assumption 1,

which finally ends the proof of Corollary 2.
a
?
10 5pd ` 1q
?
Proof of Theorem 3: Let M ě 1,
ď z ă ε and δ “ 1{ n. For
L n
simplicity, we denote by qj “ qUj and q̂j “ q̂Uj , for j “ 1, . . . , M . Define the
(
events A “ t|q̂j ´qj | ď z, @j “ 1, . . . , M u and C “ tU1 , . . . , UM u is a δ-net of S d´1 .
Let both A and C hold. Then, by Lemma 7, dH pG̃M , Gµ q ď Cz ` 4Rδ, where
R 1 ` ε{r
C“
. Therefore, by Lemmas 14 and 10,
r 1 ´ ε{r
„

4R
?
P dH pG̃M , Gµ q ą Cz `
n
˙
ˆ
?
2 2
M
`
pd{2q
log
n
,
ď Ae´L x {2`10 5pd`1qLx ` 6d exp ´
2d8pd´1q{2 nd´1
a
?
10 5pd ` 1q
for any x P R satisfying

ď x ă ε n.
L
References
[ACG94] M. A. Arcones, Z. Chen, and E. Giné. Estimators related to U processes with applications to multivariate medians: asymptotic normality. Ann. Statist., 22(3):1460–1477, 1994.

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

29

[Bar16] Y. Baraud. Bounding the expectation of the supremum of an empirical process over a (weak) VC-major class. Electron. J. Stat.,
10(2):1709–1728, 2016.
[BL88] I. Bárány and D. G. Larman. Convex bodies, economic cap coverings, random polytopes. Mathematika, 35(2):274–291, 1988.
[Bru13] V.-E. Brunel. Adaptive estimation of convex polytopes and convex
sets from noisy data. Electron. J. Stat., 7:1301–1327, 2013.
[Bru14] V.-E. Brunel. A universal deviation inequality for random polytopes.
submitted, arXiv:1311.2902, 2014.
[Cha96] P. Chaudhuri. On a geometric notion of quantiles for multivariate
data. J. Amer. Statist. Assoc., 91(434):862–872, 1996.
[DG92] D. L. Donoho and M. Gasko. Breakdown properties of location
estimates based on halfspace depth and projected outlyingness. Ann.
Statist., 20(4):1803–1827, 1992.
[DGC11] S. Dutta, A. K. Ghosh, and P. Chaudhuri. Some intriguing properties of Tukey’s half-space depth. Bernoulli, 17(4):1420–1434, 2011.
[DM16] R. Dyckerhoff and P. Mozharovskyi. Exact computation of the halfspace depth. Comput. Statist. Data Anal., 98:19–30, 2016.
[Fre13] D. Fresen. A multivariate Gnedenko law of large numbers. Ann.
Probab., 41(5):3051–3080, 2013.
[GC05a] A. K. Ghosh and P. Chaudhuri. On data depth and distribution-free
discriminant analysis using separating surfaces. Bernoulli, 11(1):1–
27, 2005.
[GC05b] A. K. Ghosh and P. Chaudhuri. On maximum depth and related
classifiers. Scand. J. Statist., 32(2):327–350, 2005.
[Gun12] A. Guntuboyina. Optimal rates of convergence for convex set estimation from support functions. Ann. Statist., 40(1):385–411, 2012.
[He16] Y. He. Multivariate extreme value statistics for risk assessment.
PhD thesis, 2016.
[HPvS10] M. Hallin, D. Paindaveine, and M. ˇ Siman. Multivariate quantiles
and multiple-output regression quantiles: from L1 optimization to
halfspace depth. Ann. Statist., 38(2):635–669, 2010.
[HW97] X. He and G. Wang. Convergence of depth contours for multivariate
datasets. Ann. Statist., 25(2):495–504, 1997.
[JP78] D. S. Johnson and F. P. Preparata. The densest hemisphere problem. Theoret. Comput. Sci., 6(1):93–107, 1978.
[Kim00] J. Kim. Rate of convergence of depth contours: with application
to a multivariate metrically trimmed mean. Statist. Probab. Lett.,
49(4):393–400, 2000.
[KM12] L. Kong and I. Mizera. Quantile tomography: using quantiles with
multivariate data. Statist. Sinica, 22(4):1589–1610, 2012.
[Kol11] V. Koltchinskii. Oracle inequalities in empirical risk minimization
and sparse recovery problems, volume 2033 of Lecture Notes in Mathematics. Springer, Heidelberg, 2011. Lectures from the 38th Probability Summer School held in Saint-Flour, 2008, École d’Été de Probabilités de Saint-Flour. [Saint-Flour Probability Summer School].
imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

Brunel, V.-E./Tukey depth level sets

30

[LPS99] R. Y. Liu, J. M. Parelius, and K. Singh. Multivariate analysis
by data depth: descriptive statistics, graphics and inference. Ann.
Statist., 27(3):783–858, 1999. With discussion and a rejoinder by
Liu and Singh.
[LS93] R. Y. Liu and K. Singh. A quality index based on data depth and
multivariate rank tests. J. Amer. Statist. Assoc., 88(421):252–260,
1993.
[LS07] R. Lòpez and G. Still. Semi-infinite programming. European J.
Oper. Res., 180(2):491–518, 2007.
[LV07] L. Lovász and S. Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures Algorithms,
30(3):307–358, 2007.
[Mas04] J.-C. Massé. Asymptotics for the Tukey depth process, with an
application to a multivariate trimmed mean. Bernoulli, 10(3):397–
419, 2004.
[ML93] P. Mani-Levitska. Characterizations of convex sets. pages 19–41,
1993.
[MRR` 03] K. Miller, S. Ramaswami, P. Rousseeuw, J. A. Sellarès, D. Souvaine,
I. Streinu, and A. Struyf. Efficient computation of location depth
contours by methods of computational geometry. Stat. Comput.,
13(2):153–162, 2003.
[MT94] J.-C. Massé and R. Theodorescu. Halfplane trimming for bivariate
distributions. J. Multivariate Anal., 48(2):188–202, 1994.
[PL08] B. Pateiro-Lopez. Set estimation under convexity type restrictions.
PhD Thesis, 2008.
[RR96] P. J. Rousseeuw and I. Ruts. Computing depth contours of bivariate
point clouds. Computational statistics and data analysis, 23:153–
168, 1996.
[RR99] P. J. Rousseeuw and I. Ruts. The depth function of a population
distribution. Metrika, 49(3):213–244, 1999.
[RS98] P. J. Rousseeuw and A. Struyf. Computing location depth and
regression depth in higher dimensions. Statistics and Computing,
8:193–203, 1998.
[SW90] C. Schtt and E. Werner. The convex floating body. Math. Scand,
66:275–290, 1990.
[Tuk75] J. W. Tukey. Mathematics and the picturing of data. pages 523–531,
1975.
[YS97] A. B. Yeh and K. Singh. Balanced confidence regions based on
Tukey’s depth and the bootstrap. J. Roy. Statist. Soc. Ser. B,
59(3):639–652, 1997.
[ZS00a] Y. Zuo and R. Serfling. General notions of statistical depth function.
Ann. Statist., 28(2):461–482, 2000.
[ZS00b] Y. Zuo and R. Serfling. Structural properties and convergence results for contours of sample statistical depth functions. Ann. Statist.,
28(2):483–499, 2000.

imsart-generic ver. 2011/11/15 file: TDLS_v2.tex date: February 10, 2017

