Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — ℓp-regularized logistic regression and the hinge-loss SVM are Wasserstein DRO under the label-preserving cost N_q

Proved
RWPI.Classif.theorem_2

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

distributionally-robust-optimizationlogistic-regressionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regularizationsupport-vector-machine

Let (X1,Y1),…,(Xn,Yn)(X_1,Y_1),\dots,(X_n,Y_n)(X1​,Y1​),…,(Xn​,Yn​) be training data with Xi∈RdX_i \in \mathbb R^dXi​∈Rd, labels Yi∈{−1,+1}Y_i \in \{-1,+1\}Yi​∈{−1,+1} and n≥1n \ge 1n≥1, and let PnP_nPn​ be their empirical distribution. Let q∈[1,∞]q \in [1,\infty]q∈[1,∞] and let ppp be its conjugate exponent, 1/p+1/q=11/p + 1/q = 11/p+1/q=1. Let DcD_cDc​ be the optimal transport cost with the label-preserving cost

c((x,y),(u,v))=Nq((x,y),(u,v))={∥x−u∥qy=v,+∞y≠v,c\big((x,y),(u,v)\big) = 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))={∥x−u∥q​+∞​y=v,y=v,​

(exponent ρ=1\rho = 1ρ=1), and let δ≥0\delta \ge 0δ≥0. Then for every β∈Rd\beta \in \mathbb R^dβ∈Rd:

  1. (logistic regression)
sup⁡P: Dc(P,Pn)≤δEP[log⁡(1+e−YβTX)]=1n∑i=1nlog⁡(1+e−YiβTXi)+δ ∥β∥p;\sup_{P:\ D_c(P,P_n)\le\delta} \mathbb E_P\Big[\log\big(1 + e^{-Y\beta^T X}\big)\Big] = \frac1n\sum_{i=1}^n \log\big(1 + e^{-Y_i\beta^T X_i}\big) + \delta\,\|\beta\|_p ;P: Dc​(P,Pn​)≤δsup​EP​[log(1+e−YβTX)]=n1​i=1∑n​log(1+e−Yi​βTXi​)+δ∥β∥p​;
  1. (support vector machine)
sup⁡P: Dc(P,Pn)≤δEP[(1−YβTX)+]=1n∑i=1n(1−YiβTXi)++δ ∥β∥p.\sup_{P:\ D_c(P,P_n)\le\delta} \mathbb E_P\Big[\big(1 - Y\beta^T X\big)^+\Big] = \frac1n\sum_{i=1}^n \big(1 - Y_i\beta^T X_i\big)^+ + \delta\,\|\beta\|_p .P: Dc​(P,Pn​)≤δsup​EP​[(1−YβTX)+]=n1​i=1∑n​(1−Yi​βTXi​)++δ∥β∥p​.

Consequently,

inf⁡β∈Rd sup⁡P: Dc(P,Pn)≤δEP[log⁡(1+e−YβTX)]=inf⁡β∈Rd{1n∑i=1nlog⁡(1+e−YiβTXi)+δ ∥β∥p},\inf_{\beta\in\mathbb R^d}\ \sup_{P:\ D_c(P,P_n)\le\delta} \mathbb E_P\Big[\log\big(1 + e^{-Y\beta^T X}\big)\Big] = \inf_{\beta\in\mathbb R^d}\Big\{\frac1n\sum_{i=1}^n \log\big(1 + e^{-Y_i\beta^T X_i}\big) + \delta\,\|\beta\|_p\Big\},β∈Rdinf​ P: Dc​(P,Pn​)≤δsup​EP​[log(1+e−YβTX)]=β∈Rdinf​{n1​i=1∑n​log(1+e−Yi​βTXi​)+δ∥β∥p​}, inf⁡β∈Rd sup⁡P: Dc(P,Pn)≤δEP[(1−YβTX)+]=inf⁡β∈Rd{1n∑i=1n(1−YiβTXi)++δ ∥β∥p}.\inf_{\beta\in\mathbb R^d}\ \sup_{P:\ D_c(P,P_n)\le\delta} \mathbb E_P\Big[\big(1 - Y\beta^T X\big)^+\Big] = \inf_{\beta\in\mathbb R^d}\Big\{\frac1n\sum_{i=1}^n \big(1 - Y_i\beta^T X_i\big)^+ + \delta\,\|\beta\|_p\Big\}.β∈Rdinf​ P: Dc​(P,Pn​)≤δsup​EP​[(1−YβTX)+]=β∈Rdinf​{n1​i=1∑n​(1−Yi​βTXi​)++δ∥β∥p​}.

The distributionally robust logistic regression and support vector machine over an optimal-transport ball that may move predictors but not labels are therefore exactly the ℓp\ell_pℓp​-norm regularized estimators, with the radius δ\deltaδ as the regularization parameter.

Formalization Note The theorem is stated per β\betaβ (what the paper's proof establishes) together with the two identities of infima over β\betaβ that the paper prints. The paper prints the support-vector-machine identity without inf⁡β\inf_\betainfβ​ on the right, although β\betaβ is free there; the reading with inf⁡β\inf_\betainfβ​ on both sides is used, and the per-β\betaβ identity covers the literal reading as well. The labels Yi∈{−1,+1}Y_i \in \{-1,+1\}Yi​∈{−1,+1} come from the setting of Example 2, which Theorem 2 continues. Expectations are lower Lebesgue integrals in [0,∞][0,\infty][0,∞], the worst case is a supremum over probability measures PPP with Dc(P,Pn)≤δD_c(P,P_n) \le \deltaDc​(P,Pn​)≤δ, and couplings are probability measures with both marginals fixed. The ℓq\ell_qℓq​ norm is that of PiLp q, so q=1q = 1q=1 and q=∞q = \inftyq=∞ are included.

Preamble
import Mathlib
import Definitions.Def_WassersteinDRO_Regularization_empiricalDistribution
import Definitions.Def_RWPI_SqrtLasso_worstCase
import Definitions.Def_RWPI_SqrtLasso_Nq
import Definitions.Def_RWPI_Classif_losses

open MeasureTheory
open scoped ENNReal
Formal statement
namespace RWPI.Classif

/-- Theorem 2, p. 11: with the label-preserving cost `c = N_q` (ρ = 1) and labels
`Yᵢ ∈ {−1, +1}`, for every `δ ≥ 0` and every `β`,
1. `sup_{P : D_c(P, P_n) ≤ δ} E_P[log(1 + e^{−Yβᵀ X})] = (1/n) Σᵢ log(1 + e^{−Yᵢβᵀ Xᵢ}) + δ‖β‖_p`;
2. `sup_{P : D_c(P, P_n) ≤ δ} E_P[(1 − Yβᵀ X)⁺] = (1/n) Σᵢ (1 − Yᵢβᵀ Xᵢ)⁺ + δ‖β‖_p`;
and hence the two identities of infima over `β ∈ ℝ^d` printed in the theorem (with `inf_β` on
both sides of the SVM identity), where `1/p + 1/q = 1`. -/
theorem theorem_2 {d n : ℕ} (hn : 0 < n) (X : Fin n → Fin d → ℝ) (Y : Fin n → ℝ)
    (hY : ∀ i, Y i = 1 ∨ Y i = -1) (p q : ℝ≥0∞) (hpq : p.HolderConjugate q)
    (δ : ℝ) (hδ : 0 ≤ δ) :
    (∀ β : Fin d → ℝ,
      RWPI.SqrtLasso.worstCase (RWPI.SqrtLasso.Nq q) δ
          (WassersteinDRO.Regularization.empiricalDistribution (fun i => (X i, Y i)))
          (logLoss β) =
        ENNReal.ofReal ((1 / (n : ℝ)) * ∑ i, logLoss β (X i, Y i) + δ * ‖WithLp.toLp p β‖)) ∧
    (∀ β : Fin d → ℝ,
      RWPI.SqrtLasso.worstCase (RWPI.SqrtLasso.Nq q) δ
          (WassersteinDRO.Regularization.empiricalDistribution (fun i => (X i, Y i)))
          (hingeLoss β) =
        ENNReal.ofReal ((1 / (n : ℝ)) * ∑ i, hingeLoss β (X i, Y i) + δ * ‖WithLp.toLp p β‖)) ∧
    (⨅ β : Fin d → ℝ,
      RWPI.SqrtLasso.worstCase (RWPI.SqrtLasso.Nq q) δ
          (WassersteinDRO.Regularization.empiricalDistribution (fun i => (X i, Y i)))
          (logLoss β)) =
      (⨅ β : Fin d → ℝ,
        ENNReal.ofReal ((1 / (n : ℝ)) * ∑ i, logLoss β (X i, Y i) + δ * ‖WithLp.toLp p β‖)) ∧
    (⨅ β : Fin d → ℝ,
      RWPI.SqrtLasso.worstCase (RWPI.SqrtLasso.Nq q) δ
          (WassersteinDRO.Regularization.empiricalDistribution (fun i => (X i, Y i)))
          (hingeLoss β)) =
      (⨅ β : Fin d → ℝ,
        ENNReal.ofReal ((1 / (n : ℝ)) * ∑ i, hingeLoss β (X i, Y i) + δ * ‖WithLp.toLp p β‖)) := by sorry

end RWPI.Classif
Source
Blanchet, Kang & Murthy, Robust Wasserstein Profile Inference and Applications to Machine Learning, arXiv:1610.05627v4, p. 11, Theorem 2; proof in App. A.1, pp. 30–31
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