Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — Natarajan-dimension generalization bound for the SPO loss over a polyhedron

Proved
SPOBounds.Natarajan.natarajan_generalization_bound

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

generalization-boundnatarajan-dimensionp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1predict-then-optimizespo-loss

Let S⊆RdS\subseteq\mathbb R^dS⊆Rd be a nonempty, compact, convex polyhedron and S\mathfrak SS the set of its extreme points, and let w∗w^*w∗ be an optimization oracle for SSS whose values are extreme points of SSS. Let C\mathcal CC be a nonempty bounded set of cost vectors, let D\mathcal DD be a probability distribution on X×Rd\mathcal X\times\mathbb R^dX×Rd whose cost component lies in C\mathcal CC almost surely, and let H\mathcal HH be a family of functions f:X→Rdf:\mathcal X\to\mathbb R^df:X→Rd. Let kkk be a natural number such that every finite set N-shattered by w∗(H)={x↦w∗(f(x)):f∈H}w^*(\mathcal H)=\{x\mapsto w^*(f(x)):f\in\mathcal H\}w∗(H)={x↦w∗(f(x)):f∈H} has at most kkk points. 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​) drawn from D\mathcal DD, every f∈Hf\in\mathcal Hf∈H satisfies

RSPO(f)≤R^SPO(f)+2 ωS(C)2klog⁡(n∣S∣2)n+ωS(C)log⁡(1/δ)2n.R_{\rm SPO}(f)\le\hat R_{\rm SPO}(f)+2\,\omega_S(\mathcal C)\sqrt{\frac{2k\log(n|\mathfrak S|^2)}{n}}+\omega_S(\mathcal C)\sqrt{\frac{\log(1/\delta)}{2n}}.RSPO​(f)≤R^SPO​(f)+2ωS​(C)n2klog(n∣S∣2)​​+ωS​(C)2nlog(1/δ)​​.

With k=dN(w∗(H))k=d_N(w^*(\mathcal H))k=dN​(w∗(H)) this is the paper's Theorem 2: the SPO risk of every predictor in the class is controlled by its empirical SPO risk plus a term of order ωS(C)dNlog⁡(n∣S∣)/n\omega_S(\mathcal C)\sqrt{d_N\log(n|\mathfrak S|)/n}ωS​(C)dN​log(n∣S∣)/n​, uniformly over the class and hence for any training procedure.

Formalization Note "With probability at least 1−δ1-\delta1−δ" is stated as: the product measure Dn\mathcal D^nDn of the set of samples on which some f∈Hf\in\mathcal Hf∈H violates the inequality is at most δ\deltaδ (outer measure for a non-measurable set, so the strong form). Added hypotheses, all disclosed: (i) the oracle returns extreme points of SSS, the proof's own "w.l.o.g." (p. 31), since p. 10 allows non-extreme optimal points under ties; (ii) the three measurability hypotheses of Theorem 1 (each loss function z↦ℓSPO(f(z1),z2)z\mapsto\ell_{\rm SPO}(f(z_1),z_2)z↦ℓSPO​(f(z1​),z2​) measurable; the uniform deviation and, for each sign vector, the signed supremum a.e.-measurable in the sample), on which the paper is silent. dNd_NdN​ is replaced by an upper bound kkk on the sizes of N-shattered sets (equivalent when dN<∞d_N<\inftydN​<∞; the printed bound is vacuous otherwise). ∣S∣|\mathfrak S|∣S∣ is Set.ncard of the extreme points; the logarithm is natural.

Preamble
import Mathlib
import Definitions.Def_SPOBounds_Natarajan_Model
import Definitions.Def_SPOBounds_Natarajan_Rademacher
import Definitions.Def_SPOBounds_Natarajan_NatarajanDim

open MeasureTheory
Formal statement
namespace SPOBounds.Natarajan

/-- **Theorem 2, second display** (arXiv:1905.11488v3, p. 11). Let `S` be a nonempty compact
convex polyhedron with extreme-point set `𝔖`, let the oracle `w` return extreme points of `S`,
let every set N-shattered by `w*(H)` have at most `k` elements, and let the cost vectors lie
almost surely in the nonempty bounded set `C`. For any `δ > 0`, with probability at least
`1 − δ` over an i.i.d. sample of size `n ≥ 1`, every `f ∈ H` satisfies
`R_SPO(f) ≤ R̂_SPO(f) + 2 ω_S(C) √(2 k log(n |𝔖|²) / n) + ω_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 `δ`. The measurability hypotheses `hℓ`, `hΦ`, `hA` are added (the paper is silent). -/
theorem natarajan_generalization_bound {d : ℕ} {X : Type*} [MeasurableSpace X]
    (S : Set (EuclideanSpace ℝ (Fin d))) (hS : S.Nonempty) (hSc : IsCompact S)
    (hSv : Convex ℝ S) (hSp : IsPolyhedron S)
    (w : EuclideanSpace ℝ (Fin d) → EuclideanSpace ℝ (Fin d)) (hw : IsOracle S w)
    (hwv : ∀ c, w c ∈ Set.extremePoints ℝ S)
    (C : Set (EuclideanSpace ℝ (Fin d))) (hC : C.Nonempty) (hCb : Bornology.IsBounded C)
    (D : Measure (X × EuclideanSpace ℝ (Fin d))) [IsProbabilityMeasure D]
    (hDC : ∀ᵐ z ∂D, z.2 ∈ C)
    (H : Set (X → EuclideanSpace ℝ (Fin d)))
    (hℓ : ∀ f ∈ H, Measurable (fun z : X × EuclideanSpace ℝ (Fin d) => spoLoss w (f z.1) z.2))
    (k : ℕ) (hk : ∀ T : Finset X, NShatters (oracleClass w H) T → T.card ≤ k)
    (n : ℕ) (hn : 0 < n)
    (hΦ : AEMeasurable (fun s : Fin n → X × EuclideanSpace ℝ (Fin d) => supDeviation D w H s)
      (Measure.pi fun _ : Fin n => D))
    (hA : ∀ σ : Fin n → Bool,
      AEMeasurable (fun s : Fin n → X × EuclideanSpace ℝ (Fin d) => signedSup w H σ s)
        (Measure.pi fun _ : Fin n => D))
    (δ : ℝ) (hδ : 0 < δ) :
    Measure.pi (fun _ : Fin n => D)
        {s | ∃ f ∈ H, ¬ (spoRisk D w f ≤ empRisk w f s +
          2 * linGapSet S C * Real.sqrt (2 * k *
            Real.log ((n : ℝ) * ((Set.extremePoints ℝ S).ncard : ℝ) ^ 2) / n) +
          linGapSet S C * Real.sqrt (Real.log (1 / δ) / (2 * n)))} ≤ ENNReal.ofReal δ := by sorry

end SPOBounds.Natarajan
Source
El Balghiti, Elmachtoub, Grigas, Tewari, Generalization Bounds in the Predict-then-Optimize Framework, arXiv:1905.11488v3, p. 11, Theorem 2, second display
Read-back

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

Throughout, E=RdE = \mathbb{R}^dE=Rd with its Euclidean structure. Several names come from imported definition files whose code was not provided: IsPolyhedron, IsOracle, spoLoss, spoRisk, empRisk, linGapSet, oracleClass, NShatters, supDeviation, signedSup. This read-back therefore cannot unfold them. It describes only how the statement uses them, and each one means exactly what its imported definition says. The doc-comment above the theorem is a comment, not part of the assertion, and is not used here.

Data and hypotheses. Fix a natural number ddd and a type XXX with a σ-algebra. The theorem assumes the following.

  • The feasible set. S⊆ES \subseteq ES⊆E is nonempty, compact and convex, and satisfies the imported predicate IsPolyhedron.
  • The oracle. w:E→Ew : E \to Ew:E→E is any function that:
    • satisfies the imported predicate IsOracle relative to SSS;
    • for every c∈Ec \in Ec∈E (including c=0c = 0c=0), returns an extreme point w(c)w(c)w(c) of SSS. Write ext⁡(S)\operatorname{ext}(S)ext(S) for the set of extreme points of SSS.
  • The cost set. C⊆EC \subseteq EC⊆E is nonempty and bounded.
  • The distribution. DDD is a probability measure on X×EX \times EX×E. For DDD-almost every pair z=(x,c)z = (x, c)z=(x,c), the second component ccc lies in CCC.
  • The hypothesis class. HHH is an arbitrary set of functions f:X→Ef : X \to Ef:X→E. No measurability of fff itself is required.
  • Measurability of the loss. For every f∈Hf \in Hf∈H, the map (x,c)↦spoLossw(f(x),c)(x, c) \mapsto \mathrm{spoLoss}_w(f(x), c)(x,c)↦spoLossw​(f(x),c) is measurable.
  • Natarajan-dimension bound. kkk is a natural number. For every finite set T⊆XT \subseteq XT⊆X that is shattered by oracleClass(w,H)\mathrm{oracleClass}(w, H)oracleClass(w,H), in the sense of the imported NShatters, we have ∣T∣≤k|T| \le k∣T∣≤k.
  • Sample size. nnn is a natural number with n≥1n \ge 1n≥1. DnD^nDn is the nnn-fold product measure on samples s=(s1,…,sn)∈(X×E)ns = (s_1, \dots, s_n) \in (X \times E)^ns=(s1​,…,sn​)∈(X×E)n.
  • Measurability of the deviation. The map s↦supDeviation(D,w,H,s)s \mapsto \mathrm{supDeviation}(D, w, H, s)s↦supDeviation(D,w,H,s) is DnD^nDn-almost-everywhere measurable.
  • Measurability of the signed suprema. For every sign pattern σ:{1,…,n}→{true,false}\sigma : \{1, \dots, n\} \to \{\text{true}, \text{false}\}σ:{1,…,n}→{true,false}, the map s↦signedSup(w,H,σ,s)s \mapsto \mathrm{signedSup}(w, H, \sigma, s)s↦signedSup(w,H,σ,s) is DnD^nDn-almost-everywhere measurable.
  • Confidence level. δ\deltaδ is a real number with δ>0\delta > 0δ>0. There is no upper bound on δ\deltaδ.

Notation for the bound.

  • R(f)=spoRisk(D,w,f)R(f) = \mathrm{spoRisk}(D, w, f)R(f)=spoRisk(D,w,f) is the imported population risk.
  • R^s(f)=empRisk(w,f,s)\hat R_s(f) = \mathrm{empRisk}(w, f, s)R^s​(f)=empRisk(w,f,s) is the imported empirical risk on the sample sss.
  • ω=linGapSet(S,C)\omega = \mathrm{linGapSet}(S, C)ω=linGapSet(S,C) is an imported real number.
  • m=ncard⁡(ext⁡(S))m = \operatorname{ncard}(\operatorname{ext}(S))m=ncard(ext(S)) is the number of extreme points of SSS, as a natural number. By this convention it would be 000 if the set were infinite.

Define

B=R^s(f)+2 ω 2k log⁡(n m2)n+ω log⁡(1/δ)2n.B = \hat R_s(f) + 2\,\omega\,\sqrt{\frac{2k\,\log(n\,m^2)}{n}} + \omega\,\sqrt{\frac{\log(1/\delta)}{2n}}.B=R^s​(f)+2ωn2klog(nm2)​​+ω2nlog(1/δ)​​.

Conclusion. The DnD^nDn-measure of the set of samples sss for which some f∈Hf \in Hf∈H has R(f)>BR(f) > BR(f)>B (that is, fails R(f)≤BR(f) \le BR(f)≤B) is at most δ\deltaδ:

Dn({ s:∃f∈H, ¬ (R(f)≤B) })≤δ.D^n\bigl(\{\, s : \exists f \in H,\ \neg\,(R(f) \le B) \,\}\bigr) \le \delta.Dn({s:∃f∈H, ¬(R(f)≤B)})≤δ.
  • The set is not asserted to be measurable, so DnD^nDn here is the outer measure.
  • The right-hand side is δ\deltaδ viewed as an extended nonnegative real.

Degenerate cases.

  • Large δ\deltaδ. If δ≥1\delta \ge 1δ≥1, the conclusion holds trivially, because DnD^nDn is a probability measure. Also, when δ>1\delta > 1δ>1, log⁡(1/δ)<0\log(1/\delta) < 0log(1/δ)<0 and the real square root returns 000, so the last term vanishes. When δ=1\delta = 1δ=1 it is 000 as well.
  • k=0k = 0k=0. The middle term is 000.
  • Logarithm term. Since n≥1n \ge 1n≥1, log⁡(n m2)\log(n\,m^2)log(nm2) is taken of a nonnegative real.
    • If m=0m = 0m=0 (an infinite or empty extreme-point set), this is log⁡0\log 0log0, which evaluates to 000 by convention.
    • If n=1n = 1n=1 and m=1m = 1m=1, it is log⁡1=0\log 1 = 0log1=0.
    • In both cases the middle term vanishes.
  • d=0d = 0d=0. EEE is a single point, so S=C={0}S = C = \{0\}S=C={0} and www is constant.
  • XXX. XXX cannot be empty, since DDD is a probability measure on X×EX \times EX×E.
  • Empty HHH. If HHH is empty, the exceptional set is empty and the statement is trivial.
  • Imported quantities. RRR, R^\hat RR^ and ω\omegaω take whatever values their imported definitions give. That includes any default values those definitions produce, for example an integral of a non-integrable function or a supremum of an empty or unbounded set, and the bound is stated against those values as they are.
  • Sign convention. The statement reads "true"/"false" in σ\sigmaσ as whatever sign convention signedSup uses.
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