Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Delta method allows one to construct confidence intervals. However the method involves substantial computational difficulties, such as inverting the Fisher information matrix, which is quite large if the number of parameters is large.

The paper proposes an alternative method. it involves regularisation and implies asymptotical convergence. The method is easier computationally and converges asymptotically. A number of convergence results are proven. The method returns good performance in practice.
strengths_and_weaknesses: I am worried this paper belongs to the domain of information theory rather than generic machine learning and some key points may be lost on the NeurIPS audience as they no doubts were lost on me.

Otherwise the paper appears to make a substantial contribution.

questions: Please correct me if I am wrong. I might have missed important points.
limitations: Yes.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes the _implicit delta method_ for estimating the asymptotic variance of an estimator of the form $\hat\psi_n = \psi(\hat\theta_n)$, where $\hat\theta_n$ is the MLE and $\psi: \Theta \to \mathbb{R}$ is a functional. The implicit delta method is computationally efficient in situations where fitting a model is computationally burdensome and/or the target functional is not known explicitly. The proposed method works by solving an additional estimation problem regularized with $\lambda \psi(\theta)$. The paper shows that subject to regularity conditions, $\hat V^{\mathrm{FDIDM}} = \lambda^{-1} (\psi(\hat\theta_n(\lambda)) - \hat\psi_n)$, where $\hat\theta_n(\lambda)$ is the regularized estimate resulting from the additional estimation problem, consistently estimates the asymptotic variance of $\hat\theta_n$.
strengths_and_weaknesses: The paper proposes an intriguing alternative approach to computing the asymptotic variance that does not require inverting the Fisher information matrix (or an estimate thereof). The approach is shown to lead to a consistent estimate of the asymptotic variance, albeit under some regularity conditions.

One weakness of the paper is that the applicability of the method appears to be very much limited to the settings for which the delta method also applies. Thus, although the proposed approach works as a computationally lighter alternative to the delta method, it cannot be used with estimators that fall outside of the framework (e.g., lasso-type estimators or high-dimensional regimes). Perhaps it was not the intention of the authors to imply that their method can be applied to any estimation procedures, but this was the impression formed by reading earlier parts of the paper.
questions: 1. For the finite-difference IDM, one can be so free in the choice of $\lambda$: Isn't there a benefit in making $\lambda$ as small as possible without causing numerical instability? Judging by the proof of Theorem 2, it looks like the choice of $\lambda$ should depend on the curvature of $\hat\psi_n$ with respect to $\lambda$. Would it be possible to see experimental results using a grid of values of $\lambda$ for different problems?

2. Section 3.2 was more difficult to follow compared to other parts. I think it may help to start the section with concrete examples rather than with a general description. Also, it is said $\psi_0$ is random, but what is $\psi_0$ in this case? $\psi_0 = m^{-1} \sum_{j=1}^{m} h(W_j; \theta_0)$?

3. Figure 2 is not ideal for comparing the performances of different methods; the reader has to imagine putting one panel on top of another. Could you create a different visualization that highlights the differences more?

4. How do the methods compare in terms of computational cost?
limitations: The authors discuss some of the limitations of their work as a method but not the societal impact. Since this is a work in statistical methodology, I do not believe this is a defect.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: Authors propose a method for uncertainty estimation for predictive models. This method aims to directly compute uncertainty estimates for the cost function used to evaluate the predictive model. Main advantage of this method is that it avoids uncertainty quantification of the model parameters. This work provides consistency results in the large sample limit and it is empirically evaluated on different predictive tasks. 

strengths_and_weaknesses: Strengths:

- The approach provides an alternative approach for uncertainty quantification which circumvents the problem of computing uncertainty estimates over the model parameters. This could potentially be a very interesting research direction, because modelling parameter uncertainty has proven to be extremely challenging in many models, especially neural networks. 

 - The approach is theoretically motivated by some consistency guarantees in the large sample limit.

- Usually, uncertainty quantification is  computationally very expensive. The proposed method provides a much cheaper way to compute confidence intervals. 

- Although the approach builds on previously widely known results, it’s adaptation to more general and larger models is novel and interesting. 


Weaknesses:

- The only uncertainty that this approach is able to capture is the uncertainty around the exact location of the MLE estimate. In the case of a model with a highly multimodal loss landscape, the proposed method will be able to compute the uncertainty which belongs to a single mode. In models like NNs, it is widely known that capturing this kind of “local” uncertainty is much less powerful than capturing uncertainty involving multiple modes of the loss landscape, as it is done by ensemble of NNs or by powerful stochastic-gradient-Monte-Carlo methods: 

B. Lakshminarayanan, A. Pritzel, and C. Blundell, “Simple and scalable predictive uncertainty estimation using deep ensembles,” in Advances in neural information processing systems, 2017, pp. 6402–6413.

Wenzel, Florian, et al. "How good is the Bayes posterior in deep neural networks really?." arXiv preprint arXiv:2002.02405 (2020


*** Updated after discussion with authors ***
I have updated this part of the review after the discussion with other authors and reviewers. 
questions: Could you please provide empirical evidence comparing your approach to a (non-bootstrapped) ensemble of neural networks? 

Why don’t you also employ the Fashion-MNIST data set and a simple neural network like Lenet-5? If you want to focus on UCI-data sets, the set of selected data sets is very reduced. 

Which are the benefits of your approach against other approaches such as conformal predictions? This discussion should be added to the paper. 


limitations: I ask authors to discuss the problem of not capturing the multimodality of the log-likelihood function.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper focuses on estimating sampling uncertainty for typical machine learning models (M-estimators) with some evaluation function $\psi$ (e.g. the test loss). They do so by using the delta method to estimate the asymptotic variance of $\psi$. While this is not a new idea, the authors note that there are two downsides to the traditional use of the delta method: (1) if the model has parameters of dimension $D$, it requires the inversion of a $D \times D$ matrix, and (2) if $\psi$ is non-differentiable, then the delta method does not apply. The authors show that solving a regularized version of the M-estimator can get around both (1) and (2).
strengths_and_weaknesses: **Strengths**
1. Issues (1) and (2) I mentioned in the summary are really big problems with previous work in estimating uncertainty in large / complex machine learning models, and I think the authors make a pretty convincing case that they have solved these issues. I actually think the authors are underselling the "you don't have to invert a big Hessian matrix" thing. A number of people have tried to deal with this issue for related approximations (i.e. infinitesimal approximations involving the inverse Hessian) and been unsuccessful. Koh and Liang 2017 use a stochastic approximation to the inverse Hessian. But Stephenson et al. 2020 find it poor for their more quantitative purposes (I suspect the current authors would find it unusable for their implicit delta method as well) and propose a different approximation. But Frangella et al. 2021 then show that the approximation of Stephenson et al. 2020 is flawed and propose yet another approximation. Their analysis might be the final word in this chain, but who knows! So, it's really great to not have to deal with solving systems with large Hessians.
2. The writing quality in the paper is great (significantly above average of the typical NeurIPS submission).

**Weaknesses**

I think the current empirical evaluation needs to be significantly strengthened. I have a few points:
1. To me, the minimal thing the experimental section should show is whether or not the proposed method improves over baselines in some way. If someone asked me to point them to parts of this paper for concrete evidence why they shouldn't just always run the bootstrap or the standard delta method to estimate sampling uncertainty, I wouldn't know what parts to point them to. I would be surprised if the authors couldn't demonstrate that their IDM is faster than the bootstrap and, in high dimensions, the delta method. Or show a model on which IDM runs but the delta method does not due to lack of differentiability. But this needs to be actually shown (or, if this isn't true, then it should be investigated why a good-sounding idea doesn't work in practice).
2. I'm not sure what to take away from Fig 3; I can't tell from this figure whether IDM is doing something good or bad. First, why should we trust the bootstrap here (how do we know both the bootstrap and IDM aren't just terrible here -- could one argue that the dimension of the model is too high compared to the amount of training data for any asymptotic estimate of variance to have kicked in)? Second, assuming we do trust the bootstrap, why does this figure say that we should trust IDM? There are differences between IDM and the bootstrap. In what sense are these large or small? It's a little hard to tell, since $\psi$ doesn't relate to any particular downstream task. It might be more helpful if $\psi$ were something more meaningful. Also, how fast is IDM versus the bootstrap here? If IDM takes 500 years to run, I sure would rather run the bootstrap!
3. On the synthetic example: again, it's hard to tell if IDM is actually doing something sensible here -- is it closer (or reasonably close compared to other methods) to the true sampling uncertainty? Since you have access to ground truth here, this could be a great opportunity to give a much more quantitative assessment. 
4. Why are Gaussian processes included in the experiments? Bayesian methods don't measure sampling uncertainty, so what is being gained by comparing them to a method for approximating sampling uncertainty?

Overall, I think this could be a really great paper if the evaluation section were stronger. I would definitely raise my score and push for an accept if the authors can provide more compelling experiments that carefully investigate whether or not there are practically meaningful regimes in which their method is an improvement (e.g. is much faster without much loss in accuracy).

**Smaller comments**

- On line 242, [13] is cited as an example of approximating the bootstrap with similar infinitestimal approximations. I wouldn't cite this paper as an example of this, as it doesn't really work for the bootstrap. You might cite Giordano et al. 2019 instead (see their  Proposition 4 about the bootstrap).
- Line 225: I don't think you only need a small number of stochastic gradient steps; this should be true for pretty much any optimizer.
- Eq (5): I would think of the version of Eq (5) using the empirical estimate of the delta method estimator as more standard in practice. This also fits better with the following sentence which says Eq (5) won't work well if $\theta$ has many dimensions (if we're actually using the population version, then it won't work well in way more cases because $I$ is hard to compute!)
- Line 135 "it is still not clear how to do [the differentiation needed to compute the delta method] in practice". I think this is clear -- we can use the implicit function theorem, which is exactly what the proof of Theorem 1 is doing.
- I think the experiments in Fig 2 should be changed (see comments above), but at the very least the scale of the color bars should be the same so we can compare the different methods.


Z. Frangella, J. A. Tropp, and M. Udell. Randomized Nystrom Preconditioning. arXiv. 2021.

R. Giordano, M. I. Jordan and T. Broderick. A Higher-Order Swiss Army Infinitesimal Jackknife. arXiv. 2019.

P. W. Koh and P. Liang. Understanding Black-box Predictions via Influence Functions. ICML. 2017.

W. T. Stephenson, M. Udell, and T. Broderick. Approximate cross-validation with low-rank data in high dimensions. NeurIPS. 2020.
questions: - The discussion in Remark 1 seems to imply that the loss needs to be the log likelihood of some probability distribution (otherwise I'm not following why we care about $\sigma$). Why is this? It seems like a lot of the arguments in the paper go through as long as $\hat\theta_n$ is any M-estimator.

- In the statement of Theorem 4, $m$ has to satisfy $m \asymp n$ or $m \gg n$. Could this be more concisely stated as $m$ is $\Omega(n)$?

- Is Theorem 1 not just proving conditions under which $\hat V_n^{IIDM} = \hat V_n^{DeltaMethod}$? If true, this seems like a more precise statement of the theorem. 

- This is a much broader question. How do the authors think such local approximations should be used when the model objective is multimodal? Should we just be approximating around the discovered mode? Should we discover multiple local optima and then run this kind of approximation for each optimum? I don't think it's necessarily the current authors' job to solve such questions, but it could be worth commenting on in the paper if they have insights.


limitations: Yes, I think the authors have addressed the potential negative impact of their work.
review_title: null

Meta-review: metareview: The paper proposes an original new tool to access the uncertainty of a machine learning model. The authors agreed that it is a valuable contribution to our community and deserves acceptance. 

Importantly, all reviewers mention that there is room for improvement, both in the presentation containing ambiguities and in the empirical evaluation that needs strengthening. The authors properly acknowledge this in their rebuttal, and a consensus emerged from the discussion that those shortcomings are fixable.

Thus, I kindly ask the authors to carefully revise their paper for the camera ready by implementing all the changes they committed to and considering all reviewer's comments. This includes (but is not limited to):
- Make the paper more accessible for a broader ML audience by including more background, clarifying the scope of the paper in the abstract and introduction, and discussing what kind of uncertainty is studied throughout the paper;
- Adding the supplemental results reported during the authors-reviewers discussion;
- Report the accuracy of the method using synthetic data in which we can simulate the actual sampling uncertainty ([asked by Reviewer  41Kr](https://openreview.net/forum?id=etY_XXnPkoC&noteId=CLiYTiN03Ed))

confidence: Certain
Decision: Accept