Theorem C.1 ([2], Theorem 34)AnypartialconceptclassHwithVC (H)<1isPAClearnable intherealizablesettingwithsamplecomplexity, RE(,,H) = O min n VC (H) log