Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4 — margin-based generalization bound for the SPO loss under the strength property (ℓ2\ell_2ℓ2​ case)

Proved
SPOBounds.Margin.margin_generalization_bound

by mikedeng1 · Sep 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

generalization-boundmarginp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1predict-then-optimizerademacher-complexity

Work in the ℓ2\ell_2ℓ2​ set-up: decisions in Rd\mathbb R^dRd with the Euclidean norm, cost vectors with its dual (again Euclidean) norm. Let S⊆RdS\subseteq\mathbb R^dS⊆Rd be nonempty, compact, convex and not a singleton, w∗w^*w∗ any optimization oracle for SSS, and suppose SSS satisfies the strength property with parameter μ>0\mu>0μ>0. Fix γ>0\gamma>0γ>0. Let D\mathcal DD be a probability distribution on feature–cost pairs (x,c)(x,c)(x,c) whose cost lies almost surely in a nonempty bounded set C\mathcal CC, and let H\mathcal HH be a class of functions from X\mathcal XX to Rd\mathbb R^dRd. Then for every n≥1n\ge1n≥1 and every δ>0\delta>0δ>0, with probability at least 1−δ1-\delta1−δ over an i.i.d. sample (x1,c1),…,(xn,cn)(x_1,c_1),\dots,(x_n,c_n)(x1​,c1​),…,(xn​,cn​) from D\mathcal DD, every f∈Hf\in\mathcal Hf∈H satisfies

RSPO(f)  ≤  R^SPOγ(f)+(22 ρ2(C)+22 μ⋅ωS(C)γμ) Rn(H)+ωS(C)log⁡(1/δ)2n.R_{\rm SPO}(f)\;\le\;\hat R^\gamma_{\rm SPO}(f)+\Big(\frac{2\sqrt2\,\rho_2(\mathcal C)+2\sqrt2\,\mu\cdot\omega_S(\mathcal C)}{\gamma\mu}\Big)\,\mathfrak R^n(\mathcal H)+\omega_S(\mathcal C)\sqrt{\frac{\log(1/\delta)}{2n}} .RSPO​(f)≤R^SPOγ​(f)+(γμ22​ρ2​(C)+22​μ⋅ωS​(C)​)Rn(H)+ωS​(C)2nlog(1/δ)​​.

Here RSPOR_{\rm SPO}RSPO​ is the SPO risk, R^SPOγ\hat R^\gamma_{\rm SPO}R^SPOγ​ the empirical γ\gammaγ-margin SPO risk, Rn(H)\mathfrak R^n(\mathcal H)Rn(H) the expected multivariate Rademacher complexity, ρ2(C)=sup⁡c∈C∥c∥2\rho_2(\mathcal C)=\sup_{c\in\mathcal C}\|c\|_2ρ2​(C)=supc∈C​∥c∥2​ and ωS(C)=sup⁡c∈CωS(c)\omega_S(\mathcal C)=\sup_{c\in\mathcal C}\omega_S(c)ωS​(C)=supc∈C​ωS​(c).

This is the paper's margin-based generalization bound: the complexity term is the multivariate Rademacher complexity of H\mathcal HH, which for common classes grows mildly in the dimensions, at the price of the empirical margin loss in place of the empirical SPO loss.

Formalization Note "With probability at least 1−δ1-\delta1−δ" is stated as: the (outer) measure under Dn\mathcal D^nDn of the samples on which some f∈Hf\in\mathcal Hf∈H violates the bound is at most δ\deltaδ. The cost space carries the Borel σ\sigmaσ-algebra. The paper is silent on measurability; added hypotheses are that every f∈Hf\in\mathcal Hf∈H and its SPO loss (x,c)↦ℓSPO(f(x),c)(x,c)\mapsto\ell_{\rm SPO}(f(x),c)(x,c)↦ℓSPO​(f(x),c) are measurable, that the uniform deviation sup⁡f(E[ℓSPOγ(f(x),c)]−R^SPOγ(f))\sup_{f}\big(\mathbb E[\ell^\gamma_{\rm SPO}(f(x),c)]-\hat R^\gamma_{\rm SPO}(f)\big)supf​(E[ℓSPOγ​(f(x),c)]−R^SPOγ​(f)) and the margin Rademacher suprema are a.e.-measurable in the sample, and that the multivariate Rademacher sums are almost surely bounded above and R^n(H)\hat{\mathfrak R}^n(\mathcal H)R^n(H) is integrable over samples, so that Rn(H)\mathfrak R^n(\mathcal H)Rn(H) is the paper's expectation (when it is infinite the bound is vacuous).

Preamble
import Mathlib
import Definitions.Def_SPOBounds_Margin_Model
import Definitions.Def_SPOBounds_Margin_Degeneracy
import Definitions.Def_SPOBounds_Margin_Rademacher

open MeasureTheory
Formal statement
namespace SPOBounds.Margin

/-- **Theorem 4, second display** (arXiv:1905.11488v3, pp. 19–20). ℓ₂ set-up: `E = ℝ^d` with the
Euclidean norm, costs and predictions in its dual (operator norm = Euclidean norm), with the Borel
σ-algebra. Let `S` be nonempty, compact, convex and not a singleton, `w` any oracle, and suppose
`S` satisfies the strength property with parameter `μ > 0`. Fix `γ > 0`, a nonempty bounded set
`C` containing the cost vector almost surely, and any `δ > 0`. Then with probability at least
`1 − δ` over an i.i.d. sample of size `n` from `D`, every `f ∈ H` satisfies
`R_SPO(f) ≤ R̂^γ_SPO(f) + ((2√2 ρ₂(C) + 2√2 μ ω_S(C)) / (γ μ)) ℜⁿ(H) + ω_S(C) √(log(1/δ) / (2n))`.
Stated as: the (outer) `Dⁿ`-measure of the samples on which some `f ∈ H` violates the bound is at
most `δ`. Added hypotheses (the paper is silent): measurability of each `f ∈ H` and of its SPO
loss (`hf`, `hℓ`), of the uniform deviation and of the margin Rademacher sups (`hΦ`, `hA`); and
almost-sure boundedness plus integrability of the multivariate empirical Rademacher complexity
(`hBdd`, `hInt`), without which `ℜⁿ(H)` is not the paper's quantity. -/
theorem margin_generalization_bound {d : ℕ} {X : Type*} [MeasurableSpace X]
    [MeasurableSpace (StrongDual ℝ (EuclideanSpace ℝ (Fin d)))]
    [BorelSpace (StrongDual ℝ (EuclideanSpace ℝ (Fin d)))]
    (S : Set (EuclideanSpace ℝ (Fin d))) (hS : S.Nonempty) (hSc : IsCompact S)
    (hSv : Convex ℝ S) (hSnt : S.Nontrivial)
    (w : StrongDual ℝ (EuclideanSpace ℝ (Fin d)) → EuclideanSpace ℝ (Fin d)) (hw : IsOracle S w)
    (μ : ℝ) (hμ : 0 < μ) (hstr : StrengthProperty S μ w)
    (γ : ℝ) (hγ : 0 < γ)
    (C : Set (StrongDual ℝ (EuclideanSpace ℝ (Fin d)))) (hC : C.Nonempty)
    (hCb : Bornology.IsBounded C)
    (D : Measure (X × StrongDual ℝ (EuclideanSpace ℝ (Fin d)))) [IsProbabilityMeasure D]
    (hDC : ∀ᵐ z ∂D, z.2 ∈ C)
    (H : Set (X → StrongDual ℝ (EuclideanSpace ℝ (Fin d))))
    (hf : ∀ f ∈ H, Measurable f)
    (hℓ : ∀ f ∈ H,
      Measurable (fun z : X × StrongDual ℝ (EuclideanSpace ℝ (Fin d)) => spoLoss w (f z.1) z.2))
    (n : ℕ) (hn : 0 < n)
    (hΦ : AEMeasurable
      (fun s : Fin n → X × StrongDual ℝ (EuclideanSpace ℝ (Fin d)) =>
        marginSupDeviation S w γ D H s)
      (Measure.pi fun _ : Fin n => D))
    (hA : ∀ σ : Fin n → Bool,
      AEMeasurable
        (fun s : Fin n → X × StrongDual ℝ (EuclideanSpace ℝ (Fin d)) =>
          marginSignedSup S w γ H σ s)
        (Measure.pi fun _ : Fin n => D))
    (hBdd : ∀ᵐ s ∂(Measure.pi fun _ : Fin n => D), ∀ σ : Fin n → Fin d → Bool,
      BddAbove (Set.range fun f : H => (1 / n : ℝ) *
        ∑ i, (f : X → StrongDual ℝ (EuclideanSpace ℝ (Fin d))) (s i).1 (signVec (σ i))))
    (hInt : Integrable
      (fun s : Fin n → X × StrongDual ℝ (EuclideanSpace ℝ (Fin d)) =>
        empRademacherMulti H (fun i => (s i).1))
      (Measure.pi fun _ : Fin n => D))
    (δ : ℝ) (hδ : 0 < δ) :
    Measure.pi (fun _ : Fin n => D)
        {s | ∃ f ∈ H, ¬ (spoRisk D w f ≤ empMarginRisk S w γ f s +
          (2 * Real.sqrt 2 * rhoSet C + 2 * Real.sqrt 2 * μ * omegaSet S C) / (γ * μ) *
            expRademacherMulti D H n +
          omegaSet S C * Real.sqrt (Real.log (1 / δ) / (2 * n)))} ≤ ENNReal.ofReal δ := by sorry

end SPOBounds.Margin
Source
El Balghiti, Elmachtoub, Grigas, Tewari, Generalization Bounds in the Predict-then-Optimize Framework, arXiv:1905.11488v3, pp. 19–20, Theorem 4, second display
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

The statement is about a dimension ddd and a type XXX of features. Let E=RdE=\mathbb{R}^dE=Rd with the Euclidean norm, and let E∗E^*E∗ be its dual: the continuous linear functionals E→RE\to\mathbb{R}E→R. XXX carries some measurable structure, which can be anything. E∗E^*E∗ carries some measurable structure that is assumed to be its Borel σ-algebra. The statement also uses several named notions that are imported and not unfolded in the code I was given: IsOracle\mathrm{IsOracle}IsOracle, StrengthProperty\mathrm{StrengthProperty}StrengthProperty, ℓSPO\ell_{\mathrm{SPO}}ℓSPO​ (spoLoss), RSPOR_{\mathrm{SPO}}RSPO​ (spoRisk), R^γ\hat R^{\gamma}R^γ (empMarginRisk), ρ(⋅)\rho(\cdot)ρ(⋅) (rhoSet), ωS(⋅)\omega_S(\cdot)ωS​(⋅) (omegaSet), Rn\mathfrak{R}^nRn (expRademacherMulti), R^\hat{\mathfrak R}R^ (empRademacherMulti), Φ\PhiΦ (marginSupDeviation), AAA (marginSignedSup) and sv\mathrm{sv}sv (signVec). What each one means depends on its definition in those imported files. Below they are described only by how they are used.

The hypotheses are:

  • The feasible set S⊆ES\subseteq ES⊆E: SSS is nonempty, compact and convex. It is also nontrivial: it contains two distinct points.
  • The oracle: w:E∗→Ew:E^*\to Ew:E∗→E is a map with IsOracle(S,w)\mathrm{IsOracle}(S,w)IsOracle(S,w).
  • Strength: μ∈R\mu\in\mathbb{R}μ∈R with μ>0\mu>0μ>0 and StrengthProperty(S,μ,w)\mathrm{StrengthProperty}(S,\mu,w)StrengthProperty(S,μ,w).
  • The margin: γ∈R\gamma\in\mathbb{R}γ∈R with γ>0\gamma>0γ>0.
  • The cost set C⊆E∗C\subseteq E^*C⊆E∗: CCC is nonempty and bounded.
  • The distribution: DDD is a probability measure on X×E∗X\times E^*X×E∗. Under DDD, the second coordinate (the cost) lies in CCC almost surely.
  • The hypothesis class: HHH is a set of functions f:X→E∗f:X\to E^*f:X→E∗.
    • Every f∈Hf\in Hf∈H is measurable.
    • For every f∈Hf\in Hf∈H, the map (x,c)↦ℓSPO(w; f(x), c)(x,c)\mapsto \ell_{\mathrm{SPO}}(w;\,f(x),\,c)(x,c)↦ℓSPO​(w;f(x),c) is measurable on X×E∗X\times E^*X×E∗.
  • The sample size: n∈Nn\in\mathbb{N}n∈N with n>0n>0n>0. Write DnD^nDn for the product measure on samples s=(s1,…,sn)s=(s_1,\dots,s_n)s=(s1​,…,sn​), where si=(xi,ci)∈X×E∗s_i=(x_i,c_i)\in X\times E^*si​=(xi​,ci​)∈X×E∗.
  • Measurability of Φ\PhiΦ: the map s↦Φ(S,w,γ,D,H,s)s\mapsto \Phi(S,w,\gamma,D,H,s)s↦Φ(S,w,γ,D,H,s) (marginSupDeviation) is almost-everywhere measurable with respect to DnD^nDn.
  • Measurability of AAA: for every sign pattern σ∈{true,false}n\sigma\in\{\text{true},\text{false}\}^nσ∈{true,false}n, the map s↦A(S,w,γ,H,σ,s)s\mapsto A(S,w,\gamma,H,\sigma,s)s↦A(S,w,γ,H,σ,s) (marginSignedSup) is almost-everywhere measurable with respect to DnD^nDn.
  • Boundedness: for DnD^nDn-almost every sample sss, and for every σ:{1,…,n}×{1,…,d}→{true,false}\sigma:\{1,\dots,n\}\times\{1,\dots,d\}\to\{\text{true},\text{false}\}σ:{1,…,n}×{1,…,d}→{true,false}, the following set of reals is bounded above:
{1n∑i=1nf(xi)(sv(σi))  :  f∈H}.\Big\{\tfrac1n\sum_{i=1}^n f(x_i)\big(\mathrm{sv}(\sigma_i)\big)\;:\;f\in H\Big\}.{n1​i=1∑n​f(xi​)(sv(σi​)):f∈H}.

Here σi∈{true,false}d\sigma_i\in\{\text{true},\text{false}\}^dσi​∈{true,false}d, and sv(σi)\mathrm{sv}(\sigma_i)sv(σi​) is the vector in EEE that signVec assigns to it. The functional f(xi)f(x_i)f(xi​) is evaluated at that vector.

  • Integrability: the map s↦R^(H; x1,…,xn)s\mapsto \hat{\mathfrak R}(H;\,x_1,\dots,x_n)s↦R^(H;x1​,…,xn​) is integrable with respect to DnD^nDn. This quantity (empRademacherMulti) depends only on the feature coordinates of the sample.
  • Confidence: δ∈R\delta\in\mathbb{R}δ∈R with δ>0\delta>0δ>0. No upper bound on δ\deltaδ is assumed.

Conclusion. Define the bad set

B={s∈(X×E∗)n  :  ∃f∈H, ¬(RSPO(D,w,f)≤R^γ(S,w,f,s)+22 ρ(C)+22 μ ωS(C)γμ Rn(D,H)+ωS(C)log⁡(1/δ)2n)}.B=\Big\{s\in (X\times E^*)^n \;:\; \exists f\in H,\ \neg\Big(R_{\mathrm{SPO}}(D,w,f)\le \hat R^{\gamma}(S,w,f,s)+\frac{2\sqrt2\,\rho(C)+2\sqrt2\,\mu\,\omega_S(C)}{\gamma\mu}\,\mathfrak R^n(D,H)+\omega_S(C)\sqrt{\frac{\log(1/\delta)}{2n}}\Big)\Big\}.B={s∈(X×E∗)n:∃f∈H, ¬(RSPO​(D,w,f)≤R^γ(S,w,f,s)+γμ22​ρ(C)+22​μωS​(C)​Rn(D,H)+ωS​(C)2nlog(1/δ)​​)}.

The statement says that

Dn(B)≤max⁡(δ,0)=δ,D^n(B)\le \max(\delta,0)=\delta,Dn(B)≤max(δ,0)=δ,

where both sides are compared as extended non-negative reals.

  • The symbols in BBB are applied to these arguments:

    • RSPO(D,w,f)R_{\mathrm{SPO}}(D,w,f)RSPO​(D,w,f) is spoRisk applied to D,w,fD,w,fD,w,f.
    • R^γ(S,w,f,s)\hat R^{\gamma}(S,w,f,s)R^γ(S,w,f,s) is empMarginRisk applied to S,w,γ,f,sS,w,\gamma,f,sS,w,γ,f,s.
    • ρ(C)\rho(C)ρ(C) is rhoSet of CCC.
    • ωS(C)\omega_S(C)ωS​(C) is omegaSet of SSS and CCC.
    • Rn(D,H)\mathfrak R^n(D,H)Rn(D,H) is expRademacherMulti of D,H,nD,H,nD,H,n.
  • Nothing in the code states that BBB is measurable. The product measure applied to a set that may not be measurable is its outer measure.

  • "Violates" means the stated inequality between real numbers fails.

  • Real-valued definitions are total. So if spoRisk or expRademacherMulti is defined through Bochner integrals or suprema, the following apply:

    • A non-integrable integrand contributes 000.
    • A set with no upper bound, or an empty set, has supremum 000.

    The code states integrability only for R^\hat{\mathfrak R}R^. It does not state integrability of the SPO loss under DDD.

Degenerate cases.

  • d=0d=0d=0: EEE has exactly one point, so no SSS can be nontrivial. The hypotheses cannot all hold, and the statement is vacuous.
  • Empty XXX: X×E∗X\times E^*X×E∗ is empty and carries no probability measure. The statement is again vacuous.
  • SSS nonempty: this hypothesis adds nothing, because nontriviality already implies it.
  • H=∅H=\emptysetH=∅: BBB is empty and the bound holds trivially.
  • δ≥1\delta\ge1δ≥1:
    • log⁡(1/δ)≤0\log(1/\delta)\le 0log(1/δ)≤0. The square root of a non-positive real is taken to be 000, so the last term vanishes.
    • The right-hand side δ≥1\delta\ge1δ≥1 is at least the total mass of the probability measure DnD^nDn, so the conclusion holds trivially.
  • 0<δ<10<\delta<10<δ<1: this is the only range where the inequality says something beyond the total mass of DnD^nDn.
  • No division by zero: n>0n>0n>0, γ>0\gamma>0γ>0 and μ>0\mu>0μ>0, so the divisions 1/n1/n1/n, 1/(2n)1/(2n)1/(2n) and 1/(γμ)1/(\gamma\mu)1/(γμ) are never by zero.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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