Research map / Architectures and efficiency / RNNs and normalization

Depth-Bounds for Neural Networks via the Braid Arrangement

NeurIPS 2025 · Architectures and efficiency › RNNs and normalization · approach: Width and depth of ReLU networks · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves a doubly-logarithmic depth lower bound for braid-fan-conforming ReLU/maxout networks computing the max of d numbers, gives a combinatorial proof that 3 layers... (5 numbers needs 3 layers under the assumption), and shows a rank-(3,2) maxout network computes the max of 7 numbers.

Problem

Exact representation of continuous piecewise linear functions by ReLU networks requires how many hidden layers; best known general lower bound is 2. The paper studies networks whose breakpoints conform to the braid fan.

Approach

Uses the isomorphism between braid-fan-compatible CPWL functions and set functions on Boolean lattices, defines subspaces Sf(k) closed under the rank-2 maxout operation (A(Sf(k)) subset of Sf(k^2+k)), yielding a doubly-logarithmic depth lower bound for braid-conforming networks.

Key results

• Shows max of d numbers requires Omega(log log d) hidden layers for braid-conforming ReLU networks (d = 2^(2^l-1))
• Gives a combinatorial proof that max of 5 numbers needs 3 hidden layers for braid-conforming networks, previously verified only computationally
• A rank-(3,2) maxout network computes max{0,x_1..x_6} (max of 7 numbers), beating the natural rank-product upper bound of 6

Measured effects reported in the paper

Surprising findings

• A rank-(3,2) maxout network computes the max of 7 numbers, showing the natural generalization of the upper bound is not tight
• Max of 5 numbers cannot be computed with 2 braid-conforming hidden layers, suggesting braid-conforming restriction is a real restriction since unrestricted networks can do 5 numbers with 2 layers

Limitations

• Results only hold for braid-conforming networks, not general ReLU networks
• Lower bound is doubly logarithmic, not the logarithmic bound needed for the open question
• Proofs are combinatorial and dense; the 5-number result relies on a combinatorial argument rather than general theory

Experimental setup

Metrics: representability (exact) lower bound on depth

Baselines: Haase et al. 2023 (B_d^0-conforming 2-layer lower bound) Arora et al. 2018 (ceil(log2(d+1)) upper bound) Mixed integer programming computational proof

Builds on: Arora et al. 2018 ReLU exact representation Haase et al. 2023 lower bounds for polyhedral complexes Hertrich et al. 2021 integral weight depth lower bounds

Closest papers by meaning

• Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes (ICLR 2023 · similarity 0.90)
• Towards Lower Bounds on the Depth of ReLU Neural Networks (NeurIPS 2021 · similarity 0.90)
• On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth (ICLR 2025 · similarity 0.89)
• Understanding Deep Neural Networks with Rectified Linear Units (ICLR 2018 · similarity 0.89)
• The Computational Complexity of Counting Linear Regions in ReLU Neural Networks (NeurIPS 2025 · similarity 0.86)
• Most ReLU Networks Admit Identifiable Parameters (NeurIPS 2026 · similarity 0.86)