Nearby simplex volume (Lattimore–György, Lemma 7)
ProvedLG2021.nearby_simplex_volumebanditconvex-geometryvolume
Let and let be convex and contain the closed Euclidean unit ball. Suppose bounds every distance between two points of , and . For each there are distinct vertices with and , satisfying
This is the nearby simplex used in the bandit stage-count argument. The source slice, number of vertices, homothety, and volume lower bound are preserved. The proof uses a triangular determinant for the base simplex rather than a maximization over regular simplices.
Preamble
import Mathlib open MeasureTheory Set
Formal statement
theorem LG2021.nearby_simplex_volume {d : ℕ} (hd : 0 < d)
{K : Set (EuclideanSpace ℝ (Fin d))} (hcv : Convex ℝ K)
(hball : Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) 1 ⊆ K)
{D δ : ℝ} (hD : 0 < D) (hδ : 0 < δ) (hδD : δ ≤ D)
(hdiam : ∀ x ∈ K, ∀ y ∈ K, dist x y ≤ D)
{x : EuclideanSpace ℝ (Fin d)} (hx : x ∈ K) :
∃ v : Fin (d + 1) → EuclideanSpace ℝ (Fin d), Function.Injective v ∧ v 0 = x ∧
(∀ i, v i ∈ K) ∧ (∀ i, dist x (v i) ≤ δ) ∧
ENNReal.ofReal ((δ / D)^d * (Real.sqrt (3 / 4))^(d - 1) / (2 * (d.factorial : ℝ))) ≤
volume (convexHull ℝ (range v)) := by sorrySource
Tor Lattimore and András György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, Proceedings of the 34th Conference on Learning Theory (COLT 2021), Proceedings of Machine Learning Research 134:2938–2964, 2021, Appendix B, Lemma 7, printed p. 16.