Theorem 22(a) — finite sample guarantee II: with the Theorem-21 constant
ProvedWassersteinDRO.Guarantees.finite_sample_guarantees_ii_v2Fix a dimension , a mean vector , a covariance matrix , and light-tail parameters , . There is a constant , depending only on — the constant of the concentration inequality of Theorem 21, eq. (28) — such that the following holds for every probability distribution on with mean vector , covariance matrix and , every sample size , every closed set containing the support of , and every class of measurable upper semicontinuous loss functions : for all and all ,
where is the law of the i.i.d. training samples , and are the mean vector and covariance matrix of the empirical distribution , is the true risk, and is the Gelbrich risk (18) over the Gelbrich hull (Definition 2) of distributions supported on with finite second moments whose mean and covariance lie in the Gelbrich uncertainty set ; risks are extended-real with the paper's p. 2 convention. In words: with probability at least over the training sample, the Gelbrich risk is an upper confidence bound on the true risk uniformly over all admissible losses. (Part (b) of Theorem 22, eq. (29b), on an optimizer of the Gelbrich risk optimization problem (19), is not part of this statement.)
Formalization Note. The retired version was false because the constant of was a free universally quantified real rather than the constant delivered by Theorem 21, so the radius could be fixed independently of the scale of (with , , the Gelbrich ball misses the truth with probability ). The new statement does the following differently. (i) is existentially quantified after and before , , , , , , exactly as in Theorem 21 ("depends on only through and ") and as in the milestone concentration_inequalities_ii; the guarantee holds with the same constant. (ii) The Gelbrich hull now requires finite second moments (gelbrichHull v2), as Definition 2 presupposes, instead of admitting measures without a covariance matrix through a junk-valued integral; the Gelbrich risk and the true risk are the paper's extended-real expectations with its p. 2 convention (gelbrichRisk/nominalRisk v2) instead of a supremum discarding non-integrable , so the retired extra hypothesis "every is -integrable", which the source does not state, is dropped. (iii) Standing assumptions made explicit: is closed and contains the support of (p. 6); every is measurable (p. 1) and upper semicontinuous (Assumption 1, p. 9, tacitly in force throughout); -integrability of Assumption 1 is automatic for the empirical distribution and not repeated; ; are the moments of the empirical distribution (the paper's definition of the sample mean and sample covariance, Section 4.3); is the Euclidean norm of EuclideanSpace ℝ (Fin m), as in (28); the light-tail condition is written as integrability plus the bound on the integral; the event's probability is the (outer) measure of the set under . 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.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_WassersteinDRO_Guarantees_meanVector import Definitions.Def_WassersteinDRO_Guarantees_covarianceMatrix import Definitions.Def_WassersteinDRO_Guarantees_empiricalDistribution import Definitions.Def_WassersteinDRO_Guarantees_nominalRisk_v2 import Definitions.Def_WassersteinDRO_Guarantees_gelbrichRisk_v2 import Definitions.Def_WassersteinDRO_Guarantees_sampleMeasure open MeasureTheory
namespace WassersteinDRO.Guarantees
/-- Theorem 22 (Finite sample guarantees II), part (a), Kuhn, Mohajerin Esfahani, Nguyen &
Shafieezadeh-Abadeh, *Wasserstein Distributionally Robust Optimization*, INFORMS TutORials
2019 (arXiv:1908.08729v2), p. 23–24, eq. (29a): assume all conditions of Theorem 21 hold and
`ε_N(η) = log(c/η)/√N` as in (28). Then for all `η ∈ (0,1)` and `ε ≥ ε_N(η)`,
`P^N { R(P,ℓ) ≤ Rε(µ̂,Σ̂,ℓ) ∀ℓ ∈ L } ≥ 1 - η`. (Part (b), eq. (29b), concerns an optimizer
of the Gelbrich risk optimization problem (19) and is not part of this statement.)
The conditions of Theorem 21 (p. 23): the unknown true distribution `P` on `ℝ^m` has mean
vector `µ` and covariance matrix `Σ`, and is light-tailed, `E_P[exp(‖ξ‖₂^α)] ≤ A` for some
`α > 2`, `A > 0`; the constant `c > 1` of (28) "depends on `P` only through `µ, Σ, α, A` and
`m`". Accordingly `c` is existentially quantified *after* `(m, µ, Σ, α, A)` and *before* `P`,
the sample size, the support set and the loss class: one constant serves every `P` sharing
these parameters, and the guarantee holds with the same `c` as the concentration inequality
of Theorem 21 (`concentration_inequalities_ii`). Standing framework (p. 1, 6, 9): `Ξ` is a
closed set containing the support of `P` (`P Ξᶜ = 0`); every `ℓ ∈ L` is measurable and
(Assumption 1, tacitly in force throughout) upper semicontinuous; `P̂_N`-integrability is
automatic for the empirical distribution. `µ̂ = E_{P̂_N}[ξ]` and `Σ̂ = Cov_{P̂_N}[ξ]` are the mean
and covariance of the empirical distribution `P̂_N` of the `N ≥ 1` i.i.d. training samples,
`P^N` is the law of the sample, and the norm on `ℝ^m = EuclideanSpace ℝ (Fin m)` is the
Euclidean norm `‖·‖₂` of (28). `R(P,ℓ)` and the Gelbrich risk are taken in `EReal` with the
paper's convention for non-integrable losses (`nominalRisk`/`gelbrichRisk` v2), so no
integrability of `ℓ` under `P` has to be assumed.
Corrected from the retired `finite_sample_guarantees_ii`: `c` was a free universally
quantified real `> 1` instead of the constant delivered by Theorem 21 (so the radius could be
chosen independently of the scale of `P` and the guarantee failed); `IsClosed Ξ`,
measurability and upper semicontinuity of the losses were missing; an extra hypothesis
`∀ ℓ ∈ L, Integrable ℓ P` not in the source was imposed; and the Gelbrich hull/risk admitted
distributions without second moments through a junk value and dropped non-integrable `Q`
(now `gelbrichHull`/`gelbrichRisk` v2). -/
theorem finite_sample_guarantees_ii_v2 {m : ℕ}
(μ : EuclideanSpace ℝ (Fin m)) (Sigma : Matrix (Fin m) (Fin m) ℝ) (α A : ℝ)
(hα : 2 < α) (hA : 0 < A) :
∃ c : ℝ, c > 1 ∧
∀ (P : Measure (EuclideanSpace ℝ (Fin m))) (N : ℕ),
IsProbabilityMeasure P → 0 < N →
meanVector P = μ → covarianceMatrix P = Sigma →
Integrable (fun x => Real.exp (‖x‖ ^ α)) P →
(∫ x, Real.exp (‖x‖ ^ α) ∂P) ≤ A →
∀ (Ξ : Set (EuclideanSpace ℝ (Fin m))), IsClosed Ξ → P Ξᶜ = 0 →
∀ (L : Set (EuclideanSpace ℝ (Fin m) → ℝ)),
(∀ ℓ ∈ L, Measurable ℓ ∧ UpperSemicontinuous ℓ) →
∀ η ε : ℝ, 0 < η → η < 1 → ε ≥ Real.log (c / η) / Real.sqrt N →
sampleMeasure P N
{ξhat : Fin N → EuclideanSpace ℝ (Fin m) |
∀ ℓ ∈ L, nominalRisk P ℓ ≤
gelbrichRisk ε Ξ (meanVector (empiricalDistribution ξhat))
(covarianceMatrix (empiricalDistribution ξhat)) ℓ} ≥
ENNReal.ofReal (1 - η) := by sorry
end WassersteinDRO.Guarantees