Appendix A — R_n(F) ≥ E s(Σσ_i), with equality when F = −F
ProvedRadGauss.Discrepancy.rademacher_ge_expect_condSuplearning-theorymaximum-discrepancyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1rademacher-complexity
Let be a probability measure on , , and a nonempty class of measurable functions . Let be the conditional supremum function of Appendix A and independent uniform signs. Then
and the inequality is an equality when implies .
This connects the Rademacher complexity with the function , whose value at is the expected maximum discrepancy.
Formalization Note is the average of over all sign vectors, embedded in with ENNReal.ofReal (its value is nonnegative under the hypotheses). Added hypotheses, which the paper uses implicitly: nonempty, every measurable, and for every sign vector the map is measurable, so that the expectations are genuine.
Preamble
import Definitions.Def_RadGauss_RiskBound_rademacherComplexity import Definitions.Def_RadGauss_Discrepancy_maxDiscrepancy import Definitions.Def_RadGauss_Discrepancy_condSup open MeasureTheory open scoped ENNReal Pointwise
Formal statement
namespace RadGauss.Discrepancy
/-- Appendix A, p. 479, first display: `R_n(F) ≥ E s(Σ_i σ_i)`, with equality when `F` is closed
under negation. The expectation over uniform signs is the average over all `2^n` sign vectors. -/
theorem rademacher_ge_expect_condSup {X : Type*} [MeasurableSpace X] (μ : Measure X)
[IsProbabilityMeasure μ] (n : ℕ) (hn : 0 < n) (F : Set (X → ℝ)) (hFne : F.Nonempty)
(hFrange : ∀ f ∈ F, ∀ x, f x ∈ Set.Icc (-1 : ℝ) 1)
(hFmeas : ∀ f ∈ F, Measurable f)
(hsup : ∀ σ : Fin n → Bool,
Measurable fun x : Fin n → X => ⨆ f : F, ∑ i, RadGauss.RiskBound.signVal (σ i) * (f : X → ℝ) (x i)) :
ENNReal.ofReal (((2 : ℝ) ^ n)⁻¹ * ∑ σ : Fin n → Bool, condSup μ n F (sumSign σ))
≤ RadGauss.RiskBound.rademacherComplexity μ n F ∧
((∀ f ∈ F, -f ∈ F) →
RadGauss.RiskBound.rademacherComplexity μ n F =
ENNReal.ofReal (((2 : ℝ) ^ n)⁻¹ * ∑ σ : Fin n → Bool, condSup μ n F (sumSign σ))) := by sorry
end RadGauss.Discrepancy
Source
Bartlett, Mendelson, Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, J. Mach. Learn. Res. 3 (2002), p. 479 (PDF p. 17), Appendix A, first display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.