Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — square-root LASSO is Wasserstein DRO: worst-case squared loss under Nq2N_q^2Nq2​ equals (MSEn(β)+δ∥β∥p)2(\sqrt{\mathrm{MSE}_n(\beta)}+\sqrt\delta\|\beta\|_p)^2(MSEn​(β)​+δ​∥β∥p​)2

Proved
RWPI.SqrtLasso.theorem_1

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

distributionally-robust-optimizationlassolinear-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. Consider the square loss l(x,y;β)=(y−βTx)2l(x,y;\beta) = (y-\beta^Tx)^2l(x,y;β)=(y−βTx)2 and the optimal transport cost DcD_cDc​ of (7) with

c((x,y),(u,v))=Nq((x,y),(u,v))2,Nq((x,y),(u,v))={∥x−u∥q,y=v,+∞,y≠v.c\big((x,y),(u,v)\big) = N_q\big((x,y),(u,v)\big)^2, \qquad N_q\big((x,y),(u,v)\big) = \begin{cases}\|x-u\|_q, & y = v,\\ +\infty, & y\ne v.\end{cases}c((x,y),(u,v))=Nq​((x,y),(u,v))2,Nq​((x,y),(u,v))={∥x−u∥q​,+∞,​y=v,y=v.​

Let 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\,\|\beta\|_p\Big)^2 ;P: Dc​(P,Pn​)≤δsup​EP​[(Y−βTX)2]=(MSEn​(β)​+δ​∥β∥p​)2;
  1. consequently,
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\,\|\beta\|_p\Big)^2 .β∈Rdinf​ P: Dc​(P,Pn​)≤δsup​EP​[(Y−βTX)2]=β∈Rdinf​(MSEn​(β)​+δ​∥β∥p​)2.

The right side of item 2 is the ℓp\ell_pℓp​-penalized square-root least-squares problem: for q=∞q = \inftyq=∞ (p=1p = 1p=1) its minimizers are those of the square-root LASSO MSEn(β)+δ∥β∥1\sqrt{\mathrm{MSE}_n(\beta)}+\sqrt\delta\|\beta\|_1MSEn​(β)​+δ​∥β∥1​. The theorem therefore identifies these estimators exactly as distributionally robust least-squares estimators, with the radius δ\deltaδ of the transport ball playing the role of the squared regularization parameter.

Formalization Note Item 2 is the printed statement; item 1 is the identity the paper's proof establishes for each β\betaβ (App. A.1, p. 29). The page does not state the range of qqq; Proposition 2 fixes q∈(1,∞]q\in(1,\infty]q∈(1,∞] and the paper calls Theorem 1 "essentially the same", so that range is used. δ≥0\delta\ge0δ≥0 is the radius of the ball. Expectations are lower Lebesgue integrals in [0,∞][0,\infty][0,∞], the supremum is over all probability measures on (Fin d→R)×R(\text{Fin } d\to\mathbb R)\times\mathbb R(Fin d→R)×R within transport cost δ\deltaδ of PnP_nPn​, couplings fix both marginals, and the right side is a real number embedded by ENNReal.ofReal. ∥β∥p\|\beta\|_p∥β∥p​ is the PiLp p norm.

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_Nq

open MeasureTheory
Formal statement
namespace RWPI.SqrtLasso

/-- Theorem 1 (Blanchet, Kang & Murthy, p. 11), with the pointwise identity its proof establishes.
For the square loss `l(x, y; β) = (y − βᵀx)²`, the cost `c = N_q^ρ` with `ρ = 2`
(`N_q((x, y), (u, v)) = ‖x − u‖_q` if `y = v`, `+∞` otherwise), `q ∈ (1, ∞]`, `1/p + 1/q = 1`, the
empirical distribution `P_n` of the data `(X_i, Y_i)` and every `δ ≥ 0`:
(1) for every `β`, `sup_{P : D_c(P, P_n) ≤ δ} E_P[(Y − βᵀX)²] = (√MSE_n(β) + √δ ‖β‖_p)²`;
(2) `inf_β sup_{P : D_c(P, P_n) ≤ δ} E_P[(Y − βᵀX)²] = inf_β (√MSE_n(β) + √δ ‖β‖_p)²`. -/
theorem theorem_1 {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 (fun z w => Nq q z w ^ 2) δ
          (WassersteinDRO.Regularization.empiricalDistribution (fun i : Fin n => (X i, Y i)))
          (squareLoss β) =
        ENNReal.ofReal ((Real.sqrt (MSE X Y β) + Real.sqrt δ * ‖WithLp.toLp p β‖) ^ 2)) ∧
    (⨅ β : Fin d → ℝ, worstCase (fun z w => Nq q z w ^ 2) δ
          (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 β‖) ^ 2) := by sorry

end RWPI.SqrtLasso
Source
Blanchet, Kang & Murthy, Robust Wasserstein Profile Inference and Applications to Machine Learning, arXiv:1610.05627v4, p. 11, Theorem 1 (pointwise form from App. A.1, p. 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