Abstract: Information-theoretic bounds, while achieving significant success in analyzing the generalization of randomized learning algorithms, have been criticized for their slow convergence rates and overestimation. 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 arbitrary and a binary variable, we derive hypothesis-based bounds that enhance existing conditional mutual information bounds by reducing the number of conditioned samples from $2$ to $1$. We additionally establish prediction-based bounds that surpass prior bounds based on evaluated loss mutual 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 functions. Our results effectively address key limitations of previous results in analyzing certain stochastic convex optimization problems, without requiring additional stability or compressibility assumptions about the learning algorithm.

Lay Summary:

Machine learning models often perform well on the data they’re trained on, but the real challenge is ensuring they do just as well on new, unseen data. To understand and improve this “generalization” ability, researchers have developed mathematical tools called generalization bounds. These bounds try to measure how far off a model’s performance on training data might be from its performance on future data.However, existing tools sometimes give very loose estimates. This paper introduces a new way to get much sharper, more accurate estimates. We focus on a well-known information-theoretic measure, but simplify it using a “binary” version, breaking complex outcomes down to simpler yes/no signals. This makes the math more manageable and leads to better bounds.Moreover, through a new technique called “binarization”, we provide the first generalization bounds that are not only more accurate but exactly tight: matching the best possible performance for a wide range of machine learning methods, without needing extra assumptions. This makes our bounds particularly valuable for analyzing modern, randomized learning algorithms used in areas like deep learning and optimization.In short, this work improves our ability to trust machine learning models by offering stronger, more precise tools to measure how well they will generalize to new data.