A Unifying Post-Processing Framework for Multi-Objective Learn-to-Defer Problems

We thank the reviewer for their positive feedbacks. We further address their questions in the following.

Questions

Q1 Dealing with overfitting is largely studied in the machine learning literature. In this work, we assume that the scores are estimated using the well-studied methods such as calibrated neural networks and random forests. This is an assumption that a large body of the field, from the first works of L2D (e.g., Mozannar et al. 2020) holds. If the posterior probabilities are not accurate, as the reviewer has mentioned, all the plug-in methods (including Mozannar et al., Verma et al., and Cao et al. for unconstrained L2D problem) would lead to incorrect solutions. Therefore, we believe the study of this issue is beyond the scope of this paper and is of its own interest. However, we should add that, as the reviewer has mentioned, the calibration of such probabilities would equip us with an interesting set of properties. In fact, if we know that the neural network $g(x)$ is calibrated, i.e., $P(Y=1|g(X)=p)=p$, then if the only information in our hand is that calibrated estimation, then the plug-in methods are reduced to the plug-in methods for $g(x)$, since in this case $\Pr(Y=1|g(x))=g(x)$, and therefore rules such as $\Pr(Y=1|g(x))\geq T$ is equivalent to $g(x)\geq T$.

Q2 These two fields are highly interrelated in the sense that in both of these fields, a competent decision-maker is selected for a particular input feature. However, the difference between these fields is that in L2D systems, due to the some reasons such as transparency and responsibility, the decision is made either by human or the classifier, while in DCS systems the solutions of the classifier can be fused with each other. Such extensions to L2D problems are also studied in the literature, e.g., Charusaie et al. 2024, and Steyvers et al. 2022. We make sure to include these references as well as DCS references in our manuscript.

Charusaie, Mohammad-Amin, Amirmehdi Jafari Fesharaki, and Samira Samadi. "Defer-and-Fusion: Optimal Predictors that Incorporate Human Decisions."

Steyvers, Mark, et al. "Bayesian modeling of human–AI complementarity." Proceedings of the National Academy of Sciences 119.11 (2022): e2111547119.

Weaknesses

The general framework provided by the author can address various constraint problems, but it does not seem to be reflected in the experimental section (especially in cases involving multiple constraints), only considering simple single-constraint situations and basic comparisons. We first should note that, as we mention in the main rebuttal section, the ACSIncome experiment controlls two constraints, namely, the disparity of true negative and false negative predictions for two demographic groups. In the following, we further introduce a new set of multi-constraint experiments in the Hate Speech experiment.

We believe that the comments of the reviewer is remained unfinished, or otherwise we are not sure how the references on Expert Intervention Budget and Long-Tail Classification are related to their comments. We have indeed cited these references in the current version of the manuscript.

New Experiment on Hatespeech Dataset

We further experimented our algorithm on Hatespeech dataset (Davidson et al. 2017) that is a content-moderation task to flag hateful and offensive tweets. The results are plotted in the submitted PDF. We used a pre-trained model (Blodgett et al. 2016) to detect whether a tweet is written in an African-American (AA) or not (NAA). We then used our algorithm to control the (i) parity of predicting a tweet hateful, or (ii) offensive, and (iii) false negative probability difference for group AA and NAA. We can observe in Figure (d) that the disparity in predicting a tweet "Offensive" for our algorithm (violet bars) is reduced to the tolerance $0.1$ by deferral to the human for group AA (see Figure (b)), and otherwise randomization of the results for group NAA (Figure (c)). Similarly, the disparity in predicting "Hate Speech" is diminishing in our algorithm (brown bars of Fig. 2,3, and 4). Furthermore, we can reduce the disparity of false negative prediction (finding a tweet Hate Speech or Offensive, given it is neither) in Figure (e). Here we note that the high variance in Fig. (e) is due to small size of non-offensive tweets. We furtherran experiments on multi-constraint setting in which both demographic disparity and human intervention budget is controlled. The accuracy and the true constraints are plotted in Fig. (h), (i), and (j). Similarly, Type-II error and human budget is controlled together and plotted in Fig. (k), (l), and (m).

Davidson, Thomas, et al. "Automated hate speech detection and the problem of offensive language." Proceedings of the international AAAI conference on web and social media. Vol. 11. No. 1. 2017.

Blodgett, Su Lin, Lisa Green, and Brendan O'Connor. "Demographic dialectal variation in social media: A case study of African-American English." arXiv preprint arXiv:1608.08868 (2016).

We first thank the reviewer for their clarifications and their response. Here, we mention a few notes.

Q1: We are glad that the reviewer agrees with us on our choice of surrogate functions. We further agree with the reviewer that linearly combining the scores might propagate the error, in a controlled manner, and in the value of objective and not the constraints. This is precisely what we have discussed after Theorem 5.1 regarding the constraint generalization. There, we have discussed that for a given error in $\ell_{\infty}$ norm of the scores, the constraints can deter at most for that error, plus the sample complexity term. Furthermore, in the error upper-bound (10) that is provided in Theorem 5.3, we observe that given the linear combination coefficient being bounded by $K$, and given the sensitivity factor being bounded away from $0$, the objective cannot be far from the true objective, as long as score errors $\delta_0$ and $\delta_1$ are small enough. We note that, when the constraint is well within the feasibility set, the value $K$ is more tightly upper-bounded. Furthermore, as we discussed it in the response to Q6 of Reviewer 7rh1, and as we have shown as an example, in Figure (f) and (g) of the submitted PDF, the constraints that lie within the feasibility set improve the sensitivity factor, thereby reducing the risk of error propagation.

Weaknesses

We appreciate the reviewer's clarification of their comments. It is important to emphasize that our work does not aim to compete with other constrained L2D optimal methods but rather to unify these methods within a single framework. Our method should indeed provide a reasonable solution for simple constraints, and improve the empirical methods by obtaining the true optimal solution for cases in which the true optimal is not known in the literature, such as L2D with fairness criteria (demographic parity, equalized odds, and equality of opportunity), or a combination of a set of constraints. These claims are supported by the experiments within the manuscript and the rebuttal. However, we do not expect that our method outperforms methods that already achieve or approximate the true optimality, such as those dealing with expert intervention budgets or long-tail classification.

We will further attempt to run the additional experiments suggested by the reviewer during the remaining discussion period. However, given the time constraints and the incompleteness of the reviewer's initial comments, it might not be feasible to complete them within this period.

We thank the reviewer for their response and comments our experimental results. As we have tried to show that via experimental results as well as theoretical results, our method provides the same theoretical post-processing method as of Narasimhan et al. 2022 for the case of human intervention budget. The differences of these methods are reflecting the way that the probabilities are estimated, i.e., the choice of loss function, and the encoding of deferral choice in the network. We have used a softmax loss function, while as mentioned, in our limited time, we implemented Section 4.1 of Narasimhan et al. that uses a form of one-vs-all loss. These two as we see have the difference of order of 0.001, while the standard deviation of accuracies is larger than this amount. As a result, we believe this is an evidence that the two methods lead to a similar result.

Here, we want to reiterate the empirical results of our work:

1- We have obtained the L2D solution under demographic parity for COMPAS dataset and compared to Madras et al. 2018 and Mozannar et al. 2022.

2- We have obtained the L2D solution under equalized odds for ACS dataset.

3- In the rebuttal period, we have implemented our work to Hatespeech dataset and under demographic parity and equality of opportunity constraint.

4- To address the reviewer's concern, we have obtained the optimal solution under multiple constraints of demographic parity+human intervention budget and Type-II error+human intervention budget.

5- To address the reviewer's concern, we have compared our method with Narasimhan et al. 2022 and Liu et al. 2024 for Hatespeech dataset as well as COMPAS dataset.

We thank the reviewer for reading the paper and their comments. We are respectively address the concerns of the reviewer.

1. 1.Why in Theorem 4.2, $f_{k, p}*(x)=\tau(\psi_1(x)-k\psi_0(x))$, while in Algorithm 1, its estimation version is $\hat{f}_{k,p}(x)=\tau(\hat{\psi}_0(x)-k\hat{\psi}_1(x))$ (where the positions are swapped)? This is a typo that we addressed in the newer version of this manuscript. In this version $\psi_0$ corresponds to the objective, while $\psi_1, \ldots, \psi_{m+1}$ correspond to the constraints.

2. Can Algorithm 1 handle multiple constraints settings? Figure 1 depicts a diagram of multiple constraints settings, but it seems Algorithm 1 is designed for single constraint settings. This algorithm, as mentioned in the main rebuttal can handle many constraints, just by adding the line of finding the empirical solution of $k_1, \ldots, k_m$ for (3) and based on validation dataset.

3. Inconsistent Notations and Typos: We have extensively proofread and resolved the typos that are raised by the reviewer. We refer the reviewer to the main rebuttal section for further details.

4. Limitations on Multiple Constraints: The paper acknowledges that the provided analyses for the algorithm (and possibly the algorithm itself) only apply to single constraint settings. More discussion on the challenges of extending these analyses (and potentially the algorithm) to multiple constraints settings would be helpful. As we further explained in the main rebuttal section, the algorithm can handle many constraints. The main result of this paper also hold for many constraints. Further extensions of the sample complexities are obtained in the main rebuttal section.

Here, we would be grateful if the respected reviewer would let us know why they think our paper is not fit to this conference, since we believe there is a disparity between the comments and the scores of the reviewer. The typos and notation issues can be minor issues that will not entail any major concerns in our work.

Dear Reviewer,

Thank you for your response and for raising the score. We are glad that we could address your concerns. Regarding the notation issues, we assure you that we will carefully proofread the next version of the manuscript to eliminate any typos.

We thank the reviewer for the positive and constructive comments on this paper. In the following, we respond their questions in order

Q1 A: This work that we have further referenced in our manuscript, as we mentioned after (6), has three main differences with our work. (i) This work only considers the Type-$k$ error and is designed to find the solution of the optimal classifier given that specific constraints. In contrary, our work can contain all types of constraints that are in form of loss function (e.g., fairness criteria, human intervention budget, long-tail classification). (ii) This work is based on strong duality theorem that as we discussed in Appendix E is not considered in our work, due to its limitations (see the counterexample of Appendix E). (iii) In our work, we not only find the optimal solution to the constrained optimization problem (3), but also show that all solutions to this problem are of the form that we have formulated in (8).

Q2 A: The L2D systems can be used in many applications, including applications that are sensitive in nature. As an instance, we can design an algorithm that either classifies a disease based on the data of a patient, or defer the decision to the doctor. This system in total can be unfair, meaning that the error that is induced by this system not detecting the disease for different demographic groups can be different. As another example, as we further explained our experiment for Reviwer 4QNG, this can be the case when we want to detect Hatespeech from a tweet automatically or using our agents. This decision could entail different errors for the tweets that are written with an African-American dialect and the ones that are not. Our results helps controlling this algorithmic unfairness. Since we add a constraint to our optimization problem, the corresponding search space reduces, and therefore the accuracy can be compromised, which is the case in many algorithmically fair methods.

Q3 A: Our experimental setting now have expanded and include content moderation experiments on Hate Speech Dataset. We refer the reviewer to the rebuttal section of Reviewer 4QNG for the details of these experiments. Note that there is no known basline to ensure a certain equalized odds constraint for an L2D system. Particularly in our setting in which the model is a random forest. However, in the next revision, we will compare our method with best fair classifier and an adapted version of Mozannar et al. 2020 for random forests in which we shift thresholds for different demographic group.

Q4 A very interesting application of $d$-GNP is its use in fair vanilla multi-class classification. This theorem can show that for controlling demographic parity or equality of opportunity, we need to first learn the scores, and then add or multiply a value to these scores based on the demographic identity. In fact, or an $L$-class classifier, if we aim to set constraints on demographic parity $\big|\Pr(\hat{Y}=0|A=0)-\Pr(\hat{Y}=0|A=1)\big|\leq \delta$ or equality of opportunity $\big|\Pr(\hat{Y}=0|Y=0, A=0)-\Pr(\hat{Y}=0|Y=0, A=1)\big|\leq \delta$ on Class $0$, then we can follow similar steps as in Appendix D to find the embedding functions as $\psi_{\mathrm{DP}} = s(A)\big[1, 0, \ldots, 0\big],$ and $\psi_{\mathrm{EO}} = t(A, 0)\big[\Pr(Y=0|x), 0, \ldots, 0\big].$ As a result, since the accuracy embedding function is $\psi_0(x)=\big[\Pr(Y=0|x), \ldots, \Pr(Y=L|x)\big]$, then, by neglecting the effect of randomness, the optimal classifier under such constraints are as h_{\mathrm{DP}}(x)=\arg\max\big$\Pr(Y=0|x)-ks(A), \Pr(Y=1|x), \ldots, \Pr(Y=L|x)\big$, and h_{\mathrm{EO}}(x)=\arg\max\big$\Pr(Y=0|x)\big(1-kt(A, 0)\big), \Pr(Y=1|x), \ldots, \Pr(Y=L|x)\big$. Equivalently, for demographic parity, the optimal classifier includes a shift on the score of Class $0$ as a function of demographic group, and for equality of opportunity, the optimal classifier includes a multiplication of the score of Class $0$ with a value that is a function of demographic group. It is easy to show that under condition of positivity of the multiplied value, these classifiers both reduce to thresholding rules in binary setting.

Q5 A: We refer the reviewer to the main rebuttal for the response to this question.

Q6 A: The tolerances are chosen in a manner that capture the dynamics of the accuracy within that range. If we permit for a very large tolerance, the accuracy saturates to its Bayes optimal value. This is what occurs at the right part of ACSIncome figure. The main assumption of Theorem 5.3 is the sensitivity assumption of Definition 5.2. To test that assumption, we can set $\gamma=1$, and reduce this assumption to a lower-bound on the derivative of the constraint w.r.t the coefficient $k$. We have plotted this in Fig. (f) and (g) of the submitted PDF and we observe that for the cases that $k$ induce a constraint within the plausible constraints, this derivative is lower-bounded. In fact, Fig. (f) shows the accuracy of the estimator for two coefficients of corresponding constraints of demographic disparities of detecting a tweet Offensive (DP-O) or Hate-Speech (DP-HS). We observe that as long as there is dynamics in the accuracy in terms of this coefficients, then the derivative of the constraints in terms of this coefficient is bounded below. This is particularly observable in right-most part of Fig. (g) for DP-O and the left-most part for DP-HS.

Q7 We should mention that estimating the value of the scores are equivalent to estimating the value of a set of posterior probabilities that are used in obtaining these scores. This is a task for which machine learning literature has developed corresponding tools such as deep neural networks, random forests, etc. Therefore, we don't believe the estimation of our scores is of particular hardness compared to this literature.

We first thank the reviewer for their positive feedback to our submission. Here, we respond to their questions

1. Q: It is mentioned that solving (2) is NP-hard. While the proof is quite clear, I wonder if such hardness is important. In my opinion, a common practice that can avoid directly solving this problem is using a surrogate loss instead of 0-1 loss and integrating the expert coverage constraint into the loss like that in the Selective-net. Can you further make some discussions on this point? A: The point of the hardness theorem is to justify the use of randomness in multi-objective setting. We should note that the practical solutions to this problem such as Selective-Net that use surrogates of the loss functions do not enjoy the guarantees for optimality. This is as opposed to the unconstrained case, in which there are continuous surrogate functions that are Fisher consistent, and therefore their minimization is equivalent to the $0-1$ loss minimization.

2. Q: If we have rather accurate class probability estimates and expert accuracy, why not use it as the solver of this problem? A: The class probabilities as well the expert accuracy can help us find the optimal solution when we allow for randomness and using $d$-GNP. If, however, we aim to find the optimal deterministic solution that is not the case. In Appendix E we introduce an example that the human has perfect information of the label, while the input feature has no information about the label. In this case, it would be more efficient to defer the decision to the human. However, if we bound the budget of the human to $b$ proportion of samples, the optimal deterministic solution would be to defer on inputs that are arised with sum probability of $b$ and not to defer in the other $1-b$ proportion. Therefore, on the inputs with the same conditional accuracy and the same conditional expert accuracy, we have a different decision. This is the reason to the hardness theorem, i.e., finding that set of inputs that sum up to $b$ can be a complex task.

3. Q: The related works are moved to the appendices, which can be confusing to readers that are new to this field. I suggest the authors use a more compact type setting in the contribution part of Section 1 and reduce/integrate some of the contributions to make more spaces. The paragraph ‘Type of Constraints’ can also be reduced given the Table 1. A: This was a decision due to the lack of space. We will make make more space for the related works in the next version of the manuscript, as suggested by the reviewer.

4. Q: The notations in this paper need further proofread, e.g., the realization and random variables are used improperly in line 141, line 188; the quantity $a_i$ in the algorithm 1 seems to be unused in this algorithm. As mentioned in our main rebuttal, we have made an extensive effort to proofread the paper. We have addressed the typos mentioned by the reviewer and appreciate their thorough reading of the manuscript.