Theorem B.1 — finite-sample regret of the oracle mixture
OpenRobustKellyTV.Supplement.theorem_B_1Assume the standing assumptions: , for every , and ; the null is . For let
Let be compact and contained in some with , and let be a probability measure with full support on ( and every relatively open nonempty subset of has positive mass). Let be the oracle mixture (53), , and . Then:
- is a test supermartingale under the conditionally varying null.
- Fix a full-support and let be i.i.d. from . For every measurable with and every , is integrable and
The mixture over pointwise oracles is thus valid against an adaptively varying null, never grows faster in expectation than the oracle rate , and loses at most the log-inverse prior mass of a neighbourhood plus times the worst oracle mismatch over ; choosing a small ball around gives logarithmic regret (Corollary B.2).
Formalization Note Observations are coordinates of under the i.i.d. law of ; is a Bochner integral and integrability of is part of the conclusion. Both suprema are taken in the extended reals, with valued in .
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
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
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