Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.1(ii), p. 8 — Wasserstein-robust linear regression equals (1/N)Σ L(⟨w, x̂_i⟩ − ŷ_i) + ρ lip(L)‖(w, −1)‖_*

Proved
RegMT.Regress.theorem_3_1_ii

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

distributionally-robustp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regressionregularizationwasserstein

Distributionally robust linear regression (Theorem 3.1(ii)). Let the input-output space Rn+1\mathbb R^{n+1}Rn+1 carry an arbitrary norm ∥⋅∥\|\cdot\|∥⋅∥, with dual norm ∥⋅∥∗\|\cdot\|_*∥⋅∥∗​, and let the transport cost be d(ξ,ξ′)=∥ξ−ξ′∥d(\xi,\xi')=\|\xi-\xi'\|d(ξ,ξ′)=∥ξ−ξ′∥ on Ξ=Rn+1\Xi=\mathbb R^{n+1}Ξ=Rn+1. Let (x^i,y^i)∈Rn×R(\hat x_i,\hat y_i)\in\mathbb R^n\times\mathbb R(x^i​,y^​i​)∈Rn×R, i=1,…,Ni=1,\dots,Ni=1,…,N with N≥1N\ge1N≥1, be training samples with empirical distribution P^N\hat{\mathbb P}_NP^N​. For ρ≥0\rho\ge0ρ≥0, let Bρ(P^N)\mathbb B_\rho(\hat{\mathbb P}_N)Bρ​(P^N​) be the type-1 Wasserstein ball (3) of radius ρ\rhoρ around P^N\hat{\mathbb P}_NP^N​. Let L:R→RL:\mathbb R\to\mathbb RL:R→R be a nonnegative, convex, Lipschitz continuous loss function with Lipschitz modulus lip(L)\mathrm{lip}(L)lip(L). The regression loss of the weight vector w∈Rnw\in\mathbb R^nw∈Rn is ℓw(x,y)=L(⟨w,x⟩−y)\ell_w(x,y)=L(\langle w,x\rangle-y)ℓw​(x,y)=L(⟨w,x⟩−y).

Then the distributionally robust regression problem (4) is equivalent to the regularized problem (6), in the following sense.

  1. For every w∈Rnw\in\mathbb R^nw∈Rn,
sup⁡Q∈Bρ(P^N)EQ[L(⟨w,x⟩−y)]  =  1N∑i=1NL(⟨w,x^i⟩−y^i)  +  ρ lip(L) ∥(w,−1)∥∗.\sup_{\mathbb Q\in\mathbb B_\rho(\hat{\mathbb P}_N)}\mathbb E^{\mathbb Q}\big[L(\langle w,x\rangle-y)\big] \;=\;\frac1N\sum_{i=1}^N L(\langle w,\hat x_i\rangle-\hat y_i)\;+\;\rho\,\mathrm{lip}(L)\,\|(w,-1)\|_* .Q∈Bρ​(P^N​)sup​EQ[L(⟨w,x⟩−y)]=N1​i=1∑N​L(⟨w,x^i​⟩−y^​i​)+ρlip(L)∥(w,−1)∥∗​.
  1. Consequently, the optimal values agree:
inf⁡w sup⁡Q∈Bρ(P^N)EQ[L(⟨w,x⟩−y)]  =  inf⁡w 1N∑i=1NL(⟨w,x^i⟩−y^i)+ρ lip(L) ∥(w,−1)∥∗.\inf_{w}\ \sup_{\mathbb Q\in\mathbb B_\rho(\hat{\mathbb P}_N)}\mathbb E^{\mathbb Q}\big[L(\langle w,x\rangle-y)\big] \;=\;\inf_w\ \frac1N\sum_{i=1}^N L(\langle w,\hat x_i\rangle-\hat y_i)+\rho\,\mathrm{lip}(L)\,\|(w,-1)\|_* .winf​ Q∈Bρ​(P^N​)sup​EQ[L(⟨w,x⟩−y)]=winf​ N1​i=1∑N​L(⟨w,x^i​⟩−y^​i​)+ρlip(L)∥(w,−1)∥∗​.

The theorem shows that Wasserstein distributionally robust linear regression with a norm transport cost is empirical loss minimization with a dual-norm penalty. The penalty acts on the extended vector (w,−1)(w,-1)(w,−1), because the transport cost moves outputs as well as inputs, and it is weighted by the radius and by the Lipschitz modulus of the univariate loss. For the Huber, ϵ\epsilonϵ-insensitive and pinball losses this gives explicit regularized programs (Corollaries 3.2–3.4).

Formalization Note. Rn+1\mathbb R^{n+1}Rn+1 is an abstract finite-dimensional real normed space EEE with Borel σ-algebra and a continuous linear isomorphism e:E→Rn×Re:E\to\mathbb R^n\times\mathbb Re:E→Rn×R that reads off inputs and outputs, so the theorem covers every norm on Rn+1\mathbb R^{n+1}Rn+1. The worst case is the published worstCaseRisk with p=1p=1p=1, Ξ=E\Xi=EΞ=E and P^N\hat{\mathbb P}_NP^N​ the published empiricalDistribution. Its expectations follow the extended-real convention of nominalRisk, and both sides live in the extended reals. ∥(w,−1)∥∗\|(w,-1)\|_*∥(w,−1)∥∗​ is the operator norm of pairing e w, and lip(L)\mathrm{lip}(L)lip(L) is the published lipschitzModulus of the univariate LLL, valued in [0,∞][0,\infty][0,∞] and finite here. The paper does not define "equivalent". The statement is the per-www identity that the proof establishes (pp. 30–31) together with the equality of optimal values, which follows from it. No attainment of the infimum is claimed. The radius ρ=0\rho=0ρ=0 is included, in which case both sides reduce to the empirical loss. The standing assumption L≥0L\ge0L≥0 of §2.1 is included.

Preamble
import Mathlib
import Definitions.Def_WassersteinDRO_Duality_worstCaseRisk_v2
import Definitions.Def_WassersteinDRO_Duality_empiricalDistribution
import Definitions.Def_WassersteinDRO_Duality_lipschitzModulus
import Definitions.Def_RegMT_Regress_Model

open WassersteinDRO.Duality
Formal statement
namespace RegMT.Regress

/-- Theorem 3.1(ii) (Distributionally robust linear regression), Shafieezadeh-Abadeh, Kuhn &
Mohajerin Esfahani, *Regularization via Mass Transportation*, arXiv:1710.10016v3, p. 8, (6).

Setting (§3.1, p. 8): the input-output space `ℝ^{n+1}` carries an arbitrary norm and is modelled
as `E` with input/output coordinates `e : E ≃L[ℝ] ℝⁿ × ℝ`; the transport cost is `‖ξ − ξ'‖` and
`Ξ = E`; `L : ℝ → ℝ` is nonnegative, convex and Lipschitz continuous; the samples are `(xhat i, yhat i)`,
`i < N`, `N ≥ 1`; `ρ ≥ 0` is the radius of the Wasserstein ball (3) around the empirical
distribution `P̂_N`. The worst case `sup_{Q ∈ B_ρ(P̂_N)} E^Q[L(⟨w, x⟩ − y)]` of (4) is
`worstCaseRisk ρ 1 Set.univ P̂_N (L ∘ pairing e w)`.

Conclusion ("(4) is equivalent to (6)"): (1) for every `w` the worst-case expected loss equals the
objective of (6), `(1/N) Σᵢ L(⟨w, xhat i⟩ − yhat i) + ρ · lip(L) · ‖(w, −1)‖_*`, with `lip(L)` the
Lipschitz modulus of `L` and `‖(w, −1)‖_*` the operator norm of `pairing e w`; (2) consequently the
optimal values of (4) and (6) agree. -/
theorem theorem_3_1_ii {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
    [FiniteDimensional ℝ E] [MeasurableSpace E] [BorelSpace E] {n N : ℕ}
    (e : E ≃L[ℝ] (Fin n → ℝ) × ℝ) (ρ : ℝ) (hρ : 0 ≤ ρ) (hN : 0 < N)
    (xhat : Fin N → Fin n → ℝ) (yhat : Fin N → ℝ)
    (L : ℝ → ℝ) (hconv : ConvexOn ℝ Set.univ L) (h_nonneg : ∀ z, 0 ≤ L z)
    (hLip : ∃ K, LipschitzWith K L) :
    (∀ w : Fin n → ℝ,
      worstCaseRisk ρ 1 Set.univ (empiricalDistribution fun i => e.symm (xhat i, yhat i))
          (fun ξ => L (pairing e w ξ)) =
        (((N : ℝ)⁻¹ * ∑ i, L (∑ j, w j * xhat i j - yhat i) : ℝ) : EReal) +
          ((ENNReal.ofReal ρ * lipschitzModulus L * ENNReal.ofReal ‖pairing e w‖ : ENNReal) :
            EReal)) ∧
    (⨅ w : Fin n → ℝ,
      worstCaseRisk ρ 1 Set.univ (empiricalDistribution fun i => e.symm (xhat i, yhat i))
          (fun ξ => L (pairing e w ξ))) =
      ⨅ w : Fin n → ℝ,
        (((N : ℝ)⁻¹ * ∑ i, L (∑ j, w j * xhat i j - yhat i) : ℝ) : EReal) +
          ((ENNReal.ofReal ρ * lipschitzModulus L * ENNReal.ofReal ‖pairing e w‖ : ENNReal) :
            EReal) := by sorry

end RegMT.Regress
Source
Shafieezadeh-Abadeh, Kuhn & Mohajerin Esfahani, Regularization via Mass Transportation, arXiv:1710.10016v3, p. 8, Theorem 3.1(ii), (6); setting §3.1 preamble p. 8, (3)–(4) p. 7; proof pp. 30–31
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