Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

John normalization of explicit stochastic convex-bandit regret

Proved
LG2021.john_normalized_bandit

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

convex-analysisonline-learningprobabilitystochastic-optimization

For each ambient dimension ddd, there is a constant Cd≥0C_d\ge0Cd​≥0 such that every nonempty compact convex set K⊆RdK\subseteq\mathbb R^dK⊆Rd admits, for each horizon n≥2n\ge2n≥2, a measurable randomized bandit policy supported on KKK with expected regret at most Cdnlog⁡2nC_d\sqrt n\log^2 nCd​n​log2n for every continuous convex loss L:K→[0,1]L:K\to[0,1]L:K→[0,1] and every admissible adaptive observation kernel. The probability space and policy precede the unknown loss and observation kernel. The noise is conditionally centered and satisfies the exponential-square moment bound E[exp⁡((Y−L(x))2)∣history,x]≤2\mathbb E[\exp((Y-L(x))^2)\mid\mathrm{history},x]\le2E[exp((Y−L(x))2)∣history,x]≤2 at every legal query.

This is the John-normalized consequence of the explicit universal dimension and diameter bound in Theorem 1 of Lattimore and György (COLT 2021). The proof uses the affine hull of KKK, applies the proved Löwner–Fritz John theorem in that dimension, specializes the explicit rate using the diameter bound of the normalized body, and transports the resulting policy and adaptive kernels through the affine coordinate map. Singleton bodies have zero regret. The theorem does not assert a computational complexity bound.

Preamble
import Mathlib
import Definitions.Def_LG2021_CanonicalBandit
open MeasureTheory BilateralProfitMHR BilateralProfitMHR.CorollaryTransport Set
Formal statement
theorem LG2021.john_normalized_bandit :
    ∀ d : ℕ, ∃ C : ℝ, 0 ≤ C ∧ ∀ n : ℕ, 2 ≤ n →
      ∀ K : Set (EuclideanSpace ℝ (Fin d)), K.Nonempty → IsCompact K → Convex ℝ K →
        ∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω), IsProbabilityMeasure P ∧
          ∃ A : QueryAlg (EuclideanSpace ℝ (Fin d)) Ω, A.IsOn K ∧
            ∀ L : EuclideanSpace ℝ (Fin d) → ℝ,
              ContinuousOn L K → ConvexOn ℝ K L → (∀ x ∈ K, L x ∈ Icc 0 1) →
              ∀ ν : ObsKernel (EuclideanSpace ℝ (Fin d)), ν.IsMeasurable →
                UnitNoiseCond K L ν →
                  expectedCumLoss A P ν
                    (fun x => ENNReal.ofReal (L x - sInf (L '' K))) n ≤
                      ENNReal.ofReal (C * Real.sqrt n * Real.log n ^ 2) := by sorry
Source
John and affine-hull transfer of Tor Lattimore and András György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, COLT 2021, PMLR 134:2938–2964, Theorem 1. The proved library Löwner–Fritz John theorem is reused; see Aharon Ben-Tal and Arkadi Nemirovski, Lectures on Modern Convex Optimization, SIAM, 2001, Theorem 4.9.1, p. 259.

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