The Discriminative Jackknife: Quantifying Uncertainty in Deep Learning via Higher-Order Influence Functions
Authors: Ahmed M. Alaa
Mihaela van der Schaar
Venue:  (2020)

Abstract: Deep learning models achieve high predictive accuracy in a broad spectrum of tasks, but rigorously quantifying their predictive uncertainty remains challenging. Usable estimates of predictive uncertainty should (1) cover the true prediction target with a high probability, and (2) discriminate between high- and low-confidence prediction instances. State-of-the-art methods for uncertainty quantification are based predominantly on Bayesian neural networks. However, Bayesian methods may fall short of (1) and (2) — i.e., Bayesian credible intervals do not guarantee frequentist coverage, and approximate posterior inference may undermine discriminative accuracy. To this end, this paper tackles the following question: can we devise an alternative frequentist approach for uncertainty quantification that satisfies (1) and (2)? 

To address this question, we develop the discriminative jackknife (DJ), a formal inference procedure that constructs predictive confidence intervals for a wide range of deep learning models, is easy to implement, and provides rigorous theoretical guarantees on (1) and (2). The DJ procedure uses higher-order influence functions (HOIFs) of the trained model parameters to construct a jackknife (leave-one-out) estimator of predictive confidence intervals. DJ computes HOIFs using a recursive formula that requires only oracle access to loss gradients and Hessian-vector products, hence it can be applied in a post-hoc fashion without compromising model accuracy or interfering with model training. Experiments demonstrate that DJ performs competitively compared to existing Bayesian and non-Bayesian baselines.

Under review as a conference paper at ICLR 2020
THE DISCRIMINATIVE JACKKNIFE: QUANTIFYING PREDICTIVE UNCERTAINTY VIA HIGHER-ORDER INFLUENCE FUNCTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Deep learning models achieve high predictive accuracy in broad spectrum of tasks, but rigorously quantifying their predictive uncertainty remains challenging. Usable estimates of predictive uncertainty should (1) cover the true prediction target with a high probability, and (2) discriminate between high- and low-confidence prediction instances. State-of-the-an methods for uncertainty quantification are based predom- inantly on Bayesian neural networks. However, Bayesian methods may fall short of (1) and (2)-i.e.. Bayesian credible intervals do not guarantee frequentist coverage, and approximate posterior inference may undermine discriminative accuracy. To this end, this paper tackles the following question: can we devise an alternative frequentist approach for uncertainty quantification that satisfies (1) and (2)
To address this question, we develop the discriminative jackknife (DJ), a formal in- ference procedure that constructs predictive confidence intervals for wide range of regression models, is easy to implement, and provides rigorous theoretical guaran- tees on (1) and (2). The DJ procedure uses higher-order influence functions (HOIFs) the trained model parameters to construct a jackknife (leave-one-out) estimator of predictive confidence intervals. DJ computes HOIF's using recursive formula that requires only oracle access to loss gradients and Hessian-vecte vector products, hence it can be applied in post-hoc fashion without compromising model accu- racy or interfering with model training. Experiments demonstrate that DJ performs competitively compared to existing Bayesian and -ayesiani baselines.
INTRODUCTION
Deep learning models have achieved state-of-the-art performance on variety of supervised learning tasks, and are becoming increasingly popular in various application domains (LeCun et al. (2015)). A key question often asked of such models is "Can we trust this particular model prediction ?" This question is highly relevant in high-stakes applications where the model is used to guide and inform critical decision-making - examples of such applications include: medical decision support, autonomous vehicle control, and financial forecasting (Amodei et al. (2016)). Despite their impressive predictive accuracy, rigorously quantifying the predictive uncertainty of deep learning models is challenging and yet an unresolved problem (Gal (2016); Ovadia et al. (2019)).
Actionable estimates of predictive uncertainty are ones that (1) cover the true prediction target with high probability, and (2) discriminate between high- and low-confidence predictions. (Figure I depicts a pictorial visualization for the coverage and discrimination requirements.) The first requirement, frequentist coverage, is especially relevant in applications where predictive uncertainty is incorporated decision-theoretic framework (e-g., administering medical treatments (Dusenberry et al. (2019)), or estimating value functions in model-free reinforcement learning (White & White (2010))). The second requirement, discrimination, is crucial for auditing model reliability (Schulam Saria (2019)), detecting dataset shifts and out-of-distee diito--distribution samples (Barber et al. (2019a)), and actively collecting new training examples for which the model is not confident (Cohn et al. (1996)).
Existing methods for uncertainty quantification based predominantly Bayesian neural networks (BNNs), whereby predictive uncertainty is evaluated via posterior credible intervals (Welling Teh (201) 1); Beráaddez-Lobate & Adams (2015); Ritter al. (2018); Maddox et al. (2019)). However,

---

Under review as a conference paper at ICLR 2020
Accurate coverage, no discrimination
No coverage, accurate discrimination
Accurate coverage and discrimination
Model Output
Model Output
Model Output
............"""""...............
Model Input
Model Input
Model Input
Figure I: Pictorial depiction for coverage and discrimination in uncertainty estimates. Red dots correspond training data and dotted black line corresponds to the target function. Confidence intervals are visualized as shaded blue regions, and dotted blue lines are the upper and lower confidence bounds. The left panel shows a confidence interval that perfectly covers the data points, but does not discriminate high-confidence predictions (regions with dense training data) and low-confidence ones (regions with scarce training data). The middle panel shows confidence interval with width proportional the density of training data, but does cover any data point. The right panel shows a confidence interval that satisfies both coverage discrimination requirements.
BNNs require significant modifications to the training procedure, and exact Bayesian inference is computationally prohibitive in practice. Approximate dropout-based inference schemes (e.g.. Monte Carlo dropout (Gal & Ghahramani (2016)) and variational dropout (Kingma et al. (2015))) have been recently proposed as computationally efficient alternatives. However, Bayesian inference in dropout-based models has been shown to be ill-posed, since the induced posterior distributions in such models do not concentrate asymptotically (Osband (2016); Hron et al. (2017)), which jeopardizes both the coverage and discrimination performance of the resulting credible intervals. Moreover, even with exact inference, Bayesian credible intervals generally do not guarantee frequentist coverage (Bayarri & Berger (2004)). Alternative non-Bayesian methods have been recently developed mostly based on ad-hoc ensemble approaches (Lakshminarayanal et al. (2017)) but formal frequentist methods with rigorous theoretical guarantees are still lacking.
Summary of Contributions. In this paper, we develop formal procedure for constructing frequen- tist (pointwise) confidence intervals on the predictions of broad class deep learning models. Our method which we call the discriminative jackknife (DJ) - is inspired by the classic jackknife leave-one-out (LOO) re-sampling procedure for estimating variability in statistical models (Miller (1974); Efron (1992)). In order to ensure both frequentist coverage and discrimination, DJ constructs feature-dependent confidence intervals using the LOO local prediction variance at the input feature, and adjusts the interval width (for given coverage probability) using the model's 's average LOO error residuals. Whereas the classic jackknife satisfies neither the coverage nor the discrimination require- ments (Barber et al. (2019h)), DJ provides strong theoretical guarantees both (i.e., DJ generates confidence intervals resembling those in the rightmost panel of Figure with high probability).
Central to the DJ procedure is the usage of influence functions fnfluencefuucctioss variational calculus (Efron (1992); Cook & Weisberg (1982); Hampel et al. (201 1)) - in order to estimate the parameters of models trained on LOO versions of the training data, without the need to exhaustively re-train the model for each held-out data point. That is, using the von Mises expansion (Fernholz (2012)) - a variant of Taylor series expansion for statistical functionals the fouttur-ffccuul) model parameters that would have been learned on LOO versions of the training dataset in terms of an infinite series of higher-order influence functions (HOIFs) for the model parameters trained on the complete dataset. We show that truncated von Mises expansion (with finite number of HOIFs) is sufficient to preserve the guarantees on coverage and discrimination. To enable efficient computation of the von Mises expansion, derive recursive formula that links HOIFss with lower-order influence functions and the partial derivatives of the model loss function.
key concept in robust statistics and
we represent
Comprehensive experimental evaluation demonstrates that the DJ procedure performs competitively compared to both Bayesian and non- -on-Baysiann methods. In particular, we found that the DJ procedure outperforms Bayesian neural networks with respect to discriminative performance, and provides better frequentist coverage compared to existing non- oa--aaysian methods, while being significantly less computationally expensive than both classes of methods.
2

---

Under review as a conference paper at ICLR 2020
2 PRELIMINARIES
Learning Setup. We consider a standard supervised learning setup with (ax y) being a feature-label pair, where the feature æ belongs to d-dimensional feature space X Rd. and y E R. A model is trained to predict using dataset D {( M4 M)) of n training examples which are drawn i from an unknown distribution P. Let the learning model be denoted as f( 0) : X - V where E θ are the model parameters, and θ is the parameter space. The learned model parameters E θ are obtained by solving the optimization problem Ô = arg minøge L(D, 8), with a loss function
(1) where we fold any regularization terms into {()). We do not pose any assumptions on how the loss function in (1) is optimized. The model [æ= 0) can be any neural network variant (e.g., ferdrforward, convolutional, etc). Throughout the paper, we limit our discussion to the regression task; extending our framework to classification tasks is an interesting direction for future work.
L(D,0) - -i=1 E(y.. (();;))),
Uncertainty Quantification. The predictions issued by the trained model (with learned parameters 0) given by (a;; 0). Our main goal is to obtain estimates for the uncertainty in the model predictions, expressed through pointwise confidence interval C(x; f) defined as follows:
C [ e [ f), fu (z: 0) fr (x; 8) < f(=; 0) < fu (z; 0), Vx E X.
(2)
The extent of uncertainty in the model's prediction (for data point with feature æ:) is quantified by the interval width W (-) of C(æ; 0). defined as W (C(:; 0)) A fu 0) (x; 0). Wider intervals imply less confidence, and vice versa. For C(x; 0) to be usable, has to satisfy the following requirements:
(i) Frequentist coverage: The confidence interval C(x;; 0) covers the true prediction target with an arbitrarily prespecified coverage probability of (1 aa), a E (0, i...
P {u E C(:; 0) 2 - o;
where the probability is taken with respect to (new) test point (x, y) as well as with respect to the training data D (Lawless & Fredette (2005); Barber et al. (2019b)).
(ii) Diserimination: The confidence interval C(æ;; 0) is wider (on average) for test points with less accurate predictions (Leonard et al. (1992)), i.e., for the test points x' E X, we have
(C 0)) 2 [[ 0))
ElC(y, f(x 2 B[els/ [(x'; 0)),
where the expectation [[]] is taken with respect to the training data D.
In the next Section, we develop a formal post-hoc procedure that takes the dataset D and the trained model (x:; 8) as inputs, and evaluates an uncertainty estimate C(x; 8) that satisfies both requirements.
3 THE DISCRIMINATIVE JACKKNIFE
Before presenting our proposed discriminative jackknife (DJ) procedure, we start with a brief recap of the classical jackknife. The jackknife quantifies predictive uncertainty in terms of the (average) prediction error, which is estimated with a leave-one-out (LOO) construction found by systematically leaving out each data point from the training dataset D, and evaluating the error of the re-trained model on the held-out sample. That is, for a target coverage of (1 a). a naïve jackknife estimates the uncertainty in the prediction for test point æ as (Miller (1974); Efron (1992)):
Ca,n (zx; 0) = fx; 0) + Qa.n
(ri....,Pn}
(3)
where r; = 1y - f( 0_.) is the error residual on the 7th data point, Ø_; are the parameters the model re-trained on the dataset D \ { vt)} with the tt point removed, and Q is the (1 a) quantile for the empirical distribution of elements of the set R = fri..... Fn defined as
Qan (R) A the [[1 a) (n + 1) smallest value of the elements of R. Note that, from the definition of Qa.n, it follows that Qa.n (R) = QQ--a.(-RR).
3

---

Under review as a conference paper at ICLR 2020
Albeit intuitive, the naive jackknife estimate in (3) is not guaranteed to achieve the target coverage of (1 ax) (Barber et al. (2019h)). More erucially, the interval width W na: 0)) is constant that does not depend on the feature æ, which renders discrimination impossible, i.c., when applied, the naive jackknife would result in confidence intervals resembling the leftmost panel in Figure
3.1 EXACT CONSTRUCTION OF THE DJ CONFIDENCE INTERVALS
We propose an ameliorated jackknife procedure, the DI, which addresses the shortcomings of the classical jackknife. We start by defining some notation. Let the sets Vi (a) and Vi (œ) be defined as:
V (a) (x) Vi, (x(x) 2 0}. and Vn (a) (x) Vi, (x(x) < }
(4)
where (x(x) f(x; f(x;; f..), n = | and n 1V Our DJ procedure estimates the predictive confidence interval for test point x: as follows: Ca,n (2;; 0) = [[n( 0), Ju (x; where
fr( 0) = f(x;0) 0) (on) - Q1-ann (V17 (az))
fu 0) = f(x:; 0) + Qan (Rn) Qannt (V (a))
(5)
Marginal Error
Local Variability
Unlike the traditional jackknife, the construction of the DJ confidence intervals comprises two terms: marginal prediction error and local prediction variability. The prediction error term, (...nRR,), uses the LOO residuals to estimate the model's (marginal) generalization error. The prediction variability
terms, Qo,tt (Vxt (x)) and Q Q (Vr (z)), quantify the extent to which each training data point impacts the value of the prediction at test point æ. The prediction error is constant, i.c., does not depend on æz hence only contributes to coverage but does not contribute to discrimination. On the contrary, the local variability terms depend on the test point feature hence they fully determine the discrimination performance. As we show later in Section 3.4, constructing confidence intervals this way provides strong theoretical guarantees on the achieved frequentist coverage and discrimination.
Figure illustrates the construction of the DJ confidence intervals in (5). The confidence intervals are chosen so that the boundaries of the aver- age error and local variability are exceeded by (nn + 1) aa) out of the n. LOO samples - these are marked with a star. For the average prediction error term, the width of the resulting boundary is the same for any test data point æ E X. For the local prediction variability term, the width of the boundary depends on the specific value of the feature ær and should get wider for less con- fident prediction instances.
Marginal prediction error
Local prediction variability
tri
Uy (ar
1:r2
(3))
(R.)))))))
- (V)()))
Qoiut (V (x))
Figure 2: Illustration the discriminative jackknife.
Based on the confidence intervals in (5), it follows that the DJ interval width is given by
W W(Ca,, (x:; 0)) 2 2... (R..) + Q1-ain (V. (a:) Q., (x)))
(6)
The marginal error and local variability terms in (6) jointly capture two types of uncertainty: epistemic and aleatoric uncertainties (Gal (2016). Epistemic uncertainty measures how well the model is matched to the data, and is reducible as the size of training data increases. On the contrary, aleatoric uncertainty is the irreducible uncertainty arising from the inherent sources of complexity in the data, such as label noise or hidden features (Malinin & Gales (2018)). Consistency of the DJ confidence estimates requires that W(Ca,n 8)) - 0, i.e., the interval width vanishes, the size of the training data increases (n + oo). It follows from (6) that there is no aleatoric uncertainty, and the underlying model is stable (i.e., lim, v, 0) and consistent (i.e., lim ri 0), then the interval width W (C...u (z:; 0)) vanishes n grows asymptotically (more training data is collected).
4

---

Under review as a conference paper at ICLR 2020
3.2 EFFICIENT IMPLEMENTATION VIA HIGHER-ORDER INFLUENCE FUNCTIONS
Exact computation of the DJ confidence intervals in (5) requires re- re-training the model times in order collect the "perturbed" LOO parameters {0-1}==1 To scale up the DJ procedure, we propose to use influence functions - a classic tool from robust statistics (Huber & Ronchetti (1981); Hampel et al. (2011)) in order to recover the parameters {0=;)==1 on the basis of the trained model fæ; 0). without the need for repeated re-training. Through our influence cunction-based implementation, the DJ can be applied in post-hoc fashion, requiring only knowledge of the model loss gradients.
Influence functions enable efficient computation of the effect of training data point (æ,, U:) on Ó. This is achieved by evaluating the change in i if (at,, V:)
up- weiihttt by some small c, resulting in new parameter 0z,- - arg mingge L(D, 0) + e Elys, (a,;; 0)). The rate of change in 0 due to an infinitesimal perturbation in data point is give by the (first-order) influence function, defined as
2 00.. de c=0
I (zi,
(xi, yc)
Note that the model parameter i is a statistical functional of the data distribution I.. Perturbing the tth training point is equivalent to perturbing TP to create a new distribution Pi, = (1 <) IP e (x; Bs), where A (xx U/) denotes the Dirac distribution in the point (æ;, 31). In this sense, the influence function in (7) operationalizes the concept of derivatives to statistical functionals, i.e., it quantifies the derivative of the learned model parameters 0 with respect to the data distribution P.
By recognizing that influence functions the "derivatives" of the model parameters â with respect to the data distribution P. we can use a Taylor-type expansion to represent the counter- counter-factual model parameter dr,. (that would have been learned from a dataset with the it data point up-weighted) in terms of the true model parameter 8 (learned from the true training dataset D) follows:
2² I (2) Mc) +
Ô - 0+ II, (I., vx) + 2
m!! (ax;, ykk .....
(m) (
(8)
where Zz/²( (x y:) is the 5thh order influence function, defined as I1/² (xx y:) 8 00.e/0 le=0- The expansion in (8), known as the von Mises expansion (Fernholz (2012)), , is a distributional analog of the Taylor expansion for a statistical functional. If all of the higher-order influence functions (HOIFs) in (8) exist, then we can recover 0z., without re-training the model on the perturbed training dataset. In Section 3.3, we will derive a recursive formula for efficiently computing the HOIFs in (8). Since exact reconstruction of d,e requires an infinite number of HOIFs, can only approximate θz., by including a sufficient number HOIF terms from the von Mises expansion. We discuss the impact of this approximation the coverage and discrimination performance of the DJ in Section 3.4.
Note that the LOO model parame- ters {0_ (required for the con- struction of the DJ confidence in- tervals) can be obtained by setting e = -1/n i.e., 0_, 0, =: since removing a training point is equiva- lent up-weighting by - 1/n n in the loss function L(D; 0). Thus, by setting e = -1/n and selecting prespecified number of HOIF terms m for obtaining the approximate LOO parameters ((T)) the DJ con- fidence intervals can be computed using the steps in Algorithm I.
Algorithm 1:
The Discriminative Jackknife
Input :Leaared parameter 0, influence order m, coverage o, training data D, test point æ
OppputtApproximatt confidence interval (l (a;
1: for i 1 to do
((m) + 0 > (n (n=*//k)) /kl) (2:, ri Y - f( ((m))
(x)x) + f(x; 8) f(x; g(mm))
4:
end
(z 0) f(æ; 0) (Rn) -uaan (VT(x))
(w; 0) <- (ax 0) + Qu, Q (Vt+tVV+ (x))
return: ((m)) (m:; 0) - [fr( 0), fo (m;
Esstmators that perturb parameters instead of a I.00 construct are known the infinitesimal jackknife (IJ) (Giordano et al. (2018)) A detailed technical background influence functions provided in Appendix
5

---

Under review as a conference paper at ICLR 2020
3.3 COMPUTING LIGHER-ORDER INFLUENCE FUNCTIONS
How can we compute the influence functions of the von Mises expansion in (8)? The recent work on model interpretability in (Koh & Liang (2017)) has studied the use of influence functions to quantify the impact of each training data point on model's 's predictions. In this work, first-order influence functions were computed using the classical result in (Cook & Weisberg (1982)) as follows:
I (z. v) Hg* Vo E(y. f(x 0)),
where Hg _ Vj (y. f(x, 0}) is the Hessian of the loss function, which is assumed to be positive definite. However, the expression in (9) is only limited to first-order influence functions. In the following Theorem', we derive a recursive formula for computing HOIFs of the model parameters O.
Theorem 1. Let f()) be a differentiable function with positive definite Hessian matrix Hg. If ((.) is locally convex in the neighborhood of 9, then the (k + 1-th order influence function of 0 exists for Z 1 we have
all (z., 8) E X x V. and for all k
If (x. H
Σ am" 9m ((I (x. v). V f(r, V) ((D m
)=
where Om is constant, and Im. is a polynomial function, Vm (1,...,m) m).
Similar expressions have been arrived at in (Giordano et al. (2019); Debruyne et al. (2008)). We give the precise definition of the constant term a.) and the function gm(()- in terms of Bell polynomials - in Appendix B. A key consequence of Theorem is that to compute all HOIFs, we need to evaluate the inverse of the Hessian matrix H only once, hence evaluating HOIFs scales linearly with the number of training examples. With automatic differentiation tools at our disposal (Paszke et al. (2017),, computing the loss gradients (arguments of gm (.)) can be done efficiently.
As it is the case in first-order influence functions, inverting He is the bottleneck operation in evaluating HOIFs, hence much of the machinery involved in (Koh & Liang (2017)) can be imported into our framework. With p parameters in 6, inverting H3 requires Onpp² + p²) operations, which can be cumbersome for deep learning models with large number of parameters. Following (Koh & Liang (2017)), we avoid explicitly computing He, and instead use implicit Hessian-vector products to efficiently approximate the Hessian products (9). For models with a very large p. we can use the stochastic estimation approach in (Agarwal et al. (2016)) to estimate Hg" with (p)) complexity.
3.4 THEORETICAL GUARANTEES
Now that we have developed a practical algorithm for implementing the DJ, we conclude this Section by revisiting the performance requirements in Section 2. In the following Theorem, we show that the approximate DJ confidence intervals satisfy the desired coverage and discrimination requirements.
Theorem 2. Let Cim) (x; 0) be the approximate DJ confidence interval evaluated with m HOIFss using Algorithm 1. Then, for any model (a: 0), the coverage rate achieved by the DJ is
lim P { Cim (1; 01} 2 1- a.
If the model is stable, i.e. P( (z 0) - f(x: 0-:) < s 8, Vi, for some E and 8 E (0, 1) (Bousquet& & Elisseeff (2002)), then Va, x' E X, v.y E v, and for a sufficiently large n, we have
TE[ W (Clo) 01)] 2 E[ (a': 0)) + B[ f(x;; 0)) 2 1
O
Theorem 2 provides a very strong guarantee on the frequentist coverage of the DJ confidence intervals. That is, without any assumptions, the exact DJ interval Caail (x; 0) has a worst case coverage that fulfills the target coverage rate of (1 a). (The approximate DJ intervals, (..)) (æ; 0). achieve the target coverage in the limit of m - oo.) In Section 5, we show through empirical evaluation that in practice - even with a finite number of HOIFs the DJ intervals will achieve the (1 a coverage. With further assumption on algorithmic stability (Bousquet & Elisseeff (2002)), Theorem states that if large number of HOIFs are involved in constructing the approximate DJ intervals, then the discrimination condition will be satisfied if we have a sufficiently large training sample.
All proofs are provided in the supplementary appendix.

---

Under review as a conference paper at ICLR 2020
4 RELATED WORK
The DJ is a post-hoc method that operates on deep learning models after being trained. Post-hoc methods are advantageous in that they neither compromise the model accuracy, nor require any modifications in model structure or training. (To implement Algorithm 1 (Section 3.3), we only need access to the model's loss gradients and Hessian-vest vector products.) It is worth noting that, while our primary motivation is to estimate uncertainty in deep learning models, our method is applicable to any machine learning model for which HOIF's are accessible. Additionally, the exact DJ procedure be applied to any model via exhaustive leave-one-out re-training, even when gradients are inaccessible.
Post-hoc methods have been traditionally underexplored since existing approaches, such as calibration via temperature scaling (Platt et al. (1999)), are known to under-perform compared to built-in methods (Ovadia al. (2019)). However, recent works have revived post-hoc approaches using ideas based on bootstrapping (Schulam & Saria (2019)), jackknife resampling (Barber et al. (2019b); Giordano et al. (2018)) and cross- volos-valiationn (Vovk et al. (2018); Barber al. (2019a)). An overview of the different classes of post-hoc and built-in methods proposed in recent literature is provided in Table 1.
Table I: Overview of existing methods for uncertainty quantification in deep learning.
Bayesian vs.
Post-hoc vs. Built-in
Method
Coverage
Frequentist
Bayesian neural nets (Ritter et al. (2018))
Bayesian
Built-in
No guarantees
Probabilistic backprop. (Blundell et al. (2015))
Bayesian
Built-in
No guarantees
Monte Carlo dropout (Gal & Ghahramani (2016))
Bayesian
Built-in
No guarantees
Deep ensembles (Lakshminarayaman et al. (2017))
Frequentist
Built-in
No guarantees
Resampling uncertainty (Schulam & Saria (2019))
Frequentist
Post-hoe
No guarantees
Cross-conformal (Vovk et al. (2018))
Frequentist
Post-hoe
1 2a
Jackknife+ (Barber et al. (2019b))
Frequentist
Post-hoc
1 2a
Jackknife-minmax (Barber el al. (2019b))
Frequentist
Post-hoc
a
As discussed earlier, Bayesianism has been the dominant approach to uncertainty quantification in deep learning ( (Welling & Teh (201 I); Hernández- Lobato & Adams (2015); Ritter et al. (2018); Maddox et al. (2019)). By their very nature, Bayesian models cannot be applied in a post-hoc fashion since they require specifying priors over model parameters, which leads to major modifications in the inference algorithms. While Bayesian models provide a formal framework for uncertainty estimation. posterior credible intervals do not guarantee frequentist coverage, and more crucially, the achieved coverage can be very sensitive to hyper-paramett Bayesian inference is often computationally prohibitive, and alternative approximations e.g., (Gal & Ghahramani (2016)) and (Kingma et al. (2015))) - may induced posterior distributions that do not concentrate asymptotically (Osband (2016); Hron et al. (2017)).
tuning (Bayarri Berger (2004)). Moreover, exact
Deep ensembles (Lakshminarayanan et al. (2017)) are currently considered the most competitive (non- Bayesian) benchmark for uncertainty quantification (Ovadia et al. (2019)). This method repeatedly re- trains the model on sub-samples of the data (using adversarial training), and then estimates uncertainty through the variance of the aggregate predictions. A similar bootstrapping approach, developed in (Schulam & Saria (2019)) uses the model's Hessian and loss gradients to create an ensemble without re-training. While these methods may perform favorably in terms of discrimination, they are likely to undercover, since they only consider local variability terms akin to those in (5). Additionally, ensemble methods do not provide theoretical guarantees on coverage and discrimination.
The (infinitesimal) jackknife method was previously applied for quantifying the predictive uncertainty in random forest models (Wager al. (2014); Mentch & Hooker (2016): Wager & Athey (2018)). In these works, however, the developed jackknife estimators are bespokely tailored to bagging predictors, and cannot be straightforwardly extended to deep neural networks. More recently, general-purposs jackknife estimators were developed in (Barber et al. (2019b)), where two exhaustive leave-one- out procedures: the jackknife+ and the jackknife-minmax where shown to have assumption-free worst-case coverage guarantees of (1 2a)) and (1 a)., respectively. Our work improves on these results in two ways. First, the DJ achieves the target coverage rate of (1 - a) with a strictly (proof is provided in Appendix D).
narrower interval width compared to the mackknife-minma Second, our proposed HOIF-based implementation of the jackknife alleviates the need for exhaustive leave-one-our re-training, which enables scaling up any jackknife-basseeeeeee based method to large datasets.
7

---

Under review as a conference paper at ICLR 2020
PBP
MCDP
BNN-SGLD
DE
100
50
0
0
-50
-50
-50
-50
1100
-100
-100
-100
-5
-5
RUE
CCP
DJ [m=1)
DJ (m=2)
100
100
50
50
50
0-
0-
0-
-50
-50
-50
50
-100
-100
-100
-100
5
-5
-5
Figure 3: Uncertainty estimates by baselines on the synthetic dataset. Training data shown as red dots and the true function is displayed as a black dotted line. Confidence intervals are shown as a shaded blue region.
5 EXPERIMENTS
Our DJ procedure (Algorithm 1) was implemented on top of PyTorch models, where computed the loss gradients and Hessian required for evaluating the HOIFs a model's parameters (Theorem 1) using aut ograd (Maclaurin al. (2015)). The only hyper-parameter involved in method is the number of HOIFs m - this was tuned by optimizing the evaluation metrics (listed below) on the training samples. Code snippets for the DJ procedure are provided in the supplementary appendix.
Baselines. We compared our DJ procedure with 6 state-of-the-art baseline methods. These included 3 built-in Bayesian methods: (1) Monte Carlo Dropout (MCDP) (Gal & Ghahramani (2016)), (2) Probabilistic backpropagation (PBP) (Hernández-Lobato & Adams (2015)), and (3) Bayesian neural networks with inference via stochastic gradient Langevin dynamics (BNN- -GND)) (Welling Teh ())11)). In addition, we considered deep ensembles (DE) (Lakshminarayanan et al. (2017)), which is deemed the most competitive built-in frequentist method (Ovadia al. (2019)). We also included post-hoe methods: resampling uncertainty estimation (RUE) (Schulam & Saria (2019)) and cross- conformal predictive distributions (CCP) (Vovk et al. (2018)). For a target coverage of (1 a). uncertainty estimates were obtained by setting the posterior quantile functions to (1-a) (for Bayesian methods), or obtaining the (1 a) percentile point of a normal distribution (for frequentist methods). We implemented all baselines in PyTorch (details provided in the supplementary appendix).
Evaluation metrics. In all experiments, we used the for the trained model fx; 9). To ensure a fair comparison, the hyper-parameters of the model f(æ;; 0) were the same for all baselines. In each experiment, an uncertainty estimate Čo,.. (x; 0) is obtained from training sample, and then coverage and discrimination are evaluated on a test sample. To evaluate empirical coverage probability, we compute the fraction of test samples for which y resides in C.,n (z; 0). Discrimination was evaluated as follows. For each baseline method, we evaluate the interval width W (C.,,. (2; 0)) for all test points. For a given error threshold E, we use the interval width to detect whether the test prediction f(: f) is high-confidence, i.e., E(y, f=; 0)) < &, or low-confidence prediction, i.e., E(y, f (a:; 0)) > E. We use the area under the ROC curve (AUC-ROC) to evaluate the accuracy of classifying high- and low-confidence predictions using W W(Ca,n (x;; 0)).
squared error (MSE) the loss T.(D,
5.1 SYNTHETIC DATA
Qualitative assessment. First, we qualitatively assess the DJ confidence intervals using the synthetic data model in (Hernández--Lobtto & Adams (2015)). This dataset is based the one-dimensional model: y = x + c, where e ~ 30)3).. We fit a fced-forward neural network model (with the Hemmández-Lobtto & Adams (2015))) 50 training examples drawn from
same architecture uniform distribution on X' [44, 4). and evaluate confidence intervals on its predictions with a target coverage of 90%. The confidence intervals constructed by all baselines visualized in Figure 3.
8

---

Under review as a conference paper at ICLR 2020
As can see in Figure Bayesian methods tend undercover the target function - i..., PBP overestimated model confidence, whereas BNN-SGLD failed to recognize that the region x > 4 should be assigned higher uncertainty since it contains no training data. For MCDP,
that higher uncertainty is assigned to the region |x] > 4, but the posterior does not concentrate around the training data, and hence credible intervals
poorly calibrated. Post-hoc methods (RUE and CCP) tend to overestimate confidence in regions with dense training data (/æl S. 4) since they rely mainly on the (in-sample) errоr variance estimate uncertainty. DE produces favorable confidence interval, but with little variation in interval width and with few training points being uncovered.
The DJ confidence intervals hit the right balance between coverage and discrimination. The addition of the marginal error 10. (Ree) in (5) ensures that the training data points and target function are covered everywhere in X. The variability terms, 1..1..2(V55 (V5)) and 9 (VVo)) ) add the discrimination components, which enable the interval width clearly distinguish high-confidence regions (aal S 4)
from low-confidence ones (|x) > 4). By contrasting the DJ estimates with m = and m 2, we see that adding more HOIF terms gives smoother and tighter confidence intervals.
Couenge rar
0.2
Auc-Boc
0.6
0.8
100
120
0.1
RUE
ENN--GLD
0.0
RUE
40
PSP
P37
0.0
DE
DE
40
80
Figure Coverage discrimination performance all baselines on high-dimensional synthetic data.
Quantitative assessment. Next, examine coverage and discrimination performance of all base- lines on the following synthetic model. For n = 100 and - a 0.9, we conduct 100 experiments, each for different feature dimensions 1, 11, ......, 101, with i..dd samples (æ,, y1) generated as ..... Uniform @d az ~ NN Ia), and yı æ. i, ~ ~N( ((TT))),1)
In each experiment, we fit 2-layer neural network with 100 hidden units to the training data, and then generate 100 test data points from the same distribution to evaluate the coverage and discrimination performance for different values of d. (Discrimination is evaluated by setting the error threshold & to be the 95% percentile of the trained model error on the test samples.) As we can see in Figure 4, DJ the only method that always manages to achieve the 90% coverage rate for any number of features d (as predicted by Theorem 2). It does so while also achieving the most competitive discrimination (AUC-ROC) performance, together with the RUE and PBP baselines. We also found that, for all values of d, the DJ interval width was strictly tighter than that of the jackknife-minmax (JM) procedure (Barber et al. (2019b)), which is the only other procedure that guarantees the a target coverage.
In this experiment, found that mance by DJ. More HOIFs would generally be needed for more complex networks, with more layers or hidden units (see further results in the supplementary appendix). Because of its post-hoc nature, the computational complexity of DJ was significantly less than built-in method (average runtime of DJ 50 times faster than DE, 30 times faster than BNN-SGLD and 10 times faster than PBP).
2 HOIFs are sufficient for achieving the best possible perfor-
5.2 REAL DATA: AUDITING MODEL RELIABILITY
We conducted series of experiments on real-world datasets in order to evaluate the accuracy of uncertainty estimates issued by the DJ procedure in various contexts. In this Section, we show how uncertainty estimates can be used to audit the reliability of predictive model. Further experiments on active learning and out-of- -iitt--diittibution detection are deferred to the supplementary appendix.
In this experiment, compare how well DJ and the competing baselines are able detect when model's 's prediction will far from the true target value. We conduct our experiments on common UCI benchmark datasets for regression strength, energy efficiency, robot kinematics (Kin8nm), naval propulsion, combined cycle power plant, red wine quality, and yacht hydrodynamics (Dua & Graff (2017)).
those included: Boston housing, concrete compression

---

Under review as a conference paper at ICLR 2020
Dataset
Method
Housing
Concrete
Energy
Kin8nm
Naval
Power
Wine
Yacht
DJ
0,93 0.01
0.55 + 0.01
0.92 0.01
0.71 1: 0.01
0.89 i 0.01
0.58 1: 0.02
0.69 1 0.01
0.92 1: 0.01 (100%))
(n
10)
(92.61%)*
(96.12%))
(99.40%)
(95.5%%))
(98.91%)*
(95.36%))
(94.87%)*
DJ
0.90 + 0.01 (93.52%)*
0.54 0.012 (97.22%)*
0.92 0.01
0.66 0.01
0.85 0.01
0.53 + 0.01 (95.21%))*
0.69 + 0.01 (92.71%)*
0.90 + 0.01 (100%))
(m
1)
(94.66%))
(91.32%))
(97.22%)*
RUE
0.88 0.02
0.51 + 0.01
0.90 0.01
0.71 0.01
0.89 0.02
0.52 + 0.03
0.69 + 0.02 (80.76%)
0.90 + 0.01
(64.77%)
(78.17%)
(97.30%))
(61.08%)
(52.21%)
(82.85%)
(100%))
MCDP
0.70 :: 0.01
0.62 0.03
0.58 0.00
0.62 0.01
0.51 +: 0.04
0.50 +: 0.00
+
(85.55%)
(55.15%)
(0.0%)
(81.15%)
(65.22%)
(50.15%)
(0.0%)
(0%)
PBP
0.51 0.01
+:
0.51 0:03
0.58 0.03
0.51 0.01
0.50 d: 0.02
0.80 =: (89.98%)
+
(8.86%)
(2.58%)
(1.49%)
(19.78%))*
(97.87%))
(40.23%)
(12.82%)
DE
0.89 0.02
0.77 + 0.01
0.88 0.03
0.58 0.02
0.68 0.02
0.50 4: 0.01
0.55 + 0.01
0.52 + 0.03
(84.48%)
(77.52%)
(76.79%)
(54.77%)
(81.48%)
(97.36%))
(42.18%)
(52.98%)
BNN
0.80 0.01
0.79 + 0.02 (100%))
0.62 0.01 (100%))
0.63 0.00
0.55 0.01
0.50 +: 0.01
0.50 + 0.00 (84.43%)
0.59 = 0.01
(88.67%)
(94.21%))
(64.21%)
(62.13%)
(83.44%)
CCP
0.51 0.01
0.57 + 0.01
0.63 0.01
0.52 0.01
0.50 + 0.01
0.50 + 0.01
0.57 + 0.02 (88.46%)
0.74 - 0.01 (80.79%)
(87.43%)
(78.17%)
(85,32%)
(86.61%)
(87.72%)
(87.67%
Table 2: AUC-ROC performance (1L: 95% confidence intervals) of baselines on the real-world UCI regression datasets. Numbers between brackets are the achieved (empirical) coverage rates. Bold numbers correspond to the best performing method. Coverage rates marked with an asterisk achieve the 90% target rate.
For each dataset, we sample 20 train-test splits, and use 90% of the data points for training. To control for model complexity. we fix a single beed-forward neural network architecture with two hidden layers and 100 hidden units, logistic activation functions, MSE loss, and a single set of learning hyper-parameters (500 epochs with 100 samples per minibatch, and an Adam optimizer with default settings). We fit single model for each split of each dataset, and compute the confidence intervals (with 1 - 0.9) for all baselines the test data. We implemented two versions of our method: DJ with a first-order von Mises approximation (m = 1), and a DJ with m = 10 HOIFs. Similar to the previous experiment, we evaluate the empirical coverage rate and discrimination (AUC-ROC) performance assuming the threshold & to be the 95% percentile of the empirical distribution over test errors. Results are provided in Table 2.
We observe that, in terms of discriminative performance, DJ outperforms (or is competitive with) the baselines- the AUC-ROC of detecting low-quality predictions by DJ was better than other methods in 6 out of the 8 datasets. Including HOIFs was important for achieving good performance in most datasets. A first-order von Mises approximation was sufficient only in the "Energy" dataset, but under-performed compared to the DJ with m = 10 in all other datasets. Another key observation that - as predicted by Theorem 2 - the DJ procedure always achieves the 90% target coverage rate. All other methods tend to undercover the test points, and some methods (such as MCDP and PBP) can even achieve close to zero coverage. It worth mentioning that on the dataset where DJ provided the biggest improvement in discriminative performance (Boston housing), it was also the only method that achieved the target coverage.
CONCLUSION
Uncertainty quantification is a crucial requirement in various high-stakes applications where deep learning can inform critical decision-makinn procedure for quantifying the uncertainty in predictions issued by deep learning models in a post-hoc fashion. Our procedure, which is inspired by classical jackknife estimators, does not require any mod- ifications in the underlying deep learning model, and provides theoretical guarantees on its achieved performance. Implementation of our procedure using higher-order influence functions entails minimal computational costs, and allows our method to scale for big datasets, without the need for repeated re- training as in the classical jackknife procedure. While this paper focuses on uncertainty estimation in deep learning, the methods therein can be applied to any machine learning model as long as we are granted access to its loss gradients and Hessian.
In this paper, we developed a rigorous frequentist
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimization in linear time. stat, 1050:15, 2016.
Ahmed M Alaa and Mihaela der Schaar. Bayesian inference of individualized treatment effects using multi-task gaussian processes. In Advances in Neural Information Processing Systems, pp. 3424-3432, 2017.
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in ai safety. arXiv preprint arXiv:1606.0663 2016.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshiianni. Conformal prediction under covariate shift. arXiv preprint
2019a.
Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+. arXiv preprint arXiv: arXiv: 1905.02928, 2019b.
M Jésus Bayarri and James O Berger. The interplay of bayesian and frequentist analysis. Statistical Science, pp. 58-80, 2004.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural networks. arXiv preprint arXivv1505.05424 2015.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499-526, 2002.
David A Cohn, Zoubin Ghahramani, and Michael Jordan. Active learning with statistical models. Journal of artificial intelligence research, 4:129-145, 1996.
Dennis Cook and Sanford Weisberg. Residuals and influence in regression. New York: Chapman and Hall, 1982.
Michiel Debruyne, Mia Hubert, and Johan AK Suykens. Model selection in kernel based regression using the influence function. Journal of Machine Learning Research, (0ct))2377,0 2008.
Luc Devroye and Terry Wagner. Distribation-free inequalities for the deleted and holdout error estimates. IEEE Transactions on Information Theory, 25(2):202-207, 1979.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL htttt://rrc/iive ics. uci. www..ed/mii.i
Michael W Dusenberry, Dustin Tran, Edward Choi, Jonas Kemp, Jeremy Nixon, Ghassen Jerfel, Katherine Heller, and Andrew M Dai. Analyzing the role of model uncertainty for electronic health records. arXiv preprint arXiv: 2019.
Bradley Efron. Jackknife-after-bbosstta standard errors and influence functions. Journal of the Royal Statistical Society: Series B (Methodological), 83311111 1992.
Luisa Turrin Fernholz. Von Mises calculus for statistical functiooaal,,, volume 19. Springer Science & Business Media, 2012.
Yarin Gal. Uncertainty in deep learning. PhD thesis, PhD thesis, University of Cambridge, 2016.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In International Conference Machine Learning (ICML), pp. 1050-1059, 2016.
Ryan Giordano, Will Stephenson, Runjing Liu, Michael I Jordan, and Tamara Broderick. A swiss army infinitesimal jackknife. arXiv preprint arXiv:1806 186.051800000550, 2018.
Ryan Giordano, Michael I Jordan, and Tamara Broderick. A higher-order swiss army infinitesimal jackknife. arXiv preprint arXiv: 121907/111000 16,11,111111 2019.
Frank R Hampel, Elvezio M Ronchetti, Peter J Rousseeuw, and Werner A Stahel. Robust statistics: the approach based influence functions, volume 196. John Wiley & Sons, 2011.
11

---

Under review as a conference paper at ICLR 2020
José Miguel Hemández--Lbaat and Ryan Adams. Probabilistic backpropagation for scalable learning of bayesian neural networks. In International Conference on Machine Learning (ICML), pp- 1861-1869, 2015.
Jiri Hron, Alexander de G Matthews, and Zoubin Ghahramani. Variational gaussian dropout bayesian. arXiv preprint arXiv: 1XXiv:771..02880 2017.
Peter Huber and Elvezio M Ronchetti. Robust statistics john wiley & sons. New York, 1(1), 1981.
Durk P Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparameteriizatoon
trick. In Advances Neural Information Processing Systems, pp. 2575-2583 2015.
Pang Wei Koh and Percy Liang. Understanding black-bor predictions via influence functions. In Proceedings of the 34th International Conference on Machine Ceaannnn-Vollume 70, pp. 1885-1894.
JMLR. org, 2017.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems (NeurIPS), pp. 6402-6413, 2017.
JF Lawless and Mare Fredette. Frequentist prediction intervals and predictive distributions. Biometrika, 9233)522--542, 2005.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436, 2015.
JA Leonard, Mark A Kramer, and LH Ungar. neural network architecture that computes its own reliability, Computers & chemical engineering, (699):819-835, 1992.
Wen-Xiu Ma. Bilinear equations, bell polynomials and linear superposition principle, In Journal of Physics: Conference Series, volume 411, pp. 012021. IOP Publishing, 2013.
Dougal Maclaurin, David Duvenaud, and Ryan P Adams. Autograd: Effortless gradients in numpy. In ICML 2015 AutoML. Workshop, volume 238, 2015.
Wesley Maddox, Timur Garipov, Pavel Izmailov, Dmitry Vetrov, and Andrew Gordon Wilson A simple baseline for bayesian uncertainty in deep learning. arXiv preprint arXiv:1902.024 2019.
Andrey Malinin and Mark Gales. Predictive uncertainty estimation via prior networks. In Advances in Neural Information Processing Systems, pp. 7047-7058, 2018.
Lueas Mentch and Giles Hooker. Quantifying uncertainty in random forests via confidence intervals and hypothesis tests. The Journal of Machine Learning Research (JMLR), 17(1):841-88) 2016.
Rupert G Miller. The jackknife-a review. Biometrika, 61(1):1-15, 1974.
Ian Osband. Risk versus uncertainty in deep learning: Bayes, bootstrap and the dangers of dropout. In NIPS Workshop on Bayesian Deep Learning, 2016.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, D Sculley, Sebastian Nowozin, Joshua V Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. arXiv preprint arXiv:/906.000 020300 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
John Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances large margin classifiers, 10(3):61-7,, 1999.
Hippolyt Ritter, Aleksandar Botev, and David Barber. scalable laplace approximation for neural networks. 2018.
Peter Schulam and Suchi Saria. Can you trust this prediction? auditing pointwise reliability after learning. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1022-1031, 2019.
12

---

Under review as a conference paper at ICLR 2020
Vladimir Vovk, Ili Nouretdinov, Valery Manokhin, and Alexander Gammerman. Cross-conformal predictive distributions. The Journal of Machine Learning Research (JMLR), pp. 37-51, 2018.
Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 1136523):1288-2444 2018.
Stefan Wager, Trevor Hastie, and Bradley Efron. Confidence intervals for random forests: The jackknife and the infinitesimal jackknife. The Journal of Machine Learning Research (JMLR), 15 (1):1625-1651, 2014.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference machine learning (ICML-II), pp. 681-688, 2011.
Martha White and Adam White. Interval estimation for reinforcement-earriig algorithms in continuous-state domains. In Advances in Neural Information Processing Systems, pp. 2433- 2441, 2010.
13

---

Under review as a conference paper at ICLR 2020
A INFLUENCE FUNCTIONS:
BACKGROUND & KEY CONCEPTS
A.1 FORMAL DEFINITION
Robust statistics is the branch of statistics concerned with the detection of outlying observations. An estimator is deemed robust if it produces similar results as the majority of observations indicates, regardless of how minority of other observations is perturbed (Huber & Ronchetti (1981)). The influence function measures these effects in statistical functionals by analyzing the behavior of functional not only at the distribution of interest, but also in an entire neighborhood of distributions around it Lack of model robustness is clear indicator of model uncertainty, and hence influence functions arise naturally in our method as a (pointwise) surrogate measure of model uncertainty. In this section formally define influence functions and discuss its properties.
The pioneering works in (Hampel et al. (2011)) and (Huber & Ronchetti (1981)) coined the notion of influence functions to assess the robustness of statistical functionals perturbations in the underlying distributions. Consider a statistical functional T P - R. defined on probability space P, and a probability distribution IP P. Consider distributions of the form Pe.- (1 e)P + = where A denotes the Dirac distribution in the point & = (z, y), representing the contaminated part of the data. For the functional T be considered robust, (TP should not be too far away from T(P)) for any possible and any small e. The limiting case of - O defines the influence function. That is, Then the influence function of T at IP in the point is defined as
T(P
:)) - T(P)
a Oe
[(2; P)
lim 6-0
T(P
(A.1)
c==
The influence function measures the robustness of 'T by quantifying the effect the estimator T when adding an infinitesimally small amount of contamination at the point 2. If the supremum of Z(.) over is bounded, then an infinitesimally small amount of perturbation cannot cause arbitrary large changes in the estimate. Then small amounts of perturbation cannot completely change the estimate which ensures the robustness of the estimator.
A.2 THE VON MISES EXPANSION
The von Mises expansion is distributional analog of the Taylor expansion applied for functional instead of a function. For two distributions and Q. the Von Mises expansion is (Fernholz (2012)):
T(Q)= = T(P)) + ((
(2;) d(Q - PP)
(A.2)
where (2; is the 3Mth order influence function. By setting Q to be perturbed version of IP, i.e.
Pe, the von Mises expansion at point reduces to:
22 T(P..z) = T(P) + (2; + 7 (2; + +...,
(A.3)
and so the kth order influence function is operationalized through the derivative
(2:
T(P
(A.4)
A.3 INFLUENCE FUNCTION OF MODEL LOSS
Now we apply the mathematical definitions in Sections A. and A.2 to our learning setup. In our setting, the functional T(.) corresponds to the (trained) model parameters i and the distribution P. In this case, influence functions of 0 computes how much the model parameters would change if the underlying data distribution was perturbed infinitesimally.
0.... ae
(2)
(zz;0) + ((;;))) Ōe.2 arg min DE0
(A.5)
1=1
Recall that in the definition of the influence function Pe.. = (1- 2)P + = where Az denotes the Dirac distribution in the point (2x, Thus, the (first-order) influence function in (A.5)
14

---

Under review as a conference paper at ICLR 2020
corresponds to perturbing training data point by infinitesimally small change and evaluating the corresponding change in the learned model parameters 0. More generally, the 1 order influence function of Ô is defined follows:
2 0z.z
RR) (2) (2)
(A.6)
1==0
By applying the von Mises expansion, we can approximate the parameter of a model trained on the training dataset with perturbed data point z as follows:
t..- = + 1 (2)
2
e (z):
I/ml [=)
(A.7)
m!
where m is the number of terms included in the truncated expansion. When m = oc, the exact parameter fe,= without the need to re-train the model.
A.4 CONNECTION TO LEAVE-ONE-OUT ESTIMATORS
Our uncertainty estimator depends on perturbing the model parameters by removing single training point at a time. Note that removing point is the same perturbing by g -1 hence we obtain an (m order) approximation of the parameter change due to removing the point follows:
Ô_ 0 1
2n 1 (2)
(2)
+
71th m!! I (m) (z),
(-1)
(A.8)
n
where 0_ is the model parameter learned by removing the data point from the training data.
B PROOF OF THEOREM
Recall that the LOO parameter ôr,c is obtained by solving the optimization problem:
fie arg min L(D, + e- Elys. ((xx;)))
(B.1)
Let us first derive the first order influence function ((1) (zi, (x;, y:). Let us first define A.,. - 0r,c 0. The first order influence function is given by:
I v:) 00,r ab.,
(B.2)
de de
Note that, since 8. is the minimizer of (B.1), then the perturbed loss has to satisfy the following (first order) optimality condition:
Vo (L + E(ys, f(x;;))) la-a.- 0.
(B.3)
Since lim,-1o d.. = 8, then we can write the following Taylor expansion:
v (L(D,) + Elyi ((:;;; 0)); O.
(B.4)
k!
k=0
Now by dropping the o(IlA terms, we have: v. (( (T(
fyy, (m; A... Vo (T(D, + Ely,, smn 0113) (B.5)
Since is a indeed minimizer of the loss function {(.), then we have Vol(.) = 0. Thus, (B.5) reduces the following condition:
{cr V Elv,, f(z;;;)) 0)) Di. - (V3 L(D,0) +e. e v E(v.. f(x;;))) 0.
(B.6)
By solving for Vo. we have
A.. = v/ L(D,0) +e
V E(yn, ((x;; 0113 {c: Vo Elys, (ax;; 01)}
(B.7)
15

---

Under review as a conference paper at ICLR 2020
which can be approximated by keeping only the O(e) terms follows:
i - [ L(D,0)} - {e- Vo E(vi f(z;; 01))
(B.8)
Noting that V L(D, 8) is the Hessian matrix Hg. we have:
A = H1 {c Vo l(vi, (a 0
(B.9)
By taking the derivative with respect to e, we arrive at the expression for first order influence functions:
7 (a yi)
- Vo Llyi, f(x;;))))
(B.10)
Now let us examine the second order influence functions. In order to obtain (x;;, V1), need to differentiate (B.6) after omitting the Occ) once again as follows:
22 e. V E(y:, f(x;;))) + { v2 L(D,0) + Aie L(D, = 0. (B.11)
Where we have applied the chain rule to obtain the above. By substituting Va L(D, 0) Ho and dividing both sides of (B.11) by e², we have
{2 Aic V3 elv. f(xn {
A 2
(Aie)
v L =0. =0. (B.12)
Ha +
Thus, by re-arranging (B.11), we can obtain
I(2) (2, in terms of (1)) (2 11) as follows:
I (z,,)) 'Ho' (II")))))) v L(D,0) + +2I vi) v Ely, f(x;;6))
Similarly, we can obtain the th order influence function, for any lo > 1, by repeatedly differentiating equation (B.6) & times, i.e.,
① Oek {o. Vo Elyi, f(x;;; 0)) + Di. V L(D.0) -0
(B.13)
and solving for /Oct By applying the higher-order chain rule the two added terms in (B.13) (or equivalently, take the derivative of (2)) (x; yi) for i - 2 times), we can represent the formula for (k) (æ,, v1) using Bell polynomials (Ma (2013)) as follows:
I I(++1)(x
(x. v) - -Hø"
Σ m=1
Bm,k+1 (f (f (z.
v). V/ ely, f(e m }_m))
+
& Binkk (fI(" V L(D,
Σ
(B.14)
j=1
where Bin is the Bell polynomial, which is defined as follows:
Bm, I2..... ... Zm k+1)
Σ jrlje! Im k+1!
m!
mm
fm-k+1
1!
2!
(m k 1)!
16

---

Under review as a conference paper at ICLR 2020
C PROOF OF THEOREM 2
We start by proving the coverage guarantee in Section C. and then prove the discrimination guarantee Section C.2.
C.I FREQUENTIST COVERAGE
In what follows, we analyze the coverage probability of the exact DJ confidence intervals. The proof parallels that of (Barber et al. (2019b)). Recall that the empirical (1 a) quantile is defined by:
(1 ..., ..,)) = the [[1 - a:) (n + 1)]-th smallest value of {X1, X
Let the test point be (1 1 1n+1) and suppose we have oracle access to the true test label Vn+1- For any two distinct indices i.j E fl, n + 1} with * j, let f-(i.)) be the model fitted on the augmented dataset (()) U [( Mn+1)], i.e., training and test data, with points i and removed. Note that f f-(1)) = ((.0) (1,0) for any i * j. and that f (f,n+1) = f-; for any = =1 1.......
Next, we define matrix K [=(++1)((++1) with entries K [Ka defined as follows:
{ 00,
i == J. i i
Kig - 1y5 (a))
(C.1)
where the off-diagonal entries represent the residual for the ith point when both and j are left out of model training, addition to the difference between the model predictions when trained on the entire training dataset and when point is left out. Let the set Q be defined as:
(
iEel In
Q(K)
[I(KA<K)) 2 (1-a) (n)
(C.2)
==1
where K = Qa.n ( (1))) Before proceeding, we first prove the following Lemma.
Lemma 1. Let (ana(an-1) be the DJ confidence interval. Then coverage condition is:
Ya+1 & (n.a(En+1) = n + 1e Q(K).
Proof. Suppose that Ön (xn+1) does not cover the true test label Un+1, i.e. Uo+t & (n then this implies that either
Un+1 f(xn+1) + Qt, (fri) + Qan (fo:(2n+11)"
which means that yn+1 > f (xn+1) + Qt (fri)in)) + for least (1 - a) many indices j E {l, .n. or
Unt1 f(mnt1) - Q+ (tr:) Qan ((v:(#n+1))
which means that Un+1 < f(xn+1) Q 1 By for least a) + 1) many indices j E .1.... n]. either case, then, we have
(1 1) Σ
{ yatz f(xnt)) (0o. (tri)ien) + +1;))
Σ {1 (1u0t1 - f-y((n42)) Qma (frebing) + 2/}
By nothing that
Bat1 f-5(2nn11)
Kntian
17

---

Under review as a conference paper at ICLR 2020
and Qan (fri)i=1) 0. k we have
- (1 1) Σ
(Knti > K
j=1
which implies that Q(K), and hence
P (yn+t & Cnnl(nnt)) s PP (n Q(K))
which concludes the proof the Lemma.
Given the result of Lemma 1, we use the exchangeability of the training and test points further bound the probability (/++1 & ((n+(() } as follows. Since the training and testing points are exchangeable, we have K & II II" for any (n + 1) x (n + 1) permutation matrix II, where d denotes equality distribution. Thus, we have
P F
[(K)) = P E Q()))
for all j E {I....,Mo n.). Based on the above, we can then evaluate the coverage probability using the equivalent condition in Lemma as follows:
Pfn+le 2(K) = n n+1
PÚj
(())
x+1
E
1 E
E [IQ(K)]]
(C.3)
n+1
Finally, compute the expected size of the set @(K) as follows. By combining the original coverage condition in (C.2) together with the equivalence result Lemma I, we have
n+1
n+1
- a1-a)(n + 1)
Σ
1 Ki) S
Σ 1 [(K) 1 (((K)),
j=1
j=1
which implies that |Q(K) I a(n + 1). By combining this with (C.3), we arrive at the following inequality
P {untt1 & Cn,a(En+1)) aa
The result of the Theorem follows from the fact that the approximate DJ confidence interval Clim) (In+1) converges in probability to the exact interval as m + co.
C.2 DISCRIMINATION
Recall that the exact DJ interval width is given by:
W (C(oo) (æ; 0)) 2 Qn,n (V..)())
(C.4)
Since the term Qa (R.)) is constant for any æ. discrimination boils down to the following condition:
E Qo, (x)) E (V.( + E[l(y, f(x; 2 B[((s/ f(=';(()))
(C.5)
Note that to prove the above, it suffices to prove the following:
[[v](=)] 2 [[[ (x(') + E[ Ely f (x; 0)) 2 E f( f((x;0)))
(C.6)
If the model is stable (based on the definition in (Bousquet & Elisseeff (2002))), then classical result by (Devroye Wagner (1979)) states that:
[E [[(, (ax θ)) - l (y, fa; 0) Ell 0)) Ely, [(;; 0_ +) + Const,, (C.7) n. do, where f (.) is the empirical risk the training sample, and the expectation above is taken over
y/ æ. From (C.7), we can see that an increase in the LOO risk É(y, f(x; 0_.)) implies an increase in the empirical risk é,, (v. of (x; 0)), and vice versa. Thus, for any two feature points æ and w'. if v(x)) is greater than u(x²). then average, the empirical risk at is greater than that at x'.
18

---

Under review as a conference paper at ICLR 2020
D EXPERIMENTAL DETAILS
In this Section, we provide more details for the experimental setups in Section 5, in addition to further experimental results the context of active learning and out-of-distribution detection.
D.1 CODE SNIPPETS FOR THE DJ PROCEDURE
The DJ procedure is very simple to implement. The key component of its implementation is the computation of HOIFs. Let model be an instance of the nn module of Pytorch, with set of parameters model. par amrrrse () that correspond to in our formulation. Below is Python code snippet for computing the first-order influence function model.
def wwwlluence_ffucttiee (model, treining
IF []
hessian (model. loss, model, paraleaaaaaeeesseeee (), create_graphhTee
Lamb 1e-3
Hinv torch, inverse (H
Lamb * torch.ep eye (H. (H.shhae(())) (0]))
for u in range (Len Straininggdatte (nnee___ddeeee)))
loss model loss fn (mmdellyyftraininnggg....o model podel.hiddee hideen (model. (taeeeeemmdlll..taaaiinngdddt deteraiiinn__dtt__ddeeeeeese [u], .flatt ())
_indexes [u]],
grads terch. wot.huuutorrdd.gae...... (lcss, model. parameter ())
IF IFaapen (torch. mv (Hinv, stack_terch_ (grads)))
return IF
Computing the HOIFs can be easily implemented by recursively evaluating the gradients and lower order influence function as stated in Theorem Once all the ingredients of the HOIFs are evaluated, then the perturbed parameters can be evaluated as explained in the paper, and modified LOO model created for every sample in the training data.
D.2 IMPLEMENTATION BASELINES
In what follows, provide details for the implementation and hyper- paremmtereeter settings for all baseline methods involved Section 5.
Probabilistic backpropagation (PBP). We implemented the PBP method proposed in (Hernández- Lobato & Adams (2015)) with inference via expectation propagation using the theano code provided by the authors in (gi thub. www/HIPS Ht////IISSSS// Probaai isstic Backpooopaattoiiono.... Training was conducted via 40 epochs.
Monte Carlo Dropout (MCDP). We implemented Pytorch version of the MCDP method proposed in (Gal & Ghahramani (2016)). In all experiments, we tuned the dropout probability using Bayesian optimization optimize the AUC-ROC performance on the training sample. We used 1000 samples at inference time to compute the mean and variance of the predictions. The credible intervals were constructed as the (1 a) quantile function of posterior Gaussian distribution defined by the predicted mean and variance estimated through the Monte Carlo outputs. Similar to the other baselines, we conducted training via 40 epochs for the SGD algorithm.
Bayesian neural networks (BNN). We implemented BNNs with inference via stochastic gradient Langevin dynamics (SGLD) (Welling Teh (2011)). We initialized the prior weights and biases through uniform distribution over [-0.01, 0.01]. We run 40 epochs of the SGLD inference procedure and collect the posterior distributions to construct the credible intervals.
Deep ensembles (DE). We implemented Pytorch version of the DE metho (without adversarial training)d proposed (Lakshminarayanan et al. (2017)). We used the number of ensemble members M = 5 recommended in the recent study in (Ovadia et al. (2019)). Predictions of the different ensembles were averaged and the confidence interval was estimated as 1.645 multiplied by the empirical variance for target coverage of 90%. We trained the model through 40 epochs.
19

---

Under review as a conference paper at ICLR 2020
Resampling uncertainty estimation (RUE). We implemented RUE (Schulam & Saria (2019)) in Pytorch using the same Hessian computation routines involved in implementing our method. We tuned the dampening factor À in the stabilized Hessian H À used for matrix inversion. We used 20 bootstrapped sub-samples of the training data to compute the prediction variance.
D.3 FURTHER RESULTS ON SYNTHETIC DATA
The minimum number of HOIF's m² required to achieve the best possible AUC-ROC for the quantita- tive experiment (d 20) in Section 5.1 is shown Figure 5. As expected, more complex models will generally require more high order terms of the von Mises expansion in order recover the parameters of the LOO re- re-trained model.
3.00
2.75
2.50
Number of HOIFs
2.25
2.00
1.75
1.50
1.25
1.00
50
100
150
200
250
300
350
400
Number of network layers
Figure 5: Impact of model complexity on number of HOIFs required for accurate recovery of LOO parameters.
D.4 FURTHER EXPERIMENTS WITH REAL DATA
We performed another series of experiments to evaluate the accuracy of the estimates of the uncertainty estimates produced by different methods. We study two particular applications of uncertainty quantification: active learning and out-of-distribution detection (OOD).
Active Learning. For this setup, we replicate the active learning experiment in (Hernández- & Adams (2015)). In active learning, it is necessary produce accurate estimates of uncertainty in order to decide which data samples we should actively collect. In this experiment, we used a neural network with a single hidden layer and 50 hidden units. We split each data into training and test sets with 20 and 100 data instances, respectively, and pool sets with all the remaining data. After this, one data point is collected from the pool set and then moved into the training set. The process repeats until 9 of these active additions to the training set have been completed, that is, until we have performed evaluations on the test set. The entire process, including the random data set splitting, repeated 40 times. The pool data is initially lacking the target variables and these become available only once the data is moved to the training set.
We compare a baseline neural network model trained random selections from the pool data with version of the model trained by data collected actively (PBP-A, MCDP-A, DE-A, BNN-A and DJ-A). Results are provided in Table 3. As better than the random baseline model on all datasets. Moreover, data actively collected using DJ-based uncertainty estimates superior to all other methods 6 out of the datasets.
ba-ba active collection of data is significantly
20

---

Under review as a conference paper at ICLR 2020
Dataset
Method
Housing
Concrete
Energy
Kin8nm
Naval
Power
Wine
Yacht
Bascline
7.0
1 0.4
4.5 0.2
0.4 1: 0.0
0.01 1: 0.0
5.5 1. 0.0
0,95 0.1
5.5 d: 0.4
DJ-A
4.8 0.3
12.7 = 0.3
3,9 + 0.2
0.3 = 0.0
0.01 + 0.0
5.1 + 0.0
0,92 = 0.0
4.0 4.0 0.3
PBP-A
5,5 + 0.2
12 # 0.2
4.1 + 0.1
0.4 # 0.0
0.02 + 0.0
5.0 + 0.1
0.90 = 0.0
4,5 + 0.4
MCDP-A
6.5 d: 0.1
12.4 d: 0.2
4.7 0.2
0.5 d: 0.0
0.03 1: 0.0
5.2 1: 0.1
1.00 1: 0.0
5.1 d: 0.4
DE-A
4.2 0.2
13.1 + 0.2
+ 0.1
0.3 + 0.0
0.05
5.4 + 0.1
0.80 0.0
5.1
BNN-A
7.1
0.1
#.1
0.5
0.02
5.3 +
Table 3: Average test RMSE and standard errors in active learning.
aut-of-distributinn detection. Next, we evaluate the accuracy the DJ uncertainty estimates in detecting whether new test example came from the same distribution the training data, or from another unknown distribution. This task is known as out-of-distribution detection (OOD), and is commonly used to benchmark uncertainty estimation methods (Ovadia al. (2019)).
In this experiment, we use data from the Infant Health and Development Program (IHDP) (Alaa & van der Schaar (2017)). The IHDP is an interventional program intended to enhance the health of premature infants. This dataset comprises observational data with treatment assignments from a real-world clinical trial, and introduced selection bias the data artificially by removing subset of the patients. Every sample in the dataset is of the form (æ, y. w), where w E {0.1) is binary treatment assignment variable which equal if the patient was treated, and is 0 otherwise. Since patients are not treated at random, i.e., the likelihood of patient getting treated depends on their feature æ, the treated and untreated patient populations have different distributions, i.e., we have P(x w 0) a Pa w 1). The entire dataset comprised 747 subjects, with 25 features for each subject, which 165 were treated and the rest were untreated.
DJ
PBP
MCDP
BNN
RUE
CCP
+ 0.01
0.69 + 0.03
0.72 0.01
0.75 0.02
0.65
0.75 + 0.01 0.72
0.02
Table 4: AUC-ROC accuracy of all baselines the OOD task.
We conducted our experiment as follows. We train the model on 100 samples for treated patients, and leave out 65 samples for testing. In testing, we use the interval width predict whether the test samples comes from the 65 treated patient (whose features resemble the training data). or from the untreated patients who were not involved in training. We repeated the experiment 20 times with random train/test splitting. The model we used is a feed-forward neural network with 2 hidden layers and 100 hidden units. AUC-ROC performance reported in Table 4.
We found that DJ outperforms other methods in detecting the OOD samples, with DE and RUE being the most competitive baselines. This result of practical significance since it implies that we can accurately determine which patients should be treated based the recommendations of machine learning-bast decision-support system, and which patients should be examined in a case by case basis through experts. Moreover, by determining which samples in observational dataset have the most unreliable predictions, and consequently determine what features are required a prospective design of clinical trial.
21


Reviews:
[{"review_id": "rkl5mh7k9S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors provide an interesting study on uncertainty estimation for deep learning for regression problems. The submission is well written and well structured w.r.t. the motivation and underlying theory, which are accompanied by extensive derivations/proofs in the annexes. However, experiments are presented for small-scale tasks only.\n\nThe title of the submission addresses deep learning in general. However, the submission specifically is limited to regression, which is only mentioned scarcely throughout the paper and only as early as Sec. 2. This limitation should be mentioned in title and abstract.  Also, even though deep learning is addressed and covered in principle by the theory, the experiments do not really seem to cover deep models, being limited to two-layer networks of limited size. In Annex D.3 and specifically Fig. 5, network depth is addressed, but virtually no further details or performance measures are given for these experiments.\n\nMany of today's deep learning tasks go beyond simple classification and handle complex tasks based on e.g. sequential or higher dimensional data strongly exploiting context, being trained on huge amounts of data, and exploiting considerable deep models with huge numbers of parameters. The experiments presented here are limited to fairly small tasks and models of limited size and especially limited depth. It would be interesting to see a discussion on how the proposed approach is expected to scale w.r.t. the size of the data set and w.r.t. the complexity of the modeling. Also, it would be interesting, to understand how prediction in context would alter the described findings.\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJgJLYo39H", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this work, the authors develop the discriminative jackknife (DJ), which is a novel way to compute estimates of predictive uncertainty. This is an important open question in machine learning and the authors have made a substantial contribution towards answering the question of \"can you trust a model?\" DJ constructs frequentist confidence intervals via a posthoc procedure. Throughout, the authors provide excellent background and exposition. They develop an exact construction of the DJ confidence intervals in Section 3.1. This is an intuitive approach that the authors explain well. Next, they explain and then develop the concept of higher order influence functions. They do a great job of communicating this concept. Section 3.4 provides the theoretical guarantees for DJ. The related work section is extensive and thorough. The authors have thoughtful experiments that demonstrate positive attributes of DJ. \n\nI suggest that this paper is weak accepted. On synthetic and real data, the DJ empirically works well, based on Figure 4 and Table 2. In addition, the theoretical exposition is very clear and compelling. The intuition provided in Sections 3.1 and 3.2 helps readers really understand what's going on, then 3.3 and 3.4 give theoretical justifications of the utility of DJ. \n\nHowever, I have a few suggestions for improvement that lead to the \"weak\" acceptance. First, I'll cover minor quibbles, then more major points. \n\nIn Figure 1: At first, the blue dots and blue shading were not clear to me. In the legend, maybe explain that the blue shading indicates coverage and the blue dots indicate regions of higher/lower discrimination. \n\nIn Equation 6: Looks like there is a misplaced parentheses. I think the last two terms of the equations should be Q(Vn-)+Q(Vn+) not Q(Vn-+Q(Vn+))\n\nIn Equation 7, and throughout: I think a better notation for the function would be \\mathcal{I}^{(1)}_{\\hat{\\theta}} rather than \\mathcal{I}^{(1)}_{\\theta} since the influence function is a derivative with respect to the optimal parameters. \n\nBelow equation 8: you should probably have an additional k exponent in the numerator of the kth order influence term, i.e. = \\frac{\\del^k \\hat{\\theta}_{i, \\epsilon}}{\\del \\epsilon^k}\n\nIn Theorem 1: could you calculate this without \\grad L(D, \\theta), since L a function of \\ell ? Maybe mention this in the appendix\n\nIt could be nice for an appendix study on how approximating the Hessian impacts performance for cases when we can compute the Hessian exactly. \n\nTable 1 could be expanded to include comparisons on computational bottlenecks and if there's retraining in these other methods. \n\nIn Figure 4, please indicate the order of the IF used in the DJ procedure. DJ(m=?)? \n\nMajor issues: \n\nWhy weren't the other jackknife procedures used as baselines as well? I realize DJ has advantages compared to them, but an apples to apples comparison would be useful. For some researchers, LOO CV might not be prohibitive. This could be a chance to really sell your method: if it does well enough compared to more expensive LOO jackknife procedures, that would be a compelling reason to choose DJ. \n\nCould you please check this reference and let us know if it substantial is different from Influence functions that you develop? \"Higher order influence functions and minimax estimation of nonlinear functionals\" Robins 2008 DOI: 10.1214/193940307000000527 Robins et al. develop a way to compute higher order influence functions, which you do claim you're the first to do \"to the best of your knowledge.\" \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "H1xDF_cEqH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies how to construct confidence intervals for deep neural networks with guaranteed coverage. The authors propose an algorithm, “discriminative jackknife”, based on the standard jackknife confidence interval estimate which they augment by a “local uncertainty estimate” based on the variability of the n leave-one-out fitted versions of the underlying algorithm (n = # data points). The whole study is concluded with toy and real-world examples showing the proposed algorithm is competitive with existing methods while also achieving the desired coverage.\n\nI am currently leaning towards recommending rejection of the paper. The main reasons for this are: (i) A potential failure to cite and acknowledge the prior contribution of [1] which seems to have non-trivial overlap with this paper (on arxiv since end of July which is more than 30 days before the ICLR submission deadline and thus should be treated as prior work); (ii) The claims of guaranteed frequentist coverage are not backed up as, according to thm.2, they only hold when n >> 0 and the number of influence functions used goes to infinity (ideally, the authors would provide non-asymptotic bounds as in [1], but at the very least, these limitations should have been clearly pointed out and their practical implications discussed). Finally, I would like to say that I am holding the paper to a higher standard due to its 10 page length as instructed by the guidelines.\n\n\nMajor comments:\n\n- Can you please explain the relation of this work to [1]? It seems that [1] already proposes use of the higher order expansions, provides an efficient implementation based on forward mode autodiff (do you plan to release code?), and moreover provides non-asymptotic bounds which are not present in your work?! \n\n- On a related note, Giordano et al. provide a careful analysis and discussion of the assumptions in their sect.4. Can you please clarify which of the assumptions you also make, and why you don’t need the others (if any)? \n\n- Throughout the paper (e.g., in and around eq.1), you seem to assume that there exists a unique minimiser of the objective which generally won’t be true (especially in your application to deep neural networks). In [1], the technical assumptions ensure this is true but I don’t see how this is handled in your case?! Can you please help me understand how to interpret your work in case there are multiple (possibly local) minima, and whether this has any effect on the results in thm.2?\n\n- I think it would be beneficial to the reader if you could please provide a discussion and/or formula for how large n has to be for Theorem 2 to apply.\n\n- On p.8, you say “To ensure a fair comparison, the hyper-parameters of the model f(x; θ) were the same for all baselines.” I am not sure I agree this is a fair comparison. Commonly, one has the opportunity to select hyperparameters for their algorithm (e.g., using a validation set, cross-validation, etc.) so it seems it would have been fair to run each algorithm with its best hyperparameters. Can you please provide a discussion of how this would affect the reported results?\n\n\nMinor comments:\n\n- On p.3, you say “We do not pose any assumptions on how the loss function in (1) is optimized.” Do you mean to say that you do not assume anything **but** that the chosen optimiser reaches a (global?!) minimum of the loss function? It seems like you would want to exclude pathological optimisers (e.g., one that always outputs zero) but also more realistically think about the known pathologies of commonly used optimisers (see, e.g., [2]).\n\n- Can you please clarify if and how the use of the algorithm from (Agarwal et al., 2016) for approximation of the Hessian products affects accuracy of your confidence intervals?\n\n- In fig.3, it seems like some of the methods are not properly tuned. For example, MC-dropout should not have zero uncertainty around zero (did you by any chance set bias variance to zero?!), and BNN-SGLD does not seem to have converged (can you please provide plots providing some evidence that the MCMC sampler has mixed + information about how the hyperparameters were selected?).\n\n- I am somewhat confused by the statement “The only hyper-parameter involved in our method is the number of HOIFs m — this was tuned by optimizing the evaluation metrics ...” on p.8. Wouldn’t thm.2 suggest that you should use as high m as possible?\n\n- Also on p.8, can you please clarify how you selected the threshold for the evaluation of “discriminative power”? In particular, thm.2 seems to suggest that what one would desire is that the ranking based on width of predictive intervals is equivalent to the ranking based on the actual prediction error. This would suggest, for example, comparing these two rankings using Kendall’s tau coefficient (perhaps a binned modification where one would count only the number of times true error puts a point into a different bin than the width of its confidence interval). Note that I am not suggesting the above method is perfect either (it completely ignores the actual sizes of the intervals), but I’m currently having trouble interpreting the results you report, so it would be very helpful to understand how you selected this particular measure of “discriminative power” and why alternatives like the example above were discarded please.\n\n\nReferences:\n\n[1] Ryan Giordano, Michael I. Jordan, Tamara Broderick. A Higher-Order Swiss Army Infinitesimal Jackknife. https://arxiv.org/abs/1907.12116\n\n[2] Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, Benjamin Recht. The Marginal Value of Adaptive Gradient Methods in Machine Learning. https://arxiv.org/abs/1705.08292", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BJe50L_9FH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose using influence functions to efficiently estimate pointwise confidence intervals for regression models. Their central idea is to construct a confidence interval around a point $x$ as a function of how much the model $f$ changes around $x$ when individual training samples are left out. Their technical innovation is to combine a marginal error term that does not depend on $x$ (which ensures coverage) with a local variability error term that does depend on $x$ (to allow for greater variability in areas where the model is more uncertain and there is less data). The authors provide experimental support for the superiority of their method (in terms of coverage and discrimination) as well as theoretical support for consistency.\n\nIn my opinion, the ideas in the paper are exciting; the paper is clear and well-written; and the experimental evaluation is quite comprehensive in terms of baselines. However, I have concerns that prevent me from recommending an accept at this time:\n\n1) Similar recursive formulations for HOIFs have appeared in the literature, so the claims in Section 3.3 should be toned down. See for example lemma 3 in Giordano, Jordan, and Broderick, 2019 (https://arxiv.org/abs/1907.12116); or for an older reference that’s a bit more specialized, see Debruyne, Hubert, and Suykens, 2008 (http://www.jmlr.org/papers/volume9/debruyne08a/debruyne08a.pdf).\n\n2) The paper refers repeatedly to how their proposed method can be applied to deep learning models and, in particular, state-of-the-art deep learning models. In my opinion, the evidence in the paper does not support these claims. The largest experiments are run on neural networks with 100 hidden units, and it is not clear how to scale up their method to state-of-the-art models and large datasets. In particular, the Hessian-vector computations and the need to iterate through the dataset scale poorly with model and dataset size, and efficient approximations for these are non-trivial and an area of active research.\n\n3) Related to the above point, the theorem statements apply to general differentiable loss functions. Are they true in such a general setting? For example, in Section 3.3, the assumption that the inverse Hessian needs to be positive definite is noted but this does not appear in the theorem statements. More importantly, it seems like some notion of strong convexity is required; for example, does the convergence of the von Mises series in Appendix A require that the parameters don’t change too much with $\\epsilon$? This might not be true in a non-convex model. The paper also elides the fact that the global minimizer $\\hat{theta}$ cannot in general be computed in non-convex models like neural networks.\n\nThe paper is otherwise compelling to me, and I believe that the above points can be remedied by being more careful and circumspect with the claims in the paper.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this work, the authors develop a method for providing frequentist confidence intervals for a range of deep learning models with coverage guarantees.  While deep learning models are being used pervasively, providing reasonable uncertainty estimates from these models remains challenging and an important open problem.  Here, the authors argue that frequentist statistics can provide confidence intervals along with rigorous guarantees on their quality.  They develop a jack-knife based procedure for deep learning.  The reviews for this paper were all borderline, with two weak accepts and two weak rejects (one reviewer was added to provide an additional viewpoint).  The reviewers all thought that the proposed methodology seemed sensible and well motivated.  Among the cited issues, major topics of discussion were the close relation to related work (some of which is very recent, Giordano et al.) and that the reviewers felt the baselines were too weak (or weakly tuned).  The reviewers ultimately did not seem convinced enough by the author rebuttal to raise their scores during discussion and there was no reviewer really willing to champion the paper for acceptance.  Unfortunately, this paper falls below the bar for acceptance.  It seems clear that there is compelling work here and addressing the reviewer comments (relation to related work, i.e. Robbins, Giordano and stronger baselines) would make the paper much stronger for a future submission.
Decision: Reject