Conformal Training with Reduced Variance

Reviewer:

Q1: How does VR-ConfTr handle situations with limited/imbalanced calibration data, and how does this affect coverage guarantees?

Authors:

Please note that, as we remarked above, the main contribution of our work is our approach to effectively overcome the sample-inefficiency of the existing ConfTr algorithm. Hence, effectively using the samples available in the calibration batch when simulating conformal prediction in-between training updates is precisely the sharp advancement that we provide and the key motivation for our research effort. In order to be effective, VR-ConfTr does need a sufficient number of samples to be used to simulate conformal prediction in-between training updates. However, we remark that our result is precisely to show that we can effectively improve the sample-efficiency over the ConfTr benchmark, as we show analytically and empirically. We concur though that the point raised by the reviewer is relevant and further studies on these cases - with limited availability of training samples to be used to simulate conformal prediction during training - are an interesting venue for future work.

Reviewer:

Q2: The paper mainly focuses on MNIST-type datasets, which restricts the demonstration of generality and robustness. How would VR-ConfTr perform on high-resolution images?

Authors:

With respect to datasets with high resolution images, note that our key contribution in this paper is to detect and provide an effective solution to the sample inefficiency problem of the original ConfTr algorithm. This is a critical problem even with benchmark datasets (with low resolution images) and relatively small models. We believe that our work is therefore a significant first step towards the possibility of applying conformal training techniques to large scale models and datasets. The experiments with the medical dataset OrganA-MNIST and the clear superior performance and effectiveness of VR-ConfTr as compared to ConfTr with this relatively more complex dataset are promising in this direction. We believe that hyper-parameter tuning needed for higher resolution images datasets and large-scale models necessitates extensive investigation and it is beyond the scope of this paper.

Thank you for your review. We will address all your concerns below:

Reviewer:

1. VR-ConfTr relies on a large calibration set to accurately estimate the quantile estimator $\hat{\tau}$ and its gradient $\hat{\frac{\partial \tau}{\partial \theta}}$, which are critical for variance reduction.

Authors:

Please note that a sufficiently large calibration batch size is one of the requirements for the original ConfTr algorithm. Indeed, the primary motivation behind VR-ConfTr and one of the key findings of our work is that ConfTr not only relies on large calibration batches, but also fails to efficiently utilize the available data samples during training. In this direction, VR-ConfTr takes a major step towards effectively optimizing models during training according to conformal prediction efficiency metrics. This is achieved thanks to our novel "plug-in" approach with which we can replace the sample quantile gradient ${\frac{\partial \hat\tau}{\partial \theta}}$ with an improved, novel and provably sample efficient estimator $\widehat{\frac{\partial \tau}{\partial \theta}}$ of the population quantile $\frac{\partial \tau}{\partial \theta}(\theta)$

Reviewer:

2. While VR-ConfTr improves prediction set efficiency, it introduces additional computational steps, which may slow down training in scenarios with limited computational resources.

Authors:

Note that the computational cost of our proposed VR-ConfTr is essentially the same as ConfTr. In fact, our proposed "plug-in" technique consists in replacing a specific component in the gradient estimation pipeline of the ConfTr algorithm, which is the estimation of the population quantile gradient, $\frac{\partial \tau}{\partial \theta}(\theta)$. Indeed, by differentiating the objective directly as a function of the sample quantile $\hat{\tau}(\theta)$, ConfTr ends up using the gradient of the sample quantile $\frac{\partial \hat{\tau}}{\partial \theta}(\theta)$. As one of the main contributions of this paper, we show that this specific estimator is sample inefficient, and our proposed VR-ConfTr is specifically designed to replace it - thanks to our "plug-in" technique - with a better, provably sample-efficient estimator $\widehat{\frac{\partial {\tau}}{\partial \theta}}$. In particular, we adopt the $m$-ranking estimator, which can be seen as a special case of the $\epsilon$-threshold estimator, which, as we show analytically, provably reduces the estimation variance with the calibration batch size, i.e., it is sample-efficient. Remarkably, the computational complexity of this estimator is essentially the same as computing $\frac{\partial \hat{\tau}}{\partial \theta}(\theta)$ - which is what is done in ConfTr - because it just boils down to computing and averaging $m$ derivatives of conformity scores. The other parts in the estimation of the objective function gradient have exactly the same computational complexity for both algorithms, and thus we can conclude that the computational complexity of the two algorithms is essentially the same. We provide a more detailed description of this reasoning in a new dedicated Appendix E in the revised version of the paper.

Reviewer: I was unable to understand why (8) holds, or where it comes from.

Authors:

We apologize if the notation of this equation was not clear. Please note that the equation follows from taking the derivative of a function of multiple variables and the chain rule. This is also called the generalized chain rule in some textbooks (for example, see Theorem 4.10 in [R1]: Herman and Strand, Calculus, vol 3, 2018). In the paper, when writing

$

\frac{\partial}{\partial \theta}\ell(\theta, \hat{\tau}(\theta), X, Y),

$

we mean the derivative/gradient, over $\theta$, of the function $\ell$, which is a function of multiple variables, which are $(\theta, \hat{\tau}(\theta), X, Y)$. When writing

$

\frac{\partial \ell}{\partial \theta}(\theta, \hat{\tau}(\theta), x, y),

$

instead, we mean the partial derivative of $\ell$ with respect to the first variable/argument $\theta$. Now, the generalized chain rule (in vector form) can be written as follows: let $u(\theta)\in\mathbb{R}^n$ and $v(\theta)\in\mathbb{R}^m$ be two differentiable functions of $\theta$, and $f(u,v)$ a differentiable function of two vector variables $u$ and $v$. Then

$

\frac{\partial }{\partial \theta}f(u(\theta), v(\theta)) = \left(\frac{\partial u}{\partial \theta}(\theta)\right)^\top \frac{\partial f}{\partial u}(u(\theta), v(\theta)) + \left(\frac{\partial v}{\partial \theta}(\theta)\right)^\top \frac{\partial f}{\partial v}(u(\theta), v(\theta)),

$

where $\frac{\partial u}{\partial \theta}(\theta)$ is the Jacobian of $u(\theta)$, i.e., the matrix with $\frac{\partial u_i}{\partial \theta_j}(\theta)$ in the $i$-th row and $j$-th column (equivalently, $\frac{\partial v}{\partial \theta}(\theta)$ is the Jacobian of $v(\theta)$). Note that in the case of $\ell(\theta, \hat{\tau}(\theta), x, y)$, $x$ and $y$ do not depend on $\theta$ so we can focus on $\ell$ as a function of the two functions $u(\theta) = \theta$ and $v(\theta) = \hat{\tau}(\theta)$. Replacing these $u(\theta)$ and $v(\theta)$ in equation above, and replacing $f(u(\theta), v(\theta))$ with $\ell(\theta, \hat{\tau}(\theta), x, y)$ we see that then

$

\frac{\partial}{\partial \theta}\ell(\theta, \hat{\tau}(\theta), x, y) = \frac{\partial \ell}{\partial \theta}(\theta, \hat{\tau}(\theta), x, y) + \frac{\partial \ell}{\partial \hat{\tau}}(\theta, \hat{\tau}(\theta), x, y)\frac{\partial \hat{\tau}}{\partial \theta}(\theta),

$

which is precisely equation (8) in the submitted manuscript, where we used the fact that $\left(\frac{\partial \theta}{\partial \theta}\right) = I_d$, where $I_d$ is a $d\times d$ identity matrix, with $d$ the dimension of $\theta$.

We have included the above description and an additional derivation at a more granular level in the new Appendix B, "Useful Facts and Derivations" in the revised manuscript - specifically Appendix B.2, for completeness. We hope that the reviewer will find this satisfactory, and that the soundness of equation (8) and (9) is fully clarified. We are happy to discuss further otherwise.

[R1]: Herman and Strand, Calculus, vol 3, openstax, 2018 (freely available at https://openstax.org/details/books/calculus-volume-3/)

We thank the reviewer for their insightful feedback. We will address all your concerns below:

Reviewer:

1. The mathematical reasoning in the paper does not seem sound
2. Even if they were, the theoretical analysis seems lacking. Given these two points, the paper could still be held up by a comprehensive empirical analysis. However, while there is some empirical analysis, it is hardly comprehensive, and could be improved on (especially if it is needed in order to compensate for (1.) and (2.)).

Authors:

Thank you for your feedback. We provide our detailed responses regarding both soundness and meaningfulness of our theoretical analysis below where we address your concerns.

Reviewer: On the soundness of the mathematical reasoning:

The derivatives in equation (5) do not exist. As currently written, the chain rule cannot be applied. Perhaps it can be salvaged with subgradients, though.

Authors:

Thank you for focusing your attention on equation (5), we are very happy to address this concern, which also allows us to enrich and improve the clarity in the manuscript. We note that the derivatives in equation (5) do, in fact, exist with probability 1. This is true because (i) the conformity score function $\theta\mapsto E(\theta, X, Y)$ is continuous and differentiable in $\theta$, and continuous in $X$; (ii) samples $(X_i, Y_i)$ are sampled independently, and hence the probability of the event that two conformity scores are identical is zero; (iii) as a consequence of the previous point, the order statistics are $E_{(1)}(\theta) < \ldots < E_{(n)}(\theta)$ - notice the strict inequalities - with probability 1, and hence, for any fixed $\bar{\theta}$, continuity of $\theta\mapsto E(\theta, X, Y)$ guarantees that the permutations of indices $\omega(\theta)$ that correspond to the order statistics is such that $\omega(\theta) = \omega(\bar\theta)$ for $\theta$ in a sufficiently small neighborhood of $\bar\theta$, and thus $E(\theta, X_{\omega_{j}(\theta)}, Y_{\omega_{j}(\theta)}) = E(\theta, X_{\omega_{j}(\bar\theta)}, Y_{\omega_{j}(\bar\theta)})$. Hence, for any fixed $\bar\theta$ the map $\theta\mapsto E(\theta, X_{\omega_{j}(\theta)}, Y_{\omega_{j}(\theta)})$ is a composition of differentiable functions, and it is therefore differentiable, in the neighborhood of $\bar\theta$. Given that the choice of $\bar\theta$ is arbitrary, $\theta\mapsto E(\theta, X_{\omega_{j}(\theta)}, Y_{\omega_{j}(\theta)})$ is differentiable everywhere with probability 1.

We have added a note about the almost sure (probability 1) differentiability of $E(\theta, X_{\omega_{j}(\theta)}, Y_{\omega_{j}(\theta)})$ after equation (5) in the revised paper. For completeness, we have included a detailed and rigorous derivation of the differentiability of $E(\theta, X_{\omega_{j}(\theta)}, Y_{\omega_{j}(\theta)})$ in the revised paper, in the new Appendix B, namely "Useful Facts and Derivations" - specifically Appendix B.1. We hope that this high level explanation together with the detailed rigorous derivation in the appendix are satisfactory, and that the reviewer is fully convinced. Otherwise, we are happy to discuss further.

Derivatives that do not exist: the justification given in the rebuttal is very unsatisfactory (and the new appendix B.1 in the paper is not much better). First, continuity and iid do not imply that ties happen with probability 0. Second, unless I'm mistaken, almost sure differentiability is not enough to guarantee the validity of the chain rule, which is the key property used in the derivation in the paper. This is not a minor issue.
Now, I'll be honest, and please forgive me if I go too overboard or am incorrect here: reading this part of the rebuttal felt almost like reading mathematical nonsense. The reasoning was very reminiscent of the usual outputs of LLMs when doing mathematical proofs, in that at the same time it seemed very flawed, but with just a tint of plausibility that forced me not to dismiss it outright. And, to be honest, many bits of the original submission already gave me a slight LLM ick. Nevertheless, I have chosen not to report the paper as LLM-written -- and maintain that choice -- because I am quite uncertain of this, and would rather give a chance to the authors rather than to 'blindly' dismiss their work. Once again, I profoundly apologize if this comment was undue.
Either way, the much bigger issue is the lack of sound mathematical reasoning, which still stands.

Equation (8): ah yes, I'm not sure why I didn't see it the first time. All fine there. (Also, I don't think there is a need to add an introduction to multivariate derivatives to your submission just because of my slight :) )

Justification for lack of need of more experiments: given that the theoretical component of the paper -- which the authors claim a number of times in their rebuttal is their main contribution -- is still rather shaky, I don't think it justifies a weaker experimental analysis. Moreover, adding such experiments can only serve to make the paper stronger, and I urge the authors to consider it for a future revision.

Equivalence between the estimators: I understand that the authors claim there to be some sort of approximate equivalence between the estimators. I am still unconvinced; if you believe there is one, I suggest to prove it formally, and add it in the form of an additional proposition to the paper (even if just in the supplementary material). I would also very much like to see the experiments with the other estimator, even if the authors claim it to be worse. I will try soon to give one more read to the rebuttal given by the authors on this point to see if I missed something.

Given the issues (especially the soundness one, and precisely in the spot that the authors claim is their main contribution), I maintain my score.

\mathbb{P}(E_i = E_j) &= \int_{-\infty}^{+\infty}\mathbb{P}(E_i = E_j\,|\,E_j = e) p_{E_j}(e)\\mathrm{d}e\\
&= \int_{-\infty}^{+\infty}\mathbb{P}(E_i = e\,|\,E_j = e) p_{E_j}(e)\\mathrm{d}e\\
&= \int_{-\infty}^{+\infty}\mathbb{P}(E_i = e) p_{E_j}(e)\\mathrm{d}e

\mathbb{P}\left(\bigcup_{(i,j): i\neq j} \{(E_i = E_j)\}\right) \leq \sum_{(i,j): i\neq j}\mathbb{P}(E_i = E_j) = 0.

Reviewer: Derivative that do not exist: almost sure differentiability is not enough to guarantee the validity of the chain rule, the key property used in the derivation in the paper.

Authors: We disagree. First note that in any neural network with ReLU activations the loss function is almost surely differentiable, and the chain rule is routinely and reliably applied. We will now provide some additional technical details to further support our claims on almost sure differentiability. The order statistics $E_{(1)}(\theta), \ldots, E_{(n)}(\theta)$ can be rewritten as $\big(E_{(1)}(\theta), \ldots, E_{(n)}(\theta)\big) = \mathbf{s}(E_\theta(X_1,Y_1),\ldots,E_\theta(X_n,Y_n))$, where $\mathbf{s}:\mathbb{R}^n \to \mathbb{R}^n$ denotes the sort function, mapping $(e_1,\ldots,e_n) \in \mathbb{R}^n$ to the unique point $(e_{(1)}, \ldots, e_{(n)})$ in $\mathbb{R}^n$ given by permuting $e_1,\ldots,e_n$ in such a way that $e_{(1)} \leq \ldots \leq e_{(n)}$. It is not difficult to see that $\mathbf{s}$ is piecewise linear and thus differentiable almost everywhere. In fact, it will be differentiable everywhere except in the finite union of hyperplanes $\{(e_1,\ldots,e_n): e_i = e_j\}$ with $i\neq j$. Let $A_n$ denote that finite union. It is not difficult to confirm that, outside $A_n$, the Jacobian matrix of $\mathbf{s}$ is simply given by a permutation matrix corresponding to the sorting permutation (which is unique when $(e_1,\ldots,e_n) \notin A_n$). More concretely, if $\mathbf{s}(\mathbf{e}) = (e_{\omega_1(\mathbf{e})}, \ldots, e_{\omega_n(\mathbf{e})})$, where $\mathbf{e} = (e_1,\ldots,e_n)$ and $\omega = (\omega_1(\mathbf{e}),\ldots,\omega_n(\mathbf{e}))$ denotes the unique sorting permutation for $\mathbf{e} \notin A_n$, then the Jacobian matrix of $\mathbf{s}$ evaluated at $\mathbf{e}\notin A_n$ is equal to a matrix where the $j$-th row is equal to the $\omega_j(\mathbf{e})$-th row of the $n\times n$ identity matrix. Let $u_1,\ldots,u_n$ denote the columns of the $n\times n$ identity matrix. Then,

$

\frac{\partial\mathbf{s}}{\partial\mathbf{e}}(\mathbf{e}) = \begin{bmatrix}
    u_{\omega_1(\mathbf{e})}^T\\
    \vdots
    u_{\omega_n(\mathbf{e})}^T
\end{bmatrix},

$

(Note: $[ a_1 \vdots a_n]$ denotes a matrix with rows $a_1, ... , a_n$)

(see, e.g., Blondel, Mathieu, et al. "Fast differentiable sorting and ranking." ICML, 2020.) and thus we can expect the chain rule to be of the form

$

\frac{\partial}{\partial\theta} \begin{bmatrix}
    E_{(1)}(\theta)\\
    \vdots
    E_{(n)}(\theta)
\end{bmatrix}
= \begin{bmatrix}
    u_{\omega_1(\theta)}^T\\
    \vdots\\
    u_{\omega_n(\theta)}^T
\end{bmatrix}\begin{bmatrix}
    \frac{\partial E}{\partial\theta}(\theta,X_1,Y_1)\\
    \vdots\\
    \frac{\partial E}{\partial\theta}(\theta,X_n,Y_n)
\end{bmatrix}

$

where $\omega_j(\theta)$ is shorthand for $\omega_j(E_\theta(X_1,Y_1), \ldots, E_\theta(X_n,Y_n))$. Naturally, equation above holds almost surely. Let us confirm this formally. First, let $B_n(\theta)$ denote the event in which there are no ties in $E_\theta(X_1,Y_1), \ldots, E_\theta(X_n,Y_n)$, i.e. that $(E_\theta(X_1,Y_1), \ldots, E_\theta(X_n,Y_n))$ lies outside of $A_n$. As discussed earlier, $\mathbb{P}(B_n(\theta)) = 1$ for any $\theta$. Formally, the random vector $X$ and random variable $Y$ live in some probability space with some outcome space $\Omega$. Let $\xi\in\Omega$ denote a concrete outcome (we will avoid using the more common notation $\omega$ as it conflicts with previous notation). Now, if $\xi\in B_n(\theta)$, then $(E_{(1)}(\theta), \ldots, E_{(n)}(\theta)) = \mathbf{s}(E_\theta(x_1,y_1), \ldots, E_\theta(x_n,y_n))$ with $x_i = X_i(\xi)$ and $y_i = Y_i(\xi)$. Once we fix a concrete outcome, then $\theta \mapsto (E_{(1)}(\theta), \ldots, E_{(n)}(\theta))$ is just a regular function $\mathbb{R}^p \to \mathbb{R}^n$, where $p = \dim(\theta)$, and thus the usual notions of differentiability and chain rule from multivariate calculus are applicable. Let us fix $\theta = \bar{\theta}$. Following the argument in appendix B.1, where we note that the complement of $A_n$ is an open set, then, for every $\theta$ in some open neighborhood around $\bar{\theta}$, we have

$

E_{(j)}(\theta) = E(\theta, x_{\omega_j(\bar{\theta})}, y_{\omega_j(\bar{\theta})}),

$

where $\omega_j(\bar{\theta}) = \omega_j(E_{\bar{\theta}}(x_1,y_1), \ldots, E_{\bar{\theta}}(x_n,y_n))$ is constant in $\theta$. Clearly then $E_{(j)}(\theta)$ is continuously differentiable in $\theta$, with Jacobian matrix exactly as given in the chain rule equation above for outcome $\xi$, i.e. $X_i = x_i$ and $Y_i = y_i$. To conclude, note that, since $\xi \in B_n(\bar{\theta})$ and $\bar{\theta}$ were arbitrary, with $\mathbb{P}(B_n(\bar{\theta})) = 1$, it follows that the chain rule in the above equation holds almost surely.

Ties with probability zero: if we assume that the distribution is continuous (which was apparently being implicitly done), then indeed it is true. Okay on this bit, though I advise the authors to be more explicit about such assumptions in the future.

Almost sure differentiability is not enough: I stand by this point. First, the argument of "note that in any neural network with ReLU activations the loss function is almost surely differentiable, and the chain rule is routinely and reliably applied": this does not mean that it is because it is 'almost everywhere defined'. The typical explanation uses subgradients, which I pointed towards in my original review. As for the following, more in depth explanation: again, the authors are being too lax with 'almost everywhere' / 'almost certainly'. I see no justification that, e.g., the E function does not end up mapping a lot of points to the set that has measure zero, where the function is not differentiable. By this point, it's not a matter of whether this can be shown -- the fact that after so many revisions I am still finding soundness issues in the authors' proofs is worrying.

Experiments: the authors claim that "our main contribution is in identifying the sample-inefficiency in ConfTr and in providing an effective solution, with a fair comparison with ConfTr that clearly shows the superiority of our novel algorithm". However, this needs to be validated, through sound theory and/or substantial experiments. The theory does not seem sound -- and even if it was, it is hardly extensive -- and the experiments, while they would have been in decent quantity were the theory substantial, it is not, and so more would be required to validate the approach.

Given my substantial concerns, I maintain my score of rejection.

Thank you for all your questions related to notation and minor issues in the paper. We have addressed all your points in the revised paper - both in the main paper and in the appendix.

With respect to $a_{n+1}$, note that the equation written by the reviewer becomes precisely our (46) because $a_n = nf_n$

We updated (50) using $\preceq$ as suggested by the reviewer, and added two steps clarifying the final relation that is indeed $\preceq$

Thank you for your review, we are happy to address your concerns in the following.

Reviewer:

1. The proposed VR-ConfTr gradient estimation method uses sample splitting, where batch data are divided into calibration and prediction subsets. This approach might introduce sampling instability, particularly with smaller datasets or non-i.i.d. data. This limitation is not sufficiently analyzed in the paper, nor do the authors consider alternative sampling strategies that might enhance stability.

Authors:

Please note that the sampling instability in the ConfTr algorithm is precisely what our novel proposed plug-in algorithm (VR-ConfTr) addresses. In order to simulate conformal prediction during training, ConfTr needs to estimate the population $\alpha$-quantile ${\tau}(\theta)$ of the conformity scores. Splitting the batch into calibration and prediction is key to estimate $\hat{\tau}(\theta)$ during training. A poor estimate of ${\tau}(\theta)$ and its gradient $\frac{\partial{{\tau}}}{{\partial \theta}}(\theta)$ hinders learning. As we show as one of the main contributions of our paper, (ConfTr) falls short of providing a good estimate of $\frac{\partial{{\tau}}}{{\partial \theta}}(\theta)$ and thus utilizes the calibration data inefficiently. With our proposed VR-ConfTr algorithm, thanks to our plug-in technique and a variance reduced estimate of $\frac{\partial{{\tau}}}{{\partial \theta}}(\theta)$, we provably address this issue, remarkably without requiring a larger calibration batch and at essentially the same computational cost as ConfTr. In other words, we design an algorithm which is sample-efficient and effectively deals with the instability problem of ConfTr.

Thank you for your review. We are happy to respond to your concerns. We provide our point to point responses below:

Reviewer:

1. Some of the formulas are not clearly explained. In particular, what does the set ${E_{\theta}(X,Y) =\tau_{\tau}}$ represent? It seems $E_{\theta}(X,Y)$ is a random variable, $\tau_{\tau}$ is a scaler, but how to interpret it in ${E_{\theta}(X,Y) =\tau_{\tau}}$? Furthermore, what expectation you take with respect to in equation 11 and 12?

Authors:

Please note that $E_{\theta}(X, Y) = E(\theta, X, Y)$ is a (scalar) function (conformity score) of the sample $(X, Y)$ - where $X$ is the feature vector and $Y$ is the corresponding label - and of the parameter $\theta$. The event $E_{\theta}(X, Y) = \tau(\theta)$ means that the conformity score function $E_{\theta}(X, Y)$ is precisely equal to the population quantile $\tau(\theta)$. The expectations in equations (11) and (12) are taken with respect to the distribution of the sample $(X, Y)$, which is the only random object in the argument of the expectations, that is the function $\frac{\partial E}{\partial \theta}(\theta, X, Y)$, because we consider a fixed $\theta$ (as we do in Theorem 1). Please let us know if this is sufficient to clarify your concerns.

Reviewer:

2. How do you the value of $\epsilon$? Can you include some ablation studies to this hyper-parameter?

Authors:

In light of the reviewer's question, we have added section C.2 in the appendix, conducting an ablation study for the $\varepsilon$-estimator on the GMM dataset. We report both the bias and variance of the estimated quantile gradients for each different value of $\varepsilon$. Moreover, in section C.2 we explore the intimate connection between the $m$-ranking and the $\varepsilon$-threshold estimators both theoretically and empirically. We first note that a good choice of $\varepsilon$ changes significantly across iterations making it hard to find a single good hyper-parameter $\varepsilon$. A potential choice to effectively adapt $\varepsilon$ during training is the $m$-ranking estimator. The $m$-ranking estimator can be seen as a special case of the $\varepsilon$-estimator in which $\varepsilon$ is chosen as the smallest value for which $m$ samples' conformity scores fall within $\varepsilon$-distance from $\hat{\tau}(\theta)$. To empirically illustrate this connection, we have included an additional study validating the importance of dynamically tuning $\varepsilon$, demonstrating how the threshold $\varepsilon$ containing $m$ conformity scores significantly changes across epochs. We hope section C.2 in the appendix fully addresses the reviewer's question.

Reviewer:

3. What is the per-step computational cost of your algorithm compared to the ConfTr?

Authors:

The per-step computational cost of our proposed VR-ConfTr is essentially the same as ConfTr. In fact, our proposed "plug-in" technique consists in replacing a specific component in the gradient estimation pipeline of the ConfTr algorithm, which is the estimation of the population quantile gradient, $\frac{\partial \tau}{\partial \theta}(\theta)$. Indeed, by differentiating the objective directly as a function of the sample quantile $\hat{\tau}(\theta)$, ConfTr ends up using the gradient of the sample quantile $\frac{\partial \hat{\tau}}{\partial \theta}(\theta)$. As one of the main contributions of this paper, we show that this specific estimator is sample inefficient, and our proposed VR-ConfTr is specifically designed to replace it - thanks to our ``plug-in" technique - with a better, provably sample-efficient estimator $\widehat{\frac{\partial {\tau}}{\partial \theta}}$. In particular, we adopt the $m$-ranking estimator, which can be seen as a special case of the $\epsilon$-threshold estimator, which, as we show analytically, provably reduces the estimation variance with the calibration batch size, i.e., it is sample-efficient. Remarkably, the computational complexity of this estimator is essentially the same as computing $\frac{\partial \hat{\tau}}{\partial \theta}(\theta)$ - which is what is done in ConfTr - because it just boils down to computing and averaging $m$ derivatives of conformity scores. The other parts in the estimation of the objective function gradient have exactly the same computational complexity for both algorithms, and thus we can conclude that the computational complexity of the two algorithms is essentially the same.
We provide a more detailed description of this reasoning in a new dedicated Appendix E in the revised version of the paper.