Approximating Full Conformal Prediction for Neural Network Regression with Gauss-Newton Influence
Authors: Dharmesh Tailor
Alvaro Correia
Eric Nalisnick
Christos Louizos
Venue: ICLR 2025 Poster (2025)
Keywords: conformal
laplace
influence
neural network
deep learning
uncertainty
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We approximate full conformal prediction by Gauss-Newton influence and local linearization.

Abstract: Uncertainty quantification is an important prerequisite for the deployment of deep learning models in safety-critical areas. Yet, this hinges on the uncertainty estimates being useful to the extent the prediction intervals are well-calibrated and sharp. In the absence of inherent uncertainty estimates (e.g. pretrained models predicting only point estimates), popular approaches that operate post-hoc include Laplace’s method and split conformal prediction (split-CP). However, Laplace’s method can be miscalibrated when the model is misspecified and split-CP requires sample splitting, and thus comes at the expense of statistical efficiency. In this work, we construct prediction intervals for neural network regressors post-hoc without held-out data. This is achieved by approximating the full conformal prediction method (full-CP). Whilst full-CP nominally requires retraining the model for every test point and candidate label, we propose to train just once and locally perturb model parameters using Gauss-Newton influence to approximate the effect of retraining. Coupled with linearization of the network, we express the absolute residual nonconformity score as a piecewise linear function of the candidate label allowing for an efficient procedure that avoids the exhaustive search over the output space. On standard regression benchmarks and bounding box localization, we show the resulting prediction intervals are locally-adaptive and often tighter than those of split-CP.

Published as a conference paper at ICLR 2025
APPROXIMATING FULL CONFORMAL PREDICTION FOR NEURAL NETWORK REGRESSION WITH GAUSS- NEWTON INFLUENCE
Dharmesh Tailor Alvaro H.C. Correia", Eric Nalisnick", Christos Louizos University of Amsterdam "Qualcomm AI Research *Johns Hopkins University
ABSTRACT
Uncertainty quantification an important prerequisite for the deployment of deep learning models in safety-critical areas. Yet, this hinges the uncertainty esti- mates being useful to the extent the prediction intervals are well-calibrated and sharp. In the absence of inherent uncertainty estimates (e-g., pretrained models predicting only point estimates), popular approaches that operate post-hoc include Laplace's method and split conformal prediction (split-CP). However, Laplace's method can be miscalibrated when the model is misspecified and split-CP requires sample splitting, and thus comes the expense of statistical efficiency. In this work, we construct prediction intervals for neural network regressors post-hoc without held-out data. This achieved by approximating the full conformal pre- diction method (full-CP). Whilst full-CP nominally requires retraining the model for every test point and candidate label, we propose to train just once and locally perturb model parameters using Gauss-Newton influence approximate the effect of retraining. Coupled with lincarization of the network, we express the absolute residual nonconformity score as piecewise linear function of the candidate label allowing for an efficient procedure that avoids the exhaustive search over the out- put space. On standard regression benchmarks and bounding box localization, we show the resulting prediction intervals are locally-adaptiv and often tighter than those of split-CP.
INTRODUCTION
Despite impressive advancements in machine learning, most models, particularly neural networks, are still designed and trained to provide only point estimates, lacking the ability to rigorously quan- tify uncertainty in their predictions. This poses a significant challenge, reliable decision-making depends on trustworthy uncertainty representation. This need has drawn increased attention to un- certainty quantification in machine learning research, especially the use of these models becomes more widespread and permeate seeety-se fields such as healthcare and autonomous driving.
Conformal Prediction (CP) (Vovk et al. 2005) is class of uncertainty quantification methods that represent uncertainty via prediction intervals. These intervals intuitively convey the degree of the larger the interval, the greater the uncertainty. What sets CP apart rigorous, distribution-free coverage guarantee: conformal prediction intervals contain the true label with probability of at least 1 a, where is a user-defined miscoverage rate. In recent years, a variant known as split (or inductive) CP (Papadopoulos et al.) 2002) has gained traction in the machine learn- ing community due to its ease of use and low computational cost. Split-CP, as the name suggests, divides the available data into training and calibration sets, using the former to fit model and the latter to construct prediction intervals. Yet, Split-CP is statistically inefficient as it cannot leverage all available data for model fitting, which hinders overall model performance. In contrast, full (or transductive) CP uses all data for both training and calibration but incurs high computational costs. It requires retraining the model multiple times-one for each test point and possible which-which is prohibitively expensive for deep learning applications.
WWrk done while Qualcomm AI Research. 'Qualcomm AI Research is an initiative of Qualcomm Technologies, Inc. and/or its subsidiaries.

---

Published as a conference paper at ICLR 2025
1v (01
absolute residhals
1 (01 (w)))
ACP-GN CUPP-GNee (onny)
SCP
L.A
Interval wiith
3 16P
p-valte
2
200
400
600
800
1000
Test point index
Figure 1:
Our approx. full-CP via Gauss-Newton influence (ACP-GN) produces adaptive intervals (bottom left figure)-similrr to Bayes via Laplace approximation (LA)-while satisfying coverage as seen in the high-overlap with Split-CP (SCP) close the data (white dots with black edge in top left figure). In the top right, we show the absolute residuals for the training points (in gray) and test point (in pink) as function of the postulated label for the test point XN+1- The conformal p p-values, in the bottom right, only change when the pink line crosses gray line, the so-called "changepoints", reducing the search space over candidate labels to incorporate in the prediction set.
In this work, we scale full-CP to neural network regression by (i) eliminating the need for retraining through a Gauss-Newtor influence approximation, and (ii) avoiding exhaustive search over the label space via network linearization. This gives new, scalable full-CP method for neural network regression we dub approximate full-CP via Gauss-Newton influence (ACP-GN), As second contri- bution, we show the same tools can applied to enhance split-CP via normalization, yielding a new adaptable split-CP method call SCP-GN. We validate ACP-GN and SCP-GN in several regres- sion and bounding box prediction tasks, showing they satisfy coverage in most cases and produce tight, adaptable prediction intervals (see Fig. [ for results with ACP-GN).
BACKGROUND ON CONFORMAL PREDICTION
Neural network regression follows the canonical empirical risk minimization framework. Given dataset N == {(x,, W consisting of N examples with inputs x; E RR' and targets E R, we minimize the (regularized) empirical risk:
0, = arg ming E(y + 1 [leli))
(I)
where f((0) is shorthand for f(x;; 0), the output of a deep neural network (DNN) at with param- eters 0 E D. E(y. f) is a loss function, and 5 an L2 regularizer (i.e. weight decay). In this work, we restrict our attention to the squared-error loss: E(y, f) 1 (y f)² As is standard practice, the problem in Eq. (I) is approached using cecchastic-gradienn methods. For unseen input Xy+1, this gives us point prediction fN+1 (N.). However, in an ideal scenario, we would like a prediction interval whose width reflects the uncertainty associated with that input. This is where conformal prediction (Vovk et al. 2005) comes into play. It provides a framework for constructing prediction intervals while satisfying the following frequentist coverage guarantee known as marginal coverage
P PUN++ E (xN++) a
2

---

Published as a conference paper at ICLR 2025
where yN+1 is the unseen target, C. (Xx+1) is the prediction interval with desired miscoverage rate (0, 1), and the probability is over all samples {(x,, y hennee the name marginal coverage.
The prediction interval C. (xx+1) is constructed using nonconformity scores, which quantify how unusual a sample (x,, 31) is compared to other samples in set. In the context of regression, which is the focus this paper, the absolute residual R₂ = R(x, yi) = 13: fi(0)] is the most common
score (Kato al. 2023). Given the data DN and score function, C. (xN+11) is defined as
Ca (U E R: (V) = [(1 aN 1)1)
where (()) = N+1 1(R; I R(XN+1, y)) is the rank of R(xN-1, y) among the other N resid- i= uals. Remarkably, the only requirement for prediction intervals constructed as in Eq. (3) to satisfy marginal coverage is that the set of scores { {R(x;, ] N+1 11 be exchangeable. This is equivalent to assuming the data is exchangeable and the score function (and consequently the regressor) preserves this exchangeability by treating data points symmetrically. Thus, Eq. (2) is distribution-fii -free guar- antee that remains valid even if the model is misspecified. This contrasts with Bayesian methods, the dominant approach for uncertainty quantification in deep learning, which are often poorly calibrated Grünwald & van Ommen 2017).
under model misspecification (Dawid 1982
Fraser 201
2.1 SPLIT CONFORMAL PREDICTION
As stated in the introduction, CP methods can generally be categorized into Split-CP and full-CP variants. The primary distinction between these two families of methods lies in how they ensure the exchangeability of the set of scores { {R(x, ) U (R(xN+1, y)]- Essentially, this means that all samples, including the test sample (XN+1. MN+1), must exert the same influence over the prediction model f-:0). Split-CP offers the simplest and most computationally efficient solution. By keeping the model fixed when computing the scores of each of the N + samples, it ensures the scores are exchangeable, as the score function is applied elementwise. However, this approach is data inefficient because it prevents using the first N samples to fit the model, requiring separate training dataset. This statistical inefficiency can negatively impact the quality of the final prediction intervals in two key ways. Since any conformal prediction method is designed to achieve coverage as described in Eq. 2). different approaches are compared in terms of their efficiency- howeeeyyyyhwwweooo small the prediction intervals are-and and adaptability- how much the size of the prediction intervals varies across samples. To be informative about both the true label and predictive uncertainty, prediction intervals must be both efficient and adaptable. However, in split-CP, efficiency is compromised because not all data is used for calibration, while fixing the model parameters reduces adaptability.
2.2 FULL CONFORMAL PREDICTION
Full-CP uses all available data for both training the model and computing prediction intervals. The main challenge in full-CP is that exchangeability of scores requires treating all data points symmet- rically, meaning the model should be fit on {(x; 1;) i=1 as well as (xN+1, IN+1). Since yN+1 is unknown priori, this necessitates retraining the model for all possible values MN+1 can take. To be precise, full-CP requires the following modification to the optimization problem in Eq. (
0+ (v) = arg ming
<>M Elye, fi(O)) + Ely, JN++ (0)) + 5 (101)))
(4)
where o (y) is the optimal model parameters for the augmented training set D (3) := DN U ((XN+1, })} that includes the test point x plus a candidate label y for UN+11 With slight abuse of notation, we use (y) to denote the residual with model parameters 00 (y). that is,
(v()) = y: fi(O (g)) Vi 1......., N and RN+1(9) ly - fN+1 (v))
(5)
From here we can construct prediction intervals in Eq. (3). but now the residuals vary for each test point XN+1 and candidate label y E R. As mentioned before, this has two major limitations. Firstly it requires retraining the model for every candidate label y which is infeasible for DNNs. Secondly in theory the method asks to consider an uncountable set (í.e. all real numbers). Therefore, in practice finite grid of possible labels for y is used, typically delimited by the training targets. Evidently, the grid imposes computation precision trade-off and has implications for the coverage if a valid candidate happens to lie between two grid points (Chen al. 2018). In few cases, the
prrpiitioonn
3

---

Published as a conference paper at ICLR 2025
prediction set can be computed efficiently and exactly without the need try candidate labels of y- In addition, this procedure only depends on a single fit on the original (umaugmented) dataset which can be efficiently updated not only for variations in y but also for different inputs + These include the Lasso (Lei] 2019). k-Nearest Neighbours Regression (Papadopoulos et al. 2011). and ridge regression (Nouretdinov et al. |00T: Burnaey & Vovk 2014). Thheee also approaches based on homotopy continuation methods (Ndiaye & Takeuchi 2019) and algorithmic stability (Ndiaye) 2022) that hold in more general settings, In the following section, we review conformalized ridge regression which is the basis of our approximate full-CP procedure.
2.3 CONFORMALIZED RIDGE REGRESSION (CRR)
Ridge regression is a special case of Eq. Ip where we have a linear model f0) := x 0. In this case, the absolute residual can be written as a piecewise linear function of the candidate with (y) = |a: + beyl. where a, and b; are coefficients capturing information from the training data and test point, resp. It is then convenient to express the rank as T(y) = I1 1 E S:). with = {y= R&(y)= S Rx+1 (V) {y |a; + bay S |aN+1 + bN++
(6) Each set St can be interval, point, ray, union of two rays, the real line, the empty set. Eq. (6) suggests that the rank for a given y can only change at points where (v) = Rx+ (y) to which we refer as "changepoints", For the absolute residual, these changepoints fall into one of the following two cases, where we assume b; 2 0 (if needed, multiplying a, and b, by 1):
If b, # b then Sy is an interval -aa aN+1)/(b, bx+1) and -aa + aN+1)/(6, + bv+1).
union of two rays, and we have two changepoints,
If b; b f 0. then S; is ray, unless d; 4N+1, in which case S, R. Here we have single changepoint -(a; + aN-1)
This leads to exact form of the prediction set by taking the union of finitely many intervals and rays whose endpoints are given by the changepoints sorted in increasing order. Given the change- points, different implementations have been proposed with varying time complexity. For the smaller datasets, we use the ridge regression confidence machine algorithm (Nouretdinov et al. 2001 Vovk al. 2005), which uses the absolute residual and changepoints described above.
There is also a simpler, asymmetric version of CRR that uses the signed residuals (Burnaev & Vovk 2014]. It allows us compute the lower and upper bounds of C. (xx+1) separately, using residuals T(() y/s for the lower bound, and y/i fO) for the upper bound. This is the version we use for the larger datasets and that appears in the depiction of our method in Alg. [] where we use 1 and u, to denote the changepoints for the lower and upper bounds, resp. When using signed residuals, S;
either ray with changepoint 1 u, = (a. (a:-av- -1) (bN if b,+1 by > 0 or otherwise, S = RR with 1, = -x: and u, = oo.
Finally, we need to write down the expression for coefficients a, and b,. Using the Sherman- Morrison formula, widely-used tool of the regressions diagnostics literature (Cook 1977), Burnaey & Vovk 4014)) showed that the required coefficients a,,..., aN+1 and bj...., bN+1 for the CRR procedure can be efficiently computed for different xN+1 by simple rank-1 update or perturbation to the ridge solution on D (see App. A for derivation):
h T O.
h4,N+1 y
1/1 x (1) Vi x 0.
hN+1 XN+1
1+ hN+1
1
- X xx+++ 0+(2)
x xN+101
O.
(8)
1 + hN+1
1 hN+1
aN+1
bN+1
where hy-1 I XxN+1 with Hessian matrix H. EM xxx] ST.
2.4 NORMALIZED NONCONFORMITY SCORES
In the previous section, we derived CRR using the nonconformity score given in Eq. (5), which is often referred to add-one-in (AOT). In this section, we also consider the leave-one-out (1.O)) and
4

---

Published as a conference paper at ICLR 2025
studentized scores, which lead to the variants CRR-deleted and CRR-studentized and their corre- sponding extensions to neural network regression given by our approximate full-CP method. All those variants are valid choices (Vovk et al.) 2005; Shater & Vovk 2008), and the literature is not
conclusive regarding which one is to be preferred (Fong & Holmes 2021: Fontana et al.] (023). Yet, in our neural network regression experiments, the studentized variant outperformed the other two.
In the leave-one-out (LOO) variety (also known as jackknife), scores R!00 are computed by ex- cluding the th data point from the augmented data (v) before retraining the model. The only exception being -1 which requires retraining, 0. already ignores the (N + 1)th data point. In the case of ridge regression with absolute residuals, we can derive the jackknife score from the
standard one as (Vovk et al. 2005)
R 1.000 R1/(1-h:),
where we have included the leverage score with respect to the augmented problem h; = x H, x;, with H. Eii x + ōI. The leverage score (Chatterjee Hadi 1986) can be viewed as diagnostics measure for measuring the sensitivity of the prediction to changes in the target. The formula a consequence of the exact rank-l updates available in ridge regression. This leads to the deleted-CRR method which proceeds in the same way as standard CRR except it uses the normalized coefficients: a; + a1/(1- 11-hh h;) and b; + b,/(1 h;) for i = 1,..., .N + 1. Such relations can also be used to recover the standard score starting from the jackknife one:
R4 R400
(10)
where R.y x. H.. x, with - N+1 مير x,x] + SI. Papadopoulos (2024) gave an interpreta-
tion of this relation as locally-weighted conformal prediction (Papadopoulos et al., 2008 where the expression in the denominator can be seen as the lcave-one-out predictive variance from a Bayesian perspective. This can be seen a measure of the difficulty of the 7th example. Similar normalizations can also be applied to nonconformity scores in split-CP framework (Vovk et al. (000)). Finally, the studentized- CRR can be interpreted as a compromise between standard and Celeted-CRR It uses a similar normalization and defines nonconformity scores
pestudent Re/V1-h.
(11)
This transformation is applied analogously to the CRR coefficients with a, and b,.
3 APPROXIMATE FULL-CP FOR NEURAL NETWORK REGRESSION
In previous work, (Martinez et al., 2023) used influence function (Jaeckel 1972; Cook & Weis- berg 1980 to approximate the retraining step in full-CP by locally perturbing the solution on the unaugmented dataset. This ensures that neural network is trained only once on the original data. However, this was restricted to classification problems and so their approach requires discretizing the (continuous) target space. This introduces an additional computational burden and must be done in a careful way to avoid further increasing the coverage gap (Chen et al. 2018). We propose to use local perturbation closely related to influence function alongside network linearization in order to express the residual nonconformity score as a linear function of the candidate label that recovers Eqs. 77 and (8) special case. Then by leveraging the conformalized ridge regression framework Nouretdinov et al. 2001), we can eliminate the need to specify a grid of candidate labels.
We propose Gauss-Newton influence approximate the solution to the augmented problem 0: (1) 0. (2).
(N+1(U) HON
0. O- + + hN+1
(12)
where db (O.) is the Jacobian of the neural network at O,, Hox EN T T
+ SI is the Gauss-Newton approximation to the Hessian, (x+1(v) = y y fN+1(0=) is the residual for the (N + th example and Ax-1 T H can be interpreted as kind of generalized leverage score (Wei et al. 1998). This is a specialization of Newton-step (NS) influence (Pregibon 1981 Beirami et al. (017). ), technique closely related to influence function (Jaeckel [972] Koh &
matrix (Martens) 2010) followed by a rank-one update (see App. B for the derivation). Whilst such influence measures are commonly
Liang 2017). by approximating the Hessian by the
5

---

Published as a conference paper at ICLR 2025
used for estimating the effect of removing single example (or group of examples) on the model, extend this for adding an example, that is add-one-in (AOI) estimation. Previous work has shown that NS influence more accurately estimates the solution to the modified problem than influence function (Pregibon 1981 Rad & Maleki 2020). However, at present influence function is the more common choice since in its standard form NS influence requires recomputing and inverting the Hessian matrix whenever a different target effect (e.g. change in removed example(s)) is desired, thus incurring a higher computational cost. Our use of the Gauss-Newton approximation leads to form amenable to rank-one update, similar to generalized linear models (Pregibon 1981). bringing down the complexity that of influence function.
Next we show that using Eq. (12 along with linearization of the neural network, we can approximate the residual as linear function of the postulated label y recovering an identical form to that of conformalized ridge regression in Eqs. and
V1 - f:(0 (v)) v yi f.)).) + h,,N+1 fN+1(0.) 1 hN+1
h4,N+1 y
(13)
1 hN+1
y - (N.1
hnt1 (0.) +
y
(14)
1+ hN+1
aN+1
where hv,N+1 = Φ. H NN+1 (see App. C for the derivation and App. D for the extension to the multi-output setting). This is not surprising as it is known that NS influence recovers the exact leave-one-out diagnostics in linear regression (Allen 1974] Cook, 1977). which is not the case for influence function. The coefficients can be readily adapted for normalized nonconformity scores as outlined in Sec. 2.4 Our use of network linearization is akin to the "direct" approach used in Martinez et al. )2023) approximate the nonconformity scores on the augmented solution directly.
In Alg. 2 we outline a simplified but complete algorithmic depiction of our method, which we dub approximate full-CP via Gauss-Newton influence (ACP-GN). We contrast with standard full-CP in Alg. [ highlighting the costly grid search and retraining steps (see App. G for a time complexity analysis). Note that ACP-GN there is no grid search and the model fit only once on all available data Dx, indicated in blue. At test time, instead of retraining the model for each -N ACP-GN only computes the CRR coefficients {ac, b using Gauss-Newton influence as in Eq. 13 and Eq. (T4). These are then used to derive the prediction set in closed form either using the method of Nouretdinov et al. 200I) or the asymmetric one of (Burnaev & Vovk 2014) that we show in Alg
Algorithm 1: Standard Full-CP.
Algorithm 2: ACP-GN (ours).
for each test point XN+1 do for each y in given grid do optimize O+ (y) as in Eq. (4)
optimize 0, in Eq. 11)
for each test point X do
compute NN+1 bx as in Eq. (14
for E {1.... N) do
Ry+1ly) ly fN+1 (
compute a; by as in Eq. 13
for E (1....]] N) do
if bx+1 - h; > then
(g) = 1y, - (v))
1 n4 (a; aN /
T(y) > N+1 (1)
else
if (g) 1 a +1] then
L4 0o and u, oc
include y in C. (xN+1)
sort (4) and {u in ascending order C. (xN++)
P [((++))//))) M((N+1)(1-/21))
Conformalizing Linearized Laplace We can show that our ACP-GN method can be interpreted as conformalizing Linearized Laplace (MacKay| 1992; Khan et al. 2019 Immer et al. 202 for regression. This relates to the result of Burnaev & Vovk (014)) who showed the CRR procedure can be viewed conformalizing "de- Blyyesignn Bayesian Linear Regression (with Gaussian assump- tions) (Burnaev & Vovk, 2014). They provide asymptotic results indicating that in well-specified settings, the conformal prediction intervals and Bayesian credible intervals closely align. This places

---

Published as a conference paper at ICLR 2025
method within the wider context of Conformal Bayes (Melluish al. 2001 Wasserman 2011 for recalibrating Bayesian intervals in case of model misspecification.
The Laplace approximation constructs Gaussian posterior approximation centered around the point estimate 0, and covariance given by the inverse of the Hessian (local curvature) of the empirical risk evaluated at O.. When the Hessian is approximated by the generalized Gauss-Newton matrix, refer to the resulting Laplace approximation as the Laplace-GGN posterior, q. (0) = N Σ.) where Σ. HGN. This is often accompanied by linearizing the output of the neural network about
0. (Foong et al. 2019 Immer et al. 2021b):
[i(0) tmm (0) f.(0.) + VoJi(O.) 0.).
(15)
The overall method is referred to as Linearized Laplace and retains the original NN point prediction as the mean of the posterior predictive. Analogous to the add-one-in estimate in Eg. (12. we can
derive an approximation the add-one ine-in posterior 9. (0) by perturbing the Laplace-GGii posterior
(see App. for derivation) whose mean is equal to (y):
(0) N(000; (v). Σt) where Σ (HaN + #N+1 N+1)
(16)
This is a simple extension of the leave-one-out results in (Nickl et al. 2023) to the add-one-in case. Using this perturbed posterior in combination with the linearized predictor in Eq. (15). we recover Eqs. (13) and [1).. From the perspective of Linearized Laplace, the Gauss-Newton influence gives the exact AOI solution with respect to the linearized network and in particular its feature expansion given the Jacobian of the network. However, it is often the case in practice that O, is not minimum of the empirical risk (i.e. neural network not trained convergence). Thus, O, not minima of the linearized network's objective. One can correct this by solving for the following objective,
arg ming E 2 (U: 0)2 + 3 (111))
(17)
where 3i := Φ. 0, + e with residual e, = y/4 f..). This is can be solved for in single step. This process is often referred to as "refinement" in the Linearized Laplace literature and has been shown to improve predictions (Immer et al. 202Tb). The exact AOI solution with respect to Eq. (17 is then given by,
system and hence
cin
0 (y) 0
HON
(18)
1 hN+1
which reduces to Eq. 12 when 0 = 0,. We can derive analogous expressions to Eqs. 13 and (4)
that differ only in the use of linearized versions of the neural network prediction and hold exactly.
Normalized Cplit-CP with Gauss-Newton Influence It turns out the tools we used to derive our approximate full-CP method are also effective to improve the adaptability and efficiency of split-CP. In vanilla split-CP, all prediction intervals have the same width because the model remains fixed. One way to alleviate this issue to normalize the scores as R2 R2 R where o, estimates the difficulty in predicting the 7th data point correctly (Papadopoulos et al. 2008). As observed in (Papadopoulos, 2024), the normalized scores described in Sec. 2.4 are scaled by the predictive variance, which is closely related to how difficult y; is to predict. This motivates our Gtaus-Newtte split-CP variant, with scores,
R lv..f. 1/
(19)
where h4 = Φ. H
H Φ. is the marginal variance given by Linearized Laplace. This is similar to Eq. 4.10 in (Vokk et al. 2005) and is analogous to the studentized scores in the full-CP case.
Validity of ACP-GN Similar to Martinez et al. 20233, we cannot assure that our ACP-GN satisfies
the coverage guarantee of full-CP. This is simply because the retraining step is locally approximated. However, bounds on the approximation error have previously been derived for Newton-step influ- ence under fairly standard assumptions (Beirami et al., 2017 Koh et al. 2019). Whilst not shown here, we anticipate that such bounds can be extended to Gauss-Newton influence, as it is just spe- cialization of Newton-step influence for a certain choice of Hessian approximation. That being said in majority of settings (datasets and target coverage levels) we empirically observe that the validity of ACP-GN does hold in practice. To address concerns about validity. in Sec. Scc.4ym we propose a variant "ACP-GN (split+refine)" that is guaranteed to provide correct coverage. This uses crain-calibration split like in Split-CP along with the refinement procedure from Linearized Laplace ensuring that the residual nonconformity score expressions are exact with respect to the linearized neural network.
7

---

Published as a conference paper at ICLR 2025
4 EXPERIMENTS & RESULTS
We compare our method, approximate full-CP via Gauss-Newats influence (ACP-GN), against Lin- earized Laplace (LA) (MacKay 1992 Immer et al. 202Tb), a recently popular Bayesian method for post-hoc uncertainty quantification, split conformal prediction (SCP) (Papadopoulos et al. 2002), conformalized residual fitting (CRF) (Papadopoulos et al., (002) and conformalized quantile re- gression (CQR) (Romano et al., 2019). We also evaluate two further proposals, "ACP-GN (split refine)" and "SCP-GN" which we proceed to describe along with the aforementioned methods:
LA: The Laplace approximation with the Hessian approximated by the generalized Gauss- Newton matrix. The linearized predictive in Eq. (15) is used for inference. We use the implementation provided in the Laplace Py PyTorch library (Daxberger et al. 202 as well as to implement our ACP-GN method.
SCP: Uses absolute residual nonconformity score in the procedure outlined in Sec. 2.1
CRF: Trains an additional network to predict the absolute residuals the original network which is then used to normalize the absolute residual nonconformity score.
CQR: Trains quantile regression network using the pinball loss. The predicted lower and upper quantile functions are then used in the split conformal quantile regression algorithm.
ACP-GN: Uses the studentized nonconformity score of Eq. as we found this score performed the best.
SCP-GN: Normalizes the absolute residual nonconformity score by the posterior predictive standard deviation of the LA method (trained only on the same split as SCP) as in Eq. (19)
ACP-GN (split refine): Uses a train-calibration split like in SCP, where we pretrain the model on the training set before running ACP-GN on the calibration set. More precisely, it solves the linearized network's objective in Eq. (17) but defined the calibration set. It then uses the linearized network prediction in Eq. (15) in lieu of the original network to evaluate the CRR coefficients, again on the calibration set.
4.1 UCI REGRESSION
We conduct experiments on popular benchmark datasets for regression taken from the UCI Machine Learning repository (Nottingham et al. 2024). These vary in size and we adapt the experimental setup accordingly, placing the datasets into 3 groups for easy referencing: small (boston, concrete, energy, wine, yacht); medium (kin8nm, power); large (bike, community, protein, facebook 11, face- book_2). A subset of these are shown in Table [ and the remainder are discussed in App. I.I For the small datasets, the reported metrics result from 10 repeats of a 10-fold cross-validation process. For the other datasets, we perform 20 different train-test splits. In all cases, 90% of the examples are used for training and 10% for testing. When calibration set is needed, the training set is divided into two chunks of equal size. We show results for a desired miscoverage rate of a E {0.1, 0.05, 0.01}.
All methods neural networks trained convergence with the Adam optimizer (Kingma & Ba, 2013). Throughout, we use fully-connected layers with 50 units and GeLU activations. The small and medium datasets have a single hidden layer whereas the large datasets use 3 hidden layers. For these architectures, it is feasible to evaluate the Gauss-Newte However, we expect this be prohibitive for larger architectures- matrix scales cubically in the number of parameters. For this reason in App. J.1 we repeat the experiments using two scalable approximations: Kronecker-factoree approximate curvature (KFAC) (Martens & Grosse 2015) and last-layer approximation (Daxberger et al. (021b) (i.e. neural linear model approach (Ober & Rasmussen] 2019).. As described in Sec. 2.3 to construct the predictive intervals from the coefficients in ACP-GN use the ridge regression confidence machine algorithm (Nouretdinov et al. 2001) on the small datasets, and the asymmetric version (Burnaev & Vovk 2014) for the medium and large datasets. See App. [.] for further details the experimental setup.
matrix without any approximations.
of the Gauss-Newton
To assess the efficiency (tightness) and well-calibratedness of our proposed methods for obtaining prediction intervals, report their average prediction interval width and coverage against the base- lines in Table [T A method is reported as satisfying validity if its empirical coverage lies within the 1% and 99% quantiles of the exact marginal coverage distribution given by the train/calibration
8

---

Published as a conference paper at ICLR 2025
Table 1: Our approximate full-CP via Gauss-Newton influence (ACP-GN) almost always gives the tightest intervals in limited-data regimes whilst satisfying the target coverage (cf. yacht, boston, energy). On larger datasets, ACP-GN remains competitive on efficiency compared with other conformal methods but can sometimes miscover. As remedy, we propose two variants inspired by ACP-GN that generally fix the miscoverage issue. Average prediction interval width and coverage for our proposed approaches (shaded gray) against baselines (non-shaded) for three different settings of the confidence level. The best average widths over well-calibrated approaches (indicated by / /X) appear in bold. Reported metrics accompanied by standard error from repeated runs.
Avg. Width
Aug. Coverage
90%
95%
99%
90%
95%
99%
LA
1. 16600=00007
2.03-tao.c20
2 2.6d7=a0027
58. 73ea.s1 (V)
90.78gu.0 as (0)
93, 08.80 do (X)
SCP
2.5 2.55322000 ura
4.001 en
10:018:0:39
89. 5..56iin ox (<)
94.07 s: (f)
99. 00.32:20. 0e (V)
yacht
CRF
2. 2 o0s
3.947 1n
9:674:20m
(X)
94. 10g3:58 (/)
90. 29 (/)
N=308
CQR
1.030==0
5.8455es.uss
6560::0.044
12.422a.22 (/)
J=6
ACP-GN
2. 2.385 com
6.915
87. 97.36G2 ss (7)
50ie (7)
89:033 (X)
SCP-GN
2 2.270=
3,3 3.3.59exucos
7.216:02244
69. 85
(V)
94. 119912.52 (/)
99. 19.119 (
ACP-GN (spli) reline)
89. 30..35e
(/)
90 (/)
99. 100-55ezuee (
LA
9.338 suoos
11. 119
2120.31
97,55300113
SCP
10.635=nv122
14.500e0..71
36.
26.27121:547
89. 5..566e..2 (
84.66a (
99.11 (
boston
CRF
11.932
16.073 am2
40 am
90.0110.3
(
94.
90. 00.30 (
N=506
CQR
=1:69220.121
15.115
628
90. 10
12:3.24
99.07=0.34
I-13
9.182
12.111 10.
20.512.0000
64
85.4913.36
SCP-GN
10.301 aooss
13.41810.:5
80. a0 (/)
99.06a2.12
ACP-GN (split refine)
13. 103
16. 26.72990.
27 44
90. 12 (
95. 41.4112
99, 290200 (
LA
2 100
32.92.0.0
36,5610
SCP
1 oz
2. 2.486-40.04
3 7772
89 44 2
99. 18
energy
CRF
1. 1.923
2.464
80 10.30 2 (/)
94. 78
99. 14
N=768
CQR
1 1670=zo0
5,139e0.c29
6. 120
90 08
21
98. 96
ACP-GN
1.462:000
1.884
8.07620015
SCP-GN
2.440
600
60
20.000
ACP-GN (split + refine)
1.7 1.745enuu
2,174
3 3001-nose
90 S
84 96 (4)
99. 18 (V)
LA
100. 100.451=2.94
119.091-2455
157 31bas.00
33, 38.20020.1
Mt. M0.8330.1
=38
180.477
251
23
17
bike
CRF
137
174,362 a1 376
311 180
90.3 a.
96. 26
90.01 (
N=10,586
CQR
141 5195209500
167.682:
:3.5
244.863
60
S3 (
54. 80.004
98. 28.000 (
I=18
ACP-GN
613=1445
213 130
89. 36.336
94.41
95. 98.6720.00 (4)
SCP-GN
122 245 1.033
160.505
254 400 nor
26
09.02:3.00
ACP-GN (ppitt + refine)
128 =.3
170.762-3.49
281, 1777
28.92 (
91
99.01=300
LA
0.3851n002
11.18310.48
14 697 jomr
88 18 (
80.0010 15
94,881 10.00 (
13.041=0000
17.161
18
83.83
protein
CRF
12. 22.64722 197
16.931 10
26.973
Mi
98
N-45,73
CQR
13.5411b
14.798 10.350
18. 239 joon
90 10
95. 17..0
98. 96 0.
[=9
ACP-GN
10 24322001
13 29:94:: 50
100
87 54
93.04
us 24.24
SCP-GN
12.426-0005
16.10220.00
13
ACP-GN (splil + reline)
12 600l
16.073e00.51
S (
Olleau (
98 97
LA
06 (888 2 noc
78. 1953 200
10 4.2
97.4 4y 20 12 (X
38.013000 (A)
98.65 (A)
SCP
16 357 =0
35.387
152 100:
89.9 so.97
85.00e (
99. 99.06=2.08 (
fscebook.2
CRF
28.677920.29
326
98
99.05 99.03=a00 (V)
N=81.311
COR
17.6055p..4t
21.571 100.00
90, 16 (/)
95.
13ea.12 (
99.01=3.0 (V)
I=53
ACP-GN
18. 33033
20. 20.088
166.790 792:
90, 90
D0
05.d5am0 (A)
99.35 99.35 (1)
SCP-GN
16. 2b
10.655.0.56
118. 4.00
80. o0
09.00.3.0 (A)
(plitt refine)
42.184
2.00:2..00
14s0.o
13.0.0
set size (depending on the method) (Angelopoulos & Bates 2021 Vovk 2012). In the case of lim-
ited data regimes (yacht, boston, energy), ACP-GN gives the tighest intervals, with the exception of boston at 95% target coverage where L.A is the most efficient (being one of the few cases when LA does not miscover). On the larger datasets, ACP-GN remains competitive ception of facebook 2 at the higher values of target coverage, but we find it miscovers. Our proposed variant, "ACP-GN (split+refine)". generally gives the correct coverage albeit incurring trade-off in efficiency due to sample splitting. We also observe that our novel normalization strategy inspired by ime.0vespro....
efficiency with the ex-
ACP-GN, SCP-GN, improves over CRF for most datasets and settings of the target coverage.
4.2 BOUNDING Box LOCALIZATION
We consider single-object localization and in particular adapt the task from Phan et al. (2018). which predicts bounding boxes localizing the face of different breeds of cats and dogs in varying condi- tions. Conformal methods have recently been adapted for this task (De Grancey et al., 2022). We construct two-sided intervals similar to Timans et al.) (2024) but without considering uncertainty in the classifier, following De Grancey et al. (2022). All images with ground-truth bounding box an- notations in the Oxford-IIIT Pet dataset (Prkkh et al. 2012) are extracted resulting in 3 686 images overall. The experiment is repeated with 20 different train-test splits where 20% of the data is used for testing. When needed, 25% of the training set is reserved calibration data. The VGG-19
9

---

Published as a conference paper at ICLR 2025
Table On a bounding box regression task using a deep convolutional neural network, our split and refine variant of ACP-GN results in the most efficient confidence regions whilst achieving compara- ble coverage to the split-CP baselines. We target coverage rates of (85%, 90%, 95%} and reported metrics are accompanied by standard error from repeated runs.
Avg. Volume (x10-²)
Avg. Coverage
85%
90%
95%
85%
90%
95%
LA
0.710 009
0.945 013
92.11 1.4
(X)
94.49 94.49...1 (X)
96.6520.10 (X)
SCP
0.800
1.16620.00
2.261 106
87. 87.8020.42 (V)
91.82=0.41 (
95.85 (V)
CRF
0.713
1.098
87.47=0.41 2.130
(V)
91.61+0.34
25.85=0.23 (
CQR
0.947 2: das
1.451 20 24.045
3. 1.6802o.133
87.45
(V)
01.29 (
96.06200 (
ACP-GN
0.384420.00
0.60520.007 007
1.22520.017
90.97:20:20 (X)
94.0910.20 (X)
27.41 (2)
SCP-GN
0.768
10071
1.85-=0.000
87.17=0.45 (
91.43+0.40
95.58+0.25
ACP-GN (split + refine)
0.311 20.0000 005
0.472=0.000
1,031
87.342044 (V)
91.314030 (
96. 22:0022 (V)
chitecture is used as the object detection backbone but with the original output layer removed. The network is trained jointly with two heads, a regression head predicting 2D bounding box coordinates (4 outputs) and a binary classification head. We only consider the regression head for constructing predictive intervals. Without a calibration split, the model gets 99.6% classification accuracy and 20.1% localization error with 0.5 IoU (Intersection over Union) threshold. With a calibration split, the model achieves 99.5% classification accuracy and 27.5% localization error.
We use the last-layer approximation to the Gauss-Newton matrix throughout for computational rea- sons. The asymmetric implementation of CRR is used due to its efficiency and we target miscov- erage rates a E {0.15, 0.1, 0.05). See App. I.2 for further experimental details. Since bounding box localization is type of multi-output regression, we obtain confidence regions given by hy- perrectangles except for LA that results in a hyperellipsoid. All conformal prediction methods are run for each output dimension independently and we evaluate the confidence region volumes by taking the product over interval widths per output dimension. We apply a multiple testing correc- tion, the Bonferroni correction, to mitigate the miscoverage that arises when conformalizing the outputs separately. However, we find that all methods still consistently overcover suggesting further improvements are possible.
In Table 2 we observe that ACP-GN gives the tightest intervals as compared with the baseline conformal methods despite having greater empirical coverage than those methods. Surprisingly our split and refine variant of ACP-GN gives even tighter intervals whilst matching the coverage of the conformal baselines. We observed a similar effect in our ablation of the previous UCI experiments with the last-layer approximation in App. J.1
5 CONCLUSION
In this work, we show how to efficiently construct prediction intervals with full conformal prediction (CP) for neural networks in regression tasks. While full-CP requires retraining the model from scratch all of the training data and for each postulated label for the test point, we show one can efficiently approximate the full-CP predictive intervals with a specialization of Newton-step influence (Pregibon, 1981 Beirami al. 2017) and the ridge regression confidence machine of Nouretdinoy et al. (2001) without retraining the model. In doing so, we also avoid relying on a grid over all possible labels for the test point, which incurs an undesirable accuracy/preccsion trade- off due to the uncountable set of real numbers. We demonstrate how this approach corresponds to exact full-CP on a linearized version of the neural network and further show how it corresponds to "conformalizing" the Linearized Laplace method (Khan et al.] 2019 [mmer et al., (0216), popular Bayesian approach for post-hoc uncertainty estimation in deep learning. Finally, through the lens of normalized nonconformity scores, we recover the leave-one-out variety of full-CP and casily extend to studentized scores that we find performs the best empirically and was left as future work in Martinez et al. (2023). This also Ieads to propose a novel adaptive split-CP method similar to conformalized residual fitting (Papadopoulos et al., 2002) but without the need to train an additional network. Empirically, we see that approximate full-CP methods typically provide tighter prediction intervals limited data regimes across the well- well-calibrated approaches. For future work, we would like to extend our method other real-world tasks such as pose estimation and tracking, and develop further the theoretical analysis.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Ahmed Alaa and Mihaela Van Der Schaar. Discriminative Jackknife: Quantifying Uncertainty in Deep Learning via Higher-Order Influence Functions. In International Conference on Machine Learning. 2020.
David Allen. The Relationship between Variable Selection and Data Agumentation and a Method for Prediction. Tèchnometrics, 1974.
Anastasios N Angelopoulos and Stephen Bates. A Gentle Introduction to Conformal Prediction and Distribution-Fire Uncertainty Quantification. ArXiv e-prints, 2021.
Javier Antorán, David Janz, James Urquhart Allingham, Erik Daxberger, Riccardo Barbano, Eric Nalisnick, and José Miguel Hernández-Lobato. Adapting the Linearised Laplace Model Evidence for Modern Deep Learning. In International Conference on Machine Learning. 2022.
Juhan Bac, Nathan Ng. Alston Lo, Marzych Ghassemi, and Roger B Grosse. If Influence Functions are the Answer, Then What is the Question? In Advances in Neural Information Processing Systems, 2022.
Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+. The Annals of Statistics, 2021.
Samyadeep Basu, Xuchen You, and Soheil Feizi. On Second- Oodee Group Influence Functions for Black-Box Predictions. In International Conference on Machine Learning, 2020.
Ahmad Beirami, Meisam Razaviyayn, Shahin Shahrampour, and Vahid Tarokh. On Optimal Gener- alizability Parametric Learning. In Advances in Neural Information Processing Systems, 2017.
Evgeny Burnaev and Vladimir Vovk. Efficiency of conformalized ridge regression. In Conference on Learning Theory, 2014.
Samprit Chatterjee and Ali S Hadi. Influential Observations, High Leverage Points, and Outliers in Linear Regression. Statistical Science, 1986.
Wenyu Chen, Kelli-Jean Chun, and Rina Foygel Barber. Discretized conformal prediction for effi- cient distribution-fii inference. Stat, 2018.
R Dennis Cook. Detection of Influential Observation in Linear Regression. Technometrics, 1977.
Dennis Cook and Sanford Weisberg. Characterizations of an Empirical Influence Function for Detecting Influential Cases in Regression. Technometrics, 1980.
A Philip Dawid. The Well-Calibrated Bayesian. Journal of the American Statistical Association, 1982.
Erik Daxberger, Agustinus Kristiadi, Alexander Immer, Runa Eschenhagen, Matthias Bauer, and Philipp Hennig. Laplace Information Processing Systems, 2021a.
Bayesian Deep Learning. In Advances in Neural
Erik Daxberger, Eric Nalisnick, James Allingham, Javier Antorán, and José Miguel Hernández- Lobato. Bayesian Deep Learning via Subnetwork Inference. In International Conference on Machine Learning. 2021b.
Florence De Grancey, Jean-Lue Adam, Lucian Alecu, Sébastien Gerchinovitz, Franck Mamalet, and David Vigouroux. Object Detection with Probabilistic Guarantees: A Conformal Prediction Approach. In International Conference on Computer Safety, Reliability, and Security, 2022.
Bradley Efron and Robert Tibshirani. Bootstrap Methods for Standard Errors, Confidence Intervals, and Other Measures of Statistical Accuracy. Statistical Science, 1986.
Edwin Fong and Chris C Holmes. Conformal Bayesian Computation. Advances in Neural Informa- fion Processing Systems, 2021.
11

---

Published as a conference paper at ICLR 2025
Matteo Fontana, Gianluca Zeni, and Simone Vantini. Conformal Prediction: Unified Review of Theory and New Challenges. Bernoulli, 2023.
Andrew YK Foong, Yingzhen Li, José Miguel Hernández-Lobato, and Richard E Turner. 'In- Between' Uncertainty in Bayesian Neural Networks. ICML Workshop on Uncertainty and Robustness in Deep Learning, 2019.
Fraser. Bayes Posterior just Quick and Dirty Confidence? Statistical Science, 2011.
Ryan Giordano, Michael Jordan, and Tamara Broderick. A Higher-Order Swiss Army Infinitesimal Jackknife. ArXiv e-Prints, 2019a.
Ryan Giordano, William Stephenson, Runjing Liu, Michael Jordan, and Tamara Broderick. A Swiss Army Infinitesimal Jackknife. In International Conference on Artificial Intelligence and Statistics, 2019b.
Girshick. Fast R-CNN. ArXiv e-Prints, 2015.
Peter Grünwald and Thijs van Ommen. Inconsistency of Bayesian Inference for Misspecified Linear Models, and Proposal for Repairing It. Bayesian Analysis, 2017.
Etash Kumar Guha, Shlok Natarajan, Thomas Möllenhoff, Mohammad Emtiyaz. Khan, and Eugene Ndiaye. Conformal Prediction via Learning Representations, 2024.
In International Conference
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified Data Removal from Machine Learning Models. In International Conference on Machine Learning, 2020.
Frank R Hampel. The Influence Curve and its Role in Robust Estimation. Journal of the American Statistical Association, 1974.
Lars Kai Hansen and Jan Larsen. Linear unlearning for cross-validation. Advances in Computational Mathematics, 1996.
Alexander Immer, Matthias Bauer, Vincent Fortuin, Gunnar Rätsch, and Mohammad Emtiyaz Khan. Scalable Marginal Likelihood Estimation for Model Selection in Deep Learning. In International Conference on Machine Learning, 2021a.
Alexander Immer, Maciej Korzepa, and Matthias Bauer. Improving Predictions of Bayesian Neural Nets via Local Linearization. In International Conference on Artificial Intelligence and Statistics, 2021b.
Tommi Jaakkola and David Haussler. Exploiting Generative Models in Discriminative Classifiers. In Advances in Neural Information Processing Systems, 1998.
Arthur Jacot, Franck Gabricl, and Clément Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In Advances in Neural Information Processing Systems, 2018.
Louis A Jaeckel. The Infinitesimal Jackknife. Technical report, Bell Lab., 1972.
Yuko Kato, David MJ Tax, and Marco Loog. A Review of Nonconformity Measures for Conformal Prediction in Regression. Conformal and Probabilistic Prediction with Applications, 2023.
Mohammad Emtiyaz Khan and Håvard Rue. The Bayesian Learning Rule. Journal of Machine Learning Research, 2023.
Mohammad Emtiyaz Khan, Alexander Immer, Ehsan Abedi, and Maciej Korzepa. Approximate Inference Turns Deep Networks into Gaussian Processes. In Advances in Neural Information Processing Systems, 2019.
Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference Learning Representations, 2015.
12

---

Published as a conference paper at ICLR 2025
Pang Wei Koh and Perey Liang. Understanding Black-Bo Predictions via Influence Functions. In International Conference on Machine Learning, 2017.
Pang Wei Koh, Kai-Siang Ang, Hubert Teo, and Percy S Liang. On the Accuracy of Influence Functions for Measuring Group Effects. Advances Neural Information Processing Systems, 2019.
Roy Laurent and Dennis Cook. Leverage and Superleverage in Nonlinear Regression. Journal of the American Statistical Association, 1992.
Cessie and J van Houwelingen. Ridge Estimators in Logistic Regression. Journal of the Royal Statistical Society Series C: Applied Statistics, 1992.
Jing Lei. Fast Exact Conformalization of Lasso using Piecewise Linear Homotopy. Biometrika, 2019.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution- Free Predictive Inference for Regression. Journal of the American Statistical Association, 2018.
David C MacKay. A Practical Bayesian Framework for Backpropagation Networks. Neural Com- putation, 1992.
Wesley Maddox, Shuai Tang, Pablo Moreno, Andrew Gordon Wilson, and Andreas Damianou. Fast Adaptation with Linearized Neural Networks. In International Conference on Artificial Intelli- gence and Statistics, 2021.
James Martens, Deep learning via Hessian-free optimization. In International Conference on Ma- chine Learning, 2010.
James Martens and Roger Grosse. Optimizing Neural Networks with -rotecker-factored Approxi- mate Curvature. In International Conference on Machine Learning, 2015.
Javier Abad Martinez, Umang Bhatt, Adrian Weller, and Giovanni Cherubin. Approximating Full Conformal Prediction at Scale via Influence Functions. In AAAI Conference on Artificial Intelli- gence, 2023.
Thomas Melluish, Craig Saunders, Ilia Nouretdinov, and Volodya Vovk. Comparing the Bayes and Typicalness Frameworks. In European Conference on Machine Learning, 2001.
Gaétan Monari and Gérard Dreyfus. Withdrawing an example from the training set: An analytic estimation of its effect on a non-linear parameterised model. Neurocomputing, 2000.
Fangzhou Mu, Yingyu Liang, and Yin Li. Gradients as Features for Deep Representation Learning. In International Conference on Learning Representations, 2020.
Eugene Ndiaye. Stable Conformal Prediction Sets. In International Conference on Machine Learn- ing, 2022.
Eugene Ndiaye and lchiro Takeuchi. Computing Full Conformal Prediction Set with Approximate Homotopy. In Advances in Neural Information Processing Systems, 2019.
Peter Nickl, Lu Xu, Dharmesh Tailor, Thomas Möllenhoff, and Mohammad Emtiyaz Khan. The Equation: Understanding Model's Sensitivity to Data. In Advances in Neu- ral Information Processing Systems, 2023.
Kolby Nottingham, Rachel Longjohn, and Markelle Kelly, UCI Machine Learning Repository, 2024. URL https::/archivee ics. uei, edu/ datasets Accessed: September, 2024.
Ilia Nouretdinov, Thomas Melluish, and Volodya Vovk. Ridge Regression Confidence Machine. In International Conference on Machine Learning, 2001.
Roman Novak, Jascha Sohl--iccsttei, and Samuel S Schoenholz. Fast Finite Width Neural Tangent
Kerne.. In International Conference Machine Learning, 2022.
13

---

Published as a conference paper at ICLR 2025
Sebastian W Ober and Carl E Rasmussen. Benchmarking the Neural Linear Model for Regression. In Second Symposium on Advances in Approximate Bayesian Inference, 2019.
Harris Papadopoulos. Guaranteed Coverage Prediction Intervals with Gaussian Process Regression. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Harris Papadopoulos and Haris Haralambous. Reliable Prediction Intervals with Regression Neural
Networks. Neural Networks, 2011.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive Confidence Machines for Regression. In European Conference on Machine Learning, 2002.
Harris Papadopoulos, Alex Gammerman, and Volodya Vovk. Normalized nonconformity measures for regression conformal prediction. In International Conference on Artificial Intelligence and Applications, 2008
Harris Papadopoulos, Vladimir Vovk, and Alex Gammerman. Regression Conformal Prediction with Nearest Neighbours. Journal of Artificial Intelligence Research, 2011.
Omkar M Parkhi, Andrea Vedaldi, Andrew Zisserman, and CV Jawahar. Cats and Dogs. In IEEE Conference on Computer Vision and Puttern Recognition, 2012.
Buu Phan, Rick Salay, Krzysztof Czarnecki, Vahdat Abdelzad, Taylor Denouden, and Sachin Vernekar. Calibrating Uncertainties Object Localization Task. ArXiv e-Prints, 2018.
Daryl Pregibon. Logistic Regression Diagnostics. The Annals of Statistics, 1981.
Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating Training Data Influence by Tracing Gradient Descent. In Advances in Neural Information Processing Systems, 2020.
Kamiar Rahnama Rad and Arian Maleki. A scalable estimate of the out-of-sample prediction error via approximate leave-one-out cross-validation. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2020.
Hippolyt Ritter, Aleksandar Botev, and David Barber. A Scalable Laplace Approximation for Neural Networks. International Conference on Learning Representations, 2018.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized Quantile Regression. In Advances in Neural Information Processing Systems, 2019.
Peter Schulam and Suchi Saria. Can You Trust This Prediction? Auditing Pointwise Reliability After Learning. In International Conference on Artificial Intelligence and Statistics, 2019.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember What You Want to Forget: Algorithms for Machine Unleaming. In Advances in Neural Information Processing Systems, 2021.
Glenn Shafer and Vladimir Vovk. A Tutorial on Conformal Prediction. Journal of Machine Learning Research, 2008
Karen Simonyan and Andrew Zisserman. Very Deep Convolutional Networks for Large-Scale Image Recognition. In International Conference on Learning Representations, 2015.
Stefano Teso, Andrea Bontempelli, Fausto Giunchiglia, and Andrea Passerini. Interactive Label
Cleaning with Example-based Explanations. Advances in Neural Information Processing Sys- tems, 2021.
Alexander Timans, Christoph-Nikon Nikolas Strachle, Kaspar Sakmann, and Eric Nalisnick. Adaptive Bounding Box Uncertainties via Two-Step Conformal Prediction. In European Conference on Computer Vision, 2024.
Vladimir Vovk. Conditional Validity Inductive Conformal Predictors. In Asian Conference on Machine Learning, 2012.
14

---

Published as a conference paper at ICLR 2025
Vladimir Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 2015.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic Learning in a Random
World. Springer, 2005.
Larry Wasserman. Frasian Inference. Statistical Science, 2011.
Bo-Cheng Wei, Yue-Qing Hu, and Wing-Kam Fung. Generalized Leverage and Applications. Scandinavian Journal of Statistics, 1998.
15

---

Published as a conference paper at ICLR 2025
A DERIVATION OF CRR COEFFICIENTS
The ridge solution on D is given by 0, = ' where X is the (N x 1) feature matrix with x and y is the N-dim vector of targets. We express the ridge solution DN+1 (v), referred to as the add-one-in (AOI) solution, as a deviation from 0.:
0 (v) (H, + x (X use Sherman-Morrison formula
+
(20)
H H. XN+ I H.
y + XN+18)
(21)
N+1 H. XN+1
x H. X y
yx N+ H. XN+1
= HH + H XN+1 1/
(22)
x+ H. XN++1
1 1+ H. XN+1
substitute 0, = H - y and hN41 x H XNN+1
x X4+10. 0.
yhN+1
=0 + HH,1x++1
y 1 1+ hN+1
(23)
1 hN+1
y x 1 0
0, + H, XN+1
(24)
1+ hN+1
Using this, is easy show the residuals can be expressed in terms of the postulated label y:
y 1 0.
yi x (t) = yi x. 0. - x, '
xN+1
(25)
1 + hN+1
& substitute hg,N41 = x, 1NN++++1
hg,411
hG,N+1 y
Yi x: 0, + 1+ hN41
Xx+10.
(26)
1 + hN+1
1/ x 0.
y -- NN 0: (y)
x x 0. x H. XN-1
(27)
1 + hN+1
& substitute hy-1
x x H. 1x11
x X 0, +
(28)
1+ 1+ hN+1
1 h+
B DERIVATION OF GAUSS-NEWTON INFLUENCE
The first two steps are similar to the usual derivation of Newton-step influence (Beirami et al. 2017) except that a single Newton step is performed on the augmented problem defined in Eq. 4 starting from 0.. For brevity, we define L( = -EN E(y,, f()) + 1 ||0| as the empirical risk on DN- (V.I(0.)) + Volly.fv substitute first-order stationarity condition VoL(0.)
(v) 0, (O.) +
(29)
0. (V)I
(0.))) -1 (oll) (oo(u.
(30)
use NewssnNeeton approximation to Hessian
R3 0, (HGN + @N+11 (1+11N+11) fol(y, (N+1
(31)
b expand the loss gradient on the (N + 1)th example by chain rule
= 0, + HHN + (N++ -1
(N+1IN++1y))
(32)
use -Morrinn formula
(N+1(y)
0. 1 hN41
(33)
16

---

Published as a conference paper at ICLR 2025
C DERIVATION OF ACP-GN COEFFICIENTS
We present the derivation for expressing the residual in the neural network regression setting as a linear function of the postulated label y.
yi f= (w))
(34)
linearize neural network about 0,
R y/ - [0. VO.)(0.) (0) - 0.)]
(35)
approximate (v) ~ 0 (y) and substitute Gauss-Newton influence
( HONDN+1
y/ f(..) Φ5
(36)
1 hN+1
definition of residual (x4 to reveal postulated label y and substitute hLN+1 of
H
GN
N++1
V/ - fi(O.) + h (N+)
h
(37)
hx+1
1 hN-1
The residual of the postulated point proceds in an almost identical manner.
D EXTENSION OF ACP-GN FOR MULTI-OUTPUT REGRESSION
In the case of multi-output regression with vector-valued targets y; E RO and outputs of DNN f, (0) E IR, the coefficients needed in the CRR procedure {a,, B now correspond to a O-dim vector and O x O matrix respectively. Since CRR was only proposed for single-output regression, also need to adapt the procedure. Considering the asymmetric version of CRR (Burnaev & Vovk 2014 we simply need to solve for the O-dim changepoints which are given by (B B, a, aw+1) long BN+1 B, is positive-definite (generalizing the positivity constraint in the single-output case). Then we propose to sort the set of changepoints followed by taking the quantile component-wi wiise analogous to the existing algorithm. Now proceed derive (a;, B.). Firstly the multi-output analogue of the AOI estimator in Eq. (12 is given by,
(-(r) 0_ + H N+1
(I
V
V++1 ex+1
(38)
where 4; = (o.) E ROXD, HaN = Σ T T. + ōI, ( = y (0.) and
V VN+I- 4 + H + N+ There is a change in notation in the last expression of the multi-output
leverage score to avoid confusion with the Hessian. Using this we can derive analogous expressions to Eqs.
13 and (14):
f(( = y [E((.)) + Vof((O.) (0: -v) -0)))
(39)
= y. - f((0.) H 2 N+ [I+ V VN+1) (x-)(y)
(40)
y; f((0.) + V. (I NN41) ( (0.)
(41)
a: V [I VN+1)= y
B.
and
- fN+1 (x:1((0(()) ~ -
-(I (I+ VN+1) - (0.)
(I V N11
(42)
SN+1
T T where V T L N+1- The normalized nonconformity scores can also be extended the
multi-output setting. In the case of deleted-CRR, we have:
a; <- VV-V.) a; B, t B.+(I-
(--I-V (I) B Vi 1, 1...,, N
(43)
17

---

Published as a conference paper at ICLR 2025
where,
V, V, (I+ VN+1) VVT V VN+1 (I+ VN+1)=
i,4+1 Yi WI
(44)
(45)
and we introduced V. HoH T..
E DERIVATION OF APPROXIMATE ADD-ONE-IN POSTERIOR WITH LAPLACE-GGN
Khan et al. (2019) show that the Laplace-GGN posterior can be equivalently stated as exact inference the following linear regression model (see their Theorem 1):
(0) III
") p(0)
(46)
where p00) x (xp(561101)) o; == Vofi(O.) and ÿi == o. 0. + e; with e; = y1 - f.(0.). This can be viewed as approximating the original non-conjugate terms by conjugate factors (see
Sec. 5.4 in (Khan & Rue )023)): ): e (0())..(00)) = e - ( 0)² which take similar interpretation site functions in expectation propagation. This used along with the standard formula for online Bayesian updating to derive the approximate AOI posterior q_ (0) 2o (0)).+)).
N+1
p(0 D N41 & II
(Nn p(O)
(47)
1=1
I> split off the (N + 1)th likelihood from the others
c (19.
Am (0)) p(0)
(48)
1=1
b apply the Laplace-GGN posterior approximation e ===iiu.f++110 (0)
(49)
approximate the (N + 1)th likelihood by its site function
ee- - + 0) q. (0)
(50)
this corresponds to an unnormalized Gaussian distribution
N( (v), (1),
(51)
F MULTI-OUTPPT REGRESSION PREDICTION INTERVALS
For Bayesian posterior predictive distribution (under Gaussian assumptions) in the multi-output case, p(y.|xx. D) = N(y-ly,, ). the confidence region is given by an ellipsoid,
(x.)) = (y RR (y --) - - y.) < xO.a}
(52)
where X2.0 is the quantile function for the chi- chi-squared distribution with degrees of freedom. Using this definition, it is straightforward to evaluate empirical coverage. Efficiency is then given by the volume of the corresponding ellipsoid,
(x..) = (x3..) 4 det(E,,) Vol[Bo]
(53)
where Bo is the unit ball with O dimensions.
18

---

Published as a conference paper at ICLR 2025
Table We have number of test points (M), number of grid points (K), number of train points (N), parameter count (D), total epochs (E), and cost of forward pass/gradient computation//acooian computation ()..). We highlight the additional complexity of FCP over ACP-GN CCP-GN (purple), ACP over ACP-GN (green), ACP-GN over ACP (blue) and ACP/ACP-GN over FCP (red).
Train
Predict
FCP
MKN'E(FP)
ACP
NEEP + N + D NE[PP] + ND* D
MK(FP)) + 2
ACP-GN
M([PP) + N + log N)
G TIME COMPLEXITY: FCP VS. ACP-GN
We write the time complexity for our ACP-GN and compare it against full conformal prediction (FCP) and approximate full conformal prediction (ACP) (Martinez et al. 2023) in Table 3 This is shown for the deleted nonconformity score similar to Sec. A.2 in Martinez et al. 2023) and for scalar targets only. For the standard score, ACP and ACP-GN are unchanged but the factor of N is dropped in FCP. "Train" refers to the upfront time complexity that can be re-used when constructing prediction intervals ("predict") for new batches of test points.
We state the best time complexity of the ridge regression confidence machine routine given the co- efficients {aa d, as (N log N) (see Sec. 2.3 in (Vok et al. 2005)). This is the same as the asymmetrie implementation of Burnaev Vovk (2014) shown in Alg. 2 (sorting the N change- points). The cost of network prediction (single forward pass) is irchtteturre-deendeer but since this is constant across the methods we do not expand on this here. We also regard the cost of gradient and Jacobian computation comparable to forward pass (see the discussion in App. D in Novak eet al. (2022)).
FCP has complexity multiplicative in the number of test points, grid points, train points (twice) and epochs. Whereas for ACP-GN, it is just multiplicative in the number of test points, given an upfront cost which is cubic in the number of parameters. We can further reduce the time complexity for ACP-GN when scalable approximations to the Gauss-Newton Hessian are used (as investigated in App.[.]] J.I). These extensions could also be adapted for ACP which was in fact left as future work in Martinez et al. (2023). This is shown in Table 4 for the cases of Kronecker faaetrfd approximate curvature (KFAC) and last-layer approximation (LL). Crucially, both these approximations relax the cubic dependence on the parameter count P which often exceeds millions of parameters for modern
architectures. Instead, the cubic dependence shifts to the input and output dimensionality of the network layers in the case of KFAC or just the last layer, which are typically far smaller than P.
Table We have number network layers (L), layer input/output dimensionality (1,,n//,,ou) cost of Gauss-Newton Hessian evaluation//nversion (Hx) along with its KFAC (H and last-layer (HI approximation, and cost of operations related to Gauss-Newton influence in the KFAC case [NN Other terms are defined in Table 3
Train
Predict
ACP-GN
F + HN"
M([F P| + ND2 + N log N)
ACP-GN(kfue)
NEFPP + H b
M(FP) + IN F ff + N log M(FPP] + NI2. + N log N)
ACP-GN(LL)
NEFPP + HN
"HN = N.FP + ND D3
bH -[FP]] [IFP]+10 + NN)++N33 >Σ=1(1 (12, + (R + Ete (1i + +
"H = -N[FP]+ + N L. + 13
"/NNF = D 1 (Ir,utt Pu + Jr.n J. P.ow))
19

---

Published as a conference paper at ICLR 2025
H RELATED WORK
There are approaches based on data splitting such as Split-CP (Papadopoulos et al. 2002 Lei al. 2018) and cross-conformal predic- tion (Vovk) 2015 Barber et al., (021). Such approaches greatly reduce the number of models that need be trained (in the case of Split-CP just one), but this comes at the expense of statistical effi-
Computationally efficient versions of conformal prediction
ciency. There are also normalized variants of split-CP (Papadopoulos et al., 2008)) and other exten- sions in the regression setting such as conformalized quantile regression (Romano et al. 2019) and gegressonn-o-cllassfcaati
CP (Guha et al. 2024). For certain model classes, computationally effi
cient implementations of full-CP exist such as ridge regression (Nouretdinov et al., 2001 [urnacy & Vovk 2014). Lasso regression (Lei 2019) and k-Nearest Neighbours Regression (Papadopou-
los et al. 2011). For more general settings, there are approaches based on homotopy continuation
method (Ndiaye& & Takeuchi 2019) and algorithmic stability Ndiayel (2022). The method of Mar-
tinez et al. (2023) is closely related to ours where they use influence function (Jaeckel] 1972] Cook & Weisberg, 1980) to approximate the retraining step in the full-CP algorithm. However, they only consider classification problems and their solution still requires an exhaustive search over possible labels. which is unfeasible for the regression setting we consider in this paper. A related approach is Alaa & Van Der Schaar (2020) that used higher-order influence functions to approximate leave-one- out retraining in jackknite+ (Barber et al. 2021) and [Schulam & Saria (2019) that approximates the bootstrap (Efron & Tibshirani 1986) using similar sensitivity-basee techniques.
Influence functions These are a family of techniques that estimate the effect on the model of deleting single example (or group of examples) from the training set, without the computationally prohibitive cost of retraining the model. There are two main approaches, the first is the infinitesimal jackknife (IJ) or simply influence function that the wider family of techniques takes its namesake.
This was first proposed in robust statistics (Jaeckel 1972 Hampel| 1974) and then was introduced as an influence measure for regression diagnostics and outhier detection in Cook Weisberg (980). It was popularized in deep learning by Koh & Liang 2017) focusing on diagnosing model errors and data attribution. The other approach, that we use this work, is the Newton-step (NS) influence which was first proposed in Pregibon| (188T) for logistic regression and generalized to more general losses and regularizers in Beirami et al. (2017). Closely related to our use case, influence functions have been used to approximate cross-validation: IJ in Giordano et al. (2019b) and NS influence in le Cessie & van Houwelingen [ Beirami et al. (2017)))) Rad & Maleki (2020). They have also been proposed for machine unlearning: 10 in Guo et al. (2200) and NS influence in Sekhari et al.
(202T). Influence functions derived using higher-order Taylor approximations have been proposed (Giordano et al./ 2019a; [Basu et al., 2020).. Many recent works have focused on scaling IJ such as Fisher information matrix (Teso et al. (022)) or generalized Gauss-Newton (Bae et al., (222) ap- proximations the Hessian, measures defined using only gradients (Pruthi et al.] 20200). Similar techniques to our Bauss-Newtee influence (in the leave-one-out setting) have appeared in past works
(Laurent & Cook 1992 Hansen & Larsen 1996; Monari & Dreyfus 2000).
Network lincarization
The use of gradients or Jacobians as features first appeared in Jaakkola & Haussler (1988) which they called "Fisher vectors". Such features have been demonstrated for fast adaptation (Maddox et al., (001)) transfer learning (Mu et al. (2020) and improving predictions in Bayesian neural networks (Immer et al. 2021b). This local linearization has received much attention in recent years due to the neural tangent kernel (Jacot et al. 2018) of which its width variety can be viewed as the kernel analogue of Fisher-vectors.
I EXPERIMENTAL DETAILS
1.1 UCI REGRESSION
For every dataset, both the input features and targets are standardized to have zero mean and unit variance. We use a batch size of 256 in SGD training with initial learning rate of 10-2 that is decayed to 10 using a cosine schedule. All methods require tuning the L2 regularizer/prior preci- sion. Additionally, for Linearized Laplace we have the observation noise. For the small and medium datasets, these are tuned using online marginal likelihood optimization (Immer et al. (021a) that alternates between standard neural network training and gradient-based updates to the hyperparam-
20

---

Published as a conference paper at ICLR 2025
Table We repeat the bounding box experiment in Table 2 but with 50% calibration split.
Avg. Volume (x100 2)
Avg. Coverage
90%
95%
90%
915%
LA
0.710
0. 0.945:1..0
1.405
92.1140.1 (7)
84.494o.11 (X)
96.65
SCP
=0.77
1.723
3.137=0.081
87.36
(K)
(2)
95.91=0.19 (V)
CRF
1.248
1 1.90020.0e 944
3.781 20.002
87.4820.34 (X)
91.9610.20 (X)
96, 06.02220.0 (V)
CQR
1.627
2.739:0.00
7.971
87.46620.1
(X)
91.42+0.28
95.97=0.14
ACP-GN
0.381=0.00
0, 1.005=0.000 007
1.225=0.017
90,97+0.20 (X)
94.09:+0220 (X)
97.41=0.16 (8)
SCP-GN
1.149
1.615=20.00 004
2.64132..044
86, 26 (
91.35::0.11 (/)
95. 95.56.0.21 (V)
ACP-GN (split + refine)
0.565 006
0.556-2..10
1.104 022
87.7820.37 (X)
91.75:20:31
95.6220.17 (V)
ACP-GN
SCP
CRF
CQR
ACP-GN
SCP-GN
(split-refine)
Figure 2: Demonstration of our method (starting 3rd from right) for object localization alongside common conformal prediction baselines. The two-sided prediction regions are shown in green and neural network prediction is shown in red.
eters using the differentiable marginal likelihood estimate. We use layerwise structure in the prior precision. The marginal likelihood estimate also used for early stopping. The prior precision and observation noise initialized 1. Overall, using Adam optimizer we run for 5000 epochs with hyperparameter learning rate of - decayed to 10 10-3 using a cosine schedule, 100 burn-in epochs, and take 50 hyperparameter steps on single marginal likelihood evaluation every 50 epochs.
For the large datasets, the (scalar) prior precision is tuned via grid-search for each order of magnitude from 10- to 10 10% of the training set is used for validation and once the best prior precision is found, the network is retrained on full training set. The observation noise is fit to the training data via maximum likelihood after training.
We follow the above procedure for all methods except "ACP-GN (split refine)" where we first train with L2 regularizer fixed to 8/N 10-4, For the small datasets, the hyperparameters are tuned via post-hoc marginal likelihood training with 5000 steps and the same learning rate schedule described earlier. In Fig. we
we demonstrate the trade-off between coverage and efficiency in the split variant of ACP-GN GN. We set the sensitivity hyperparameter (3) of CRF (see Eq. 16 in (Papadopoulos 1 as used in Romano al. (2019). The additional network is identical to the original one and re-uses the same hyperparameters and training configuration. It is worth mentioning that the original proposal of CRF in the context of neural networks (Papadopoulos al.,
Haralambous 201T))
2002) used ridge regression model to predict residuals.
The quantile regression network CQR uses the same architecture as that used in the other methods except there are two output units. As done in CRF, hyperparameters from SCP are re-used along with the training configuration. Rather than retraining for each desired significance level, the output layer is appended with additional units and trained jointly. We do not perform tuning of the quantiles so it is expected the intervals can be made more efficient (Romano et al. 2019).
Results on additional UCI datasets reported in Table 8 Furthermore, in Table 9 and 10 we repeat all experiments with 25% calibration split.
1.2 BOUNDING Box LOCALIZATION
The training setup is adapted from Girshick (015) using SGD optimizer and simple data augmenta- tion involving random horizontal flips of probability 0.5. The robust L1 loss is used for the bounding box regression head and logistic loss for the classification head. With L1 loss, Eqs. (12) to (14) no longer hold but we demonstrate the efficacy of our procedure when the objectives for training and predictive interval construction differ.
21

---

Published as a conference paper at ICLR 2025
Images resized 224 224 followed by scaling the pixel values [0, 1] and then normalizing to statistics computed from the ImageNet dataset as required by the pretrained VGG-19 backbone (Simonyan & Zisserman 2015). Bounding box coordinates denote the top-left and bottom-right corners and are scaled to (,, 1J. The reported volumes use the standardized targets. A demonstration is shown in Fig. 2
For SGD training we use a batch size of 128 for 200 epochs and an initial learning rate of 10-2. A learning rate schedule used that takes incremental steps towards the base learning rate for the first 5 epochs (warm-up) and then decays to 0 using a cosine schedule. The SGD optimizer uses nesterov momentum 0.9 and weight decay 5 x 10-4 At inference with squared- hoc finetuning of hyperparameters (regularization coefficient, observation noise) using the marginal likelihood. This is optimized using Adam for 250 epochs with learning rate of 10-1, For LA, we use the expressions outlined in App. Fo to evaluate the volume and coverage.
loss, we perform post-
Due to the last-layer approximation, the off-diagonal entries of the O O multi-output leverage scores are zero. We can understand this by realizing the Jacobian of an output with respect to parameter tied to different output is zero. Due to this inherent output independence, we can simply use the expressions given in the single-output case in parallel over the output dimensions rather than use the expressions derived for the multi-output setting in App.
When training the additional network in CRF and the quantile regression network in CQR, the backbone parameters are initialized to those of the original network and not updated. They are trained in similar fashion except for 100 epochs, without warm-up in the learning rate schedule and without data augmentation. The sensitivity hyperparameter (3) CRF is set to 0.01 after trying few different values single seed.
In Table 5 we repeat the experiment but with 50% calibration split. In this case the model achieves 99.4% classification accuracy and 37.0% localization error.
J ADDITIONAL EXPERIMENTS
J.1 ABLATION WITH SCALABLE APPROXIMATIONS TO THE GAUSS-NEWTON MATRIX
For most deep architectures, storing and inverting the full Gauss-Newton matrix is infeasible. We investigate two choices for scalable approximations to the Gauss-Newton matrix in the context of our experiments involving the large UCI datasets. These are inspired by two popular choices for scalable Laplace approximations.
The first is the use of Kronecker-factored approximate curvature (KFAC) (Martens & Grosse 2015) as an approximation to the GN. By approximating each layer's Gauss Newton independently as Kronecker product, this leads to a plock-diagonal factorization for the overall GN matrix enabling efficient storage and computation of inverses. We use the specific form proposed in Immer et al. (2021b) that performs an eigendecomposition of the Kronecker factors and avoids the "dampening" approximation of Ritter et al. (2018). With regards to refinement, we observed that the one-step solve with KFAC approximation performs much worse than without refinement. Hence, we instead take a gradient-based approach as outlined in Antorán et al. (2022) optimizing the linearized network's 's objective using a similar configuration to the original NN training. The linearized network's loss gradients are evaluated without explicitly instantiating Jacobians via vector-Jacobian and Jacobian- vector products.
The results are shown in Table II For LA, we observe that KFAC leads to slightly tighter intervals but the miscoverage increases. the case of SCP-GN, we find KFAC be very competitive to the full Gauss-Newton with little change to the interval width or coverage. For ACP-GN we show results for the standard (i.e. AOI) nonconformity score as opposed to the studentized nonconformity score reported in Table and g This is because we found that the deleted and studentized noncon- formity scores combined with the KFAC approximation performed poorly. However for the reported standard nonconformity score, we observe KFAC leads to much tighter intervals with just slight increase in miscoverage. For the "ACP-GN (split + refine)", on all datasets except bike, we observe tighter intervals with KFAC however the miscoverage is often slightly greater.
22

---

Published as a conference paper at ICLR 2025
Table 6: We compare against Approximate full Conformal Prediction (ACP) that uses a target dis- cretization strategy.
Avg. Width
Avg. Coverage
9198
95%
99%
909
95%
999
energy
ACP
1.700i00.0s
2:21940058
3.6ll=nooro
87.41ea.s
98:
N=768
ACP-GN
1.007-00000
1.88210008
3.087:10015
N8.3228 on (/)
83.87 ms (7)
g0:01
1=8
ACP-GN (split + reline)
L.745e0.01
2.17
5. 5,3000zm004
90 90.59ee2e
(
94 96 (
99. 18 (
ACP
17.854:0.104
11.00009.119
31 1100
30
88
43:2.07 (
N=1,030
15 15.00028.112
19.850+o.:41
29.179
19.95ea.u
84.90= M
7-8
ACP-GN (split refine)
18,907 10300
24.01210.22
35,948 1o.s7
90.
96. 23
(
99.1
10..17...000
wine
ACP
2. 2:158=0.00
2.67619
8.63020005
90.
46
94.
88
(
98 22
(
N-1,599
ACP-GN
2.091
2.650
3.797.0005
90.30
10
I-11
ACP-GN (split refiee
2.77....07
3.05410.000
1.924.00000
(
84.81
0.00
Kinmmm
ACF
0:207.0000
0.26550001
0.3652000
88 8380 as
0A)
54 Toge
(7)
UR 77 (7
N=8.192
ACP-GN
0.213
0.36240.011
0 0.50
89
68
58
98 85
I=8
Explit reline)
0.28440001
02
pOwGE
ACP
12:131 =0.02
14.84010027
504
59 28 (/)
54 088 (7)
58 10
N-9,568
ACP-GN
12.126. 0.001
11.24810
21 19022
90. 8
95.
13
98 80
[=
ACP-GN retine)
12.744:0.045
15. 12..999
22.043
90 17
26
98 98.
community
ACP
0.401 -0000
1.502
0.7001003
89 19.71
34.001.8.5
07.71 10
N-1,994
ACP-GN
0.000
0.594 10,00
0.936 Lo0s7
90 a
96 21.. (7)
29:18 29:181333 (
/=100
ACP-GN (split retine)
0.521
0.65449
1.011:0077
90 05.95
99. 16 (/)
bike
121
156.0900=2295
59.03
18.13320.0
N=10.886
ACP-GN
97 07.-660-111 195
130. 132
216:677:22.0
89 12 (0)
94.32 (9)
98, 72 (e)
I=18
ACP-GN (uplit retine)
130.953
174.19047.008
288.603 003-0200
90.09 (
94 94.98amm (
99.06=2.0r (V)
The second choice is last-layer approximation or neural linear model approach (Ober & Ras- mussen 2019) that can be considered a special case of subnetwork inference for Linearized Laplace (Daxberger et al. 2021b). This makes the AOI estimation exact with respect to a linear model whose basis features are given by the activations of the penultimate layer. This can be recovered as a special case of Gauss-Newton influence. This leads to storing and inverting much smaller matrix whose size corresponds to the number of parameters in the final layer. In the context of Linearized Laplace, be combined with KFAC for increased scalability but we do not investigate this configuration here.
the last-layer approximation
The results are shown in Table [2] The last-layer approximation has the effect of making the ex- isting undercoverage in LA much worse. In the case of SCP-GN, the approximation leads to the intervals being no more efficient than SCP, that is without normalization, whilst maintaining correct coverage. For ACP-GN, the intervals undercover by a large margin on the bike, community and protein datasets. The split and refine variant is still able to successfully correct this attaining the desired coverage whilst being competitive to the full Gauss-Newton on tightness. We also observed the different varieties of nonconformity score all performed similarly results reported are those of the studentized variety as in Table [ and g
J.2 COMPARISON AGAINST APPROXIMATE FULL CONFORMAL PREDICTION
We compare ACP- GN and ACP-GN (split+refine) to Approximate full Conformal Prediction (ACP) (Martinez et al. ) several UCI datasets taken from Table I and g ACP uses the AOI non- conformity score (referred to as the ordinary scheme in (Martinez et al. 2023)). Whilst the exact Hessian is computed in (Martinez et al.) 2023) with damping term ensure positive eigenvalues, we approximate the Hessian by a (damped) Gauss-Newton matrix in order to keep approximations consistent in the comparison. The damping term tuned in the same way as ACP-GN, as described in App. [.I The Gauss-Newton matrix has been used in previous works when evaluating influence function (Bae et al., 2022 Nickl al. 2023). ) Furthermore, we use "direct approach" (see Eq, 4 in (Martinez et al. 2023)). Martinez et al. (2023) only considered classification tasks so ACP needs to be adapted for regression. We define grid of candidate targets using simple discretization strategy that constructs fine, uniform grid of 200 points delimited by the training targets.
Table G shows that in some datasets and target coverage levels, ACP-GN is more efficient but in others ACP is more efficient. However, we used 200 grid points which exceeds the upper end of what was investigated in prior work (Chen et al., 2018). We also emphasise that ACP-GN has lower space complexity since it only computes changepoints for each combination of test and train point, whereas ACP computes residuals for each combination of test point, train point and candidate target value. For the datasets considered we did not observe considerable difference in the running time between the two methods but we do expect for larger datasets ACP to be slower due to the need for batched computation.
23

---

Published as a conference paper at ICLR 2025
J.3 COMPARISON AGAINST FULL CONFORMAL PREDICTION
We compare full conformal prediction (FCP) against ACP-GN and ACP (Martinez et al. 2023 as well LA and SCP. This evaluated on synthetic dataset with outliers (500 train points and 100 test points) taken from Papadopoulos (2024) (see Sec. 5.2). This generates data from a Gaussian Process prior with RBF kernel. There coin flip of probability 0.1 for which the observation noise standard deviation is increased by factor of 10. The experiment is repeated 20 times with different seeds also controlling the data generation. Tanh activation function is used throughout. This is trained using Adam for 500 epochs (full-batch training) with an initial learning rate of 10-2 that decays following a cosine schedule to 10-3, We use uniform grid of 50 points for the target discretization in FCP which is on the lower end as suggested by previous works (Chen et al. 2018) and enough to give valid coverage. ACP follows the configuration outlined in App. J.2 with 200 grid points. The AOI nonconformity score is used throughout for FCP, ACP and ACP-GN. SCP uses a 50% calibration split. Hyperparameters are tuned using the online marginal likelihood procedure described in App. L1 which exclude from the running time.
MLP with a single hidden layer, 100 units and
As Table 7 shows, all conformal methods give the correct coverage but FCP is indeed the most efficient. However, the running time is factor of 10 slower than all other methods including ACP and ACP-GN. This experiment run NVIDIA A100 GPU.
Table We compare against Full Conformal Prediction (FCP) on synthetically- dataset.
Avg. Width
Avg. Coverage
Time (x
90%
95%
99%
90%
95%
99%
LA
1.001
0:064:00.00
1.661=0.ca9
91.45 (X)
95.15=0.a2 (
96. 00.00. (X)
0.03-1=0.001
SCP
0.623:00.04
1. 1.406=o.co0
3.632:0.151
91.10s0.82 (V)
96.10.6.45 (
99.50a0 (V)
0.023
FCP
0.451
=0.00a
3.090=0.co2
87.00+1000 (V)
95 95.25=0.52
98. 28.90ss.33 (/)
169.522 0.9.527=4.50n
ACP
0.532 ona
1.37020004
90.35 3.17720:004
(
95.502o 1 (/)
99.00 (V)
0.035
ACP-GN
0.001
1.450s0.0Ga
3.529e0.106
91.00+0.81 (V)
95.60 (/)
23.25 (V)
0.03/120.om
24

---

Published as a conference paper at ICLR 2025
protein
ACP-GN w/ Calibration Split
none
50%
90%
96%
99%
LA
ACP-GN
ACP-GN
(studentized)
ACP-GN
(jackknife)
80%
85%
90%
95%
100%
80%
85%
90%
95%
100%
80%
85%
90%
95%
100%
Avg. Coverage
Avg. Coverage
Avg. Coverage
LA-
ACP-GN
ACP-GN
4
(studentized)
ACP-GN
(jackknife)
10
15
20 Avg. Width
25
20
25
10
20
25
Avg. Width
Avg. Width
Figure 3: Our extension to ACP-GN that employs a separate calibration set to evaluate nonconfor- mity scores combined with refinement of the linearized model shows considerable improvement the coverage. Unsurprisingly it leads to larger average interval widths due to smaller training set. This is shown for protein dataset at (90%, 95%, 99%) confidence levels.
25

---

Published as a conference paper at ICLR 2025
Table 8: Additional results on UCI regression datasets.
Avg. Width
Avg. Coverage
LA
15. 025
18. 18.497=s nos
24. 31.31000.19
89.30 1 (V)
93.53es. 10 (
97. =7. (0
SCP
19.22 19:216:2..1 1216:...2
24.526
42.110sa
89.92233. a9
94.97 (
99.11 (/)
concrete
91.97
(P)
N=1,030
CQR
22.496.
27.145
39.9 10.33.
90.51
95.24.5.36 (
99.01.0.04 (
1=8
ACP-GN
15.727
19.810ss.1447
29. 19.70.77
89.00
94.77 (
98.8559.28 (
SCP-GN
21.780Le.19
36, 10.313
94.87
99.1510077
ACP-NN (xplit + reline)
4U7: Los
24.01 24.012eo 129
35, 94 260
10
00:200
(
05, 233 (
99.17:40.00
LA
2 20090:20.01
2.501
3. 2.28770.000 200,00
91. 12 (7)
91.58es.
588. 988.1100.c (7)
SCP
2 183220000
2.76889.00
3.9 2.900
90.41aa.0
95.07 07.07.00122 12 (
99. 99.12 (
wine
99.02
N-1,599
CQR
10977_0000 o0s
2,400 1.00,..00 o16
3.86710.cmm 10.cer
30.24
95.05 (
10.07.0000
1-11
ACP-GN
2 20100..0
2.065 oos
3.827 10.007
161
95,8014.00
99.17 10.77
SCP-GN
2.
3.75310.co
ACP-GN (split + refine)
2. opp
3.054e0.00
1.30140.000
89 26
94.81 88.80..
98 20.9994..co
LA
0.213 0.213 20.00
0.264
0.334 s0.co
033 88.88
08.09.nu
SCP
0:231
0.285
90.1810.0
0.229
0.282
90.50
99.1810.00
N=8.192
CQR
0.254420004
0.304 00
0. 0.42622.00 000
95.21
g0.0240
7-8
ACP-GN
0.2131000
0.262 oo
n. 0.36510.00 o0
80688
94.5816
98. 85.85100
SCP-GN
0.252e5.00
ACP-GN (split + refine)
0.284=s.om
90.45e
95, 05.02.0.22 (
99.10 10
LA
34,35,,uu 11445_11000
15,001 10.001
20 898 10.005
92.08.0. K
05 17 (
DS. 26.16. 00.000
SCP
15.35926.00
power
CRF
12 22.573.000
oos
84.83
98 98
N=9,568
CQR
12 8001::0.c20
15.180ee..o
21 9 166
20
94 91.93e0
98 89
1=4
ACP-GN
12 526
15.2 15.24856
21. 09220..00
90. 16
95, 13
(
98. 8020
SCP-GN
ACP-GN (split refine)
12.744.00015
15.442.6.oo L...0o
22 153
10.17
15.2616.17
98 10.c0
LA
0.548
0.653326
1.888.0116
00:0013000
913 8338
97 27.00
SCP
1.159en.c2s
86.68e0.4
99. 99.1220.00
commaniity
CRF
0 0.5
0.721 029
1.16429.com
00:20
95.33 33.33 as
99.12aa.15
N=1,994
CQR
0.701
1 L077
90.90
95.70se..a (
99.35.a0:35 (
T-100
ACP-GN
0.510_0o:66
0.756
1.224.0.26
90.00.3.0
95,30
99. 39.25..0.44
0.474:0.015
0.656
110440.004
90.58
94.95.0.2
(
ACP-GN (split + refine)
0.662
1.010.0.06
90.07
95, 28.2811 41 (A)
00.12aa mm
LA
580:=2
80. 142
891
15 (
US. 70 (X)
20.7T1:32
90.00
facebook.1 1
CRF
18. 689=1194
35.76551.870
121
89
19.98
(
95. 95.10.... (
99. 28.08...44
N-40,948
CQR
19 6255...m 10.57
25.970.
59.922 112.774
90. 30
94.91 a0. (
98.97 20.04 (
/=53
ACP-GN
17. 779886.1..o
90.36
39.712.3.1
125.078
90.001..10
90.0410.3
ACP-GN (split + reline)
29 99.6006-s.422
54.0599:4..96
172, 20122222
90.06ea 10 (
26.20 (
99.144004
26

---

Published as a conference paper at ICLR 2025
Table 9: We repeat the UCI regression experiment in Table but with 25% calibration split. In the case of yacht, the desired coverage 99% was too small significance level to accurately evaluate the quantile of the calibration scores.
Arg. Width
Avg. Coverage
90%
95%
99%
90%
95%
99%
SCP
2.306e9.117
8.806au..um L1S
BI] 11.1 7o (7)
yach:
CRF
2:26 ao
3.808859 1.0
90.11a00
(+)
95 05.8228.4 0 (/)
N-308
CQR
3,236610
4.8 4.80510
90 (0..3310 A7 (/)
35.85.8.30 (/)
ACP-GN
SCP-GN
2,07020
3.111aa
Bita st (v))
36.9528.51
ACP-GN (uplic reline)
3.931 1.03110:043
5,92610 144
91 6610 st (+)
06 X6.66.2..11 (7)
LA
B. 8,30849:44
11 19
18.7 8ea
D1 2 a: (7)
91.31122224 (?)
53.55 (3)
SCP
10.06510
14.74610
38.674:1
boatoon
CRF
9.87420-15
14,20420
37.421.99138
90.0310
(/) 05.52.8.4
98.28.10
N-506
CQR
10.91810:131
14.61810.ars
31.130,0.03
3: (/)
95.65
98.17
I=13
ACP-GN
9 90.82
12.11lsoaas
20.512:0007
90.641022 2: (/)
45.49:8.36
99.11
SCP-GN
13.37210
27.274:1
96.49_..00
98.13.0.11
(split refine)
17.37210.252
22.85210.15
42.081.1:170
00.6810.44
95.79.6.8
98.96.10113
1AA
1.50220 306
1.70030 ocT
2.35320 op
88 9610 (
g2.9220 (
96. 36.99ga (0
SCP
1 1.84410.377
2.36510044 016
4.313.0
90.0510
(/)
95 05.04_635
90.38
CRF
LS07
2.34110046
4.316:0.13
40.97
96.02a623
99.36
N=768
CQR
1.779aa.002
7.092:0.173
90.35
1=3
ACP-GN
462
1888
3.070:20m5
88 28
03.699233
95.86-2111
SCP-GN
1881290.04
2.348
4.226a0
90 16
96 18an.4 (
90.31 31 (V)
ACP-GN refine)
2. 19889..06
5. 5.601a0
19
95 28.288333
99.43
SCP
113.504a1.370
150.11412.0 aST
287.466.5.45
90 28
96.11
98.87 (
bike
CRF
112 101:i.tss
150.161s2244 406
283.911 180.911s920
90 90 22
96.1 96.17sa.1 (/)
95.03anmm (/
N=10.886
CQR
10T 141ess0
130. 756
212.513
90
95. 18.88xx
98.90 98.97 (/)
ACP-GN
SCP-GN
105.12001)
139.301
656
07 (/)
ACP-GN (split refine)
137 114.9.99
178 639
285. 997 204
60
20
95 0.006..
99. 10.16amm. (A)
LA
U.35559
11. 18
14.00
X
50,0029
31
protein
CRF
25, 006
9..93
22.822mm (V)
NoA5,730
CQR
13:174ta0.0 1e9
14 422
17. 07
90 10 m
95 04.04.00
98. 22 (
F-9
ACP-GN
10:243110
13 25433
20.101
54
00
83.04.0
98 24 (0)
SCP-GN
11.74310.015
15.31210
20.2433.0
04.5
98.051001
(ppli refine)
19.229
18.74110.rm
20.927.0000
94.93
1A
66-18812.300
48.7 nee
103.00514 201
07
Us 0..0ig (
SCP
15. 73111..10
34.11410.64
145.543.1
80
05 (/)
94 96.9 0.00
98.01
facebook
CRF
257257
N-81,311
CQR
17.92910
$0.8540 (/)
00
98.02
I-53
ACP-GN
18.39611..50 5.5
40.088.11 0s1
166. 166.79215.0 ca9
90 11 (
95.4510a (0
59 30. (0)
SCP-GN
15. 63.3 220
$0.192to
122 22.00/944
$0.S1s007 (/)
94 94.96.000 (/)
99 99.00amaz
ACP-GN (split refine)
20.157
41.05129.st4
152 152.090ssx.90
18 (/)
95 36.08esurt
99.11
27

---

Published as a conference paper at ICLR 2025
Table 10: We repeat the UCI regression experiment in Table
but with 25% calibration split.
Arg.
Avg. Coverage 95%
90%
95%
99%
90%
99%
LA
15.523 10.087
18. 13.4997um uc-303
24.310.n.550
30.7 (
93.53 (
97.37 00
SCP
17.56349
conoreta
16:946110:7
21.808_c. L..98
38.48001..00
89.44.0.8
94.88.0.30
98.03
N=1.030
CQR
20.06349 ora
24.620
37 02000660..000 320
89 88
94 90 (
98.11#0000 0v (
T=8
ACP-GN
15, so
19.8 19.810
29. 29.19:10 mm
80 80.00a
94 77 (
98, 08.85.0 (/)
SCP-GN
98.11+0012
ACP-GN isplit refine)
25.331 20.
32. 294
47. 29..4.0
90.30 (
95.45 (V)
99.13 (A)
L.A
2,090100000
2,5411
3. 28.27 10.
91.1210 (
94. 58 (
SCP
10.1210.000
2,686
4.032
90.11
95.00.b.11
99.27
wine
2.186:1 018
2.733
4.3077.00000 075
94 04.92200000
901 201200000000
N-1,599
CQR
1,966 yo
2.421 0016
3.92010..0
89.97 00
94.95
98.1 12
/=1l
ACP-GN
100
2. 2.665
827
91.10 16
95 80
90.1 10.1750000
SCP-GN
3.700a0
96
ACP-GN (split refine)
239
8.527 e0.
90. 20
94 98 (
99 00000.0..0
LA
0.213
0.2044 001
83 83.0
51.8810.00 (K)
DS 2010
SCP
90.10
98.15.0000
0.271
0.381
05.96.011
29.12
N=2,199
CQR
(1241 20:00
8:2266 oo1
0.3922 600
90.11 24
96. 18.18
98 080
7-8
ACP-GN
0.21310000
01 0.2662:5
0.365
80.8
94 5810
SCP-GN
0.273e5.00
90
19,1 10:000000
ACP-GN (split refine)
0.243
n.298=ccoom
a0
95.27 25.27
(
17.0000000
LA
13.3 13.345 10.000
15,001 Lc.001
20 888 10.445
82 08
08.8610117
96 2610000000000
SCP
10.00
15.212.0.0m
21.72010:245
05.01.649
98 00.09...000
power
12.457..000
15.019-
21 56.56331
30.32
95.06
98 Doen
N-9,568
CQR
12.818: .4
15.081
21 10990001070 37
90.52 c0
94.90
99.02
f=4
ACP-GN
12.526:5008
15.248
21 58225
16
U5 13
08 8010
15.215es.000
21.
ACP-GN (split refine)
12 23.
15.561 m000
22 5855 200
18
95 18
LA
0.0033
50.50 (
86 S3ano
97 07.0mmmm
SCP
0l471
1.0033
98.97
community
0.40410.000
0.617.c.00
0.992
90.35
95.03
88.000.00
N=1,994
CQR
0.660aa no4
8.9926i nos
1.349020.0m o07
91 28
96.00
98.0
I=100
ACP-GN
0. 0.460s..002
0 0.932s0.cm
15
95 85.05en
98 21
SCP-GN
0.621
ACP-GN (split refine)
0.700=c.000
1. L.82240.22
94 42 (
98. 85.0.0.
LA
67 19.47
S0.527 .3.143
105.531 14.330
97 63
(
58. 15.101 (K)
58. mo0 0
SCP
18. 18.
42.110
176.332.5.533
89.96a0:2
95.08
99.03
facebook
16.845..
34.078
114.760.-111
90.0410
12:000 (
99 08.98.0000
N=10,948
CQR
21. 120ee
27. 27.024=:.am
43 23.095-22290
90.06en
(
95.0 95.06=00 (V)
98 95566600000
/=53
ACP-GN
17. 986-66
41. 11.03356.700 T9o
199 000-331:2
90 90.36a0
95.5612 (0)
37.00
SCP-GN
130.967
90.01e0.5
95.0
ACP-GN (split refine)
21. 24.639er..0
51. 11.864=22.00 687
90.27 (
24 (V)
98.1 90.1450004
28

---

Published as a conference paper at ICLR 2025
Table 11: KFAC approximation to the Gauss-Newton evaluated large UCI datasets
Avg. Width
Avg. Coverage
90%
95%
99%
90%
95%
99%
LA
100.451..5.0
80.82.0.20
00.29
96.831
LAGAec
91.501
105.0300
143.290s 6.700
87.2441:00
91.07 (P)
56. 55.2010.3
131. 138-11011
180 17.477722224
324.750
20 (
95. 17au.a (V)
bike
SCP-GN
122 245:2 uta
160.505e1 760
254.400lg tot
90.3420 sa (
25..5 1a (/)
30.025 (
N=10.886
[=18
SCP-GNrBie)
121. 40 nos
160.214g1
250. 770.9000:..94
90.46 90.46:0
(
95 22,0 (/)
08.00 08.00 g.
(
ACP-GN
133.781e7.314
212.144:3..47
27s0.1
94. 15. (A)
98. 69.0
ACP-GNittc))
121.501ssm
(split refine)
250.800
(/)
99.01=2.06
ACP-GNitec Esplit reline)
600
211
953
336.975e1.200
81 (A)
80.21emce
LA
D. 1.548annnc4
0.NiMao:10
50.50an.o (V)
35.8319 (/)
57 05.0 (K)
LA(ide))
4722nuus
0.562
a.730
00.45
88.55mm
96. 98.9556
00.17
community
N=1.994
I=100
SCP-GNAAS
476a00u2
0.600
06637uu
2000
1.110
00.62a
95.30em (
(
08.00
ACP-GN
0.78440.190
a0. 1.222
(
90.2810.rr 4333..4110 (
90.26 (
ACP-GN/AGe)
0. 1.77Ganuus
0.6122ou22
0.964a0.co
40.78a (
20.0.07 (
99. 99.2628322 (
ACP-GN (split reline)
066
10000goc
01. 38
95-45aa (
20.20:a014 (
ACP-GN/AGs) rsplit
0.64420.04
1818110077
S0.00
LAAga)
1.1322nn
18.811
14.301 20044
84
53 00
88.63.0. (K)
54.04
SCP
13 O11 uus
17. 17.16lume
26.181 m0
89 78amu (
91 33 (V)
98 18.99 (
protein
N545.730
SCP-GN
SCP-GNAAAe)
12. 128-
16.57010
16-10220.0
24.0
89 78an to
94 8830 (
04.8530
08.942 (
ACP-GN
13. o5r
18.94
90.14go
ACP-GNAAae)
00
12.000
19.093.0.00
86.02a0.1 (0)
91.92
97. 77.0
ACP-GN (pli refine)
12 614lss
15.961
28.188
89, 88 (/)
91
90 (V)
98.97=a.co
ACP-4NN/tec refme))
12 120 tus
15. 3.3363e
22 22.260len0
85
39 00
93. 82 18 (8)
96. 19 (X
LA
31.527a3142
10b.511
63sads
18.15m
58. 7010
LA(ffer)
105.707
70.77122.
192
178.8900...oo
(/)
Iacebcok_1
N=10.918
I=53
SCP-GNI100)
SCP-GN
20. 303,0 one
160s2 ass
40.5 331
142
125.078
128.583a5 583 700
90.00
00.01am (/)
11 (
91 91.9tsun (V)
95 95.012900 (
90.03
30.0d=ncs
ACP-GN
30. 400077700
62 830
223 223.809 45.477
90 10.60a..1
95.61 (X)
59 2610 (0)
ACP-GNAAG))
40.99110.954
1
30.24an.1 (V)
95.38ss.o
99. 24.00
(split refine)
(
ACA tsplit
20.732e1.1
121.601=3.00
89.81an.0
91.66998 (/)
98.901a3.44
LA
66 18.08811000 708
78 7.774.,..00 2.0
103. 103.4833 1.30
97 97.47 (0)
99.01 99.01 s00o (8)
D8 6510 (X)
63.301
70.774xa477
99.5844.4.50
97 28
97 97.84 (A)
58. 04 (0)
facebook__
N-81.111
I=53
SCP-GNAAG
SCP
SCP-GN
16. 18.387a
10.213em.199
152.706
116.072=3.18
118.450
89.0 80.97amo
89. 08.58anor7
(/)
95 00 (/)
98 (/)
(
99.00sa.cs (
00, 00.06aaeee0 (
99.02
536-33663 sia
36.470027
197.
54ga
05.46.2000 (P)
59 2310
ACP-GN/AGe)
20.497 1.77
43.2 43.2466...02
(47.852..33.55 350
04.34 (0
96.22 (K)
59 1810 (K)
ACP-GN (split + refine)
23 0965511125
12 23.53811ss
125.337=2:16
90, 17anu (+)
95 15 (
99 99.08 (V)
ACP-GNite) (split refine)
20. 487
117,996122.40
90. 11..1
95 95esn (/)
00.11
29

---

Published as a conference paper at ICLR 2025
Table 12: Last-layer (LL) approximation to the Gauss-Newton evaluated on large UCI datasets
Avg.
Avg. Coverage
90%
95%
99%
90%
95%
99%
LA
100.451=2.804
119 69.222as
157.305as..0 749
89. 11/82mm.n (v)
90 19.29han ax (1)
90.83 (K)
LACLO
79. 79.825-3.087
96. 231
125. 159h
62.80st.12
80,50 60.984112 (5)
92. 19
131.138_6.419
180.477.1.0
324.7561-40
90.33
(
95.17.a.15
50.00 (
N-10.8%6
SCP-GNiLLI
122.24h.1.073
130.965
100.505
227
424.427 4004
254.400
90.34
90,20 (V)
98.17ssap (/)
96.26
99.02.o.4
59.00 (/)
I-18
ACP-GN
98.813:2.466 465
130 803
213. 13
80 M6ai
(F)
94. 14.41a00r on (0)
08.67 (X)
ACP-GNILLI
76.808_1.66
100. 1075
160-44819
81.00
88 88.20
95.1750 (A)
ACP-GN (split refine)
128 4.0
170. 782s3
281.632s1.11
00.08aa.22 (
91.9
99.01saae (
ACP-GNiLL: refine)
128-853-1.101
07941
225. 97s
95.12
LA
0.88810.11
90.9000.. (V)
33,8110.50
97.06.0.0
LALL
0,455=6.005
0.542x0.015
0.712s0u29
89.28 (
92.53ken 94 (X)
96.06 (0)
SCP
0.534g6.000
735
1.16420
M0.1
(
95 (5.33sn
17177
commuiity
SCP-GN
0.473_6.01
0.00010003
90.5020.00 1.116100
05.10
/-100
SCP-GNIEL)
0.530..6000
0.730
1.15740025
90.33a0.4
95.50u
ACP-GN
0.5700=0.11
0. 155
1:22/au
(
95. 50.3000..4
25eae
ACP-GN(LL
0.498:6.012
0.56423001
0.88720
88 83 m (
98. 78.78 m (6
08.4220m 00
ACP-GN (splic refine)
0.519
6.63200
1.110son:
90.97
a (4)
96. 96.28.0.41
99 12112..
ACP-GNILLI (split refine)
0.495
0.648soaze
90.7 90.75aa.. L040sno:4
(
95,70=5.20
29.355 (/)
9.385_6.060
18310
14:07100m3
85.43
80.0010 X0
94.81
LAiL
8.967 -0.006
10. 10.328 10.3
13.973a0041
82.51 (X)
87.0810 (0
92.81
SCP
13.041=s.ees
17. 161as0e
26, 16.18129.10 11m
89 78.88 (V)
94.33a oe (V)
96 9 (
prctein
Ns45,730
SCP-GN(LL)
SCP-GN
12.426
13.095_4.064
16. 002
24.02250
80.78 (
94.82,0.00
94 04.86
9429 (
10.203:0.00
83.0dam
ACP-GNILL
3. 8.731=0.002
11. 311aume
17. 19192
62.62 (
89.16am (0
96. 06.29 (0)
ACP-GN (split refine)
12.660
16. 173...m
28-445.o
80.83 (-)
94.90 (/)
37 (
ACP-GNILLi (split refine)
12.616..0.00m
16 16.078 10.00
20.072
$9.81 (A)
94.77 (/)
58 98.9 (/)
LA
67-580)_2.657
106.831
07.6310
98.1610
08.76.000
LA(Z))
66.025_-1.00
67315.506
103.3044
96.9010.11
97.4510
98.10.01:
SCP
20.771=2.462
H. 192
178, 800 oos
90.00 (v)
95,03sa.se (V)
20.05eac4
Zacebook_
N-40,988
SCP-GN
20. 23.4600-2.00 488
39 7 712ss1.44
125 078 uns
90.01 u (v)
94.94aa.0 (V)
29.0te (
I-53
SCP-GNILL
20,735
44 237
177. 50500
00.02 11 (V)
95 05.033a.
99 90.042
ACP-GN
17.986:0.480
41 003
199.331
90.36anoa (/)
96.56an
99.37
17.3055:0.544
89.51sm13
98.63en.
(split refine)
29.0066-1449
64 107
72222222 a5*
00an (/)
05.2013
1420
ACP-GN(LL. (split refine)
19.198_.6.65
42 a0.a
176.527
90.02 (/)
06.12.9.06 (/)
06.06 (/)
LA
06.088 2.700
78. 7451.1996
10A. 453
07. 60.13 DK
08.01 (X)
98.05 (X)
LVLL
64.183=4.014
77. 194
97.02
97.56an
98.23
16.387=0.20m
a0.97 (/)
facebook 2
N=81.311
/-53
SCP-GNILL
SCP-GN
16.323=6.11
16.287=2621e
33. 655
35 192
118. 459 aus
199
90.00 (V)
30.00 (V)
94. 31.90
91.88saee (V)
99.06 (
29.00saus (
ACP-GN
18.296_.6.546
40 0SS a 0ea
166. 702.7222..
90.47 10 (0
95 45.45 ms (9)
90.35 (8)
ACP-GN(LL)
17.671-6.635
37. 040
127.615a5770
89.94am. (
94.44a
98.73
(pplit refine)
21.160
95 10.10
ACP-GNOLL (split refine)
16.805
36. 727 a7r
149.72334 197
50.08 (
05
09.00
30


Reviews:
[{"review_id": "QrQPizoOXm", "reviewer": "Reviewer_6yBk", "summary": "The authors developed a new and scalable full-CP method considering the Gauss-Newton influence. The paper is well-organized.", "questions": "1. A complexity analysis of the proposed method should be included to demonstrate its efficiency relative to the standard Full-CP approach.\n2. Several state-of-the-art algorithms from the past three years are expected to be compared to further demonstrate the advantages of the proposed method.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical analysis is thorough.", "weaknesses": "Some more state-of-the-art algorithms are expected to be adopted for comparison to illustrate the effectiveness.", "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": "", "extra_scores": {}}, {"review_id": "AnNhqsPJ7i", "reviewer": "Reviewer_mcn6", "summary": "This paper proposes to use influence function to approximate full conformal prediction for regression tasks. Like a recent literature, it perturbs the model in the prediction space, and allows for training the model once instead of carrying out the actual costly full conformal prediction procedures.", "questions": "1. Do the author have any thoughts on the validity?\n\n2. Why do we need to approximate FCP in \"low-data regime\"? Related to this, maybe an actual FCP baseline should be included for yacht, boston and energy.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "This paper extends a recent work on approximate FCP on classification to regression. FCP is indeed expensive and, if to be applied on large modern datasets with NNs, needs to be made more efficient one way or another.", "weaknesses": "1. Inappropriate literature review: This paper didn't cite important (although un-sound, see Appendix C of https://dl.acm.org/doi/abs/10.5555/3540261.3540902) previous research https://proceedings.mlr.press/v119/alaa20a.html despite the very similar idea (and they are also studying regression). Similarly, even though (Martinez et al. 2023) is classification, the current draft severely underplays the clear similarity. While this probably does not constitute a research integrity issue yet, in my opinion this MUST be fixed.\n\n2. Validity of the method: Although I'm very glad that the authors didn't make claims about validity of the approximated FCP method, this paper also lacks an appropriate discussion on the *invalidity* like (Martinez et al. 2023, section title \"Validity of ACP\"). I highly recommend the authors include a similar section, as in my opinion, the whole point of conformal prediction is about \"validity\", and approximate CP methods are, to some extent, closed to a \"calibrated\" non-CP method. Alternatively, I'm hoping to see some \"worse case\" guarantee when we make additional assumptions about the data distribution. Either way, a discussion on validity is needed. \n\n3. Experiments: \n\ta. While it is obvious that for very small datasets SCP is very wasteful (due to the sample splitting), I think to use half of the training data as the calibration set is also misleading. Yes, this was what was proposed decades ago, but in practice no one actually reserve half of the data as the calibration set. I suspect with a more appropriate data splitting, we wouldn't see much difference between SCP and ACP on bike.\n\tb. The lack of validity of ACP is very concerning, as it lacks both theoretical and empirical validity. \n\tc. I don't see why SCP-GN is related to this paper. It seems the same as \"Locally-Weighted Conformal Inference\" in (Lei et al., 2018).", "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": "", "extra_scores": {}}, {"review_id": "riXQIZOi3e", "reviewer": "Reviewer_pv54", "summary": "The authors highlight in this paper the computational challenges associated with full conformal prediction (FCP), arguing that it is infeasible for practical applications due to needing to train a new instantiation of the model for every data point for every unique label. In an attempt to alleviate this issue and scale FCP to neural network (NN) regression, they attempt to approximate FCP through the use of Gauss-Newton influence and network linearization to form their method ACP-GN and an extension for split CP SCP-GN. The use of Gauss-Newton influence prevents the need to retrain the network as it allows an approximate solution to perturbation of the model parameters, while the use of network linearization prevents the need for an exhaustive grid search over the label space. The evaluation shows that ACP-GN provides a more well-calibrated method in terms of coverage compared to comparable methods in experiments tested.", "questions": "Can the authors comment on the following:\n- The lack of evaluation to previously proposed approximate FCP methods.\n- The potentially misleading statement in the conclusion of the paper. \n- Why you did not approximate the saved training time between FCP and ACP-GN as computational infeasibility is the main motivation behind the paper.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The proposed methodology to alleviate the issues with FCP is intuitive and logical. It is further backed up with well-written derivations provided in the appendix.\n- Sections 1 to 4 are extremely well written: references and literature covered are correct/up-to-date and craft good motivation. Notation throughout is consistent and rigorous.\n- The numerous datasets and evaluation splits tested upon are impressive and provide statistically rigorous results.\n- Highlighting between Algorithms 1 & 2 is great for readability.\n- It is clear originality is high.", "weaknesses": "- The main motivation behind the method is that utilising FCP is computationally infeasible. It then feels detached to not comment on the possible/potential computational savings between FCP and ACP-GN. Calculating an approximate training time that FCP would take on an example dataset and comparing it to ACP-GN's training time would be helpful and insightful in Appendix E.\n- Realistically, between the handful of proposed methods, the evaluation compares against two methods: a Laplace approximation, and the base split CP. This feels a little weak; I would have preferred to see comparisons against works that use influence functions, or homotopy.\n- In the conclusion, the authors state - 'our approximate full-cp methods provide tighter prediction intervals in limited data regimes'. When looking at the small datasets, this statement is true when alpha=(0.1). But when alpha=(0.05 or 0.01), the Laplace method consistently outperforms all proposed variations.\n\nSmall weaknesses:\n- Captions for tables and figures throughout the paper are used for discussion instead of describing what the table is showing specifically.\n- Bolding in Table 1 is potentially misleading. Even though you declare what definition for bolded results. Typically, bolding is used for top-performing results. In Table 1, in numerous cases, bolded results are not best performing. This is a shame as it takes away from the great results reported in the 'coverage' column.", "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": "", "extra_scores": {}}, {"review_id": "rK6OFiSVdh", "reviewer": "Reviewer_EePj", "summary": "The paper proposes an efficient conformal prediction method for regression problems based on neural networks. To do so, the paper suggests to use Gauss-Newton influence in order to approximate how the residue of the NN changes, which allows for the CP intervals to be computed without performing NN training in full again.", "questions": "1. Are there any possible theoretical guarantees for the achieved CP bounds? Given that the Gauss-Newton influence seems like a well-studied theory, and that linearised NNs are also common assumptions in the NTK theory (which itself provides extensive theoretical guarantees for NN predictions), I am wondering if those results can be used to show how accurate the residual estimates would be, and how they would affect the quality of the resulting interval predictions. I am unsure if these theoretical bounds are typical in CP works but it would make the work more theoretically sound.\n\n2. How sensitive are the conformal intervals with respect to the initialisation of the neural network?\n\n3. In the related works section, you have mentioned some more recent methods for conformal prediction on regression problems. Why were these benchmarks unsuitable for comparison in the experiments section as opposed to some of the older methods that were used in the experiments?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written, especially in providing enough background for those who may be unfamiliar with the CP methods already.", "weaknesses": "- Although I think the paper is already well-written, I feel it would improve on the presentation further if more visualisations are provided, especially in trying to understand how the \n\n- Even though the paper claims that their method should be more efficient than existing naive CP methods for NNs, it would still be interesting to see more results on how this compares. In particular, since the algorithm requires the inverse of a Hessian, it would be interesting to see how the method can scale to larger NNs or to cases with more training data. In particular, some results on running time that compares the proposed methods to other methods would be interesting.\n\n- To also verify the use of Gauss-Newton method, it may also be an interesting demonstration to directly compare the naive method in Algorithm 1 and the approximation in Algorithm 2, to show that even using the approximation the tradeoff in accuracy is not so large but more gained in the running time (I am unsure if this is already shown in the SCP benchmark case already though, in which case the discrepancy in result would be interesting to discuss).", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)