We study data-dependent uniform generalization bounds by approaching the problem from a PAC-Bayesian perspective. We first apply the PAC-Bayesian framework on « random sets » in a rigorous way, where the training algorithm is assumed to output a data-dependent hypothesis set after observing the training data. This approach allows us to prove data-dependent bounds, which can be applicable in numerous contexts. To highlight the power of our approach, we consider several applications of these new techniques.
First, we prove uniform bounds over the trajectories of continuous Langevin dynamics and stochastic gradient Langevin dynamics. These results provide novel information about the generalization properties of noisy algorithms.
Second, we focus on the geometric terms appearing in our generalization bounds and use it to (1) simplify and recover existing fractal-based generalization bounds and (2) develop new topological bounds that are better adapted to discrete-time stochastic optimizers compared to the previous fractal approach.

Links to the papers:
– https://arxiv.org/abs/2404.17442
– https://arxiv.org/abs/2407.08723
– https://arxiv.org/abs/2302.02766