Shallow ellipsoid cover
ProvedLG2021.shallow_ellipsoid_coverconvex-geometryellipsoid-method
Let , let be nonsingular, let , and let have Euclidean norm one. Write and
There are a nonsingular matrix and a center such that
and hence
This unrounded shallow-cut cover, including dimension one, provides the volume contraction needed by the convex-bandit ellipsoid argument. It is a specialization of the cited shallow-cut formulas, with an explicit exponential estimate; it does not assert a finite-precision implementation bound.
Preamble
import Mathlib import Definitions.Def_ModernConvex_Ellipsoids_Ellipsoid open Matrix MeasureTheory
Formal statement
theorem LG2021.shallow_ellipsoid_cover {d : ℕ} (hd : 0 < d) (c : Fin d → ℝ)
(B : Matrix (Fin d) (Fin d) ℝ) (hB : B.det ≠ 0)
(p : Fin d → ℝ) (hp : p ⬝ᵥ p = 1) :
∃ (B' : Matrix (Fin d) (Fin d) ℝ) (c' : Fin d → ℝ), B'.det ≠ 0 ∧
{x | ∃ u, u ⬝ᵥ u ≤ 1 ∧ p ⬝ᵥ u ≤ 1 / (2 * (d : ℝ)) ∧ x = c + B *ᵥ u} ⊆
ModernConvex.Ellipsoids.ellipsoid B' c' ∧
|B'.det| ≤ Real.exp (-1 / (8 * ((d : ℝ) + 1))) * |B.det| ∧
volume (ModernConvex.Ellipsoids.ellipsoid B' c') ≤
ENNReal.ofReal (Real.exp (-1 / (8 * ((d : ℝ) + 1)))) *
volume (ModernConvex.Ellipsoids.ellipsoid B c) := by sorrySource
Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics 2, Springer, 1988, equations (3.1.16)–(3.1.17), pp. 71–72, and Lemma (3.3.21), pp. 99–100. The unrounded specialization at shallow-cut parameter 1/(2d) supplies the geometry used in Tor Lattimore and András György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, COLT 2021, PMLR 134:2938–2964, Lemma 3, printed p. 5.