Generalized Fast Exact Conformalization
Authors: Diyang Li
Venue: NeurIPS 2024 poster (2024)
Keywords: Conformal Prediction
Generalized Statistical Estimation
Numerical Optimization
Primary area: optimization

Abstract: Conformal prediction converts nearly any point estimator into a prediction interval under standard assumptions while ensuring valid coverage. However, the extensive computational demands of full conformal prediction are daunting in practice, as it necessitates a comprehensive number of trainings across the entire latent label space. Unfortunately, existing efforts to expedite conformalization often carry strong assumptions and are developed specifically for certain models, or they only offer approximate solution sets. To address this gap, we develop a method for fast exact conformalization of generalized statistical estimation. Our analysis reveals that the structure of the solution path is inherently piecewise smooth, and indicates that utilizing second-order information of difference equations suffices to approximate the entire solution spectrum arbitrarily. We provide a unified view that not only encompasses existing work but also attempts to offer geometric insights. Practically, our framework integrates seamlessly with well-studied numerical solvers. The significant speedups of our algorithm as compared to the existing standard methods are demonstrated across numerous benchmarks.

Generalized Fast Exact Conformalization
Diyang Li Cornell University di diyang01@cs cornoll....lll..ooooo.. edu
Abstract
Conformal prediction converts nearly any point estimator into a prediction interval under standard assumptions while ensuring valid coverage. However, the extensive computational demands of full conformal prediction daunting in practice, it necessitates a comprehensive number of trainings across the entire latent label space. Unfortunately, existing efforts expedite conformalization often carry strong assumptions and are developed specifically for certain models, or they only offer approximate solution sets. To address this gap, develop method for fast exact conformalization of generalized statistical estimation. Our analysis reveals that the structure of the solution path is inherently piecewise smooth, and indicates that utilizing second-orde information of difference equations suffices to approximate the entire solution spectrum arbitrarily. We provide unified view that not only encompasses existing work but also attempts to offer geometric insights. Practically, our framework integrates seamlessly with well-studied numerical solvers. The significant speedups of our algorithm as compared to the existing standard methods are demonstrated across numerous benchmarks.
Introduction
In modern algorithmic practice, quantifying uncertainty is crucial for accurate and reliable model predictions. Conformal prediction [1] serves as powerful statistical tool that leverages the observed data to construct prediction intervals containing the outcome with a predefined probability level. It enjoys model-free coverage guarantee regardless of the underlying distribution of the data. In recent years, conformal prediction has gained increasing attention from the community of machine learning [2-5], data mining [6-8] and computer vision [9, 10]. This growing interest is attributed to the attractive properties that it operates under the assumption of exchangeability. which is weaker condition than independence and identical distribution, allowing for wider range of applications in real-world scenarios where data may not meet strict statistical assumptions. Meanwhile, conformal prediction can be combined with almost any existing point estimators, even when the model is potentially misspecified [5].
While exhibits appealing properties, the application of conformal prediction often comes high computational cost [11, 12]. Kindly note that in this paper we refer to the full conformal prediction that does not discard training points as opposed to the split conformal prediction, as the latter involves only one single fitting. From numerical perspective, when constructing a conformal prediction set, one needs to exhaustively search all points (potential candidates) in the label space, where for each point the learning model needs to be refitted and the conformity score needs to be re-calculated. In many scenarios like regression, the number of possible candidates is infinite as the latent label can take an uncountable number of possible values. Conventional conformal prediction works by grid-search type method loop over the label space [13, 14], which discretize the interval of interest and subsequently solve sequence of individual optimization subproblems. To improve such brute-force approach, there have been many efforts in community that devoted develop better algorithms for computing the prediction set. A natural idea is to generate the set of all solutions
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Representative related work, which instances of generalized parametric estimations.
Model
Reference
Exact
Loss
Regularizer
Constrained
Path Structure
Leust Squares
[15]
Quadratic
Piecewise Linear
Ridge Regression
[16]
Quadratic
||]]
X
Piecewise Linear
Empirical Risk Minimization
[17]
Convex
Convex
X
Piecewise Smooth
Elastic Net
[12]
Quadratic
[w]l]
Piecewise Linear
Generalized Lasso Regression
[18]
Convex
[
Piecowise Lincar
General Formulation (ours)
Section 4
PC
PC
Piecewise Smooth
indexed by the latent label candidate using numerical continuation (a.k.a. homotopy) method, and we name this set optimal solutions as (exact) solution path, illustrated in Figure 1.
Despite extensive theoretical and empirical ef- forts, the understanding of conformalization path remains rather deficient. For some sim- ple cases, closed-form characterizations of con- formal prediction sets are available, such as k- nearest neighbors, least squares regression [15], and ridge regression [16] with quadratic loss. The study by [12] presents an exact solution path for conformalized Lasso and elastic net using their statistical property and issparsyty analysis. Investigations into more general objec- tives as discussed in [17, 18] incorporate linear interpolation to approximate the intrinsic piece- wise smooth structure, yielding prediction sets lacking of finite-same sample calibration. In other terms, [17, 18] offer only an upper bound for the approximation error and fail to control the degree of approximation relative to the optimal solutions. We summarize these relevant prior studies in Table 1. Given that existing exact algorithms are either tailored to select few models, or turn out to be grid-search type approaches that take very black-box approach, it prompts the following question:
Win
V1
X
y/u
y
W
[9]
Vi++1
(3)
Diagram of setting on fast exact con- formalization, where label candidate 3n+1 should loop over the whole latent label space y and each possible Vn++ E R² corresponds to one point on the (red) solution path. Conventional practice is to refit the model on each new 3/++1 while employ the woth-following algorithm to obtain the whole solution spectrum within 1 execution.
Figure
Can we "open the black-box" by developing a methodology that better exploits the structure of the path?
We answer this question positively by introducing differential equation perspective to analyze the ground truth solution path, which enables us to better reveal and exploit the fundamental path structure. This more profound understanding enables to build more generalized conformalization algorithm and present improved computational guarantees.
1.1 Our contributions
The main contributions brought by this paper are summarized as follows.
Generalizable framework This study aims to extend the application of fast exact conformalization into generalized statistical estimation. We relax the assumptions by considering a cost function that is no longer globally differentiable, but rather piecewise differentiable, while introducing constraints on the weight vector to fit more statistical models. In our analysis, the Clarke subdifferential of the objective is derived, and the set of nonsmooth points of path can essentially be described as level set of certain smooth functions. By adopting reparameterization regime, our framework effectively broadens the scope of several existing algorithms in Table and provides a unified view of them.
Theoretical insights We analyze the underlying structure of path through the first-order optimality conditions of the regularized problem, identifying sufficient conditions for a local path to be smooth around a given point and reveal that the structure of the path is inherently piecewise smooth. More precisely, if conditions are met, then the path locally the projection of a higher-dimensional smooth manifold onto the optimization space, thus offering preliminary geometric intuitions. Our

---

investigation further suggests that leveraging the second-orde information of difference equations can approximate the solution spectrum arbitrarily.
Practical efficiency Practically, our framework is not only straightforward to implement but also computationally efficient. With theoretical analysis, we present explicit expressions for the gradient flows of objective, which is homogenized and well aligned with standard forms used by mainstream numerical libraries for ordinary differential equations (ODE), thereby easing the programming efforts. When crossing potential kinks (or nonsmooth points), the computations are facilitated by boundary conditions pre-set the numerical solver. Notably, our algorithm eliminates the need for extensive iterations for computing the entire solution spectrum, contrasting sharply with conventional baselines. In experiments, we demonstrate the significant computational speed advantages of our algorithm over existing baselines, without compromising accuracy.
2 Background
Notation For set I C TRP, we denote by cl(TT the closure and by int the interior of J w.r.t. the natural topology on IRP. Define [i) the i-th element of I and conv(J) be the convex hull of J, or conv(JT) = {v
Ex=, 8,u, us E J, E R - 0 = 1}. The w()) is the i-th element of vector w and II(-) an indicator function. Let z(() be the derivative da(t) of function 2(t). Let O be the zero matrix and P {-} be the event probability. The sgn(-) is the sign function sgn(x) (r 0) or (x 0) that applied entrywise.
2.1 Model and assumptions
Given the dataset (x,, Vi 3i where x, R is the sample (covariate) and yi is the i-th label (response) live in label space y C RR We consider the generalized parametric estimation problem
m
w E arg min
Σ Li (B (w.)) 1=1
+
Σ
2yS2, (w)
1=1
(I)
s.t. gi (w) = 0, 15i5r
hy (w) < O, 15i5s.
where 7w is the model prediction function, L3 is the loss and Q is the regularizer. The gi hy are constraints and parameter X; E R controls the degree of regularity. In the following, will define the piecewise differentiability and state main assumptions that used throughout this work.
Definition (PC" Function). Let f U - R be continuous on the open set U S R and : + R, i fI....,k) be set of r-times continuously differentiable (or C") functions for r r NuNU. If ffx) (lla))eett.... holds for all x E U, then is an r-times piecewise continuously differentiable (or "CT)ffuntiion The i fu is a set of selection functions of f-
When working with PC"-functions in local sense, it useful to only consider the selection functions that have an impact on the local behavior around given point.
Definition (Essentially Active Set). Let f U + T be a PC" function on the open set U IPP with set of selection functions (f1,..., Denote 1k {I...., k}. Then given In E U. 171) & (ie IK f(x1) = f(x1)) is called the active set at Fı. and the (x)) (i E In x E clnt (1x2 U.: f(x2) [((2)))) is the essentially active set at ax- Assumption 1. We assume that Li and 22 in (1) are PC functions each with a of selection functions Ukerr, (Di.} and UkErG, (Di,b, respectively.
Assumption 2. We assume that Ωi and Lij are non-differentiable at w with multiple active selection functions, where 12 (w) = R2, (w), 12 (w) = TÉ, (w) holds for all w considered and all Ω2 L, in the following.
{I....,m, .m); i E (1...., + 1}. We further assume that
Assumption ensures that all selection functions we consider are actually relevant for the represen- tation of 2y Li. i.e., it does not matter if we consider the active or the essentially active set in the underlying optimizing space, which allows for easier representation of DV and D
3

---

2.2 Conformal prediction
Definition (Symmetrical Algorithm). A deterministic algorithm (I1,..,, 7 A is symmetric for any permutation of (n,...,nn. M(I,....,Ial (l Tr(())) Definition (Conformity Score). The conformity score function A, symmetric in its first v. inputs, is defined as A(x X,;; (n:xx++)) (R(+1)xx + R, where X (x,,
Conformal prediction starts from a conventional model fitting stage, followed by the evaluation of conformity score and the construction of prediction set. The score function A serves as a measure of deviation or conformity, assessing the extent to which the new input X aligns with the previously fitted model. A higher conformity score indicates a better match between Xn+1 and the model [1. 14]. For a new instance Xn+1 where the prediction region desired, the conformalization method operates by assigning a p-value to each latent Vn+1 y formalized as
x+1 I 2 Ant1),
Pynei
n1
where A; - A(x &;- R xx+1: Xz)) Specifically, in density estimation. AA is defined as Tw (x++1), where '/ is the density function estimated from the augmented dataset. For regression tasks, A might be set as 11 JJ (Xx+1)). with V/w being the regression function trained by the dataset including n + samples. Under the assumption of exchangeability among the pairs
{x,, M/ J= 1i the P returned by (2) has been demonstrated to be statistically valid [13, 14]. To generate the prediction set r(-), one thresholds these p-values at a prescribed error level a E (0, 1), resulting in
n++1
r(x++1) = {yn+1 P9n-1 2 =
Theorem 1. [19] Suppose that (xi, Jiri= nn+1 are exchangeable and the fitting algorithm A symmetric.
Conformal prediction applied on {x,, y/ ) U (xx++1) outputs set I'(.) such that
P (un+1 E [((x+11)} 2 -.,,
(4)
where t is the ground truth (n + 1)-th label.
Theorem (a.k.a. coverage guarantee) requires only exchangeability of input data and symmetry of the conformity score function, which are met by nearly prevalent model fitting algorithms. In aligmment with the analysis taken in prior research, we treat 3a+1 == gx+1 (2) as function of scalar variable We utilize it to facilitate the traversal of yn+1 across the entire label space D, and compute the homotopy solution path (w" (w"()) Zmin I I Emax] } (also shown in Figure 1). We assume that > continuously differentiable in terms of for simplicity.
(-+1(-): [zminy 2max]
3 Main results
present our main results for fast exact conformalization. The discussions here focus on positive but the derivation extends easily to include negative values as well, which will be discussed later.
3.1 Surrogate function
Lemma 1. Let f: U + R be a PC" PC"-function -function on the open set U C IRP and let C" C"-functions (fi....,fu frt be set of selection functions of f. Then for any U, there exists an open neighborhood U' _ U of on which J is also continuous selection of [s: i E T5(x))
Drawing insights from Lemma 1, we minimize the surrogate function of (1) as
m
min E, (w) WERP
Σ (v. (xi) Σ (w) +p (g(WW) +p max (0,h,(w)) (5)
For technicality reasons, enforce > eeen the limit w' (0+) A lim w (z) might be well-defined.

---

where p R=0 and Mn+1 = Mn+1 (z). This definition of & (w) is meaningful regardless of whether the contributing functions are convex. Denote model estimation terms Σ, L, + ,5 as L ( (w|z). and the minimizer of (5) as (z).. It is interesting to compare &g (w) to the Lagrangian function
(w(w) LM (w]z) Σ (w) + Σ pghy(w),
which captures the behavior of (-) near the optimum. At constrained minimum w the Lagrangian satisfies the stationarity condition VL(w*) O; its inequality multipliers Py are nonneg- ative and satisfy the complementary slackness (wnh5("*) = O. In the penalized (5), one usually takes
(7) which creates the favorable circumstances: (1) C. (w) I (w) for all w, (ii) (w) I (wr()2)) (w)) for all feasible w, (iit) (=(w)) -lw = (w(")) with profound consequences.
p> m .2..,
Theorem 2. Our surrogate function (w) is increasing in p. Furthermore, (w) is strictly convex for one p > 0 if and only if strictly convex for all p > O. Likewise, it is coercive for one p > 0 if and only if it is coercive for all p>> 0. Finally, if La (-) is strictly convex (or coercive), then (w) for all p are strictly convex (or coercive).
Given Theorem 2, several classical results [20] state that minimizing (2(w) is effective in minimizing (ar()) subject to the constraints we choose by (7).
3.2 Conformal path characterization
Definition 5 (Clarke Subdifferential). For continuous function f U + R on the open set U C RP, ler θ S U be the set of points in which f is not differentiable. The Clarke subdifferentaal of f at U is defined as
0f(z) A conv(tò R² 32:)) O with lim I2 = x, lim vf(x;) = +}).
1000
1000
Specifically, f is continuously differentiable in x. 0f(z) = (Vf())} While FC"-functions are generally non-smooth, we can use the Clarke subdifferential to obtain first-order optimality of (5),
Σ
( (1, aw (w- kEI?,(W")
Σ
Σ
(untal Nw (x) D'(w")
REIT (wr)
oy Vgi(w")+pp Σ On, Vh, (w")
Σ
Σ JIKEIN (w*)
1yb2 (w" (W') (w") (w")-D'(w") = =0, (8)
where 0b 8/. is the k-th auxiliary parameter for convex hull of each S2y. L. The (8) is accompanied by the active sets conditions and the subdifferentials conditions, rewritten in detail as
Di,(w*)) D2i, (w*)= = 0, Vk E (w" M44), Vie Tí D (ww)=D'' D22 (w*) 0, vk E L2 (w'))rr,). Vj Iū 87, (ww)-Lr -1 0, 02 (w") 2 0, 0,
(9)
kE kEIE,(w')
@k 0g - 0, 8 (w') 2 0, 1 i
(WTR((w")
RETS (w*)
where rj, l is randomly selected from Iß TÝ, and being fixed, with coefficients satisfying 0g
[-1} g. (w) < 0
{0} hy(w) < 0
[-1.]] (.(w) = On, E
[0, hy(w) = 0. this work, we specialize to the case where the
g:(w) >
{1) hy(w) > 0
5

---

constraint functions 9i (15i5r) and h2 (1 s) are affine, i.e., the gradients (w) (w)
gi(w) are constant." 2 We define 9: and h2 as constraint residuals gi (w) == v. w d, hy(w) := w/ w ej.
We keep track of the following index sets determined by signs of constraint residuals:
Na {i: (() v - < 2 {i: g. v w - d, 0), Pa (i: ((( w- 0),
Ni = [j: (e)) w < 0), 21 (w::h(()))wwwee-- = [j: hy (w) W/ e- 0}.
(10)
To characterize the path, we further introduce reparameterization in terms of an auxiliary variable t 2 O (thought of as time), whereby for a given T > 0 we introduce functions 2(.) : [0, T] + [Zmin 2max] and E(-) [zmins Zmax] - R such that: {(-) is Lipschitz, 2(-) is differentiable on (0, T), and we have 2 = (()( for all & E (0, T). In a slight abuse of notation, we define the path w.r.t. t
as (1) w (=(1)) : L E [0, TT. To enhance structural clarity, we denote zzz
2 U Zi| and
represent the certain matrix inversion
H lz) (2) Uz
P P(w'l2) Q (w* (z)
Q(w*lz) R
].
(11)
Ongxnz xnz
where the rows of matrix Uz are the constant differentials, v. for i E ZE and w for j E 2, and
H(w 2)
H
Σ
(L,(w") (W') DV (yi Tww (x:)) + Σ Σ
2 (w" (w") (w")
1=1 KEIE, KETZ,(W (wr)
kedi (wr)
O Oi (en)s("))) (w*)V2
(Bn+1 (0 7, (xn+1)).
KE (W*)
(12)
Now are fully equipped unveil the structure of homotopy path, as shown in next subsection.
3.3 Piecewise smooth structure & Unified view
To describe the structure, we define the kink (non-smooth point) as the point that 0% 0t. hit the restriction bound in (9), or set in (10) is violated so the entire structure changes.
Theorem 3. Given optimum (wō; 20) at to, and assume that to is not kink, then there exists open neighborhood of to such that w" (t) is a C¹ function of and satisfies the following autonomous system
w=(()) a = ((w",
Σ
0 0/ (em.,("")@e
0. V.D. (Un+1(z), ,'w (xx+1))
(EI2
(13)
where P(w*lz) is obtained from the definition in (11), and the Ör., On, can be solved from (8).
The (13) offers an explicit gradient flow of the solution path in underlying optimization space. Solving this ODE numerically would recover all the optimal parametric solutions, which provide the conformity scores and one can obtain the required p-values (2) that used for exact conformal prediction via (3).
Theorem 4. The optimality solution (w" ((), z(()) has unique trajectory for 1 E (0, The w w*(() is continuous if selections D4 (:), Di, (.) are convex. Furthermore, if gradients of constraints 0} are affinely independent at the solution w" (z) over an open neighborhood of 2, then the coefficient paths gr On, are unique and continuous at Theorem 5. On optimality path with set configuration (10), the coefficients for constraints satisfies
(V (w): (g.(w) = 0) J (Vh,(w) Why
(ee(w))) (w*)
] - --Q(w") - [D((w))+) +u]
T2 e
(14)
'In principle similar algorithm can be developed for the general convex constraint where the h2 are relaxed convex. but that beyond the scope of current paper.

---

The essence of Theorem lies its suggestion that the dynamics of w*()) )) piecewise continuous, i.e. (t) maintains smoothness between two adjacent kinks. By considering specific choices of E(- and (x+1(z), our system (13) generalizes some previously studied methodologies in fast conformalization. First, consider the scenario with equally spaced discretization of the interval [0, Tİ. namely fx = k h for some fixed step-size h' > 0. Thus, the sequence 2 := =(tx) is approximately given by # Σς: h E(zx). Intuitively, the choice of g(-) controls the dynamic of z()) and generalizes some previously considered sequences {=x] } for the problem (5). For example, recover the where Q(w") is from (11), and
Σ iENL
Vi + Σ iEPs
V. Σ w.
2 =
JEPI
Although Theorem 3, 4, and 5 are highly technical and may difficult to grasp on first glance, they lay the groundwork for practical application, illustrated later in Section 4. Specifically, Theorem ensures continuity, which is fundamental for the numerical ODE solvers. Theorem 5, on the other hand, provides rule for handling constraints.
Theorem 6. Suppose that Di, (-) is p-strongly convex for 0, D2, is o-strongly convex a > O, and ((w") 2), 0g D (-), O₂ D (.) are all locally E-Lipschitz continuous. Suppose further that E(-) is Lipschitz continuous [2mins Zmaxi and satisfies (5(2)] C for all [2mius Zmax] Then, it holds that .-..) defined in (13) uniformly er L--ipschitz continuous with er = Ol
(x+ 1++1++EN ET Ayo for any E [Zmin Xmax] when the active selections I,, In are fixed.
20t
letting {(=) 1 recover the arithmetic sequence in [12] and letting {(z) geometric sequence in [17].
4 Fast conformalization algorithm
The complete algorithm the fast exact conformalization is outlined in the plate referred as Algorithm 1.
Algorithm Fast Exact Conformalization Algorithm
Input: Training data (x,, y: new covariate X range [zmin: Zmax], initial solution wi. regu-
larization strength {A, { miscoverage level (0, 1).
\\ Full Path Generation
2: z < 0, set Ng. PE. Pi and all Tr, In by w
3: while 0 < S 7max
4: while partitions NE. Pr. Pt, Ir. In are met do
5: Calculate H(w 12), rz as in (12), (14).
6: Solve ODE system (13).
7: end while
8: Update Ne. PE, Pı, Lz, lg by index violator(s).
9: end while
10: z + 0.
11: while 2min = 0 do
12: Repeat the above procedure analogously for negative values of 2, obtaining
(w*(z) Zmin < = 0).
13: end while
14: \\ Conformal Set Generation
15: i to to
do
Calculate conformity score path A, for i-th sample.
17: end for
Calculate the path of P by (2).
T(x,+1) + {yr+1* P 2 a
Output: Conformal prediction 1 (x++1).

---

Table 2: Numerical results for average empirical coverage, average length of the conformal prediction set, and the total number of kinks observed. One standard error is given in the parenthesis following the average number.
(Parameter)
Coverage
Length
Coverage
Length
Coverage
Leagth
fried
(001()
5.82(0.53)
(.81())007)
5.55(0.94)
0.80(0.001)
5.3000.72)
6
0.82(0.007)
5.54/0.12)
0.82(0.007)
5.6300.44
0.80(0.003)
5.35(0.02)
(LS())
5.63/0.16)
5.29/0.52)
5.26:0.271
cadata
GPH(A: - 0.008)
0.82(0.001)
11.64:0.15)
0.81(0.004)
11.38(0.36)
0.80/0.003)
11.34(0.27)
cadata
GTX 00002)
0.83.0.008)
10.72/0.91)
0.51(0.00:)
10.39/0.97)
0.80(0.001)
10.13(0.21)
elevator
(7M1A==0.000
0.83.00003)
01.09(0.58)
0.81(0.007)
01.34(0.97)
0.80(0.000)
10.68(0.81)
fried
= =0.0.
0.81(0.002)
19.14(0.78)
19.69/0.900
19.05/0.19)
cadata
=0 =0002)
0.82
10. 19.99/0.39
0.80(0.002)
10.16/0.20
0.80(0.0002
19.14(0.82)
elevator
IGR(A =0
0.82(0.008)
18.99
0.81(0:001)
18.53
0.81(0.005)
18.46(0.75)
7
iime NL3
nunnnng Time MOSt SM
2a.10000 2011
20
Rurning Time
2007 4394
5081
2048 10485 12242
19776
350
1800
2750
2403
4203
5400
6300
1200
4043
9048
13500
38000 22508 2700e 31306 3006
Size of dataset (delta
Size
detaset (fried)
Size of dataset (fried)
Figure 2: The running time under different sizes datasets.
4.1
On solving (11)
To avoid the direct computation of matrix inversion (11), our practical algorithm involves sweep operator [22, 23]. Suppose A is an p p symmetric matrix, sweeping the k-th diagonal entry
A&k # 0 of results in a matrix A with entries
Âs ARs
Au
Ask
(i*
Aug
Akj (i+ k).
Áij A.
Aus (i.j k). (15)
Ace
Ast
Ask
Since the sweeping (15) preserves symmetry, all operations can be performed solely on either the lower or upper-triangular part of A to ease the computational burden [24]. To begin with, we initiate
H=)
with a sweeping tableau as
and further sweeping of diagonal entries of block H
Uz
M
Mar
yields M
Then we reinitialize
tableau in the form of
Ma:
Maa
M
and further sweeping of diagonal entries of block M22 makes R Q (w")a) P(w"l=)
Compared direct
inversion, it also decreases a O(p² + +n2) storage space.
4.2 Efficiency
Algorithm shows very favourable behavior empirically, and converges remarkably faster than the standard grid-search type algorithm. We argue that this observation is actually quite natural. Indeed, our algorithm can follow the ground truth solution path, and the numerical integration process is fully deterministic, which avoids large fluctuations between the iteration steps like stochastic gradient descent. Therefore, the solving process of Algorithm exhibits more stable character being completely deterministic and has no extensive loops, which explains the much faster convergences observed in practice. In contrast, the standard grid-search type method would cost N --times the original batch iterative algorithms, where N is the number of grid points.
5 Numerical experiments
We provide experimental results on real-world benchmarks to validate our derived algorithm. All experiments presented in this study were conducted on workstation running the Ubuntu 18.04 operating system, equipped with Intel Xeon Gold 5218R CPUx64 and 60.9 GB of RAM. We integrate system of ordinary differential equations using lsoda from the FORTRAN library, where an

---

interface for SciPy is available using the odepack. The concrete parameter settings of ODE solver are shown in the Table 3, wherein the numerical solver exploit the Runge- Kutta method of order 4 or 5. The parameterizers are set to (=) = 4z, {(z) 1, respectively.
Table 3: List of the key parameters in the numerical solver.
Parameters
Descriptions
Values
rtol
allowed relative error in the solution allowed absolute error the solution vector of critical points
1e-6
atol
1.e9
tcrit
by known explicit kinks
ho
initial step size for the integration maximum absolute step size allowed minimum ahsolute step size allowed maximum number steps allowed for each point
0.02+| 122a(2ma
Emin
hmax
0.1* Smaz
Zmann)
hmin
1e-7
mxstep
mxordn
maximum order be allowed for the non-stiff method maximum order to be allowed for the stiff method. cxtra printing at method switches
mxords
ixpr
True
axhnil
maximum number of messages printed
tfirst
the required order of first two arguments
full_.output
return dictionary of optional outputs
True
Model For evaluation, here we employ 3 specific forms of (1), i.e. Nonnegative Least Squares
(NLS) [25]. Graph-guided Fused Model (GFM) [26], and Inverse Gaussian Regression (IGR) [27].
Conformalization A conformal prediction set with target coverage level 0.8 (a 0.2) is calculated for each sample in testing set using each the 4 methods, i.e., the standard grid-point evaluation method (Grid1) [1], with warm-restart strategy (Grid2) [28], the split conformal prediction method (SCP) [4], and our exact conformalization method in Algorithm (Exact). We use the conformity score function A, -ly 'Iw- (x:)). Conventionally, the interval [y 1 (part of the input) can be chosen sim- ply as [W]]] Mm]]l where Y/11 S Vi2) S I y/n] are the order statistics of the response variable. In experiments we set the search range even more conservatively. enlarg- ing the sample range by 50% of length (y v
25
GrGalay 6.33
method
23
Eeucsh
11
225 200
220
252
204
Number grids (fried dataset)
Figure 3: The training time against grid numbers.
[Mn 0.25( U[u)): Mmn) + 0.25()()) m[]))]-
Dataset Our experiments ducted using real-world datasets. We em- ploy real-world datasets from OpenML [29] and UCI repository [30] in simula- tions. We randomly partition the dataset into training set, testing set, and calibra- tion set (used in SCP) with 70%. 10%, and 20% of the total samples. To facilitate op- timization, we have standardized the entire original dataset by removing the mean and scaling to unit variance for the features, and adjusting the mean of all labels to O.
2. bam
A--l2
Running time (log(ai)
0.8
Probability
2--20-2
4 s
6.2
y
0.33
4,
100
300
400
kinks
k
Figure The histogram of kink numbers and the run- ning time of Algorithm I against k where & lives in yn+1 := k E N).
Setup Our central claim is twofold, en- compassing both accuracy and efficiency. We first report the average empirical coverage, average length of the prediction set in Table 2. Re- garding running efficiency, we present average training time per dataset in Figure 2 while varying the scale of training set. In Figure we compare the training times when different grid numbers are used in Grid1 and Grid2. We further plot the histogram of kink numbers, and the running time against various + (-) in Figure 4.
Results & Analysis From Table we observe that all these methods provide valid and nearly perfect coverage. The grid and exact method give similar lengths, where the slight difference is due

---

to the rounding between neighboring grid points. The SCP produces wider intervals due to a less efficient use of data. Given Figure our exact method is much faster than the baselines, with same solid performance. We can also learn from the Figure 3 that the time of Algorithm still compares favorably against the grid-search type method, even when the grid sparse. Figure 4 found that there exists tiny number of kinks in majority runnings, which offers hope for the future expansion of our algorithm, and indicates that the choice of Un++1 can make a difference efficiency, as will determine the solving interval and the total query times of gradient.
6 Conclusion
In this work, we present a unified framework and an elaborate algorithm with statistical analysis for fast exact conformalization regarding generalized parametric estimation. We illustrate the strong and competitive performance of proposed methods in series of benchmarks.
In future work, potential direction is consider scenarios where labels are multidimensional, such as multi-task learning, in which the label space y would be indexed by multiple independent parameters (21,...> =x). Under such conditions, the homotopy solution path would extend solution surface, and our ODE system could be reformulated as a corresponding system of partial differential equations. Additionally, compared some previous work, Algorithm offers increased speed but at the cost of higher memory requirements. It necessitates storing all training samples throughout the process for gradient queries. We believe it would be interesting to use recent advancements like the Kronecker- factored approximate method to potentially enhance the memory scalability.
Acknowledgement
I would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the presentation of this paper.
References
[1] Glenn Shafer and Vladimir Vovk. A tutorial conformal prediction. Journal of Machine Learning Research, 9(3), 2008
[2] Victor Cheroohuukov, Kaspar Wüthrich, and Yinchu Zhu. Distributional conformal prediction. Proceedings of the National Acudemy of Sciences, 11848)::21077411 18, 2021.
[3] Osbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Practical adversarial multivalid conformal prediction. Advances in Neural Information Processing Systems, 35:29362-29373, 2022.
[4] Matteo Fontana, Gianluca Zeni, and Simone Vantini. Conformal prediction: unified review of theory and new challenges. Bernoulli, 29(1):1-23, 2023.
[5] Anastasios N Angelopoulos, Stephen Bates, et al. Conformal prediction: A gentle introduction. Foundations and Trends@ in Machine Learning, 16(4):494-51, 2023.
[6] Jonathan Alvarsson, Staffan Arvidsson McShane, Ulf Norinder, and Ola Spjuth. Predicting with confidence: using conformal prediction in drug discovery. Journal of Pharmaceutical Sciences, 110(1):42-49, 2021.
[7] Margaux Zaffran, Olivier Féron, Yannig Goude, Julie Josse, and Aymeric Dieuleveut, Adaptive conformal predictions for time series. International Conference on Machine Learning, pages PMLR, 2022.
[8] Chen Xu and Yao Xie. Conformal prediction for time series. IEEE Transactions Patlern Analysis and Machine Intelligence, 2023.
[9] Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncer- tainty sets for image classifiers using conformal prediction. International Conference on Learning Representations, 2020.
10

---

[10] Paul Melki, Lionel Bombrun, Boubacar Diallo, Jérôme Dias. and Dean-Pierre Da Costa. Group- conditional conformal prediction via quantile regression calibration for crop and weed classifi- cation. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pages 623, 2023.
[11] Harris Papadopoulos, Vladimir Vovk, and Alexander Gammerman. Regression conformal prediction with nearest neighbours. Jourmal of Artificial Intelligence Research, 40:815-840, 2011.
[12] Jing Lei. Fast exact conformalization of the lasso using piecewise linear homotopy. Biometrika, 106(4):749-766 2019.
[13] Jing Lei, James Robins, and Larry Wasserman. Distribution-free free prediction sets. Journal of the American Statistical Association, 108(501):278-287, 2013.
[14] Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. Journal the American Statistical Associ- ation, 1095233):044111111 2018.
[15] Geoffrey S Watson. Linear least squares regression. The Annals of Mathematical Statistics, pages 1679-1699, 1967.
[16] Evgeny Burnaev and Vladimir Vovk. Efficiency of conformalized ridge regression. In Confer- ence on Learning Theory, pages 605-622. PMLR, 2014.
[17] Eugene Ndiaye and Ichiro Takeuchi. Computing full conformal prediction set with approximate homotopy. Advances Neural Information Processing Systems, 32, 2019.
[18] Etash Kumar Guha, Eugene Ndiaye. and Xiaoming Huo. Conformalization of sparse generalized linear models. In International Conference Machine Learning pages 1 11871-11887. PMLR, 2023.
[19] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29. Springer, 2005.
[20] Andrzej Ruszczynski. Nonlinear optimization. Princeton university press, 2011.
[21] David Avis and Komei Fukuda. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. In Proceedings of the seventh annual symposium on Computational geometry, pages 98-104, 1992.
[22] James H Goodnight. A tutorial on the sweep operator. The American Statistician, 33(3): 149-158, 1979.
[23] Roderick JA Little and Donald B Rubin. Statistical analysis with missing data, volume 793. John Wiley & Sons, 2019.
[24] Kenneth Lange, J Chambers, and W Eddy. Numerical analysis for statisticians, volume 2. Springer, 1999.
(25) Rasmus Bro, Sijmen De Jong, and Sijmen De Jong. A fast non-negativity.coostranne least squares algorithm. Journal of Chemometrics: A Journal of the Chemometries Society, 11(5): 393-401, 1997.
[26] Xi Chen, Qihang Lin, Seyoung Kim, Jaime G Carbonell, and Eric P Xing. An efficient proximal gradient method for general structured sparse learning. stat, 1050, 2010.
[27] Venkata Seshadri. The inverse Gaussian distribution: statistical theory and applications, volume
137. Springer Science & Business Media, 2012.
[28] Parikshit Ram. On the optimality gap of warm-started hyperparameter optimization. In International Conference on Automated Machine Learning, pages 12-1. PMLR, 2022.
[29] Joaquin Vanschoren, Jan N Van Rijn, Bernd Bischl, and Luis Torgo Openml: networked science
in machine learning, ACM SIGKDD Explorations Newsletter, 15(2):49 60, 2014.
11

---

[30] Arthur Asuncion and David Newman. Uci machine learning repository, 2007.
[31] Fuzhen Zhang. The Schur complement and its applications, volume 4. Springer Science & Business Media, 2006.
[32] Dimitri Bertsekas, Angelia Nedic, and Asuman Ozdaglar. Convex analysis and optimization. volume 1. Athena Scientific, 2003.
[33] Michael Ulbrich. Nonsmooth newton-like methods for variational inequalities and constrained optimization problems in function spaces. Habilitation, Technical University of Munich, Munich, 2002.
[34] Stefan Scholtes. Introduction to piecewise differentiable equations. Springer, 2012.
[35] Walter Gautschi. Numerical analysis. Springer Science & Business Media, 2011.
[36] Jack Levine and HM Nahikian. On the construction of involutory matrices. The American Mathematical Monthly, 69(4):267-272, 1962.
12

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See Section and Section 3.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
See Section 2, Section 3 and Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: Yes]
Justification: The contribution is primarily new statistical framework. See Section 4 and Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [No]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
SorreeeSbmissioooooe icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips.c..c wttp:ccccppbccccccecce.cccccccct pppuulccguuudes..../ CCodeSubeieeeeeee
/ cetbbmissiii iemiisssioni www.nnoolllooooeeeooeeooo onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: See Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https /ttp///eerpp//eeeee
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
[NA]
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
16

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Licenses are available referring to the provided links.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi whhersswithodeee thcode. com/ datasets
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
17

---

Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
18


Reviews:
[{"review_id": "YETO1rRGMs", "reviewer": "Reviewer_ji5B", "summary": "The authors introduce an algorithm to compute prediction intervals for conformal prediction in the context of empirical risk minimization  (ERM) with constraints on the parameters. To do so, the authors derive a differential equation solved by the ERM estimator as a function of the last label to compute a solution path and generate the conformity scores for each possible label.\nIn their numerical experiments, the method is compared to the baseline (which simply iterates over a grid of labels) and split conformal prediction (SCP). The authors observe that their method provide the correct coverage and roughly the same interval length as the baseline for a fraction of the numerical cost.", "questions": "- It would be nice to have a comparison with the running time of split conformal prediction (while the computations are not exactly the same) as in Figure 3 to get a sense of the order of magnitude of the computation time.\n- For simple settings such as Lasso, it would have been nice to compare the computation time with methods from the literature e.g. [Lei, 2017].\n- How does the method scale (in terms of running time) with the dimensionality ? \n\nMisc. questions : \n- In equation (12), is there a difference between Q(w*) and Q(w* | z) from (9) or is the conditioning on z implicit ?", "limitations": "Some limitations are discussed in Appendix F. As the paper is quite theoretical, the question of societal impact is not applicable here.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The method introduced by the authors works for general scenarios, extending beyond the cases of Ridge / Lasso.\n- On the numerical side, their methods appear to provide a significant improvement (in terms of running time) over the baseline while having the same interval size. As a by product, the authors show that their method can be used to update the estimator when a single label is changed in the training data.", "weaknesses": "- Clarity : I found the mathematical details of section 3 to be difficult to follow and check (for the parts in the Appendix). I feel like some parts, while they are important for the rigor of the paper, could be explained after the introduction of Algorithm 1 or put in the Appendix. For instance Theorem 4 and Theorem 6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Many thanks for appreciating our research!\nDear reviewer ji5B,\n\nWe are truly grateful for your thoughtful review of our paper and for the encouraging support you've shown towards our work! In the following, we will provide a comprehensive response to your comments.\n\n---\n> can be used to update the estimator when a single label is changed in the training data\n\nThank you for your interest in our by-product. In fact, it allows for the simultaneous variation of multiple labels. These indices can form a subset $\\mathcal{D}$ (see line 320), making our Algorithm 2 more efficient.\n\n>  I feel like some parts ... could be explained after the introduction of Algorithm 1 or put in the Appendix\n\n- Thanks for your comments, and we fully understand your concerns.\n\n  - Regarding the burden of mathematical notation, we invite you to refer to our general response. As for the statistical derivations in the appendix, we acknowledge that they require a certain level of mathematical maturity to fully understand. However, we believe this will **attract interest from researchers in other fields** and help **bridge the communities of conformal prediction and numerical optimization**.\n\n  - Theorems 4 and 6 are crucial supports for our algorithm. Theorem 4 provides the foundational guarantee for Theorem 5, ensuring the computational feasibility of our core idea, which is essential for designing Algorithm 1. Theorem 6 is closely related to Corollary 1, offering geometric insights into the path and forming the unified view that we have claimed in the abstract. We consider these theorems indispensable parts of our contributions. \n\n- By your comments, we **deleted some minor technical paragraphs, and enhanced our descriptions to better link the theorems and algorithms, ensuring readers do not get lost.** We appreciate your suggestion!\n\n> a comparison with the running time of SCP as in Figure 3 to get a sense of the order of magnitude\n\nThank you for your constructive feedback! Our thoughts are as follows:\n\n- This work primarily focuses on optimization for full CP rather than SCP, so comparing efficiency (runtime) with SCP is not particularly meaningful.\n\n- SCP is theoretically guaranteed to be faster than standard full CP and our algorithm because **it only requires a single training on the training set** and then calculates conformity scores on calibration set [1]. In contrast, our algorithm needs to compute the solution spectrum w.r.t. entire label space, involving repeated calls to and fitting on the training set. The **order of magnitude can be easily estimated**; previous observations & analyses (e.g. [2]) have shown it to be approximately $\\frac{1}{N_{\\text{gird}}}$ times that of standard full CP, which already provided in our results.\n\n- Figures 3/4 are already content-rich; adding more curves might reduce the readability of the results.\n\n> compare the computation time with methods from [Lei, 2017].\n\nPlease refer to general rebuttal, section ③. Thank you!\n\n> How does the method scale (in terms of running time) with the dimensionality?\n\n- Thank you for your insightful question. In Algorithm 1, we essentially performed two things: one is numerical integration over $[z_{min}, z_{max}]$, and the other is refreshing the current partitions $\\mathcal{N}\\_\\text{E}$, $\\mathcal{P}\\_\\text{E}$, $\\mathcal{P}\\_\\text{I}$, $I_L$, $I_\\Omega$ at the kinks.\n\n  - Let the dimensionality be $p$, the complexity of the latter is $\\mathcal{O}(p)$, as we analyzed it in Section 4.3. \n\n  - The complexity of the former when varying $p$, however, is somewhat nontrivial. This is primarily due to a fact that the computational complexity of numerical solvers for ODEs *can indeed differ significantly* based on the employed method and the particularities of the equations at hand. For example, factors like the system's stiffness and the length (or area) of the solving interval, can play a crucial role [3]. Without further assumptions, it is difficult to analyze the complexity of numerically solving the entire ODE system. However, recent studies (e.g., [4]) have increasingly shown that oracle complexity (a.k.a. query complexity) plays a very significant role throughout the computation. Using our method under the sweep operator and Sherman–Morrison formula (see Section 4.1, Appendix B.8), the upper bound on oracle complexity is at most $\\mathcal{O}(p^2)$. \n\n- Due to the adaptiveness of numerical solvers, it is challenging to establish an exact / tight relationship between overall runtime and $p$. We believe **it should lie between linear and quadratic growth**.\n\n- Given the suggestions of other reviewers, we temporarily don't intend to further expand the appendix length (e.g., adding more experiments).\n\n> the difference between Q(w*) in (12) and Q(w* | z) from (9) or is the conditioning on z implicit ?\n\nYour understanding is correct; they all refer to the same block matrix. When presenting our Theorem 5, we use $\\mathbf{Q}(\\mathbf{w}^\\star)$ to represent $\\mathbf{Q}(\\mathbf{w}^\\star|z)$, and $\\mathbf{D}^{\\prime}(\\mathbf{w}^\\star)$ to represent $\\mathbf{D}^{\\prime}(\\mathbf{w}^\\star|z)$. **This is to reduce the symbol density in the main body** without causing ambiguity.\n\nNote in appendix, we still use the full notation of them (see line 773) due to the needs of the analysis.\n\n---\n**References:**\n\n[1]  \"Conformal prediction: A gentle introduction.\" Foundations and Trends in Machine Learning, 2023\n\n[2] \"Fast exact conformalization of the lasso using piecewise linear homotopy.\" Biometrika, 2019\n\n[3] \"Diagonally implicit Runge–Kutta methods for stiff ODEs.\" Applied Numerical Mathematics, 2019\n\n[4] \"A characterization of functions over the integers computable in polynomial time using discrete ordinary differential equations.\" Computational Complexity, 2023\n\n**We thank the Reviewer ji5B again for your insightful feedback and strong support of our submission! If you have any remaining concerns or further inquiries, please do not hesitate to let us know.**", "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": "unG46RqL44", "reviewer": "Reviewer_4Aeq", "summary": "In the manuscript \"Towards fast exact Confomralization of Generalised Parametric Estimation\" the authors provide a very interesting generalisation of an approach, fundamental even if a bit disregarded in the mainstream literature on Conformal Prediction, that aims at computing the whole solution path of a regression algorithm in order to render more efficient the estimation of (full) conformal prediction sets.\nAfter having described the very general framework in which they operate, the authors proceed to obtain theoretical insights about their methodology. More specifically, they characterise the underlying structure of the path to be an inherently piecewise smooth function.\nAfter doing so they propose a practical methodology to compute such path, essentially by solving an ODE.\nThe method is then evaluated with an extensive empirical study, showing its remarkable performance", "questions": "- Some claims are a bit vague. I understand why the authors focus on Full conformal, but I doubt a reader not fully aware of Conformal Prediction will be able to do it (Paragraph 2 of the introduction). I suggest to the authors to be more explicit about the reasons\n- Footnote of page 1 - the authors need to clarify that symmetricity in this case is intended in the specific sense used in the CP literature, which in fact is defined later on... or omit the consideration which seems rather tangential\n- Rather then \"inexact\" I would rather talk about lack of (finite sample) calibration.\n- I don't understand why the already present approaches are deemed to be \"black boxes\". moreover I don't think that \"opening the black box\" is the right narrative to use in this case. Maybe something along the line of \"let's generalise...\"\n- The label space is a generic $\\mathcal{Y}$. I am wondering if the authors can be more specific about, for instance, possible extensions of their approach to the relatively rich field of Conformal Prediction for multivariate and complex data.", "limitations": "The authors state relevant open problems on the subject.\nSince the very clear applicative interest this paper may have, I believe that adding something on the methodological side (such as the need for extensions to the multivariate case, or some ideas about possible extensions to a dependent data setting) could be very interesting.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "- The work is extremely thorough and deep, and the discussion about the different peculiarities of their approach\n- The referencing work is quite remarkable, as it depicts very clearly the literature landscape where the authors are moving\n- While building on previous works, the authors provide a very novel take on the subject, proposing a completely new methodology, of great practical usability", "weaknesses": "- The authors are not tackling an easy task in terms of communication, having to tackle, and in a fairly deep way, many different topics. For this reason I find the presentation a bit \"nebulous\" and vague at times\n- No code is provided, which has prevented me from verifying some of the claims.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Many thanks for acknowledging our work!\nDear reviewer 4Aeq,\n\nWe extend our sincere gratitude for dedicating your valuable time to reviewing our paper and for expressing your appreciation and support for our work! In the following, we will provide a comprehensive response to your questions.\n\n---\n\n## Ⅰ. Introduction\n\n>  I understand why the authors focus on Full conformal, but I doubt a reader not fully aware of Conformal Prediction will be able to do it (Paragraph 2 of the introduction).\n\nYour feedback is extremely beneficial to us. \n\nI believe **Reviewer jxtf** shares similar concerns. Please allow us to briefly describe the differences between the two approaches.\n- In SCP, we first split the entire dataset into a training set and a calibration set. On the training set, we use algorithm $\\mathcal{A}$ to obtain the model parameter $\\mathbf{w}^*$. Then, on the calibration set, we get prediction values using $\\mathbf{w}^*$, and subsequently obtain conformity scores to calculate the conformal set. This process involves only one single fitting.\n- Full CP, on the other hand, avoids data splitting and does not discard any sample points. It loops over all possible $y_{n+1}$ values and for each new candidate, we refit the augmented data to compute the $\\mathbf{w}^*$. Based on these solutions we obtain a set of training scores. Therefore, the traditional computation of full CP is significantly more expensive.\n\n> I suggest to the authors to be more explicit about the reasons\n\nThank you for your constructive suggestion. I agree that we may omitted some relevant background in the introduction. We have added the necessary descriptions in the second paragraph of the \"*1. Introduction*\" on the first page to help readers better understand our considerations.\n> Footnote of page 1 - the authors need to clarify that symmetricity in this case is intended in the specific sense used in the CP literature ... or omit the consideration which seems rather tangential\n\nThank you for your thoughtful feedback! We find your advice very reasonable, and after our careful consideration, we have decided to remove this footnote to reduce the technical density of the main body. We also agree that it does not directly relate to the main theme of this work.\n\n## Ⅱ. Technical Phrase\n\n> Rather then \"inexact\" I would rather talk about lack of (finite sample) calibration\n\nThanks for your insightful advice. We have revised the relevant statements on the second page.\n\n> I don't understand why the already present approaches are deemed to be \"black boxes\"\n\nThis is our oversight; please refer to the general response, and sorry for the confusions.\n\n> I don't think that \"opening the black box\" is the right narrative to use in this case\n\nWe have revised the relevant phrases according to the general rebuttal above. They now should be reasonable in the new context. \n\nIf you have any further thoughts, please feel free to share them.\n\n## Ⅲ. Potential Extension\n\n> The label space is a generic $\\mathcal{Y}$ ... if the authors can be more specific\n\nYes, in the current version of our analysis, an implicit setting is $\\mathcal{Y} \\subseteq \\mathbb{R}$. In this work, $y_i\\in\\mathcal{Y}$ need to be unidimensional. However, we are happy to discuss various extensions; please see the following question.\n\n> for instance, possible extensions of their approach to the relatively rich field of Conformal Prediction for multivariate and complex data.\n\nWe believe our work has the potential to extend CP to multivariate and complex data that you mentioned. Specifically,\n\n- If the data features include multiple interrelated variables, we can use well-studied techniques such as ODE discovery [1] to encode the correlations and synergistic effects between variables. If the labels are multidimensional (e.g., in multi-task learning), the label space $\\mathcal{Y}$ will also be indexed by multiple independent parameters $(z_1, ..., z_p)$. In this case, the homotopy solution path would turn into a solution surface, and our ODE system can be rewritten as a similar partial differential equation system.\n\n- In complex environments, such as dynamic data or online conformal inference, we can leverage knowledge from our by-product as a starting point to adapt our framework to an online mode for parameter updates. \n\nFor other types of data like network dataset, we can use neural ODEs [3] for model reparameterization, considering the network structure and connection patterns. We also believe this would be very interesting, as previous baseline work [2] has even begun to explore this direction (albeit in a somewhat different setting). More potential extensions will be left for future work. We believe this paper can serve as an important cornerstone, attracting subsequent researchers to fill these gaps.\n\n> the very clear applicative interest this paper may have\n\nWe are very pleased to hear that you find our new algorithm to be widely applicable.\n\n> adding something on the methodological side (such as the need for extensions to the multivariate case, or some ideas about possible extensions to a dependent data setting) could be very interesting.\n\nThank you for the helpful comments. We agree with your viewpoint, and inspired by your suggestion, we will add discussions on extensions in our Section 6 or Appendix F. We also hope to attract researchers from other relevant communities.\n\n---\n**References:**\n\n[1] \"Discovering governing equations from data by sparse identification of nonlinear dynamical systems.\" PNAS, 2016\n\n[2] \"Fast exact conformalization of the lasso using piecewise linear homotopy.\" Biometrika, 2019\n\n[3] \"Neural Ordinary Differential Equations.\" NeurIPS 2018\n\n**We thank the Reviewer 4Aeq again for your insightful feedback to improve our paper quality and strong support! If you have any remaining concerns or further inquiries, please do not hesitate to let us know.**", "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": "Ba8KgZinE5", "reviewer": "Reviewer_x8xk", "summary": "The paper introduces a method to compute exact conformal prediction intervals that have statistical guarantees. The method improves from previous work in three ways:\n* The conformal interval has exact guarantees instead of approximative\n* The loss function family covered is larger than convex, same for the regularizer family\n* It works for linearly constrained problem \n\nThe core idea is to build a path from  value $t\\in [0,1]$ to targets $y$ and find how the parameters of the function $\\mathbf{w}$ evolve as we vary $t$ (and therefore $y$). The weights $\\mathbf{w}(\\cdot)$ as a function of $t$ satisfy an ODE that can be solve with standard solvers when the functions in the loss function and constrains are piecewise continuously differentiable.\n\nThe authors then show the improvement in terms of coverage, dataset size and more importantly speed on several datasets.", "questions": "* Does the method require more memory than the baseline methods?\n* I am not convinced by the explanation given for classification(1067-1074). This might be valid for some ranking tasks but not when there is no order in the classes, in my opinion. Could you illustrate it, even with a toy example?", "limitations": "* You mention not implementing [13] because it uses underlying structure and therefore might be faster. It would still be interesting to see if the gain of speed from using [13] instead of your method is significant or not, in cases where it applies. \n* (see comment on classification)", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 4, "strengths": "* The examples are compelling are show very well the improvement\n* The contribution is pretty significant as it widens the possible families of loss functions", "weaknesses": "* My main issue is that the paper is very hard to read. It is too notation heavy and dense. For example, why use $\\hat \\theta$ instead of $\\theta$? The $\\hat {}$ make them look like estimators when it is not the case here\n* Classification is a big application of conformal prediction, it is unfortunate that we do not have an example .\n* Figure 1 might be a bit misleading. It seems to imply that the method works for higher dimensions of $\\mathcal{Y}$ but it does not seem the case", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Many thanks for acknowledging our research!\nDear reviewer x8xk,\n\nWe want to express our heartfelt thanks for taking the time to review our paper and for your kind words of appreciation and support for our work! In the following, we will provide a comprehensive response to your review comments.\n\n---\n## Ⅰ. Notation\n> It is too notation heavy and dense\n\nThank you for your valuable comments. We understand and appreciate your concerns regarding the mathematical notation. **For a comprehensive explanation, please refer to our general response.**\n\nWhile the statistical derivations in the paper indeed necessitate a certain level of mathematical proficiency, we believe they will appeal to researchers from diverse fields. This, in turn, can foster collaboration between the communities of *conformal prediction* and *numerical optimization*.\n> why use $\\hat{\\theta}$ instead of $\\theta$? The $\\hat{~}$ make them look like estimators\n\nThank you for your thought-provoking question! In our intention, $\\hat{\\theta}^k$ in the analysis is indeed used to denote **the estimator of ${\\theta}^k$**. Technically,\n\n- Let us recall that Lemma 3 (page 20) explains that for the special case of $PC^r$ functions, there is a simpler expression for the Clarke subdifferential $\\partial f$ (Definition 5) in terms of the gradients of the selection functions $\\\\{D^k\\_f\\\\}$. Hence, the Clarke subdifferential of $f$ is easy to compute and that the set of nonsmooth points of $f$ can essentially be described as a level set of certain smooth functions (see our line 73), i.e., $\\sum\\_k \\theta^k D^k\\_f$, where the $f$ could be any function in Assumption 1 or 2.\n\n- Since the combination of $\\theta^k$ can be non-unique (as long as they form a valid level set), it is challenging to use this set of non-vanishing coefficients to obtain the first-order approximations for nonsmooth analysis. However, in theory, we can compute a set of coefficients $\\\\{\\hat{\\theta}^k\\\\}$ (based on the analytical properties of $f$) to uniquely represent the convex hull of the gradients of the selection functions, i.e., we can have $\\partial f=\\sum\\_k \\hat{\\theta}^k \\nabla D^k\\_f$.\n\n- A similar concept is: the model parameter $\\mathbf{w}$ in Eq. (1) could be somehow arbitrary as long as it satisfies the constraint conditions, whereas $ \\mathbf{w}^*$ is the estimator of $\\mathbf{w}$, found as the optimal solution of the objective after training / fitting.\n\nFor a more detailed introduction into nonsmooth analysis, we refer to [1]. Inspired by your question, **we are considering using Carathéodory's theorem to reduce the number of selection functions needed for computing the Clarke subdifferential**. Alternatively, **we may change it to a more concise notation, if it does not cause ambiguity in the main body.**\n\n## Ⅱ. Label Space\n> Classification: it is unfortunate that we do not have an example\n\n- We do agree with your view that classification problems are an important application. In our current version, both the inverse Gaussian deviance and group lasso estimators **can be used for classification tasks as long as the labels in the dataset are categorical** (please refer to their respective original papers).\n\n- We primarily showcase regression tasks here because, in conformalization for regression tasks, the standard full CP computation is more demanding. **In regression tasks, the label space is dense rather than discrete, making it more representative and challenging** compared to classification tasks.\n\n> Figure 1 might be a bit misleading. It seems to imply that the method works for higher dimensions ...\n\nWe sincerely appreciate this feedback, and we have added the $\\mathcal{Y} \\subseteq \\mathbb{R}^1$ in its caption. We believe that readers will easily recognize this when reading Section 2 as well.\n\nMotivated by your comment, if $\\mathcal{Y}$ is higher-dimensional (e.g., in multi-task learning), we cannot use a single scalar variable $z$ to loop over the entire space. In this case, our $y_{n+1}$ would be indexed by $\\[z_1, \\ldots, z_p\\]$. The intuitive idea is that the homotopy path would turn into a **solution surface** [2], and our ODE system could be rewritten as a similar partial differential equation system. *While it introduces new challenges, it's very promising. Now we'll not expanding into this scenario, as it would significantly increase the notational complexity.*\n\n> Classification: ... when there is no order in the classes. Could you illustrate it?\n\nWe are not senior researchers in classification theory, but if unordered classes cannot be encoded into a 1-dimensional $y$, then you're correct. Thanks again for your insights! It's very helpful in improving the quality of work.\n\n## Ⅲ. Computations\n> Does the method require more memory than baseline?\n\nYes, due to character limitation, we invite you to see Appendix F.3 for discussion. Meanwhile we believe that in most cases, the practical bottleneck of the conformalized algorithms is runtime cost rather than system memory.\n> the gain of speed from using [13] instead of your method\n\nSorry for any confusion caused. The work [13] and our Algorithm 1 are completely identical in actual implementation, so there will be no gain in speed (if we dismiss the randomness). **Please refer to section ③ in our general rebuttal**.\n> You mention not implementing [13] because it uses underlying structure and therefore might be faster\n\nThis was our oversight, and **we have now corrected the relevant descriptions** in Appendix D.3 (line 964). We apologize again for any confusion caused! We will continue to check for such details.\n\n---\n**References:**\n\n[1] \"Introduction to Nonsmooth Optimization: theory, practice and software.\" Springer, 2014\n\n[2] \"Grouping pursuit through a regularization solution surface.\" JASA, 2010\n\n**We thank the Reviewer x8xk again for your insightful feedback and strong support of our submission! If you have any remaining concerns or further inquiries, please do not hesitate to let us know.**", "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": "8Xxk7QcmKY", "reviewer": "Reviewer_KUWB", "summary": "This paper proposes a new method to accelerate the computation of full conformal prediction sets, a task that traditionally requires a computationally intensive grid-search approach. The proposed method aims to streamline this process, potentially reducing the need to refit the predictive model for each test point and each possible outcome value. However, the paper suffers from poor writing, heavy mathematical notation, and an overly dense presentation, while also employing tricks like small font sizes in figures and text wrapping to extend beyond the standard page limits. Due to these significant issues, I believe that a thorough review of this paper is not feasible at this time. I would consider this a 'desk rejection' from my perspective. I hope the authors will not be offended or discouraged, as this is not a judgment on the quality of their research, which I was unable to carefully assess, but rather an invitation to improve the presentation to facilitate the review process.", "questions": "- Could you try to enhance the writing quality and clarity of the paper to make it more accessible to a broader audience?\n- Would you consider shortening the paper, or alternatively, submitting it to a venue that accommodates longer articles? This paper might turn out to be much easier to understand in an extended version. My philosophy is that if the content cannot be effectively conveyed within 9 pages, it is better suited for a different format. Forcing it to fit within this limit does a disservice to the readers by compromising clarity and comprehensiveness.", "limitations": "The primary limitation of this paper is its poor writing quality and extremely dense presentation, making it difficult to follow and understand. In its current form, the potential audience of this paper might at best be limited to a very narrow group of readers, which unfortunately does not include this reviewer.", "rating": 3, "confidence": 1, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- This paper studies an important problem in conformal inference, namely to speed up computations for full-conformal prediction.\n- The proposed method could potentially reduce the computational burden associated with conventional grid-search approaches.", "weaknesses": "- The paper is not very well written, it's very dense, and difficult to understand, even for those familiar with the broader field.\n- The paper is too long and only fits within the page limits due to some \"tricks\" such as using very small font sizes in figures and wrapping text around figures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Thankful for your constructive feedback!\nDear reviewer KUWB,\n\nWe are very grateful for the effort you have put into reviewing our work and for recognizing the importance of our research problem. We have addressed and acted upon your main criticisms, and we are looking forward to further interaction with you. \n\n---\n## Ⅰ. Text Wrapping & Figure Size\n\n> employing tricks like small font sizes in figures and text wrapping to extend beyond the standard page limits\n\n>  due to some \"tricks\" such as using very small font sizes in figures and wrapping text\n\n- Thank you for your feedback. Firstly, we would like to politely point out that *text wrapping* and *figure scaling* are ***not*** tricks we specifically employed in this paper. **Such practices are quite common at NeurIPS and other similar venues like ICML / ICLR**. \n  - *e.g.*, P7 in [1], P6-P8 in [2], P8 in [3], P5-P7 in [4], etc.\n\n- We understand your concerns. All the images inserted in this paper, whether experimental results or logical diagrams, are **vector graphics and can be enlarged arbitrarily without distortion**. \n  - Based on your feedback, **we promise to further adjust the layout** by merging some runtime comparison figures with sections in the appendix. This will allow us to **increase the font size of each figure** in the main body.\n\n- Besides, kindly note that **if this paper was accepted, we will have one extra page** in the camera-ready version.\n\n- As per our response to Reviewer ji5B, **we will also move some minor technical content to the appendix or remove it entirely.** For example, some corollaries, Sections 4.1 and 4.2. This will create further space in the main body, reducing its content density.\n\n## Ⅱ. Clarity & Length\n\n> However, the paper suffers from poor writing\n\n> The primary limitation of this paper is its poor writing quality\n\nDespite the mathematical notation being dense (in some sections), our overall structure should be pretty clear and is well organized, as acknowledged by other reviewers. Our introduction part (including *motivation*, *high-level ideas*, and *related work*) and experimental sections have been well understood by several reviewers. This indicates that **the presentation of our paper, while not perfect, still meets the basic standards of a technical paper**. We are also continuously improving our writing.\n\n> The paper is too long\n\n> the content cannot be effectively conveyed within 9 pages... Forcing it to fit within this limit does a disservice by compromising clarity and comprehensiveness\n\n- We fully understand your worries regarding the length and formatting of the paper. At first, please let us kindly point out that **all content in our appendix merely provides further explanations of the technical results in the main bofy, rather than introducing new arguments.**\nEven if we were to remove the entire appendix (except proofs), the content of our main body still remains entirely self-contained, which has included the core theorems, discussions on assumptions, and statistical descriptions of the novel framework. \n\n  - Any reader familiar with optimization and conformal prediction can follow the algorithmic steps presented in the 9 pages, without reading the appendix. Therefore, we respectfully *disagree* with the viewpoint that the content cannot be effectively conveyed within main body.\n\n- We believe the length and (technical) clarity involve a trade-off.\n  - We could, of course, write several hundred pages listing every definition and detailing every step of derivations, but this would be inappropriate for a formal research paper.\n  - Thus, in addition to the main body, we have included extensive discussions in the appendix, which help readers understand the core framework from various perspectives. **These in-depth discussions and extra experiments aim to enhance the *clarity* and *technical comprehensiveness* of our research findings**, stimulate readers' thoughts on the algorithmic details, and attract researchers with different backgrounds. (as some content like *IVP in differential equation* might be overly fundamental for readers who are already familiar with them)\n\n- In appendix we dedicated **10 pages to study our by-product**. Since the main focus is conformalization, **we can simply delete this part and immediately reduce the paper's length by nearly 20%**.\n\n> Would you consider shortening the paper\n\n**Yes**! Thanks again for your advice.\n\n## Ⅲ. Community Interest\n\n>  difficult to understand, even for those familiar with the broader field\n\n> audience might at best be limited to a very narrow group of readers\n\nThank you for your thoughtful comments. Fully understanding the details of theoretical framework indeed requires *a certain level of math maturity*. However, **for those engaged in algorithmic research, referring to the pseudo-code and the explanations provided in the appendix should be sufficient** to apply our new algorithm, and promote its application at a more practical level, even for those outside the ML community.\n\nAs we explained, the **contributions of this work encompass both algorithmic and new theoretical advancements**. By NeurIPS guideline, this community spans over optimization theory, statistics, and probabilistic ML. I believe our work will also attract researchers beyond those specializing in conformal prediction.\n\n---\n**References:**\n\n[1] \"Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances.\" ICLR 2024\n\n[2] \"In-context impersonation reveals Large Language Models' strengths and biases.\" NeurIPS 2023\n\n[3] \"Steve-1: A generative model for text-to-behavior in minecraft.\" NeurIPS 2023\n\n[4] \"SaNN: Simple Yet Powerful Simplicial-aware Neural Networks.\" ICLR 2024\n\n**Meanwhile we would like to highlight our main contributions again in the following.** *We respectfully ask you to read our response and consider stronger support based on the soundness and contribution of this work.* Our sincere thanks once again.", "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": "y4T7GBFmGm", "reviewer": "Reviewer_jxtf", "summary": "The authors study the *solution path* of constrained optimization problems when one training label varies in ${\\mathbb R}$. In the Conformal Prediction framework, this is equivalent to studying the output of a Full-CP algorithm. The paper extends the approach to optimization problems with general constraints and a piece-wise differentiable objective.", "questions": "- In the abstract, you mention the computational burden of full-CP algorithms. What about Split-CP? Does \"strong assumptions\" mean data inefficiency?\n- Is the solution path unique? What happens for overparametrized models?\n- In what sense the prediction sets of [18] and [19] do not have statistical guarantees? Can't one combine the upper bound on the estimation error and standard CP validity?\n- Is the formalism developed in Section 3 only needed because of the general constraints and piece-wise assumption in  Equation 1? \n- Intuitively, what does produce a kink in $w_*(t)$? \n- Why do you fix $\\alpha=0.8$?\n- In Algorithm 1, does $z$ need to be discretized?\n- Why Split CP does not appear in Figures 3 and 4?\n- Why is the standard approach, i.e. ``Grid1/Grid2`` in Table 2, outperformed by Split CP? Normally full-CP is expected to be more efficient.", "limitations": "The authors do not discuss the limitations of their work. They may have added a few lines about the applicability of their assumption and the limited choice of predictors in the experiments.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Characterizing the solution path of a series of smoothly varying optimization problems is relevant, even beyond the CP framework.\n- The Lagrangian reparametrization approach is interesting.\n- The proposed method seems to be more efficient than Split CP.", "weaknesses": "- It would be helpful to clarify from the start what \"opening the black box\" means, e.g. by listing the assumptions needed to obtain the solution path efficiently. \n- The authors should justify better why they need \ni) general constraints and \nii) piece-wise differentiable objectives. \nA warm-up section describing the unconstrained case would also help. Has the unconstrained and globally differentiable case been considered elsewhere?\n- The method seems to apply in a convex neighbor of the optimum. Assuming the algorithm is initialized there, the optimization problem is quadratic. The authors should comment on the difference between their method and the standard full-CP approach in the presence of several local optima.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Many thanks for appreciating our work!\nDear reviewer jxtf,\n\nWe deeply appreciate your commitment in reviewing our paper and your encouraging words of support for our work! In the following, we will provide a comprehensive response to your review comments.\n\n---\n> clarify what \"opening the black box\" means\n\nPlease refer to general rebuttal, section ②. Thank you!\n> should justify better why they need i) constraints ii) piece-wise differentiable\n\nThis is primarily **to achieve the versatility of the objective**. Nowadays many learning tasks essentially involve unconstrained optimization, but it's well known that many loss functions are not globally differentiable, so we believe this extension is natural. Moreover, constraints are also not rare in real-world tasks, e.g., ordinal support vector machines used for classification and regression [1], linear programming in operations research [2], and certain fairness constraints in fairness classifications [3], all of which can be accommodated within our Eq. (1). Several models in experiments also validate this, as current work cannot handle their conformalizations.\n\nFollowing your constructive suggestion, **we added relevant examples and further motivation** in Section 2.\n> Has the unconstrained and globally differentiable considered elsewhere?\n\nAll baselines prior to our work have studied the unconstrained case (Table 1), and mostly require the objective function to be globally differentiable. For research on solution paths that unrelated to conformalization, please refer to Appendix F.1.\n> The method seems to apply in a convex neighbor of the optimum\n\nWe believe that homotopy continuation does not necessarily occur within the convex neighborhood (even if the selection function is strongly convex), but is generally within a closed or bounded neighbor of the optimum. More theoretical properties will be explored in future work.\n> The authors should comment on the difference ... in the presence of several local optima\n\nStandard full-CP uses batch-training solvers (e.g. various SGD), making it difficult to control their optimization behavior. Whether the solver can escape saddle points depends on its inherent properties and user parameters. On our algorithm, please see next question. \n\nWe added further explanations based on your comments.\n> Is the solution path unique? What happens for overparametrized models?\n\nComputationally, the Picard–Lindelöf theorem proves that the solution of numerical ODE is unique. Geometrically, if regularity conditions are met, then points of the path (with non-vanishing KKT multipliers) is locally the projection of a higher-dimensional smooth manifold onto optimization space, hence it's not unique but our algorithm can indeed follow a path of stationarity points.\n\nOverparametrized case: please see Appendix F.4.\n> computational burden: What about Split-CP? Does \"strong assumptions\" mean data inefficiency?\n\n(Characters limitation) please see response to Reviewer 4Aeq. Thanks!\n\nIt means that previous methods cannot be extended and are not sufficiently general.\n> In what sense the [18, 19] do not have statistical guarantees? Can't one combine the ...?\n\nThanks for valuable feedback! This thought is reasonable, and aligns with one of the motivations behind these works. We have revised our writing to indicate that there are no optimal statistical guarantees, as their solutions for minimization are indeed not exact.\n> Is the formalism developed in Section 3 only needed because of the general constraints and piece-wise assumption?\n\nYes, our framework would be simplified (but less useful) without the above settings.\n> what does produce a kink in $\\mathbf{w}^\\star(t)$?\n\nKinks (or non-smooth transition points) on the path are caused by non-differentiable points, including boundary constraints hitting or the non-differentiable points within the loss / regularizer itself (e.g., the $\\ell_1$ norm at $0$). Appendix C.3 provides an intuitive illustration of kinks in a 2-dimensional optimization space.\n> Why fix $\\alpha=0.8$?\n\nThis is only needed for numerical simulations. Our algorithm primarily focuses on *full path generation*, while $\\alpha$ is used in *conformal set generation* (the second stage). Like the baselines, we use standard way to compute the conformal set, so **the setting of $\\alpha$ has no impact on our core algorithm**. We observed that most related works set $\\alpha$ around 0.1 or 0.2, so our setup is reasonable. Let us know if you have specific concerns.\n\nAnother insight from your question is that we could consider $\\alpha$ as a *variable* to study the underlying relationship between the resulted conformal set and $\\alpha$, but this beyond the current scope.\n> does $z$ need to be discretized?\n\nThe need for discretizing $z$ depends on the property of the label space $\\mathcal{Y}$. In regression, since $y_{n+1}$ is continuous, there's no need to discretize $z$. In classification problems, $z$ is generally discrete for computational purposes, as we focus on the discrete $y_{n+1}$ of interest.\n> Why SCP does not appear in Figures 3, 4?\n\n(Characters limitation) please see response to Reviewer ji5B. Thanks!\n> Why is the standard approach outperformed by Split CP?\n\nIndeed, the SCP results are better in a few lines. That's may due to our choice of grid points not being overly dense to ensure fairness in comparisons. That's also related to the data distribution and calibration set partitioning in SCP.\n> The authors do not discuss the limitations\n\nTechnical limitations are described in Appendices F.3 and F.4.\n\n---\n**References:**\n\n[1] \"Support vector machines–an introduction.\" Springer, 2005\n\n[2] \"Linear programming and its applications.\" Springer, 2007\n\n[3] \"Fairness constraints: Mechanisms for fair classification.\" AISTATS 2017\n\n**We thank the Reviewer jxtf again for your insightful feedback and strong support of our submission! If you have any remaining concerns or further inquiries, please do not hesitate to let us know.**", "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:
# Gratitude to All the Reviewers 😃
---

Dear Reviewers,

Thanks for the time and effort you have devoted to evaluating our submission #451. We also wish to express our appreciation for your recognition of the strengths of this work, including:

> (ji5B) The method introduced by the authors **works for general scenarios**, extending beyond the cases of Ridge / Lasso

> (ji5B)  their methods appear to **provide a significant improvement** (in terms of running time) over the baseline while having the same interval size

> (4Aeq) the authors provide **a very interesting generalisation** of an approach, fundamental even if a bit disregarded in the mainstream literature on CP

> (4Aeq) The work is **extremely thorough and deep**, and the discussion about the different peculiarities of their approach

> (4Aeq)The **referencing work is quite remarkable**, as it depicts very clearly the literature landscape where the authors are moving

> (4Aeq) the authors provide a very novel take on the subject, proposing a completely new methodology, of **great practical usability**

> (x8xk) The **contribution is pretty significant** as it widens the possible families of loss functions

> (x8xk) The conformal interval **has exact guarantees** instead of approximative; The loss function family **covered is larger than convex**, same for the regularizer family

> (x8xk) The **examples are compelling** ... show very well the improvement

> (KUWB) This paper **studies an important problem** in conformal inference

> (KUWB) The proposed method could potentially **reduce the computational burden**

> (jxtf) Characterizing the solution path of ... optimization problems **is relevant, even beyond the CP framework**

> (jxtf) The Lagrangian reparametrization approach **is interesting**

> (jxtf) The proposed method seems to be more **efficient than** Split CP

You have also raised some questions/concerns, to which we have replied in our detailed rebuttal. Here we provide responses to several recurring concerns as follows

### ① Notation is dense / heavy

$\quad$*(Reviewer ji5B, Reviewer x8xk, Reviewer KUWB)* 

We extend our gratitude to the reviewers for this valuable feedback. This work is not solely a contribution at the algorithmic level; it also provides new statistical insights and an analytical framework in the optimization theory. NeurIPS hosts a diverse community, drawing participants from a broad range of backgrounds; we believe our work could attract researchers not only from the field of conformal prediction but also from *optimization* and *learning theory*.

And unfortunately, **under the premise of ensuring mathematical rigor and technical correctness, it appears that further simplification of symbols / theorems is not feasible currently**. It is worth noting that our initial draft was significantly more complex than the current one, and the present version is likely the most concise iteration we have achieved through repeated exploration. To achieve this goal, our efforts have included:
1) When deriving the ODE system (11) or (14), we initially arrived at complex preliminary conclusions, with formulas at least twice the length of the current ones. We simplified the obtained expressions by utilizing matrix computation properties and non-convex analysis, enhancing their human readability. This is reflected in **page 24 to 25** of our proof.
2) We have carefully considered how to present our notation system and the main core theorem outcomes. We defined **a certain matrix inversion** (9), which includes many of the common structures used in theorems, significantly reducing the notation density in the paper.
3) To enhance readers' understanding of the framework presented, we provide a more in-depth discussion and explore the potential for simplifying notation under stronger assumptions. You are welcome to visit our **Appendix F.2** for discussions on this point. We also applied it to two simple toy cases (*i.e.*, vanilla Lasso and elastic net) in Appendix C.

As you suggested, conciseness and readability remain our goals, and we are continuously contemplating how to further improve in this regard. 

### ② On the “open the black-box”

$\quad$*(Reviewer 4Aeq, Reviewer jxtf)*

We appreciate the reviewers' careful reading and for pointing this out. We realize that our current phrasing is incorrect. 

Our use of "black-box approach" should indeed refer to grid-search based methods (*i.e.*, existing batch trainings on different $y_{n+1}$), as they completely disregard the underlying potential path structure. "Black-box approach" should not describe the fast conformalization methods (*i.e.* baseline in Table 1; whether precise or imprecise), as they all reformulate the conformalization problem as a path-following optimization  problem and use white-box methods to compute solution spectrum. **We have corrected the relevant phrasing.** Thanks!

### ③ Experiment: conformalization of Lasso

$\quad$*(Reviewer ji5B, Reviewer x8xk)*

Several reviewers suggested we compare our work with the Lasso conformalization algorithm from (Lei, 2019) [13]. We appreciate this feedback, but we would like to politely point out that Lasso inherently falls under generalized parametric estimation (see Table 1). Thus, (Lei, 2019) [13] is **a special case within our framework**. Further technical analysis is available in Appendix C.1, which demonstrates how our framework recovers the piecewise linear homotopy path when specifying the loss to be quadratic and the regularizer to be $\ell_1$-norm. 

**From a practical perspective, these two algorithms are essentially the same**, making the comparison potentially meaningless. We apologize for not clarifying this in our experimental setup and have revised the confusing descriptions in the appendix. Thanks!

---

Please feel free to let us know if you still have any remaining concern, we will be happy to address them. Thanks for your time and support!

$ $

Best Regards,

Submission451 Authors

Meta-review: There is an overall agreement among the evaluators about the value of the result presented in this paper. The reviews and the discussion were detailed and provided many directions to improve the presentation further. The paper provides a valuable contribution towards efficient conformal prediction, a promising approach to uncertainty estimation in many practical settings. I recommend acceptance as a poster.
Decision: Accept (poster)