VC uniform convergence theorem 2026-10-31
A finite VC dimension gives simultaneous control of empirical misclassification risk for every member of a hypothesis class. Sufficient independent sample size is . The displayed event implies an empirical risk minimization rule has misclassification risk at most , including for unrealizable labels.[ref]
Learnability and VC Dimension in MIT 6.790. Uniform convergence and quantitative fundamental theorem