A major challenge in designing efficient statistical supervised learning
algorithms is finding representations that perform well not only on available
training samples but also on unseen data. While the study of representation
learning has spurred much interest, most existing such approaches are
heuristic; and very little is known about theoretical generalization
guarantees.
In this paper, we establish a compressibility framework that allows us to
derive upper bounds on the generalization error of a representation learning
algorithm in terms of the "Minimum Description Length" (MDL) of the labels or
the latent variables (representations). Rather than the mutual information
between the encoder's input and the representation, which is often believed to
reflect the algorithm's generalization capability in the related literature but
in fact, falls short of doing so, our new bounds involve the "multi-letter"
relative entropy between the distribution of the representations (or labels) of
the training and test sets and a fixed prior. In particular, these new bounds
reflect the structure of the encoder and are not vacuous for deterministic
algorithms. Our compressibility approach, which is information-theoretic in
nature, builds upon that of Blum-Langford for PAC-MDL bounds and introduces two
essential ingredients: block-coding and lossy-compression. The latter allows
our approach to subsume the so-called geometrical compressibility as a special
case. To the best knowledge of the authors, the established generalization
bounds are the first of their kind for Information Bottleneck (IB) type
encoders and representation learning. Finally, we partly exploit the
theoretical results by introducing a new data-dependent prior. Numerical
simulations illustrate the advantages of well-chosen such priors over classical
priors used in IB.

设计高效的统计监督学习算法的一大挑战是找到不仅在可用训练样本上表现良好，也在未知数据上表现良好的表示方法。本文建立了一个压缩性框架，通过标签或潜在变量（表示）的 “最小描述长度”（MDL）来推导表示学习算法的泛化误差的上界。通过与固定先验的训练集和测试集的表示（或标签）分布之间的 “多字母” 相对熵，而不是通常认为反映算法泛化能力的编码器输入和表示之间的互信息，建立了新的界限。本文的压缩性方法是信息论的，基于 Blum-Langford 的 PAC-MDL 界限，并引入了两个关键因素：块编码和有损压缩。最后，本文通过引入新的数据依赖性先验，部分利用了理论结果。数值模拟展示了选择良好的先验与 IB 中使用的经典先验相比的优势。