Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2 — DR linear regression with the squared ℓq\ell_qℓq​ cost: worst-case square loss =(MSEn(β)+δ∥βˉ∥p)2=(\sqrt{\mathrm{MSE}_n(\beta)}+\sqrt\delta\|\bar\beta\|_p)^2=(MSEn​(β)​+δ​∥βˉ​∥p​)2

Proved
RWPI.SqrtLasso.proposition_2

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

distributionally-robust-optimizationlinear-regressionoptimal-transportp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Fix q∈(1,∞]q\in(1,\infty]q∈(1,∞] and let ppp satisfy 1/p+1/q=11/p+1/q = 11/p+1/q=1. Let (X1,Y1),…,(Xn,Yn)∈Rd×R(X_1,Y_1),\dots,(X_n,Y_n)\in\mathbb R^d\times\mathbb R(X1​,Y1​),…,(Xn​,Yn​)∈Rd×R, n≥1n\ge1n≥1, be training data with empirical distribution PnP_nPn​, and let δ≥0\delta\ge0δ≥0. Take the square loss l(x,y;β)=(y−βTx)2l(x,y;\beta) = (y-\beta^Tx)^2l(x,y;β)=(y−βTx)2 and the cost c((x,y),(u,v))=∥(x,y)−(u,v)∥q2c((x,y),(u,v)) = \|(x,y)-(u,v)\|_q^2c((x,y),(u,v))=∥(x,y)−(u,v)∥q2​ on Rd+1\mathbb R^{d+1}Rd+1, with optimal transport cost DcD_cDc​ as in (7). Write βˉ=(−β,1)\bar\beta = (-\beta,1)βˉ​=(−β,1) and MSEn(β)=1n∑i=1n(Yi−βTXi)2\mathrm{MSE}_n(\beta) = \frac1n\sum_{i=1}^n (Y_i-\beta^TX_i)^2MSEn​(β)=n1​∑i=1n​(Yi​−βTXi​)2. Then:

  1. for every β∈Rd\beta\in\mathbb R^dβ∈Rd,
sup⁡P: Dc(P,Pn)≤δEP[(Y−βTX)2]=(MSEn(β)+δ ∥βˉ∥p)2;\sup_{P:\ D_c(P,P_n)\le\delta}\mathbb E_P\big[(Y-\beta^TX)^2\big] = \Big(\sqrt{\mathrm{MSE}_n(\beta)} + \sqrt\delta\,\|\bar\beta\|_p\Big)^2 ;P: Dc​(P,Pn​)≤δsup​EP​[(Y−βTX)2]=(MSEn​(β)​+δ​∥βˉ​∥p​)2;
  1. consequently (Eq. (13)),
inf⁡β∈Rd sup⁡P: Dc(P,Pn)≤δEP[(Y−βTX)2]=inf⁡β∈Rd(MSEn(β)+δ ∥βˉ∥p)2.\inf_{\beta\in\mathbb R^d}\ \sup_{P:\ D_c(P,P_n)\le\delta}\mathbb E_P\big[(Y-\beta^TX)^2\big] = \inf_{\beta\in\mathbb R^d}\Big(\sqrt{\mathrm{MSE}_n(\beta)} + \sqrt\delta\,\|\bar\beta\|_p\Big)^2 .β∈Rdinf​ P: Dc​(P,Pn​)≤δsup​EP​[(Y−βTX)2]=β∈Rdinf​(MSEn​(β)​+δ​∥βˉ​∥p​)2.

The distributionally robust least-squares problem with an ℓq\ell_qℓq​-transport ball is a regularized regression whose penalty is ∥βˉ∥p\|\bar\beta\|_p∥βˉ​∥p​, which also charges the intercept-like coordinate 111. Theorem 1 removes that coordinate by forbidding transport of the response.

Formalization Note Item 1 is the display that concludes the paper's proof (p. 29); item 2 is the printed statement (13). The page's statement does not mention δ≥0\delta\ge0δ≥0; it is the radius of the ball. The data space is (Fin d→R)×R(\text{Fin } d\to\mathbb R)\times\mathbb R(Fin d→R)×R, and the cost is the ℓq\ell_qℓq​ norm of the stacked vector in Rd+1\mathbb R^{d+1}Rd+1. Both sides are compared in [0,∞][0,\infty][0,∞]; the right side is a real number embedded by ENNReal.ofReal.

Preamble
import Mathlib
import Definitions.Def_WassersteinDRO_Regularization_empiricalDistribution
import Definitions.Def_RWPI_SqrtLasso_worstCase
import Definitions.Def_RWPI_SqrtLasso_squareLoss
import Definitions.Def_RWPI_SqrtLasso_MSE
import Definitions.Def_RWPI_SqrtLasso_lqSqCost

open MeasureTheory
Formal statement
namespace RWPI.SqrtLasso

/-- Proposition 2 (p. 10), with the pointwise identity its proof establishes (p. 29). Fix
`q ∈ (1, ∞]` and `p` with `1/p + 1/q = 1`. For the square loss and the cost
`c((x, y), (u, v)) = ‖(x, y) − (u, v)‖_q²` on `ℝ^{d+1}`, and every `δ ≥ 0`:
(1) for every `β`, `sup_{P : D_c(P, P_n) ≤ δ} E_P[(Y − βᵀX)²] = (√MSE_n(β) + √δ ‖β̄‖_p)²`;
(2) (13): the infima over `β ∈ ℝ^d` of both sides agree. -/
theorem proposition_2 {d n : ℕ} (hn : 0 < n) (X : Fin n → Fin d → ℝ) (Y : Fin n → ℝ)
    (q p : ENNReal) (hq : 1 < q) (hpq : p.HolderConjugate q) (δ : ℝ) (hδ : 0 ≤ δ) :
    (∀ β : Fin d → ℝ,
      worstCase (lqSqCost q) δ
          (WassersteinDRO.Regularization.empiricalDistribution (fun i : Fin n => (X i, Y i)))
          (squareLoss β) =
        ENNReal.ofReal
          ((Real.sqrt (MSE X Y β) + Real.sqrt δ * ‖WithLp.toLp p (betaBar β)‖) ^ 2)) ∧
    (⨅ β : Fin d → ℝ, worstCase (lqSqCost q) δ
          (WassersteinDRO.Regularization.empiricalDistribution (fun i : Fin n => (X i, Y i)))
          (squareLoss β)) =
      ⨅ β : Fin d → ℝ, ENNReal.ofReal
          ((Real.sqrt (MSE X Y β) + Real.sqrt δ * ‖WithLp.toLp p (betaBar β)‖) ^ 2) := by sorry

end RWPI.SqrtLasso
Source
Blanchet, Kang & Murthy, Robust Wasserstein Profile Inference and Applications to Machine Learning, arXiv:1610.05627v4, p. 10, Proposition 2, Eq. (13); pointwise form from App. A.1, p. 29 (display after (29))
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

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