Lemma 1 β βΜ_N(π’; S_N) β€ L βΜ_N(F; S_N^x) and β_N(π’) β€ L β_N(F) for costs L-Lipschitz in the β-norm
ProvedPrescAnalytics.ERM.lemma_1_comparisonLet and be measurable spaces, a class of decision rules , and a cost that is -Lipschitz in with respect to the -norm, uniformly over :
with . Let . Then:
- for every and every sample , with ,
- for every probability measure on and every , if every is measurable, is pointwise separable and is jointly measurable,
where samples i.i.d. from and samples i.i.d. from the marginal of .
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 -norm and constant ; 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 , which is the two-sided bound above (swap ); the Lean norm on Fin d β β is this max. Complexities are in EReal (empirical) and (marginal), with ; when the cost does not depend on and both sides are for nonempty . 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.
import Mathlib import Definitions.Def_PrescAnalytics_ERM_Basic
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.