A Distribution-Free Separation Between Learned and Fixed Features
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…
- 用途
- 原典で確認
- 難易度の目安
- Hard
- 実装コストの目安
- High
概要
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.
参考リンク
リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。
実装を始めるプロンプト
参考リンクを確認したうえで、次の内容をコピーして利用できます。
# 論文・記事 A Distribution-Free Separation Between Learned and Fixed Features # 概要 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… # 原典 https://arxiv.org/abs/2610.25335 上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。