Invited Open Problem: Is the Power of Deep Learning over Linear Models Inherently Distribution Dependent?

Vitaly Feldman, Pritish Kamath, Nathan Srebro
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7117-7122, 2026.

Abstract

We ask whether distribution-independent SQ learning implies low dimension complexity, and whether anything learnable with (S)GD on a (benign) neural network under any input distribution is also learnable with a linear model.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-feldman26a, title = {Invited Open Problem: Is the Power of Deep Learning over Linear Models Inherently Distribution Dependent?}, author = {Feldman, Vitaly and Kamath, Pritish and Srebro, Nathan}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {7117--7122}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/feldman26a/feldman26a.pdf}, url = {https://proceedings.mlr.press/v336/feldman26a.html}, abstract = {We ask whether distribution-independent SQ learning implies low dimension complexity, and whether anything learnable with (S)GD on a (benign) neural network under any input distribution is also learnable with a linear model.} }
Endnote
%0 Conference Paper %T Invited Open Problem: Is the Power of Deep Learning over Linear Models Inherently Distribution Dependent? %A Vitaly Feldman %A Pritish Kamath %A Nathan Srebro %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-feldman26a %I PMLR %P 7117--7122 %U https://proceedings.mlr.press/v336/feldman26a.html %V 336 %X We ask whether distribution-independent SQ learning implies low dimension complexity, and whether anything learnable with (S)GD on a (benign) neural network under any input distribution is also learnable with a linear model.
APA
Feldman, V., Kamath, P. & Srebro, N.. (2026). Invited Open Problem: Is the Power of Deep Learning over Linear Models Inherently Distribution Dependent?. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:7117-7122 Available from https://proceedings.mlr.press/v336/feldman26a.html.

Related Material