We present a unified framework for deriving PAC-Bayesian generalization bounds. Unlike most previous literature on this topic, our bounds are anytime-valid (i.e., time-uniform), meaning that they hold at all stopping times, not only for a fixed sample size. Our approach combines four tools in the following order: (a) nonnegative supermartingales or reverse submartingales, (b) the method of mixtures, (c) the Donsker-Varadhan formula (or other convex duality principles), and (d) Ville's inequality. Our main result is a PAC-Bayes theorem which holds for a wide class of discrete stochastic processes. We show how this result implies time-uniform versions of well-known classical PAC-Bayes bounds, such as those of Seeger, McAllester, Maurer, and Catoni, in addition to many recent bounds. We also present several novel bounds. Our framework also enables us to relax traditional assumptions; in particular, we consider nonstationary loss functions and non-i.i.d. data. In sum, we unify the derivation of past bounds and ease the search for future bounds: one may simply check if our supermartingale or submartingale conditions are met and, if so, be guaranteed a (time-uniform) PAC-Bayes bound.
翻译:我们提出了一个用于得出PAC-Bayesian通用定义的统一框架。 与大多数以前关于这个主题的文献不同, 我们的界限是随时有效的( 即时间统一), 意味着它们在所有停留时间都保持, 不仅仅是固定的样本大小。 我们的方法将四个工具合并为以下顺序:(a) 非消极的超级超向或反向亚向交界, (b) 混合物的方法, (c) Donsker- Varadhan公式( 或其他相似的双重性原则), (d) Ville的不平等性。 我们的主要结果是一个PAC- Bayes 理论, 它保存着一个广泛的离散的随机性进程。 我们展示了这个结果如何意味着有四个不同的工具:(a) 非负面的超向式超级交界, 比如Seeger、 McAlester、 Maurer 和 Catoni, 以及许多最近的约束。 我们还提出了几个新的界限。 我们的框架还使我们能够放松传统假设; 特别是, 我们认为非静止的Bayes- Baye- bayes 等约束性功能, 以及非约束性搜索功能, 如果我们最终的上、 或连续地检查。 d. d.