Dual VC Dimension Obstructs Sample Compression by Embeddings

Zachary Chase, Bogdan Chornomaz, Steve Hanneke +2

This work studies embedding of arbitrary VC classes in well-behaved VC classes, focusing particularly on extremal classes. Our main result expresses an impossibility: such embeddin…