Theorem 6 — robust lower bound on by perturbed empirical distributions, on Borel
ProvedWassersteinDRO.Duality.robust_lower_bound_v2Let with an arbitrary norm (a finite-dimensional real normed space) and its Borel -algebra, let be closed, , , and let be the empirical distribution of training samples . For any measurable, upper semicontinuous, -integrable loss the worst-case risk is bounded below by the worst-case empirical loss over all perturbation matrices in an -norm uncertainty set:
Both sides are taken in : the supremum is for an unbounded constraint set and if no perturbation is feasible (e.g. ).
Formalization Note. The retired version was false because its -algebra on was a free parameter: with the trivial -algebra no non-constant loss is integrable under any probability measure, so the integrability-guarded worst-case risk was the supremum of the empty family, , while the left-hand side was a real number. The new statement does the following differently. (i) is a finite-dimensional real normed space (the paper's with an arbitrary norm) carrying its Borel -algebra ([FiniteDimensional ℝ E] [BorelSpace E]); the retired version quantified over every MeasurableSpace E, including -algebras unrelated to the norm, for which the Wasserstein cost is a lower integral and non-constant losses are integrable under no measure. (ii) The worst-case risk is the paper's with the paper's p. 2 convention for non-integrable losses (worstCaseRisk/nominalRisk v2, valued in ) instead of a supremum that silently discarded every under which is not integrable. Standing assumptions made explicit: closed (p. 6); a probability distribution; and (p. 3, 6); the loss is measurable (p. 1) and, by Assumption 1 (p. 9, "tacitly assumed to hold throughout the rest of the paper"), upper semicontinuous and -integrable. For a real-valued and the empirical the integrability is automatic and is carried only for fidelity to Assumption 1; matches the paper's indexing . Losses are taken real-valued, a special case of the paper's extended-real-valued losses that the retired version already made. No correction to the printed source.
import Mathlib import Definitions.Def_WassersteinDRO_Duality_worstCaseRisk_v2 import Definitions.Def_WassersteinDRO_Duality_empiricalDistribution open MeasureTheory
namespace WassersteinDRO.Duality
/-- Theorem 6 (Robust lower bound), Kuhn, Mohajerin Esfahani, Nguyen & Shafieezadeh-Abadeh,
*Wasserstein Distributionally Robust Optimization*, INFORMS TutORials 2019
(arXiv:1908.08729v2), p. 10, eq. (9): if `PN` is the empirical distribution of the training
samples `ξ̂₁,…,ξ̂_N`, then the worst-case risk (6) of any fixed loss function `ℓ ∈ L` is
bounded below by the worst-case empirical loss over all perturbation matrices
`Θ = (θ₁,…,θ_N)` in an `L_{p,1}`-norm uncertainty set:
`Rε,p(PN,ℓ) ≥ sup { (1/N) Σᵢ ℓ(ξ̂ᵢ+θᵢ) : θᵢ ∈ E, ξ̂ᵢ+θᵢ ∈ Ξ ∀i, (1/N) Σᵢ ‖θᵢ‖^p ≤ ε^p }`.
Setting (p. 3, 6, 9): `E` is `ℝ^m` with an arbitrary norm (finite-dimensional real normed
space) with its Borel σ-algebra; `Ξ ⊆ E` is closed; `p ∈ [1,∞)`, `ε ≥ 0`; `N ≥ 1` (the paper
indexes `i ∈ [N]`). The loss satisfies the standing conventions: measurable (p. 1) and, by
Assumption 1 (p. 9), upper semicontinuous and `PN`-integrable (automatic for a real-valued
`ℓ` and the empirical `PN`, but carried for fidelity). The finite supremum is taken in `EReal`
so that an unbounded constraint set gives `+∞` and an infeasible one (e.g. `Ξ = ∅`) gives
`-∞ = sup ∅`, exactly as in the paper.
Corrected from the retired `robust_lower_bound`: the σ-algebra was a free `[MeasurableSpace E]`
(with the trivial σ-algebra no non-constant `ℓ` was integrable under any `Q`, so the guarded
worst-case risk collapsed to `-∞`), `E` was not finite-dimensional, measurability/upper
semicontinuity of `ℓ` were missing, and the worst-case risk dropped non-integrable `Q` instead
of using the paper's convention (now `worstCaseRisk`/`nominalRisk` v2). -/
theorem robust_lower_bound_v2 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E]
(ε p : ℝ) (hε : 0 ≤ ε) (hp : 1 ≤ p) (Ξ : Set E) (hΞcl : IsClosed Ξ)
{N : ℕ} (hN : 0 < N) (ξhat : Fin N → E)
(ℓ : E → ℝ) (hℓm : Measurable ℓ) (hℓusc : UpperSemicontinuous ℓ)
(hℓ : Integrable ℓ (empiricalDistribution ξhat)) :
(⨆ (θ : Fin N → E)
(_ : ∀ i, ξhat i + θ i ∈ Ξ)
(_ : (∑ i, ‖θ i‖ ^ p) / (N : ℝ) ≤ ε ^ p),
(((∑ i, ℓ (ξhat i + θ i)) / (N : ℝ) : ℝ) : EReal))
≤ worstCaseRisk ε p Ξ (empiricalDistribution ξhat) ℓ := by sorry
end WassersteinDRO.Duality