Neural architecture & complexity · Statistical learning theory · Memory & capacity / Open question
How Large Must a Shallow Network Be?
Depth can be traded for enormous width and precision. Once two layers suffice in principle, the meaningful question is how much model description is needed to realize that expressivity.
Seed catalog · Showing the bundled record.
Problem statement
Let be the minimum total binary encoding length of a rational-weight ReLU network with at most two hidden layers satisfying for every . Is ? Construct such a polynomial-size family, or prove a superpolynomial encoding lower bound. Count every matrix entry, bias and numerator/denominator bit; unlimited width or unlimited-precision weights cannot be free resources.
Assumptions and scope
- Depth counts hidden ReLU layers; the final map is affine. Each network has finite widths, arbitrary rational weights/biases and an ordinary explicit dense-matrix binary encoding, including dimension metadata.
- Require exact equality on all real inputs. Approximation on a compact domain or correctness only on sampled inputs is a different problem.
- An existence family of polynomial total length is the base target; a uniform efficient construction would strengthen it. Lower bounds for integer or fixed-base fractional weights do not establish the unrestricted rational bound.
What would settle it?
A universal polynomial upper bound on s_2, or a family showing that no universal polynomial bound exists. Improving the explicit exponential upper bound is partial progress; a certified search failure in one ansatz is not a network lower bound.
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
October work claims an unrestricted two-hidden-layer collapse, so neither MAX_13 existence nor a greater-than-two unrestricted depth lower bound is retained. Myrisiotis explicitly leaves polynomial total size at depth two unresolved; its construction gives an exponential depth-two encoding bound and polynomial encodings at O(log(n)/log(log(n))) depth. These are preprint claims, not independently audited proofs. 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
- Myrisiotis — A Witnessing Duality for ReLU Network Depth ↗problem statement · source checked 2026-11-19
HTML Section 1.4, Open Problem 2 and Appendix E scope checked: polynomial total encoding length at depth two remains unknown; the paper gives exponential-length depth-two blocks and polynomial-length sublogarithmic-depth constructions. Fixed-prime denominator lower bounds do not cover unrestricted rational weights.
- Brunck et al. — Two ReLU Layers Is All You Need ↗partial theory · source checked 2026-11-19
Primary abstract checked: exact two-hidden-layer simulation is claimed for every ReLU network. Unrestricted-depth existence is therefore not retained as an open target; size and bit complexity are separate.