Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence

Information-theoretic bounds, while achieving significant success in analyzing the generalization of randomized learning algorithms, have been crit-icized for their slow convergence rates and over-estimation. This paper presents novel bounds that bridge the expected empirical and population risks through a binarized variant of the Jensen-Shannon divergence. Leveraging our foundational lemma that characterizes the interaction between an arbi-trary and a binary variable, we derive hypothesis-based bounds that enhance existing conditional mutual information bounds by reducing the num-ber of conditioned samples from 2 to 1. We ad-ditionally establish prediction-based bounds that surpass prior bounds based on evaluated loss mu-tual information measures. Thereafter, through a new binarization technique for the evaluated loss variables, we obtain exactly tight generalization bounds broadly applicable to general randomized learning algorithms for any bounded loss func-tions. Our results effectively address key limi-tations of previous results in analyzing certain stochastic convex optimization problems, without requiring additional stability or compressibility assumptions about the learning algorithm.