Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity

Amit Daniely, Roy Frostig, Yoram Singer

Abstract

This paper establishes a formal mathematical duality between neural network architectures and "compositional kernels." The authors prove that common random initializations create representations rich enough to express any function in a corresponding kernel space, suggesting that the success of deep learning stems from the fact that random weights provide an excellent "starting line" for optimization.

Introduction

Despite the massive empirical success of deep learning, a theoretical gap remains in explaining why it works so well. Neural network training involves optimizing highly non-convex objectives that should, in theory, be plagued by poor local minima. This research addresses three fundamental mysteries:

  1. The Role of Initialization: Why does starting with random weights lead to such good results?
  2. Expressivity vs. Learnability: Which functions can networks actually learn efficiently?
  3. Architecture Design: Is there a principled way to understand why specific architectures, like CNNs, outperform fully connected networks on structured data?

Methods

The researchers bridge the gap between Neural Networks (NNs) and Kernel Methods using several novel constructs:

  • Computation Skeletons: They define a "skeleton" as a Directed Acyclic Graph (DAG) that describes the topology of a network (e.g., layer count, node connectivity) independently of specific weights.
Examples of computation skeletons ($S_1$ through $S_4$) representing different network topologies used to derive dual kernels.
  • Compositional Kernels: For any given skeleton and activation function (like ReLU), they derive a corresponding "dual" kernel. This kernel describes the similarity measure the network "naturally" uses.
  • Dual Activation Functions: They introduce a mathematical transformation that maps standard NN activation functions into a "dual" form that operates within the kernel space.
  • Theoretical Analysis: The paper provides rigorous proofs showing that as the width of a randomly initialized network increases, its empirical behavior converges to that of its dual compositional kernel.

Key Insights and Ideas

  • The "Dual View": Every neural network architecture has a "shadow" kernel. By studying this kernel, we can understand the "inductive bias" of the architecture—what kinds of patterns it is naturally predisposed to find.
  • Initialization as a "Warm Start": Random initialization is not just a placeholder; it populates the network with a diverse set of features that span the entire dual kernel space. This turns a non-convex problem into one that starts very close to a high-quality solution.
  • The ReLU Advantage: The paper highlights that the ReLU activation is "positive homogeneous" ($\sigma(ax) = a\sigma(x)$). This makes it uniquely robust to the scale of random initialization, explaining its ease of tuning compared to other activations.
  • The "Collapsing" Depth: In standard fully connected networks, adding layers eventually causes the dual kernel to converge to a degenerate (constant) form. This explains why very deep networks require specialized components like ResNet skip connections to remain effective.

Key Results

As a theoretical paper, the authors provide mathematical proofs to explain existing empirical phenomena, citing results from datasets like MNIST, CIFAR-10, and ImageNet. Key findings include:

  • Approximation Theorems: A network with $r$ hidden units can approximate its dual kernel with an error that decreases as $r$ increases.
  • Convex Proxy: Optimizing just the last layer of a randomly initialized network is a convex task that serves as a powerful proxy for the expressive power of the entire architecture.
  • Architecture Comparison: The framework demonstrates why CNN dual kernels are a better fit for signals like audio and images compared to the kernels of fully connected networks.

Limitations and Future Work

While the paper proves that the required width $r$ is polynomial, the actual exponents in the bounds are large, which may not fully reflect the efficiency seen in practice. Furthermore, the current framework primarily analyzes fully connected and convolutional layers; extending this dual view to max-pooling and Recursive Neural Networks (RNNs) remains a key direction for future research. Finally, the paper focuses on the starting point and expressivity rather than the full trajectory of weights during training via Stochastic Gradient Descent.

Summary updated

BibTeX
@inproceedings{daniely2016toward,
  author = {Amit Daniely and Roy Frostig and Yoram Singer},
  title = {{Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
}
Figure