This paper, originally presented at ICLR 2018, provides a rigorous theoretical foundation for a trend that has dominated deep learning for years: complex connectivity. While researchers have long known that "deeper is better," this work proves that how you connect those layers—specifically in Dilated Convolutional Networks (DCNs)—is just as critical for a model's representational power.
TL;DR
The authors prove that interconnecting different dilated convolutional networks creates a "mixed" model that is far more powerful than the sum of its parts. By using tensor decomposition theory, they show that even a single extra connection between intermediate layers can lead to a quadratic gap in efficiency. This allows a small "connected" network to represent functions that would require a massive, impractical "chain" network.
The Problem: Expressive Efficiency and Connectivity
In deep learning theory, expressive efficiency is the gold standard for proving an architecture's worth. It asks: Can Architecture A represent a complex function using significantly fewer parameters than Architecture B?
Historically, most "expressive efficiency" proofs focused on depth, showing that deep networks are exponentially more efficient than shallow ones. However, modern state-of-the-art networks like ResNets and DenseNets rely heavily on complex connectivity—skip connections, branching, and merging.
The authors tackle the lack of theoretical understanding regarding connectivity in Dilated Convolutional Networks (DCNs). DCNs (like WaveNet) are the backbone of modern audio and text processing, using "dilated" filters that skip over samples to capture a wider context. The core question is: Does wiring different DCNs together actually make them "smarter," or just bigger?
Methods: Bridging Deep Learning and Multilinear Algebra
The paper bridges the gap between deep learning architectures and multilinear algebra using Tensor Decompositions.
- Grid Tensors: The authors view the function a network learns as a massive, multi-dimensional lookup table (a tensor).
- Mode Trees: They represent the dilation pattern of a network as a "mode tree." A standard DCN follows one specific tree structure, mapping the hierarchical merging of information.
- Mixed Tensor Decompositions: This is the core innovation. The authors define a way to "mix" two different mode trees (representing two different dilation schemes) by swapping information at intermediate "mixture nodes."
- Matricization Rank Analysis: To prove efficiency, they analyze the "rank" of these tensors. A higher rank means the network can represent more complex correlations in the data. They provide a new theorem that gives the tightest bounds to date on these ranks, proving the mathematical superiority of mixed architectures.
Key Insights and Results
- Connectivity as a Power Multiplier: Connectivity isn't just an optimization trick to make training easier (like skip-connections helping with vanishing gradients); it fundamentally expands the "vocabulary" of functions a network can express.
- The Quadratic Gap: The most striking theoretical result is that a mixed network can be quadratically more efficient. For example, if a mixed network needs 128 channels to perform a task, a standard chain network might need over 1,500 channels to match it. In a production environment, that is the difference between a model that fits on a single GPU and one that requires a server farm.
- Zero-Cost Gains: The "mixed" architectures used in the experiments had the exact same number of parameters and the same computational cost as the baseline, yet they performed better simply because of their connectivity.
Empirical Validation
The authors validated their theory using the TIMIT speech corpus, a standard benchmark for acoustic-phonetic studies, focusing on individual phoneme classification. They compared a baseline DCN against "mixed" versions where layers from two different DCN architectures were rewired together. As the number of interconnections between hidden layers increased, the validation accuracy improved steadily (rising from roughly 69% to 71%), demonstrating that expressive efficiency translates directly into better accuracy on real-world tasks without increasing the model's budget.
Limitations and Future Work
- Arithmetic Circuits vs. Standard CNNs: Much of the formal proof relies on "convolutional arithmetic circuits" (where the activation function is a product). While the authors show that standard ReLU-based networks follow the same empirical trends, the mathematical proof for ReLU is more complex and left for future work.
- Specific Connectivity Types: The paper focuses on a specific way of mixing DCNs. While this provides a "proof of concept" for connectivity, it doesn't yet cover every possible wiring scheme used in the wild (like the dense blocks in DenseNet).
- Design Tools: The authors suggest that "expressive efficiency" should be used as a metric to design new architectures from scratch, rather than just analyzing existing ones, paving the way for future automated network design tools.
Summary updated