Summary
The authors propose a new oracle PAC-Bayesian bound that has two main features: it is valid for unbounded losses (or at least under assumptions weaker than bounded loss) and it allows for an exact optimization of the free parameter $\lambda$ appearing in most PAC-Bayesian bound, with only the cost of a penalty that is logarithmic in the number of data points. Based on this new bound, the authors first recover existing bounds and improve over the prior art by introducing model-dependent assumptions in the generalization bounds. They also make the link with regularization techniques. In particular, they obtain new bounds based on input-gradients by combining their theory with log-Sobolev-type inequalities.
Strengths
- The ability of exactly optimizing the free parameter $\lambda$ in an oracle PAC-Bayesian bound is a nice contribution. It may be useful in several settings.
- The proofs of the main results rely on quite general bounded CGF assumptions, which are weaker than the usual bounded loss assumption and allow for model-dependent assumptions.
- Instead of usual exponential terms that are averaged over the prior distribution, the authors provide PAC-Bayesian bounds with a stronger dependence on the posterior distribution, hence leveraging the concentration properties of each individual model. Beyond tightening the generalization bounds, this could strengthen the practical relevance of PAC-Bayesian theory.
Weaknesses
- It should be made more clear how the main results compare to existing results, especially the ones relying on grids and union bounds, as well as other PAC-Bayesian bounds that do not have neither a $\log(n)$ penalty nor free parameters for subgaussian (hence unbounded) losses. These existing results should be written explicitly and compared with the new bounds.
- Adding a few examples of situations where the new bounds clearly outperform the existing ones would enhance the paper.
- Additional technical background on the generalized inverse and its main properties would help a lot the readability of the paper, as it is the main technical ingredient.
- The log-Sobolev inequalities mentioned in the last section seem to be stronger than the usual log-Sobolev inequality. Some clarification should be added (see the questions).
- There might be a mistake in the statement of Theorem 1. Shouldn't it be $1/\lambda$ instead of $1/(\lambda n)$? In Theorem 3 of [Germain et al., 2016], the result is stated with $1/\lambda$ instead of $1/(\lambda n)$.
Questions
- Do you know any explicit example where your oracle bound yields a better optimization of $\lambda$ than the best existing results under the same assumptions (obtained either by union bound arguments or other techniques)?
- In Lemma 18, you prove that $\Lambda_\theta^* (a) < \infty$ on $[0,L(\theta))$, but then in the proofs of Lemma 6 and theorem 7, you apply $\Lambda_\theta^*$ on $gen(\theta, D)$, which may take negative values. Why is that justified?
- Corollary 13: the result would be even stronger if the expectation over the posterior was outside of the square root. Do you think it is possible to obtain such a result?
- After Assumption 2, line 279, you claim that the log-Sobolev inequality state in Assumption 2 holds for several well-known distributions, such as the Gaussian distribution. However, in the reference [50] you give for this result, a much weaker inequality appears. Indeed, the log-Sobolev inequality would be $\Lambda_\theta (\lambda) \leq \frac{C}{2} \lambda^2 L(\theta)^2$, where $L(\theta)$ is the Lipschitz constant of $x \longmapsto \nabla_x \ell(x, \theta)$. Can you prove that Assumption 2 indeed holds for the Gaussian distribution, or give a reference?
- Line 250: where exactly is this result proven in the cited paper? Can you be more precise about how this result is obtained?
**Minor remarks / questions:**
- Line 26: a $\to$ an.
- Line 17: The notation $\mathcal{M}_1(\Theta)$ should be introduced.
- Line 131: space permits to use the long notations in most cases, but it is not done, while it would improve the readability of the paper.
- Line 243: regularizaton $\to$ regularization
- Line 244: based in $\to$ based on.
- Assumption 1: if $\ell$ is $M$-Lipschitz in $\theta$, then $\Vert \nabla_\theta \ell (x,\theta)\Vert_2^2$ is bounded by $M^2$, not $M$.
- We see in Appendix A that the fact that $\ell\geq 0$ plays an important role in the proofs. Does your theory hold if $\ell$ is not lower bounded?
- In the definition of $\Lambda_\theta^*$, could the parameter $b$ depend on $\theta$? Could that cause any issue in your proofs?
Limitations
Most of the limitations were discussed in the paper.
The paper has no societal or ethical impact.