Appendix A — |E s(N) − s(EN)| ≤ E|s(N) − s(EN)| ≤ 4√(2/n)
ProvedRadGauss.Discrepancy.expect_condSup_deviationlearning-theorymaximum-discrepancyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1rademacher-complexity
Let be a probability measure on , with , and a nonempty class of measurable functions . Let for independent uniform signs , so that . Then
Together with the two previous identities this bounds the gap between the Rademacher complexity and the expected maximum discrepancy.
Formalization Note Expectations over the signs are averages over all sign vectors, and is written . The sample size is even so that is an attainable value of . 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, last display: for `N = Σ_i σ_i` (so `E N = 0`) and `n = 2m`,
`|E s(N) − s(E N)| ≤ E|s(N) − s(E N)| ≤ 4 √(2/n)`. Expectations over uniform signs are averages
over all `2^n` sign vectors. -/
theorem expect_condSup_deviation {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)) :
|((2 : ℝ) ^ (2 * m))⁻¹ * ∑ σ : Fin (2 * m) → Bool, condSup μ (2 * m) F (sumSign σ)
- condSup μ (2 * m) F 0|
≤ ((2 : ℝ) ^ (2 * m))⁻¹ * ∑ σ : Fin (2 * m) → Bool,
|condSup μ (2 * m) F (sumSign σ) - condSup μ (2 * m) F 0| ∧
((2 : ℝ) ^ (2 * m))⁻¹ * ∑ σ : Fin (2 * m) → Bool,
|condSup μ (2 * m) F (sumSign σ) - condSup μ (2 * m) F 0|
≤ 4 * Real.sqrt (2 / ((2 * m : ℕ) : ℝ)) := 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, last display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.