Communication Complexity of Universal Features
Abstract
Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we consider a deterministic encoder that observes X∼ D and produces a finite encoding before a task f∈ℱ⊆{0,1}𝒳 is specified. For each task, a decoder must predict f(X) with error at most ε under D. We construct an encoder that outputs a representation with O(d*log(1/ε)) bits, where d* is the dual VC dimension of ℱ. Our encoder greedily selects O((d*/ε)log(1/ε)) functions from the class and uses their joint label pattern to produce the encoding. The key idea in our upper bound is a novel potential function argument, where we compare the entropy gained from each greedy selection with the number of patterns allowed by the dual VC dimension. We present lower bounds showing that the representation length achieved by our encoder is worst-case optimal for every d* ≥ 1 and ε < 1/4 up to a universal constant factor, and instance-wise optimal for every family ℱ up to an O(log(1/ε)) factor. We give two ways to learn the representation from unlabeled samples, with different guarantees on the representation size and sample complexity. Experimentally, we verify the greedy construction's accuracy-size tradeoff and explore its connection to neural sparse autoencoders.
Related
- A note on the nondeterministic communication complexity of equality
- Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity
- Infinite Communication Complexity and KW Games
- A Universal Lower Bound for the Complexity of Gaussian-Divisible Spin Glasses
- Embedding complexity into the universal Banach space and the strong Novikov conjecture
BibTeX
@misc{hu2026communication,
title = {{Communication Complexity of Universal Features}},
author = {Lunjia Hu and Anish Jayant and Peter Li and Princewill Okoroafor and Abhishek Shetty},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27402},
eprint = {2610.27402},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27402},
}
RIS
TY - UNPB
TI - Communication Complexity of Universal Features
AU - Lunjia Hu
AU - Anish Jayant
AU - Peter Li
AU - Princewill Okoroafor
AU - Abhishek Shetty
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.27402
UR - https://arxiv.org/abs/2610.27402
AB - Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we consider a deterministic encoder that observes X∼ D and produces a finite encoding before a task f∈ℱ⊆{0,1}^𝒳 is specified. For each task, a decoder must predict f(X) with error at most ε under D. We construct an encoder that outputs a representation with O(d^*log(1/ε)) bits, where d^* is the dual VC dimension of ℱ. Our encoder greedily selects O((d^*/ε)log(1/ε)) functions from the class and uses their joint label pattern to produce the encoding. The key idea in our upper bound is a novel potential function argument, where we compare the entropy gained from each greedy selection with the number of patterns allowed by the dual VC dimension. We present lower bounds showing that the representation length achieved by our encoder is worst-case optimal for every d^* ≥ 1 and ε < 1/4 up to a universal constant factor, and instance-wise optimal for every family ℱ up to an O(log(1/ε)) factor. We give two ways to learn the representation from unlabeled samples, with different guarantees on the representation size and sample complexity. Experimentally, we verify the greedy construction's accuracy-size tradeoff and explore its connection to neural sparse autoencoders.
ER -