Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6(c), p. 14 — if λ*(β) > λ_thr(β), the law of X + √δ G A(X)⁻¹β, G = ZG₋ + (1 − Z)G₊, attains the worst case with E[c(X, X*)] = δ

Proved
OTDRO.WorstCase.worst_case_randomized_monge

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

distributionally-robust-optimizationoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-distribution

Assume Assumptions 1 and 2, δ>0\delta>0δ>0 and B⊆RdB\subseteq\mathbb R^dB⊆Rd convex; fix β∈B\beta\in Bβ∈B with β≠0\beta\neq0β=0 and a dual optimizer λ∗(β)∈arg⁡min⁡λ≥0fδ(β,λ)\lambda_*(\beta)\in\arg\min_{\lambda\ge0}f_\delta(\beta,\lambda)λ∗​(β)∈argminλ≥0​fδ​(β,λ). Suppose λ∗(β)>λthr(β)\lambda_*(\beta)>\lambda_{thr}(\beta)λ∗​(β)>λthr​(β). Then there are measurable functions G−,G+:Rd→RG_-,G_+:\mathbb R^d\to\mathbb RG−​,G+​:Rd→R such that, for P0P_0P0​-almost every xxx, G−(x)G_-(x)G−​(x) and G+(x)G_+(x)G+​(x) belong to Γ∗(β,λ∗(β);x)\Gamma^*(\beta,\lambda_*(\beta);x)Γ∗(β,λ∗​(β);x) and

G−(x)2=min⁡g∈Γ∗(β,λ∗(β);x)g2,G+(x)2=max⁡g∈Γ∗(β,λ∗(β);x)g2;G_-(x)^2=\min_{g\in\Gamma^*(\beta,\lambda_*(\beta);x)}g^2,\qquad G_+(x)^2=\max_{g\in\Gamma^*(\beta,\lambda_*(\beta);x)}g^2 ;G−​(x)2=g∈Γ∗(β,λ∗​(β);x)min​g2,G+​(x)2=g∈Γ∗(β,λ∗​(β);x)max​g2;

the moments cˉ=EP0[G+2βTA(X)−1β]\bar c=E_{P_0}[G_+^2\beta^{\mathsf T}A(X)^{-1}\beta]cˉ=EP0​​[G+2​βTA(X)−1β] and c‾=EP0[G−2βTA(X)−1β]\underline c=E_{P_0}[G_-^2\beta^{\mathsf T}A(X)^{-1}\beta]c​=EP0​​[G−2​βTA(X)−1β] are finite; q=(cˉ−1)/(cˉ−c‾)q=(\bar c-1)/(\bar c-\underline c)q=(cˉ−1)/(cˉ−c​) lies in [0,1][0,1][0,1]; and, with ZZZ a Bernoulli(q)(q)(q) variable independent of X∼P0X\sim P_0X∼P0​, G=ZG−(X)+(1−Z)G+(X)G=ZG_-(X)+(1-Z)G_+(X)G=ZG−​(X)+(1−Z)G+​(X) and

X∗=X+δ G A(X)−1β,X^*=X+\sqrt\delta\,G\,A(X)^{-1}\beta,X∗=X+δ​GA(X)−1β,

the joint law π∗\pi^*π∗ of (X,X∗)(X,X^*)(X,X∗) satisfies E[c(X,X∗)]=δE[c(X,X^*)]=\deltaE[c(X,X∗)]=δ and attains the worst case:

Eπ∗[ℓ(βTX∗)]=sup⁡P: Dc(P0,P)≤δEP[ℓ(βTX)].E_{\pi^*}\bigl[\ell(\beta^{\mathsf T}X^*)\bigr]=\sup_{P:\,D_c(P_0,P)\le\delta}E_P\bigl[\ell(\beta^{\mathsf T}X)\bigr].Eπ∗​[ℓ(βTX∗)]=P:Dc​(P0​,P)≤δsup​EP​[ℓ(βTX)].

The theorem describes an adversarial distribution explicitly: each data point is moved along the single direction A(x)−1βA(x)^{-1}\betaA(x)−1β by an amount read off the one-dimensional problem (7), randomizing between two extreme maximizers only to spend the transport budget exactly.

Formalization Note The page defines G−=inf⁡Γ(β,λ∗(β);X)G_-=\inf\Gamma(\beta,\lambda_*(\beta);X)G−​=infΓ(β,λ∗​(β);X) and G+=sup⁡Γ(β,λ∗(β);X)G_+=\sup\Gamma(\beta,\lambda_*(\beta);X)G+​=supΓ(β,λ∗​(β);X) (with Γ\GammaΓ for Γ∗\Gamma^*Γ∗). Its proof (p. 40) instead takes measurable selections with g+2=sup⁡g∈Γ∗g2g_+^2=\sup_{g\in\Gamma^*}g^2g+2​=supg∈Γ∗​g2 and g−2=inf⁡g∈Γ∗g2g_-^2=\inf_{g\in\Gamma^*}g^2g−2​=infg∈Γ∗​g2, and only that choice makes c‾≤1≤cˉ\underline c\le1\le\bar cc​≤1≤cˉ follow from the first-order conditions. With the printed choice the statement can fail: for d=1d=1d=1, A≡1A\equiv1A≡1, δ=1\delta=1δ=1, β=1\beta=1β=1, ℓ(u)=max⁡(−3u,u,3u−c0)\ell(u)=\max(-3u,u,3u-c_0)ℓ(u)=max(−3u,u,3u−c0​) with c0c_0c0​ large and P0P_0P0​ uniform on two suitable points, λ∗=1\lambda_*=1λ∗​=1 is a dual optimizer with Γ∗={−3/2,1/2}\Gamma^*=\{-3/2,1/2\}Γ∗={−3/2,1/2} at one point and {1/2,3/2}\{1/2,3/2\}{1/2,3/2} at the other, so the printed cˉ=c‾=5/4\bar c=\underline c=5/4cˉ=c​=5/4 and no mixture has cost δ\deltaδ. The statement follows the proof. "The law of X∗X^*X∗ attains the supremum in (6)" is encoded with the published primal problem of Blanchet–Murthy: π∗\pi^*π∗ is a coupling with first marginal P0P_0P0​ and cost at most δ\deltaδ (primalFeasible) whose value ∫ℓ(βTy) dπ∗\int\ell(\beta^{\mathsf T}y)\,d\pi^*∫ℓ(βTy)dπ∗ equals the supremum primalValue over all such couplings; the cost is the lower Lebesgue integral of ccc. The random ZZZ is encoded through the mixture law (mixtureCoupling). The convexity of BBB is the paper's standing assumption (p. 1).

Preamble
import Mathlib
import Definitions.Def_ModelRiskOT_Duality_primalFeasible
import Definitions.Def_ModelRiskOT_Duality_primalValue
import Definitions.Def_OTDRO_Dual_Setting
import Definitions.Def_OTDRO_WorstCase_Transport

open MeasureTheory
Formal statement
namespace OTDRO.WorstCase

/-- **Theorem 6(c)** (arXiv:1810.02403v3, p. 14; proof §5.4, pp. 39–40). Under Assumptions 1–2,
for `β ≠ 0` and a dual optimizer `λ*(β) > λ_thr(β)`, there are measurable selections `G₋, G₊` of
`Γ*(β, λ*(β); ·)` such that, with `c̄ = E[G₊² βᵀA⁻¹β]`, `c̲ = E[G₋² βᵀA⁻¹β]` and
`q = (c̄ − 1)/(c̄ − c̲) ∈ [0, 1]`, the joint law of `(X, X*)`,
`X* = X + √δ (Z G₋ + (1 − Z) G₊) A(X)⁻¹β` with `Z ∼ Bernoulli(q)` independent of `X`, is a
feasible coupling that attains the worst-case value and has transport cost exactly `δ`.
`G₋, G₊` are the elements of `Γ*` of least and greatest square, as in the proof (p. 40). -/
theorem worst_case_randomized_monge {d : ℕ} (P0 : Measure (EuclideanSpace ℝ (Fin d)))
    [IsProbabilityMeasure P0] (A : EuclideanSpace ℝ (Fin d) → Matrix (Fin d) (Fin d) ℝ)
    (ρmin ρmax : ℝ) (hA : OTDRO.Dual.Assumption1 P0 A ρmin ρmax) (ℓ : ℝ → ℝ) (h2 : OTDRO.Dual.Assumption2 P0 ℓ)
    (δ : ℝ) (hδ : 0 < δ) (B : Set (EuclideanSpace ℝ (Fin d))) (hB : Convex ℝ B)
    (β : EuclideanSpace ℝ (Fin d)) (hβB : β ∈ B) (hβ : β ≠ 0)
    (lamStar : ℝ) (hlam0 : 0 ≤ lamStar)
    (hmin : IsMinOn (fun l => OTDRO.Dual.fDelta P0 ℓ A δ β l) (Set.Ici 0) lamStar)
    (hthr : OTDRO.Dual.lamThr P0 ℓ A δ β < lamStar) :
    ∃ Gminus Gplus : EuclideanSpace ℝ (Fin d) → ℝ,
      AEMeasurable Gminus P0 ∧ AEMeasurable Gplus P0 ∧
      (∀ᵐ x ∂P0, Gminus x ∈ OTDRO.Dual.maximizers ℓ A δ β lamStar x ∧
        Gplus x ∈ OTDRO.Dual.maximizers ℓ A δ β lamStar x ∧
        ∀ g ∈ OTDRO.Dual.maximizers ℓ A δ β lamStar x, Gminus x ^ 2 ≤ g ^ 2 ∧ g ^ 2 ≤ Gplus x ^ 2) ∧
      Integrable (fun x => Gminus x ^ 2 * OTDRO.Dual.quadInv A β x) P0 ∧
      Integrable (fun x => Gplus x ^ 2 * OTDRO.Dual.quadInv A β x) P0 ∧
      0 ≤ bernoulliWeight (sqMoment P0 A β Gplus) (sqMoment P0 A β Gminus) ∧
      bernoulliWeight (sqMoment P0 A β Gplus) (sqMoment P0 A β Gminus) ≤ 1 ∧
      mixtureCoupling P0 A δ β Gminus Gplus ∈
        ModelRiskOT.Duality.primalFeasible (OTDRO.Dual.mahalCost A) P0 δ ∧
      ModelRiskOT.Duality.primalObj (fun x => ℓ (inner ℝ β x))
          (mixtureCoupling P0 A δ β Gminus Gplus) =
        ModelRiskOT.Duality.primalValue (OTDRO.Dual.mahalCost A) (fun x => ℓ (inner ℝ β x)) P0 δ ∧
      ∫⁻ p, ENNReal.ofReal (OTDRO.Dual.mahalCost A p.1 p.2) ∂(mixtureCoupling P0 A δ β Gminus Gplus) =
        ENNReal.ofReal δ := by sorry

end OTDRO.WorstCase
Source
arXiv:1810.02403v3, Theorem 6(c), p. 14, (10); proof §5.4, pp. 39–40
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 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