Proof of Theorem 4.4, p. 17 — for Q = (1/N)ΣΣ α_ik δ_{ξ_ik}, E^Q[ℓ(ξ)] = (1/N)ΣΣ α_ik ℓ(ξ_ik) ≥ the objective of (13) at a feasible point
ProvedWassDDRO.Extremal.objective13_le_expectdistributionally-robust-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-distribution
Let , let be measurable and never , and let . For every feasible point of program (13), with and ,
The equality is the expectation of under a discrete distribution (the middle equality of the paper's chain on p. 17), and the inequality follows the paper's estimate . Together with the previous milestone it gives the lower bound chain in the proof of Theorem 4.4.
Formalization Note The expectation is the extended expectation of p. 5 (the positive and negative parts are integrated separately, with ). The -th term on either side is when (the convention of p. 14).
Preamble
import Mathlib import Definitions.Def_WassDDRO_Extremal_Setting
Formal statement
namespace WassDDRO.Extremal
/-- Proof of Theorem 4.4, p. 17: for any feasible point (α, q) of (13), the expectation of
ℓ = max_k ℓ_k under Q = (1/N) Σᵢ Σ_k α_ik δ_{ξ_ik} equals (1/N) Σᵢ Σ_k α_ik ℓ(ξ_ik) (the term
being 0 when α_ik = 0), and by ℓ ≥ ℓ_k this dominates the objective (1/N) Σᵢ Σ_k α_ik ℓ_k(ξ_ik)
of (13). -/
theorem objective13_le_expect {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E]
{K N : ℕ} (hN : 0 < N) (Ξ : Set E) (ℓ : Fin K → E → EReal)
(hmeas : ∀ k, Measurable (ℓ k)) (hne_top : ∀ k ξ, ℓ k ξ ≠ ⊤)
(ξhat : Fin N → E) (ε : ℝ)
(α : Fin N → Fin K → ℝ) (q : Fin N → Fin K → E) (h : Feasible13 ε Ξ ξhat α q) :
DupacovaWets.Consistency.expect (discreteQ ξhat α q) (maxLoss ℓ) =
((1 / (N : ℝ) : ℝ) : EReal) * ∑ i, ∑ k, term13 (maxLoss ℓ) (ξhat i) (α i k) (q i k) ∧
objective13 ξhat ℓ α q ≤
DupacovaWets.Consistency.expect (discreteQ ξhat α q) (maxLoss ℓ) := by sorry
end WassDDRO.Extremal
Source
Mohajerin Esfahani & Kuhn, arXiv:1505.05116v3, proof of Theorem 4.4 (second claim), p. 17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.