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∈F⊆{0,1}X 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 F. 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 F 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.
Figures & tables
Figure 1: A representation P with seven cells and one task f . Each cell is decoded by its majority label, so the minority points are the errors and their mass is errP(f) . A universal representation keeps this mass at most ε for every task in F at once.
Figure 2: Representation size of the maximum-error greedy construction on threshold products, plotted against d∗log(1/ε) . The curves follow the expression in Equation 8 ; the dashed line is y=x .
Figure 3: Minimum tested bit budget passing validation at each error target, shown as the median over seeds with a configuration. Dotted lines indicate the lossless reference B0 . Open triangles indicate instances for which no configuration passes validation.
Figure 4: Bit budgets against the shattered-set bound Bsh(ε) . Each point represents one selected seed, with offsets for visibility. Filled diamonds were certified on test. The dashed line indicates Bbits=Bsh(ε) .
Figure 5: Worst-case error against the bit budget per dimension for reconstruction-trained SAEs, one dot per random seed (three per dimension) for each d∗∈{1,2,4,8,10} . × are the exact error 2−ℓ−1 of equal-width quantization using ℓ bits per coordinate. Prediction error decreases as the representation budget increases.
Neural networks can leverage feature superposition to encode more concepts than dimensions, but cross-feature interference constrains the linear accessibility of simultaneously active features. By framing linear accessibility as a compressed sensing problem, we derive high-probability bounds for fixed supports under subgaussian noise, proving the sufficient dimension scales linearly (d=Oε(klogm)) rather than prior worst-case quadratic limits. We characterize the asymmetry between active and inactive interference and the trade-off between interference and observation-noise budgets. We then validate these bounds across system parameters through Gaussian-tail approximations. We also introduce IHT-SAE, which uses learned iterative refinement to improve feature recovery beyond the limits of linear availability. These results quantify the geometric constraints of the linear representation hypothesis, providing a framework for evaluating sparse autoencoders, compositional generalization, and neural interpretability.
Enrico Vompa
Applied Artificial Intelligence Group Tallinn University of Technology, Estonia
The success of neural networks is largely attributed to their ability to learn useful representations from training data. However, known results that prove a computational advantage of learned features over fixed ones are restricted to specific input distributions. We settle the COLT open question of Feldman, Kamath, and Srebro (2026) by showing that this advantage can persist in the distribution-free setting. We construct a family of hypothesis classes that can be efficiently learned by a natural gradient-based algorithm on a two-layer ReLU network, but cannot be represented by linear predictors over any fixed feature map with polynomial dimension (and runtime). Specifically, for any sufficiently small error and any sufficiently large runtime budget R (depending on the error), there exists a hypothesis class that the neural network learns under any input distribution to the desired expected classification error in time at most R, while the dimension complexity (governing the dimension needed by linear predictors) is superpolynomial in R.
We analytically study the evolution of the energy function of Dense Associative Memories (DenseAMs) as they train on randomly sampled codewords of random expander low-density parity-check codes (a.k.a. solutions of random XORSAT problems). We identify two distinct regimes and a transition between them, reminiscent of grokking in neural networks. A regime of small training set size is where the model memorizes a few training examples but cannot discover the underlying rules of the entire codeword dictionary generative process. The opposite regime, corresponding to a larger training set size, is where the model has uncovered the sparse constraints that generated the entire data set after seeing only polynomially many patterns. We also design a novel class of DenseAMs with a thresholding learning rule, and show that any amount of thresholding enables the model to perform simplified sparse Hamiltonian learning, which exponentially reduces the number of training examples needed to learn the true underlying data set. In this regime, the model learns how to discover exp[O(n)] solutions from only O(logn) training samples, which is asymptotically optimal for any learning algorithm. When training on codewords of certain random codes, the model can even learn the underlying code when a small O(1) fraction of bits are latent variables. These latent variables are not shown to the model during learning, but will be discovered by sparsifying observed higher-order correlations. For certain random codes, we show that a simple and conservative algorithm learns a minimal latent representation for the data set. This provides a transparent, physics-motivated, and analytically tractable toy model for how deep latent representations emerge in an associative memory training.
Andrew Lucas, Dmitry Krotov
Department of Physics and Center for Theory of Quantum Matter, University of Colorado, Boulder, CO 80309, USA · Dynamical Mind, Cambridge, MA 02141, USA