Research map / Architectures and efficiency / RNNs and normalization
On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth
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.
Shows via a volume-modulo-prime argument that max(0,x_1,...,x_n) needs at least ceil(log_p(n+1)) hidden layers for ReLU networks with N-ary fraction weights (p prime not dividing N), giving ceil(log_3(n+1)) for decimal weights and an Omega(ln n / ln ln N) bound.
Problem
Exact representation of the max function max(0,x_1,...,x_n) by ReLU networks requires a minimum number of hidden layers; prior tight results covered only integer or real weights, while practical networks use rational (N-ary/decimal) weights.
Approach
Extends the Haase-Hertrich-Loho polyhedral/volume-parity argument from the prime 2 to an arbitrary prime p, using mixed volumes and the fact that normalized volume modulo p is additive when the dimension is a power of p; rescales N-ary weights to integers to transfer the lower bound.
Key results
- Max function max(0,x_1..x_n) cannot be exactly represented with fewer than ceil(log_p(n+1)) hidden layers by ReLU networks with N-ary fraction weights, for any prime p not dividing N.
- For decimal-fraction weights, the bound is ceil(log_3(n+1)) hidden layers (using p=3 since 3 does not divide 10).
- For N-ary fraction weights, depth must be at least Omega(ln n / ln ln N), so no constant-depth network suffices for fixed N.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict weights to N-ary fractions, with p a prime not dividing N | ReLU networks representing F_n exactly · F_n = max(0, x_1, ..., x_n) | minimum hidden layers required: at least ⌈log_p (n + 1)⌉ hidden layers | Helped |
| Restrict weights to decimal fractions | ReLU networks representing F_n exactly · F_n = max(0, x_1, ..., x_n) | minimum hidden layers required: at least ⌈log_3(n+1)⌉ hidden layers | Helped |
| Restrict weights to N-ary fractions | ReLU networks representing F_n exactly · F_n = max(0, x_1, ..., x_n) | minimum depth: at least C · \frac{\ln n}{\ln\ln N} | Helped |
Limitations
- Does not resolve the conjecture for general real weights.
- Lower bound is only partial confirmation of the conjecture for rational weights, since ln ln N grows slowly but is not constant.
- Tightness only up to constant factor and only for integer-weight upper bounds.
Experimental setup
Builds on: Haase, Hertrich, Loho (ICLR 2023) integer-weight lower bound Hertrich, Basu, Di Summa, Skutella (NeurIPS 2021) polyhedral characterization of Toth-type mixed volume theory
Closest papers by meaning
- Neural Networks with Small Weights and Depth-Separation Barriers (NeurIPS 2020 · similarity 0.91)
- The Expressive Power of Neural Networks: A View from the Width (NeurIPS 2017 · similarity 0.91)
- Depth-Bounds for Neural Networks via the Braid Arrangement (NeurIPS 2025 · similarity 0.89)
- Most ReLU Networks Admit Identifiable Parameters (NeurIPS 2026 · similarity 0.87)
- Expressivity of ReLU-Networks under Convex Relaxations (ICLR 2024 · similarity 0.87)
- Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.