nucleation

LIT-890: The power of deeper networks for expressing natural functions

3 min read

Properties5
StatusActive — read 2026-10-09 (NOTE-693); worth reading as the sequel that turns LIT-887's one depth-separation theorem into a family, and for where the family stops. Proved, for networks without biases and smooth activations with nonzero Taylor coefficients: one hidden layer needs exactly ∏(rᵢ+1) neurons to Taylor-approximate the monomial x₁^r₁⋯xₙ^rₙ, against Σ(7⌈log₂ rᵢ⌉+4) for a deep network; a sparse polynomial with c monomials costs at least 1/c of its dearest monomial; xᵈ costs d+1 shallow against 7⌈log₂ d⌉ deep; and a product of n inputs costs O(n^((k−1)/k)·2^(n^(1/k))) at depth k. The move to uniform approximation, its headline over LIT-887, rests for the lower bounds on a step the proof asserts and that is false in general (a network can be uniformly within ε of a polynomial while its Taylor coefficients diverge), so only the Taylor-sense lower bounds are established. That depth k needs 2^Θ(n^(1/k)) neurons is a conjecture, backed by one trained-network figure at n = 20 with tanh, outside the theorems' hypotheses. The gap is exponential in a monomial's degree, not in the number of inputs: polynomials of bounded degree, such as the low-order Hamiltonians LIT-887 calls natural, show none.
Tagsmathematics, learning-theory, anthology-candidate
ExtendsLIT-887 — Why does deep and cheap learning work so well?
Cited as “paper” byNOTE-693 — The power of deeper networks for expressing natural functions
Cited as “source” byTHEORY-206 — For networks of smooth units without biases, one hidden layer needs exactly ∏(rᵢ+1) neurons to match the monomial x₁^r₁⋯xₙ^rₙ's Taylor polynomial at the origin, and a deep network O(Σ log rᵢ), with the upper bounds holding for uniform approximation too, so the cost of flattening a polynomial grows exponentially with its degree in distinct variables and not with the number of inputs: products of many inputs separate depths, bounded-degree polynomials do not

Graph View

David Rolnick and Max Tegmark (2017), ICLR 2018 — ARXIV-1705.05502

Key takeaways

  • The monomial cost, exactly. For σ with nonzero Taylor coefficients up to degree d (2d for uniform approximation), one hidden layer needs exactly ∏(rᵢ+1) neurons to approximate x₁^r₁⋯xₙ^rₙ of degree d, and a deep network at most Σ(7⌈log₂ rᵢ⌉+4) (Theorems 4.1 and 4.2). With all rᵢ = 1 this is LIT-887’s 2^n against about 4n.
  • Proved in the Taylor sense; the uniform lower bound is not. Taylor approximation of a homogeneous polynomial gives uniform approximation with the same neuron count by rescaling (Proposition 3.3, checked), so every upper bound holds uniformly. The uniform lower bounds assume that a network uniformly within ε of p has Taylor coefficients near p’s; one bias-free unit, ε·tanh(x/ε²), is within ε of 0 with first coefficient 1/ε, so that step needs an argument the paper does not give.
  • Sparse polynomials and univariate ones. A polynomial with c monomials costs a single layer at least 1/c of its dearest monomial (Theorem 4.3), so the gap survives subexponential sparsity. Any univariate polynomial of degree d needs at most d+1 shallow neurons; xᵈ needs exactly d+1 shallow and at most 7⌈log₂ d⌉ deep (Propositions 4.5 and 4.6): linear against logarithmic.
  • Depth k interpolates, by construction and conjecture. Multiplying groups of n^(1/k) inputs per layer gives O(n^((k−1)/k)·2^(n^(1/k))) for a product of n inputs at depth k (Theorem 5.1, Taylor-sense construction). That this is tight, 2^Θ(n^(1/k)), is Conjecture 5.2, supported by one heat map of trained networks at n = 20.
  • The gap is in the degree, not in n. Every lower bound grows with the number of distinct partial derivatives of a monomial, so a polynomial of bounded degree has a shallow cost at most c·2^d whatever n is. The exponential separation is for products of many variables, not for the low-order polynomials LIT-887 argues physics supplies.

Standing in the record

Filed on 2026-10-09 at the owner’s request, as one of the works cited by the batch on hierarchy and hyperbolic geometry that neither record held (nucleation#115, via LIT-887): the reading of Lin, Tegmark and Rolnick (LIT-887, NOTE-688) named this sequel by two of its authors as held in neither record. Read on its own merits (NOTE-693), and placed against that reading so as not to repeat it.

What it adds to LIT-887. NOTE-688 found LIT-887’s no-flattening theorem narrow on four counts: one hidden layer only, Taylor matching only, smooth activations only, and products only. This paper widens the last (general monomials, sparse and univariate polynomials) and the first (an upper bound at every depth k, with a conjecture for the matching lower bound). It claims to widen the second, to uniform approximation, and does so for the upper bounds; its lower-bound proofs carry an unsupported step. It does not touch the third: it excludes ReLU from its theorems, and its only evidence for ReLU and for tanh (whose even Taylor coefficients vanish) is the experiment. It also does not close the gap NOTE-688 named in LIT-887’s depth argument, a flattening cost for the composition of a Markov hierarchy’s sufficient statistics; products remain the only composition with a proved cost.

Filed as THEORY-206. It bears on QUESTION-025 only indirectly: the exponential cost is for products of real-valued inputs, while a conjunction of k binary attributes is one threshold unit (LIT-887, Eq. 13), so a concept lattice’s meets over binary attribute indicators stay cheap.

Backlinks