Selective Omniprediction and Fair Abstention

We thank the reviewer for their very thorough evaluation of our paper and for the excellent questions, which are all important points that we should expand on and clarify in the final version of our paper. We answer them in order:

(1) Yes, coverage refers to the fraction of the points in the domain on which the predictor does not abstain (e.g., a non-selective classifier has full coverage equal to 1). We should have defined this term formally in the paper and will add a definition. Regarding the coverage of a selective omnipredictor vs that of decision trees, it is arguably intuitive to expect the selective omnipredictor to attain higher coverage. This is because the omniprediction framework provides a much stronger learning guarantee than that of usual loss minimization. Because the labels are boolean, the values of the selective omnipredictor are "polarized" towards 0 and 1 because it is a more powerful learning algorithm. Meanwhile, we are comparing it to a method with no theoretical guarantees, so it makes sense that decision trees attain lower coverage (because the predictions are more uncertain and thus closer to $½$).

Regarding the question of whether there are limitations to high coverage for all losses, the main limitation for the coverage rate is that we are working in the agnostic setting, and so we are not making any assumptions about the data generation process. Indeed, the labels could be random noise. In this case, unless the cost of abstention is extremely high, one would expect very low coverage. More generally, the rate of coverage depends on the relative cost of misprediction vs of the cost of abstention, given that higher costs of abstention lead to higher coverage (and vice-versa; if it is much cheaper to abstain than to predict, then we should expect low coverage). A theoretical guarantee of our selective omnipredictor is that the abstention interval $I_{abs}$ is fixed for each generalized Chow loss function, independent of the true labels (as we show in Lemma 3.2). So, the coverage rate corresponds to the rate of datapoints that have $k_{\ell_{\pm}, \ell_{?}} \circ h$ value outside of the abstention interval $I_{abs}$ (where $h$ is a selective omnipredictor). Again, because we work in the agnostic setting, we cannot have a formal guarantee on how many such points there are, but perhaps if we had some assumptions on the data generation process then we would be able to argue about the number of points that fall within the $I_{abs}$ interval once the loss function has been fixed. This is an interesting direction for future work.

(2) Yes, sorry, there is a typo in the definition of the 0-1 loss. We will change it and stick to the $\ell_1$ loss. Thank you!

(3) These are all great points. First of all, regarding the definition of the class $SC(C)$: we remark that we take the definition directly from the reliable agnostic learning framework defined by Kalai, Kanade and Mansour (they call it $PC(C)$ in their paper). In their case, they are only considering boolean concepts $c \in C$. For a selective classifier, we need to compare the abstention rate to the base class $C$, but the issue is that $C$ only contains boolean concepts. So, we need to add abstentions to $C$. Note that because the concepts in $C$ are boolean, it doesn’t make sense to consider post-processings of the form $k \circ C$, as used in our selective omniprediction definition (where the concepts are real-valued). If we want to add abstentions ? to $c: X \rightarrow \{0,1\}$ without having to bring in other concept classes (i.e., we want to get it directly as a variation of the original class $C$), and given that the motivation of reliable agnostic learning is to ensure that whenever the classifier predicts, it essentially makes no errors, then the definition of $SC(C)$ is in fact very natural. We take the concepts that make no false positives, the concepts that make no false negatives, and ensemble them as per line 177. This ensures that we add abstentions to the class such that the classifiers in this class (i.e., $SC(C)$) make no errors whatsoever whenever they predict. We agree that we should explain this intuition behind the construction of $SC(C)$ (which we remark is not our original definition) and will include it in the paper.

Regarding the difference between $SC(C)$ and $k \circ C$, it is important to note that for anything reliable agnostic learning related (i.e., for the original Kalai et al. paper and our Section 4), we are dealing with boolean concepts. Instead, for $k \circ C$ and our selective omnipredictors (i.e., Section 3), we are dealing with real-valued concepts. We will make this distinction clear in the paper. $SC(C)$ and $k \circ C$ are a priori incomparable, but we can relate them by expanding the boolean class $C$ as follows: for each $c_1, c_2 \in C$, we define the class $C’$ as containing the concepts $(c_1 + c_2)/2$ (note that $C’$ is no longer a boolean class). We define the post-processing $k \circ C$ as mapping 0 to 0, 1 to 1, and $½$ to “?”. Then, we have that $SC(C) \subseteq k \circ C’$.

Lastly, regarding the relative strengths of Theorems 3.1 and 4.1, they are incomparable. The above paragraph explains how we can think of relating the base concept classes, but they are still different. The objects that the theorems are dealing with are also different: there is no class $G$ in the case of Theorem 3.1, only $C$. A $C$-selective omnipredictor is also not necessarily stronger than a $(C, G)$-selective classifier: there are no guarantees on its “local” abstention rate on each $g \in G$ (there is no class $G$ to begin with). The concepts also have different ranges, as we have discussed. We view Theorem 4.1 as the “multigroup” version of fully reliable learning (as originally introduced by Kalai et. al), which is also why we continue to use $SC(C)$ in that case, and because we similarly want to ensure that whenever we predict, we make no mistakes (as per Condition 1 in the definition of $(C,G)$-selective classification). As discussed, this base class is not appropriate for the definition of a selective omnipredictor, and there we also instead consider the total Chow loss, which considers the total loss rather than asking for no misprediction loss (unlike in the reliable agnostic setting).

It is a good question whether we could get selective omnipredictors from the weaker primitive of calibrated multiaccuracy rather than from multicalibration, especially in light of new constructions of omniprediction from calibrated multiaccuracy (see “Loss Minimization Through the Lens Of Outcome Indistinguishability” by Gopalan et al. and “Near-Optimal Algorithms for Omniprediction” by Okoroafor et al.). It is a question that we would like to explore further.

(4) Yes, $C \cap G$ corresponds to the class ${cg \mid c \in C, g \in G}$. We will add the formal definition to the paper. We acknowledge that $C \cap G$ is a larger class than $C$ and $G$ separately, but agnostic learning is hard in theory for most concept classes anyway. So, it is not taking the intersection of the classes what makes the problem hard in theory. In practice, we have heuristics to simulate a weak agnostic learning oracle (e.g., using random forests or neural networks). It is still useful (and common) to solve a learning problem (in this case, constructing a $(C, G)$-selective classifier) by assuming oracle access to another learning problem (in this case, constructing a $(C \cap G)$-weak agnostic learner), even if we only have heuristics to simulate this oracle access in practice. The theoretical reduction still holds in practice.

Separately, is interesting to ask whether we can solve the problem of $(C \cap G)$-weak agnostic learning by using only a $C$-weak agnostic learner and a $G$-weak agnostic learner (i.e., without having to require a weak agnostic learner for the class $C \cap G$). We do know whether this is possible, but it appears to be a standalone interesting learning-theoretic question.

(5) As far as we know, there are no known lower bounds for omniprediction, although there has been a lot of recent work dedicated to improving the construction of omnipredictors (see, for example, the work “Near-Optimal Algorithms for Omniprediction” by Okoroafor et al.). It would be good to think more about the precise relationship between the problem of omniprediction vs the problem of selective omniprediction, both in terms of learning primitives and of computational efficiency. Now that we have introduced the notion of selective omniprediction in our work, this is a natural next direction. More broadly, it would be great to better understand the relationship between typical learning-theoretic problems and their selective counter-parts. For example, Kanade and Thaler showed that reliable agnostic learning is weaker than (weak) agnostic learning (under standard hardness assumptions). We can ask: is this a general phenomenon when adding abstentions to a "non-selective" learning problem?

Lastly, we agree that it would be useful to make some of the statements more informal for some of the results and give some more experimental details for a NeurIPS audience, and will incorporate this in the final version of our paper. We will also compare the known sample complexity differences between calibrated multiaccuracy and multicalibration. Thank you very much!

We thank the reviewer for their positive comments on our paper and for providing insightful feedback. We agree that we should have formally defined the class $C \cap G$ rather than directly use it in the proofs; we will add a formal definition in the beginning of Section 4. We also agree that we should explicitly say that we assume that the constant 0 and 1 functions are in both $C$ and $G$. We say so for $C$ in the beginning of Section 2, and for $G$ in lines 326-327, but we should be more explicit about this assumption. Thank you!

We thank the reviewer for their insightful comments and questions. We answer them in order:

(1) Thank you very much for pointing out these typos, we will make sure to correct all of them.

(2) This is a great point about the definition of the Bayes optimal predictor. We agree that we misuse this term in the paper; what we should have said in line 91 (and will say in the final version of the paper) is that $f^{\ast}$ is the ground truth predictor $f^{\ast}(x) = E[y|x]$. This corresponds to the Bayes optimal predictor in the form written by the reviewer in the case of the squared loss. More generally, all proper losses ensure that $E[\ell(y, f(x))]$ is minimized by the ground-truth predictor. (For improper losses, we can post-process the ground-truth predictor $f^{\ast}$ to minimize the loss; see the paper “Near-Optimal Algorithms for Omniprediction” by Okoroafor et al. for details.) We will be careful about this distinction and stick to the name “ground-truth predictor” in our paper.

(3) Yes, that is correct about the conditioning on $g(x)=1$. We will correct it, thank you!

We thank the reviewer for their insightful questions. We answer them in the same order:

(1) We provide the details of how we generate the synthetic data for our experiments in the appendix. All the details of the experiments for selective omniprediction can be found in Section F.1. Specifically, for these experiments, we generate 10,000 samples and 20 features as our data using sk-learn’s function "make_classification".

The experiments for the conformal prediction application of FRL can be found in Section F.2. Specifically, for these experiments, we generate 5,000 data samples synthetically using sk-learn’s "make_blobs" function, which generates isotropic Gaussian blobs for clustering.

Lastly, the experiments for (C, G)-selective classifiers can be found in Section H. Specifically, we use the same data generation process as in the selective omnipredictors experiments. Namely, we generate 10,000 samples synthetically using sk-learn’s "make_classification" function.

(2) Selective omnipredictors, given their strong learning guarantees, allow us to train without having to commit to a loss function in advance. This is very useful in scenarios where we do not know the loss function at the time of training, or when we might want to change the loss function in the future. For example, if false positives become costlier over time, or if the cost of abstention changes over time. Having this type of flexibility is very useful in any prediction setting and in real-world deployments. While this flexibility is also present in the original notion of an omnipredictor (i.e., without abstentions), being able to abstain (optimally) is also a very useful outcome option to add to a predictor. For example, in societal applications, this allows us to identify the points on which the prediction is uncertain and defer them to further review, rather than forcing a prediction. Our framework merges the line of work on omniprediction and the line of work on selective classification, thus merging the benefits of both frameworks. Our selective omnipredictors abstain optimally and do so in this very flexible “loss agnostic” sense. So, this is useful both because we have the loss function flexibility feature and because we give the predictor the option to abstain.

(3) Yes, it can be extended beyond binary classification settings, and we will make a remark in the paper. Multiple follow-up works to the original papers on multicalibration and omniprediction have provided constructions for the real-valued labels setting. (See, for example, the works “Omnipredictors for regression and the approximate rank of convex functions“ by Gopalan et al. and “Multicalibration as Boosting for Regression” by Globus-Harris et al.). Because our algorithm for selective omniprediction relies on a multicalibration algorithm, known extensions of the multicalibration algorithm to the real-valued setting apply to us as well.

(4) Yes, it is standard in all works on multicalibration to multiply by the probability of the subgroup. We need to do something about the very small subgroups; otherwise, the task of building a multicalibrated predictor becomes statistically impossible (indeed, otherwise one could consider the collection G including all singletons, in which case requiring multicalibration would not be computationally feasible). Different papers deal with the very small subgroups in slightly different (but equivalent) ways: we can multiply by the probability of the subgroup (for example, as done in the original omnipredictors paper), or we can condition on the group g, but then we must discard the level sets that have probability mass less than some chosen constant gamma, so that we speak of (epsilon, gamma)-multicalibration (for example, as done in the original multicalibration paper).

We remark that there are two different types of “subgroups” going on here. Multicalibration is all about ensuring calibration on subgroups of the domain, and it does so for every group that includes a constant fraction of the population, and the guarantee does hold for all of these. What we are discarding are the subgroups that are smaller than that. But, as in many things in computer science, we just cannot make any promises for probabilities that are too small; there is not a way around not having enough statistical signal.

Next we address the “Other minor comments/questions”:

(1) Yes, we will add an explanation in the main body regarding how we can extend the construction of selective omnipredictors beyond convex and Lipschitz loss functions. The formal proof is provided in Section E in the appendix. Essentially, the idea is to only require Lipschitzness over a large enough closed interval, rather than on all of $\mathbb{R}$. This relaxation allows us to add new loss functions to the class $\mathcal{L}$. This relaxation is used in the original omnipredictors paper, where these type of functions are called nice loss functions. Recent work has expanded the construction of omnipredictors beyond convex losses (see “Loss Minimization Through the Lens Of Outcome Indistinguishability” by Gopalan et al. and “Near-Optimal Algorithms for Omniprediction” by Okoroafor et al.).

(2) While the original definition of multicalibration and the way we state it in Section 2.1 is for boolean functions, the notion of multicalibration was quickly extended to concepts $c$ taking real values on a closed interval. This is why in both the original omnipredictors theorem (Theorem 2.1) and in our selective omnipredictors theorem (Theorem 3.1) we use real-valued concepts $c$. We will clarify this in the paper so that the theorem statements are coherent with the precise multicalibration definition that we use.

(3) We will include a definition of computational indistinguishability. Essentially, we just wanted to give some intuition as to why multicalibration is a useful tool for omniprediction. As formalized in the so-called “Outcome Indistinguishability” framework by Dwork et al., multicalibration can be viewed as a form of indistinguishability, in the sense traditionally used in the field of complexity theory. A thorough explanation of the omniprediction framework from the lenses of computational indistinguishability can be found in the paper “Loss Minimization through the Lens of Outcome Indistinguishability” by Gopalan et al.

(4) They refer to the $\ell_1(y, t) = |y-t|$ and $\ell_2(y, t) = (y-t)^2$ loss functions, respectively.

(5) While we do not formally state bounds on the coverage of our method, one would expect a selective omnipredictor to attain higher coverage than a decision tree. The reason is that omniprediction is a very strong learning notion, which provides much more stringent guarantees than usual loss minimization. Because the labels are boolean, the values of the selective omnipredictor are "polarized" to 0 and 1 because it is a more powerful learning algorithm. Meanwhile, we are comparing it to a method with no theoretical guarantees, so it makes sense that decision trees attain lower coverage (because the predictions are more uncertain and thus closer to $½$). It would be interesting to formally investigate the coverage guarantees further.

(6) These empty regions are because the figure comes from our experimental results, and so our selective omnipredictor doesn’t have all values $p \in [0,1]$ in its range. So in theory, the blue and red regions are entirely the designated color; experimentally, the empty regions correspond to points $p \in [0,1]$ that are not in the range of the post-processed selective omnipredictor for the particular data at hand.

Thank you for all of the comments!