  Since the celebrated works of Russo and Zou (2016,2019) and Xu and Raginsky
(2017), it has been well known that the generalization error of supervised
learning algorithms can be bounded in terms of the mutual information between
their input and the output, given that the loss of any fixed hypothesis has a
subgaussian tail. In this work, we generalize this result beyond the standard
choice of Shannon's mutual information to measure the dependence between the
input and the output. Our main result shows that it is indeed possible to
replace the mutual information by any strongly convex function of the joint
input-output distribution, with the subgaussianity condition on the losses
replaced by a bound on an appropriately chosen norm capturing the geometry of
the dependence measure. This allows us to derive a range of generalization
bounds that are either entirely new or strengthen previously known ones.
Examples include bounds stated in terms of $p$-norm divergences and the
Wasserstein-2 distance, which are respectively applicable for heavy-tailed loss
distributions and highly smooth loss functions. Our analysis is entirely based
on elementary tools from convex analysis by tracking the growth of a potential
function associated with the dependence measure and the loss function.
