Lemma 2.4 (b), p. 6, (2.12) — w.p.1, sup_x ℋ(∂f̂_N(x), ∂f(x)) → 0
ProvedSAARate.Polyhedral.lemma_2_4_bhausdorff-distancep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sample-average-approximationstochastic-programmingsubdifferential
Let be finite with probability measure , let every be piecewise linear and convex on , and let be an i.i.d. sample from . With , and as in the mission's setting and the Hausdorff distance between subsets of , with probability one
The subdifferentials of the sample average function converge to those of the true expected value function uniformly over the whole space. This is the route to Theorem 2.3 through optimality conditions.
Formalization Note The Hausdorff distance is Mathlib's extended Hausdorff distance (values in ), and the supremum is taken in . The statement concerns one i.i.d. sequence: "w.p.1" means for almost every sample path.
Preamble
import Mathlib import Definitions.Def_SAARate_Polyhedral_Setting import Definitions.Def_ShorNonsmooth_Subdiff_Subdifferential open MeasureTheory ProbabilityTheory Filter Topology ShorNonsmooth.Subdiff
Formal statement
namespace SAARate.Polyhedral
/-- Lemma 2.4 (b), p. 6, (2.12): under (i) and (ii), with probability one the subdifferentials
`∂f̂_N(x)` converge to `∂f(x)` uniformly in `x ∈ ℝ^m`, in the Hausdorff distance. -/
theorem lemma_2_4_b {m : ℕ} {Ω : Type*} [Fintype Ω] [MeasurableSpace Ω]
[MeasurableSingletonClass Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(h : SAARate.Sharp.E m → Ω → ℝ) (hpl : ∀ ω, IsPLConvex (fun x => h x ω))
{S : Type*} [MeasurableSpace S] (Q : Measure S) [IsProbabilityMeasure Q]
(ω : ℕ → S → Ω) (hω : SAARate.SharpLD.IsIIDSample Q P ω) :
∀ᵐ s ∂Q, Tendsto (fun N : ℕ => ⨆ x : SAARate.Sharp.E m,
Metric.hausdorffEDist (subdifferential Set.univ (SAARate.Sharp.saaObj h (fun j => ω j s) N) x)
(subdifferential Set.univ (SAARate.Sharp.expectedObj P h) x)) atTop (𝓝 0) := by sorry
end SAARate.Polyhedral
Source
Shapiro & Homem-de-Mello, On Rate of Convergence of Optimal Solutions of Monte Carlo Approximations of Stochastic Programs, preprint (SPEPS copy, edoc.hu-berlin.de), p. 6, Lemma 2.4 (b), (2.12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.