Lemma E.2, (140), p. 104 — E|f_z(π_z)| ≤ 2Δ + 6θ(F, Δ, γ⁻¹; ρ_µ) log²(Rγ ∨ e)/γ + γ·E[f_z²(π_z′)], for R ≥ 1
ProvedStatComplexityDM.Disagreement.decoupling_disagreementLet be a finite index set with a distribution , let and let be a class of functions . Let and , and let . Then for all ,
where are independent draws from and is the disagreement coefficient of Definition 6.3.
The lemma decouples the random function from the random decision : the coupled quantity on the left is controlled by the decoupled second moment on the right at the price of the disagreement coefficient. It is the engine of the posterior-sampling bound of Theorem 6.2.
Formalization Note The infimum over is stated as a bound for every , which is equivalent. The page states the lemma for every ; its proof treats and extends to every by rescaling, which does not cover , so the statement here assumes (Theorem 6.2 uses ). The distribution is a finite weighted family; is the natural logarithm and .
import Mathlib import Definitions.Def_StatComplexityDM_Disagreement_Coefficient
namespace StatComplexityDM.Disagreement
/-- Lemma E.2, (140), p. 104 (arXiv:2112.13487v3), for `R ≥ 1`: for a finitely supported
`µ = Σ_i w i · δ_{z_i}` on an index set, a class `F ⊆ (Π → [−R, R])`, `f_z = fz i ∈ F`, `π_z = πz i`
and `ρ_µ(π) = µ({π_z = π})` (the weighted family `Σ_i w i · δ_{πz i}`), for all `γ > 0` and `Δ > 0`,
`E_{z∼µ}[|f_z(π_z)|] ≤ 2Δ + 6θ(F, Δ, γ⁻¹; ρ_µ) log²(Rγ ∨ e)/γ + γ · E_{z,z′∼µ}[f_z²(π_{z′})]`.
The infimum over `Δ > 0` of (140) is expressed as "for every `Δ > 0`". -/
theorem decoupling_disagreement {ι Act : Type*} [Fintype ι] (F : Set (Act → ℝ)) (R : ℝ)
(hR : 1 ≤ R) (hF : ∀ f ∈ F, ∀ π, |f π| ≤ R) (w : ι → ℝ) (hw : StatComplexityDM.LowerBound.IsDist w)
(fz : ι → Act → ℝ) (hfz : ∀ i, fz i ∈ F) (πz : ι → Act) (γ : ℝ) (hγ : 0 < γ)
(Δ : ℝ) (hΔ : 0 < Δ) :
∑ i, w i * |fz i (πz i)|
≤ 2 * Δ + 6 * disagreementCoeff F Δ γ⁻¹ w πz * Real.log (max (R * γ) (Real.exp 1)) ^ 2 / γ
+ γ * ∑ i, w i * ∑ j, w j * fz i (πz j) ^ 2 := by sorry
end StatComplexityDM.Disagreement
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.