arXiv preprint ·
A Distribution-Free Separation Between Learned and Fixed Features
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Robust Direct Preference Optimization under Preference Label-Flip Attacks
Corrected Block Sparse Spectral Optimization: Exact Models, Finite Identification, and Local Dynamics
Dimension-free comparison inequalities between $f$-divergences for Gaussian location mixtures
Detection Augmented Learning In Non-Stationary Bandit Environments
Decision-Target Reversal under Informative Label Missingness
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.