# On the Expressive Power of Deep Learning: A Tensor Analysis

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

## Key facts

- Cited by 97 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2015.

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

- [Rethinking Spatial Dimensions of Vision Transformers](https://mlsanity.com/paper/2103.16302/) (2021)
- [SpookyNet: Learning Force Fields with Electronic Degrees of Freedom and Nonlocal Effects](https://mlsanity.com/paper/2105.00304/) (2021)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [TT-Rec: Tensor Train Compression for Deep Learning Recommendation Models](https://mlsanity.com/paper/2101.11714/) (2021)
- [An end-to-end trainable hybrid classical-quantum classifier](https://mlsanity.com/paper/2102.02416/) (2021)
- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [Random Feature Amplification: Feature Learning and Generalization in Neural Networks](https://mlsanity.com/paper/2202.07626/) (2022)
- [ExSpliNet: An interpretable and expressive spline-based neural network](https://mlsanity.com/paper/2205.01510/) (2022)
- [Tensor Networks Meet Neural Networks: A Survey and Future Perspectives](https://mlsanity.com/paper/2302.09019/) (2023)
- [Tensor-Train Density Estimation](https://mlsanity.com/paper/2108.00089/) (2021)
- [Grokking phase transitions in learning local rules with gradient descent](https://mlsanity.com/paper/2210.15435/) (2022)
- [Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks](https://mlsanity.com/paper/2201.11729/) (2022)
- [Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.00136/) (2021)
- [High-Order Pooling for Graph Neural Networks with Tensor Decomposition](https://mlsanity.com/paper/2205.11691/) (2022)
- [What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?](https://mlsanity.com/paper/2409.07953/) (2024)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [2-D SSM: A General Spatial Layer for Visual Transformers](https://mlsanity.com/paper/2306.06635/) (2023)
- [Deep ReLU Networks Preserve Expected Length](https://mlsanity.com/paper/2102.10492/) (2021)
- [On the Spectral Bias of Convolutional Neural Tangent and Gaussian Process Kernels](https://mlsanity.com/paper/2203.09255/) (2022)
- [Machine learning with tree tensor networks, CP rank constraints, and tensor dropout](https://mlsanity.com/paper/2305.19440/) (2023)
- [Tensor networks and efficient descriptions of classical data](https://mlsanity.com/paper/2103.06872/) (2021)
- [Are All Linear Regions Created Equal?](https://mlsanity.com/paper/2202.11749/) (2022)
- [Permutation Search of Tensor Network Structures via Local Sampling](https://mlsanity.com/paper/2206.06597/) (2022)
- [The Serial Scaling Hypothesis](https://mlsanity.com/paper/2507.12549/) (2025)
- [Neural networks with linear threshold activations: structure and algorithms](https://mlsanity.com/paper/2111.08117/) (2021)
- [A Simple Single-Scale Vision Transformer for Object Localization and Instance Segmentation](https://mlsanity.com/paper/2112.09747/) (2021)
- [Minimal Width for Universal Property of Deep RNN](https://mlsanity.com/paper/2211.13866/) (2022)
- [On the Ability of Graph Neural Networks to Model Interactions Between Vertices](https://mlsanity.com/paper/2211.16494/) (2022)
- [Tensor-view Topological Graph Neural Network](https://mlsanity.com/paper/2401.12007/) (2024)
- [Identifiability of Deep Polynomial Neural Networks](https://mlsanity.com/paper/2506.17093/) (2025)

## Abstract (arXiv)

It has long been conjectured that hypotheses spaces suitable for data that is compositional in nature, such as text or images, may be more efficiently represented with deep hierarchical networks than with shallow ones. Despite the vast empirical evidence supporting this belief, theoretical justifications to date are limited. In particular, they do not account for the locality, sharing and pooling constructs of convolutional networks, the most successful deep learning architecture to date. In this work we derive a deep network architecture based on arithmetic circuits that inherently employs locality, sharing and pooling. An equivalence between the networks and hierarchical tensor factorizations is established. We show that a shallow network corresponds to CP (rank-1) decomposition, whereas a deep network corresponds to Hierarchical Tucker decomposition. Using tools from measure theory and matrix algebra, we prove that besides a negligible set, all functions that can be implemented by a deep network of polynomial size, require exponential size in order to be realized (or even approximated) by a shallow network. Since log-space computation transforms our networks into SimNets, the result applies directly to a deep learning architecture demonstrating promising empirical performance. The construction and theory developed in this paper shed new light on various practices and ideas employed by the deep learning community.