Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications
Authors: Daniel Lee
Georgy Noarov
Mallesh Pai
Aaron Roth
Venue: NeurIPS 2022 Accept (2022)

Abstract: We introduce a simple but general online learning framework in which a learner plays against an adversary in a vector-valued game that changes every round. Even though the learner's objective is not convex-concave (and so the minimax theorem does not apply), we give a simple algorithm that can compete with the setting in which the adversary must announce their action first, with optimally diminishing regret. We demonstrate the power of our framework by using it to (re)derive optimal bounds and efficient algorithms across a variety of domains, ranging from multicalibration to a large set of no-regret algorithms, to a variant of Blackwell's approachability theorem for polytopes with fast convergence rates. As a new application, we show how to ``(multi)calibeat'' an arbitrary collection of forecasters --- achieving an exponentially improved dependence on the number of models we are competing against, compared to prior work. 

Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications
Daniel Lee', Georgy Noarov', Mallesh Pai Aaron Roth
University of Pennsylvania, Rice University
danielleoBalumi.uppe edu, gnoarov@seas upenn. edu, mallesh, pwwpiii.aiiiiiie...ee edu, aaroth@cis upenn edu
Abstract
We introduce a simple but general online learning framework in which learner plays against an adversary in vector-valuee game that changes every round. Even though the learner's objective not convex-concave (and so the minimax theorem does not apply), we give simple algorithm that can compete with the setting in which the adversary must announce their action first, with optimally diminishing regret. We demonstrate the power of our framework by using it to (re)derive optimal bounds and efficient algorithms across variety of domains, ranging from multicalibration to large set of no regret algorithms,, to variant Blackwell's s approachability theorem for polytopes with fast convergence rates. As new application, show how to "(multi)calibeat" forecasters achieving an exponentially improved dependence on the number models we competing against, compared to prior work.
arbitrary collection of
Introduction
We introduce and study simple but powerful framework for online adversarial multiobjective minimax optimization. At each round f, an adaptive adversary chooses an environment for the learner play in, defined by a convex compact action set X' for the learner, convex compact action set y for the adversary, and a d-dimensional continuous loss function f X x y [-1, 1] that, in each coordinate, is convex the learner's action and concave in the adversary's ' action. The learner then chooses action, or distribution over actions, æf, and the adversary responds with action y². This vector e (2'",, v²), which accumulates over time. The learner's goal to minimize the ET E) (a* .v)).
results
maximum accumulated loss over each of the dimensions: max5e[4]
One may view the environment chosen at each round / as defining zero-sum game in which the learner wishes minimize the maximum coordinate of the resulting loss vector. The objective of the learner in the stage game in isolation can be written as
wi = inf max EX D E
max (a (2',,²)) (EE(d]
Unfortunately, although é is convex-concave in each coordinate, the maximum over coordinates does preserve concavity for the adversary. Thus the minimax theorem does not hold, and the value of the game in which the learner moves first (defined above) is larger than the value of the game which the adversary moves first- that is, w¹, wx where w defined
brief aside about the "inf max max" structure w/;: since each e continuous, so is maxy tj. and hence max, (max, ()) is attained the compact set y However, max, (max, E5) may be continuous function of x and therefore the infimum over 2 need not he attained.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

w'A sup min y'Ey" E
max (( .3')
(jll)
Nevertheless, fixing a series Tf environments chosen by the adversary, this defines hindsight an value of the constituent
aspirational quantity W = Ei= w'A- summing the adversary-moves- zero sum games. Despite the fact that these values are not individually obtainable in the stage games, we show that they are approachable on average over a sequence of rounds, i.e., there is an algorithm for the learner that guarantees that against any adversary,
+ ((( +
+WI + AV 2nd
max 2E(4
Our derivation is elementary and based a minimax argument, and is development of a game- theoretic argument from the calibration literature due to Hart [2020] and Fudenberg and Levine [1999 The generic algorithm plays actions at every round t according
minimax equilibrium strategy in a surrogate game that is derived both from the environment chosen by the adversary at round well as from the history of play far previous rounds t' < t. The loss in the surrogate (and so we may apply minimax arguments), and can be used to upper bound
game is convex-concan the loss in the original games.
We then show that this simple framework can be instantiated derive a wide array of optimal bounds, and that the corresponding algorithms can be derived in closed form by solving for the minimax equilibrium of the corresponding surrogate game. Despite its simplicity, our framework has a number of applications to online learning- we sketch these below.
Clllti-Calibeatting: Foster and Hart [202]] recently introduced the notion of "calibeating" an arbitrary online forecaster: making online calibrated predictions about adversarially chosen sequence of inputs that are guaranteed to have lower squared error than an arbitrary predictor f. where the improvement in error approaches s's calibration error in hindsight. Foster and Hart give two methods for calibeating an arbitrary collection of predictors F simultaneously, but these methods have exponential and polynomial dependence in their convergence bounds on [F], respectively.
Using our framework, we can derive optimal online bounds for online multicalibratiin (Hébert) Johnson et al. 2018 Gupta al. 2022]. and as application, obtain bounds for calibeating arbitrary collection models with only a logarithmic dependence on [F]. Our algorithm naturally extends to the more general problem of online "multi-calibeatie multicalibration and calibeating. Namely, we give an algorithm for making real-valued predictions given contexts from some space Q. The algorithm is parameterized by (i) a collection G C 2 of (arbitrary, potentially intersecting) subsets of θ that we might envision to represent e.g. different demographic groups in setting in which we are making predictions about people; and (ii) an arbitrary collection of predictors F. We promise that our predictions are calibrated not just overall, but simultaneously within each group g not just overall, but simultancously within each group E G. We do this by proving an online analogue of what Hébert-Johnson et al. [2018) call a "do no harm" property in the batch setting using a similar technique: multicalibrating with respect to the level sets of the predictors.
i.e. combining the goals of online
and moreover, that calibeat each predictor f E F
Fast Polytope Blackwell Approachability: We give a variant of Blackwell's Approachability Theorem [Blackwell 1956) for approaching a polytope. Standard methods approach a set in Euclidean distance, at rate polynomial in the payoff dimension. In contrast, we give a mameeniion-nndpendenn approachability guarantee: approximately satisfy all halfspace constraints defining the polytope, after logarithmically many rounds in the number of constraints, a significant improvement over a polynomial dimensional dependence in many settings. It is equivalent to the results of Perchet 2015). which show that the negative orthant && is approachable in the foo metric with a log(d) d) dependence in the convergence rate. This result follows immediately from specialization of our framework that does not require changing the environment at each round, highlighting the connection between our framework and approachability. We remark that approachability has been extended in number of ways in recent years [Mannor et al. 20144 b. |erchet and Mannor 2013). However most of our other applications take advantage of the flexibility of our framework play different game each
"This argument was extended in Gupta et al. 2022 to obtain fast rates and explicit algorithms for multicali- bration and multivalidity.
2

---

round (which can be defined by context) with potentially different action sets, and so do not directly follow from Blackwell approachability. Therefore, while many of our regret bounds could be derived from approachability to the negative orthant by enlarging the action space exponentially to simulate aspects of our framework, this approach would not easily lead to efficient algorithms.
Recovering Expert Learning Bounds: Algorithms and optimal bounds for various expert learning
problems fall naturally out of our framework corollaries. This includes external regret [Vovk]
1990 Littlestone and Warmuth, 1994]. internal and swap regret [Foster and Vohra 1998 Hart and
Mas- Colell |0um| and Mansour ].07]. adaptive regret [Littlestone and Warmuth 1994
Hazan
and Seshadhri
et al. 2012]. sleeping experts [Freund et al. 1997 Blum 1997 Blmm
and Mansour 2007
Kleinberg al. 2010]. and the recently introduced multi-group regret B Blum
Rothblum and Yona 2021]. Multi-group regret refers to a contextual prediction problem in which the learner gets contexts from θ before each round. It is parameterized by collection of groups 9 C 2 e.g., if the predictions concern people, G may represent an arbitrary, intersecting set of demographic groups. Here the "experts" are different models that make predictions on each instance; the goal is to attain no-regret not just overall, but also on the subset of rounds corresponding contexts from each g G. Multi-group regret, like multicalibration, is one of the few solution concepts in the algorithmic fairness literature known not to involve tradeoffs with overall accuracy [Globus-Haree
and Lykouris 2020
al., 2022]. Blum and Lykouris (2020) derived their algorithm for online multigroup regret via a reduction to sleeping experts, and Gupta et al. (2022) derived their
algorithm for online multicalibration via direct argument. Here we derive online algorithms for
both multicalibration and multigroup regret corollaries of the same fundamental framework.
2 General Framework
2.1 The Setting
A Learner (she) plays against an Adversary (he) over rounds [T] (T). Over these rounds, she accumulates d-dimensional loss vector (d 2 1), where each round's loss vector lies in [-C, for some C >> 0. At each round I, the Learner and the Adversary interact as follows:
1. Before round f, the Adversary selects and reveals to the Learner an environment comprising:
(a) The Learner's 's and Adversary's respective convex compact action sets X y embedded into a finite-dimensiona. Euclidean space;
(b) continuous vector loss funetion (((,)) X y > --C with each ()()):
X' y + I-C, C1 (for j E [d] convex in the 1st and concave in the 2nd argument.
2. The Learner selects some x' X
3. The Adversary observes the Learner's selection -², and responds with some y E yt.
4. The Learner suffers (and observes) the loss vector 8 (z²,x")
The Learner's objective is to minimize the value of the maximum dimension of the accumulated loss vector after T rounds-in other words, to minimize: max5e[a] Exemy Ef v²).
To benchmark the Learner' performance, we consider the following quantity at each round t: Definition 2.1 (The Adversary-Movee -Moees-irrtt (AMF) Value at Round t). The Adversary-Moves--iie value of the game defined by the environment (X* yrt (¹) at round t is:
= sup min (max (xt,x")) w²))
w A
y'E)" x'Ex" (Eld]
If the Adversary had to reveal Y first and the Learner could best respond, wA would be the smallest value of the maximum coordinate of L she could guarantee. However, the function maxje(d] E (x*, yy) is not convex-concave (as the max does not preserve concavity); hence the minimax theorem does not apply, making this value unobtainable for the Learner, who in fact obligated to reveal x' first. However, can define regret benchmark given by the cumulative AMF values of the games:
3

---

Definition 2.2 (Adversary- Movees--orv-snn (AMF) Regret), On transcript X²= ( ,, ...VV.. Y==1 we define the Learner's Adversary Moves First (AMF) Regret for the j dimension at time t be:
Σ 13(0")0))
The overall AMF Regret is then defined as follows: R' (T²) = m R3
Again, the game played at each round is not convex so we cannot get R < 0. Instead, we will aim to obtain sublinear AMF regret, worst-case over adaptive adversaries: R² = o(T).
2.2 General Algorithm
Our algorithmic framework will be based natural idea: instead of directly grappling with the maximum coordinate the cumulative vector valued loss, we upper bound the AMF regret with a mne-dimensional "soft-max" surrogate loss function, which the algorithm will then aim to minimize.
Definition 2.3 (Surrogate loss). Fixing a parameter 1) E (0, 1), we define our surrogate loss function (that implicitly depends on the transcript n' through the respective round t. as:
:= = Σ exp (nR)) fort [T). and L := d.
jELd
This surrogate loss tightly bounds the AMF regret R² = maxjeld Rly:
Lemma 2.1. The Learner's AMF Regret is upper bounded using the surrogate loss as: RT S In
Next we observe simple but important bound on the per-round increase in the surrogate loss. Lemma 2.2. For any 1, any transcript through round t, and any S 26 it holds that:
L' s (2n22² + I Σ exp (1) (e) (m'.0') 1 w'x) jEld]
The proof is very simple (see Appendix B.1 : we write out the quantity L' -'- L'-1 use the definition of AMF regret R', and then bound L'
via the inequality e" < 11+2 + x for x S 1.
We now exploit Lemma 2.2 to bound the final surrogate loss L and obtain a game- game-theoretic algorithm for the Learner that attains this bound. While the above steps should remind the reader of standard derivation of the celebrated Exponential Weights algorithm via bounding a log-sum-exp potential function, the next lemma is the novel ingredient that makes our framework significantly more general by relying on Sion's 's powerful generalization of the Minimax Theorem to convex-coneed games.
Lemma 2.3. For any 1) & 20, the Learner can ensure that the final surrogate loss bounded as:
L s d (4 +1)"
Proof sketch; see Appendix B.1 Define, for E [T], continuous convex- Coneex-concaveeeeee functions w' X y + E. by: u'(x, y) := Exe(d exp (nR) (z, y) w'A) If the Learner can ensure u'(x", y²) _ 0 on all rounds E [T] regardless of the Adversary's 's play, then Lemma Lemma implies L' < C2 + L'-1 for all E [T]. leading to the desired bound on L Due to the continuous convex- concave nature each n¹ (inherited from the loss coordinates f9), we can apply Sion's Minimax Theorem to conclude that: ming max u' (x", .y²) = max mina u' (x',y").
In words, the Learner has so-called minimax-optima strategy x', that achieves (worst-case over all y E ) value u' (x", yr) as low as the Adversary moved first and the Learner could best- respond. But in the latter counterfactual scenario, using the definitions of uf and the Adversary- moves-first value w we can casily see that by best-responding to the Adversary, the Learner would always guarantee herself value < 0: that is, m eyt mill ue (zf, v²) < 0. Thus, m max,' e w' (x*, y"), and so by playing Munimmx--pptmmllly at every round t E [T]. the Learer will guarantee u' (x*, v²) < 0 for all t, leading to the desired regret bound.
We will generally elide the dependence the transcript and simply write H; and R²

---

In fact, via a simple algebraic transformation (see Appendix B.1) taking advantage of the values w being independent the actions z', y", we can explicitly express the Learner's minimax optimal strate- exp( -; (e(""")"))
gies at all rounds as: argmin max u' (z, y) = argmin max Σ =EX'
L (z, (22.)) y).
exp(nE.si P5(x" w²))
sE>x
zE vEV' jE[4 ic[
Together with the proof of Lemma 2.3 this immediately gives the following algorithm for the Learner that achieves the desired bound on L (and thus,
will show, the AMF regret R²).
Algorithm 1: General Algorithm for the Learner that Achieves Sublinear AMF Regret for rounds .,...:7 7 do
Learn adversarially chosen Xt, yr, and loss function ('(,))
exp ( (g(x)
Let
x² = Eield exp (nE (f(2", ((xx,,0) v²))
for j E [d].
Play
x' E argmin max
Σ Xi -,((,)))))
xEx" yEy'
SEId
Observe the Adversary's selection of y E E
Theorem 2.1 (AMF Regret guarantee of Algorithm D.. For any T Z In d, Algorithm @with learning
In T
obtains, against any Adversary, AMF regret bounded by: R 4CVTTmd.
rate 17- V
Indeed, using Lemma 2.1
then Lemma 2.3 then + x S E", and finally settingn V TTC., we get:
Rd In ln In (n(d(s)((++1))) In(doxp(4Tx
Ind 4CVTT=
7
Remark 2.1. Our framework is easy to adapt to the setting where the Learner randomizes, at each round, amongst a finite set of actions A (i.e. X AA'), and wishes to obtain in-expectation and high-probability AMF regret bounds. This is useful in all our applications below. Additionally, our AMF regret bounds are robust the Learner playing only an approximate (rather than exact) minimax strategy at each round: we use this to derive our simple multicalibration algorithm below. See Appendix 8.2ffor both these extensions.
Deriving No-X-Regret Algorithms from Our Framework
The core our framework the
-ovees-orrttteeee regret strictly more general than very large variety of known regret notions including: external, internal, swap, adaptive, sleeping-experts, multigroup, and wide-range (b) regret. Specifically, in Appendix C we use our framework derive simple -regrrt algorithms for what we call subsequence regret, which encapsulates all these regret forms. In each of these cases, our generic algorithm is efficient, and often specializes (by computing a minimax equilibrium strategy in closed form) to simple combinatorial algorithms that had been derived from first principles in prior work. We note that in any problem that involves context or changing action spaces (as the sleeping experts problem does), we are taking advantage of the flexibility of our framework to present different environment every round, which distinguishes our framework from more standard Blackwell approachability arguments. In fact, as we will see in Section 5 below, framework recovers fast Blackwell approachability
special case.
For our general subsequence regret algorithms, please see Appendix C Now, as a warm-up application of our framework, we directly instantiate it for the simplest case of obtaining O(VT) external regret.
Simple Learning From Expert Advice: External Regret In the classical experts learning setting Littlestone and Warmuth 1994], the Learner has a set of pure actions ("experts") A. At the outset of each round t E [T', the Learner chooses distribution over experts x' E A.A. The Adversary then comes up with a vector of losses yd = (ra)aed E [0, 1]4 corresponding to each expert. Next, the Learner samples a' z', and experiences loss corresponding to the expert she chose: ri-- The Learner also gets to observe the entire vector of losses p' for that round. The goal of the
5

---

Learner is to achieve sublinear external regret that is, to ensure that the difference between her cumulative loss and the loss of the best fixed expert in hindsight grows sublinearly with T: R (T= Eietry ra. minjjea Etefr r (
Theorem 3.1. Fix a finite pure action set A for the Learner and a time horizon 2 In |A]. Then, an instantiation of our framework's Algorithm B. lets the Learner achieve the following regret bounds:
ExT
R (x")) 4V Al: and R (x") (P)88TTh
Tin
LAI
with prob. 1 8.
Proof. We instantiate (the probabilistic version of) our framework (see Section B.2.1p
At all rounds, the Learner's pure action set is A, and the Adversary's strategy space is the convex and compact set [0. 1]14 from which each round's collection (ra) of all actions' losses is selected. Next, we define a Al-dimensionall loss function E = (E)), where each coordinate loss eg expresses the regret the Learner's chosen action a relative to action j E A:
((a,r") = =raa - -rr, for E A,r 10,1)
T' In [A], where w is the AMF value at round f. Using this AMF regret bound, we can bound the Learner's external regret as:
By Theorem B.I.
E
maxjEA EiETyy (a (() -iary S 4/
E
rul 73
E
E (E( ((dd'r")) UEA
max
<4 [E(T] why
[E|T]
thus remains to show that the AMF value w S 0 for all This holds, since if the Learner knew the Adversary's choice of losses (ra) beaA before round 6, then picking the action a E A with the smallest loss rá would get her 0 regret in that round. [ This gives the in-expectation regret bound; the bigh-probability bound follows in the same way from Theorem B.2
bound of /T In [.A] is optimal for external regret in the experts learning setting, and so serves to witness the optimality of our framework's general AMF regret bound in Theorem 2.1
In fact, the above instantiation of Algorithm B.T Littlestone and Warmuth 1994]: at each round the action a' is sampled with Pr(a" j]
| yields the classical Exponential Weights algorithm
exp
1| - for j E A. We denote this distribution by EW, (=' A(4).
Indeed, given the above defined loss ét, the Learner solves the following problem at each round:
x² E argmin max #ÉAA rfE[0,]] AI
E [r ry].
JEA
exp(1 الا 1
exp(
where x² Elea exp(1 Ei=l(r -r
E.eA exp( >> That is, the per-coordinate weights
(x))sed themselves form the Exponential Weights distribution with rate 7).
For any choice of r' by the Adversary, the quantity inside the expectation, (a,arr) r - rj. antisymmetric in a and j: that is, ra) = (,) Due to this antisymmetry, no mat- ter which r¹ gets selected by the Adversary. by playing ~ EW, ( the Learner obtains Ea.j~EW, (x [rd + = 0, thus achieving the value of the game. It is also easy to see that x' EW, , (I- is the unique choice of x' that guarantees nonnegative value, hence Algorithm B. when specialized to the external regret setting, is equivalent to the Exponential Weights Algorithm
*Formally, for any vector of actions' losses r', define a., == argmin rha and notice that
min max (a, r') S max é (a,1,"") max aEA
(rá: -r:) min rá min 0.
JEA
Henee, the AMF value is indeed nonpositive at each round: w/A sup min maxjed C(a,rr) ( 5
ee 0, I)IA asA

---

Multicalibration and Multicalibeating
We now apply our framework to derive an online contextual prediction algorithm which simulta- neously satisfies a (potentially very large) family of strong adversarial accuracy and calibration conditions. Namely, given an arbitrarily complex family 9 of subsets of the context space (we call them "groups". term from the fairness literature), the predictor will be both calibrated and accurate on each group g E G (that is, over those online rounds when the context belongs to g).
The accuracy benchmark that we aim to satisfy was recently proposed by Foster and Hart (2021) who called calibeating: given any collection FF of online forecasters, the goal is (intuitively) to "beat" the (squared) eπror of each f E F by at least the calibration score of f.
In Section 4.1
framework rederive the online multigroup calibration (known as multicalibration) algorithm of Gupta et al. [022). In Section [.2 we show that by appropriately augmenting the original collection of groups G, this algorithm will, in addition to multicalibration,
calibeat any family of predictors f E F on every group E G, which we call multicalibeatiigg
4.1 Multicalibration
Setting There is feature (or context) space @ encoding the set of possible feature vectors repre- senting individuals E O. There is also label space [0, 1]. At every round & [T]:
1. The Adversary announces a particular individual 6º O, whose label be predicted;
2. The Learner predicts label distribution x' over [0, 1]:
3. The Adversary observes x², and fixes the true label distribution y' over [0, 1]:
4. The (pure) guessed label a' x.' and the (pure) true label 8 y² sampled.
Objective: Multicalibration The Learner is initially given an arbitrary collection S 2 of protected population groups. Her goal, multicalibration, is empirical calibration not just marginally over the whole population, but also conditionally on individual membership each g E g. Formally, for any n 2 1 we let the n- n-bucketing of the label interval [o, 1] be its partition into subintervals [0, 1/m) ,
2/n, 1 - 1/m), [1 1/n, 1]. The 7th of these intervals (buckets) is denoted B Definition 4.1 ((a, M)-uuttiiaaliirtti with respect to G). Fix real a > 0 and an integer n 2 1. Given the transcript of the interaction {(a', b²) Heet; the Learner's 's sequence of guessed labels {a hemm (a, m-llticcaiibrtedd with respect the collection of groups 9 if:
Lo'es LoleB; (bb - a²) S for every group 9 E 9 and every bucket B', (for i E [n]).
T
Using our framework, we now derive the guarantee on a that matches that of Gupta et [002
Theorem 4.1 (Multicalibration). Fix a family of groups G, time horizon T Z In Gl), and any natural n, r 2 1. Then, our framework's 's Algorithm B.I can be instantiated as Algorithm D. to produce (a, n2) mej-multicalibrrted predictions w.r.t. G. where a satisfies (over transcript randomness):
E[a] S rm +4 (l)
and Pr Pr A m
+ 8/ +
(21mm) 21- (0.
Proof sketch; see Appendix for details. The adversary's 's strategy space will be y = 10, 1]. The learner will randomize over A, = f0, 1/(r)), 2/(rn)..... 1} for integer 2 1 (to ensure
continuity of the loss functions that we are about to define), i.e., her strategy space is = AAA
Loss functions: The definition of multicalibration consists of 2 constraints (one for each +
sign, group g, and bucket of the following form: + Lorce latEB; (bb (6)= S a.
at)
Thus, we define (for each t E [T], σ +1, g. and loss function over (a²,b*) A, y as: et (aa,(aa,,)) == a Loreg LatEB; (b' - a').
Now, defining 2 dimensional loss vector g for each I E max. ΣT et (a', < aT.
WEnl [T] recasts multicalibration in our framework as requiring that
7

---

Bounding the AMF regret: To bound the Seversary-Moves..oe
value with these loss functions, suppose the Adversary announces b' E [0. 1]. Then, we easily see that by (deterministically) responding with a² argm |b - al, for all o, g, t ( (²) S 2rm Hence,
wn1 sup min max We(o.1]='EAA oelml.0E..0((1.11 afrant [hig (a',
2mm for every E [2].
Now, for T 2 ln(2 the AMF regret RD maXicll, Ei= e li ,') Es nn, by framework's guarantees, satisfies E[R"] T/ over the Learner'
randomness. Since Et wn S T we get E[unKKEln.gEES.eE((1))) Ei= e (at, 2rn'
(at,b) f) S
T +4/Tln(2g 2m
This gives (a, n) -multicallbration with R[a] & 7 (f.m. 2rm + + +4TTm((2(gg))
=
1 2rn
+ 4v
In ln
The high-probability bound on a is obtained similarly.
Simplifying Learner's algorithm: To attain the AMF value w = 2rm at each round, our framework has the Learner solve a linear program (that encodes her minimax strategy). However, she can
obtain the almost optimal value +. without solving an LP: this observation gives Algorithm D.1 (see
Appendix D).
The guarantees on a only differ from optimal ones by replacing I.
Irn
4.2 Multicalibeating
We now give approach to "beating" arbitrary collections of online forecasters via online mul- ticalibration. The goal, called calibeating by Foster and Hart [02T]] who introduce the problem, is to make calibrated forecasts that are more accurate than each of an arbitrary set of forecasters, by exactly the calibration error in hindsight of that forecaster. They achieve optimal calibeating bounds for single forecaster, but their extension calibeating multiple forecasters incurs at least polynomial dependence on the number of forecasters. We achieve a logarithmic dependence on the number of forecasters. Additionally, we able to simultaneously calibeat forecasters all (big enough) subgroups in some set G. with still only logarithmic dependence on [9] and the number of forecasters in the group-wise convergence bound. We call this multicaliheating. We now give an overview of our setting, results, and techniques. For full details, see Appendix E
Setting The Learner (predictor a (E(T) and the Adversary (true labels b = HE()) interact the same way as in Section 4. but the Adversary additionally reveals to the Learner finite set of forecasters F. where each _ E IF is function f O > Dj. Here D, C [0, 1] is assumed to be a finite set of all possible forecasts that / makes: will characterize the level sets of f. We often suppress the dependence on the transcript, denoting I E Dy the forecast at time l.
The Learner's goal is to 'improve on" the forecasts of all f F,, for some suitable scoring of the predictions. We measure the Learner's 's and the forecasters' accuracy via the squared error, alternatively known as the Brier score.
Definition 4.2 (Brier Score). The Brier score of a forecaster J over all rounds L. E [T] is defined as: Bí 3(xT)) = Exerp -2)2.
The Brier score be decomposed into so-called calibration and refinement parts. The former quantifies the extent to which the predictor is calibrated, while the latter expresses the average amount of variance in predictions within every calibration bucket.
To define this decomposition, we need some extra notation. We denote by St the subsequence of Similarly, sdd (eliding (f) when clear from
days on which the Leamer's prediction is in bucket F context) denotes days on which forecaster f predicts d. We let (t) = S; n (f)) Finally, we use bars to indicate average predictions over given subsequences. For instance, a(S) is the Learner's average prediction over a given subsequence S.
Definition 4.3 (Calibration and Refinement). The calibration score K and refinement score R of forecaster I over the full transcript n² are defined as:
(-)))=- JED, -ueD, (dd(db(
dED, -
'Note that St depends implicitly the bucketing parameter and the transcript n..
8

---

Fact (Calibration-Refineee B (I") = KC' (²"(())()))))))))))(" + R (I")
Decomposition of Brier Score [DeGroot and Fienberg 1983
The goal of calibeating is to beat the forecaster's Brier score by an amount equal to its calibration score. Or equivalently, to attain a Brier score (almost) equal to the refinement score of the forecaster. Definition 4.4 (Calibeating). The Learner's predictor a is said r-calibeat a forecaster f if: B²(x") S R (T") +T.
We will now extend the definition of calibeating simultaneously along two natural directions. First, will want to calibeat multiple forecasters once. The second extension is that we will want to calibeat the forecasters not just overall, but also on each of the subsequences corresponding to cach "population group" 9 G in given family of subpopulations G 2
Definition 4.5 (Multicalibeating), Given family of forecasters F, groups G S 29, and mapping 3 F X 9 > R2,, the Learner's predictor a is an -m)d)mmulticlllibette if for every g 9: B ( ((:)r)))) I min {RS ( ((1(())))))))))))))))))))))))))) +
(
Note that [J),(0), B(f, == - multicclibbetting is equivalent r-calibeating a forecaster f.
We first show how to calibeat a single forecaster (Definition 4.4). The modularity of multicalibration will then let us easily extend this result multiple forecasters and population subgroups.
The idea is to show that if our predictor is multicalibrated with respect to the level sets of f, then we achieve calibeating. Höbert-Johnson al. (2018) give a similar bound in the batch setting. We denote the collection level sets of f as: S(f) == (0 E θ f(0) = dddED,,
Theorem 4.2 (Calibeating One Forecaster). Suppose that the Learner's predictions a are (a, n)- multicalibrated on the collection of groups S(f) U (O). Then the Learner is na..nn-calbbbatee on O and she (on() - 2) + 2. -calibeatss forecaster s.
Proof sketch. We show that a has small calibration score, and refinement score close to that of f.
Step 1: Replace B with a surrogate Brier score B Consider a (pseudo-)predictor ā given by ā' - .....)) for E [T] (where ia is the bucket of at). That is, whenever a' E B a' predicts the average of over all such rounds & [T] that E B This is a pseudo-pres preuuddreee,oor,, as the bucket averages of are unknown until after round T. Thus, â has precisely n level sets, unlike a. Now, we define B, KC, R. to be the Brier, calibration, and refinement scores of a. We can show 1 < B,, + l/n, allowing us to switch to bounding the more manageable Brier loss B KCa + Rg
Step 2: Bound the surrogate calibration score Kg Since the Learner is (a, -callbbratee on the domain θ the calibration error per level set is at most a. There are level sets, so IC; S an.
Step& 3: Bound the surrogate refinement score R We connect R! and R via a joint refinement score: R which measures the average variance of the partition generated by all intersections of the level sets of a and f. The finer the partition, the smaller the refinement score, so R > R/xe, Next, informally, multicalibration ensures that a has already "captured" most of the variance explained by f. Therefore, refining a's level sets by does little to reduce variance. More precisely, we show that R < R xa an () + 1) + Combining with our previous inequality, we have: R. < R + anl + +
Combining the above, we get: 8
< R
Kg (R' +
am 1.
Calibeating many forecasters Generalizing the above construction, we can easily calibeat any collection of forecasters F on the entire context space O: it suffices to ask for multicalibration with respect the level sets of all forecasters, i.e. (Ure=S(f)) to each fi the only degradation in the guarantees will come in the form of larger a, since asking for multicalibration with respect to more groups than before. But this effect will be small, since a depends on the number of required groups (g'l as (( (g'). See Corollary E.2
(0}. Theorem 4.2 applies separately
However, to fully satisfy Definition 4.5 of multicalibeating, we need to calibeat all J F. on all
groups g E G in a given collection requiring multicalibration with respect to all pairwise intersections of the forecasters' level sets with
20. For that, we simply extend the above construction by

---

the groups g E G. By further augmenting this collection with the protected groups & themselves, we finally achieve our ultimate goal: simultaneous multicalibeating and multicalibration.
Theorem 4.3 (Multicalibeating + Multicalibration). Let 9 C 20, and F some set of forecasters
f - Dj. The multicalibration algorithm on g' := (Urerlans: (g,S) E E S(U) ug
with parameters n, 2 1, after T rounds, attains expected (F,9,3) (am.)))mmmiccaabbattnnn where:
B[3(f. 9) = 2 + r-laia)/T + +n((1D)+ StaiepT In (2 + Σ,1D,1) 9f
1Dyl+2
while maintaining (a, momtiicccaiali on G, with: E[a] S 44-14/ 7 IDD1))
1 rn
In particular, for any group g occurring more than 7 of the time, we asymptotically converge to =calibbetting as T + oo, thus combining the goals of online multicalibration and multigroup regret.
5 Polytope Blackwell Approachability
Consider a setting where the Learner and the Adversary are playing repeated game with vector- valued payoffs, in which the Learner always goes first and aims to force the average payoff over the entire interaction approach given convex set. Blackwell's Theorem [1956] states that a convex set is upproachable if and only if it is response- satisfaable (roughly. for any choice of the Adversary. the Learner has response forcing the one-round payoff inside the convex set). The rate of approachability typically depends on the dimension of the payoff vectors.
This is specialization of our framework to the case of fixed environment across rounds. Thus dimension-iudepeeddnntn rate bound in the fundamental case where the approachable set is convex polytope. Our bound is only logarithmic in the polytope's 's number of facets, and is achievable via an efficient convex-programming based algorithm.
framework can be used to obtain a dimension independent
Let us formalize our setting. In rounds t 1,2..... ... the Learner and the Adversary play a repeated game. Their respective pure strategy sets are AA and V. where A is a finite set and y S R (for some integer m 1) is convex and compact. The game's utility function is X-dimensional (for some integer 2 1), continuous, concave in the second argument, and is denoted by u A x y - R². At each round f, the Learner plays mixed strategy xf E AA, the Adversary responds with some y" E V, and the Learner then samples a pure action a' ~ x This gives rise to the utility vector u(aa, (.) The average play up to any round 2 1 is then defined as a' = =
= u(a","")
The target convex set that the Learner wants to approach is a polytope P(H) C TR,,,, defined as the intersection of finite collection of halfspaces H (ha.,), where for any given a E RA, E we denote h = {ar R : (a, x) - 3 S 0}. Finally, by way of normalization, consider any two dual norms ||- 1pp and ||- llg. We require, first, that ||a||p S 1 and [.3] < 1 for each halfspace ha,8 E H; and second, that the payoffs be in the || Ilg-unit ball: [|u[a, x)ll, S 1 for a E A. y E y.
Theorem 5.1 (Polytope Blackwell Approachability. Suppose the target Convex polytope P(H) is response-sation satisfiable, in the sense that for any Adversary action y E Y, the Learner has a mixed response E AA that places the expected payoff inside P(H): that is, Eeaz [u(a, y}1 E P(H)).
Then, P(H) is approachable, both in expectation and with high probability with respect to the transcript of the interaction. Namely, the Learner has an efficient convex programming based algorithm which simultaneously offers both following guarantees (see Appendix For the proof):
1. For any margin E O, the average play ut up any round E maaxb,,oeH (fa, ut) - B)] Se.
>
(4ln/9) will satisfy
2. For any 8 (0,1), the average play it up to any round 2 In [7]] will satisfy max ((a, u²) 3) 16/ + In
[M4] [
with probability at least 8.
(g)) denotes the subsequence of days on which group g occurs, suppressing dependence on transcript.
10

---

References
Dmitry Adamskiy, Wouter M Koolen, Alexey Cherov, and Vladimir Vovk. A closer look at adaptive regret. In International Conference Algorithmic Learning Theory, pages 290-304. Springer, 2012.
Yossi Azar, Uriel Felge, Michal Feldman, and Moshe Tennenholtz. Sequential decision making with vector outcomes. In Proceedings of the 5th conference on Innovations in Theoretical Computer Science, pages 195-206 2014.
David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathe- matics, 6(1):1-8, 1956.
Avrim Blum. Empirical support for winnow and scheduling domain. Machine Learning, 26(1):5-23 1997.
algorithms: Results on calendar
Avrim Blum and Thodoris Lykouris. Advancing subgroup fairness via sleeping experts. In Innovations in Theoretical Computer Science Conference (ITCS), volume 11, 2020.
Avrim Blum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
Morris H. DeGroot and Stephen E. Fienberg. The comparison and evaluation of forecasters. The Statistician, 32:12-22, 1983.
Nadejda Drenska and Robert V Kohn. Prediction with expert advice: A pde perspective. Journal of Nonlinear Science, 30(1):137-173, 202..
Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009.
Dean P Foster and Sergiu Hart. "calibeating"" Beating forecasters at their own game.
https
// /www.mm www.ma.hiin muj..uji.aaa ac ht/"aartt/ppaapaeeeeaaaeaaaaaaaa taart/pppers/aee catpbaalllbbbccbaa beatbeet., pdf 2021.
Dean P Foster and Rakesh V Vohra. Asymptotic calibration. Biometrika, 85(2):379 -3000 1998.
Yoav Freund, Robert E Schapire, Yoram Singer, and Manfred K Warmuth. Using and combining predictors that specialize. In Proceedings of the twenty-ninth annual ACM symposium Theory of computing, pages 334-343, 1997.
Drew Fudenberg and David K Levine. An easier way calibrate. Games and Economic Behavior, 29(1-2):131-137, 1999.
Ira Globus-Harris, Michael Kearns, and Aaron Roth. Beyond the frontier: Faimess without accuracy loss. arXiv preprint 2xxv:2201.10008. 2022.
Amy Greenwald and Amir Jafari. general class of no-regret learning algorithms and game-theoretic equilibria. In Learning theory and kernel machines, pages 2-12. Springer, 2003.
Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, and Aaron Roth. Online Multivalid Learning: Mcans, Moments, and Prediction Intervals. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). pages -2:1-8 2022.
Sergiu Hart. Calibrated forecasts: The minimax proof, 2020. URL http:t/////ww hwtp://wwww..aa....mm.oo..mm. wuj..uijii..... il/ petrt//apprs/cclla wwtps//aaabmmmmm..a.mmmamaaamaam .pdff
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica,
2000.
Elad Hazan and Comandur Seshadhri. Efficient learning algorithms for changing environments. In
Proceedings of the 26th Annual International Conference on Machine Learning, pages 393-400, 2009.
11

---

Ursula Häbert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Cali- bration for the compuuaaionall--ddenffabb masses. International Conference on Machine Learning, pages 1939-1948, 1948. PMIR, 2018.
Thomas Kesselheim and Sahil Singla. Online learning with vector costs and bandits with knapsacks. In Conference on Learning Theory, pages 2286-2305. PMLR, 2020.
Robert Kleinberg, Alexandru Niculescu- and Yogeshwer Sharma. Regret bounds for sleeping experts and bandits. Machine Learning, 80(2):245-273 2010.
Vladimir A Kobzar, Robert V Kohn, and Zhilei Wang. New potential based bounds for prediction with expert advice. In Conference on Learning Theory, pages 2370-2400 PMLR, 2020.
Ehud Lehrer. wide range no-regret theorem. Games and Economic Behavior, 42(1):101-115, 2003.
Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. Information and computation, 108(2):212 1994.
Shie Mannor, Vianney Perchet, and Gilles Stoltz. Approachability in unknown games: Online learning meets multi-objective optimization. In Conference on Learning Theory, pages 339-355. PMIR, 2014a.
Shie Mannor, Vianney Perchet, and Gilles Stoltz. Set-valued approachability and online learning with partial monitoring. The Journal of Machine Learning Research, 15(1):3247-3295, 2014b.
Vianney Perchet. Exponential weight approachability. applications to calibration and regret mini- mization. Dynamic Games and Applications, 5(1):136-153, 2015.
Vianney Perchet and Shie Mannor. Approachability. fast and slow. In Conference on Learning Theory, pages 478-488. PMLR. 2013.
T.E.S. Raghavan. Zero-sum two-person games. In R.J. Aumann and S. Hart, editors, Handbook of Game Theory with Economic Applications. volume Handbook of Game Theory with Economic Applications, chapter 20, pages 735-768. Elsevier, 1994. URL http::://ees::..rttt repec org/h. h/ eee/ beeegamchp/22-0 html
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability. Advances Neural Information Processing Systems, 13.1984-1992, 2010.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Beyond regret. In Proceedings of the 24th Anmual Conference on Learning Theory, pages 359-594. JMLR Workshop and Conference Proceedings, 2011.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Relax and randomize: from value to algorithms. In Proceedings of the 25th International Conference on Neural Information Processing Eistems-Volume 2, pages 2141-2149, 2012.
Guy N Rothblum and Gal Yona. arXiv:2/05.09988 2021.
Multi-group agnostic pac learnability.
arXiv preprint
Volodimir Vovk. Aggregating strategies. Proc. of Computational Learning Theory, 1990, 1990.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
12

---

(c) Did you discuss any potential negative societal impacts of your work? [N/A] This concern not directly applicable here: this a theory paper whose aim is to present unifying rigorous framework encompassing many disparate, both novel and classical, theoretical results.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Full proofs of all results are the Appendix, and the main part contains sketches of some of them.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [N/A]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "oJnL6CkRtzI", "reviewer": "Reviewer_wRUm", "summary": "This paper consider an online adversarial multiobjective minimax optimization scenario, where at each round t, the adversary chooses an environment defined by a convex compact action set $\\mathcal{X}^t$ for the learner, a convex compact action set $\\mathcal{Y}^t$, then learner choose action $x_t$ and adversary chooses action $y_t$. The d dimensional loss function is defined such that each of its coordinate is convex in x and concave in y. We use the maximum of these coordinate as the final loss, i.e., $\\max_{j\\in [d]}\\ell_j^t(x_t,y_t)$. The authors proposed an online exponential multiplicative algorithm to solve this minimax problem and show that it achieve sub-linear regret bound, i.e., $\\sqrt{T}$. They further show a direct application of their algorithm: Multicalibration and Multicalibeating.\n", "questions": "I think there are some previous works in Multicalibration and Multicalibeating, so can authors compare their algorithm with others, what is the advantage of their method?", "limitations": "I did not see negative societal impact of this work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper consider a novel online learning scenario, where the objective is the maximum coordinate of a vector loss, and borrow the idea from bandit learning to solve it. The proof looks good to me. They also give applications of their framework in fairness field. However, I am not familiar with fairness including Multicalibration and Multicalibeating, so I cannot judge the value of their application.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HbgvZ59lU_", "reviewer": "Reviewer_mPvY", "summary": "The paper makes several theoretical contributions to multi-objective online learning and its applications. First, it proposes a new performance metric called \"Adversary-Moves-First\" regret, and a novel algorithm to control it via solving a convex-concave problem in each round. This general framework leads to three interesting applications:\n\n1. For the expert problem, it yields an algorithm with sublinear \"subsequence regret\", which subsumes many well-known performance metrics. Moreover, special versions of this algorithm recover classical solutions designed from first principles, like EW. \n2. It leads to an approachability algorithm for polytopes, whose approaching rate depends logarithmically on the amount of constraints. This recovers a strong result from the approachability literature. \n3. For the calibration problem, it improves a recent result on \"calibeating\": the bound depends logarithmically, rather than polynomially, on the number of forecasters. Moreover, this can be combined with the \"multicalibration\" task to achieve a stronger goal called \"multicalibeating\". The proof strategy improves an existing level set analysis. ", "questions": "1. There seems to be an intriguing connection between the proposed multi-objective setting and the standard expert problem (Appendix F.1), and this intuitive similarity extends to the algorithms: Similar to EW, the analysis in Section 2.2 also argues that the log-sum-exp potential does not grow too fast, despite a quite significant deviation in Lemma 2.3. It might be helpful to add some discussions in Section 2.2 and emphasize the novelty of this reasoning compared to EW. \n2. From a somewhat aesthetic point of view, although the EW algorithm is recovered in Appendix F.1, the constant $4$ in the bound is not the asymptotically optimal one achieved by EW ($1/\\sqrt{2}$). Improving this constant might make the general framework even more appealing. \n3. Based on the connection to the expert problem, I think the proposed general algorithm might be interpreted as a regret-computation tradeoff. With a known $T$, we can use dynamic programming to obtain the absolutely optimal strategy for the expert problem. Apparently this is not computationally feasible, therefore EW serves as a proximal solution, which is fast and asymptotically optimal.\\\nAs for the multi-objective setting, if we fix the domains then DP can still be applied to obtain the absolutely optimal strategy. The proposed algorithm might be seen as an approximation of it, which only requires solving a stage-wise minimax problem online instead of a global one offline. \n4. There is a possibly interesting future direction, related to [Rakhlin et al., 2012] cited in Appendix A. The idea of [Rakhlin et al., 2012] is that we can first write down the conditional value function achieved by DP, then try to relax (upperbound) it by a tractable potential function. This argument has been improved recently [Drenska and Kohn, 2020; Kobzar et al., 2020], where potential functions are more easily obtained by solving a PDE. For the expert problem with few experts, this yields tighter bounds compared to EW. Also, it allows general terminal conditions: instead of $\\max_j R^T_j$, we can bound $\\phi(R^T_1,\\ldots,R^T_d)$ for more general $\\phi$. \\\nNot sure if this PDE approach extends to the setting of the present paper, but if it does, then the generalized terminal condition might also be useful in related applications, e.g., calibration, approachability, etc. \\\n\\\nDrenska, Nadejda, and Robert V. Kohn. \"Prediction with expert advice: A PDE perspective.\" Journal of Nonlinear Science 30.1 (2020): 137-173.\\\nKobzar, Vladimir A., Robert V. Kohn, and Zhilei Wang. \"New potential-based bounds for prediction with expert advice.\" Conference on Learning Theory. PMLR, 2020.\n5. Some minor suggestions on organization. Maybe it's just a personal preference, I feel the last two applications (No-regret expert & approachability) are easier to read compared to calibration, therefore might be moved forward (after Section 2) for better clarity. Section 3.2 (multicalibeating) is quite dense, so I suggest shortening it using high-level arguments rather than precise arguments (details are in the appendix anyway). In particular, the proof sketch of Theorem 3.2 and the statement of Theorem 3.3 (it's complete but really hard to parse). \n6. Very minor:\n- The setting of multicalibeating involves level sets (Line 240), but it's not defined until Line 275. \n- The predictor for multicalibeating is denoted as $a$. Instead, $\\mathbb{A}$ or $\\mathcal{A}$ might be clearer?\n- Line 91, $2^\\theta\\rightarrow 2^\\Theta$.", "limitations": "Limitations are truthfully stated in the paper. This is a theoretical work, therefore the societal impact questions are not applicable.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a strong submission in my opinion, and overall a pleasant read.\n\nStrengths: \n1. The setting of the framework is simple but general. The proposed solution has a EW flavor but differs in some substantial ways that I am not aware of in existing works. This could be interesting to a large subset of the community. In particular, the algorithm \"upweights\" the coordinates with higher historical losses in the resulting convex-concave problem, which is natural but insightful. \n2. The paper provides an extensive discussion on existing works. Contributions are clear, and limitations are truthfully presented. \n3. Technical extensions and applications are thoroughly developed, with clear proofs. \n4. The paper is well-written in general. It is a dense paper, but the authors delivered the key idea quite clearly. \n\nWeaknesses: \nI don't have any major complaints on the paper; its current form is already good. Some minor suggestions are provided in the following. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0oirysySE9G", "reviewer": "Reviewer_x4kU", "summary": "This paper introduces a simple and general online learning framework with adversary plays. And the author shows how to (multi)calibeat and multicalibrate at the same time. ", "questions": "Should you add some experiments to the main paper?", "limitations": "line 228, introduces.\n", "rating": 9, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Generally, this work is well-written and solid. \nMy main concern is that this paper seems to be too heavy for a conference paper. It includes too many ingredients such as softmax, the main conclusion, applications, and extensions. \nI guess they should separate it into several papers and only focus on one term each time.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept