Human Expertise in Algorithmic Prediction
Authors: Rohan Alur
Manish Raghavan
Devavrat Shah
Venue: NeurIPS 2024 oral (2024)
Keywords: human/AI collaboration
human/AI complementarity
multicalibration
machine learning for healthcare
trustworthy machine learning
Primary area: human-AI_interaction
TL;DR: We introduce a novel framework for incorporating human judgment into algorithmic predictions; our approach focuses on the use of human judgment to distinguish inputs which ‘look the same’ to any feasible predictive algorithm.

Abstract: We introduce a novel framework for incorporating human expertise into algorithmic predictions. Our approach leverages human judgment to distinguish inputs which are *algorithmically indistinguishable*, or "look the same" to predictive algorithms.  We argue that this framing clarifies the problem of human-AI collaboration in prediction tasks, as experts often form judgments by drawing on information which is not encoded in an algorithm's training data. Algorithmic indistinguishability yields a natural test for assessing whether experts incorporate this kind of "side information", and further provides a simple but principled method for selectively incorporating human feedback into algorithmic predictions. We show that this method provably improves the performance of any feasible algorithmic predictor and precisely quantify this improvement.  We find empirically that although algorithms often outperform their human counterparts *on average*, human judgment can improve algorithmic predictions on *specific* instances (which can be identified ex-ante). In an X-ray classification task, we find that this subset constitutes nearly 30% of the patient population. Our approach provides a natural way of uncovering this heterogeneity and thus enabling effective human-AI collaboration.

Human Expertise in Algorithmic Prediction
Rohan Alur EECS, LIDS MIT ralurGmit. edu
Manish Raghavan EECS, LIDS, Sloan MIT mragh@mit edu
Devavrat Shah EECS, IDSS, LIDS, SDSC MIT devavrat@@itt.ede
Abstract
We introduce a novel framework for incorporating human expertise into algorithmic predictions. Our approach leverages human judgment to distinguish inputs which are algorithmically indistinguishable or "look the same" to predictive algorithms. We argue that this framing clarifies the problem of human-Al collaboration in prediction tasks, as experts often form judgments by drawing on information which is not encoded in algorithm's 's training data. Algorithmic indistinguishability yields natural test for assessing whether experts incorporate this kind of "side information", and further provides simple but principled method for selectively incorporating human feedback into algorithmic predictions. We show that this method provably improves the performance of any feasible algorithmic predictor and precisely quantify this improvement. We find empirically that although algo- rithms often outperform their human counterparts on average, human judgment can improve algorithmic predictions on specific instances (which can be identified ex-ante). an X-ray classification task, we find that this subset constitutes nearly 30% of the patient population. Our approach provides a natural way of uncovering this heterogeneity and thus enabling effective human-Al collaboration.
Introduction
Despite remarkable advances in machine learning, human judgment continues play critical role in many high-stakes prediction tasks. For example, consider the problem of triage in the emergency room, where healthcare providers assess and prioritize patients for immediate care. On one hand, prognostic algorithms offer significant promise for improving triage decisions; indeed, algorithmic predictions often more accurate than expert human decision makers [13, 17, 30, 41, 44, 16. 15, 53]. On the other hand, predictive algorithms may fail to fully capture the relevant context for each individual. For example, algorithmic risk score may only have access tabular electronic health records or other structured data (e.g., medical imaging), while a physician has access to many additional modalities not least of which is the ability to directly examine the patient!
These two observations-that algorithms often outperform humans, but humans often have access to a richer information set-are not in conflict with each other. Indeed, [3] find exactly this phenomenon in an analysis emergency room triage decisions. This suggests that, even in settings where algorithms outperform humans, algorithms might still benefit from some form of human input. Ideally this collaboration will yield human-A/ complementarity [6, 61], in which joint system outperforms either human algorithm working alone. Our work thus begins with the following question:
When (and how) can human judgment improve the predictions of any learning algorithm?
Example: X-ray classification. Consider the problem of diagnosing atelectasis (a partially fully collapsed lung; we study this task in detail in Section 5). Today's state-of-the-aat deep learning models can perform well these kinds of classification tasks using only patient's chest X-ray as
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

input [35, 59, 11. We are interested in whether we can further improve these algorithmic predictions by incorporating "second opinion" from a physician, particularly because the physician may have access to information (e.g., by directly observing the patient) which is not present in the X-ray.
A first heuristic, without making any assumptions about the available predictive models, is to ask whether a physician can distinguish patients whose imaging data are identical. For example, if a physician can correctly indicate that one patient is suffering from atelectasis while another is not-despite the patients having identical chest X-rays-the physician must have information that the X-ray does not capture. In principle, this could form the basis for a statistical test: we could ask whether the physician performs better than random in distinguishing a large number of such patients. If so, even a predictive algorithm which outperforms the physician might benefit from human input.
Of course, we are unlikely to find identical observations in continuous-valued and/or high-dimensional data (like X-rays). A natural relaxation is to instead consider observations which are sufficiently "similar", as suggested by [3]. In this work we propose a more general notion of algorithmic indistinguishabiliy, or coarser subsets of inputs in which no algorithm (in some rich, user-defined class) has significant predictive power. We show that these subsets can be discovered via novel connection multicalibration [33], and formally demonstrate that using human feedback predict outcomes within these subsets can outperform any algorithmic predictor (in the same user-defined perspective:
class). In addition to being tractable, this framework relevant from a although we' ve focused thus far on algorithms' fundamental informational constraints, it is also natural to ask whether an expert provides signal which is merely difficult for an algorithm to learn directly (due to e.g., limited training data or computational constraints). Our approach naturally interpolates between these contexts by defining indistingushaabiliyy with respect to whichever class of models is practically relevant for a given prediction task. We elaborate on these contributions below.
Contributions. We propose a novel framework for human-AI collaboration in prediction tasks. Our approach uses human feedback to refine predictions within sets of inputs which are algorithmically indisinguuisable, or "look the same" to predictive algorithms. In Section 4 we present a simple method to incorporate this feedback only when it improves on the best feasible predictive model (and precisely quantify this improvement). This extends the "omnipredictors" result of [28] in the special case of squared error, which may be of independent interest. In Section 5 we present experiments demonstrating that although humans fail to outperform algorithmic predictors on average, there exist specific (algorithmically indistinguishable) instances on which humans are more accurate than the best available predictor (and these instances are identifiable ex ante). 2 In Section we consider the complementary setting in which an algorithm provides recommendations to many downstream users, who independently choose when to comply. We provide conditions under which a predictor is robust to these compliance patterns, and thus be simultaneously optimal for all downstream users.
2 Related work
The relative strengths of humans and algorithms. Our work is motivated by large body of literature which studies the relative strengths of human judgment and algorithmic decision making [13, 17, 30, 44] or identifies behavioral biases in decision making [66, 11, 4, 60). More recent work also studies whether predictive algorithms can improve expert decision making [41, 53, 7, 1].
Recommendations, deferral and complementarity. One popular approach for incorporating human judgment into algorithmic predictions is by deferring some instances to a human decision maker (49, 58, 52,37, 55, 38). Other work studies contexts where human decision makers are free to override algorithmic recommendations [20, 8. 14, 22, 1]. which may suggest alternative design criteria for these algorithms [5, 9, 34]. More generally, systems which achieve human-Al complementarity (as defined in Section 1) have been previously studied in [2, 5, 69, 23, 64, 19, 47].
[61] develop a comprehensive taxonomy of this area, which generally takes the predictor as given, or learns a predictor which is optimized to complement a particular model of human decision making. In contrast, we give stronger results which demonstrate when human judgment can improve the performance of any model in a rich class of possible predictors (Section 4), or when single algorithm can complement many heterogeneous users (Section 6).
We provide additional technical results Appendix A. We elaborate on connections to [28] in Appendix D. "Code replicate our experiments is available https: h /ttp//gtttthuttt//// com/ralur/heeppregg
2

---

Performative prediction. A recent line of work studies performative prediction [57], or settings in which predictions influence future outcomes. For example, predicting the risk of adverse health outcomes may directly inform treatment decisions, which in turn affects future health outcomes. This can complicate the design and evaluation of predictive algorithms, and there is a growing literature which seeks to address these challenges [10, 51, 31, 21, 36, 39, 50, 67, 32, 70, 48, 54, 56]. Performativity is also closely related to the selective labels problem, in which some historical outcomes are unobserved as a consequence of past human decisions [45]. Though these issues arise in many canonical human-Al collaboration tasks, we focus on standard supervised learning problems in which predictions do not causally affect the outcome of interest. These include e.g., weather prediction, stock price forecasting and many medical diagnosis tasks, including the X-ray diagnosis task we study in Section 5. In particular, although physician's 's diagnosis may inform subsequent treatment decisions, it does not affect the contemporaneous presence or absence of a disease. More generally, our work can be applied any "prediction policy problem", where accurate predictions can be translated into policy gains without explicittyy explicitly modeling causality [42].
Algorithmic monoculture. Our results can be viewed one approach to mitigating algorithmic monocultrre, in which different algorithms make similar decisions and thus similar mistakes [43, 65]. This could occur because these systems are trained on similar datasets, or because they share similar inductive biases. We argue that these are precisely the settings in which a "diversifying" human opinion may be especially valuable. We find empirical evidence for this in Section 5: on instances where multiple models agree on a prediction, human judgment adds substantial predictive value.
Multicalibration, omnipredictors and boosting. Our results make use of tools from theoretical computer science, particularly work on onnipredictors [28] and its connections to multicalibration. [24] show that multicalibration is tightly connected to a cryptographic notion of indistinguishability. which serves as conceptual inspiration for our work. Finally, [27] provide an elegant boosting algorithm for learning multicalibrated partitions that we make use of in our experiments, and [29] provide results which reveal tight connections between a related notion of "swap agnostic learning", multi-group fairness, omniprediction and outcome indistinguishability.
3 Methodology and preliminaries
Notation. Let X E X' be random variable denoting the inputs (or "features") which are available for making algorithmic predictions about an outcome Y [0, 1]. Let Ý E [0, 1] be an expert's prediction of Y, and let v. y, ú denote realizations of the corresponding random variables. Our approach is parameterized by a class of predictors F, which is some set of functions mapping X' to [0, 1]. We interpret F as the class of predictive models which are relevant (or feasible to implement) for a given prediction task; we discuss this choice further below. Broadly, we are interested in whether the expert prediction Y provides a predictive signal which cannot be extracted from X by any F.
Choice of model class F. For now we place no restrictions on F, but it's helpful to consider a concrete model class (e.g.. specific neural network architecture) from which, given some training data, one could derive a particular model (e.g., via empirical risk minimization over F). The choice of F could be guided by practical considerations; some domains might require interpretable models (e.g., linear functions) or be subject to computational constraints. We might also simply believe that a certain architecture or functional form is well suited to the task of interest. In any case, we are interested in whether human judgment can provide information which is not conveyed by any model in this class, but are agnostic as to how this accomplished: an expert may have information which is not encoded in X, or be deploying decision rule which is not in F F- or both!
Another choice is to take F to model more abstract limitations the expert's cognitive process. In particular, to model experts who are subject to "bounded rationality" [63, 40], F might be the set of functions which can be efficiently computed (e.g., by circuit of limited complexity). In this case, an expert who provides a prediction which cannot be modeled by any ʃ E F must have access to information which is not present in the training data. We take the choice of F as given, but emphasize that these two approaches yield qualitatively different insight about human expertise.
indistinguishability with respect to F. Our approach will be to use human input to distinguish observations which are indistinguishable to any predictor f E F. We formalize this notion of indistinguishabiliyy follows:
3

---

Definition 3.1 (a- (a-Indistinguisabll subset), For some a 2 0, set S S A' o-indistinguishable with respect to function class JF and target Y for all f f F,
(f X S) a
(1)
To interpret this definition, observe that the subset S can be viewed generalizing the intuition given in Section for grouping identical inputs. In particular, rather than requiring that all a E S exactly equal, Definition 3.1 requires that all members of S effectively "look the same" for the purposes of making algorithmic predictions about Y, as every f E F only weakly related to the outcome within S. We now adopt the definition of multicalibrated partition [28] follows:
Definition 3.2 (a-Multicalibrated partition). For 2 1, S1 ... SK S X is an a-multicalibrated partition with respect to F and Y if (1) . Sk partitions. X' and (2) each Sg is c-indistinguishable with respect to and Y.3
Intuitively, the partition {St] "extract[s] all the predictive power" from F [28]; within each element of the partition, every F is only weakly related to the outcome Y. Thus, while knowing that an input æ lies in subset Sg may be highly informative for predicting Y - for example, may be that E| X x] s EE[Y X x'I for all x, E Ss no predictor E F provides significant additional signal within Sk. We provide a stylized example of such partitions in Figure below.
5,
+
+
+
+
S/s
(b)
Figure I: Partitions which are approximately multicalibrated with respect to the class of hyperplane classifiers (we consider the empirical distribution placing equal probability on each observation). In both panels, no hyperplane classifier has significant discriminatory power within each subset.
It's not obvious that such partitions feasible to compute, even that they should exist. We'll show in Appendix B however that a multicalibrated partition can be efficiently computed for many natural classes of functions. Where the relevant partition is clear from context, [.I.]. Vara (-), Cova(:,.) to denote expectation, variance and covariance conditional on the event that {X E S. For subset S X, we use Es(r], (.rs(.) and Covs(:;) analogously.
Incorporating human judgment into predictions. To incorporate human judgment into predictions, a natural heuristic is to first test whether the conditional covariance Cov (Y, Y) is nonzero within some indistinguishable subset. Intuitively, this indicates that the expert prediction is informative even though every model f E is not. This suggests a simple method for incorporating human expertise: first, learn a partition which is multicalibrated with respect to F, and then use ý to predict y within each indistinguishable subset. We describe this procedure in Algorithm below, where we define a univariate learning algorithm A as procedure which takes one or more (0i, Mr) E [0, 1]² training observations and outputs function which predicts Y using Y. For example, A might be an algorithm which fits a univariate linear logistic regression which predicts Y as a function of Y
Algorithm simply learns a different predictor of Y as function of Ý within each indistinguishable subset. As we show below, even simple instantiations of this approach can outperform the squared error achieved by any f F. This approach can also be readily extended to more complicated forms of human input (e.g., freeform text, which can be represented as nigh-dimensional vector rather than point prediction Y), and can used to test whether human judgment provides information that algorithm cannot learn from the available training data. We turn to these results below.
'This closely related to a-approximate multicalibration [28]. which requires that Definition 3.1 merely holds in expectation over the partition. We work with stronger pointwise definition for clarity, but our results also be interpreted holding for the 'typical' element of a-approximately multicalibrated partition.

---

Algorithm A method for incorporating human expertise into algorithmic predictions
1: Inputs: Training data (Ii, Vt, De 1 a multicalibrated partition (St univariate regres- sion algorithm A, and a test observation (In+1; Do+1)
2: Output: A prediction of the missing outcome Un+1
3: for = 1 to K do
3: Zx (0), Us) IJ E S
3: Øk 6 A-Z)))
4: end for
5: k" + the index of the subset Sy which contains 2n+1
6: return 9x- (fn+1)
4 Technical results
In this section we present our main technical results. For clarity, all results in this section are presented in terms of population quantities, and assume oracle access multicalibrated partition. We present corresponding generalization arguments and background on learning multicalibrated partitions in Appendices and B, respectively. All proofs are deferred to Appendix C.
Theorem 4.1. Let {Sk]kEJK] be a-muliicalibruted partition with respect model class F
and larget Y. Let the random variable (XX E [K] be such that J (X) = k iff X Sx Define ,,, E R.K as
9, E arg min
E
(2)
TERK BERK
Then, for any f E and k E [K].
Ex (x- -1-7% - -B2)) 4Cov s Es (x-
- f(x)) + 2a.
(3)
That is, the squared error incurred by the univariate linear regression of on Ý within each indistinguishable subset outperforms that of any f F. This improvement at least 4Cov (Y, y)? up to an additive approximation error 2a. We emphasize that F is arbitrary class, and may include complex, nonlinear predictors. Nonetheless, given a multicalibrated partition, a simple linear predictor improve the best f F. Furthermore, this approach allows to selectively incorporate human feedback: whenever CYv 8) O, recover a coefficient 37 of 0.*
Nonlinear functions and high-dimensional feedback. Theorem 4.1 corresponds to instantiating Algorithm 1 with a univariate linear regression, but the same insight generalizes readily to other functional forms. For example, if is binary, it might be desirable instead fit logistic regression. We provide a similar guarantee for generic nonlinear predictors via Corollary A. 1 in Appendix A. Furthermore, while the results above assume that expert provides prediction Y [0, 1]. the same insight extends to richer forms of feedback. For example, in a medical diagnosis task, a physician might produce free-form clinical notes which contain information that is not available in tabular electronic health records. Incorporating this kind of feedback requires a learning algorithm better suited to high-dimensional inputs (e.g., deep neural network), which motivates our following result.
Corollary 4.2. Let S be an a- a--indstinguishable subset with respect to a model class F and target Y. Let H E H denote expert feedback which takes values in some arbitrary domain (e.g., frefform text, which might be tokenized to take values in zd for some d > 0), and let g : H [0. 1] be function which satisfies the following approximate calibration condition for some 2 and for all B, E TR.
Es((Y -(()) < Es((Y - -
(4)
Then, for any f F,
*Recall that the population coefficient in univariate linear regression of Y on & is Cov(Y,
Var(Y")
5

---

Es [ g(H))² + (Covs((Y = Es f(x))²] + 2a +n.
(5)
To interpret this result, notice that (4) requires only that the prediction g(H) cannot be significantly improved by any linear post-processing function. For example, this condition is satisfied by any calibrated predictor g(H)) Furthermore, any g g(H) which does not satisty (4) can be transformed by letting 0(H) = ming, [E{ y 3g( (g((t))]]; }) i... by linearly regressing Y on g(H), in which case g(H) satisfies (4). This result mirrors Theorem 4.1: a predictor which depends only on human feedback H can improve on the best f E FF within each element of multicalibrated partition.
Testing for informative experts. While we have thus far focused on incorporating human judgment to improve predictions, we may also be interested in the related question of simply lesting whether human judgment provides information that cannot be conveyed by any algorithmic predictor. For example, such test might be valuable in deciding whether to automate a given prediction task.
Theorem 4. suggests heuristic for such a test: if the conditional covariance Cov Ý) is large, then we might expect that Y is somehow "more informative" than any S E F within Sg- While covariance only measures a certain form linear dependence between random variables, we now show that, in the special case of binary-valued algorithmic predictors, computing the covariance of Y and y within an indistinguishable subset serves stronger test for whether Y provides any predictive information which cannot be expressed by the class F.
Theorem 4.3. Let {Sk]ke(K] be an a-multicalibrated partition for a binary-valued model class F.binary and target outcome Y. For all k E [K], let there be fir E F such that Y IL Y [X)) X e Sg. Then, for all E [K].
(ov S aa
(6)
That is, if each indistinguishable subset has a corresponding predictor foe which "explains" the signal provided by the human, then the covariance of Y and is bounded within every Sg. The contrapositive implies that a sufficiently large value of Cov & (Y, Y) serves as a certificate for the property that no f F can fully explain the information that Y provides about Y within each indistinguishable subset. This can be viewed as a finer-grained extension of the test proposed in [3].
Taken together, our results demonstrate that algorithmic indistinguishability provides principled way of reasoning about the complementary value of human judgment. Furthermore, this approach yields concrete methodology for incorporating this expertise; we can simply use human feedback to predict Y within subsets which are indistinguishable on the basis of X alone. Operationalizing these results depends critically on the ability to learn multicalibrated partitions, e.g., via the boosting algorithm proposed in [27]. We provide additional detail on learning such partitions in Appendix B.
5
Experiments
5.1 Chest X-ray interpretation
We now instantiate framework in the context of the chest X-ray classification task outlined in Section We consider the eight predictive models studied in [59], which were selected from the leaderboard of a large public competition for X-ray image classification. These models serve natural benchmark class F, against which we investigate whether radiologist assessments provide additional predictive value. These models were trained collected across 65, 65,240 patients [35], and then evaluated on a holdout set of 500 randomly sampled radiographs. This holdout set annotated by eight radiologists for the presence (Y 1) absence (Y = 0) of five selected pathologies; the majority vote of five radiologists serves as ground truth label, while the remaining three are held out assess the accuracy of individual radiologists [59].
dataset of 224,316 chest radiographs
A calibrated predictor is one where Es 9(H) g(H). This is fairly weak condition; for example, it is satisfied by the constant predictor g(H) = [Y] [18, 25).

---

In this section we focus on diagnosing atelectasis (a partial or complete collapse of the lung); we provide results for the other four pathologies Appendix We first show, consistent with [35, 59], that radiologists fail to consistently outperform algorithmic classifiers then demonstrate that radiologists do outperform all eight leaderboard algorithms on large subset (nearly 30% of patients) which is indistinguishable with respect to this class of benchmark predictors. Because radiologists this experimental setting only have access to the patient's chest X-ray, and because do not apply any postprocessing to the radiologist assessments (i.e., 9k. as defined in Algorithm 1, is simply the identity function, which is most natural when Y and Y are binary), interpret these results as providing lower bound on the improvement that radiologists can provide relative to relying solely on algorithmic classifiers.
average. However, we
Algorithms are competitive with expert radiologists. We first compare the performance of the three benchmark radiologists to that of the eight leaderboard algorithms in Figure 2. Following [59], we use the Matthew's Correlation Coefficient (MCC) as a standard measure of binary classification accuracy [12]. The MCC is simply the rescaled covariance between each prediction and the outcome, which corresponds directly to Definition 3.1. In Figure we see that radiologist performance statistically indistinguishable from that of the algorithmic classifiers.
0.7
Correlation Coefficient
predictor
dmet
ihil
jfaboy
0.6
ngango2
ngango3
sensexdr
uestc
yww211
0.5
radiologist
radiologist
radiologist 3
algorithmic
radiologist
Prediction Type
Figure 2: The relative performance of radiologists and predictive algorithms for detecting atelectasis. Each bar plots the Matthews Correlation Coefficient between the corresponding prediction and the ground truth label. Point estimates are reported with 95% bootstrap confidence intervals.
Radiologists can refine algorithmic predictions. We now apply the results Section 4 to investigate heterogeneity in the relative performance of humans and algorithms. First, we partition the patients into pair of approximately indistinguishable subsets, which are exceptionally straightforward compute when the class F has finite number of predictors (we provide additional detail in Appendix F). We plot the conditional performance of both the radiologists and the eight leaderboard algorithms within each of these subsets in Figure
While Figure 2 found no significant differences between radiologists' and algorithms'' overall per- formance, Figure reveals large subset subset 0, consisting of 29.6% of sample where radiologists achieve a better MCC than every algorithm. In particular, every algorithm predicts a positive label for every patient in this subset, and radiologists identify sizable fraction of true negatives that the algorithms miss. For example, radiologist achieves a true positive rate of 84.0% and negative rate of 42.9%, while the algorithms achieve corresponding rates of 100% and 0%.
This partition is not necessarily unique, and principle an analyst could compare the performance of starker difference in
radiologists and algorithms across different subsets which could yield conditional performance. However, even for discrete-valued data, searching over possible subsets computationally and statistically intractable; instead, our approach provides principled way of identifying the particular subsets which human judgment is likely to add predictive value.
Other pathologies. Although we focus here on atelectasis, and the findings above are consistent for two the other four pathologies considered in [59] (pleural effusion and consolidation): although radiologists fail to outperform algorithms average, at least two of the radiologists outperform algorithmic predictions on sizable minority patients. Results for cardiomegaly and edema appear qualitatively similar, but lack statistical power. We present these results in Appendix G.
7

---

0.6
predictor
Correlation Coefficient
random baseline
0.4
dmet
ihil
jfaboy
0.2
ngango2
ngango3
0.0
sensexdr
uestc
yww211
-0.2
radiologist
radiologist
-0.4
radiologist 3
Subset
Subset
Subset Index
Figure 3: Conditional performance for atelectasis. Within subset O (n 148), all algorithms predict Y=1, thus achieving true positive rate (TPR) 1, true negative rate (TNR) and an MCC of Radiolo- gists achieve a corresonningg (TPR, TNR) of (84.0%, 42.9%). (72.6%, 47.6%) and (93.4%, 19.0%), respectively. Subset (n = 352) contains the remaining patients. The baseline a random permuta- tion of the labels. Confidence intervals for algorithmic performance are not strictly valid (subsets are chosen conditional on the predictions), but are included for reference. All else is as in Figure 2.
5.2 Prediction of success in human collaboration
We next consider the visual prediction task studied in [62]. this work, the authors curate photos taken of participants after they attempt an Escape the Room' puzzle-"a physical adventure game which group is tasked with escaping a maze by collectively solving a series of puzzles" [62]. A separate set of subjects are then asked to predict whether the group in each photo succeeded in completing the puzzle. Subjects the control arm perform this task without any form of training, while subjects in the remaining arms are first provided with four, eight and twelve labeled examples. respectively. Their performance is compared to that of five algorithmic predictors, which use 33 high-level features extracted from each photo (e.g., number of people, gender and ethnic diversity, age distribution etc.) to make competing prediction. We provide full list features in Appendix H.
Accuracy and indistinguishability in visual prediction. As in the X-ray diagnosis task, we first compare the performance of human subjects to that of the five off-the-shelf predictive algorithms considered in [62]. We again find that although humans fail to outperform the best predictive algorithms, their predictions add significant predictive value on instances where the algorithms agree on positive label. As our results are similar to those in the previous section, we defer them to Appendix We now use this task illustrate another feature of our framework, which the ability to incorporate human judgment into substantially richer class of models.
infinite class. While our previous results illustrate that human judgment can complement a small, fixed set of predictive algorithms, it's possible that richer class could obviate the need for human expertise. To explore this, now consider an infinitely large but nonetheless simple class of shallow (depth < 5) regression trees. We denote this class by JRĪS
Multicalibration
As in previous sections, first step will be to leamn partition which is multicalibrated with respect to FRIS_ However, because FkTS is infinitely large, enumerating each f J=TS and clustering observations according to their predictions is infeasible. Instead, we apply the boosting algorithm proposed in [27] to construct predictor h X' -> [0, 1] such that no E FRTS can substantially improve the squared error of h within any of its approximate level sets {a h(z) 0), far
h(x) E (0..1)... {x (xx) E [.9, 1]]. We plot the correlation of the human subjects' predictions with the true label within these level sets in Figure 4.
Figure 4 highlights a key insight provided by our framework. On one hand, the predictions made by more accurate out of sample (72.2%) than even the best performing cohort (67.3% (3%.%)) Nonetheless, the predictions made by all four cohorts of human subjects are predictive the outcome within every
'We discuss the connection between this condition and multicalibration in Appendix B. As in the previous section, we cannot necessarily verify whether the multicalibration condition is satisfied empirically. However, the theory provides guidance for choosing subsets, within which directly test conditional performance.

---

Correlation Coefficient
0.4
predictor
random baseline
multicalibrated predictor
0.2
(control)
human (4 examples)
human (8 examples)
human (12 examples)
0.0
Level Set Index
Figure 4: Human performance within the approximate level sets of predictor h which is multical-
ibrated over FRTS Level sets 0, 1, and 10 are the sets {a h(x) = 0}. {z h(x) (0,.1]), and {æ h(x)) E [.9, I]]. and contain 259, 309 and 292 observations, respectively. All other level sets are empty our test set. random permutation of the labels is included as a baseline.
nonempty level set of of h.? This suggests that humans provide information which cannot be extracted from the data by any FRTS, While we focus on shallow regression trees for concreteness, this approach extends to any function class for which it is feasible to learn multicalibrated partition.
6 Robustness to noncompliance
We have thus far focused on how an algorithm might incorporate human feedback to improve prediction accuracy, how algorithmic decision pipeline might selectively defer to human expert. However, many decision support tools are deployed the opposite setting where the user instead decides when defer the algorithm. For example, physicians with access prognostic risk score may choose to simply ignore the risk score at their discretion. Furthermore, is common for hospitals employ different norms and policies governing the of algorithmic predictors [46]. Thus, although it is tempting to simply provide all downstream users with the single "best" risk score, such an approach can be suboptimal if users vary their compliance behavior [5]. We illustrate the challenges of this kind of heterogeneous user behavior via the following stylized example.
Example: the challenge of noncompliance. Consider generic prognostic risk recommendations regarding patient care. Although physicians generally comply with the algorithm's recommendations, they free override they see fit. For example, suppose that one particular physician believes (correctly or not) that the algorithm underweights high blood pressure as a risk factor, and thus ignores its recommendations for these patients. second physician similarly ignores algorithmic recommendations and instead exercises their own judgment for patients 65 and older.
which makes
What does optimal risk score look like in this setting? For the first physician, would like to select the algorithm which minimizes error on patients who do not have high blood pressure, as these are the patients for whom the physician uses the algorithm's 's recommendations. Similarly, for the second physician, we would like to minimize error on patients who are under 65. Of course, there is guarantee that these the population will, in general, produce different predictor than empirical risk minimization over the second population. This is not just finite sample problem; given any restricted model class (e.g., linear predictors), the optimal predictor for one subpopulation may not be optimal for different subpopulation. For both practical and ethical reasons however, cannot design individualized predictors for every physician; we would like to instead provide a risk score which is simultaneously "optimal" (in sense we make precise below) for every user.
algorithm: empirical risk minimization over the first
Noncompliance-robus prediction. In Appendix A.3, we show that, without further assumptions, the setting described above poses statistically intractable problem: if physicians choose whether
Though this result may initially seem counterintuitive, recall the classical Simpson's paradox: in setting where Y is uncorrelated (or even negatively correlated) with Y. there may still exist partition of the data such that the two positively correlated within every subgroup.

---

to comply in arbitrary ways, then we need a predictor which is simultaneously optimal for every possible patient subpopulation. The only predictor which satisfies this criterion the Bayes optimal predictor, which is infeasible to learn in a finite data regime.
However, suppose instead that physicians decide whether to defer to the algorithm using relatively simple heuristics. If we believe we can model these heuristics as "simple" function of observable patient characteristics - e.g. that all compliance patterns can be expressed as a shallow decision tree, even if particular compliance behavior varies across physicians - then we can leverage this structure to design a single optimal predictor. In particular, we show next that, given a partition which is multicalibrated over the class of possible user compliance patterns, we can learn predictors which remain optimal even when users only selectively adopt the algorithm's 's recommendations.
Theorem 6.1. Let II be class of binary compliance policies, where, for E I1, π(х) 1 indicates that the user complies with the algorithm X x. Let F be class of predictors and let {Sk kKERK] be a partition which is a-multicalibrated with respect to Il and the product class (J(X)T(()) E F, I1. Then, V E. F, E ETT,A. E [K].
6a
Bx[(Y - Ex x(X)= =1 E.SEE -
- ((X))² [(X)= -1 (x()
That is, given an appropriately multicalibrated partition, ously near-optimal for every downstream user. In particular, observe that the left hand side of (7) is the squared error incurred by the constant prediction E& [Y] within Sy when the user defers to the algorithm. Although this prediction does not depend on the policy æ, it remains competitive with the squared error incurred by any f F for any policy. Unsurprisingly, the bound becomes vacuous as ( (T(X) 1) goes to 0 (we cannot hope to learn anything on arbitrarily rare subsets). This is consistent with our interpretation of however, as the performance of the algorithm matters little if the decision maker ignores nearly all recommendations.
derive predictor which is simultane-
This result is complementary to those in Section 4 rather than learning to incorporate feedback from a single expert, we can instead learn a single predictor which is (nearly) optimal for a rich class of downstream users whose behavior is modeled by some II.
7 Discussion and limitations
In this work we propose an indistinguishaailltt-aass framework for human-AI collaboration. Under this framework, we develop a set of methods for testing whether experts provide predictive signal which cannot be replicated by an algorithmic predictor, and extend our results to settings in which users selectively adopt algorithmic recommendations. Beyond these methodological contributions, we argue that our framing clarifies when and why human judgment can improve algorithmic performance. In particular, primary theme in our work is that even if humans do not consistently outperform algorithms on average. selectively incorporating human judgment can often improve predictions.
A key limitation of our work is a somewhat narrow focus on minimizing a well-defined loss function over a well-defined (and stationary) distribution. This fails to capture decision makers with richer, multidimensional preferences (e.g., fairness, robustness or simplicity), and does not extend to settings in which predictions influence future outcomes (see the discussion of performative prediction in Section 2) or the distribution otherwise changes over time. However, we view indistinguishabilit as a powerful primitive for modeling these more complex scenarios; for example, a decision maker might impose additional preferences - like a desire for some notion of fairness - to distinguish inputs which are otherwise indistinguishable with respect to the "primary" outcome of interest. At a technical level, results rely on the ability to efficiently learn multicalibrated partitions. While give conditions under which this is feasible in Appendix and a finite sample analysis in Appendix A, finding such partitions can be challenging for rich function classes.
Finally, we caution that even in contexts which fit neatly into our framework, human decision makers can be critical for ensuring interpretability and accountability. Thus, although our approach can provide guidance for choosing the appropriate level of automation, it does not address the practical or ethical concerns which arise. Despite these limitations, we argue that indistinguishability helps to clarify the role of human expertise algorithmic decision making, and this framing turn provides fundamental conceptual and methodological insights for enabling effective human-A4 AI collaboration.
10

---

Acknowledgements
RA, MR and DS are supported part by Stephen A. Schwarzman College of Computing Seed
Grant. DS is supported in part by an NSF FODSI Award (2022448).
References
[1] N. Agarwal, A. Moehring, P. Rajpurkar, and T. Salz. Combining human expertise with artificial intelligence: Experimental evidence from radiology. Technical report, Cambridge, MA, July 2023.
[2] A. Agrawal, J. Gans, and A. Goldfarb. Exploring the impact of artificial intelligence: Prediction versus judgment. Technical report, National Bureau of Economic Research, Cambridge, MA, May 2018.
[3] R. Alur, Laine, D. K. Li, M. Raghavan, D. Shah, and L. Shung. Auditing for human expertise. In Advances in Neural Information Processing Systems, volume 36, 2023.
[4] D. Arnol, W. Dobbie, and P. Hull. Mcasuring racial discrimination in bail decisions. Technical report, National Burcau of Economic Research, Cambridge, MA, Apr. 2020.
[5] G. Bansal, B. Nushi, E. Kamar, E. Horvitz, and D. S. Weld. Is the most accurate ai the best teammate? optimizing ai for teamwork, 2020.
[6] G. Bansal, T. Wu, Zhou, R. Fok, B. Nushi, E. Kamar, M. T. Ribeiro, and D. Weld. Does the whole exceed its parts? the effect of ai explanations on complementary team performance, 2020.
[7] H. Bastani, O. Bastani, and W. P. Sinchaisri. Improving human decision-making with machine learning, 2021.
[8] E. Beede, E. Baylor, F. Hersch, A. lurchenko, L. Wilcox, P. Ruamviboonsuk, and L. M. Vardoulakis. A human-centered evaluation of deep learning system deployed in clinics for the detection of diabetic retinopathy. Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems, 2020.
[9] N. L. C. Benz and M. G. Rodriguez. Human-aligned calibration for ai-assisted decision making, 2023.
[10] G. Brown, S. Hod, and I. Kalemaj. Performative prediction in stateful world. ArXiv, abs/2011 1.001,,0385, 2020.
[11] C. Camerer and E. Johnson. The process-performance paradox expert judgment: How can experts know much and predict badly? In A. Ericsson and J. Smith, editors, Toward General Theory of Expertise: Prospects and Limits. Cambridge University Press, 1991.
[12] D. Chicco and G. Jurman. The advantages of the matthews correlation coefficient (MCC) over F1 score and accuracy in binary classification evaluation. BMC Genomics, 21(1):6, Jan. 2020.
[13] B. Cowgill. Bias and productivity in humans and algorithms: Theory and evidence from resume screening, 2018.
[14] B. Cowgill and M. T. Stevenson. Algorithmic social engineering. AEA Pap. Proc., 10:99-1100. May 2020.
[15] J. Currie and W. B. MacLeod. Diagnosing expertise: Human capital, decision making, and performance among physicians. Labor Econ., 35(1):1-43, Jan. 2017.
[16] R. M. Dawes. A case study of graduate admissions: Application of three principles of human decision making. Am. Psychol., 26(2):180-188 Feb. 1971.
[17] R. M. Dawes, Faust, and P. E. Meehl. Clinical versus actuarial judgment. Science, 243(4899):1668-16777 1989.

---

[18] A. P. Dawid. The well-calibrated bayesian. Journal of the American Statistical Association, 77:605-610, 1982.
[19] A. De, N. Okati, A. Zarezade, and M. Gomez-Rodriguezz. Classification under human assistance, 2020.
[20] M. De-Arteaga, R. Fogliato, and A. Chouldechova. A case for humans-in-thes Decisions in the presence of erroneous algorithmic scores. 2020.
[21] S. Dean and J. Morgenstern. Preference dynamics under personalized recommendations. Proceedings of the 23rd ACM Conference Economics and Computation, 2022.
[22] B. Dietvorst, J. Simmons, and C. Massey, Overcoming algorithm aversion: People will use imperfect algorithms if they can (even slightly) modify them. Management Science, 64:1155- 1170, 03 2018.
[23] K. Donahue, A. Chouldechova, and K. Kenthapadi. Human-algorithm collaboration: Achieving complementarity and avoiding unfairness, 2022.
[24] C. Dwork, M. P. Kim, O. Reingold, G. N. Rothblum, and G. Yona. Outcome indistinguishability. 2020.
[25] D. P. Foster and R. V. Vohra. Asymptotic calibration. Biometrika, 85(2):379-390, 1998.
[26] C. Garbin, P. Rajpurkar, J. Irvin, M. P. Lungren, and O. Marques. Structured dataset documenta- tion: a datasheet for chexpert, 2021.
[27] I. Globus-Harri,, D. Harrison, M. Kearns, A. Roth, and J. Sorrell. Multicalibration as boosting for regression, 2023.
(28) P. Gopalan, A. T. Kalai, O. Reingold, V. Sharan, and U. Wieder. Omnipredictors. In Innovations Theoretical Computer Science 2022), 2022.
[29] Gopalan, M. P. Kim, and O. Reingold. Swap agnostic learning, or characterizing omnipredic- tion via multicalibration, 2023.
[30] W. M. Grove, D. H. Zald, B. S. Lebow, B. E. Snitz, and C. Nelson. Clinical versus mechanical prediction: a meta- analyssnalysi.. Psychol Assess, 12(1):19-30 30, Mar 2000.
[31] M. Hardt, M. Jagadeesan, and C. Mendler-Dünner. Performative power. ArXiv, abs/2203.12232. 2022.
[32] M. Hardt and C. Mendler-Dünner. Performative prediction: Past and future. abs/2310.16600, 2023.
ArXiv,
[33] U. Hébert-Johnson, M. Kim, O. Reingold, and G. Rothblum. Multicalibration: Calibration for the coompurationally-deenffaa
masses. International Conference on Machine Learning, pages 1939-1948. PMLR, 2018.
[34] A. Hüyük, Q Wei, A. Curth, and M. van der Schaar. Defining expertise: Applications to treatment effect estimation, 2024.
[35] J. Irvin, P. Rajpurkar, M. Ko, Y. Yu, S. Ciurea-Ilcus, C. Chute, H. Marklund, B. Haghgoo,
R. Ball, K. Shpanskaya, J. Seekins. D. A. Mong, S. S. Halabi, J. K. Sandberg, R. Jones, D. B.
Larson, C. P. Langlotz, B. N. Patel, M. P. Lungren, and A. Y. Ng. Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison, 2019.
[36] M. Jagadeesan, T. Zrnic, and C. Mendler-Dünner. Regret minimization with performative feedback. In International Conference on Machine Learning, 2022.
[37] V. Keswani, M. Lease, and K. Kenthapadi. Towards unbiased and accurate deferral to multiple experts. Proceedings of the 202/ AAAI/ACM Conference on AI, Ethics, and Society, 2021.
[38] V. Keswani, M. Lease, and K. Kenthapadi. Designing closed human-in-the-loop deferral pipelines, 2022.
12

---

[39] M. P. Kim and J. C. Perdomo. Making decisions under outcome performativity. ArXiv, abs/2210.01745, 2022.
[40] M. Klaes and E.-M. Sent. A conceptual history of the emergence of bounded rationality. Hist. Polit. Econ., 37(1):27-59, Mar. 2005.
[41] Kleinberg, H. Lakkaraju, Leskovec, J. Ludwig, and S. Mullainathan. Human decisions and machine predictions. February 2017.
[42] J. Kleinberg, J. Ludwig, S. Mullainathan, and Z. Obermeyer. Prediction policy problems. American Economic Review, 105(5):991-95, May 2015.
[43] J. Kleinberg and M. Raghavan. Algorithmic monoculture and social welfare. Proceedings of the National Academy of Sciences, 18(22))c018344118, 2021.
[44] N. R. Kuncel, D. M. Klieger, B. S. Connelly, and D. S. Ones. Mechanical versus clinical data combination in selection and admissions decisions: meta-analysis. Appl Psychol, 9866):1000-107, Nov 2013.
[45] H. Lakkaraju. J. Kleinberg, J. Leskovec, J. Ludwig, and S. Mullainathan. The selective labels problem: Evaluating algorithmic predictions the presence of unobservables. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 117, page 275-284, New York, NY, USA, 2017. Association for Computing Machinery.
[46] S. Lebovitz, H. Lifshitz Assaf, and N. Levina. To engage or not to engage with ai for crit- ical judgments: How professionals deal with opacity when using ai for medical diagnosis. Organization Science, 33, 01 2022.
[47] D. Leitão, P. Saleiro, M. A. T. Figueiredo, and P. Bizarro. Human ai collaboration in decision- making: Beyond learning defer. ArXiv, abs/2206. 13202, 2022.
[48] L. Lin and T. Zmic. Plug-in performative optimization. ArXiv, abs/2305. 187288, 2023.
[49] D. Madras, T. Pitassi, and R. S. Zemel. Predict responsibly: Improving fairness and accuracy by learning to defer. Advances in Neural Information Processing Systems 31, pages 6150-6160, 2018.
[50] C. Mendler-Dünneet F. Ding, and Y. Wang. Anticipating performativity by predicting from predictions. In Neural Information Processing Systems, 2022.
[51] C. Mendler-Dünnee J. C. Perdomo, T. Zrnic, and M. Hardt. Stochastic optimization for performative prediction. ArXiv, abs/2006.06887, 2020.
[52] H. Mozannar and D. A. Sontag. Consistent estimators for learning to defer to an expert. In International Conference Machine Learning. 2020.
[53] S. Mullainathan and Z. Obermeyer. Diagnosing physician error: A machine learning approach to low-value health care. Technical report, National Bureau of Economic Research, Cambridge, MA, Aug. 2019.
[54] C. Oesterheld, Treutlein, E. Cooper, and R. Hudson. Incentivizing honest performative predictions with proper scoring rules. ArXiv, abs/2305.17601, 2023.
[55] N. Okati, De, and M. Gomez-Rodriguez. Differentiable learning under triage, 2021.
[56] A. Pan, F. Jones, M. Jagadeesan, and J. Steinhardt. Feedback loops with language models drive in-context reward hacking. ArXiv, abs/2402.06627, 2024.
[57] C. Perdomo, T. Zinic, C. Mendler-Dünner, and M. Hardt. Performative prediction. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume abs/2002.06673,, 2020.
[58] M. Raghu, K. Blumer, G. Corrado, J. Kleinberg, 7. Obermeyer, and S. Mullainathan. The algorithmic automation problem: Prediction, triage, and human effort, 2019.
13

---

[59] P. Rajpurkar, A. Joshi, A. Pareek, A. Y. Ng, and M. P. Lungren. Chextemal: Generalization of deep learning models for chest x-ray interpretation to photos of chest x-rays and external clinical settings. 2021.
[60] A. Rambachan. Identifying prediction mistakes in observational data. October 2022.
[61] C. Rastogi, L. Leqi, K. Holstein, and H. Heidari. A taxonomy of human and ml strengths in Dacision-making to investigate human-ml complementarity. 2022.
[62] M. Saveski, F. Awad, I. Rahwan, and M. Cebrian. Algorithmic and human prediction of success human collaboration from visual features. Scientific Reports, 11:2756, 2021.
[63] H. A. Simon. Models of Man: Social and Rational. Wiley, 1957.
[64] M. Steyvers, H. Tejeda, G. Kerrigan, and Smyth. Bayesian modeling of human-Al comple- mentarity. Proc. Natl. Acad. Sci. U. S. A., 119(1))e2111447) Mar. 2022.
[65] C. Toups, R. Bommasani, K. A. Creel, S. H. Bana, D. Jurafsky, and P. Liang. Ecosystem-level analysis of deployed machine learning reveals homogeneous outcomes. In Advances Neural Information Processing Systems 37, 2023.
[66] A. Tversky and D. Kahneman. Judgment under uncertainty: Heuristics and biases. Science, 18144155):1124-1111,, 1974.
[67] W. van Amsterdam, N. van Geloven, J. H. Krijthe, R. Ranganath, and G. Cin'a. When accurate prediction models yield harmful self self-fuliiliig prophecies. ArXiv, abs/2312.01214 2023.
[68] M. Wainwright. Hiigh-imensional statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, England, Feb. 2019.
[69] B. Wilder, E. Horvitz, and E. Kamar. Learning to complement humans, 2020.
[70] Z. Zhao, A. Rodríguez, and B. A. Prakash. Performative time-series forecasting. ArXiv, abs/2310.06077, 2023.
14

---

A Additional technical results
In this section we present additional technical results which complement those in the main text. All proofs are deferred to Appendix C.
A.1 nonlinear analog of Theorem 4.1
Below provide simple extension of Theorem 4.1 from univariate linear regression to arbitrary univariate predictors of Y given Y
Corollary A.1. Let S an o-indistinguishable subset with respect to a model class F and target Y. Let g [0, 1] > [0, 1] be function which satisfies the following approximate Bayes-optimality condition for q 0:
Ry - g(()) EEs(Y E VT) + +.
(8)
Then, for any f E F,
Es (V-)(})))) + 4Covs(Y, 8)3 Es (Y x(x))² + 2a + 17.
That is, any function g which is nearly as accurate (in terms of squared error) as the univariate conditional expectation function Es[Y Y] provides the same guarantee as in Theorem 4.1. This conditional expectation function is exactly what e.g., logistic regression of Y on Y seeks to model. We provide proof in Appendix C.
A.2 finite sample analog of Corollary 4.2
For simplicity, the technical results in Section 4 presented in terms of population quantities. In this section we consider the empirical analogue of Corollary 4.2, and provide a generalization argument which relates these empirical quantities the corresponding population results in Section 4. We focus our attention on Corollary 4.2, as the proof follows similarly for Theorem 4.1 and Corollary A.I.
Let be some class of predictors mapping H to [0, 1]. We'll begin with the setup of Corollary 4.2, with C X' denoting fixed, mcasurable subset of the input space (we'll generalize to a full partition S below). Further let ng >>= [(x; S) denote the number of training examples which lie in the subset S S X, and {yr, h denote i.i.d. samples from the unknown joint distribution over the random variables (Y. H) conditional on the event that X E S. Let ngs
Ôs = arg min JEG ng (14 gh+)))² denote the empirical risk minimizer within S. Our goal will be to show that there exists some i E 9 satisfying (4), then the empirical risk minimizer ğs also approximately satisfies (4) with high probability.
Lemma A.2. Let L (eg 9 E 9), where (g(x.y) (y-
denote the class of squared loss functions indexed by g G, and let Rug (L) denote the Rademacher complexity of L. Let P(S) IPXX E S) denote the measure of S. Then, for any 8 Z O, with probability at least nPis
g(x))) (y-g(z)))
(1
((1 22 2e-ee-PP PP())), we have
Es(Cg] S - + 4Rng (C) + 28, and ns 2 nP(S)/2.
(10)
That is, if there exists some g" E G satisfying (4), then the empirical risk minimizer I E G within the subset S also satisfies (4) with high probability, up to an approximation error that depends on Rademacher complexity of L. For many natural classes of functions, including linear functions, the Rademacher complexity (1) tends as - oo and (2) can be sharply bounded in finite samples (see e.g., Chapter 4 in [68]), We provide proof of Lemma A.2 in Appendix C.
15

---

Extending Lemma A.2 to a partition of X. The result above is stated for a single subset S, and depends critically on the measure that subset P(S) P(X E S). We now show this generalization argument can be extended to partition of the input space S ... .x S X' by arguing that Lemma A.2 applies to "most" instances sampled from the marginal distribution over X. Specifically, we show that the probability that X lies in any subset S with measure P(S) approaching 0 is low probability event; for the remaining inputs, Lemma A.2 applies.
Corollary A.3. Let {Sk kEjK] be a (not necessarily multicalibrated) partition of the input space, chosen independently of the training data, and let ny denote the number of training observations 0 and ò 2 0, X lies in a subset Sy S X such
which lie in a given subset Ske S X. Then, for any any that,
ExlCa] S. Exllo-] + 4R (C) +
(11)
with probability at least (1 - (1 - e - )1 2e *) over the distribution of the training data {ri, Vi, Us Y and test observation (In++1 +aa+1,yn++10 +n+ Un+1,,n+1}> Dn+1).
The preceding corollary indicates that Lemma A.2 also holds for a "typical" subset of the input space, replacing the dependence on the measure of any given subset P(S) with lower bound on the probability that test observation Tn+1 lies in some subset whose measure is least द. We provide a formal proof in Appendix C.
A.3 The impossibility of arbitrary deferral policies
In this section we formalize the argument in Section 6 to show that it is infeasible to learn predictors which are simultaneously "optimal" (in a sense we make precise below) for many downstream users who independently choose when to comply with the algorithm's 's recommendations. We provide proof in Appendix C.
Lemma A.4. Let F be some class of predictors which map countable input space X' to [0, 1]. We interpret a compliance policy x X > [0, 1] such that π T(x) = 1 indicates that the user complies with the algorithm's 's recommendation at X = For all E F, unless f E X] almost everywhere, then there exists a deferral policy π X- + {0, 1} and constant E
[0, 1] such that:
IB[(Y - ((X))² π (X)= = 1] RI(Y - c)²
n (X) =1
(12)
Lemma A.4 indicates that for any predictor ʃ which is not the Bayes optimal predictor, there exists a compliance policy which causes underperform a constant prediction on the instances for which it is ultimately responsible. Because learning the Bayes optimal predictor from a finite sample of data is generally infeasible, this indicates that a predictor cannot reasonably be made robust to an arbitrary deferral policy. The proof, which we provide below, is intuitive: the decision maker can simply choose to comply on exactly those instances where performs poorly.
B Learning multicalibrated partitions
In this section we discuss two sets of conditions on F which enable the efficient computation of multicalibrated partitions. An immediate implication of our first result is that any class of Lipschitz predictors induce a multicalibrated partition.
Level sets of F are multicalibrated. Observe that one way in which Definition 3.1 is trivially satisfied (with a = 0) is whenever every F is constant within a subset S C X. We relax this insight as follows: if the variance of every f E F is bounded within S, then S is approximately indistinguishable with respect to F.
Lemma B.1 Let F be a class of predictors and S C X be a subset of the input space. If:
max Var(f(X] X E S) S 4a²
(13)
FEF
then S is a-indistinguishable with respect F and Y.
16

---

This result yields natural corollary: the approximate level sets of F (i.e., sets in which the range of every f E F is bounded) are approximately indistinguishable. We state this result formally as Corollary B.2 below. We use exactly this approach to finding multicalibrated partitions in our study of a chest X-ray classification task in Section 5.
Corollary B.2. Let F. be class of predictors whose range is bounded within some S C X. That is, for all E F:
max #ES
f(x) min f(x') I 4a z'E8
(14)
Then S is a-indistinguishabbl with respect to F.
Lemma B.1 also implics simple algorithm for finding multicalibrated partitions when F Lipschitz with respect to some distance metric x X - R: observations which are close under d(.,-) are guaranteed to be approximately indistinguishable with respect to F. We state this result formally as Corollary B.3 below.
Corollary B.3. Let Frip(L,d) be the set of LuLipschiir,functions with respect to some distance metric d(.,)) on X. That is:
- f(x') Ld(x, x') f FLip(L.))
(15)
Let (SkTkek for K S N be some L)-net on X with respect to d(.,)). Then {Skheek is a-muliicalibrated with respect to Flip(L,)).
Proofs of the results above are provided in Appendix C.
Multicalibration via boosting, Recent work by [27] demonstrates that multicalibration is closely related to boosting over a function class F. In this section we first provide conditions, adapted from [27]. which imply that the level sets of a certain predictor h : X [0. are multicalibrated with respect to F; that is, the set {x h(x))= indistinguishable. We then discuss how these conditions yield a natural boosting algorithm for learning a predictor h which induces a multicalibrated partition. In the lemma below, we use R(f denote the range of a function f.
f} for every v in the range of is approximately
Lemma B.4. Let F be a function class which is closed under affine transformations; i.e., f E
a + bf E F for all a, b E R, and let F = {f E FF R(f)) S [0, 1]}. Let Y E [0. 1] be the target outcome, and h X [0, be some predictor with countable range R(h) C [0, 1]. If. for all
FEF E R(h):
E [(h(X) - - Y) ((X) = < a²,
(16)
then the level sets of h are (2a)-mullicallibrate with respect to FE and Y.
To interpret this result, observe that (16) is the difference between the mean squared error of f and the mean squared error of h within each level set S, = {o X' h(z) v). Thus, if the best E F fails to significantly improve on the squared error of h within a given level set S., then S, is indistinguishable with respect to F (which is merely F restricted to functions that lie in [o, 1)). [27] give boosting algorithm which, given a squared error regression oracle for F, outputs a predictor which satisfies (16). We make use of this algorithm in Section 5 to learn a partition of the input space in visual prediction task. Although the class we consider there (the class of shallow regression trees FRI5) is not closed under affine transformations, boosting over this class captures the spirit of our main result: while no f E J.RT can improve accuracy within the level sets of h, humans provide additional predictive signal within three of them.
Taken together, the results in this section demonstrate that multicalibrated partitions can be efficiently computed for many natural classes of functions, which in turn enables the application of results in Section 4.
'Informally, a squared error regression oracle for F an algorithm which can efficiently output arg min [Y - [x)]] for any distribution over X, Y. When the distribution is over a finite set of training data, this is equivalent to empirical risk minimization. We refer to [27] for additional details, including generalization arguments.
17

---

C Proofs of primary results
In this section we present proofs of main results. Proofs of auxiliary lemmas are deferred to Appendix E.
C.1 Omitted proofs from Section
Lemma C.1. The following simple lemma will be useful in our subsequent proofs. Let X {0,1) be a binary random variable. Then for any other random variable, Y:
Cov(X,
(17)
PP = 1) X = B[y]) P( 0) E| X 0))
(18)
(19)
This is exactly corollary 5.1 in [28]. We provide the proof in Appendix E.
Proof of Theorem 4.1
Proof. A well known fact about univariate linear regression is that the coefficient of determination (or 2² is equal the square of the Pearson correlation coefficient between the regressor and the outcome (or r). In our context, this means that within any indistinguishable subset S₃. we have:
835) 27 (Y
E&
(Y-
7k
COva (Y, (Y, 8)2
(20)
Es
Ex 1x
(Y) (Y)Var
+ E&
[V
E& [M1}]]
E&
(ī- -1388) 21
Covi 8)2
(21)
Var(F)
(y (y- - -838)
= Es [or- (V<((()))))
Cove(Y,
R&
(22)
Var(P)
S Ex (Y - (-EE((()))
-4, 8712
(23)
Where (23) is an application Popoviciu's inequality for variances, and makes use of the fact that Ý E [0. 1] almost surely. We can then obtain the final result by applying the following lemma, which extends the main result in [28]. We provide proof in Appendix E, but for now simply state the result as Lemma C.2 below.
Lemma C.2. Let {S* be an a-multicalibrated partition with respect to real-valued function
class F (f X' > [0, 1]} and target outcome E [0, 1}. For all f E F and k E [K], it follows that:
E& (VV-R(y))? E [ Y ((X)) + 2o
(24)
We provide further discussion of the relationship between Lemma C.2 and the main result of [28] in Appendix D below.
Chaining inequalities (24) and (23) yields the final result:
Eg
Y - (Y-23
73 - ;,88
< Ex ( -(x))) + 2a (CO VEEF
(25)
(y- - 8388) 27
(Y) = Ex (V--f(X))) + +2a VFEF
(26)
18

---

Proof of Corollary 4.2
Proof. The proof is almost immediate. Let 8 R be the population regression coefficients obtained by regressing Y on g(f) within S (as in Theorem 4.1; the only difference is that we consider a single indistinguishable subset rather than a multicalibrated partition). This further implies, by the approximate calibration condition (4):
Es
|(Y - g(H))) S Es [Y - (1 + +1
(27)
The proof then follows from that of Theorem 4.1, replacing Y with g
Proof of Theorem 4.3
Proof. Fix any & E [K].
(ovx(Y,
(28)
[x Y (x(( (B& (x()),, [ (x))))
(29)
(OVy (E)), FA(OIDI
(30)
V Var(EalY (x))) (E( fx()))
(31)
- 2 (ar (x)))
(32)
Where (29) is the law total covariance, (30) follows from the assumption that Ý f (X), X E Sa. (31) is the Cauchy-Schward inequality and (32) applies Popoviciu's inequality to bound the variance of E[Ý fxx) (which is assumed to lie in [0, 1] almost surely).
We now focus on bounding Vara (Ex[Y [x))).. Recall that by assumption, |Cov& {x()) S a, so we should expect that conditioning on fi(XX) does not change the expectation of Y by too much.
Vara (FxlV fa(X)))
(33)
= =BA[(TA Y [x() EA (X))))
(34)
= -Y fx)) - E&[T])
(35)
=Pa(fa(X) 1)(B) 1x(X) -1] Bx17)
+ +Pa(fx(X) = O) [xx(X) = 0] E& (
(36)
(x(fx(X) = 1) | Y (x) = -1j-Es
+ (X)(f = 0) [Ex (Y [x(() = o] E& Y
(37)
Where the last step follows because Y is assumed to be bounded in [0. almost surely. Applying Lemma C. to (37) yields:
Varg (E& (x)) < (Y, < 2a
(38)
Where the second inequality follows because our analysis is conditional on X E Sş for some a-indistinguishable subset Sg. Plugging (38) into (32) completes the proof.
19

---

C.2 Omitted proofs from Section 6
Proof of Lemma A.4
Proof. Let f E F be any model and let S S X' be subset such that (x))) > 0 (2) the Bayes optimal predictor E| X] is constant within S and (3) f(X) + E|Y X =x=a x] for all a E Such subset must exist by assumption. It follows immediately that choosing
1 if x S otherwise
T T(x)
suffices to ensure that f(X) underperforms the constant prediction cs EY X E S] on the subset which ı delegates to This implies that even if F includes the class of constant predictors [f(X) = c E R] perhaps the simplest possible class of predictors then we cannot hope to find some f which is simultaneously optimal for any choice of deferral policy.
Proof of Theorem 6.1
Proof. We start with the assumption that {Sk] is a-multicalibrated with respect to II and the product class (f(X)((X) f E F, n 11}. That is, both of the following hold:
[Cov,(Y, Sa II, e [K] [Cov)((,f(X)xx()) a F [K]
(39)
(40)
First, we'll show that this implies that the covariance of Y and f(X) is bounded even conditional on compliance. To streamline presentation state this separate lemma; the proof is provided further below.
Lemma C.3. Given the setup of Theorem 6.1, the following holds for all k [K], F and II:
20
[Cov (Y, ((X) 1)1
(41)
Pa(T(X)=1) =1
We provide a proof in Appendix E. By Lemma C.2, Lemma C.3 implies, for all k E [K], E F and TT:
Ex (Y - (X)) = 11)² x(X) =
s Ex ( f(x))² x(X) =
4a
(42)
(( 1)
This is close to what we want to prove, except that the prediction Ex[Y (XX) 1 depends on the choice of the policy x.)). We' ll argue that by (39), Ex T(X) = 1] 2J E. YY) Indeed, because ((.) is binary, we can apply Lemma C.I to recover:
[Cov(T(X), Px(a(XX) = 1) B x(X) 1] E [Y]
(43)
|E (XX) - [Y]] Pa(a(X)=
(44)
We rewrite the LHS of (42) to make use of this identity as follows:
Eạ (Y EE,(Y T(X)= 1])² (X) =
(45)
= Ex ((Y [x]) + (E& E I =1))² ( =
(46)
20

---

Ex -x + (Ba[y] B T (X) 1])2
+ + EA (Bx E x(X)= 11)) [x() =
(47)
2 Eb [[(X - Ex(r1)² + 2(Y (x E& T = 11)) x(x) = 1]
(48)
= Ex [X - -Ex(x))² =(X) = 1]
+ + - Ex|Y xxx) = 1)) (B&lY T(X) = Ex(r])
(49)
2a
2 E& Ex(T) =(X)
(50)
(x(x(X)= =)
Where the last step follows by observing that either (1) [Y = Ex =(x== or (2) exactly =
one of (E, - E π (XX) 1]) or (E+lY xx - is strictly positive. Assume
that E2 | + E ((X) = 1); otherwise the bound follows trivially. We bound the positive term by recalling that Y lies in [0, 1]. and we bound the negative term by applying (44). Thus, the product
of these two terms is at least -0
Finally, combining (50) with (42) completes the proof.
(=(x(X)=1)
C.3 Omitted proofs from Appendix A
Proof of Corollary A.1
Proof. Observe that, because the conditional expectation function E& [Y| y minimizes squared error with respect to all univariate functions of Y, we must have:
Es (V ESSY
| < Es -- -
(51)
Where 7/' E R. 8 R are the population regression coefficients obtained by regression on g(H) as in Theorem 4.1. This further implies, by the approximate Bayes-optimality condition (8):
Es [Y g(>))}|
s Es (
vē -
-; +
(52)
The proof then follows immediately from that of Theorem 4.1.
Proof of Lemma A.2
We will adopt the notation from the setup of Corollary 4.2. Further let be some class of predictors mapping H to [0. 1], over which we seek to learn the arean-squared--ee -eroo minimizing Is E & within some subset
Proof.
X.
Let ns = Σi (xx E S) denote the number of training examples which lie in the subset S, and 1
let Es|4,] my E'a (Y: 9(X,))² denote the empirical loss incurred by some within S. Finally, let [s([g] = E[(Y s(X))² X S] denote the population analogue of Bs({g)-
By Hoeffding's inequality we have:
P ns nP(()
2 21-2--P (1-2e-P(S)))
(53)
that is, ns at least half its expectation with high probability. Let = flg E 9), where (, v) = - 2==)) the class of squared loss functions indexed by g E G. Let Rng (C) denote the Rademacher complexity of L, which is defined as follows:
21

---

Definition C.4. Rademacher Complexity
For fixed N, let c1..f.. En denote i.i.d. Rademacher random variables (recall that Rademacher random variables take values and - with equal probability 2). Let 7.... Zn denote i.i.d. random variables taking values in some abstract domain 2, and let T be class of real-valued functions the domain Z. The Rademacher complexity of T denoted by (T) and is defined as follows:
R. (7) =
sup IET
Σ 71
(54)
Where the expectation is taken over both c1... Cn and Z1... Zn- Intuitively, the Rademacher complexity is the expected maximum correlation between some t e T and the noise vector Cn.
We now make of standard uniform convergence result, which is stated in terms of the Rademacher complexity of function class. We reproduce this theorem (lightly adapted to our notation) from the texthook treatment provided in [68] below:
Theorem C.5. (adapted from [68]) For any b-uniformly-boutte bounded class of functions T, any positive integer n 2 1 and any scalar ó 0, have:
n Σ i=1
sup EET
t(2,) B[((Z))] $ (T) +
(55)
with probability at least 1 - exp
n
26
Applying Theorem C.5 (noting that C is uniformly bounded in [0, 1J) implies:
sup Esle Eslco] s 2nng (C) +
(56)
with probability at least 1 - no
Finally, combining (53) with (56) further implies, for any 2 0,
Es[4]] s Es(Lg-1 4Rng (C) 28
(57)
with probability at least (1
(1 1ee-2e-P(s- PP()m))m desired.
Proof of Corollary A.3
Proof. We'll adopt the notation from the setup of Lemma A.2 and Corollary A.3. Observe that, if
we were to take the union of every element of the partition (5& kEE with measure P(S) = P(X Sc)) Σ K. the result would be a subset of the input space with measure at most K к c. Note that this is merely an analytical device; we need not identify which subsets these are.
Thus, with probability at least (1 - E). newly sampled test observation will lie in some element of the partition {Sk] with measure least &. Conditional this event, can directly apply the result of Lemma A.2, plugging in lower bound of & for P(S). This yields, for any 0 and 5 2 0, X lies subset Sp C X' such that,
Ex[Ca] S Ex + 4Rm (C) 28
(58)
with probability at least (1 - e) - e
m6d?
3R
)(1 2c K over the distribution of the training data
(oe, Wis ds 1 and a test observation (z--11 Un++ Hn+1) 1), as desired.
22

---

C.4 Omitted proofs from Appendix B
Proof of Lemma B.1
Proof. We want to show [Cov(Y, f(X) | X E S)l S for all f F and some S such that
maxfeF Var(f(X) X E S) S 4a².
Fix any f E F.F. We then have:
(ov((Y x E S)
(59)
Var(Y X (f) E S)
(60)
4 Var(f(X) X E
(61)
V 4
4a²
(62)
a
(63)
Where (60) the Cauchy-Schwarz inequality, (61) is Popoviciu's inequality and makes of the fact that Y is bounded in [0, 1] by assumption, and (62) uses the assumption that jax Var( X E S) < 4a².
Proof of Corollary B.2
Proof. We want to show that f E F:
(Cov(Y, X E S) a
(64)
By assumption, f(X) is bounded in range of 4a within S. From this it follows by Popoviciu's inequality for variances that v f F:
Var(s(X) X ( 5 (4a)² 4a²
(65)
The proof then follows from Lemma B.1.
Proof of Corollary B.3
Proof. We want to show that Flip(L,d), K:
[Y, S
(66)
Because S& part of 4a/ Lnnet, there exists some m E [0. such that (f(()) E [m, m + 4a] X S,) 1; that is, f(X) is bounded almost surely in some interval of length 4a. From this it follows by Popoviciu's inequality for variances that V f E FLip(L.d), k K:
Varx(f(X)) < (4a)
4a²
(67)
4
The remainder of the proof follows from Lemma B.1.
23

---

Proof of Lemma B.4
Proof. The result follows Lemma 3.3 and Lemma 6.8 in [27]. We provide simplified proof below, adapted to our notation. We'll use E. to denote the expectation conditional on the event that (h(X) of for each v R(h). We use Cov,(..)) analogously.
Our proof will proceed in two steps. First we'll Il show that:
- YY² Ve E R(h), / E F (()))
(X(X) -Y
(68)
-X) <a R(h),f
(69)
This condition states that if there does not exist some in the range of h where the best f E FF improves on the squared eπror incurred by h by more than a², then the predictor h(-) a- multicalibrated in the sense of [27] with respect to the constrained class F. We then show that the level sets of predictor (t--) which satisfies (69) form a multicalibrated partition (Definition 3.2). That is:
B. ((()(( v)] s vo E R(h), = Cov. (ox) S 2a Ve E R( (70)
That is, the level sets S. = { k(x) = v form a (2ci)-multicalibrated partition with respect to F. First, we'll prove the contrapositive of (69). This proof is adapted from that of Lemma 3.3 in [27]. Suppose there exists some U E R(h and f E F such that
E.If(X((Y v)] 2
(71)
Then there exists f' E F such that:
Ex((f((x) r)2 (h(x)-1) a²
(72)
Proof: let 17 B.IÍ(xI and f = + E.I = + nf(X). Then:
E, [(((X) - y)² - (('()- - r
(73)
E, [(v Y)² - (XX) - 2
(74)
= E. [2² 2 2Yu - 1² -1 (xx) Y -2mnf(X) 2uY + 2xf(X
(75)
E. [2n((X) (Y -) {(x))
(76)
a²
E. (xn (Y w) [x)
(77)
a²
2 2ma Ex(f(X)
(78)
a²
(79)
(80)
Where the last step follows because we took f F. the subset of the function class J which only
takes values in [0, 1]. This implies that if instead E., [()(( y)² (h(X) Y) < a² for all
E R(h), f' E F, then E. [f v)] < for all v E R(h) and f f F. Next we prove (70); that is, (X)
- =)] < a for all E R(h) and f E F implies (Cove(((X), Y) < 2a for all E R(f),, F.
24

---

The proof is adapted from that of Lemma 6.8 in [27]; our proof differs beginning at (88). Fix some
f E F and v E R(hh.. By assumption we have, for all v E R(h and f E F,
Ex(s(X)(Y v)]
(81)
Then we show:
X)
(82)
(83)
(._xX)))__..((X)]] (E) uB.
(84)
(xlf(X)(Y - (=
(85)
S
- -B]]=
(86)
(87)
S + (E.
(88)
Where the last step follows from the assumption (81). Now, let f'(X) = [x() be the constant function which takes the value E. [x() We can write (88) as follows:
a + (+ - a ((() w)
(89)
a + (X) u)ll
(90)
Because F is closed under affine transformations, it contains all constant functions, and thus, f(() E F. F, by definition, is the subset of F whose range lics in [0, Because f E it must be that [x() E [o, 1] and thus, f E F. So, we can again invoke (81) to show:
+ Ex)((X)) -v)] S 2a
(91)
Which completes the proof.
D Relating Lemma C.2 to Omnipredictors [28]
In this section compare Lemma C.2 to the main result of [28]. While the main result of [28] applies broadly to convex, Lipschitz loss functions, we focus on the special case of minimizing squared error. In this under somewhat weaker and more natural conditions. We proceed in three steps: first, to provide self-contained exposition,
show that Lemma C.2 extends the main result of [28] to cover real-valued outcomes
state the result of [28] for real-valued outcomes in the special of squared error (Lemma D.1 and Lemma D.2 below). Second, we derive a matching bound using Lemma C.2 (our result), which do by demonstrating that the conditions of Lemma D.2 imply the conditions of Lemma C.2. Finally, we show that Lemma C.2 applies in more generality than Lemma D.2, under conditions which match those of Definition 3.2.
We first state the main result of [28] (adapted to our notation) below, which holds for binary outcomes
Y E {0, 1).9
Lemma D.1 (Omnipredictors for binary outcomes, specialized to squared error ([28), Theorem 6.3)). Let S be subset which is a-iiddstinguiisable with respect to real-valued function class F and hinary target outcome Y E (0, Then, for all F.F
Es (Y- E|-)))))]] < Es (X-)(x))) 44
(92)
"As discussed in Section 1, we also continue to elide the distinction between the 'approximate" multicali- bration of [28] and our focus on individual indistinguishable subsets. The results in this section can again be interpreted as holding for the 'typical' element of an approximately multicalibrated partition.
25

---

This result makes use of the fact that for any fixed y E [0. 1], the squared error function is 2-Lipschitz with respect f(z) over the interval [0, This is similar Lemma C.2, but requires that Y is binary-valued. In contrast, Lemma C.2 allows for real-valued Y [0, 1]. and gains factor of 2 on the RHS. [28] provide an alternate extension of Lemma D.1 to bounded, real-valued Y, which we present below for comparison to Lemma C.2.
Extending Lemma D.I to real-valued Y. Fix some e and let B(e) 10.., L3J). Let Y be random variable which represents a discretization of Y into bins of size द- That is, Y mi)se |
be 2 Let R(Y) denote the range of Y. Observe that the following holds for any
function g X + [0, 1]:
B(O o(x)) -(((E 9(x)) sc
(93)
Where (93) follows because the function (y - g2=)) is 2-Lipschitz with respect g(x) over [0. 1] for y E [0, 1]. We now work with the discretization of Y, and provide an analogue to Lemma D.1 under a modified indistinguishabiiiyy condition for discrete-valued Y, which we'll show is stronger than Definition 3.1.
Lemma D.2 (Extending Lemma D.1 to real-valued Y ((28), adapted from Theorem 8.1)). Let R()) denote the range of a function f, and let 1()) denote the indicator function. Let S be a subset of the imput spuce X which satisfies the following condition with respect to function class F and
discretized target Y:
For all f E F and ÿ E R(Y), if:
()) S
(94)
Then:
Es (P-Essh -s- Es (x-)(x)) +2
2 2
(95)
To interpret this result, observe that (95) yields bound which is similar to Lemma D.1 under modified 'pointwise" indistinguishability condition (94) for any discretization Y of Y. Combining (95) with (93) further implies:
Es [Y- -yy-Ey -M-1s
< Es ( ((x))²
+2
2
2e
(96)
Deriving Lemma D.2 using Lemma C.2
We show next that the 'pointwise' condition (94) for a 2 implies our standard indistinguishabilit condition (Definition 3.1) for a' = = a. This will allow us to apply Lemma C.2 to obtain a bound which is identical to (96). Thus, we show that Lemma C.2 is at least as general as Lemma D.2.
Lemma D.3. Let S be subset satisfying (94). Then, for all f E F,
2
(Y
(97)
We provide a proof in Appendix E. Thus, combining assumption (94) with Lemma C.2 and (93) recovers result which is identical to Lemma D.2. That is, for all f E F:
Note that Lemma C.2 also requires that each f E F takes values in [0, 1]. but this is without loss of generality when the outcome is bounded in [0, 1]: projecting each f E F onto [0, 1] can only reduce squared emror.
26

---

(1)s(1((=0),
(98)
(Covs(Y.f(X) _ a
(99)
(8-Es((T)
21 /
< Es (8 - ((x)
/
2
Es
+
(100)
+ Es (x- -I-))
}
< Ess [X - f(x))²
+
2
a
2e
(101)
Where (99) follows from Lemma D.3, (100) follows from Lemma C.2 and (101) follows from (93).
Extending Lemma C.2 beyond Lemma D.2
Finally, to show that Lemma C.2 extends Lemma D.2, suffices to provide a distribution over f(X) for some ʃ E F and discrete-valued y taking 2 1 values such that Definition 3. satisfied at level a 0, but (94) is not satisfied at a' (a/l) (though in fact that taking a' also suffices for the following counterexample).
Consider the joint distribution in which the events (Y' 0, f(x) 03, (Ý = f. = } and {Ý = / f(x) =1 occur with equal probability conditional on {X E 5) for some 5 C A'. We suppress the conditioning event {XX S} for clarity. Then:
Cov(1 = P 1) (EIS(X) y =0 -)][((( 6
(102)
On the other hand we have:
Cov(Ý, ((x)) -
(103)
= -
(104)
3
1
x
x
x
x
(105)
3
2
3
3
12
That is, we have [ov((ý, (Co((),(X)) ((X)) = 1 < (o)
= Thus, Lemma C.2 establishes result which is similar to (D.2) for real-valued under the weaker and more natural condition that [Cov(Y, f(X)) is bounded, which remains well-defined for real-valued Y, rather than requiring the stronger pointwise bound (94) for some discretization Y.
12
Finally, we briefly compare Lemma C.2 to Theorem 8.3 in [28], which generalizes Lemma D.2 hold for linear combinations of the functions ʃ E F and to further quantify the gap between the "canonical predictor' E& [Y] and any f E (or linear combinations thereof). These extensions are beyond the scope of our work, but we briefly remark that the apparently sharper bound of Theorem 8.3 is due to an incorrect assumption that the squared loss - g(x))² is 1-Lipschitz with respect to g(x) over the interval [0, 1], for any y E [0. 1]. Correcting this to Lipschitz constant of 2 recovers the same bound as (101).
E Proofs of auxiliary lemmas
Proof of Lemma C.1
Proof. We'll first prove (18).
Cov(X, Y = X| [
(106)
EE XY X]| E
(107)
27

---

P(X = 1) X = 1] + X)E X - 0] E
(108)
P(X 1)E|Y X ==1 1] E[
(109)
PP(X = 1)E(Y X = IP(X- = 1)
-1|-IP(A
(110)
P(X 1) (ElY |X x=1I-[(>]
(111)
As desired. To prove (19), let x'= X. Applying the prior result yields:
Cov(X', 1) X' E
(112)
Because x'=
=1=16 + X = 0, it follows that:
Cov(X', = P(X = 0) X = 0] - -E()
(113)
Finally, because covariance is a bilinear function, Cov(X', Y) = Cov(1 X,Y) = Cov (X,v Y)
Chaining this identity with (113) yields the result.
Proof of Lemma C.2
The result want to prove specializes Theorem 6.3 in [28] the of squared error, but result allows Y [0, 1] rather than Y E {0, The first few steps of our proof thus follow that of Theorem 6.3 in [28]; our proof diverges starting (118). We provide detailed comparison of these two results in Appendix D above.
Proof. Fix any [K]. We want to prove the following bound:
EE((Y - [Y]) E. Ex f(x))? + 4a
(114)
It suffices to show instead that:
E& [ R&(s(x)) E.((Y f(x)) 4a
(115)
From this the result follows, [x(((- [ S E& c) for any constant To simplify notation, we drop the subscript k and instead let the conditioning event {X E Sk} be implicit throughout. We first show:
B[(Y - ((x)) = (xx))
[x]] 2 E [Y E[f(X) YDJ
(116)
Where the second inequality is an application of Jensen's inequality (the squared loss is convex in f(X)). From this it follows that:
[( - - - (Y
(117)
I E -V (I(()) 2
-
(118)
=E [YEE)) -BX(X) Y 2Y Y]]
(119)
-1E/EE//))111--/////))D--E11111 |Y}
(120)
(121)
= = -
|Y]] + +
(122)
2Cov((, - Var(E(((X)) Y))
(123)
< 2a
(124)
28

---

Where each step until (124) follows by simply grouping terms and applying linearity of expectation. (124) follows by the multicalibration condition and the fact that the variance of any random variable is nonnegative.
Proof of Lemma C.3
Proof. For any a E II, f & F,,, assumption (40) gives us [Cov(Y.[(Xxx(())) S a. We'll expand the LHS to show the result.
(125)
+o (,X)) +(XII
(126)
= (P)(=(() = ((x x(x)=1)
= (,0, x(X)
+ (EEx [xx)x)x,(/((((())))))) I
(127)
= [ - (Y, +(X) =
+ (Es (()),, E, (x())(((X)) +xX)I|
(128)
Where (126) is the application of the law of total covariance. Observe now that Cov, f(X)
(X) = =1 is exactly what we want to bound. To do so, we now focus on expanding Cov (Ex) [Y (X)). This is:
x (X)).. (x))
E, E (xx) [X)]] BA [(X))
BB [()]] (129)
=((m(X) 1)R (V ((x))=]]{[((())) m(X) = 1]
(xX 1])E<(((XX +(X) 1]
(130)
=P(T(()= [fX) (E) Y (xX) -1[[)
(131)
Because ((-) is binary valued function, we can apply Lemma C. to write
E& Y ((X) = 1| E Cova(Y,
((x(X)=1 1)
Plugging in this identity yields:
= = 1)ExII(EE)) (X)) = 1 / 1]]
(132)
E& [X) x(X) = 1CCr
(133)
Plugging (133) into (128) yields:
CCov (Y (1)(X)))=CCoaa
(134)
[P = 1)Covv (Y, +(X) = 1) Bx = [[Cov)(Y;
(135)
IP(T(X)= (Xx
+(X) = 1) (-ExIf(X) =(X) (Y,
(136)
[IP(T(X) (Y. =(X) 1 (Ex T(X) IY, (XX)]l
(137)
((T(X) 1)Cov (Y, +(X) = - -EXI((X) =(X) = 1|Cov (X)))
(138)
Where (137) the application of the reverse triangle inequality. Combining the initial assumption that S₁ is indistinguishable with respect to (f(X)((XX f F, E III (40) and (138) yields:
(T (X, mX)) 1)1
29

---

[xlf(X) ((X) =
(139)
Which further implies:
(+) 1) (X) 1)1 - [XX]((X) | TX))
( (X))) (140)
+ Balf(X) x(() = []|CCov (X))( (141)
/Cov (X))]
(142)
- 2a
(143)
Which finally implies (Y, f(X) T (X)
1)] P(x(())1)+ as desired. (141) and (142) follow
from the assumption that f(X) e-indistinguishable with respect to every 1I (39).
E [0. 1]. and (143) follows from the initial assumption that Sy. is
Proof of Lemma D.3
Proof. Recall that Y a discrete random variable taking values 0, c, 3e .... 1.11. We again use RYY) to denote the range of Y. Our analysis below proceeds conditional on the event {X E S}. which we suppress for clarity. We can show
Cov(Y, [BL EXT]
(144)
[(K) BU((X) SER())
Σ JP(Y= 17)
(145)
B(EEf((X) -[f(x)
Σ
OP(Y = 5)
(146)
$ER(P)
Σ (ER((
SP( = -)) y = = -EE((X)) Σ
TP(Ý = 5)
(147)
SER(V)
Σ
JP(Ý 5)) (8 - -E((()))
(148)
SER())
Σ JPPY 1) (BL(X)) (81())1811 18= -
(149)
(ER(()
Σ JER(L)
1 Cor(1(}- (.). ((x))
(150)
Σ ja
(151)
(YR(Y)
Σ
(152)
(YR(Y)
2
a
(153)
c
Where (149) makes use of the fact that 5 2 (150) makes use of the identity
Cov(i(Ý f), f(X)) P(Ý か) (EI((X) Øl E[f(x)) (this is straightforward analogue of Lemma C.1), (151) applies assumption (94), and (152) makes use of the fact that ğ < 1.
30

---

Finding multicalibrated partitions: chest X-ray diagnosis
In this section we provide additional details related to the chest X-ray diagnosis task studied in Section 5. As discussed in Section the relevant class F the set of 8 predictive models studied in [59] for diagnosing various pathologies using chest X-ray imaging data. A key insight for learning multicalibrated partition with respect this class is that, because the class of models is finite, we can apply Lemma B.1 to discover indistinguishable subsets without training new models or even accessing the training data. Instead. we can think of the relevant input space as {0. 13:: the 8-dimensional vector containing the classifications output by the 8 models in F for a given X-ray. Then, per Lemma Lemma C.3 and Corollary A.3, any subset of X-rays for which the Chebyshev distance (i.e., the maximum coordinatewise difference) in this 8-dimensional space is bounded must be approximately indistinguishable. Thus, to find approximately indistinguishable subsets, we simply apply an off-the-ste she- clustering algorithm to minimize the intracluster Chebyshev distance. Code and instructions replicate this procedure are available at https : // github. www.ecoooaaaaaeeee wttp://aarrreaaaaaaae repl.
G Additional experimental results: chest X-ray diagnosis
In this section we provide results which are analagous to those presented in Section 5 for the four additional pathologies studied in [59]. For each pathology we first present a figure comparing the accuracy of the benchmark radiologists to that of the eight leaderboard algorithms, in Figure for atelectasis. We then present a figure which plots the conditional performance of each radiologist within a pair of indistinguishable subsets, in Figure 3.
Results for diagnosing a pleural effusion are presented in Figure 5 and Figure 6. Results for diagnosing cardiomegaly are presented in Figure 7 and Figure 8. Results for diagnosing consolidation are presented Figure and Figure 10. Finally, results for diagnosing edema are presented in Figure 11 and Figure 12.
Correlation Coefficient
predictor
0.8
dmet
ihil
jfaboy
0.7
ngango2
ngango3
sensexdr
uestc
yww211
radiologist
radiologist
radiologist 3
0.5
algorithmic
radiologist
Prediction Type
Figure 5: The relative performance of radiologists and predictive algorithms for detecting a pleural effusion. Each bar plots the Matthews Correlation Coefficient between the corresponding prediction and the ground truth label. Point estimates are reported with 95% bootstrap confidence intervals.
H Additional experimental details: prediction from visual features
In this section we provide additional details related to the escape the room task studied in Sec- tion 5, Our work focuses on study 2 in [62]; study analyzes the same task with only treat- ment arms. As discussed in Section 5, the dimension of the feature space is 33, and encodes the mean/median//tanddad deviation (for numerical features) or one-hot encoding (for categorical fea- tures) of the following: the location in which the puzzle was attempted (Boston, Arizona, NYC etc.), type of escape the room puzzle (theater, office, home etc.), the number people the photo, summary demographic information (age, gender, race, racial diversity), whether participants are smiling, and whether (and what type) of glasses they are wearing. This exactly the set of features considered in [62]; for additional detail on the data collection process refer to their work.
31

---

predictor
Correlation Coefficient
random baseline
0.50
dmet
ihil
jfaboy
ngango2
0.25
ngango3
sensexdr
uestc
0.00
yww211
radiologist
radiologist
radiologist 3
Subset 0
Subset Index
Figure 6: The conditional performance of radiologists and predictive algorithms for detecting pleural effusion within two approximately indistinguishable subsets. random permutation of the true labels is included as baseline. The confidence intervals for the algorithmic predictors are not strictly valid (the subsets are chosen conditional on the predictions themselves), but are included for reference against radiologist performance. All else is as in Figure 5.
Correlation Coefficient
predictor
0.7
dmet
ihil
jfaboy
ngango2
0.6
ngango3
sensexdr
uestc
yww211
0.5
radiologist
radiologist 2
radiologist
algorithmic
radiologist
Prediction Type
Figure 7: The relative performance of radiologists and predictive algorithms for detecting car- diomegaly. Each bar plots the Matthews Correlation Coefficient between the corresponding prediction and the ground truth label. Point estimates are reported with 95% bootstrap confidence intervals.
Correlation Coefficient
0.6
predictor
random baseline
dmet
0.4
ihil
jfaboy
ngango2
ngango3
0.2
sensexdr
uestc
yww211
0.0
radiologistt
radiologist
radiologist 3
Subset 0
Subset
Subset Index
Figure 8: The conditional performance of radiologists and predictive algorithms for detecting cardiomegaly within two approximately indistinguishable subsets. random permutation of the true labels is included as baseline. The confidence intervals for the algorithmic predictors are not strictly valid (the subsets are chosen conditional on the predictions themselves), but are included for reference against radiologist performance. All else is as in Figure 7.
32

---

0.6
Correlation Coefficient
predictor
0.5
dmet
ihil
jfaboy
0.4
ngango2
ngango3
sensexdr
0.3
uestc
yww211
radiologist
0.2
radiologist 2
radiologist 3
algorithmic
radiologist
Prediction Type
Figure 9; The relative performance of radiologists and predictive algorithms for detecting consolida- tion. Each bar plots the Matthews Correlation Coefficient between the corresponding prediction and the ground truth label. Point estimates reported with 95% bootstrap confidence intervals.
0.75
predictor
Correlation Coefficient
random baseline
drne
0.50
jiaboy
ngango2
0.25
ngango3
sensexdr
yww211
0.00
radiologist
radiologist
radiologist
Subset 0
Subset
Subset Index
Figure 10: The conditional performance radiologists and predictive algorithms for detecting consolidation within two approximately indistinguishable subsets. A random permutation of the true labels included as a baseline. The confidence intervals for the algorithmic predictors are not strictly valid (the subsets are chosen conditional on the predictions themselves), but are included for reference against radiologist performance. All else as in Figure
Correlation Coefficient
predictor
dmet
0.6
ihil
jfaboy
ngango2
ngango3
sensexdr
uestc
yww211
radiologist
radiologist
0.4
radiologist
algorithmic
radiologist
Prediction Type
Figure 11: The relative performance of radiologists and predictive algorithms for detecting edema. Each bar plots the Matthews Correlation Coefficient between the corresponding prediction and the ground truth label. Point estimates are reported with 95% bootstrap confidence intervals.
33

---

Correlation Coefficient
0.6
predictor
random baseline
dmet
0.4
ihil
jfaboy
ngango2
0.2
ngango3
sensexdr
uestc
0.0
yww211
radiologist
radiologist
radiologist 3
Subset 0
Subset
Subset Index
The conditional performance of radiologists and predictive algorithms for detecting edema within two approximately indistinguishable subsets. random permutation of the true labels is included as baseline. The confidence intervals for the algorithmic predictors are not strictly valid (the subsets are chosen conditional on the predictions themselves), are included for reference against radiologist performance. All else is as in Figure 11.
Figure 12:
To learn a partition of the input space, we apply the boosting algorithm proposed in [27]. We discuss this algorithm and its connection multicalibration Appendix
I Additional experimental results: prediction from visual features
In this section present additional experimental results for the visual prediction task studied in [62].
Humans fail to outperform algorithms. As in the X-ray diagnosis task Section 5, we first directly compare the performance of human subjects to that of the five off-the-shelf learning algorithms studied in [62]. We again use the Matthew's Correlation Coefficient (MCC) as measure of binary classification accuracy [12]. Our results confirm one of the basic findings in [62], which is that humans fail outperform the best algorithmic predictors. We present these results in Figure 13.
Correlation Coefficient
0.40
predictor
naive bayes
random forest
0.35
logistic regression
gradient boosting
0.30
linear
human (control)
human (4 examples)
0.25
human examples)
human (12 examples)
0.20
human subjects
algorithmic
Prediction Type
Figure 13: Comparing the accuracy human subjects' predictions to those made by off-the-shelf learning algorithms across four treatment conditions. Subjects in the control condition are given no training, while subjects in each the three remaining conditions are presented with small number of labeled examples before beginning the task. Each bar plots the Matthews correlation coefficient between the corresponding prediction and the true binary outcome; point estimates are reported with 95% bootstrap confidence intervals.
Although these results indicate that humans fail to outperform algorithms average in this visual prediction task, we now apply the results Section 4 to investigate whether humans subjects can refine algorithmic predictions on specific instances.
34

---

Resolving indistinguishabiitt via human judgment. As in Section 5, we first form partition of the set of input images which is multicalibrated with respect the five predictors considered in Figure 13. As indicated by Lemma B.1 and Corollary B.2, we do this by partitioning the space of observations to minimize the variance of each of the five predictors within each subset." Ii Because the outcome is binary, it is natural to partition the space of images into two clusters. We now examine the conditional correlation between each prediction and the true binary outcome within each these subsets, which we plot in Figure 14.
Correlation Coefficient
predictor
0.4
gradient_boosting
linear_svm
Aegisticrregressinn
naive. _aaee_
random forest
0.2
human (control)
human examples)
human (8 examples)
human (12 examples)
0.0
Subset
Subset
Model Prediction Bins
Figure 14: The conditional performance of human and algorithmic predictions within two approxi- mately indistinguishable subsets. Subset (n 189) the set in which all five predictors predict positive label: Subset 0 (n 671) contains the remaining observations. All else is as in Figure 13. The confidence intervals for the algorithmic predictors are not strictly valid (the subsets are chosen conditional on the predictions themselves), but are included for reference against human performance.
As we can see, the human subjects' predictions perform comparably to the algorithms within subset but add substantial additional signal when all five models predict a positive label (subset 1). Thus, although the human subjects fail to outperform the algorithmic predictors on average (Figure 13), there is substantial heterogeneity in their relative performance that can be identified ex-ante by partitioning the observations into two approximately indistinguishable subsets. In particular, as in find that human subjects can identify negative
the X-ray classification task studied in Section instances which are incorrectly classified as positive by all five algorithmic predictors.
le describe this procedure in Appendix F.
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction make claims which accurately reflect the paper's contributions and scope, which cover (1) framework and method for incorporating human judgment into algorithmic predictions (2) technical results demonstrating the conditions under which this approach performs well and (3) empirical results demonstrating the utility (and limitations) our approach practice.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Limitations are discussed throughout, and specifically addressed in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
36

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Yes, each theoretical result provided with the full set of relevant assumptions, and proofs are included in Appendix C. Where relevant, additional lemmas are stated with the full set of relevant assumptions and proved in Appendix E.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Each of the experimental results include all important methodological choices and hyperparameters needed reproduce the result; additional detail reproduce our experiments is provided in Appendix F and Appendix H. Code, data and detailed instructions to replicate our results are available at https: hggggtttu....... wwworoalurraaaaaooaeeoeeeeaaeeee wallur/haap-aa htwphhaaarrereee repl.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
37

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code, data and instructions replicate our experimental results are available at https://githu:
mallur/heag h
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc.
httii///uuudess/ooeeubbbimaa www.sssiiiiiiyoooooooooomlliiipl for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. /t/pc//pp//.c wwc/public/ggiiiee /et/gudde///ooeubmiiii
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The main text includes all high-level methodological choices, including hyperparameters (and the logic choosing them). Additional details are provided in Appendix F and Appendix H, and detailed instructions, code and data needed to replicate our experiments are provided at https: //github. http///aaurrhea-rreee
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
38

---

Justification: Each experiment in Section 5 includes enror bars along with the methodology and level of statistical significance. We generally report bootstrap standard intervals at 95% confidence level. Additional detail regarding the calculation of error bars (e.g., the libraries used) is available https: /ttp::///ihhiin
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our experiments do not require any special hardware, and can be run on standard core personal laptop in under 10 minutes. This fact is included in our README (https: http://gttttbbtt com/ralur caaaaurreee htap/hhapppppee
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: httparrp.....pubbllcchccccceteee
Answer: [Yes]
Justification: To our knowledge, paper conforms with every aspect of the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
39

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Yes, these are discussed in Section 7. In particular, the primary potential social impact of our work for readers to interpret our results advocating for particular level of automation, including in high-stakes clinical health tasks. As we discuss in Section 7, our methodology addresses only few technical questions related human-Al collaboration, and are not sufficient for ensuring that other desiderata (including, but not restricted to, fairness, accountability and interpretability) are satisfied.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our contributions primarily methodological, and the assets release (short scripts to reproduce our results) do not pose the same risks as e.g., releasing generative language image models. The data not scrape or otherwise collect additional data for this work.
already widely publicly available; did
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided relcasing unsafe images.
40

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Licenses associated with the data we use are described in the README (https://gi wwwptttuu.cooomeeeeeeemm
Other work is properly credited throughout.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URI..
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The assets we release are documented in the README con/raluur/eaa--ep))
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our work does not include new crowdsourced or human subjects. We do use widely available datasets which were initially collected in [62] and [35]. The data sheet asso- ciated with the latter is available at [26]. Both works contain detailed information regarding the instructions given participants, screenshots, and details regarding compensation.
Guidelines:
41

---

The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does not include crowdsourced human subjects. We do use widely available datasets which were initially collected in [62] and [35] (the data sheet associated with the latter is available in [26]). Both papers indicate that the studies described therein were approved by the relevant institutional review board.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.
42


Reviews:
[{"review_id": "JoSG2x7gGC", "reviewer": "Reviewer_fseb", "summary": "This paper introduces a framework for joint human-AI prediction, where human experts can augment AI predictions in particular ex ante identifiable subsets.", "questions": "How might you model deicision makers with richer preferences than mean squared error?", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper makes a lot of interesting contributions. First, its scope is broad and important: it tackles the question of how and whether human judgment can improve the predictions of any learning algorithm. That is and will remain to be a very important question in our time. It contributes a very interesting framework, rooted in algorithmic indistinguishability and multicalibration, to find subsets in which no algorithm in a user-specified class has predictive power (because they are algorithmically indistinguishable) but human experts do (because they might have more access to the instances, such as doctors examining patients). It demonstrates that using this framework, we can find subsets of instances where human experts can outperform algorithms, and thus the combination of the two can outperform either alone. It applies this to an important medical problem and in another domain of making predictions from photos of people. It even extends the framework to apply to a setting with noncompliance. The community stands to learn a lot from this paper.", "weaknesses": "As the authors mention, the framework is dependent on minimizing mean squared error only.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**In response to:** *How might you model decision makers with richer preferences than mean squared error?*\n\nThank you for your feedback, we agree that we should address this possibility in more detail (particularly in the final discussion section). We provide our thoughts below, and will plan to update our manuscript to better communicate the scope of indistinguishability beyond minimizing mean squared error (this is closely related to reviewer XFzN's question about the generality of our framework; for convenience, we copy our response under both reviewers comments).\n\nOne way of interpreting algorithmic indistinguishability is that the algorithm provides the decision maker with a partial ordering over instances, where the ordering is defined with respect to a single outcome of interest $Y$. In particular, the algorithm can assert that instances in one indistinguishable subset $S_1$ have a larger average value of $Y$ than another indistinguishable subset $S_2$ --- so the algorithm implicitly ranks each $x \\in S_1$ higher than each $x \\in S_2$ --- but it has no way of ordering instances *within* each indistinguishable subset. Theorem 4.1 and Corollary 4.2 focus on settings where the objective of interest is to minimize mean squared error, and show how additional information provided by the expert can be used in service of this objective. However, this is far from the only possibility: for example, a decision maker might use predictions to inform a selection rule which seeks to balance both maximizing the mean value of $Y$ within the pool selected while also ensuring some measure of fairness or diversity (e.g., a university choosing which students to accept, where $Y$ is some measure of academic performance). In this setting, a very natural application of our framework would be to present the decision maker with a set of inputs which are algorithmically indistinguishable with respect to $Y$, and allow the decision maker to then choose from this pool to maximize their chosen fairness metric (e.g., by choosing a set of candidates with diverse interests from within a pool which cannot be distinguished on the basis of predicted academic performance). Similarly, a decision maker whose utility function includes some measure of risk aversion may select a pool of candidates from within an indistinguishable subset to minimize e.g., the *variance* of $Y$ among those selected. In both cases, indistinguishability provides a principled basis for imposing \"secondary\" preferences in decision making, as the decision maker can reasonably assert that they otherwise lack information to distinguish instances on the basis of (the expected value of) $Y$ alone.\n\nFinally, we note that in both of these examples, we did not assume that the decision maker's utility can be linearly decomposed across inputs. This is in contrast to mean squared error, which can be decomposed as a (normalized) *sum* of prediction errors accross inputs. For example, a measure of fairness might depend on the composition of the entire group selected; it may not always make sense to ask whether the selection of a single individual in isolation is \"fair\". Similarly, a measure of risk might also depend on the composition of the entire group which is selected; perhaps the decision maker wants to select a set of inputs whose outcomes are minimally correlated (e.g., choosing a portfolio of stocks), and thus their utility is again necessarily a set-valued function.  Thus, our framework is not restricted to minimizing mean squared error or simple variants thereof; instead, it provides a substantially more general basis for decision making under uncertainty. Modeling a decision maker with richer preferences is a fascinating direction, and would be happy to address any followup questions or comments during the upcoming discussion period.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YxNisJxtJ3", "reviewer": "Reviewer_jnGw", "summary": "The paper first presents some theory for the modelling of how to identify when human judgements may offer a better diagnosis - through access to additional information - than machine predictions, despite the latter typically being more accurate. This is followed by exploring how to integrate the human input with the algorithmic (model) input. Subsequently, the authors present some focussed experimental results using chest x-ray interpretation that support their proposition.", "questions": "Q1. The case studies are retrospective so both machine and human outcomes are available to use in the analysis. How would the approach work in a live situation?", "limitations": "Section 7 provides some properly reflective critique on scope and applicability.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: carefully drawn comparison with the literature, situates and differentiates the contribution.\n\nQuality + Clarity (addressed together):\n\nClear abstract and intro with well-defined contributions. Content offers a reasonable balance between technical and intuitive. Recognition of the value of the human contribution and seeking to integrate it in decision making.\n\nThe later mathematical results (section 4) have effective accompanying interpretations (see complementary point in weaknesses).\n\nEffective, selective presentation of results: choosing one and going into detail, while two other cases in the appendices support the same observation, rather than trying to squeeze them all into the paper body. Same applies to results in section 5.2.\n\nSignificance: provides a sound framework for a particular, amenable class of collaboration problems that allows for the proper incorporation of human prediction where machine prediction could fall short.", "weaknesses": "Clarity: Indistinguishability and multicalibration are critical elements to the contribution; it would be helpful if the interpretation of their definitions (3.1, 3.2) went into a bit more detail for accessibility.\n\nThis reader is not succeeding in following the argument about robustness (section 6).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**In response to:** *...it would be helpful if the interpretation of...definitions (3.1, 3.2) went into a bit more detail for accessibility.*\n\nThank you for your feedback. We agree that these definitions could use a bit more exposition; we will add more background and provide a concrete interpretation in the context of diagnosing atelectasis (which is described earlier in the introduction) to make them more accessible.\n\n**In response to:** *This reader is not succeeding in following the argument about robustness (section 6).*\n\nWe agree that this portion of the manuscript could be more accessible. We will add some additional exposition to section 6 and further clarify the intended application of these results. To motivate this section, it is helpful to consider the following stylized example:\n\nSuppose we are interested in designing an algorithmic risk score for a large hospital system. As discussed in section 6, one important consideration is that doctors at this hospital system may only selectively comply with the algorithm. Concretely, suppose there is one doctor, doctor A, who generally complies with the algorithm's recommendations except on patients who have high blood pressure; the doctor believes (correctly or not) that the algorithm underweights high blood pressure as a risk factor, and simply uses their judgment to make decisions for this subset of patients. A second doctor, doctor B, similarly complies with the algorithm on all patients under the age of 65, but ignores its recommendations for patients 65 and older.\n\nWhat does an optimal algorithm look like? For doctor A, we would like to select the algorithm which minimizes error on patients who do not have high blood pressure, as these are the patients for whom the doctor actually uses the algorithm's recommendations. Similarly, for doctor B, we would like to select the algorithm which minimizes error on patients who are under 65. The key thing to note is that there is no guarantee that these are the same algorithm: if we were to run empirical risk minimization over the first population of patients, we might get a different predictor than if we ran empirical risk minimization over the second population. This is of course not just a finite sample problem; it is also possible that, given any restricted model class (e.g., all linear predictors), the optimal predictor for one subpopulation may not be optimal for a different subpopulation.\n\nFor both practical and ethical reasons, we cannot provide individualized risk scores for every physician; we must provide a single risk predictor for the entire hospital system. Our first result (Lemma A.4) shows that, without further assumptions, this is an intractable problem. If there are arbitrarily many physicians who may choose to comply in arbitrary ways, then we need a predictor which is simultaneously optimal for every possible patient subpopulation. The only predictor which satisfies this criterion is the Bayes optimal predictor, which is infeasible to learn in a finite data regime.\n\nHowever, it is perhaps more likely that physicians decide whether or not to defer to the algorithm using relatively simple heuristics. If we believe we can model these heuristics as a \"simple\" function of observable patient characteristics --- e.g., that all compliance patterns can be expressed as a shallow decision tree, even if particular compliance behavior varies across physicians --- then perhaps we can leverage this structure to design a single optimal predictor. Theorem 6.1 shows that indeed this is possible: if a predictor is multicalibrated over the appropriate class of risk scores and compliance patterns, then, for every physician, on the subpopulation of patients that the physician defers to the algorithm, the performance of the multicalibrated predictor is competitive with that of any other predictor in the class ${\\cal F}$. Thus, by leveraging known or assumed structure in user compliance patterns, we can design predictors which are \"robust\" to those compliance patterns.\n\nWe hope that helps clarify the motivation and intended application of the results in section 6. As mentioned above, we will update our manuscript to make this section more accessible, and would be happy to answer any follow up questions during the upcoming discussion period.\n    \n**In response to:** *The case studies are retrospective so both machine and human outcomes are available to use in the analysis. How would the approach work in a live situation?*\n\nThis is an excellent question, and one which we will address in more detail (particularly in the discussion section). On a forward-looking basis, perhaps the most natural application of our framework is to proactively solicit expert feedback on *only* those inputs where it appears to provide additional information. For example, in section 4, we observe that a nonzero coefficient $\\beta_k^*$ indicates that an expert provides additional signal within subset $S_k$, whereas a coefficient of $0$ indicates the opposite. Thus, although we assume that we have retrospective expert predictions for every instance, we could prospectively focus expert attention on only the subset of instances where experts add value and simply defer the remainder to an algorithm.\n\nMore generally, choices for both *whether* to solicit expert feedback and *how* to incorporate that feedback into forward-looking decisions is a substantial topic in its own right. For example, translating predictions to decisions, and deciding whether to incorporate expert feedback to do so, may require a rich model of decision makers' preferences or utility functions. We discuss these at length in our response to reviewers fseb and XFzN. Furthermore, although we focus on the standard \"batch\" supervised learning setting to highlight our main contributions, we view the extension to an online learning context as a promising avenue for future work, and will include it in our discussion of open problems in section 7.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zvw9f7oaQJ", "reviewer": "Reviewer_WEMo", "summary": "The paper proposes a framework to incorporate human expert knowledge in algorithmic predictions. Under this framework, the authors introduce a meta-algorithm that uses a training dataset including human expert predictions together with a multi calibrated partition of the data; a partition of the dataset into bins, where each bin contains data that are indistinguishable to the predictive model. Using the data of each bin the meta-algorithm trains a regression algorithm to predict the true label from the human expert prediction. In this way, the authors aim to leverage the human expertise, that may be more accurate than the predictive algorithm on specific instances, to achieve complimentary—to achieve higher predictive accuracy through human AI collaboration than the performance of a human expert or AI in isolation.", "questions": "N/A", "limitations": "The authors adequately discuss the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper suggests an elegant method to improve algorithmic predictions in light of human expertise, that could have significant applications such as the medical domain, where the additional information of human experts may lead them to more accurate predictions on certain instances compared ot predictive models.    \n\nThe paper is very well and clearly written, nicely motivated and follows a clear structure. There is a thorough and comprehensive discussion on related work as well as a comprehensive and clearly presented experimental evaluation.", "weaknesses": "Since the theoretical results of section 6 complement the ones of section 4, it would be perhaps more natural to follow them, rather than placing them after the experimental evaluation, which appears a bit odd.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**In response to:** *Since the theoretical results of section 6 complement the ones of section 4, it would be perhaps more natural to follow them, rather than placing them after the experimental evaluation, which appears a bit odd.*\n\nThank you for your feedback --- we agree that this portion of the manuscript could flow a bit better. Section 4 and 5 are intended to be complementary, as both focus on a particular application of algorithmic indistinguishability. In contrast, section 6 presents results on a qualitatively different application of indistinguishability, which is intended to highlight the generality of our framework and suggest open directions for future work. We will update both the exposition to section 6 (see response to reviewer jnGw) and more directly highlight the flexibility of our approach (see responses to reviewers fseb and XFzN), which we expect will address this concern as well. We are however certainly open to other feedback on this point.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m5a4VS2kWi", "reviewer": "Reviewer_XFzN", "summary": "This paper introduces a new framework into algorithmic predictions. The paper asks and answers the question \"how can we incorporate human input into the prediction algorithm, which may not even be captured in the training data\"? The authors develop a method that first runs the predictor, and then runs a second predictor using the human input. The authors show that even a simple instantiation of their method can outperform existing predictors. They use the X-ray classification task as experimental datasets.", "questions": "My main comment is that the authors should comment more about the future work and implications of this method. Furthermore, I would be interested to hear what the authors think about a related paper [1], and how these papers might be related.\n\n[1] DEFINING EXPERTISE: APPLICATIONS TO TREATMENT EFFECT ESTIMATION (https://arxiv.org/pdf/2403.00694)", "limitations": "The authors have addressed the limitations in the conclusion section", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is written very clearly, and offers a novel method to incorporate human input into algorithmic prediction. Both theoretical derivations and experiment results are sound. The contributions of this paper is significant, and I believe this paper deserves to be accepted in its current form.", "weaknesses": "The paper would be even more satisfying if the method is presented as a framework rather than a specific instantiation. In addition, it would be great if the authors can discuss potential ways to improve on the method they propose, and what these methods mean in the broader context of incorporating human feedback into algorithmic predictions. Nevertheless, these small weaknesses does not diminish the significance and novelty of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**In response to:** *The paper would be even more satisfying if the method is presented as a framework rather than a specific instantiation...* And: *My main comment is that the authors should comment more about the future work and implications of this method.*\n\nThank you for your feedback, we agree that we could devote more space to discussing the generality of our approach and avenues for possible future work. We provide our thoughts on this point below, and will plan to update our manuscript to better communicate the scope of indistinguishability beyond minimizing mean squared error (this is closely related to reviewer fseb's question about modeling decision makers which richer preferences; for convenience, we copy our response under both reviewers comments).\n    \nOne way of interpreting algorithmic indistinguishability is that the algorithm provides the decision maker with a partial ordering over instances, where the ordering is defined with respect to a single outcome of interest $Y$. In particular, the algorithm can assert that instances in one indistinguishable subset $S_1$ have a larger average value of $Y$ than another indistinguishable subset $S_2$ --- so the algorithm implicitly ranks each $x \\in S_1$ higher than each $x \\in S_2$ --- but it has no way of ordering instances *within* each indistinguishable subset. Theorem 4.1 and Corollary 4.2 focus on settings where the objective of interest is to minimize mean squared error, and show how additional information provided by the expert can be used in service of this objective. However, this is far from the only possibility: for example, a decision maker might use predictions to inform a selection rule which seeks to balance both maximizing the mean value of $Y$ within the pool selected while also ensuring some measure of fairness or diversity (e.g., a university choosing which students to accept, where $Y$ is some measure of academic performance). In this setting, a very natural application of our framework would be to present the decision maker with a set of inputs which are algorithmically indistinguishable with respect to $Y$, and allow the decision maker to then choose from this pool to maximize their chosen fairness metric (e.g., by choosing a set of candidates with diverse interests from within a pool which cannot be distinguished on the basis of predicted academic performance). Similarly, a decision maker whose utility function includes some measure of risk aversion may select a pool of candidates from within an indistinguishable subset to minimize e.g., the *variance* of $Y$ among those selected. In both cases, indistinguishability provides a principled basis for imposing \"secondary\" preferences in decision making, as the decision maker can reasonably assert that they otherwise lack information to distinguish instances on the basis of (the expected value of) $Y$ alone.\n\nFinally, we note that in both of these examples, we did not assume that the decision maker's utility can be linearly decomposed across inputs. This is in contrast to mean squared error, which can be decomposed as a (normalized) *sum* of prediction errors accross inputs. For example, a measure of fairness might depend on the composition of the entire group selected; it may not always make sense to ask whether the selection of a single individual in isolation is \"fair\". Similarly, a measure of risk might also depend on the composition of the entire group which is selected; perhaps the decision maker wants to select a set of inputs whose outcomes are minimally correlated (e.g., choosing a portfolio of stocks), and thus their utility is again necessarily a set-valued function.  Thus, our framework is not restricted to minimizing mean squared error or simple variants thereof; instead, it provides a substantially more general basis for decision making under uncertainty. Modeling a decision maker with richer preferences is a fascinating direction, and would be happy to address any followup questions or comments during the upcoming discussion period. \n\n    \n**In response to:** *Furthermore, I would be interested to hear what the authors think about a related paper [1], and how these papers might be related. https://arxiv.org/pdf/2403.00694*\n\nThank you for the pointer to this work. This is a fascinating and related topic, which characterizes the value of human expertise as an inductive bias for guiding model selection. In particular, the authors argue that expert decisions regarding treatment allocation can be highly predictive of the true treatment effects, and that this fact can be used to inform the model selection process for treatment effect estimation. Importantly however --- and as is typical in treatment effect estimation problems --- [1] assumes *no hidden confounding* (see Section 2), which rules out the possibility that experts leverage information which is correlated with potential outcomes but unavailable to the algorithm.\n    \nThis perspective is complementary to our work, which is instead focused on the possibility that experts *do* have information which is unavailable to the algorithm, and studies how to incorporate this information at \"inference\" or \"test\" time. Thus, even given infinite data to learn the best possible (e.g., Bayes optimal) model of $Y$ given $X$, our method might incorporate expert feedback at test time to improve predictions. In contrast, [1] uses expert decisions at training time to more efficiently learn a model under sample size constraints, but do not consider incorporating expertise at test time because it is assumed that experts do not provide signal which the algorithm could not (eventually, given sufficient training data, and under the overlap and unconfoundedness assumptions) learn on its own. \n\nWe thank you for pointing us to this work, and we will include a citation in our manuscript. We'd be happy to discuss this point further and answer any followup questions during the upcoming discussion period.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We are grateful to all four reviewers for their thoughtful and constructive feedback. Below we describe how we intend to incorporate this feedback into our manuscript and include responses to specific reviewer questions and concerns.

Meta-review: The paper tackles an important and longstanding problem: when and how human judgment can improve algorithmic predictions. It identifies a key technical construct: multicalibration subsets where algorithms' predictions will be indistinguishable, but humans can still make distinctions. It uses this insight to create a meta-algorithm to improve the algorithm's predictions. Reviewers appreciated the broad and fundamental insight as well as experiments on three diverse datasets. The paper is also well-written and accessible. Thank you for submitting this work to NeurIPS and I'm glad to recommend Accept.
Decision: Accept (oral)