Exercise 4: the growth function of the composition class F₂ ∘ F₁ is at most τ_{F₂}(m) τ_{F₁}(m)
ProvedUnderstandingML.growth_compositioncombinatoricsgrowth-function
Exercise 4 (Growth function of composition). Let be a set of functions from to and let be a set of functions from to . Let be the composition class: for every and , there exists such that . Then . The codomains are finite.
Preamble
import Definitions.Def_UnderstandingML_NeuralNetworks open MeasureTheory
Formal statement
namespace UnderstandingML
/-- **Exercise 4 (growth function of composition)** (p. 282). Let `F₁` be a set of functions
from `X` to `Z` and let `F₂` be a set of functions from `Z` to `Y`. Let `H = F₂ ∘ F₁` be the
composition class: for every `f₁ ∈ F₁` and `f₂ ∈ F₂`, there exists `h ∈ H` with
`h(x) = f₂(f₁(x))`. Then `τ_H(m) ≤ τ_{F₂}(m) τ_{F₁}(m)`. The codomains are finite. -/
theorem growth_composition {X Z Y : Type*} [Finite Z] [Finite Y] (F₁ : Set (X → Z))
(F₂ : Set (Z → Y)) (m : ℕ) :
growthY (compositionClass F₂ F₁) m ≤ growthY F₂ m * growthY F₁ m := 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, §20.9 p. 282, Exercise 4 (used in the proof of Theorem 20.6, p. 275)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.