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.

该论文介绍了一种将锁链法和互信息法结合起来得到算法相关和利用假设间的相关性的泛化界限的技术，并提供了一个实例，其中我们的界限显著优于锁链和互信息界限；作为推论，当学习算法从高概率的小假设子集中选择其输出时，紧缩了杜德利不等式。