← All AI/ML open problems

Statistical learning theory · Embeddings & representations / Open question

Deep Learning Beyond Linear Models

Does deep learning have a distribution-independent computational advantage, or does its power rely on exploitable structure in the data distribution?

OpenEditorially scopedSpecified modelCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

Does distribution-independent learning by standard neural-network SGD force low linear dimension complexity? For a Boolean class HH on {±1}n\{\pm1\}^n, suppose a fully connected ReLU network with SS weights, Gaussian initialization and logistic-loss SGD achieves expected classification error ε<1/4\varepsilon<1/4 for every input distribution and every target in HH after TT updates. Is dc(H)≤CTS\mathrm{dc}(H)\leq C T S for a universal constant CC, as asked in COLT 2026 Question 1?

Assumptions and scope

  • Dimension complexity is the least d for which one feature map into R^d represents every member of H by a linear sign rule; it is not merely the number of network parameters.
  • Use the source's layerwise Gaussian variance 1/(input width), fixed step size, one fresh labelled example per update and sign of the sum of network outputs over the final half of training.
  • The same architecture, initialization law and training settings must work for every input distribution and target. Engineered initialization that simulates an arbitrary algorithm is outside this question.

What would settle it?

Prove the proposed dimension bound, exhibit a class and standard-SGD guarantee violating it, or resolve the weaker polynomial-bound formulation with its changed scope explicit.

Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.

Status and evidence

Feldman, Kamath and Srebro explicitly pose the standard-SGD question. Distribution-dependent separations already exist. Patel's September 2026 Theorem 1 negatively resolves their separate SQ-versus-deterministic-dimension question; that resolved statement is not this target. Their Section 3 also flags a flaw in an earlier claimed reduction. This is an editorial reformulation of a published open problem. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.

Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.

Sources and further reading

  1. Feldman, Kamath and Srebro — Is the Power of Deep Learning over Linear Models Inherently Distribution Dependent? ↗problem statement · source checked 2026-11-19

    PDF Sections 1–4 checked: Question 1 fixes fully connected ReLU networks, Gaussian initialization, logistic-loss SGD and a tail-averaged predictor; asks dc(H) <= C T S. The separate SQ Question 2 has a subsequent negative resolution by Patel. Section 3 reports a flaw in an earlier claimed reduction.

  2. Patel — A Separation Between Distribution-Free SQ Learning and Dimension Complexity ↗status context · source checked 2026-11-19

    Full HTML statement and construction checked: Theorems 1 and 3 give a superpolynomial separation, negatively answering the deterministic-dimension SQ question. This is not a convergence proof for standard Gaussian-initialized ReLU SGD.

  3. Malach et al. — Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels ↗partial theory · source checked 2026-11-19

    Identified as a distribution-dependent separation baseline in Feldman et al. Sections 1–2; its proof was not independently audited.