Lemma 21.6: no algorithm has a mistake bound smaller than Ldim(H): M_A(H) ≥ Ldim(H) for every A
ProvedUnderstandingML.ldim_le_mistake_boundlittlestone-dimensionlower-boundonline-learning
Lemma 21.6. No algorithm can have a mistake bound strictly smaller than ; namely, for every algorithm , we have .
Preamble
import Definitions.Def_UnderstandingML_Online open MeasureTheory open scoped InnerProductSpace
Formal statement
namespace UnderstandingML
/-- **Lemma 21.6** (p. 291). No algorithm can have a mistake bound strictly smaller than
`Ldim(H)`; namely, for every algorithm `A`, we have `M_A(H) ≥ Ldim(H)`. -/
theorem ldim_le_mistake_bound {X : Type*} (H : Set (X → Bool)) (A : OnlineAlg X Bool) :
ldim H ≤ mistakeBound A H := 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, §21.1.1 p. 291, Lemma 21.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.