Boosting Dilated Convolutional Networks with Mixed Tensor Decompositions

Nadav Cohen, Ronen Tamari, Amnon Shashua

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.

  1. Grid Tensors: The authors view the function a network learns as a massive, multi-dimensional lookup table (a tensor).
  2. 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.
DCNs and their corresponding mode trees
  1. 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."
Mixing two mode trees to create an interconnected network
  1. 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

Abstract

The driving force behind deep networks is their ability to compactly represent rich classes of functions. The primary notion for formally reasoning about this phenomenon is expressive efficiency, which refers to a situation where one network must grow unfeasibly large in order to replicate functions of another. To date, expressive efficiency analyses focused on the architectural feature of depth, showing that deep networks are representationally superior to shallow ones. In this paper we study the expressive efficiency brought forth by connectivity, motivated by the observation that modern networks interconnect their layers in elaborate ways. We focus on dilated convolutional networks, a family of deep models delivering state of the art performance in sequence processing tasks. By introducing and analyzing the concept of mixed tensor decompositions, we prove that interconnecting dilated convolutional networks can lead to expressive efficiency. In particular, we show that even a single connection between intermediate layers can already lead to an almost quadratic gap, which in large-scale settings typically makes the difference between a model that is practical and one that is not. Empirical evaluation demonstrates how the expressive efficiency of connectivity, similarly to that of depth, translates into gains in accuracy. This leads us to believe that expressive efficiency may serve a key role in developing new tools for deep network design.
BibTeX
@inproceedings{cohen2018boosting,
  author = {Nadav Cohen and Ronen Tamari and Amnon Shashua},
  title = {{Boosting Dilated Convolutional Networks with Mixed Tensor Decompositions}},
  booktitle = {International Conference on Learning Representations},
  year = {2018},
  url = {https://openreview.net/forum?id=S1JHhv6TW},
}
Figure