§2.1, proof of Proposition 2.1, p. 3 — if δ_N < α(ε)/2 then Ŝ^ε_N ⊂ 𝒮^ε
ProvedKleywegtSAA.ExpRate.subset_of_devMax_ltp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sample-average-approximation
Let be a nonempty finite set, the true objective and the sample average function along a realization , , and suppose is nonempty so that of (2.3) is defined. For every sample size and every realization ,
This is the deterministic core of Propositions 2.1 and 2.2: once the sample average is uniformly within of the true objective, every -optimal solution of the SAA problem is -optimal for the true problem.
Formalization Note The implication is pointwise in and ; it needs no independence, integrability or measurability, so those standing hypotheses are omitted (a stronger statement).
Preamble
import Mathlib import Definitions.Def_KleywegtSAA_ExpRate_Setting open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace KleywegtSAA.ExpRate
/-- Proof of Proposition 2.1, p. 3 (restated p. 4): if `δ_N < α(ε)/2` then `Ŝ^ε_N ⊂ S^ε`.
Deterministic in the realization `ω` and the sample size `N`. -/
theorem subset_of_devMax_lt {X : Type*} (S : Finset X) (hS : S.Nonempty)
{𝒲 : Type*} (G : X → 𝒲 → ℝ)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) (W : ℕ → Ω → 𝒲)
(ε : ℝ) (hε : 0 ≤ ε) (hne : (nonOptSet S hS (trueObj G P W) ε).Nonempty) :
∀ (N : ℕ) (ω : Ω), devMax S hS G P W N ω < alpha S hS (trueObj G P W) ε hne / 2 →
epsSet S hS (sampleObj G W N ω) ε ⊆ epsSet S hS (trueObj G P W) ε := by sorry
end KleywegtSAA.ExpRate
Source
Kleywegt & Shapiro, The sample average approximation method for stochastic discrete optimization, preprint (two-author version, sha256 56657748…), p. 3, proof of Proposition 2.1 (restated p. 4, §2.2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.