Comparing Comparators in Generalization Bounds
This work provides a theoretical framework for improving generalization bounds in machine learning, which is incremental but offers insights for researchers in statistical learning theory.
The paper tackles the problem of deriving tight generalization bounds by using arbitrary convex comparator functions to measure the discrepancy between training and population loss, showing that the optimal bound is achieved with the convex conjugate of the cumulant-generating function, which confirms near-optimality for known cases and yields new bounds for other distributions.
We derive generic information-theoretic and PAC-Bayesian generalization bounds involving an arbitrary convex comparator function, which measures the discrepancy between the training and population loss. The bounds hold under the assumption that the cumulant-generating function (CGF) of the comparator is upper-bounded by the corresponding CGF within a family of bounding distributions. We show that the tightest possible bound is obtained with the comparator being the convex conjugate of the CGF of the bounding distribution, also known as the Cramér function. This conclusion applies more broadly to generalization bounds with a similar structure. This confirms the near-optimality of known bounds for bounded and sub-Gaussian losses and leads to novel bounds under other bounding distributions.