Lemma E.2 (proof), p. 105 — P(∃f ∈ F : |f(π)| > δ, E[f²] ≤ ϵ²) ≤ (ϵ²/δ²)·θ(F, Δ, ε; ρ) for ϵ ≥ ε, δ ≥ Δ
ProvedStatComplexityDM.Disagreement.prob_disagree_le_coeffdecouplingdisagreement-coefficientp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a class of functions , let be a finitely supported distribution on , and let , . Then for all and ,
where is the disagreement coefficient of Definition 6.3 and is independent of .
This is the step of the proof of Lemma E.2 at which the disagreement coefficient enters: it converts the probability of disagreement at every pair of scales into .
Formalization Note The page states the step for the class with and ; the statement here holds for any uniform bound and any positive , which contains the page's case. The bound makes the supremum in finite. Distributions are finitely supported.
Preamble
import Mathlib import Definitions.Def_StatComplexityDM_Disagreement_Coefficient
Formal statement
namespace StatComplexityDM.Disagreement
/-- Proof of Lemma E.2, p. 105 (arXiv:2112.13487v3): from the definition of the disagreement
coefficient, for a class `F` of functions bounded by `R` in absolute value, a finitely supported
`ρ`, `Δ₀ > 0`, `ε₀ > 0`, and all `ε ≥ ε₀`, `δ ≥ Δ₀`,
`P_{π∼ρ}(∃ f ∈ F : |f(π)| > δ ∧ E_{π′∼ρ}[f²(π′)] ≤ ε²) ≤ (ε²/δ²) · θ(F, Δ₀, ε₀; ρ)`. -/
theorem prob_disagree_le_coeff {κ Act : Type*} [Fintype κ] (F : Set (Act → ℝ)) (R : ℝ)
(hF : ∀ f ∈ F, ∀ π, |f π| ≤ R) (ρw : κ → ℝ) (ρpt : κ → Act) (hρ : StatComplexityDM.LowerBound.IsDist ρw)
(Δ₀ ε₀ : ℝ) (hΔ₀ : 0 < Δ₀) (hε₀ : 0 < ε₀) (δ ε : ℝ) (hδ : Δ₀ ≤ δ) (hε : ε₀ ≤ ε) :
distProb ρw ρpt (disagreeEvent F δ ε ρw ρpt)
≤ ε ^ 2 / δ ^ 2 * disagreementCoeff F Δ₀ ε₀ ρw ρpt := by sorry
end StatComplexityDM.Disagreement
Source
arXiv:2112.13487v3, App. E.2.1, proof of Lemma E.2, p. 105 ("Now, from the definition of the disagreement coefficient")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.