Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets.

Amir R. Asadi, Emmanuel AbbearXiv 2019 · OpenReview

TL;DR

This paper introduces a novel approach to training neural networks by leveraging "multilevel relative entropy" and a "chaining mutual information" technique. This allows for new generalization bounds and a training procedure that exploits the chain rule of relative entropy, offering theoretical guarantees and an alternative to traditional backpropagation.

What Problem Does This Paper Address?

Training deep neural networks effectively often involves a trade-off between fitting the training data (low empirical risk) and generalizing well to unseen data (low excess risk). Traditional methods for bounding generalization error, like those based on KL-divergence or mutual information, often treat the neural network as a monolithic entity. However, neural networks have a hierarchical, layered structure. This paper aims to develop generalization bounds and training algorithms that explicitly account for this multilevel structure, potentially leading to tighter bounds and more robust training.

Methods

The core of this work lies in two main contributions:

  • Multilevel Relative Entropy and Chaining Mutual Information (CMI): The authors extend the concept of relative entropy to a "multilevel relative entropy" that captures the hierarchical nature of neural networks. They combine this with the "chaining mutual information" (CMI) technique, which breaks down complex dependencies into a sum of simpler ones. This allows them to derive generalization bounds that are "algorithm-dependent" and exploit the layered architecture.
  • Multilevel Entropic Regularization and Training: The derived generalization bounds lead to a new regularization term: "multilevel entropic regularization." Minimizing this regularization term results in a "multi-scale generalization of the Gibbs posterior distribution." This distribution is obtained through a novel "Marginalize-Tilt (MT)" algorithm, which effectively uses the chain rule of relative entropy. This forms the basis for a new training procedure that offers performance guarantees.
  • Multilevel Metropolis Algorithm: To efficiently implement the training procedure, a "multilevel Metropolis algorithm" is developed. This algorithm simulates the multi-scale Gibbs distribution, specifically demonstrated for a two-layer neural network.

Datasets

  • MNIST: Used for an experimental evaluation of the proposed multilevel Metropolis algorithm on a two-layer neural network.

Key Insights and Ideas

  • Exploiting Hierarchy: Neural networks are not just complex functions; they are structured in layers. By explicitly modeling this hierarchy with multilevel relative entropy, we can derive more informative generalization bounds.
  • Chain Rule of Relative Entropy vs. Derivatives: The proposed training method replaces the traditional reliance on the chain rule of derivatives (used in backpropagation) with the chain rule of relative entropy. This offers a fundamentally different perspective on how to optimize neural networks.
  • Gibbs Distribution Generalization: The work extends the well-known Gibbs posterior distribution to a "multi-scale" version, which is crucial for handling the hierarchical structure of neural networks.
  • Algorithm-Dependent Bounds: The derived bounds are not just theoretical curiosities; they are "algorithm-dependent," meaning they can be influenced by the specific training algorithm used, offering a path towards more tailored optimization.

Key Results

  • New Generalization Bounds: The paper derives new generalization and excess risk bounds for neural networks based on multilevel relative entropy and CMI. These bounds are algorithm-dependent and exploit the network's multilevel structure.
  • Novel Training Procedure: A new training procedure is proposed, based on minimizing a multilevel entropic regularization term. This procedure is theoretically grounded and offers performance guarantees.
  • Experimental Validation: A multilevel Metropolis algorithm was implemented and tested on the MNIST dataset for a two-layer neural network. While the experiment was a proof of concept, it demonstrated the feasibility of the approach. The training error reached approximately 0.052 and the test error reached approximately 0.067.

Limitations and Future Work

  • Computational Cost: The paper acknowledges that Markov Chain Monte Carlo (MCMC) methods, like the proposed multilevel Metropolis algorithm, can be computationally more demanding than gradient-based methods.
  • Tuning Parameters: Tuning the temperature parameters for simulating the Gibbs distribution is mentioned as a challenge, and the authors suggest this as future work, aiming to achieve low test error while maintaining low mixing time.
  • Scalability: While the theoretical framework is general, the efficient implementation (multilevel Metropolis) is demonstrated for a two-layer network. Extending this to deeper networks and exploring optimizations for faster simulation are areas for future research.
  • Generalization to Other Architectures: The work focuses on feed-forward neural nets and ResNets. Further exploration of how this framework applies to other architectures (e.g., recurrent neural networks, transformers) would be valuable.

Summary updated

Abstract

We derive generalization and excess risk bounds for neural nets using a family of complexity measures based on a multilevel relative entropy. The bounds are obtained by introducing the notion of generated hierarchical coverings of neural nets and by using the technique of chaining mutual information introduced in Asadi et al. NeurIPS'18. The resulting bounds are algorithm-dependent and exploit the multilevel structure of neural nets. This, in turn, leads to an empirical risk minimization problem with a multilevel entropic regularization. The minimization problem is resolved by introducing a multi-scale generalization of the celebrated Gibbs posterior distribution, proving that the derived distribution achieves the unique minimum. This leads to a new training procedure for neural nets with performance guarantees, which exploits the chain rule of relative entropy rather than the chain rule of derivatives (as in backpropagation). To obtain an efficient implementation of the latter, we further develop a multilevel Metropolis algorithm simulating the multi-scale Gibbs distribution, with an experiment for a two-layer neural net on the MNIST data set.
BibTeX
@misc{asadi2019chaining,
  author = {Amir R. Asadi and Emmanuel Abbe},
  title = {{Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets.}},
  year = {2019},
  eprint = {1906.11148},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.11148},
}
Figure