PAC-Bayes

todo

Master theorem

Let $M_t(\theta )$ be a nonnegative supermartingale with initial value 1 for all $\theta \in \Theta$. Let $\nu$ be a data-free prior. Then,

$$\mathbb{P}(\forall t,\forall \rho \in \mathcal{M}(\Theta ):{\mathbb{E}}_{\rho }\log M_t(\theta )\le D_{\text{KL}}(\rho \Vert \nu )+\log (1/\delta ))\ge 1-\delta .$$

This is the time-uniform version of the master theorem, but we can also state a master fixed-time version. This reads: Let $N(\theta )$ be nonnegative have expected value at most 1 (it is an e-value) for all $\theta \in \Theta$. Then

$$\mathbb{P}(\forall \rho \in \mathcal{M}(\Theta ):{\mathbb{E}}_{\rho }\log N(\theta )\le D_{\text{KL}}(\rho \Vert \nu )+\log (1/\delta ))\ge 1-\delta .$$