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

We derive generalization and excess risk bounds for neural nets using a\nfamily of complexity measures based on a multilevel relative entropy. The\nbounds are obtained by introducing the notion of generated hierarchical\ncoverings of neural nets and by using the technique of chaining mutual\ninformation introduced in Asadi et al. NeurIPS'18. The resulting bounds are\nalgorithm-dependent and exploit the multilevel structure of neural nets. This,\nin turn, leads to an empirical risk minimization problem with a multilevel\nentropic regularization. The minimization problem is resolved by introducing a\nmulti-scale generalization of the celebrated Gibbs posterior distribution,\nproving that the derived distribution achieves the unique minimum. This leads\nto a new training procedure for neural nets with performance guarantees, which\nexploits the chain rule of relative entropy rather than the chain rule of\nderivatives (as in backpropagation). To obtain an efficient implementation of\nthe latter, we further develop a multilevel Metropolis algorithm simulating the\nmulti-scale Gibbs distribution, with an experiment for a two-layer neural net\non the MNIST data set.\n