The polynomial bound on Φ_d(m) (p. 57): Φ_d(m) = 2^m for m ≤ d, and Φ_d(m) ≤ (em/d)^d for m ≥ d ≥ 1
ProvedComputationalLearning.phi_polynomial_boundcombinatoricsvc-dimension
p. 57. For , . For , since , , so .
Formally: for all : if then ; and if then (as real numbers; at this is ).
Preamble
import Definitions.Def_ComputationalLearning_VC open MeasureTheory
Formal statement
namespace ComputationalLearning
/-- **The polynomial bound on `Φ_d(m)`** (p. 57): for `m ≤ d`, `Φ_d(m) = 2^m`, and for `m ≥ d ≥ 1`,
`Φ_d(m) ≤ (em/d)^d = O(m^d)`. -/
theorem phi_polynomial_bound (d m : ℕ) :
(m ≤ d → Phi d m = 2 ^ m) ∧
(1 ≤ d → d ≤ m → (Phi d m : ℝ) ≤ (Real.exp 1 * m / d) ^ d) := by sorry
end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, §3.4 p. 57, the bound Φ_d(m) ≤ (em/d)^d = O(m^d)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.