Appendix A — D_n(F) = s(0) = s(E Σσ_i)
ProvedRadGauss.Discrepancy.discrepancy_eq_condSup_zerolearning-theorymaximum-discrepancyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1rademacher-complexity
Let be a probability measure on , let with , and let be a nonempty class of measurable functions . Then the expected maximum discrepancy equals the conditional supremum function at zero:
The identity expresses the fact that, because are i.i.d., every balanced split of the sample into two halves is equivalent to the fixed split used in the definition of .
Formalization Note Stated as ; . The sample size is even () because needs half sums. Added hypotheses as for the other statements: nonempty, members measurable, and measurability of for every sign vector.
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: `D_n(F) = s(0) = s(E Σ_i σ_i)` for `n = 2m`. -/
theorem discrepancy_eq_condSup_zero {X : Type*} [MeasurableSpace X] (μ : Measure X)
[IsProbabilityMeasure μ] (m : ℕ) (hm : 0 < m) (F : Set (X → ℝ)) (hFne : F.Nonempty)
(hFrange : ∀ f ∈ F, ∀ x, f x ∈ Set.Icc (-1 : ℝ) 1)
(hFmeas : ∀ f ∈ F, Measurable f)
(hsup : ∀ σ : Fin (2 * m) → Bool,
Measurable fun x : Fin (2 * m) → X => ⨆ f : F, ∑ i, RadGauss.RiskBound.signVal (σ i) * (f : X → ℝ) (x i)) :
expectedMaxDiscrepancy μ m F = condSup μ (2 * m) F 0 := 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, display after the first display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.