Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration
Authors: Parikshit Gopalan
Michael P. Kim
Omer Reingold
Venue: NeurIPS 2023 poster (2023)
Keywords: Agnostic Learning
Omniprediction
Multicalibration
TL;DR: Introduces swap agnostic learning and shows feasibility via a suprising equivalence to swap variants of omniprediction and multicalibration.

Abstract: We introduce and study the notion of Swap Agnostic Learning.
The problem can be phrased as a game between a *predictor* and an *adversary*:  first, the predictor selects a hypothesis $h$; then, the adversary plays in response, and for each level set of the predictor, selects a loss-minimizing hypothesis $c_v \in \mathcal{C}$; the predictor wins if $h$ competes with the adaptive adversary's loss.
Despite the strength of the adversary, our main result demonstrates the feasibility Swap Agnostic Learning for any convex loss.
Somewhat surprisingly, the result follows by proving an *equivalence* between Swap Agnostic Learning and swap variants of the recent notions Omniprediction (ITCS'22) and Multicalibration (ICML'18).
Beyond this equivalence, we establish further connections to the literature on Outcome Indistinguishability (STOC'20, ITCS'23), revealing a unified notion of OI that captures all existing notions of omniprediction and multicalibration.

Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration
Parikshit Gopalan Apple, Inc.
Michael P. Kim UC Berkeley
Omer Reingold Stanford University
Abstract
We introduce and study Swap Agnostic Learning. The problem can be phrased as game between predictor and an adversary: first, the predictor selects a hypothesis h; then, the adversary plays in response, and for each level set of the predictor {a E X h(x) = v) selects a loss-minimizing hypothesis C, E the predictor wins if p competes with the adaptive adversary's loss. Despite the strength of the adversary, our main result demonstrates the feasibility Swap Agnostic Learning for any convex loss. Somewhat surprisingly, the result follows by proving an equivalence between Swap Agnostic Learning and swap variants of the recent notions Omniprediction [15] and Multicalibration [20]. Beyond this equivalence, we establish further connections to the literature on Outcome Indistinguishabbiity [6, 14], revealing unified notion of OI that captures all existing notions of omniprediction and multicalibration.
Introduction
Since its inception as an extension to Valiant's PAC framework [30, 19, 23], Agnostic Learning has been the central problem of supervised learning theory. Agnostic learning frames the task of supervised learning through loss minimization: given loss function e, hypothesis class C, and E 2 0, a predictor is an agnostic learner if it achieves loss that competes with the minimal achievable within the hypothesis class.
E[e(y, [(x))] & min E(((y.c(x)) +
<EC
While the agnostic learning paradigm has been remarkably successful, in recent years, researchers have investigated alternative learning paradigms to address concerns of the modern prediction pipeline, including fairness and robustness. The work of [20] introduced multicalibration
new paradigm learning fair predictors. Multicalibration asserts fairness as a first-order goal, requiring that predictions appear calibrated even conditioned membership in one of a potentially-huge collection of subgroups C of the domain.' As a solution concept, multicalibration can be achieved efficiently using a weak learner for C to identify subgroups where predictions miscalibrated. In contrast to agnostic learning, multicalibration does not make reference to minimizing any loss.
Yet, it turns out that there are surprising connections between multicalibration and agnostic learning. This connection was first discovered in the work of [15], who introduced the notion of omniprediction as new solution concept in supervised learning. Intuitively, that provides the agnostic learning guarantee for many losses simultaneously. More formally, for collection of loss functions L and hypothesis class C, a predictor is an omnipredictor if for any loss the collection L, the predictions achieve loss that competes with the minimal achievable
omnipredictor is single predictor
'This collection of subgroups is suggestively denoted by C, indicating that (in correspondence with a hypothesis class) subgroup membership can be computed using models of bounded capacity, such as small decision trees, halfspaces, neural networks.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

within the hypothesis class. 2 The main result of [15] demonstrates that multicalibrated predictors are omnipredictors for Levx the class of all convex loss functions. In other words, the multicalibration framework is capable of guaranteeing agnostic learning in very strong sense: learning a single multicalibrated predictor gives an agnostic learner, for every target convex loss & E Levx. The results of [15] stand in contrast to the convential wisdom that optimizing predictions for different loss functions requires a separate training procedure for each loss.
On the surface, multicalibration seems like a fundamentally different approach to supervised learning than agnostic learning. The implication of omniprediction from multicalibration, however, suggests a deeper connection between the notions. In fact, follow-up work of [14] gave new constructions of omnipredictors (for different loss classes L). similarly deriving the guarantees from variants of multicalibration. To summarize the state of the art, we have constructions of omnipredictors of various flavors, and all such constructions rely on some variant of multicalibration. While multicalibration suffices to guarantee omniprediction, glaring question remains in the development of this theory: multicalibration necessary for onniprediction? We investigate this question, exploring the connections between agnostic learning, notions of omniprediction, and multicalibration.
Our Contributions. In this work, provide new perspective that unifies these seemingly- incomparable paradigms for supervised learning. Key to this perspective, we introduce a new learning task, which we call Swap Agnostic Learning. This swap variant of agnostic learning is inspired by the notion of swap regret in the online learning literature [10, 2]. where the learner must achieve vanishing regret, not simply overall, but even conditioned on their decisions. While swap agnostic learning is a natural extension, at first glance, it is considerably stronger goal than standard agnostic learning. Nevertheless, our work demonstrates an efficient algorithm for swap agnostic learning for any convex loss function, leveraging only a weak agnostic learner for the hypothesis class. The algorithm follows by discovering surprising connection: swap agnostic learning and swap variants of omniprediction and multicalibration are actually equivalent. In other words, once we move to swap variants, multicalibration is necessary for omniprediction, and even for agnostic learning. We show how the original multicalibration algorithm of [20] actually guarantees the stronger goal of "swap multicalibration" " (and thus, swap omniprediction and swap agnostic learning). Our results provide an exact characterization of these swap learning notions, as well as relationships between other learning desiderata explored recent works [6, 14].
Our motivation for introducing Swap Agnostic Learning comes from trying to understand the relation- ship between (standard) multicalibration and omniprediction. Prior work shows that multicalibration implies (convex) omniprediction, but leaves open the question of whether omniprediction implics multicalibration. The present work sheds new light on this question, suggesting that the asnwer is no: standard omniprediction does not imply multicalibration. The answer to this question comes by introducing the idea of Swap Learning, in the agnostic leariin/onmiipreiiciion setting, as well as in multicalibration. Importantly, for multicalibration, Swap multicalibratin and Standard mul- ticalibration are essentially the same notion. Claim 2.9. as well as our analysis of prior algorithms for multicalibration, shows that standard multicalibration is already strong enough to capture the swap variant. The distinction (definitionally and algorithmically) between swap and standard mul- ticalibration is minimal: our results suggest that one should really think of them as a single notion of multicalibration For agnostic learning and omniprediction, however, Swap Learning is much stronger than Standard Learning. We prove separations between swap and standard omniprediction in Appendix B. The separations are summarized in figure 1. This tells us that (swap) multicalibration is equivalent to the stronger notion of swap omniprediction, which is provably stronger than standard omnipreidiction.
Organization. We continue the manuscript with formal setup and defintions of Swap Agnostic Learning, Swap Omniprediction, and Swap Multicalibration. Then, in our main result, we prove the equivalence of these notions. This equivalence suggests an efficient algorithm for Swap Agnostic Learning. We conclude with an overview of our other results, as well related work and discussion. Throughout the manuscript, we include formal definitions of key notions and proof' of essential claims. We introduce the notion os swap loss OI which generalizes omniprediction in Section In
OOn technical level. the omniprediction guarantee is made possible by post- post-processing the predictions after the loss is revealed. Importantly, the cost-processing is data-free univariate optimization that can be performed efficiently, based only on the loss function and not the data distribution.

---

Section B, we dicuss the relation and show separatiosn between various notions of omniprediction. All omitted proofs of formal claims are included in the Appendix.
2 Formal Setup: Swap Notions of Supervised Learning
We work in the agnostic learning setting, where we assume a data distribution (x, y) ~ DD supported on X' {0, 1]. The objects of study in agnostic learning real-valued hypotheses h X - R. Omniprediction and multicalibration study the special case of predictors ý X' - [0. 1] that map domain elements probabilities. We denote the Bayes optimal predictor p p'(x)
Pr(y 1|x = æt. As is standard in agnostic learning, we make no assumptions about the complexity of p" : X [0, 1]. While, in principle, predictors and hypotheses may take on continuous values in R, we restrict our attention to functions supported on finitely-many values. We let Im(ğ) S [o, 1] denote the set of values taken on by p(z).
Given a hypothesis h X' - R. it will be useful to imagine drawing samples from D two steps: first, we sample a prediction v E R according to the distribution of h(x) under D; then, we draw the random variables (x.y) y) according to the conditional distribution D D)h(x)= = v. Accordingly, let Dr, denote the distribution of h(x) where D.
2.1 Swap Agnostic Learning
Swap agnostic learning is defined with respect to loss function é: (0, x RR + R and hypothesis class C {c + IR} and can be viewed as a game with two participants. The predictor plays first and selects a hypothesis h X + R. The adversary plays in response: for each level set {z Æ : h(z)= = v), the adversary may choose separate mos-mminiizzing hypothesis co E C.
Definition 2.1 (Swap Agnostic Learning). For loss function E, hypothesis class C. and error E 2 0, hypothesis h is a (E, E))saap agnostic learner if
E(e(y,c((x) = v) +e.
Ble(y,h(x)))
S
E v~DA
min [cEEC
We borrow nomenclature from online learning: a predictor using swap agnostic learner h has no incentive to "swap" any of their fixed predictions lxx) to predict according to c, E C. Contrasting the requirement in (2) to that of agnostic learning in (1), we have switched the order of
quantifiers, such that the minimization is taken after the expectation over the choice of h(()
Swap agnostic learning strengthens standard agnostic learning, where the predictor only competes against the single best hypothesis C.
Indeed, swap agnostic learning seems to be much more stringent condition. Provided the class C contains all constant functions, the adversary can simply imitate the predictor when h(z) by choosing co (x) v. For such C, (2) implies that imitation is the best strategy for the adversary.
2.2 Swap Omniprediction
As in [15, 14], we observe that for any loss function l and known distribution on outcomes y Ber(p) for Prr& E [0, 1]. there is an optimal action ke(p) that minimizes the expected loss É, Formally, we define the optimal post-processing of predictions by the function le [0, 1] - R. which specifies the action that minimizes the expected loss.
kp(p) arg min
E EER y>
[C(y, t)].
This observation is particularly powerful because the function ky is given by simple, univariate optimization that can be used as a data-free post-processing procedure on top of a predictor p.
We recall the original notion of omniprediction proposed by [15]. which requires predictor to yield an agnostic learner simultancously for every loss in a collection L. Concretely, omniprediction requires that the function fe k p is an (f, aaggnottii learner for every l E L.
If there multiple optima, break ties arbitrarily.
3

---

Definition 2.2 (Omnipredictor, [15]). For a collection of loss functions L, a hypothesis class C, and enror 0, predictor p X [0, 1] an .oomiieinniir for every & C,
Ele(y, k( I min Ele(y, +
(4)
aEC
We propose strengthened notion of Swap Omniprediction, where the adversary may choose both the loss l, E C and hypothesis G, E based on the prediction p(z) = v.
Definition 2.3 (Swap Omnipredictor). For collection of loss functions L, hypothesis class C, and error & > 0, a predictor p : X' + [0, 1] is a loss functions (lo vELLm())
omnipredictor for any assignment of
E V~22
Bleu(y, (u)) f(x)= - v1] v
E v>D2
min (x))( (x()) J3
v (5)
+
Swap omniprediction gives the adversary considerable power. For instance, the special case where restrict the adversary's 's choice of losses to be constant, L, = f, realizes swap agnostic learning for
Claim 2.4. If is (. omnipredictor, it is (l, seswap agnostic learner for every E C, and hence a -ooniircciirrii
Analogous to the standard notions, swap omniprediction implies swap agnostic learning for every e however, swap omniprediction gives an even stronger guarantee since the adversary's 's loss E, may be chosen in response to the prediction p(x) v.
2.3 Swap Multicalibration
Multicalibration was introduced in the work of [20] as a notion of algorithmic fairness following [26]. but has since seen broad application across many learning applications (e.g.. [6, 15, 25, 18]). Informally, multicalibration requires predictions to appear calibrated, not simply overall, but also when we restrict our attention to subgroups within some broad collection C. The formulation below appears in [14].
Definition 2.5 (Multicalibration, [20]). For hypothesis class C and a 2 0, predictor p X - [0, 10 is (C, miuliiaabiiee if
max E <EC v>>Dg
E(c(x) ( vv)
= Sa.
(6)
When c X' -> 10 1) is Boolean (and has sufficiently large measure), this definition says that conditioned on c(x)= = 1, the calibration violation small, recovering the definition in [20].
Swap Multicalibration strengthens multicalibration, extending the pseudorandomness perspective on
multicalibration developed in [6. 15]. Swap multicalibration requires that for the typical prediction Dj. no hypothesis in Co E C achieves good correlation with the residual labels over D conditioned on p(x) = v. Definition 2.6 (Swap Multicalibration). For hypothesis class C and 0. predictor p X [0,1] is (C, aswapp multicalibrated if
Blc,(x 15(x) -v| Sa.
E V- D3
ECEC
Again, the difference between swap and standard multicalibration is in the order of quantifiers. The standard definition requires that for every E C, the correlation [c()((c (vv)] achieved in small in expectation over Dz.. Swap multicalibration considers the maximum of Epj, (c(x) [c)))((()(( over all e E C for each fixing of v and requires this to be small in expectation over v Dp- It follows that swap multicalibration implies standard multicalibration.
v)]l
Claim 2.7. If p is (C, -swap multicalibrated, it is (C, a) multicaaallii.
While swap multicalibration is nominally a stronger notion that than standard multicalibration. the complexity of achieving swap multicalibration is essentially the same as multicalibration. We show that starting from a (C, mmmuticcallibrated predictor ý. by suitably discretizing its values, we obtain predictor that is close and a' (Caa')-saap multicalibrated, with some degradation in the value of a'.

---

Definition 2.8. Let 8 E [0. 1] so that m = = 1 Z. Define B [[j 1)6, for E [m - and and
B, [1 6, 11. Define the predictor Ps where for every x such that p(x) B, Ps(x) =
Claim 2.9. Let p X + [0. 1] be a (C, ..)lliiciicallbbrrtted For any 8 E [0, 1] where 1/6 Z, the predictor Ps is (C, 2 /a/8 5 5)-swap multicalibrated, and max (p(x) P5( - 6.
While the bound of the theorem is valid for all 6, the swap multicalibration guarantee is only meaningful when 5 2 ((a)). Thus, by discretizing (C, (...)-))ilicaalbrrtte predictor, we obtain a (C, O(sl/3))-swap multicalibrated predictor. While this generic transformation suffers a polynomial loss in the accuracy parameter, such a loss may not be algorithmically necessary. As we argue in Lemma 3.8, known algorithms for achieving multicalibration [20, 15] actually guarantee swap multicalibration without any modification.
3 An equivalence: swap agnostic learning, omniprediction, multicalibration
Our main result is an equivalence between swap agnostic learning, swap omniprediction, and swap multicalibration. Concretely, this equivalence shows that swap agnostic learning for the squared error is sufficient to guarantee swap omniprediction for all (nice) convex loss functions. We begin with some preliminaries, then formally state and prove the equivalence. We conclude the section by showing how to use the existing framework for learning multicalibrated predictors to achieve swap agnostic learning for any convex loss.
Nice loss functions. For loss function é: {0, 1} x R- + IR, we extend & linearly to allow the first argument to take values in the range E [0, 1] as:
t(p y~Ber(p)
E
( t)] p {(1,)) + (1 p) E(),
We say the loss function is convex if for y E {0, E(y,t) 1) is convex function of By linearity, this convexity property holds for E(p, 1) for all p.
As in [14], for loss E, we define the partial difference function de: IR + R as
ae(t) = {(1,t) E(O,t).
We define a class of "nice" loss functions, which obey a minimal set of boundedness and Lipschitzness conditions.
Definition 3.1. For a constant B > 0, a loss function is B-nice if there exists an interval Ie C IR such that the following conditions hold:
1. (Optimality) If Ulg R + 1t denotes projection onto the interval 1g, then Up, lle(t)) S E(p, for all t E R and E [0, 1].
2. (Lipschitzness) For y E {0, 1} and 1 E Tg, ((u,t) is 1-Lipschitz as a function of
3. (Bounded difference) For E Ls, [0e(t)) < B.
The class of all B-nice loss functions by L(B). The subset of B-nice convex loss functions is denoted by (B..
Bounded loss functions generalize the idea of loss functions defined over a fixed interval of IR (by optimality) and of bounded output range (by bounded difference). By optimality of nice loss functions, we may assume ke [0, 1] + le since we do not increase the loss by projection onto 4e. Indeed, for convex losses the natural choice for 1e is take the interval [O), ke (1)]. The bounded difference condition implies that e is Lipschitz in its first argument, property that will be useful.
Lemma 3.2. For every é L(B) and to Le. the function E(p, to) is B-Lipschitz as a function p.
Concept classes. For a concept class of functions C : fc X - R}. we assume that C is closed under negation, and it contains the constant functions 0 and 1. Denoting ||e|| max |e(z) over E C, x E X, we say that C is bounded if ||e|loo < 1. For W E R+, let Lin(C, W) be all functions that can be expressed as a (W- -sparse) linear combination of base concepts from C,
(x) Σ We c(x),
Σ
wel I W.
5

---

Note that for bounded C, the norm of linear combinations scales gracefully with the sparsity, [[Lin[C, a W. We define Lin(C) to be the set of all linear combinations with no restriction on the weights of the coefficients.
Notation. To simplify notation, we use the following shorthand for the data distribution condi- tioned on p(x) For each E Iın()), let D), denote the conditional distribution D Combined with earlier notation, the distribution D/v for ~ Dj is simply the data distribution D. We also use the notation (p(x),y) (v, y) to indicate p(x) and
3.1 Statement of Main Result
Theorem 3.3. Let P a predictor, C be bounded hypothesis class, and Cex( be the class of B-nice convex loss functions. The following properties are equivalent:"
1. p (C, )-)wap multicalibrated.
2. p an (Cev (B), Lin(C, W), O((W + -Ssaa omnipredictor, for all W 21,B20
3. p an (fz, Lin 2), aswas agnostic learner.
In preparation for proving the theorem, establish some preliminary results. We define function a Im( + [-1, 1] which measures the maximum correlation between c and y U. conditioned on prediction value E Im((). Let
(
max E (x) vi] E. Di
Using this notation, (C, (aa--wap multicalibration can be written as
E [a(v)] S ap-
V-
We observe that swap multicalibration is closed under bounded linear combinations of C, like with standard multicalibration.
Claim 3.4. For every h E Lin(C, W) and E Im(p), have
[(h(x)(y -()xx)())))x(x)) w) Wa(u).
keLin(C,W)
Let pt Elylp(x) v). Then
1r: rl S a(v)-
(8)
Equation (8) follows since 1 E
Claim 3.5. For h E Lin(C, w), v E Im(p) and y E {0,1}, 1}. define the following conditional expectations:
u(h: = E(M(x) p(x) = c]
((h: v, E[M(() = (v.y))-
Then for each y {0, 1}
Pr(y plp( = u| [1( v. v) p(h: v)1 (W + 1)a(v).
(9)
Next we show the following lemma, which shows that one can replace h((x) by the constant [T(()(h: r)) without large increase in the loss.
Lemma 3.6. For all h Lin(C, W), Im(β) and loss é Levx have
E [, [l(((h: u))l S E [f(y, h())] + 2(W + 1)a(v). DI.
(10)
'When we say these conditions are equivalent, we mean that they imply each other with parameters o, that polynomially related. The relations we derive result most quadratic loss parameters.

---

In the interest of space, we defer the proof of the Lemma to the Appendix.
Next compare [T(p(h v)) with (z))). It is clear that the latter is better for minimizing loss when y ~ Ber(u), by definition. We need to compare the losses when y ~ Ber(p.)- But p. and v most ((v) apart by Equation (8). Hence, by using Lipschitzness,
infer that ke(v) is better than [ u)) and hence hxx). This is formalized in the following lemma and its proof. Lemma 3.7. For all E Tm(Ø), E Levx( ()) and E Lin(C, W), we have
E (((,)))(((x))) - E [e(y,,(x))) + 2(W + B + 1)a(v).
(11)
DI.
Proof. By the definition of ke, ke(v) minimizes expected loss when y ~ Ber(v), so ((u,k((v) S (e((hh)))(
(12)
On the other hand,
E [e t)] E(pT, t), where p = E [y].
D).
D).
Thus our goal is compare the losses ((pt, t) for t ke(u) and t Ile(p(h v)). Hence, applying Lemma 3.2 gives
E(p' ke(v)) S ke))) + a E(p.. [Te(((h: v)) S l((u, [T v)) + a(e)
Subtracting these inequalities and then using Equation (12) gives
Epr ke(v)) E(pt, He(p(h: v)) S E(v, ke())) E(v, Ie((((h : o)) + 2Ba(u)
(13)
S B.
(14)
We can now write
E (eyy ke(u))] Uip ke(v)) Dlo
I E(pt, [e(((h v)) + +a(
(by Equation (14))
E [ely, [e( v)) 2a(1)
D).
< E [ely, 2(W + +1)((v) + 2Ba(v). D).
(by Equation (10)
We now complete the proof of Theorem 3.3.
Proof of Theorem 3.3. (1) = (2) Fix a (C, swap multicalibrated predictor p. Fix a choice of loss functions {lo E Leex (eem)() and hypotheses {hv E H)velm(f) For each v, apply Equation (1I) with the loss = Ly, hypothesis h h2 to get
E [Lo ke, (v))] < E [Lx hy (x)) + 2(W + B 1)a(t). DI.
DI.
We now take expectations over v ~ Dj. and use the E(a(v)] < ai to derive the desired implication.
(2) (3) with 03 Tag because l is 1 1/2-nice loss function,
plug in B 1/2 and
W = 2 into claim (2).
It remains to prove that (3) - (1). We show the contrapositive, that if P is not a multicalibrated, then f = f not a (&2, Lin(C, 2), ssaps agnostic learner. By the definition of multicalibration, for every Im(ğ), there exist such that
E (x) f(x)) (v) DI.
E
[ 2 a1
D,
By negating C, if needed, we may assume a(w) 2 0 for all We now define the updated hypothesis h where
h' h'(z) a(v)c, for p (c)
7

---

Algorithm Swap Agnostic Learning via MCBoost
Parameters: loss l, hypothesis class C, and 0, let poly(s)
Given: Dataset S sampled from D
Run:
P + (C
h4 t k2 o
Return: he
A standard calculation (included in the Appendix) shows that
E Dic
(yy - v) - E
[(y 1 h²(x))) 2 a(v)?
DIc
Taking expectation over v ~ Dp. we have
E E ly - u)
E Div
[yy - (2(())91
2 B[a(v) E E[a(v)}² az. Dj
D3
remains to show that v + ag Co (z) E Lin(C, 2). Note that
E (y(x)( u) I max |o(x) max(ly p(x)) S D).
ag
since c(x), - o E [-1, 1]. Hence n'(x) = w1 1 wzzc(v) where |w + |uaz S 2. This contradicts
the definition of an (l2, Lin 2), -swpp agnostic learner if ag a..
3.2 An algorithm for Swap Agnostic Learning
The equivalence from Theorem 3.3 suggests an immediate strategy for obtaining swap agnostic learner. First, learn swap multicalibrated predictor; then, return the predictor, post-processed to an optimal hypothesis according to E. While the MCBoost algorithm of [20] was designed to guarantee multicalibration, we observe that, in fact, it actually guarantees swap multicalibration.
Lemma 3.8. Suppose the collection C has weak agnostic learner, WAL. For any O, MCBoost makes at most poly(1/or calls to WAL and returns (C, a -swap multicalibrated predictor
Weak agnostic learning is basic supervised learning primitive used in boosting algorithms. Through the connection to boosting, weak agnostic learning is polynomial-time equivalent agnostic learning, and inherits its data-efficiency (scaling with the VC-dimension of C), but also its worst-case computa- tional hardness [27]. Importantly, however, MCBoost reduces the problem swap multicalibration (and thus, swap agnostic learning) to standard agnostic learning task. We review MCBoost weak agnostic learning formally the Appendix.
In all, we can combine the MCBoost algorithm for a class C with specific loss e to obtain (E, C. -swap agnostic learner.
Corollary 3.9 (Informal). For any (nice) convex loss E, hypothesis class C, and e > 0, Algorithm I returns a (e, e)-swap agnostic learner from sample of < VC(C)- (oCC)))oly(1/)) data points drawn from D, after making I poly(1/E) calls to weak agnostic learner for C.
Beyond Swap Agnostic Learning: Swap Loss Outcome Indistinguishability
In this we introduce unified notion of Swap Loss Outcome Indistinguishability which captures all of the other notions of mutlicalibration and omniprediction defined so far. The notion builds on line of work due to [6, 7], which propose the notion of Outcome Indistinguishabbliiyy (OI) solution concept for supervised learning based on computational indistinguishabiity.
fact, the main result of [6] is equivalence between OI and multicalibration. Despite the fact that OI is really multicalibration in disguise, the perspective has proved to be a useful technical perspective.
Key to this section is the prior work of [14]. This work proposes a new variant of OI, called Loss OI. The main result of [14] derives novel omniprediction guarantees from loss OI. Further, they show how to achieve loss Ol using only calibration and multiaccuracy over class of functions derived from the loss class L and hypothesis class C. As we'll see, this class plays a role in the study of swap loss OI: swap loss OI is equivalent to multicalibration over the augmented class.
8

---

Additional Preliminaries. Intuitively, OI requires that outcomes sampled from the predictive model P are indistinguishable from Nature's outcomes. Formally, we use (x,y") ) to denote a sample from the true joint distribution over X x {0, 1.. Then, given predictor p. we associate it with the random variable with E []] = f(æ),, i.e., where y/z ~ Ber(p(a)). The variable y can viewed as fjs simulation of Nature's s label y". In this section, we use 'D to denote the joint distribution (x,y", y), where Ely |x] = p" (a: and Ejy a|] p(z). While the joint distribution of (y",)) is not important to us, for simplicity we assume they are independent given x
4.1 Swap Loss OI
The notion of loss outcome indistinguishabiiityy was introduced in the recent work of [14] with the motivation of understanding omniprediction from the perspective of outcome indistinguishabiiiy
[6]. Loss OI gives strengthening of omniprediction. It requires predictors p fool a family 2 of statistical tests u X' x [0, 1] x {0, } that take point x E X, a prediction p(x) E [0, 1] and label y E {0. 1} as their arguments. The goal distinguish between the scenarios where y y is generated by nature versus where y y is simulation of nature according to the predictor p. Formally, we require than for every u U4
E p(x), me Elu(x, p(x).
D
Loss OI specializes this to specific family of tests arising in the analysis of omnipredictors. Definition 4.1 (Loss OI, [14]). For a collection of loss functions L, hypothesis class C, and 2 0, define the famity of tests (C, {ue,chee where
ue,c(x, u. y) Ely, ke(v)) Ely, c(z)).
(15)
A predictor p: x + [0, 1] is (C,CC O1 for every u E U(C, C), it holds that
E (x.y J~D
ju( (x. p(x),
E (x.9)~((i)
((x), 3)1 Se.
(16)
[14] show that loss-OI implies omniprediction. Lemma 4.2 (Proposition 4.5, [14]). If the predictor ğ is (C, eloss OI, then it is an (C, s.) onnipredictor.
Indeed, the expected value of u is nonpositive for all u E U(CCC), then p must achieve loss competitive with all C. The argument leverages the fact that must be nonpositive when y ~ (xxe((((x))-a -ftter all, in this world ý is the Bayes optimal. By indistinguishability. I must also be optimal in the world where outcomes drawn y". The converse, however, is not always true.
Next, we introduce swap loss OI, which allows the choice of distinguisher to depend on the predicted value.
Definition 4.3 (Swap Loss OI). For a collection of loss functions L. hypothesis class C and 2 O, for an assignment of loss functions {Le () and hypotheses (he E Hivetm(p) denote Uhe Uee, c. E EU(L,C). A predictor p is (L, (C, aswssapp loss O1 if for all such assignments,
E D~
E [x, v,y") uy (x, v. v) Sa. Dlv
The notion generalizes both swap omniprediction and loss-Ol simultaneously. Lemma 4.4. If the predictor ñ satisfies (C,C, or)-swap loss O1, then
is an (C, ai)- omnipredictor.
is (L, -loss OI.
This Section continues as Section A in the Appendix, where we show the following characterization of loss OI.
Theorem 4.5. Let L be a family of nice loss functions containing the squared loss. For any hypothesis class C, a predictor satisfies C)-sapp loss Ol if and only if it is (AL a Cw-swap multicalibrated, where dL C (al c)EEC.EEC

---

Related Work and Discussion
Independent concurrent work. The notion of strict multicalibration was defined in independent work of [8]. They connect this and other multigroup fairness definitions to various versions of the Szemeredi regularity lemma [28] and its weaker version due to Frieze and Kannan [11], following [29]. Their notions bears important similarities to swap multicalibration, but it is different. Like swap multicalibration, strict multicalibration involves switching the order of expectations and max. But they require statistical closeness guarantee, whereas we only require first order guarantee, that c(x) be uncorrelated with y v conditioned on v.
The independent work of [13] relates multicalibration to real-valued boosting ot minimize Eg loss. The implication that (42, C)) swap-agnostic learning implies multicalibration follows from Part(1) of Theorem 3.2 in their paper. They prove that violation of multicalibration leads to a better strategy for the adversary the (f2, -sswpp minimization game. They do not consider the notion of swap multicalibration, so their result is not tight characterization unlike ours.
Multi-group fairness and regret minimization. Notions of multi-group fairness were introduced in the work of [20, 24] and [22]. following [26]. The flagship notion of multicalibration has been extended to several other settings including multiclass predictions [7], real-valued labels [18, 21], online learning [18] and importance weights [17]. Alternate definitions and extensions of the standard notions of multicalibration have been proposed in [15, 16, 5, 8]. Multicalibration has also proved to have unexpected connections to many other domains, including computational indistinguishabiity
[6], domain adaptation [25], and boosting [15, 13].
Our notions of swap loss minimization and swap omniprediction are inspired by notions of swap regret minimization in online learning [10, 9, 2]. The classic results of [10, 9] relate calibration and swap regret, whereas [2] show a generic way to convert a low external regret algorithm to ones with low internal and swap regret. The study of online learning and regret minimization extensive, with deep connections to calibration and equilibria in game theory. we refer the readers to [4, 3] for comprehensive surveys. Recent work has established rich connections between online learning and regret minimization on one hand, and multigroup fairness notions on the other. Multicalibration has been considered in the online setting by [18], while [1, 12] relate multigroup fairness to questions in online learning.
Conclusion. Our work adds new and significant connection in the theory of agnostic learning and multi-group fairness. This theoretical work relies on a few basic assumptions, including access to a representative unbiased data source and a weak agnostic learner for the collection C. These assumptions, while standard in the supervised learning literature, should be interrogated before applying mutlicalibration as a notion of fairness in a practical setting.
Perhaps the most interesting aspect of our work is the connections it draws across different areas of learning theory. In particular, by borrowing the notion of swapping from online learning, we uncover
but feasible solution concepts for supervised learning. The equiv- alence we draw between swap agnostic learning for the squared error and multicalibration with swap omniprediction for all conver losses highlights the power of simple goals like squared error minimization and calibration.
Our work gives a complete characterization of the notions we study at the "upper end" of strength (i.e., swap variants). A fascinating outstanding question to address in future research is whether there is a similar characterization of standard omniprediction in terms of multi-group fairness notions.
A Acknowledgements. Omer Reingold is supported by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness, the Simons Foundation investigator award 689988 and Sloan Foundation grant 2020-1390 13941.
10

---

References
[1] Avrim Blum and Thodoris Lykouris. Advancing Subgroup Fairness via Sleeping Experts. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151, pages 15::-44 2020.
[2] Avrim Blum and Yishay Mansour. From external to internal regret. J. Mach, Learn. Res.,
8: 8:1307-1324, 2007.
[3] Avrim Blum and Yishay Mansour. Learning, regret minimization, and equilibria. In Algorith- mic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani editors. Cambridge University Press, 2007.
[4] Nicolò BasacBianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
[5] Zhun Deng, Cynthia Dwork, and Linjun Zhang. Happymap : A generalized multicalibration method. In 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, volume 251 of LIPIcs, pages 41:1-41:23. Schloss Dagstuhl Leibniz-Zentruu für Informatik, 2023.
[6] Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. Outcome indistinguishabiiity In ACM Symposium on Theory of Computing (STOC'21). 2021.
[7] Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. Beyond bermoulli: Generating random outcomes that cannot be distinguished from nature. In The 33rd International Conference on Algorithmic Learning Theory, 2022.
[8] Cynthia Dwork, Daniel Lee, Huijia Lin, and Pranay Tankala. New insights into multi culti-calibration. 2023.
[9] Dean Foster and Rakesh Vohra. Regret in the on-line decision problem. Games and Economic Behavior, 29:7-35, 1999.
[10] Dean P. Foster and Rakesh V. Vohra. Asymptotic calibration. Biometrika, 85(2):379-390, 1998.
[11] Alan Frieze and Ravi Kannan. The regularity lemma and approximation schemes for dense problems. In Proceedings of 37th conference on foundations of computer science, pages 12-20. IEEE, 1996.
[12] Stephen Gillen, Christopher Jung, Michael J. Kearns, and Aaron Roth. Online learning with an unknown fairness metric. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages
2018
[13] Ira Globus-Harrie Declan Harrison, Michael Kearns, Aaron Roth, and Jessica Sorrell. Multical- ibration as boosting for regression, 2023.
[14] Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder. Loss minimiza- tion through the lens of outcome indistinguishability. In Innovations in theoretical computer science (ITCS'23) 23), 2023.
[15] Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredictors. In Innovations in Theoretical Computer Science (/TCS22022), 2022.
[16) Parikshit Gopalan, Michael P. Kim, Mihir Singhal, and Shengjia Zhao. Low-degree multi- calibration. In Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 3193-3234. PMLR, 2022.
[17] Parikshit Gopalan, Omer Reingold, Vatsal Sharan, and Udi Wieder. Multicalibrated partitions for importance weights. In International Conference on Algorithmic Learning Theory, 29-1 April 2022, Paris, France, volume 167 of Proceedings of Machine Learning Research, pages 408 435. PMLR, 2022.
[18] Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, and Aaron Roth. Online mul- tivalid learning: Means, moments, and prediction intervals. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, volume 215 of LIPlcs, pages 82:1-82:24. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2022.
[19] David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and Computation, 100 (00(1):78-150) 1992.

---

[20] Ursula Hébert-Johnson Michael P. Kim. Omer Reingold, and Guy N. Rothblum. Multicali- masses, Proceedings of the 35th
bration:
Calibration for the ccompuaaionnally-denniina International Conference on Machine Learning, ICMI., 2018.
[21] Christopher Jung, Changhwa Lee, Mallesh M. Pai, Aaron Roth, and Rakesh Vohra. Moment multicalibration for uncertainty estimation. In Conference Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 2634-2678. PMLR, 2021.
[22] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerry- mandering: Auditing and learning for subgroup fairness. arXiv preprint 1rXiv:1111.051 144, 2017.
[23] Michael J Kearns and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994.
[24] Michael Kim, Amirata Ghorbani, and James Zou. Multiaccuracy; Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAT/ACM Conference on Al, Ethics, and Society, pages 247-254, 2019.
[25] Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold. Universal adaptability: Target-independen inference that competes with propensity scoring. Proceedings of the National Academy of Sciences, 119(4), 2022.
[26] Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-off's in the fair determination risk scores. In 8th Innovations in Theoretical Computer Science Conference, ITCS, 2017.
[27] Krzysztof Pietrzak. Cryptography from learning parity with noise. In SOFSEM, volume 12, pages 994114. Springer, 2012.
[28]
Endre Szemerédi. Regular partitions of graphs. Technical report, Stanford Univ Calif Dept of Computer Science, 1975.
[29] Luca Trevisan, Madhur Tulsiani, and Salil Vadhan. Regularity, boosting, and efficiently simulat- ing every high-entropy distribution. In 2009 24th Annual IEEE Conference Computational Complexity, pages 126-136. IEEE, 2009.
[30] Leslie G Valiant. theory of the learnable. Communications of the ACM, 27(11):1134 1142, 1984.
12

---

A Equivalence of swap loss OI and swap multicalibration over augmented class
We show that (c,pp loss Ol and (aC o -sss multicalibration are equivalent for nice loss functions.
Theorem A.I (Formal statement of thm:swap-eq-inf). Let S C(B) be a family of B-nice loss functions such that lg E L. Then (aL o C, 01) -swap multicalibration and (L, C, -swap loss Of are equivalent."
In preparation for this, we first finish the proof of Lemma 4.4.
Proof of Lemma 4 The proof Part (1) follows the proof of [14, Proposition 4.5], showing that loss Ol implies omniprediction. By the definition of ke, for every X such that p(x))
E y S--Ber(o)
E
1 ke. (v)) lo cx
y BerBe( (U kie (v)) - (o,
0
Hence this also holds in expectation under Dio. which only considers points where j(x)
E (x, v) S 0.
Since ğ satisfies swap loss OI, we deduce that
E
[u (x, u, a(v)
Di.
Taking expectations over D3 and using the definition of Uky we get
E E [y" he, (v)) (x))) E (x,,(x,v,y"))
v~Dp Dlv
v~D,
< E [a(v)] Sa v>Ds
Rearranging the outer inequality gives
E E V-D; Dlv
ke,
E [ (x))] ta.
v-D; Div
Part (2) is implied by taking tu for every v.
We the following simple claim from [14].
Claim A.2 (Lemma 4.8, [14]). For random variables y1.y2 {0, 1} and e I, E(f(y1, t) - Ely2, t)] E((y1 - -2))
(17)
We record two corollaries of this claim. These respectively be strengthenings of the two parts of Theorem [14, Theorem 4.9], which respectively characterized hypothesis Of in terms of multiaccuracy and decision Ol in terms of calibration. We generalize these the swap setting.
Corollary A.3. For every choice of {Lu, Cw hvelm(p) have
E ( Di.
(y
((y" - ÿ) o cov(x)) Dlv
(18)
D.
DnDg
Hence if is (#L o C, -swp multicalibrated. then
E (e lu (v cv (x))]
E V
aa
Herre equivalence means that there are reductions in either direction that lose multiplicative factor of (B in the error.
13

---

Proof. Equation (18) is derived by applying Equation (17) to the LHS. Assuming that i (OLoC,a). swap multicalibrated, we have
E D>Dp
E Plv
[ly
y)dev co(
S E vnDD
max E [(y* - s)c((2) Sa. d'EaLoC
Corollary A.4. Let flo (vEm(L)) be a collection of loss B-nice loss functions. Let k(()) = ke, (v). If P is a-calibrated then
E
E
[evly' k(v)) - fv (F,A(v)))
< Ba.
(19)
v-Da
Dlu
Proof. We have
E
E
(V (y k(v)) -000)))(((,,,,))))
E
E [ly - v)ac.
v~DD
Dlv
v>D;
Dlv
E vnD2g
|06 [0lo
E ly
Div
B E
E
ly
v-
Dlv
Ba.
where we use the fact that k<v)= Le, and so (kC((K())) B.
Finally, we show the following key technical lemma which explains why the loss has special role.
Lemma A.S. If is ((f2), C, -swps O1, then it is a-calibrated.
Proof. Observe that l2(y, v) = (y - u)3 so (e,(v) = c. Hence, ue2,0l2r, v, l2 ke(v)) (2 0) =(wy u)² - =- + /²/22.
(20)
Recall that {0, 1] C C. The implication of swap loss OI when we take C. for all is that
E v~DD
E Dl.
[ue (x, v,y") u v. 87]
S a.
We can simplify the LHS using Equation (20) to derive
E Dl.
[-vv* + +22/2) - (-v V² v²/21]
v(y" - 5)]
Dr
Dlv
=
v
E ly y'1
Sa. (21)
v-Dp
Dv
Considering the case where c, for all v gives
U42.1 (ar, v.y) = l2(2, (e())) f2(2,11 1)
((y 0)² (1 2)2
v)y (v² 1)/2.
We derive the following implication of swap loss Ol by taking = 0 for all 2:
[ v,y") - " v.
= E
(1 v)
y y"1
Sa
(22)
D.. Adding the bounds from Equations (21) and (22) we get
vnDD;
v~D2
D
E Dr
E v - y"1
E
E Dlv
<a
Dlv
D.
14

---

We can now complete the proof of Theorem A.1.
Proof of Theorem A.I. We first show the forward implication, that swap multicalibration implies swap loss OI.
Since & L and 1 E C, have Ol2 1 1 E o C. This implies that p is a-mulitcalibrated since
E [
vill <
E Vo
max REC
[c(x)(y
wil S a.
vr-D,
Consider any collection of losses (l))ell)()) Applying Corollary A.4, we have
E V-Dp
E Plu
[Bv(y" k(v)) - 6x (S,
S Ba.
On the other hand, by Corollary A.3, we have for every choice of (ln, colvelm(p)
E
E Dlv
[yvly" (x)x (x(5. aa
v-Dp
Hence for any choice of {uu (TTm(() we can bound
E
E
[u (x,, u. (x, vx,
v~D;
Dlv
[y k(v)) Cx A(v]]
(ely"",,(x)) cx Dlv
v>Dp
Dlv
< (B + 1)a
which shows that ğ satisfies swap loss OI with 02 (D 1)a1
Next we show the reverse implication: P satisfies (C, C, (r2))-ssaaea swap loss OI, then it satisfies (OC C, 01 >-swap multicalibration. The first step is to observe that by lemma A.5, since bg E L. the predictor p is a2 calibrated. Since any l E L B-nice, we have
[e k(v)) (s (V))(
E (y- S)((v]] D.
E V~DD
E Dlv
E v~Da
Baz-
For any (les Cotoelm(() since
-,(2, loly, +c(,,c)))))
write
E
E 1v Dlv
((x)) (y((",c(())) (.(6
<
E
E (x ux (x. +
E R Dlv
v-D
Div
< (B + 1)a2-
But by Equation (18), the LHS can be written as
E Do
E D..
Lv (y", c(x)) Lv(7 c(x))]
= E v~D,
E Dl.
1el (xx(((x('''
p
This shows that is (ŌC o C, (B + 1)az) multicalibrated.
B Relating notions of omniprediction
In this work, we have discussed the four different notions of omniprediction defined date.
00) Omniprediction, originally defined by [15].
15

---

Swap Loss Oi
Swap Omniprediction
Loss
Omniprediction
Figure I: Relation between notions of omniprediction
01) Loss OI, from [14].
10) Swap omniprediction.
11) Swap Loss OI.
In order to compare them, we can ask which these notions implies the other for any fixed choice of loss class and hypothesis class C.
Loss Ol implies omniprediction by [14, Proposition 4.5].
Swap omniprediction implies omniprediction by Claim 2.4.
Swap loss OI implies both loss OI and swap multicalibration by Lemma 4.4.
These relationships are summarized in Figure 1.
Further, this picture captures all the implications that hold for all (C,C). Next, we show that for any implication not drawn in the diagram, there exists some (natural) choice of (C,C). where the implication does not hold. In particular, we prove that neither loss OI nor swap omniprediction implies the other for all (C, C). This separates these notions from swap loss OI, since swap loss OI implies both these notions. By similar reasoning, it separates omniprediction from both these loss Ol and swap omniprediciton, since omniprediction is implied by either of them.
Swap omniprediction does not imply loss OL We prove this non-implication using coun- terexample used in [14]. In particular, they show that omniprediction does not imply loss Of [14, Theorem 4.6), and the same example in fact shows that swap omniprediction does not imply loss OI. In their example, we have D on [=1]3 x 1] where the marginal on [=1}3 3 uniform, and p=(x) = (1+2) /,, whereas p(x:) = 1/2 for all z. We take C = [1, I22 Ta). Since ý 1/2 is constant, it is easy to check that p - p= = - -21 2 uncorrelated with C. Hence P satisties swap multicalibration (which is the same multicalibration or even multiaccuracy in this setting where Ç is constant). Hence by Theorem 3.3, f is an (Levx (1), Ling, Owap omnipredictor. [14, Theorem 4.6] prove that P is not loss OI for the l, loss. Hence have the following result.
Lemma B.1. The predictor p is (C, O)-spap multicalibrated and hence it is (fe.), Lin(C), 0)-s onnipredictor. But is not ((e,), Lin(C, 1), elosss OI for 4/9.
We remark that the construction extends to all Ep losses for even 2. Hence even for convex losses, the notions of swap omniprediction are loss-Ol seem incomparable.
For instance if loss Ol implied swap loss O1, it would also imply swap omniprediction, which our claim shows it does not.
16

---

(21,02)
(x
((x)
(-1,-1)
0
(+1,-1)
(11,+1
1
(+1,+1)
Table Separating loss-OI and swap-resilient omniprediction
Loss OI does not imply swap omniprediction. Next we construct an example showing that loss OI need not imply swap omniprediction. We consider the of all GLM losses defined below, which contain common losses including the squared loss and the logistic loss.
Definition B.2. Lei g R IR be a convex, differentiable function such that [o, 1] S Im(('). Define its matching loss to be lg = g(t) yl. Define LGLM = (6g) } be the set of all such loss functions.
[14] shows a general decomposition result that reduces achieving loss Ol to a calibration condition and multiaccuracy condition. Whereas arbitrary losses might require multiaccuracy for the more powerful class 0L C, for LGLM. 0LGLM o C C. This is formalized the following result.
Lemma B.3 (Theorem 5.3, [14]). If p is e--calibrated and (C, mam-miccicccuuratte then it is (AGLM, Lin(C, -lloss O1 for 8 = E1 + Wé2.
In light of the above result, it suffices to find a predictor that is calibrated and multiaccurate (and hence satisfies loss OI), but not multicalibrated, hence not swap multicalibrated. By Theorem 3.3 it is not an (((2), Ling, 5w-s omnipredictor for less than some constant.
Let us define the predictors p", {=1}² + [0, 1] as below. We use these to show a separation between loss OI and swap omniprediction.
Lemma B.4. Consider the distribution 'D on (+1]2 x (0.1) where the marginal on {+1)² is uniform and E[y[æ] (x). Let C {1,,
1. i E Lin(C, Moreover, it minimizes the squared error over all hypotheses from Lin(C).
2. i is perfectly calibrated and (C, mulliiicceee So it is (CGLM; Lin(C), 0l-soss OI.
3. p not (C, a) multicalliibbee for a < 1/88. is not (l2, Lin(C,, 8) -swap agnostic learner for 8 < 1/64.
Proof. We compute Fourier expansions for the two predictors:
(x())= = (4 + 3zg 21
(23)
8
p(x) = (4 + +322)
(24)
This shows that p E Lin(C), and moreover that is the optimal approximation to p" in Lin(C), as is the projection of p" onto (C). This shows that is an (lz, Lin(C), O)aagnostic learner.
It is easy to check that p is perfectly calibrated. is (C, multiaaccceeate,, since the projection of p" onto Lin(C), so P p" is orthogonal to Lin(C). Hence we can apply Lemma B.3 to conclude that is (CGLM, Lin(C), Ol-soss OI, where LGLM which contains the squared loss.
To show that ア is not swap-agnostic, we observe that conditioning on the value of p(x) = (4+33z2) equivalent conditioning on 22 E {+11). For each value of 22, the restriction of p" which is now
linear in æ belongs to Cin Indeed if we condition on p(x) = 1/8 so that 22 -1, we have
1
3
+
('(x)
2
8
Conditioned on p(z) 7/8 so that Ø2 1, we have
1
3
p (x)
+
2
8
8
17

---

Hence we have
min El(y h(x)) = - E - p" px))) = Varlyl,
A (C)
whereas the variance decomposition of squared loss gives
El(y x(x)) El(y p" (x))²) (l(p"(x) (x) ((x))
Var[y] + 64
[[(x12))
+aaly] + 64
Hence is not (62, Lin(C), agnostic learner for å 1/64.
To see that not multicalibrated for small a, observe that conditioned on 22 E {+1}, the correlation between T1 and p p" is 1/8.
Note that item (1) above separates swap omniprediction from omniprediction and agnostic learning. This separation can also be derived from [15, Theorem 7.5] which separated (standard) omniprediction from agnostic learning, since swap omniprediction implies standard omniprediction.
Comparing notions for GLM losses. When we restrict our attention to LGLM. in fact, the notions of swap loss Ol and swap omniprediction are equivalent. The key observation here that dL = C, as shown in [14]. Paired with Theorem 3.3 and Theorem A.l (proved next), we obtain the following collapse.
Claim B.5. The notions of (CeLM; C, a1)-spp loss Ol and (CGLM, C, swwpp onniprediction equivalent.
Proof. To see this, note that by Theorem A. (CGLM, C, a1) -swap loss Ol is equivalent (aCGLM C, a' >-sap multicalibration. We know from Theorem 3.3 that this is also equivalent to (0LGLM C, (:22-=saaapp omniprediction. So, by the fact that 0LaM C C, we have the claimed equivalence.
Finally, know that loss Ol implies omniprediction for LGLM, since this holds true for all L. We do not know if these notions are equivalent for LGLM, since the construction in Lemma B. used the & loss which does not belong LGLM-
C Omitted Proofs
We define the multicalibration error of ザ wrt C under D as
MCED(f.C) = max E E (c(x v)] aEC vnD,
Dl
We define the swap multicalibration error of p wrt under as
sMCE = E
max CEC
E [c(x) -
v~Dp
Dlv
C.1 Properties of Swap Notions of Supervised Learning Proof of Claim 2.4. We let l, for all Im(ū), so that k(v) ke(v). We pick the hypothesis
h = arg min E [e(y, h(x)))
hER D).
The swap omniprediction guarantee reduces to E E [E(y kx(v)) El kx(x)) vED₁ Div
E min E [f(y, h(x)) + 5. v~DD hEw Dl.
This implies that f ke o p is swap agnostic learner for every E L since we allow the choice of to depend p(x) which is more informative than f(x) kp(x))).
18

---

Proof of Claim 2.7. We have
(D.ED(
E
max
E
(y² vi]]
vn
oEC
Dlv
[c(x)(y von
max
E V-
E Plv
MCE+(D,C)
aEC
since the expectation of the max is higher than the max of expectations. Bounding the RHS by a equivalent to (C, a mullticcaliibation.
Proof of Clain 2.9. The foo bound is immediate from the definition of p. We bound the swap multicalibration error of t.. We have p(x) jō iff f(x) E By, that 1p(x jöl S 5 holds conditioned on this event. So
sMCED(P,
Σ je(m)
Pr(p(x)= j6] max cEC
Blc(x) jo)lp(x) 58]
D
Σ
Pr(p(x)=
B,] max SEC
El Elc(x)(y jo)1o(x)) E BJ]
je(m]
Σ Pr(p(x) Bj] (6+
max oEC
Bic(x) -0x))((x))xxx E By]
jE(m]
< 8 +
Pr(p(x) E Bj] max
Ble(x) - f(x))1((x) E B,]
(25)
aEC D
JE(m
Let us fix a bucket B, and a particular c E C. For 2 a to be specified later we have
E[c(x) p(x)))((x) E B,]l < (r(c(x) - p(x)) 2 p(x E B,] + Prrj(())(y f(x)) S Blp(x) E B,]
Pr[ğ(x) E Bad (c, f) n By]
+
Pr(p(x) E B,]
Pr[p(x) Bads (c, f)l
+
Pr(p(x) E Bj] a/B +
Pr(p(x)= E By]
Since this bound holds for every c, it holds for the max over c C conditioned on p(x)
Bj. Hence
a/3
Σ
Pr(p(x) E By] max
((c(x)( - ((x))lF(x) E B,]] < Σ
Pr(ū(x) E By] Pr(s(xx B,] +
CEC D
JE(m]
jE(m]
385 + 3,
where we use m = 1/6. Plugging this back into Equation (25) gives
SMCED = E
max E [c(x) v\] 5
[c(x))y-vv)]
3 5.
w--PD
oEC Dlv
38
Taking 3 va/ō gives the desired claim.
C.2 Omitted Proofs from Main Result
Proof of Lemma 3.2. We will show that for p.p [0, 1] and lo E Ie, we have
E(p, to) - E(p' to) I lp P'
By the definition of E(p. 1), we have
E(p, 1o) lpp' (o) = (p-p')
=
-
Taking absolute values and using the Boundedness property gives the desired claim.
19

---

Proof of Claim 3.4. Suppose that h E Lin(c, W) of the form h(x) = Ecsc c(x). From
Claim 2.7, we know that the multicalibration violation for E C is bounded by a(v) for every E lm).
BlM(x)(y - v) fx(x)= w||
E
Σ .EEC
we c(x)(x - v) f(x) v
Σ
max OEC
(y - u) p(() = r]1
CEC
W a(v)
The inequalities follow by Holder's inequality and the assumed bound on the weight of W for Lin(C, W).
Proof of Claim 3.5. Recall that Covly, z] = Elyz] - B[y] E[z]. For any / E Lin(C, W) we have pxx)
[Covly, ((x) u|l ElA [x) ((x)) = u|]
- v)(p(() = r]l E[( y))p(x) r]] S (W + 1)a(v)
where we use the fact that / E Lin(C, W) and E C. Since y E {0, 1). this implies the claimed bounds by standard properties of covariance (see [15, Corollary 5.1]).
Proof of Lemma 3.6. For any y E {0, 1),
(()y, (F(), = (v, (w,y)] = E (x) (p(x), (v, DI.
h
D
2 (ly, Eih(xx (f(x), = (v.
(26)
E(V, ((h y))
2 E(y, IL (1(h U. 8)))
(27)
where Equation (26) uses Jensen's inequality, and Equation (27) uses the optimality of projection for nice loss functions. Further, by the 1-Lipschitzness of l on It, and of II on R
E(y, [el v.)) E(y. [e( e))) [[e[[(
v)) Ie(((h 2))l s 1u(h : U. 3) u(h: : w)
(28)
Hence we have
E [0(y, Molu(h : u))l - E [e(y, l(x))] D..
D
Σ Priy ylp(x) v) (e(y, (e( : v))) El((g, (v.)))) vE(0.1}
Σ
Pr(y = ylp(x) = 2) (C(y. [e((( w))) - (c
(By Equation (27))
(0.1)
S
Σ
Pr(y = vlp(x) v) (u(h v, v) m(h v))
(by Equation (28))
(0(0.1)
< 2(W + +1)(()).
(By Equation (9)
D Details on Algorithm
Here, we give a high-level overview of the MCBoost algorithm of [20] and weak agnostic learning. Definition D.1 (Weak agnostic learning). Suppose D is a data distribution supported on X' x [-1, 1]. For kypothesis class C, a weak agnostic learner WAL solves the following promise problem: for some accuracy parameter > 0, if there exists some e E C such that
E (x.x)>
[c(x) z] 2
20

---

then WAL returns some h X - R. such that
[h(x) 2] 2 poly(a). (x.x))
For the sake of this presentation, we are informal about the polynomial factor in the guarantee of the weak agnostic learner. The smaller the exponent, the stronger the learning guarantee (i.c., we want W return hypothesis with correlation with z as close O{a) as possible). Standard arguments based on VC-dimension demonstrate that weak agnostic learning is statistically efficient.
D.1 MCBoost
The work introducing multicalibration [20] gives boosting-style algorithm for learning multicali- brated predictors that has come to be known as MCBoost. The algorithm is an iterative procedure: starting with trivial predictor, the MCBoost searches for supported value group" Cy E C that violate the multicalibration condition. Note that some care has to be taken to ensure that the predictor p stays supported on finitely many values, and that each of these values maintains significant measure in the data distribution Dp. In this pseudocode, we ignore these issues; [20] handles them in full detail.
Im(p) and "sub-
Importantly, the search over C for condition (29) can reduced to weak agnostic learning. Intuitively, pass WAL samples drawn from the data distribution, but labeled according y when p(x)= u.
Lemma 3.8. The iteration complexity of MCBoost is directly (inverse quadratically) related the size of the multicalibration violations we discover in (29). A standard potential argument can be found in [20].
By the termination condition, we can see that P must actually be (C, swap multicalibrated. In particular, when the algorithm terminates, then for all Im(p), we have that
max E (x). (y - e) ((x) v) s poly(a) S a.
Therefore, averaging over Dj., we obtain the guarantee.
Corollary 3.9. By Lemma 3.8, we know that ý returned by MCBoost is (C, aswp multicalibrated.
By Theorem 3.3, P is equivalently a (Levx, C, C, a' ass-s omnipredictor for some polynomially-related a' In other words, by Claim 2.4, if we post-process according to kę for any nice convex loss function E, we obtain an (, sswap agnostic learner. Taking a poly(e) sufficiently small, we obtain the swap agnostic learning guarantee.
Algorithm 2 MCBoost
Parameters: hypothesis class C and a >
Given: Dataset S sampled from D
Initialize: ((x)) +- 1/2.
Repeat:
3u E Im(p) and o E such that
Exc,(x) (y - v) pxx) v] > poly(a)
(29)
update p(x) + p(x) + (x) 1pp(x) v)
Return: p
21


Reviews:
[{"review_id": "pCB5B5PovW", "reviewer": "Reviewer_7mxb", "summary": "This paper provides a new learning framework referred to as Swap Agnostic Learning, a variant of agnostic learning aiming to a stronger goal.\nIt is shown that this framework is equivalent ot swap variants of the notions of Omniprediction and Multicalibration.\nAn algorithm for Swap Agnostic Learning is provided, which is shown to work well for any convex losses.", "questions": "I would appreciate an answer to the concerns in \"Weaknesses\".", "limitations": "I have no concerns about the limitations and potential negative societal impact.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- A new problem setup is introduced along with its interpretation, which would be of interest for readers in the NearIPS community.\n- The relationship with various existing studies is well explained.", "weaknesses": "There are unclear points in the algorithm procedure and analysis.\nFor example, the paper states that MCBoost from [20] is used, but it is not clear what the corresponding algorithm in the paper [20] is.\nAlgorithm 2 given in Appendix B.1 looks very different from algorithms in [20].\nIn Algorithm 2, there is no explanation of how to set the parameter $\\eta$.\nI cannot find a proof that the iterations in Algorithm 2 terminate.\n\nIn the algorithm section, the fact that the MCBoost algorithm, originally designed to guarantee multicalibration, actually also guarantees swap multicalibration, would be a very important and nontrivial point, in my understanding.\nI believe it would be better if a more detailed explanation of this fact and the intuition were added to the text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We apologize for some of the confusions.  Multicalibration is a fairly young notion, but has had significant developments and contributions to the literature in the past few years.  As such, the presentation and nomenclature has become a bit ambiguous.  Let us clarify.\n\nMCBoost—i.e., Mutlicalibration Boosting—is a name that has come to refer to Algorithm 3.2 of [20] over the years.  While [20] presents the algorithm in terms of sets (rather than hypotheses) and only incorporates the reduction to weak agnostic learning in Section 4, the literature has settled on referring to this general learning paradigm as MCBoost, and attributing it to [20].\n\nMCBoost operates iterative, in a boosting-style fashion.  Importantly, in each iteration, the input domain is partitioned by the current predictions.  This split of the domain effectively conditions on the level sets of the current predictor, then searches over $c \\in \\mathcal{C}$.  In other words, even though the algorithm was designed to satisfy standard multicalibration, the order of quantifiers matches that of swap multicalibration.  This is why MCBoost actually guarantees the stronger variant of swap multicalibration.\n\nThanks for bringing up these points!  We are happy to clarify these points in our presentation of MCBoost.  We hope that incorporating these changes would improve your impression of the manuscript.\n"}, {"review_id": "cyHzCXyjVB", "reviewer": "Reviewer_7A6v", "summary": "This paper studies algorithmic fairness from a learning theoretic lens, specifically extensions of the recent notion omniprediction by Gopalan et al and its connections to to agnostic learning - multicalibration is sufficient to obtain omniprediction and guarantee agnostic learning for all convex loss functions simultaneously. The main contributions are in introducing a new learning paradigm called Swap Agnostic Learning (SAL), and subsequently new notions of \"swap\" omniprediction and multicalibration in a similar vein, and proving that they are all equivalent. The authors show that the standard multicalibration algorithm of Herbert-Johnson et al. in fact guarantees swap multicalibration algorithm, and consequently can also be used to obtain a SAL guarantee.\n\nThe contributions all hinge on the introduction of the new learning task - swap agnostic learning. SAL requires, informally, that a predictor plays a hypothesis h such that on any level set of their predictor - i.e. set of all x's such that h(x) = v for some fixed v - they have no incentive to change their predictions to any other hypothesis from the hypothesis class on that set. This contrasts the standard agnostic learning which says that the predictor is competitive with the same, single error-minimizing hypothesis in expectation over all the level sets. \n\nThe swap notion of omniprediction is similar. A standard omnipredictor for a class of losses L and hypothesis C is a predictor that can be post-processed (in a way that depends on the chosen loss from L) such that it is competitive with the best hypothesis for each loss in L simultaneously. The swap variant requires that the omnipredictor be competitive (up to a level-set dependent post-processing) the best hypothesis on each level set for any assignment of loss functions to level sets. \n\nSection 3 proceeds with the proof of equivalence between these three notions and a brief explanation of how the standard McBoost multiwcalibration algorithm in fact satisfies swap multicalibration, and consequently can be used to achieve the other two swap notions.  ", "questions": "I understand the technical conditions of swap AL, MC, omniprediction and how they are different from the standard notions, but I am slightly confused by the motivation. The original notions seem natural in some sense, is there a reason why these additional technical conditions for the swap variants are intuitive or useful - e.g. giving adversary the additional control down to the granularity of level sets? If I understand correctly, the analogous versions of connections established in this work for all of the \"non-swap\" notions of these learning tasks are already shown, so again I am slightly confused what the advantage of these swap variants are. ", "limitations": "-", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper makes a significant contribution in the area of omniprediction and multicalibration, which are currently popular topics in the study of algorithmic fairness. The newly introduced notion of SAL is interesting and provides a complete picture of the connections between the swap variants of mutlicalibration, omniprediction, and agnostic learning. \n\nThough the content is technically and notationally dense, the presentation is clear. ", "weaknesses": "A minor suggestion is that if possible, adding a bit of exposition to the swap omniprediction definition to guide the reader through all the moving parts would be helpful. It feels a little trickier to parse than the swap multi calibration and swap agnostic learning definitions. Also, per the below question, maybe adding some exposition describing why these swap variants are natural / intuitive could be helpful. \n\nSimiarly, in Section 3.1, if possible, proof sketches/intuition would be useful as well. There are maybe one or two parts where it is done but the section feels largely like a proof with limited expositional guidance. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "To be very clear, the equivalences we show for the swap variants are NOT known to be true in the standard models:  the implications are only known to go in one direction.  In fact, our work suggests that they do not generally hold.  This is a key contribution of our work.  On a technical note, (Gopalan et al., ITCS 2023) demonstrate some equivalences in the standard learning model, but they cannot give guarantees for convex omniprediction, which we study here."}, {"review_id": "mYMe49ZXE9", "reviewer": "Reviewer_XpDf", "summary": "The paper introduces the notion of swap agnostic learning, and proves the feasibility of swap agnostic learning for any convex loss using only weak agnostic learners. To prove this result, the authors establish the equivalence between swap agnostic learning and the swap variants of multi-calibration and omniprediction, and show that the existing multicalibration algorithm of [20] already guarantees the stronger notion of swap multicalibration. They also show that the notion of swap loss outcome indistringuishability captures all existing notions of omniprediction and multicalibration.", "questions": "- In line 5 of the abstract, what does $p$ refer to? Is this supposed to be $h$?\n- In Definition 2.5, multi-calibration is defined in terms of the expectation of the absolute difference over $v\\sim\\cD_{\\tilde{p}}$, which contrasts with the definition involving $\\max_v$ as in Definition 2.6 from reference [20]. How critical is this choice of definition for your results? If multi-calibration were defined in terms of the maximum rather than the expectation, would this make swap multi-calibration and multi-calibration equivalent? Could this be why existing algorithms for achieving multi-calibration, such as those in references [20,15], are able to guarantee swap multi-calibration without modification?", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper explores the important connection between the group-fairness notion of multi-calibration and the loss minimization notions of agnostic learning and omniprediction, and establishes many interesting equivalences under swap variants. This equivalence result provides new insights into what multi-calibration can offer and deeps the understanding of the relevant notions.\n\n- The paper is well-written and clearly explains the problem and its contributions.", "weaknesses": "The paper would benefit from additional discussions on the differences between the 'swap' variations and their standard counterparts. For instance, clarifying how 'swap multicalibration' diverges from the conventional concept introduced in [20] would be beneficial. Further, it would be insightful if the paper could elaborate on why equivalences under the 'swap' notions are easier to establish. What are the challenges involved in extending these to the standard definitions? This additional discussion could give readers a more thorough understanding of the subject.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Swap and standard multicalibration are equivalent in the max version you describe.  Unfortunately, the max version is hard to achieve from sample access alone. This is why all known algorithms work with (some variant of) the expectation version, which allows us to ignore unlikely predictions.  (Even the original formulation of (Hebert-Johnson, et al. ICML 2018) uses this on-average version under the hood.) None of the algorithms mentioned can guarantee the max version, since they all work from samples alone, they essentially guarantee the expectation version.  Still, the algorithms work by searching for a successful auditing function $c \\in \\mathcal{C}$, conditioned on each prediction value (i.e., the level sets of the current predictor).  This conditioning, followed by searching for $c \\in \\mathcal{C}$, flips the quantifiers from the standard multicalibration definition, and gives rise to an algorithm that naturally guarantees swap multicalibration."}, {"review_id": "vD9MNvXF96", "reviewer": "Reviewer_HdZq", "summary": "The authors study swap agnostic learning, or a game between a predictor and an adversary where the predictor has to come up with a family of hypotheses to compete with a strong adversary's loss. They prove a surprising feasibility result for swap agnostic learning for any convex loss by proving that swap agnostic learning is equivalent to swap variants of omniprediction and multicalibration. Furthermore, they connect these ideas even further by relating them under the umbrella of outcome indistinguishability.", "questions": "None", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ The equivalence result seems like it is a novel and useful finding -- however, I was not familiar with the notions of omniprediction and multicalibration.\n+ The technical contributions of this paper are insightful and nontrivial.\n+ This paper connects results from different areas of ML, which is always nice to see.", "weaknesses": "- I found the paper to be rather inaccessible in its lack of intuition about results and its overeagerness to use jargon. I acknowledge that this is not an area I am an expert in, but I found it rather hard to follow.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate you bringing up these points on presentation.  If there is any jargon that you feel is particularly inaccessible to the general machine learning audience, we are happy to incorporate definitions and clarifications.  We will be cognizant of aiming for accessibility in our revisions for the camera-ready version, which no doubt, will improve the paper.  Thanks!"}, {"review_id": "NmdVDg0QI1", "reviewer": "Reviewer_if87", "summary": "The authors propose a stronger variant of agnostic learning called *swap* agnostic learning, and show that this notion of learning is equivalent to “swap” variants of multicalibration and omniprediction. Multicalibration means that the predictor is simultaneously calibrated on a given collection of subpopulations $\\mathcal{C}$. Omniprediction means that a *single* predictor’s output values can be post-processed so that its performance is competitive with the best from a given hypothesis class $\\mathcal{C}$ w.r.t. multiple loss functions. Here, the post-processing must depend only on the given loss function and *not* the covariates.\n\nMulticalibration is related to algorithmic fairness since it means that “chance” predictions of a given (potentially malicious) predictor “mean the same thing” across many subpopulations. Omniprediction is useful for training machine learning (ML) models since it means that one can train a *single* predictor that performs well w.r.t. multiple loss functions. Thus, an omnipredictor obviates the need to train separate models for each loss function.\n\nPrevious work has shown that multicalibration is sufficient for omniprediction, thereby showing that satisfying fairness constraints may lead to practical benefits in machine learning. The question of whether multicalibration is *necessary* for omniprediction is still open. This work takes a step towards this question by showing that their *swap* analogues are equivalent to each other.", "questions": "- Are there provable separations between swap and vanilla versions of each notion (multicalibration, omniprediction)? What separations are known and which ones are unknown?\n- Multicalibration can be interpreted as “calibration w.r.t. any subpopulation in $\\mathcal{C}$”.  Does swap multicalibration have such simple interpretation? How would one motivate swap multicalibration as a stand alone concept? Ditto for swap omniprediction.\n- Calibration has a long history dating back to early research on weather forecasts and their assessments. The natural setting of this early literature is sequential prediction (i.e., inputs are *adversarial* sequences consisting only of labels $y$ rather than i.i.d. samples $(x,y)$ with covariates $x$ drawn from an unknown, but fixed, distribution). Even in the sequential setting, multicalibration has a natural interpretation: calibration w.r.t. multiple subsequence selection rules (see e.g., [Daw85]). How should one think of infinitary analogues of swap mulitcalibration?\n\n**Minor editorial comments**\n- In the abstract, it’s not clear what $p$ refers to when the authors say “the predictor wins if $p$ competes with the adaptive adversary’s loss”. Did the authors mean $h$?\n- The projection operator $\\Pi_\\ell$ in Definition 3.1 is not defined anywhere in the paper.\n- In Theorem 4.2, the word “incomparable” is too vague and uninformative, even for an informal theorem statement. I would suggest the authors provide a more concrete statement.\n\n**References**\n- [Daw85]: Dawid, A. P. Calibration-based empirical probability. *Annals of Statistics*. 1985", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- **Contribution.** The paper makes a significant and timely contribution to the fast-growing literature on multicalibration by showing that seemingly distinct notions of success in learning and algorithmic fairness are in fact equivalent. Key to their result is their definition of swap agnostic learning, a stronger learning requirement than (vanilla) agnostic learning, and the swap variants of multicalibration and omniprediction. The swap analogues of each notion enable tight connections among themselves.\n- **Exposition.** The paper is overall well-written. Ideas are presented clearly and concisely. The authors also do a good job situating their results in relation to previous work.", "weaknesses": "**Motivation behind swap multicalibration and swap omniprediction.** As a stand alone concept, i.e., for purposes other than establishing equivalence between the notions, the motivation behind the definition of swap multicalibration and swap omniprediction is unclear to me. I expand on this point in the Questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "To reiterate from the main response, multicalibration and swap multicalibration are essentially the same, so there is little additional motivation.  For swap omniprediction (and similarly agnostic learning), the guarantee seems to be much stronger.  In some sense, one can view this as pushing the limits of supervised learning:  how strong can we make the adversary that the learner is up against, and still be able to achieve the solution concept?  We show that despite the very strong framing, swap omniprediction can be achieved through weak agnostic learning.\n\nRe:  How should one think of infinitary analogues of swap mulitcalibration?\nFantastic research question!  Very recent work (posted to the arXiv) looks at exactly this question, particularly in the online setting."}, {"review_id": "rlayUluppd", "reviewer": "Reviewer_Xn6q", "summary": "This paper introduces and studies 3 learning theoretic problems, namely \"swap\" versions of agnostic learning, omniprediction, and multicalibration. These swap versions are inspired by the notion of \"swap regret\" in online learning. They show that in some settings, all three of these learning-theoretic problems are equivalent (up to polynomial factors). Then they also introduce another notion called Swap Loss Outcome Indistinguishability and study relationships between it and the others.", "questions": "1. Could the authors address why one should study these learning problems (swap versions)?\n2. While the paper was motivated by studying omniprediction and multicalibration, the results herein focus on the swap version. What are the high level implications for the relationships between omniprediction and multicalibration?\n3. Can one do an online2batch reduction for the swap versions of online learning and agnostic learning?\n4. How do the results depend on the size of the support of $\\tilde{p}$? Do they become less interesting if $\\tilde{p}$ is assumed to be a continuous-valued predictor (as is done in many practical scenarios)?\n5. Could the authors state some examples of \"nice\" loss functions? Are all the loss functions commonly used in learning theory, e.g, square loss, hinge loss, exp loss, log loss, etc all \"nice\"?\n\nMinor typos/clarifications:\n- line 63: \"defintions\"\n- I may have missed this, but what is meant by the notation $\\ell_2$ and $\\ell_4$? In some cases, it seems like it means square loss, but in others it is used to denote a loss function that is picked for a value $v$.\n- What is meant by \"sparse\"? Typically it means a bound on $\\ell_0$ (or the number of nonzero weights), but it seems like you are using it to mean $\\ell_1$ bound.\n- line 297: \"ot\"\n- line 188: do you mean $\\lVert \\mathcal{C} \\rVert_\\infty \\le 1$?", "limitations": "Yes, n/a.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is clearly written, and all the definitions of the different learning problems make sense. The proofs are easy to follow/digest.\n- The results seem novel, and provide a relatively complete picture of the relationships between the different learning problems that are introduced.", "weaknesses": "- The main question which is not really addressed is why one should care about these learning problems? Agnostic learning and multicalibration are important problems because they have tremendous practical significance. Maybe the authors can touch upon this in the rebuttal. At first glance (since I do not have much background in the field of multicalibration), it seems like the authors introduced three \"brand new\" learning problems and proved relationships between them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the questions.  We hope the main response above helps to answer the motivation for our study.  These swap variants are natural in a few ways.  Perhaps the way to motivate these notions as natural is through multicalibration.  Multicalibration was introduced as a notion of algorithmic fairness in prediction tasks.  It makes no reference to loss functions or to swapping.  And yet, we show that this notion is tightly characterized by the notion of Swap Agnostic Learning.  Even though initially, it seems like a simple syntactic extension of the Agnostic Learning paradigm, it is clear from our initial study that swap agnostic learning may have a deep and rich theory to uncover.\n\nHopefully questions 1. and 2. are addressed in the main response.\n\n3.  Obtaining sample-efficiency was a key consideration in the original work of [20], but they do not use an online to batch conversion.  It is a very interesting question for future investigation.  The online version of the problem has only very recently been studied (in a follow-up to our work).\n\n4.  Restricting ourselves to a finite support size is a technical convenience.  As we show, by rounding, one can achieve approximate versions of all these notions.\n\n5.  All of the loss functions you mention are nice! ( Page 10 of the original Omnipredictors paper (GKRSW’22) shows this explicitly.)  In fact, it’s a bit of an exercise in creativity to think up loss functions that are not nice.  Thank you for flagging this.  We will add a sentence about this fact, which will no doubt improve the clarity of the presentation.\n"}]

Author rebuttal:
We thank all of the reviewers for their thoughtful, and overall, positive feedback on the submission on Swap Agnostic Learning, Multicalibration, and Omniprediction.  We hope to clarify our views on the distinction between the Swap and Standard learning tasks—a point that came up across many reviews—and the motivation for studying the swap variants.

Our motivation for introducing Swap Agnostic Learning comes from trying to understand the relationship between (standard) multicalibration and omniprediction.  Prior work shows that multicalibration implies (convex) omnipredction, but leaves open the question of whether omniprediction implies multicalibration.  The present work sheds new light on this question, effectively answering it in the negative:  standard omniprediction does NOT seem to imply multicalibration.  The answer to this question comes by introducing the idea of Swap Learning, in the agnostic learning / omniprediction setting, as well as in multicalibration.

Importantly, for multicalibration, Swap multicalibration and Standard multicalibration are essentially the same notion!  Claim 2.9, as well as our analysis of prior algorithms for multicalibration, shows that standard multicalibration is already strong enough to capture the swap variant.  We will emphasize this point in the future presentation.  The distinction (definitionally and algorithmically) between swap and standard multicalibration is minimal:  our results suggest that one should really think of them as a single notion of multicalibration.

For agnostic learning and omniprediction, however, Swap Learning is much stronger than Standard Learning.  We prove separations between swap and standard omniprediction, but due to space requirements, the formal statements and proofs were deferred to Appendix C.  The separations are summarized in Appendix Figure 1.  We are happy to elaborate on these separations in the main body for the camera-ready version.

Our main result shows that (Swap) Multicalibration, Swap Agnostic Learning for $\ell_2$, and Swap Convex Omniprediction are all equivalent.  By this equivalence alone, Swap Agnostic Learning is a well-motivated learning model—it is an alternative view on a popular notion of algorithmic fairness in prediction.  Further, by the separation of Swap Convex Omniprediction and Standard Convex Omniprediction (proved in the appendix), we effectively separate Multicalibration from Omniprediction:  multicalibration suffices for omniprediction, but the converse should not generally be true.

Thus, in the standard setting, the state of the art is that multicalibration suffices for (convex) omniprediction.  We leave open the fantastic question of what (if any) notion of multi-group fairness characterizes (i.e., is equivalent to) standard omniprediction.  (Gopalan et al., ITCS 2023) make some progress on this question for non-convex losses, which may provide a roadmap to this question for convex losses.

The reviewers' comments and questions are very helpful, in forcing us to articulate these points more clearly!  In the camera-ready version, we will include prose (as above) to better situate our study of the swap variants of learning.


Meta-review: The paper introduces and explores the concept of “swap” versions of agnostic learning, omniprediction, and multicalibration, establishing their equivalence under certain conditions. While reviewers initially sought clarification on the motivation and practical relevance of these variants, the authors effectively addressed these concerns by emphasizing their significance in bridging the gap between learning theory and fairness considerations. Overall, the paper is technically sound and makes valuable contributions, and with further refinements and clarifications in the final version, it has the potential to stimulate further research in this area.
Decision: Accept (poster)