  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.
