Theorem 12, part 4 — R_n(φ∘F) ≤ 2L_φ R_n(F) for L_φ-Lipschitz φ with φ(0) = 0
ProvedRadGauss.Structural.theorem_12_part_4Theorem 12, part 4 (Bartlett–Mendelson 2002, p. 469). Let be a probability measure on , an integer, and the Rademacher complexity of Definition 2. Let be a class of real functions on , and let be Lipschitz with constant , that is for all , with . Writing ,
The paper attributes this inequality to Ledoux and Talagrand (1991, Corollary 3.17). Composing a class with a fixed Lipschitz function, such as a margin loss, changes its Rademacher complexity by at most a constant factor; this is how the paper's risk bounds are turned into bounds for loss classes.
Formalization Note is Lipschitz on all of (LipschitzWith Lφ φ, ), as printed. Complexities are -valued and no boundedness of is assumed. The factor comes from the absolute value inside the supremum in Definition 2.
import Mathlib import Definitions.Def_RadGauss_RiskBound_rademacherComplexity open MeasureTheory open scoped ENNReal Pointwise
namespace RadGauss.Structural
/-- **Theorem 12, part 4** (Bartlett–Mendelson, JMLR 3 (2002), p. 469): if `φ : ℝ → ℝ` is
Lipschitz with constant `L_φ` and `φ(0) = 0`, then `R_n(φ ∘ F) ≤ 2 L_φ R_n(F)`, where
`φ ∘ F = {φ ∘ f | f ∈ F}`. -/
theorem theorem_12_part_4 {X : Type*} [MeasurableSpace X] (μ : Measure X)
[IsProbabilityMeasure μ] (n : ℕ) (F : Set (X → ℝ)) (φ : ℝ → ℝ) (Lφ : NNReal)
(hφ : LipschitzWith Lφ φ) (hφ0 : φ 0 = 0) :
RadGauss.RiskBound.rademacherComplexity μ n ((fun f => φ ∘ f) '' F) ≤
2 * (Lφ : ℝ≥0∞) * RadGauss.RiskBound.rademacherComplexity μ n F := by sorry
end RadGauss.Structural
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.