A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning
Authors: Nika Haghtalab
Michael Jordan
Eric Zhao
Venue: NeurIPS 2023 poster (2023)
Keywords: multicalibration
multi-objective learning
learning theory
calibration
fairness
games
TL;DR: We use learning in game dynamics as a unifying framework for the design and analysis of multicalibrated predictors with guarantees improving on past results.

Abstract: We provide a unifying framework for the design and analysis of multi-calibrated predictors. By placing the multi-calibration problem in the general setting of multi-objective learning---where learning guarantees must hold simultaneously over a set of distributions and loss functions---we exploit connections to game dynamics to achieve state-of-the-art guarantees for a diverse set of multi-calibration learning problems. In addition to shedding light on existing multi-calibration guarantees and greatly simplifying their analysis, our approach also yields improved guarantees, such as error tolerances that scale with the square-root of group size versus the constant tolerances guaranteed by prior works, and improving the complexity of $k$-class multi-calibration by an exponential factor of $k$ versus Gopalan et al.. Beyond multi-calibration, we use these game dynamics to address emerging considerations in the study of group fairness and multi-distribution learning.

A Unifying Perspective on Multicalibration: Game Dynamics for Multi-Objective Learning"
Nika Haghtalab, Michael I. Jordan, and Eric Zhao
University of California, Berkeley
{nika, jordan,, eric. zb) edu
Abstract
We provide unifying framework for the design and analysis of multicalibrated predictors. By placing the multicalibration problem in the general setting of multi- objective dearning-whee learning guarantees must hold simultaneously over a set of distributions and loss functions we exploit connections to game dynamics achieve state-of-the-art guarantees for diverse set of multicalibration learning problems. In addition to shedding light on existing multicalibration guarantees and greatly simplifying their analysis, our approach also yields improved guarantees, such error tolerances that scale with the square-root of group size versus the constant tolerances guaranteed by prior works, and improving the complexity of k-class multicalibration by exponential factor of k versus Gopalan et al. [17]. Beyond multicalibration, we use these game dynamics to address emerging considerations in the study of group faimess and multi-disttibution learning.
1 Introduction
Multicalibration has emerged as a powerful tool for addressing fairness considerations in machine
learning. Based on calibrated forecasting 6 12 which requires among instances z a predictor predicts the probability h(x) v, a fraction have positive outcome multicalliration yields more fine-grained guarantees by seeking calibration across large and possibly overlapping collections of pobpllppllaions (21). Multicalibration has been studied in numerous settings, including those with rich label sets (multi-class multicalibration [17),, adversarial rather than stochastic data (online multicalibration [18), and problems where no Bayes classifier exists (agnostic multicalibration (38)). The concept of multicalibration has also been applied to estimate other quantities, such as higher moments (22] and been strengthened in various ways, such as providing conditional guarantees (2]
Multicalibration's 's versatility has led to the development of numerous specialized algorithms, each tailored to unique multicalibration problem and requiring its own individualized analysis. Promising attempts to provide an overarching conceptual framework for multicalibration, such as outcome indistinguishabiliy [7]. have had limited success in unifying these various algorithms. this paper, we tackle this challenge, developing a general-purpos algorithmic framework to guide the design of multicalibrated learning algorithms for a wide range of settings and considerations.
Our approach is a dynamical systems and game-theoretic approach [see, e.g., 13 9. We demonstrate that many multicalibration algorithms be formulated as particular instances of two-player zero- sum games where players independently either run no-regret algorithms or best-response algorithms. wide range of multicalibration algorithms that exhibit varying trade-offs can be obtained by plugging in different no-regret and best-response algorithms. This unified framework both recovers existing guarantees and in many cases improves upon them.
Authors ordered alphabetically. Correspondence to eric. ww@berkeley...ooo..ook edu.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Problem
Complexity
Dynamic
Previous Results
Our Results
Reference
MC (Det)
Oracle
NRBR
O(ke 3)
17
O(In(k)=
Thm 4.2
MC (Sqrt Err, Det)
Sample
NRBR
O(="vAkm (n
O(E (In()(S)
Thm 4.4
Agnostic MC (Det)
Oracle
NRBR
0(12)
38
O(E 3)
Thm
E.9
Agnostic MC
Sample
NRNR
0(18)=
38
O((d + k)=
Thm
E. E.
Cond. MC (Det)
Oracle
NRBR
O(1S)²=-
O(1S)=
Thm
E.3
Cond. MC
Sample
NRNR
O(1S)' (d kije
0(15) (d + A)e
Thm
E.4
MC (Succinet)
Sample
NRNR
Oldd + AAjE
17
O((d + +1) 1))
Thm 4.1
Online MC
Regret
BRNR
O( lov(og( ( 18
(Matching)
Thm
4.3
rth Moment MC
Oracle
NRBR
O(rE*
(Matching)
Thm E.13
Table This table summarizes the sample complexity and agnostic learning oracle complexity rates we obtain for multicalibration (MC), compared with the previous state of the art. S denotes the set of groups one wants multicalihration on, d the VC dimension of S, the number of label classes, and e the error tolerance. (Det) and (Succinct) respectively denote when only deterministic only succinct predictors are acceptable. "Sqrt Err" refers to requiring an error tolerance of Ev /Pr(x E 5) for each group rather than E.
Although approaching multicalibration- min-max optimization problem-with game dynamics seems like an obvious approach, no prior work has succeeded in using game dynamics framing to unify multicalibration algorithms. The primary challenge not reducing multicalibration to min-max optimization, which is straightforward (Facts 2.3 2.66 but rather solving the resulting equilibrium computation problem in way that connects to practical algorithms. The needs of multicalibration (such as determinism, large and complex predictor spaces, etc.) differ significantly in this regard from earlier applications of general-purpose no-regret algorithms and game dynamics.
Our primary contributions can be categorized into three areas.
1) Unifying framework. In Section
give overview of game dynamics concise but general framework for obtaining muli-objective learning guarantees. To use these dynamics as generic solution to various multicalibration problems, introduce a powerful renerol-purpose no-regret algorithm (Theorem (.7) and a distribution- free best-response algorithm (Theorem (3.8), for calibration like objectives. This approach allows to unify the diverse and often, seemingly mmrelated-algorihmms that have been studied in the multicalibration literature, offering a general template for their derivation and analysis.
2) New guarantees. In Sections we use our framework to improve guarantees for various multicalibration settings (sce Table by simply plugging in different no-regret and best-response algorithms.. These improvements include an exponential (in k) reduction in the complexity of k-class multicalibration over Gopalan et al. [17] polynomial (in I/E) reduction in the complexity of learning a succinet multicalibrated predictor over Dwork et al. (7). the first conditional multicalibration results for the batch setting, the first agnostic multicalibration guarantees that beats uniform convergence, and a multicalibration algorithm that efficiently guarantees an eтrоr tolerance that scales with square-root we demonstrate that our framework can be extended
of each group's probability mass. In Section 5 to analyze problems beyond multicalibration, such as multi-group learning (39
3) Simplified analyses. We also demonstrate that our framework can recover the guarantees of various existing multicalibration algorithms, including online multicalibration (18) and moment multicalibration (22). while avoiding intricate and problem-specifie arguments.
1.1 Related Work
The study of calibration originated in online (adversarial) forecasting 20], with classical literature having also studied calibration across multiple sub sub-popula uub-populations [II. Multicalibration, on the other hand, is classically studied in the stochastic setting: i.e., where (ır;, ys ~ D, which case calibration is trivially satisfied by the predictor h(x)) E [v]. Due to this difference in formulation in the literature on calibration and that on multicalibration, the specific technical tools that have been developed in these areas have largely remained distinct. Our work can be viewed as bridging this gap by showing

---

that game-theoretic dynamics provides unified foundation for studying multicalibration, just as no-regret learning underpins the study of calibration.
Motivated by fairness considerations, a formal definition of multicalibration was presented by 21], and has found wide range of applications and conceptual connections Bayes optimality, conformal predictions, and computational indistinguishabiiiy [21. 22, 16 I8 Z 23 Algorithms for multicalibration have largely developed along two lines: one studying oracle-efficient boosting- like algorithms [see, c.g.,
21
25
7 and another studying algorithms with flavors of online Our work establishes that the contrast between these lines of work
optimization [see, e.g.. 18
and the algorithms they develop are entirely attributable to different choices of game dynamics.
Multi-objective and multi dinliiddistibbtiinnn learning concepts that have found broad applications in addressing fairness, collaboration, and robustness challenges. Blum et al. 4 initiated the study of learning predictors with near-optimal accuracy across multiple populations (distributions), with later works attaining tight bounds [19 34 31. Recently, multi-objective learning has been applied to settings where sub-populations are mutually compatible [37 39 3]. In Section 5 framework to match and improve guarantees relative to this literature.
we use our
Preliminaries
We use X' to denote a feature space and y a label space, where y [k] in k-class classification. A data distribution D is a probability distribution supported on labeled datapoints X' x V. We use H to denote a set of hypotheses and G a set of objectives, where an objective- or equivalently, loss-is a function é: H (X' )) + [0, 1] that takes a hypothesis and datapoint and returns penalty value.
We denote expected objective values by L == B(ra)) [E (h, (z. y))] For non-deterministic
p E A(H) and y E A(D x 9), we overload notation to write (g) = (D.p,(D.)) ( We
often use the shorthands (1:T)) = z(1)___ ..... (x') and {f(=
f(x(1), )...) f(x(")) We
also write -a. to denote the function x + f(a, x) or f()(a) (a) to denote + fa(a). For y E [k]
by E {0, 1} denotes its one-hot delta function, while for E [k], E [A] we write 6y.j = 11y = jl
2.1 Multicalibration
We use p = (A)))* to denote the set of all k-class predictors which are maps from features to label distributions. To differentiate between predictors and distributions over predictors, we refer to h E P as a deterministtic predictor, and p A(P), as non-deterministic predictor Calibration is a property of predictors
P requiring, for example in binary classification, that among instances x assigned prediction probability h(x))= [1 v, v] a fraction are truly labeled Multicalibration [21] is the finer- finer-grained notion that requires calibration on subgroups of one's domain. This set of subgroups is typically finite of finite VC dimension. In practice, we work with approximate notions of calibration//mlliccliiiiii assignment. In k-class prediction, we partition the k-dimensional hypercube into x equal cubes VV. where VA := {JO, 1/A), [1/X,2/X) 2/A).... }. For any interval VA. use h(x) E to denote that prediction hxx) falls pointwise in the buckets of U, i.e., h(r) E Uy for all j E [k]. We next formally define multicalibration
and discretize the range of probability
Definition 2.1. Fix 8 >> O. X E 74, and a set of groups S C 2 A (possibly non-deterministic) k-class predictor p E A(P) is (8, m)multiicaiibrteee for some data distribution D if
VS S [k)
E (..))DD
(M(z), 55.) 1[1(x) E E v $1 Sc.
That is, p is calibrated on every level set U E V every group S E S for every class j E [k]. We are often specifically interested deterministic solution; that is, where p E P.
*Imprrtatll, determinism of predictor h does not imply that & E yx as opposed to A(y)**
"This discretized (binned) definition multicalibration follows convention and can readily translated into others (21). We also follow convention in measuring in the fax norm, the l norm is also commonly used in calibration. Some definitions of multicalibration [e.g..21] appear as conditional expectations, but for constant probability domain subgroups, which makes them equivalent to our definition.
3

---

The batch setting, where we want to find a multicalibrated predictor for some fixed data distribution D, is the most commonly studied. Multicalibration can also be defined for online settings where the data distribution changes adversarially over time.
Definition 2.2 (Online multicalibration). Fix E E Σ,, and set of groups S C 2* In
online multicalibration, at every timestep [T]. a learner chooses a k-class predictor p ((P). Nature, which observes p(L:t), responds with any choice of data distribution D The learner's predictors pll.T) are (S, E, X)-online multicalibrated on D(1:T) if
T
YS ESE [k]
E hmpplt) (a-))~D())
[1 SS 1[1x)) E (h(x), dy,و] SE.
2.2 Multi-Objective Learning
We use multi-objective learning (a generalization of multi-distribution learning introduced by [9] as
a tool for studying multicalibration and other related problems. The goal of multi mujtti-o learning to find hypothesis that simultaneously minimizes set of objective values.
Definition 2.3 (Multi-objective learning). A multi-objective learning problem (D,g, H) consists of a set of objectives G, hypothesis class H. and set data distributions DD An E-optimal solution to (D, 9, H) is (potentially non-deterministic) hypothesis E (H)) where
max DED
ppp(p) S -min max LD= (h") + +E.
K'EH DCHD"EED EDDEEEEEE
We usually prefer a deterministic solution E H over a non-deterministic solution p E A (HH).
We mainly consider single-distribution multi-objective problems, where D = (D). though multi- distribution multi-objective learning arises in conditional multicalibration (Section E. and group faireess (Section 5). We can also consider multi-objective learning in online adversarial settings.
Definition 2.4 OOnline multi-objective learning). An online multi-objective learning problem (D, G. H)) consists of set of distributions DD objectives G and hypothesis class H. At each timestep e (T. a learner first picks hypothesis pl AHH).. Nature, who sees (11tt) responds with data distribution D(9) E D. We say the hypotheses p(::T) are s-optimal on the distributions (1::)) if
CDD,, S max min max LD (h"))++) + WED
max REG
In many problems consider, like online multicalibration, Nature can pick from any data distribution; that is, 'D is unrestricted. Let us also note that the baseline the raght-hand-side of (2) differs from that of [I). This is intentional: when D is unrestricted, the min-max baseline of (I) may be large, since there may be no hypothesis that is simultaneously good for all distributions. Instead, the max-min baseline of (2) is the best hypothesis h² for the most difficult distribution D*
Multicalibration as multi-objective learning. (Batch) Multicalibration is a single- diglic-distiuutionn multi-objective learning problem, whose objectives penalize over-estimation and under-estimation of label probabilities on subsets of the domain.
Fact 2.5. Let D be a data distribution for some k-class prediction problem and fix 0, X E Z and a set of groups S C 62x. For every direction i E {+1], level set v E Vh. group S E S, and class
j E [K), we define objective lij.S.u P > [0, 1] where
(h, (x., v)) 0.5 + 0.5 1(((x) U, E (h(xx) - -5.3)
and Gmc == (le.,S.. is the set of these objectives. Predictor p A(P) is 6-optimal solution to the multi-objectivv problem (ID), ((D),mee, P) and only if p is (S, 28, A)-multicalibrated for D.
Online multicalibration is similarly an online multi-objeccive learning problem.
Fact 2.6. Let ((TT)) be data distributions for some k-class prediction problem, D be the set of all data distributions, and Gme be as defined in 3.. Fix E > 0, X E Z,, and set of groups S C 2² A sequence of predictors ((ETT) E A(P) is e-optimal on ((::T) for the online multi-objective learning problem (D, Gmc, P) and only if (1::T) is (8, 22, A)-online multicalibrated on (11:T)

---

3 Tools for Solving Multi-Objective Learning using Game Dynamies
common approach multi-objective learning imagine game between a minimizing player who proposes hypotheses and maximizing player who proposes objectives and data distributions. It well-established (inspired by min-max equilibria, e.g.. [14 that a solution can be obtained when players use no-regret algorithms. However, considerations that arise in multicalibration motivate us to study a broader range of dynamics and their implications than has been commonly explored.
Online learning. In an online learning problem, at each timestep & E [7]. learner chooses an action at E A which an adversary observes and responds to with a cost function c(t) :A - [0, 1). We will usually assume costs to be linear maps. The learner's 's regret is defined as , (((::)) ==
E ((= (a!t) min EAA Ei= cl)) which no-regret algorithms like Hedge [14] can bound. Lemma 3.1 (Hedge Regret (24)). In an online learning problem where the action set is the simplex
A = As and costs are lineur, the actions chosen by Hedge huve regret of at most 2/1n2//uoo (b)(...T
We write no-regret algorithms as a function of sequence of cost functions Alg (10, 1} + A. For example, when A = Ax. the output of the Hedge algorithm is defined as Hedge(c ..... clt))
[w1/ ||[||| ....,...,,............. ....,
wx/ [|o]]]] where w;; =exp(-n Ei= (6:)). ). for specific choice of 1j.
We sometimes define regret against different baseline B E R. with Regg(a (1:1 (l:T)) ci
B. For example, we often consider the min-max baseline Bweak = T E max. c" (a*), where C is the set of cost functions that the adversary chooses from.
We also often encounter stochastic cost functions, functions of form e A x (X' x )) - [0, 1] for which we want to minimize expected value L.D.c == B(z,))= [e(- (2,, ())] on some distribution D.
A stochastic cost is linear if, for every x E X. V c(., (z, y)) is a linear map. The regret of online learning algorithms on stochastic costs concentrates quickly.
Lemma 3.2 (Stochastic Approximation B3]. Lemma 3.1). Consider an online learning problem on the simplex Ar with linear stochastic costs. Suppose, after each timestep I E [Ti-hatt is, after picking the action alt) estimate the expected cost LD with (a) (a,(1,)) y()),, where y/)) us D. With probability least 1 8. [Reg(a(:T)) ( } (1:T))
(agaaaa),,aa) S O((TTin(//0)
We say an action a is an e-best response to a cost if c(a) S miia"")"(a")) + Similarly, an action a is a distribution-free e-best response to a stochastic cost e if maX c(a, (z,z) < max yey min c(a", (zr é. We sometimes express the sample complexity of an al- gorithm in terms of the number of calls made to an agnostic learning oracle, which can compute e-best-responses to stochastic cost functions using few samples. See Appendix Aor a discussion.
Game dynamics. We consider no-regret dynamics between learner (minimizing player) who chooses hypotheses p(4) E A(H) and an adversary (maximizing player) who chooses data distribu- tions and objectives ( E ADD x 9) where the learner's loss is Lgen (p(9). When both players are no-regret, the time-average actions they picked quickly converge to approximate solution for the multi-objective learning problem (D, G. H). This method of no-regret dynamics has long played a role in empirical convergence to notions of equilibria [14]. Here, we review these dynamies and their convergence guarantees. While the proofs of these lemmas are standard at high level (and deferred to Appendix C.T). they differ in fundamental ways from past work. In particular, these lemmas consider weak regret, single timestep solutions (instead of time-averaged ones), and the consequences of having distribution free best responses, all of which play important roles in multicalibration.
Lemma 3.3 (No-Regret vs. No-Regret (NRNR)). Consider multi-objectii learning problem (D, G. H), where learner and adversary chose (1:T) e A(H)) and q(::T) E A(D x G). If both play- are no-regret, Regneat (p(2:T), (Cytes (1)))))) < T''s and Re (( (I:T)) <
TE, then the non-deterministic hypothests p = (n)form(p((:T) is a 22-optimal solution.
The next dynamic focuses on obtaining solution from single timestep, rather than time-averaged solutions. To obtain this, we consider a dynamics which the learner goes first and no-regret, the adversary observes the leamner's 's action and then best responds.
5

---

Lemma 3,4 (No-Regret vs. Best-Response (NRBR)). Consider multi-objeccive learning problem (D, G. H), where a learner chose p ((1:T) E (HH) and an adversary chose q E A(D x G). If the learner is no-regret, Regweak (pQ-T), , (.)) S Te, and the adversary e-best-responded to the costs (-()) (1:T) using qf (I:T), then there is aate [T] where (lt) is 2e-optimal solution.
Once the existence of single-round solution p(*) is established by Lemma 3.4 it is easy to find which time step corresponds to this solution by using few samples and testing all p (1:T) as follows.
Lemma 3.5. Suppose a set of hypotheses p(l.T) contains an e-optimal solution. We can find a 5e-optimal solution p(u) E p(1:)) using O [ samples with probability 1 8.
The next dynamic considers difficult distribution- problems, such as online multi-objective learning. To enable learning in these scenarios. we consider no-regret adversary that chooses objectives g g1::2) E (g)) and learner who first observes q()) and plays distribution-free best- response. The following lemma considers the consequences of these interactions.
Lemma 3.6 (Best-Response vs. No-Regret (BRNR)). Consider an online multi-objective learning problem (D,G,H) H), where a learner chose p(..T) E A(H), an adversary chose q(:i)) E A(g), and D(1:") E D is any sequence. Assume that the adversary is no- regret, ie., (eggg"":,((-Ann (((0)))))))) distribution-free e-best-responses to the stochastic costs q(2T)), i.e., maxa, (ia (plt)) S maxs,y ming- ((a.)).t (p") e. Then, the hypotheses p(1:T) are 2e-optimal on D(1:T).
S Te, and the learner's actions p(1:2) are
The question of which dynamic should be used and their implementation hinges on the type of solution desired and what online learning and best-response guarantees are possible for each player. NRNR dynamics often offer maximum sample efficiency, since calculating e-best-responses may be more sample intensive, but produce time-averaged solution. NRBR dynamics, though less sample- efficient due to the adversary's ' repeated best-response computation, provides a single timestep solution and is crucial for, e-g., deterministic multicalibration. BRNR dynamics, where learners follow (act after the adversary) and have greater ease being no-regret, are crucial for online settings.
3.1 No-regret and Best Response Computation in Multicalibration
In this section, we introduce algorithms for obtaining (weak) no-regret and best response guarantees in multicalibration, so that we can apply the previously discussed dynamics.
Since the adversary picks from the-lsually, small-set of objectives Gmc. it can be no-regret using standard algorithms like Hedge. However, the learner picks from the-very large-space of all predictors P; if it used Hedge, its regret would grow linearly in domain size |x']. An important aspect of multicalibration is that complexity must be independent of the domain size X' (while it can depend on the complexity of the subgroups S). We leverage structural properties of multicalibration objectives (see Appendix C.2 for formal treatment) to obtain generic no-regret and best response algorithms that give the learner commiinindeependee regret learning algorithm for the learner that provides three important properties simultaneously: 1) Domain-independent regret-bound that is also logarithmic in k; 2) uses no samples (or knowledge of) the underlying distribution D. and 3) deterministically outputs deterministic predictor per round. Properties 1-2 lead to fast convergence and low sample complexity in the aforementioned dynamics and property is key for obtaining deterministic multicalibration guarantees (via NRBR).
guarantees. Our first theorem gives no-(weak)-
Theorem 3.7. Consider P the set of k-class predictors and any adversarial sequence of stochastic costs (1-7) E ((Gme), where Gme are the multicalibration objectives B There a no-regret algo- rithm that outputs (deterministic) predictors prediccoo h(T:T) E P such that Regweat (H(T)) {ED.g(>) } (1:T)) s
2 (lk for every data distribution D. The algorithm does not need any samples from D.
Proof. Consider the following algorithm. At each feature x E X, initialize Hedge algorithm that picks an action (xr) E A())) at each timestep / E [T]. Aggregating each algorithm's 's action yields our learner's overall action (0) e P. For each z E X, let (x) be the outcome of Hedge at step

---

1 ++ 1 after observing linear loss functions S (()
A -R* - >00,1] for E [1];
1 M (z)== = 0.5 0.5 0.5
Σ
Bj Uis i.
(4)
where S. is the probability g()) assigns to loss L.j.S.v. Hedge gives E S Min (x))
(7)
ma())) Ei= S 2 (=*) S 2 [k))T (Lemma 3.1 Since this inequality holds for all x E X,
2/In(K)T 2
E (r.y)>D
Σ
h0, (x))
E (x.y)~
min 2 2*E(())
Σ Aco (=))
(=*)
(5)
T
E (m,y)~
Σ
if (1
hits
min EP
E (m,y)~n
Σ
En hit (1" (x)) (2))
by law of total expectation, where the last transition is by defining h- such that (x)x) = x" for every a-deependent choice of z" in (5 Add and subtract Ei= -t=1 E
[1 ((00,_(6) to obtain
(a.w)>
T
Σ
E
h00 (x)
S2 (24
(6)
(a.y)~D
1=1
where the last transition is by the fact (x)) [5, |x), Σt= 100 (h) - 5,)) 0.57.
Next, we show the LHS of (6) is equivalent to Reg (1:1) { (1:1)). First recall from
multicalibration objectives that (h, (x,y)) = 0.5 + 0.5 11(()) E v, E ()))(((()) (h(x), - 5yg)
(+) Since Sig,,S,v is the probability (()) assigns 5.. in 44) we have that ( (1) (x, (x.
((t) . (x)) 5y). Therefore, 6 implies that ET- L (h(*)) S 0.57 + 2 In(k)T. Is left to establish that the min max baseline of these losses indeed at least 0.5. This is implied by Fact 2.5
and its proof is deferred to Appendix C.2 Thus Regweak (h(1:7) (LD.g(t) (1:2)) s 2/In(K)T.
Our second theorem proves the existence of a distribution best-response algorithm for the learner, which is key for obtaining online multicalibration guarantees (via BRNR). Note that, as distribution-free algorithm, it requires samples compute these best-responses.
Theorem 3.8. Consider the sel of k-class predictors P. Fix E O and let q Al9ma) be a mixture of multicalibration objectives (3). There always exists a (non-deterministic) predictor p E ((P) that a distribution-free e e-best-response (7) to the stochastic cost function q(, (2x, y))-
Proof Sketch. At a high level, this statement and proof are similar to the min-max proof of calibration [T0 20), with additional details in Appendix C.2 Let A()) be finite covering of A()) and dx A(ā())) A()) - |-1, 1] the bilinear function da b)
_.). ( l E U, s) (ā, - b,)]. Consider p(x) = arg min max (x b). By
(EA(A())) BEA())
the minmax theorem, max &n (p(x),b) = max min Φz & max min (a b) + bEA()) aEā())
bEA())
BEA()) (EA())
Thus, max q(p, (x, & 0.5 max mink eP qhh", (x, y)) for all X.
L
4 Multicalibration with Game Dynamics
We match and improve a broad set of previous results in multicalibration (See Table T that had received individualized and ad hoc treatments in the past. Our work establishes that not only is there a unified approach for obtaining these results but that it all comes back to game dynamics empowered by our no-regret and distribution-free free response results for multicalibration mutiiallivationn-TTeeene -arerionnTThheemsss 3.7 and
3.8 Below we focus on three main results highlighting NRNR, NRBR, and BRNR dynamics. We defer the proofs, formal statement of algorithms, and additional results to Appendix D and
7

---

Multicalibration. Our first algorithm uses no-regret no-regret (NRNR) dynamics to find non- deterministic multicalibrated predictors. This algorithm matches the fastest known sample complexity rates for multicalibration [8 35 of order O(In( S| /==)) It also improves upon existing fast-rate algorithms of Gupta et al. 18,, Noarov et al. [55] by producing predictors with succinct support and small circuit size. These properties were previously only known to be attained by the less sample simultancously attains the best efficient multicalibration algorithms of [21]. In this way, Algorithm |
aspects of the algorithms of [18] and [21].
Theorem 4.1. Fix & O, X, k E E4, set of groups S C 2²x and data distribution D. The below 6, returns a non-deterministic k-class predictor that is (S,e, e, X)-
algorithm, with probability malticalibrated on D and lakes no more than O ((n(() /6) + k kl(())) samples from D.
No-Regret vs No-Regret
Construct the problem (1D), from Fact 2.5 and let T = CE 2 PIn( X² (8) for some uni- versal constant C. Over T rounds, have an adversary choose g(:T)) A(gme) by applying Hedge D. In parallel, have a learner choose predictors (1:T) E P by applying the no-regret learning algorithm of Theorem 3.7 to the stochastic costs ((:TT), where g(t) itd.
to the costs {1- (()(h)) (t))) (xx15), tyth) (1:T) where (x(",, .y(t) )
~ g( Return the predictor = Uniform(h(1:T) This algorithm
is written explicitly in Algorithm
Theorem 4.1 4.alnn along with all other results in this section-can be rewritten with VC(S) log l/)) replacing In ([S): : this is done by taking a cover of S. We further note that Algorithm | can be instantiated with different choices of no-regret algorithms for the adversary and different versions of Theorem 3.7 for the learner. In Section [6] we empirically compare such variants of Algorithm
Our second algorithm uses no-regret best-response (NRBR) dynamics to find deterministic multicali- brated predictors. This algorithm improves Gopalan et al. [17's 's oracle complexity of O (k/c²) with O (In(k)/=?). an exponential reduction of the dependence on the number of classes k
Theorem 4.2. Fix E > O, K E Z_, a set of groups S C 2*, and a data distribution D. The following algorithm returns a deterministic k--class predictor that is (S, (,,,,,))-ma ---ltiicalibbatted on D and makes (ln(k))/=)) calls to an agnostic learning oracle. Moreover, with probability 1 - 6, the
oracle calls can be implemented with δ (VI(()) (S)[K(|SAAA/ + k kI(())) samples D.
No-Regret vs Best-Response
Construct the problem (1D), Gme: P) from Fact 2.5 and let T = = C In((S) X*5) for some uni- versal constant C. Over T rounds, have a learner choose predictors ((TT)) E P by applying the
no-regret learning algorithum of Theorem 3.700 the stochastic costs g(1:T), Have an adversary choose
g(::T) by calling an agnostic learning oracle at each t E [T]: g(t) = As/ss(1 ( (. Using
Cln(T) (In(T/5)/e2 samples from D, return the predictor (1)))) with the lowest empirical mulficalibration
error. This algorithm is written explicitly in Algorithm 2
Online multicalibration. Our next algorithm uses best-response no-regret (BRNR) dynamics for online multicalibration, matching the best known regret bounds for online multicalibration [88 35 As with Theorem 4.11, our analysis simplifies that of [18] 35 by avoiding exponential potential arguments in favor of no-regret dynamics. We state the following result for binary classification, where y {o. }} but note it trivially extends to multi-class settings. For convenience, we will say that predictors P for binary classification output real-valued h(x) E [0, 1]. where h(x) is the predicted probability of class and h((x) is the predicted probability of class 0.
Theorem 4.3. Fix > 0, E Z,, and a set of groups S C 2 The following algorithm guarantees (S, on-oiie multicalibration with probability 1 - 8.
Best-Response vs No-Regret
Construct the online multi oulti-objectivv learning problem (D, Gmcc P) in Fact 2.6 and let T= T-Ce-2 Cc-2 (n((S) 26) for some universal constant C. Over T rounds, have an adversary choose ( ((gme) by applying Hedge the costs {1 (p("), (x((), ((((), ((:))) where
'In concurrent work, Dwork et al. 8 also showed that O (In(k)/E?) oracle calls are sufficient for multi-class multicalibration, with algorithm similar to Algorithm 2
8

---

(x ()))))))))))) Ltd. D(t), Have a learner best-respond to each stochastic cost g0) with the (e/2)
distribution- best-response pl) E (P)) of Theorem 3.8 This algorithm is written explicitly in Algorithm 3
The bigh-probbbility condition of Theorem can be removed if we assume nature presents data- points rather than data distributions, as is assumed in prior works. Interestingly, Algorithm 3]s use of best-response no-regret dynamics exactly recovers the online multicalibration algorithm of [8] 351 The analysis of Theorem 4.3 is, however, significantly simpler because we make explicit the role of the no-regret dynamics, whereas 18 35 use potential arguments that ultimately prove no-regret
dynamics and the multiplicative weights algorithm from scratch.
Additional results. We can also use game dynamics to improve guarantees for various other multicalibration settings and considerations. We can use Algorithms [ and 2 to achieve domain- independent sample complexity rates for agnostic multicalibration (Theorem E.9 improving upon Shabat et al. [38] 's uniform convergence guarantees. Plugging in an online learning algorithm with second-order regret bounds allows us to achieve the first non non-trivial sample complexity guarantees for conditional multicalibration in the batch setting (Theorem E.3) and a multicalibration algorithm that-with minor less than cube-root increase in sample complexity-guaraaeee for each group that scales with the square-root of the group's s probability mass (Theorem 4.4 We highlight the latter result in the following theorem.
an error tolerance
Theorem 4.4. Fix E > X, k E E., two sets of groups S C 2*, and data distribution D. There is an algorithm that, with probability at least 1- 6, takes ((ln(k) (In([S) In(A))/=*) samples from D and returns a deterministic k-class predictor h satisfying
E (2.g))
[(h(z); 66.)) 1[((x) EU, E ST] SE)Pr((E
for all S E S, Vh. [R]]
Plugging in an online learning algorithm with strongly adaptive regret bounds allows us to parallelize the moment multicalibration algorithm of Jung et al. [22 (Theorem E.1
5 Other Fairness Notions
This general framework of approaching nulti-objective learning with game dynamics can be extended beyond multicalibration to derive results on multi-group learning. Recall that, in agnostic multi- objective learning, the trade-off between objectives is arbitrated by the worst-off objective, which can be suboptimal when some objectives are inherently more difficult. An alternative is to, given problem (D, 9, H), define a competitor class H'' and try to learn a hypothesis l so that there is no objective that competitor performs significantly better on, i.e. Lig (h) mink EN Lxx (h*) S E where Cipe (h) == max
(h.)) We refer to such a solution h as being learning can find such a solution: replace the objectives G with new objectives G' := { (1 + E(-) - E(h')) ( G, h' E H'} and solve as usual. Since the sample complexity of objti-obeecttve learning is O (In((()) + |D] In( [g] (5)) 119. we have the below sample complexity bound on finding e-competitive solutions.
maxteg LD. (h) min
e-competitive. A simple modification to
Theorem 5.1. Consider multi-objectiive learning problem (D. H)) and competitor class H'. There an algorithm that takes O ((=-2(In((H)) + [D] In( (D) [74' [g] /8)) samples and with probability
1 --6 8 returns a solution E A(H) that is E-competitive against H!.
Consider the multi- group learning problem, where we seek to simultaneously minimize a general loss function on different subsets of the domain (37.
Definition 5.2. Fix ε > 0, a set of groups S S 2*, a hypothesis class H. and a loss
H. (X x y) + [0, 1]. An E-optimal solution the multi- group learning problem (S, H) is a randomized hypothesis p E A(H) that satisfies. for all S E S, E [(((p, (I,z)) - 1[x E S]] < min EH E [e(h", (z,y)) 1[x S]] + E. We always assume such a hypothesis p exists in class H.
A (near) optimal sample complexity for multi-group learning of O (In([S) [H))/²)) was attained by (39] using reduction to sleeping experts. (39 also asked whether there exists a simpler optimal algorithm that does not rely sleeping experts. We answer this affirmatively by designing optimal
9

---

algorithm that just runs two Hedge algorithms. The following is a direct implication of Lemma 3.3
and the observation that multi group learning directly reduces to learning an E-competitive solution.
Theorem 5.3. Fix set of groups S _ 2 loss e: y x ) - [0, 11. hypothesis class H. X + V and distribution D. There is a no-regret no- no-regret algorithm that takes 2T = O (In( S) =²)
samples from D and returns an e-optimal solution to the multi-grouy learning problem (S, H).
Empirical Results
In this section, we study the empirical performance of multicalibration algorithms the UCI Adult Income dataset (26), a real-world dataset for predicting individuals' incomes based on the US Census. We defer additional results, datasets, and methods to the Appendix G
Experiment setup. This experiment, summarized in T aims to learn a predictor on the UCI dataset that predicts the 'income" label and is multicalibrated on the values of eight other labeled attributes including 'age'. We discretize with 0.1-width bins (A = 10), and perform random 80-20 train/test splits of the dataset. This results in approximately 24000 training samples, 6000 test samples, and 130 groups. Each multicalibration algorithm is evaluated on 10 seeds, each after 50 iterations, with performance measured by their average iterate's 's and last iterate's 's multicalibration violations.
We study four multicalibration algorithms based on no-regret best-response dynamics. which use an empirical risk minimizer as the adversary and implements either Hedge [14), Prod (28. Optimistic Hedge (OptHedge) [36], or Gradient Descent (GD) as the learner. We study two algorithms based on no-regret no-regret dynamics, which plays against itself either Hedge (Hedge-Hedge) or Optimistic Hedge
Learning rate decay is tuned on the training set by sweeping over [0.8, 0.85, 0.9, 0.95] for the learner and [0.9, 0.95, 0.98, 0.99) for the adversary.
Algorithm
Train Error
Test Error
Test Error (Ergodic)
Hedge-Hedee (NRNR)
2.0e-2 + 2.0e-3
3.0e-2 + 3.0e-3
2.3e-4 + 2.7e-5
Opdeeee (NRNR)
7.0c-3 + 0.0
2.7e-2 + 3.0e-3
2.6c-4 + 2,8c-
OptHedge-Eil ERM (NRBR)
0.0 = 0.0
4.7e-2 - 1.0e-3
4.8e-4 + 9.0c-6
Hedge-HR (NRBR)
0.0 + 0.0
6.4e-2
+ 1.0e-3
6.4e-4
+ 1.1c-5
Prod-ERM (NRBR)
0.0 = 0.0
5.3e-2 4.0e-
5.3e-4
4,4c-5
GD-ERM (NRBR)
5.3e-2 = 1.1e-2
8.3e-2 + 3.0e-3
9.5e + 6.5e-5
Table 2: Average (#: standard error) of multicalibration violations on UCI Adult Dataset. Train Error and Test Error evaluate the last iterate (deterministic predictor) on training and test splits; Test Error (Ergodic) measures the average iterate (non-deterministic predictor) on test split. GD-ERM (NRBR) is worst and OptHedge-OptHedge (NRNR) is best on both deterministic and last iterates.
One's choice no-regret algorithm matters. The original multicalibration algorithm of 21, which is based gradient descent, consistently attains the worst multicalibration errors, both in terms of average-iterate and last-iterate. This is consistent with gradient descent being a theoretically less effective no-regret algorithm, due to instability near the boundaries of probability simplex. Due to the superficial similarity between boosting and multicalibration, the field has already begun adopting multicalibration algorithms with Hedge's multiplicative updates rather than gradient descent's 's additive ones 25 Our findings offer the first theoretical and empirical endorsement of this shift.
The last iterates of no-regret no-regret dynamics are surprisingly multicalibrated. The al- gorithms based on no-regret no-regret dynamics, namely Hedge-Hedge and SopHHedgeOOpHeddge consistently yield not only among the most multicalibrated randomized predictors (with their average iterate) but also the most multicalibrated deterministic predictors (with their last iterate). Note that these algorithms only enjoy theoretical advantage over no-regret best-response algorithms in terms of average iterate guarantees. This does not appear to be an artifact of early stopping or learning rates (Figure D.. but may rather indicate that their more stable adversary updates provide regularization.
Acknowledgements. This work was supported in part by the National Science Foundation under grant CCF-2145892 C3.AI Digital Transformation Institute grant, and the Mathematical Data Science program of the Office of Naval Research. This work was partially done while Haghtalab and Zhao were visitors at the Simons Institute for the Theory of Computing.
10

---

References
[1] R. Bassily, K. Nissim, A. D. Smith, T. Steinke, U. Stemmer, and J. R. Ullman. Algorithmic stability for adaptive data analysis. Proceedings of the SIAM Journal on Computing, 50(3), 2021.
[2] O. Bastani, V. Gupta, C. Jung, G. Noarov, R. Ramalingam, and A. Roth. Practical adversarial multivalid conformal prediction, 2022.
[3] A. Blum and T. Lykouris. Advancing subgroup faimess via sleeping experts. In T. Vidick, editor, Proceedings of the ACM Conference on Innovations Theoretical Computer Science Conference (ITCS), 2020.
[4] A. Blum, N. Haghtalab, A. D. Procaccia, and M. Qiao. Collaborative PAC learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 2392-2400. Curran Associates, Inc., 2017.
[5] A. Daniely, A. Gonen, and S. Shalev-Shwartz. Strongly adaptive online learning. In F. R. Bach and D. M. Blei, editors, Proceedings of the International Conference on Machine Learning (ICML), volume 37 of Proceedings of the Journal of Machine Learning Research, pages 1405-1411. JMLR.org, 2015.
[6] A. P. Dawid, The well-calibrated Bayesian. Journal of the American Statistical Association, 77 (379):605-610, 1982.
[7] C. Dwork, M. P. Kim, O. Reingold, G. N. Rothblum, and G. Yona. Outcome indistinguishabiiity.
In Proceedings of the Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1095-1108. ACM, 2021.
[8] C. Dwork, D. Lee, H. Lin, and P. Tankala. New insights into multicalibration, 2023.
[9] D. Foster and R. Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21 21:0-55, 1997.
[10] D. P. Foster. A proof of calibration via blackwell's approachability theorem. Games and Economic Behavior, 29(1-2):73-78, 1999.
[11] D. P. Foster and S. M. Kakade. Calibration via regression. In G. Seroussi and A. Viola, editors, Proceedings of 2006 IEEE Information Theory Workshop, pages 82-86. IEEE, 2006.
[12] D. P. Foster and R. V. Vohra. Asymptotic calibration. Biometrika, 85(2):379-335 1998.
[13] Y. Freund and R. F. Schapire. Game theory, on-line prediction and boosting. In A. Blum and M. Kearns, editors, Proceedings of the Conference on Learning Theory (COLTT), pages 325-332. ACM, 1996.
[14] Y. Freund and R. E. Schapire. A application to boosting. Journal of Computer and System Sciences, 55(1):119-133 1997.
generalization of on-line learning and an
[15] Gaillard, G. Stoltz, and T. van Erven. A second-order bound with excess losses. In M. Balcan, V. Feldman, and C. Szepesvári, editors, Proceedings of the Conference on Learning Theory (COLT), volume 35 of Proceedings of the Journal of Machine Learning Research, pages 176-196. JMLR. org. 2014.
[16] Gopalan, A. T. Kalai, O. Reingold, V. Sharan, and U. Wieder. Omnipredictors. In M. Braver- man, editor, Proceedings of the ACM Conference on Innovations in Theoretical Computer Science Conference (ITCS), pages 79:1-79:21, 2022.
[17] P. Gopalan, M. P. Kim, M. Singhal, and S. Zhao. Low-degree multicalibration. In P.-L. Loh and M. Raginsky, editors, Proceedings of the Conference on Learning Theory (COLT), pages PMLR, 2022.
[18] V. Gupta, C. Jung, G. Noarov, M. M. Pai, and A. Roth. Online multivalid learning: Means, moments, and prediction intervals. In M. Braverman, editor, Proceedings of the ACM Conference on Innovations in Theoretical Computer Science Conference (ITCS), pages 82:1-82:24. Schloss Dagstuhl- Liabbiiz-Zentumm für Informatik, 2022.
[19] N. Haghtalab, M. I. Jordan, and E. Zhao. On-demand sampling: Learning optimally from multiple distributions. In S. Bengio, H. M. Wallach, H. Larochelle, Grauman, N. Cesa- Bianchi, and R. Gamettt, editors, Advances in Neural Information Processing Systems, 2022.
11

---

[20] S. Hart. Calibrated forecasts: The minimax proof, 2022.
[21] U. JeherttJohnson, M. P. Kim, O. Reingold, and G. N. Rothblum. Multicalibration: Calibration for the coomputaioonall--ddentttan
masses. In J. G. Dy and A. Krause, editors, Proceedings of the International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, pages 1944-1953. PMLR, 2018.
[22] C. Jung, C. Lee, M. M. Pai, A. Roth, and R. Vohra. Moment multicalibration for uncertainty estimation. In M. Belkin and S. Kpotufe, editors, Proceedings of the Conference on Learning
Theory (COLT), Proceedings of Machine Learning Research, pages 2634-2678. PMLR, 2021.
[23] C. Jung, G. Noarov, R. Ramalingam, and A. Roth. Batch multivalid conformal prediction, 2022.
[24] S. Kale. Efficient Algorithms Using the Multiplicative Weights Update Method. Princeton University, 2007.
[25] M. P. Kim, A. Ghorbani, and J. Y. Zou. Multiaccuracy: Black-box post-processing for fairness in classification. In V. Conitzer, G. K. Hadfield, and S. Vallor, editors, Proceedings of the AAAI Conference on Artificial Intelligence (AAAT), pages 247-254. ACM, 2019.
[26] R. Kohavi and B. Becker. UCI adult dataset. UCI Machine Learning Repository, May 1996.
[27] M. Koklu and I. A. Ozkan. Multiclass classification of dry beans using computer vision and machine learning techniques. Computers and Electronics in Agriculture, 174: 174:105507, 2020.
[28] N. Littlestone. Learning quickly when irrelevant attributes abound: new linear-threshold algorithm (extended abstract). In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 68-77. IEEE Computer Society, 1987.
[29] S. Mannor and O Shamir. From bandits to experts: on the value of side-observations. In
J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. C. N. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, pages 684 2011.
[30] F. McSherry and K. Talwar. Mechanism design via differential privacy. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 103. Proceedings of the IEEE Press, 2007.
[31] M. Mohri, G. Sivek, and A. T. Suresh. Agnostic federated learning. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pages 4615-4625, PMLR, 2019.
[32] S. Moro, P. Cortez, and P. Rita. A data-driven approach to predict the success of bank telemar- keting. Decision Support Systems, 62:22-31, -1, June 2014.
[33] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-169, 2009.
[34] H. I.. Nguyen and I.. Zakynthinou. Improved algorithms for collaborative PAC learning. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 7642-7650. Curran Associates,
Inc., 2018
[35] G. Noarov, M. M. Pai, and A. Roth. Online multiobjective minimax optimization and applica- tions, 2021.
[36] A. Rakhlin and K. Sridharan. Online learning with predictable sequences. In S. Shalev-Shwartz and I. Steinwart, editors, Proceedings of the Conference on Learning Theory (COLT), volume 30 of Proceedings of the Journal of Machine Learning Research, pages 993-1019. JML.. 2013.
[37] G. N. Rothblum and G. Yona. Multi-group agnostic PAC learnability. In M. Meila and T. Zhang, editors, Proceedings of the International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 9107-9115. PMLR, 2021.
[38] E. Shabat, L. Cohen, and Y. Mansour. Sample complexity of uniform convergence for multi- calibration. In H. Larochelle, M. Ranzato, R. Hadsell. M.-F. Balcan, and H.-T. Lin, editors. Advances in Neural Information Processing Systems, 2020.
[39] C. J. Tosh and D. Hsu. Simple and opar-optimal algorithms for hidden stratification and multi- group learning, In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, editors, Proceedings of the International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages 21633-21657 PMLR, 2022.
12

---

Contents
Introduction
1.1
Related Work
2
Preliminaries
Multicalibration
2.2
Multi-Ojecctvv Learning
3
Tools for Solving Multi-Objective Learning using Game Dynamics
3.1
No-regret and Best Response Computation in Multicalibration
Multicalibration with Game Dynamics
Other Fairness Notions
Empirical Results
10
Additional Background
14
Proofs for Section 2
16
Proofs for Section 3
17
Game Dynamics
17
C.2
No-Regret and Best- Restones Computation in Multicalibration
19
Proofs and Algorithms for Section 4
23
D. Batch Multicalibratinn
23
D.2 Online Multcalibration
25
Additional Multicalibration Considerations
27
Conditional Multicalibration
27
Agnostic Multicalibration
29
Moment Multicalibration
32
E.4
Square-root Multicalibration Guarantees
35
Other Fairness Notions
38
Empirical Results
40
Experiment Setup
40
Results
G.3
Experiment Details
43
13

---

A Additional Background
In this section, we supplement our discussion of online learning with some additional notations and results.
No-regret algorithms. In the following lemma, we state the regret bound of the Hedge algo- rithm [14 for general choices of the learning rate 17 (0,
Lemma A.1 (Hedge (24)). Consider an online learning problem on the simplex D and any adver- sarial sequence of linear cost functions cl.TT), If Hedge, with learning rate 1) (0, 1), outputs a alI:T) then Reg(a (al1:T), (((:T)) & Tn+
ln(k) If = /ln(I
( = 2 In(k)T.
It is helpful to note that the learning rate of the Hedge algorithm also bounds how far its iterates move in the primal space.
Lemma A.2 (Hedge Iterate Stability), Consider an online learning problem on the interval [0, 1] and any sequence of linear costs. Let ((1:T) E [0, 1] be the actions that gel picked by Hedge instantiated with learning rate n E (0, 1). Then, for every timestep E [T]]|((1) a()) S 2n
Proof. By the triangle inequality, it suffices to prove that the learner's actions move by at most 21j at each timestep. That is, [a(++)) a S 2n at every timestep E [T]. By definition of the Hedge algorithm, the learner's action at timestep is given by
exp( 17 E.= (1)
(++1
exp(-n clr) (0) + -ap(-nnt (1)
We rearrange this (++1) = (1)) a ex-cpp( ( (1)), where is ratio of normalization terms defined as
exp(-n)
r- 1-1 (()) (0) exp exp(-n) (1)
exp( ( E (0) exp( - nc (0)) exp( (-1) Et= (1) (1))
Note that 2 1. Let write x1 exp( (xpp-n/> Σn el) (0)), 22 exp(-n el) (1)), x3
exp(-no()(0)) and 24 exp(-ne (1) (1)), noting that the values 2 22, I3, 11 are all positive. Observe that デリ
+2 < max - 1 24 }. To see this, suppose without loss of generality that xạ 2
33. Then x2 - 22:24, which implies that æ 32 S zamataua or equivalently, 21.29
234
23
23
Substituting in our values for Fı, 22, 23, 24, therefore have
1 a S max exp(-ncct) exp(-ne(t) S exp(-n)
The second inequality is because costs are bounded in [o, 1]. This gives the iterate movement bound
al01 max? (1) exp(-nrc(0(1) exp( 10 exp(1) -
(1(+1)
exp((xcc((()) a00l)
<max (a))ex(()))
Here, the second inequality applies the fact that le- - 1| < |x| for any x 2 0 to the right-hand value. Since 17 E (0, 1), we can use the fact that (exp(1) 1 2m. Thus, we attain the desired bound (1(+1) (1) 2n.
We can modify the Hedge algorithm to obtain strongly adaptive regret bounds that provides guarantees for every contiguous interval.
Lemma A.3 (Strongly Adaptive Regret 5
Consider online learning problem on the simplex that, for any adversarial sequence of linear costs ( 5)
AK. There is modified Hedge algorithm
14

---

outputs actions a! (::)) such that, for every interval Ti < ST,
Reg(a (1 ( (T.TT)))
Σ (a
min Σ 0 (a") t=
a
0 ([vnn(k)+ + In(()) vT2 - Ti
There are also online learning algorithms that provide second-order regret bounds. We present the regret bound of one such algorithm, Prod [5].
Lemma A.4 (Second-Order Regret Bound of Prod [5].. Consider online learning problem on the simplex = A and any adversarial sequence of linear costs c1:T) If the Prod algorithm of 15V is used and outputs the actions (1:T), then
Reg(a (1:T) (. so
In(k) E [(eb)aal))-ch)) (l*))2 t=1
max a'EAA
We also know that there are adversarial bandit algorithms with sublinear regret guarantees.
Lemma A. (Semi Bandit Regret Bounds (19). Consider online learning problem the simplex Dk. and any adversarial sequence of linear costs c(1:T), Let I be partition of [k) into groups. There high-probabillig variant of (29)'s 's ELP algorithm that, for any adversarial sequence of costs (1:T) outputs sequence of mixtures a (1:1) E Dg such that, with probability at least 1 - 8,
Reg(a ( S ( (Vrln(k/8yT)
Moreover, after each time the algorithu chooses (! the algorithm samples an integer j(t) ~ (t)) (unseen by the adversary). Let (() is the group in I that it belongs to. The algorithm will only ever observe the components of its cost vector corresponding to I(i(t)): (cl E I(t())} (0.
Best responses. An action a is an 8-best response to a cost function c A - [0, if c(a) < min c(a") + E. An agnostic learning oracle Ag (A 1]) 24 A is function that, given a cost function e and subset of actions A' C A.A computes an g-best response Ac, to from A'. When A' A, we may write Ae(e) without the second argument. Agnostic learning oracles are given this name because they are usually used to find best-responses to the expected values of stochastic cost functions using some number of samples. Through this paper, we design learning algorithms that only interact with a data distribution through querying an agnostic learning oracle; the oracle complexity of such an algorithm defined as the number of agnostic oracle calls that the algorithm makes. Using standard sample complexity bounds, all our algorithms also have corresponding sample complexity that circumvent the use of agnostic learning oracles.
Another concept we encounter in online settings is the distribution-free best response. An action is distribution-free e-best response stochastic cost if
min c(a", (xr, (Ir max c(a, (2r, v)) S xEX. aAA ye
Best-response algorithms. We can efficiently find an & best-response to the expected value of a stochastic cost function using agnostic learning oracles. For example, computing single best- response requires at most (Im((A))//" samples by uniform convergence. In game dynamics, will often need provide best-responses for a sequence of stochastic cost functions. These sequences are usually adaptive, in that which stochastic cost functions appear later in the sequence depending on how we responded previous stochastic cost functions. Adaptive data analysis algorithms for these settings.
provides
Lemma A.6 (Adaptive Data Analysis (I Corollary 6.4). There an algorithm that, for any adaptive sequence of stochastic costs ((::1), is guaranteed with probability 8 to e-best respond to each cost in (D (1:T) while drawing al most
VT 2
In
3/2
1
(TTn((AA/0))
samples from D. Here, (.) suppresses In(1/s) and In (1/00) factrrs.
15

---

Remark A.7. It often suffices. for our results, that a sequence of actions a is on average E-best responding cost sequence c that is, E elt S > ming E e (a*)+ Te. Thus, may be possible to use more efficient minimization oracles than Lemma A.6 in our algorithms.
+Ta.
B Proofs for Section 2
This section proves Fact 2.5 and Fact 2.6ct226fooro from Section 2
Fact 2.5. Let D be data distribution for some k-class prediction problem and fix 0, X Z+, and a set of groups S C 2 For every direction E {+1), level set v E V group S E S, and class j E [k), we define objective S...S.v
[0, 1] where
(1, (2, u)) 0.5 + 0.5 1[{(x) u, E (h(()))) - -
(3)
and Gme (.i.s,eeis.. i.SSSe the set of these objectives. Predictor p (PP) is e-optimal solution to the multi-objective problem ({D), 9me, P) if and only if is (S, 2E, A) multicaalibiee for D.
Proof. In the multi-objective learning problem (D, Gme: P), the multi-objective value of a predictor (p) = maxp ED LD- x (p), exactly the (rescaled and shifted) magnitude the predictor's multicalibration violation. Formally,
1 max (p) 2 jE(M),SSS,revV (ma))-Db>pp
E
[1(()) - )9.s) 1[b(x) E o, E S]]
Since write the absolute value of an abstract value |w] maxie(=1) i w, next observe that the optimal multi-objective value of the problem (D, Gme: P) is 0.5.
min L- (²1h)) hPEP
2 + max i. 2 (=(11)
max E [(h(z), - 593) 1[((x) E v E S]] jE( (w.v)~D "EV. hmep
2
This fact is because multicalibration objectives Gme are symmetric around 0.5 (where i == +1 and i == 11 penalize over and under estimation), leading to the worst loss to be at least 0.5. Furthermore, the Bayes classifier ht neither overestimates nor underestimates the label distribution and therefore achieves the loss of 0.5 exactly. Combining these inequalities, we have
(x)
min L- (h²h)) = max 2 SES
[(h(x), - 5n.)) 1[h(x) E E S]]
MPPP
[a.n)~D h-pp
Therefore L (p) min (* = = and only if our multicalibration violation is 2E.
Fact 2.6. Let (1:T)) be data distributions for some k-class prediction problem, D be the set of all data distributions, and Gme be as defined (3). Fix >> 0, X E E④, and set of groups 8 2* sequence of predictors p(2:T) ((P) is e-optimal D(1:I) for the online multi-objective learning problem (D, Gmc; P) and only if (1:T) is (S,22, 22, X)-online multicalibrated D(1:T).
Proof. Note that online multicalibration an online multi-objective learning problem by construction. To analyze its optimality condition, expand the definition of the objectives in Gie as
1 T
Din e (0)
max EEG
1
+
max JE(KSSSS
E k
Σ
1| e S] 1[h(z) e o) (h(z), 60:5)
2
DEVt
(w,))~(())
We again observe that the optimal value of the problem 0.5; formally,
max min max Ln., (h") 0.5.
D' KEE E*E
This is because choosing h² be the Bayes classifier for D* achieves the value of 0.5, which given the absolute value in the second term is the minimum achievable value. Thus, pl:T)) is e-optimal on D(I:T) if and only if p is (S, 2e, opttiia on (1:T))
16

---

C Proofs for Section 3
We first recall our characterization of multi multi-objeectve learning as two-player zero-sum game. this game, a learner player chooses non-deterministic hypothesis A(H) and an adversary player chooses a joint distribution over data distributions and objectives q E A(D x G). The payoff of the game is the expected objective value (p). In single-distribttion multi-objective learning problems where the adversary only has one data distribution D to choose from, we sometimes write q E A A(G) for simplicity. In online multi-objective learning, the adversary does not have control over which data distribution is chosen by nature. In these cases, the adversary only chooses objectives q E A(g) and the game payoff function becomes (p))
C.1 Game Dynamics
We now prove formalizations of Lemma 3.3 Lemma 3.4
Lemma
3.5 and Lemma 3.6 from Section
B
The following is a formal restatement of Lemma 3.3
Lemma C.1 No-Regret vs. No-Regret). Consider a multi oulti-objective learning problem (D,g, H), and two sequences (1:T) E (HH) and (1:))) E A(D G). Suppose Regn (p(1:T) (+) s TE and Reg(a (1:T), {1 (p(t))))) (1:T) S Te where B E R. Then, the non-deterministic hypoth- esis p E ((H) defined as p = Uniform(p! (pll:T) satisfies (T) S B + 2E. If the baseline B the min-max baseline Bweak then p is 22-optimal solution for the problem (D, 9, H).
Proof. By connecting the adversary's regret bound and the learner's (weak) regret bounds of
Lo -e S
Cgtor (1) and Egjto (v S T(s + B);
max D' ED
t=/
directly observe that max
(o 2$ B. Linearity of expectation
allows us to equate + ΣT= LD- (p(1) = L (T)), which yields our first claim that (T) <
2s B. The second claim just plugs Bweak into the previous inequality obtain the definition of 28-optimal solution.
The following is a formal restatement of Lemma 3.4
Responesp..s). Consider a multi-objective learning prob- lem (D, G, H) and two sequences p(2:T) E A(H) and q(::T) A(D G). Suppose S Te where
Lemma C.2 (No-Regret vs.
Reg (p (p(: (Egen
TR. Further suppose (1:TT) are, on average,
best-responses to the cost functions {1 (100)33)) Then there exists a t E [T] where (D(")) < B 2e. If B Bweaks then ((t) is 23 20-optimal solution for the problem (D, G,H,.
Proof. Assume the contrary, namely that L (p(t)) > B + 2= at all t [T]. Then
T
Te
2
C (p() - TB,
(bounded regret w.r.t. B)
t=1
L (p("t) -TT TB,
(on average e e-best-responding)
1=1
T
[B + - C -BB),
(assumption to contrary)
gives us a contradiction that T(2 - 22) > This proves our first claim. The second claim follows by plugging B = Bweak into our inequality L (p(1)) S B B+2 2s to obtain the definition a 2e-optimal solution.
The following is formal restatement of Lemma
3.5
17

---

Lemma C.3. Consider multi-objectivy learning problem (D.g.7 H) and a sequence p!:T) E A(H)
of hypotheses where at least one hypothesis p(t) is e-optimal. We can find a 3e-optimal solution plt") E p(u:") with probability at least 1 - 8 by taking only D(s-2In(TT [D] - |9| (8)) samples from each distribution D E DD If we further have access to sequence g(2:T) E A x G) of
best-responses to the cost functions (1 - {( ()())) ((.T) then a 5e-optimal solution can be found with only In(T))))) samples from each D E D.
Proof. Let the e-optimal solution be denoted ploms)) This claim is a simple uniform convergence argument. Suppose that N i...d. samples XD drawn from each distribution D E D. We can then use (p))(p) denote the empirical value of the loss function E of hypothesis p on distribution D, as approximated by the samples xp- We similarly define L as the empirical analog of the multi-objective value L Since the range of each objeclive is bounded in [0, 1J. Chernoff's bound
guarantees that for any q A(D x g) and p A(H) we have Prx (P) (g( 2 E -
exp (-2Na²). Taking a union bound over each D ED E [T] and 8 9 gives
Pr x
- DD, D, [T]: ( -D,,))) - 2 _
2 | T exp (-2NE?).
Letting t" = arg min ('((()) and N= 0 (c-21 In(TT) |2) (1)--11//6)) guarantees
L - (1 - E Er (n(t") S I (vllome) S L (p + s S min L (*²")) + 28,
with probability at least 8. We can therefore return p(t') as our solution.
To prove our second claim, take instead a union bound over each /. E [T] so that
Pr x
3t [T] (2qro - Cp (p(o)) 2 E S 2T exp (-2N=²).
Letting t = arg m Lyto (p!9) and N = O (s-2 (m((/)) guarantees with probability at least
1 8 that we can return pft") as our solution, as
L (p(t") 22 S Cytee (p(")) -E < (grr>((((")) (p(()) < E of (row) (ollmeel) S (((mm)) (pllowee)) +E
(since ((')) is an s-bost response.)
S L (phtowll) +2 S min (*(h²) + 3E.
The following is formal restatement of Lemma 3.6
Lemma C.4 (Best- Respones vs. No-Regret). Consider a online multi-ohjective learning prob- lem (D, 9, H) and the sequences (1::1) A(H), qLa.)) A()), and D D. Suppose
(1000))) S Te and p(u.T) E A(H) are distribution-free e' best- responses to (., (I, Then, p!l:T) are (s + t''ottml on D(1:)).
Reg(g (1-
Proof. Let DD be the set of all data distributions over X' x V. By linearity of expectation, the maximum arg maxpep LD(p(() can always be attained on degenerate distribution supported only on a single point (z, y). Thus, the learner's distribution-free best-response guarantee provides the bound
EDi, ex: (D) - e' < max 9 19 (p)),
10, (x,1)) - < max min EDr,,re> (h"). D'ED* h EH
NEX
We can obtain our desired claim by recovering 2 with a triangle inequality between the adversary's regret bound and a summation of the previous inequality over t [T]::
LDw (p - -Ts <
Eiit, ()))),
max E9
Σ Eon (p) -Te' <
max min LD- .000 m0)
S max min max CD.,e (h).
T
D'ED" heWl
D'DD MEH
18

---

C.2 No-Regret and Best-Response Computation in Multicalibration
In this section, we prove generalizations of Theorem 3.7 and Theorem 3.8 from Section B which describe why multicalibration objectives are amenable to efficient online learning. a more general class of multi-objective learning problems. We refer to such problems as having separable objectives.
Definition C.5. Consider multi-objective learning problem (D, 9, H) where H is the set of all functions of form h X - W and W is some convex space (and not necessarily the label space y). We say the objectives G of such a problem are separable if every & E G is form
E(h, (z, v)) = c fe(x, h(z)) (h(z) - ge(y)),
where Je: X' x W - W and gr y + W are arbitrary functions and e is some constant offset.
We will see that, like with multicalibration objectives, having a learner's cost functions all be separable objectives introduces two major advantages generally.
There exist no-regret learning strategies that do not require to randomize their actions, or even sample any data, yet still guarantee The following theorem, which proves this advantage of separable objectives, is generalization of Theorem 3.7
Advantage 1:
regret bounds.
Theorem C.6. Consider a multi-ohjective learning problem (D,g, H) where all objectives in G are separable and all distributions in 'D are absolutely continuous with respect to a com- mon distribution D Let A be an online algorithm that, for any linear costs c(1:T), out- puts actions a (1:2") E W where Reg(a (000)))
c..21) 3 R(T)). If [D] > 1, further assume Reg(a(2:)) (.:)T) S R(T)- max V (c)(((()))))- - (a*)) Then for any stochas- tic costs g(az)) E A(G) and distributions D(1:T) E D, the below algorithm oulputs predictors h(:T)) E H where Regø- (hO:T), DCD go ())A))) S V(DjR(T) and B is the baseline
B²
min N'EH T
max E NEH
(f(xx, (h*(x) ge(v))
(8)
(D tng
Al euch timestep construct the predictor ( 1) (x) by setting, for all X.
(z) = =A(e (1) where (w) = 2 (x)
1 (x)
(1+ E englr)
[f(le,)()<=)] .w)
where (x) (n) is the Radon-Nikod derivative of D(F) with respect to D
Proof. First, suppose that D = (D), that is D = 1. Then, for any x E X, ex (1:T) are linear costs and thus A guarantees Reg( (z) (1:7)) R(T). By the law of total expectation,
2R(T)
dD(x) fe |00 (x)
dD fe (1, (1,
E ()
min w wWWW
E togite
=
(D)
dD=(x)
D
T'
T min W'EW
[se(c,N0)]] (10000)
E
- E znD
E toug(t)
w0
Z>D
(nig(t)
T
((((2,1(0)) (100))))
(F((z,)(0) -x)(
E D(t
min EH
E
2 Dit,
tml
19

---

If [D] > 1, A further guarantees
T
Pr(x). Reg(( (x)) (.) D-
s Pr(x) max R(T),
(110 2 (w)))
D
wEW
(x) 2
S Pr(x) R(T)
2T
dDr())
T
S
R(T)-
Pr
(x)²
2T
D
For simplicity, assumed above that (1:T) each have discrete support. The law of total expectation gives
V2. R(T).
Pr (x)
2T
Die)
(x) fele,hh0)) (x)
dzl
E
E
min w. WW
E
-
D~D-
Engg(t)
(D)
Eng(t)
dDr(x)
T
E Dengtt)
he)( (x))
(x))
min h E'
E Dit
To bound the lent-hand term, we can apply Cauchy-Schwand to get
To Pr(x)2
Pr (x))
E
Σ DED
D
T
D
xE
ZER'
TD
Pr(x)
D
T
ZEX DED
Pr(x)
T
D
DED
ZEN
S D
where Tn is the number of timesteps E [T] where D(C) D. Thus, whether [D] or |D] >
we have
T
T
[Felo, [x)(
[f(x,)()) m(xx) $ S2VID
min MEHH
D(t lnglts
DIO (bug(t)
t=l
Adding and subtracting the term Σ E Dc [felz, (())))())) we have
T Σ
[e(2, (())))) -e(())]
((()) (tg(t)
1=1
s 22//D)R(T) + min M
E ((t)) (t)
(3))))) -
20

---

Adding the constant c to both sides, we have
git (110) (D) + +T min
E
e a+ felz; (x) se(vi))
K T
t=1
Eng
s 22//DIR(T) +T min ME T NEH
max
Σ
E
lo+ fe(zz -(e)))))
(a.)) Eng(t)
We can directly prove Theorem 3.7 by instantiating the algorithm of Theorem no-regret learning algorithm A.
C.6 with Hedge as the
Theorem 3.7. Consider P the set of k-class predictors and any adversarial sequence of stochastic
costs (1:7) E (9 where gme are the multicalibration objectives (3. There is a no-regret algo- rithm that outputs (deterministic) predictors h ((T:T) E P such that Regweat (h(1:T), ( } (1:T)) S
(
2 /llT for every data distribution D. The algorithm does not need any samples from D.
Proof. First, observe that every objective in multicalibration is separable. Specifically, for every i E j E [k], S E S, v E VX. the corresponding objective Li.j.S. E gme can be written in the form i. (h, (x. v)) c+ ( h()) (h(x)) ji. (v)) where
0.5, W = A U Ak. Ii..8, v) 5, and (x, = 59 0.5 - [M(x) E u, E S). Next, we recall that
((())(((())
by Lemma A.1 the Hedge algorithm guarantees regret bound of 4 //nkk)]T for any linear costs on W An -A (Lemma A.I). The algorithm of Theorem C.6 for any stochastic costs (1:T) E A(9mn). outputs (1:T)) where
T
Σ (1)00) S 88VIn( + T min max max E h EE e Eg NEH (2.1)=-)
|c+ (x, (hh x(i))
< 88]nn() T max max E E9 MEN (an))n
(c+ Se- (x)) (g(y) s(v))l
<8VIn(AAT + Tcc
if we choose (x) = B (g() x]. Since the adversary is choosing from objectives symmetric around e, the min-max baseline B is at least meaning that Regwesk (1:T), (.r (1) S /In(())T
Advantage 2: There (almost) always exists distribution-free best responses. This advantage is what allows multicalibration to be achievable in online settings where data arrives adversarially. 110 (0 first showed that this advantage exists in calibrated online forecasting when Hart pointed out that Foster's asymptotic calibrated forecasting result could be obtained by appealing to Blackwell approachability. Moreover, their proof extends trivially to online multicalibration. Later on, [18 35) independently rediscovered this same advantage and proof. In the following theorem, we provide generalizes to all multi-objective
rigorous treatment- largely in line with the prior learning problems that have separable objectives and satisfy some weak compactness conditions.
Theorem C.7. Consider an online multi-objective learning problem (D, G. HH) with separable objectives and where 'D is the unrestricted set of all data distributions. Further, consider any objective mixture g E A(G) with finite support and suppose that for every objective I G. (1) there is a finite subset Y& C y s.t. {ge(y) E Ve} is an (g/3)-ned for {ge(y) y E Y), (2) the range of ge convex, compact and finite-dimensional, and (3) fixing any x. y pair, E(h, y)) is, in the argument h, function of bounded variation. Then, for any > 0, there is non notedettriiiisticc hypothesis p ((H) (given by (9h) that is a distribution E best-response for q.
Proof. Let G2 Support(q) be the support of our objective mixture, noting that 1gg assumption. Let W, S Trrs, W denote the range of the vector- vector-valued function g y + W, where g(v) == (ee(v)lees, Fixing some X. observe that we rewrite our loss q(, (z, y)) as the
by
21

---

function qo : W x W3 + [0, 1] where q(h, (z. v)) = Toe (.(h(z)) and we define (2( v) = c+ Eeng (fe(w,,1 () (w vt)]-
By assumption (3), Te (w, v) is a function of bounded variation in w for all a E 2, E Wg. By Lemma C.9 for any
X E y, there must exist some finite subset Wa.y E W such is an (e/3)-net of {Ta (w, (z, (e)g()
that (āe (w, (z, (())))
Let us choose W. == Ueeg Uyey, Wz,y, which is a finite set as [3eel < oo by assumption (1) and we Ggl < co by assumption. Moreover, by construction, for any V, (w, (z, v)) is an (2e/3)-net of {ūx (w, (Ir, y)))
We now define our best response pointwise at each I E X, letting
p(z)= = arg min max ="EA(W.) yEy wwws (u (x, ((y))) = arg min max w "'E((W.) s(o) www
E
[7,(w, (z, g())))
Because each objective l is separable, (w, (V))) is linear in (v)) By linearity of expectation, we also know that Euwe- lg (w, (I, {()))) is linear in w². Thus, for any æ E X,
max Ts (p(x), (c, {()))) = min max s
w-EA(W,) s(u)EW, ummw (w (x. (()))) (w, (x. ( (U)) (minimax theorem)
(construction of f)
max min
s(vieW w EA(W,) wwws
S max min E (w, (2t g + re, (discretization error) (x (x. ((n))) + re.
s(y)EW, EA(W) wwas"
< max min a())WW, EAH
In the above, we were able to apply the minimax theorem because of assumption (2). Recall that our construction of Wz guarantees, for any E W.y V there is a w' E W2.v's E ) such that
(n, (z, p()))) (w,, (x..(()))) < e/3, (u/ E))
(w, (z, g(y())))))))))))))))))))))))gg Cx g ()) s/3, (w' E We,)) (w', (()))) - To(w', (I, (()))) S s/3, (v/ E e²) (w, (x))()))) Tn (())( S a. (triangle inequality)
We, therefore, have that
max (P.( max
xEX (1,
DED
max Th (p(x), (I,
max min (x (r), (r.)()))) rre
=EX,gl)) (E((H))
max min (p'p' (x), (z, ,(v))) +rs
xEX EA((H)
max min LD. (p") +re.
DED EA(())
We can now directly prove Theorem 3.8
Theorem 3.8. Consider the set of k-class predictors P. Fix an E > 0 and let q E Al9ma) be mixture of multicalibration objectives 3 There always exists a (non-deterministic) predictor p E A(P) that a distribution-free e-best-response to the stochastic cost function q(:, (x. ()).
Proof. Let (D', G'e. P) be the relaxation of the problem (D, Gue, P) where, instead of assuming that nature can only sample discrete labels y E [k], nature too can sample mixed labels y E Ag. By linearity expectation, we have that ma Lr (p) = maxDeD (p) for every predictor p E ((P) and objective y E Gme, where o' E G is the relaxation of g. Thus, distribution & best-response 7 for the relaxed problem is a distribution-free
best-response for our original problem (D, Gme: P). We next observe that (D', G P) satisfies the conditions of Theorem C.7
22

---

Recall that every objective q' E gime can be written in separable format where, for every e {+1],j E [k], E S E VX, we can write (...S, (h, (x, y)) = c (z,, h(x)) (h(x) (... where c = 0.5, St, = y and fi (2. h(x)) E [0, 1] SJ. The domain and range of identity gi..s. y exactly A& which is convex, compact, and k-dimensional; thus, it has a finite e-covering. Finally, we observe that (h(z), (r, v)), and by extension &. (h, (2r, y)), is always piecewise constant function in h(x)) with finite discontinuities. It follows that S. must be of bounded total variation in h(x) as variation along any linear segment most Thus, Theorem C.7 states there exists a distribution-free best-response for (D', Gme P) and by extension (D, Imc: P).
0.5-2-1 E v, E
Remark C.8 (Closed-form of distribution-fies best-responses). For calibration and multicalibratiin problems, the best-responss implicitly defined in Theorem C.7 takes a clean closed-form. for any given x E X, p(æ) randomizes on neighboring actions. This simple closed form was first derived by [10] and independently rediscovered by [88.
In Theorem C.7
referenced the notion of function being of bounded variation. This is a common notion in analysis which says that a function cannot go up and down too many times; thus reasonable objectives (including every finite loss function you can think of) should all be of bounded variation. For completeness, we prove below that bounded variation implies finite domain coverings.
Lemma C.9. Consider a function f K (0, 1] where K is convex compact subset TR". Suppose that f has pathwise bounded variation on K: that is, there exists finite constant M such that for any linear path y [0. 1] + K. Vf(f) supo-to S SuSSt=- E llf(r((t)) - -f(r(t=-1)) s M. Then for any > 0, there exists finite subset C K such thatfor every y E f(K), there exists an D, with fx+) yl <.
Proof. Since is compact, is totally bounded. For any 5 > O, there exists finite set T such that K is covered by balls of radius ó centered at points in T. Let ó ZMT where M is the constant from the pathwise bounded variation condition. For each point 1. T, choose a point 8, E K such that || [|] < 8. Define S = {sx / T}. Let y ʃ(K). Then there exists x E K with f(z) = y. Since K is covered by balls radius centered at points in T, there exists a t with | - t|| < 8. By the construction of S. also have ||s: t|| < 5. Then, by the triangle inequality,
[ss - x < || - t/| + ||t xl < 26 = -/- Consider a linear continuous path ? [0, 1] + K and 711 s; such a path must exist by the convexity of K. By the pathwise
with (0)
bounded variation condition, we have V.( & M. For the partition = to S t = 1, we have (s:) vll (s:) - f(x)]l < (,(f)-lssr 211 < M. Ar =. Thus, for every y E f(K), there
exists an S, E S such that (st) - vll <.
D Proofs and Algorithms for Section
In the algorithms throughout this section, given objective g(t) Gme, write 200) (0,(())s()) v()) such that {(t) E.j.S.v.
D.I Batch Multicalibration
Multicalibration with non-deterministic predictors. Our first algorithm uses no-regret no-regret (NRNR) dynamics to find non-deterministic multicalibrated predictors. We now restate and prove its guarantees from Theorem 4.1
23

---

Algorithm 1 Non-Deterministic Multicalibration Algorithm (Theorem 4.1
1: Input: 8 C 2 E (0, 1), k A, Z,, and distribution D;
2: Initialize Hedge iterate q(2) Uniform(Gme) and Hedge iterate h()) 11/k,...,
3: for t= 1 to I" do
4: Sample objective g(0) (0) and datapoint (x(1),)1)) D;
5: For every a E X, let ( (x) = Hedge(c) Cz (1:t)), where
= (1 + 100 1[h(x)) vl), ix E ES(0) 0zjo);
6: Letg((+1)= == Hedge((Cad (1 where Cadv (t) = - (2))) ,y(0));
7: end for
8: Return: p", a uniform distribution over h(), lT;;;
Theorem 4.1. Fix > 0, X, E Z+, set of groups S C 2², and data distribution D. The below algorithu, with probability 1 6, returns a nonedeteriiiistic k-class predictor that is (S, X)- multicalibrated on D and takes no more than O (s ((n((()) /8) + k kn(())) samples from D.
No-Regret vs No-Regret
Construct the problem (4D), 9wes P) from Fact 2.5 and let T Ce 8 X /8) for some uni- versal constant C. Over T rounds, have an adversary choose ((::T) E (GGme) ) by applying Hedge to the costs {1 64 (h(t) (xx(t) , y)ti)) ((:T) where (x(t), ,ytt) hid D. In parallel, have a learner choose predictors h(..T) E P by applying the no-regret learning algorithm of Theorem 3.7 to to the stochastic costs ((1:)), where g(t) itd. g(t). Return the predictor Uniform(h(::))) This algorithm is written explicitly in Algorithm
Proof. By Theorem 3.7, T 64s-2 ln(k), the predictors (1:1") guarantee the learner
regret bound of Regweak Reg (h(2:21 (C ((:2)) < Ts/4. Similarly, by Lemma 3.1 if T > 576c I (SI), the objective mixtures g (I:T) guarantee the adversary regret bound of Reg (IT) (1 (1((), (zx(1), (((") (() T i2-
We now argue that the adversary's regret with respect to the costs 1- 1-4 E (1 (x((1, ()))) approximates its regret with respect to the costs 1- -. (h )).
Since ((() ((())(()) (o((),(()) = (h(()) by Lemma 3.2 there is universal con- stant such that, if 2 Ce In (81/8).
Reg (1 (0000 (1 (1) (1 ())) 1)) (1:)) Reg (n {1 (l.c)(h
- T 12'
with probability 1 - 5. Similarly, since Extnngt [FD (h(0) = LD (h(0), Lemma guarantees
3.2
Reg (q - (1- (..,3(00))) (1)))))))) - RReg (1- LD. (..)) ST
12
with probability 1 8. Taking a triangle inequality and union bound, we can see that for sufficiently large C, Reg ((::7) {1 C ( < Te/4.
By Lemma 3.3 the ergodic iterate h²' is (E/2)-optimal solution. By Fact 2.5 h² is therefore (S,e, -) predictor. The sample complexity is exactly T since the algorithm only samples one datapoint at each iteration.
Multicalibration with deterministic predictors. We are often specifically interested in finding deterministic multicalibrated predictors. This is usually because non-deterministic predictors can be multicalibrated in very weak sense, we show in the following example.
Example D.1. Consider a data distribution D supported uniformly on X = [2). where
y' [0, 1). Pr(Y = | X x1) = and Pr(Y 1 x2) = 1. The non-determinisic predictor that is supported uniformly on predictors hy and h2, where hı = 0 and hy (322 = 0.5 and h2(11) 0.5 and hz(x2) 1, is technically multicalibrated. However, neither by nor 2 are calibrated.
24

---

Our second algorithm uses no-regret best-response (NRBR) dynamics to find deterministic multicali- brated predictors. We now restate and prove guarantees from Theorem 4.2
Algorithm 2 Deterministic Multicalibration Algorithm (Theorem 4.2)
1: Input: S S 2* E (0, 1). k A, E Z4, distribution D, and agnostic learning oracle .A;
2: Initialize Hedge iterate (1) = [1/k,........... 1/k]*;
3: for 1 to 7 do
4: Let ((() = Ac/88 Cady (4), , (me) where cadv" (f)=== (10==1-Lo.(bb))
5: For every x E 7 let 1(++)) Hodgo (cl.:)),, where
(1 110 1lh(x) o0) 5(0) Tyo);
6: end for
7: Take C'In(T/0)/E" samples x ~ D and let = arg min 1E[T] (a.v)ex
Σ (100)) (z, v)):
8: Return the predictor ((();;
set of groups S C 2*, and a data distribution D. The following algorithm returns a deterministic k-class predictor that is (S,,, A)-multicallirateed on D and makes (1n(k)/e" calls to an agnostic learning oracle. Moreover, with probability - 6, the oracle calls can be implemented with δ (2 (VIn(k)) (n(k))nkk) (S) /6) + 1s In(())) from D.
Theorem 4.2. Fix > 0, X, E L_. set
No- No-Regret vs Best-
Construct the problem (LD), Sme: P) from Fact 2.5 and let T CE-2In((S X* for some uni- versal constant C. Over T rounds, have learner choose predictors ((22)) E P by applying the no-regret learning algorithm of Theorem 1.hhorrmm..71 3.7 the stochastic costs ((1:T), Have adversary choose g(aT) by calling an agnostic learning oracle at each I [T]: g(() = Ae/s(11 - (D.(>)hh()) Using
Cln(T/5)/e" samples from D. return the predictor (t") with the lowest empirical multicalibration
error. This algorithm is written explicitly Algorithm 2
Proof. By Theorem 3.7 T > 256 2 In(k), the predictors (1:7) guarantee the learner a regret {C (1:21) < Te/8. Moreover, by construction, every g(t) is an (s/8) (0(())))))))))))))))))))))) By Lemma 3.4 there must exist timestep where 1,(0) is (c/4)- By Lemma 3.5 the ((*)) found by the algorithm is (e/2) with probability at least 1 - 5. By Fact 2.5 ((()) is (S, mututiicalleratee predictor. The oracle complexity is exactly T, while the sample complexity of oracle A is standard adaptive data analysis result (Lemma A.6
bound of Regweak (h [ITT
best-response to the cost
We note that use of no-regret best-response dynamics recovers multicalibration algorithm similar to the original multicalibration algorithm of [2I] and which can also be found in 77] 25 We also remark that the guarantees of Theorem 4.2 hold in weaker settings. In particular, Theorem 4.2
holds with the same analysis even if we only asked that our agnostic learning oracle AA to be best- responding with respect to a min-max baseline. Furthermore, the last step of Algorithm 2 which explicitly samples datapoints to find timestep t", can be removed if one assumes that our agnostic learning oracle signals to when it cannot find greater than violation of multicalibration the current predictor. This assumption would allow Algorithm to terminate early and return the current predictor, and is assumed by prior multicalibration literature.
D.2 Online Multicalibration
Our next algorithm uses best-response no-regret (BRNR) dynamics for online multicalibration. We
now restate and prove its guarantees from Theorem 4.3
25

---

Algorithm 3 Online Multicalibration Algorithm
1: Input: 8 C 2*x E (0, 1), X, Z4:
2: Initialize Hedge iterate q(2) Uniform(9me):
3: for = 1 to 7 do
4: p =
min p" (00 [0
max 2 (x)
1 +
E li- 1/x E S. E (Ø -
a,
5: Announce predictor pl Nature and observe Nature's 's data distribution D(0;;
6: Sample (of1)) (+)) D( and let ((++1) Hedge(Cadv (1:0) where Cadv ( (8) = 1
((h()) (2 y))));
7: end for
Theorem 4.3. Fix 0, E E., and a set of groups C 2*, The following algorithm guarantees eS, on-onie multicalibration with probability 1 5.
Best-Response vs No-Regret
Construct the online multi multi-objecttie learning problem (D, Smc, P) in Fact 2.6 and let T Ce-2 In(]S) 26) for some universal constant C. Over T rounds, have an adversary lid.
choose (1:I) A(gme) by applying Hedge the costs {1 -e))(1)) ()) where
(x!(), ())) ~ D(O) Have a learner best-respond to each stochastic cost q))) with the (e/2)-
distribution best-response p()) E A(P) of Theorem 3.8 This algorithm is written explicitly in Algorithm
Proof. By Lemma 3.1 if > 576 576 mn(2AA the objective mixtures (1:TT) guarantee the adversary regret bound of Reg (1T):)) ( 4-) (xx(1), (() < T
12. By Lemma 3.2
there is universal constant C such that, if T -c In(AA C (S)/8),
Reg q (:T (1 (0) (2 y (1)) ()) - Reg ( (: - CD0 (p ()))))) s 12"
with probability 1 1-6 5. Thus, Reg (IT) L (-) (h(1)) (1:1)) s Te/4 with probability 1
Since each p (1) is (c/4) distribution-free best-response to (0)) whose existence is proven by
Theorem 3.8 by Lemma 3.6 the predictors ((I:T) are (=/2)-optimal on (I::)) with probability 1 -
By Fact 2.6 pl (1:T) are also (S, s, onnonie multicalibrated on (1:T))
The gigh-probability condition of Theorem can be removed if we assume nature presents data- points rather than data distributions, as is assumed in prior works. Interestingly, Algorithm 3]s use of best-response no-regret dynamics exactly recovers the online multicalibration algorithm of [88] 35). The analysis of Theorem 4.3 is, however, significantly simpler because we make explicit the role of the no-regret dynamics, whereas IX 35 use potential arguments that ultimately prove no-regret dynamics and the multiplicative weights algorithm from scratch.
An online-to-batch reduction. The online multicalibration algorithm of Theorem 4.3 can also be used to obtain a non-deterministic multicalibrated predictor in batch settings through an online-to- batch reduction. This exactly recovers the non-deterministic multicalibration algorithm of [8 35
Theorem D.2 (Analysis of Algorithm 3 for batch multicalibration). Fix e > 0, X Zon, a set of groups S C 2x, and data distribution D. Simulate Algorithm 3 by huving Nature choose D at every timestep and return a uniform distribution p over its outputs p pLld") With probability 1 5. p is
-..utiiaiiittiatbbbaa on D. This algorithm takes (In([S))/0) / samples from D.
max &Gme Σt_ CD. (p()) < Te. Thus, the non-deterministic predictor P given by taking a uniform distribution over p! (1) .....p!) (T))) is (S, miulttiaalilr predictor.
Proof. By Theorem 4.3
Unlike the algorithm of Theorem 4.1 the predictor p output by Theorem D.2 is neither guaranteed to be succinct guaranteed to be of small circuit size. The lack of succinetness is because, even if p's
26

---

predicted label distribution on any feature 2 E X' is succinet, P itself can require an exponentially large support over P. The large circuit size is because, each timestep the learner is best-responding to distribution qft) over objectives & with non-zero weight on every objective. In contrast, in the algorithm of Theorem 4.1 the learner only interacts with single new objective g(t) at each timestep
E
Additional Multicalibration Considerations
In this section, we present additional results multicalibration that all follow from the same game dynamics presented in Section 3
E.1 Conditional Multicalibration
One shortcoming of existing definitions of multicalibration is that they measure violations marginally over the entire distribution D. That is, the amount that a predictor allowed violate calibration on a subgroup is inversely proportional to the probability mass of the subgroup, as reflected by the use of the indicator function Definition 2.1 This can lead to predictors that are certifiably multicalibrated, but still poorly calibrated on underrepresented or minority groups. In contrast, the original definition of multicalibration proposed by (21]. for which no non-trivial guarantee is known, a conditional notion of multicalibration.
Below, we generalize this notion of conditional multicalibration so that setting S' recovers the original multicalibration definition of (2
Definition E.1. Fix E > O, À E E., and two sets of groups S. 2², A k-class predictor P E A(P) (8, 8' A)-onditionillllll multicalibrated for some data distribution D if
E VS E S, E S V v e [k]: (xa))-DAh>p
[(h(z), - 89.)) -1(h(x) E v, E S) x S4)
Se.
is not possible to obtain conditional multicalibration generally, so we will assume sample access to the conditional distributions {Ds }s where D D S'. In practice, this assumption means that we are able to sample data from certain protected groups that may otherwise be underrep- resented. For convenience, in this section, we will assume prior knowledge of (PrD( & s's) but note these probabilities can be cheaply estimated beforehand.
To derive conditional multicalibration algorithms from game dynamics, we first write conditional multicalibration as a misti-distributtonn multi- multi-obeeective learning problem.
Fact E.2. Let D be data distribution for some k-class prediction problem and fix > 0, X Z. and two sets of groups S,S' C 2 Let Gmo be the set of objectives {Li..s.) as defined in Fact 2.5 and let = (D's) sres Predictor p E (PP) a E-optimal solution to the multi objjetvvee learning problem (D, 9me; P) if and only if p is (S,8 S 28, -)-oodittinnlll multicalibrated for D).
Proof. In the multi-objective learning problem ((D')ssrs) .me, P), the multi-objective value of a predictor p, L (p) == ED. LD> (p), exactly the (rescaled and shifted) magnitude of the predictor's multicalibration violation. Formally,
1 1 1
(w)
max 2 jE(K],SES.S es' "s',""",,"" WEV
E (s.g)>-Ds.hh-p
[(((r); - 8y.5) 1[h(z) E v,æ E S.
The optimal multi-objective value of the problem (D, Gme, P) is 0.5, as Gmo are symmetric around 0.5 and the Bayes classifier still achieves a loss of 0.5.
1 1,1
min ("(h") = + max i.
max JElk),SES VEVY vk
E (n.viDD hop
[h(x), - Sy.z) 1[h(x) E v, E S]] =
kP
2 (=(11)
2
Thus, (p) mingrer (*(ht) = if and only if our conditional multicalibration violation 2z.
27

---

Conditional multicalibration algorithms. The following Theorem E.3 is, to the best of our knowledge, the first non-trivial guarantee for conditional multicalibration.
Theorem E.3. Fix ε > O, X, E 2+, two sets of groups S,S' S 2* and data distribution D. The following algorithm returns a deterministic k-claas predictor that is (S,S',E, -A)nndiiiiil multi- calibrated on D and makes (In(k)/E²)) calls an agnostic learning oracle. Moreover, with proba-
bility 1 8, the oracle calls can be implemented with Ô samples from each conditional distribution (D'))
( (Vin(k) In(k) |8|(8))))) ([](8'166) /6) 10)++++1 + kn(())))
No-Regret vs Best-Response
Construct the problem (D, Ime P) from Fact E.2 ler T Ce C In(k) for some universal
constant C. Over T rounds, have a learner choose predictors h(TT) by applying the no-regret
learning algorithm of Theorem C.6 to the stochastic costs ((1:1) and distributions {D gites }(1-1)
Have an adversary choose (*(1T)) and ((:TT) by calling an agnostic learning oracle at each t E [T]
St()) g(t) = Aejs(1- - ()
Using C CIn(TT (80/)/()//))1) /0)/E² samples from each distribution
in ( return the predictor 1e00)) with the lowest empirical multicalibration error. This algorithm written explicitly in Algorithm 4
Proof. In order to apply Theorem C.6 first observe that every objective in 9mc is sep- arable and every distribution D's is absolutely continuous with respect to D. By definition, for any S E S' the Radon-Nikodym derivative of D's with respect to D at x X is [/ / (r E S¹). Thus, the sequence h(1:T) corresponds to running the no-regret al- gorithm of Theorem C.6 when A is chosen to be Prod. By Lemma ing the Prod algorithm as A satisfies the conditions of Theorem C.6 with R(T)) E O( (()In())T)
A.4, we know that choos-
Theorem C.6 therefore guarantees that Regg- Regg-(h(::)) {EDggre Betn,, ece (.)) I Olv In(k)T), where B Is as defined in
(8) Since we can lower bound the baseline B 2 0.5 by plugging
the Bayes classifier ht (I) (( [y x]] into (8) Regweak (1:T), { grtt eto ()) (.)
Regg- (1(0))))) {CD (e0) E00 ()) S ((v|8'I
Thus, if T N
Regweak (h(T))) , grce) pwv (to (.)()))) Te/8.
By construction, every pair (*(0) g0t) is an (e/8) best-response to the cost function 1 1 L. (h(0)) By Lemma 3.4 since the learner has at most Te/8 weak regret and the adversary is e/8 best- responding, there must exist timestep t [I'] where (t) is (e/4)ooptiml. By Lemma 3.5 the h((") found by the algorithm is (z/2)-optimal with probability least 1 8. By Fact E.2
A [ is
(S, e, >) conditionally multicalibrated predictor. The oracle complexity is exactly while the sample complexity of oracle A is standard adaptive data analysis result (Lemma A.6
We can also implement faster non-deterministic conditional multicalibration algorithms.
Theorem E.4. Fix E 0, X, ks Z4, sets of groups S' 2* and data distribution D. The following algorithm returns a non-deterministicc k-class predictor that is (S,S', coondiition multicalibrated on and takes O (IS') (In((5))8))/5) + kl(()))/e2) samples in total from the distributions in {D's) s'Es.
No-Regret vs No-Regret
Construct the problem (D, 9m,, P) from Fact E.2 and let T CE-2 (S'] In( S| for some universal constant C. Over T rounds, have a learner choose predictors (1:T) E P by applying the no-regret learning algorithm of Theorem C.6 to the stochastic costy ((1:T) and distributions (D (1:T), In parallel, have an adversary choose Sr(1:T), g(1:T) by applying ELP to costs
{1 (1-Lp, L.),, (1(0)) Return the predictor = Uniform(h!1:T) This algorithm is written
explicitly in Algorithm
Proof. As we proved in Theorem E.3
Theorem C.6
guarantees that if T' > C In(k)//², the .eco
learner's 's regret is bounded by Regweak (((r)) {Cp groo ero (.) (1:11) < Ts/4. We now turn to the
adversary.
28

---

We will define a sequence of costs Cadv (1:7) that mirrors the adversary's costs {1- (
For all timesteps t E [T], rename (x (rigtes (g)))) = (x(1), (()) (
(f) ( itd Ds as the data- while for all other S' S' define the random samples (
point that the adversary would have hypothetically sampled if it had chosen to sample from D's instead of Dyno at timestep L. We now can define Cadv (S'", (1,,,, S,))) = (0.5 0.5
(x)g))))) Note that, since the ELP algorithm only observes values of Cadv (0) ((i, J., S. v)) where S' = S*()
1[h(=s)) E U, U, (t) E S]
(ō
V
Reg( ((Sr(t), (()))(: Cadv (1:))
= Reg([(S'(), ) (1:7), Cady ).
By Lemma
A.5 the adversary satisfies Reg(( {(:)) Cadv (:)) & O(v S (k
Thus, we also have that Reg(((('(() {()))(117) Cady (1:T) S 50
(nk//)TT) ( By Lemma 3.2
there is universal constant C such that, if T 2 Ca In(2h S (8)).
In
[Reg([(S*)) ((:)) Cadv (1:)) Reg(( (1850)
{1 (1:),
())) (h()))))(()))))))))))))))) (1))))(()))) S Te/12,
with probability - 8. Taking triangle inequality and union bound, we can see that for sufficiently large C, ReggRegese ((50)))))))) (())) {1 LD ())))))))))))))))))))))))) Te/4
By Lemma 3.3 the ergodic iterate h" is an (e/2) -pptimll solution. By Fact E.2 he is a (S,S', e,, X)- conditionally multicalibrated predictor. The sample complexity is exactly since the algorithm only samples one datapoint at each iteration.
Stronger multicalibration guarantees for (almost) free. We can also drop the assumption of access to the conditional distributions (Ds s'es and ask for weaker guarantee than conditional multicalibration where a subgroup's error tolerance scales with /Pr(æ E S'). For simplicity, we will fix S' = S here. Note that unlike Theorem E.3 Theorem 4.4eeem/444cc does not assume knowledge of the vector [Prn E S)]sEs.
Theorem 4.4. Fix E > 0, A,K two sets of groups S C 2 and a data distribution D. There is an algorithm that, with probability at least 1- takes ((In())-(nn((())))))))) ( +ln()))/s()) samples from D and returns a deterministic k-class predictor h satisfying
E (a.))~D,hvpp
1(h(z); 895) 1(1(x)) E U., S]] SeVPr(rES)
for all S E S,S V E
The sample complexity of Theorem should be improvable to a sample complexity of Ö((v/n In([S] /5) + & (= using adaptive data analysis [30 [.. Even without using adaptive data analysis, Theorem E.3 guarantees sample complexity that only 1/e factor greater (less than cube-root increase) than the best known sample complexity for deterministic multical- ibration. In fact, matches the best sample complexity for deterministic multicalibration that is known to be possible without adaptive data analysis. This means that we can attain this strictly stronger multicalibration guarantee for free (compared to its non-adaptive data analysis counterpart) or with only minor cube-root increase in sample complexity (compared to its adaptive data analysis counterpart). We defer a complete proof and algorithm statement to Section
E,2 Agnostic Multicalibration
An implicit assumption of multicalibration is that one has unlimited freedom to vary their predictions based on which subgroups a datapoint belongs to. This assumption arises because we assume that groups are defined as subsets of the domain, 5 C X, and predictors are allowed to condition arbitrarily on the domain. This impractical in many settings including, for example, when subgroups correspond to protected demographics. This is an important concern for faimess applications of multicalibration.
One can extend multicalibration to more general agnostic setting by assuming that group member- ship is passed the predictor separately from the covariate. Note that, in this definition, different groups may not share Bayes classifier and fully multicalibrated predictor may not exist.
Definition E.S. Consider a data distribution supported on X x X' x y and where the set P of k k-class predictors that are functions of the visible covariates X but not the protected covariates X'.
29

---

Fix > 0, À E Z+, and a set of groups S 2 A (possibly non con-dtterministic] k-class predictor p (PP) (S, E, A)--noosttt multicalibrated with respect to a baseline B if
AA S, V
(a. (1(+);
E - 82.5) 1(h(x) o S]] S B.
In the probability that covariate z belongs certain group; this necessary to attain sample complexity rates independent of domain size X. We will similarly allow agnostic multicalibration to take for granted knowledge of the group memberships of each covariate x E X'.
original definition of multicalibration, it is implicitly assumed that one knows, a priori, the
Choosing a baseline. One challenge with defining agnostic multicalibration is choosing a proper baseline B. An immediate option choose a min-max baseline:
Bweak min max EH J.a.S
E (=,= (x)) vソ)) 1[h"xx) E x' E S]]
However, achieving this baseline is intractable. with a sample and oracle complexity that depends- potentially linearly-on domain size. Moreover, the predictor attaining the min-max baseline is odd and undesirable: when two groups disagree on the label for a set of covariates, the predictor hedges its losses by spreading its predictions for those covariates into as many bins as possible.
2_ and uniformly sample random half of X as X S X where [2| = /12 Let X' [1,2], X 3 and 2, and define the marginal distributions Pr x' = 1) and Pr x' = 2) to be uniform on X. For x & X. let labels be random: Pr = 2 = 1, (r = 1 x' 2, 0.5. For x E X, let labels be deterministic: Prp(y 1 1,x) = 0 and PEp
Proposition E.6. Define X [m]] for some large
x 2, x) Finding a predictor that is e,,e, -aggnoosi multicalibrated with respect to the min-max baseline requires at least ([x))) samples must be taken from D for 0.1.
Proof. The min-max optimal multicalibated predictor divides X into 4 equal parts: Ei..... X4. It predicts h(()) = 0.5 for all x & X, x E Xi and x E &2. It predicts h(x)) = 1/3 for all x E Xz. predicts h(x) 2/3 for all E X4. This attains multicalibration violation of 1/6. Thus, achieving an e-optimal predictor requires determining the membership (in X') of at least 3/4 fraction of X.
To provide more satisfactory definition of agnostic multicalibration, we ask that one's predictor assigns the same label probabilities to datapoints with the same group memberships and relaxes the baseline so that hedging not necessary.
Definition E.7. We say that k-predictor h is agnostic multicalibrated if the predictor h provides the same prediction probabilities h(æ1) = h(x2) to datapoints I1. T2 E X that share the same group membership distributions VS S Pr(z' E S x z1) Pr(x' E S x = 22); and (2) is (S,e, a.ggnssticcc multicalibrated with respect to the multi-accuracy baseline:
Bmutti-ace
min max E" je JESSS
- 5y.) (x))
1/s E ES]]
(10)
This baseline is zero when the groups share Bayes classifier, recovering Definition 2. With a slight
tweak to Fact 2.5 problem.
2.5 we can write agnostic multicalibration as the following multi-objective learning
Fact E.8. Let D be data distribution for some k-class prediction problem and fix > 0, À E Σ,, and a set of groups S 2 For every protected feature x' E EX')x, direction E {+1}, level set E Vž. group S E S, and class j E [k], we define an objective Ex (s.S,, P x (X' x )) + [0, 1] where
Ex..J.Ss. (h, h,, (x, = 0.5 + 0.5 i 1[h(z) U E ST (h(z), - 8y.3),
(11)
and 9ng = (bx.,yss, bx..s.ss..w.s..... the set of these objectives. We also define objectives without subscript x', where l. (h, (z, .))) = 0.5 + 0.5 i. 1[h(z) E o, e S| (h(z); 8y.)) and
30

---

Gog = =fli,,,,h33s.. For every objective & E Pag let qe E A(9ug) denote the objective mixture where Eg~D, [((-)] L= [E(-)) If predictor E A(P) is s-optimal solution to the multi-objective learning problem ((D) Pug. P) with respect to the multi-accuracy baseline, then p (S, 22, agagostie multicalibrated for D with respect the multi-accuracy baseline.
A simple modification to our batch multicalibration algorithm suffices to achieve agnostic multicali- bration.
Theorem E.9. Fix & > O, A. & Z4,, a set of groups S C 2 and a data distribution D. The following algorithm returns deterministic k--laass predictor that is (,,e, X)-agnostic mul- ticalibrated on with respect to the multi-accuracy baseline. It makes ((I(()/e²) calls to an agnostic learning oracle and, with probability 1 6, these oracle calls can be implemented with (V][k) In (8| /6) + k In())) samples from D.
No-Regret Best-Response
Construct the problem (1D), Gug: from Fact 2.5 and let T C2-22ennn X some universal constant C. Over T rounds, have adversary choose ((1:T) I'g by calling an agnostic learning oracle at each t E [T]: g(t) = Aess(1 (n.t)((h))) 9'ag). Have a learner choose predictors (1:T)) E P by applying the no-regret learning algorithm of Theorem Co6 the stochastic costs {gee> } (1:7) (9gag). Using C C'In(T/ ( /5)/E² samples from D. return the predictor h(t") with the lowest empirical multicalibration error. This algorithm is written explicitly Algorithm
256 In(k), the predictors h(::T) satisfy Regg- (egg--(((1))) (ITT),, {gro) } (1:T)) < TE/8. Note that. since predictors h(:TT) can only observe and not x', we applied the algorithm of Theorem C.6 to (mixtures of) objectives from Gug that depend only on (Ir, v). Since Ex-D,fa 5.0. (200) [o [x,,),s
Proof. By Theorem C.6 if T
2
Er' [c)] however, still bound regret with respect to the loss functions in P'g. which do depend x', by Regn- (I(1:)) ((:77) = Reg Re (h(1:7), {qrus} } (1:T)) S Te/8; we define both these regrets with respect to the set of all predictors from X + y. Also note that the 3 baseline bounded by the multiaccuracy haseline (10):
B
min he EH T
Σ max E NEW (2.9)DD)
(x, (M))) (1"))
min
max
E
(x, (1) gv))
EH* E'Eg MEH (2,0)~D
min max
E ())
[1h w3) 1/2 E S]]
E* J.S
B Buulti-ace
Thus, we have regret Reg aa (h (1:T), ((:-T) < Regg. (1(1.)) g(,TT) < T By construction,
every ((0) is (s/8) best-response the cost (. (h By Lemma 3.4 there must exist
a timestep where (t))) is (e/4)-optimal with respect to Bimuttiace- By Lemma 3.5 the (())) found by the algorithm is (e/2)-optimal with respect to Buultince with probability at least - 8. By Fact E.8 1e(()) is (S, e, A)-agnostic multicalibrated predictor. Lastly, verify that datapoints with identical group membership probabilities must have the same label probabilities as the update rules for their predicted labels identical.
The best existing sample complexity bounds for agnostic multicalibration come from uniform convergence (38], and scale with ()(() = |h'tt is, sample complexity scales with the size of one's domain. In contrast, Theorem E.9 provides sample complexity that still depends only on the complexity of the groups on which one desires multicalibration. This can be an exponential (in (x') reduction in sample complexity.
Similarly to Algorithm we can use the same modification to scale our non-deterministic multicali- bration algorithm (Algorithm I] to agnostic settings.
31

---

Theorem E.10. E O, E Σ+ and a set of groups S S 2². There exists an algoritim guarantees, with probability least the algorithm returns a randomized (S,E, agggnssiii multicalibrated predictor while taking no more than O ((In( (1 + kin(A))/=E) samples from D.
E.3 Moment Multicalibration
Our treatment of multicalibration, and extensions of multicalibration, hold more generally for any problem that can be written as multi- multi-objective learning with objectives that look separable. As an example, we demonstrate that we can use the same approach to devise algorithms for moment multicalibration, which concerns not only learning multicalibrated label predictor but also second predictor that estimates the higher-order moments of the label distribution
[22]. As in online multicalibration, we will work with only binary classification problems in this section, and so will say that predictors output real-valued (z),),, (x) E [0, 1].
Definition E.11. Let D be a data distribution for a binary classification problem and fix E > 0, X, m E Ey,, and set of groups S 2 A pair of predictors p (Pus Pm) where Pps Pmn X - [0, is (S, e, X, memn---o-oonniniooneee moment-multicalibraace
D if. for all S E S, Uns Um E Va.
E D.tpp. (x)(2)) - y) 1.( Upr hm Um, x E ST]
E 2Z
E D.
(()p((z) - 9)th hm (x) E Upy ugy hm E Um, E S]]
We will write h (Ny hm) shorthand, where h(x) = (hy())), (mm())) Moment multicalibration can also be expressed as a multi-objective learning problem.
Fact E.12. Consider the set of all pairs of predictors H ((hp::mm) : hus Bm : X - (0, 1]}-
Fix E > 0 and X, m E Zt. and a set of groups E 2 Define the objectives Gthc = (epri... sE(S))))S(())) and I = (Emn)SS))(())),SSseee where
(m, (I, 4)) = 0.5 0.5- 1(Mx) E v, E E) (Am(a) - (y - (z)))
(, (x, 4)) 0.5 0.5 i- 1[h(z)= E u, E S]. (1p(2)) - y).
A pair of predictors is E-optimal solution to the single-distribuics
learning problem ({D), Ime U P)) if and only if the pair is also (S, 22, m)) mean-couee conditiiond moment multicalibrated.
Thus, we can follow the same steps as before to derive a moment multicalibration algorithm. The algorithm derive for Theorem F.13 recovers the sample complexity of [22) for moment multicali- bration. Moreover, the algorithm is parallelized in that it learns the mean and moment estimators hys hm simultaneously, in contrast with [22] 's algorithm which uses nested optimization.
Theorem E.13. Fix e > O, X, r E Z4, a set of groups S C 2x, and data distribution D. The following algorithm returns a pair of predictors that are "S,,,,,m)-maan --man-conditionel moment multicalibrated on D and makes O(1/=²) calls to an agnostic learning oracle. Moreover, with probability - 6, the oracle calls can be implemented with (m]n((S) x/8)/e²) samples from D.
No-Regret Best-Response
Construct the problem (1D), 9 UG P) from Fact E. and let T C=- In([S) X+ for some
universal constant C. Over T rounds, have a learner choose predictors hm (1:T" E P by applying
the no-regret learning algorithu of Theorem C.6 to the stochastic costs e (1:T), instantiating A
be Hedge with learning T-3/1. In parallel, have learner choose predictors (Q E E by applying the no-regret learning algorithm of Theorem C.6 the stochastic costs (1:T) instantiating
A be the strongly adaptive Hedge algorithm (Lemma A.3). Have an adversary choose (l)) el
by calling an agnostic learning oracle at each E [T] (1l A./s(1 - (1) 9m) and
'This definition aligns with the definition of "pscudo- ipseudo-moment moment multicalibration" proposed by (22). We
adopt this particular definition previous studies [22] [8] develop their algorithms and analyses based on this detinition of moment multicalibration, with translations other definitions occurring only retrospectively.
32

---

( = Ae/s(1 - (1(0),,, mm Using Cln(T/0)/E² samples from D, return the predictor h(())
with the lowest empirical multicalibration error. This algoritim written explicitly in Algorithm
First, we prove an intermediate result.
Lemma E.14, In the Algorithm condition Regweak (1 (1::),, {fm (1) + e (1) ja::)) E E (Vm13//)
7 the sequence of hypotheses ((1:)) satisfies the bounded regret
Proof. For simplicity, we'll round T to the next largest square. Recall that using Hedge to select
T actions from the interval [0, 1] with learning rate mm guarantees regret bound of
2 lln(2) (Lemma A. By Theorem C.6 since chose A to be Hedge with learning rate
T-3/4 when learning 1 Σ (h:0) s 0.57 (l2 Similarly, by Theorem C.6
having chosen A to be strongly adaptive Hedge when learning (1) we have for any T1 [T] and h E Hm,
T+VT Σ
(co0 - 0.5 I=
(1 ( - (())))) = 0 (TT)) (x.a)
In the above equation,
((t) fm and gl the separable components of the loss en de- fined in Definition C.5 We now turn to bound the expectation term. By triangle inequality,
(l (x, h(0) (x)) (x) gm (y)) s f (z, (z)) (x) gi (2)) + gm (TT) (y) (1))))))) gm (v)
Using the inequality that (aTh 6dd S m
when a, E [0, 1]. and the movement upper bound (Ti) (v) ( m (x) hp (Ti) (x) mn, vT. where
of Hedge (Lemma A.2 we have gm
Ua 1121/21-01 is the learning rate of the mean predictor hy. Thus, for all Ti, by choosing (Ti) hm (I) gm (y) we have that
TI+TT
(C,s) (C (1 - 0.5)
TitVT
Σ
f0ll ( (2) (1)) + mTn, + (0T//4m(())
< min
E
he Hm
(2.0)D
Tj
S 3mm +0
0 (I3/4)
This gives Et (h(0)) + (h(00) 1 50 ((I(T)) + Vm)T3/1) desired.
We now return to proving Theorem E.13
Proof of Theorem E.13 By Lemma E.14 the learner's 's regret is Reg (H(T:T) + p(()(()))) e
+
O (m /223344 When Cm² /et we thus have Regweak (1:T)) (max e(t) det }] (1:T)) Te/8.
By construction, every max (( ((t) is (e/8) best-response to the cost
1 (t) By
Lemma 3.4 there must exist a timestep where (9) is (e/4)-optini) By Lemma 3.5 the predictors
Ie(e)) found by the algorithm are (s/2)-optimal with probability least By Fact E. 12 h (())
(S,s, s, A, mmmmmmmmmaammone monn-cooniiin moment multicalibrated predictor.
33

---

Algorithm 4 Conditional Multicalibration Algorithm (Theorem E.3
1: Input: S' C 2 e (0,1); A, A,T,,,C E 2,, distributions (D's) sies and agnostic learning
oracle A:
2: Initialize Prod iterate h()) [L/
3: for t = 1 to T do
4: Let S*(t), g(() Ae/s(Cadi (1) , x Imc) where Cady (5', =1 gr
5: Let 1((+))())))))))))))))
(x) (rod(ctt where
1/r E ST(()
10 (0) = 2 Pr 5010) (1 + 1[((a)) 00)), a (t0 ,000 Tz());;
6: end for
7: Take C'I(TT/)//²
samples x(5")
Dg for all S E 8' and let
t" ara min
Σ
(19()) (I, y));
8: Return the predictenx/ddlil
Algorithm 5 Non-Deterministic Conditional Multicalibration Algorithm (Theorem E.4
1: Input: S,S' C 2 E (0, 1), k; A,T E 2,, and distributions {
2: Initialize Prod iterate (11) = [1/k,... ................................ 1/k]* and ELP iterate (50)) ~ Uniform(S' x
9mc));
3: for t= 1 to T do
4: Let (((+1)())))))))))))))))))))) (x) = (rodd(ef::t) where
1/r E S'(O)
(1) PPrp( E ST00) (1 + [[((x) (0)) x ((0) ,0(0) T0o));
5: Sample (x,1), yy()) ~ Dsccoo and let (1((1), = -EIP(ca (1:0) with
Cadv (S', (..s,)) == 1
= S'() (1 ((((a(t) 20 E ESS. (6 h(x(1)))))
6: end for
7: Return h", a uniform distribution over (1)) "(0,...,,''" N1();;
Algorithm Agnostic Deterministic Multicalibration Algorithm (Theorem E.9
E (0, 1). k A, E E., agnostic learning oracle A, and distribution D; 2: Initialize Hedge iterate (1) = 11/k,..., 1/k]*
1: Input: S C 2*
3: for 1 to T do
4: Let Li.j.S = g(t)= = As/8(Cuuv (1), (1) Gyg) where Caty (1) = LD.e(h())::
5: Let (((11)())) (x) = Hedge( ct (1:t)) with
11 ( 2 (1 +
Σ
Pr(a' (x) 1[h(x) E o()) x' E ss(0) Djo
x'Ex"
6: end for
7: Take Cl samples x from D, and let t" arg min
Σ g10(1))) (x, (2))),
8: Return the predictor h((");
tE(T]
34

---

Algorithm 7 Moment Multicalibration Algorithm (Theorem E.13
1: Input: 8 2 (0, 1), k. A, T, Z,,, agnostic learning oracle A, and distribution D;
2: Initialize Hedge iterate 1 = 0.5 and Hedge iterate hp (1) = 0.5*;
3: for lo= to T do
4: Let Cn = A./8( (9, _mm) and p(t) = As/s(Cadr (0) g where Cadv (c) = 1
(D.e(h());
5: For x E X, let (1+1)) (x) = Hedge( and hp ((+1) (x) == Hedge (,,z where
1
m. マ (1
(t) 10 a a SW),, e0 (1) 2 (1 + (()) 11 E wlt E 1
6: end for
7: Take C' in(T/8)/=² samples x from D and let arg min Σ (h (2) + (h!0), (119)(,,,)) (x,
8: Return the predictors him .hj (e")
tE[T] (2,y)
E.4 Square-root Multicalibration Guarantees
The following Theorem E.15 is stronger restatement of Theorem 4.4
Theorem E.15. Fix = > 0, X, E Σ+ and sets of groups S C 2 Ser T = C'In(k)/² for some universal constant C. Algorithm
8 with probability at least 8, requires no more than (ln(k)- (In(k /58) knn(A))/E*t) samples from D find a deterministic k-class predictor satisfying
(2.0)~D [(((z); 5..)) 1[h(x) E ST SEvPr(E ES),
E
for all S S VL, [k]. That is, h is deterministic predictor that is (8, /Pr(x E A)- multicalibrated, where the error tolerance /Pr(æ E S) depends on the group mass.
Before proceeding to a proof, first introduce some technical results which are simple variants of lemmas that the reader has seen previously in the manuscript. Note that, in the following multi- objective learning problem construction, we will allow negative objective values for simpler notation.
Fact E.16. Let D be data distribution for some k-class prediction problem and fax > 0, A E Z,, and a set of groups S C 2 We define the following set of multicalibration losses:
Gme { (r
1
{ e S)
i- (h(x); - -8y)) EU.
(12)
Predictor p E A(P) is c-optimal solution the multi-objectivg learning problem ((D), Gue, P) and only if is (S,e e //rr(P E ES), mimltiiccall for D.
Proof. In the multi-objective learning problem ((D), Ime: P), the multi-objective value of predic- tor p. (p) = max;,,.s.e. J. Eg LDD.,g,,. (p), is exactly the magnitude of the predictor's multicalibra- tion violation. Formally,
((gg) [(h(2); - )nJ) 1[h(x) E v, e S]] PPro(x E)
(x)
max SEM,,SESS.Ev
The optimal value is 0, as the objectives are symmetric around 0 and the Bayes clasifier achieves a loss of 0. Thus, L (p) mink- (*hh)) 2 if and only if our multicalibration violation is at least e /Prf E S).
Lemma E.17. Let D be a data distribution for some k-class prediction problem, E E (0, (0,0.)). (0, 1) and fix set of groups S C x where, for all S E S, Pro(x S) 2 2. With only
Here, the tilde-O hides log- log factors.
35

---

((n((//0)/E)) samples, one can find with probability at least 1 - ô a vector u E R| where, for all S S.
Us Pr(x E 5)
S < SxPr(x
(13)
1
$
(14)
VUg
PrD((EES)
VPrn(r E S)
V0g
v Pr(x E S)
S Pr(x E S).
(15)
Proof. Fix some sufficiently large universal constant C. Sample N = ClI(S/8)/e4 datapoints X from D, and let ui [X [(x))ex 1/z E S]. Observe that E [u] [rD(( E S)]ses. The multiplicative Chernoff bound says that, fixing an S,
Pr(lus Pr(# S) 2 Pr(# S)) = 2 2xxp(=e2 E 5)/3)
S <2cxp(-<\N/3)
With our choice of N, taking a union bound over all E S, with probability at least 1 - have our first claim. Taking square-root of both sides, also have that for all S E S, S) vug I /(1+ (ID+)) PrD S). The second claim then follows by ob- serving that, for any (0,0.6, 1 VIzz E, and VI-E 1 - c. The third claim follows by observing that, for any (0,1), vI+E- S and 1 vI-
e(1-))
The following lemma is modification of Theorem C.6 that states that the learner has a no-regret strategy on the calibration objectives given in Fact E.16
Lemma E.18. Consider the set of k-class predictors P, a data distribution D, and any adversarial sequence of stochastic costs g(1:T) E Ime where Sie are the multicalibration objectives defined in Lemma 1. Suppose you are given V E satisfying (14) and (13) for all S S and that, for all S S. Pro(# E S) 2 e?. There is a no-regret algorithm that outputs (deterministic) predictors h(TT) p' such that Regweot (h(iiT, (fD (1:T) s ((vin(k)T + ET). Moreover, the algorithm does not need any samples from D.
Proof. Consider the following algorithm. At each feature X, initialize a Prod algorithm that picks action (x) A()) at each timestep t E [T]. Aggregating each algorithm's is action yields our learner's s overall action (t) E P. For each x E X. let (x) be the outcome of Prod at step
t + after observing linear loss functions f/7,, R - [0, 1] for E [d]:
1/7 (x))) (z) 2
(1 (1+280)) j(t) (1 (x) E ol) E s(r1)
(16)
Prod gives Σm. 1
A00 (1(0 ma Σ fho an (x*) s cV/I((B) D 1 sco
(Lemma A.4) for some universal constant C. Since this inequality holds for all x E X, apply- ing the law of total expectation Lemma A.4
T ln(k)
CPr(2),
(()
*EX
T
T Σ
Pr(2))((
hey (h
Σ min
Pr(
zex EA(())) D
xEX t=
tm1
Σ
Σ
Pr(x) (1( 1 (z))
min KP
ΣΣ
Pr(x) 10 (h²
ZEN
T Σ
Pr(
max AIEP
100
TEN t=l
36

---

with the equality following because we allow arbitrary predictors. Expanding the definition of f.
max EP
Σ
Pr Pr(x)
f
(() NO, v
(x)
- 1x))))
D
ZE
1=1
T
max
Pr(æ)
(x(00())-~((1) 10) (x)
000 e sSto))
ht EP
D
2 2//0
ZEX
(z)
18 I x]) 10 (x) E 000 1 E s(oi)
E
E
2 2000
yr sce)
T
Prn S(O)
Uga
By definition of v,
Prn(x E SW))
CD (h!0)
Σ vI - EL- (h())
Σ D,e (h(*)) -Te.
Ug(t)
We also know by construction of the losses in Mno that the weak baseline Bweak 0. We can therefore bound
Rogweak (I:T,, a ((.T)) TT+ Σ
CCp(())
ln(k)
Ug(e)
#EX
T Σ CPr(x)
ln(k) Σ (1+E)
Pro(# E S(1)
ZEX
1
Te C CVTTi()(L+
Pr(x)
Pr (z). D s(t)
D
T
To bound the last inequality, let a E R v E R be vectors defined as ug PrD(2)) and
Ux. VE PRD stes (x). Then, by Sauchy-Schwarz inequality, we have that u S || other words.
||1||22 In
T Pr (z) Dett)
T Σ
CVTTnn(K) Σ NEN
Pr(x)
CC/TTI)
Σpr(a) Pr(x))
Σ FEX
T
Pr
(a)
D
Dg(o)
<T/nk)))).
The following lemma states that the adversary can efficiently best-respond to the objectives from Fact E6
Lemma E.19. Consider a k-class predictor E P. a data distribution D, and set of multicalibration objectives G' Suppose you are given R satisfying (15) for all S S. There is an algorithm that, taking only e ( /6) + In(A)) samples for some universal constant C. returns a Lij,5.v E S'm such that, with probability least 1 5, LD...,. (h) 2s maxi "","", a (h).
Proof. Consider the following algorithm. Draw N = C' Ca- (In([S]] ( /8) + Im())) samples (z, v) (1:N) from D. For all S E S, initialize the empty buffer Xs = U.. Then, for every value of r = I,...,N and for every group E S, (r) E S, append (z, () to Xs. Let
uy 1 lij.S.v maxi,j.9,0 V Pro(eEs) [Xsl Elayexxs (aj.s, (x, v)) be the multicalibration objective
37

---

that minimizes the empirical risk on its respective buffer Xs. Note that finding f...S.vv does not require knowledge of Pr S), the explicit factor of / 1/Prr(( S) is cancelled out by S..,SSe.
We first observe that Xs| is binomial random variable with parameters N and Pr(x E S). By Chernoff's s bound, with probability 1 - 8 ||| |xs Pr(x S) 2 /6) + I)n(()) for some universal constant C", where we choose C' to be large enough so that C" 2 By union bound, with probability - 6, for every S E S, Xs| 2 Pr(z E S2N/2.
Condition on this event and fix ki.sS,e E Mmme We observe that each (z, Xs is an unbiased sample from Ds, we have least Pr(xr S)N samples, and (ij.S,v E (1/ Pr(æ E S)}. Thus, by Chernoff's bound, with probability at least 1 8 [mmmel"
|xsl_
Σ
vPr(z Sya,,, (x, (2.8)) vPr(s S)DDshsss
(x.y)eXs
S <=/(3/Pr(x& E S)).
Thus with probability at least for all l,,,S3v E Ime
[xsl
Σ
Pr(x E Sy (x, Pr(x S)
(
[xsl
Σ
Pr(x 8)4sss (2, CD.L,s..
(aa))Xs
S..
Taking union bound over all l E I'e by uniform convergence, with probability at least 26, our returned (.,,S.v is an best-response to the cost function Lij,S, V Pro(nes) CD.....s.. (l))))
By (15) maxi, LD.. (h(0) - LD..SS, (h(*)) S E. Thus, Lij.9,0 is an 2E best- response to the cost function (,j,s, + -... (h!!))
Proof of Theorem E.15 First, we will assume without loss of generality that, for every group S E S, Prn( E S) > $//32. This is because for such S, our multicalibration constraint is trivially satisfied for tolerances of at least e e/232. We can remove such S from our group S by testing Pr E S) < /3;; O In((S)/8)) samples suffices.
Next, will sample according to Lemma E.17 which also takes most O (I((()/6))) samples. Lemma E.18 then guarantees that, since T 2 C (k))///e? Regweak (M(1:), ( (1:)) s
Te/8. By Lemma E.19 g(() is an (s/8) best-response to the cost function -LD.() (1( with probability at least T/T at each timestep f. By Lemma since the learner has at most Te/8 weak regret and the adversary is E/8 best-responding, there timestep & E [T] where h90 is (e/4)-optimal for the problem ({D), "'me: P). By Lemma 3.5 the (())) found by the algorithm is (E/2)-optimal with probability at least 1 - 8. By Fact E.16 this is an (S, muutiiicallbbraee predictor.
F Other Fairness Notions
This general framework of approaching multi-objective learning problems with game dynamics can be extended beyond multicalibration. In this section, we use multi-objective learning derive new guarantees for multi-disttibution learning and multi-group learning.
38

---

Algorithm 8 Conditional Multicalibration Algorithm (Theorem E.15)
1: Input: 8 C 2*x E (0, A,,, Zu4, and distribution D;
2: Initialize Prod iterate h(1) [1/k,.... ..,,,,.......................... ,1///
3: Sample C'In(S/0)/s datapoints X from D and, for each S E S, remove S from 8 C 1 S] - /3/32:
4: Sample (lI((/8) datapoints X from D, and let us [XT Caaiee 1[x S] for all 8 E 8;
5: for / 1 to 7 do
6: Draw = Ce (In T/6) + (n())) samples (x. (z.y); ()=) from D;
7: For all S, let X1, (z, u); i [N], ES}:
8:
Let Cadv (S,E) == VUs (e,s) (x.,)exx,ss ((h(t) (x,
9:
Let ((t) = arg max Cadv" (S,));
10: Cady (St0, ((0) S 8/8 terminate and return h(:;
11: Let (x()))))) (x) = -Prod(c. :0) where
(1) 1 = 1[x E StO)
(1+ 1[((x)) E v x E ((0) 1000).0000.. (y)))
2 ug
12:
end for
13: Return p", uniform distribution over (()) ...., A(T),
Competing in multi-distribution learning. Usually, in agnostic multi-objective learning problems, the trade-off between objectives is arbitrated by the worst-off objectives maxD= LD --p-eeli (-)- However, this approach negotiating trade-offss may be suboptimal when objectives inherently more difficult. In those cases, we can take into account the difficulty of individual objectives by asking for predictor where there objective for which competitor H* performs significantly better.
Definition F.1. For a multi-objective learning problem (D, H., solution that e-competitive with respect to a class H'' is a hypothesis A(H) satisfying,
Cx (p) min Liv (h*) S where (h)(() = max max (ax,LD,e()) min (D,(hh). DED EEG
Only simple modification needed to provide e-competitive guarantees: amplify your original objectives G into objective set g' := {1 E(-) l(h')) é G, H²} and solve as usual. The following fact, which holds by definition, formalizes this reduction.
Fact F.2. Consider multi-objective learning problem (D, G, H). For some choice of H', let g' = (0.5 + 0.5(E(.) - ([h)) G, E H'). Any solution p that is s-optimal for the multi- objective learning problem (D, H), is also 2e-competitive (Definition F.I w.r.. H' for the original problem (D.9.H..
19 showed that the sample complexity of finding e-optimal solution to multi-objective learning problem (D, 9, H) O( ((n(((?))) + [D] In( (D) ( /8))). Thus, Fact F22 immediately implies
Theorem 5.1 sample complexity bound for finding s-competitive solution.
39

---

Algorithm 9 Multi-Group Learning Algorithm (Theorem 5.3
1: Input: 8 C 2 E E (0, 8: x x [0, 1), hypothesis class H : X - V/ and distribution D;
2: Initialize Hedge iterate q(2) Uniform(S x H) and p(a) Uniform(H!):
3: for t= 1 to T do
4: Sample (2ig ) D and (ap Upp D;
5: Let ((++1) = Hedge(cy (1:t)) and p((+1) = Hedge(Cp (1:0) where
(S,
[x/ ()(t (. E(N, (2,) " (()
2 h'mp(())
(h) _
1
[Lat0) S)(e(h, "/ e(h', (x (a)),())))) x/>m))=
E
s. (((t))
6: end for 7: Return: p", a uniform distribution over p p(T)
Multi-group learning. Consider the multi-group learning problem (Definition (5.2) than seeking simultaneously calibrated estimates of different subsets of the domain as in multicalibra- tion, we seek to simultaneously minimize general loss function on different subsets of the domain 37
where, rather
(near) optimal sample complexity for multi multi-group group learning of O (In([S) [+))/=²) was attained by
[39] using reduction to sleeping experts. [39] also asked whether there exists a simpler optimal algorithm that does not rely on sleeping experts. We answer this affirmatively by designing an optimal algorithm that just runs two Hedge algorithms.
We can equate the multi-group learning problem (Definition 5.2 to finding an e-competitive solution in single- distribbbtoioonn multi-objective learning problem.
Fact F.3. Fix 0, set of groups S C 2 a hypothesis class H. data distribution D, and loss : H x (X x y) - 1]. We define (h, (æ, U)) = E(h, (x.y)) 1[x E S). If a hypothesis p E (HH) e-competitive with respect the class H. for the single-distribution multi-ojjective learning problem ({D), [ts) H), then p is also an s-optimal solution to the multi-group
learning problem (S, Ht).
The following formalization of Theorem 5.3 is direct consequence of running no-regret no-regret dynamics, as in Lemma 3.3]
Theorem F.4 (Multi-grone group learning). Fix set of groups S S 2% loss E yxyy + 10. hypothesis
class H. : X + y, and distribution D; For some universal constant C and T = C (n(SS] /
Algorithm 9 takes 2T O (In([S) /ea)))") samples from D and returns an e-optimal solution to the multi- group learning problem (8, H)-
G Empirical Results
G.1 Experiment Setup
We conduct three sets of experiments to evaluate different batch multicalibration algorithms. The three sets of experiments we conduct correspond to three datasets: the UCI Adult Income dataset [26] a real-world dataset for predicting individuals' incomes based on the US Census, the UCI Bank Marketing dataset [32). a dataset for predicting whether an individual will subscribe to a bank's 's term deposit, and the Dry Bean Dataset [27] a dataset for predicting dry bean's variety.
In every experiment, the performance of a multicalibration algorithm measured based on the multicalibration violations of the average iterate and last iterate, where multicalibration violations are as defined in Definition [.1] In every experiment, we empirically evaluate six multicalibration algorithms. Four algorithms are based on no-regret best-response dynamics, using an empirical risk minimizer as the adversary and implementing either Hedge [44 (Hedge-ERM), Prod (28 (Prod-ERM), Optimistic Hedge [36] (OptHedge-FRRN,
Gradient Descent (GD-ERM) as the learner. Two algorithms are based on no-regret no-regret dynamics, using either Hedge (Hedge- Hedge) or Optimistic Hedge OppHedge-OptHedgee as both the learner and adversary. We also note
40

---

that the most commonly used multicalibration algorithms are included in these comparisons. The original multicalibration algorithm of [2T] is equivalent to GD-ERM. The revised, poostng-inssiired
multicalibration algorithm of 25 i
is equivalent to Hedge-ERM.
G.2 Results
The results of these experiments are summarized in Table which reports the multicalibration errors of each algorithm's final iterate and average iterate. In Appendix [G] [igure[ploo the evolution of training and testing multicalibration emrors over the duration of the training process. We identify two key trends that are statistically significant and hold consistently in all three experiments.
Error Measures
Train Error (Det)
Test Error (Det)
Test Error (Non-Det)
Hedgee-Hedge (NRNR)
2.0e-2 1 2.0e-3
3.0e-2 1: 3.0e-3
2.3e-4 1: 2.7e-5
Adult
OptHedge-OptHedee (NRNR)
7.0e- 0.0
2.7e-2 3.0e-3
2.6e-4 2.8e-5
OptHedge-ERM (NRBR)
0.0 0.0
4.7e-2 +: 1.0e-3
4.8e-4 + 9.0e-6
Hedge-ERM ERM (NRBR)
0.0 0.0
6.4e-2 1.0e-3
6.4e-4 1.le-5
Prod-ERM (NRBR)
0.0 +: 0.0
5.3e-2 1: 4.0e-3
5.3e-4 +: 4.4e-5
GD-ERM (NRBR)
5.3e-2 1.1e-2
8.3e-2 3.0e-3
9.5e-4 6.5e-5
Hedge-Hedge (NRNR)
2.4e-2 1.0e-3
4.3e-2 1.1e-2
5.3e-4 1.2e-4
OptHeede-OptHHedge (NRNR)
1.3e-2 + 1.0e-3
2.0e-2 + 1.0e-3
2.1c-4 + 5.0e-6
UCI UCI Bank
OptHedge-ERM (NRBR)
2.0e-3 1.0e-3
1.8e-2 0.0
2.2e-4 6.0e-6
Hedge-ERM (NRBR)
2.0e-3 1 0.0
5.2e-2 +: 1.0e-3
5.3e-4 1: 8.0e-6
Prod-ERM (NRBR)
0.0 0.0
4.6e-2 3.0e-3
5.1e-4 2.3e-5
GD-ERM (NRBR)
8.0e-3 + 1.0e-3
9.9e-2 + 6.0e-3
1.1e-3 + 7.1e-5
Hedge-Hedge (NRNR)
3.2e-2 + 5.0e-3
4.6e-2 +: 4.0e-3
2.4c-5 + 1.0e-6
OptHedge-OptHedde (NRNR)
1.9c-2 1.0c-3
5.3e-2 1.0c-3
2.7e-5 1.0c-6
Dry Bean
OptHedge-ERM (NRBR)
1.3e-2 + 0.0
5.2e-2 + 2.0e-3
2.6e-5 + 1.0c-6
Hedge-ERM (NRBR)
1.4e-2 0.0
5.5e-2 1.0e-3
2.6e-5 1.0e-6
Prod-ERM (NRBR)
1.2e-2 + 4.0e-3
6.5e-2 + 1.6e-2
2.9e-5 + 5.0e-6
GD-ERM (NRBR)
6.0e-3 0.0
7.6c-2 1.0c-3
3.1e-5 1.0c-6
Table 3: Average + standard error) of multicalibration violations on UCI Adult Dataset (20 seeds), UCI Bank Marketing Dataset (5 seeds), and the Dry Bean Dataset (5 seeds). Train Error (Det) and Test Error (Det) evaluate the last iterate (deterministic predictor) on training and test splits; Test Error (Non-Det) measures the average iterate (non-deterministic predictor) on the test split.
Figure plots the evolution of training and testing multicalibration errors over the duration of the training process. These plots confirm that the relative performance of different multicalibration algorithms is fairly monotonic and regular, even across the duration of training and the learning rate schedule.
The last iterates of no-regret no-regret dynamics are surprisingly multicalibrated. On all datasets, the algorithms based no-regret no-regret dynamics, namely Hedge-Hedge and OptHedge- OptHedge, consistently yield not only among the most multicalibrated randomized predictors (with their average iterate) but also the most multicalibrated deterministic predictors (with their last iterate). This is surprising because the last iterate of these algorithms is not guaranteed to be multicalibrated. and only enjoys theoretical advantage over no-regret best-response algorithms in terms average iterate guarantees. As corroborated by Figure [] this trend does not appear to be an artifact of early stopping or learning rates, but may rather indicate that their more stable adversary updates provide regularization to these algorithms.
41

---

Multicalibration Errors On Adul. Income Dataset
Training: Cailiration Error
0.10)
Desling Calitration Erroe
Hodge
Hidgg-laxpp
Opelisber
0.19
OptReddee Fgggl
Frod
8
0,011
Bodg- Holge
4 10
Optiledyy
0.003
Optildag Oyclilge
xx 1u73
Prod
Multicalibration Ervors On Bonk Market Dataset
GD
Training Chlibration Error
9.000
Tosing Caiibration Ereor
Opelbddg
Opt Bolaz
Pood
Badge-Heige
Oyttfelge
Pood
70
Iterations
Irevations
Multicalibration Errors On Dry Beans Dasasot
GD
GU
Thiiing Calibratioe Iiror
Helar
Tosting Calliorziion Ervor
Hedagr
Holge
Opelledge
Optliedge
Opeltrlpp-OOttiittee
Opttirdgs Oyn
Puod
Pood
6 101
3,00
60
100
40
100
Iterations
Iberations
Figure 1: These plots depict the multicalibration violations (Definition 2.1 various multicalibration algorithms on the UCI Adult Income dataset (top left). Bank Market dataset (top right), and Dry Bean dataset (bottom). The lines plot how much the current iterate violates the multicalibration condition the training data (top plot) and testing data (bottom plot), with enror bars denoting standard error. The iterates of the no-regret dynamics using the Optimistic Hedge algorithm, the most multicalibrated predictors.
algorithm, which implements no-regret vs
One's choice of no-regret algorithm matters. On all datasets, we see that the best multicalibration results are consistently achieved by algorithms that instantiate the Optimistic Hedge no-regret algorithm. This consistent with the theoretical results of (36), which show that Optimistic Hedge converges faster than standard Hedge in games. We also see that the original multicalibration algorithm (21). based on gradient descent, consistently attains the worst multicalibration errors, both in terms of average-iterate and last-iterate. This is consistent with gradient descent being theoretically less effective no-regret algorithm, as it is unstable near the boundaries of a probability simplex.
Due the superficial similarity between boosting and multicalibration, the field has already be- gun adopting multicalibration algorithms with Hedge's multiplicative updates rather than gradient descent's additive ones, as suggested by (25). Our findings offer the first theoretical and empirical en- dorsement of this shift. Moreover, results suggest that practitioners should further explore the use of Optimistic Hedge-based algorithms and algorithms based on no-regret no-regret dynamics even when is only interested in deterministic predictors.
42

---

G.3
Experiment Details
The source code for these experiments is included in the repository https: githbb com/ Model checkpoints for replicating our results can be found 1 55WFkoUX usp=sharing All experiments were performed on 2021 MacBook Pro, with MI Pro chip. The total compute time for replicating the experiments this section, including hyperparameter tuning, is approximately 20 hours.
ericchhoo28mmuuicallleeeee htta///rveeeoooo/////eae lattps:/ www.ge.ooog....oooooooo..
UCI Adult Income Dataset. The UCI Adult Income dataset [26
dataset for predicting
individuals' incomes based on the US Census. Our experiments use the dataset's binary 'income" attribute as the target label and form 129 protected groups using eight of the dataset's labeled attributes: "age', 'workclass', 'education', 'marital-status', 'occupation', 'relationship', 'race', and 'sex'. We perform random 80-20 train/test splits the dataset, resulting in approximately 24000 training samples, 6000 test samples, and 130 groups. We discretize the label space into 0.1-width bins (A = 10). Experiments are repeated for 20 seeds, with multicalibration algorithms running for 50 iterations.
UCI Bank Market Dataset. The UCI Bank Marketing dataset 32 is a dataset for predicting individuals' subscriptions to term deposit bank. Our experiments the dataset's binary "y" attribute as the target label and form 129 protected groups using eight the dataset's 's labeled attributes: 'age', 'job', 'marital', 'education', 'default', 'housing'. 'loan', and 'contact'. We round ages to the nearest age divisible by 5 since 'age' a continuous attribute. We perform random 80-20 train/test splits of the dataset, resulting in approximately 36000 training samples, 9000 test samples, and 180 groups. We discretize the label space into 0.1-width bins (A = 10). Experiments are repeated for 5 seeds, with multicalibration algorithms running for 50 iterations.
Dry Bean Dataset. The Dry Bean Dataset 27 is a dataset for predicting a dry bean's variety using its physical attributes. Our experiments use the dataset's bean 'type' attribute (which takes possible values) as the target label and form 80 protected groups using eight of the dataset's labeled attributes: 'perimeter', mmajor-axis-length" 'minor-axis-length 'aspect-ratio', "eccentricity", 'convex-area" and attributes by evenly dividing the range of possible values into 10 segments. We perform random 80-20 train/test splits of the dataset, resulting in approximately 11000 training samples, 2700 test samples, and 80 groups. We discretize the label space into 0.25-width bins 4). Experiments are repeated for 5 seeds, with multicalibration algorithms run for 100 iterations.
equivalent-diimetter We discretize all numericallcomiinuuulyyy-aa
Hyperparameter tuning. each experiment, the learning rates of the algorithms are tuned on the training set using 10 seeds (Adult Income dataset), 5 seeds (Bank Market dataset), and 5 seeds (Dry Bean dataset). We sweep over the learning rate decay rates of [0.8, 0.85, 0.9, 0.95) for the learner and (if applicable) y E [0.9, 0.95, 0.98, 0.99] for the adversary, where the learning rate of the learner at the /th iteration is r/ and the adversary 100 v7. In the Dry Bean dataset, learning rates are universally doubled to 2ny² and the adversary is 200 ./¹.. The selected learning rate decays are summarized below.
Hedge-
OptHedge- OptHedgee
OptHedge- ERM
Hedge- ERM
Dataset
Prod-ERM
GD-ERM
Hedge
Adult
7 (0.95, 0.9)
(0.95,0.9)
1 0.9
" 0.9
17 0.9
1) 0.9
Income
Bank
" (0.95, 0.95)
(0.95.0.95)
' 0.95
1 0.95
0.95
0.85
Marketing
Dry
" = (0.99, 0.98)
(0.95,0.99)
== 0.95
0.95
= 0.95
0.95
Bean
43


Reviews:
[{"review_id": "Qq6Ecmn9VA", "reviewer": "Reviewer_vjmg", "summary": "This paper provides a unifying framework for the algorithm design and performance analysis of multicalibrated predictors.\nIn this paper, the multicalibraion problems is placed in the setting of multi-objective learning.\nUnder this interpretation, approaches based on game dynamics is proposed and analyzed.\nIt is shown that this approach yields improved performance guarantees.", "questions": "- In previous studies (e.g., [17,21,34]), multicalibrated predictors appear to be defined in terms of conditional expectation.\nOn the other hand, in Definition 2.1 of this paper, it appears to be defined in some sense by joint probabilities.\nI believe this means that the errors bounded in 2.1 are smaller than those adopted as definitions in previous studies.\nThis raises concerns about whether comparisons with existing research bounds are valid.\nI would appreciate an answer to this concern to see if there is a problem.\n- Is there lower bounds that can be compared to the results obtained?", "limitations": "I have no concerns about the limitations and potential negative societal impact.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Bounds are improved for a variety of problems.\n- Experimental results support the effectiveness of the proposed method.", "weaknesses": "- The approach based on game dynamics does not seem very surprising as it is a common approach to transform min-max optimization into a problem of finding an equilibrium solution by interpreting it as a zero-sum game.\n- I have concerns about whether the definition is consistent with that of existing studies. (please refer to \"Questions\")\n\n\nMinor comments:\n- When citing existing results in Table 1, etc., it would be better to indicate the theorem number or the relevant section. I had a hard time checking the corresponding part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. Below we address your comments and questions.\n\n**Is the game dynamics approach surprising?**\\\nWe agree that writing min-max optimization problems as a zero-sum game is a common first step in many analyses. But it is the next steps that matter, and for multicalibration it has not been obvious what those next steps might be.  Indeed, no prior multicalibration work has succeeded in using a game-theoretic framing as a unifying principle for multicalibration despite over 5 years (and 50+ papers) on the topic.\n\nThe nontrivial underlying challenge is not the mere reduction to min-max optimization—which is why we refer to Facts 2.5 and 2.6 as facts and not lemmas/theorems—but rather in solving the resulting equilibrium computation problem in a way that connects to practical algorithms. The needs of multicalibration (such as determinism, large and complex predictor space, etc.) differ significantly in this regard from earlier applications of general-purpose no-regret algorithms and game dynamics. Most notably, the minimizing player’s action set is the set of all predictors, which scales exponentially in the domain size $|X|$! We must therefore construct a novel and highly nontrivial online learning strategy for the minimizing player with a regret that is independent of the size of the action set and $|X|$. Moreover, this no-regret algorithm must use non-randomized predictors against an adaptive adversary (Theorem 3.7). Another example is that we need to obtain a deterministic solution from the game dynamics despite not having convexity, which required us to introduce a novel form of no-regret/best-response game dynamics (Lemma 3.4) that, to the best of our knowledge, has not been studied previously.\n\nOverall we think that it is quite surprising that *every* known multicalibration algorithm and guarantee can be cleanly recovered—and improved upon—with game-theoretic learning dynamics using our framework. The generality of our framework and strength of Theorems 3.7 and Lemma 3.4 are further evidence that the progress made by our work is surprising, novel, and has the potential to significantly change the landscape of research in multicalibration. We will make sure that the final version of our paper emphasizes this generality from the outset and more clearly places in relief the challenges of applying learning dynamics to multicalibration.\n\n**Defining multicalibration with conditional expectations versus joint probabilities.**\\\nThank you for raising this question. Due to the inconsistent definitions of multicalibration employed in the multicalibration community, this has been an ongoing point of confusion.\nWe define multicalibration using joint probabilities in the same way as other recent literature (see GHKRS23, DLLT23), where the error tolerance for a group $G$ is inversely proportional to the group’s probability mass $\\Pr(x \\in G)$. Some early multicalibration works (such as HKRR18) define multicalibration with a conditional expectation—where the error tolerance for a group is independent of the group’s probability mass—**but make an assumption that all groups have a probability mass of at least some constant fraction** (see, e.g., Theorem 3.7 in HKRR18 which states $|S| \\geq \\gamma N$ ). That assumption means that their definition is actually weaker than our more direct joint-probability definition that is now the norm in the multicalibration community. Please let us know if this clarifies your question and we will add a footnote clarifying this in the final version as well.\n\nWe also want to bring to your attention that one of our results, Corollary E.4, shows that a guarantee even stronger than those of prior works is possible when the error tolerance for a group $G$ scales with $1 / \\sqrt{\\Pr(x \\in G)}$ rather than $1 / \\Pr(x \\in G)$. We are able to obtain this novel guarantee by plugging in second-order regret bounds into our game dynamics framework.\n\n**Lower bounds**\\\nWe are not aware of any (nontrivial) lower bounds for multicalibration. We want to emphasize that our work has improved several upper bounds in multicalibration (see Table 1), suggesting the community’s known results are likely not tight.\n\n[HKRR18] U. Hebert-Johnson, M. P. Kim, O. Reingold, and G. N. Rothblum. Multicalibration: Calibration for the (computationally-identifiable) masses. In J. G. Dy and A. Krause, editors, Proceedings of the International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, pages 1944–1953. PMLR, 2018\\\n[GHKR23] Globus-Harris I, Harrison D, Kearns M, Roth A, Sorrell J. Multicalibration as boosting for regression. arXiv preprint arXiv:2301.13767. 2023 Jan 31.\\\n[DLLT23] C. Dwork, D. Lee, H. Lin, and P. Tankala. New insights into multicalibration, 2023.\n"}, {"review_id": "aG7EPatotl", "reviewer": "Reviewer_Mwev", "summary": "The authors proposed a unified framework for multicalibration learning by exploiting its connection to the game dynamics in multi-objective learning. Strong theoretical guarantees were given and its extension to address group fairness was discussed.", "questions": "see weakness.", "limitations": "NA", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The analysis of the game dynamics in multi-objective learning was novel and strong.\n2. Connection between multicalibration learning and game dynamics in multi-objective learning was well exploited, unified framework was given.\n2. The author gave a clear presentation of the key ideas of the work despite substantial material.", "weaknesses": "1. The experiment parts seem to compare with algorithms within the proposed framework. Is there any comparison with existing baseline algorithms?\n2. How does the multi-objective learning discussed in the paper related to the Pareto optimal one?\n3. Given different learner choices shown in the empirical section, is there any learner who fits the proposed framework better?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your positive review. Below, we address your comments and questions.\n\n**On experiment comparisons to baselines existing algorithms.**\\\nOur experiments already include comparisons to existing and baseline multicalibration algorithms (see lines 1189-1191 of the appendix for further clarification). An important aspect of our framework is that it recovers **all existing multicalibration algorithms**. In the current presentation of Table 2, we refer to existing baseline algorithms by the name of the dynamics they take in our framework, e.g., the original multicalibration algorithm of HKRR18 is referred to as GD-ERM and the newer multicalibration algorithm that has become the community’s de facto standard (see e.g., KGZ19, DKRRY21) is referred to as Hedge-ERM. To clarify that these are indeed the baseline algorithms, we will add the appropriate citations on those row numbers in the final version of the paper.\nWe note that our experiments show that using optimistic Hedge and no-regret/no-regret dynamics (as a concrete proposal for an algorithm in our framework) provides better empirical performance than both of these existing baselines.\n\n**Is there a learner which empirically does better?**\\\nAs discussed above, all of the algorithms discussed in the empirical section are derived from our framework, reflecting the generality of the framework. In terms of which specific algorithms are the most empirically successful, we find that playing optimistic hedge against optimistic hedge (Opt-Hedge Opt-Hedge NRNR) is consistently the most effective algorithm. We emphasize that this choice of algorithm had not been considered in the past, and it is through the unifying feature of our framework that its importance has come to light.\n\n**On the relationship of multiobjective learning to pareto optimality.**\\\nThe multi-objective learning discussed in the paper is concerned with attaining a min-max value rather than finding a strategy guaranteed to be on the Pareto front. We did not need to additionally consider the stronger condition of Pareto optimality in multiobjective optimization because the connection between multi-objective learning and multicalibration goes through the min-max value alone. We therefore do not include Pareto optimality in our definition of multiobjective learning. This is also consistent with recent works in multi-objective learning such as [HJZ22].\n\n**References**\\\n[HKRR18] U. Hebert-Johnson, M. P. Kim, O. Reingold, and G. N. Rothblum. Multicalibration: Calibration for the (computationally-identifiable) masses. In J. G. Dy and A. Krause, editors, Proceedings of the International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, pages 1944–1953. PMLR, 2018\\\n[HJZ22] N. Haghtalab, M. I. Jordan, and E. Zhao. On-demand sampling: Learning optimally from multiple distributions. In S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, 2022\\\n[KGZ19] M. P. Kim, A. Ghorbani, and J. Y. Zou. Multiaccuracy: Black-box post-processing for fairness in classification. In V. Conitzer, G. K. Hadfield, and S. Vallor, editors, Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 247–254. ACM, 2019.\\\n[DKRRY21] C. Dwork, M. P. Kim, O. Reingold, G. N. Rothblum, and G. Yona. Outcome indistinguishability. In Proceedings of the Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1095–1108. ACM, 2021.\n\n"}, {"review_id": "DMSKxLI6Pa", "reviewer": "Reviewer_ymik", "summary": "This work exploits connections to game dynamics to propose a unifying algorithmic framework to address the multicalibration problem which has been recently used for tackling fairness concerns in machine learning. More precisely, based on the classic game dynamics approach used in learning problems, it is shown that multicalibration results can be seen as learning dynamics for two-player zero-sum games relying on no-regret algorithms or best response dynamics. Using this unifying framework, the paper recovers some guarantees for existing multicalibration algorithms with simplified proofs and results. Multi-objective learning guarantees are shown and new guarantees are also established for several multicalibration settings including in particular an exponential reduction in the complexity of k-class multicalibration over prior work. Experiments were conducted to evaluate the empirical performance of multicalibration algorithms on some real-world datasets. \n", "questions": "- The game dynamics approach to multi-objective learning is a ‘common approach’ as mentioned in l. 138. The paper connects multicalibration to multi-objective learning in Facts 2.5 and 2.6 which leads to a connection between multicalibration and the game dynamics approach. Are Facts 2.5 and 2.6 novel results? Is there a particular reason for using ‘Facts’ for these results instead of ‘Lemma’ for instance? Is this related to the simplicity of the proofs in Appendix B once the losses are defined as in the facts? \n\n\n- How do you justify the equality in l. 230-231?\n\n- Section 3.1 is about multicalibration but section 3 is about multi-objective learning. Section 4 is 'Multicalibration with Game Dynamics'. Would it be more appropriate to move section 3.1 to section 4? \n\n**Minor questions and suggestions:**\n\n- Why is the baseline of (2) not also used in (1) so that the formulations are unified?\n\n- The notations max and min are used for minimization over a hypothesis class or maximization over a class of loss functions and a set of data distributions. How are these guaranteed to be reached without further assumptions? Are the classes supposed to be finite or are the more general notations sup and inf more appropriate? For instance, cardinalities are used in Lemma 3.5 while the preliminaries do not seem to specify the nature of the classes. \n\n- Minor suggestion: in Definition 2.2., you could keep the same notation as in Definition 2.1 and only change the dependence on $t$ for $D$ and $p$ to ease the reading (with the same order for the quantities and a single indicator function). \n\n - l. 82: $\\Delta(\\mathcal{Y})^{\\mathcal{X}}$ with parenthesis.\n", "limitations": "Limitations of the results do not seem to be clearly discussed throughout the paper to the best of my knowledge. ", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "-  The paper proposes a unifying approach using game dynamics which recovers prior results with simpler proofs and establishes novel guarantees improving over prior work in multiple settings. \n- This paper is well-written, the presentation is very clear. \n- While I am not familiar with the calibration/multicalibration literature and I did not go through the long appendix supporting the main part in details, the results are sound, quite rigorously exposed and the proofs which leverage for instance prior online learning results seem solid to the best of my knowledge. \n- Several additional experimental results are also provided in the appendix to support the theoretical findings. ", "weaknesses": "Regarding novelty, the related work section mentions in l. 55-56 that ‘no work has established a broad connection between no-regret learning and multicalibration’. No-regret learning has been priorly used for calibrated forecasting as acknowledged by the paper. While it is mentioned that multicalibration ‘has very different challenges than calibrated forecasting’, the discussion regarding these is reduced to a single line l. 57-58 in the related work section. Given that one of the main contributions of this work is the unifying framework based on the connection with game dynamics, I would expect a more detailed discussion to further clarify the novelty with respect to prior work and calibrated forecasting regarding this particular aspect. For instance, some proofs such as the one of Theorem 3.8 follow similar lines to the proof of calibration as also mentioned in l. 246-247. Moreover, it seems that this connection to game dynamics was known for multi-objective learning and multicalibration is linked to it via the simple facts 2.5 and 2.6. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. Below, we address your comments and questions.\n\n**On game dynamics being a common approach for multi-objective learning.**\\\nWhile it appears intuitive that game dynamics must have a role to play in multicalibration, given that no-regret learning plays a role in calibrated forecasting, it has taken 5 years and 50+ papers in this space for our work to be the first to make this connection in a broad and unified way. \n\nThe nontrivial underlying challenge is not the mere reduction to min-max optimization—which is why we refer to Facts 2.5 and 2.6 as facts and not lemmas/theorems—but rather in solving the resulting equilibrium computation problem in a way that connects to practical algorithms. The needs of multicalibration (such as determinism, large and complex predictor space, etc.) differ significantly in this regard from earlier applications of general-purpose no-regret algorithms and game dynamics. Most notably, the minimizing player’s action set is the set of all predictors, which scales exponentially in the domain size $|X|$! We must therefore construct a novel and highly nontrivial online learning strategy for the minimizing player with a regret that is independent of the size of the action set and $|X|$. Moreover, this no-regret algorithm must use non-randomized predictors against an adaptive adversary (Theorem 3.7). Another example is that we need to obtain a deterministic solution from the game dynamics despite not having convexity, which required us to introduce a novel form of no-regret/best-response game dynamics (Lemma 3.4) that, to the best of our knowledge, has not been studied previously.\n\nThe key to our simple proofs are not Facts 2.5 and 2.6 but rather Theorems 3.7 and Lemma 3.4, and other lemmas in Section 3, that allow us to use different dynamics to address various specific needs and settings in multicalibration. None of these theoretical tools come from (or were even needed) in calibrated forecasting. Moreover, in section 3, we highlight how alternative game dynamics and benchmarks (such as notions of weak regret and deterministic solutions) can lead to equilibrium notions that are more in line with the needs of multicalibration. It is against this backdrop of alternative game dynamics that we introduce Theorem 3.7 that is the key to many of our results.\nWe agree that Theorem 3.8 is inspired by a similar lemma in calibrated forecasting, as we mentioned in the paper. But Theorem 3.8 goes further, providing a connection between online multicalibration and the calibrated forecasting literature that is new to our work. Indeed, we highlight that Theorem 3.8 is primarily used by our online multicalibration results. \n\n**Equality on Line 230-231**\n\nThis equality is because we can choose $h^*$ so that $h^*(x) = z^*$. Intuitively, this equality arises because we are optimizing over all well-defined predictors $h: X\\rightarrow Y$.\n\n**The baseline of (2) vs baseline of (1)**\\\nThe baseline of (2) is much larger than the baseline of (1). In fact, the baseline of (2) would be trivial to attain in an offline batch setting, whereas the baseline of (1) is impossible to attain in an online setting.\n\n**On related work.**\\\nWe appreciate your feedback and will amend the related works to emphasize that the technical tools our results rely on differ significantly from those explored in the calibrated forecasting literature. Below, we highlight some clarifying examples.\n* Non-deterministic predictors are necessary in calibrated forecasting, whereas multicalibration is usually defined for deterministic predictors. We needed to design novel game dynamics that produce deterministic solutions since, as we note above, we could not rely on convexity to perform online-to-batch reductions. These determinism/non-determinism concerns do not arise at all in calibrated forecasting.\n* The concept of calibrated forecasting does not require one to reason about a covariate distribution. In contrast, multicalibration is a form of supervised learning and is—at its asymptotic limit—exactly the task of learning a Bayes-optimal classifier. As a result, calibrated forecasting requires solving only a simple online learning problem over 2 actions—predicting 0 or predicting 1—while multicalibration requires online learning on an action set that grows exponentially with the size of one's domain $2^{|X|}$.\n* Calibrated forecasting reduces to an online learning problem where sublinear regret is achievable [Fos99, Har22]. Multicalibration reduces to an online learning problem where sublinear regret is not always achievable. As a result, we had to introduce notions such as weak regret (Line 150).\n"}, {"review_id": "aXLh5AMwEy", "reviewer": "Reviewer_pd5T", "summary": "The paper provides a two-player dynamics framework that seeks to unify many strands of recent work on multicalibration and multiobjective optimization. With three possible setups considered: No regret against No regret, Best response against No regret, and Best response against Best response, efficient algorithms are provided to demonstrate that these generic setups apply in particular to (multi-)calibration-like constraints. The framework is then applied to several existing and new settings in the literature with the goal of improving some convergence bounds or, respectively, simplifying and streamlining the analysis of specific algorithms. Some experiments are given that show what happens when proposed dynamics are run with specific well-known no regret algorithms in the driver's seat. ", "questions": "See the above section.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "To me, the main strength of this paper is the rather clean nature of the setup, which promises that by combining, in any combination, best-responding and no-regret agents, it is possible (though not without further work) to recover existing multigroup fairness results. Previous guarantees are (with a couple exceptions) improved somewhat marginally, or greater simplicity of the framework is claimed in some other cases, but overall it is the generality of this framework --- showcased by its adaptability and ability to recover various insights about calibration (not just regret bounds, but also questions of the simplicity of the output calibrated model, amount of randomness required, etc) --- that is the paper's main forte.\n\nAdditionally, the conditional multicalibration setup presented in the paper (and generalizing previous conditional results in the quantile setting) looks like an interesting addition to the literature.", "weaknesses": "No particular weaknesses, other than the relatively well-studied nature of, and relatively small gains in, some of the applications (but no big deal), as well as the somewhat terse and cramped presentation.\n\nFor instance, there are a few \"intuitive-sounding\" claims made about where NRNR, BRNR, BRBR may be applied to the greatest utility, but the actual applications are then scattered throughout the paper rather than recalled immediately (there is also Table 1, but I would appreciate a more intuitive dive into which dynamic was used where and why, at the point where these dynamics were actually introduced). For another example, I would be interested in further comments on potential alternative definitions of conditional multicalibration and a slightly expanded treatment of the comparison to the existing 1/sqrt(# people in group) type of guarantee. \n\nStill, the paper is overall solid and well-done and I enjoyed reading it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your positive review. We appreciate your feedback on including a discussion about which dynamics are used where and lead to which improvements—we will make some revisions to further improve the flow. We also appreciate your suggestion to include additional comments on our sqrt-conditional multicalibration result (Corollary E.4).\n\n**On further details for conditional multicalibration**\\\nWe would like to highlight the following points regarding Corollary E.4 to clarify its significance, as we believe it is an example of a significant theoretical improvement that our framework yields as a consequence of  its versatility.\n\nAlthough existing multicalibration algorithms only guarantee an error bound that—for each group $G$—scales inversely with the group’s probability mass $\\Pr(x \\in G)$, we show **it is possible to obtain an error bound that scales with $1 / \\sqrt{\\Pr(x \\in G)}$ rather than $1 / \\Pr(x \\in G)$**. We are the first to obtain this stronger guarantee (Corollary E.4). We achieve this without introducing any additional assumptions and with no increase in the sample complexity (compared to the sample complexity of algorithms that do not use adaptive data analysis) or only a cube-root increase in sample complexity (compared to algorithms that use adaptive data analysis). Even more interestingly, this result is obtained by simply replacing first-order regret bounds with second-order regret bounds in our game dynamics. Please let us know if you have further questions and comments about these results.\n\nBased on your feedback, we plan to add to the section some of these clarifying comments. We will also include refinement of Corollary E.4 which should be more readable, removes an extraneous $\\sqrt{S’}$ factor from the sample complexity of Corollary E.4, and makes clear the corollary does not need to assume knowledge of $\\Pr(x \\in S)$ nor make any other assumptions. \n"}, {"review_id": "01YXw9h33n", "reviewer": "Reviewer_rNCE", "summary": "This paper presents a novel approach to multicalibration by leveraging game dynamics and no-regret learning algorithms. The central idea is that multicalibration can be modeled as a multi-objective learning problem where an adversary and a learner play against each other, guided by no-regret dynamics.\n\nThe authors propose three types of dynamics: no-regret no-regret (NRNR), no-regret best-response (NRBR), and best-response no-regret (BRNR), each serving different purposes. These dynamics are used to establish the multicalibration algorithms that match or improve the fastest known sample complexity rates for multicalibration, provide deterministic multicalibrated predictors, and offer online multicalibration.\n\nThis work also extends the application of these dynamics to other fairness notions, specifically multi-group learning and multi-distribution learning. For the multi-group learning problem, the authors devise an optimal multi-group learning algorithm that relies on NRNR dynamics and is simpler than the existing approaches.\n\nThe authors validate their theoretical claims with empirical results on a few standard datasetst. The results highlight the importance of effective no-regret algorithms for better multicalibration, with the Optimistic Hedge outperforming others in the no-regret no-regret dynamics.\n\nOverall, this paper contributes to the field by providing a unified, game-theoretic framework for multicalibration that unites disparate existing results and offers more efficient solutions, both in theory and practice. Moreover, it highlights the broader applicability of game dynamics and no-regret algorithms to other fairness notions in machine learning.", "questions": "The paper provides an improved theoretical framework for multicalibration using game dynamics. However, it seems there's a disconnect between the theory and empirical results presented. Could the authors elaborate on why specific experiments were chosen and how they directly validate the theoretical developments?\n\nThe empirical evaluation mainly focuses on the standard datasets like UCI. How do the authors envision their proposed algorithms performing on other types of datasets, especially those with different characteristics, such as image datasets or high-dimensional problem? Could they provide any insights or theoretical guarantees on their algorithms' robustness across varied datasets?\n\nThe high-level descriptions of the proposed algorithms are appreciated, but having more concrete, step-by-step details of the algorithm implementations would be very helpful. Could the authors provide pseudocode or a more in-depth explanation of their proposed algorithms?\n\nThe paper could benefit from a more detailed comparison with previous works. How do the authors' contributions improve upon or differentiate from existing methods, specifically in terms of performance and applicability?\n\nThe paper presents a novel framework that generalizes previous works. How far can this generalization go? Are there any theoretical or practical constraints that limit its applications? Are there any lower bounds? Any insight into this would be beneficial for the understanding and application of the framework.\n\n\n\n\n\n", "limitations": "The authors do not provide a clear discussion of the limitations of their work or potential negative societal impacts, which is a critical part of any comprehensive research paper. This is an area where the paper could be improved. Here are a few suggestions for potential limitations and societal impact considerations:\n\nDiscuss the computational complexity and scalability of the proposed methods. This is crucial for real-world applications, particularly when dealing with large and complex datasets.\n\nGiven that the paper deals with fairness notions in learning, the authors could consider discussing the implications of misapplication of these methods. While the goal is to improve fairness, any shortcomings or misuse could unintentionally lead to bias or unfair outcomes.\n\n\n\n\n\n\n\n", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper introduces a novel perspective by approaching multicalibration and other fairness notions using game dynamics and no-regret learning algorithms. It presents multicalibration as a multi-objective learning problem within a game-theoretic framework. However, while the application to multicalibration is new, the use of no-regret algorithms and game-theoretic models is well-established in other areas of calibration literature.\n\nThe paper offers a technically sound approach with rigorous mathematical derivations. The theorems are well-proved, and the proposed algorithms are clearly detailed. However, the empirical section could be expanded upon to strengthen the validation of the theoretical claims with real-world data.\n\nThe authors have done a reasonable job in articulating complex concepts and methodologies, with the paper being generally well-structured. The use of tables aids understanding, though more insights can be provided for the technical results.\n\nThe work has the potential to unify and extend prior work on multicalibration and other fairness notions. However, the impact of the work may depend heavily on how effectively these theoretical insights can be translated into practical applications. Furthermore, while the findings from the empirical results could guide the selection of no-regret algorithms in multicalibration tasks, the experimental validation is relatively limited and does not fully exploit the range of situations where these algorithms could be applied.", "weaknesses": "The paper provides a theoretically strong development of multicalibration algorithms using game dynamics. However, there seems to be a gap between the theoretical development and the empirical results. The authors could improve this aspect by designing more comprehensive experiments that test a wide range of scenarios to validate their theoretical claims. These could include different types of datasets, varying levels of complexity, and possibly real-world use cases.\n\nThe experimental evaluation is currently limited to only a few standard but simple dataset. This may not sufficiently test the robustness of the proposed algorithms under different conditions. More experiments with diverse datasets would provide a better understanding of the algorithms' performance and potential limitations. Additionally, it would be beneficial to compare the proposed methods with more baseline or state-of-the-art algorithms for multicalibration to understand the relative performance.\n\nAlso, the paper could be improved by providing more detailed descriptions of the proposed algorithms. While the authors do discuss the high-level ideas behind using game dynamics for multicalibration, it may be beneficial for readers to have more specific details about how these algorithms are implemented.\n\nAlthough the authors discuss several previous works, it is not entirely clear how their contributions improve upon or differ from these existing methods. Besides theoretical comparison, a clearer empirical comparison would make the authors' contributions more evident.\n\nThe paper could benefit from a more explicit discussion of the limitations of the proposed methods. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. Below we respond to your questions.\n\n**On providing Pseudocode**\\\nWe already provide detailed step-by-step pseudocode for every algorithm in the Appendix: see Algorithms 2, 3, 4, 5, 6, 7. We also have fully released our source code for the experiments (see supplemental material).\nOn including experiments comparing to state-of-the-art algorithms in multicalibration\nOur experiments already include comparisons to all existing and baseline multicalibration algorithms (see lines 1189-1191 of the appendix for further clarification). An important aspect of our framework is that it recovers all existing multicalibration algorithms. In the current presentation of Table 2, we refer to existing baseline algorithms by the name of the dynamics they take in our framework, e.g., the original multicalibration algorithm of HKRR18 is referred to as GD-ERM and the newer multicalibration algorithm that has become the community’s de facto standard (see e.g., KGZ19, DKRRY21) is referred to as Hedge-ERM. To clarify that these are indeed the baseline algorithms, we will add the appropriate citations on those row numbers in the final version of the paper.\n\n**On the choice of experiment datasets**\\\nOur experiments, which evaluate on three datasets including both binary and multi-class problems, are among the most thorough in the multicalibration literature. Most prior work in this space is purely theoretical with no empirical evaluations. In cases where prior work in multicalibration has done empirical evaluations, those evaluations have only used toy simulated datasets (e.g. in GKSZ22). Indeed, our work includes the most extensive empirical evaluation of existing and introduced algorithms in multicalibration to date. This is in addition to the main contribution of our paper, which is to unify the theory of multicalibration.\n\n**On the lack of deep learning results**\\\nRunning deep learning experiments for high-dimensional image data sets is both beyond the scope of this work and of limited relevance to multicalibration. To the best of our knowledge multicalibration has never been successfully scaled to deep learning settings before (though we note multi-accuracy, a related but much easier problem, has). Moreover, UCI datasets present a more relevant empirical setting since they include demographic features that provide meaningful proxies for the definitions of groups in multicalibration.\n\n**On misapplication of multicalibration as a fairness technique**\\\nMulticalibration has long been used as a method of algorithmic fairness and is an established line of work (see HKRR18). Overall, we are interested in improving the theory and design of algorithms for multicalibration that lead to better statistical and computational bounds. Note that in Section E.2 we do address some—to the best of our knowledge—previously overlooked shortcomings of multicalibration as a fairness technique and propose some solutions. However, a broad discussion of misapplication of statistical sample complexity bounds is not in the scope of this work.\n\n**References**\\\n[HKRR18] U. Hebert-Johnson, M. P. Kim, O. Reingold, and G. N. Rothblum. Multicalibration: Calibration for the (computationally-identifiable) masses. In J. G. Dy and A. Krause, editors, Proceedings of the International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, pages 1944–1953. PMLR, 2018\\\n[GKSZ22] P. Gopalan, M. P. Kim, M. Singhal, and S. Zhao. Low-degree multicalibration. In P.L. Loh and M. Raginsky, editors, Proceedings of the Conference on Learning Theory (COLT), pages 3193–3234. PMLR, 2022.\n"}]

Author rebuttal:

Meta-review: By exploiting connections between multicalibration and multiobjective optimization, the paper unifies and in several cases improves upon existing multicalibration algorithms and guarantees through the game dynamics perspective. The contributions are strong and insightful. Most reviewers are positive with the contributions except one who did not participate in the discussion.  Hence, I recommend to accept the paper.
Decision: Accept (poster)