A Distribution-Free Separation Between Learned and Fixed Features
Abstract
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.
Related
- Random p-adic matrices with fixed zero entries and the Cohen–Lenstra distribution
- Polyconvex neural-network surrogates with learned paired directional features for anisotropic hyperelastic homogenization
- Learned Monotone Recurrent Features in Governed Credit Scoring: The Price of the Frame and the Necessity of Macro Conditioning
- The binomial distribution maximises entropy among sums of negatively related indicators with fixed mean and support
- Mazurov's question on fixed points of automorphisms of free Burnside groups
BibTeX
@misc{barzilai2026distributionfree,
title = {{A Distribution-Free Separation Between Learned and Fixed Features}},
author = {Daniel Barzilai},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25335},
eprint = {2610.25335},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25335},
}
RIS
TY - UNPB
TI - A Distribution-Free Separation Between Learned and Fixed Features
AU - Daniel Barzilai
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2610.25335
UR - https://arxiv.org/abs/2610.25335
AB - 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.
ER -