  We examine the relationship between the mutual information between the output
model and the empirical sample and the generalization of the algorithm in the
context of stochastic convex optimization. Despite increasing interest in
information-theoretic generalization bounds, it is uncertain if these bounds
can provide insight into the exceptional performance of various learning
algorithms. Our study of stochastic convex optimization reveals that, for true
risk minimization, dimension-dependent mutual information is necessary. This
indicates that existing information-theoretic generalization bounds fall short
in capturing the generalization capabilities of algorithms like SGD and
regularized ERM, which have dimension-independent sample complexity.
