  To date, no "information-theoretic" frameworks for reasoning about
generalization error have been shown to establish minimax rates for gradient
descent in the setting of stochastic convex optimization. In this work, we
consider the prospect of establishing such rates via several existing
information-theoretic frameworks: input-output mutual information bounds,
conditional mutual information bounds and variants, PAC-Bayes bounds, and
recent conditional variants thereof. We prove that none of these bounds are
able to establish minimax rates. We then consider a common tactic employed in
studying gradient methods, whereby the final iterate is corrupted by Gaussian
noise, producing a noisy "surrogate" algorithm. We prove that minimax rates
cannot be established via the analysis of such surrogates. Our results suggest
that new ideas are required to analyze gradient descent using
information-theoretic techniques.
