Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.5, p. 8 — finite sample guarantee: P^N{E^P[h(x̂_N, ξ)] > Ĵ_N} ≤ β for the radius ε_N(β)

Proved
WassDDRO.Consistency.theorem_3_5

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

distributionally-robust-optimizationfinite-sample-guaranteep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1wasserstein

Let EEE be a finite-dimensional real normed space with its Borel σ\sigmaσ-algebra, m=dim⁡E≠2m=\dim E\ne2m=dimE=2, and let PPP be a probability distribution on EEE supported on Ξ⊆E\Xi\subseteq EΞ⊆E (that is, P(E∖Ξ)=0P(E\setminus\Xi)=0P(E∖Ξ)=0). Suppose Assumption 3.3 holds: for some a>1a>1a>1,

A=EP[exp⁡(∥ξ∥a)]<∞,A=\mathbb E^P\big[\exp(\|\xi\|^a)\big]<\infty,A=EP[exp(∥ξ∥a)]<∞,

and let c1,c2>0c_1,c_2>0c1​,c2​>0 be constants for which the concentration inequality (7) holds. Fix N≥1N\ge1N≥1 and β∈(0,1)\beta\in(0,1)β∈(0,1), a feasible set X⊆RnX\subseteq\mathbb R^nX⊆Rn and a loss h:Rn×E→Rh:\mathbb R^n\times E\to\mathbb Rh:Rn×E→R with h(x,⋅)h(x,\cdot)h(x,⋅) measurable for every xxx and PPP-integrable for every x∈Xx\in Xx∈X. Let x^N\widehat x_NxN​ be an optimizer of the distributionally robust program (5) with ambiguity set BεN(β)(P^N)\mathbb B_{\varepsilon_N(\beta)}(\widehat P_N)BεN​(β)​(PN​): for every sample Ξ^N={ξ^1,…,ξ^N}⊆Ξ\widehat\Xi_N=\{\hat\xi_1,\dots,\hat\xi_N\}\subseteq\XiΞN​={ξ^​1​,…,ξ^​N​}⊆Ξ, x^N∈X\widehat x_N\in XxN​∈X and x^N\widehat x_NxN​ minimizes x↦sup⁡Q∈BεN(β)(P^N)EQ[h(x,ξ)]x\mapsto\sup_{Q\in\mathbb B_{\varepsilon_N(\beta)}(\widehat P_N)}\mathbb E^Q[h(x,\xi)]x↦supQ∈BεN​(β)​(PN​)​EQ[h(x,ξ)] over XXX. Let J^N\widehat J_NJN​ be the optimal value of (5). Then the finite sample guarantee (2) holds:

PN{Ξ^N: EP[h(x^N,ξ)]>J^N}≤β,equivalentlyPN{Ξ^N: EP[h(x^N,ξ)]≤J^N}≥1−β.P^N\Big\{\widehat\Xi_N:\ \mathbb E^P\big[h(\widehat x_N,\xi)\big]>\widehat J_N\Big\}\le\beta, \quad\text{equivalently}\quad P^N\Big\{\widehat\Xi_N:\ \mathbb E^P\big[h(\widehat x_N,\xi)\big]\le\widehat J_N\Big\}\ge1-\beta .PN{ΞN​: EP[h(xN​,ξ)]>JN​}≤β,equivalentlyPN{ΞN​: EP[h(xN​,ξ)]≤JN​}≥1−β.

The certificate J^N\widehat J_NJN​ is thus an upper confidence bound, at level 1−β1-\beta1−β, on the out-of-sample cost of the data-driven decision.

Formalization Note The probability is stated for the failure event, as an outer measure, because the success event need not be measurable (x^N\widehat x_NxN​ is an arbitrary selection of optimizers). The constants c1,c2c_1,c_2c1​,c2​ enter as any constants satisfying (7) (Theorem 3.4 supplies them); m≠2m\ne2m=2 is the scope of (7) and (8). The optimizer is required only for samples in Ξ\XiΞ, as in §2 (Ξ^N⊆Ξ\widehat\Xi_N\subseteq\XiΞN​⊆Ξ). The loss is real-valued and PPP-integrability of h(x,⋅)h(x,\cdot)h(x,⋅) on XXX is assumed, a specialization of the paper's extended-valued loss: the worst-case expectation counts only distributions under which h(x,⋅)h(x,\cdot)h(x,⋅) is integrable, so without this hypothesis PPP itself would not be counted.

Preamble
import Mathlib
import Definitions.Def_WassDDRO_Consistency_Setting

open MeasureTheory
Formal statement
namespace WassDDRO.Consistency

/-- Theorem 3.5 (Finite sample guarantee), p. 8. Under Assumption 3.3, with constants
`c₁, c₂` for which (7) holds (`m ≠ 2`), `β ∈ (0, 1)`, `N ≥ 1`, and `x̂_N` an optimizer of (5)
with ambiguity set `B_{ε_N(β)}(P̂_N)`, the guarantee (2) holds in failure-set form:
`P^N{E^P[h(x̂_N, ξ)] > Ĵ_N} ≤ β`. -/
theorem theorem_3_5 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
    [MeasurableSpace E] [BorelSpace E]
    (P : Measure E) [IsProbabilityMeasure P] (Ξ : Set E) (hP : P Ξᶜ = 0)
    (a : ℝ) (ha : 1 < a) (hA : Integrable (fun ξ => Real.exp (‖ξ‖ ^ a)) P)
    (hm : Module.finrank ℝ E ≠ 2)
    (c₁ c₂ : ℝ) (hc₁ : 0 < c₁) (hc₂ : 0 < c₂) (h7 : Concentration7 P a c₁ c₂)
    (N : ℕ) (hN : 1 ≤ N) (b : ℝ) (hb : 0 < b ∧ b < 1)
    {n : ℕ} (X : Set (EuclideanSpace ℝ (Fin n))) (h : EuclideanSpace ℝ (Fin n) → E → ℝ)
    (hmeas : ∀ x, Measurable (h x)) (hint : ∀ x ∈ X, Integrable (h x) P)
    (xh : (Fin N → E) → EuclideanSpace ℝ (Fin n))
    (hopt : ∀ ξhat : Fin N → E, (∀ i, ξhat i ∈ Ξ) →
      xh ξhat ∈ X ∧ ∀ x ∈ X,
        WassersteinDRO.Duality.worstCaseRisk (radius c₁ c₂ a (Module.finrank ℝ E) N b) 1 Ξ
            (WassersteinDRO.Duality.empiricalDistribution ξhat) (h (xh ξhat)) ≤
          WassersteinDRO.Duality.worstCaseRisk (radius c₁ c₂ a (Module.finrank ℝ E) N b) 1 Ξ
            (WassersteinDRO.Duality.empiricalDistribution ξhat) (h x)) :
    (Measure.pi fun _ : Fin N => P)
        {ξhat | ¬ (((∫ ξ, h (xh ξhat) ξ ∂P : ℝ) : EReal) ≤
          droValue X h (radius c₁ c₂ a (Module.finrank ℝ E) N b) Ξ ξhat)} ≤
      ENNReal.ofReal b := by sorry

end WassDDRO.Consistency
Source
Mohajerin Esfahani & Kuhn, arXiv:1505.05116v3, Theorem 3.5, p. 8; (2) p. 5, (5) p. 6, (7)–(8) p. 8
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me