About PAC-Bayesian bounds in learning theory

Question

Consider PAC-Bayesian bounds used in learning theory (as defined in say section $1.2$, page $3$ of this paper, https://arxiv.org/pdf/1707.09564.pdf).

• I want to know what is the precise mathematical expression that is asked to be true when one says that the "prior distribution has to be independent of the training data". Can someone kindly state that as an equation in probability theory?

  This is confusing because to make sense of a notion of "independence" here one has to somehow first be able to imagine the "prior" and the "data" both as random variables on the same probability space. To the best of my knowledge the only formal notion of independence is that of between $2$ random variables both of which are mapping from the same probability space.

• If say one had to make a list of $K$ priors and allow oneself to choose one of these priors then there is a way to rewrite such bounds with an extra $log(K)$ term in the numerator under the square-root on the RHS.

  Now lets say that I do some auxiliary experiments with training this predictor on certain samples and realize that there is a certain prior which gives me a good RHS then I guess I am not allowed to use this prior in the bound because this is now dependent on the data. But,

  (a) Am I allowed to include this prior in the list of $K$ prior options? Or will that also break the assumptions of this proof?

  (b) Am I allowed to use this prior if I say use it in a PAC-Bayes bound for the same predictor but I have say changed the changed the data distribution from which the samples are being taken (from the auxiliary experiments to the case when the bound is being evaluated) or I have thrown away from the support of the distribution the part of the data on which I did these auxiliary experiments.

Answer 1

1. Conceptually, there are two different types of distributions: the data distribution, i.e. so we can draw data $x\sim\mathcal{D}$, and the (various) distributions over learning models, often expressed as distributions over the parameter spaces (e.g. if you're familiar with Bayesian neural networks), so we can for example write $\theta \sim \mathcal{R}$ to draw, say, a set of random weights for a neural network.

   The idea in PAC-Bayes is that you learn a distribution over predictors, $Q$, so that if you draw a random predictor $f_\theta\sim Q$ (which really means $\theta\sim Q$ I suppose but I'm following their notation), then $f_\theta$ should perform well on the data. In other words, $Q$ depends on the training data, $T=\{x_i\}_i,\,x_i\sim\mathcal{D}$. We can think of this as assuming $Q$ has parameters $\phi$, and we are learning $\phi$ from $T$. Thus, $Q$ is dependent on $T$, and thus $f_\theta\sim Q$ is dependent on it as well.

   In the paper, they consider a special case, where $f_{w+u}\sim Q$, where $w$ is learned but presumably deterministic, and $u$ is random (so I'd write $w+u\sim Q$). Consider the joint distribution $p(\theta, T)$ where $\theta=w+u$. Because $\theta$ is learned, it is dependent on $T$, so we cannot say $p(\theta,T)=p(\theta|T)p(T)=p(\theta)p(T)$.

   Now what do you do if you haven't seen any training data yet? You still want to be able to draw random predictors. So, as a Bayesian :), we define a prior $P$, so that we can draw $f_\psi \sim P$, where $P$ has no dependence on the data $T$, i.e. it is not learned. So we can write $p(\psi,T)=p(\psi)p(T)$, because $T$ and $\psi$ are independent.

   This is confusing because to make sense of a notion of "independence" here one has to somehow first be able to imagine the "prior" and the "data" both as random variables on the same probability space. To the best of my knowledge the only formal notion of independence is that of between 2 random variables both of which are mapping from the same probability space.

   The prior is not a random variable, it is a distribution. The key is that there are two spaces, the set of data $\mathcal{X}$ and that of model parameters $\Phi$, and there are distributions ($\mathcal{D}$ and $Q$ & $P$) on those spaces. Our notion of independence is on one space, if you want to think of it that way: it is on the product space, i.e. $ S= \mathcal{X}\times \Phi$, so that we can define joint distributions like $p(\psi,T)$ or $p(\theta,T)$. At least that's how I see it.

2. (a)

   Am I allowed to include this prior in the list of K prior options? Or will that also break the assumptions of this proof?

   I'm not sure about this, I don't know of the theorem you are talking about. But for this theorem or a modification of it specifically, then yes, I think it will break the proof assumptions. It would let you put $Q$ in the list for example, which probably seems problematic.

   However, you might be interested in papers doing this: e.g., Parrado-Hernandez et al, PAC-Bayes Bounds with Data Dependent Priors

   (b)

   Am I allowed to use this prior if I say use it in a PAC-Bayes bound for the same predictor but I have say changed the changed the data distribution from which the samples are being taken (from the auxiliary experiments to the case when the bound is being evaluated) or I have thrown away from the support of the distribution the part of the data on which I did these auxiliary experiments.

   Interesting question. I think this is possible but with different bounds. Specifically, maybe you could think of this as an instance of domain adaptation (for which there is a lot of work on learning bounds, which contain an additional term that is based on the difference between the old and new distributions). Note that PAC-Bayes in the domain adaptation context (e.g., Germain et al, A New PAC-Bayesian Perspective on Domain Adaptation) still utilize a prior from before seeing the the source or the target domains. You cannot escape this, usually, in a truly Bayesian method. What I am suggesting is considering the change in distribution used in the method you proposed as a form of domain adaptation. I'm not an expert in this area though. :)

---

Edit in response to the comments:

The question is

what is the fundamental mathematical difference between an RV and a distribution?

I think I will merely paraphrase a section from the Wikipedia article on RVs, which adequately describes it (italics mine):

The domain of a random variable is a sample space, which is interpreted as the set of possible outcomes of a random phenomenon.

A random variable has a probability distribution, which specifies the probability of its values. Random variables can be discrete, endowed with a probability mass function; or continuous, via a probability density function; or a mixture of both types.

Two random variables with the same probability distribution can still differ in terms of their associations with, or independence from, other random variables. The realizations of a random variable, that is, the results of randomly choosing values according to the variable's probability distribution function, are called random variates.

Answer 2

The answer to the first question above is satisfactory, so I will elaborate on the second question.

(a) Yes, this is possible by choosing data-independent priors $P_1$ to $P_K$, letting each bound hold with probability $1-\delta/K$, and then applying the union bound, so all of the bounds hold simultaneously with probability $1-\delta$, adding a term $\log(K)$ from the $\log\delta$ term. It is also possible to do this using a prior which is a mixture distribution, see e.g. Theorem A.1 from [1]. However, it is still crucial that each $P_k$ is independent of the data.

(b) If we are using a different set of data than we use to evaluate the bound, this is fine. This could either be drawn from the same distribution, or a different (but ideally similar) one. See e.g. [2] amongst many other works.

I also mention further work in e.g. [3] which uses a differentially-private mechanism to learn learn a prior from the data, adding an extra term to the bound. This is based on the idea that a differentially-private prior is "nearly" independent of the data.

[1] Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, Peter Orbanz: Non-vacuous Generalization Bounds at the ImageNet Scale: a PAC-Bayesian Compression Approach. ICLR (Poster) 2019.

[2] John Shawe-Taylor, Emilio Parrado-Hernández, Amiran Ambroladze: Data Dependent Priors in PAC-Bayes Bounds. COMPSTAT 2010: 231-240

[3] Gintare Karolina Dziugaite, Daniel M. Roy: Data-dependent PAC-Bayes priors via differential privacy. NeurIPS 2018: 8440-8450