Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 β€” β„œΜ‚_N(𝒒; S_N) ≀ L β„œΜ‚_N(F; S_N^x) and β„œ_N(𝒒) ≀ L β„œ_N(F) for costs L-Lipschitz in the ∞-norm

Proved
PrescAnalytics.ERM.lemma_1_comparison

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

contraction-inequalitylipschitzp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1rademacher-complexity

Let X\mathcal XX and Y\mathcal YY be measurable spaces, F\mathcal FF a class of decision rules f:Xβ†’Rdf:\mathcal X\to\mathbb R^df:Xβ†’Rd, and c(z;y)c(z;y)c(z;y) a cost that is LLL-Lipschitz in zzz with respect to the ∞\infty∞-norm, uniformly over yyy:

∣c(z;y)βˆ’c(zβ€²;y)βˆ£β‰€Lmax⁑k=1,…,d∣zkβˆ’zkβ€²βˆ£forΒ allΒ z,zβ€²βˆˆRd,Β y∈Y,|c(z;y)-c(z';y)|\le L\max_{k=1,\dots,d}|z_k-z'_k|\qquad\text{for all }z,z'\in\mathbb R^d,\ y\in\mathcal Y,∣c(z;y)βˆ’c(zβ€²;y)βˆ£β‰€Lk=1,…,dmaxβ€‹βˆ£zkβ€‹βˆ’zkβ€²β€‹βˆ£forΒ allΒ z,zβ€²βˆˆRd,Β y∈Y,

with Lβ‰₯0L\ge0Lβ‰₯0. Let G={(x,y)↦c(f(x);y):f∈F}\mathcal G=\{(x,y)\mapsto c(f(x);y):f\in\mathcal F\}G={(x,y)↦c(f(x);y):f∈F}. Then:

  1. for every NNN and every sample SN=((x1,y1),…,(xN,yN))S_N=((x^1,y^1),\dots,(x^N,y^N))SN​=((x1,y1),…,(xN,yN)), with SNx=(x1,…,xN)S_N^x=(x^1,\dots,x^N)SNx​=(x1,…,xN),
R^N(G;SN)≀L R^N(F;SNx);\widehat{\mathfrak R}_N(\mathcal G;S_N)\le L\,\widehat{\mathfrak R}_N(\mathcal F;S_N^x);RN​(G;SN​)≀LRN​(F;SNx​);
  1. for every probability measure ΞΌ\muΞΌ on XΓ—Y\mathcal X\times\mathcal YXΓ—Y and every NNN, if every f∈Ff\in\mathcal Ff∈F is measurable, F\mathcal FF is pointwise separable and ccc is jointly measurable,
RN(G)≀L RN(F),\mathfrak R_N(\mathcal G)\le L\,\mathfrak R_N(\mathcal F),RN​(G)≀LRN​(F),

where RN(G)\mathfrak R_N(\mathcal G)RN​(G) samples (x,y)(x,y)(x,y) i.i.d. from ΞΌ\muΞΌ and RN(F)\mathfrak R_N(\mathcal F)RN​(F) samples xxx i.i.d. from the marginal ΞΌX\mu_XΞΌX​ of ΞΌ\muΞΌ.

The left sides are univariate complexities, the right sides multivariate. This comparison lemma extends Ledoux and Talagrand's contraction principle to vector-valued classes with the ∞\infty∞-norm and constant 111; it is what lets the out-of-sample bound of Theorem 13 be stated in terms of the decision rules alone.

Formalization Note The paper writes the Lipschitz condition as sup⁑zβ‰ zβ€²(c(z;y)βˆ’c(zβ€²;y))/max⁑k∣zkβˆ’zkβ€²βˆ£β‰€L<∞\sup_{z\ne z'}(c(z;y)-c(z';y))/\max_k|z_k-z'_k|\le L<\inftysupzξ€ =z′​(c(z;y)βˆ’c(zβ€²;y))/maxkβ€‹βˆ£zkβ€‹βˆ’zkβ€²β€‹βˆ£β‰€L<∞, which is the two-sided bound above (swap z,zβ€²z,z'z,zβ€²); the Lean norm on Fin d β†’ ℝ is this max. Complexities are in EReal (empirical) and [0,∞][0,\infty][0,∞] (marginal), with 0β‹…(±∞)=00\cdot(\pm\infty)=00β‹…(±∞)=0; when L=0L=0L=0 the cost does not depend on zzz and both sides are 000 for nonempty F\mathcal FF. The paper states part 2 with no measurability assumptions; the Lean adds measurable rules, a pointwise separable class and a measurable cost, the conventions under which the expectations are defined.

Preamble
import Mathlib
import Definitions.Def_PrescAnalytics_ERM_Basic
Formal statement
namespace PrescAnalytics.ERM

open MeasureTheory

/-- Lemma 1 (pp. 39–40), multivariate comparison lemma. If the cost `c(z; y)` is `L`-Lipschitz in
the decision `z ∈ ℝ^d` with respect to the `∞`-norm, uniformly over `y`, then for the cost class
`𝒒 = {(x, y) ↦ c(f(x); y) : f ∈ F}`:
(i) on every sample `S_N`, `β„œΜ‚_N(𝒒; S_N) ≀ L β„œΜ‚_N(F; S_N^x)`;
(ii) for i.i.d. sampling from `ΞΌ`, `β„œ_N(𝒒) ≀ L β„œ_N(F)`, where `β„œ_N(F)` samples only the
covariates, i.e. from the marginal `ΞΌ_X` of `ΞΌ`. Part (ii) carries the measurability conventions
(measurable rules, pointwise separable class, measurable cost) under which the expectations exist. -/
theorem lemma_1_comparison {X Y : Type*} [MeasurableSpace X] [MeasurableSpace Y] {d : β„•}
    (F : Set (X β†’ Fin d β†’ ℝ)) (c : (Fin d β†’ ℝ) β†’ Y β†’ ℝ) (L : ℝ) (hL : 0 ≀ L)
    (hc_lip : βˆ€ (z z' : Fin d β†’ ℝ) (y : Y), |c z y - c z' y| ≀ L * β€–z - z'β€–) :
    (βˆ€ (N : β„•) (s : Fin N β†’ X Γ— Y),
        empRademacherR (costClass c F) s ≀ (L : EReal) * empRademacher F (fun i => (s i).1)) ∧
    (βˆ€ (ΞΌ : Measure (X Γ— Y)) [IsProbabilityMeasure ΞΌ] (N : β„•),
        (βˆ€ f ∈ F, Measurable f) β†’ IsPointwiseSeparable F β†’ Measurable (Function.uncurry c) β†’
        margRademacherR ΞΌ N (costClass c F) ≀
          ENNReal.ofReal L * margRademacher (ΞΌ.map Prod.fst) N F) := by sorry

end PrescAnalytics.ERM
Source
Bertsimas, Kallus, From Predictive to Prescriptive Analytics, arXiv:1402.5481v4, pp. 39–40, Lemma 1
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