Selective Omniprediction and Fair Abstention
Authors: Sílvia Casacuberta
Varun Kanade
Venue: NeurIPS 2025 spotlight ()
Keywords: Selective classification
Learning to abstain
Multicalibration
Omniprediction
Conformal prediction
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: We propose new learning algorithms for building selective classifiers, which are predictors that are allowed to abstain on some fraction of the domain. We study the model where a classifier may abstain from predicting at a fixed cost. Building on the recent framework on multigroup fairness and omniprediction, given a pre-specified class of loss functions, we provide an algorithm for building a single classifier that learns abstentions and predictions optimally for every loss in the entire class, where the abstentions are decided efficiently for each specific loss function by applying a fixed post-processing function. Our algorithm and theoretical guarantees generalize the previously-known algorithms for learning selective classifiers in formal learning-theoretic models.
    
We then extend the traditional multigroup fairness algorithms to the selective classification setting and show that we can use a calibrated and multiaccurate predictor to efficiently build selective classifiers that abstain optimally not only globally but also locally within each of the groups in any pre-specified collection of possibly intersecting subgroups of the domain, and are also accurate when they do not abstain. We show how our abstention algorithms can be used as conformal prediction methods in the binary classification setting to achieve both marginal and group-conditional coverage guarantees for an intersecting collection of groups. We provide empirical evaluations for all of our theoretical results, demonstrating the practicality of our learning algorithms for abstaining optimally and fairly.

Selective Omniprediction and Fair Abstention
Silvia Casacuberta Department of Computer Science Stanford University scasac@stanf ord. edu
Varun Kanade
Department Computer Science
University of Oxford
varun, kanadedcs. ox. ac uk
Abstract
We propose new learning algorithms for building selective classifiers, which are predictors that are allowed to abstain on some fraction of the domain. We study the model where a classifier may abstain from predicting at a fixed cost. Building the recent framework on multigroup fairness and omniprediction, given pre- specified class of loss functions, we provide an algorithm for building a single classifier that learns abstentions and predictions optimally for every loss in the entire class, where the abstentions are decided efficiently for each specific loss function by applying fixed post-proceen post-processing function. Our algorithm and theoretical guarantees generalize the previously- formal learning-the thhorreic models.
algorithms for learning selective classifiers
We then extend the traditional multigroup fairness algorithms the selective classification setting and show that we can use a calibrated and multiaccurate predictor to efficiently build selective classifiers that abstain optimally not only globally but also locally within each of the groups in any pre-specified collection of possibly intersecting subgroups of the domain, and are also accurate when they do not abstain. We show how our abstention algorithms can be used conformal prediction methods in the binary classification setting achieve both marginal and group-conditional coverage guarantees for intersecting collection of groups. We provide empirical evaluations for our theoretical results, demonstrating the practicality of our learning algorithms for abstaining optimally and fairly.
Introduction
Selective classification has long been proposed a way of achieving higher accuracy at the cost of abstaining from making predictions on certain points 19 43
22 23 Such behavior is often desirable, e.g. when stakes of mistakes (of type another) be very costly, such as medical diagnoses. There has been a wide range of theoretical and empirical work in this area. The most relevant one to our work the learning-theoree theoretic reliable learning framework [43] of Kalai, Kanade, and Mansour, where they introduce a framework that gives guarantees on еттоr and abstention rate in an agnostic learning framework. Their work focuses on binary classification problems using only the zero-one loss function. A more general learning framework for selective classification is to consider the Chow loss [12 and its generalizations, where one can consider loss functions for predictions as well as fixed penalty for abstention, and weighted combination of these should be minimized.
Separately, recent work has studied the question of whether training from scratch is required for every loss function. Gopalan et al. introduce the notion a (C, -)mmiiprreeictorr for a class of loss functions and concept class C. which a single classifier that can be efficiently post-processed to compete with a class of models for the large family C [25). Omnipredictors turn out to be efficiently constructable from multigroup fairness notion called multicalibration predictors are required to be calibrated, even conditioned on group membership from a large, possibly- intersecting, collection of groups. While (multiicalibration is desirable property, these notions
[32 50 [6] Here
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

do not imply anything about accuracy, and rely upon the base predictor (which is then modified to satisfy multicalibration) being accurate to begin with. As in the case of selective classification more generally, it may be desirable to abstain in order to guarantee high accuracy when predicting.
In this work, we apply the rich line of work on omniprediction and multigroup faimesss the problem of selective classification. First, we introduce the notion of a selective classifier, which is able to simultaneously minimize generalized Chow losses from a rich family of loss functions. We show how this generalizes the previous results on reliable agnostic learning beyond the 0-1 loss. Second, we introduce the notion of multigroup selective classification, where the predictions need to be highly accurate, but in addition it is required that the rate of abstention conditioned on any group is no worse than the abstention rate of an optimal classifier for that class from a base class of abstaining classifiers. We show that such a predictor can be obtained starting from a slightly weaker notion of calibrated multiaccuracy (rather than multicalibration) and access to a weak agnostic learner for a suitable class. When the number of groups is small, we show that this can be constructed efficiently with only access to reliable learner for the base class (which is believed to be weaker notion than weak agnostic learning 45 ). The main results and the focus of our work is theoretical. We do however also provide an empirical evaluation on synthetic data that shows that our algorithms are easy to implement and achieve the desired outcomes. All proofs of our claims are deferred to the appendix.
1.1 Related work
We summarize the most relevant work to ours here; further related work is discussed in the appendix.
Selective classification. The idea of building algorithm that abstains certain predictions is not new and has traditionally been called selective classification [9]. A selective classifier is allowed to also return ? as output (which indicates abstention), along with the usual numerical values. The works [43 45 study this in the context of agnostic learning and give bounds on both the error and abstention rate (competitive with respect to a base class). Selective classification has also been studied within the context of a Chow loss framework, where there is a fixed cost of abstention in addition to a loss function on predictors and the goal is to minimize the overall cost [12]. Abstention has also been used to provide bounds on efficient learning in the presence of covariate shifts [4
23 Although
somewhat different, related notion is that of conformal prediction (66 3 39 where the classifier is allowed to output a set and the goal is that the true label should be in the predicted set with high probability. In binary classification case, considering abstention as predicting the set {0, 1) relates these two notions tightly.
Fairness. Recently, in the setting of faimees,, some works have studied the effect of selectively abstaining. Jones et al. find that certain forms of selective classification can magnify disparities across groups (37,, and follow-up works try to restrict this type of disparities [52] 62 67]. Some recent works have put forth the necessity of accounting for uncertainty in the setting of algorithmic fairness
5 40 54 49
53 13 but this question remains largely understudied. This question is also related
to the problem of model multiplicity, which has recently drawn a lot of attention 7 g [3] Outside of the selective classification problem, the multigroup fairness framework has recently developed various techniques for ensuring that desired properties of the predictor (e.g., accuracy, calibration) hold even when conditioned on any of the possibly intersecting groups in rich collection 332
29
48
51 61).
2 Notation & Preliminaries
We let X' denote the domain, y' {0, 1} the set of labels, D a distribution over X' x y and C concept class over X' of concepts e (their range is specified in each application). We assume that C is closed under complement and contains the constant functions 0, 1. We denote the marginal distribution over X' by Dx. A loss function É takes label y E )' and an action t E IR and returns loss value L t). Examples include the lp losses t, = ly - -tl², the logistic loss costs
l(y, t) = log(1 + cxp(- - y,)),, and binary classification with different false- talse-poosiiveeegatiie t(y.t) = cyly - tl. We let L C= {E: y'x + R} denote collection of loss functions. We are interested in minimizing loss functions: we want to find a hypothesis h X + IR that makes the expected loss (h) := Eo[((y, h(x))) small. We work in the agnostic setting, where we want the expected loss of our hypothesis h to be at most epsilon higher than the best concept in C for that loss function. Importantly, the optimal concept in C depends on the choice of We denote the ground truth predictor by f (x) = Ex(y
2

---

2.1 Multigroup fairness notions
The multigroup framework was introduced as way bridge individual and group fairness notions
32 46]. Given a collection of subgroups G = {g X' - {0. }}} that can intersect arbitrarily, we
want ensure property of interest (aceuracy, calibration) within each of the subgroups in G.
Definition 2.1 (Multiaccuracyy, calibrated multiaccuracy, and multicalibration a predictor h is (G, mulliiccuuaaee for a distribution '
32 26)
We say that
max REG
Elg(x)(y
h(x))l| c.
We say the predictor h is e-calibrated for if E /ly//(()))))))))))))))))) - [xx)]] S c. We say that is (9, e)- multiaccurate and calibrated if it is both (G, m)muliiacceurate and e-calibrated. Further, say that is (9, )ymuliicalibrtted if
max m -(pp)l]ppxx)))]) p(x))]] gES
We can efficiently construct predictors satisfying these increasingly demanding notions if we have access to the learning primitive of a weak agnostic learner for the class G: we require ((1/²))
calls to the weak agnostic learner in the case of (G,e)-m (ff,)-))taacccracyy (32) and of (G. e)-alibbrated
multiaccuracy [26), and ( calls in the case of (G, m)-mltticalliiatii 32 25 The line of
work multigroup fairness has proven to be extremely rich in recent years 24
16
18
2.2
Omnipredictors
One of the most successful applications of the multigroup fairness framework has arguably been in learning theory, where Gopalan et al. used it to propose new indistinguishability bbsed learning framework [25] This framework has been applied in many follow up works [35] 28 27 59 24). Specifically, the usual learning paradigm first chooses loss of interest (e.g.. l (2), and then trains a model to minimize it. But what if we do not know the specific loss at the time of training, or if we want to change it a later time without having the re-train from scratch? We could instead hope to construct the following object, which they called a (C, -omniirredrr.....r
Definition 2.2 (Omniprediction
Given class of loss functions and a concept class C of 25
concepts e X + IR, predictor h :x - [0, 1] is an (C, C, c) oomiirredictor if for every & E L there exists function ky [0, so that
lo(ke o h) min (D(c) + eEc
That is, for every loss E C. there exists a simple (univariate) transformation ke of the predictions of h (chosen tailored to E) such that ke has loss comparable to the best hypothesis E C, which chosen dependent on That is, we can train a single predictor h that is able do as well as the best hypothesis in C separately for every loss function in L. This realizes a very strong learning guarantee. Note that for every C, C, the ground truth predictor I* is an (C, -)-omiirreeiiooorr As shown in 255 the right post-processing function ke turns out to be the minimizer of the expected loss under the Bernoulli distribution, a fact we use to show the optimality our selective predictor. In their main result, Gopalan et al. show that technique of multicalibration:
construct omnipredictors efficiently using the
Theorem 2.1 (Building omnipredictors from multicalibration 25 Let be a distribution on X' x 1), C family of real-valued functions on X, and L the family of all B-Lipschitz, convex loss functions. Then, ( multicaallbbetee predictor h an C,, (F,CC,..)-omiippeeeico
ooniprediicorr.
This result can be extended beyond convex Lipschitz loss functions, including to the exponential loss, GLM losses, I-Lipschitz losses, proper losses, and bounded variation losses 25 59].
2.3 Reliable agnostic learning
In our setting, we allow predictors to output an abstention ?, and so we consider triplets of loss functions (4, Ez). ) predictor allowed to abstain and thus ? in support, we denote with abstention sign in the subscript.
3

---

Losses (4+.e_b))) We further specify loss functions depending on the value of E {0, 1}. Given a loss function &: y {IR (?)} E. we decompose é (c) as follows:
1. Negative labels. For inputs (y, t) where t * ? and y = 0, we write (t) for &D (0, t).
2. Positive labels. For inputs (v. 6) where t + and y = 1, we write (t) for tp (1,())).
3. Abstentions. For inputs (y, t) where
?, we write (x for E(y, t). In turn separate the cases y = 1 and y = O, we write (x(1) 44 and (0 = a.. Whenever the predictor cannot be uniquely inferred from the context, we still write (y.
We drop D if it can be directly inferred. For example, in the specific case of the 0-1 loss, (0, [0 10-1) and (1, t) - 11- f/.
and the expected loss Ele+ (y, h(x))] is equal to the rate of false positives and E[e_ (o.l.y..... [x))] to the rate of false negatives. The sum of losses e + f- corresponds to the usual definition of error of the predictor.
turn, E generalizes the definition of the abstention rate of predictor [Ep[1] [x(x) [x) = ? The case where (vy) = a for any constant a >> 0 corresponds
to the traditional Chow model [22 41. Note that we allow different abstention costs depending on whether the corresponding label is 0 or y 1.
Definition 2.3 (Triplet of loss functions). Given a family of loss functions C, each loss function E e C {R U {?}} + I induces the triplet of loss functions (f+, l_ (T), where (t) (0, t) and l- (t) = (1,1 t) for all t * ?. and Er(y) = (y t) for all = ?
We directly use the notation (L+,e_,
L. When we consider selective omnipredictors, will further associate weights (A, μ4, 1) with the triplet of loss functions (4+,e_,)); so that the total loss incurred by predictor is equal to Xe+ + pl- + vLg.
Allowing abstentions increases the reliability of non '?' predictions. The work most closely related to ours is the learning- theooreic framework of reliable agnostic learning. first proposed by Kalai, Kanade, and Mansour 43 which adapts the usual agnostic framework. While they introduced their definitions only for the case of the 0-1 loss, in our results we generalize their results to many more loss functions, and so we directly introduce the more general versions of their original definitions. Let EX(D) denote the example oracle which when queried returns (x, y) ~ D. Given concept class of Boolean concepts c: X + {0,1) and a distribution D, we further define the following concept classes from C [43]
C+ fEEC (c, 0},
C (cECCC]L 0).
Definition 2.4 (PRL for family of loss functions 43
45 ). A concept class C of Boolean concepts
C-positively reliably learnable if there exists learning algorithm that for any distribution D over X' x {0, 1}. any l,, f_ E L, and any 8 >> O, when given access to the example oracle EX(D), outputs hypothesis X + [0, 1] that satisfies the following with probability at least 6:
1. (lx+)))=((+(((x))))) e,
2. E(x,y)=l(_ (h(x)) < mine,ect EIxx))=D((((++xx)) +
The notion of L-negative reliable learning (NRL) is defined analogously, by switching the positives and the negatives (see the appendix for the full definitions).
Hence, in the case of the 0-1 loss, positive reliable classifier is one that almost never produces false positives, while simultaneously minimizing false negative errors, attaining rate comparable to the false negative error rate of the best classifier c C+ [45). Symmetrically, a negative reliable classifier is one that almost never produces false negatives while simultancously minimizing false positive errors, attaining a rate comparable the false positive error rate of the best c_ C
Given any Boolean c+ E C+ and c_ E C-, we ensemble them to construct a selective classifier Ca (-+,c_) as follows:
I if (4) = = (x) 1,
(x) = 0 cf =c (x)
? (x) (z)
We then let SC(C)= = ((ct,c)) c-) c_ CCt.c- E C-} (for "selective clasifiers"). This ensembling provides a natural way for adding abstentions to the base class C. We can now define fully reliable learning using the base class SC(C):

---

Definition 2.5 (FRL for a family of loss functions). A concept class C of Boolean concepts is L-fully reliably learnable if there exists a learning algorithm that for any distribution over X x {0, 1}. any f,,-_ Lr E f. and any 6, 8 > O, when given access to the example oracle EX(D), outputs hypothesis h X - [0, 1] (?) that satisfies:
(xx,))= [ (1z (x)) + &- (lv(())) s.
2. E(x (y, hy (x)) & mino; (xx,y)>ollr(y, cx(x)) +c.
For the specific case where L corresponds only to the 0-1 loss, Kalai, Kanade, and Mansour showed that if C is efficiently agnostically learnable, then C is also efficiently C-reliable learnable, all for PRL, NRL, and FRL [43]
2.4 Generalized Chow model
In the original Chow abstention model, the predictor can choose to abstain at a fixed cost of 2 0 [1]. The goal the predictor is to learn how choose real-valued predictions and abstentions as to minimize the total loss. We generalize and formalize this model with what we call the generalized Chow loss function:
Definition 2.6 (Generalized Chow loss), Given a triplet of loss functions ((+,_,6) induced by :: y {R U U{?)} + with associated weights (A, (. 2/,, where + f + v S 1, and selective classifier h? X + {?}. the generalized Chow loss incurred by h is equal to
(oc,
[A4+ (h(x)) pll (h(x)) + vl:
(x.Y)~>
One can include randomized predictors h to this definition (where h assigns probability of abstaining to each x E X);; however, as we show in the appendix (Section C.I), randomization does not help in minimizing the generalized Chow loss function.
2.5 Selective omniprediction
In our work, we extend the omniprediction framework the setting of selective classification.
In the next section, we show that we can efficiently build a (C, C, e) -multigroup selective omnipredic- tor that optimally minimizes the generalized Chow loss of any triplet of loss functions (L+, Ex) induced by any E C. We then use this result to show how to efficiently build C-FRL classifiers, generalizing the main result of [43].
Definition 2.7 (Selective omniprediction). Given a concept class C on X, distribution D, c > and a class of loss functions L, we say that a predictor h X + [0, 1] is (C, C, c,)),,eleettive omnipredictor for every (L,,k_, bz) E L and any associated weights (A, u,,)), v), there exists a function k e [0, - IR U (?) such that for any post-processing function k; [0. + R R (?).
(kc,D h; u)
min c.
(oc.p(esiA
Importantly, as in the original omniprediction framework, the optimal classifier oz in k C is tailored to the specific triplet of loss functions, whereas h is a single classifier for all of L and (X, (,,) v).
3 Building Selective Omnipredictors
The key idea in the omniprediction learning framework is to first learn model f that is (C, c)- computationally indistinguishable from f*, which is accomplished through the technique multical- ibration, and then apply post-processing function kü once loss function / E L has been fixed. In our setting of selective classification, we similarly use the following post-processing function that minimizes expected loss under the Bernoulli distribution. which we show yields an optimal final loss:
Definition 3.1. Given loss functions (L,, Lz,)) and corresponding weights (X, μ, v), let the function kt ke [0, 1] + R U {?} be defined as
kig (p) arg min mi)
[Ae+(t) + pl- (t) +x>())]
y-BBer(p))
(ue_(1) + voc+) + (1 11 p) (Je+ + va-).
= arg min min P.
5

---

Our main result in this section is the feasibility of efficiently constructing selective classifiers:
Theorem 3.1 (Constructing selective omnipredictors), Let be a concept class of concepts e X [-M, MI, D distribution on X'x (0, 1}, é > O, and f. a family loss functions with associated weights (x.p. u) with À ++ + u S 1, such that all E L. are B-Lipschitz. Then, a (C, e) mamliicalibbre predictor is (L, C, 4eB B) -selectvee omnipredicior, where is an absolute bound on f.p e, lg.
The full proof of Theorem 3.1 is deferred to the appendix; here we provide a proof sketch.
Proof sketch of Theorem 3.7 Our algorithm first constructs a (C, c)-multicallibatee predictor h. For
each specific choice of (L+.L_,)) E L and weights (A, μ. v), we apply the post-processing function ki__,, h. We show that the generalized Chow loss incurred by ki E (within an é slack) than that incurred by the best classifier in l C, where A : [0, 1] - R U (?) is any post-processing function adding abstentions. We outline why this is an optimal and efficient strategy.
is no more
Following the generalized Chow loss expression (Definition 2.6 for each t E R, we either pay the cost of predicting, whose expected value we denote by Kireed or the cost of abstaining, whose expected value we denote by Kabs:
1E Kpred (p) minn P. pl- + (1 -t)()t))
Kabs (p) = v(p (7(1) - (1- (0)) (ppp at + (1-p)
For each point p. in order to minimize the expected generalized Chow loss under the Bernoulli distribution, we proceed in two steps: (1) Find the value 1" (p) that minimizes the value of Kpred (p) given a fixed value of p. This depends only on the choice of X, f.,,,,,, h. and not on the underlying data. Specifically, this corresponds to finding the value 1" (p) that minimizes the function k (p). where
k& (p) argmin, Be-no)))))) [X++ (y,t) + (y, t) (2) For each predicted value h(x) p. then map it to either t" (p) or to "?' depending on whether it is cheaper to predict or to abstain; that is,
depending on the value of min (ain((ppn (rep (t" (p)), (p))
In other words, we can re-write our post-processing function e as kiats o kÿ, where
{1" {
if Kprodd S. Kabs:
kabe
if Ripred > Rabs-
Then, the value of ke_,,, can be computed efficiently because (1) computing the value of Kipred (p) corresponds to solving a one-dimensional minimization problem, and (2) the value of kig,e, is then fully determined from the values of Kprea (p)) and of Kabs To show optimality, we consider the level set ((r.) {z E X h(z)) P, 7 for each p E range(h) and each y in the range of c. For each set (p-r), we split the proof into cases, depending on whether h and e abstain or predict per their respective decision rules. The key idea is that, even though the concept abstains or predicts using an arbitrary decision rule, multicalibration ensures that the expected value y on X(,,>) is approximately p. which allows us show that k2_,,, (h) incurs more loss than k o c.
Interval of abstention. We further show the following about the points where kZ h abstains:
Lemma 3.2. Given any loss functions C+, l- by E C, the points x E R such that ki (x) = =?form a contiguous interval, which we denote by Tabs-
This follows from the fact that (p) concave as a function of p. and that Kaba (p) is affine in Lemma (.2u does not require the loss functions to be convex; only affine in p. Importantly, note that we can determine Laks directly from the chosen triplet of functions (L,,e_,6) E7), without any dependence on the underlying data. This is why our method is highly efficient: once we run the multicalibration algorithm, we directly apply our off the-shelf post-processing function ke
3.1 Selective omniprediction in action
While our results are of theoretical nature, we provide experiments demonstrate the feasibility of selective omniprediction in practice and to provide some concrete examples of the function kū__0, for specific choices of triplets of loss functions (f+, Lz).

---

We generate synthetic data to create binary classification problem with n = 10,000 samples and implement the multicalibration algorithm to baseline predictions to obtain a C- C-multicalibrated predictor h, where we set C to be the concept class C of decision trees of depth 3. For various choices of loss functions& e = (4+,e_ -,, fe), we compare the coverage (i.e., the fraction of the points in the domain on which the predictor does not abstain) and total loss of our post-processed _ & o h predictor (where +,,;; is chosen for each é but / is the same predictor across all loss functions) with that of predictor optimized specifically to minimize the generalized Chow loss function, using the same base concept class of decision trees of depth 3. The bar plots show the points p E [0, 1] where k2,,e; o h abstains for different triplcts of loss functions, indicated in the caption of each subfigure. We compute abs theoretically for each of these triplets, independently of the data (see caleulations in the appendix): in Figure | one can see that these are indeed the regions where our algorithm abstains in practice. Table [
shows the final loss and coverage incurred by our single selective omnipredictor (post-processed accordingly) compared to those obtained by each of the decision trees, which are trained separately for each of the triplet of loss functions. The full details of the experimental set-up along with further examples and repetitions can be found in the appendix.
Aloiention tikcemkopp redmadodai))
Alodutiion (olawrkesp, rodmalaiiit)
MC L1 Abstertian reaightec)
06
06
3.5
1.0
04
9.2
0.4
0.
00
1.
4+ = f- = l, 0.1,
2+ = E-
l, 0.2,
f, (1) = 0.3, Ex( = 0.1,
Tabs = [0.1,
Jabs = (..2.
Jabs = 10.125, 0.75].
Abstertion Ib e-keop. red-abstair)
Abstemtion (blue=keep, red=abstain)
MC Abstention iemegntec)
D4
0.1 Pirk procosodd re..kacttrrot probitoon
Mi
1.2
Pook oucood meliis deulld
Eg, E7
0.1,
E2, E 0.2,
l2, (1) = 0.3, (0
= 0.1.
Tabs
V0.6
1+v06
Jabs
1- 0.22
1+
Jabs =
4- 4+
2
10
10
Figure 1: Final loss and coverage incurred by our single selective omnipredictor, post-processed with 1 for each of the specific triplets indicated in the subfigure caption. Red: abstain. Blue: predict.
Table 1: Comparison of coverage and losses. "Cov" stands for coverage, "Pred" for predicted loss (i.e., over the non- non-abstaining region), and "Total" for the total generalized Chow loss.
l 0.1
t 0.2
& 6x 0.3, (x) = 0.1
k24.00 8g
o
Abst. DT
k .gg h
Abst. DT
k2_ .e, h
Abst, DT
Cov: 22%
Cov: 2.3%
Cov: 52.70%
Cov: 3.8%
Cov: 42.90%
Cov: 2.5% Pred: 0.002
Pred: 0,045
Pred: 0.001
Pred: 0.083
Pred: 0.002
Pred: 0.058
81
Total: 0.088
Total: 0.098
8
Total: 0.1
Total: 0.194
Total: 0.144
Total: 0.198
Cov: 24.15%
Cov: 3.8%
Cov: 61.15%
Cov: 13.2%
Cov: 64.6%
Cov: 13%
Pred: 0.046
Pred: 0.001
Pred: 0.078
Pred: 0.010
Pred: 0.082
Pred: 0.0017
82
Total: 0.087
Total: 0.098
E2
Total: 0.125
Total: 0.183
&
Total: 0.122
Total: 0.193
3.2 Building general reliable agnostic learners & conformal prediction
We show how we can use our efficient construction of selective omnipredictors to recover and generalize the results on reliable agnostic learning obtained by (43 from 0-1 loss to an entire family of loss functions (as defined in Section 2.3
Theorem 3.3. Let C be concept class of Boolean concepts, L any class of B-Lipschitz loss functions, and D a distribution on X x Y. If C is agnostically learnable under in time T T(e, 8), then C is C-fully reliably learnable under D in time
7

---

Conformal prediction from FRL. Lastly, we demonstrate a useful application of the reliable agnostic learning framework. Specifically, we show that one can view FRL as conformal prediction method for the case of binary classification, where we view the (0, }} prediction set as "?"
In the classification setting, the goal of conformal prediction is to construct prediction set of the possible labels S(z) S y/ for each point I E X' such that Pr(xy)>-ly E S(x)] 2 for a chosen error rate c E (0. This is known as the e-marginal coverage guarantee. In the case of binary classification, the possible prediction sets can only be {0}, {1}, {0, 1]. We show the following:
Lemma 3.4. Let hy : X + 3 be an FRL predictor for C, D. e and the 0-1 loss. Then, the prediction sets induced by the level sets of h, where we map + {0), 1 + {1}, and ? {0, 1}. satissy the e-marginal coverage guarantee.
Remark 3.1. While any conformal prediction method must definitionally satisfy the e-marginal coverage guarantee, typical algorithms offer no theoretical bounds on the size of the prediction sets. In the case of binary classification, this means that we could have an arbitrarily large number of points mapped to {0, 1} (even the entire domain, which is trivial way of satisfying the marginal coverage guarantee). However, FRL does provide provable abstention guarantees with respect to base concept class C' of our choice. Let h2 X - {0, 1, ?} be an FRL predictor for the class C. 0-1 loss, and > 0, and let (0), {1), {0, 1 be its induced prediction sets as a conformal prediction method. Then,
(x) = {0, 1 (x-Y)D
Pr
min Pr (x) = ?] + ESC(C) (x,Y)>
We defer the proof in the appendix, where we also run experiments implementing FRI as a conformal prediction method.
4 Learning Abstentions Fairly
So far, we have considered the question of how to learn abstentions optimally, where we measure optimality in the agnostic sense, with respect base concept class C and generalized Chow loss function Égc. The motivation for abstaining is to be able to make almost no errors when predicting, which we can accomplish by mapping the uncertain points additionally have fairness concerns: suppose that we have a collection G {g X' + {0, 13} of subgroups of interest of the domain. Besides achieving high accuracy over the points where we do predict a numerical value, we would also like to abstain fairly on each of the groups g E G, so that we avoid achieving high global accuracy at the expense of overly abstaining on some subgroups. Motivated by the multigroup fairness framework, we also want the groups in G to be able to intersect.
'?" instead. However, we might
How can we measure how optimal abstention rate looks like within each of the groups g E g? Motivated by the reliable agnostic learning framework [43], we do so by requiring our predictor to abstain no more than the optimal selective classifier of SC(C) (with an e slack) on each group E G, where e) can naturally be different for each group. That is, similar to our notion of a selective omnipredictor, we want to construct a single classifier simultaneously for all groups, but its abstention rate competes with that of a c that is chosen optimally in each group. Formally, we introduce the following definition, which corresponds to the multigroup version of the original notion of realiable agnostic learning:
Definition 4.1 ((C, m)-multigroup selective classification). Given a collection of subgroups ς of X, concept class C, distribution D. and > O, we say that a predictor hy X + [0, 1] U (?) is (C, G, e) m)mlliiirou selective classifier if the following two conditions are satisfied:
1. Global accuracy. (Ir)) Exxy)~D(Ix hx(x)) [x)r(x) +?]] Se.
2. Optimal local abstention rate. For every g E G.
Pr (x.y)~D [g(x) (x) = ?]] S min Pr [9(x) [[c7(x) ?I] cc.
evEBC(C) (x,))D
Note that Condition 2 automatically implies an optimal global abstention rate as well, by applying the local condition with 1 (which we can assume is always contained in G). We remark that the multigroup fairness and omniprediction literature had so far always taken C = G: our notion demonstrates why it is useful to separate the base concept class C from the collection of groups G.
8

---

We show that we can efficiently construct (C, e.. mulliigru selective classifier for any C, 9 from a multiaccurate predictor for the class C. G {eg c C. E 9} that is also globally calibrated:
Theorem 4.1. Given access to (C g, ( multiaccrra and calibrated predictor, we can efficiently construct a (C, 9, m)mulrggrou selective classifier in time poly(1/c)-
The key idea in our proof is to convert a (C-G,e)-me muultiaaccerate and calibrated predictor h X + [0. 1] into selective classifier by mapping all such that h(z) (c, c) '?", For each group g. let of = (c] c² be an optimal selective classifier in SC(C) within g. Since cº E C+, it follows that whenever e = 1, the true label y on that point is also 1. By the multiaccuracy guarantee for ctt and (which is in C 9), we obtain that ID [y] R ED [x)) R 1 in the region where cq. (x) = 1, g.)))) 1. symmetric argument holds with c²_ and g. We use the global calibration condition to ensure that our thresholded h2 remains accurate in the entire domain.
It is natural to ask whether can efficiently construct (C, 9)-mlttgrrou selective classifiers starting from a weaker learning primitive than a weak agnostic learner for C G. We answer this question in the positive in the case where [g] is small:
Lemma 4.2. If the class is fully reliably learnable for the E loss and > O, we can construct a (C, m-ulligppg selective classifier in time poly([g), 1/ee with oracle access the full reliable learner for C.
Answering this question in generality (i.e., where G can be arbitrarily large) appears to be a very interesting open question.
Calibrated multiaccuracy and multicalibration. We make a further remark about how the various multigroup faireess definitions relate to selective classification (which we show in the appendix).
(a) If we have the stronger primitive of a (C- G) muulticcalibrated predictor (which implics a (C g)- multiaccurate calibrated predictor), then we can have a non-selective predictor which would also give local agnostic guarantees. This follows from the works of 25 10 27).
(b) Given a (C-G, c)- mulliaaccurate and calibrated predictor, we can directly obtain FRL predictors for the class C for the é loss by thresholding the predictor as we do in the proof of Theorem |. Given that calibrated multiaccuracy implies agnostic learning [1I]. it is already implied by Theorem 4. that we can achieve reliable agnostic learning from calibrated multiaccuracy. However, this approach gives direct reduction. Reliable agnostic learning is believed to be a weaker learning primitive than agnostic learning [45)
4.1 Conformal prediction from (C, -multigrruu selective classification
Similar to Section 3 we can view (C, 9) muultigrouu selective classification as a conformal prediction method in the case of binary classification. Besides the marginal coverage guarantee, now that we have a collection G of groups one can also hope to satisfy a conditional version of coverage. Namely, g(x) = 1] 2 1-6 e. This property is
for every g E G, we want to satisfy PIxx.y)>Dyy S(x) known the (G, c)-gruu conditional coverage guarantee (39] We show that (C, (C, -uultirruuu
selective classifiers do indeed satisfy this conditional guarantee:
Lemma 4.3. Let h. X [0, 1] U {?} be (C, mmmultiirroou selective classifier: Then, the prediction sets induced by the level sets of h, where we map (0. c - (0), - e, 1 - {1), and Prolg(x)=1] for all g E g.
(c,1-c) + 1) satisfy Pr(xx))-Dly E S(x)) 19(x)= = 1]
Remark 4.1. As pointed out in Section 3 typical conformal prediction methods offer no theoretical bounds on the size of the prediction sets. Through our framework of (C, 9) -m-ultigrruup selective classification, however, we do obtain provable abstention guarantees for each g E g with respect to a base concept class C of our choice. Specifically, for each G. the prediction sets of our (C, ((c.))mmuute multigroup selective classifier he as specified in Lemma 4.3 satisfy
Pr (x,y)>D
[9(x) [[b((x) = [0. 1H1] < min Pr (x.y)>
[c, = +
cx)3C(C)
Importantly, -m-ulligrruuu selective classification as a conformal prediction method ensures group conditional coverage and a provable abstention bound on each group even when these intersect.
In the appendix we implement (C, -multtigrru selective classifiers by adapting the multicalibration algorithm and demonstrate its utility conformal prediction method in practice.

---

Conclusion and Future Work
We conclude by providing some directions for future work.
The complexity of reliable agmostic learning. The first is concerned with the dependence on e when obtaining fully reliable learner from agnostic learning. In the of (44), they are able to learn PRI., NRL, and FRI. predictors for a concept class C in time T(O(c2)) using an agnostic learner for C that runs in time T()). In our case, when obtain fully reliable learners from selective onnipredictors in Theorem 3.3 in order to obtain a C-fully reliable learner with error e we require a selective omnipredictor with error e². appears that the nature of the two constraints in the definition of reliable agnostic learning (unlike the case of the generalized Chow loss formulation) induces this overhead, but is unclear whether is unavoidable.
Building selective omnipredictors. For our construction selective omnipredictors, we require the multigroup fairness primitive of multicalibration. For the case of regular omniprediction (i.e., without abstentions), recent works have shown that we can construct omnipredictors from the weaker primitive of calibrated multiaccuracy, and even with weaker notions of global calibration [26 [59]. Our proof of selective omniprediction seems to require the full power of multicalibration; is unclear whether relax it calibrated multiaccuracy, or whether can have direct reduction from omniprediction.
Weak agnostic learner for C G. Our construction of (C, m)mmltigrrup selective classifier in Section requires access to a (C m)-multiaccurate and calibrated predictor. From the works on multigroup fairness [26] 11. this in requires access to a weak agnostic learner for the class C G. We do not know whether it is possible to construct (...-)ligrooup selective classifiers having only access to separate weak agnostic learners for C' and G, without requiring weak agnostic learner for their intersection. This can be seen as broader question about the learnability of intersections of concept classes.
G)
we show that we can construct a (C. m)muttigrou selective classifier from fully reliable learner, which is believed to be weaker primitive than (weak) agnostic learning [45]. However, we are only able to show this for classes G that are small in size, given that we need to call the FRL oracle |g] times. Hence the question of whether we can build selective classifiers from a weaker primitive than agnostic learning for a general class G remains open.
Building selective elassifiers. In Lemma 4.2
Conformal prediction & model multiplicity. Lastly, in light of connections between reliable agnostic learning and (C, ()) selective classification with conformal prediction, it would be interesting develop this connection further, particularly focusing on the ability of these methods to provide provable guarantees on the sizes of the prediction sets beyond the setting of binary classification. It also appears fruitful study how our framework of learning with abstentions, where a predictor is able to measure its own reliability, relates to the recent works on model multiplicity.
Acknowledgments
We thank Michael Kim and Inbal Livni Navon for helpful pointers. We are grateful to the participants of the Workshop Predictions and Uncertainty COLT 2025 for valuable feedback. During the development of this work, SC was supported by a Rhodes scholarship.
10

---

References
[I] Gustaf Ahdritz, Aravind Gollakota, Parikshit Gopalan, Charlotte Peale, and Udi Wieder. Prov- able uncertainty decomposition via higher-order calibration. arXiv preprint arXiv:2412.18808, 2024.
[2] Junaid Ali, Preethi Lahoti, and Krishna P Gummadi. Accounting for model uncertainty in algorithmic discrimination. In Proceedings of the 2021 AAAI/ACM Conference on Al, Ethics, and Society, pages 336-345, 2021.
[3] Anastasios Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.075// 1, 2021.
[4] Tina Behzad, Silvia Casacuberta, Emily Ruth Diana, and Alexander Williams Tolbert. Reconcil- ing predictive multiplicity in practice. In Proceedings of the 2025 ACM Conference on Fairness, Accountability, and Transparency, pages 3350-3369, 2025.
[5] Umang Bhatt, Javier Antorán, Yunfeng Zhang, Q Vera Liao, Prasanna Sattigeri, Riccardo Fogliato, Gabrielle Melançon, Ranganath Krishnan, Jason Stanley, Omesh Tickoo, al. Un- certainty as form of transparency: Measuring, communicating, and using uncertainty. In Proceedings of the 2021 AAAI/ACM Conference Al, Ethics, and Society, pages 401-413, 2021.
[6] Emily Black, Klas Leino, and Matt Fredrikson. Selective ensembles for consistent predictions. arXiv preprini (eXxi:2111.082.000 2021.
[7] Emily Black, Manish Raghavan, and Solon Barocas. Model multiplicity: Opportunities, con- cerns, and solutions. In Proceedings of the 2022 ACM Conference Fairness, Accountability, and Transparency, pages 850-863, 2022.
[8] Emily Black, John Logan Koepke, Pauline Kim, Solon Barocas, and Mingwei Hsu. Less discriminatory algorithms. Available at SSRN, 2023.
[9] George EP Box and George C Tiao. Bayesian inference in statistical analysis. John Wiley & Sons, 2011.
[10] Sílvia Casacuberta, Cynthia Dwork, and Salil Vadhan. complexity-theoree implications of multicalibration. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1071-1082, 2024.
[11] Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, and Omer Reingold. How global calibration strengthens multiaccuracy. arXiv preprint arXiv:2504. /5206, 2025.
[12] Chi-Keung Chow. An optimum character recognition system using decision functions. IRE Transactions on Electronic Computers, (4):247-254, 1957.
[13] Feder Cooper, Katherine Lee, Madiha Zahrah Choksi, Solon Barocas, Christopher De Sa, James Grimmelmann, Jon Kleinberg. Siddhartha Sen, and Baobao Zhang. Arbitrariness and social prediction: The confounding role variance in fair classification. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 22004-2200 2024.
[14] Gianluca Detommaso, Martin Bertran, Riccardo Fogliato, and Aaron Roth. Multicalibration for confidence scoring in llms. arXiv preprint arXiv:2404 04689, 2024.
[15] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012.
[16] Cynthia Dwork, Michael P Kim, Omer Reingold, Guy N Rothblum, and Gal Yona. Outcome indistinguishabiiity. In Proceedings of the 53rd Anmual ACM SIGACT Symposium on Theory of Computing, pages 1095-11000 2021.

---

[17] Cynthia Dwork, Daniel Lee, Huijia Lin, and Pranay Tankala. From pseudorandomness to multi-group fairness and back. In Gergely Neu and Lorenzo Rosasco, editors, The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pages 3566-3614, PMLR, 2023. mlr. press/ /aaass/v199 w19. dwokkw33233a...mmmmm html
[18] Cynthia Dwork, Omer Reingold, and Guy N Rothblum. From the real towards the ideal: Risk prediction in a better world. In 4th Symposium on Foundations of Responsible Computing (FORC 2023). Schloss Dagstuhl-Leeinni-zZennne
für Informatik, 2023.
[19] Ran Yaniv et al. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 11(5), 2010.
[20] Vitaly Feldman. Distribution-speciff agnostic boosting. arXiv preprint arXiv:0909.2927,, 2009.
[21] Yarin Gal and Zoubin Ghahramani. Bayesian convolutional neural networks with bernoulli 2015.
approximate variational inference. arXiv preprint
[22] Surbhi Goel, Steve Hanneke, Shay Moran, and Abhishek Shetty. Adversarial resilience in sequential prediction via abstention. Advances in Neural Information Processing Systems, 36: 8027-8047, 2023.
[23] Shafi Goldwasser, Adam Tauman Kalai, Yael Kalai, and Omar Montasser. Beyond perturbations: Learning guarantees with arbitrary ad adversarial test examples. Advances in Neural Information Processing Systems, 33:15859-15870, 2020.
[24] Aravind Gollakota, Parikshit Gopalan, Adam R Klivans, and Konstantinos Stavropoulos. Ag- nostically learning single-index models using omnipredictors. arXiv preprint arXiv:2306.10615. 2023.
[25] Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredictors. arXiv preprint arXiv: (tth::2009.55000 05389, 2021.
[26] Parikshit Gopalan, Lunjia Hu, Michael P Kim, Omer Reingold, and Udi Wieder. Loss mini- mization through the lens of outcome indistinguishabiiiyy. arXiv preprint arXiv:2210.086499, 2022.
[27] Parikshit Gopalan, Michael Kim, and Omer Reingold. Swap agnostic learning, or characterizing omniprediction via multicalibration. Advances in Neural Information Processing Systems, 36, 2024.
[28] Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Sherry, and Mihir Singhal. Omnipredictors for regression and the approximate rank of convex functions. In The Thirty Seventh Annual Conference on Learning Theory, pages 2027-2070. PMLR, 2024.
[29] Dutch Hansen, Siddartha Devic, Preetum Nakkiran, and Vatsal Sharan. When is multicalibration post-processing necessary? arXiv preprint arXiv:2406. 2tl.:24060004887,, 2024.
[30] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
[31] David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and Computation, 100( (1):71111500 1992.
[32] Ursula Hébert-Johnson Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the coompuattinally--deeiiaat masses. In International Conference on Machine Learning, pages 1939-19999 1948. PMLR, 2018.
[33] Maria Heuss, Daniel Cohen, Masoud Mansoury, Maarten de Rijke, and Carsten Eickhoff. Predictive uncertainty-base based bias mitigation in ranking. In Proceedings of the 32nd ACM International Conference Information and Knowledge Management, pages 762-772, 2023.
[34] Lunjia Hu and Charlotte Peale. Comparative learning: A sample complexity theory for two hypothesis classes. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), 2023.
12

---

[35] Lunjia Hu, Inbal Rachel Livni Navon, Omer Reingold, and Chutong Yang. Omnipredictors for constrained optimization. In International Conference on Machine Learning, pages 13497- 13527. PMLR, 2023.
[36] Junqi Jiang, Antonio Rago. Francesco Leofante, and Francesca Toni. Recourse under model multiplicity via argumentative ensembling. arXiv preprint arXiv:2312.15097 2023.
[37] Erik Jones, Shiori Sagawa, Pang Wei Koh, Ananya Kumar, and Percy Liang. Selective classifi- cation can magnify disparities across groups. arXiv preprint arXiv:2010. 14134, 2020.
[38] Christopher Jung. Changhwa Lee, Mallesh Pai, Aaron Roth, and Rakesh Vohra. Moment multicalibration for uncertainty estimation. In Conference on Learning Theory, pages 2634- 2678. PMLR, 2021.
[39] Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Batch multivalid conformal prediction. arXiv preprint arXiv:2209. /5/4, 2022.
[40] Patrick Kaiser, Christoph Kern, and David Rügamer. Uncertainty-awan aware predictive modeling for fair data-driven decisions. arXiv preprint arXiv:2211.02773) 2022.
[41] Adam Kalai and Varun Kanade. Towards optimally abstaining from prediction with ood test examples. Advances in Neural Information Processing Systems, 34:12774-12785, 2021.
[42] Adam Tauman Kalai and Varun Kanade. Efficient learning with arbitrary covariate shift. In Algorithmic Learning Theory, pages 850-864. PMLR, 2021.
[43] Adam Tauman Kalai, Varun Kanade, and Yishay Mansour, Reliable agnostic learning. Journal of Computer and System Sciences, 78(5): 1481-1955, 2012.
[44] Varun Kanade and Adam Kalai. Potential-based agnostic boosting. Advances in neural information processing systems, 22, 2009.
[45] Varun Kanade and Justin Thaler. Distribution innpputiiiniiddeeeeeetne reliable learning. In Conference on Learning Theory, pages 3-24. PMLR, 2014.
[46] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerryman- dering: Auditing and learning for subgroup fairness. In International Conference on Machine Learning, pages 2564-2572. PMLR, 2018
[47] Michael Kearns, Robert E Schapire, and Linda M Sellie. Toward efficient agnostic learning. In Proceedings of the fifth annual workshop on Computational learning theory, pages 341-352, 1992.
[48] Christoph Kern, Michael Kim, and Angela Zhou. Multi-cate: Multi-accurate conditional average treatment effect estimation robust to unknown covariate shifts. arXiv preprini arXiv:2405. 18206, 2024.
[49] Falaah Arif Khan, Denys Herasymuk, and Julia Stoyanovich. On fairesss and stability: Is estimator variance a friend or a foe? arXiv preprint arXiv:2302.04552 2023.
[50] Michael P Kim, Amirata Ghorbani, and James Zou. Multiaccuracy; Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 247-254, 2019.
[51] Daniel Lee, Georgy Noarov, Mallesh Pai, and Aaron Roth. Online minimax multiobjective opti- mization: Multicalibeating and other applications. Advances in Neural Information Processing Systems, 35:29051- 2022.
[52] Joshua K Lee, Yuheng Bu, Deepta Rajan, Prasanna Sattigeri, Rameswar Panda, Subhro Das. and Gregory W Wornell. Fair selective classification via sufficiency. In International conference on machine learning, pages 6076-6086. PMLR, 2021.
[53] Carol Long, Hsiang Hsu, Wael Alghamdi, and Flavio Calmon. Individual arbitrariness and group faimeess. Advances in Neural Information Processing Systems, 36, 2024.
13

---

[54] Carol Xuan Long, Hsiang Hsu, Wael Alghamdi. and Flavio P Calmon. Arbitrariness lies beyond the aairurss-accuracy frontier. arXiv preprint (Xiv:2306.0942555 2023.
[55] Philip M Long. On agnostic learning with {0,* 1]-valued and real-valued hypotheses. 14th Annual Conference on Computational Learning Theory, volume 14, page 289. Springer Science Business Media, 2001.
[56] Cassandra Marcussen, Aaron Putterman, and Salil Vadhan. Characterizing the distinguishability of product distributions through multicalibration. arXiv preprins arXiv:2412.03552, 2024.
[57] Charles Marx, Flavio Calmon, and Berk Ustun. Predictive multiplicity in classification, In International Conference on Machine Learning, pages 6765-6774. PMLR, 2020.
[58] Georgy Noarov and Aaron Roth. The statistical scope of multicalibration. In International Conference on Machine Learning, pages 26283-26310. PMLR, 2023.
[59] Princewill Okoroafor, Robert Kleinberg, and Michael Kim. Near-optimal algorithms for omniprediction. arXiv preprint arXtv:2501.17205, 2025.
[60] Aaron Roth, Alexander Tolbert, and Scott Weinstein. Reconciling individual probability forecasts. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Trunsparency, pages 101-110, 2023.
[61] Guy N Rothblum and Gal Yona. Multi-group agnostic pac learnability. In International Conference on Machine Learning, pages 9107-9115, PMLR, 2021.
[62] Nicolas Schreuder and Evgenii Chzhen. Classification with abstention but without disparities. In Uncertainty Artificial Intelligence, pages 1227-1236. PMLR, 2021.
[63] Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008.
[64] Anique Tahir, Lu Cheng, and Huan Liu. Faimess through aleatoric uncertainty. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pages 2372-2381, 2023.
[65] Vianney Taquet, Vincent Blot, Thomas Morzadec, Louis Lacombe, and Nicolas Brunel. Mapie: an open sperce library for distribution-fred uncertainty quantification (2022). arXiv preprint arXiv:2207.1221 02000...2220 12274, 2022.
[66] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29. Springer, 2005.
[67] Tongxin Yin, Jean -ran-Françiis Ton, Ruocheng Guo, Yuanshun Yao, Mingyan Liu, and Yang Liu. Fair classifiers that abstain without harm, arXiv preprint 1XXx:2310006605, 2023.
14

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA]-
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1 (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked While "[Yes] " is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providded a proper justification is given (e.g., "error bars expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
the checklist one of the factors in their evaluation.
reported because it would be too computationally
"[No] " or "[NA] is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best, judgment and write justification elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All mathematical proof's of our formal claims are in the appendix. These are complete and fully formal. We also place our paper correctly within the current literature. We provide full details of our synthetic data experiments in the appendix, as well as the code that we used to run them.
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 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 as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
15

---

Answer: [Yes]
Justification: We provide a limitations section in the appendix and provide directions for future work and open problems.
Guidelines:
The answer NA means that the paper has no 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 sele--pecfiicaion. 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 with few runs. In general, empirical results often depend on implicit assumptions, which should be 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, a worse outcome might be that reviewers discover limitations that aren't acknowledged in 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 proof's
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification:
We provide full mathematical proof for all our results.
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 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 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: We provide all of our code and explain the choice of parameters, etc. in the appendix. Thus our code is fully reproducible.
16

---

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 urchitecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it 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 to replicate the results, access to a hosted model (e.g., in the case of 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) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model limited in some way (e.g., 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 faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We directly provide the Python code that we use for our experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
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 NeurIPS code and data submission guidelines (https
www.obiiiiiiioooooooiiooo 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.
17

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All of these details are provided in our appendix.
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 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]
Justification: tency.
We provide repetitions of all of our experiments and demonstrate its consis-
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 clearly stated (for example, train/test split, initialization, random drawing of some parameter, or 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but 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 of 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 are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
We provide all this information in our appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
18

---

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 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We have read the code of ethics and confirm that our paper conforms to it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in 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]
Justification: Not only does paper discuss the societal impacts of our work, it is fully motivated by it. We study selective classification with the motivation of ensuring reliability of predictions, which is crucial to ensure particularly in sensitive applications. The second half of our paper is concerned with providing algorithms that provably abstain fairly within each subgroup of interest. Our work is fully placed within the algorithmic faimess literature.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 out that 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.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
19

---

Answer:
[NA]
Justification:
We only run self-contained experiments with synthetic data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 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 releasing unsafe images.
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
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We credit any packages and works that we have used in producing our code.
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 the asset used and, possible, include URL.
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 re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not provide assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codeemoodll 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 an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
20

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We do not have crowdsourcing experiments or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, 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
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 the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: Not applicable to our work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on 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 as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification:
We fully detail how we used LLMs in producing our code in the appendix.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.MM policy fbttps://neuria ce cc//oomfereeccee/222/1111 for what should or should be described.
21

---

A Related Work
In recent years, there has been an increasingly close examination of algorithmic predictions, particu- larly when used in high-stakes settings. Most of these close examinations have focused on studying the potential biases present in these predictions, such as in the development of individual and group fairness notions [IS] 30). Another prominent example is the recent line of work on multigroup fairness, which aims to detect and avoid unwanted forms of bias on the outputs of a predictor h that maps individuals in domain X' to values in [o. 1], where the biases are measured with respect to class G of subgroups of the population that can intersect (32 50].
However, we also need to study the reliabilty of the predictions made by h. Some recent works have put forth the necessity of accounting for uncertainty in the setting of algorithmic fairness 2 40
54 49 53 13), but this question remains largely understudied. A major application of these
notions is in learning theory through the new learning paradigm of omniprediction [24 27 16 18 17. Multigroup fairnes notions can be understood as providing computational indistinguishabilit guarantees, formalized through the Outcome Indistinguishabiiiy framework [16] and follow-up
works 10 56 I1 which helps provide intuition for why they are well-suited as a method to add abstentions, as we do our work. Recent work on calibration uses higher order calibration as a way to decompose the predictive uncertainty of a model into aleatoric and epistemic components II.
We remark that other works on multicalibration and omniprediction do not separate C' and G classes, which we do in this paper.
Selective classification.
The idea of building algorithm that abstains certain individuals is not new and has traditionally been called selective classification 19]. A selective classifier is allowed to also return ? an output (which indicates abstention), along with the usual numerical values. In the setting of fairness, some works have studied the effect of selectively abstaining. Jones et al. find that certain forms of selective classification can magnify disparities across groups [37], and follow-up works try to restrict this type of disparities [52 62 67 Abstentions in learning have also been used
to provide bounds on efficient learning in the presence of arbitrary covariate shifts 42 23 22
and in the introduction of partial hypotheses classes (55 34].
Bayesian approaches & Conformal prediction. Another major approach for the task of uncertainty quantification is that of Bayesian inference. These methods place distributions over the model parameters, and build a model by iteratively updating the prior with new data in order to obtain the posterior through an application of Bayes rule [9] For training neural networks in a way that also allows for quantifying uncertainty, incorporating these techniques yields the so-called Bayesian Neural Networks (BNNs) (21). Some fairness works that are also concerned with incorporating uncertainty have used BNNs in the context of fair prediction (5 methods tend to be very slow and largely intractable.
33 64
However, Bayesian
An alternative to Bayesian-based approaches that is gathering growing popularity is that of conformal prediction, first proposed by by Gammerman, Vovk, and Vapnik [66] 3] Conformal prediction is technique for determining precise levels of confidence which can be applied to any method that has already been trained on the data [63]. Instead of a point- prenitpreiitiion (e.g., 0.8 for individual r). with conformal prediction the algorithm on that prediction. The wider the interval, the lower the confidence and the higher the uncertainty. Some recent works have extended the conformal prediction setting to provide conditional guarantees instead of only marginal guarantees by adapting the multicalibration algorithm (38 33)
can also return a prediction interval that indicates the confidence of
Reliable learning. Still, none of the previous works studies abstention from theoretical perspective. In the formal setting of learning theory, the study of selective classification was initiated in 2009 by Kalai, Kanade, and Mansour, who called it "reliable learning" [43]. How can we come up with formal model of classifiers that abstain, what does mean to "abstain optimally"" and how can we learn such classifiers?
The authors answer this by adapting the original agnostic learning framework 31 to what they call agnostic reliable learning. Here, the goal is to output selective classifier whose accuracy nearly matches the accuracy the best selective classifier from a pre-specified concept class. [43 show that if a concept class C is agnostically learnable, then it is also agnostic reliable learnable. In the other direction, due to follow-up work by Kanade and Thaler it widely believed that reliable agnostic learning is casier than agnostic learning (45).
22

---

PQ-learning and Chow's 's model of abstention. In 2020, Goldwasser, Kalai, Kalai, and Montasser presented a model of learning meant tackle the covariate shift problem, in which the training data is distributed according to P and the test data according to Q. where P and Q can be arbitrary distributions over the domain X' [23]. This form of learning is not possible to achieve in general, given that P and Q might not even overlap.
To make this problem tractable, Goldwasser et al. introduce the model of PQ-learning, where the learner has access to unlabeled test examples from Q and the option to abstain on any point æ E X. We compute the rejection rate 61 of the algorithm (i.e.. the fraction of X over which the classifier abstains) and the misclassification rate 62, which quantifies the error of the classifier only over the subset of the domain on which the classifier does not abstain. Goldwasser et al. give algorithms for building selective classifiers in the PQ-learning model which guarantee low test error rate and low rejection rate with respect to P for concept classes of bounded VC dimension [3]. Their algorithm is efficient if we have access to an Empirical Risk Minimizer (HRM) for C. For classes C of bounded VC dimension, being able to do ERM efficiently is equivalent to proper agnostic learning 42)
In follow-up work, Kalai and Kanade then showed that PQ-learning is equivalent to reliable learning. Moreover, they provide further evidence that the computational hardness of PQ-learning and reliable learning lies in-between PAC and agnostic learning (under the usual hardness assumptions) 42). This separation was already shown by Kanade and Thaler, who gave an algorithm for reliably learning majorities over {0, 1 in time 20(V0) whereas there are no known agnostic learning algorithms for this problem that run in time less than 20(() 45
In another follow-up work, Kalai and Kanade consider a different formulation of the selective classification problem considered by Goldwasser et al., which is based on the slightly different and more general framework of Chow's abstention model [12]. Here, instead of finding trade-off between error rates E1, E2, we have a fixed parameter a > 0 which corresponds to the abstention X, we either make a prediction ý and suffer loss Ely. 9)
cost. Le., for each abstain and pay a price of a. Importantly, this is a stronger model than PO-learning/reliaen given that they are able to by-pass the lower bounds shown in (23). For this reason, in this paper prove our main results using (a generalized version of) Chow's 's abstention model, given that it is the strongest of the three formal learning with abstention models.
5). or learning.
Multigroup fairness and omniprediction. In recent years, the algorithmic fairness literature has developed a rich line of work on multigroup fairness notions, with applications to the covariate shift problem, complexity theory, causal inference, the model multiplicity problem, and conformal
prediction, among many others 332 29
48
51
58 60)
A major application of these notions is in learning theory through the new learning paradigm of omniprediction (24] 17) Multigroup fairnes notions can be understood providing computational indistingushaabiltyy guarantees, formalized through the Outcome Indistinguishabilit framework [16] and follow-up works [00, which helps provide intuition for why they are very well-suited as method to add abstentions, as we do in our work. Recent work on calibration uses higher order calibration as way to provably decompose the predictive uncertainty of a model into aleatoric and epistemic components
Variance and predictive multiplicity. Some works that studying the reliability of predictors focus on the predictive multiplicity problem. which is concerned with the following fact: for given fixed dataset, there are multiple ways in which we can train a predictor on the dataset such that it achieves high accuracy, but these various potential and equally good predictors can then disagree on individual predictions [7]. Various metrics have been proposed for quantifying the variance of the predictions within the class M [57], and various algorithms have been proposed for ensembling these various competing models in different ways 6 60 4)
Several works have studied the relationship between the variance within the class M and group fairness metrics [54
53 49 36 Notably, following this variance approach, Cooper et al. find that we can obtain close-to-fair predictions simply by abstaining on the individuals with high variance 13. A drawback of these variance-baae based methods is that they require fitting an entire class M of models.
23

---

B Deferred Definitions
B.1 Reliable agnostic learning
The framework of reliable agnostic learning was first proposed by Kalai, Kanade, and Mansour for the case of zero-one loss [43] In the main body, we generalized the definitions to a family of loss functions L. Here, we state the original definitions for the 0-1 loss, which help grasp the notions of PRL, NRL, and FRL. We first recall the usual definitions of the error, false positive rate, and false negative rate of a predictor h in the case of 0-1 loss and for Boolean labels y = {0, 1}.
err(h, D) = Pr [l(x)= + yy),
(x-y)
falsc+ (h. (x,y)
Pr lo(x) 1 A 0].
false 1aase-(h,777 (h. = Pr lc(x) 0 A 1]. (x,y)=/D
Note that err(h, D) = false+ D)) + false- (), D). We drop the distribution D when it can be inferred from context, and sometimes write errp (h) for err(h, D).
Definition B.1 (Positive Reliable Learning (PRL.) 43 ). A concept class C of Boolean concepts is positive reliably learnable if there exists learning algorithm that for any distribution D over X' x (0.1) }}, any é, >> 0, with access to the example oracle EX(D), outputs a hypothesis h X ->
{0, 13 that satisfies the following with probability least 1 6,
1. false+ (h, D) S.
2. false_ (h, D) < mine, EC+ false_ (c4s D) + e, where C+ = {c E C false,, (c. (c = -0--
Symmetrically, we have that:
Definition B.2 (Negative Reliable Learning 433 A concept class C of Boolean concepts is negative
reliably learnable if there exists a learning algorithm that for any distribution over X x {0, 1}. any Ō >> O, with access to the example oracle EX(D), outputs hypothesis h X + {0, 1) that satisfies the following with probability at least 8,
1. false- (h, D) S e, and
2. false+ (h, D) < EC-(D) false. () where C- = {c E C false- (c. D) = 0}.
Full reliability, Both PRL and NRL are non- con-selective classifiers; the hypothesis h in the definitions of PRL and NRL map from X' to {0. 1}. But if we want both the positive and the negative rates to be low (i.e., for the total error to be low), then this is not possible unless we allow for ? to be in the range of l as well. Recall the definition of the class SC(C) derived from the concept class C (Section 2.3) By the definitions of C+ and C-, note that all concepts in SC have error over the non-abstaining region.
We further define the uncertainty ?(v D) and accuracy acc(hy, D) of a Boolean selective classifier by as follows:
?l,,, D) E (x [h(x) = ?].
acc(h,, D) = E (x,y)>
[1 (x) = 0] (1 -yy) y) + (x)x = 1].
One can see that err (h,, D) + ?h,,, D) + aco(h,, D) =
Full reliable learning is then defined as follows:
Definition B.3 (Full Reliable Learning (FRL) 43 A concept class C of Boolean concepts is fully reliably learnable if there exists a learning algorithm that for any distribution D over x {0, 1}, any e, > O with access to the example oracle EX(D), outputs a selective classifier by : X - {0, 1, that satisfies the following with probability at least 8,
1. crr(h,, D) false4 (he, D) + false (hr, D) S
2. acc(h2, D) 2 eo(() acc(c?, D)
24

---

Alternatively, using the fact that err(h D) + ?h?, D) + acc D) = 1, we can write the FRL definition with the formulation used [45] where Condition 2 expressed in terms of the abstention rate rather than in terms of accuracy. Indeed, we can equivalently define FRI. as follows:
Definition B.4 (Full Reliable Learning (FRL) 43 A concept class C of Boolean concepts is fully reliably learnable if there exists a learning algorithm that for any distribution D over X {0. 1), any é > O, with access to the example oracle EX(D). outputs a selective classifier h : X + (0,1,?}.
that satisfies the following with probability least 1 - 6,
1. err(h,, D) = false+ + (h2, D) + false (hv,, D) SC
2. ?(h,, D) v ess ?(cz, D) +..
When instantiating our generalized definitions (Section 2.3 to the case of the 0-1 loss, 4 corresponds to false L_ corresponds to false_, and & to ?
The original definitions of PRL, NRL, and FRL were introduced only for the case the 0-1 loss For this specific choice of loss function, Kalai, Kanade, and Mansour showed the following:
43
Theorem B.1 ( (43)) Let L contain only the 0-1 loss. If a concept class C is agnostically learnable under distribution 'D in time T(e, 8), then C is L-positively reliably learnable and L-negative reliably learnable, both in time ( 22, Then, C is also G-full reliably learnable, in time (T (22 /8, 5/2).
Lastly, in the main body we deferred the definition of C-NRL to the appendix, which we include for completeness:
A concept class C of Boolean concepts is L-negatively reliably learnable if there exists learning algorithm that for any distribution 'D over X' x {0, 1}. any L,, f- E L. and any e, > O, when given access to the example oracle EX(D), outputs hypothesis
Definition B.5 (NRL for a family of loss functions 43
+ [0, 1] that satisfies the following with probability at least 1 ô:
1. Exxy)) (aap)-/llehh(--) (h(x)) c,
2. ((xx))=((++((x))) mine_ec- (xx.))-pl4+(c-xx/) +
B.2 Agnostic learning
Definition B.6 (Weak agnostic learning). Given a concept class on X' and a distribution D on X' V. (a, 7)-weak agnostic learner for C, denoted WALe, is algorithm that satisfies the following promise problem. Given a collection of labeled samples (x, y) ~ DD if there is some e E C such that (c))(c) S a, then WAT. returns hypothesis h X [0, such that errp (h) I 7 with probability at least 1 - 5.
Definition B.7 (Agnostic learning). Given a concept class on X and a distribution D on X x D, a (strong) agnostic learner for C is algorithm that, given collection of labeled samples (x,y) D and an error parameter e O, returns a hypothesis h : X + [0, 1] satisfying, with probability at least 1 5,
@rr S min errp (c) + e.
eEC
From the results of [44,] 20 on agnostic boosting, we know that strong agnostic learning reduces to weak agnostic learning for any concept class C.
Throughout the statements and proofs, by "efficiently" we mean that the algorithm runs in polynomial time in the appropriate parameters. We drop the failure probability 5 from the statements.
Deferred Proofs from Section 3
C.1 Selective omnipredictors
We emphasize that the selective omniprediction learning paradigm can be extremely useful in practice: once we have obtained (C, C)-selective omnipredictor, we can choose any loss function in L at later time. For example, this allows us to change the abstention costs over time, or to change the cost of false positives or false negatives over time. One envision many practical settings in which
25

---

this flexibility is highly desirable; e.g., if not catching patients with specific illness becomes more dangerous over time. Note that our framework allows us to separate the costs of both prediction and abstention for the cases of y and O.
Theorem 3.1 (Constructing selective omnipredictors). Let C be a concepi class of concepts e: X - [-M, M, J DD distribution X' (0, 1}, 6 > O, and f. family loss functions with associated weights (X.p.1) with À + + V < 1, such that all & E L are B- B-Lipschitz. Then, (C, muuticaalbbbet predictor is a (C,C, 4eB + -eeeeetectvve omnipredictor, where is an absolute bound on f+, e_ Lq-
Remark C.1. The condition À + up: equivalently we could just get 2B + a + v as the additive error.
S is to ensure that the additive error term does not scale
Proof. Given the concept class C and parameter e, we discretize each E C to precision (i.e., into [1/e] many buckets). We denote these discretized concepts by and the corresponding concept class by Ć. Because all loss functions are B-Lipschitz, discretizing the concepts to precision c incurs an additive error of at most cB.
We begin by calling the multicalibration theorem of [32 26 with X. D, c, and È to obtain a (C, c)- multicalibrated predictor h. For any fixed loss function E &,,,,,,6 Ey) E L. we claim that kig.es oh, where kēg,e, is the post-processing function defined in Definition 3.1 is selective omnipredictor.
By the definition of a selective omnipredictor, we want to show that generalized Chow loss incurred by k .y, h is supper-bundee by the generalized Chow loss incurred by k o for every a E C, where k: [0, 1] + IR } is an arbitrary post- post-processing function. By definition of k2+,0, recall that
Ke (p) argmin P. (wf_(() + -l:(1)) + +1 p) (A)+(())))) + (0)(
Following this generalized Chow loss expression (Definition 2.6 we decompose it into the expected cost of predicting, which we denote by Kprodd and the expected cost of abstaining, which we denote by Kabs: both under the Bernoulli distribution (i.e., for y ~ (een()(x)) for each p E range(h)):
Epred (p) min p- pl- (t) (1 p) Xt)
Kabs (p) = uIp (1)) (1 p) (x = u a+ + (1 p) aa-)
Note that the prediction cost depends on the value of I, whereas the abstention cost independent of f. Then, for each point p. in order to minimize the expected generalized Chow loss under the Bernoulli distribution Bern(p(x)), we proceed in two steps:
Find the value t" (p) E M, .M] that minimizes the value of Kpree (p) given fixed value of p. This depends only on the choice of μ, t,, A, A, l. and not on the underlying data. This corresponds to finding the /" (p) value that minimizes the value of k (p).
For each predicted value h(x) = p. we map it to either t" (p) or depending on whether it is cheaper to predict or abstain; that is, depending on the value of min Kprea (p)), Kaba)-
In other words, we can re-write kā__e, as kahs o kūt where
if Kipred S Fibh
kabs
if Kppeed > Rabs
The key idea is the following: the true labels are distributed as y Bxrn(p"(x)). So if we had access to the true (xx) value for each æ. then the optimal prediction/abstention decision rule (i.e., the post-processing function applied to the p" value that yields the minimum total generalized Chow loss) is precisely kiabs.
We can write the cost function incurred by the post-processing function k. _ = Kabs kū as:
x(t,p) min(p (l)(1)) + (1 - p) (
(1- Cz(0))
An important point to remark is that, while the prediction/abssention decision rule is decided with the p-values (to which we have access to, since they correspond to the predictions of the multicalibrated predictor ft), the actual cost that we incur is computed with the true values p". Multicalibration
26

---

precisely allows us to bridge this gap: the predictor h believes that the labels are distributed according to Bern(p(x)), and so uses the function kahs o ki as post-processing, which yields the optimal cost under the distribution y ~ BernBp( (p(n(p()) In order to bridge the "simulated" labels y ~ Bern (p()). which are used in our decision rule, and the "true" labels y ~ Bern(p" (x)), which yield the actual cost that we pay, we use the fact that h is C-mullicalibrated, which ensures that
Bly h = p, č 7] Elp h -.c.p- 7
for each y in the range of ē. The RHS can equivalently be written as B/h | h = p, "bridging" enabled by the multicalibration property satisfied by the predictor h is what allows us to show that our selective onnipredictor (namely, the predictor ki E. incurs optimal loss with respect to the class C.
- = 7]. This
We have discussed how the prediction/abstention decision rule for the multicalibrated predictor is need to show that the
given by xs( (p), p)- As per the definition of selective omnipredictor, generalized Chow loss incurred by ki 8t is -opur-bounded by the generalized Chow loss incurred by any of the selective concepts Cv, where E C and k : [0,1] - R (?} is any post-processing function that adds abstentions to the concepts e E C. The only natural restriction on k is that it is a function of the values ē(-), and cannot be a function of æ. E.g., if ((x1) y 6(22), then it must be that é7 (z1) = (x22) Hence, in the case of the concepts è C. we cannot directly assume that the rediitiion/bbsenttio decision rule corresponds to k2_,,, as well.
However, we can use the multicalibration condition to reason about the loss incurred by the concepts Specifically, for each concept è E č, we define the sets K(nr)) = {x E X Mxx)) p, d(x) = 7 for each p E range(h) and each y E raage(c). Moreover, we let
((p,)) E[y|x E &(pp)))
The fact that h is (Č, -uulticaliibrated implies that ( = Ely| h(x)= = p. a(x) =>]= m E(h(x) h(x) = p. ((x) = 7 = =
((p))) Re P.
In practice, the multicalibration condition applies on expectation over the level sets K(p.)) for all P. We fix a level set h(x) = p of h and concept è E Ć. We want to compare the loss incurred by kg (h) with the loss incurred by le c, where [0, 1] - R U {?} is any post- post-processing function. Within the level set Mxx) = p, all of the values 12,, ee (h) are the same, and so k24 (h) is either predicting the value t" (p) on all of the points in the level set h(zz) p, or abstaining in all of the points in the level set, as determined by the cost function k<(t (p). p). Within the level set h(x) = p. we further partition it according to the level sets of é. That is. we consider the partition of X, into the sets Kip..) for each y E range()), G). For each x E X (p, é either predicts or abstains, using a decision rule i that is allowed to be arbitrary. For each set (p))), we split the proof into 4 cases, depending on whether and decide to abstain or predict as per their respective decision rules.
Throughout, we let / denote a bound on the absolute values of t., l_, by. Moreover, we can write the loss function as
(kc, o h; X, H,,
E
E
E
[LoC,ly (h(x))),
pErange(h) (Erange( x>DD (((r))
and similarly for k č.
Having fixed the values = p and é = 7, we argue about the expected loss incurred by the post- processed multicalibrated predictor versus the expected loss incurred by the concept on the level set X(n.))
1. k es h predicts & k predicts. We begin by swapping Φ(p,)) for p in the following expression:
d(n))) pl- (t" (p)) + (1 - )(p))) (t (p) = p- pl (p)) + (1 p) Al+ (p)) + (0(p,)) - (ue- (t" (t"(p)) - (t)
By definition of L (p), it follows that L' (') is the minimizer of Ripred (p) in [-M, MD given fixed value of p. Hence,
p pe- (p) + (1 - p) (t" (p)) S ul + +(1+01111100 (1-p)-Xe4()).
27

---

Swapping p for ((p,)) again, we get that
p p-ue (7) (1- p) xe+(7) + PPl -X
(e-((()))
= - pulpppe--1 (1)+(1-))))))) (D0
Putting everything together, we get that
((pm)) pl (1"()) (1 ((m))) Xe+ (v))
(( (a)e:)))))))(()))))()())))) (1) ()) (u)))))))) By the 3-bound on the loss functions, and given that X + / + S 1, it follows that
(dip.)) - pp) (t'))) - (x - (wl (+))] - (0(p,7) - -pl 433.
Therefore, over Np,y)) where ki_,,r o h is predicting and & a à is predicting 7, the expected generalized Chow losses compare as follows:
(cc,0(M2.. h; X, u4 v x E Mpmn) S loc é A, un x M(M)) + +b(en)) - pl 4..
2. Ki o h predicts & k o abstains. As in the previous case, we swap P(p.t) by p:
((pm)) pl- (p)) (1 d(p))) xl+ (c) = =p- -e-ppl(("(()) + (1- Xe+ (x (p)
+(0(g)) () (p)) - (t+ (x)
By the decision rule for lo determined by the value of k((" if kū o h predicts on ((p)) this implies that
P- p- (p)( + (1 (1-p) p) At+ (p)) p vl, (1) + (1 p) v1)
Again swapping p for ((p.))> we obtain:
p p-vl (1) (1 p) vl:(()) + (d(p.)) - (()(et(((() -x4
= Oppp) (())))))(((((((((p))))))))))))))
By the B-bound on the loss functions, and given that X + # S 1, it follows that
( 1aa--pa -D) [ue (t Xe+ - (v)()))))>(0)) s (0(():)) - -pl- 4,3.
Therefore, putting everything together, we obtain that
lGC.D (ki h; X, μ1 v x E Xpm)) I foc.p(ko H1 X Mprr) + +b(()))) - pl -48.
3. k2 o h abstains & k o è predicts. We start by swapping P for p as in the previous two cases:
((p))) vl,(1) + (1 -1-de ((p.)) (0) = vlx(1) + (1 11-p) p) =l2(() + (d()n) - -
Because k e h abstains on this level set, it must be that
p. p-vl;(1) + (1 - pp)- vl2(0) S p pl (t- + (1 p) X4 (t)
By definition of (p) as the minimizer of Kipred: for any value of 7 we have that p- p-ul_ (t=((t"())) (p)) + (1-p)) p)-
Sp ul (7) + (1 - p) (7).
We again switch p back to ((p.))
p. p. (7) + (1 - p) xx4(7) + (0)m)) - 0(p,)) uul + (1- (7) + (dipn) p) p) (vl= vl> -dd)))))
- -V((()
(ul- (e
By the 8-bound on the loss functions, and given that \ / + 1, it follows that
( - (1)(((((1 - vl)( - (ul- (7) + Xl- (x)) < (p().)) pl 48.
28

---

Putting everything together, we obtain that
LGC ( h; A. p. Mpmr) I (oC é; A. u, x X(pr)) ((( - -43.
hi h abstains & k é abstains. In this case, given that the values of (1( and (, are independent of directly follows that both kit,0, and & incur the exact same generalized Chow loss on ()))))
Putting these four cases together, and by taking the expected value over all level sets ((,))) for all p in the range of h and y in the range of é, and by thus applying the multicalibration guarantee on Bll - pl] (i.e., which guarantees that ([( - pl] I e), we obtain that
loc,D(ki,, & o h; X, u, I (cc o e; À, H1, v) + 4eB.
Because these four cases are exhaustive and hold for all values of p and 7, conclude that (y ki (h(x))))
foc,p(kied o hr ))),
E pErange(h) (Eaange()
E
E x x ((x)
E pErango(M) (Erange(() x x( ((oo))
E
E
(y k(c(x)))) 4eB
lGc o X, u4, + 4eB.
Therefore, for the non non-discretized concept class C, and accounting for cB loss incurred in the clippings of each of с and t" (p). we conclude that
L & h; p,,) s (cc. + 4eB + eB
for all loss functions in L, and hence h is a selective omnipredictor, as we wanted to show.
Then, the value of kg can be computed efficiently because (1) computing the value of Ripred (p) corresponds to solving a one-dimensional minimization problem, and (2) the value of k2 fy is then fully determined from the values Kipred (p) with the optimal ( = L" (y) and of Kibs, independent from the data.
Lastly, we show that allowing for randomized selective predictors does not help in minimizing the generalized Chow loss function. Suppose that the selective predictor was randomized, such that for each point x E A' it would predict a value
[0, 1] indicating the probability of abstention on Then, for a fixed we can write our post- procesrocsssing function as
keg ke (p) argmin,, (1 - a) (ipeed + atiabe = (Kabe Kpred) a + Kpred-
For a fixed t E IR U { (and once the loss functions have been fixed), the total loss only depends on Epreed and Nabss which in turn only depend on p. Note that after fixing t, kj,, is linear function on Ripred, Kabs- This implies that the total generalized Chow loss is minimized either 0 or so no fractional abstention is required.
Remark C.2. If the concepts e E are not bounded a priori, then we can clip them into an interval [-M, M for some finite value M. Given any convex loss function & and parameter e, we find -M and M by determining the values of t E R such that E(00 t) = and E(1, t) = e, respectively; these correspond to the values of -M and M. This clipping is either helpful (prevents the loss from getting too large) or incurs at most e additional loss; for example, for the logistic loss, we set M log (1/c), -M = log(1/c).
Interval of abstention. Having shown that we can efficiently build selective omnipredictors, we further show that all points p that are set to ? by kig,e, are in contiguous interval. This follows from the affinity of the loss functions 4, -_ L.
We can also write Kpred (p) as Kipred (p, t*) ) indicate that the value of t" has been set to the optimal
value for each prediction p. More generally, we let Kprea(p, Jp, t) = p -l- (t) + (1 - p) -xe (t). Lemma 3.2. Given any loss functions l,, l_ lg E C, the points x E such that kū_,,, ., (x) = ? form a contiguous interval, which we denote by Labs-
To prove Lemma 3.2 we first show the following intermediate lemma:
29

---

Lemma C.1. The function Repred t²) is concave as function of p.
Proof. Recall that Kpred (p, (*) = min p pul (1) + (1 - p) xe+ (1), where "prea(p,t"
minkeR Kpread (p, !)
For every fixed lo IR, the function Kipred (p, (n) affine in p:
Kpred to) (ul-((t)) xe+(to)) p (to)
Affine functions convex and concave, and Kpred (p) min Ripred (p, to) is equal to the pointwise infimum of a family of affine functions in p. It is a known fact in analysis that the pointwise infimum of affine functions is concave, and so Kipred (p, t*) is indeed concave as function of p. L
<(p,t)
x(p.t) t)
0.5
0.5
1.5
2
0.5
0.5
1.5
P
(a) Example with the & function; Nipred (p. t) with fixed values of p. For each fixed value of p, the result- ing function is convex in
(b) Example with the & function; Kpeed 1) with fixed values of For each fixed value of the result- ing function is affine in p.
Note that for our results Tabs we only need affinity in p.
Proof of Lemma 3.2 Recall that k2_ e, (p) = min (onn(Aippp (ripred t²), Kabe Per Lemma C.1 the function Keree (p. t²) is concave in p. By definition, note that (abs(p) (p) is affine in p:
Rabs (p) (va+ -a- a
Therefore, the function Kpredd (p, (*) (pt is still concave in p. Hence this function has at most two roots, and hence the of points p where Kipred (*) (p) forms contiguous interval (which can be empty, in the case where it is always better to predict than to abstain). By the definition of our post-processing function k2 .r (p), this interval corresponds precisely the set of points where ki (p) ?, and hence this interval is equal to Lass
Figure 2b illustrates the concavity of ppredd (p, ()) function of / (left) and the affinity of Kprea (p, () as function of p (right), which prove that the abstentions as allocated by the selective omnipredictor occur in one contiguous (and possibly empty) interval Jabs-
Omniprediction with constraints. Recent work by Hu, Livni-Navon, Reingold, and Yang extends the line of work on omniprediction to constrained optimization problems 35). This allows the learner train agnostic to the final choice of loss function well of constraints that will be later imposed (as long as these satisfy certain conditions). By viewing Condition in the definitions of PRL. NRL, and FRL as a constraint, one could potentially adapt their results in order construct C-PRL and C-NRL predictors, and then ensemble them in the usual way to obtain C-FRL predictors. is unclear how this approach could be used to obtain optimality in the more general framework of selective omniprediction with generalized Chow losses (Definition 2.7
In the proof of Theorem we used Kpread Here we write to remind that function has been minimized with respect t.
In the of ties, we decide to predict.
30

---

C.2 FRL from selective omniprediction
Theorem 3.3. Let C be a concept class of Boolean concepts. L any class of B-Lipschitz loss functtins, and D distribution on X x y. If C is agnostically learnable under 'D in time (E,,6), then C is C-fully reliably learnable under DD in time T /6,
Note that here we use our proposed notion of C-FRL (Definition 2.5 which is generalization of the 0-1 version proposed 43
Proof. Let be the target error parameter for fully reliable learning. We consider the parameters = = 1/3 and / = =//6. From C, we define the concept class C" concepts x {0, 1/2, 1 as containing the concepts (cr + o2)/2 /2 for every possible pairing Cı, 02 E C. Defining the post- processing i as mapping to 0, to 1, and 1/2 to we get that SC(C) C k o Let oa be an optimal abstaining classifier in SC(C). By definition of SC(C), it follows that all concepts in SC(C) incur error over the non-abstaining region, and hence
Lcc.p(c;; X, u. v) vc)())).
Let h be (L,C', r--selcttvve omnipredictor (which we can obtain for C' given that C' is agnostically learnable, as shown in Theorem 3.T.. By the selective omniprediction guarantee, it follows that for any post-processing function k 0. R {?}.
(b; A, H < min lgc. (c); A, (c;
+
In particular, using the post-processing & that maps 0 to 0, 1 to 1, and 1/2 to ?, this implies that
(Gc, A, u,,) v) & (oc.p(c;;
= ,l2(()) + 7/
By setting 7 = c2/6. and using the fact that (c(c)) - 1, we get and since À = 1/3, v = c/6,
1/ (h) S c/6 e and so (h) S c. Similarly, we have that 2h) S c. Finally,
yb*(h) S 762(c)) e² 2/6
since 7 c/6, it follows that,
(x))) s (((c)) +c.
This completes the proof.
C.3 Conformal prediction from FRL
Lemma 3.4. Let by : X 3 be an FRL predictor for C, D.e and the 0-1 loss. Then, the
prediction sets induced by the level sets of h, where we map + {0), + {1}, and ? + {0, 1}. satisfy the e-marginal coverage guarantee.
Proof. Let err(h,, D) = -Pt(x.y)=D((xx(x) + y] denote the error of the selective predictor foz and recall that
false, (12, D) Pr [hr = - = 0] false (1r, D) = Pr [1x(() = 0 A = =1]. (x,y)~
(x,y)~D
Since err( (hr,, D) < by the FRL guarantee of by and err(lv, D) = false (hv, D) + false_ (h,,, D). it follows that
false, (hr, D) S e,
false (hz, D) S c.
This implies that for all y = 1,
Pr (x,))>
{1)) Se
and symmetrically for all y O. Therefore, we satisfy the marginal coverage guarantee for the prediction sets (0): [1]. We also trivially satisfy for the prediction set (0, 1}, since y Boolean
and so Pr(x.y)~Diy E {0, 1]] 1.
31

---

which shows that FRL viewed as conformal prediction method, besides satisfying the e-marginal coverage guarantee, also provides a provable upper bound on the size of the set {0, }}, which constitutes a measure of uncertainty:
Lastly, we formalize and prove Remark 3.1
Lemma C.2. Let by : X + {0, 1, be an FRL predictor for C, D,e, and the 0-1 loss. Then, the prediction sets induced by the level sets of ho satisfy:
Pr (x
(x) (0, 1H S
min evESC(C) (x-))
Pr
J0r (2) +
Proof. This follows directly from Condition 2 in the definition of FRL, which ensures that
?(v, D)
min ((%,, D) +e. ey CS)
D Examples of Selective Omnipredictors
In this section, we provide concrete examples of the post-processing function ki, for specific choices of loss function triplets (,). We do so for the triplets of loss functions used in Figure [] and for each triplet we theoretically derive the abstention interval Jabe. Recall that Labs only depends on the chosen generalized Chow loss, and not on the underlying data, which is what makes our selective omniprediction framework extremely efficient to adapt to many different loss functions.
& loss with diffferent abstention costs. the abstention cost be fixed some value > 0. That is:
Consider letting L-, l correspond to the 0-1 loss, and let
e_ (1) = | 4, (() 14, (7(y)
Then,
Kipred (p) -mmnn p- - t + p) |t),
Kabs a.
The value (p) that minimizes Hipred (p) for each p corresponds to (p) (") 1p 2 1/2]. Then, for each predicted value h(z)) ki will compare the expected prediction cost under the Bernoulli distribution y Bem(()), namely
Kpred (p) p-
11- t" (p) p- (1 p) 11" (p) - p- 11 1pp 2 1/2] + (1- p) 1 1/2//: (1)
with the expected cost of abstention Kiabs a. If Kirred (p) Kabss then k2 (p) (p): otherwise,
k e, (p) ?
We compute the interval Tabe for different choices of For arbitrary value of riabs ai abs corresponds to the interval contained between the roots of the polynomial Kipred (p) Kabss which is function in p. In the case of a 0.1, the roots of Kpred (p) 0.1 (where Kpred is given in Equation I
yield Labs = [0.1, 0.9). For = 0.2, the roots of Kered (p) - 0.2 yield [0.2, 0.8).
Lastly, consider the case where (7( 0. 0.3 and (7( a 0.1. Here, we have that
Kabe(() = p- a4 + (1 p) a Then, the roots of the polynomial Kpred - a- a4 + (1 (1-p) a for = 0.3 and a = 0.1 yield
Jabs 10.125, 0.75].
the case of the lg loss, and still with fixed abstention l2 loss with different abstention costs. cost (g) a, we have that
k (e, p- 11 (1 p) (0 t)² + axx
Hence, if we decide to predict, we pay an expected cost of Kipred (p) = min, p- (11-))+((--))000-- If we abstain, pay expected cost Kabs (p) = a. Both of these expected costs are under the Bernoulli distribution y ~ Bern(p). For a fixed value of p. the function lipred (p. t) is minimized at t" (p) p. and hence
Eprea t²) (1 (1-p)² p)
32

---

Hence, the value of & (p) is fully determined by the quantity min (1-p)² +1-pp)+(1-p))) .
We can similarly compute the interval Jabs for different choices of a by computing the roots of the polynomial Kpred Rabs-
In the case of 0.1, the roots of Kpred (p) 0.1 yield Lass
1-v0.6
1+,0.
For = 0.2, the roots of Kpred (p) 0.2 yield las = 11.2 1+y02)
2
Lastly, again consider the case where {1 a+ 0.3 and (0
0.1. The roots of the
polynomial (prea p p. + (1-p) a for a+ = 0.3 and a 0.1 yield Labs = 10 y
10
All of these theoretically-deriee abstention intervals Labs can be visualized in our experiments, as summarized in Figure We further provide an illustrative example in Figure 3 to show how the abstention interval Tabs widens when we decrease the cost of abstention from 0.2 to 0.1.
0.4
0.4
0.2
0.2
p
0.4
0.6
0.8
0.2
0.6
0.8
-0.2
0.2
Figure 3: Example with the & loss and (7 = 0.2 for all (i.e., the traditional Chow abstention
model) in the left subfigure and Ez(y) 0.1 for all y in the right subfigure. The purple line represents Eprred (p, (*) and the orange line represents Kabs (p). The green line represents Kprea J (*) Kabs (p), so its roots determine the interval Tabs where
abstain optimally (shaded in blue). In the left example, Jabe (1 (2 (1 /2). independent of the data. As we decrease the cost of abstention from a = 0.2 to a 0.1 (and so the orange line moves down), our selective omnipredictor obtains increasingly wider abstention interval Labs (e.g., in the right subfigure), as one would expect.
E
Experiments for Section
E. Selective omnipredictors
We construct selective omnipredictors from multicalibration to demonstrate the feasibility of our abstention method in practice. We remark that, as far as we are aware, none of the previous works on omniprediction included experimental evaluations. Because our experiments are a proof of concept, use synthetic data for all of them
We first provide full description of the experimental set-up that we used to generate Figure T and Table T in Section 3.1 Next, we provide further repetitions of our experiment showing selective omnipredictors in action.
First, we generate 10, 000 samples and 20 features as our data using sk- sk-learn's function laaee_classifccee
and train random forest obtain baseline predictions. We then im- plement the multicalibration algorithm from scratch using the concept class of decision trees of depth 3. At each step, we check for correlation between any concept in C and the residuals computed with the current predictions. For the multicalibration algorithm, we use discretization parameter of 0.1, a learning rate of 0.01, and 200 maximum iterations. The multicalibration algorithm is run on the validation set (20% of the data) and we then report all of our statistics on the test set (20% of the data). This gives us a predictor h; note that so far we have not used any loss functions.
Next, we choose specific triplets E4,,_,0 E2) and for each we apply our post-procesd processing function k kig,e. We use the triplets that shown in Tables I 2 This pre-computed function that derive mathematically, so it is extremely efficient post-process our h in this way. For each triplet, we compute the total coverage, the total loss over the non-abstaining region (i.c., 4 + 67), and the
The code for this paper can be found
http://hhh..cmlallllsaaaaaaaaaaa abstaai
33

---

abstention loss (i.e., E2). Separately, we do loss spssificc minimization to compare with. In order to use the same concept class C, we implement decision
that minimize the Chow losses for the
chosen triplet (L+: e-, fτ). That is. we train a different decision tree (that adds abstentions) for each We similarly report the total coverage, the total loss over the non-abstaining region, and the abstention loss (i.e., Ey). Further details on our experiments can be found directly in our code.
of the different triplets T 4
We repeat all of this process for different initializations of the synthetic data and report several runs All of them demonstrate the same pattern: our post-processed predictor h, even single predictor for any of the loss triplets, achieves better coverage and better loss than the loss-specific abstaining decision tree. This is because the multicalibration process helps calibrate the predictions towards O and 1. In contrast, the decision tree abstains significantly more (and thus obtains lower loss over the non-abstention region). Therefore, this demonstrates the utility of using selective omniprediction in practice.
Tables 1 2 3
though it
Table 2: Comparison of coverage and losses. "Cov" stands for coverage, "Pred" for predicted loss (i.e., over the non- abstainni region), and "Total" for the total generalized Chow loss.
& 0.1
& 0.2
& (1) 0.3, (0) = 0.1
k7 + /n
o
Abst. DT
1 1e h
Abst. DT
k2 a
Abst. DT
Cov: 45.70%
Cov: 1.9%
Cov: 89.15%
Cov: 4.4%
Cov: 62.60%
Cov: 4.8%
Pred: 0.038
Pred: 0.010
Pred: 0.069
Pred: 0.030
Pred: 0.065
Pred: 0.005
21
Total: 0.072
Total: 0.108
Total: 0.083
Total: 0.221
Total: 0.093
Total: 0.192
Cov: 47.55%
Cov: 4.4%
Cov: 89.65%
Cov: 10.5%
Cov: 66.65%
Cov: 11.5%
Pred: 0.037
Pred: 0.003
Pred: 0.066
Pred: 0.007
Pred: 0.057
Pred: 0.012
82
Total: 0.070
Total: 0.098
l
Total: 0.079
Total: 0.186
82
Total: 0.085
Total: 0.181
Table 3: Comparison of coverage and losses. "Cov" stands for coverage, "Pred" for predicted loss (i.e., over the non-abstaining region), and "Total" for the total generalized Chow loss.
& 0.1
8 0.2
(1 = 0.3, (x( 0.1
k24.4 Eg h
Abst. DT
1 Ag h
Abst. DT
Abst. DT
Cov: 20.50%
Cov: 9.5%
Cov: 43. 80%
Cov: 12%
Cov: 39%
Cov: 11.25%
Pred: 0,027
Pred: 0.032
Pred: 0.043
Pred: 0.176
Pred: 0.042
Pred: 0.010
f1
Total: 0.085
Total: 0.122
4
Total: 0.131
Total: 0.211
Total: 0.136
Total: 0.184
Cov: 22.90%
Cov: 12%
Cov: 39.20%
Cov: 20.3%
Cov: 58.20%
Cov: 23.6%
Pred: 0,032
Pred: 0.009
Pred: 0.064
Pred: 0.015
Pred: 0.075
Pred: 0.014
L2
Total:0.084
Total: 0.097
82
Total: 0.119
Total: 0.174
&2
Total: 0.119
Total: 0.161
Table 4: Comparison of coverage and losses. "Cov" stands for coverage, "Pred" for predicted loss (i.e., over the non-abstanee abstannnann region), and "Total" for the total generalized Chow loss.
t 0.1
8, 0.2
(x(1) 0.3, (x 0.1
ki+.07 .7 h
Abst. DT
k ., h
Abst. DT
k h
Abst. DT
Cov: 48.7%
Cov: 10.7%
Cov: 74.15%
Cov: 19.3%
Cov: 70.80%
Cov: 13.15%
Pred: 0,022
Pred: 0.029
Pred: 0.043
Pred: 0.065
Pred: 0.044
Pred: 0.008
f1
Total: 0.062
Total: 0. 118
81
Total: 0.084
Total: 0.226
f1
Total: 0.078
Total: 0.178
Cov: 50.45%
Cov: 19.3%
Cov: 79.25%
Cov: 24.9%
Cov: 76.85%
Cov: 24.6%
Pred: 0.024
Pred: 0.005
Pred: 0.048
Pred: 0.013
Pred: 0.048
Pred: 0.020
L2
Total: 0.062
Total: 0.086
f2
Total: 0.079
Total: 0.164
8
Total: 0.072
Total: 0.164
E.2
Conformal prediction from FRL
As shown I 3.44 and Remark formalized Lemma C.2 we can view FRI. as a conformal prediction method. We illustrated the feasibility of implementing FRL in practice and compare its
34

---

Table Match on f for each weight w, choose a minimizing the difference & error between the FRL and the conformal prediction methods.
Weight
a
FRL MAE
CP MAE
FRL coverage
CP coverage
0.25
0.250
0.260
100.0%
97.0%
5.0
0.05
0.139
0.130
54.5%
42.3%
10.0
0.05
0.113
0.130
40.0%
42.3%
25.0
0.01
0.078
0.027
25.5%
11.0%
50.0
0.01
0.045
0.027
17.7%
11.0%
75.0
0.062
0.027
16.0%
11.0%
150.0
0.01
0.015
0.027
13.1%
11.0%
200.0
0.01
0.000
0.027
9,4%
11.0%
coverage and & error with that standard conformal prediction algorithms. Similar to our other experiments in the paper, experiments proof of concept for theoretical results, but do not intend to perform an exhaustive comparison to all of the conformal prediction methods in the literature.
We generate 5, 000 data samples synthetically using sk-learn's 's make_blou blobs function, which generates isotropic Gaussian blobs for clustering. To create FRL predictor, do it by training a PRL and an NRL predictor separately for the same data, and then ensembling them the usual way (i.e., if the two agrec a prediction NRI. predictors, we use random forests where we give extra weight w to the label that we wish to penalize most for the predictions (so false positives in the of PRL, and false negatives in the of NRL). We try weights w = [1, 5, 10, 25, 50, 75, 150, 200). This ensures that our trained predictors achieve the required one-sided guarantees. For the ensembled FRL, compute its global coverage and E error.
keep it, otherwise
abstain). To create the PRL and
Next, we use popular conformal prediction algorithm for binary classification to compare to. We choose the widely-used MAPIE library [63] and use the standard split conformal prediction method using the LAC method compute the conformity score. We note that this is the only allowed conformity score method in MAPIE for binary classification, which is why we did not add other conformity
random forest the base class, and train different models for different confidence levels of a = [0.01, 0.05, 0.10, 0.20, 0.25] (i.e., this the parameter for the marginal coverage guarantee). When tested the test set, the conformal prediction method returns prediction sets {0), {1}. or {0, 1). We view the set {0. 1} as equivalent to an abstention ?, and then compute the global coverage and ε error for the conformal prediction method.
methods. We
To compare both methods for
the weights w = [1, 5, 10, 25, 50, 75, 150, 200) and coverage parameter [0.01, 0.05, 0.10, 0.20, 0.25] match them based on a) matched & error, and b) matched coverage. We report the results pairs of tables as follows: a) for each weight w, we take the value that corresponds to the closest lj error of the FRL predictor for this w, and we report the errors and coverages for this pair. We then also report the results by matching coverages instead: b) for each weight w, instead take the coverage value that corresponds to the closest coverage that of the FRL predictor for this w, and we report the errors and coverages for this pair.
We do several repeats of our experiment for different initializations of the synthetic data and report the pairs of tables. 3 correspond to one run, Tables and to another, and 9 and T0 to last run. We observe the same pattern: FRL provides similar coverage and error guarantees to the standard conformal prediction method, with FRL usually having higher coverage and lower L error.
F Deferred Proofs from Section 4
F1 (C, -uulliirruu selective classification
Theorem 4.1. Given access to (C G, è²
/ mulliaccuee and calibrated predictor, we can efficiently construct (C, mumuliggrou selective classifier in time poly(1/e).
35

---

Table 6: Match on coverage: for each weight w, choose a minimizing the difference in coverage between the FRL and the conformal prediction methods.
Weight
a
FRL E
CP 4
FRL coverage
CP coverage
0.25
0.250
0.260
100.0%
97.0%
5.0
0.10
0.139
0.172
54.5%
62.7%
10.0
0.05
0.113
0.130
40.0%
42.3%
25.0
0.01
0.078
0.027
25.5%
11.0%
50.0
0.045
0.027
17.7%
11.0%
75.0
0.01
0.062
0.027
16.0%
11.0%
150.0
0.01
0.015
0.027
13.1%
11.0%
200.0
0.01
0.000
0.027
9.4%
11.0%
Table 7: Match on 4 for each weight w, choose a minimizing the difference & error between the FRL and the conformal prediction methods.
Weight
a
FRL &
CP &
FRL coverage
CP coverage
1.0
0.25
0.226
0.223
100.0%
98.5%
5.0
0.10
0.136
0.155
56.7%
64.5%
10.0
0.05
0.111
0.093
43.2%
41.0%
25.0
0.05
0.084
0.093
28.7%
41.0%
50.0
0.075
0.093
21.3%
41.0%
75.0
0.01
0.052
0.026
19.1%
11.6%
150.0
0.01
0.052
0,026
15.5%
11.6%
200.0
0.01
0.046
0.026
10.8%
11.6%
Table 8: Match on coverage: for each weight w, choose a minimizing the difference coverage between the FRL and the conformal prediction methods.
Weight
a
FRL l
CP &
FRL coverage
CP coverage
1.0
0.25
0.226
0.223
100.0%
98.5%
5.0
0.10
0.136
0.155
56.7%
64.5%
10.0
0.05
0.111
0.093
43.2%
41.0%
25.0
0.05
0.084
0.093
28.7%
41.0%
0.075
0.026
21.3%
11.6%
75.0
0.01
0.052
0.026
19.1%
11.6%
150.0
0.01
0.052
0,026
15.5%
11.6%
200.0
0.01
0.046
0.026
10.8%
11.6%
Table 9: Match on f; for each weight w, choose a minimizing the difference & error between the FRL and the conformal prediction methods.
Weight
a
FRL &
CP &
FRL coverage
CP coverage
0.25
0.239
0.247
100.0%
98.8%
5.0
0.10
0.127
0.147
57.3%
67.2%
10.0
0.05
0.104
0.083
43.3%
41.1%
25.0
0.05
0.070
0.083
29.9%
41.1%
50.0
0.047
0.038
23.4%
13.0%
75.0
0.01
0.046
0.038
19.5%
13.0%
150.0
0.01
0.034
0.038
14.9%
13.0%
200.0
0.01
0.000
0.038
10.2%
13.0%
36

---

Table 10: Match on coverage: for each weight w, choose a minimizing the difference coverage between the FRL and the conformal prediction methods.
Weight
a
FRL &
CP &
FRL. coverage
CP coverage
0.25
0.239
0.247
100.0%
98.8%
5.0
0.10
0.127
0.147
57.3%
67.2%
10.0
0.05
0.104
0,083
43.3%
41.1%
25.0
0.05
0.070
0.083
29.9%
41.1%
50.0
0.01
0.047
0.038
23.4%
13.0%
75.0
0.01
0.046
0.038
19.5%
13.0%
150.0
0.01
0.034
0.038
14.9%
13.0%
200.0
0.01
0.000
0.038
10.2%
13.0%
Proof. Let g E g be some group and let focus the part of the domain Xg = {rr g(x) 1). Consider the classes C C derived from the Boolean concept class C, where C (D) = (c
Pr[c(x) = 1, ( = y = 0J 0} and Cj (D) = {o E C Pr(c(x) = 0, gx) = 1, =1
Let be a (C G, 2///)))))))) / and calibrated predictor for X, D, which we can build using the main theorem in (26). Consider any c+ C C. The multiaccuracy condition is ensured for all e- g E C. G, and so for this particular c+ fixed group we have that
E [o(()) (x)) - h(x))] S 2/8 D
Given that whenever (x)) and g(x) have that y by definition of Cj. it follows that
Ely s(x) 1, (x)
That is, within the region in X, where c4 (z) 1, we have that Eply] = 1. Then, by the multiac- curacy guarantee on c4 g. follows that the expected value of over the same region (i.e., where c4 (x) inside of X2y) is also close to 1:
[g(x)) c4 (x)) - h(x))]l = | [[((x) ( -xx))]((]]]]]]]] < E//8 B
E
and
2² B [(((x) g(x) 1, c4 1] 2 8 8Eolg (x)
Now, we have two cases, either Pr|c+ (x) = 1,9(z) = Eolc+ (x)g(x) S e/2, in which case we trivially have,
E [1(((x) 21 (011cl9(()) 2 (x)((x) c/2.
or, from Equation 2 we have that
E [[hxx) < 1 - g(()) = 1, (x)
1]
4 EEDlg(x)c_ (x)]
In this case, by taking the complement and multiplying both sides by ED (x)c4 (x)], we get,
E [1(x(x) 2 cl g(x)) 2 [1]{() 2 c) ((x))+(x))
(x)g(xx) e/4.
Thus, in either case we have,
E [1[h(x) 2 1- - > [x)c(x))(xx)
e/2.
symmetric argument holds in the case of c_ E C with the same group g. By the definition of C (D), it holds that whenever c_ (x) 0 and g(x) 1, = 0. and so within the region in X, where c (x) = O, Ey = O. Let e_ be the complement of c.. (which we can take since C is closed under complement). Then, follows that:
Ely g(x) = 1,ē_ 1 = 0. D
37

---

By the multiaceuracy guarantee on č_ 9, we can use an identical argument above (by a case
distinction on whether Pr[c_ (x) 0, g = 1] N e/2) show that
L [[h(x) S c] (()] T 2- (x)g(x)] - -e/2.
From the (C. g, ( muutiacucae and calibrated h, we construct our (C, G, --multiggoou selective
classifier by by post-processing h as follows:
[h(x) h(a( e [ 1], if E (e,1-6).
hx(x)= -1 ?
Observe that
E D
(x) #?| -xx)]
E [1] 2 1 c) g(x)]
+E [1]((xx) S -glg((x))
D
2 Flc+ + (x)g(()
Recall that any og E SC(C)) is of the form (c+, By the construction of SC(C) (see Section 2.3 and given that č_ is the complement of c_ it follows that
E (x)e((x) * ? 9[x]] s [x(c+(x)) + 2 D
D
Therefore, the two above equation show that
E
[1 (xx +3] 9xx)] 2 [ (cx #?] -g(())(x
D
Hence, on each g E G. byy does not abstain significantly more often than the optimal ey for each group.
Note that the global calibration property of ly and the fact that the predicted values of (x( are in [0, e) or (1 - c, 1] implies that both the false positive and negative rates of h2 are bounded by thus satisfying Condition in Definition
Note that to achieve the global accuracy guarantee, we only used the global calibration condition and the fact that we abstain in the region where h(x) E (e, 1 ee (per our definition of l; from h). In the other hand, to achieve the local abstention guarantee, we used the multiaccuracy guarantee and the definitions of C+ and C=. Hence, our proof clearly delineates the complementary roles played by each of the multiaccuracy and calibration. This complementarity structurally similar to the recent result by [I]] demonstrating that calibrated multiaccuracy implies agnostic learning.
It is natural to ask whether from a weaker learning primitive than that of a calibrated multiaccurate predictor for the class C n G. What is the weakest learning primitive that we can build it from? In Theorem below, we answer this question in the positive in the case where G is small. Specifically, we show that in this case, we can construct it from fully reliable learning:
efficiently construct (C, m)multiigou selective classifiers starting
Lemma 4.2. If the class C is fully reliably learnable for the & loss and > O. construct (C. mulliggruu selective classifier in time poly([g), with oracle access to the full reliable learner for C.
Proof. For each E G. we call the FRL oracle with the restricted domain {z | g(z) = 1}. error
parameter e/lg), classes C, G. and the 0-1 loss function. Let h² {a g(x) = 1] + {0, 1, ?} denote
the selective classifier that we obtain with an FRL call with the domain X, = fx [g(z) = 1}. We
construct our final global classifier h : X + {0. 1, ?? as follows: for every point x E X, consider
the set K. C G of all groups C such that g(z) = 1. Then, h2 is equal to the plurality vote of the [K] total classifiers h.
By the FRL guarantee, each he makes a wrong prediction on at most e/ e/|9] points in X. In the worst case, all the 9 error regions are disjoint and cause all the majority votes taken on the points æ in these regions to cause the wrong prediction. Hence,
(hz) = Elly - hx))) 1 (x) + ?]] = |
< E,
g
38

---

and thus we satisfy Condition 1 in the definition of ( -uultigruu selective classification (global accuracy).
Secondly, we have not added further abstentions in our ensembling of the h& predictors, and so we continue to satisfy optimal local abstention rate within each g 9. Namely, the FRI. guarantee each g ensures that
[x(x) [x:((x) ?]] (x
Pr
min Pr cxE))(C) (x.y)-D
[g(x) [x)((x)
=?]] + c.
In fact, we are getting a better e e/lG] error. Hence, we satisfy Condition 2 in definition in the definition of (C, -mulliigroup selective classification. Thus we have shown that by is ge)- multigroup selective classifier, as desired.
F.2 Multigroup fairness primitives
We recall that multicalibration a stronger notion than calibrated multiaccuracy, which is in turn a stronger notion than multiaceuracy.
(a) If have the stronger primitive of a (C --muticccalibrte predictor (which implies a (C g)- maltiaccurate calibrated predictor), then we can have non-selective predictor which would give local agnostic guarantees. This follows from the works of (25 10 27
Formalized:
construct classifier h: + [0, 1] in time poly(1/e) satisfying the following local accuracy property: for every E G.
Lemma F.1. Given access to (C (Cng G, multicaaalibre (
predictor,
E Ily h(x)) (x.y>~
g(x) 1]
min eEC (x,y)~D
[ly - c(x)) g(x) = +c.
Note that a (C,G, e m)multtigou selective classifier achieves a local accuracy property within each E G, where the error term is weighted by 1/ [rr[g(x) = 1]. In Lemma F.1 however, we do so without requiring abstentions, which is why need the stronger notion of multicalibration rather than of calibrated multiaccuracy. Note that accuracy notion in Lemma F.1 is of the agnostic form, rather than an absolute error guarantee.
(b) Given a (C- c G, m)multiiccurrat and calibrated predictor, we can directly obtain FRL predictors for the class C for the E loss by thresholding the predictor as we do in the proof Theorem 4.1 Given that calibrated multiaccuracy implies agnostic learning (TTY, it is already implied by Theorem 1 that we can achieve reliable agnostic learning from calibrated multiaccuracy. However, this approach gives a direct reduction. Reliable agnostic learning is believed to be weaker learning primitive than agnostic learning (45].
Formalized:
Lemma F.2. Given access to a (C. . G, c)-multiaccurate and calibrated predictor h, we can apply post-processing function to h to obtain an C-FRL predictor for the E loss.
Proof. Let be (C G, mumuticiaeeerate and calibrated predictor. We first construct L-FRL predictor hy from h by applying the same post-processing function as in the proof of Theorem 4.1 Namely, we let
hx(x) = (h(x)
h((()) e [1-e][[1e,, if E 1-)
By the definition of FRL, we need to show that h; satisfies 1) low global enror, and 2) optimal abstention. This follows directly from our Theorem 4.1 by using the group g =
We remark that extend the previous lemma to the 0-1 loss.
39

---

F33
Conformal prediction from (C, 9)-mmliggrrupp selective classification
Lemma 4.3. Let h? : X + [0. 1] { be a (C, (-mmmturtigrouu selective classifier: Then, the prediction sets induced by the level sets of h. where we map [0, cl + (0). e, 1] H {1}. and
(e,1- + 1) satisfy Pr(xxy)=Dy E(x) g(x) - 1] 2 Prola(x)=1] for all g E G.
Proof. By the definition of a (C, G, e) -multigroup selective classifier, it follows that h& satisfies the global accuracy guarantce with an e error parameter. This directly implics local accuracy guarantee on each g E G if we weight the error parameter by the probability mass assigned by D g; that is:
E
yy - (x)()] (x) # ?! g(xx = 1] S Pro(g(x) = 1]
(XY))D
Then, the result follows from the fact that for all y 1,
Pr yy {1} 9(x) 1 (x-))=
E
[ly - hy(xx) 1 (xx)(x) #?] ( 11.
(xy))
and symmetrically for all y 0 follows that
Pr yy [0] (x) 1] S (xy))
[ly bx(xx) [[b7(x) { g(x) = .]]
(x.Y))D
Lastly, we formalize and prove Remark 4. which shows that (C, g, {,)mmmultigrouu selective classi- fication, when used as a conformal prediction method, besides satisfying the conditional coverage guarantee, also provides provable upper bound the size of the set {0, 1} within each group g E G:
Lemma F.3. Let hy X [0, 1] U be (C,g,e, -)multggrou selective classifier. Then, the prediction sets induced by the level sets of he satisfy:
Pr (x-y)~
[g(x) [[hr(x)= = (0, 13]] < min Pr
[g(x) [[cx(x) =?1] +e CxC (x.y)~
for every group g E G.
Proof. This follows directly from the optimal local abstention rate guarantee of (C, G, ( mumultigouu selective classifier, which ensures that for every g E G,
Pr (xY)DD [Ø(x) [[)((x)= = ?I] S
min Pr ex) (x.y)D
[9(x) 1[c;(x) = =?]] + c.
G Experiments for Section 4
Lastly, we implement our (C,9) (C..)-multigee multiggoou selective ominpredictors in practice. To do so, we modify the construction our proof of Theorem 4.1 to adapt the multicalibration algorithm that we used in the experiments for Section 3 Again for our proof of concept, we generate 10, 000 samples synthetically using sk- sk-learn's 'srss make_ www.scclssssccctcccoccceaa
function. For the concept class C, we use the same class of decision trees of depth 3. For the class of groups G, we generate them from data using randomness by allowing the groups to intersect and by ensuring some correlation with the labels within each group. In these experiments, we use 10 groups, and each ends up having size of between 300 and 400 samples.
We use the same discretization parameter 0.1 and learning rate 0.01 the update step as in the experiments for Section 3.1 We perform the multicalibration algorithm across all groups in G. In each, we use the same concept class C of decision trees of depth and we cap the number of iterations at 150. We see that the (C, G) ( the la (i.e.. Brier score) and expected calibration error (ECE) for each of the groups in G, as shown in Table 11 We emphasize that, as far as we are aware, our work is the first to separate the roles of the concept class G and the group collection (in the multigroup fairness literature, one usually sets C- C= 9).
find correlation with the residuals greatly reduces
40

---

Table 11: Group- metrics before and after (C, 9)
multicalibbratin.
G
N
Brierpre
Brierpost
ECEp pre
ECEpost
414
0.106
0.004
0.162
0.036
389
0.122
0.003
0.139
0.036
419
0.120
0.005
0.158
0.046
3
395
0.119
0,006
0.164
0.047
416
0.111
0.005
0.170
0.047
5
387
0.111
0.005
0.178
0.051
410
0.116
0.009
0.118
0.054
7
400
0.120
0.008
0.152
0.060
388
0.120
0.011
0.168
0.063
380
0.116
0.011
0.156
0.060
Table 12: Group- Sroup-wise metrics before and after (C, (C,g))mmltienn muuttiaaaliiiiiiinnn
G
N
Brierpre
Brierpost
ECEpre
ECEpost
381
0.072
0.002
0.149
0.024
394
0.084
0.003
0.134
0.029
400
0.079
0.006
0.137
0.033
406
0.081
0.004
0.142
0.036
380
0.089
0.008
0.140
0.049
5
390
0.095
0.007
0.136
0.051
400
0.090
0,009
0.137
0.045
396
0.090
0.010
0.141
0.052
8
416
0.095
0,010
0.126
0,053
379
0.082
0.011
0.158
0.048
We give another example from another run with different initialization of synthetic data:
Next, we turn our (C, multtccallibrte predictor into ( mmulttigrouup selective classifier, apply the thresholding function that we repeatedly use in our proofs in Section namely, for chosen value of c, we map the predicted value if is S c, if is c, and to otherwise. We then compute the coverage and é eтror (i.e., mean absolute error) of our (C, -)muliiigrruuup selective classifier within each of the groups g E 9 for different values
Separately, we again use the MAPIE library to train a conformal prediction method separately within Notably, this methodology does not technically allow the groups to
each of the groups g intersect, but we report the statistics independently on every group. In contrast, our method yields one global predictor, instead of predictor for each group that does not allow for intersections. This is a significant advantage of using (C, ---uuliggrouup selective classification as a conformal prediction method. We remark that two recent works use the multicalibration algorithm to obtain group conditional coverage guarantees for an intersecting collection of groups and perform extensive evaluations [38 39 We once again remark that the significance of our theoretical results Section 4 are extend the multigroup fairness framework to learn how to abstain fairly, and that the use of our algorithms as conformal prediction methods is presented
use case rather than the end goal.
For the MAPIE training, we use random forests as the base class and a = 0.1 as the parameter for the coverage guarantee. After training the predictor, we obtain the prediction sets {0), [1], and {0, 1} for each of the points in the test set. Viewing {0. } as equivalent to ?, we compute the coverage and l error of the conformal prediction method within each group (where we remark that the predictor is trained separately for every group, unlike our selective classifier), We report the coverage and f errors of the selective classifier for different values of (specifically, e 0.2, 0.3. 0.4) and compare it to the coverage and é errors of the per-group conformal prediction method. We perform different runs with different initializations the synthetic data and report the results in Tables 13 and [5 All runs show a similar pattern: the selective classifier is competitive with the conformal prediction method within each group g E G, even though we have single predictor for all groups and the conformal prediction method is trained separately each group.
41

---

Table 13: Per-group Coverage and l error for (c, mulliggouu selective classification thresholding
at = 0.20, e = 0.30, c = 0.40, compared with a separate conformal prediction predictor per group.
Group
N
Covo.20
100.00
Covo.30 0.30
10.30
Cove.40
110.10
Cov
e
421
0.983
0.104
0.988
0.106
1.000
0.107
0.988
0.108
405
0,983
0.118
0.985
0.118
0,990
0.120
0,938
0.100
408
0.975
0.131
0.983
0.135
0.993
0.141
0.963
0.115
384
0.977
0.120
0.979
0.122
0.992
0.123
0.958
0.114
410
0.949
0.118
0.956
0.117
0.973
0.128
0.956
0.128
401
0.960
0.114
0.970
0.116
0.980
0.120
0.963
0.098
388
0.961
0.123
0.977
0.129
0.985
0.134
0.951
0.108
399
0.952
0.124
0.967
0.122
0.987
0.124
0.962
0.109
400
0.932
0.123
0.948
0.127
0.970
0.139
0.963
0.109
409
0.914
0.131
0.917
0.133
0.961
0.155
0.941
0.132
Table 14: Per-group Coverage and l error for (C, -m-ultiggroup selective classification thresholding
at = 0.20, = 0.30, = 0.40, compared with a separate conformal prediction predictor per group.
Group
N
Covo.20
10.20
Covo.30
1.030
Covo.40
100.40
Cov
e
407
0.973
0.078
0.978
0.080
0.988
0.082
0.988
0.082
381
0.958
0.090
0.969
0.100
0.992
0.098
0.969
0.095
422
0.979
0.099
0.988
0.101
0.995
0.102
0.988
0.118
386
0.948
0.093
0.959
0.092
0.974
0.096
0.984
0.111
384
0.948
0,082
0.958
0.087
0.979
0.098
0.992
0.102
391
0.954
0.056
0.959
0.059
0.977
0.068
0.982
0.078
389
0.928
0.066
0.941
0.071
0.967
0.077
0.985
0.081
400
0.910
0.074
0.932
0.078
0.955
0.081
0.998
0.128
411
0.937
0.078
0.956
0.084
0.973
0.092
0.985
0.099
414
0.908
0.069
0.923
0.071
0.952
0.081
0.988
0.108
G.1 Code reproducibility
We include all of the code that
obtain the experimental results for Sections and ZIP file the supplementary material. These experiments were conducted locally using a system equipped with MI chip and 16 GB of local memory. We used ChatGPT to help debug the code and implement the abstaining decision trees, and we studied the multicalibration code provided the Python package from the paper 229 to aid with implementation (which we did from scratch, (29 finds correlation with the residuals using the Boolean groups
given that the implementation in G, whereas want to use the real-valued concepts in the concept class C).
42

---

Table 15: Per-group Coverage and & enror for (C, muultiggruu selective classification thresholding
ε 0.20, e 0.30. e 0.40, compared with a separate conformal prediction predictor per group.
Group
N
Covo.20
10020
Covo.30
110.30
Cove.40
f00.40
Coy
393
0.977
0.146
0.985
0.147
1.000
0.148
0.827
0.138
409
0.971
0.131
0.983
0.132
0.990
0.133
0.856
0.131
381
0.971
0.119
0.979
0.118
0.984
0.120
0.803
0.101
360
0.964
0.118
0.975
0.120
0.992
0.132
0.831
0.110
377
0.966
0.140
0.981
0.141
0.984
0.143
0.862
0.154
389
0.961
0.155
0.979
0.157
0.985
0.157
0.823
0.150
387
0.948
0.125
0.974
0.130
0.987
0.134
0.858
0.139
361
0.958
0.150
0.970
0.154
0.992
0.165
0.853
0.169
373
0.920
0.122
0.952
0.124
0.973
0.129
0.847
0.133
393
0.959
0.149
0.985
0.150
0.987
0.149
0.852
0.152
43


Reviews:
[{"review_id": "27GtsDlv54", "reviewer": "Reviewer_FrNz", "summary": "This paper extends the problem of omniprediction to the selective classification setting. That is, the goal is to learn an omnipredictor that is trained for a class of loss functions and can easily be post-processed with respect to a specific loss function at test time, while being allowed to abstain from making a prediction. The authors show that a selective omnipredictor that achieves comparable loss to the best selective classifier can be constructed by first constructing a multicalibrated predictor and then applying the post-processing function, which is taken from the standard omnipredictor setting and extended to the triple of loss functions for selective classifications. They additionally show that a similar insight can be used to build selective classifiers with fair abstentions, where fairness is defined as the local abstention rate within each subgroup being comparable to that of an optimal selective classifier.", "questions": "1. How was the synthetic data for experiments generated?\n\n2. What are some example scenarios in which selective omniprediction is necessary?\n\n3. Can this framework be easily extended beyond binary classification settings?\n\nOther minor comments/questions:\n- It would be nice to get at least some high level insights in the main body of the paper about how the framework can be generalized beyond convex and Lipchitz loss functions. For space concerns, I think the very long preliminaries could be simplified a little bit. For instance, I would suggest focusing on FRL in the main paper rather than distinguishing PRL, NRL, and FRL.\n- Multicalibration: why multiply by probability of group? Is this standard definition? Less calibrated ok for minority then\n- Theorem 2.1: Should $\\mathcal{C}$ be a set of functions $\\mathcal{X} \\to \\{0,1\\}$ instead, for compatibility with the notion of multicalibration?\n- Line 214: what is the formal definition of “$(\\mathcal{C}, \\epsilon)$-computationally indistinguishable”?\n- Section 3.4: what do $l_1$ and $l_2$ refer to?\n- Table 1 shows that the proposed method achieves much higher coverage. Is this a general phenomenon implied by the theoretical framework?\n- What are the empty regions (neither blue or red) in Figure 1?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The main contributions of this paper are theoretical, showing how to build selective omnipredictors for both convex and nonconvex losses, which guarantees on the performance that seem fairly strong. The results are also technically sound as far as I can tell.\n\nMoreover, the authors also provide experiments on a synthetic dataset demonstrating that the proposed selective omnipredictors can achieve comparable or even better final loss than selective decision trees trained for each triple of loss functions, even though the loss within non-abstaining regions are much higher, thanks to higher coverage rates. However, the details of how the synthetic dataset was generated were not shared, and the results would be stronger with additional experiments on real-world benchmark datasets.\n\nWhile the theoretical framework of selective omniprediction is strong, the significance of the setting combining omniprediction and selective classification could be better motivated, especially with potential real-world application scenarios.\n\nI am less convinced about the proposed notion of fair abstentions. Often for tasks where fairness is a concern, the data itself is biased. For instance, the labels for certain minority groups may be less accurate or noisier. In this case, even though abstention rates are locally comparable to optimal selective classifiers within each subgroup, they may still be highly disproportionate among different subgroups. I think a more natural definition that aligns with existing fairness notions might be to additionally equalize (up to epsilon) the abstention rates across subgroups.\n\nThe authors defer a lot of details to the appendix, which can somewhat hurt readability. However, I understand that this is hard to avoid to some degree due to page limits.", "was_revised": true, "final_justification": "The authors have addressed most of my questions, and I am raising my score to a 5.", "rebuttal": "We thank the reviewer for their insightful questions. We answer them in the same order:\n\n(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\".  \n\nThe 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. \n\nLastly, 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.\n\n(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.\n\n(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.\n\n(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).\n\nWe 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.\n\nNext we address the “Other minor comments/questions”:\n\n(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.). \n\n(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.\n\n(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.\n\n(4) They refer to the $\\ell_1(y, t) = |y-t|$ and $\\ell_2(y, t) = (y-t)^2$ loss functions, respectively. \n\n(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.\n\n(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.\n\nThank you for all of the comments!"}, {"review_id": "gFekJ8WMo0", "reviewer": "Reviewer_snFc", "summary": "The paper proposes selective omniprediction, a framework with the scope of training once a single predictor for a class $\\\\mathcal{L}$ of convex Lipschitz losses by using data samples that can later be post-processed without additional data to compete with the best predictor in a given concept class $\\\\mathcal{C}$ with respect to a generalization of the Chow loss induced by a given loss function $\\\\ell \\\\in \\\\mathcal{L}$.\nThe main contribution of the selective omniprediction framework, which distinguishes it from plain omniprediciton, is that it allows classifiers to abstain whenever the risk of a misprediction can be too high.\nIt achieves this by first building a multicalibrated predictor $h$ and then applying a data-free post-processing $k\\_{\\\\ell}$.\nThe resulting abstention region is always shown to be a single contiguous interval and to allow a desirable coverage guarantee, while the method remains computationally efficient.\nThe construction yields positive, negative, and fully reliable learners for losses in $\\\\mathcal{L}$, subsuming earlier $0$-$1$ reliable learning results and enabling a simple conformal prediction scheme with bounded abstentions.\nBecause the approach relies only on the agnostic learnability of the base class $C$, it remains computationally practical too.\nSynthetic experiments confirm that a single multicalibrated omnipredictor, after task-specific post-processing, matches or surpasses other baseline models for each loss while abstaining exactly on the theoretically predicted interval, validating the approach in practice.", "questions": "- At line 91, the Bayes optimal predictor has a specific form. The general definition should be something like $f^*(x) = \\\\arg\\\\min\\_{t \\\\in \\\\mathbb{R}}\\\\mathbb{E}[\\\\ell(y,t) | x]$. Could you clarify how your definition is equivalent to the general one?\n- In the math display below line 100, shouldn't the conditioning on \"$g(x) = 1$\" be in the outer expectation?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper presents an interesting framework for selective omniprediction, which is well-motivated and theoretically sound.\nThis is obtained by extending the omniprediction framework to allow for abstention by considering a novel generalization of the Chow loss.\nOn top of that, the paper provides a clear and comprehensive overview of the theoretical results with multiple insights into the properties of the proposed method.\nFor instance, the notions of positive, negative, and fully reliable learnability are clearly described and adopted in order to perform conformal prediction, whose objective is to output prediction sets that provide a coverage guarantee for the true labels with respect to a given error rate $\\\\epsilon$.\nThe results are further extended to consider a notion of multigroup fairness, providing a way to construct a fair selective omnipredictor by relying on the notion of calibrated multiaccuracy.\nThe methods and concepts adopted could also be of interest in other related areas.\n\nIn addition to the positive theoretical results, the experiments are another strong point of this work.\nAlthough the empirical study is limited to a single synthetic dataset and a concise set of baselines, the selective omnipredictor attains significantly higher coverage than loss-specific abstaining decision trees while also achieving a lower total loss.\n\nOn the other hand, the write-up presents some typos that could affect the overall understanding of the results, since the notions handled in the arguments are somewhat delicate.\nThese mistakes are generally minor and should be easily fixable.\n\n**Minor comments and typos:**\n- Line 68: \"that true\" should be \"that the true\"\n- Line 82: it would be clearer to specify that the marginal distribution is over $\\\\mathcal{X}$\n- Lines 83-84: the absolute loss is called $0$-$1$ loss by the authors, which is correct if $t \\\\in \\\\{0,1\\\\}$ but might be a misleading name when $t \\\\in [0,1]$ in general\n- Line 85: \"$=$\" should be \"$\\\\subseteq$\"\n- Line 86: \"$\\\\ell_{\\\\mathcal{D}}$\" should be \"$\\\\ell_{\\\\mathcal{D}}(h)$\"\n- Line 91: it would be clearer to argue why the Bayes optimal predictor is defined as shown\n- Line 117: \"predictions\" should be \"predictions of\"\n- Line 147: \"any value of\" is a bit misleading, and it would be clearer to say something like \"a constant\"\n- Line 168: \"$c(x)$\" should be \"$c\\_{+}(x)$\"\n- Lines 198, 225: please, provide a more precise reference to the appendix\n- From line 227, the proof sketch of Theorem 3.1 has no clear end, so it would be better to put a q.e.d. mark when it is concluded\n- Line 288: in \"$\\\\mathcal{S}(x) \\\\subseteq \\\\mathcal{Y}$\", $x$ should not be bold\n- Below line 301, $c\\_{\\?}(x)$ should have a bold $x$\n- Lines 314-319: it would be clearer to make the dependence of $c\\_{\\?}$ on $g$ explicit, e.g., using $c\\_{\\?}^{g}$\n- Lines 325-327: just as a remark, it would suffice to assume that $\\\\mathcal{G}$ satisfies $\\\\bigcup\\_{g \\\\in \\\\mathcal{G}} g = \\\\mathcal{X}$\n- Lines 350-360: consider making this part a more explicit and structured remark, since it contains interesting observations\n- Line 368: \"$[0,1] \\\\cup \\?$\" should be \"$[0,1] \\\\cup \\\\{\\?\\\\}$\"\n- Line 369: $[1-\\\\epsilon,\\\\epsilon]$ should be $[1-\\\\epsilon,1]$\n- Line 370: specify the inequality holds \"for all $g \\\\in \\\\mathcal{G}$\"\n- Lines 538-565: the instructions block can be deleted", "was_revised": true, "final_justification": "I keep my already positive initial evaluation, also given that the authors replied to all my concerns and no sudden issue came up during the discussion.", "rebuttal": "We thank the reviewer for their insightful comments and questions. We answer them in order:\n\n(1) Thank you very much for pointing out these typos, we will make sure to correct all of them.\n\n(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.\n\n(3) Yes, that is correct about the conditioning on $g(x)=1$. We will correct it, thank you!"}, {"review_id": "BvG3buB7iR", "reviewer": "Reviewer_AQet", "summary": "This work extends the literature on omniprediction and multigroup fairness to the reliable learning framework. They define a selective omnipredictor for a class of loss triples (where losses may differ on negatively and positively labeled examples, as well as examples on which the classifier abstains) and concepts C to be a predictor h such that for every loss in L, and any associated weights for these losses, there exists an efficient post-processing function such that post-processing the predictions of h yields predictions with loss that is competitive with the best (potentially abstaining) post-processing of a concept in C. They prove that multicalibration is sufficient for selective omniprediction, and show that selective omnipredictors will abstain in contiguous intervals that balance the cost of abstention vs classification. They then consider the question of abstaining fairly, so that no group suffers gratuitous abstention for the sake of reliability. They show that calibrated multiaccuracy with respect to the class $C \\cap G$ is sufficient for fair abstention, and also observe that their fair selective classifier can be interpreted as providing group conditional coverage in the sense of conformal prediction.", "questions": "See comments above", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "This paper provides a very useful contribution to our understanding of multigroup fair and reliable classification. I don’t think there are many particularly novel techniques used to prove the results of this work, but I see its contribution more as giving the right definitions of models of fair abstention to make nice observations about how the properties of multicalibration and calibrated multiaccuracy facilitate fair, flexibly loss-minimizing, and reliable learners. \n\nI don’t think $C \\cap G$ was actually defined anywhere. It can be inferred via context and proofs, but would be good to define before first used in section 4. \n\nI think in one of the proofs it is assumed that the constant function g(x) = 1 is in G, but that assumption doesn’t appear in the theorem statement.", "was_revised": true, "final_justification": "I have a positive appraisal of the paper and I believe the updates proposed by the authors in the rebuttal will address my concerns regarding clarity", "rebuttal": "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!"}, {"review_id": "Gd3RekfS9L", "reviewer": "Reviewer_6Q23", "summary": "This paper proposes extending the “omniprediction” framework of Gopalan et al. to also allow predictors to abstain (a la selective prediction frameworks). The paper begins by introducing omniprediction and the multi-group fairness notions which allow achievable omniprediction (multiaccuracy, multicalibration, calibrated multiaccuracy). In section 2.3, the paper introduces the reliable agnostic learning framework. Any loss $\\ell$ is decomposed into a triple of losses $(\\ell_+, \\ell_{-}, \\ell_{?})$, which are respectively the cost of misclassifying a negative prediction, positive prediction, and the cost of abstention.\n\nGiven a concept class $\\mathcal{C}$, the paper defines $\\mathcal{C}^+$ as the subset of concepts in $\\mathcal{C}$ which have $\\ell_+(c, \\mathcal{D}) = 0$, that is, the subset of hypotheses which never have false positive predictions on the distribution $\\mathcal{D}$. Similarly define $\\mathcal{C}^-$ as the subset of hypotheses which never have false negative predictions.\n\nThe paper then defines the (agnostic) positively reliable learning (PRL) framework of Kalai et al. and Kanade et al. In short, a concept class $\\mathcal{C}$ with loss pair $(\\ell_+, \\ell_{-})$ is PRLearnable if the learner can output an $h$ w.h.p. Obtains both:\nIn expectation, $\\ell_+(h(x)) \\leq \\epsilon $ \n$h$ is competitive on $\\ell_{-}$ with the best $c \\in \\mathcal{C}^+$ for the loss $\\ell_{-}$. That is, $h$ is competitive with the best hypothesis which never has false negative predictions on the distribution.\nNegatively reliable learning (NRL) is defined analogously.\n\nFinally, the paper defines the class $\\textrm{SC}(\\mathcal{C})$ as the set of classifiers $c_?$, where each $c_?$ only predicts something other than ? on $x$ if there exist a pair of hypotheses $c_+ \\in \\mathcal{C}^+$ and $c_{-} \\in \\mathcal{C}^{-}$ agree. Intuitively, the class SC is filled with very cautious classifiers which will only predict not ? if there are two high confidence predictors which agree. The “fully” reliable learning framework (FRL) asks for a learner to output a $h_?$ which has low error on the sum of losses $\\ell_+$ and $\\ell_{-}$, and also is competitive w.r.t. The best $c_?$ in $\\textrm{SC}(\\mathcal{C})$.\n\nEverything up to now was introduced in previous selective classification frameworks (Kalai et al. Kanade et al.). In section 2.4, the paper introduces a generalization of the Chow loss model (triplet of losses $(\\ell_+, \\ell_{-}, \\ell_{?})$) which allows for weighing each sub-loss by constants $\\lambda, \\mu, \\nu$ respectively.\n\nFinally, we are ready to define selective omniprediction. We say that a predictor $h$ is a $(\\mathcal{L}, \\mathcal{C}, \\epsilon)$-select omnipredictor if the expected generalized chow loss of $h$ composed with a postprocessing function $k*$  (which maps from $[0,1] \\to \\mathbb{R} \\cup {?}$ ) is almost as good as the best $c_?$ coming from the class $k \\circ \\mathcal{C}$. This is exactly normal omniprediction, but we allow for \n1. post-processing functions to map certain regions of predictions from $[0,1] \\to ?$\n2. The loss function class to be the generalized chow loss, which penalizes ? differently.\n\nNote that $k^*$ is the optimal post-processing function for a specific loss triplet for the Bayes optimal predictor, similar to the optimal post-processing function from normal omniprediction).\n\nIn theorem 3.1, the paper claims that selective omniprediction is achievable. In fact, it follows from standard omniprediction with no adjustments except for the post-processing functions $k$ which allow for abstention. Interestingly, lemma 3.2 shows that the interval where k^* abstains is a contiguous subset of $[0,1]$.\n\nIn section 3.1, a nice experiment is run which demonstrates that multicalibration + selective omniprediction achieves comparable / better generalized Chow loss in practice relative to training a depth-3 decision tree for each loss individually. This provides empirical evidence for Theorem 3.1.\n\nNext, in theorem 3.3, the paper utilizes selective omniprediction to generalize the existing results for PRL, NRL, and FRL beyond the 0-1 loss and to an entire family of losses. Of note is that many of the results up until now extend to some important families of non-convex losses, similar to recent work in normal omniprediction. In Lemma 3.4, the paper shows how the FRL allows the predictor to have guarantees on the fraction of the distribution it abstains on (via conformal prediction sets). \n\nNext, the paper turns towards group-fairness notions based on selective classification. In particular, the paper asks whether we can provide accurate predictions overall and not penalize certain subgroups of the population $\\mathcal{G}$ by abstaining more on them than necessary. Along this vein, the paper defines a $(\\mathcal{C}, \\mathcal{G})$-selective classifier as one which produces both good overall error, and also achieves optimal abstention rate when compared to the best in class abstaining predictor $c_? \\in \\textrm{SC}(\\mathcal{C})$ for each subgroup $g \\in \\mathcal{G}$. In Theorem 4.1, the paper shows that global calibration + multiaccuracy w.r.t. The intersection class $\\mathcal{C} \\cap \\mathcal{G}$ suffices to achieve this notion of group sensitive selective classification. In Lemma 4.2, the paper then shows that for finite $|\\mathcal{G}|$, we don’t need a weak agnostic learner for the intersection of the concepts in order to achieve group sensitive selective classification.\n\nFinally, in section 4.1, the paper shows that $(\\mathcal{C}, \\mathcal{G})$-selective classifiers also satisfy group-conditional conformal coverage guarantees which have recently become popular. These state that the resulting predictor has good conformal guarantees not only overall, but also when conditioned on subgroups of the population $\\mathcal{G}$.", "questions": "1. Coverage as a concept does not seem to be defined before it is used in Table 1. Does coverage mean that the predictor is abstaining less and predicting more? On that note, why is the coverage so different for training DTs from scratch versus selective omniprediction? Also, are there fundamental limitations to high coverage for all losses?\n\n2. Is there a typo in the definition of 0-1 loss where it is first introduced? It is currently defined as $|y - t|$, however, for $t \\in \\mathbb{R}$ (as stated in line 83), this is not the 0-1 loss, this is the $\\ell_1$ loss. Throughout the paper, we are working with predictions from a concept class $\\mathcal{C}$ which only contains hypotheses which map to ${0,1}$, so that’s fine. However, this isn’t true when you introduce the 0-1 loss in line 82/83, where you allow $t \\in \\mathbb{R}$.\n\n3. I think more discussion on the class $\\textrm{SC}(\\mathcal{C})$ is warranted. Why is this class interesting or important to be competitive w.r.t.? How do selective classification and selective omniprediction relate to each other? I understand that the former compares to the best in class for $\\text{SC}(\\mathcal{C})$, whereas the latter for the best in class $k \\circ \\mathcal{C}$, but how should I think about the relative strengths of the results in Theorems 4.1 and 3.1? Are they in some sense incomparable because the baselines are different? However, the calibrated multiaccuracy requirement is also a weaker condition than full multicalibration, so I would assume 3.1 is stronger. Is it strictly stronger (a la multicalibration vs. calibrated multiaccuracy)?\n\n4. Is $\\mathcal{C} \\cap \\mathcal{G}$ the class of all intersections of concepts from $\\mathcal{C}$ and $\\mathcal{G}$? Isn’t this difficult to achieve multiaccuracy for in general? It seems so, given the fact that this requires a weak-agnostic learner for the class. I understand this is why Lemma 4.2 is proposed.\n\n5. Do we have lower bounds for omniprediction, and do these extend to selective omniprediction?", "limitations": "The authors include some limitations implicitly in lines 342-345. It may be good to point out that a WAL for the intersection class can be difficult to obtain (in theory, not sure about in practice). Perhaps one could also highlight the higher sample complexity for full multicalibration (and hence, selective omniprediction) vs. calibrated multiaccuracy.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I believe that the paper is a clear accept. It extends both the selective prediction and omniprediction frameworks, showing that they combine in a relatively straightforward way. Learning to abstain has become a popular topic, especially in fairness, and combining utilizing the omniprediction guarantees seems to naturally present some nice technical solutions to this. In addition, I really enjoy that the paper has significant numerical experiments with reasonable classes of predictors (depth 3 decision trees, random forests etc.). The paper also has some nice connections between omniprediction and conformal prediction, which I have not ran into before (although I don't keep up with the omniprediction literature, and have read only the first Gopalan et al. paper). In addition, to the best of my knowledge there is plenty of potential for future work with selective omniprediction in, for example, online settings which have become quite popular in the omniprediction community.\n\nOverall, the paper introduces the abstention framework to the omniprediction line of work, which may prove to be fruitful for future research in this area.\n\nMinor Weaknesses:\n1. The proofs, while numerous, seem relatively straightforward given the definitions proposed in this paper, the definition of omniprediction, and the definitions of PRL, FRL, NRL, etc. However, I think this is not a major weakness. In particular, I believe that this means that the selective prediction definitions in this paper were chosen correctly if things work out so nicely.\n2. In some sense, there are many results in the paper (and further experiments demoted to the appendix). Given that omniprediction papers rarely have experiments, I would perhaps recommend giving informal theorem statements for some of the later results, and trying to include more of the experimental results in the main paper. For the average neurips audience, this could be especially interesting / useful.", "was_revised": true, "final_justification": "The authors answered all my minor questions / clarifications, and will take them into consideration in the next draft of the paper. I believe that the paper is a clear accept since it advances the ominprediction and selective prediction literature in a very intuitive and clean manner.", "rebuttal": "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:\n\n(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 $½$). \n\nRegarding 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.\n\n(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!\n\n(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.\n\nRegarding 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’$. \n\nLastly, 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).\n\nIt 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.\n\n(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.  \n\nSeparately, 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.\n\n(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? \n\nLastly, 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!"}]

Author rebuttal:

Meta-review: The paper studies omniprediction in the setting of selective classification, i.e., where it can abstain from making a prediction. The authors present a post-processing framework that allows a single classifier to optimally learn abstentions and predictions for any pre-specified class of loss functions. They then turn their sights on “fair abstention” by extending multicalibration algorithms to consider abstention. Their main result in this setting is an efficient construction of a (fair) selective classifier from a multiaccurate and calibrated predictor.

Strengths:
- The paper is well-motivated and overall well-structured (but see weakness below).
- The reviewers agree that both the theoretical and empirical results are strong and make a meaningful contribution to the field of omniprediction and selective prediction.

Weaknesses:
- The reviewers identified quite a few typos and areas where exposition was lacking; the authors promised to fix these in the camera-ready version of the paper and reviewers were by and large convinced.
Decision: Accept (spotlight)