Theorem 14 (29) — w.p. ≥ 1 − δ, E g(T) ≤ (1/N) Σ g(uⁱ) + ḡ√(log(1/δ)/2N) + ℜ_N(𝒢) for all g ∈ 𝒢 (0 ≤ g ≤ ḡ)
ProvedPrescAnalytics.ERM.theorem_14_eq29Let be a probability measure on a measurable space , and let be a pointwise separable class of measurable functions with
Let , , and let be an i.i.d. sample from , i.e. drawn from the product measure . Then, with probability at least ,
where and is the marginal Rademacher complexity (factor , no absolute value).
This is the first half of the paper's restatement of the main uniform deviation bound of Bartlett and Mendelson (2003); applied to the cost class of a family of decision rules it gives inequality (26) of Theorem 13.
Formalization Note The paper assumes only ; the printed statement is false without (with , uniform on , , , the bound fails with probability ), so the Lean adds and keeps every printed constant. "With probability " is stated as: the set of samples on which the inequality fails for some has outer -measure at most . The inequality is written as in , which is equivalent since . Pointwise separability is the added measurability convention. For , Lean's is and the claim is trivial, as on the page.
import Mathlib import Definitions.Def_PrescAnalytics_ERM_Basic
namespace PrescAnalytics.ERM
open MeasureTheory
/-- Theorem 14, (29) (p. 40), with the corrected boundedness `0 ≤ g ≤ ḡ`. Let `G` be a pointwise
separable class of measurable functions `U → ℝ` with values in `[0, ḡ]`, `P` a probability measure on
`U`, `N ≥ 1`, `δ > 0`. Outside a set of `P^N`-measure at most `δ`, every sample
`S_N = (u^1, …, u^N)` satisfies
`E[g(T)] ≤ (1/N) Σ_i g(u^i) + ḡ √(log(1/δ)/(2N)) + ℜ_N(G)` for all `g ∈ G` simultaneously
(stated as: the bad set, an outer measure, is `≤ δ`; the inequality is written
`ofReal(E g − Ê g − ḡ√…) ≤ ℜ_N(G)`, equivalent since `ℜ_N(G) ≥ 0`). -/
theorem theorem_14_eq29 {U : Type*} [MeasurableSpace U] (P : Measure U) [IsProbabilityMeasure P]
(G : Set (U → ℝ)) (gbar : ℝ) (hG_meas : ∀ g ∈ G, Measurable g)
(hG_sep : IsPointwiseSeparable G) (hG_bdd : ∀ g ∈ G, ∀ u, 0 ≤ g u ∧ g u ≤ gbar)
(N : ℕ) (hN : 1 ≤ N) (δ : ℝ) (hδ : 0 < δ) :
(Measure.pi fun _ : Fin N => P)
{s | ∃ g ∈ G, margRademacherR P N G <
ENNReal.ofReal ((∫ u, g u ∂P) - empMean s g
- gbar * Real.sqrt (Real.log (1 / δ) / (2 * N)))} ≤ ENNReal.ofReal δ := by sorry
end PrescAnalytics.ERM
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.