Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4 — scalar and directional Gaussian observation bias

Proved
LG2021.Concentration.parameter_observation_bias_bounds

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

convex-analysisgaussian-analysisprobabilitystochastic-optimization

Let d,nd,nd,n be positive integers and D≥0D\ge0D≥0. Set

L=32log⁡ ⁣(106(d+1)(D+1)(n+1)),λ=(4⋅105dL)−1,r=105d22L.L=32\log\!\bigl(10^6(d+1)(D+1)(n+1)\bigr),\qquad \lambda=(4\cdot10^5dL)^{-1},\qquad r=10^5d^2\sqrt{2L}.L=32log(106(d+1)(D+1)(n+1)),λ=(4⋅105dL)−1,r=105d22L​.

Let f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R be KKK-Lipschitz, with ∣f(0)∣≤1|f(0)|\le1∣f(0)∣≤1 and K≤dD/rK\le dD/rK≤dD/r. Let ∥z∥≤r/(2d)\|z\|\le r/(2d)∥z∥≤r/(2d) and ∥η∥≤1\|\eta\|\le1∥η∥≤1. Draw XXX from the standard Euclidean Gaussian, and then draw YYY from a measurable probability kernel κ(X)\kappa(X)κ(X).

Assume that, for Gaussian-almost every xxx, the exponential moment E[exp⁡(Y2/16)∣X=x]\mathbb E[\exp(Y^2/16)\mid X=x]E[exp(Y2/16)∣X=x] is integrable and at most two. On the support of the published Gaussian truncation at (λ,r,z)(\lambda,r,z)(λ,r,z), assume E[Y∣X=x]=f(x)\mathbb E[Y\mid X=x]=f(x)E[Y∣X=x]=f(x). The conditional mean outside that support is unrestricted.

Let Aλ,r,z(X)A_{\lambda,r,z}(X)Aλ,r,z​(X) be the published truncated scalar likelihood-ratio coefficient, and let Bλ,r,z,η(X)B_{\lambda,r,z,\eta}(X)Bλ,r,z,η​(X) be its published directional gradient coefficient. For the Gaussian surrogate

g(z)=E[f(X)]+λ−1(E[f((1−λ)X+λz)]−E[f(X)]),g(z)=\mathbb E[f(X)]+\lambda^{-1}\bigl(\mathbb E[f((1-\lambda)X+\lambda z)]-\mathbb E[f(X)]\bigr),g(z)=E[f(X)]+λ−1(E[f((1−λ)X+λz)]−E[f(X)]),

both numerical bias estimates hold:

∣E[YAλ,r,z(X)]−g(z)∣≤18rn,∣E[YBλ,r,z,η(X)]−Dg(z)[η]∣≤18rn.\bigl|\mathbb E[YA_{\lambda,r,z}(X)]-g(z)\bigr|\le\frac1{8rn},\qquad \bigl|\mathbb E[YB_{\lambda,r,z,\eta}(X)]-Dg(z)[\eta]\bigr|\le\frac1{8rn}.​E[YAλ,r,z​(X)]−g(z)​≤8rn1​,​E[YBλ,r,z,η​(X)]−Dg(z)[η]​≤8rn1​.

The expectations use the Gaussian/kernel joint measure.

This isolates the scalar and gradient bias bounds associated with Lemma 4(a,b) of Lattimore and György (COLT 2021, PMLR 134), using the formal proof's explicit parameter choices and a conditional observation-kernel formulation. Requiring the mean only where the truncation is active permits legal-query fallback outside the active Gaussian region. All coefficients and Gaussian objects are the existing published definitions. This node is a closed analytic ingredient in the dimension-dependent stochastic convex-bandit regret proof.

Preamble
import Mathlib
import Definitions.Def_LG2021_GaussianEstimators

open LG2021 LG2021.Concentration MeasureTheory ProbabilityTheory
Formal statement
theorem LG2021.Concentration.parameter_observation_bias_bounds {d n : ℕ} (hd : 0 < d) (hn : 0 < n)
    {D : ℝ} (hD : 0 ≤ D) {f : Space d → ℝ} {K : NNReal}
    (hf : LipschitzWith K f) (hf0 : |f 0| ≤ 1)
    (hK : (K : ℝ) ≤ paperLipschitz d D (parameterLog d D n))
    (z η : Space d) (hz : ‖z‖ ≤ paperRadius d (parameterLog d D n) / (2 * (d : ℝ)))
    (hη : ‖η‖ ≤ 1) (κ : Kernel (Space d) ℝ) [IsMarkovKernel κ]
    (hobs : ∀ᵐ x ∂gaussian d, Integrable (fun y : ℝ => Real.exp (y ^ 2 / 16)) (κ x) ∧
      (∫ y : ℝ, Real.exp (y ^ 2 / 16) ∂κ x) ≤ 2)
    (hmean : ∀ᵐ x ∂gaussian d,
      truncation (paperLambda d (parameterLog d D n)) (paperRadius d (parameterLog d D n)) z x = 1 →
        (∫ y, y ∂κ x) = f x) :
    |(∫ p : Space d × ℝ, p.2 * scalarCoefficient (paperLambda d (parameterLog d D n))
        (paperRadius d (parameterLog d D n)) z p.1 ∂((gaussian d) ⊗ₘ κ)) -
      surrogate (paperLambda d (parameterLog d D n)) f z| ≤
        1 / (8 * paperRadius d (parameterLog d D n) * (n : ℝ)) ∧
    |(∫ p : Space d × ℝ, p.2 * directionalGradientCoefficient (paperLambda d (parameterLog d D n))
        (paperRadius d (parameterLog d D n)) z η p.1 ∂((gaussian d) ⊗ₘ κ)) -
      fderiv ℝ (surrogate (paperLambda d (parameterLog d D n)) f) z η| ≤
        1 / (8 * paperRadius d (parameterLog d D n) * (n : ℝ)) := by sorry
Source
Tor Lattimore and András György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, Proceedings of the 34th Conference on Learning Theory, Proceedings of Machine Learning Research 134:2938–2964, 2021. Lemma 4(a,b), printed p. 7, and Appendix D, printed pp. 20–22. Explicit numerical parameter and conditional observation-kernel formulation.

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