Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper derives PAC-Bayes bounds for epistemic uncertainty in terms of excess risk. A new quantity
is defined called Bayesian Excess Risk which captures the epistemic uncertainty when the true
model is known.

strength_and_weaknesses: This paper solves a pressing problem in understanding epistemic uncertainty (EU) and connects it very
well to the more traditional methods of practically estimating EU. The paper offers novel and useful
theoretical contributions which are then supported by demonstratng a regularization strategy and several
numeric experiments. The work though would be valuable even without the additional validation.

The main weakness is some of the contributions could be better signposted in the writing.

clarity,_quality,_novelty_and_reproducibility: This is highly original work that builds very nicely off of Xu and
Raginsky's recent work on excess risk. The paper is challenging to
follow due to the theoretical nature of the contributions. It would
also benefit from better signposting where the different versions of
excess risk are introduced and the reason why becomes clearer earlier
in the paper.

This work is of high quality and significance. Due to the theoretical
nature of the work, reproducibility is less of a concern.

summary_of_the_review: This is interesting and useful theoretical analysis of bounding epistemic uncertainty.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work explores the relationship among excess risk, widely used epistemic uncertainty and generalization error with convergence analysis in the setting of approximate Bayesian inference. Empirical evaluations on synthetic datasets are carried out to confirm the theoretical results. Further evaluations on UCI datasets and contextual bandit tasks are presented to compare the proposed approach with existing baselines.
strength_and_weaknesses: This work focus on excess risk analysis under approximate Bayesian inference instead of an exact setting as in existing work, which is a more practical setting and seems novel to me. The main theoretical contributions are Thm 1, Thm 2 and Thm 3 where Thm 1 connects Bayesian excessive risk under log loss with approximate mutual information and the one under squared loss with variance and Thm 2&3 upper bounds the summation of prediction excess risk and Bayesian excess risk with convergence analysis.
are nicely explained and seem technically sound.

Still, here are a few concerns:
- p^q is not defined in Eq 4.
- I'm confused by Remark 2. What do you mean by "misspecify noise function"? Can you explain it in a more formal way?
- In Fig 1 and Fig 2, I wonder which N are chosen? From the curves, it seems that the N are not uniformly chosen and also the curves are highly non-smooth. The author might what to try with more N to make some smooth curves that clearly shows the relationship among the three quantities.
- The empirical evaluation would benefit from including more baselines other than particle VI. For example, to include Bayesian Dropout methods including MC dropout, variational dropout, ensembles, Langevin MCMC etc...
clarity,_quality,_novelty_and_reproducibility: This paper is overall well-written. It makes a reasonable attempt to provide sufficient background for the readers to understand the proposed methods. The theoretical contribution is novel to me.
summary_of_the_review: Despite some minor confusion and some potential improvement for the empirical evaluations, the contributions in this work seems solid and novel to me.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This works studies the frequentist validity of popular epistemic uncertainty estimates, showing that they equal certain "Bayes excess risk" measures (Thm. 1) and are *lower bound* for the unobservable excess risk of a stochastic predictor derived from the (approximate) posterior.  The authors argue that such behaviors are undesirable and consistent with the fact that epistemic uncertainty are often underestimated in practice.  Based on these observations, the authors proposed a modified variational inference objective for regression problems, where a conditional variance term is down-weighted (Eq. 21).  Empirically the new objective demonstrates improved performance on regression and contextual bandit tasks.
strength_and_weaknesses: This work studies a very relevant problem: whether (approximate) Bayesian epistemic uncertainty estimates are valid upper bounds for the excess risk, in which case they can be viewed as valid in a frequentist sense.  The authors showed that posterior variance-like quantities can be *lower bounds* for the excess risk, which would be a serious issue and worth addressing.

However, it appears to me that the authors studied the wrong excess risk: they considered the excess risk of the stochastic predictor derived from the Gibbs posterior,
$$
R^l(Y | X, \mathbf{Z}^N) := E_{Z^n} E_{\color{blue}q(\theta\mid Z^n)} E_{Z=(X,Y)} \ell(Y, f_\theta(X)),
$$ 
as opposed to the deterministic predictor which approximates the true Bayes predictor.  The former predictor only achieves order-optimal excess risk, which is reasonable for studying contraction properties such as predictive error, but usually unreasonable as a target for uncertainty quantification.

As a concrete example, for homoscedastic regression problems with a square loss, our point estimate is typically based on the posterior mean estimate $\hat f_n(x) := \mathbb{E}_{q(\theta\mid Z^n)} f_\theta(x)$, and we are most interested in whether posterior variance quantities such as $\mathbb{E}\_{q(\theta\mid Z^n)}\big(f\_\theta(x) - \hat f_n(x)\big)^2$ upper bounds the excess risk-type quantities for the posterior mean estimator, $\mathbb{E}\_{\nu(Y|X=x)} (\hat f\_n(x) - Y)^2 - \text{(Bayes Risk at $x$)} = (\hat f_n(x) - f_0(x))^2$.  This corresponds to the scenarios where the credible intervals may have correct coverage.  However, the authors in their Theorem 2 compared this posterior variance with the quantity 
$$
R^l(Y | x, \mathbf{Z}^N) - \text{(Bayes Risk)} = \underbrace{\mathbb{E}\_{q(\theta\mid Z^n)}\big(f\_\theta(x) - \hat f_n(x)\big)^2}\_{\mathrm{BER}(Y|x,\mathbf{z}^N)} +  \underbrace{((\hat f_n(x) - f_0(x))^2}\_{\mathrm{PER}(Y | x, \mathbf{z}^N)}.
$$
Clearly, the fact that the posterior variance fails to upper bound the above says nothing about its frequentist validity.

As another sanity check, it is also unconvincing that theoretical explanations for the under-coverage issue can be provided in such general settings, as for the results in Section 3: the theorems apply to the true Bayesian posterior and correctly specified (low-dimensional) parametric models.  Clearly, the right conclusion shouldn't be that under-coverage happens across all such settings.

clarity,_quality,_novelty_and_reproducibility: The writing is reasonably clear, although the notations might be optimized.  E.g., it might be better to highlight the dependency of various quantities such as $ER^l$ on $q$.
summary_of_the_review: The authors studied a relevant problem, but appeared to have misinterpreted their results.

**Post-rebuttal update**. 

I have read the authors' response but did not find them addressing my concerns.  My concerns were twofold:

1. **The messages in Sec 3.2 were misleading.**

For the square loss case, the manuscript appears to draw connections between their Theorem 2, which shows that the posterior variance ($Var_{\theta|z^N} f_\theta(x)$) *lower bounds* their version of excess risk ($ER^{(2)}$), and the experimental fact that the posterior variance underestimates the epistemic uncertainty (EU); as shown in the following quotes:

> From Eq. (12), Varθ|zN fθ(x) clearly is a lower bound of excess risk and test error, consistent with the well-known result that the variance of the predictor often underestimates EU (Lakshminarayanan et al., 2017).

> First, the widely used EU measurements are the lower bounds of the test error and excess risks. This is consistent with the experimental fact that these EU measurements often underestimate EU.

As noted in my review and response, this is only because the authors looked at the wrong definition of ER (for this purpose): for squared loss, it equals 
$$
ER^{(2)} = E_{Z^n} E_{q(\theta|Z^n)} E_{Z=(X,Y)} (f_0(X)-f_\theta(X))^2,
$$
as opposed to 
$$
E_{Z^n} E_{Z=(X,Y)} (f_0(X) - E_{q(\theta|Z^n)} f_\theta(X))^2.
$$
(The last tuple $(X,Y)$ denote the test input.) The latter is what we want to compare the posterior variance with.

The authors misunderstood my definition of "coverage problem" in the first response, which I have clarified; in their second response, they noted that my concerned relation about $E_{(X,Y)}(Y-E_{q(\theta)} f_\theta(X))^2$ and $E_X E_{q(\theta)} (f_\theta(X) - E_{q(\theta)} f_\theta(X))^2$ (posterior variance) was not analyzed in this work.  But this is precisely my point: what Sec 3.2 analysed was not useful (and misleading), and to explain the experimental fact ofunder-coverage, one should analyze this relation as opposed to the relation studied in Theorem 2.

2. **The motivation of the algorithm was unsatisfactory.**

As the authors noted in their second response, the algorithm is motivated by the fact that "minimizing the standard VI leads to minimizing PR and BER simultaneously, as shown in Eq.~19". (I think they were referring to the standard ELBO.)  Without further explanation, or restriction of the scope of discussion, it is very unclear why this is a problem that needs to be addressed: if we do not restrict the variational family of choice, the true posterior is the minimizer for the ELBO, and clearly it doesn't always suffer from coverage problems.  The remaining of that subsection (3.3) did not offer any convincing explanation.

In summary, while the manuscript contains interesting materials (the algorithm and experiments, for example), it appears that the theoretical discussions need to be thoroughly revised.  Therefore, my rating remains unchanged.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This works studies potential PAC-Bayesian like guarantees for epistemic uncertainty estimates. The approach is to define "Bayesian Excess Risk" as to capture epistemic uncertainty, and the authors provided a number of theoretical results to analyse this quantity. 

Reviewers agree that the problem that the paper intended to study is interesting, and the technical approach of extending Xu and Raginsky's recent work is original. They have no problem with the technical correctness of the proofs.

However, concerns have been raised about the interpretation of the theoretical results. In particular, one reviewer pointed out that the theoretical results in section 3.2 can be misleading, as the reviewer and the authors cannot agree on the definition of excess risk.

After a brief read of the paper, I personally think that, while the theoretical technical results (in terms of proofs) are indeed correct, the quantities that the authors studied are not exactly the same as what Bayesian deep learning papers often report in experiments. Indeed in BDL practice for regression problems the experimental results we report (e.g., posterior predictive mean and uncertainty estimates) are computed in the way as Reviewer 6WHt pointed out. Therefore, this means it is not straightforward to directly connect the theoretical results to practical observations. E.g., the authors interpret Thm 2's indication as "consistent with the well-known result that the variance of the predictor often underestimates EU" and cited the Deep Ensemble paper, while to the best of my knowledge, there's no explicit target that allows us to directly evaluate under- or over-estimate of EU in a quantitative sense, and most of the (frequentist) calibration evaluations do not separate EU and aleatoric uncertainty.

In summary, while this paper presented very interesting theoretical tools towards studying epistemic uncertainty estimates, due to concerns of the misleading message connecting the theory and practice, I decide that the paper cannot be accepted in its current form. I encourage the authors to submit this work to another venue, by better clarification of the message of connecting theory with practice.
justification_for_why_not_higher_score: Concerns over the message communicated by the theoretical theorems are not addressed.
Decision: Reject