 f k andf k as convex hulls that on the domain Ω
Hence, we conclude that with high probability. Now, using Theorem 15 and Markov's inequality, we also know that with probability of at least 19 20. Conditioned on this event, and using the fact that f k is uniformly bounded by 1, we obtain On the intersection of the two events defined above, which has probability at least 9 10, we have Deriving the theorem Since we have three events each of which hold with probability of at least 9/10, then the intersection of these events is not empty. Therefore, an f k satisfying all the desired properties exists, and the theorem follows.
By taking ǫ = 1/2, and choosing C to be large enough, we conclude that for any particular △ i, with probability at least 1−n −(3d+1). Taking the union bound over all k(n) triangles, the claim follows.
The main step is the following lemma, which shows that for any given simplex △ i, if we draw Cd log n points from the uniform distribution on △ i for sufficiently large C, then there exists some subset S of these points whose convex hull P covers almost all of the simplex and can also be triangulated by a polylogarithmic number of simplices whose vertices lie in S.
Lemma 17. Let S ⊂ R d be a simplex, and m ≥ C 3 d log(n), for some large enough C 3 ≥ 0. Let Y 1,..., Y m ∼ P S. Then, with probability of at least 1 − n −3d there exists a set A of simplices contained in S with disjoint interiors of cardinality |A| ≤ C d log(m) d−1 such that Proof. For each s ∈ {0, 1,..., d − 1} and P a polytope, we let f s (P ) denote the number of s-dimensional faces of P. We need the following result, which was first proven in (Dwyer, 1988); for more details see the recent paper Reitzner et al. (2019).
Theorem 18. Let S ⊂ R d be a simplex, and let Y 1,..., Y m ∼ P S. Then, S m = conv(Y 1,..., Y m ) is a simplicial polytope with probability 1, and the following holds: This theorem does not give us what we need directly, since it treats only expectation while we require high-probability bounds. (To the best of our knowledge, sub-Gaussian concentration bounds are not known for the random variables f d−1 (P m ), P(S \ S m ) when S is a simplex, cf. (Vu, 2005).) This necessitates using a partitioning strategy. We divide our Y 1,..., Y m into C 1 d log(n) blocks, for C 1 to be chosen later, each with m(n) := m C1d log(n) samples drawn uniformly from △. Let P 1,..., P B be the convex hulls of the points in each block, each of which are independent realizations of the random polytope S m(n). For each P i, Markov's inequality and a union bound yield that with probability at least 1 3, and Since there are C 1 d log(n) independent P i, at least one of them will satisfy these conditions with probability 1 − 2 3 C1d log n, and choose C 1 so that this is at least 1 − n −3d.
Conditioned on the existence of P i satisfying (20) and (21), we take one such P i and triangulate it by picking any point among the original Y 1,..., Y m lying in the interior of P i and connecting it to each of the (d − 1)-simplices making up the boundary of P i. The set A is simply the set of d-simplices in this triangulation. Now, to obtain Lemma 11, we condition on the event of Lemma 16 and apply Lemma 17 to each △ i such that P(△ i ) ≥ Cd log(n)/n, with the Y 1,..., Y m taken to be the points of X n+1,..., X 2n drawn from P which fall inside of △ i. Using the fact that P n (△ i ) ≥ 0.5P(△ i ), we see that m ≥ Cd log n for each △ i, so Lemma 17 is in fact applicable. In addition, the bounds on the cardinality of S i X and on the volume of △ i left uncovered by the simplices in S i X follow immediately by substituting cP(△ i ) for m in the conclusions of Lemma 17. For i such that P(△ i ) ≤ Cd log(n)/n, we take S i X to be the empty set.

Proof of Lemma 13
We will use the following auxiliary estimator for the mean of a random variable that is presented in (Devroye et al., 2016): Lemma 19. Let δ ∈ (0, 1) and let Z 1,..., Z k be i.i.d. samples from a distribution on R with finite variance σ 2 Z. There exists an estimatorf δ : R k → R with a runtime of O(k), such that with probability of at least 1 − δ, We will use the following notations: g p denotes the L p (U (△)) norm of some simplex △ ⊂ B d. Our first step is to estimate the L 1 norm of any convex function g. In the following sub-sub-section, we will prove Lemma 12 that appears above.
The final step will be to estimate the L 2 norm of g under the assumptions of Lemma 13, by using the Lemma 12 and the claim of Lemma 13 will follow.

Proof of Lemma 12
We will use the following facts, which can be extracted from the statements and proofs of (Gao and Wellner, 2017, Lemmas 2.6-2.7) that regards the regular simplex with radius one S ⊂ B d, also for each t ∈ [0, 1], denote by S t := (1 − t)S.
Lemma 20. Let g : S → R be a convex function. Then, the following holds: Using the lemma above, the almost immediate corollary follows: Corollary 21. For any l ∈ (0, 1), the exists exists a constant δ = max{c(l, d), c/d} such that g restricted to S δ is uniformly bounded by C d s −(d+1) g 1, and moreover S\S δ |g − |dU (x) ≤ l g 1.
Now, we will present our following result that may have independent of interest: Define the measure where we define B y to be the largest ball centered on y which is contained in S. Next, for any simplex △, we can define a measure p △ (x) := p S (T −1 x), where T is the affine transformation such that △ = T S.
] be a convex M g L1(U(△)) Lipschitz such that argmin w affine g − w L2(U(△)) = 0. Then, the following holds: In addition, for every affine function w, Moreover, where v d is the volume of the unit ball in dimension d, and there exists an efficient algorithm to compute p △ (x) for any x ∈ △.
We will prove this lemma below, note that by changing of variables and the fact that L 1 scales with the determinant of T such that S = T △, it is enough to prove this result for the regular simplex S. The observation that leads to this measure is based on the following idea: If g is a convex function with zero mean and barycenter, and intuitively, such functions must be negative near the barycenter of △ and positive near the boundary. One can therefore hope that the integral of g in a neighborhood of the boundary gives a lower bound on the L 1 -norm of g.
Using the above results we can estimate the L 1 norm g : △ → [−1, 1]. First, we define the unique affine transformation such that T △ = S. Also, we define the shrunken simplex △ δ, where △ δ := T −1 (T △) δ(l,d), where l = 1/10 and δ(l, d) is defined in Corollary 21. There are few cases that we are going to consider in this proof.
The first case is the following: g½ △\△ δ 1 ≥ 4 −1 g 1, i.e. the L 1 norm of g is attained on the shell outside of △ δ. Using Corollary 21, we know that Therefore it is enough to estimate the mean (scaled by U (△ \ △ δ )) of the r.v. g(X) where X ∼ U (△ \ △ δ ). It can be done using the samples that lie in this set. Using Lemma 19 above, we conclude that using these samples we have an estimatef (1) with probability of at least 1 − δ such that where we used that fact that U (△ \ △ δ ) ≥ c d.
Using half of the samples that fall into △ δ, we may apply Lemma 8, that gives usŵ g such that with probability 1 − δ log(2/δ) m Since, we can easily estimatef (