  We adopt an information-theoretic framework to analyze the generalization
behavior of the class of iterative, noisy learning algorithms. This class is
particularly suitable for study under information-theoretic metrics as the
algorithms are inherently randomized, and it includes commonly used algorithms
such as Stochastic Gradient Langevin Dynamics (SGLD). Herein, we use the
maximal leakage (equivalently, the Sibson mutual information of order infinity)
metric, as it is simple to analyze, and it implies both bounds on the
probability of having a large generalization error and on its expected value.
We show that, if the update function (e.g., gradient) is bounded in $L_2$-norm
and the additive noise is isotropic Gaussian noise, then one can obtain an
upper-bound on maximal leakage in semi-closed form. Furthermore, we demonstrate
how the assumptions on the update function affect the optimal (in the sense of
minimizing the induced maximal leakage) choice of the noise. Finally, we
compute explicit tight upper bounds on the induced maximal leakage for other
scenarios of interest.
