Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem B.1 — finite-sample regret of the oracle mixture

Open
RobustKellyTV.Supplement.theorem_B_1

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

e-valuesp2o-gran-per-chapterp2o-plan-paperp2o-v1robust-hypothesis-testingsequential-testingtest-supermartingale

Assume the standing assumptions: d≥2d\ge2d≥2, Pi>0P_i>0Pi​>0 for every iii, and 0<ϵ0<1−min⁡iPi0<\epsilon_0<1-\min_iP_i0<ϵ0​<1−mini​Pi​; the null is P0=BTV(P,ϵ0)\mathcal P_0=B_{\mathrm{TV}}(P,\epsilon_0)P0​=BTV​(P,ϵ0​). For m,δ>0m,\delta>0m,δ>0 let

Km,δ={U∈Δd: min⁡iUi≥m, DTV(U,P)≥ϵ0+δ}.\mathcal K_{m,\delta}=\{U\in\Delta_d:\ \min_iU_i\ge m,\ D_{\mathrm{TV}}(U,P)\ge\epsilon_0+\delta\}.Km,δ​={U∈Δd​: imin​Ui​≥m, DTV​(U,P)≥ϵ0​+δ}.

Let A⊂Δd∖P0\mathcal A\subset\Delta_d\setminus\mathcal P_0A⊂Δd​∖P0​ be compact and contained in some Km,δ\mathcal K_{m,\delta}Km,δ​ with m,δ>0m,\delta>0m,δ>0, and let Π\PiΠ be a probability measure with full support on A\mathcal AA (Π(A)=1\Pi(\mathcal A)=1Π(A)=1 and every relatively open nonempty subset of A\mathcal AA has positive mass). Let BnΠ=∫A∏t=1nEU(Xt) Π(dU)B^\Pi_n=\int_{\mathcal A}\prod_{t=1}^nE_U(X_t)\,\Pi(dU)BnΠ​=∫A​∏t=1n​EU​(Xt​)Π(dU) be the oracle mixture (53), Γ(S)=inf⁡R∈P0DKL(S∥R)\Gamma(S)=\inf_{R\in\mathcal P_0}D_{\mathrm{KL}}(S\|R)Γ(S)=infR∈P0​​DKL​(S∥R), and h(S,U)=∑iSilog⁡EU(i)h(S,U)=\sum_iS_i\log E_U(i)h(S,U)=∑i​Si​logEU​(i). Then:

  1. (BnΠ)(B^\Pi_n)(BnΠ​) is a test supermartingale under the conditionally varying null.
  2. Fix a full-support S∈AS\in\mathcal AS∈A and let X1,X2,…X_1,X_2,\dotsX1​,X2​,… be i.i.d. from SSS. For every measurable V⊆AV\subseteq\mathcal AV⊆A with Π(V)>0\Pi(V)>0Π(V)>0 and every nnn, log⁡BnΠ\log B^\Pi_nlogBnΠ​ is integrable and
0≤nΓ(S)−ESlog⁡BnΠ≤log⁡1Π(V)+nsup⁡U∈V{Γ(S)−h(S,U)}≤log⁡1Π(V)+nsup⁡U∈VDKL(S∥U).0\le n\Gamma(S)-\mathbb E_S\log B^\Pi_n\le\log\frac1{\Pi(V)}+n\sup_{U\in V}\{\Gamma(S)-h(S,U)\}\le\log\frac1{\Pi(V)}+n\sup_{U\in V}D_{\mathrm{KL}}(S\|U).0≤nΓ(S)−ES​logBnΠ​≤logΠ(V)1​+nU∈Vsup​{Γ(S)−h(S,U)}≤logΠ(V)1​+nU∈Vsup​DKL​(S∥U).

The mixture over pointwise oracles is thus valid against an adaptively varying null, never grows faster in expectation than the oracle rate Γ(S)\Gamma(S)Γ(S), and loses at most the log-inverse prior mass of a neighbourhood VVV plus nnn times the worst oracle mismatch over VVV; choosing VVV a small ball around SSS gives logarithmic regret (Corollary B.2).

Formalization Note Observations are coordinates of ω:N→Fin d\omega:\mathbb N\to\mathrm{Fin}\,dω:N→Find under the i.i.d. law of SSS; ES\mathbb E_SES​ is a Bochner integral and integrability of log⁡BnΠ\log B^\Pi_nlogBnΠ​ is part of the conclusion. Both suprema are taken in the extended reals, with DKLD_{\mathrm{KL}}DKL​ valued in [0,∞][0,\infty][0,∞].

Differences from the source:

  • reading: test supermartingale under the conditionally varying null (undefined in the paper) → M_0 = 1, M ≥ 0, and a supermartingale for the prefix filtration under every probability law on sequences whose one-step conditional laws lie in P0 almost surely; reason: the standard sequential composite null, the strongest natural reading, and the one the paper's proof (each fixed-U factor is in E0, then Tonelli) establishes
  • encoding: Π with full support on A → Π a probability measure with Π(A) = 1 and every relatively open nonempty subset of A of positive Π-mass; reason: the definition of the support of a measure on the compact set A
  • encoding: i.i.d. observations X_1, X_2, … from S → the infinite product law of S on ℕ → Fin d, with X_t the coordinate t − 1; reason: every process is a function of the observed prefix, so no instance changes
  • encoding: E_S log B^Π_n → Bochner integral, with integrability of log B^Π_n added as a conjunct of the conclusion; reason: rules out the junk value 0 of a non-integrable integral; log B^Π_n is bounded on A ⊆ K_{m,δ}, so this adds no content beyond the paper's
  • encoding: real suprema over V and log(1/Π(V)) → suprema in EReal (D_KL in [0, ∞], coerced), log(1/Π(V)) as Real.log (1 / Π(V).toReal); reason: no junk value of a real supremum; both suprema are finite on A ⊆ K_{m,δ}, and Π(V) ∈ (0, 1]
  • encoding: n unspecified → every n ∈ ℕ, including n = 0; reason: at n = 0, B^Π_0 = 1 and the chain reads 0 ≤ 0 ≤ log(1/Π(V)), which holds, so no instance changes
Preamble
import Mathlib
import Definitions.Def_RobustKellyTV_kl
import Definitions.Def_RobustKellyTV_oracleE
import Definitions.Def_RobustKellyTV_seqLaw
import Definitions.Def_RobustKellyTV_Supplement_oracleMixture
import Definitions.Def_RobustKellyTV_Supplement_IsTestSupermartingaleCV

open MeasureTheory
open scoped ENNReal
Formal statement
namespace RobustKellyTV.Supplement

/-- **Theorem B.1** (Finite-sample regret of the oracle mixture). A. Saha, A. Ramdas, *Beyond
least-favorable distribution pairs: asymptotically instance-optimal robust hypothesis testing*,
arXiv:2611.02130v1, Appendix B, Theorem B.1, eq. (54), p.35 (proof p.36).

Let `A ⊂ ∆_d \ P0` be compact, contained in some `K_{m,δ}`, and let `Π` be a probability measure
with full support on `A`. The process `(B^Π_n)` is a test supermartingale under the conditionally
varying null. Fix a full-support `S ∈ A`. For every measurable `V ⊆ A` with `Π(V) > 0`,
`0 ≤ nΓ(S) − E_S log B^Π_n ≤ log(1/Π(V)) + n sup_{U∈V} {Γ(S) − h(S, U)}
  ≤ log(1/Π(V)) + n sup_{U∈V} D_KL(S‖U)`.

**Formalization Note.** Standing assumptions (p.6) are bundled in `σ : Setting d`.
`K_{m,δ} = {U ∈ ∆_d : minᵢ Uᵢ ≥ m, D_TV(U, P) ≥ ϵ0 + δ}` (p.22) is written out, with
`minᵢ Uᵢ ≥ m` as `∀ i, m ≤ Uᵢ`. "Full support on `A`": `Π(A) = 1` and every relatively open
nonempty subset of `A` has positive mass. `E_S` is the Bochner integral under the i.i.d. law of
`S` on `ℕ → Fin d`, and integrability of `log B^Π_n` is a conjunct, so a junk value `0` cannot
satisfy the bounds. Both suprema are taken in the extended reals (`EReal`; `D_KL` is `[0, ∞]`-valued
and coerced), so no junk value of a real supremum enters; `n` ranges over all of `ℕ`. -/
theorem theorem_B_1 {d : ℕ} (σ : Setting d) (A : Set (Fin d → ℝ)) (hAc : IsCompact A)
    (hAnull : A ⊆ stdSimplex ℝ (Fin d) \ nullBall σ)
    (hAK : ∃ m δ : ℝ, 0 < m ∧ 0 < δ ∧
      A ⊆ {U | U ∈ stdSimplex ℝ (Fin d) ∧ (∀ i, m ≤ U i) ∧ σ.ε₀ + δ ≤ tv U σ.P})
    (prior : Measure (Fin d → ℝ)) [IsProbabilityMeasure prior] (hprior : prior A = 1)
    (hsupp : ∀ O : Set (Fin d → ℝ), IsOpen O → (O ∩ A).Nonempty → 0 < prior (O ∩ A)) :
    IsTestSupermartingaleCV σ (oracleMixture σ prior A) ∧
    ∀ S : stdSimplex ℝ (Fin d), (S : Fin d → ℝ) ∈ A → (∀ i, 0 < (S : Fin d → ℝ) i) →
    ∀ V : Set (Fin d → ℝ), MeasurableSet V → V ⊆ A → 0 < prior V → ∀ n : ℕ,
      Integrable (fun ω => Real.log (oracleMixture σ prior A n ω)) (seqLaw S) ∧
      0 ≤ (n : ℝ) * Gamma σ S - ∫ ω, Real.log (oracleMixture σ prior A n ω) ∂(seqLaw S) ∧
      (((n : ℝ) * Gamma σ S - ∫ ω, Real.log (oracleMixture σ prior A n ω) ∂(seqLaw S) : ℝ) :
          EReal) ≤
        ((Real.log (1 / (prior V).toReal) : ℝ) : EReal) +
          (n : EReal) * (⨆ U ∈ V, ((Gamma σ S - hRet σ S U : ℝ) : EReal)) ∧
      ((Real.log (1 / (prior V).toReal) : ℝ) : EReal) +
          (n : EReal) * (⨆ U ∈ V, ((Gamma σ S - hRet σ S U : ℝ) : EReal)) ≤
        ((Real.log (1 / (prior V).toReal) : ℝ) : EReal) +
          (n : EReal) * ((⨆ U ∈ V, kl S U : ℝ≥0∞) : EReal) := by sorry

end RobustKellyTV.Supplement
Source
A. Saha, A. Ramdas, Beyond least-favorable distribution pairs: asymptotically instance-optimal robust hypothesis testing, arXiv:2611.02130v1, Appendix B, Theorem B.1, eq. (54), p.35 (proof p.36); setting of Appendix B, p.35; K_{m,δ}, p.22

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