Deviation inequalities for random polytopes in arbitrary convex bodies. (English) Zbl 1455.60027

Brunel, Victor-Emmanuel

Bernoulli 26, No. 4, 2488-2502 (2020).

Summary: We prove an exponential deviation inequality for the convex hull of a finite sample of i.i.d. random points with a density supported on an arbitrary convex body in \(\mathbb{R}^d\), \(d\geq 2\). When the density is uniform, our result yields rate optimal upper bounds for all the moments of the missing volume of the convex hull, uniformly over all convex bodies of \(\mathbb{R}^d \): We make no restrictions on their volume, location in the space or smoothness of their boundary. For general densities, the only restriction we make is that the density is bounded from above, even though we believe this restriction is not necessary. However, the density can have any decay to zero near the boundary of its support. After extending an identity due to B. Efron [Biometrika 52, 331–343 (1965; Zbl 0138.41301)], we also prove upper bounds for the moments of the number of vertices of the random polytope. Surprisingly, these bounds do not depend on the underlying density and we prove that the growth rates that we obtain are tight in a certain sense. Our results are non asymptotic and hold uniformly over all convex bodies.

MSC:

60D05	Geometric probability and stochastic geometry
60E15	Inequalities; stochastic orderings

Keywords:

convex body; convex hull; covering number; density support estimation; deviation inequality; random polytope

Citations:

Zbl 0138.41301

References:

[1]	Affentranger, F. and Wieacker, J.A. (1991). On the convex hull of uniform random points in a simple \(d\)-polytope. Discrete Comput. Geom. 6 291-305. · Zbl 0725.52004 · doi:10.1007/BF02574691
[2]	Bárány, I. and Buchta, C. (1993). Random polytopes in a convex polytope, independence of shape, and concentration of vertices. Math. Ann. 297 467-497. · Zbl 0788.52003
[3]	Bárány, I. and Larman, D.G. (1988). Convex bodies, economic cap coverings, random polytopes. Mathematika 35 274-291. · Zbl 0674.52003
[4]	Bronshtein, E.M. (1976). \( \epsilon \)-Entropy of convex sets and functions. Sib. Math. J. 17 393-398. · Zbl 0354.54026
[5]	Buchta, C. (2005). An identity relating moments of functionals of convex hulls. Discrete Comput. Geom. 33 125-142. · Zbl 1065.52003 · doi:10.1007/s00454-004-1109-3
[6]	Buchta, C. and Müller, J. (1984). Random polytopes in a ball. J. Appl. Probab. 21 753-762. · Zbl 0552.60006 · doi:10.2307/3213693
[7]	Efron, B. (1965). The convex hull of a random set of points. Biometrika 52 331-343. · Zbl 0138.41301 · doi:10.1093/biomet/52.3-4.331
[8]	Giannopoulos, A. and Tsolomitis, A. (2003). Volume radius of a random polytope in a convex body. Math. Proc. Cambridge Philos. Soc. 134 13-21. · Zbl 1053.52007 · doi:10.1017/S0305004102006254
[9]	Groemer, H. (1974). On the mean value of the volume of a random polytope in a convex set. Arch. Math. (Basel) 25 86-90. · Zbl 0287.52009 · doi:10.1007/BF01238645
[10]	Grote, J., Kabluchko, Z. and Thäle, C. (2019). Limit theorems for random simplices in high dimensions. ALEA Lat. Am. J. Probab. Math. Stat. 16 141-177. · Zbl 1456.52006 · doi:10.30757/ALEA.v16-06
[11]	Hug, D. and Schneider, R. (2007). A stability result for a volume ratio. Israel J. Math. 161 209-219. · Zbl 1139.52012 · doi:10.1007/s11856-007-0079-6
[12]	Korostelev, A.P., Simar, L. and Tsybakov, A.B. (1995). On estimation of monotone and convex boundaries. Publ. Inst. Stat. Univ. Paris 39 3-18. · Zbl 0817.62023
[13]	Leichtweiss, K. (1959). Über die affine Exzentrizität konvexer Körper. Arch. Math. 10 187-199. · Zbl 0089.38303
[14]	Mammen, E. and Tsybakov, A.B. (1995). Asymptotical minimax recovery of sets with smooth boundaries. Ann. Statist. 23 502-524. · Zbl 0834.62038 · doi:10.1214/aos/1176324533
[15]	Mammen, E. and Tsybakov, A.B. (1999). Smooth discrimination analysis. Ann. Statist. 27 1808-1829. · Zbl 0961.62058 · doi:10.1214/aos/1017939240
[16]	Pardon, J. (2011). Central limit theorems for random polygons in an arbitrary convex set. Ann. Probab. 39 881-903. · Zbl 1221.52011 · doi:10.1214/10-AOP568
[17]	Pardon, J. (2012). Central limit theorems for uniform model random polygons. J. Theoret. Probab. 25 823-833. · Zbl 1258.60026 · doi:10.1007/s10959-010-0335-2
[18]	Reitzner, M. (2003). Random polytopes and the Efron-Stein jackknife inequality. Ann. Probab. 31 2136-2166. · Zbl 1058.60010 · doi:10.1214/aop/1068646381
[19]	Rényi, A. and Sulanke, R. (1963). Über die konvexe Hülle von \(n\) zufällig gewählten Punkten. Z. Wahrsch. Verw. Gebiete 2 75-84. · Zbl 0118.13701
[20]	Rényi, A. and Sulanke, R. (1964). Über die konvexe Hülle von \(n\) zufällig gewählten Punkten. II. Z. Wahrsch. Verw. Gebiete 3 138-147. · Zbl 0126.34103
[21]	Schneider, R. (1993). Convex Bodies: The Brunn-Minkowski Theory. Encyclopedia of Mathematics and Its Applications 44. Cambridge: Cambridge Univ. Press.
[22]	Schütt, C. (1993). On the affine surface area. Proc. Amer. Math. Soc. 118 1213-1218. · Zbl 0784.52004
[23]	Schütt, C. and Werner, E. (1990). The convex floating body. Math. Scand. 66 275-290. · Zbl 0739.52008
[24]	Thäle, C., Turchi, N. and Wespi, F. (2018). Random polytopes: Central limit theorems for intrinsic volumes. Proc. Amer. Math. Soc. 146 3063-3071. · Zbl 1391.52007 · doi:10.1090/proc/14000
[25]	Tsybakov, A.B. (2004). Optimal aggregation of classifiers in statistical learning. Ann. Statist. 32 135-166. · Zbl 1105.62353 · doi:10.1214/aos/1079120131
[26]	Turchi, N. High-dimensional asymptotics for random polytopes. Ph.D. thesis, Faculty of Mathematics, Ruhr University Bochum. · Zbl 1423.52007 · doi:10.1142/S0219199718500384
[27]	Vu, V. · Zbl 1094.52002 · doi:10.1007/s00039-005-0541-8