How much must a data representation compress before the task it will be used for is known? The authors formalize this as a communication problem: an encoder observes a sample X from a distribution D and sends a finite message; later, a function f from a known class F is specified, and a decoder must predict f(X) within error epsilon. The question is how few bits the encoder can get away with while still supporting every function in the class.
The main result is an encoder that outputs O(d* log(1/eps)) bits, where d* is the dual VC dimension of F. The construction works greedily, selecting O((d*/eps) log(1/eps)) functions from the class and using their joint label pattern as the encoding. The proof relies on a novel potential function argument that compares the entropy gained from each greedy selection against the number of label patterns permitted by the dual VC dimension.
The authors also prove lower bounds: the representation length is worst-case optimal for every d* >= 1 and eps < 1/4 up to a universal constant factor, and instance-wise optimal for every family F up to an O(log(1/eps)) factor. They give two ways to learn the representation from unlabeled samples, with different guarantees on representation size and sample complexity. Experiments verify the greedy construction's accuracy-size tradeoff and explore its connection to neural sparse autoencoders, suggesting practical relevance beyond the theoretical framing.