Chaining Mutual Information and Tightening Generalization Bounds
Bounding the generalization error of learning algorithms has a long history, which yet falls short in explaining various generalization successes including those of deep learning. Two important difficulties are (i) exploiting the dependencies between the hypotheses, (ii) exploiting the dependence between the algorithm's input and output. Progress on the first point was made with the chaining method, originating from the work of Kolmogorov, and used in the VC-dimension bound. More recently, progress on the second point was made with the mutual information method by Russo and Zou '15. Yet, these two methods are currently disjoint. In this paper, we introduce a technique to combine the chaining and mutual information methods, to obtain a generalization bound that is both algorithm-dependent and that exploits the dependencies between the hypotheses. We provide an example in which our bound significantly outperforms both the chaining and the mutual information bounds. As a corollary, we tighten Dudley's inequality when the learning algorithm chooses its output from a small subset of hypotheses with high probability.
The paper begins with musings about deep learning and SGD. It then makes this claim    "In particular, classical generalization bounds do not allow to explain this phenomenon."  which requires citation as it is not established by this paper, and otherwise it's hearsay. In fact, it's arguably false. On the surface, Bartlett's 1998 bounds say that controlling the norm of the weights suffices and it could have been the case that overparametrized networks allowed for small norm solutions... enough to establish generalization.  But, in fact, these bounds imply only that the population classification error is .... less than one. That is, vacuous. Dziugaite and Roy demonstrate this by studying margin bounds based on the path-norm. (Zhang et al, in fact, do not demonstrate that Rademacher bounds cannot explain generalization... no one ever seriously proposed to explain overparametrized neural network generalization by UNIFORM convergence alone!!! Ridiculous.)  This papers contributions are more fundamental than recent hype, and so I would suggest cutting the hearsay and sticking to fundamentals as well. I find the conclusion odd as well.  I have two concerns:  1. The authors do not seem to be aware that PAC-Bayes bounds relate to mutual information by taking P = E[Q(S)] for S ~ i.i.d. and Q : Z^m \to M(H) the randomized learning algorithm. Then the KL(Q||P) part of the PAC-Bayes bound is  equal to the mutual information. While PAC-Bayes bounds control the risk of Gibbs classifiers, taking expectations leads one to bounds on the expected generalization error of a classifier drawn at random, which overlaps with the setting here!  This connection with mutual information can be found in Catoni (2007), I believe. It's certainly mentioned by McAllester in one of his PAC-Bayes tutorials too.   2. No citation is made to Audibert and Olivier (2004) "PAC-Bayesian Generic Chaining", which, combined with 1, would seem to have already delivered on the promised combination here, albeit for randomized classifiers. Raginsky et al seem not to be aware of these connections either.  I need to hear a concrete plan for how the paper will be modified to address this prior work, which seems to overlap significantly.  Other comments:  I really liked the example. Extremely clear. Regarding Table 1:  the CMI is impressive compared to the chaining and MI bounds on their own, but the bounds seem to be off by 20 or so. What explains that gap? Could a better sequence of partitions have fixed it? Generic chaining? A 20x gap will completely blow any chance of teasing apart the generalization performance of state of the art versus JUNK algorithms.   I also like the proof sketch, which is also very very clear.  Some issues:  179 The order of operations here is ambiguous. I am parsing this as           (argmax_phi X_phi) \oplus Z (mod 2pi)      which seems to be the only sensible parsing, but it's annoying I had to      spend 20 seconds on this, and manage this uncertainty going forward.  204 strictly speaking, it doesn't fail. it's just vacuous. a failure sounds like the bound is violated, which it isn't.  205 these side facts about LIL and random tournaments are irrelevant.   minor typographical issues:  122 hyphens should be an "endash" in Azuma--Hoeffding and other pairings of names.  130 typo: increasing sequence   136 text is bouncing back and forth between "the metric space" and "a (bounded) metric space". Are we now assuming (T,d) is bounded? Or only for this paragraph. If you stick with "the", consider writing "Assume now that (T,d) is a bounded space."  136 unnecessary to recall this soon after making these definitions.  204 the union bound