Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Gaussian separation objects

Definition
LG2021_GaussianSeparation

by sim2000dg · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

Concrete standard Gaussian, normalized Gaussian sphere law, Gaussian surrogate, centered curvature matrix, and explicit radius and Lipschitz parameters for formalized convex-bandit separation.

Definition code
import Mathlib.Probability.Distributions.Gaussian.Multivariate
import Mathlib.Analysis.Calculus.Gradient.Basic

/-!
# Gaussian objects for stochastic convex-bandit separation

These concrete Euclidean Gaussian quantities formalize the separation argument
for Lattimore–György (COLT 2021), Sections 4–5 and Appendix E.
The curvature matrix is expressed using the centered Hermite score `x xᵀ - I`.
-/

noncomputable section

namespace LG2021

open MeasureTheory ProbabilityTheory
open scoped RealInnerProductSpace

abbrev Space (d : ℕ) := EuclideanSpace ℝ (Fin d)

def gaussian (d : ℕ) : Measure (Space d) := stdGaussian (Space d)

instance (d : ℕ) : IsProbabilityMeasure (gaussian d) := by
  unfold gaussian
  infer_instance

instance (d : ℕ) : IsGaussian (gaussian d) := by
  unfold gaussian
  infer_instance

def gaussianMean {d : ℕ} (f : Space d → ℝ) : ℝ := ∫ x, f x ∂gaussian d

def surrogate {d : ℕ} (lambda : ℝ) (f : Space d → ℝ) (z : Space d) : ℝ :=
  gaussianMean f +
    ((∫ x, f ((1 - lambda) • x + lambda • z) ∂gaussian d) - gaussianMean f) / lambda

/-- The uniform sphere law, represented concretely by normalizing a standard Gaussian.
The origin is mapped to zero; in positive dimension this exceptional input has Gaussian mass zero.
-/
def sphereMeasure (d : ℕ) (R : ℝ) : Measure (Space d) :=
  (gaussian d).map (fun x => (R / ‖x‖) • x)

/-- The isotropic Gaussian Lebesgue density with standard deviation `s > 0`. -/
def gaussianDensity {d : ℕ} (s : ℝ) (x : Space d) : ℝ :=
  ((Real.sqrt (2 * Real.pi) * s)⁻¹) ^ d * Real.exp (-‖x‖ ^ 2 / (2 * s ^ 2))

/-- The Hermite-score curvature matrix `E[(XXᵀ - I) f(X)]`. -/
def curvatureMatrix {d : ℕ} (f : Space d → ℝ) : Matrix (Fin d) (Fin d) ℝ :=
  fun i j => ∫ x, (x i * x j - if i = j then 1 else 0) * f x ∂gaussian d

def quadraticForm {d : ℕ} (M : Matrix (Fin d) (Fin d) ℝ) (z : Space d) : ℝ :=
  ∑ i, ∑ j, z i * M i j * z j

def gaussianGap {d : ℕ} (r : ℝ) (f : Space d → ℝ) : ℝ :=
  gaussianMean f - sInf (f '' Metric.closedBall (0 : Space d) r)

def paperRadius (d : ℕ) (L : ℝ) : ℝ := 10 ^ 5 * (d : ℝ) ^ 2 * Real.sqrt (2 * L)

def paperLambda (d : ℕ) (L : ℝ) : ℝ := 1 / (4 * 10 ^ 5 * (d : ℝ) * L)

def paperLipschitz (d : ℕ) (D L : ℝ) : ℝ := (d : ℝ) * D / paperRadius d L

end LG2021
Source
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, Lemma 5 and Appendix E. Separation argument adapted for formalization.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me