Abstract
The driving force behind convolutional networks - the most successful deep learning architecture to date, is their expressive power. Despite its wide acceptance and vast empirical evidence, formal analyses supporting this belief are scarce. The primary notions for formally reasoning about expressiveness are efficiency and inductive bias. Expressive efficiency refers to the ability of a network architecture to realize functions that require an alternative architecture to be much larger. Inductive bias refers to the prioritization of some functions over others given prior knowledge regarding a task at hand. In this paper we overview a series of works written by the authors, that through an equivalence to hierarchical tensor decompositions, analyze the expressive efficiency and inductive bias of various convolutional network architectural features (depth, width, strides and more). The results presented shed light on the demonstrated effectiveness of convolutional networks, and in addition, provide new tools for network design.
Introduction
Despite the world-conquering success of Convolutional Networks (ConvNets), our understanding of why they work remains largely empirical. Most architectures are designed via trial-and-error or "conventional wisdom." This paper moves ConvNet design from heuristic "black magic" toward a principled science by providing a formal mathematical bridge between ConvNets and hierarchical tensor decompositions.
The analysis focuses on two core concepts:
- Expressive Efficiency: The ability of an architecture to represent complex functions using significantly fewer parameters than an alternative.
- Inductive Bias: The prioritization of specific types of functions that are useful for real-world tasks, such as those modeling correlations between nearby pixels.
Theoretical Framework: ConvNets as Tensor Decompositions
The authors utilize a specific model family called Convolutional Arithmetic Circuits (ConvACs). These are ConvNets where activations are linear and pooling is based on products rather than "max" or "average." The "secret sauce" of this research is the proof that ConvACs are mathematically equivalent to hierarchical tensor decompositions.
Specifically, shallow networks correspond to CP (CANDECOMP/PARAFAC) decompositions, while deep networks correspond to HT (Hierarchical Tucker) decompositions. By leveraging this equivalence, tools from tensor analysis and quantum physics (specifically entanglement measures) can be applied to prove theorems about standard ConvNet features.
Key Insights and Ideas
The equivalence to tensor networks allows for a rigorous study of how architectural choices affect a model's hypothesis space.
- The Exponential Power of Depth: Deep networks are proven to be "exponentially efficient." To replicate the functions of a deep network, a shallow network would need an exponential number of hidden channels. In ConvACs, this efficiency is "complete," meaning almost any function a deep network learns is impossible for a shallow one to mimic efficiently.
- Pooling and Inductive Bias: The geometry of pooling windows determines which input regions can "interact." Standard contiguous pooling favors interactions between nearby regions—perfect for natural images. By changing pooling geometry, one can tailor a network to favor different symmetries.
- Overlaps and Interconnectivity: Overlapping operations (strides smaller than window sizes) provide an exponential boost in expressive efficiency compared to non-overlapping versions. Furthermore, interconnecting parallel paths (as in ResNets) brings at least a quadratic gap in efficiency.
- The Quantum Connection: By viewing ConvNets as tensor networks, the authors use the "min-cut" principle (analogous to entanglement entropy in quantum many-body systems) to show that the width of deep layers is critical for modeling long-range dependencies.
Results and Implications
The theoretical findings establish that for ConvACs, the expressive efficiency of depth is both exponential and complete. While standard Rectifier Networks (ReLU and max-pooling) also show exponential efficiency, it is "incomplete," suggesting that Arithmetic Circuits might have untapped potential for even greater expressive power.
These results provide new tools for network design. Instead of trial-and-error, engineers can potentially use "min-cut" and tensor tools to calculate optimal layer widths and pooling geometries based on a task's specific correlation structure.
Conclusion
This series of works provides a rigorous foundation for understanding the success of ConvNets. While the most rigorous proofs apply to Arithmetic Circuits, the framework extends to standard ReLU networks. Future research aims to automate network design using these theoretical tools, bridging the gap between representation theory and practical optimization.
Summary updated