§5, p. 20 — star-shaped H and r > β_N(γ) ⇒ E sup_{h∈H∩rD} |N⁻¹Σε_ih(X_i)| ≤ γr
ProvedLearnNoConc.ERM.radSup_le_of_betaN_ltlocalizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rademacher-complexitystatistical-learning
Let be a probability space, , , and let be a class of real functions on that is star-shaped around (if and then ). Let be i.i.d. with law and independent random signs. If , then
where is the unit ball of .
The infimum need not be attained; this statement says that for a star-shaped class the defining inequality holds at every radius above it. It is the localization step used in Corollary 5.5.
Formalization Note The expectation of the supremum is taken in (Mathlib's lower Lebesgue integral), and is -valued; no measurability hypothesis is needed for this statement.
Preamble
import Mathlib import Definitions.Def_LearnNoConc_ERM_Setting
Formal statement
namespace LearnNoConc.ERM
open MeasureTheory
open scoped ENNReal
/-- §5, p. 20: if `H` is star-shaped around `0` and `r > β_N(H, γ)`, then
`E sup_{h ∈ H ∩ rD} |(1/N) ∑ ε_i h(X_i)| ≤ γ r`. -/
theorem radSup_le_of_betaN_lt {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (H : Set (Ω → ℝ)) (hH : StarShaped H) (N : ℕ) (hN : 0 < N)
(γ : ℝ) (hγ : 0 < γ) (r : ℝ) (hr : betaN μ H N γ < ENNReal.ofReal r) :
radSup μ {h ∈ H | eLpNorm h 2 μ ≤ ENNReal.ofReal r} N ≤ ENNReal.ofReal (γ * r) := by sorry
end LearnNoConc.ERM
Source
Mendelson, Learning without Concentration, arXiv:1401.0304v2, §5, p. 20, "it is straightforward to verify that if H is star-shaped"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.