Theorem 1 — greedy worst-case distribution
ProvedChenWasserstein.Reform.theorem_1Let be a finite-dimensional real normed space with its Borel sigma algebra, let , and let be arbitrary samples, with repetitions permitted. Let be open with nonempty complement . Write , , and , where is the infimum of the expected norm cost over all couplings. Assume .
Assume the samples are ordered so that . Choose any satisfying . Let be the number of zero distances, , and . When , let . Define by the corresponding atomic law below. Then is a probability law in and attains the worst unsafe probability:
If , then
If , then
The paper reproduces this previously established uncertainty-quantification result without proof. The assertion includes the full attaining law, not merely its value.
Formalization Note The nonempty unsafe set makes explicit the paper's implicit nearest-point convention (finding F1). Safety may be empty. Nearest-point selections are arbitrary and need not be unique; their existence follows from closedness, nonemptiness and finite dimension. All probability suprema and transport integrals are extended nonnegative values. No epsilon is needed in this uncertainty-quantification statement. The defined greedy law, rather than an assumed optimal law, occurs in the conclusion.
import Mathlib import Definitions.Def_ChenWasserstein_Reform_Data open MeasureTheory open scoped ENNReal BigOperators
/- Imported declaration bodies, quoted verbatim for standalone blind auditing.
These are comments, not redeclarations or additional assumptions.
noncomputable def distUnsafe {E : Type*} [NormedAddCommGroup E] (S : Set E) (u : E) : ℝ :=
Metric.infDist u Sᶜ
noncomputable def kthSmallest {N : ℕ} (v : Fin N → ℝ) (j : ℕ) : ℝ :=
((Finset.univ.val.map v).sort (· ≤ ·)).getD j 0
def IsCoupling {S : Type*} [MeasurableSpace S] (μ₁ μ₂ : Measure S) (π : Measure (S × S)) : Prop :=
IsProbabilityMeasure π ∧ π.map Prod.fst = μ₁ ∧ π.map Prod.snd = μ₂
noncomputable def transportCost {S : Type*} [MeasurableSpace S] (c : S → S → ℝ)
(μ₁ μ₂ : Measure S) : ℝ≥0∞ :=
⨅ (π : Measure (S × S)) (_ : IsCoupling μ₁ μ₂ π), ∫⁻ p, ENNReal.ofReal (c p.1 p.2) ∂π
noncomputable def worstProb {S : Type*} [MeasurableSpace S] (c : S → S → ℝ) (μ : Measure S)
(δ : ℝ) (A : Set S) : ℝ≥0∞ :=
⨆ (P : Measure S) (_ : IsProbabilityMeasure P ∧ transportCost c μ P ≤ ENNReal.ofReal δ), P A
noncomputable def empiricalDistribution {E : Type*} [MeasurableSpace E] {N : ℕ}
(ξhat : Fin N → E) : Measure E :=
(N : ENNReal)⁻¹ • ∑ i, Measure.dirac (ξhat i)
noncomputable def prefixSum {N : ℕ} (d : Fin N → ℝ) (j : ℕ) : ℝ :=
∑ i : Fin N, if i.val < j then d i else 0
noncomputable def zeroCount {N : ℕ} (d : Fin N → ℝ) : ℕ :=
(Finset.univ.filter (fun i => d i = 0)).card
noncomputable def jStar {N : ℕ} (d : Fin N → ℝ) (θ : ℝ) : ℕ :=
((Finset.range (N + 1)).filter (fun j => prefixSum d j ≤ θ * (N : ℝ))).sup id
noncomputable def pStar {N : ℕ} (d : Fin N → ℝ) (θ : ℝ) : ℝ :=
if h : jStar d θ < N then
(θ * (N : ℝ) - prefixSum d (jStar d θ)) / d ⟨jStar d θ, h⟩
else 0
noncomputable def fullLaw {E : Type*} [MeasurableSpace E] {N : ℕ}
(ξ η : Fin N → E) (d : Fin N → ℝ) : Measure E :=
(N : ℝ≥0∞)⁻¹ • ∑ i : Fin N,
if i.val < zeroCount d then Measure.dirac (ξ i) else Measure.dirac (η i)
noncomputable def partialLaw {E : Type*} [MeasurableSpace E] {N : ℕ}
(ξ η : Fin N → E) (d : Fin N → ℝ) (θ : ℝ) : Measure E :=
(N : ℝ≥0∞)⁻¹ • ∑ i : Fin N,
if i.val < zeroCount d then Measure.dirac (ξ i)
else if i.val < jStar d θ then Measure.dirac (η i)
else if i.val = jStar d θ then
ENNReal.ofReal (pStar d θ) • Measure.dirac (η i) +
ENNReal.ofReal (1 - pStar d θ) • Measure.dirac (ξ i)
else Measure.dirac (ξ i)
noncomputable def greedyLaw {E : Type*} [MeasurableSpace E] {N : ℕ}
(ξ η : Fin N → E) (d : Fin N → ℝ) (θ : ℝ) : Measure E :=
if jStar d θ = N then fullLaw ξ η d else partialLaw ξ η d θ
-/
namespace ChenWasserstein.Reform
/-- Chen, Kuhn and Wiesemann (2024), Theorem 1, printed p. 413 / PDF p. 4.
The samples are ordered by distance. η is any selection of closest unsafe points.
The nonempty complement states the source's implicit nearest-point domain. -/
theorem theorem_1
{E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
[MeasurableSpace E] [BorelSpace E] {N : ℕ}
(ξ η : Fin N → E) (S : Set E) (θ : ℝ)
(hN : 0 < N) (hθ : 0 < θ) (hS : IsOpen S) (hC : Sᶜ.Nonempty)
(horder : Monotone (fun i => WassDRCCP.Improved.distUnsafe S (ξ i)))
(hη : ∀ i, η i ∈ Sᶜ ∧ ‖ξ i - η i‖ = WassDRCCP.Improved.distUnsafe S (ξ i)) :
let d := fun i => WassDRCCP.Improved.distUnsafe S (ξ i)
let P := greedyLaw ξ η d θ
IsProbabilityMeasure P ∧
ModelRiskOT.WorstProb.transportCost (fun u v : E => ‖u - v‖)
(WassersteinDRO.Duality.empiricalDistribution ξ) P ≤ ENNReal.ofReal θ ∧
ModelRiskOT.WorstProb.worstProb (fun u v : E => ‖u - v‖)
(WassersteinDRO.Duality.empiricalDistribution ξ) θ Sᶜ = P Sᶜ ∧
(jStar d θ = N → P = fullLaw ξ η d ∧ P Sᶜ = 1) ∧
(jStar d θ < N → P = partialLaw ξ η d θ ∧
P Sᶜ = ENNReal.ofReal (((jStar d θ : ℕ) : ℝ) + pStar d θ) / (N : ℝ≥0∞)) := by sorry
end ChenWasserstein.Reform
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting.
- is a finite-dimensional real normed vector space with its Borel σ-algebra, and is a natural number.
- and are points of , is a set, and is a real number.
Hypotheses.
- and .
- is open, and its complement is nonempty. Since is open, is closed.
- Set . The sequence is nondecreasing in the index.
- For every , and . So each is a nearest point of to .
Notation used in the conclusion.
- is the empirical measure.
- is the greedy law of , with all ingredients expanded:
- .
- , or if that set is empty.
- If , then , which is if . If , then .
- If :
- Otherwise . Here for . Otherwise for . Otherwise for . Otherwise .
- The transport cost between two measures on is
a value in . The infimum is over couplings : probability measures on whose first marginal is and second marginal is . An infimum over no couplings is .
- The worst-case probability of a set is
Conclusion. All five of the following hold:
- is a probability measure.
- .
- , so the supremum is attained at . This is an equality in .
- If , then and .
- If , then and
Since always, exactly one of items 4 and 5 applies.
Degenerate cases:
- and . Both are excluded by the hypotheses.
- . There is a single sample. Then , and exactly when .
- Zero-dimensional . If , the only open set with nonempty complement is . Then , every , , and .
- Index order. The statement uses in index order and the position test . Under the monotonicity hypothesis, these index positions coincide with sorted positions.
- Division by zero. If and , then is defined to be .
- Automatic consequences. The statement does not separately assume . Item 1 nevertheless asserts that has total mass exactly , and that includes the mass carried by index when . The hypothesis on can be satisfied, because is closed and nonempty in a finite-dimensional space, so nearest points exist.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.