Theorem 7.3: a countable union of classes with the uniform convergence property is nonuniformly learnable
ProvedUnderstandingML.nonuniform_of_countable_union_ucnonuniform-learnabilitystructural-risk-minimizationuniform-convergence
Theorem 7.3. Let be a hypothesis class that can be written as a countable union of hypothesis classes, , where each enjoys the uniform convergence property. Then is nonuniformly learnable.
Formally: for nonempty with each having the uniform convergence property, NonuniformLearnable loss H (general loss framework).
Preamble
import Definitions.Def_UnderstandingML_Nonuniform open MeasureTheory
Formal statement
namespace UnderstandingML
/-- **Theorem 7.3** (p. 85). Let `H` be a hypothesis class that can be written as a countable
union of hypothesis classes, `H = ⋃ₙ Hₙ`, where each `Hₙ` enjoys the uniform convergence
property. Then `H` is nonuniformly learnable. (`H` nonempty, so that a learner with outputs in
`H` exists.) -/
theorem nonuniform_of_countable_union_uc {Z : Type*} [MeasurableSpace Z] {Hyp : Type*}
(loss : Hyp → Z → ℝ) (Hn : ℕ → Set Hyp) (hne : (⋃ n, Hn n).Nonempty)
(hUC : ∀ n, HasUniformConvergence loss (Hn n)) :
NonuniformLearnable loss (⋃ n, Hn n) := by sorry
end UnderstandingML
Source
Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press 2014, doi:10.1017/CBO9781107298019, §7.1.1 p. 85, Theorem 7.3 (proved in §7.2 via Theorem 7.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.