Deep learning versus linear models across all input distributions

Neural networks trained by gradient descent can learn functions that linear models of comparable size cannot, but the classical examples all rely on a carefully chosen input distribution. If plain SGD on a standard network learns a class under every input distribution, can a linear model of comparable dimension always represent that class?

Problem

Let $X = \{\pm 1\}^n$ and let $H \subseteq \{\pm 1\}^X$ be a class of Boolean functions. The dimension complexity $\mathrm{dc}(H)$ is the smallest $d$ for which there is a feature map $\varphi : X \to \mathbb{R}^d$ such that every $h \in H$ can be written as $h(x) = \operatorname{sign} \langle w_h, \varphi(x) \rangle$ for some $w_h \in \mathbb{R}^d$.

Consider a fully connected ReLU network of depth $L$ with widths $n_0 = n, n_1, \dots, n_{L-1}$ and one output, so that $f_\theta(x) = \theta_L\, \sigma(\theta_{L-1}\, \sigma(\cdots \sigma(\theta_1 x)))$ with $\sigma(z) = \max(0, z)$ applied entrywise, and $S = \sum_i n_i n_{i-1}$ weights in total. Initialize each entry of $\theta_i$ independently from a Gaussian of variance $1/n_{i-1}$. For a target $h^\star \in H$ and input distribution $D$, run SGD with stepsize $\eta$ for $T$ steps: draw $x^{(t)} \sim D$ and set

$$\theta^{(t+1)} = \theta^{(t)} - \eta \nabla_\theta\, \ell\big(h^\star(x^{(t)})\, f_{\theta^{(t)}}(x^{(t)})\big), \qquad \ell(z) = \log(1 + e^{-z}),$$

then predict with $\hat h(x) = \operatorname{sign} \sum_{t = \lceil T/2 \rceil}^{T} f_{\theta^{(t)}}(x)$.

Question. Is there an absolute constant $C$ such that the following holds for every class $H$ and every $\varepsilon < 1/4$? If some architecture with $S$ weights, stepsize $\eta$ and $T$ steps gives $\mathbb{E}\,\Pr_{x \sim D}[\hat h(x) \ne h^\star(x)] \le \varepsilon$ for every input distribution $D$ and every target $h^\star \in H$, the expectation being over the initialization and the samples, then $\mathrm{dc}(H) \le C\, T S$.

A weaker bound $\mathrm{dc}(H) \le \mathrm{poly}(T, S)$, or a proof that none holds, would also be of interest.

Background

Ben-David, Eiron and Simon showed that dimension complexity can be far larger than VC dimension [2]. Some such classes, such as all $2^n$ parities of $n$ bits, are computed by small networks, so empirical risk minimization over networks beats linear models in sample complexity. But networks are trained by gradient methods, and SGD fails to learn parities under worst-case inputs. The known separations between SGD-trained networks and linear or kernel models, such as parities under a special mixture distribution or functions with the staircase property, are tied to a specific input distribution. Feldman, Kamath and Srebro asked whether this is unavoidable, as an invited open problem at COLT 2026 [1]. The details of the procedure are not essential to them, but the network must be benign: with purpose-built architectures or initializations, gradient descent can simulate any learning algorithm [3].

What is known

• A claimed answer for a modified procedure. Barzilai (October 2026) trains a block-structured two-layer ReLU network, with non-standard initialization, by one noisy sign-gradient step on the hidden layer followed by projected SGD on the output layer. He proves that this learns Patel's class (below) under every distribution in time $\exp(O(m^{2/3}\log^2(m/\varepsilon)))$, where $m$ is the number of blocks, while its dimension complexity is $2^{\Omega(m)}$, and presents this as a negative answer [6]. It is an unrefereed preprint, and it leaves open whether ordinary SGD without injected noise achieves a comparable separation.
• The statistical-query analogue is false. The posers also asked whether learning $H$ under every distribution with $m$ statistical queries of tolerance $\tau$ implies $\mathrm{dc}(H) = O(m/\tau^2)$. Patel (September 2026, unrefereed preprint) found a subclass of DNF formulas, disjunctions of conjunctions on disjoint known blocks of variables, that is learnable under every distribution with polynomially many queries of inverse-polynomial tolerance, yet has dimension complexity $n^{\omega(1)}$ [5].
• The converse of the SQ question holds up to the input length. If $\mathrm{dc}(H) = d$, then $H$ is learnable with statistical queries whose number and inverse tolerance are polynomial in $d$, $n$ and $1/\varepsilon$, via the halfspace algorithm of Dunagan and Vempala (2004), as explained in [1].

What would count as progress

• A careful check of the October 2026 construction [6], confirming it or finding a gap.
• The same separation for the plain procedure above: a fully connected network, standard initialization and SGD on all layers without injected noise. Alternatively, a proof that such SGD cannot learn Patel's class under every distribution.
• A proof that $\mathrm{dc}(H) \le \mathrm{poly}(T, S)$, or $\mathrm{poly}(T, S, n)$, for every class that plain SGD learns in this way, perhaps first for two-layer networks.
• The same questions for the probabilistic variants of dimension complexity [4], also proposed by the posers.

References

1. V. Feldman, P. Kamath and N. Srebro, Invited open problem: Is the power of deep learning over linear models inherently distribution dependent?, COLT 2026, PMLR 336 (2026), 7117–7122. PMLR
2. S. Ben-David, N. Eiron and H. U. Simon, Limitations of learning via embeddings in Euclidean half spaces, J. Mach. Learn. Res. 3 (2002), 441–461. JMLR
3. E. Abbe, P. Kamath, E. Malach, C. Sandon and N. Srebro, On the power of differentiable learning versus PAC and SQ learning, NeurIPS (2021). arXiv:2108.04190
4. P. Kamath, O. Montasser and N. Srebro, Approximate is good enough: probabilistic variants of dimensional and margin complexity, COLT 2020, PMLR 125 (2020), 2236–2262. PMLR
5. S. Patel, A separation between distribution-free SQ learning and dimension complexity, preprint (2026). arXiv:2609.19780
6. D. Barzilai, A distribution-free separation between learned and fixed features, preprint (2026). arXiv:2610.25335

Source

Imported from COLT open problems, COLT 2026, curated by the Conference on Learning Theory (COLT). Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.