Delegated Classification

Summary

This work provides a framework for incentive-aware delegation of machine learning tasks. It considers a principal-agent game, where the principal can spend a limited budget on the outsourcing the training of a machine learning model, with the hope of getting the most accurate model, and the agent provides a machine learning model to the principal, but aims to invest minimal effort in training. This work considers the problem of optimal contract design, where the principal commits to a contract that determines how much the agent will be paid for every possible accuracy level of the model, and the agent chooses a profit-maximizing number of samples to use to train the model in response to the contract. This contract design problem requires that the “learning curve”--a function that maps the number of samples to the accuracy of the model is known to both the principal and agent. When the learning curve has a nice structure, it is possible to leverage a connection to the Neyman-Pearson lemma to see that the optimal contracts have a simple threshold form.

Strengths

1. The paper proposes an interesting new problem. The framing of the problem is well-motivated, clear, and sensible. Figure 2 is a great figure! It nicely captures the motivation for this problem and demonstrates possible contract types. 2. The main contribution of this work is demonstrating that under easy to understand assumptions (Monotone Likelihood Ratio Property, concavity), the optimal contract of the proposed principal-agent game takes on a simple threshold form. The technical contribution of this paper is closely related to the connection between optimal contracts and the Neyman-Pearson lemma established by Bates et al., 2022. It is great to see this work build on the direction of Bates et al, 2022 and demonstrate a connection between optimal contract design and statistical hypothesis testing. The taxonomy given in Table 1 is helpful. 3. The discussion in Lines 352-363 of how overestimation and under-estimation can have quite different implications is useful beyond the scope of this work. It suggests that when estimating learning curves, not all errors should be treated equal and we may want to penalize overestimation more strongly. This may be of interest to communities that aim to estimate/learn scaling laws.

Weaknesses

A potential weakness of the model that the authors propose is the assumption that the principal has access to a learning curve– which captures the stochastic performance of a machine learning model as a function of sample size. Nevertheless, the authors address this weakness quite thoroughly–the authors cite many related works that suggest that the learning curve can be predicted from scaling laws and also analyze the construction of contracts in the partial information setting, where the learning curve is not known and must be estimated.

Questions

1. In Section 2 Lines 110-113, the authors discuss that $h_{n}$ is a stochastic quantity. It would be helpful to add a sentence here that $h_{n}$ is distributed according to a distribution that depends on $n$ (and more details on how to evaluate the expectation will be provided later in the work). At first glance, this equation is somewhat unclear because we have not yet defined the distribution over $h_{n}$ for a given $n$? 2. The second plot of Figure 3 is somewhat hard to parse. Could the authors add some clarifications? 3. It may be helpful to emphasize that the contract $t$ is a function that takes on a different value depending on each possible value of the validation accuracy. (The connection between the domain of $t$ and the sample size of the validation set can easily be missed). 4. What do the authors mean by “robustness” in Line 372? 5. Nit writing: Line 120 “the principal cannot now” -> “the principal cannot know.” 6. Nit: Should the subscript of $f_{n}$ in Equation 2 be $f_{a}$? 7. Nit writing: Line 308 has an incomplete sentence.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Yes.

Summary

The paper introduces an interesting problem, and provides interesting theoretical results based on a connection to classical result on statistics. The problem setup follows the standard principal-agent problem with moral hazard, and the principal commits to a contract to incentivize the agent behaving favor of the principal. They mainly analyze that thresholded structure is optimal in case of contract for classification task, and provide some fruitful implications upon it.

Strengths

Overall, the paper is well-written and easy to follow. The problem setting they considered is novel and of interest to NeurIPS community, especially given the increasing attention to contract theory/delegation mechanism. The analysis looks sound and the results are thorough.

Weaknesses

I'm not entirely sold on the main results and their implications/takeaways, though I agree its technical soundness. Details are presented below on questions/limitations.

Questions

Model * Section 2.1 describes contract design without budget constraint, but the problem setup actually involves budget constraint. I wonder why the authors consider this problem setup, and what happens if the principal does not have a budget constraint (though I understand that both may have plausible applications) * It seems the agent should be aware of the distribution $f_a$ to compute the expected payment; distribution over possible outcomes from action a. How can this be made practically? Also, $f_a$ corresponds to $f_n(j)$? Results * Given the vast literature on contract theory, why the existing techniques cannot be applied to the presented problem setup? I couldn't find the authors discussing on it. Minor comments * Reference unresolved in L93

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

* Thresholded rule is optimal - Yes, it makes sense that thresholded contract would be efficient against expected utility maximizer, however, it would carry over a huge amount of variance for the agent's reward. How would the optimal structure change if the agent exhibits risk-averse nature? * Again, such an extreme thresholded contract is not widely applied in practice - at least some amounts of minimal wage exist, or rather a linear contract is typical (e.g., Carroll15). Besides, finding an agent who admits such a thresholded contract would be difficult than that via posting more conservative/safer contract, thereby possibly inducing the quality of agent to be lower than expected. I'd like to see some discussions on it. * In the above context, if the budget constraint is given in ex-post manner, given the use of constant/linear/threshold with the same maximal payment (as in Fig 2), I doubt that the quality of the agent would be endogenous depending on the pricing rule to be exploited (e.g., giving constant B would attract highest-quality agent), rather than being exogenous. I'd appreciate some (empirical or theoretical) discussions on it. * As the paper contributes to an applied modeling of real-world scenario with claiming the efficiency of thresholded rule, I expected to see some comparisons between various contract structures in the experiment. * Also, the title of delegated classification looks a bit overly abstract to me. I would (though weakly) suggest making it more explicit, e.g., including contract sort of notions.

Summary

This paper presents a novel theoretical principal-agent framework for examining the incentive-aware delegation of machine learning tasks. In this context, a principal can design a monetary contract to stimulate an agent to exert private efforts towards training a classifier. In the proposed framework, the agent's private actions is the number of samples he/she can process, while the principal operates within a monetary budget $B$. Importantly, the contract design is entirely based on observed outcomes, modeled as the prediction accuracy of the agent's trained classifier against the validation samples. The paper first shows that the budget-optimal contract is essentially an all-or-nothing contract when the agent has only binary actions. Then the paper also provides several (structural) characterizations on the optimal contract if the action-to-outcome distributions satisfy certain regularity assumptions (e.g., monotone likelihood ratio property, concavity). Finally, the paper also provides empirical results to study how the model parameters affect the design of the contracts and the resulting agent’s trained classifier.

Strengths

The paper is rigorous and very well-written. I largely view this work as an modeling paper. The proposed principal-agent framework is novel and interesting, and it provides an economic view to understand the dynamics when a training task is delegated to another entity, potentially possessing conflicting interests. The paper also provides several characterizations on the optimality of contract when the considered problem has some certain structure (e.g., binary-action, binary-outcome), and also some characterizations for the general action/outcome space but with imposing some additional assumptions. The empirical section also adequately evaluates the proposed framework.

Weaknesses

My main concern regarding the paper lies within the technique results. It is noted that many of the characterizations about the optimal contract align closely with, or can be derived from, recent research on the algorithmic principal-agent problem. For instance, as noted by the author (line 262), the optimal contract for binary-action can be derived using the Linear Programming (LP) duality. The paper instead uses a proof approach related to hypothesis testing. It could enhance the paper's value if the author elucidated the advantages of this particular approach. Can it illuminate more complex instances, and if so, how? In addition, in my humble opinion, it seems that the current characterizations could also be derived by merely considering a pure principal-agent problem, thereby bypassing any classification or machine learning elements. Since the primary aim of this paper is to frame the delegated training problem as a principal-agent problem, I believe the exploration could be enriched if it delves deeper into how typical tradeoffs (e.g., the number of samples used by the agent has some implications on the prediction accuracy in a quantitive way via some generalization error) in standard machine learning tasks affect the considered game. Other questions: 1. missing refs in Line 93 2. it is a bit confusing in Proposition 2, is that $B$ the budget? If so, then by definition of all-or-nothing contract, there should be only one outcome that has positive payment? 3. In Program (5) in Appendix B.2, the objective should be $t$?

Questions

See above

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

No

Summary

The paper studies the problem of a decision maker (the principal) delegating the task of training a machine learning model to an agent. Both parties are strategic, and the principal must commit to a contract to encourage the agent to invest effort (e.g., labeling training samples). The authors consider the principal's problem of designing the optimal contract subject to a budget constraint, which maximizes the expected performance of the model trained by the agent given that the agent best responds to the contract. Technically, they give (1) an LP-based algorithm for computing the optimal contract, (2) a characterization connecting the optimal contract to hypothesis testing when the agent has only 2 possible actions, and (3) another characterization stating that optimal contracts have a simple form when the learning curve satisfies certain conditions. They validate these findings with experiments, and also empirically study a setting where the principal does not have enough information and therefore must estimate the learning curve.

Strengths

The problem is natural and exhibits quite some theoretical depth. The paper is well written, and in particular, the introduction nicely motivates the problem. The technical results are nice and clean, and they also appear to be practically meaningful, as supported by experimental results.

Weaknesses

While I like the paper overall, one concern is regarding the model: the model is quite specific, and I wonder if / to what extent the results can be generalized and remain (approximately) valid. Another practical concern is regarding scalability: in the experimental section the authors say that their full LP solver works for m no larger than 20, which doesn't sound like a very practical number; there is the local solver but it's not totally clear what it does, or how reliable it is. Also see detailed comments for some minor points.

Questions

(also putting minor comments here) Figure 1: at this point it's not totally clear to me what role m plays in the model. In particular, how should m be chosen (either by nature or by the principal), and how does the choice affect the performance of the contract? I'm sure this will become clear later, but it might make sense to briefly comment earlier, perhaps in a footnote. Line 56, "MLRP": what does this mean? Line 93: broken citation Line 120: "... principal cannot now how many examples ..." Line 130: "a-priory" Line 266, "under MLRP n_2 is always implementable": I'm not sure I get this --- what if c_2 - c_1 > B? Line 272, "important special case of binary-outcome": this (corresponding to m = 1) sounds less practical to me. Any justification for the importance of this case? Theorem 2: I feel the way this result is presented in Table 1 is somewhat misleading. The impression I initially got from the table is that the problem of computing the unconditional, unrestricted optimal contract is NP-hard. Or is this actually implied by Theorem 2? Line 307, "as m increases, required budgets": unfinished sentence? Line 310, "the local solver is easy to run": what does the local solver do?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

n/a