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

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.

arXiv comment30 pages, 3 figures

References in corpus (10)

• Rényi Divergence and Kullback-Leibler Divergence
• Stochastic Gradient Hamiltonian Monte Carlo
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• From $\epsilon$-entropy to KL-entropy: Analysis of minimum information complexity density estimation
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach
• A Primer on PAC-Bayesian Learning
• Learners that Use Little Information
• A simple probabilistic construction yielding generalized entropies and divergences, escort distributions and q-Gaussians
• Representing smooth functions as compositions of near-identity functions with implications for deep network optimization

Cited by in corpus (1)

• Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms