Proposition 2.2, (2.5), p. 4 — under Assumption A, ∃ γ > 0: limsup (1/N) log[1 − P(Ŝ^ε_N ⊂ 𝒮^ε)] ≤ −γ
ProvedKleywegtSAA.ExpRate.proposition_2_2Let be a nonempty finite set, , and an i.i.d. sample of the random vector such that is measurable and for every . Let and , and let and be the sets of -optimal solutions of and .
Suppose Assumption A holds: for every the moment generating function of is finite in a neighbourhood of . Then for every there is a constant such that
That is, the probability that every -optimal solution of the sample average approximation is an -optimal solution of the true problem tends to one exponentially fast in the sample size.
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 logarithm is ENNReal.log with and the limit superior is taken in the extended reals, so the statement remains correct (with value ) when the event is sure, e.g. when . The constant may depend on , as on the page, where it depends on . The term at is and does not affect the limit superior.
import Mathlib import Definitions.Def_KleywegtSAA_ExpRate_Setting open MeasureTheory ProbabilityTheory Filter Topology
namespace KleywegtSAA.ExpRate
/-- Proposition 2.2 and (2.5), p. 4: under Assumption A, for every `ε ≥ 0` there is `γ > 0` with
`limsup_{N → ∞} (1/N) log[1 − P(Ŝ^ε_N ⊂ S^ε)] ≤ −γ` (with `log 0 = −∞`). -/
theorem proposition_2_2
{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) :
∀ ε : ℝ, 0 ≤ ε → ∃ γ : ℝ, 0 < γ ∧
Filter.limsup (fun N : ℕ => ((1 / (N : ℝ) : ℝ) : EReal) *
ENNReal.log (1 - P {ω | epsSet S hS (sampleObj G W N ω) ε ⊆
epsSet S hS (trueObj G P W) ε})) atTop ≤ ((-γ : ℝ) : EReal) := by sorry
end KleywegtSAA.ExpRate
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.