# Convolutional Rectifier Networks as Generalized Tensor Decompositions

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2016.

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

- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Model Complexity of Deep Learning: A Survey](https://mlsanity.com/paper/2103.05127/) (2021)
- [Tensor Methods in Computer Vision and Deep Learning](https://mlsanity.com/paper/2107.03436/) (2021)
- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [Fast convolutional neural networks on FPGAs with hls4ml](https://mlsanity.com/paper/2101.05108/) (2021)
- [Tensor Networks Meet Neural Networks: A Survey and Future Perspectives](https://mlsanity.com/paper/2302.09019/) (2023)
- [Approximation and Learning with Deep Convolutional Models: a Kernel Perspective](https://mlsanity.com/paper/2102.10032/) (2021)
- [Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks](https://mlsanity.com/paper/2201.11729/) (2022)
- [Augmenting Deep Classifiers with Polynomial Neural Networks](https://mlsanity.com/paper/2104.07916/) (2021)
- [Learning with convolution and pooling operations in kernel methods](https://mlsanity.com/paper/2111.08308/) (2021)
- [A Survey on Statistical Theory of Deep Learning: Approximation, Training Dynamics, and Generative Models](https://mlsanity.com/paper/2401.07187/) (2024)
- [On the Ability of Graph Neural Networks to Model Interactions Between Vertices](https://mlsanity.com/paper/2211.16494/) (2022)
- [Classical versus Quantum: comparing Tensor Network-based Quantum Circuits on LHC data](https://mlsanity.com/paper/2202.10471/) (2022)
- [Piecewise Linear Neural Networks and Deep Learning](https://mlsanity.com/paper/2206.09149/) (2022)
- [Language Modeling Using Tensor Trains](https://mlsanity.com/paper/2405.04590/) (2024)
- [Entangled q-Convolutional Neural Nets](https://mlsanity.com/paper/2103.11785/) (2021)
- [Why do networks have inhibitory/negative connections?](https://mlsanity.com/paper/2208.03211/) (2022)
- [What Makes Data Suitable for a Locally Connected Neural Network? A Necessary and Sufficient Condition Based on Quantum Entanglement](https://mlsanity.com/paper/2303.11249/) (2023)
- [Memorization Capacity of Neural Networks with Conditional Computation](https://mlsanity.com/paper/2303.11247/) (2023)
- [A Tensor Decomposition Perspective on Second-order RNNs](https://mlsanity.com/paper/2406.05045/) (2024)
- [Efficient Visual Recognition with Deep Neural Networks: A Survey on Recent Advances and New Directions](https://mlsanity.com/paper/2108.13055/) (2021)
- [Spatial-temporal traffic modeling with a fusion graph reconstructed by tensor decomposition](https://mlsanity.com/paper/2212.05653/) (2022)
- [Low-Rank Tensor Decompositions for the Theory of Neural Networks](https://mlsanity.com/paper/2508.18408/) (2025)
- [Tensorized Hypergraph Neural Networks](https://mlsanity.com/paper/2306.02560/) (2023)
- [Tensor Ring Optimized Quantum-Enhanced Tensor Neural Networks](https://mlsanity.com/paper/2310.01515/) (2023)
- [conv_einsum: A Framework for Representation and Fast Evaluation of Multilinear Operations in Convolutional Tensorial Neural Networks](https://mlsanity.com/paper/2401.03384/) (2024)
- [Lecture Notes on Linear Neural Networks: A Tale of Optimization and Generalization in Deep Learning](https://mlsanity.com/paper/2408.13767/) (2024)
- [Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks](https://mlsanity.com/paper/2501.05930/) (2025)
- [On the Role of Depth in the Expressivity of RNNs](https://mlsanity.com/paper/2604.02201/) (2026)
- [Tensor-Augmented Convolutional Neural Networks: Enhancing Expressivity with Generic Tensor Kernels](https://mlsanity.com/paper/2604.08072/) (2026)

## Abstract (arXiv)

Convolutional rectifier networks, i.e. convolutional neural networks with rectified linear activation and max or average pooling, are the cornerstone of modern deep learning. However, despite their wide use and success, our theoretical understanding of the expressive properties that drive these networks is partial at best. On the other hand, we have a much firmer grasp of these issues in the world of arithmetic circuits. Specifically, it is known that convolutional arithmetic circuits possess the property of "complete depth efficiency", meaning 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 implemented (or even approximated) by a shallow network. In this paper we describe a construction based on generalized tensor decompositions, that transforms convolutional arithmetic circuits into convolutional rectifier networks. We then use mathematical tools available from the world of arithmetic circuits to prove new results. First, we show that convolutional rectifier networks are universal with max pooling but not with average pooling. Second, and more importantly, we show that depth efficiency is weaker with convolutional rectifier networks than it is with convolutional arithmetic circuits. This leads us to believe that developing effective methods for training convolutional arithmetic circuits, thereby fulfilling their expressive potential, may give rise to a deep learning architecture that is provably superior to convolutional rectifier networks but has so far been overlooked by practitioners.