§2.2, p. 4 — under Assumption A, P{|ĝ_N(x) − g(x)| ≥ α(ε)/2} ≤ e^{−Nγ_x} + e^{−Nγ′_x}
ProvedKleywegtSAA.ExpRate.deviation_le_two_expAssume the standing setting of §1–§2 and Assumption A. Let . Then for every there are constants and such that for every sample size ,
On the page , and are the values of the rate functions of and at and . Taking and summing over in the union bound yields Proposition 2.2.
Formalization Note The standing setting of §1–§2 is carried as hypotheses: is a nonempty finite set of an arbitrary type, each is measurable, the sample is an independent, identically distributed sequence of measurable maps on a probability space (the paper's is the -st term of a -indexed sequence, and the law of is that of the first term), and for every . The statement is made for every rather than only for ; this is stronger and avoids the nonemptiness of . The constants are real numbers: when a rate function is , any positive constant works.
import Mathlib import Definitions.Def_KleywegtSAA_ExpRate_Setting open MeasureTheory ProbabilityTheory Filter Topology
namespace KleywegtSAA.ExpRate
/-- §2.2, p. 4: under Assumption A, for every `r > 0` (the page's `r = α(ε)/2`) and every
`x ∈ S` there are `γ_x, γ'_x > 0` with `P{|ĝ_N(x) − g(x)| ≥ r} ≤ e^{−Nγ_x} + e^{−Nγ'_x}` for all
`N ≥ 1`. -/
theorem deviation_le_two_exp
{X : Type*} (S : Finset X) (hS : S.Nonempty)
{𝒲 : Type*} [MeasurableSpace 𝒲] (G : X → 𝒲 → ℝ) (hG : ∀ x ∈ S, Measurable (G x))
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(W : ℕ → Ω → 𝒲) (hWm : ∀ n, Measurable (W n)) (hind : iIndepFun W P)
(hid : ∀ n, IdentDistrib (W n) (W 0) P P)
(hint : ∀ x ∈ S, Integrable (fun ω => G x (W 0 ω)) P)
(hA : AssumptionA S G P W) (r : ℝ) (hr : 0 < r) :
∀ x ∈ S, ∃ γx γx' : ℝ, 0 < γx ∧ 0 < γx' ∧ ∀ N : ℕ, 1 ≤ N →
P {ω | r ≤ |sampleObj G W N ω x - trueObj G P W x|} ≤
ENNReal.ofReal (Real.exp (-((N : ℝ) * γx)) + Real.exp (-((N : ℝ) * γx'))) := by sorry
end KleywegtSAA.ExpRate
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.