Rejection via Learning Density Ratios

We thank the reviewer for sharing their insights and providing useful suggestions on improving our evaluation. Please find the rebuttal below.

Related Work

We thank the reviewer for their various references. We will make sure to include these in the next version of the paper. We would also be happy to add a dedicated related work section. In particular, discussion regarding softmax response and score-based vs abstaining classifiers would be added.
We would add this either to the main text (Sec 2) with the additional page / space of the camera ready (alongside some reduction on the GVI / DRO section) or via an additional appendix section.

Empirical evaluation can be improved (datasets)

Thanks for the dataset recommendation. Please see the shared rebuttal response section. We have added some preliminary results utilizing the MedMNIST collection.

Q1: Softmax Response (SR)

Our work primarily started from examining rejection approaches which were inspired by surrogate loss functions and cost-sensitive losses. These approaches formed the baselines which we considered (many of these papers did not consider softmax response).
Although we do not include softmax response as a baseline, we note that the density-ratio rejectors have a strong connection to this method.
In the case of the KL-divergence rejectors with the practical trick employed (as noted in Line 271 onwards), our rejector will threshold the model’s predictive entropy. This is similar to the maximum softmax score.
The theoretical framework of prediction using density-ratios presents a generalization of this elucidating further connections to DRO / GVI. We further believe that the sample complexity bounds do not have an equivalent in SR.

Empirically, as a result, our approach and naive threshold rejection using the softmax scores should be comparable (when both utilize temperature scaling).
The component of SR that we are missing is the calculation of the threshold according to a desired coverage guarantee. This would be a nice direction for future work to automatically prescribe $\\tau$.

We will include this discussion and connection to the SR in the next version of the paper.

Q2: DEFER without expert

One can utilize DEFER without human predictions by utilizing a ground-truth expert (one returning the data’s label). In particular, it has been shown that this interpretation provides a surrogate loss function of the 0-1-c loss function. This has been shown in $a, see Appendix A.2$ and $b$ which generalizes this. We are happy to include this discussion to make this baseline choice clear.

$a$ Charoenphakdee, Nontawat, et al. "Classification with rejection based on cost-sensitive classification." International Conference on Machine Learning. PMLR, 2021.

$b$ Cao Y, Cai T, Feng L, et al. Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses. NeurIPS, 2022.

We thank the Reviewer for praising the interesting nature of our proposed approach and for the insightful questions. We are glad that the Reviewer appreciates the different approach we have taken and hope that the connections to DRO / GVI / distributions can lead to new theories. Please find the per-point rebuttal below.

$...$ this method may only address low-dimensional data $...$

We agree that with a naive application of this approach, there may be problems in high dimensions. This is a weakness shared by other density ratio-style algorithms like importance weighting.
We would however note that there has been success in leveraging representation learning to operate in a lower dimension. This can be used as a potential work around, especially if the model weights of the original classifier is available.

This is a weakness seen in other density ratio-style approaches like importance weighting.

We would like to comment on the hyperparameters noted by the reviewer.

• We are unsure what hyperparameter $T$ the reviewer is referring to.
• $\\tau$ for the threshold can be treated as a hyperparameter. But it can also be used as a value to be found to satisfy a specific risk-coverage requirement. This can be equivalent to $c$ considered in the baseline approaches.
  Actually, Reviewer dzAs reminded us of some work which picks thresholds according to a coverage-modified-risk requirement $a$ . As future work, this might be an interesting future direction to our work.
• We agree that tuning may present some challenges $\\lambda$ and $\\alpha$. However, we note that picking $\\lambda$ and $\\alpha$ is equivalent to picking an appropriate divergence. This is equivalent to how picking a surrogate loss for the classifier-rejection 0/1 loss function has many options.

One additional note that we make about hyperparameter tuning of our approach, is that although there are potentially more individual parameters one may want to pick from, it is substantially cheaper to tune than the other baselines. Indeed, the process of learning the 1D normalization constant $b$ required for density ratio rejectors (Line 287) is substantially cheaper than learning typically a whole network as required by the baselines. For our approach, we can keep the base classifier fixed and we only need to learn $b$ (see Appendix P.III for discussion on the number of tunable parameters of the approaches).

$a$ Geifman, Yonatan, and Ran El-Yaniv. "Selective classification for deep neural networks." Advances in neural information processing systems 30 (2017).

Experiments (Weakness 3)

Please see the shared rebuttal section. Other reviewers also commented about adding other datasets for strong evaluation. We have taken Reviewer dzAs’s recommendation of considering datasets in the MedMNIST collection.

Q1: Calibration

Although calibration for the multiclass case is more challenging in practice than perhaps estimating $\\max P(y \\mid x)$, we shouldn’t dismiss theoretically motivated frameworks due to this reason.
From a practical point of view, there are still many approaches which have shown reasonable success. For example, the standard temperature scaling approach that we utilize in the paper; or various different ensembling-style methods which we do not explore.

Q2: Experts for DEFER

In essence, we are assuming that the experts replicate the ground truth labels.
This is equivalent to the reduction in $b, see Appendix A.2$ which provides a surrogate loss function for rejection. Essentially, the learning to DEFER loss function can be used to learn a general $g \\colon \\mathbb{R}^d \\rightarrow \\mathbb{R}^{K+1}$ classifier for $K$ classes with the last $K+1$ output dimension being used for rejection.
This reduction / interpretation was also commented by Cao et al. (reference $2$ of the reviewer) as their method generalizes this instantiation of DEFER.

We will make sure to clarify how we are using DEFER in the next version of the paper.

$b$ Charoenphakdee, Nontawat, et al. "Classification with rejection based on cost-sensitive classification." International Conference on Machine Learning. PMLR, 2021.

Q3: Comparing with $2$

Apologies, this seems to be a clarity issue. The GCE baseline tested in the paper is actually $2$ (in retrospect, this may not be as clear as we also cited the general cross-entropy loss function’s original paper). Following up on Q2 as well, this GCE baseline can be interpreted as a generalization of the surrogate loss derived from DEFER.

We thank the reviewer for their detailed reading and many suggestions for improving the readability of the paper. We will change “classification-rejection” to “classifier-rejector” as per the reviewer’s suggestion and space-permitting, will include the broader impact section in the main-body (or add a compact part of it in the conclusion). Please find other rebuttal points below.

Perhaps table representation or different way to show the result might help. $...$ Only three simple datasets were used in this paper

Thank you for the suggestion. We will add tables corresponding to different coverage targets to the paper. Please see the shared section to see a demonstration on an additional dataset added in the rebuttal period. We hope that the added dataset from the MedMNIST collection also alleviates the concern that the datasets we consider are only simple.

KL and $\\alpha$ divergence give almost exactly the same performance in all cases $...$ + Q1

We would first like to note that we do include a hyperparameter sensitivity plot in Figure VII of the appendix. This tests different $\\alpha$s greater than 1.
In terms of ranges of $(\\alpha \\geq 1)$-divergences, the change in performance-to-coverage is minor. This can also be further seen in the table provided in the shared response section (which more clearly shows that although the results are not identical, they are not significantly different).
One difference we did find was that the coverage curve “shortens” for $\\tau \\in$ 0, 1 $$. Although $\\tau$ can be increased in practice, the cut-off in coverage for \\tau \= 0 shortens.

Analysis of what kind of dataset characteristic makes the proposed distributional method more effective $...$ + Q4: Weakness under noise

We believe that the dataset characteristic and your question about weakness under noise are linked. In general, in the noiseless case, there doesn’t seem to be a specific characteristic between what makes our proposed distributional rejection more effective. In general, it seems that the distributional rejection is slightly better in this clean case (results in tabular format, see general response).
However, it becomes clear that from the drop in performance in the noisy dataset setting, that distributional rejection using $(\\alpha \\geq 1)$-divergences with our current proposed implementation is not as robust to noise as other methods. This makes sense as the current approach relies on the calibration of models, which would break under distribution shift.
A note here is that future work examining divergences used in robustness may help alleviate this issue.

$...$ writing and organization of this paper can be significantly improved.

We thank the reviewer for their suggestions on improving the writing and organization of the paper. The following summarizes the small changes regarding this topic that will be made:

• Additional space provided by the camera ready will be utilized for further experimental discussion (including some of the above discussed points in this rebuttal section) and a table summarizing experiments.
  A related work (sub)section dedicated for rejection will be added as suggested by Reviewer dzAS (possibly deferred to the appendix).
  The content for DRO and GVI will be reduced if needed.
• To shortcut the theoretical parts of the paper, we will add an pseudo-code block next to Figure 1 which summarizes the abstract algorithm of distributional rejection. In addition, we will reference specific equations used to define the ratio $\\rho$.
  Additional text referencing this will also be added in the intro and start of Sec 3.
• Frame / highlight environments will also be used on equations referenced in the pseudo-code, as suggested by the reviewer.
• We believe that the current structure of the Sec 2-4 works well from a theoretical analysis point of view. And the proposed changes above will shortcut and identify key components for implementation.

We are confident that with the +1 page, adding additional discussion, tables, and cosmetic highlights can be complete to improve the paper’s presentation.

Q2: Clarity on $\\phi'$ and $L'$

We would like to confirm that $\\phi'$ is the derivative. Actually, the $L'$ notation also can be interpreted as a functional derivative of $L$ on $Q(x)$. We will mention this notational choice to clarify why notation is set this way. Do feel free to comment if this still makes the notation of $L’$ confusing. We are open to changing this to another symbol if required, eg, via font $\\mathrm{L}$ or with a bar $\\bar{L}$.

Q4: Theorem 4.2

We agree with the reviewers comment that the theorem is restrictive. Its purpose is just to verify that the proposed distributional rejection method produces Chow’s rule under theoretically optimal conditions.
When the optimal classifier is not optimal, the optimal rejection becomes a thresholding function over the pointwise risk of the model (in the language of CPE classification, see reference $48, 49$ ).

We thank the reviewer for their praise of the mathematical presentation of the paper and their careful reading. We are happy to change the paper as per the reviewer's suggestions and will ensure that the typos and grammar improves. In what follows, we will answer Reviewer m8bi additional questions.

What is the meaning of "The maximization is adversarial over the marginal label distribution" in line 128?

This line was to clarify that in DRO for label noise (specifically reference $60$ ), typically the distribution which is “adversarial” only applies to the marginal label distribution and not the full joint distribution over both inputs and labels. Thus the set of adversarial joint distributions $Q(y) P(x | y)$ are generated by varying the marginal over labels $Q(y)$ whilst keeping the conditional equal to the data $P(x | y)$.

I had hard time to understanding the meaning of the "idealized rejection distribution" (as called. in line 157)

The best intuitive way of thinking of the idealized distribution definition is to remove the regularization term in Definition 3.1. This corresponds to the distribution which minimizes the current model’s loss. Hence its “ideal” for the current model / set of parameters.

especially because the following sentence $…$

For the follow up sentence, we further elaborate.
When $\\rho(x)$ is small, this implies that $Q(x) \\ll P(x) \\leq 1$. (Recalling that $Q$ is the idealized distribution and $P$ is the data distribution.)
Further note that from Definition 3.1 / Equation (8), $Q(x)$ being small implies that the loss $L’(x)$ cannot be too large (as otherwise we should reallocate mass from other x’s).
Hence wrt the data distribution $P(x)$, moving mass away for regions of $x$ where $\\rho(x)$ is small reduces the loss function.

Further, I can't understand why does it make sense not to reject where is relatively small? $...$ Or is the argument that we do not need to care the small probability mass in the first place as it won't incur a significant loss in expectation?

The reviewers comment about the values corresponding to loss probability mass and thus no significant loss penalty in expectation is correct. Our rejection approach focuses on losses at different inputs values, as per Definition 3.1.

Of course, this is from the perspective of our framework, so practically, various rejection rules may be needed to account for different types of uncertainty.
A future direction may be to consider alternatives to expected loss which account for low $P(x)$. For example CVaR etc.

An alternative theoretical reason for this style of thresholding choice is Theorem 4.2 in the paper. With our specific choice of thresholding / rejection on the ratio \\rho(x) \= Q(x) / P(x), we recover Chow’s rule. The alternative of rejecting based on $P(x)$ would not yield this equivalence.

In the experiments, the proposed algorithms seem to perform well in the high-coverage regime, while dominated by existing methods in the low-coverage regime. Do you have any explanation on this?

Good question. Firstly, we note that the trade-off curves can be extended further by increasing $\\tau > 1$. We suspect the difference in performance to be related to the quality of calibration. If the model was perfectly calibrated, then the density approach would be optimally rejecting. As such, deviation / suboptimality would be due to calibration error.
This explanation is partially supported by the drop in performance of our approach on noisy variants of the dataset. Here the training set (and data used for calibration) is not representative of the test set which would result in a model miss-calibrated on the test set.

For two additional notes:

We also point the reviewer to the results of the MedMNIST dataset -- additionally added in the rebuttal -- in the shared response section. Here we find that for the lower 80% regime, our approach can perform better than the baselines for a more complicated dataset.

A reason why the baselines do not provide / perform well in the extremely high-coverage regime (~ 95%) is that it is difficult to tune the rejection costs $c$ hyperparameter to allow for fine tuning of the coverage. As the rejection decision of these baseline involve training a whole other model, the cost of tuning requires training several NNs.