A Additional preliminaries for Section 2 Complexity measures. The capacity measures, VC

See Definitions 1.1 and 1.2 for the See [ 2, Section 2 and Appendix C] for more details. Before proceeding to the proof, we present the following result on learning partial concept classes. Recall the definition of VC is in the context of partial concepts (see Appendix A). 15 Theorem C.1 ([ 2 ], Theorem 34) The sample complexity of this model is defined formally in Definition E.1 . By taking the expectation on Eq. ( 3) we have, E We now prove Theorem 4.4 . Lemma C.2 (Agnostic sample compression generalization bound) We show that in our use case, we can deduce a stronger bound.