Skip to content
conftrace_
2026 COLT COLT 2026

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

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.

❓ The Questioner

Authors

Vitaly Feldman, Pritish Kamath, Nathan Srebro

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Learning Types > Deep Learning Deep Learning > Optimization & Theory > Theory

Keywords

sample complexity deep learning linear model neural network input distribution statistical query model
Download PDF

More from COLT 2026

All COLT 2026 papers →
Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
Gradient-Variation Regret Bounds for Unconstrained Online Learning
Open Problem: How much overparametrization is needed for ALS in tensor decomposition?
Invited Open Problem: Online Optimization of Piecewise-Lipschitz Functions with Applications to Data-Driven Algorithm Design
Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?
Invited Open Problem: Does Differential Privacy Make PAC Learning Much Harder?