Lemma 3 — R_n(F)/2 − 2√(2/n) ≤ D_n(F) ≤ R_n(F) + 4√(2/n), and R_n(F) − 4√(2/n) ≤ D_n(F) if F = −F
ProvedRadGauss.Discrepancy.lemma_3generalization-boundlearning-theorymaximum-discrepancyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1rademacher-complexity
Let be a probability measure on a measurable space , let with , and let be a nonempty class of measurable functions mapping to . Let be the Rademacher complexity and the expected maximum discrepancy of (Definition 2). Then
If is closed under negation ( implies ), the lower bound can be strengthened to
So the expected maximum discrepancy and the Rademacher complexity are equivalent up to a factor and an additive , and either may replace the other in data-dependent risk bounds.
Formalization Note
- The sample size is even, , , because is defined with half sums; for odd the paper's is undefined.
- Since takes values in , each inequality is written , with the real quantities and embedded by
ENNReal.ofReal; for (true for nonempty ) and finite (true for bounded) this is equivalent to the printed form. - Added hypotheses, which the paper uses implicitly: nonempty, every measurable, and for every sign vector the map is measurable, so that is a genuine expectation.
- The third display of Lemma 3, , is not part of this statement: it is false as printed (for , uniform on , , , the left side is ).
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
/-- **Lemma 3** (p. 465), first and second displays, for `n = 2m`:
`R_n(F)/2 − 2√(2/n) ≤ D_n(F) ≤ R_n(F) + 4√(2/n)`, and `R_n(F) − 4√(2/n) ≤ D_n(F)` when `F` is
closed under negation. Subtractions are moved to the other side to avoid truncated subtraction
in `ℝ≥0∞`. -/
theorem lemma_3 {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)) :
(RadGauss.RiskBound.rademacherComplexity μ (2 * m) F / 2
≤ ENNReal.ofReal (expectedMaxDiscrepancy μ m F)
+ ENNReal.ofReal (2 * Real.sqrt (2 / ((2 * m : ℕ) : ℝ))) ∧
ENNReal.ofReal (expectedMaxDiscrepancy μ m F)
≤ RadGauss.RiskBound.rademacherComplexity μ (2 * m) F
+ ENNReal.ofReal (4 * Real.sqrt (2 / ((2 * m : ℕ) : ℝ)))) ∧
((∀ f ∈ F, -f ∈ F) →
RadGauss.RiskBound.rademacherComplexity μ (2 * m) F
≤ ENNReal.ofReal (expectedMaxDiscrepancy μ m F)
+ ENNReal.ofReal (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. 465 (PDF p. 3), Lemma 3, first and second displays
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.