Improved and Oracle-Efficient Online $\ell_1$-Multicalibration
Authors: Rohan Ghuge
Vidya Muthukumar
Sahil Singla
Venue: ICML 2025 poster (2025)
Keywords: online multicalibration
online learning
oracle-efficient algorithms
Primary area: general_machine_learning->online_learning_active_learning_and_bandits

Abstract: We study *online multicalibration*, a framework for ensuring calibrated predictions across multiple groups in adversarial settings, across $T$ rounds. Although online calibration is typically studied in the $\ell_1$ norm, prior approaches to online multicalibration have taken the indirect approach of obtaining rates in other norms (such as $\ell_2$ and $\ell_{\infty}$) and then transferred these guarantees to $\ell_1$  at additional loss. In contrast, we propose a direct method that achieves improved  and oracle-efficient rates of $\widetilde{\mathcal{O}}(T^{-1/3})$ and $\widetilde{\mathcal{O}}(T^{-1/4})$ respectively, for online $\ell_1$-multicalibration. Our key insight is a novel reduction of online $\ell_1$-multicalibration to an online learning problem with product-based rewards, which we refer to as *online linear-product optimization* ($\mathtt{OLPO}$). 

To obtain the improved rate of $\widetilde{\mathcal{O}}(T^{-1/3})$, we introduce a linearization of $\mathtt{OLPO}$ and design a no-regret algorithm for this linearized problem. Although this method guarantees the desired sublinear rate (nearly matching the best rate for online calibration), it is computationally expensive when the group family $\mathcal{H}$ is large or infinite, since it enumerates all possible groups. To address scalability, we propose a second approach to $\mathtt{OLPO}$  that makes only a polynomial number of calls to an offline optimization (*multicalibration evaluation*) oracle, resulting in *oracle-efficient* online $\ell_1$-multicalibration with a corresponding rate of $\widetilde{\mathcal{O}}(T^{-1/4})$. Our framework also extends to certain infinite families of groups (e.g., all linear functions on the context space) by exploiting a $1$-Lipschitz property of the $\ell_1$-multicalibration error with respect to $\mathcal{H}$.

Improved and Oracle-Efficient Online 4-Muutticlibrraton
Rohan Ghuge'
Vidya Muthukumar
Sahil Singla
Abstract
1. Introduction
We study online multicalibration, framework for ensuring calibrated predictions across multi- ple groups in adversarial settings, across 7 rounds. Although online calibration is typically studied in the & norm, prior approaches to online mul- ticalibration have taken the indirect approach of obtaining rates in other norms (such as l and ) and then transferred these guarantees to & at additional loss. In contrast, we propose di- rect method that achieves improved and oracle- efficient rates of 1/3) and O(T-1/4) re- spectively, for online f--mutiicllibration Our key insight a novel reduction of online 41- multicalibration an online learning problem with product-basee rewards, which we refer to as online linear-produce optimization (OLPO).
Machine learning algorithms, powered by advances in data availability and model development, play a crucial role in decision-making across domains such healthcare diagnos- tics, recidivism risk assessment, and loan approvals. This work focuses on forecasting algorithms that predict, say, the probability of binary outcomes (such as patient's sever- ity or loan repayment) based on observable features z, in online settings where predictions are made as data is col- lected. A key metric used to evaluate the performance of such probability forecasters calibration (Dawid, 1982). Roughly, it says that for any candidate prediction p [o. 1]. the fraction of forecasts with prediction p should converge to In 1998, the seminal work of Foster & Vohra (1998) showed a bound of O(T-1/3) for online calibration in the & metric. Since then, this ( 1/3) bound has been re- proved through insightful alternative approaches (Abernethy et al., 2011; 1; Hart, 2022). However, improving this bound is challenging open problem that has only recently seen some progress (Dagan et al., 2025; Qiao & Valiant, 2021).
To obtain the improved rate of ((T3)/3), we introduce a linearization of OLPO and design a no-regret algorithm for this linearized problem. Although this method guarantees the desired sub- linear rate (nearly matching the best rate for online calibration). it computationally expensive when the group family H is large infinite, since it enumerates all possible groups. To address scal- ability, we propose a second approach to OLPO that makes only a polynomial number of calls to an offline optimization (multicalibratiinn evalua- tion) oracle, resulting in oracle- crall-efffcieen online f ei-multicalibration with a rate of OTT-1/4). Our framework also extends certain infinite families of groups (e.g., all linear functions on the context space) by exploiting a 1-Lipschitz property of the E fi-multicalibration error with respect to H.
Despite its popularity, calibration has a major limitation: calibrated predictions may perform poorly on specific sub- populations in the data, identifiable through contextual fea- tures such as gender, race, and age. To address this issue, Hébert-Johnson al. (2018) proposed multicalibration, framework designed to address discrimination arising from data in the batch setting. Informally, multicalibration is requirement that the forecasts be statistically unbiased con- ditional both on its own prediction and on membership in any one of a large collection of intersecting subsets of the data space H. Multicalibration and its variants have been an active area of research (see, e.g., Mlobus-Harris (2023); Gupta al. (2022); Jung et al. (2021); ;; Kim et al. (2019; 2022)). Multicalibration has also found applications in omniprediction (Gopalan et al., 2022; 2023), concept that asks for single prediction which can be simultancously used to optimize a large number of loss functions such that it is competitive with some hypothesis class H. Approxi- mately multicalibrated models in the l metric turn out to automatically be omnipredictors, in both the batch (Gopalan et al., 2022) and online (Garg et al., 2024) settings.
al.
HH. Milton Stewart School of Industrial and Systems Engi- neering/ Algorithms and Randomness Center, Georgia Institute of Technology, Atlanta, USA. "School of Electrical and Com- puter Engineering/II. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology. Atlanta, USA. 'School of Computer Science, Georgia Institute of Tech- nology, Atlanta, GA, USA.. Correspondence to: Rohan Ghuge <rghuge3 gatech.edu>>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
We are especially focused on online multicalibration (Garg et al., 2024; Gupta et al., 2022), which naturally generalizes

---

Improved and Oracle-Efficient Online & Ei-Multicalibration
the fundamental problem of sequential calibration. Existing approaches first provide multicalibration guarantees in the (weaker) foo or i2 metric, and then transfer these guarantees to the 41 metric at additional and possibly superfluous loss. The resulting rates for online & --multicalibration are signifi- cantly weaker than those for online calibration. A second drawback is that the runtime of most existing algorithms (with the exception of Garg et al. (2024), which we dis- cuss later) for online multicalibration is typically linear in |H] (Gupta et al., 2022; Lee et al., 2022). These algorithms are hence inefficient in even simple practical scenarios (e-g- linear functions in d dimensions) where the hypothesis class is usually exponential in relevant problem parameters.
throughout the paper. For n E N, we use [n] to denote the All of our algorithms will con- sider a discretized set of forecasts P ;= [0, m. ......, 1} for some discretization parameter m E N. We use M to denote the size of P, i.e., M = |P] = m + 1.
set of integers (1,...,,7) n2).
1
Online prediction proceeds in rounds indexed by & E [T], for given horizon of length T. In each round, the interaction between a learner and an adversary proceeds as follows:
The adversary selects a context x, E X and corre- sponding label y/ E y.
2. The learner receives x,, but no information about y/a is revealed.
In light of these considerations, the main motivating ques-
3. The learner selects a distribution w, and outputs Pa E
tion of our work is the following:
P sampled according to W.-
4. The learner observes yt-
Is there an online (1 m-mullicaaibration algorithm that guar- antees O(T-1/3) error? Can design "oracle-eficient" algorithms for online & i-maliicalibration?
The learner's s interaction with the adversary results in his- tory wy = (x+, St. Pt ) We make no assumptions about the adversary; however, the learner is allowed to use ran- domness in making predictions. This induces a probability distribution over transcripts, and our goal is to design online algorithms that have low online & E1-multicalibration error in expectation, which is defined as follows:
In this work, we make progress towards answering both these questions. We propose a method that achieves improved and oracle-efficient rates of ((T))/3) and Ö(r-1/4), respectieel. for online L f1-multicalibratio. Our key insight is a novel reduction of online & m--ulticcalibrttion to an online learning problem with product- rewards, which we refer as online Sinear-produce optimization (OLPO). To obtain the improved rate of O(T-)/3), we in- troduce a linearization of OLPO and design no-regret al- gorithm for this linearized problem. Although this method guarantees the desired ((33 rate, it becomes computa- tionally expensive when the group family H is large or infi- nite, since it enumerates all possible groups. To address scal- ability, we propose a second approach to OLPO that makes only a single call per round an offline optimization (mul- ticalibration evaluation) oracle, resulting in pracle-efficient online fy-multicalibratin
Definition 1.1 (6 MG-Multicalibrrtioon Error). Given a tran- script nT, a function h E H. we define the learner's 's online e--mutticalibratin error with respect to h as
((=r,))==- == Epep 7 E p)) Mxx)) - (yt - pt)
where we define S(Tr.p) f+ : Pt = p}. Finally, we define f f--mulicalibration error with respect to the family H as K (TT, H) == maXjeH K (TT,A) h).
[T]
From here on, online multicalibration error will, by default, refer to online f--muticallibration error. When clear from context, we will drop मं and use K(h) or K K(H) to denote the leamer's online multicalibration error.
with rate of O(74//4). Our framework also extends to certain infinite families of groups (e.g., all linear functions on the context space) by exploiting a 1-Lipschitz property of the ε m-uulticalibration error with respect to H. We discuss the basic setup of online multical- ibration, our results and our techniques in the rest of this section. Due space limitations, we defer our treatment of related work to Appendix A.
1.2. Our Results
Our first main result establishes an O(T-1/3) rate for online E f-mmlticalibration when the hypothesis class H. is finite.
Theorem 1.2. There is an algorithm that achieves online E m-muliicalibration error with respect to H with
1.1. Online Multicalibration
E[K(TT, H4) S (BT-1// (OST-1/8/oo(667 /Tog(67
We now formally define the problem of online l1- multicalibration (Garg et al., 2024; Gupta et al., 2022). Let X' denote the context space and y = J0. 1] denote the label domain, which we assume to be one-dimensional. Let H denote a collection of real- valued functions h : X + R. We use HB = (h- : maxxex [x(x)] < B} to denote the set of functions with maximum absolute value on the context space bounded by B, and make the mild assumption that H. C HB
The running time of this algorithm is linear in [7] and polynomial in T.
This improves over an Ö(T-1/1) bound obtained in Gupta et al. (2022) via online Loo muutiiiialliirian (without need- ing to go through "bucketed" predictions), and nearly matches the best known bound for online calibration (Dagan et al., 2025).
2

---

Improved and Oracle-Efficiet Online & 2/-Multicalibration
Comparison to Noarov et al. (2025). After the initial submission of this work, it has been brought to our attention that similar bound for online <--mutticalibration for finite hypothesis class H. could be derived from Theorem 3.4 of Noarov et al. (2025). We note that their algorithmic frame- work is quite different from ours, despite both works using an expert routine. In particular, their framework requires a small-loss regret bound to get the result, while a worst-case regret bound suffices in ours. Additionally, our algorithm is simpler (e.g. not requiring the solution of any min-max op- timization problem) and proceeds through a novel reduction to the OLPO problem (defined in Section 2.1). We believe that this reduction is of independent interest as it facilitates the oracle-efficient results in a more natural and modular way.
Definition 1.6 (Offline Oracle). We receive sequence of contexts {x=)a== with corresponding reward vectors { {fe) coefficients {k=) and an error parameter > O. The offline oracle returns solution (h", 00) E H. x t that approximately solves, up to an additive error 6,
maNKEH,PE { Ei Ns (0,)(x,) f.) }
Given such an oracle, our main result is the following.
Theorem 1.7. There is an algorithm that achieves oracle-
efficient online E f1mmulicallbrrtiin with respect to a binary- valued H. : X + {0, 1} with
E[K(TT H)] - ((r-V/A/lo((T)) (T)(
Although Theorem 1.2 obtains O(T-1/3) rate for online ( (t-multicalibration, it does not apply to infinite-sized hy- pothesis class H. To address this, our next result obtains bounds in terms of the "covering number" of H.
under the assumptions of either transductive or sufficiently separated contexts (Syrgkanis et al., 2016) (see Section 4.2 for formal definitions). Moreover, this algorithm requires only a single call to the offline oracle per round.
This result improves over the ((T-1/8) bound obtained in Garg et al. (2024), who also provide oracle-efficiee multicalibration algorithm but require access to an online regression oracle. Our oracle is equivalent to evaluating the online ε i--multicalibration error for sequence of prediction in a one-shot manner - essentially, an offline oracle. Of- fline oracles are considered to be easier than online oracles. The assumptions in Theorem 1.7 on contexts and of binary- valued H are required make the oracle implementable while maintaining the "stability" of the online algorithm, and are also commonly used in oracle-efficient online learn- ing (Dudík et al., 2020; Syrgkanis et al., 2016). We also provide a generic "black-box" bound in Theorem 4.4.
Definition 1.3 (3-cover in L metric, Bronshtein (1976)). For any function class H. finite subset of functions Ha = (h"....,he 3 S H is a 3-cover with respect to the Los metric if for every h E H. there exists some i E [N] such that maxxex [h(x)- h h2())] $ B.
Let Hi denote a smallest possible 8-cover for H. We show that the online multicalibration error for infinite-sized hy- pothesis class H can be bounded in terms of [Hel.
Theorem 1.4. There is an algorithm that achieves online l mumulaicalibrattinn error with respect to H with
([K H)] S (BT-1/3 Vlg 6T H4l)) + B.
1.3. Our Techniques
The running time of this algorithm is linear in HHl and polynomial in T.
At the heart of our approach is a novel reduction of on- line m1-mltticalibration to an online learning problem with product-based rewards, which we refer to as online linear- product optimization (OLPO). In particular, we show that any learning algorithm for OLPO with regret Ry (C: H) can be efficiently transformed into an algorithm with online f1- multicalibration error (C H)), up to a small error (see Theorem 2. This reduction is crucial in both our improved and oracle-efficient rates for online L m-multicalibration.
As a consequence of this result, we obtain immediate ap- plications to polynomial regression and bounded, Lipschitz convex functions (see Section 3.2 for details). We state one corollary here for the class of bounded linear functions.
Corollary 1.5. Suppose X' = [0, 1]d and H. = {h E B} is the class of bounded linear functions. Then, there is an algorithm with runtime O(B ())) that achieves online e iaaultiiaalibration error with respect to H with
Rdd :1bbla <
Improved Rates. Our first set of results establish the best-known information-thhoreti rates for online f-- multicalibration, beginning with the case of finite-sized hypothesis class. We achieve this by designing a no-regret algorithm for OLPO. The main challenge in solving OLPO is that it is unclear apriori how to perform online optimization on a reward function that involves a product of variables. To address this, we define an online linear optimization problem in a nigher-dimensione space and show that OLPO reduces to this problem, thereby effectively linearizing the
EJK(TT (TT, H)] = O (Bd' log( IT))
Next, we give an "oracle-efficien" algorithm for online L1- multicalibration for large hypothesis class H. Our earlier algorithms need to enumerate over H. or its 8-cover, both of which are often exponentially large. We show how this can be avoided using the following offline oracle.
3

---

Improved and Oracle-Efficient Online Ei-Multicalibration
reward structure-an the cost of enumerating over all h E H. We denote this new problem Lin-OLPO (or linearized online linear-product optimization problem). The reduction from OLPO to Lin-OLPO introduces two issues. The first issue is that we need to ensure that the best fixed actions in OLPO and Lin-OLPO remain consistent. To address this, we introduce a specific mixed norm and restrict the set of actions of Lin-OLPO to a unit ball in this mixed norm. The second issue is that the expanded decision space may in- troduce better actions for Lin-OLPO that are not valid in OLPO. To resolve this, we appropriately scale decisions as we translate them from Lin-OLPO to OLPO, ensuring consis- tency between the action spaces of OLPO and Lin-OLPO (see Lemma 3.2).
structure. Specifically, it suffices to restrict decisions for OLPO to the Boolean hypercube; i.e., {+1]M us to ultimately prove Theorem 1.7.
1 This allows
2. Reducing Multicalibration to OLPO
In this section, we show how to efficiently reduce online multicalibration to online learning problem with product- based rewards, which we refer to online linear-product optimization (OLPO), and define next. This reduction will be crucial to our improved rates for online multicalibration. We note that there is precedent for connections between calibration and regret; in particular, (Abernethy et al., 2011) provided simpler reduction between calibration and online linear optimization.
Next, we design no-regret algorithm for Lin-OLPO with the mixed- norm constraint that carefully combines two com- no-regret online linear optimization (OLO) algorithm (e.g., online gradient de- scent), and (ii) a reward-maximizing no-regret algorithm for the experts setting (e.g., multiplicative weights update). Our approach runs [H| instances of the OLO algorithm in parallel. Each OLO instance executes the action opti- mal for calibration with respect to a specific hypothesis h E H. Meanwhile, the experts algorithm identifies hy- potheses that appear "more difficult" with respect to cali- bration
2.1. Online Linear-Product Optimization
ponents: (i) a wwward-mxxiiin/
We formally define the online linear-product optimization problem (OLPO). Let X' denote the context space and let hypothesis class H C Hy be a collection of B-bounded real-valued functions h X + TR. Let B S R.M denote
the unit cube, i.c., Bx = {0 E IR MMM, ||0| S 1}. The set H x B&x will denote an action set. In each round E [7]:
1. Learner plays function h2 E H. and vector 0, E B Bo..
difficulty is measured using the cu- mulative reward of the corresponding OLO algorithm. We obtain the final guarantee by analyzing the regret of this algorithm (see Lemma 3.3) and combining it with the two earlier reductions.
2. Adversary then reveals a context x; and a reward vector
ft E RM
3. Learner then receives reward (0:, h0,,1((x) fi).
To transfer these bounds to an infinite-sized hypothesis class H. (Theorem 1.4), we first show that online multicalibration error is 1-L.ipschitz with respect to H. Then, we construct an appropriate covering of the hypothesis class H. and appeal to online & i--muliccalibration rates for finite H.
Note that this is not a standard online linear optimiza- tion problem since it involves a product of variables. We will use L denote a generic algorithm for OLPO. This algorithm takes as input a sequence of vectors (x1, fi),... (x,-1, ft-1) and returns a pair (he, 0z) E H. x B We denote by Rr(C; (x1, fi).... (Xr.fr) H) the regret of L when compared to the best fixed ac- tion (1), Formally, RT(C; (x1, fi).... (XT. fr); H) equals: max EB. (E h (xx)) (0",
Oracle Efficiency. A plethora of oracle-efficient online learning algorithms have been developed in the last decade, with the aim of efficient online regret minimization given offline optimization oracle (Daskalakis & Syrgkanis, 2016; Dudík et al., 2020; Syrgkanis et al., 2016). We cannot easily adapt these frameworks to Lin-OLPO, primarily because the algorithm needs to maintain and access [H]] parallel copies of OLO algorithms, even if Step (ii) above is made efficient. Fundamentally, Lin-OLPO operates in augmented space that is linear in |7|| and therefore intractable.
Et he (x:)) St). When the input sequence clear, we will omit it from the definition and simply write Ry (C; H).
Recall that in online multicalibration, the learner receives context x in each round / E [T] and makes prediction Pt E P = [1/m] according to some distribution w,. Then, W, is a -ddimensional probability vector (recall that M = (P), where (i( represents the probability that pt equals m. The main result of this section shows that an algorithm for OLPO can be efficiently converted into an algorithm for online & -uutiicalibratio.
We instead adapt the oracle-efficient framework directly to the OLPO problem, circumventing the need to access the aug- mented Lin-OLPO structure. We leverage the generalized Follow- Perturrbee Leader family of algorithms (Dudík al., 2020) and show that, remarkably, regret bound for OLPO can be derived using similar techniques as in Dudík et al. (2020) using certain special properties of the OLPO
Theorem 2.1. Let L be an algorithm for OLPO for some col- lection H. C Hy with expected regret denoted by Ry (L; H). Then, there is a sequential prediction algorithm with online
4

---

Improved and Oracle-Efficient Online & 21-Multicalibration
4y-ulticalibration error with respect to H bounded by
Algorithm 1 ONLINE SISIIN&&I-MUUNN EI-MULTICALIBRRATIO
1: for t = L....' do
BB
Ry Ry(C
4BV m log PI))
4m
observe X
3: query the OLPO algorithm:
Moreover, this algorithm is efficient; its running time is polynomial in the running time of C, the discretization pa- rameter m, and T.
(he, 01) < fi)....,.... ( fi-)).
4: query the halfspace oracle: W, + Oxx, hy: 02)-
5: predict ~ We and observe yr-
6: ft <- fe(w,,Yt) yt) as per (2)
We will instantiate Theorem 2.1 with different online leam- ing algorithms for OLPO in Section 3 and Section 4. In the remainder of this section, we outline the reduction and proof sketch of Theorem 2.1. this reduction, the context space X' and the collection of functions H remain unchanged. The key steps will involve utilizing the fact that the actions in H x 30 and carefully setting the reward vectors f fr E R.
7:
end for
Proof Sketch of Theorem 2.1. We first relate the expected multicalibration error for any group h to | Σ h(x,)- ft ll through martingale argument (see (8)). Then, using the definition of the dual norm,
Σ h(xi) fo
1
sup 11
0,
Σ h(xx) fo
2.2. The Reduction
Thus, the overall multicalibration error can be (roughly) related to the reward of the corresponding instance of OLPO. We include the complete proof of Theorem 2.1 in Ap- pendix B.I.
In order convert algorithm for OLPO into online multicalibration algorithm, we need a "halfspace oracle". One such oracle was used to reduce calibration to Blackwell approachability (and subsequently to no-regret learning) in (Abernethy et al., 2011).
3. Improved Online Multicalibration
Definition 2.2 (Halfspace Oracle). We assume access to an efficient halfspace oracle O that can, given x E X. f E H and 0 E Bx, select a probability distribution w E M with || 111 = 1 such that for all y E V, we have
In this section, we give upper bounds for online multicali- bration foregoing computational complexity considerations. In Section 3.1, we consider the case of finite hypothesis class Ht and provide upper bounds through the design of an appropriate no-regret algorithm for OLPO. Combined with Theorem 2.1 and Lemma 3.2, this yields sublinear bounds for online multicalibration when the hypothesis class H. is finite, proving Theorem 1.2. Section 3.2, we describe the changes necessary to handle an infinite-sized hypothesis class H and prove Theorem 1.4.
0 (i) h(x) w(1) (y-
B
A surprising result of (Abernethy et al., 2011) 1) shows that an efficient halfspacc oracle always exists in the context of calibration for y = [o. 1]. We show that this result extends to our setting, i.e., given and x, the oracle construction remains unchanged. See Appendix B.3 for details.
3.1. Online Multicalibration for Finite Groups
Lemma 2.3 (Algorithm 4). Given any x E X. h E H. and E Bx.. there exists an efficient halfspace oracle.
We describe a no-regret algorithm for OLPO in the case where the hypothesis class H. is finite. The key idea is to introduce an online linear optimization problem in higher- dimensional space, and to subsequently reinterpret OLPO in terms of this problem. We denote this problem as Lin-OLPO (or linearized online Linear-prodwe optimization problem). We set up some preliminaries to define Lin-OLPO. We index the elements of H. by (1(1,, (2) h 1744, Given a vector z R|H| M let z denote the M -imeensioon sub-vector
We are now ready to describe our multicalibration algorithm. Multicalibration Algorithm. At each round E [T], the al- gorithm randomly predicts pt according to some distribution W, E TR-M The distribution w, obtained using a combina- tion of the output of the learning algorithm C for OLPO and the halfspace oracle O. In particular, given previous con- texts XI,..., x and previous vectors fi..... fi-1, let (he, 0.) denote the action selected by L in round t. The pre- diction distribution for current context x, is now obtained using the halfspace oracle: w. = O(x, h2 0.). Finally, after observing ye. define ft == f(,,, (w,, 31) where
of indexed by h H. Then, we define the mixed norms:
||2||1,00 = Σ [|z(h)]loc and ||z||oo,1 1 == max [z(h)]]
heH
NEA
and use 11,00 = (0 ||0| 1.00 S 1) and B = {f |f < 1) to denote a unit in the respective norms.
(wr, vr); -.) (y+- )
(2)
We now define Lin-OLPO, which is an online linear opti- mization problem over B Bj,c.-
We formally describe the reduction in Algorithm
5

---

Improved and Oracle-Efficient Online Ei-Multicalibration
Definition 3.1 (Lin-OLPO). In round 1 (T) of Lin-OLPO, the learner plays (a possibly random) action 0, E 1. The adversary reveals reward vector ft E Bo,, which leads to linear reward ( f:). The goal of an online learning algorithm for Lin-OLPO, denoted henceforth by É. to min- imize the regret. The regret, denoted by Ry Ri.nn-DLPO (C: B1,co) equals:
for calibration error is precisely the cumulative reward of the corresponding OLO algorithm). See Algorithm 2 for formal description.
Algorithm& 2 LINEARIZED ONLINE LINEAR- PRODUCT OPTIMIZATION
1: Input: OLO algorithm A, experts algorithm
start instances A ,......!!! A one for each h E H.
3: for t 1,... T do
max o, (i.E. E
4: obtain prediction 0f from A", for h E H
5: query & to obtain distribution 7/+
6: let h = h with probability 71();; predict 02 = 0
where the expectation is taken over possible randomness in i,.
observe reward vector ft.
8: for h E H. pass reward fr(h) to Ahh
We now present a reduction from OLPO to Lin-OLPO. Re- call that the primary challenge with OLPO is that the reward function involves a product of variables. However, by ap- propriately "expanding" the reward vectors fI, f2,..., and the decision space cover all possible h E H. we can effectively linearize the reward function, aligning it with the structure of Lin-OLPO. This lincarization introduces two key challenges: (1) the need to ensure that the best fixed actions in OLPO and Lin-OLPO remain consistent, and (2) preventing the expanded decision space in Lin-OLPO from introducing "better" actions that cannot be captured by OLPO (see Section 1.3 for more detailed discussion).
for h E H. pass reward (0): f((h)) to
10: end for
In Algorithm 2, will use the popular online gradient de- scent algorithm as our reward-maximizing no-regret online linear optimization algorithm, which is known to have regret O(DG/vT where D denotes the f2 diameter of the action set and G denotes the ε f--norm of the largest reward vec- tor (Hazan et al., 2016). For the experts algorithm E, we use the familiar multiplicative weights update algorithm which provides regret (pvTTn) when rewards are bounded in [-p, and n denotes the number of experts. Consequently, we obtain the following guarantee.
Lemma 3.2. Let E be an online learning algo- rithm for Lin-OLPO with corresponding expected regret Reiz 2iLin-01P0 (LP B..) Then, there exists randomized learn- ing algorithm L OLPO with the decision set H.B x Boo such that its expected regret Rr(C; = B L
Lemma 3.3. The regret R (2; (,,0) of Algorithm 2 can be bounded as follows.
Rej Re,in-0LPO B1,,o),, where L (ll is the maximum f--norm of the reward vectors in the OLPO in- stance.
(1, (
Tlog H + VTM
Proof Sketch. At a high level, the regret bound proceeds by first applying the regret bound for the multiplicative weights update algorithm, and then subsequently applying the no-regret property given by each instantiation, i.e., for each h E H. of the online gradient descent algorithm. We provide the detailed proof in Appendix C.2.
We defer the proof of this lemma to Appendix C.I.
We now present a no-regret algorithm for Lin-OLPO whose runtime per round is linear in [7).
Algorithm. Our algorithm for Lin-OLPO relies on two com- ponents: (i) a reward-maximizing no-regret online linear optimization algorithm, denoted by A (c.g., online gradi- ent descent), and (ii) a coluudd-aximzzinggg no-regret algo- rithm for the experts setting, denoted & (c.g., multiplicative weights update). Our algorithm will execute [7|] copies of A, one for each E H; that is, we treat each function as an expert who runs their own copy of A, denoted AAt, each measuring regret against the action set o.... Subsequently, the predictions made by h are aggregated using E. At high level, each of the OLO algorithms A executes the ac- tion we would want to take if we were only concerned about calibration with respect to the specific hypothesis h, and the experts algorithm selects for hypotheses that seem "more difficult" with respect to calibration error (where our proxy
We can now complete the proof of Theorem 1.2.
Proof of Theorem 1.2. Using Theorem 2.1, Lemma 3.2 and Lemma 3.3, E| (TT, H)] S 7BT 1/3 Iog(67 + 5BT 1/2 Vlg H O [BT (oo-1//Voog((TTT)) (Tog(6T) where the penultimate inequality uses M I 2m, and the final in- equality uses L < 1 as per the reduction in Theorem 2.1 and m 1/
3.2. Extending to Infinitely Many Groups
We now describe the necessary changes to obtain improved bounds for online multicalibration for infinite-siee -ized hypoth- esis class H. At a high-level, our approach reduces to the finite setting by constructing an appropriate covering of the
6

---

Improved and Oracle-Efficient Online & E1-Multicalibration
hypothesis class H. Then, it uses the simple fact that the online multicalibration error is 1-Lipschitz w.r.t. H.
for which we obtain Corollary 1.5. See Appendix C.4 for details.
Recall our definition of covering with respect to the L0 metric (Definition 1.3). We say that a subset Hg = "e'.....4'' S H. is a f-cover with respect to the I metric if for every h E H. there exists some i E [N] such that ||A h 12 = max [h(x)- (=)))) - B. Hence- forth, we denote Hys and [Haa] as the minimal 3-cover and the corresponding, 3-covering number respectively of H. referring to the fo metric by default. With this definition in hand, the key steps for our extension to an infinite-sized hypothesis class H. are as follows:
4. Oracle Efficient Online Multicalibration
In this section, we explore approaches to computationally efficient online multicalibration and ultimately prove Theo- rem 1.7. We do this by adopting the framework of oracle efficiency (Daskalakis & Syrgkanis, 2016; Hazan & Koren, 2016; Syrgkanis et al., 2016) for the online linear-product optimization problem (OLPO) arising from the reduction in Theorem 2.1. In particular, we design an online learning al- gorithm for OLPO that makes single call to an optimization oracle per round' and does not need to access the augmented Lin-OLPO structure. We recall the definition of our oracle.
1. We begin by replacing H. with Hi for some 8 > 0 and subsequently appealing to Theorem 1.2 to bound the online multicalibration error with respect to Hz.
Definition 4.1 (Offline Oracle). The offline oracle receives sequence of contexts {xg J with corresponding reward vectors {fs) coefficients (Na )==) and an error param- eter > 0. The oracle returns a solution (4", 0*) E H x θ that approximately solves, up to an additive error c,
2. Then, by showing that the online multicalibration error is L-Lipschitz with respect to H. in the Lx metric, we can conclude that the prediction is indeed multicali- brated with respect to H. up to the additional error term B (see Lemma 3.4).
max {Eo Ko (0, h(xx) fa)
(3)
3. Finally, we appropriately set 33 o(T) (in manner that optimally balances the terms Vlog [Ha and 3 in the multicalibration error). We instantiate the last step with various examples of linear, polynomial, and uniformly Lipschitz convex function classes.
Note that the oracle can handle input of variable length, i.e., the number of rounds itself is implicit input the optimization oracle.
In the introduction, we claimed that solving (3) essentially amounts to evaluating approximate multicalibration error. To see this, suppose we call the oracle with input length equal T' and set Kt 1 for all & < T. Then, for a fixed h E H. we have maxage ΣT O0 h(xx) fi) m (0, (__Tn((x)) ft = ET_ h(x:) ft and the argument O that maximizes the above is expressible in closed form. Maximizing this quantity over h E H. yields the approximation to the multicalibration error with respect to the family H that is defined in Equation (8) (where the approximation error is upper bounded in Lemma B.
The main result of this section shows that any algorithm that multicalibrated with respect to H. is also multicalibrated with respect to H C Hg up to an additional error of B.
Lemma 3.4. Let H denote collection of real-valued func- tions h. X - TR and let Hy denote a 3-cover of H with respect to the Loo metric. If a sequence of predictions is multicalibrated with respect to H.g then it is also multicali- brated with respect to H. up to an additive B. Formally, if K (TT, Ho) < o, then K (TT, H) S a + 3.
The proof of this lemma can be found in Appendix C.3. We can now complete the proof of Theorem 1.4 using Theo- rem 1.2 and Lemma 3.4.
In the remainder of this section, we design an oracle- efficient online learning algorithm for OLPO that relies on the oracle defined in (3). In Section 4.2, we provide explicit efficient constructions of the oracle under the assumption that the contexts fx: )T_ satisfy either the transductive or small-separutor conditions, both of which are commonly made assumptions in oracle-efficient online learning (Dudík et al., 2020; Syrgkanis et al., 2016). We restate these as- sumptions for completeness in Section 4.2.
Proof of Theorem 1.4. Fix an h E H. and let W' E Hy such that maxxex [x(x)) l((x) < B. Then, E[K(TT, [i]] ] = ([[((T AO] + E (TT, h) - K (KT,,')) < <OBT 1/3 Vlo (6g H + 8, where the first term is bounded by Theorem 1.2 on the class H, and the second term follows from Lemma 3.4 since Hi is 8-cover. D
We apply this result to specific function classes that are known to have bounded covering numbers, namely, to poly- nomial regression and to bounded, uniformly Lipschitz, convex functions. The class of bounded linear functions is subsumed by the polynomial regression class (when k: = 1),
We first make an observation tailored to the decision set B recall that in round / E [7']. the learner in OLPO plays
'Ntte that we can think of oracle calls requiring O(1) time, as we have dispatched computational effort to the optimization oracle.
7

---

Improved and Oracle-Efficient Online E--Mutticalibration
(1,; E H B For any h E H. we have
Algorithm 3 Generalized FTPL for OLPO
1: Input: perturbation matrix T e [o, 1) H| x )xN and
arg m Box [Ein h(xx) (fr, (1 E (+1JaM
accuracy >> 0
randomness a (a1, ,aN): oi Unif(o, vT]
Based on this observation, we restrict our decisions to the Boolean hypercube; i.e., 0: {+11]A, and note that for any learning algorithm L for OLPO, the regret remains changed. We also allow actions O, to be randomized; as result, [[o,] can and will lie in the interior of {=1} J.M. Accordingly, we will assume the optimization oracle returns a solution (h", 0*) E H. x {=1] M satisfying (3).
3: for t = ......
................................ T do
4: select (h2, 02) E H x (+1) per (4)
5: observe context x, and reward vector ft.
6: receive payoff (0,, (x.) ft)
7: end for
does not yet guarantee oracle-effiiiency since a naive con- struction of I would require space that is linear in |H| and exponential in M. Thus, we need the property that the per- turbations to each action (h, 0) can be simulated efficiently through the optimization oracle (3); that is, without needing to actually access r. This requirement is captured by the implementability condition, stated next.
4.1. Online Multicalibration via Admissibility and Implementability
We now give an algorithm for OLPO that is situated in the generalized
(GFTPL) frame- work (Dudík et al., 2020), and describe the conditions under which it can be made efficient with respect to the oracle in Definition 4.1. In particular, our algorithm will ultimately require only single oracle call per round. The algorithm is roughly constructed in two steps.
Definition 4.3 (Implementabilityy). A translation matrix r is implementable with complexity D) if for any realization of the random vector a. there exists a set of coefficients {r² [ and vectors { (both of which will depend on a) such that can express, for all (h, 0) E H x (#1]MM M,
The first step is to design an algorithm in the GFTPL frame- work that obtains sublinear regret. The main idea is to draw a lower-dimensional random vector a E RR- where each aj is drawn independently from an appropriate distribu- tion, and N < essentiaal we will think of runtime that is linear in N to be acceptable. The payoff of each of the algorithm's is actions is perturbed by some linear combi- nation of a as given by a perturbation translation matrix I [-B, B](A) x2 x (note that [H| x 2M denotes the size of the action space of the algorithm). In each round I E (T). the algorithm selects (hi, 0.) E H x {+1] to approximately maximize:
- My (0, fi)
= Eド=
(5)
Crucially, this allows us to simulate (4) by (5) (which is the oracle in Definition 4.1). We note that the definition differs slightly from the definition in Dudík et al. (2020) but they can be shown to be equivalent, and this definition turns out to be slightly more convenient to work with in the proof.
The main theorem of this section shows that the GFTPL framework achieves sublinear regret for OLPO.
max NEH M
Σ ((x))) - fa) + a P
(4)
Theorem 4.4. Consider the instance of OLPO with the de- cision set H. X {=1]a Suppose that the perturbation translation matrix I E [-B, B (1H1)x22) satisfies 8- admissibility and satisfies implementability with complexity D. Then, Algorithm 3 executed with e = 1/vT satisfies the expected regret Rr H)) guarantee
up to an additive error > O. We will show that is equiv- alent to the oracle (3) in Definition 4.1 (refer to the "im- plementability condition in Definition 4.3). This algorithm described in Algorithm 3, and is no-regret up to the er- for of the oracle c as long as I satisfies the following 5- admissibility condition.
RT H) SO (B'NTT)
(6)
Definition 4.2 (ö-admissibility (Dudik et al., 2020)). A translation matrix I is 6-admissible if its rows are distinct, and distinct elements within each column differ by at least 5. Formally, in our framework, for every pair (h, 0) * (h', 0') we need P e( # ((,,,e) ) and for every j E [N] we either have I (1,,0) = 1 (12, jo). or [F(n,,), - e 2 6.
Furthermore, this algorithm requires single oracle call per round, and the per-round complexity is O + ND..
The proof of Theorem 4.4 is provided in Appendix D.I. The key steps are similar to the analysis of the GFTPL algorithm in (Dudík et al., 2020), i.e., the analysis includes characteriz- ing an approximation error term and stability error term. We note that combining (6) with Theorem 2.1 gives a "black- box" algorithm for obtaining online fy-multicalibration given 5-admissible and implementable l.
It turns out that the aforementioned 5-admissibility condi- tion suffices to design an algorithm that obtains an over- all regret guarantee of ONNVT/8 + cT). However, this
8

---

Improved and Oracle-Efficient Online fi-Multicalibration
4.2. Our Admissible and Implementable Constructions
is admissible and implementable. Specifically, we give efficient algorithms for the transductive and small-separator settings when H. is binary-valued, i.e., h X + {0, 1) for all h E H. and prove Theorem 1.7.
In this section, we give settings in which one can explicitly construct a I matrix that is admissible and implementable. Specifically, we will give efficient algorithms for the trans- ductive setting and the mepll-seprrator setting, defined next. We also assume in this section that H. is binary-valued, i.e., h: - {0, 1 for all h E H.
Potential improvements and extensions of analysis. It is natural to ask about the extent to which the assumptions we have made - access to the offline oracle, Ainary-valued H. and either transductive or sufficiently separated data- can be weakened or improved. We begin by noting that our proofs will directly work given "C-approximate oracle" (3) (to prove C-approximate regret, which would suffice for our reduction in Theorem 2.1) since they rely on the GFTPL framework of Dudík et al. (2020) in a blxck-box manner. Two concurrent recent works (Block et al., 2022; Haghtalab al., 2022) showed that the generalized FTPL framework can provide oracle-efficient regret bounds for on- line supervised learning on infinite-sized hypothesis classes with bounded VC dimension (in the case of binary labels) or pseudodimension (in the case of real-valued labels) if the contexts are smoothed with respect to some known base probability measure. We believe that adapting their proof technique, especially for the stability term, to the OLPO in- stance is an interesting direction for future work.
Transductive Setting. In the transductive setting, the learner has access to the set X' from which contexts will be drawn. Formally, we will say that X' = {x',. [x'....,x"] x and that at each round t, the context X, E X.
Small-Separator Setting, In the sepaa-sep setting, assume access to small set of contexts X, called separator. Let X' fx .......)), ), and we have that for any two groups h, h E "H, there exists feature E X such that (xx) # (x).
These settings are commonly used, even for the simpler problem of oracle-efficient online prediction (Dudík al., 2020; Syrgkanis al., 2016), and have since been built to ensure oracle-efficient online learning under smoothed data or transductive learning with hints? (Block et al., 2022; Haghtalab et al., 2022). We are now ready to define our con- struction of the translation matrix I for these two settings. In particular, we prove the following (which proves Theo- rem 1.7 by combining with Theorem 2.1 and Theorem 4.4).
At more fundamental level, the discrepancy in rates be- tween inefficient and oracle-efficient multicalibration arises solely from the linear dependence on m (or M) in the regret bound of oracle-efficient OLPO, as compared to the O(m²/3) dependence in the inefficient OLPO implementation. Improv- ing the dependence on m in the oracle-efficiee regret bound would require improving the regret analysis of (Dudík et al., 2020), which would be of independent interest.
Lemma 4.5. In the transductive and small-separator set- tings, there exists perturbation translation matrix I E [-B, ([H (D(M) that is L-admissible and imple- mentable with complexity D.
A Acknowledgments
The proof of Lemma 4.5 is deferred to Appendix D.2. We now examine implications of Lemma 4.5 for oracle-efficient multicalibration. Plugging in 8 = 1 and N = DM into the statement of Theorem 4.4, and appealing to the reduction in Theorem 2.1 gives us
We are grateful to the anonymous reviewers of ICML for valuable feedback. The last author is thankful Marco Molinaro for discussions on online linear optimization over general convex bodies and the proof of Lemma 3.3.
B + + (BDMVT))
E (KT, (T). <
m
Impact Statement
m mlog(67 (H))
4mB
+ 4B
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
T
T
Finally, setting the allowable error in the optimization oracle to = " = Tiन and using M = m +1 gives us
( HB) S S0005000000 (BDT 1/4 (lo(((((())
References
which is the bound stated in Section 1.2. In Section 4.2, we give settings where one can construct a I matrix that
Abernethy, J., Bartlett, P. L.., and Hazan, E. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 27-46, 2011.
While it is conceivable that our approach could be extended these more complex settings as well, we do pursue this path this paper.

---

Improved and Oracle-Efficient Online & 2/-Multicalibration
Acharya, K., Arunachaleswaran, E. R., Kannan, S., Roth, A., and Ziani, J. Oracle efficient algorithms for groupwise regret. In 12th International Conference Learning Representations (ICLR 2024), 2024.
Foster, D. P. and Vohra, R. V. Asymptotic calibration. Biometrika, 85(2)3379-390, 1998.
Fudenberg, D. and Levine, D. K. An casier way to calibrate. Games and economic behavior, 29(1-2):131-13) 1999.
Agarwal, A., Hsu, D., Kale, S., Langford, J., Li, L., and Schapire, R. Taming the monster: A fast and simple algo- rithm for contextual bandits. In International Conference on Machine Learning, pp. 1638-1646. PMLR, 2014.
Garg, S., Jung, C., Reingold, O., and Roth, A. Oracle efficient online multicalibration and omniprediction. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2725-2722299 SIAM, 2024.
Azoury, K. S. and Warmuth, M. K. Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine learning, 43:211-246 2001.
Globus-Harin L., Harrison, D., Kearns, M., Roth, A., and Sorrell, J. Multicalibration as boosting for regression. In Proceedings of the 40th International Conference on Machine Learning, ICML'23, 2023.
Block, A., Dagan, Y.. Golowich, N., and Rakhlin, A. Smoothed online learning is as easy as statistical learn- ing. In Conference on Learning Theory, pp. 1716-1786. PMLR, 2022.
Gopalan, P., Kalai, A. T., Reingold, O., Sharan, V., and Wieder, U. Omnipredictors. In 13th Innovations in The- oretical Computer Science Conference (ITCS 2022), pp. 79:1-79:21, 2022.
Bronshtein, E. E-entropy of convex sets and functions. Siberian Mathematical Journal, 17(3):393-398, 1976.
Dagan, Y., Daskalakis, C., Fishelson, M., Golowich, N., Kleinberg, R., and Okoroafor, Breaking the T2/3 bar- rier for sequential calibration. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 250 2025.
Gopalan, P., Kim, M., and Reingold, O. Swap agnostic learning, or characterizing omniprediction via multical- ibration. Advances in Neural Information Processing Systems, 36:39936-3999 2023.
Guntuboyina, and Sen, B. Covering numbers for convex functions. IEEE Transactions on Information Theory, 59 (4):1957-1965. 2012.
Daskalakis, and Syrgkanis, V. Learning in auctions: Regret is hard, envy is easy. In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science, FOCS'16 16, pp. 219-228. IEEE, 2016.
Gupta, V., Jung, C., Noarov, G., Pai, M. M., and Roth, A. Online Multivalid Learning: Means, Moments, and Prediction Intervals. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pp. 82:1- 82:24, 2022.
Dawid, A. P. The well-calibrated bayesian. Journal of the American Statistical Association, 77(379):605-610, 1982.
Deng, S., Hsu, D., and Liu, J. Group-wise oracle-efficient algorithms for online multi-group learning. arXiv preprint arXiv:2406.05287, 2024.
Haghtalab, N., Han, Y., Shetty, A., and Yang, K. Oracle- efficient online learning for smoothed adversaries. Ad- vances in Neural Information Processing Systems, 35: 4072-4084, 2022.
Dudík, M., Haghtalab, N., Luo, H., Schapire, R. E., Syrgka- nis, V. and Vaughan, J. W. Oracle-efficient online leam- ing and auction design. Journal of the ACM (JACM), 67 (5):1-57, 2020.
Hart, S. Calibrated forecasts: The minimax proof. arXiv preprint S.XXi:2209005865 2022.
Foster, D. and Rakhlin, A. Beyond ucb: Optimal and ef- ficient contextual bandits with regression oracles. In International Conference Machine Learning, pp. 3199- 3210. PMLR, 2020.
Hart, S. and Mas-Colell, A. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5): 1127-1150, 2000.
Hayes, T. P. A large-deviation inequality for vector-valued martingales. Combinatorics, Probability and Computing, 2005.
Foster, D. proof of calibration via blackwell's approach- ability theorem. Games and Economic Behavior, 29(1-2); 73-78, 1999.
Hazan, E. and Koren, T. The computational power of opti- mization online learning. In Proceedings of the forty- eighth annual ACM symposium on Theory of Computing, pp. 128 128-141, 2016.
Foster, D. P. and Kakade, S. M. Calibration via regression. In 2006 IEEE Information Theory Workshop-ITW Punta del Este, pp. 82-86. IEFF, 2006.
10

---

Improved and Oracle-Efficient Online Ei-Multicaliiration
Hazan, E. et al. Introduction to online convex optimization. Foundations and Trendsè in Optimization, 2(3-4):157- 325, 2016.
Wang, G., Hu, Z., Muthukumar, V., and Abernethy, J. D. Adaptive oracle-efficient online learning. Advances in Neural Information Processing Systems, 35:23398- 23411, 2022.
Héhert-Johnson, U., Kim, M., Reingold, O., and Rothblum, G. Multicalibration: Calibration for the (computationally- identifiable) masses. In International Conference on Ma- chine Learning, pp. 1939-1948. PMLR, 2018.
Jung, C.,, Lee, C., Pai. M., Roth, A., and Vohra, R. Moment multicalibration for uncertainty estimation. In Conference on Learning Theory, pp. 2634-2678. PMLR, 2021.
Kalai, A. and Vempala, S. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71332291-3307 2005.
Kim, M. P., Ghorbani, A., and Zou, J. Multiaccuracy: Black- box post-processing for fairness in classification. In Pro- ceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pp. 247-254, 2019.
Kim, M. P. Kern C., Goldwasser, S., Kreuter, F., and Reingold, O. Universal adaptability: Target-independen inference that competes with propensity scoring. Pro- ceedings of the National Academy of Sciences, 119(4): e2108097119, 2022.
Lee, D., Noarov, G., Pai, M., and Roth, Online minimax multiobjective optimization: Multicalibeating and other applications. Advances in Neural Information Processing Systems, 15:29051-290633 2022.
Noarov, G., Ramalingam, R., Roth, A., and Xie, S. High- dimensional prediction for sequential decision making. In Proceedings of the 42nd International Conference Machine Learning (To Appear), ICML'25, 2025.
Perchet, V. Calibration and internal no-regret with ran- dom signals. In International Conference on Algorithmic Learning Theory, pp. 68-82. Springer, 2009.
Qiao, M. and Valiant, G. Stronger calibration lower bounds via sidestepping. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 456- 466. ACM, 2021.
Sandroni, A. The reproducible properties of correct fore- casts. International Journal of Game Theory, 32(1):151- 159, 2003.
Sandroni, A., Smorodinsky, R., and Vohra, R. V. Calibration with many checking rules. Mathematics of operations Research, 28(1):141-153, 2003.
Syrgkanis, V., Krishnamurthy, A., and Schapire, R. Efficient algorithms for adversarial contextual learning. In Interna- tional Conference on Machine Learning, pp. $159-2166 PMLR, 2016.

---

Improved and Oracie-Efficient Online Ei-Multicalibration
A. Further Related Work
Calibration. The notion of (sequential) calibration has been extensively studied in statistical learning and forecasting (Dawid, 1982; Foster & Vohra, 1998; Hart, 2022). Dawid (1982) introduced the notion of calibration, and Foster & Vohra (1998) showed the existence of an algorithm capable of producing calibrated forecasts in an online adversarial setting. Subsequently, numerous algorithms were discovered for calibration; see, for example, Foster & Kakade (2006); Fudenberg & Levine (1999); Hart & Mas-Colell (2000): Perchet (2009); Sandroni (2003); Sandroni et al. (2003). Foster (1999) has given a calibration algorithm based on Blackwell approachability, while Abernethy et al. (2011) showed connection between calibration and no-regret learning (via Blackwell approachability).
The concept of multicalibration extends standard calibration by requiring calibrated predictions not just overall, but across multiple subpopulations defined by hypothesis class. This notion was first introduced by Hébert-Johnson et al. (2018) in the batch setting. They showed that multicalibrated predictors could provide strong fairness guarantees while maintaining predictive accuracy. Since then, multicalibration and some analogous notions have been studied; for example, Kim al. (2019) study multiaccuracy, Jung et al. (2021) give algorithms for moment multicalibration, and Gupta al. (2022) investigates quantile multicalibration. Another line of work explores the connection between multicalibration and omniprediction (Garg et al., 2024; Gopalan et al., 2022; 2023). Omniprediction is paradigm for loss minimization that was introduced in Gopalan et al. (2022). Informally, an omnipredictor is a prediction algorithm that could be used for minimizing large class of loss functions such that its performance is comparable to some benchmark class of models F. Gopalan et al. (2022) show that we can reduce omniprediction to a l f-multicalibration. In particular, if a prediction algorithm is multicalibrated (in the & metric) with respect to some benchmark class of models H. then is an omnipredictor with respect to all Lipschitz convex losses and the class H. The problem of online omniprediction was introduced in Garg et al. (2024), and they used similar ideas to that of Gopalan et al. (2022) and Globus-Harris et al. (2023) to show that online omniprediction can be reduced to online f1 E3-multicalibration. Furthermore, they provided an efficient reduction from online multicalibration to online squared error regression over H. yielding oracle-efficient algorithms for online é--mutiiaalibrtion and, consequently, for online omniprediction. Other works have also explored online multicalibration under different settings; for example, Gupta et al. (2022) and Lee et al. (2022) provided algorithms that guarantee online multicalibration in the Zo metric.
Multicalibration
Oracle Efficient Algorithms and Online Multigroup Learning. No-regret algorithms based on injecting random perturbations, such as www.ttheePettubbd--eeaddd have an early history in lending themselves to computational efficiency on specially structured combinatorial problems, such as the shortest path problem and prediction with decision trees (Kalai & Vempala, 2005). these problems, the "oracle" constitutes solving a shortest path problem or learning an optimal decison tree from offline data. Motivated by this, Hazan & Koren (2016) posed the more general problem of achieving computational efficiency in online learning with respect to an offline optimization oracle and showed that this goal is not achievable in the worst case. Subsequently, Block et al. (2022); Daskalakis & Syrgkanis (2016); Dudík et al. (2020); Haghtalab et al. (2022); Syrgkanis et al. (2016); Wang et al. (2022) showed that oracle-efficient learning is possible under further assumptions both for a variety of combinatorial settings involving market design, and for online supervised learning involving contexts {x and labels { For the learning settings the results make assumptions on the contexts (x ) but not on the labels. The setting of online 4 --multicalibrationn is more reminiscent of (but not exactly the same as) the latter case of online supervised learning. Accordingly, we adopt the assumptions of transductive sufficiently separated data made in (Dudík et al., 2020) (which subsume those made in (Daskalakis & Syrgkanis, 2016; Syrgkanis et al., 2016)) and believe our results could be adapted to the weaker assumption of smoothed data or K-hint data (Block et al., 2022; Haghtalab et al., 2022) in future work. Recently, the oracle-efficient framework was also adopted for online multigroup learning with the aim of minimizing group-regret (Acharya et al., 2024; Deng et al., 2024). While group-regret could be closely related to multicalibration and the associated OLPO instance that we set up, it is unclear how to adapt the techniques in (Deng et al., 2024), which are tailored to binary labels and loss functions, to the OLPO problem.
There also exists a rich body of work on oracle efficiency with respect to either online regression oracles or cost-sensitive classification oracles in the contextual bandits literature (see, e.g. (Agarwal et al., 2014; Foster & Rakhlin, 2020)). Indeed, an online regression oracle was assumed by (Garg et al., 2024) but in completely different manner from the contextual bandit application. We do not adopt these frameworks for oracles because the contextual bandit problem is different in scope and unnecessary to solve for multicalibration. It is also arguably more difficult than full-information contextual learning: the strongest of the aforementioned results assume stochasticity in the labels [ and that they are realized by a function in the hypothesis class, and still require an online regression oracle, which is stronger than an offline oracle and only known
12

---

Improved and Oracle-Efficient Online & M-Multicalibration
be solvable in the special case of linear models (Azoury & Warmuth, 2001).
B. Missing Proofs from Section
B.1. Proof of Theorem 2.1
Proof of Theorem 2.1. We first reduce online L -i-caiibration error for any group h to the (1-norm of the vector + Er= h(xx). ft plus a small additive "error" term. Recall, the expected online {--multicalibration for group E H:
Tp p} h(xx) (ye p) w)]
E (KTr,,
E
Σ PEP
Σ
T
We use the following lemma to relate the indicator random variables {1{pt - hEp to their corresponding expectations (we(p) where (p) denotes the probability that pa equals
Lemma B.1. We have
|
E
max
Σ
uipt p} w.(p)) h(xx)) (ye (00-p)))
p)-w,(p))
4B ABVTnn T' log(61)HH) + 4mB.
NEW
PEP
The proof of this lemma relies on a vector version of Azuma- Hoenf-ig inequality and is deferred to Appendix B.2. We will next use to complete the proof of Theorem 2.1. We now proceed upper bound the online multicalibration error for H. Using (7) along with the triangle inequality, we get
E [K(TT, H)] =
max HEH
[p p} (x(x)) (y/+ - p)
T
PEP
1=1
we(p) n(xx)) (ye - p) 20 }
max
T
NEH
pEP
(1p: = p} - wolp)) h(xx) (yt - ps)
E
max hEH
T
PEP
Σ h(x)) ft
m mlog(6T
4mB
max
+ 4B
(8)
T
KCH
T
T
where the last inequality follows from Lemma B.1 together with the definition of ft in (2). Now using the definition of the dual norm, we can write
T
T
1
Σ h(xx) ft
0. M h(xx) fc
T MEH
max
=
T DE
max
1=1
1
RT (C; H)
B m
R H) T
he(x:)
fi)
T
T
where the first inequality follows by applying the regret bound for OLPO obtained by L and the second inequality follows from the definition the halfspace oracle (see Definition 2.2). We note that we can replace the "sup" operator with a "max"
operator the equality above by the compactness of B = (0 ||0||oc I 1) and the continuity of the linear function. Combining (8) and (9) completes the proof of Theorem 2.1.
B.2. Proof Lemma B.1
The proof relies on "vector" form of the Hoeffdingg inequality (see Theorem 1.8 (Hayes, 2005)).
13

---

Improved and Oracle-Efficient Online & Ei-Multicalibration
Theorem B.2 (Vector Azuma-Hosfi'ing' inequality). Let S Ei=1 X, be a martingale relative to the sequence
X,...., Xa where each X, takes values in T& and satisfies (i) E 0 and (it) |x+ll2 S c. Then, for any n > 0 and
2 I, we have
P(||s 2 n) S 2e exp
2nc
Given this inequality, we can now complete the proof of Lemma B.I.
Proof of Lemma B.I. For each h E H and t E [T], we define the vector Y E RM such that
Y = [Ppp = p} - -e(()) h(xi) (ye p)
We now verify that the conditions on the sequence (Y (p) for the Vector Azuma Azuma-Hoeffdaa Hoeffding inequality (Theorem B.2) hold. We note that
|| =
Σ
Σ h(xx)2 (y1- - p)² (Ilpe = p} ww) PEP
V
PEP
$ max xeX
Σ
(1(p: = p} - wo(p))² & V2B,
pEp
where the final inequality follows from the fact that h E H S HB. EpEp lppp = p} 1, and that w, a distribution. This verifies condition (ii). Next, observe that
E ())) Y YE- = [[((xx)) (Ve - p) (T(pr = p) -w,(p) Y ...... Y
h(xx)) (D) B[(L/pt = pp wx(p)) Y!. i..... Y
since w, only depends on information from rounds 1,...,, 1....,,-1, 1, and B[[[pp; = p}) Y .i...., Y = we(p). This verifies
condition (i). Thus, S Σ²=1 Y is a martingale with respect Y Y!..... and
T
T
w.(p) Mxx)) (yt - p)
|
Σ pEp
Σ
T(p = p} M(xx) (yr - p)
Σ
Furthermore, since S R,M, we have ||St||| S VM- ||4/ and applying Theorem B.2 implies that
-8B3T log(6T) HP))
2e
P 21 2222
2e exp
exp
4B2T
(H
T
Thus, with probability at least 1/(T|H()) we have
|| < 1|8 I 22m 2V2B (lg s 4B (6
(10)
since = m + < 2m. We are now ready to complete the proof. Let Gn. denote the event that ||S S 4B /Tm ( for h E H. Let G denote the event that G₁, holds simultaneously for all h E H: i.e. G OhenGh
By the union bound over all / E H. we can conclude that P(G)) > 1-111 1-1/T. Then, we have
EE
max NEH
{
[1]]
= E
max [1s NER
G P(G) - E
max { NEW
|1
G
P(G)
(1 (1- -
< 4B log
+
max NEW
(1IS
T P(G)
4B / TTTTmoo + 2MBT S 4B 4B TT H!) + 4mB.
where the first inequality uses (10) for all h E H and the second inequality bounds |St|11 2MTB for all h E H. The final inequality uses M m < 2m. This completes the proof of the lemma.
14

---

Improved and Oracie-Efficient Online E/-Multicalibration
B.3. Constructing the Halfspace Oracle
Here we repeat the construction of an efficient halfspacce oracle from (Abernethy et al., 2011) for our setting. In particular, we will design an efficient oracle O that can, given x X, h E H. and 0 Box select distribution R such that for all y E [0, 1/. we have
m Σ
0 h(x) w(i) (y-
B m
m
We describe this oracle in Algorithm 4.
Algorithm 4 h(x,h,0) 0)
1: Input: x E X, h E H _ Uo and 0: |101 I 1
2: define 0: ((i) = ( h(x)
3: if 0(0)= < 0 then
4: 1x-dd. 60
5: else if ((m) 2 0 then
6: w + 8m
7: else
8: find coordinate i such that ((1)= > 0 and 0(i + 1) s
9: W 011+1)-008 6, 0(1)- 06+1)
0(++1)
o())
5,41
10: end if
11: return
immediately follows from the description that w is a valid distribution. Furthermore, note that this oracle can be implemented efficiently. If (0) > and (m)) < 0, then there must exist such that 0(i) > and 0(i + 1) I 0, and such an index can be found using binary search. Thus, this algorithm requires at most (llo(mm)) computations. The following lemma proves the main property of the halfspace oracle.
Lemma B.3. Given any E X, h E H and 0 E Boo, let w Oxx, h, 0) be the output of Algorithm 4. Then, for any E [0, 1). we have E (i) hxx)- (v )))= w(i) I B
Proof. We first note that we can write
m Σ
0() h(x). (V
w(i) = Σ @(1) v 1 (W-
i m
w(i).
m
where we have used (1) = (i) h(x) for all i = 0, I,..., m. Observe that (00 S or (m) 2 0, the lemma is trivially true. Otherwise, we have
i w(i)=
i
1+1
(ii)
y
=
y
w( (i) O(1) +
1/
w(i
0(i +
m
m
0=
@(i + 1)
-(1) +
i+1
@ + 1)
y
0(1 + 1) ((1)
m
1(1)
0 1)
( 0(i+11
max 0()). 0 1)1}
B
1 0 (
2
m
where the penultimate inequality uses the AM-HM inequality, and the final incquality follows from the fact that E B and maxxex [b(x)] & B for all h E H.
15

---

Improved and Oracle-Eficciet Online & M/MMutticalibrrttonn
C. Missing Proofs from Section 3
C.1. Proof of Lemma 3.2.
Proof. We begin by describing how to obtain learning algorithm L for OLPO using learning algorithm C for Lin-OLPO. To achieve this, two components are required: (I) translating decisions from & to C, and (2) generating reward vectors for the Lin-OLPO instance using rewards from the OLPO instance. For each round E [T], given decision 0, from É. set h4 = h with probability 7)(h) = | so) and 0, (1)) (ha) E IB... Then, (h₂, 0.) corresponds to the decision taken by L for the OLPO instance. Next, given context X and reward vector f. from the OLPO instance, let ft BL - (16 .t..... , ((H)) fe) be the reward vector used to simulate the Lin-OLPO instance. Note that ft E x0,
since h E Hy and felll I L. This completes the reduction from OLPO to Lin-OLPO. Next, we analyze the corresponding regret.
First, we observe that
T
T
T
h(x,)
max 00
ft
max NEW
Σ
f((h))12
= max WEH
Σ
t=1 B.
[=1
1
0, Σ h(xx) ft 5:))
max hET, O.
(11)
B
1=1
where in the final equality used the definition of the dual norm. Furthermore, observe that for any Oe 1,,0 and Sc (x(1)((x))) "0...,,,,MM))))) ft), we have
(h) M(x,)
B((O,, hx...) f() B Σ (h)))
7a(h)" B. f:
PER
(.(h), f.(h)) B L 0r. fi) fi)
B
(12)
where (h) = [10(( denotes the probability of selecting group h round and 0, = (1/>e(h)) (hh)). On combining (11) and (12), and taking expectations, we can conclude that:
T Σ
RT( = max NEH. AE
hxxx) ft
Ei hx f.ll
[ml
@ fil) Fi)iI
= B. L
max 0E
0, Σ fi
E
-B L Rl
OLPO (C. (1,o))
(13)
1=1
1=1
This completes the proof of the lemma.
C.2. Proof of Lemma 3.3
Proof. To bound the regret, we observe
T
T ΣΣ (=1 NER
T Σ
}
E Or (o,
Thh)) (0%
2 max KEH
or (o0)))))))
V log 174,
(14)
where the inequality follows by applying the no-regret property of the multiplicative weights update algorithm & and noting that fe(h)) E [-1,1] for all h H (since f, B...)). Subsequently, apply the no-regret property of each of the online gradient descent algorithms AI,...,ApH: obtain
T Σ
(o. VTM
T 1
10% F.(h))
>
max
-
(15)
BEB.
16

---

Improved and Oracle-Effccient Online Ei-Multicalibration
where the regret bound the fact that [|fe(h)l22 s [lf(())la 1 and that the lg diameter of &B is VM. Combining (14) and (15) gives
T
Σ
E
(o.
fi)
Σ 1=1
f((hlli V log H
VTM,
t=1
which upon re-arranging proves the lemma.
C.3. Proof of Lemma 3.4
Proof. Fix a transcript गт {(xx, Pt. yr.) 1= avoid notational clutter, we will drop the argument øт the remainder of the proof. We will also index predictions as p e P, and use S(p) to denote the set of rounds in which the prediction was pt that is, S(p) {t [T] Pt p}. For h H. recall
k(h) K(TT, 1)
((xx) PEP (ES(p)
Σ
(ye - p)
Furthermore, define (nhh) = EEES(n) h(xi) (yt - p) for every p E P.
Claim C.1. For any p E P. let T, ((p)). Then, we have for any h' H:
[kp(h) Kp(h')l s Tp || blllew
Using this claim, we can complete the proof of Lemma 3.4. First, we note that K K(h) = - EpEp Kp(h). Since K(A) 2 0, we have K(h)= = [K)]. Using this, and the triangle inequality twice, we get
K (h) K(h)
[Kh)] (Kh')) & [k(h) K(h))
1
$ 1
1 Σ
(kp(()) kk(h'))
Kp(h) Kg(h')
T
T PEP
PEP
1
<
Σ
Tp ||h - Wlles 111--11le = ||/ -h-10 h l/
T
pEP
where the final inequality uses Claim C. and the final equality used EpEr Tp T. By symmetry, similarly have
K(h') k(h) //4 W/1l
from which we conclude that [K(h) K(h')l I || h' ee Now, fix an h E H. and pick h E His such that || - ll < 3 (note that such an E Hg always exists according to Definition 1.3). Thus, we have
K(h) < K(N) + |h le Sa+
desired. We complete the proof of Lemma 3.4 by proving Claim C.I. Proof of Claim C.I. Applying the reverse triangle inequality, we have
K(h) K(h)- = Σ h(x;) (vr - p)
Σ (ES(P)
h((x))) (ye p))
(E)(
Σ
h(x:): (y -p) Σ
1'(x:) (ye - p)
(ES(p)
LE (EP(
Σ
(h(x:) - 11 l((x))) (y+ - p)
(ES(p)
17

---

Improved and Oracle-Efficient Online &
2/-Multicalibration
Applying again the triangle inequality the expression above, and using the fact that yr [0, 1] for all / [7]. get
khh) K(+)
[(h(x,) h1 (xx)) - Tp max tES(p)
h(xx) h1 h((x)) Tp 11/- w/llaw
(16)
xEX
By symmetry, we also have the following.
K(h) - K(h) S Tp 1111 hm
(17)
Combining (16) and (17) completes the proof.
This completes the proof of Lemma 3.4.
C.4. Applications of Theorem 1.4
In this section, we give applications of Theorem 1.4 specific function classes.
Application 1: Polynomial Regression. Suppose X' [0, 11s. and our hypothesis class corresponds multivariate polynomial regression functions of degree that is, given X, h(x) = Σi= Σx=1 h++(a-1)++ I where g E R Suppose that Hdd, k) = {h E g ||hl] & B}. Then, constructing an 3-cover for H in the traditional sense gives us an 3-cover for H. in the functional sense. particular, since X' [0, 1] have
max (h(x) n'(x)l < || 1'll
zEX
It is then standard fact that the 8-covering number of the & ball of radius B with respect to the & is at most -Therefore, applying Theorem 1.4 and setting 3 = T-133 gives us multicalibration error
kd
+
2B #
B B Hpoly(d,))) = O (kkd)) logg (BT)
The class of bounded linear functions is subsumed by this class (when k = 1), for which we obtain the Corollary 1.5.
Application 2: Bounded, uniformly Lipschitz, convex functions. Let H((0, 1J B, L) S HB denote the set of real- valued convex functions defined on X' : [0, 1j that are uniformly bounded by B and uniformly Lipschitz with constant
L. (?)Theorem 191vaarpoonnn shows that in this case, |HH,e| S & (()
d/2 where C is positive constant
that depends only on the Lipschitz parameter L. Therefore, applying Theorem 1.4 and setting B = T 212/ yields multicalibration error
K(F1, H([0, B, L)) = O(BA/2T-1// log( + OTT 244/3
The second term dominates if d 2, and reflects the standard "curse of dimensionality" that we encounter in statistical learning of real-valued convex functions.
D. Missing Proofs from Section 4
D.I. Proof of Theorem 4.4
We first show that if the perturbation translation matrix I E [-B, B, (| satisfies 5-admissibility, then Algorithm has regret bounded by O(BN/T/8). Then, we show that since satisfies implementability with complexity D, we can indeed execute Algorithm efficiently. For ease of exposition, we will use Ry denote the regret of Algorithm 3. To begin, recall that we defined
{( L (xx)) (x(x)))-F) fo (o0d)..)))
(0:
})}
T
R
max E
Σ El hx))) fel.
(18)
WWithout Lipschitz assumption, (Guntuhoyina & Sen, 2012) showed that covering number actually infinity.
18

---

Improved and Oracle-Efficient Online & Ei-Muutiicllibratinn
suffices uniformly upper bound the regret incurred by each h H; we will provide a worst-case analysis of this quantity for arbitrary reward vectors (ft [ft]t=1 Formally, we can write
RT
max (h) where kEW
Rr(h): ==
max (1
Σ (0,((x)) fi) E Σ (r, (x())) fi)
For each E H. let 0, E [=1] M be a maximizer of the function decompose (h) into terms as below:
Σ/ (0, (x,,) fi) in the variable 0. Then, we can
r
Ry (h) E
0 h(x,) ffi)
10 hx(x)) fe)
T
E
(0% h(x)) .f))
Σ
(0++1. hx41(x))) fi)
21
T
T
0 1411 (x.) f()
Σ
(0,, (x(x)) ft) .
(19)
T2
The first term Ti corresponds an approximation error term: suppose we could use the clairvoyant decision (he+1. 0++1) for round without noise, this would be optimal, but with noise it will create extra error. The following lemma(Lemma B.1 in (Dudík et al., 2020)), characterizes Ti pointwise for every realization of the noise a.
Lemma D.1. (Be-the-Approximaate Leader Lemma) In the Generalized FTPL algorithm, we have
Ti S a (1))),0,) -(n,o)) + (T +1
for each (h, 0) E H1 x (+1)M and every realization of the noise
Proof. We will prove this lemma by induction on T. For the base case, T = 0, and so it suffices to show that (T (h,,0,,) .,)) T (). + 6 2 0 for all (h, 0). Here, the statement follows directly from the e-approximate optimality of oracle; that is, we select (h1, 0,) such that
a I (1) 2
max (E
{a [( -
Next, we prove the inductive step. Assume that the lemma holds for some T. Now, for all (h, E H x {=1]M, we have
T+1
T
(x+) Si) + a (1)
Σ
1041, f() + T(n...) + (0742, ST
10442, f() + a ((hr44.0r=2) - (T'+1)
(01+2, hr fr+1)
(0+42 hT4((x)) fi) + ((hr4200r22) - (T +1)
a (x,(())) f() a T(,,) - (T
where the first inequality follows by applying the induction hypothesis and considering the pair (hT+2, 0r-2), and the final inequality follows by the c-approximate optimality of the oracle time T This completes the proof the lemma.
19

---

Improved and Oracle-Efficient Online & 2/-Multicalibration
Next, we characterize the term T2 in (19). The term T2 is essentially stability enror term, which measures the cumulative effect of the difference in the decisions (he+1, 0x+1) and (he, 0t) reward. Intuitively, stable algorithm will result in similar slowly varying decisions over time and therefore small stability enror term. The following lemma characterizes the stability error term under the condition that the perturbation matrix I is 6-ammissible.
Lemma D.2. (Stability Lemma) Suppose we run Algorithm 3 with 6-admissible matrix I E [0, 1]11)x2))) and random vector (0t,,"", ,ON) such that each oi is drawn independently from Unif(O, vT). Then, we have
B +E VT
T2 & 4TN - (1+6-1)
The proof is identical to the proof of the stability lemma (Lemma 2.4) presented in (Dudík al., 2020), and is omitted here. Plugging our upper bounds on I3 and T/ into (19) gives us
(r(h) s a. (Fmr.er) - [(hoo))) + (T +1) + 4TN
(1+6-1)
B c VT
B +
I a ((n) tc. + +) ATN (1 (1+5-1)
VT
S NVT (T++) 16BNVT =0 BNVT
Above, the first inequality uses the fact that > 0 and r E [0, 1011 the second inequality uses the fact that E [0, 1](1X(22") ) and each a drawn independently from Unif[0, VTJ. and the final equality uses the assumption that 1/VT.
Finally, argue that if I satisfies implementability with complexity D, then Algorithm 3 with 1/VT can be implemented in time poly(N, D, P). This directly follows by noting that for any a, we have set of coefficients {Ky} and vectors ( (which may depend on a such that
D Σ (xx)) fa) + [(h,o) E (x.) fa) Σ Ng. (0, 5.)
This is exactly in the form of our offline oracle (Definition 4.1). Thus, the runtime of Algorithm 3, treating as black boxes the step of sampling from the uniform distribution and the oracle (3) is O(T + TND). This completes the proof of Theorem 4.4.
D.2. Proof of Lemma 4.5
Proof. We consider I' E [-B, B|(HI )x((M)) )x(DM), so that the rows of r can be indexed by (4, 0) E H x {+1] and the columns of can be indexed by (j. i) E [D] x [M]. Then, we will specify each entry as ((..0)((..)) = Mxx') 0z. Note that ((.,)))(.))) S B since h E C H.. We first prove implementability and then 1-admissibility.
Proof of implementability. Consider any realization of the noise As with the columns of I, we index a by the tuple (j.) (D) x [M]. We denote as (G)))) E RM the sub-vector (o().)) .G.M)) Then, we have
M
ΣΣ ((.)) h(x²) 0
f=1
D (xx))
which clearly satisfies the implementability condition (5) with complexity D, K6 = 1 for all j [D], and f, = a(.)))
Proof of admissibility. Consider any two rows indexed by (h, 0). (h', 0'). We need show that:
20

---

Improved and Oracie-Efficient Online & 21-Multicalibration
1. ((h,0) + ())
2. If (h. + Tar,or. then (1.0))(11)) - P Parter (nr.e) 2 1.
Showing the first statement is easy: either h + h', in which case there exists at least one index E [D] such that h(x²) * h. In the other case where h = h', consider any index j such that h(x)) o 0 (at least one such index must exist, otherwise we can simply remove h from the hypothesis class without loss of generality). Further, since in this case we must have 0 * 0', there exists at least one index for which 8 + 6%-- Therefore, we have T (1h.0).(1.) = h(x²) )d; # h(x)) )((.
To show the second statement, we use the structure the Boolean hypercube to say that if 0; # 6% then 10: 0f Similarly, if o O, then [0,] Then, we again consider two cases when (1.0). + (.).)))...)) The first is h(x²) o (x²).. In this case, suppose without loss of generality that h(xx) 1 while 1 (x') 0. Then, we have
(h.0).00. Tar 10.1 1.
On the other hand, suppose that h(x²) h'(x)). IF h((xx)) have o)..0).G.)) (' lf((x)) have
[ (A.0).(A)) T Tnv = |0; 0% E {0.2)
This proves the second statement and therefore we have proved 1-admissibility, which completes the proof of the lemma.
21


Reviews:
[{"review_id": "uHixcOCm8a", "reviewer": "Reviewer_FERs", "summary": "This paper studies the online l1-multicalibration problem. Multicalibration is a natural extension of calibration with group identities. It is a natural group fairness definition and implies some learning concept called omniprediction. \n\nThe authors improved based on a previous work that provides O(T^{1/4}) upperbound for l2-multicalibration. This paper directly solves l1-multicalibration with O(T^{1/3}) and oracle efficient O(T^{1/4}) upperbound using halfspace oracle, which they provided an implementation in the paper. This paper improves the previous work in many perspectives.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review of our paper (and for discovering a typo in Appendix~C). We also appreciate the reminder to acknowledge the known lower bound for online calibration, which indeed extends to online $\\ell_1$- multicalibration.\n\nTo address the first comment, yes, our results do imply improved bounds for online omniprediction since our improved bounds for online $\\ell_1$-multicalibration can be transformed into improved bounds for online omniprediction when the loss functions are convex and Lipschitz; see,  e.g., Garg et al. (2024). \nWe opted against including results for online omniprediction because it was not the primary focus of our work, and we wanted to avoid distracting from the core contributions on online $\\ell_1$-multicalibration and the $\\mathtt{OLPO}$ framework. \nAdditionally, due to space limitations, providing a satisfactory treatment of omniprediction results would have been challenging. \nThat said, we acknowledge that this connection is standard and well-known in the community, and we will add a short discussion in the related work in the final version of the paper.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I read the arguments at a high level, and they make sense to me.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper provides some better results on a problem studied by some previous work.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "This paper provides a reduction from online multicalibration to online linear-product optimization, which is similar to the connection between calibration and online linear optimization. The result is an improvement, and the reduction provides some new understanding of the online multicalibration problem.", "other_comments_or_suggestions": "There is one typo that needs to be fixed at the end of Appendix C but does not hurt understanding.", "questions_for_authors": "I am wondering if the authors can confirm that their results also provide the same upperbound for online omniprediction for free since l1-multicalibration error is an upper bound for omniprediction error in the offline setting.\n\nAlso, does the lower bound in online expected calibration error also a lower bound for online multicalibration? I think it would be nice if the authors could discuss a bit in related work.", "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": "", "extra_scores": {}}, {"review_id": "D7Q92xwTyp", "reviewer": "Reviewer_F47Q", "summary": "The paper studies an online prediction setting, where a learner wished to minimize $\\ell_1$ multicalibration error with respect to a class of real-valued predictors $\\mathcal{H}$ that act as group selection functions. The authors propose an algorithm that obtains an error rate of $O(T^{-1/3})$, through reducing the problem to an online problem they term online linear product minimization, which they solve by an linearizing the reward function by enumerating over all $h\\in\\mathcal{H}$, and running an algorithm that employs an algorithm for the expert setting over $\\vert\\mathcal{H}\\vert$ online linear optimization algorithms (\"meta-experts\"), one for each $h\\in\\mathcal{H}$. They then show how to extend their result to non-finite classes $\\mathcal{H}$ using the technique of covering numbers and finding a finite cover for $\\mathcal{H}$. Finally, the authors consider obtaining online $\\ell_1$ multicalibration with oracle-efficient algorithms (which do not require enumerating over all of $\\mathcal{H}$, but instead assume access to an offline optimization oracle), for which they show an algorithm based on a reduction to the generalized FTPL framework (Dudik et al. 2020), and obtaining an error rate of $O(T^{-1/4})$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation of our paper, and for pointing us towards the paper [NRRX'23]. Please refer to the response to Reviewer~uPiD.", "claims_and_evidence": "The paper is purely theoretical. I have only glanced at the appendix with the proofs, but the claims appear to be substantiated.", "methods_and_evaluation_criteria": "N/A.", "theoretical_claims": "I did not.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "The paper is studying online $\\ell_1$ multicalibration and provides: (a) (computationally inefficient) algorithm that improves error rates over prior work (Gupta et al. 2022, Lee et al. 2022) (though Noarov et al. may implicitly still obtain the same bounds, see question to authors) and extensions to non-finite classes, and (b) oracle-efficient algorithm obtaining a faster error rate than known in prior work (Garg et al. 2024), and under milder assumptions (offline oracle instead of online regression oracle).", "essential_references_not_discussed": "Most of the relevant related work appears in in manuscript. An exception is \"High-Dimensional Prediction for Sequential Decision Making\" by Noarov et al. 2023 that I believe is highly relevant and is not discussed. I believe that using their approach of obtaining subsequence regret guarantees can be utilized when each subsequence is defined by $h\\in\\mathcal{H}$, and optimizing over the number of buckets in the prediction should obtain similar bounds of $O(T^{-1/3})$.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is very well-written and presentation is clear and concise. I enjoyed reading it.\n2. The problem is clearly motivated, and is rather central in the domains of fairness/uncertainty estimation.\n3. The result on obtaining $O(T^{-1/4})$ $\\ell_1$ multicalibration with an oracle-efficient algorithm and an offline oracle I believe is novel and very interesting, as well as the bounds for non-finite classes in the first part of the paper.\n\nWeaknesses:\n1. Novelty of the $O(T^{-1/3})$ bound using an inefficient algorithm in the finite case, please see questions section.", "other_comments_or_suggestions": "-", "questions_for_authors": "Can the approach in Noarov et al. 2023 for subsequence regret be utilized to derive similar bounds of $O(T^{-1/3})$ for $\\ell_1$ multicalibration? Can you elaborate on the differences?", "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": "", "extra_scores": {}}, {"review_id": "E1kWz6rfP3", "reviewer": "Reviewer_avZG", "summary": "The paper studies the problem of online multicalibration for L1 norm. The paper proposes a method with theoretical guarantees. The key contribution is based on the reduction of online L1-multicalibration to an online learning problem.\n\n### update after rebuttal\nI am maintaining the current score following the rebuttal.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and positive evaluation of our paper.", "claims_and_evidence": "These claims are well-supported through theoretical analyses and mathematical proofs.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "The theoretical contributions are sound. The idea on extending the algorithms to a more general setting make sense. The proposed OLPO is novel.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The results improve the prior work on online multicalibration (Gupta 2024, Garg 2024).   In particular, the error rate when H is finite is improved from $O(T^{-1/4})$ in Garg 2024 to  $O(T^{-1/3})$ in this paper. Morever, the oracle-efficient bound is also improved from  $O(T^{-1/8})$ in Garg 2024 to  $O(T^{-1/4})$.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "1. The paper is very well-written and the maths appears to be rigorous.\n2. The paper proposed an approach that only takes a polynomial number of call to an optimization oracle, greatly improve the no-regret algorithm for OLPO.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "", "extra_scores": {}}, {"review_id": "2cf5LZDCtW", "reviewer": "Reviewer_uPiD", "summary": "The paper focuses on the online multicalibration task, for which it (1) presents a O(T^{2/3})-ECE error algorithm, thus matching the best known constructive efficient bounds for vanilla calibration; and (2) presents an oracle-efficient algorithm that obtains O(T^{3/4}) multicalibration ECE error given access to a certain offline oracle. \n\nBoth results above are achieved by developing a new online prediction framework that the authors called online linear product optimization (OLPO), which is distinct from online convex optimization. They also develop a linearized variant of OLPO, which helps obtain the first contribution.  They obtain the second contribution via implementing (non-linearized) OLPO via the oracle-efficient FTPL technique of Dudik et al (2020), which works under two certain conditions. They then show that for the natural \"transductive\" and \"small-separator\" classes of group families, these conditions always hold.\n\n#######\nUpdate after rebuttal:\nI have read the authors' response. It addresses my concerns by promising to include additional discussion of the reference, and I therefore keep my original score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for pointing us towards this relevant reference. \nAfter reviewing their results, we agree that their framework can be used to derive bounds for online $\\ell_1$-multicalibration, and we outline a high-level approach for binary-valued hypothesis classes below.\nFix a $h \\in \\mathcal H$ and denote the collection of events \n$\\mathcal E := \\{E_{h,i}: h \\in \\mathcal H \\text{ and } i \\in \\{0,\\ldots,m\\} \\}$ \nwhere $E_{h,i}(x,p) = \\mathbb{I}[h(x_t) = 1, p_t = i/m]$. Further, denote $T_{h,i} := \\sum_{t=1}^T \\mathbb{I}[h(x_t) = 1, p_t = i/m]$ and note that this is equal to $\\sum_{t=1}^T E_{h,i}(x_t,p_t)$. Also note that $\\sum_{i = 0}^m T_{h,i} \\leq T$. Then, applying Theorem~3.4 of the reference together with the halfspace oracle, one would obtain\n$$\nK_T(\\pi,h) \\lesssim \\sum_{i = 0}^m \\sqrt{T_{h,i} \\cdot \\log (2|\\mathcal H|mT)} + \\frac{T}{m} \\leq \\sqrt{mT \\cdot \\log (2|\\mathcal H|mT)} + \\frac{T}{m},\n$$\nand then optimizing over the discretization level $m$ gives the result.\n\nIt is worth noting that the algorithmic framework in the paper [NRRX'23] is quite different, despite both works using an expert routine. In particular, the work [NRRX'23] requires a small-loss regret bound to get the result, while we do not. \nAdditionally, we believe our algorithm is much simpler (e.g. not requiring the solution of any min-max optimization problem) and the reduction to OLPO is of independent interest as it facilitates the oracle-efficient results in a more natural and modular way.\nWe will certainly include a discussion of this connection in the related work section to provide better context and contrast our contributions with theirs.\n\nFinally, thank you for the presentational feedback. We agree and we would be happy to move this derivation (at least the statements of the conditions, if not the full proof) to the main body of the paper.", "claims_and_evidence": "Yes, the claims made in the submission are supported by convincing evidence in the form of proofs.", "methods_and_evaluation_criteria": "N/A --- this paper presents a theoretical contribution only.", "theoretical_claims": "Yes, I checked the bulk of proofs and statements in the main part and in the supplementary, and believe them to be correct --- possibly modulo some small unchecked technicalities.", "experimental_designs_or_analyses": "N/A --- this paper presents a theoretical contribution only.", "relation_to_broader_scientific_literature": "There exists a large prior literature on online vanilla calibration, and a smaller but substantial literature on online multicalibration and related methods. Relative to this latter literature, this paper obtains new algorithms for online multicalibration with rates matching the (near-) best known rates for vanilla calibration, as well as the first oracle efficient algorithm. \n\nFor the latter, oracle efficiency, part, the closest-related prior work is (Garg et al, 2024), which obtained oracle efficient online omniprediction (a closely related but distinct task), but the sense in which Garg et al's was an oracle-efficient algorithm required access to an online (regression) oracle, whereas the present paper shows in its setting that an offline oracle can suffice, and do so via novel arguments in their developed framework, connecting it to the oracle efficiency afforded by an adaptive FTPL algorithm of Dudik et al. \n\nFor the former contribution, that is, the O(T^{2/3}) L1 multicalibration rate, I believe this rate is already subsumed by an existing online unbiased prediction framework (https://opt-ml.org/papers/2023/paper96.pdf); see below. The OLPO algorithm and framework used by this paper to obtain this result is similar but appears distinct from the former framework (the two frameworks might possibly be duals of each other in some sense).", "essential_references_not_discussed": "The following paper [NRRX'23] (https://opt-ml.org/papers/2023/paper96.pdf) contains what appears to be a highly related framework for online unbiased vector-valued prediction, where in their case unbiasedness is stated with respect to general events that may depend on the context and on the predictions themselves. In particular, their method already attains O(T^{2/3}) L1 multicalibration as an immediate corollary. Namely, discretizing into m uniform buckets and defining conditioning events for each pair (group, bucket), their framework gives, for each group after T rounds, L1 calibration on every group bounded as: T/m (accumulated discretization error over the T rounds) + O(\\sum_{buckets i} \\sqrt{number of rounds prediction fell into bucket i}). In the worst case when each bucket appears in T/m rounds this leads to the bound O(T/m + \\sqrt{Tm}) = O(T^{2/3}) for the standard choice m = T^{1/3}.\n\nBeyond this result, it appears that the OLPO is quite related to this unbiased framework, with both reducing to applying the combination of experts + OCO algorithms, so it appears important for context to discuss this connection in some detail.", "other_strengths_and_weaknesses": "Overall, I believe that the main strength of this paper lies in its carefully built framework that allows to exploit the oracle-efficient FTPL technique in this setting. While oracle efficient FTPL is clearly a possible candidate subroutine to guarantee oracle efficiency in this and many other online settings, it remained unclear in the online calibration literature until now how to connect this setting so that this subroutine can be exploited. This paper does that, and also makes a first step to identify: under what conditions can group families induce this efficient oracle algorithm? Similarly, also instructive and fruitful are the careful techniques exploiting the calibration halfspace oracle of Abernethy et al (2011) that are involved in the first part of the paper. Another strength is that the paper is well-written.", "other_comments_or_suggestions": "A presentational suggestion: I believe the derivation in the last appendix, which confirms the two conditions in the case of transductive and small separator set groups, is actually quite important for the reader to ingest, so I think it is wise to move it to the main part of the paper --- indeed, it nicely clarifies the applicability of the novel oracle-efficient construction.", "questions_for_authors": "The main question that I have is a substantive comparison to the reference above --- beyond the O(T^{2/3}) L1 multicalibration implication, OLPO appears to share some essential algorithmic features with the proposed framework here, seeing as both frameworks rely on appropriately linearizing the task into a combination of an experts algorithm to aggregate over the \"groups\", and on an online convex optimization method to form actual predictions.", "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": "", "extra_scores": {}}, {"review_id": "5SyTYIB6wP", "reviewer": "Reviewer_4b8V", "summary": "This paper tackles the challenge of online multicalibration. The key contribution of this paper is theoretical: the paper proposes a method that achieves improved rate of O(T^-1/3) and oracle efficient rate of O(T^-1/4). The key insight is that one can reduce the L1 multicalibration problem into an online linear-product optimization problem (OLPO).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s concern regarding the theoretical nature of our work. While our contributions are indeed theoretical, we believe ICML is an appropriate venue for the following reasons. (1) Relevance to Core ML Problems: Multicalibration — and online multicalibration in particular — is a key problem at the intersection of machine learning, fairness, and sequential decision-making. Recent ICML papers (e.g., on online learning, calibration, multigroup fairness, omniprediction) have explored similar themes, indicating strong interest from the ICML community.\n(2) Methodological Advancement: Our work introduces a new online learning problem (OLPO) — and gives a reduction similar to one that was obtained for online calibration and OLO. \n(3) Precedent: Similar works were published at ICML; see, e.g., Noarov and Roth (2023), Globus-Harris et al. (2023). In fact, the original multicalibration paper, Hébert-Johnson et al. (2018), also appeared in ICML.\nWorks on online learning, optimization and oracle-efficient online learning also regularly appear at ICML.\n\n$Regarding \\ the \\ motivation$: While our work does improve upon existing error rates, our motivation is broader: online multicalibration is a key tool for ensuring fairness and reliability in sequential prediction settings, which arise in many real-world applications. Our contributions aim to make this framework both statistically and computationally efficient. We will revise the introduction to better highlight this broader motivation and its relevance to the ML community.", "claims_and_evidence": "Yes, claims are usually backed up with references or motivation.", "methods_and_evaluation_criteria": "The paper does not provide any evaluation of the proposed approach.", "theoretical_claims": "The paper is extremely heavy on theory and I did not check the correctness of proofs.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "The paper improves upon existing literature by improving the oracle efficient rate from T^-1/8 to T^-1/4, and the online multicalibration rate from T^-1/4 to T^-1/3. Also, the paper mentions connections with omnipredictions.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "# Main Strengths:\n\n1. The paper tackles the multicalibration problem, which is a nice property that models should've to output precise probabilities. By analyzing theoretically the proposed solution, the paper improves the convergence rate;\n\n2. Several results are provided, showcasing the importance of online multicalibration;\n\n# Main Weaknesses:\n\n1. The paper is extremely heavy on theory. I wonder whether ICML is the proper venue to present such findings or another conference (e.g., theoretical computer science) could be a better fit;\n\n2. The structure of the paper is not ideal: first results are provided (Sec 1), and after they are proved (Sec 2). Also, I do not understand how 1.1 and the next subsections could fit into the introduction. I'd rather have a Sec 2 starting from 1.1;\n\n3. Although the paper presents a pseudo-code for the proposed algorithm, seeing results on toy data would improve the quality of the paper;\n\n4. The motivation underlying the paper is hidden, and it seems to simply be \"this existing paper achieves the following guaranteed error, can we do better?\". The point of why this is relevant should be highlighted.", "other_comments_or_suggestions": "Overall, I don't feel like the community at ICML could benefit from these theoretical results and probably another venue could be a better fit. However, I am open to change my mind, should the other reviewers be positive on the paper.", "questions_for_authors": "NA", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper considers the online multicalibration problem, and develops T^(2/3) and T^(3/4) regret algorithms for the oracle-inefficient and oracle-efficient case. The reviewers pointed out that the T^(2/3) regret for the oracle-inefficient case can be achieved by a recent work of Noarov et al. 2023. However, this does not detract that much from the quality of the paper, since the proposed algorithm is very different. In addition, the oracle-efficient guarantee is significant and novel. The results should be of interest to the ICML audience, though I recommend that the authors rewrite things a bit to make it more readable for a broader audience.
Decision: Accept (poster)