PaperfootJoin free
arXiv

Proof shows learning features can outperform fixing them

For a constructed family of classification problems, a two-layer neural network learned efficiently regardless of input probabilities, while predictors using fixed features required far more features.

Paper by Daniel Barzilai
A light blue lattice fits scattered circles and squares into matching openings beside a crowded heap of gray and dark blue-green pieces.
Preprint: theory

Edited by Boris Djordjevic · Paperfoot

Paper

The paper proved that learning features—the numerical descriptions a model uses for prediction—can offer a computational advantage on a constructed family of classification problems. The result held under any distribution of inputs, meaning any probabilities of encountering different inputs.

A gradient-based method, which uses local slopes to guide training adjustments, efficiently trained a two-layer neural network on these problems. For sufficiently small target error and a sufficiently large time budget, the network reached the desired average classification error within that budget. The comparison covered every fixed feature map: a way of describing inputs chosen before training. Linear predictors, which combine those features through weighted sums, required a feature count growing faster than any fixed power of the network’s time budget.

Why it matters

The proof settled an open question about whether learning features can retain a computational advantage without assuming a particular distribution of inputs. Earlier proofs required specific distributions.

Caveats

The proof concerns a constructed family of problems, not measured performance on practical tasks; its guarantee requires sufficiently small target error and sufficiently large time budgets. The paper is a preprint, not yet peer-reviewed.

In this paper

distribution-free learning of neural networks

Methods
two-layer ReLU network (this paper)

What it shows

A two-layer ReLU network trained by noisy signSGD followed by projected SGD efficiently learns a hypothesis class distribution-free, whereas its dimension complexity is superpolynomial in the runtime budget.

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).

Abstract

There exists an absolute constant c1 > 0 such that the dimension complexity of the hypothesis class Hm is at least 2^(c1*m) for all m >= 2.

There is an absolute constant c_{1}>0 such that \operatorname{dc}(\mathcal{H}_{m})≥ 2^{c_{1}m} for all m≥ 2.

Proposition 2.

For every m >= 2 and accuracy in (0, 1/4), the two-stage training algorithm learns Hm distribution-free to expected error at most epsilon.

For every m≥ 2 and \varepsilon\in(0,1/4), Algorithm, with the hyperparameters of Table 1 in the appendix, learns \mathcal{H}_{m} distribution-free to expected error at most \varepsilon, using n samples and P parameters (so O(Pn) arithmetic operations), where

Theorem 3.

Dimension complexity cannot serve as a universal runtime lower bound for natural gradient-based neural network learning.

Thus, dimension complexity cannot serve as a universal runtime lower bound for natural gradient-based neural network learning.

6 Discussion

Quoted word for word from the full text on arXiv.

The paper

A Distribution-Free Separation Between Learned and Fixed Features

Daniel Barzilai

arXiv, Oct 18, 2026, Open access, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.25335

arXiv:2610.25335v1 in cs.LG, also stat.ML

AbstractPDFHTML

Cite as BibTeX
@misc{barzilai2026distributionfree,
  title = {A Distribution-Free Separation Between Learned and Fixed Features},
  author = {Barzilai, Daniel},
  year = {2026},
  eprint = {2610.25335},
  archivePrefix = {arXiv},
  primaryClass = {cs.LG},
  doi = {10.48550/arxiv.2610.25335},
  url = {https://arxiv.org/abs/2610.25335}
}

Related