We derive upper bounds on the generalization error of learning algorithms
based on their \emph{algorithmic transport cost}: the expected Wasserstein
distance between the output hypothesis and the output hypothesis conditioned on
an input example. The bounds provide a novel approach to study the
generalization of learning algorithms from an optimal transport view and impose
less constraints on the loss function, such as sub-gaussian or bounded. We
further provide several upper bounds on the algorithmic transport cost in terms
of total variation distance, relative entropy (or KL-divergence), and VC
dimension, thus further bridging optimal transport theory and information
theory with statistical learning theory. Moreover, we also study different
conditions for loss functions under which the generalization error of a
learning algorithm can be upper bounded by different probability metrics
between distributions relating to the output hypothesis and/or the input data.
Finally, under our established framework, we analyze the generalization in deep
learning and conclude that the generalization error in deep neural networks
(DNNs) decreases exponentially to zero as the number of layers increases. Our
analyses of generalization error in deep learning mainly exploit the
hierarchical structure in DNNs and the contraction property of $f$-divergence,
which may be of independent interest in analyzing other learning models with
hierarchical structure.

该研究使用算法传输成本的期望 Wasserstein 距离得到了学习算法泛化误差的上界，为通过最优传输视图研究学习算法的泛化提供了新途径并对损失函数施加了较少的限制，并通过总变差距离、相对熵和 VC 维度提供了几个其他的算法传输成本的上界，最后基于我们的建立的框架，我们分析了深度学习中的泛化误差并得出了结论：深度神经网络中的泛化误差随着层数的增加而指数级下降。