Methods in Estimation of Convex Sets

arXiv:1709.03137v1 [] 10 Sep 2017

Victor-Emmanuel Brunel
e-mail: vebrunel@mit.edu
Abstract:
In the framework of shape constrained estimation, we review methods
and works done in convex set estimation. Some methods are standard in
statistics, coming especially from the theory of empirical processes, but we
more geometric methods that are specific to convex set estimation. The
statistical problems that we review include density support estimation, estimation of the level sets of densities or depth functions, nonparametric regression, etc. We focus on the estimation of convex sets under the Nykodim
and the Hausdorff metrics, which require different techniques and, quite
surprisingly, lead to very different results, in particular in density support
estimation. Finally, we discuss computational issues in high dimension.
MSC 2010 subject classifications: Primary 62-02, 62G05.
Keywords and phrases: Convex body, Set estimation, Nykodim metric,
Hausdorff metric, Support function.

1. Preliminaries
1.1. Introduction
In nonparametric inference, the unknown object of interest cannot be described
in terms of a bounded number of parameters. Examples include density estimation, nonparametric and high dimensional regression, support estimation, etc.
Since the number of observations is only finite, it is necessary to make assumptions on the object of interest in order to make statistical inference possible.
Two types of assumptions are most common. First, smoothness assumptions: If
the unknown object is a function, one may assume that it is smooth in a certain
sense. If it is a set, a smoothness assumption may be imposed on its boundary.
Second, shape constraints, such as monotonicity, convexity, log-concavity, etc.
Smoothness is a quantitative condition, whereas a shape constraint is usually
qualitative. Smoothness classes of functions or sets depend on meta parameters,
such as the number of existing derivatives or upper bounds on some functional
norms. However, in statistical applications, these meta parameters are unlikely
to be known to the practitioner. Yet, statistical inference usually requires to
choose tuning parameters in a way that depends on them. One way to overcome this issue is to randomize the tuning parameters and apply a data driven
adaptive procedure (e.g., cross validation). However, such procedures are often
technical and computationally costly. On the other hand, shape constraints usually do not introduce extra parameters: This makes them particularly attractive.
Many different shape constraints can be imposed on sets. For instance, [Tsy94,
KST95b, KST95a] consider boundary fragments, which are subgraphs of a positive function defined on a hypercube. Shape constraints on such sets directly
1

V.-E. Brunel/Estimation of Convex Sets

2

translate into shape constraints on their edge functions. For general sets, convexity is probably the most simple shape constraint, and yet it leads to a very
rich field in geometry. It has been extended to the notion of r-convexity, where
a closed set is r-convex if its complement is the union of open Euclidan balls
of radius r, r > 0 (see, e.g., [ML93] and [RC07, PL08] for set estimation under
r-convexity). Intuitively, convexity is the limit of r-convexity as r goes to ∞.
Such a shape constraint introduces one meta parameter r, which may not be
known a priori to the practitioner. Adaptation to r has been tackled, for instance, in [RCSN16]. In the present article, we only focus on convexity, which
has brought a lot of attention in the statistical literature. In addition to convexity, the following shape constraints are common:
• Rolling ball condition: A convex set G is said to satisfy the r-rolling ball
condition if, for all x on the boundary of G, there is a Euclidean ball B(a, r)
such that x ∈ B(a, r) ⊆ Ḡ, where Ḡ is the closure of G. An equivalent condition is that the complement of G has reach at least r [Thä08, Definition
11].
• Standardness: A convex set G is called ν-standard if for all x on its boundary, Vol (G ∩ B(x, ε)) ≥ νVol (B(x, ε)), for all ε > 0 small enough. This
roughly means that the set G does not have peaks.
For more discussion about the different assumptions in set estimation, we refer
to [Cue09].
Different models associated with the estimation of convex sets include density support estimation [KT93a, KST95b, KST95a, Bru16, Bru17b, Bru], density
level set estimation [Har87,Pol95,Tsy97], inverse problem in support estimation
[BKY], estimation of the support of a regression function [KT93b,Tsy94,Bru13],
estimation of the level sets of the Tukey depth [Bru17a], recovering support
functions [GKM06, Gun12], etc.
Before going more into the details, let us introduce the notation and the main
definitions.
1.2. Notation and Definitions
In the sequel, d is a positive integer, standing for the ambient dimension. For
a positive integer p, the closed p-dimensional Euclidean ball with center a ∈ Rp
and radius r ≥ 0 is denoted by Bp (a, r). If p = d, we may omit the subscript p.
The (p − 1)-dimensional unit sphere is denoted by Sp−1 and the volume of the
p-dimensional unit Euclidean ball is denoted by βp . The Euclidean norm in Rd
is denoted by ∥⋅∥, the Euclidean distance is ρ and we write ⟨⋅, ⋅⟩ for the canonical
dot product.
A convex body G ⊆ Rd is a compact and convex set with nonempty interior.
(1)
We denote by Kd the collection of all convex bodies and by Kd the collection
of all convex bodies included in B(0, 1). The support function hG of a convex
body G is defined as hG (u) = max{⟨u, x⟩ ∶ x ∈ G}, for all u ∈ Sd−1 : It is the
signed distance of tangent hyperplanes to the origin.

V.-E. Brunel/Estimation of Convex Sets

3

For any positive integer p, the p-dimensional volume of a measurable set
A ⊆ Rp is denoted by ∣A∣p . When p = d, we may omit the subscript.
The Nykodim distance between two measurable sets K, L ⊆ Rd is the volume of their symmetric difference: d△ (K, L) = ∣K △ L∣. The Hausdorff distance between any two sets K, L ⊆ Rd is defined as dH (K, L) = inf{ε ≥ 0 ∶ K ⊆
L + εB(0, 1), L ⊆ K + εB(0, 1)}.
The cardinality of a finite set A is denoted by #A.
When i.i.d. random points X1 , . . . , Xn ∈ Rd have a density f with respect
to the Lebesgue measure, we denote by Pf their joint distribution and by Ef
the corresponding expectation operator. When f is the uniform density on a
compact set G, we simply write PG and EG . The convex hull of X1 , . . . , Xn is
denoted by K̂n .
Remark 1. In this article, most, if not all, set-valued estimators are polytopes
that depend on a finite random sample. Nonetheless, in order to be consistent
with the literature, we reserve the name random polytope for K̂n only.
1.3. Outline
The main goal of this article is to present different techniques that are used
in estimation of convex sets. These techniques are essentially borrowed from
stochastic and convex geometry.
In Section 2, we review basic properties of random polytopes and connect
them to the problem of support estimation under the Nykodim metric. We
recall well known results on the covering number of classes of convex bodies
and show how these can be used in order to deviation inequalities in convex
support estimation. We also review extensions of these results to the estimation
of convex level sets and discuss other convex set estimation problems under the
Nykodim metric.
In Section 3, we give general insights on the estimation of convex bodies
through their support functions. In particular, we review important properties
related to support functions and convex bodies and show how they apply to the
estimation of convex sets under the Hausdorff metric.
Finally, in Section 4 we discuss the problem of estimation of convex sets in
high dimension. We show, through two examples, how to reduce the computational cost without affecting the rate of convergence of convex set estimators.
2. Estimation of convex sets under the Nykodim metric
2.1. Random polytopes and density support estimation
The most common representation of random polytopes consists of taking the
convex hull of i.i.d. random points in Rd . Stochastic and convex geometry have
provided powerful tools to understand the properties of random polytopes, since
the seminal works [RS63, RS64]. In these two papers, d = 2 and the random

V.-E. Brunel/Estimation of Convex Sets

4

polygon is the convex hull of uniform points in a planar convex body. The
expectations of the missing area and of the number of vertices of the random
polygon are computed, up to negligible terms, as n goes to infinity. The results
depend drastically on the structure of the boundary of the support. Namely, the
expected missing area is significantly smaller when the support is itself a polygon
than when its boundary has positive curvature everywhere. The missing area is
exactly the Nykodim distance between the random polygon and the support of
the random points. Hence, [RS63, RS64] give an approximate value of the risk
of the random polygon as an estimator of the support of the initial data points.
After Renyi and Sulanke’s work, much effort has been devoted to extend their
results to higher dimensions. Among most general results, one is due to [BL88].
For G ∈ Kd and ε > 0, let G(ε) be the ε-wet part of G, i.e., the complement of
the ε-floating body of G in G (see [Dup22, Bla23, SW90] for formal definitions).
Theorem 1 ( [BL88]). Let G ∈ Kd have volume one. Then,
c1 ∣G(1/n)∣ ≤ EG [∣G ∖ K̂n ∣] ≤ c2 (d)∣G(1/n)∣,

∀n ≥ n0 (d),

where c1 is a universal positive constant, c2 (d) is a positive constant that depends
on d only and n0 (d) is a positive integer that depends on d only.

As a consequence, computing the expected missing volume of K̂n asymptotically reduces to computing the volume of the (1/n)-wet part of G. In addition, it
is known that if G has volume one and ε goes to zero, then ∣G(ε)∣ is of the order
at least ε ln(1/ε) and at most ε2/d+1 [BL88]. The former rate is achieved when
G is a polytope and the latter when G has a smooth boundary with positive
curvature everywhere. In the latter case, a more refined result is available:
Theorem 2 ( [Sch94]). Let G ∈ Kd . Denote by κ(x) the generalized GaussKronecker curvature of ∂G at the point x and by µ the superficial Lebesgue
measure on ∂G. Then,
lim n2/(d+1) EG [

n→∞

d−1
1
∣G ∖ K̂n ∣
] = c(d)∣G∣− d+1 ∫ κ(x) d+1 dµ(x),
∣G∣
∂G

where c(d) is a positive constant that depends only on d.
[Sch94] give an explicit form for the constant c(d). An interesting result,
K̂n ∣]
due to [Gro74], shows that the quantity EG [∣G∖
is maximum when G is an
∣G∣
ellipsoid. In that case, a simple computation shows that the right hand side in
Theorem 2 is of the order dd+o(d) , as d becomes large. As a consequence, when the
dimension d becomes too large, the random polytope K̂n performs poorly as an
estimator of G in the worst case, because it suffers the curse of dimensionality,
both in the rate n−2/(d+1) and in the constant factors. Yet, it is known that
the rate n−2/(d+1) cannot be improved in a minimax sense. The following result
is proven in [Bru16] where, for two sequences an and bn of positive numbers,
we write an ≲θ bn if an ≤ c(θ)bn , ∀n ≥ 1, for some positive constant c(θ) that
depends on a parameter θ. In the sequel, we also write ≲ with no subscript if
the involved constant is universal.

V.-E. Brunel/Estimation of Convex Sets

5

Theorem 3 ( [Bru16]). The following inequalities hold:
n− d+1 ≲d inf sup EG [
2

G̃n G∈Kd

2
∣G △ G̃n ∣
∣G △ K̂n ∣
] ≤ sup EG [
] ≲d n− d+1 ,
∣G∣
∣G∣
G∈Kd

where the infimum is taken over all estimators G̃n based on n i.i.d. observations.
As a consequence, the random polytope K̂n is rate optimal on the class Kd
in a minimax sense, with respect to the Nykodim metric.
2.2. Adaptation to polytopal supports
As we already mentioned earlier, an attractive feature of most shape constraints
is that no meta parameters are needed to describe the objects of interest, unlike
in smoothness classes. Nonetheless, classes of functions or sets with a shape constraint usually contain parametric subclasses that correspond to simpler structures. For instance, classes of non decreasing functions contain piecewise constant functions with a bounded number of pieces. Classes of convex functions
contain piecewise affine functions with a bounded number of pieces. As for sets,
the class Kd contains polytopes with a bounded number of vertices. Note that
the support function of a polytope is piecewise linear with a bounded number
of pieces, corresponding to the vertices.
A desirable property of an estimator is adaptation to simpler structures.
This means that if the unknown object has a simpler structure, then the rate of
convergence of the agnostic estimator should be nearly as good as that of an estimator that would know about the simpler structure in advance. In log-concave
density estimation, [KGS16] shows that the maximum likelihood estimator over
the class of log-concave densities is adaptive to log-concave densities whose logarithm is piecewise affine with a bounded number of pieces. In univariate isotonic
(resp. convex) regression, [CGS15] shows that the least square estimator over
the class of non decreasing (resp. convex) sequences is adaptive to sequences
that are piecewise constant (resp. affine) with a bounded number of pieces.
When estimating the convex support of a uniform distribution, the random
polytope K̂n also optimizes a criterion: It is the maximum likelihood estimator
on the class Kd :
n

K̂n = argmax ∣C∣−n ∏ 1Xi ∈C .
C∈Kd

i=1

By Theorem 3, K̂n estimates G at the speed n−2/(d+1) in the worst case, i.e., when
G has a smooth boundary, under the Nykodim metric. When G is a polytope,
then Theorem 1 implies that K̂n estimates G at a much faster speed, namely,
n−1 (ln n)d−1 . A more refined result was proven in [BB93]. For a polytope P ⊆ Rd ,
let T (P ) be the number of flags of P , i.e., the number of increasing sequences
F0 ⊆ F1 ⊆ . . . ⊆ Fd−1 ⊆ Fd = P of faces of P where Fk is a k-dimensional face of
P , k = 0, . . . , d.

V.-E. Brunel/Estimation of Convex Sets

6

Theorem 4 ( [BB93]). Let G = P be a polytope. Then,
lim

n→∞

n
∣P ∖ K̂n ∣
T (P )
EP [
]=
.
(ln n)d−1
∣P ∣
(d + 1)d−1 (d − 1)!

In particular, if G is a polytope, then there is a significant gain in the speed of
convergence of K̂n , which becomes nearly parametric. In other words, K̂n adapts
to polytopal supports. However, it still suffers the curse of dimensionality in its
rate, because of the (ln n)d−1 factor. In [Bru16], it is shown that this rate is
not minimax optimal on classes of polytopes. Recall that K̂n maximizes the
likelihood function over the class of all convex bodies. If G is known to be a
polytope with at most r vertices, where r ≥ d + 1 is a known integer, [Bru16]
considers the maximum likelihood estimator over the corresponding subclass
of polytopes. Namely, denote by Pr the class of all convex polytopes with at
most r vertices. The maximum likelihood of P in the class Pr is defined as
n

P̂n(r) ∈ argmax ∣P ∣−n ∏ 1Xi ∈P : It is a polytope with at most r vertices that
Q∈Pr

i=1

(r)

contains X1 , . . . , Xn and has minimum volume. Note that, unlike K̂n , Pn is
not always uniquely defined. The rate of this estimator no longer suffers the
curse of dimensionality, unlike that of K̂n , when G ∈ Pr .

Theorem 5 ( [Bru16]). Let r ≥ d + 1. Then,

∣P △ G̃n ∣
1
≲d inf sup EP [
] ≤ sup EP
n
∣P ∣
G̃n P ∈P (r)
P ∈P (r)
n

n

⎤
⎡
⎢ ∣P △ Pn(r)∣ ⎥
⎥ ≲d r ln n ,
⎢
⎥
⎢
∣P ∣
n
⎥
⎢
⎦
⎣

where the infimum is taken over all estimators G̃n based on n i.i.d. observations.
It is also shown in [Bru16] that if d = 2, then
r
∣P △ G̃n ∣
≲ inf sup EP [
].
n G̃n P ∈P (r)
∣P ∣
n

(r)
P̂n

The estimator
is not computable in practice, but it gives a benchmark
for the optimal rate in estimation of P ∈ Pr , under the Nykodim metric. It is
still not clear whether the logarithmic factor could be dropped in the upper
(r)
bound (see [Bru16, Section 3.2]). A drawback of P̂n is that it requires the
knowledge of r, whereas K̂n is completely agnostic of the facial structure of
G. [Bru16] proposes a fully adaptive procedure and defines an estimator P̂nadapt
that is agnostic of the facial structure of G and yet performs at the same rate
(r)
as P̂n when G ∈ Pr for some integer r ≥ d + 1, and as K̂n for general supports
G (see [Bru16] and [Bru14] for more details).
2.3. Convex bodies, covering numbers and empirical processes
Covering numbers provide a powerful tool to describe the complexity of a class.
In the theory of empirical processes, it is often used in order to bound the

V.-E. Brunel/Estimation of Convex Sets

7

statistical performance of an estimator obtained by optimizing a criterion, such
as the likelihood function. In estimation of the support of a uniform distribution,
the random polytope K̂n maximizes the likelihood over the class Kd . Under
∣G ∖ K̂n ∣
,
the Nykodim metric, its risk is measured using the rescaled quantity
∣G∣
whose distribution is invariant under affine transformations of G. Hence, as
(1)
shown in [Bru16], it is sufficient to suppose that G ⊆ B(0, 1) (i.e., G ∈ Kd ) in
(1)
the analysis of the risk of K̂n . Let ε > 0 and let d(⋅, ⋅) be a metric on Kd (e.g.,
(1)
(1)
Nykodim or Hausdorff distance). A set N ⊆ Kd is called an ε-net of Kd with
(1)
respect to the metric d(⋅, ⋅) if, for all G ∈ Kd , there is G∗ ∈ N with d(G, G∗ ) ≤ ε.
(1)
The ε-covering number of Kd with respect to d(⋅, ⋅) is the minimum cardinality
(1)
of an ε-net of Kd . The following bound is proven in [Bro76].
Theorem 6 ( [Bro76]). Let ε ∈ (0, 1). The ε-covering number of Kd with
−(d−1)/2
respect to the Hausdorff distance is at most ceδ
, for some positive constant
c that depends on d.
(1)

This theorem implies a similar bound for the covering numbers with respect to the Nykodim distance. Indeed, by [Bru, Lemma 2], the Nykodim dis(1)
tance is dominated by the Hausdorff distance on the class Kd : d△ (G1 , G2 ) ≤
(1)
αdH (G1 , G2 ), for all G1 , G2 ∈ Kd , where α is a positive constant that depends
on d only. Hence, using this theorem combined with standard techniques from
M-estimation and empirical processes, (see, e.g., [VdV00,VdG98]), [Bru] proves
the following deviation inequality for K̂n .
Theorem 7 ( [Bru]). There exist positive constants c1 , c2 and c3 such that the
following holds. Let x ≥ 0 and n ≥ 2 be an integer. For all G ∈ Kd ,
2
∣G ∖ K̂n ∣
x
≤ c1 n− d+1 +
∣G∣
n

with PG -probability at least 1 − c2 e−c3 x .

Using the same techniques, more general deviation inequalities are proven
in [Bru], when the density of the Xi ’s is not uniform, but only supported on a
convex body G. For all measurable sets G, G′ ⊆ Rd and all densities f on Rd ,
denote by df (G, G′ ) = ∫G∖G′ f (x) dx.
Theorem 8 ( [Bru]). There exist positive constants C1 and C2 , that depend
on d only, such that the following holds. Let x ≥ 0 and n ≥ 2 be an integer. Let
(1)
G ∈ Kd and f be a density supported in G, with f ≤ M almost everywhere, for
some positive number M . Let X1 , . . . , Xn be i.i.d. random points with density f
and K̂n be their convex hull. Then,
df (G, K̂n ) ≤ C1 (M + 1)n−2/(d+1) +

with probability at least 1 − C2 e−x .

x
n

V.-E. Brunel/Estimation of Convex Sets

8

When f satisfies some margin condition (cf. below), the above upper bound
can be transferred to the Nykodim distance between K̂n and G, with a new rate
that depends on the margin condition. We refer to [Bru16] for more details.
2.4. Estimation of density level sets under convexity assumptions
The level sets of a density f in Rd are the sets Gλ = {x ∈ Rd ∶ f (x) ≥ λ}, for
λ > 0. Estimation of density level sets and, more specifically, of convex level sets,
has been tackled, e.g., in [Har87,Pol95,Tsy97]. Let λ > 0 such that Gλ ≠ ∅. The
excess mass of a measurable set C ⊆ Rd is defined as Mλ (C) = ∫C f (x) dx−λ∣C∣.
Simple algebra shows that Mλ (C) ≤ Mλ (Gλ ), for all measurable set C ⊆ Rd .
The empirical excess mass of a set C, given a sample X1 , . . . , Xn , is naturally
̂λ (C) = 1 ∑n 1X ∈C −λ∣C∣. Hence, the main idea to estimate Gλ is
defined as M
i
i=1
n
̂λ (C) over C ∈ C, where C is a given class of measurable sets. In
to maximize M
(1)
(1)
this section, we assume that Gλ ∈ Kd , hence, C = Kd . For instance, convexity
of Gλ is ensured if f is log-concave. If f is the uniform density on a convex body
(1)
G ∈ Kd , then G = Gλ for all λ ∈ (0, βd−1 ): In that case, support estimation is
equivalent to level set estimation, for small levels λ. In what follows, λ > 0 is a
̂λ (G).
fixed number and we define the estimator Ĝn ∈ argmin M
(1)

G∈Kd

In order to achieve consistency, an assumption is necessary about the behavior
of f around the boundary of its level set Gλ . Namely, f should not be too flat
near the boundary of Gλ . The assumption proposed in [Pol95] takes the following
form.
Assumption 1. There exist positive constants c, γ such that
µ ({x ∈ Rd ∶ ∣f (x) − λ∣ < η}) ≤ cη γ ,
for all η > 0 small enough.
Assumption 1, called margin condition, was introduced in [MT99]. It is usually imposed for discriminant analysis [MT99,LM15], statistical learning [Tsy04]
level set estimation or density support estimation [Bru].
In [Pol95], the notion of covering number with inclusion, sightly different
from that of covering number, is used to prove the main results.
Definition 1 (Covering number with inclusion). Let C be a class of measurable
subsets of B(0, 1), µ a probability distribution in Rd and ε > 0. The ε-covering
number with inclusion with respect to µ is the smallest integer N such that there
exists a collection N of measurable sets, with #N = N , satisfying the following:
For all C ∈ C, there exist C∗ , C ∗ ∈ N with C∗ ⊆ C ⊆ C ∗ and µ(C ∗ ∖ C∗ ) ≤ ε. It
is denoted by NI (ε, C, µ).
The following estimate is available for the class Kd :
(1)

Theorem 9 ( [Dud14]). Let the restriction of µ on B(0, 1) have a density f
with respect to the Lebesgue measure. Assume that f ≤ M almost everywhere,

V.-E. Brunel/Estimation of Convex Sets

9

where M > 0 is a given number. Then,
ln NI (ε, Kd , µ) ≲d,M ε−
(1)

d−1
2

,

as ε → 0.
Together with this estimate, [Pol95, Theorem 3.7] yields the following result.
Theorem 10 ( [Pol95]). Assume that d ≥ 2. There exists a constant c(d) such
that the following holds with probability one, as n goes to infinity. Let µ be
a probability measure on B(0, 1) with a bounded density f with respect to the
(1)
Lebesgue measure and let Assumption 1 hold. Let λ > 0 and let Gλ ∈ Kd . Then,
2γ
⎧
⎪
c(2)n− 3γ+4 if d = 2,
⎪
⎪
⎪
γ
⎪
µ (Ĝn △ Gλ ) ≤ ⎨c(3)n− 2γ+2 ln n if d = 3,
⎪
2γ
⎪
− (γ+1)(d+1)
⎪
⎪
if d > 3.
⎪
⎩c(d)n

Note that Ĝn is a polytope, and its vertices are sample points. Indeed, for all
(1) ̂
∗
∗
̂
C ∈ Kd , M
λ (C) ≤ Mλ (C ), where C is the convex hull of the sample points
contained in C. In the two dimensional case, [Har87] proposed an algorithm to
compute Ĝn . To the best of our knowledge, there is no algorithm to compute
Ĝn or an approximation of Ĝn in higher dimension.
2.5. Convex support estimation in nonparametric regression
Let the following model hold:
Yi = f (Xi ) + ξi ,

i = 1, . . . , n,

where X1 , . . . , Xn are deterministic or random points in [0.1]d , ξ1 , . . . , ξn are
i.i.d. random variables, with mean zero, independent of X1 , . . . , Xn and f ∶
[0, 1] → [0, ∞). In this section, we are interested in the estimation of the support
G of f , i.e., the closure of the set {x ∈ [0, 1]d ∶ f (x) > 0}. Throughout the
section, we assume that G is a convex body included in [0, 1]d . In [Bru13], the
function f is the indicator function of G: f (x) = 1 for x ∈ G, f (x) = 0 otherwise.
The design points X1 , . . . , Xn are i.i.d., uniformly distributed in [0, 1]d and the
ξi ’s are sub-Gaussian, i.e., E [etξ1 ] ≤ e 2 , for all t ∈ R, where σ > 0 need
not be known. [Bru13] considers a least square estimator Ĝn ∈ argmin A(C),
σ2 t2

C∈N

where N is a n−2/(d+1) -net of Kd , with respect to the Nykodim metric and
(1)

n

A(C) = ∑(1 − 2Yi )1Xi ∈C . The following upper bound is shown in [Bru13], in
which PG stands for the joint distribution of the sample with f (⋅) = 1⋅∈G .
i=1

Theorem 11. There exist two positive constants C1 , C2 , C3 that depend on d
and σ 2 and a positive integer n0 that depends on d only, such that the following
holds:

V.-E. Brunel/Estimation of Convex Sets

For all G ∈ Kd

(1)

10

and all x ≥ 0,
∣Ĝn △ G∣ ≤ C1 n− d+1 +
2

x
n

with PG probability at least 1 − C2 e−C3 x .

Of course, the estimator Ĝn is not computable in practice, since ε-nets of Kd
are not available. However, we believe that maximizing the functional A over
(1)
the whole class Kd would yield a similar upper bound, whose rate is proven
to be minimax optimal. Still, it would be unclear how to compute the resulting
(1)
estimator G̃n . Nonetheless, note that for all C ∈ Kd , A(C) = A(C ∗ ), where
∗
C is the convex hull of all the design points Xi ∈ C, implying that G̃n can be
chosen to be a polytope whose vertices are design points. Another open question
is whether Ĝn (or G̃n ) is adaptive to polytopal supports. In [Bru13], it is shown
that the minimax rate on the class Pr of polytopes with at most vertices is of
the order (ln n)/n: Is the error of G̃n of that order when the true support G is
a polytope ?
Here, we have only discussed the case when f is an indicator function, but
more general models for f are considered in [KT93b]. All these models, though,
impose a sharp separation condition on f , e.g., boundedness away from zero
on its support, which essentially reduces to the case of indicator functions. To
the best of our knowledge, harder cases, e.g., when f satisfies a margin type
condition, i.e., ∣{x ∈ [0, 1]d ∶ f (x) ≤ η}∣ ≤ cη γ for all η > 0 small enough, where c
and γ are positive constants, have not been tackled in the literature.
(1)

3. Estimation of convex sets under the Hausdorff metric
3.1. Support functions and polyhedral representations of convex
bodies
Support functions play a central role in estimation of convex bodies under the
Hausdorff metric. Indeed, the Hausdorff distance between two convex bodies G1
and G2 can be written in terms of their support functions hG1 and hG2 :
Lemma 1.
dH (G1 , G2 ) = sup ∣hG1 (u) − hG2 (u)∣,
u∈Sd−1

∀u ∈ Sd−1 .

Here, we state a few results about support functions that are useful in estimation of convex sets, and we refer to [Sch93] for more details on their account.
Note that a convex body is completely determined by its support function
and G = {x ∈ Rd ∶ ⟨u, x⟩ ≤ hG (u), ∀u ∈ Sd−1 }, for all G ∈ Kd .
A function h ∶ Sd−1 → R is the support function of a convex set if and only if
it is subadditive, in the following sense.

Definition 2. Let h ∶ Sd−1 → R. Define the function h̃ as h̃(v) = ∥v∥h(v/∥v∥) if
v ≠ 0, h̃(0) = 0. We say that h is subadditive if h̃ is convex.

V.-E. Brunel/Estimation of Convex Sets

11

If h ∶ Sd−1 → R is subadditive, then it is the support function of the convex
set {x ∈ Rd ∶ ⟨u, x⟩ ≤ h(u), ∀u ∈ Sd−1 }.
A polyhedral representation of a convex body is a way of writing that convex
body as the intersection of closed halfspaces or, equivalently, as a set of affine
constraints. For φ ∶ Sd−1 → R, we denote by Gφ = {x ∈ Rd ∶ ⟨u, x⟩ ≤ φ(u), ∀u ∈
Sd−1 }. It is easy to see that hGφ (u) ≤ φ(u), for all u ∈ Sd−1 . In general, the two
functions are not equal, since φ is not necessarily subadditive. This is actually
a necessary and sufficient condition (see [Bru17a, Proposition 1]):
Lemma 2. Let φ ∶ Sd−1 → R. Then, φ = hGφ if and only if φ is subadditive.
Actually, an interesting consequence of this result is the following.
Lemma 3. Let φ ∶ Sd−1 → R. Then, hGφ is the largest subadditive function that
is smaller or equal to φ.
Proof. Let g ∶ Sd−1 → R be a subadditive function with g(u) ≤ φ(u), for all
u ∈ Sd−1 . Then, Gg ⊆ Gφ . As a consequence, hGg (u) ≤ hGφ (u), for all u ∈ Sd−1 .
By Lemma 2, since g is subadditive, hGg = g, yielding g(u) ≤ hGφ (u) for all
u ∈ Sd−1 .
By Lemma 1, the Hausdorff distance between two convex sets Gφ and Gψ
can be written in terms of hGφ and hGψ . However, these support functions may
not be easy to compute in terms of φ and ψ. The following lemma overcomes
this issue when both φ and ψ are continuous.
Lemma 4 ( [Bru17a]). Let φ, ψ ∶ Sd−1 → R be two continuous functions. Assume
that Gφ and Gψ have nonempty interiors. Moreover, let R > r > 0 and assume
that B(a, r) ⊆ Gφ ⊆ B(a, R), for some a ∈ Rd . Let η = maxu∈Sd−1 ∣ψ(u) − φ(u)∣.
ηR 1 + η/r
.
If η < r, then dH (Gψ , Gφ ) ≤
r 1 − η/r
In this lemma, the mapping ψ plays the role of an estimate of φ. However,
in certain cases, it may not be easy to control the accuracy of the estimation
of φ(u) for all u ∈ Sd−1 simultaneously, but instead, only on a finite subset of
Sd−1 . Recall that for ε ∈ (0, 1), an ε-net of Sd−1 is a subset N of Sd−1 such that
for all u ∈ Sd−1 , there is u∗ ∈ N with ∥u − u∗ ∥ ≤ ε. For a subset N of Sd−1 and a
d
function ψ ∶ N → R, denote by GN
ψ = {x ∈ R ∶ ⟨u, x⟩ ≤ ψ(u), ∀u ∈ N }. Then, the
following result is complementary to the previous lemma, when φ = hGφ (i.e., by
Lemma 2, when φ is subadditive) and when ψ is only defined on a (fine enough)
discretization of Sd−1 .
Lemma 5 ( [Bru17a]). Let G ∈ Kd and ψ ∶ Sd−1 → R. Let ε ∈ (0, 1) and N
be an ε-net of Sd−1 . Let R > r > 0 and assume that B(a, r) ⊆ G ⊆ B(a, R),
for some a ∈ Rd . Let η = maxu∈N ∣ĥ(u) − hG (u)∣. Then, if η < r, dH (GN
ψ , G) ≤
ηR 1 + η/r 2Rε
+
.
r 1 − η/r 1 − ε
Finally, the next lemma provides a polyhedral representation of the convex
hull of a finite collection of points in the space. It is straightforward, given that a

V.-E. Brunel/Estimation of Convex Sets

12

linear function defined on a convex body is necessarily maximized at an extreme
point, but it yields a useful representation of random polytopes.
Lemma 6. Let x1 , . . . , xn ∈ Rd and let Kn be their convex hull. Then,
hKn (u) = max ⟨u, xi ⟩,
1≤i≤n

∀u ∈ Sd−1 .

In particular, Kn = {x ∈ Rd ∶ ⟨u, x⟩ ≤ max ⟨u, xi ⟩, ∀u ∈ Sd−1 }.
1≤i≤n

Of course, this polyhedral representation is not optimal, since Kn is a polytope, yielding that only a finite number of affine constraints should be sufficient
to describe the set Kn : those corresponding to unit vectors u that are normal
to (d − 1)-dimensional faces of Kn (see Minkowski-Weil’s theorem for polyhedra). All other affine constraints are redundant. However, in practice, finding
the (d − 1)-dimensional faces of the convex hull of a given finite collection of
points is a hard problem (see, e.g., [BFM98]).
3.2. Estimation of support functions
Sometimes, in order to estimate a convex body G, it can be natural to estimate
its support function hG . The previous lemmas indicate that if the estimation
error are measured with respect to the Hausdorff metric, then it is enough to
bound the pointwise or sup-norm error for the estimation of hG .
In this section, G is an unknown convex body and we assume that an estimator ĥn of hG has been extracted from available data. Then, Gĥn is a natural
estimator of G. We review examples and show how the results and properties
stated in the previous section apply, by distinguishing two cases: when ĥn is
subadditive, hence, when it is the support function Gĥn , and when it is not.
3.2.1. When ĥn is subadditive

This is the case, for instance, in density support estimation: A natural estimator of the support G of i.i.d. random points X1 , . . . , Xn is ĥn (u) = max ⟨u, Xi ⟩,
1≤i≤n

u ∈ Sd−1 . By Lemma 6, ĥn is actually the support function of K̂n , hence, it is
subadditive.
Lemma 7. Let G ∈ Kd . Let ĥn be a subadditive estimator of hG and let
Ĝn = Gĥn . Let δ, η ∈ (0, 1) and assume that ∣ĥn (u) − hG (u)∣ ≤ η with probability
at least 1 − δ, for all u ∈ Sd−1 . Then, dH (Ĝn , G) ≤ 2η with probability at least
1 − 2(18/η)dδ.
(1)

Proof. The proof of this lemma relies on two fundamental facts. First, by a standard volumetric argument, there exists an ε-net of cardinality at most (3/ε)d,
for all ε ∈ (0, 1). Second, the following result, which is Lemma 5.2 in [FV14], is
a very elegant tool to work with approximations of the unit sphere.

V.-E. Brunel/Estimation of Convex Sets

13

Lemma 8 ( [FV14]). Let ε ∈ (0, 1) and let N be an ε-net of Sd−1 . Then, for all
u ∈ Sd−1 , there are sequences (uk )k≥0 ⊆ N and (εk )k≥1 ⊆ R such that
• u = u 0 + ∑ εk u k
∞

k=1

• 0 ≤ εk ≤ εk ,

∀k ≥ 1.

Let ε = η/6 and let N be an ε-net of Sd−1 . Denote by −N = {−u ∶ u ∈ N }. Let
A be the event when ∣ĥn (u) − hG (u)∣ ≤ η, simultaneously for all u ∈ N ∪ (−N ).
By a union bound,
P[A] ≥ 1 −

∑

u∈N ∪(−N )

P[∣ĥn (u) − hG (u)∣ ≤ η] ≥ 1 − 2(#N )δ ≥ 1 − 2(18/η)dδ.

Now, assume that A is satisfied and let u ∈ Sd−1 . Then, with the notation of
Lemma 8, using subadditivity of support functions and the fact that hG ≤ 1
(since G ⊆ B(0, 1)),
ĥn (u) ≥ ĥn (u0 ) − ∑ εk ĥn (−uk )
k≥1

≥ hG (u0 ) − η − ∑ εk (hG (−uk ) + η)
k≥1

≥ hG (u0 ) − η − 2 ∑ εk
k≥1

2ε
= hG (u0 ) − η −
1−ε

≥ hG (u) − ∑ εk hG (uk ) − η −
k≥1

≥ hG (u) − η −
≥ hG (u) − 2η.

Similarly,

2ε
1−ε

3ε
1−ε

hG (u) ≥ ĥn (u) − 2η.

As a consequence, if A is satisfied, then dH (Ĝn , G) = supu∈Sd−1 ∣ĥn (u) −
hG (u)∣ ≤ 2η, which finishes the proof of the lemma.
This technique is applied in [Bru17b] for support estimation. The general
(1)
framework considered in that work is the following. Let G ∈ Kd and µ a probd
ability measure in R , satisfying the following assumption.
Assumption 2. For all u ∈ Rd and all t ∈ [0, r], µ(CG (u, t)) ≥ Ltα , where:
• r, L, α are given positive numbers with r < 1;
• CG (u, t) is the cap of G in the direction u and with height t, i.e.,
CG (u, t) = {x ∈ G ∶ ⟨u, x⟩ ≥ hG (u) − t}.

V.-E. Brunel/Estimation of Convex Sets

14

Particular cases of such pairs (G, µ) include uniform distributions on general
convex bodies (α = d) or smooth convex bodies (α = (d + 1)/2), uniform distributions on the boundary of smooth convex bodies (α = (d − 1)/2), projections
of uniform distributions on higher dimensional smooth convex bodies, distributions with densities supported on a convex body with polynomial decay near
the boundary, etc.
It is easy to show that under Assumption 2, for all u ∈ Sd−1 and all t ∈ [0, r],
α
∣ĥn (u) − hG (u)∣ ≤ t with probability at least 1 − e−Lnt . Hence, the following
⎧
⎪
⎪1 if α ≥ 1
theorem is shown, using Lemma 7. Set τα = ⎨ α−1
⎪
2
if 0 < α < 1.
⎪
⎩
Theorem 12 ( [Bru17b]). Let r ∈ (0, 1) and L, α > 0. There exists a positive
1
−1
C ln n α
) and bn = n α . Let
constant C such that the following holds. Set an = (
n
(1)
G ∈ Kd and µ be a probability measure in Rd and let Assumption 2 hold. Then,
for all x ≥ 0 such that an + bn x ≤ r,
dH (K̂n , G) ≤ 2an + 2bn x

with µ-probability at least 1 − 12d exp (−Cα Lxα ).

As a consequence, K̂n satisfies dH (K̂n , G) = OP (( lnnn )

−1/α

tion 2.

) under Assump-

Remark 2.
• [Bru17b] uses a different technique in order to bound the
error of K̂n when G is a polytope that satisfies a standardness condition.
1/d
Using the technique shown above would yield the rate ((ln n)/n) (α = d),
which is suboptimal. Indeed, the following inequality is shown when G is
a polytope with at most p vertices (p ≥ d + 1) and satisfies a standardness
condition (i.e, intuitively, has no pointy vertices):
PG [n1/d dH (K, K̂n ) ≥ x] ≤ pe−νβd x , ∀x ≥ 0,
d

where ν > 0 is a constant coming from the standardness condition.
• Surprisingly, the adaptive feature of K̂n disappears under the Hausdorff
metric. As discussed in Section 2, K̂n adapts to polytopal supports under
the Nykodim metric. On the contrary, the rate of K̂n in the Hausdorff
metric deteriorates when the support G is a polytope.
Another model where the same ideas could be applied has been considered
in [GKM06, Gun12]. Given independent observations Yi = hG (ui ) + εi , where
ui ∈ Sd−1 is either deterministic or random and εi is a zero mean error term,
independent of ui , [Gun12] estimates hG by the least square estimator on the
class of all subadditive functions h ∶ Sd−1 → R. This produces an estimator
ĥn that is a support function itself. In general, L2 -type metrics are natural to
measure the performance of least square estimators. [GKM06,Gun12] prove rates
of convergence of their estimator with respect to the L2 -distance, with minimax

V.-E. Brunel/Estimation of Convex Sets

15

optimality proven in [Gun12]. [GKM06] also translates these error bounds to
the L∞ metric, using elegant norm inequalities for subadditive functions, which
show that the L∞ distance is dominated by the L2 distance in some sense
(see [Gro96, Proposition 2.3.1] and [GKM06, Proposition 2.2]). Nevertheless, as
remarked by [Gun12], the bounds that they obtain are very loose. The optimal
(1)
rate of estimation of G ∈ Kd with respect to the Hausdorff distance in that
model is still an unsolved problem.
3.2.2. When the estimator ĥn is not subadditive

As we have already mentioned, the estimator ĥn is not subadditive in general.
Hence, it is not the support function of the corresponding set estimator Ĝn =
Gĥn and the technique of the previous subsection does not apply. Lemmas 4
and 5 are two key results to deal with this case. Lemma 4 is useful when ĥn is
continuous almost surely and its error can be bounded uniformly on the unit
sphere Sd−1 . Indeed, if ∣ĥn (u) − hG (u)∣ ≤ η for all u ∈ Sd−1 simultaneously, with
high probability, then, if G satisfies the assumptions of Lemma 4 and η is small
enough, dH (Gĥn , G) ≤ η ′ with high probability, where η ′ is a small number that
depends on η and other parameters. We apply Lemma 5 in two cases: when
the true support function hG is not available (e.g., when G = Gφ for a known
function φ that is not necessarily subadditive) and when the error of ĥn can
only be controlled pointwise, i.e., for each u ∈ Sd−1 separately. Indeed, by a
union bound, pointwise deviations transfer to uniform deviations on ε-nets. We
give two examples, borrowed from [Bru17a] and [BKY], where these results are
used.
Estimation of the level sets of the Tukey depth

[Bru17a]

Let µ be a probability measure in R . The Tukey depth Dµ (x) of a point
x ∈ Rd with respect to µ is defined as the smallest probability mass of a closed
halfspace containing x:
Dµ (x) = inf µ(H),
d

x∈H∈Hd

where Hd is the collection of closed half-spaces in Rd . For α ∈ (0, 1), the α-level
set of Dµ is the set G = {x ∈ Rd ∶ Dµ (x) ≥ α}. It is a closed convex set and it
has the following polyhedral representation [KM12, Theorem 2] and [Bru17a,
Lemma 1]:
G = {x ∈ Rd ∶ ⟨u, x⟩ ≤ qu , ∀u ∈ Sd−1 },
(1)

where qu is the upper (1 − α)-quantile of ⟨u, X⟩ with X ∼ µ. Let X1 , . . . , Xn
be i.i.d. random points with distribution µ and let µn be the corresponding
1 n
empirical measure: µn (A) = ∑ 1Xi ∈A , for all Borel sets A ⊆ Rd . The empirical
n i=1

V.-E. Brunel/Estimation of Convex Sets

16

α-level set of the Tukey depth is Ĝn = {x ∈ Rd ∶ Dµn (x) ≥ α}, which also has a
simple polyhedral representation
G = {x ∈ Rd ∶ ⟨u, x⟩ ≤ q̂u , ∀u ∈ Sd−1 },

(2)

where q̂u = sup{t ∈ R ∶ #{i = 1, . . . , n ∶ ⟨u, Xi ⟩ ≥ t} ≥ nα} is the empirical upper
(1 − α)-quantile of the sample ⟨u, X1 ⟩, . . . , ⟨u, Xn ⟩, for all u ∈ Sd−1 .
Note that in general, neither u ↦ qu nor u ↦ q̂u are subadditive. However,
the latter is always continuous, as a consequence of [Bru17a, Lemma 15] and the
former is continuous under some assumption on µ (see [Bru17a, Lemma 11]).
Using standard results from empirical processes theory, [Bru17a] shows that
under some assumption on µ, supu∈Sd−1 ∣q̂u − qu ∣ is small, with high probability.
Hence, using Lemma 5, this yields the following result.
Theorem 13. [Bru17a, Corollary 2]
Let µ have a density f with respect to the Lebesgue measure and let 0 < α <
maxx∈Rd Dµ (x). Assume that f satisfies one of the following conditions:

1. f is continuous and positive everywhere and there exist C > 0 and ν > d − 1
such that ∣f (x)∣ ≤ C(1 + ∥x∥)−ν , ∀x ∈ Rd .
2. f is supported on a bounded convex set and is uniformly continuous on its
support.
Then, dH (Ĝn , G) = OP (n−1/2 ).

More precise deviation inequalities are proven in [Bru17a] but here, we only
state the result in this form for simplicity of the development. Note that any
log-concave distribution satisfies one of the two conditions imposed on f in this
theorem. The uniform distribution on a convex body K satisfies the second
condition and, in that case, G is equal to the floating body of K (since it
is easy to see that the inclusion in [Bru17a, Lemma 1] is an equality in this
case). The estimator Ĝn is a polytope, also called k-hull of X1 , . . . , Xn , for
k = ⌈nα⌉ [CSY87]. Such a polytope extends the notion of convex hull, which is
just the 1-hull. Computational questions are tackled in Section 4.
Estimation of the convex support of a density from noisy observations
[BKY]
Let G ∈ Kd and X1 , . . . , Xn be i.i.d. random points uniformly distributed in
G. Assume that only Yi = Xi + ξi , i = 1, . . . , n, are observed, where the ξi ’s are
i.i.d. centered Gaussian vectors with covariance matrix σ 2 Id (Id is the identity
matrix and σ 2 > 0 is known), independent
of the Xi ’s. For u ∈ Sd−1 , let ĥn (u) =
√
max1≤i≤n ⟨u, Yi ⟩ − bn , where bn ≈ 2σ 2 ln n is a deterministic bias and set Ĝn =
Gĥn . It is proved that ∣ĥn (u) − hG (u)∣ is small with high probability, for each
u ∈ Sd−1 separately. Hence, using Lemma 5, [BKY] proves that
ln ln n
).
dH (Ĝn , G) = OP ( √
ln n

V.-E. Brunel/Estimation of Convex Sets

17

A stronger deviation inequality is proven in [BKY]. It is also shown that the
minimax rate of estimation of G in this model is very slow and that Ĝn is rate
optimal up to logarithmic factors, in a minimax sense.
4. Computational challenges for random polytopes in high
dimension
The computational complexity of a set estimator can be very large, and some
estimators may not even be computable in practice. For instance, computing
the convex hull of n points in Rd requires approximately nd/2 operations (see,
e.g., [Cha93]). As for the level sets of the empirical Tukey depth, aka k-hulls
[CSY87], there is no available algorithm to compute them in high dimension, to
the best of our knowledge. As we have seen above (Lemma 6 and (1)), both these
random convex sets can be easily written using infinitely many affine constraints.
Here, we show how to obtain approximate polyhedral representations of these
random convex, so as to significantly reduce their computational complexity
without affecting the rate of their statistical accuracy.
The key idea is to discretize Sd−1 , using a minimum cardinality ε-net, for
some ε > 0 that is small enough. The choice of ε will depend on the statistical
accuracy the random set of interest. However, minimal ε-nets of Sd−1 are not
available in practice, hence, we use the following lemma, proven in [Bru17a],
which bounds from above the number of random unit vectors that are necessary
to produce an ε-net of Sd−1 with high probability.
Lemma 9 ( [Bru17a]). Let M be a positive integer and U1 , . . . , UM be i.i.d.
uniform vectors in Sd−1 . Let ε ∈ (0, 1) and let C be the event satisfied when the
collection {U1 , . . . , UM } is an ε-net of Sd−1 . Then,
P[C] ≥ 1 − 6d exp (−

M εd−1
2d8

d−1
2

1
+ d ln ( )) .
ε

Note that sampling a unit vector is simple: Sample a standard Gaussian
vector and divide it by its Euclidean norm.
4.1. Approximating random polytopes
Let G ∈ Kd and X1 , . . . , Xn be i.i.d. random points with probability distribution
µ whose support is included in G.
For an integer M ≥ 1, let U1 , . . . , UM be i.i.d. uniform vectors on the unit
sphere Sd−1 , independent of X1 , . . . , Xn , and denote by K̂n,M = {x ∈ Rd ∶
⟨Uj , x⟩ ≤ max ⟨Uj , Xi ⟩, ∀j = 1, . . . , M }. Then, the following theorem, proven
1≤i≤n

in [Bru17b], is a consequence of Theorem 12 and Lemma 5.

Theorem 14 ( [Bru17b]). Let G ∈ Kd and X1 , . . . , Xn be i.i.d. random points in
d−1
G, with some probability measure µ. Let Assumption 2 hold. Let C > 2α−1 d2 8 2

V.-E. Brunel/Estimation of Convex Sets

and M = Cn

d−1
α

(ln n)

α−d+1
α

18

. Then,

⎛ ln n α ⎞
dH (K̂n,M , G) = OP (
) .
⎠
⎝ n
1

As a corollary, the random polytope K̂n can be approximated by K̂n,M :
Corollary 1 ( [Bru17b]). Let the assumptions of Theorem 14 hold. Then,
⎛ ln n α ⎞
dH (K̂n,M , K̂n ) = OP (
) .
⎝ n
⎠
1

Computing the estimator K̂n,M requires sampling M uniform random unit
vectors and checking nM affine constraints. Hence, the overall computation cost
of computing K̂n,M is O(dnM ). Hence, the convex hull of i.i.d. uniform points
d−1
in a general convex body can be approximated in O (d2 8 2 n2−1/d (ln n)1/d )
operations, and the convex hull of i.i.d. uniform points in a smooth convex body
d−1
3d−1
d−3
can be approximated in O (d2 8 2 n d+1 (ln n)− d+1 ) operations, without affecting
the rate of the statistical accuracy.
4.2. Approximating empirical Tukey depth level sets
The empirical Tukey depth level sets are an extension of the convex hull and, in
general, it is not known how to compute them in high dimension. Here, we use
similar ideas as for the convex hull in order to produce good approximations
that do not reduce their statistical accuracy. The main difference is that in
the polyhedral representation (1) of the true level sets, the mapping u ↦ qu is
not necessarily subadditive. Actually, we refer to [Bru17a, Section 2] for open
questions about this mapping.
For M ≥ 1, set Ĝn,M = {x ∈ Rd ∶ ⟨Uj , x⟩ ≤ q̂Uj , ∀j = 1, . . . , M }, where U1 , . . . , UM
are i.i.d. uniform random variables on S d−1 , independent of X1 , . . . , Xn . Next
theorem is proven in [Bru17a].
Theorem 15 ( [Bru17a]). Recall all the assumptions of Theorem 13 and assume, in addition, that the mapping u ↦ qu is subadditive. Then, for M >
d−1
8 2 d(d + 1)nd−1 ln n,
dH (Ĝn,M , G) = OP (n−1/2 ) .
As a consequence, the k-hull Ĝn can be approximated by Ĝn,M and we have
the following corollary.
Theorem 16. Let the assumptions of Theorem 15 hold. Then,
dH (Ĝn,M , Ĝn ) = OP (n−1/2 ) .
Of course, the computation cost of the estimator Ĝn,M , for the choice of
M prescribed in this theorem, drastically suffers the curse of dimensionality,
because of the factor nd−1 .

V.-E. Brunel/Estimation of Convex Sets

19

References
[BB93]

I. Bàràny and C. Buchta. Random polytopes in a convex polytope,
independence of shape, and concentration of vertices. Math. Ann.,
297:467–497, 1993.
[BFM98] D. Bremner, K. Fukuda, and A. Marzetta. Primal-dual methods for
vertex and facet enumeration. Discrete Comput. Geom., 20(3):333–
357, 1998. ACM Symposium on Computational Geometry (Nice,
1997).
[BKY]
V.-E. Brunel, J. Klusowski, and D. Yang. Recovering the endpoint
of a density from noisy data with application to convex body estimation. in preparation.
[BL88]
I. Bàràny and D. G. Larman. Convex bodies, economic cap coverings,
random polytopes. Mathematika, 35:274–291, 1988.
[Bla23]
W. Blaschke. Vorlesungen über Differentialgeometrue II. SpringerVerlag, 1923.
[Bro76]
E. M. Bronshtein. ǫ-entropy of convex sets and functions. Siberian
Mathematical Journal, 17:303–398, 1976.
[Bru]
V.-E. Brunel. Uniform deviation and moment inequalities for random
polytopes with general densities in arbitrary convex bodies. submitted, arXiv:1704.01620.
[Bru13]
V.-E. Brunel. Adaptive estimation of convex polytopes and convex
sets from noisy data. Electronic Journal of Statistics, 7:1301–1327,
2013.
[Bru14]
V.-E. Brunel. Non parametric estimation of convex bodies and convex polytopes. PhD Thesis, 2014.
[Bru16]
V.-E. Brunel. Adaptive estimation of convex and polytopal density
support. Probab. Theory Relat. Fields, 164(1):1–16, 2016.
[Bru17a] V.-E. Brunel. Concentration of the empirical level sets of tukey’s
halfspace depth. Submitted, 2017.
[Bru17b] V.-E. Brunel. Uniform behaviors of random polytopes in hausdorff
metric. Submitted, 2017.
[CGS15] S. Chatterjee, A. Guntuboyina, and B. Sen. On risk bounds in isotonic and other shape restricted regression problems. Ann. Statist.,
43(4):1774–1800, 2015.
[Cha93] B. Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete Computational Geometry, 10:377–409, 1993.
[CSY87] R. Cole, M. Sharir, and C.-K. Yap. On k-hulls and related problems.
SIAM J. Comput., 16(1):61–77, 1987.
[Cue09]
A. Cuevas. Set estimation : Another bridge between statistics and
geometry. Sociedad de Estadı́stica e Investigación Operativa, 25:71–
85, 2009.
[Dud14] R. M. Dudley. Uniform central limit theorems, volume 142 of Cambridge Studies in Advanced Mathematics. Cambridge University
Press, New York, second edition, 2014.

V.-E. Brunel/Estimation of Convex Sets

[Dup22]

20

C. Dupin. Applications de géométrie et de méchanique à la marine.
Ponts et Chaussées, Paris, 1822.
[FV14]
D. Fresen and R. Vitale. Concentration of random polytopes around
the expected convex hull. Electron. Commun. Probab., 19:1–8, 2014.
[GKM06] R. J. Gardner, M. Kiderlen, and P. Milanfar. Convergence of algorithms for reconstructing convex bodies and directional measures.
Ann. Statist., 34(3):1331–1374, 2006.
[Gro74]
H. Groemer. On the mean value of the volume of a random polytope
in a convex set. Arch. Math., 25:86–90, 1974.
[Gro96]
H. Groemer. Geometric applications of Fourier series and spherical harmonics, volume 61 of Encyclopedia of Mathematics and its
Applications. Cambridge University Press, Cambridge, 1996.
[Gun12] A. Guntuboyina. Optimal rates of convergence for convex set estimation from support functions. Annals of Statistics, 40:385–411,
2012.
[Har87]
J. A. Hartigan. Estimation of a convex density contour in two dimensions. J. Amer. Statist. Assoc., 82(397):267–270, 1987.
[KGS16] A. K. H. Kim, A. Guntuboyina, and R. J. Samworth. Adaptation in
log-concave density estimation. Preprint, 2016.
[KM12]
L. Kong and I. Mizera. Quantile tomography: using quantiles with
multivariate data. Statist. Sinica, 22(4):1589–1610, 2012.
[KST95a] A. P. Korostelev, L. Simar, and A. B. Tsybakov. Efficient estimation
of monotone boundaries. The Annals of Statistics, 23:476–489, 1995.
[KST95b] A. P. Korostelev, L. Simar, and A. B. Tsybakov. On estimation
of monotone and convex boundaries. Publications de l’Institut de
Statistique de l’Université de Paris, 39:3–18, 1995.
[KT93a] A. P. Korostelev and A. B. Tsybakov. Estimation of the density
support and its functionals (in russian). Probl. Peredachi Inf., 29:1–
15, 1993.
[KT93b] A. P. Korostelëv and A. B. Tsybakov. Minimax theory of image
reconstruction, volume 82 of Lecture Notes in Statistics. SpringerVerlag, New York, 1993.
[LM15]
S. Loustau and C. Marteau. Noisy discriminant analysis with boundary assumptions. J. Nonparametr. Stat., 27(4):425–441, 2015.
[ML93]
P. Mani-Levitska. Characterization of convex sets. in Gruber,
P.M. and Wills, J.M., Eds., Handbook of Convex Geometry, NorthHolland, pages 19–41, 1993.
[MT99]
E. Mammen and A. B. Tsybakov. Smooth discrimination analysis.
Ann. Statist., 27(6):1808–1829, 1999.
[PL08]
B. Pateiro-Lopez. Set estimation under convexity type restrictions.
PhD Thesis, 2008.
[Pol95]
W. Polonik. Measuring mass concentrations and estimating density
contour clusters - an excess mass approach. The Annals of Statistics,
23:855–881, 1995.
[RC07]
A. Rodrı́guez Casal. Set estimation under convexity type assumptions. Ann. Inst. H. Poincaré Probab. Statist., 43(6):763–774, 2007.

V.-E. Brunel/Estimation of Convex Sets

21

[RCSN16] A. Rodrı́guez-Casal and P. Saavedra-Nieves. A fully data-driven
method for estimating the shape of a point cloud. ESAIM Probab.
Stat., 20:332–348, 2016.
[RS63]
A. Rényi and R. Sulanke. Über die konvexe Hülle von n zufällig
gewählten Punkten. Z. Wahrscheinlichkeitsth. Verw. Geb., 2:75–84,
1963.
[RS64]
A. Rényi and R. Sulanke. Über die konvexe Hülle von n zufällig
gewählten Punkten. ii. Z. Wahrscheinlichkeitsth. Verw. Geb., 3:138–
147, 1964.
[Sch93]
R. Schneider. Convex bodies: the Brunn-Minkowski theory. Cambridge University Press, 1993.
[Sch94]
C. Schütt. Random polytopes and affine surface area. Mathematische
Nachrichten, 170:227–249, 1994.
[SW90]
C. Schütt and E. Werner. The convex floating body. Math. Scand,
66:275–290, 1990.
[Thä08] C. Thäle. 50 years sets with positive reach - a survey. Surveys in
Mathematics and its Applications, 3:123–165, 2008.
[Tsy94]
A. B. Tsybakov. Multidimensional change-point problems and
boundary estimation. In Change-point problems (South Hadley, MA,
1992), volume 23 of IMS Lecture Notes Monogr. Ser., pages 317–329.
Inst. Math. Statist., Hayward, CA, 1994.
[Tsy97]
A. Tsybakov. On nonparametric estimation of density level sets.
Ann. Stat., 25:948–969, 1997.
[Tsy04]
A. B. Tsybakov. Optimal aggregation of classifiers in statistical learning. Ann. Statist., 32(1):135–166, 2004.
[VdG98] S. Van de Geer. Empirical Processes in M-estimation. Cambridge
University Press, 1998.
[VdV00] A. W. Van der Vaart. Asymptotic Statistics. Cambridge University
Press, 2000.

