Learn-to-Defer is a paradigm that enables learning algorithms to work not in isolation but as a team with human experts. In this paradigm, we permit the system to defer a subset of its tasks to the expert. Although there are currently systems that follow this paradigm and are designed to optimize the accuracy of the final human-AI team, the general methodology for developing such systems under a set of constraints (e.g., algorithmic fairness, expert intervention budget, defer of anomaly, etc.) remains largely unexplored. In this paper, using a $d$-dimensional generalization to the fundamental lemma of Neyman and Pearson (d-GNP), we obtain the Bayes optimal solution for learn-to-defer systems under various constraints. Furthermore, we design a generalizable algorithm to estimate that solution and apply this algorithm to the COMPAS and ACSIncome datasets. Our algorithm shows improvements in terms of constraint violation over a set of baselines.
Paper
Similar papers
Peer review
Summary
While there has been extensive research on L2D, general methods for designing such systems under various constraints (e.g., algorithmic fairness, expert intervention budget, defer of anomaly, etc.) remain largely unexplored. This paper utilizes $d$-dimensional generalization to the fundamental lemma of Neyman and Pearson ($d$-GNP) to obtain Bayes optimal solutions for L2D under various constraint conditions and designs a generic algorithm to estimate these solutions.
Strengths
1. This paper proposes a novel general framework for addressing L2D under various constraint conditions. 2. Different constraint conditions can be simultaneously addressed. 3. The proposed method is a post-processing approach that can be easily extended to existing models.
Weaknesses
1. 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. Expert Intervention Budget: Liu S, Cao Y, Zhang Q, et al. Mitigating Underfitting in Learning to Defer with Consistent Losses. ICML, 2024. Narasimhan H, Jitkrittum W, Menon A K, et al. Post-hoc estimators for learning to defer to an exper. NeurIPS, 2022. Long-Tail Classification: Narasimhan H, Menon A K, Jitkrittum W, et al. Learning to Reject Meets Long-tail Learning. ICLR, 2024.
Questions
1. Post-Processing Framework has many benefits, but it also faces challenges in confidence calibration, which is particularly evident in deep models. Inevitable overfitting makes the model's output probabilities unreliable, indirectly leading to biases in approaching the Bayes optimal solution through post-processing methods. Does the method proposed in this paper include mechanisms to mitigate these issues? 2. There are many studies similar to L2D, such as the dynamic classifier selection literature (DCS). What is the main difference between L2D and DCS? Cruz R M O, Sabourin R, Cavalcanti G D C. Dynamic classifier selection: Recent advances and perspectives[J]. Information Fusion, 2018, 41: 195-216.
Rating
4
Confidence
5
Soundness
3
Presentation
3
Contribution
2
Limitations
N/A.
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.
New Comparative Experiments + Theoretical Equivalence
Dear Reviewer, We further thank you for the suggestion of comparing our unifying methods with other methods in specific cases. In the time we had we could compare our method to the two of the mentioned work, Liu et al 2024, and Narasimhan et al. 2022. for the sanity check. We have indeed simulated the post-hoc formula of (11) in Narasimhan et al. 2022 and the modified equation (9) of Liu et al. with One-vs-All Losses. Since these works are not tailored to handle hard thresholds, we have fitted the parameters for each specific tolerance via validation data in Narasimhan et al. and via re-training in Liu et al. and searching within 1000 values of deferral cost between -1 and 1. The comparison shows a competetive accuracy in our method compared to these baselines. We note here that the high variance of the accuracy in COMPAS dataset is already reported in Mozannar et al. 2023, Figure 3 (b). ### Hatespeech | Tolerance | d-GNP Accuracy | d-GNP Constraint | Liu et al. 2024 Accuracy | Liu et al. 2024 Constraint | Narasimhan et al. 2022 Accuracy | Narasimhan et al. 2022 Constraint | |----|---|---|---|---|---|----| | 0.05 | **0.890 ± 0.004** | 0.049 ± 0.005 | 0.887 ± 0.004 | 0.043 ± 0.005 | 0.886 ± 0.005 | 0.047 ± 0.006 | | 0.10 | **0.902 ± 0.005** | 0.099 ± 0.007 | 0.899 ± 0.005 | 0.092 ± 0.005 | 0.898 ± 0.005 | 0.098 ± 0.007 | | 0.15 | **0.910 ± 0.004** | 0.147 ± 0.011 | 0.908 ± 0.005 | 0.137 ± 0.009 | 0.908 ± 0.005 | 0.148 ± 0.009 | | 0.20 | **0.916 ± 0.004** | 0.200 ± 0.011 | 0.914 ± 0.005 | 0.186 ± 0.010 | 0.914 ± 0.004 | 0.195 ± 0.012 | | 0.25 | **0.920 ± 0.004** | 0.244 ± 0.009 | 0.918 ± 0.004 | 0.233 ± 0.013 | 0.917 ± 0.005 | 0.240 ± 0.017 | | 0.30 | **0.921 ± 0.005** | 0.287 ± 0.016 | 0.920 ± 0.005 | 0.276 ± 0.025 | 0.919 ± 0.005 | 0.283 ± 0.015 | ### COMPAS | Tolerance | d-GNP Accuracy | d-GNP Constraint | Liu et al. 2024 Accuracy | Liu et al. 2024 Constraint | Narasimhan et al. 2022 Accuracy | Narasimhan et al. 2022 Constraint | |---|---|---|---|---|---|---| | 0.015 | 0.646 ± 0.022 | 0.014 ± 0.010 | **0.649 ± 0.031** | 0.003 ± 0.004 | **0.649 ± 0.031** | 0.016 ± 0.018 | | 0.075 | 0.647 ± 0.026 | 0.042 ± 0.033 | 0.648 ± 0.031 | 0.030 ± 0.022 | **0.650 ± 0.031** | 0.053 ± 0.032 | | 0.135 | 0.649 ± 0.026 | 0.072 ± 0.050 | **0.651 ± 0.026** | 0.065 ± 0.040 | 0.649 ± 0.031 | 0.082 ± 0.048 | | 0.195 | **0.656 ± 0.023** | 0.111 ± 0.074 | 0.654 ± 0.027 | 0.079 ± 0.054 | 0.652 ± 0.033 | 0.132 ± 0.069 | | 0.255 | **0.656 ± 0.029** | 0.122 ± 0.085 | 0.653 ± 0.027 | 0.108 ± 0.085 | 0.655 ± 0.033 | 0.165 ± 0.095 | We further discuss the theoretical equivalence between our method and other methods that tackle human intervention budget and long-tail classification by which we conclude that the closeness of the accuracies to these baselines are not surprising. For human intervention budget, since using Table 1 we know that the embedding functions are as $$\psi_0(x)=[\Pr(Y=0|X=x), \ldots, \Pr(Y=L|X=x), \Pr(Y=M|X=x)],$$ and $$\psi_1(x)=[0, \ldots, 0, 1],$$ therefore, the optimal predictor using Theorem 4.1 and the discussion after (4) is equal to $$h^*(x)=\arg\max_{i\in [1:L]} \psi_0(x)-k\psi_1(x) $$, and $r^*(x) = 1$ if $L+1=\arg\max_{i\in [1:L+1]} \psi_0(x)-k\psi_1(x)$. Therefore, using the definitions of embedding functions, we have $$h^*(x)= \arg\max_{1:L} [\Pr(Y=1|X=x), \ldots, \Pr(Y=L|X=x)],$$ and $r(x)=1$ if $\Pr(Y=M|X=x)-k>\max \{\Pr(Y=1|X=x), \ldots, \Pr(Y=L|X=x)\}$. This is equivalent to what is proposed in (11) in Narasimhan et al. 2022. For the long-tail classification problem using Table 1, we have $$\psi_0(x)= \Big[\frac{\Pr(Y=1|X=x)}{\alpha_{i_1}\Pr(Y\in G_{\alpha_{i_1}})}, \ldots, \frac{\Pr(Y=L|X=x)}{\alpha_{i_L}\Pr(Y\in G_{\alpha_{i_L}})}, 0\Big]$$ and $$ \psi_t(x) = \frac{\Pr(Y\in G_t|X=x)}{\Pr(Y\in G_t)}[1, \ldots, 1, 0] - \frac{\alpha_t}{K}$$ as embedding functions, where $i_j$ is the index of the group $G_{i_j}$ to which the label $j$ belongs. Now, since the first $L$ components of all $\psi_t$s are equal to each other, we have $$h^*(x)=\arg\max_{i\in [1:L]} \psi_0(x) - \sum_{t=1}^K k_t \psi_t(x) = \arg\max_{i\in [1:L]} \psi_0(x) = \arg\max \Big[\frac{\Pr(Y=1|X=x)}{\alpha_{i_1}\Pr(Y\in G_{\alpha_{i_1}})}, \ldots, \frac{\Pr(Y=L|X=x)}{\alpha_{i_L}\Pr(Y\in G_{\alpha_{i_L}})}\Big].$$ Furthermore, the tightness condition $\mathbb{E}\big[\langle \psi_t(x), f^*(x)\rangle\big]=0$ concludes that $\alpha_{i_j}\Pr(Y\in G_{\alpha_{i_j}}) = \alpha^*_{j}$ where $\alpha^*_{j}$ defined in (8) of Narasimhan et al. 2024. These two conclude in the optimal classifier (8) of Narasimhan et al. 2024. Similarly, we can show that the optimal deferral strategy using $d$-GNP is $r(x)=1$ if $\sum_{t}\frac{k_t \Pr(Y\in G_t|X=x)}{\Pr(Y\in G_t)}>\max\Big[\frac{\Pr(Y=1|X=x)}{\alpha_{1}^*}, \ldots, \frac{\Pr(Y=L|X=x)}{\alpha_{L}^*}\Big]$ which is a similar rule to that of (8) in Narasimhan et al. by setting $\mu^*\_t=1-k_t \alpha_{i_t}$.
Concerns remain about the experimental component
Thank you to the authors for providing some of the experimental results. However, I’m afraid I still feel that this paper is not very complete. Despite the theoretical section being thorough, there are too many omissions in the experimental part that need to be addressed. Specifically: 1. There is a lack of separate experiments addressing the various constraints involved in this work. 2. There are no cross-experiments with different constraints (they do not need to be exhaustive). 3. There is a lack of comparative experiments with methods that have already addressed the constraints. Additionally, I have concerns regarding the experimental results related to the expert intervention budget that were added at the end. Although the method proposed by Narasimhan et al. (2022) cannot be directly compared (as the cost needs to be adjusted), according to the viewpoint in [1], their optimal solutions should be the same. Furthermore, you have employed the same post-processing method; therefore, the experimental results should be fundamentally similar. However, from the aforementioned experiments, it appears that the method presented in this paper performs better. [1] W. Jitkrittum, G. Neha, A. K. Menon, H. Narasimhan, A. Rawat, and S. Kumar. When Does Confidence-Based Cascade Deferral Suffice? In NeurIPS, 2023
A Resoponse to Your Concerns
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.
Summary
The paper studies multi-objective learn-to-defer problems, where the objectives include minimizing deferral loss and satisfying several constraints. It demonstrates that these problems are generally NP-hard and can be reduced to functional linear programming. Additionally, it shows that the problem can be further reduced to a d-dimensional generalized Neyman-Pearson problem and characterizes its solution when there is only one constraint. The paper also presents a unifying post-processing algorithm with generalization bounds and provides numerical validations.
Strengths
The paper offers several theoretical insights into multi-objective learn-to-defer problems, enhancing the understanding of these problems. It also introduces a unifying post-processing algorithm with provable performance guarantees.
Weaknesses
1.Inconsistent Notations and Typos: The paper is difficult to follow due to inconsistent notations and potential typos. For instance, $m$ can mean the expert decision (line 111) or the number of constraints (Equation 3). $r$ can mean the rejection function (line 110) or a distribution vector (Theorem 4.1). In line 7 of Algorithm 1, should it be $\hat{C}(k)$ instead of $\hat{C}(t)$? And line 208 only defines $\psi_{i}$ for $i=1,...,m+1$, then in line 209, what is $\psi_{0}$? 2.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.
Questions
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)? 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.
Rating
5
Confidence
3
Soundness
3
Presentation
1
Contribution
2
Limitations
See weaknesses.
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.
Summary
The paper introduces a unifying post-processing framework for multi-objective learn-to-defer problems, allowing the system to defer tasks to an expert under specified constraints. By generalizing the Neyman-Pearson lemma, the paper derives the Bayes optimal solution for this framework and develops an algorithm to estimate it. The proposed algorithm is evaluated using the COMPAS and ACSIncome datasets.
Strengths
1. The paper introduces a general post-processing framework. 2. The paper is well-written and has excellent illustrations, for example, Figure 1. 3. The framework accounts for multiple objectives in L2D. 4. The method can potentially be extended beyond the L2D setting to apply to other constrained objectives.
Weaknesses
1. The proposed algorithm requires the estimation of scores and $\hat \psi$ (Lines 4 and 5 of Algorithm 1). However, accurately estimating these values can be potentially challenging. 2. The experiments could potentially be expanded further.
Questions
1. The multi-class Neyman-Pearson (NP) paradigm has been studied in [66]. Could the authors summarize the key differences between the framework proposed in this paper and the prior work? 2. What is the motivation for imposing specific constraints in learning to defer? Could this compromise the accuracy of the process? 3. How does the proposed algorithm empirically compare with the baselines on the ACSIncome datasets? Do you think the experiments could be expanded further? 4. It seems that the method could potentially be applicable to other constrained objectives beyond the L2D setting. Could the authors further elaborate on this? 5. Could the authors further comment on the challenges of extending the analysis and algorithm to multiple constraint cases? 6. How are the tolerances chosen during the experiments? Can the assumptions in Theorem 5.3 be verified in practice?
Rating
6
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
Yes.
Summary
This paper aims to provide a provably consistent unified post-processing framework of learning to defer with constraints. The problem of constrained L2D is first reduced to a linear programming problem. Then the linear programming problem is further tackled with a generalized version of Neymar-Pearson lemma, which lead to an efficient solver of this problem. Non-asymptotic analysis is conducted to further provide guarantee for the empirical version of the algorithm. Experimental results validate the efficiency of the proposed solver.
Strengths
1. A unified post-processing framework for constrained L2D is proposed in this paper, which allows training a randomized classifier-rejector tuple with small number of validation data combined with a trained model’s confidence output. 2. The hardness of directly solving the original problems and in-processing methods are thoroughly analyzed in this paper, which provides enough rationale for the proposed method. 3. The introduction of the generalized Neyman-Pearson lemma is novel to the field of L2D, which can provide insights for the future works of this field.
Weaknesses
1. 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. 2. 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.
Questions
1. 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? 2. If we have rather accurate class probability estimates and expert accuracy, why not use it as the solver of this problem?
Rating
7
Confidence
4
Soundness
3
Presentation
3
Contribution
3
Limitations
Please see the weaknesses.
Thank you for your response. It addresses some of my concerns and I have raised the score. However, I must emphasize that the typos and notation issues significantly hinder the understanding of the work. In my view, a high-quality paper should have minimal typos and consistent notations to ensure clarity and readability.
Response
Thank you for your elaborated response to my review. Please allow me a response to your response. add Q1/A1: I know that addressing the probability calibration issue caused by overfitting is challenging, so the author's plug-in method relies on excellent surrogate loss functions. However, we need to point out that in previous surrogate loss function, only comparisons between probabilities are required (e.g., comparisons may be accurate, but values may not be accurate, such as Mozannar et al. 2020), rather than direct use. In contrast, the author's method requires direct utilization of estimated probabilities that may be inaccurate for multiple operations, which may amplify errors. I know that calibrating probabilities is not the focus of this study, but I believe this is a potential risk of the plug-in method that warrants discussion. add Weaknesses: I apologize for not accurately expressing my confusion earlier. My main concern is that the authors claim their framework can solve various constraint problems, but in the experiment section, they don't compare their work with previous works that have already solved some of these constraint problems (such as expert intervention budget and long-tail classification). I think such comparative experiments are very important. In my opinion, the lack of comparative experiments is the main drawback of the work.
Thank you for your response. Your discussions on the motivation of this work and the hardness analyses have solved my concerns. I’ll keep my decision of acceptance.
Decision
Accept (poster)