Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Gaussian estimators and explicit confidence parameters

Definition
LG2021_GaussianEstimators

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

Concrete Gaussian likelihood-ratio estimators and confidence base A=10^6(d+1)(D+1)(n+1), L=32 log A. These are definitions; their mathematical properties are proved separately.

Definition code
import Definitions.Def_LG2021_GaussianSeparation

/-!
Concrete likelihood-ratio estimators from Lattimore–György (COLT 2021), Section 4.
Its radial condition is also used to guard feasible loss queries.
-/

noncomputable section

namespace LG2021.Concentration

/-- Density ratio of the contracted, translated standard Gaussian to the standard Gaussian. -/
def likelihoodRatio {d : ℕ} (lambda : ℝ) (z x : Space d) : ℝ :=
  Real.exp (‖x‖ ^ 2 / 2 - ‖x - lambda • z‖ ^ 2 / (2 * (1 - lambda) ^ 2)) /
    (1 - lambda) ^ d

/-- The common truncation in the scalar and gradient estimators. -/
def truncation {d : ℕ} (lambda r : ℝ) (z x : Space d) : ℝ :=
  if likelihoodRatio lambda z x ≤ Real.exp 1 / (1 - lambda) ^ d ∧
    ‖x‖ ≤ r / (d : ℝ) then 1 else 0

/-- Multiplier of a noisy loss observation in the scalar surrogate estimator. -/
def scalarCoefficient {d : ℕ} (lambda r : ℝ) (z x : Space d) : ℝ :=
  (1 - 1 / lambda + likelihoodRatio lambda z x / lambda) * truncation lambda r z x

/-- Vector multiplier of a noisy observation in the surrogate-gradient estimator. -/
def gradientCoefficient {d : ℕ} (lambda r : ℝ) (z x : Space d) : Space d :=
  (likelihoodRatio lambda z x * truncation lambda r z x / (1 - lambda) ^ 2) •
    (x - lambda • z)

/-- The gradient multiplier tested against a fixed direction. -/
def directionalGradientCoefficient {d : ℕ} (lambda r : ℝ)
    (z η x : Space d) : ℝ :=
  inner ℝ (gradientCoefficient lambda r z x) η

/-- An explicit confidence base for the fixed-dimensional corollary. -/
def parameterBase (d : ℕ) (D : ℝ) (n : ℕ) : ℝ :=
  10 ^ 6 * ((d : ℝ) + 1) * (D + 1) * ((n : ℝ) + 1)

/-- An explicit logarithmic confidence parameter, avoiding an implicit root selection. -/
def parameterLog (d : ℕ) (D : ℝ) (n : ℕ) : ℝ :=
  32 * Real.log (parameterBase d D n)

end LG2021.Concentration
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