# On the Expressive Power of Deep Neural Networks

arXiv: https://arxiv.org/abs/1606.05336 · HTML: https://mlsanity.com/paper/1606.05336/

## Key facts

- Cited by 306 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2016.

## Built on by (most cited first, 30 of 306)

- [High-Performance Large-Scale Image Recognition Without Normalization](https://mlsanity.com/paper/2102.06171/) (2021)
- [Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective](https://mlsanity.com/paper/2102.11535/) (2021)
- [The Expressive Power of Low-Rank Adaptation](https://mlsanity.com/paper/2310.17513/) (2023)
- [Disentangling the Causes of Plasticity Loss in Neural Networks](https://mlsanity.com/paper/2402.18762/) (2024)
- [Foundation Model for Advancing Healthcare: Challenges, Opportunities, and Future Directions](https://mlsanity.com/paper/2404.03264/) (2024)
- [Zen-NAS: A Zero-Shot NAS for High-Performance Deep Image Recognition](https://mlsanity.com/paper/2102.01063/) (2021)
- [Model Complexity of Deep Learning: A Survey](https://mlsanity.com/paper/2103.05127/) (2021)
- [Prompt Waywardness: The Curious Case of Discretized Interpretation of Continuous Prompts](https://mlsanity.com/paper/2112.08348/) (2021)
- [Normalization and effective learning rates in reinforcement learning](https://mlsanity.com/paper/2407.01800/) (2024)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Neural Architecture Search for Spiking Neural Networks](https://mlsanity.com/paper/2201.10355/) (2022)
- [Deep Networks Always Grok and Here is Why](https://mlsanity.com/paper/2402.15555/) (2024)
- [Neural Redshift: Random Networks are not Random Functions](https://mlsanity.com/paper/2403.02241/) (2024)
- [Get rich quick: exact solutions reveal how unbalanced initializations promote rapid feature learning](https://mlsanity.com/paper/2406.06158/) (2024)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [The Neural Race Reduction: Dynamics of Abstraction in Gated Networks](https://mlsanity.com/paper/2207.10430/) (2022)
- [On the Power of Foundation Models](https://mlsanity.com/paper/2211.16327/) (2022)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [The Tunnel Effect: Building Data Representations in Deep Neural Networks](https://mlsanity.com/paper/2305.19753/) (2023)
- [Neural Injective Functions for Multisets, Measures and Graphs via a Finite Witness Theorem](https://mlsanity.com/paper/2306.06529/) (2023)
- [Neural Response Interpretation through the Lens of Critical Pathways](https://mlsanity.com/paper/2103.16886/) (2021)
- [Counting Ability of Large Language Models and Impact of Tokenization](https://mlsanity.com/paper/2410.19730/) (2024)
- [LieGG: Studying Learned Lie Group Generators](https://mlsanity.com/paper/2210.04345/) (2022)
- [SplineCam: Exact Visualization and Characterization of Deep Network Geometry and Decision Boundaries](https://mlsanity.com/paper/2302.12828/) (2023)
- [Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMs](https://mlsanity.com/paper/2503.10084/) (2025)
- [Do Sparse Autoencoders Capture Concept Manifolds?](https://mlsanity.com/paper/2604.28119/) (2026)
- [NASI: Label- and Data-agnostic Neural Architecture Search at Initialization](https://mlsanity.com/paper/2109.00817/) (2021)
- [Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions](https://mlsanity.com/paper/2210.07236/) (2022)
- [Multifidelity Modeling for Physics-Informed Neural Networks (PINNs)](https://mlsanity.com/paper/2106.13361/) (2021)

## Abstract (arXiv)

We propose a new approach to the problem of neural network expressivity, which seeks to characterize how structural properties of a neural network family affect the functions it is able to compute. Our approach is based on an interrelated set of measures of expressivity, unified by the novel notion of trajectory length, which measures how the output of a network changes as the input sweeps along a one-dimensional path. Our findings can be summarized as follows: (1) The complexity of the computed function grows exponentially with depth. (2) All weights are not equal: trained networks are more sensitive to their lower (initial) layer weights. (3) Regularizing on trajectory length (trajectory regularization) is a simpler alternative to batch normalization, with the same performance.