Appendix A — the Lipschitz condition |s(n₁) − s(n₂)| ≤ 4|n₂ − n₁|/n
ProvedRadGauss.Discrepancy.condSup_lipschitzlearning-theorymaximum-discrepancyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1rademacher-complexity
Let be a probability measure on , , and a nonempty class of measurable functions . For any two integers that are values of for some sign vectors (that is, and ),
This Lipschitz property lets the concentration of around transfer to around .
Formalization Note The paper writes the argument for ; the bound is used for , which is negative half of the time, so it is stated here for every pair of attainable values (the inequality is symmetric in ). Added hypotheses as for the other statements.
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: the Lipschitz condition `|s(n₁) − s(n₂)| ≤ 4|n₂ − n₁|/n`, stated for
every pair of values attained by `Σ_i σ_i` (the page writes `0 ≤ n₂ < n₁ ≤ n`). -/
theorem condSup_lipschitz {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))
(N₁ N₂ : ℤ) (hN₁ : ∃ σ : Fin n → Bool, sumSign σ = N₁)
(hN₂ : ∃ σ : Fin n → Bool, sumSign σ = N₂) :
|condSup μ n F N₁ - condSup μ n F N₂| ≤ 4 * |(N₂ : ℝ) - N₁| / n := 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 '|s(n_1) − s(n_2)| ≤ 4|n_2 − n_1|/n'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.