Improved Bounds for Swap Multicalibration and Swap Omniprediction
Authors: Haipeng Luo
Spandan Senapati
Vatsal Sharan
Venue: NeurIPS 2025 spotlight ()
Keywords: (Swap) Multicalibration
(Swap) Omniprediction
(Swap) Agnostic Learning
Contextual Swap Regret
Primary area: theory
TL;DR: We prove improved bounds for swap multicalibration, swap omniprediction, and swap agnostic learning in both the distributional and online settings.

Abstract: In this paper, we consider the related problems of multicalibration --- a multigroup fairness notion and omniprediction --- a simultaneous loss minimization paradigm, both in the distributional and online settings. The recent work of Garg et al. (2024) raised the open problem of whether it is possible to efficiently achieve $\tilde{\mathcal{O}}(\sqrt{T})$ $\ell_{2}$-multicalibration error against bounded linear functions. In this paper, we answer this question in a strongly affirmative sense. We propose an efficient algorithm that achieves $\tilde{\mathcal{O}}(T^{\frac{1}{3}})$ $\ell_{2}$-swap multicalibration error (both in high probability and expectation). On propagating this bound onward, we obtain significantly improved rates for $\ell_{1}$-swap multicalibration and swap omniprediction for a loss class  of convex Lipschitz functions. In particular, we show that our algorithm achieves $\tilde{\mathcal{O}}(T^{\frac{2}{3}})$ $\ell_{1}$-swap multicalibration and swap omniprediction errors, thereby improving upon the previous best-known bound of $\tilde{\mathcal{O}}(T^{\frac{7}{8}})$. As a consequence of our improved  online results, we further obtain several improved sample complexity rates in the distributional setting. In particular, we establish a $\tilde{\mathcal{O}}(\varepsilon ^ {-3})$ sample complexity of efficiently learning an  $\varepsilon$-swap omnipredictor for the class of convex and Lipschitz functions, $\tilde{\mathcal{O}}(\varepsilon ^{-2.5})$ sample complexity of efficiently learning an $\varepsilon$-swap agnostic learner for the squared loss, and $\tilde{\mathcal{O}}(\varepsilon ^ {-5}), \tilde{\mathcal{O}}(\varepsilon ^ {-2.5})$ sample complexities of learning $\ell_{1}, \ell_{2}$-swap multicalibrated predictors against linear functions, all of which significantly improve on the previous best-known bounds.

Improved Bounds for Swap Multicalibration and Swap Omniprediction
Haipeng Luo" USC haipengl@usc.edu
Spandan Senapati"
Vatsal Sharan" USC vsharan casrce@@uscedu
USC ssenapat@usc.edi
Abstract
In this paper, we consider the related problems of multicalibration multigroup fairness notion and omniprediction - a simultaneous loss minimization paradigm, both in the distributional and online settings. The recent work of Garg et al. (2024) raised the open problem of whether >-multicalibration error against bounded linear functions. In this paper, we answer this question in a strongly affirmative sense. We propose an efficient algorithm that achieves ÖTT) E2-swpp multicalibration error (both high probability and expectation). On propagating this bound onward, we obtain significantly improved rates for fwss multicalibration and swap omniprediction for a loss class con- vex Lipschitz functions. In particular, we show that our algorithm achieves Õ(T5) f1-swap multicalibration and swap omniprediction errors, thereby improving upon the previous best-known bound of Ō As consequence of our improved online results, we further obtain several improved sample complexity rates in the distributional setting. In particular, we establish a O( sample complexity of efficiently learning an E-swap omnipredictor for the class of convex and Lipschitz functions, ( sample complexity of efficiently learning an e-swap agnostic learner for the squared loss, and Ó 5), Ö( 2.5) sample complexities of learn- ing ε swwp multicalibrated predictors against linear functions, all of which significantly improve on the previous best-known bounds.
possible efficiently achieve Ó
Introduction
Recent years have witnessed surprising connections between multicalibration - multigroup faimess perspective (Héhert-Johnson al., 2018) and omniprediction paradigm, first introduced by Gopalan et al. (2022a). In this paper, we consider multicalibration and omniprediction in both the distributional (offline) and online settings. We begin by introducing these two notions, starting with some notation. Let the instance space be X' C Rdd label set be ) = {0, }}. D be an unknown distribution over X' x YV, 8 [0, 1] x> y + R be a loss function, L be class of loss functions, F be collection of hypotheses over X', and X' + [o, 1] be predictor. Multicalibration (for Boolean functions, e.g., Boolean circuits, decision trees Hébert-Johnson et al. (2018) as mechanism to incentivize fair predictions. For Boolcan functions, multicalibration can be interpreted as calibration (the property that the predictions of p are correct conditional on themselves, i.e., = E[ylp(x)
simultaneous loss minimization
{0. 1)2²) was introduced by
e) for all E Range(p)). which is additionally conditioned on set membership. In its most general form, for an arbitrary bounded hypothesis class F C x multicalibration translates to the understanding that the hypotheses in F do not have any correlation with the residual error y p(x) when conditioned on the level sets of p. On the other hand, omnipredictors are sufficient statistics that simultaneously encode loss-minimizing predictions for
Author ordering is alphabetical.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

broad class of loss functions L. Notably, omniprediction generalizes loss minimization for a fixed loss function (agnostic learning (Haussler, 1992)) to simultaneous loss minimization. Since different losses expect different "types" of optimal predictions (e.g., for the squared loss E(p, y) = (p y)², the optimal predictor p that minimizes the expected risk E[((p(xr), v)] is the Bayes optimal predictor Ely[a]], where as for the l fi-loss E(p, y) | yl the optimal predictor is [[]]v[]]] 2 0.5)) such a simultaneous guarantee is made possible by a ppost-processingg or "type-checking" of the predictions (a univariate data free minimization problem) via loss specific function ke, ie., for each & E C. ky o p incurs expected loss that is comparable to the best hypothesis in F.
Even though multicalibration is not stated in the context of loss minimization, the first construction of an efficient omnipredictor for the class of convex and Lipschitz functions L in Gopalan et al. (2022a) was achieved via multicalibration, thereby representing surprising connection between the above notions. However, multicalibration is not necessary for omniprediction (Gopalan et al., 2022a), thereby raising an immediate question related to the characterization of omniprediction in terms of sufficient and necessary condition. Motivated by the role of swap regret in online learning and to explore the interplay between multicalibration and omniprediction, Gopalan et al. (2023b) introduced the concepts of swap multicalibration, swap omniprediction, and an accompanying notion swap agnostic learning, and also established computational equivalence between the above notions. Informally, each of the above notions is a stronger version of its non swap variant, and requires a particular swap-like like-ike guarantee (specific to the considered notion) to hold at the scale of the level sets of the predictor, e.g., for swap agnostic learning, the predictor p is required to have a loss that is comparable to the best hypothesis in F not just overall but also when conditioned on the level sets of p.
Despite the qualitative progress in understanding the interplay between swap omniprediction and swap multicalibration in both the distributional (Gopalan et al., 2023b) and online settings (Garg et al., 2024), quantitative statistical treatment for the above measures has a huge scope of improvement even for the quintessential setting when the hypothesis class comprises of bounded linear functions Flin. In particular, the existing bounds for swap omniprediction and Ey-swap multicalibration in the online setting as derived by Garg et al. (2024) are much worse than the corresponding bounds for online omniprediction (Okoroafor et al., 2025) and fz-calibration (Luo et al., 2025; Fishelson et al., 2025; Foster and Hart, 2023; Foster and Vohra, 1998) respectively. Even more, the sample complexity of learning efficient swap omnipredictor for the class of convex Lipschitz functions Love with error at most e is R e -0 (Gopalan et al., 2023b), which is prohibitively large. Along the lines of the above concern, Garg et al. (2024) devised an efficient algorithm with Ö( ) f2-swap multicalibration error after T rounds of interaction between a forecaster and an adversary, and raised the problem of whether it is possible efficiently achieve Õ(VT) Iy-multicalibration error against Jzin In this paper, we answer this question in a strongly affirmative sense by proposing an efficient algorithm that achieves Ö ) f2-swap multicalibration error against F.iin. On propagating the above bound onward, we obtain significantly improved rate for swap omniprediction for L Subsequently, using our improved rates in the online setting, we construct efficient randomized predictors for swap omniprediction and swap agnostic learning in the distributional setting and derive explicit sample complexity rates, which significantly improve upon the previous best-known bounds.
Contributions and Overview of Results. Throughout the paper, we consider predictors p such that Range(p) C Z, where Z = {0, 1 ..... N-1 1} is a finite discretization of [o, 1] and N is parameter to be specified later. Similarly, in the online setting, we consider forecasters that make predictions that lie in Z. Our contributions are follows.
In Section 2. propose an efficient algorithm that achieves (T f2-swap multicalibration error (both in high probability and expectation) against the class of d-dimensional linear functions Flin. In contrast to our result, Garg et al. (2024) achieved a Ö(T d) bound by reducing 42-wap multicalibration the problem of minimizing contextual swap regret an extension of swap agnostic learning to the online setting. Towards achieving this improved rate, we proceed in the following manner:
1. We introduce the notions of pseudo swap mullicalibration and pseudo contextual swap regret where the swap multicalibration error (swap regret respectively) is measured via the the conditional distributions Pi...., Pr rather than the true realizations Pl.....PP .r. Subsequently.
2

---

in Section 2.2. in similar spirit to Garg et al. (2024), we establish a reduction from pseudo swap multicalibration to pseudo contextual swap regret.
2. By not taking into account the randomness in the predictions, the pseudo variants are often easier to optimize. Indeed, in Section 2.3, we propose deterministic algorithm that achieves o(T pseudo contextual swap regret. In contrast, for contextual swap regret, Garg et al. (2024) established Ó(T d) bound by using the reduction from swap regret to external regret as proposed by Ito (2020). To achieve the desired bound for pseudo contextual swap regret, we use the Blum- MunnMr (BM) reduction (Blum and Mansour, 2007) instead. On high level, the key to the improvement from T (contextual swap regret) to T (pseudo contextual swap regret) the following: Garg et (2024) derived a ÓTTyN NVT)) bound on the contextual swap regret, where the (1//N) term accounted due to a rounding operation (additively accounted for 7 rounds) and the V(NVT) term is due to a concentration argument, which is inevitable since the reduction by Ito (2020) is randomized. However, by using the BM reduction and an improved rounding procedure due to Fishelson et al. (2025), we propose a deterministic algorithm that achieves (TT/N² + .) bound on the pseudo contextual swap regret, where the (1/N2²) term is due to the rounding operation and the (N) term is because each of the N external regret algorithms in the BM reduction can be instantiated to guarantee (1) external regret against bounded linear functions. The desired result follows by choosing N = é
3. Using the reduction from pseudo swap multicalibration to pseudo contextual swap regret, we obtain Ö(T bound for the former. Noticeably, since the swap multicalibration error is possibly random and our algorithm for minimizing pseudo swap multicalibration is deterministic, we derive concentration bound in going from pseudo swap multicalibration to swap multicalibration. By performing a martingale analysis using Freedman's 's inequality (Lemma Appendix B), we show that this only accounts for a ((N) deviation term, which does not change the final rate.
In Section C in the appendix, multicalibration. Particularly, in Section C.I, we show that our algorithm from Section 2.3 achieves 3(T3d) swap omniprediction error for C against Falf, where Falf a class of appropriately scaled and shifted linear functions. This significantly improves upon the ④ ) rate of Garg al. (2024). In Section C.2, we show that the same algorithm (with a different choice of the discretization parameter N) achieves 3 contextual swap regret, which improves upon the ÖT d) bound Garg et al. (2024). We summarize a comparison of our results to the ones derived by Garg et al. (2024) in Table 1.
we explore several consequences of our improved rate for fz-swap
contextual swap regret (A)
sw-swap multicalibration (B)
f--swap multicalibration (C)
swap omniprediction
pseudo contextual swap regret (E)
E2-pseudo swap
multicalibration (F)
Figure 1: Path A + C-+ D Depreseens the sequence of reductions followed by Garg et al. (2024), whereas path E + F B D represents our road-map. To derive an improved guarantee for B, we establish: (i) a Ö(T') bound for E; (ii) a reduction from E to F; and (c) a concentration bound from to B. The improved guarantees for and follow as a consequence the improvement in B. The improved guarantee for A follows due to E and concentration bound from E to A.
We remark that although relevant ideas for the above steps have appeared the literature, our paper successfully unifies them in a novel framework to achieve state-of-the-ar bounds for swap multicalibration and swap omniprediction. Refer to Figure for summary of our framework. For detailed comparison with prior work, refer to the section related work.
As consequence of our improvements the online setting, we establish several improved sample complexity rates in the distributional setting. Towards achieving we perform an online-to- batch conversion (Cesa-Bianchh) et al., 2004) using our online algorithm in Section 2.3 to obtain a randomized predictor p that mixes uniformly over the I' predictors output by the online algorithm.
3

---

Table 1: Comparison of our rates with the previous best-known bounds. For simplicity, we only tabulate the leading dependence on E. The first 4 rows correspond to regret/error bounds (as function of '') in the online setting, whereas the last 4 rows correspond to sample complexity bounds (as function of é) in the distributional setting.
ONLINE (REGRET/ERROR) AND DISTRIBUTIONAL (SAMPLE COMPLEXITY) BOUNDS
Quantity
Previous bound
Our bound
Contextual swap regret
( )
(Garg et al., 2024)
O ) (Theorem 3)
f2-swap multicalibration
O(T)) (Garg et al., 2024)
O(Tš) (Theorem 1)
s-wwa multicalibration
O(T5) ) (Garg et al., 2024)
O ) (Corollary 1)
Swap omniprediction
O(T%) (Garg et al., 2024)
O(TS) (Theorem 2)
Swap agnostic error
O Haobuus-Harris et al.,
O 225) (Theorem 5)
2023)
sw-s multicalibration
Ö (Globus- Harris et al., 2023)
O 2.5) (Theorem 6)
f--swap multicalibration
((s-10) (Hébert-Johnson et al., 2018; Globus-Harris et al., 2023)
O (Theorem 6)
Swap omniprediction
O( 10) (Hébert-Johnson et al., 2018; 8; Globus-Harris et al., 2023)
O (Theorem 4)
In Section D.I in the appendix, we show that 2 e samples are sufficient for to be a swap om- nipredictor for _ against Faff with error at most e. To prove this, we obtain tight concentration bound that relates the swap omniprediction errors in the distributional and online settings. Our arguments in deriving the concentration bound are motivated by a recent work by Okoroafor et al. (2025), who proposed similar online-to-batch conversion for omniprediction. However, compared their result, an online-to -itiie--t-btchh conversion for swap omniprediction poses several other technical nuances. In particular, unlike Okoroafor et al. (2025), we cannot merely use Azuma-Hoeffding Hoeffdingg s inequality or related concentration inequalities that guarantee concentration to a v factor (n is the number of random variables). By performing a careful martingale analysis using Freedman's 's in- equality on a geometric partition the interval [0, 1], we finally establish the desired concentration bound.
In Section D.2, we specialize to the squared loss and show that 2 5- 2.5 samples are sufficient for achieve swap agnostic error e. Notably, since the squared loss convex and Lipschitz, the result of Section D.1 already gives Ō sample complexity. However, specifically for the squared loss, we derive concentration bound that relates the contextual swap regret with the swap agnostic error. As we show, this bound is tighter than the corresponding deviation for swap omniprediction. Combining this with an improved Ö(Tê) bound for contextual swap regret compared to swap omniprediction (Ō(T)) )) we obtain the improved sample complexity. Finally, in Section D.3, by using characterization of f2-swap multicalibration in terms of swap agnostic learning (Globus- Harris et al., 2023; Gopalan al., 2023b), establish -.55 sample complexity for f2-swap multicalibration, and thus ((e-5) 5) for swap multicalibration against J:lin We summarize our results and the previous best-known bounds in Table 1. For discussion regarding the previously best-known bounds, refer to the section on additional related work (Appendix A).
1.1 Preliminaries
For simplicity, we give formal definitions of several notions considered in the paper in the online setting, and defer definitions for the distributional setting to Appendix D.
Online (Swap) Multicalibration. Following Garg et al. (2024), we model online (swap) multicali- bration as a sequential decision making problem over binary outcomes that lasts for T time steps. At each time t E [T]: (a) the adversary presents context 2, E X; (b) the forecaster randomly

---

predicts ~ Pt. where Pi E Ag represents the conditional distribution of Pr; and (c) the adversary reveals the true label 1/2 y. For simplicity in the analysis, throughout the paper we assume that the adversary is oblivious, i.e., it decides the sequence V1),-. (IT, MT) at time 0 with complete knowledge about the forecaster's algorithm, although our results readily generalize to an adaptive adversary. For each p 2, letting Pp.j 21-1 plp=p//aaa(y be the empirical average Ex 1pp=pp]
of the correlation of f with the residual sequence (y/ pol (conditioned on the rounds when the prediction made is Pt p), the lg -swap multicalibration error incurred by the forecaster is defined as
T
T Σ 1=1
SM =
sup MpE BeE PEZ
Σ
Σ t=
Mpp = rl) |pp.sol== = =E PEZ
Tpr =
sup 1pp,sl" (1) JEF
We also introduce a new notion - pseudo swap multicalibration, where the swap multicalibration enror measured via the conditional distributions P1 PI...., Pr rather than the true realizations P...... PT.
Particularly, letting Pp.s = Σi ((xp)) we define the by pseudo swap multicalibration Diz Pe(p)
error incurred by the forecaster as
PSMCal = sup Σ (LET)REZ PE2 [=1
10o.1o1== Σ PEZ t=1
Σ
sup Pi(p)
løp.1l (2)
JeF
As we shall see, by not taking into account the randomness in the predictions, pseudo (swap) multicalibration is often easier to optimize. Note that, (pseudo) multicalibration ((P) is special case of (pseudo) swap multicalibration where the comparator profile is Sp = for all E Z:
MCal
sup fEF PEZ
Σ
Σ Upr = pl lparl" PMCal sup Σ JEF PEZ
Σ B((0))
lōp. (3)
and calibration (Cal,)) is a further restriction of multicalibration to F= {1), where denotes the constant function that always outputs 1. In this paper, shall be primarily concerned with the l,, f2-(pseudo) (swap) multicalibration errors, which are related as PSMCal S VT PSMCal
PMCalF,1 S /T PMCal SMCal5,1 S v SMCal MCal=,1 /T MCal The proof (skipped for brevity) follows trivially via the Cauchy-Schwartz inequality.
Online (Swap) Omniprediction. Omnipredictors are sufficient statistics that simultaneously encode loss-minimizing predictions for broad class of loss functions L. Since different losses expect different "types" of optimal predictions, the output of an omnipredictor has to be "post-processed" or ttype-checked" via loss specific function
[0. 1] - [o, 1] approximately minimize & relative to the hypotheses in F. The post pusst-roceesing function ke is chosen to be best-response function, i... ke(q) = argmin po (yy) [[(p. 3)] denotes the prediction that minimizes the expected loss for y Ber (q). Online omniprediction follows similar learning protocol as that of online multicalibration described above, however, equip our protocol with learners (parametrized by loss functions) who utilize the forecaster's predictions to choose actions. In particular, after the forecaster predicts pt. each l-learner (l L) chooses action ke(pt) and incurs loss ((ke(pe), Wt). The swap omniprediction error against a loss profile {Ep pppp,, comparator profile (frlpez is defined as
T
50mni (fep)ee,, (fphpzz) = Σ Ep. (pt). v.) (Fp. (2z). yc).
The swap omniprediction error incurred by the forecaster is then defined as a supremum over all loss, comparator profiles, i.e., SOmnic,r sup(e, S0mni ((lp pez, (p)pez). Omniprediction is special case of swap omniprediction where the loss, comparator profiles are fixed and independent of p.
In the distributional setting, a computational equivalence between swap multicalibration and swap omniprediction was established in Gopalan al. (2023b) via an intermediate notion - -swap agnostic learning, which was extended to the online setting by Garg et al. (2024) contextual swap regret.
5

---

Contextual Swap Regret. Throughout the paper, we consider contextual swap regret for the squared loss. Contextual swap regret a special case of online swap omniprediction when {{}
and p(. y) (p y)², so that ke(p) = p. Similar to pseudo swap multicalibration, we also introduce a new notion - pseudo contextual swap regret:
PSRegy=
sup EfETl
Σ Ep [(D: - ye)) (fr.(1e) - -30) )=
(5)
Other Notation. For any m E N. let [m] == f1,2....,m?? mZ denote the index set. We use bold lowercase letters to represent vectors and bold uppercase letters for matrices. The indicator function is denoted by I[-], which evaluates to 1 if the condition inside the braces is true, and 0 otherwise. For any k E N. we define A& as the (k- - 1)-dimensional probability simplex: A = (a E
Rk;;; I4 2 0 for all E [K], Ei Ij = =1}. More generally, for a set Ω2 let An denote the set of all probability distributions over Ω. A function f W + R is said be a-exp-concave over a convex set W if the function exp(-af(w)) is concave on W. The following notation is used extensively throughout the paper: given a hypothesis class F and /
we define the subset FB = {f E F; (x) S 3 for all x E X}. Finally, we use the notations (2(.), to hide lower- order logarithmic terms.
A note the organization. Due to the numerous concepts considered in this paper and the limited space available, we focus our detailed discussion on our improved bound for f2-swap multicalibration and the path E + F - B in Figure I, deferring the discussion of other results to the appendix. Readers are encouraged to keep the broader context presented in Figure 1 in mind and to note that our improved sample complexity bounds in the offline setting arise from an online-to-batch conversion.
1.2 Comparison with Related Work
We discuss comparison with the most relevant work, deferring additional discussions to Appendix A.
Calibration. For fa-calibration (Cal2), Foster and Hart (2023); Luo et al. (2025) showed that there exists an efficient algorithm that achieves Calg = Ō(Tb). ). The result of Luo et al. (2025)
builds on a recent work by Fishelson et al. (2025), who showed that it is possible to achieve Ö f2-pseudo calibration (PCal2) by minimizing pseudo (non-contextual) swap regret of the squared loss. Building on the works of Luo et al. (2025); Fishelson et al. (2025), we observe that it is possible to achieve SMCal 22 = Ö In particular, our introduction of pseudo swap multicalibration and pseudo contextual swap regret is reminiscent of pseudo swap regret by Fishelson et al. (2025). Furthermore, our Freedman- martingale analysis in going from f2-pseudo swap multicalibration to f2-swap multicalibration is largely motivated by a similar analysis by Luo et al. (2025) in going from f2-pseudo calibration to fz-calibration. Arguably, our result shows that f2- swap multicalibration and Ez-calibration share the same upper bounds, despite the former being a stronger notion.
Omniprediction. Very recently, Okoroafor et al. (2025) have shown that is possible achieve oracle-efficient omniprediction, given access an offline ERM oracle, with ( sample complex- ity (matching the lower bound for the minimization of a fixed loss function) for the class of bounded variation loss functions LBv against an arbitrary hypothesis class F with bounded statistical com- plexity. Notably, the class Lev is quite broad and includes all convex functions, Lipschitz functions, proper losses, etc. At high level, Okoroafor et al. (2025) obtain Õ( online omniprediction error by identifying proper calibration and multiaccuracy as sufficient conditions for omniprediction and proposing an algorithm based on the celebrated Blackwell approachability theorem (Blackwell, 1956; Abernethy et al., 201 I) that simultaneously guarantees Ō ((VT) proper calibration and multiaccuracy errors. The result for (offline) omniprediction then follows from an online-to-batte conversion along with other technical subtleties to make the algorithm efficient (with respect to the offline ERM oracle). Next, we highlight our comparisons with Okoroafor et al. (2025)'s result and techniques. While Okoroafor et al. (2025) analyze omniprediction in more general setting (for the class LBv against an arbitrary F), we study the harder notion of swap omniprediction but in specialized setting (for Loox C Lav, against Faff). Finally, as mentioned in the introduction, although our online-to-bates conversion in Section D.1 follows in similar spirit to Okoroafor et al. (2025), it is substantially different due to more involved martingale analysis via Freedman's 's inequality.

---

2 Achieving Ō lz-Swap Multicalibration
In this section, we propose an efficient algorithm to minimize the sw-s multicalibration error. As per Figure I, we shall reduce f2-swap multicalibration to f2-pseudo swap multicalibration, followed by reduction to pseudo contextual swap regret. Finally, we shall propose an efficient algorithm to minimize the pseudo contextual swap regret.
2.1 From swap multicalibration to pseudo swap multicalibration
Lemma 1. Let F 1-, be finite hypothesis class. For any algorithm y such that for each t E [T] the conditional distribution Pe is deterministic, with probability at least 1 - 8 over
ASMcaly 's predictions, we have SMCaly,2 S 384(N +1) log G(N+1))FF
PSMCaly:2-
The proof of Lemma 1 is deferred to Appendix B.1 and is motivated by recent result due to Luo et al. (2025) who derive a high probability bound (via Freedman's 's inequality) that relates the fz-calibration error (Cal2) with the f2-pseudo calibration error (PCalz). Particularly, our proof is an adaptation of the analysis provided by Luo et al. (2025) to the contextual setting. Note that the assumption that the conditional distribution P. is deterministic is because the algorithm we propose for minimizing pseudo contextual swap regret is deterministic, therefore the only randomness lies the sampling Pt Pa. In way, our proposed algorithm in Section 2.3 correctly aligns with the assumption. However, we remark that this assumption can be relaxed to account for the randomness in Pt.
Next, we instantiate our result for the class of linear functions with bounded norm, defined over the set X = {æ E BB;; =1 }. The requirement that each æ E X has a constant first coordinate (equal to 1/2) is without any loss of generality. More generally, we only require that each
X has constant i-th coordinate (equal to I' for some I E (0, 1)) to ensure that the class J = (fo(z) (0, e [d): is closed under affine transformations - property that shall be required later. Although not explicitly mentioned in Garg et al. (2024), we realize that they also invoke this requirement. By definition, Flin {f E Flin; [x()) < for all E } and the set of all 0's characterizing Flln satisfies BB C {0 E Rd; (0, < 1 for all æ E }} C 2 Bd. Since Ffin is infinite, the result of Lemma does not immediately apply for the choice = Fiin. Instead, to bound SMCal we form finite sized cover C. of Flin. bound SMCal 2 in terms of SMCale,,, and use the result of Lemma bound SMCalc,,a in terms of PSMCale,, 2- Recall that for function class F, function class G is E-cover if for each f E F there exists g G such that [f(z) g(x)l < for all x X. For each F, we refer to the corresponding function E G that realizes the condition as a representative. We use the following standard result (refer (Luo, 2024, Proposition 2)) to bound [C,] in the proof of Lemma 2, whose proof is deferred to Appendix B.2.
Proposition 1. There exists a cover C2 C Filn of Flin with |C&| = O (t)
Lemma 2. For the class Fiin and any 0, with probability at least 1 5, have SMCalyffr. O N log N Nd + PSMCal +²T 5
2.2 From pseudo swap multicalibration to pseudo contextual swap regret
In this section, we show that the 62-pseudo swap multicalibration error is bounded by the pseudo contextual swap regret. Notably, our result is an adaptation of a similar result proved by Garg et al. (2024) for contextual swap regret (see also Globus -arris et al. (2023); Gopalan al. (2023b) for similar characterization of swap multicalibration in terms of swap agnostic learning) to pseudo contextual swap regret. Our result holds for any arbitrary hypothesis class F satisfying the following mild assumption:
Assumption 1. F is closed under affine transformations, i.e., for each f E F, the function g(æ) = (x( + b F for all a, b e R.
We remark that the above is quite standard and has been explicitly assumed in Garg et al. (2024); Globus-Harris et al. (2023), and implicit in Gopalan et al. (2023b). Clearly, Julnn sat- isfies Assumption 1. This is because, for f F that is determined by E Rd we have
7

---

a (0, + = (a + following converse result.
2b 21 E Frln. Before proving the main implication, we prove the
Lemma 3. Assume that there exists a E 2 Fi such that Pa.s 2 a for some a > 0. Then, a².
there exists f' E F4 such that Di_ P.(p) (p-
Σi-1 P(())
The proof of Lemma 3 can be found in Appendix B.3 and is similar to (Garg et al., 2024, Theorem 3.2). In particular, consider the function fz) p + (z(z), where 17 min (1, / 1
Eis P.())(((a)))) Under Assumption f F. Furthermore, since f E Fi, we have I' E F4. Σl P((x)
then follows from direct computation that Σ. (( v=)²
2 2na - -n²H. Finally, we analyze the cases 2 μ and a < μ and derive common lower bound 21ja 1/² /1 2 a², thereby
Σi= Pr(p)
finishing the proof. Equipped with Lemma 3, we prove the main result this section.
Lemma 4. Assume that there exists > 0 such that PSRegy, S a. Then, PSMCal S a.
The proof of Lemma 4 can be found in Appendix B.4 and follows by the method of contradiction, using the result of Lemma 3. Particularly, assuming that PSMCal > a, we conclude that there exists a comparator profile {fpnnez that realizes Epez Op > at, where Op = - (p) )² By definition of Op. there exists function (x) E (fp(x), (x(()) such that Pr.1; = V El-1 P((
Op
for all p E Z. By Lemma 3, for each p E Z, there exists f E Fa that satisfies Σ === (.(p) y1)² - (2)) 7) 2 ap. Summing over all p E Z we obtain contradiction to the assumption that PSReg,, S a.
Combining the result of Lemma 2 and 4, we observe that to bound SMCaly we only require bound on PSRegzin. 2- In the next section, we propose an efficient algorithm to minimize PSReg
2.3 Bound on the pseudo contextual swap regret
Now, we give an algorithm to minimize the pscudo contextual swap regret of the squared loss (p, v) (p- y)² against the hypothesis class Fllm. Recall that for our choice of X, the set of l's that determine Flinn satisfies 2- BB C {0 E R4; (0, 1)) < 2 for all x E X C 4 Bg. We consider the more general setting when F is arbitrary and then instantiate our result for Ftin. Our general algorithm (Algorithm 3) is based on the well-known Blum-Mansour (BM) reduction (Blum and Mansour, 2007).
Before proceeding further, first recall the BM reduction (Algorithm 3 in Appendix B.5). Let 2 be enumerated as 2 = (zo...., 2N.,, J. where 2; = i/N for all E {O...., ..). The reduction maintains N 1 external regret algorithms Ao ,,, AN. At each time t, let qr.i E AN+1 denote the probability distribution over Z produced by A.. Let Q [qr.o...., qt.N] be the matrix formed by concatenating gt.0.-. Qt,N as columns. Upon receiving the context Tt. compute the stationary distribution of Q. i.e., a distribution pt E AN+1 satisfying Q.P, = Pt- With p. being our final distribution of predictions, i.c. (z)) = Pt.i. we sample Pt ~ P. and observe the outcome yt- Thereafter, we feed the scaled loss function (t, ye) to A.. Let CT,, = it RR-++1 +1 be a scaled loss vector, where (+()) = {Zz, yr). It immediately follows from Proposition 2 (Appendix B.5) that PSReg; S Eo Reg, (F), where Reg, (F) == sup ΣT
(t.:(f((za) - y:)², i.e., the pseudo swap regret is bounded by the sum of the (scaled) external regrets of the N + algorithms. It remains to design the i-th external regret algorithm A, that minimizes Reg, (J). We emphasize that A, is required to predict distribution qt. over Z and is subsequently fed a scaled loss function Pr.; (r) at each time I. To implement A,, we assume the following oracle ALG that solves a (scaled) external regret minimization problem for the squared loss (which will be later instantiated by a concrete algorithm for the linear class).
(9... 435) Ei=
Assumption 2. Let ALG be an algorithm for minimizing the (scaled) external regret against F in the following learning protocol: at every time t E [T), (a) an adversary selects context Ie E X, a scaling parameter an [0, 1), and the true label yı (b) the adversary reveals xı; (c) ALG predicts w. E [0, 1), observes 04,, yt, and incurs the scaled loss Or (wr, Wt). We assume that ALG achieves the following
external regret guarantee: E sup Et= onl (we )2 - (x((((r))) - y1)²| S rT(,F), where
8

---

F)) F) is non-negative function that captures the regret bound of ALG, and the expectation is taken over the joint randomness in the adversary and the algorithm.
To instantiate A; (Algorithm 1), we propose using ALG; (an instance of ALG for the i-th external regret algorithm) along with the randomized rounding procedure of Fishelson et al. (2025). The round- ing procedure is required because at each time t, ALG, outputs W1,, E [0, 1]. however, A, is required to predict a distribution qt.i AN+1 over Z. Towards this end, Fishelson et al. (2025) proposed the randomized rounding scheme summarized in Algorithm 2. In Proposition 3 (Appendix B.6), we show that the change in the expected loss due to rounding, i.e., the quantity Σj= (2z, v) - E(p, y) is at
most
Algorithm 1 The i-th external regret algorithm (A;))
1: for (= 1,..., T:
2: Set Wr, [0, as the output of ALG, at time (where ALG, satisfies Assumption 2);
3: Predict qr.; = (Round(we.)) (Algorithm 2);
4: Receive the scaled loss function ft,(w) = pt, yr) and feed it to ALG,,
Algorithm 2 Randomized rounding (RRound(p))
Input: p E [0, 1], Output: Probability distribution E AN+1:
Scheme: Let Ps. P.+1 for some E (O..... N 1} be two neighboring points in 2 such that
P. S < Pi+1; output q E AN+1. where qi = Pe P- 9++1 = p-pp and qj = otherwise.
Pi+1 p."
Combining everything, we derive the regret guarantee Reg, (F) of A, It follows from Proposition that at any time I, the distribution qt (wee,) satisfies (qr,s, Ra) S flwe, Me) + Nz. Multiplying with Pt, and summing over all i, we obtain
T Ep.(we y0) -(.((f(()) - yc)² -ve)²
Reg, (F) S sup feF
Pts SM(,F(
1 N2
Σ Pr.se
N
where r: FT..F) denotes the external regret bound of ALG; (Assumption 2). It then follows from Proposition 2 that
N
N
N (T,
T
PSReg
Reg (F)
(T,
N2
Pt.
N
i=0
$=0
When F= Fln. we can instantiate each ALG, with the Online Newton Step algorithm (ONS) (Hazan et al., 2007) corresponding to the scaled loss i (r.,(((0, - y²)², which is 50 exp-cccneev and 10-Lipschitz over 4 - IB (Proposition 4 in Appendix B.7). We propose to employ ONS over the set 4. BB since the set of all 0's characterizing Flln is a subset of 4 By. ONS; (Algorithm 4 in Appendix B.5) represents instance of ONS for ALG, On updating or,; via ONS,, ALG; (Algorithm 5) simply predicts Wt,; = Projjo ((01,,, I:))), where Projjo.1) denotes the projection to [0, 1). i.e., Proijo,1 (x) == yrgmingy[oo.1] [ y/-
The following lemma (due to Hazan et al. (2007)) bounds the regret of ONS,,
Lemma 5. The regret of ONS; can be bounded as supec4 (0,,) (t, = Od T).
The regret of ALG, can then be bounded as supag4.3g Et= Pi,(we, - y1 - Pt, (10, xr.) - y/, S supee4-B3 Σt= (fr.;) (0) = Od T). where the first inequality follows since (Proj( (Proj((Or,,, .x)) 2 < (10 Iz) 22 The above bound implies that (T, Od T) and PSRegym O (Nd + N²) ). Combining the result of Lemma 2 and Lemma 4 with the bound on PSRegyp, we obtain the following theorem.
Theorem 1. There exists an efficient algorithm that achieves the following bound: SMCal yf d (log T) + ( O(T d (log 3 where the expectation is taken over the internal randomness of the algorithm.
) log ()) with probability 2 1 8. Furthermore, E. gM =

---

Theorem answers the open problem raised by Garg et al. (2024). Compared to our result, Garg et al. (2024) showed that SMCaly!r. F Ô (dT log with probability at least 1 - 5. An immediate corollary of Theorem is an improved ((T5) bound on SMCal (refer Corollary 1 in Appendix B.8).
Conclusion and Future Directions
In this paper, we obtained state-of-the-ard regret/error bounds (in the online setting) and sample complexity bounds (in the distributional setting) for swap multicalibration, swap omniprediction. and swap agnostic learning. Crucially, our bound for swap multicalibration is derived in the context of linear functions, and that for swap omniprediction is obtained specifically for convex Lipschitz functions against hypothesis class that comprises linear functions. A natural question is whether it is possible to extend our framework (Figure 1) to arbitrary hypothesis, loss classes and obtain oracle-efficient algorithms (similar to Garg et al. (2024); Okoroafor et al. (2025)). Moreover, recall that we obtained ( ) and Ö bounds for pseudo contextual swap regret and contextual swap regret, respectively, which is in contrast the non-contextual setting, where both quantities enjoy the favorable O rate (Foster and Hart, 2023; Luo et al., 2025; Fishelson et al., 2025). The ( bound for contextual swap regret is limitation of our analysis in Section C.2; we suspect this can be improved by more sophisticated analysis which can also improve the sample complexity of swap agnostic learning as a by product. This improvement shall manifest in further improvements in the sample complexity of swap multicalibration as per the discussion in Section D.3.
Acknowledgements
We thank Princewill Okoroafor and Michael P. Kim for several helpful discussions. This work was supported in part by NSF CAREER Awards CCF-2239265 and IIS-1943600 and an Amazon Research Award (2024). Any opinions, findings, and conclusions recommendations expressed in this material are those of the author(s) and do not reflect the views of sponsors such as Amazon or NSF
References
Abernethy, J., Bartlett, P. L.,, and Hazan, E. (2011). Blackwell approachability and no-regret learning equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, pages 27-46. JMLR Workshop and Conference Proceedings.
Arunachaleswaran, E. R., Collina, N., Roth, A., and Shi, M. (2025). An elementary predictor obtaining distance to calibration. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1366-1370. SIAM.
Bastani, O., Gupta, V., Jung, C., Noarov, G., Ramalingam, R., and Roth, A. (2022). Practical adversarial multivalid conformal prediction. Advances in neural information processing systems, 11-29362-29377
Beygelzimer, A., Langford, J., Li, L., Reyzin, L.. and Schapire, R. (2011). Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings.
Blackwell, (1956). analog of the minimax theorem for vector payoffs.
Blasiok, J., Gopalan, P., Hu, I.., and Nakkiran, P. (2023). A unifying theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1727-1740.
Blum, A. and Mansour, (2007). From external to internal regret. Journal of Machine Learning Research, 8(6).
10

---

Casacuberta, S., Dwork, C., and Vadhan, S. (2024). Complexity-theoree theoretic implications of multical- ibration. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1071-1082.
Cesa-Bianchi, N., Conconi, A., and Gentile, C. (2004). On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 5009):050--2577.
Collina, N., Globus-Harris, I., Goel, S., Gupta, V., Roth, A., and Shi, M. (2025). Collaborative prediction: Tractable information aggregation via agreement. arXiv preprint wxXiv2554.006055.
Collina, N., Goel, S., Gupta, V., and Roth, A. (2024). Tractable agreement protocols. arXiv preprint arXiv:2411.19791.
Dagan, Y., Daskalakis, C., Fishelson, M., Golowich, N., Kleinberg, R., and Okoroafor, (2024). Improved bounds for calibration via stronger sign preservation games. arXiv preprint arXiv:2406. 13668.
Devic, S., Korolova, A., Kempe, D., and Sharan, V. (2024). Stability and multigroup faireess in ranking with uncertain predictions. Proceedings of the 41st International Conference on Machine Learning, pages 10661-10686.
Dwork, C., Lee, D., Lin, H., and Tankala, P. (2023). From pseudorandomness multi-group fairness and back. In The Thirty Sixth Annual Conference on Learning Theory, pages 3566-3614, PMLR.
Fishelson, M., Kleinberg. R., Okoroafor, P., Paes Leme, R., Schneider, J., and Teng. Y. (2025). Full swap regret and discretized calibration. In Kamath, G. and Loh, P.-L., editors, Proceedings of The 36th International Conference Algorithmic Learning Theory, volume 272 of Proceedings of Machine Learning Research, pages 444 480. PMLR.
Foster, D. P. and Hart, S. (2021). Forecast hedging and calibration. Journal of Political Economy, 129(12)
Foster, D. P. and Hart, S. (2023). "calibeating": Beating forecasters at their own game. Theoretical Economics, 1444):4441-1474
Foster, P. and Vohra, R. V. (1998). Asymptotic calibration. Biometrika, 85(2):379-390.
Garg, S., Jung, C., Reingold, O., and Roth, A. (2024). Oracle efficient online multicalibration and omniprediction. In Proceedings the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2725-2792. SIAM.
Hobuus-aarris I., Harrison, D., Kearns, M., Roth, A., and Sorrell, J. (2023). Multicalibration as boosting for regression. In International Conference on Machine Learning, pages 1459-11492. PMLR.
Gollakota, A., Gopalan, P., Klivans, A., and Stavropoulos, K. (2023). Agnostically learning single- index models using omnipredictors. Advances in Neural Information Processing Systems, 36: 14685- 14704.
Gopalan, P., Hu, L., Kim, M. P., Reingold, O., and Wieder, U. (2023a). Loss Minimization Through the Lens Of Outcome Indistinguishability. In Tauman Kalai, Y., editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informaties (LIPIcs), pages 60:1-60:20, Dagstuhl, Germany, Schloss Dagstuhl Leibniz-Zentrun für Informatik.
Gopalan, P., Kalai, A. T., Reingold, O., Sharan, V., and Wieder, U. (2022a). Omnipredictors. In Braverman, M.. editor. 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LJPles), pages 79:1-79:21, Dagstuhl, Germany. Schloss Dagstuhl - Leibniz-ZZentumm für Informatik.
Gopalan, P., Kim, M. P., and Reingold, O. (2023b). Swap agnostic learning, or characterizing om- niprediction via multicalibration. In Teirty-seventh Conference on Neurul Information Processing Systems.
11

---

Gopalan, P., Kim, M. P.. Singhal, M. A., and Zhao, S. (2022b). Low-degree multicalibration. In Conference on Learning Theory, pages 3193-3234. PMLR.
Gopalan, P., Okoroafor, P., Raghavendra, P., Sherry, A., and Singhal, M. (2024). Omnipredictors for regression and the approximate rank of convex functions. In The Thirty Seventh Annual Conference on Learning Theory, pages 2027-2070. PMLR.
Guntuboyina, A. and Sen, B. (2012). Covering numbers for convex functions. IEEE Transactions on Information Theory, 59(4): 1957-195..
Gupta, V., Jung, C., Noarov, G., Pai, M. M., and Roth, A. (2022). Online multivalid learning: Mcans, moments, and prediction intervals. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 82-1. Schloss Dugstuhl-Leibnii-Zeenne
für Informatik.
Haghtalab, N., Jordan, M., and Zhao. E. (2023). A unifying perspective multi-calibration: Game dynamics for multi-objective learning. Advances in Neural Information Processing Systems, 36:72464-72506.
Haghtalab, N., Qiao, M.. Yang, K., and Zhao, E. (2024). Truthfulness of calibration measures. In The Thirty-eighth Arnual Conference on Neural Information Processing Systems.
Haussler, D. (1992). Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and computation, 100(1):78-150.
Hazan, E., Agarwal, A., and Kale, (2007). Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169-192.
Hébert-Johnson, U., Kim, M., Reingold, O., and Rothblum, G. (2018). Multicalibration: Calibration for the coamputaiionlll--dennffii pages 1939-1948. PMLR.
masses. In International Conference on Machine Learning.
Hu, L., Tian, K., and Yang, C. (2024). Omnipredicting single-index models with multi-index models. arXiv preprint arXiv:2411.13083
Hu, L. and Wu, Y. (2024). Predict to minimize swap regret for all payoff-bounded tasks. 2024 IEEE 65th Annual Symposiun on Foundations of Computer Science (FOCS), pages 244-263. IEEE.
Ito, S. (2020). A tight lower bound and efficient reduction for swap regret. Advances in Neural Information Processing Systems, 33: 13:18590-18559
Jung. C., Lee, C., Pai, M., Roth, A., and Vohra, R. (2021). Moment multicalibration for uncertainty estimation. In Conference on Learning Theory, pages 2634-2678. PMLR.
Kleinberg, B., Leme, R. P., Schneider, J., and Teng, Y. (2023). U-calibration: Forecasting for an unknown agent. In The Thirty Sixth Annual Conference on Learning Theory, pages 5143-5145. PMLR.
Lu, J., Roth, A., and Shi, M. (2025). Sample efficient omniprediction and downstream swap regret for non-linear losses. arXiv preprint 22X.v:2502.12564.
Luo, H. (2024). Csci 678: Theoretical machine learning lecture https://haipeng- luo net/ http:////ppp..aaaeeeeeeeeeeeaaee /eettrreeeeeeeeeeeee .df.
courses/ wwt.///ee/cS//////0000/ ftt1:////222a211/// fww.//acttllls////eeaaaaaaaaaall
Luo, H., Senapati, S., and Sharan, V. (2024). Optimal multiclass u-calibration error and beyond. In
The Thirty-eighth Annual Conference on Neural Information Processing Systems (NeurIPS).
Luo, H., Senapati, S., and Sharan, (2025). Simultaneous swap regret minimization via kl-calibration.
arXiv preprint 2502:225002.6388
Noarov, G., Ramalingam, R., Roth, A., and Xie, S. (2023). High-dimensional prediction for sequential decision making. arXiv preprint arXiv:2310.17666
Obermeyer, 7.., Powers, B., Vogeli, C., and Mullainathan, S. (2019). Dissecting racial bias in an algorithm used to manage the health of populations. Science, 366(6464):447-453,,
12

---

Okoroafor, P., Kleinberg, R., and Kim, M. P. (2025). Near-optimal algorithms for omniprediction. arXiv preprint 17Xiv:2501.77205.
Qiao, M. and Valiant, G. (2021). Stronger calibration lower bounds via sidestepping. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 456-466.
Qiao, M. and Zheng, L. (2024). On the distance from calibration in sequential prediction. In The Thirty Seventh Annual Conference on Learning Theory, pages 4307 PMLR.
Roth, A. and Shi, M. (2024). Forecasting for swap regret for all downstream agents. In Proceedings of the 25th ACM Conference on Economics and Computation, pages 466-488.
Tang, J.. Wu, Wu, Z. S., and Zhang. J. (2025). Dimension-free decision calibration for nonlinear loss functions. arXiv preprint a7X1:22504.15615.
Zhao, S., Kim, M., Sahoo, R., Ma, T., and Ermon, S. (2021). Calibrating predictions to decisions: A novel approach to multi-class calibration. Advances in Neural Information Processing Systems, 34:22313 1-22241-22324.
13

---

Contents
1
Introduction
1.1 Preliminaries
1.2
Comparison with Related Work
2
Achieving Ö Ey-Swap Multicalibration
2.1
From swap multicalibration pseudo swap multicalibration
2.2 From pseudo swap multicalibration to pseudo contextual swap regret
2.3 Bound on the pseudo contextual swap regret
8
Conclusion and Future Directions
10
A Additional Related Work and Notations
15
Deferred Proofs and Discussion Section
16
B.1 Proof of Lemma
16
B.2 Proof of Lemma
20
B.3 Proof of Lemma
20
B.4 Proof of Lemma
20
B.5
Deferred algorithms
21
B.6
Expected loss of randomized i...............................
22
B.7 Exp-concavity parameter of the scaled loss
22
B.8 Proof of Theorem
23
Bound on Swap Omniprediction and Contextual Swap regref
23
C.1 Bound on swap omniprediction..
24
C.2 Bound on the contextual swap regret
24
From Online to Distributional
27
D.I Sample complexity of swap omniprediction
27
D.2 Sample complexity of swap agnostic learning
33
D.3 Sample complexity of swap multicalibration
35
14

---

A Additional Related Work and Notations
Downstream decision making. The seminal work of Foster and Vohra (1998) proposed the first algorithm for online calibration that achieved [E[Ca]]] = Ö(T3). For 4i-calibration (Cal1), lower bound of S (T) was folklore, and recent breakthroughs by Qiao and Valiant (2021); Dagan et al. (2024) have made progress towards closing the gap between the lower and upper bounds. In particular, Dagan et al. (2024) proved that for any online algorithm, there exists an adversary such that [[[Ca]] = Q(T0.51389) and also proved the existence of an algorithm (a non-constructive proof) that achieves E[Cah]] O where E > O. Understanding the limitations of l f--caiibration, i.e., it is impossible achieve vT f--caiibration, has led the introduction of several weaker notions of calibration, c.g., continuous calibration (Foster and Hart, 2021), decision calibration (Zhao et al., 2021; Noarov et al., 2023; Tang et al., 2025). U-calibration (Kleinberg et al., 2023; Luo et al., 2024), distance to calibration (Blasiok et al., 2023; Qiao and Zheng, 2024; Arunachaleswaran et al., 2025), maximum swap regret (Roth and Shi, 2024; Hu and Wu, 2024), subsampled smooth calibration error (Haghtalab et al., 2024), etc. The above measures are still meaningful for downstream tasks and can be achieved at more favorable rates. On the contrary, the work by Luo et al. (2025) introduced the notion of KL-calibration, which is arguably a stronger measure for studying upper bounds than 2-- calibration and showed that KL-calibration simultaneously bounds swap regret for several important subclasses of proper losses while being achievable at Ö(T') rate. A recent work by Collina et al. (2025) (see also Collina et al. (2024)) considered the problem of online collaborative prediction, where over a sequence of T days, two parties, Alice and Bob, each with their context (the context of Alice is unknown to Bob and vice-versa), engage in a communication protocol to solve a error regression problem defined over the joint context space. Using the bound for contextual swap regret as derived by Garg al. (2024), Collina et al. (2025) propose an online collaboration protocol that achieves (T 80 external regret against the class of bounded linear functions. Not surprisingly. this bound can be improved using our algorithm in Section 2.3 instead.
squared
(Swap) Multicalibration. Since its inception, starting with the work of Hébert-Johnson et al. (2018), multicalibration has found surprising connections with several domains, e.g., computational complexity (Casacuberta et al., 2024), algorithmic fairness (Hébert-Johnson et al., 2018; Obermeyer al., 2019; Devic et al., 2024; Gopalan et al., 2022b), learning theory (Gopalan et al., 2022a, 2023a; Gollakota et al., 2023; Glorus-Harris et al., 2023), conformal prediction (Bastani et al., 2022), online learning (Gupta et al., 2022; Jung et al., 2021: Haghtalab et al., 2023), cryptography (Dwork et al., 2023), etc. However, the literature on multicalibration has differed in the concrete definition, thereby leading to some confusion. In this paper, we primarily adopt the definition given by Globus-Harris et al. (2023); Gopalan et al. (2023b) in the distributional setting and its extension by Garg et al. (2024) to the online setting. The previously best-known sample complexity bounds as mentioned in Table 1 are with respect to these definitions.
For loc fe-mmlticallibaation, Haghtalab et al. (2023) derived a Ō( sample complexity when random- ized predictors are allowed, and a Ō(a-4) sample complexity for deterministic predictors. Notably, since L loe multicalibration errors are related as E < |Z| Exx. their result implies a Ö(s ?) sample complexity for fy-multicalibration (the bound for lox ie-multicalibratton has logarithmic dependence on [2], therefore Z can be chosen to be (()). However, Haghtalab et al. (2023) use bucketed definition of multicalibration which is different from that considered in this paper, where we enforce our predictor to predict among |2] possible values. For swap- wwap-multiaalibration the multicalibration algorithms of Hébert-Johnson et al. (2018): Gopalan et al. (2022a) were shown to be swap-multicalibrraeed in Gopalan et al. (2023b), thereby establishing a ((e-10) sample complexity for (s-swap multicalibration. For fz-swap multicalibration, Globus-Harris et al. (2023) proposed an algorithm that achieved éz-multicalibration error at most e given 2 - samples. However, we realize that their algorithm is in fact swap multicalibrated, thereby establishing a (s-5)) sample complexity for swap multicalibration. Since é,, lw-swap multicalibration errors are related as E S vl2. their result also implies a Ō(E-11) ((e) sample complexity for l fs-wwpp multicalibration matching that of Gopalan et al. (2023b), albeit with remarkably simpler algorithm. Since f--swap multicalibration error implies O(E) swap omniprediction error for _ (Gopalan et al., 2023b), the above discussion implies a Ō sample complexity for swap omniprediction for _evx, As mentioned, although the multicalibration algorithm of Haghtalab et al. (2023) requires fewer samples, their considered
15

---

definition of multicalibration is different and it is not clear whether they achieve the stronger swap multicalibration guarantee, therefore, we do not portray comparison to their results in Table
Omniprediction. For the class of convex and Lipschitz functions, Gopalan et al. (2022a) proposed the first construction of efficient omnipredictor via E t-multicalibration. However, shown by Gopalan et al. (2022a), multicalibration is not necessary for omniprediction. Several follow-up works (Gopalan et al., 2023a; Okoroafor et al., 2025) have investigated weaker notions of multicalibration that suffice for omniprediction. Particularly, Gopalan et al. (2023a) identified calibrated multiaccuracy to imply omniprediction for more general classes of loss functions (beyond convexity) and proposed an oracle-efficient algorithm (given access to an offline weak agnostic learning oracle) that required 2 g-10 samples. Subsequent work by Hu al. (2024) proposed efficient construction of omnipredictors for single index models, requiring 2, =- samples. Very recently, Okoroafor et al. (2025) have shown that is possible to achieve oracle-efficient omniprediction, given access to an offline ERM oracle with (s==²) sample complexity (matching the lower bound for the minimization of a fixed loss function) for the class of bounded variation loss functions Lev against an arbitrary hypothesis class F with bounded statistical complexity. thereby settling the sample complexity of omniprediction.
In the context of swap omniprediction, recent work by et al. (2025) proposed notion of decision swap regret for high-dimensional predictions in the regression setting, i.e., y = [0, 1]. However, compared to swap omniprediction, the loss function is not indexed by the forecaster's s prediction, and
notably, the techniques in our paper are considerably different than those proposed by Lu et al. (2025) who impose a relaxation of calibration called decision calibration (Zhao et al., 2021; Noarov et al., 2023; Tang et al., 2025) to achieve low decision swap regret.
Additional Notations. For set I, its complement is denoted by I, representing all elements not in I. We denote conditional probability and expectation given the history up to time t- (inclusive) by Pt and E,, respectively. A loss é [0, 1] x {0, 1] - E is called proper if By--Berlp) [ y) s Ey Ber (C(p',)) for all p.p' d [0, 1), e.g., the squared loss [(p. y) (p- -)) log loss E(p, y)
-y loggp- (1 - y) log(1 p), etc.
B Deferred Proofs and Discussion in Section 2
B.1 Proof of Lemma
Lemma 6 (Freedman's Inequality). (Beygelzimer et al., 2011, Theorem 1) Let Xi...., x be a martingale difference sequence where [Xil S B for all i = I,...,n, n, and B is a fixed constant. Define V = Σm [x?) Then, for any fixed μ E [0, 11 B E [0, with probability at least 1 - 8.
we have
log 42
Σ X
WV
P
Proof of Lemma 1. apx E z E F. We first bound Ipp.f pp 1. To achieve so, we consider the martingale difference sequences (X,), (Y7), (Ze), where
X, := (P: Clearly. [Z,] < for all E [T]. Furthermore, since f E F c we have [X,l < 1, |Yı| < 1 for all t [T]. Fix a pa [6, i]. Applying Lemma 6 to the sequences X, Z and taking union
П[' = p]), Y, = (P))) - Ipp = p)). Z, = Po(p) - 1p. p].
bound (over X, Y, Z), we obtain that with probability at least 1 8 (simultaneously over X, Y, Z),
r
log 6 /
9e (x.()))(P())) - -[pp = p))
S Vx +
(6)
14p
T (p.)) - -Mp = x))
log 6
Σ
< Mp Vy
Mp
log
Σ P((p) - Dpp pp
< 14 V +
(8)
Mp
16

---

where Vx, Vr, Vz are given by
T
Vx Σ Be
[(f(E)) P((D)) -
Pe(p),
T
T
T
Vy= =
Σ
Be |
Σ
((()))) P((p)) -
P((p),
1=1
[=1
1=1
T
T
V2= =
Σ
= Σ
Polp)( S Σ P(())
1=1
1=1
To bound 1pp. P we first upper bound Pp.s Pp. as per the following steps:
pp.. Pp.s =
1== Pr(p)((Ee)(i
Σ 1pp (xx)ee
Et= Pi=iPolp)
E 1=1 llp = p]
1=1 Tpp = (x)((
T
- P.(p))(m:))
Et= Mp =p p)
Σt=1 Po(p)
Mp Et= P((p)
log
EE= Ilp: plf(v))
E/= Mp =p) =p]s(1a) +
Uy
E Pt(p)
Ei= Uyt p)
21=1 Mp p)((2))
T
Mp Ex= P((p) + My
log -E= 1p; = (x+)
p
21= I/p: =pl
Σ Pp(p)
log %
El= Lpp: = p))(())))
Σ
Ipp = pl - -P(co) +
= Up
+
Mp Σ T
1=1 Pp(p)
Σ1= 1p: = pl Ei= (p)
log o
Et Upp = (zx(
Hp +
Pclp) - -lipe = p]
Hp Et Pr(p)
Ei Upp = pp Σi= Pt(p)
log a
Lt=1 Hp = -p)f(z))
1
6
I Upp +
14p
P((p) +
1og x
)
+
Hp Σ 1=1 Pc(p)
1=1 1lp = =pl Ei= Pc(p)
1=1
log o
Σ Upp p)f(
PP Σ P((p) + 1
6
p Up
Hp 1- (p())
+
Σ Up = pl Σl_ Pp())
Up
log
6 4 log?
< 4pp +
6
PP ET_ (p())
where the first inequality follows from (6), (7); the second inequality follows from (8); the final inequality follows since f E F.
Proceeding in a similar manner, we can upper bound Pr.f - Pp.f. We have,
Pv. Pp.
T t Hpt = =p]{(x))v)
ΣT. Pr(p)
T 1 1lpt = pl
Et.
Σ 1 Pr(o)s(ax))
Σt Mpp = p))(at)
Et Upp = rl
T Mp = px]((x))
Up Σt= Pr(p) + 1 log 6 -Et Mpp = 2) (xx)) +
Σ
Fo Σ Pp(p)
Σ Ipp pl
Mp Σt Pr(p) + 1 log @ + +T 1pp = plf(2e)
Σr Mpt = px)(
upp
p
Σr= P((p)
Σ Up = p)
17

---

log? 8
Ei=1 Lpp: = p),((
Σ Pe(p) - lp = pl) +
Up +
Mp -1=1 Pc(p)
7
E1= lp:: = p| Ei= Pi(p)
log o
Ei=1 Up = (20()))
T
Σ 1lp pl - Pi(p)
Up +
Mp Ei=1 Pc(p)
Ei=1 Ilp = =p Ei=ı Pe(p)
log@
1=1 Up = =plf(ze)u
P((p) + 1
6
S Up
P4p
log
+
Mp Σ 1=1 Pc(p)
Σ 1=1 1p = pl Ei= Pi(p)
Hpp
1=1
log 6 p Up
El 1= lipt pzf(
1
))
P((p) + - log
14p
Mp El= Pp(p)
Σ
Up = p] Σ/= Pp(p)
4 log 6 8
< App +
Mp Ei=1 (p(p)
Combining both the bounds obtained above, have shown that lpp.s pr.5l 4pp
log
(p)
Taking union bound over all E / E F, with probability at least 1 - 5, we have (simultaneously for all p Z F)
lpp. - Pp.sl S 4pp + log 6(
T P(()) Up, = pl S Up Σ
T
log 6(N+1)
Σ
Po(p) +
Mp Σr (p)
(9)
Consider the function ((m) == p n. where 2 0 is a fixed constant. Clearly, min g(u) 2/ when S 1, and + a otherwise. Minimizing the bound in (9) with respect to plp- we obtain
=
log 6(N+1)
6(N + +1
1pp.1 Po.s S 8, 1
if log
Pa(p).
Σ P((p)
8
t=1
Moreover, since f E F, by definition we have lpp.11 < 1. 1. S 1 and thus lpp. pp.1l < 2. However, when ΣT (p) is quite small (e.g.. 0), the bound on |pp.s pp..1 obtained above is much worse than the trivial bound lpp.5 Pp.fl < 2. Therefore, we define the set
I D 2 s.t. log 6(N + FI
Σ P
T
t=1
and bound lpp. Pr.5l as
log 1
8
p E EI, otherwise.
IPp.t - Po.l S
E(_ (p(p)
(10)
2
Similarly, by minimizing (9) with respect to Ml, we obtain the following bound:
Σ P((p) Tlp =p] S
T
2 Σt= Pp(p) log 6(N+1)
if E I, otherwise.
(11)
Σr Po(p) + log 6(N+i)
8
Our next goal is to bound SMCal in terms of PSMCal By definition,
T
T
SMCaly:2 = sup
Σ
Σ
Tpp =pl
(pp.to)) Σ
Σ
Tpt = pl
sup Pr.t. yEF
(FeF))oz pez
\==
PEZ
1=1
T P((P)
T
PSMCaly;3
sup
Σ
Pm.s== = Σ
Σ
P((p)
sup Po.
(LEF),cz pEz
JEF
1=1
DEZ
18

---

Therefore,
( (suglons- - -po,)² + sup p SEF
Σ up = pl
2M S 2
PEZ
where the inequality follows by the sub-additivity of the supremum function and since (u + v)² < 2u² + 2v². Equipped with (10) and (11), is easy to express SMCal in terms of PSMCal To achieve so, we define two terms TERM1, TERMa
T
TERM = Σ
Tpp pl
sup(pp. Po.s)² + sup Pr.tt FEF
FEF
DEZ
T
TERM =
Σ
Tpp: = pl
sup(P - Po.s) + sup Pp.. feF
SEF
PEZ
and bound TERM,, TERM2 separately. We begin by bounding TERM,
6(N + 1) |F]
TERM
Σ
Σ
P((0)
Σ Po(o)
log
sup(pn. - 22. SEF
sup Pi.s feT
PEI
$
Σ
T
T Pi(p) +2
Σ
Pp(p)
log
6(N 1) |F1
644 6(N+1)15 ΣT -- Pc(p)
+ sup Pr.. feJ
PEI
(=1
T
(44log 6(N+1))
I 3
Σ
Σ Pc(p)
sup Pp.. SEF
1= Pe(p)
PEZ
1=1
6(N + 1)
192 [Z] log
3
Σ
Σ
Pt(p)
sup Pp..
feF
PEI
where the first incquality follows from
(11); the second inequality follows from (10); the third
inequality follows since log 6(N+1)
< E 11=1 Pp(p) as p E I. Next, we bound TERM, as
6(N 11 F
TERM
Σ
2
Px(p) + log
sup(po. pn.)) + sup pr..) feF
8
JEF
PEI
6(N + 1) 1)
Σ PET
2 Pp(p) + log
4+ 4 sup fEF
Po.1)
8
| log 6(N + F
S 13
Σ
Σ
((()) sup Pr.tt feF
8
PEZ
where the first inequality follows from (11); the second inequality follows from (10); the final inequal- ity follows from the definition Z and since |p.. S 1. Combining the bounds on TERM,, TERM2 to SMCaly;2 < 2(TERM, + TERM2), we obtain
6(N + 1)
SMCal S 384 |Z] log
6
Σ PEZ
Σ
Pe(p)
sup P JEF
8
1=1
26 7
log
6(N + 1) |F
Σ PEZ
Σ
T
Po(p)
sup Pr. JEF
6(N + [
T
< 384(N + 1) log
6
P((p)
sup P7.1 /EF
PEZ
1=1
6(N + [
384(N + 1) log
+ 6 PSMCal
6
This completes the proof.
19

---

B.2 Proof of Lemma 2
Proof. To bound pMC terms SM we realize that for each f E Flin, letting fo C. be the representative of f. have
Ei Mp = p)((()))) - (c( -p)
lp..5 Pp.Se
SE.
Σi=1 Tym p)
Therefore, eu 17.s- S 2ssup P + 262 and
T
SMCal Σ
Σ Ipe pl
sup Pr 2
Σ
Σ
Ip pl
P7.s 2 SEC.
sup
fESt
PEZ
2SMCalo. + 2T
Using the result of Lemma bound SMCale,,2 2, we obtain
SMCal S (68(N- log 6(N + 1) + 12PSMCal + 26
where we have also used the inequality PSMCale,22 & PSMCal p/ since Cs S Fln. Using Proposition I to bound [C&| finishes the proof.
B.3 Proof of Lemma 3
Proof. Consider the function f'(x) = p + nf(x), where
:= min
Σr (P)((()))) Eis: P((p)
Under Assumption J" E F. Furthermore, since f F1, we have (f'(x))² < +))))))((()) S
4. therefore, f' E F4. For convinience, define A = Et Pp(p) ((p -y1)² (ff(z)) -1))). By direct computation, we obtain
T
T
A
- v() Σ P((p) ((p - y1)² - (p -
= Σ Pi(p) + 2nf(xi) (2) - (p))-)).
Therefore, the desired quantity can be lower bounded as
2n Pp.j n/2 Ei P(l))(((E.))² Pi(p)
2 2nja 1/2 Et= P((p) Et=IP(P)
2nJ 17²
ΣE 1 Pp(p)
where μ DT P.())((()))) ET, Pi(p)
Next, we consider two cases depending on whether or not 1 realizes the minimum in the expression defining n. o 2 n min(1, ()) 1. Therefore, 2naa 17214
2a p 2 a 2 a where the last inequality follows since Pp. S as ʃ E Fi, and Pp.f 2 a by assumption, thus < 1. Otherwise, if a μ. have 7
0 and 2na 1/² a² > a² since A 2 a², which completes the
S as f E Fi. Combining both cases, we have shown that >T P.(p) proof.
B.4 Proof of Lemma 4
Proof. We shall prove the desired result by contradiction. Assume that PSMCal 22 > a. Therefore, there exists comparator profile {fp Fi Filpez such that
Σ PEZ
Σ
P((p))
(Pp.st)) a
(12)
20

---

For each p 2, define ap
(Ii=) Pt(p)
Pp.s.
Thus, there exists a function (a) which is Clearly, f E Fi. It follows from Lemma
either (x) or [x) such that Pn.J; V Ei_1 Px(p)
Opp
that for each p E P, there exists a fg E F4 such that
P((e) ((- y.)² (f)(11)) - ye)3) 2 Ap-
Summing over p E we obtain that the comparator profile (8g E FAJDEZ realizes
CePoll ((p ve)² - (f)()))) v1 - 2 Σ ap>a,
PEZ
PE2
where the last inequality follows from (12). This is contradiction the assumption that PSReg This completes the proof.
B.5 Deferred algorithms
Algorithm Generic BM algorithmic template
Initialize: A₁ for i (0, N and qı,i N
N+I
1: for /= I,..,,
2: Receive context Ti;
3: Set Q: = Qr,0. 4t.v]:
4: Compute the stationary distribution of Q,, i... Pt AN+1 that satisfies Q.P: Pr;
5: Output conditional distribution P., where Pz(z) (i) and observe y::
6: for i ....., N
7: Feed the scaled loss function (r,((w) = pt, ((. yb) to A, (Algorithm 1) and obtain q++1,
Algorithm 4 Online Newton Step (ONS,) with scaled losses
1: Set A 640
and initialize 01,5 4 IBC arbitrarily;
2: for = 2,...,77 T,
3: Update Oe.; as
0,, = 11 11 (
A Vi-1.)
1
1:3
where Vr, (0,,) 2p-,i ((0,,1,
A E.=l V..VI why, and
II Ar-i is the projection operator with respect the norm induced by A,-1,5, ie..
4.g
AL-1 (0) =argmin(( A0
1- 8g4-By
Algorithm 5 ALG;
1:
for 1, 1,...,2
2: Obtain the output Or,; of ONS; and predict wi, (10,,,,
Proposition 2. For Algorithm 3, we have PSReg < MN
i== Reg, (F).
Proof. For each E (O,..., fix ax By definition of Reg, (F), we have
T
N
Σ
Σ
v1)²
P(.(f((z.) v)2 Reg, (F).
Pt.
t=
Ø=0
21

---

Summing the equation above for all i E {O....,N}, NN, we obtain
T N
T N
N
ΣΣΣ
Pr. - y1)²
- -y))
- Σ
Reg (F).
(13)
[=1 ==
(=1 i=
1=0
Simplifying the first term on the left-hand side of the equation above, we have
T N
T
N
T
T Σ pll,,
ΣΣΣ
Pe.guaa(2) - v1)²
ΣΣ
Pt. (qr. Le)
Σ
1= i=0 2=0
1l i=0
t=1
1=1
where the last equality follows since Pt is chosen such that QiP: = P.- Therefore, simplifies to
T N
ΣΣ
pes ((z= - v (fe( 2 Reg, (F).
Taking the supremum over all fi 's completes the proof.
B.6 Expected loss of randomized rounding
Proposition 3. Let p E [0, 1] and p ,p* E Z be neighbouring points in 2 such that p SP pt Let q be the random variable that takes value p with probability D²-P and p² with probability F Then, for all y E {0, 10, we have (B[((q, v)] - -(pp.) S N
p--p-
Proof.
Let A = Egg (q-
y). Substituting Pt N: Pi+1
and by direct computation, we N
obtain
++1
2
p
N
iit1
2
y
+
y
N
N
N
I
1/
2
+
N
i
y
+
N
y
2
N
N2
1
+ 2
p
N
N
y
N
N
N
2
i
i
)
i
1/
+
N
P -
N
+
N
N
-
2
1
i
N
p
+ (p 3) +2
N
P
(p
v)
+
N
p
N
2
p
N
N
y
2
i
i N
2
N P
+ (p v)² +
2
N
N
2
(p- "²
N
p
p N
1 < (p v)²
N2
where the inequality follows by dropping the negative term, and since p < proof.
1-1 This completes the
B.7 Exp-coneavity parameter of the scaled loss
x)) - Proposition 4. Let r E 18 E 13. The function o 4-B3 + RR defined as x(0) = a((0,z))) for some [0, 1] exp-cconnevv and 10-Lipschitz.
Proof. For a 0. let (()) = exp (-)) The first derivative of g is given by
(g(()= = -20 .) - y) exp (6)a(((, .x) - y)²) w.
Differentiating with respect to 0 again, we obtain
V'g(0) - 2ya exp (+) - -)²) -11 27a((0, x) - v) xr..
22

---

Choosing 1. the expression above simplifies to
50
g0) 25 exp
50 (10, x) 1)9 (1-
25 (0, v))² -xxt 0,
where the inequality because ((0,z) x) y)² - 25 since (60 x>حه - |00| ||ح|| - 4 by the Cauchy- Schwartz inequality, therefore (0, - yl 5; this implies that (0, y)² 1. Hence, the function exp (- (()) is concave, thus á is to exp-conavv by definition. To bound the Lipschitzness parameter, we note that since Vo(0) 2a((0,z) y)æ, we have || 2a (0, .) - y| ||ж||| z 10. Therefore, & is 10-Lipschitz. This completes the proof.
B.8 Proof of Theorem
Proof. We have,
5MCal = = N log
+ .Nllo
Ndlog T +
T N2
+ =²2
T + N²
0 N log
+ .Nlogo
o T (To
T
log
(14)
dlog
where the first equality follows from combining the result of Lemma 2 and Lemma 4 with the bound
PSReg = O Ndlog T
N
the second equality follows by substituting V the final equality follows by substituting
N
T
To bound E SMC we let & denote the event in (14). Then,
Zlog T
SMCal
5f IP(E) + E 5f (P(E))
(2 (dlog T
Tddd (log T)3 (
T
1 log 5 + +8T
= = (Tbdā (log T))g
where the second equality follows by bounding 2 as per (14), P(E) < P() < 8, and 5t 2| T by definition; the second equality follows by choosing 1/T. This completes the proof.
Corollary 1. There exists an efficient algorithm that achieves
= T SMC
()) + (d' (dlog
$ log
with probability at least 1 - 8. Furthermore, E [MMal o (T' a (log where the expectation is taken over the internal randomness of the algorithm.
Proof. The high probability bound follows since SMCal
I
T SMCal The in-
expectation bound is because SMCal < V T E SMCal by applying Jensen's 's in- equality. This completes the proof.
C Bound on Swap Omniprediction and Contextual Swap regret
In this section, we derive substantially improved rates for (a) swap omniprediction for the class of bounded convex Lipschitz loss functions, and (b) contextual swap regret.
23

---

C.1 Bound on swap omniprediction
Let fe denote the class of bounded (in [nn--,1] 1) convex 1-Lipschitz loss functions, i.e., _ com- prises of functions that are convex in for a fixed {0, 1), E(. y) E 1.,,1], and [pE y)1 S 1 for all p E [0, I]. {0, 13, where the subgradient is taken with respect p. We first state a result that bounds the (swap) omniprediction error in terms of the (swap) multicalibration error. The following result holds for any hypothesis class F; subsequently, we instantiate our result for an appropriate choice of F.
Lemma 7. (Garg et al., 2024, Theorem 4.1) Let F C 10. be an arbitrary hypothesis class. We have S0mni g F S 6 SMCal Omnig 6. 1C
Note that Lemma does not immediately apply to the choice F Fl since the hypotheses in Flin can take negative values. To align with Lemma 7, consider the hypothesis class Jaaff
{folz) = (0,))=); E Rd) and its restriction Faft = {Fo(z) 1+(0.z), :101 s 1 instead. Falf
satisfies Assumption since
a01
1 (1 (0', x))
afo(x) (b=)))>=33) a
2b (I2zd 02:d)
2
2
where 8' E Rd is such that 8f = 2a + a01 + 4b - and 0 = aB, for all S i S d. For this choice of 1+ (0.))
S for all X. where recall that = {I 11 = } Clearly, Fatt S Jilf by the Sehhart- inequality. Furthermore, it is easy to verify that 0₁ B$ C 2 C 02 By, where 01, 02 = ((1) Therefore, the entire analysis in Section be extended (with only multiplicative change in the constants, which does affect the final rate) to bound SMCal py" 1. and thus SMCal since F S J Since Faff C [0, 1]*t we can finally use Lemma 7 to bound 50mni Fur. We skip the exact derivations for the sake of brevity; however remark that the above discussion was implicitly skipped by Garg et al. (2024), who used the result of Lemma 7 to bound SOmni g
Jafff F. is determined by the set of all 0's that satisfy
2
Using Corollary to bound SMCal in Lemma 7, we obtain the following theorem.
Theorem 2. There exists an efficient algorithm that achieves
S0mni goo Fant of
(T r (log T) +T (dlog log
1
with probability at least 1- 8. Furthermore, [SOmni cam Full = (rådt (log where the expectation is taken over the internal randomness of the algorithm.
Theorem 2 significantly improves upon the ò (T& log 2)+ high probability bound of Garg et al. (2024).
C.2 Bound on the contextual swap regret
In this section, we derive an improved high probability bound on SReg Similar to Lemma 1, we first obtain a high probability bound that relates SReg, and PSReg, for a finite hypothesis class. Lemma 8. Let c 1] be a finite hypothesis class. For any algorithm AsRes, such that for each t E [T] the conditional distribution P, is deterministic, with probability at least 1 - 8 over ASRegz predictions . Pr, we have
such
2(N + F + + + 1) log
2(N + 1) [F]
SReg, & PSReg, 8v (N 1)T
8
5
Proof. The proof follows by an application of Freedman's inequality, similar Lemma 1. Fix f E F.p E Z and define the martingale difference sequence {Xe)?=1 as
X = (Ip: = pl PP(()) ((p 2 - (f(x.) - ))
24

---

Since f E [[1,,]), [X,] < 4 for E (T]. Fix a Up E [o. #.] Applying Lemma 6, we obtain
T
T
Σ [1pp: = p] - -P(p)) ((p - y1)² (f(x)) - -ye))) - 16p Σ
P((p) +
1
log
Mpp 8
1=1
t=1
where the inequality is because the total conditional variance can be bounded as
T
Σ Rx
[x]]
[Tb. p] - ((P - ye)² (f( - y0)
t=1
T
< 16
Σ
P1
and we drop the negative term. Taking a union bound over all probability least 1 (simultaneously over all p E 2, F),
2 E F, we obtain that with
T
1
2(N +1
Σ (Tpp p] - P.(p)) ((0 v()= - (f(z))
v1)
S 16uup
EP(())
log 5
Hp
[=1
Next, minimize the bound above with respect Mpp If 2 is such that Σ Pa(p) 2
log 2 the optimal choice up is t
Σt Pi(n) otherwise, the optimal up is 1. Therefore,
log 2(++1)
we define the set
P((p) 2 log 2(N + [ I == PE S.t Σ
T
and bound the deviation as
T
Σ
(I[p = p] - PP(())) (1D-91) v1)² - (f(xz) y1)2) S
(15)
8 E Pr(vi) log 2(N+1)FF
if EI,
4 ΣT (p(p) + log 2(++1)
otherwise.
Equipped with (15), we can bound SReg, in the following manner:
SReg,=
sup
ΣΣN
T[p: ((p y2)² - (fp(2.) -ye)² )²)
UyeFhvez PEZ t=1
T
Σ sup 2EZ FEF t=1
Ipp = pl ((D - y.)² - (f(x)) - v2)3)
T
Σ sup PEZ fEF t=1
(Ipr p] - Pp())) ((p ne)² - (f(xs) - -))))) + PSRegg
T
2(N + 1) F
T
2(N + 1F
< 8
Σ P:(p)
log
+ 4
Σ [=1
Pr(x) + log
+ PSReg,
8
8
pEZ
PEZ
2(N + |
2(N + +1)
<8 Σ
Σ P((p)
log
+ +8 [Z
log
PSReg
8
PEI
2(N + F
2(N + F
< 8
I
Σ
P((p)
log
+ 8 |Z|
log
+ PSReg
8
8
PEZ t=
25

---

<8/(N + $8/(N+1)Tion 1)
2(N 1) F1 8(N 1) log
2(N
[F1
PSRegr:
where the first inequality follows from the sub- sub-additivity of the supremum function, and by a similar reasoning as the first two equalities above, we have
PSReg
Σ sup PEZ /EF
E Pi(o) ((0- (0)))))2- --)² (f(xz) -y:)²);
the second inequality follows from (15); the third inequality follows since log 2(N+1)/1 Σ Pp(p) for all p I; the fourth inequality follows from the This completes the proof.
5
inequality.
Equipped with Lemma 8 and by a covering number-based argument, we bound SRegzjo in the following theorem.
Theorem 3. There exists an efficient algorithm that achieves
SReg = T (d 3) 3 + T (dlog (dlogT)- Vlog
with probability at least 1 - 5. Furthermore, E. [Reg = (T TT where the expec- tation is taken over the internal randommess in the algorithm.
Proof. First, we bound SR in terms of SRegs,, where Sg S Flln is an e-cover of Fli Let E Flin and fe E Sg be its representative. Then, for any t E [7]. we have
(f=( - y.)² (f(z) - yo)² (fe(zz) f(xx))(f((x)) + f(x,) - 22y) S 6E.
Therefore, SRegrt can be bounded in terms of SRegs,
T
SRegrt
Σ sup JEFl
Σ
Upr p] ((p - yx)² - -f(x)) - yr)²) < SRegs. + 6e7.
PEz
Since |S is finite (Proposition 1), using Lemma 8 to bound SRegs, we obtain
2(N + +1
2(N + S.
SReg < PSRegs, + v (N + 1)T'
+8(N + 1) log
+ GE
N1S,
N SS
0 PSRegr NT
N log
+ #T
8
T 0
N
N2 + +NdlogT
NT No log
+ VNdTloge Tog
g
T T) (d T) - log 0
1
with probability least The first equality above follows since PSRegs, I PSReg the second equality follows by substituting & 7 and bounding |S, as per Proposition 1, dropping the lower order terms, and since PSRegy o ( No T); the final equality follows by substituting N = T
The in-expectation bound follows by repeating the exact same steps to bound E x in the proof of Theorem 1. This completes the proof.
lng
For SRegat. Garg et al. (2024) proposed an algorithm that achieves SReg = (aT Vlog :)) Clearly, result in Theorem 3 is strictly better, with an improved dependence in both d, T.
26

---

which is different from the choice of N in Theorem 3. Substituting the former value yields leading dependence of Ö in the bound on SRegz! Therefore, even if not the best achievable bound on SRegz!., the algorithm guaranteed by Theorem achieves an improved dependence on compared to Garg et al. (2024)'s result.
Remark 1. Note that Theorem we set N
Tlog T
D From Online to Distributional
In this section, using our improved guarantees for contextual swap regret (Theorem 3), swap multical- ibration (Theorem 1), and swap omniprediction (Thcorem 2), we establish significantly improved sample complexity bounds for the corresponding distributional quantities. For swap omniprediction and swap agnostic learning, we shall perform an online-to-batee reduction using the corresponding online algorithm that achieves the improved guarantee. The sample complexity bound for swap multicalibration shall follow from that swap agnostic learning. Before proceeding to the details, first give formal definitions of the above notions in the distributional setting.
Distributional (Swap) Multicalibration, For bounded hypothesis class F, the predictor is perfectly multicalibrated if sup [[[(() (v - -w) p(x) = v] 0 for each v E Range(p). Since perfect multicalibration is both information theoretically and computation- ally infeasible, the above requirement is quantified via the objective of minimizing the mul- ticalibration error, where the predictor has ey-multicalibration error (q 2 1) at most e DMCalF,, sup Eyy [Ep [f(x) (v (y-vi v))p(z) e|]"]] satisfies DMCalF I Motivated by the role of swap regret in online learning and to explore the interplay between multicali- al., 2023b) introduced the notion of swap multicali- bration, where the predictor has Sy-wapp multicalibration error at most if DSMCal = E, (supyEF EEp [x) (y - v) p(x) = =]]]] < e. Since DMCalf, I DSMCal a swap- mutlicalibrated predictor also multicalibrated.
bration and omniprediction, (Gopalan
Distributional (Swap) Omniprediction. A predictor p such that DOmnig.F supre supperuprrrrr E ((((k(p(())). - {()()),)) < is referred to as (, Fommirrccccctt In al. (2023b) introduced the notion of swap
similar spirit swap multicalibration. Gopalan omniprediction, where the predictor is required to outperform the best hypothesis in F not just marginally but also when conditioned on the level sets of the predictor, even when the losses are indexed by the predictions themselves. In particular, the predictor p has swap omniprediction error at most e if
DSOmnic. ==
sup (L.EC.f.EF) F.E)
EowD, [E (ke, (o = e]] < (16)
Notably, omniprediction corresponds to a special case of swap omniprediction when the loss, comparator profiles fixed and independent of Z. Therefore, have the trivial relation DOmnic. < DSOmnic.F.
Swap Agnostic Learning. Swap agnostic learning is special case of swap omniprediction when {2} and
(p- so that kp(p) = p. We define the swap agnostic error as
SAE = sup (J.EF)eez
E [(p(x) - y) (Uplz)(z) y)
(17)
D.1 Sample complexity of swap omniprediction
We first derive the sample complexity of learning a (c, __ _Faffaffssssarr swapp omnipredictor. As already mentioned, we perform an online-to-batee reduction using our online algorithm in Theorem 2, which we refer to Aswap for brevity. The reduction proceeds in the following manner: given T samples (x1, "i,,...,,.. (IT, 3T) sampled i.i.d from D, we feed the samples to Asuap to obtain predictors Pı,.... PT, where pt X' + Z for each E [T]. Subsequently, we sample predictor from the uniform distribution x over PI....,Pr. To obtain the number of samples T sufficient to drive the swap omniprediction error to be at most shall derive concentration bound (tailored to the
27

---

C = L that relates the distributional version of the swap omniprediction choice of == C error with online analogue, i.e. we bound the deviation A defined be the supremum of
E (.a.))DD,pmn (poco) (Kégce) (p(x)), v) - (p(a) (2)))(2)))))
sup ((e.J.))CxFFuee
1
(ne (pe (x)() v1) (no Σ
T
Since is the uniform mixture over Pi.....PP we have
E(z.g)~D.pmn pmr (kp(e) (p(x)), v) (x))
B(x,)>D (e (pce)))))))
(pr(x)),
Using the Triangle inequality and sub-additivity of the supremum function, we obtain A s + T2), where Ti, T2 are defined as
T = sup (f. EC) 1=1
pellas) (Ki (Hiepitoes) (pe( 21)
Σ (a (Kecs)) (p.())),
T2 = sup ((tx..))CxF).ez
Σ mml (ntt))
Σ ElyyyD (
In the next lemmas, we bound Ti, T2.
Lemma 9. For a ò S t. with probability at least 1 - 8, we have Ti =
7 0 + NT log x
Proof.
We begin by upper bounding Ti as
T =
T (pps)) = u) lo (ke, (k,,,,)),))) (v) - P(pi(x) = u) E (v),
sup
(LEEhee2
IeEZ t=1
T
sup
Mpp( -0. -()e(((())) y1) P(p.(x)) = (E)(((((U))
VEZ Fee
sup VEZ Croper
Σ [pp((z)) = v) E((v, - P(pp(z)) = u) E (((((e)))lx(()) =0]
(18)
where the second inequality follows since the loss E(p, v) defined as ē(p, yy ((k((p), vy) proper; we replace the supie croper with supre geoper. It follows from (Kleinberg et al., 2023, Theorem 8) that there exists a basis for proper losses in terms of V-shaped losses (p y) = (v - y) sign(p - v), i.c.
((p.v) = [ pe(v)= Co y)de,
where pe [0, + R20 and So pe(v)dv S
avoid overloading the usage of e both (p y) and u E Σ, we replace the in (18) with for all the subsequent steps. Furthermore, as shown in (Okorvafor et al., 2025, Lemma 6.4), for each V-shaped loss l,, setting v' = & [No]] E ensures
the following bound for all p Z. E {0, 1}:
(v.(v) (p, v)
[(v y) sign(p v) - (v' y) sign(p '')l
1
= =I u') sign(p - u) < N
(19)
28

---

where the second equality is because for all p 2, we have sign(p v) = sign(p v²). Using this bound Ti further, we obtain
Ti
T Σ
[p)( = / ( S/" ne(v) (lCo(p.v)llc = plde
E sup
PEZ rEcoup
Σ sup PEZ Cecww
L' me(w)
Σ
P(p((1) p) (( =p] du
sup FE 0
me(v)
Σ (xp)(x)) p] Lo(p, v.) P(pr(x) =) BlC. dv.
PEZ
In the next step, we bound the term inside the absolute value. follows from (19) and the Triangle inequality that the term can be bounded by
T
[p((
pl +
P(p(())=p))
N
N
Σ (p,(),)) -l (D. M1) (x)((x) = pp) (2
Fix u' P.p E 2. Observe that the sequence XI,..., X defined as
X; (x+) b. (p. Me) (((((()) = p)
is martingale difference sequence with |X,] S 2 for all [7]. Furthermore, the cumulative conditional variance can be bounded by
Σ
E. X
Σ
p)
(E & (()((() = p).
Fix Exaper E [0, }. By Lemma 6, have
T
T
2 g p(p((x)=1 + log
X
< 44
Since ΣT= P(p((z) p) is a random variable, the optimal μ min also random. Therefore, we cannot merely substitute the optimal (similar to our proofs in Lemmas I and 8). However, note that the optimal choice of μa E
1, V. Ei (()(())=p)
log
is
log T
2
For the subsequent steps,
log 2
for simplicity in the analysis we assume that there exists a n Zzo such that partition the interval I
2 and
as I= ... UI1 U Io where Is = 26+T
1
for all
2
E [m] and To { } Each interval corresponds a condition on Σt P(pr (4) = p) for which the optimal μ lies within that interval. particular, for each l: E [n]. the interval Iy shall correspond to the condition that
log 2(n+1)
2(n + 1)
T
2(n 1)
2 4 log
P(p((x) = p) < 4th log
26
((p(())=p)
(20)
For each interval Ig. associate parameter μ4 ZET.. Applying Lemma 6 and taking union bound over
However, Io shall represent the condition that 0 < ΣL_ P(r(()) p) S log
2(n+1)
8
29

---

all k E {O...... ni, we obtain
Pk Σ ((p(()) p) 1
2nn + 1)
Σ
log 1* 8
with probability at least 1 6 (simultaneously for all R). Next, we prove an uniform upper bound on
Ei= Xt by analyzing the bound for each interval. Towards this end, let & E [m) be such that (20) holds. Then,
T
T ((p)(()) = 2*1 log
2(n 2(n+1) + S
9
T Σ P(p) = p) log
2(n + 1)
X S
2k+1
5
21
where the second inequality follows from (20). Note that the choice of fi optimal, however, since the optimal I
261J is not necessarily
1
2nr for Ix. the bound on
Σ i=1 X2 obtained above
only worse than the optimal by a constant factor. Similarly, for k: = 0, we have
T
T
2(n + 1)
2 + 1)
X
(x)) = =p) + 2lo
v log
5
2
5
1=1
Combining both bounds, we have shown that
X
9
Σ
((pr(x))))
log
2(n + 1)
5
log
2(n + 1)
2
2
[=1
1=1
T
P(pe(1)) P(m)(x)=))) -)) log 5
1 + log
1
0
where the second equality follows since n O (log T") and log n+1 Ollo 4) since ò I 4 Taking union bound over all v' E Z.p E Z, and substituting back to the bound on Tr, obtain
Ti S
T
N N + log Σ P(p((x) = po x
(p,(
pl
P()(()) -()((r)=p)+0 =
N
PEZ
1=1
T N
N (() = p) log 8
log N
N
=0
O
N + +H+VVNTN
NT log
PEZ 1=1
where the first equality follows from the
inequality. This completes the proof.
For Tz, we specifically tailor our analysis to the case L = _ and = we cannot merely apply Freedman's 's inequality and take a union bound over all l E L. Furthermore, fox does not have finite-sized cover with respect to the fx metric (Guntuboyina and Sen, 2012), thereby rendering our covering number-based arguments futile. However, a recent result (Lemma 10) due to Gopalan et al. (2024) gives tight (up to logarithmic terms) bound on the approximate rank convex functions. Therefore, to obtain a high probability bound for Tz. we shall express the supremum over E _ in terms of supremum over the elements of the basis and subsequently apply Freedman's inequality to bound the latter quantity.
res Since L is infinite,
We first define notion of approximate basis, following Gopalan et al. (2023b); Okoroafor et al. (2025).
Definition 1 (Okoroafor et al. (2025)). Let I be a set and FF C 1J A set G C 1 is an > 0 approximate basis for F with sparsity s and coefficient norm ffr every h E F, there exists a finite subset (9I...., . S G and coefficients cI...., E [-1,1] satisfying
h(z) - Σ (z)(())
S f all x E T and Σ S
30

---

In the special case when 9 itself has elements, we say G is a finite e-basis for F of size s with coefficient norm X.
Lemma 10 (Gopalan et al. (2024)), For all & > O, Lex admits finite E-basis of size O log # (+)
with coefficient norm
In the following result, we bound T2 when F is finite. Subsequently, we bound To for Frll by covering sumber-based argument.
be a finite hypothesis class. For a ò S 7, with probability at least Lemma 11. Let F C [-1, 1]x
1 8, we have To = O T + /NTTog NIJI
Proof. Observe that E(p, y) can be written as E(p, v) = (1 ((p,0) + E(p, 1). We begin by bounding T2
T2
sup (eoxx
[pp) = (olo((((())) u.) P(p((x) =) EIG.(ff(())
PEZ t=1
sup pEZ (
[pr( o/. ()]{((((x)))) v.) (())(x) = =)) ((((S((s) =
Σ vi) (.).I1e [pp((x)) = o) (([(z)), P(e((x) = v) E [(1 9) -((((x)
sup PEZ (oa
T
Σ sup PEZ (
Σ 1=1
(p)( = o) {(f(zt), 1) (x) = w) E ((f(z),1)lllt =
The two terms above can be bounded in an exactly similar manner. For the sake of brevity, we only provide details for bounding the second term. We begin by bounding the absolute value accompanying the second term. Since the function E(p. 1) convex in p. admits finite e- basis & with coefficient norm 2 (Lemmaa 10), i.e., there exist functions ......, -[9] such that for each E Lox there exist constants e1 (e),..., G (f) E [-1,1] satisfying Σ |ca(E) S 2 and 1) (p) S & for all E [o, 1]. Bounding {(f(x,, 1) in terms of its basis representation and applying the Triangle inequality, we obtain the following upper bound on the absolute value accompanying the second term
|Gl
W1 [[pp(x))= w)
Σ
(()a(((()))))
-P(p(x =)
E [v =((0((())))o)))))==)))))))))))))
Σ y/ (pp(( + Σ ((px(x)) v)
which can be further bounded by
[+]
Σ y1 Tpp((xx) = =((((())))) P(p((x) u) TE ())BB)))(((()))))))) (((()))l.. 00
(e)
sup gEg
Σ Ue [pr = o] o) + Σ ((p((x)) = u).
Therefore, the following expression upper bounds the second term:
T ve. (pe) = v) (x(()))) (P(p)()) = v) E gf (x(())) = + +57)
Σ sup VEZ JEG.FEF
Σ
31

---

ag E G. 2 and define the martingale difference sequence XI...., Xr, where x= y [x))(x)) = o] ((f(z))) - ((p((z) = v) E ly ((f(x))lp((o) = v]. Repeating a similar analysis in the proof of Lemma 9, we obtain,
T
(1
Σ X -0
P(p((z)= - log + log 8
Taking union bound over all g F Z, obtain that with probability at least
31 (pp)()))) = - (()((z) = u) Ey o(f(=)))p,(x)
(VE2
T
N
NI 8
NI [g]
N
Σ ((p((x) ((p =t)
log
log
8
Combining everything, we have shown that the second term can be bounded by
Σ EE
Σ
T
((p.(z) v)
log
N
|
+ N log
|
9
+
ET'
8
N F
O
+
NT log
N
5
on choosing v. bounding [9] per Lemma 10, and using the Cauchy-Schwer inequality. Repeating the steps above, we obtain the same bound for the first term. Adding both the bounds yields the desired result.
Using the result of Lemma and by a covering number-based argument, we bound T/ for F Fraff in the following lemma.
Lemma 12. When F Falt for a S 1. with probability at least 1 1-6 8. we have To
O ( E + VdNTlog )
Proof. Let Ce be an E-cover for res. For a f E Faff let fo be the representative of f. By the 1-Lipschitzness of f, we have
[e(f(z).v) e(fe(x). If(()) fe(x)) se.
Therefore, To can be bounded as
T2
T
- - PP()(()) = b) -E((((()) v))((()))))ba((()) =c] Σ (xx)))) = ((f(z))
sup (OU
PEZ
Σ sup pEZ Lo
Σ (xx)) = -0. E(J((x)) v6) - P(p((() v) B((((()) =0] + 2:T
T N
N IC NTNTooo
T I + ANNT dNNTlog log
N
o
+
+ eT 0
8
on choosing n and bounding |Cr| as per Proposition 1. This completes the proof.
Combining the result of Lemmas and 12, we have the following high probability bound on the deviation between the distributional and online swap omniprediction errors: A
N log ) Combining this with bound on the online swap omniprediction error
(Theorem 2), we obtain the following theorem, which bounds the swap omniprediction error of the predictor learned via the online-to-batee reduction.
32

---

Theorem 4.
With probability at least 1-6, the randomized predictor learned via the online-to to-hatch reduction satisfies
S0mni pom JT = Ō x(4
d 3/
1
+
T
V
log
Consequently (dee samples are sufficient for to achieve a swap omniprediction error at most E.
Proof. The swap omniprediction error of the predictor be bounded as
SMCal FI
SMCal
0 ((
Nd log
N
A +
SA+1
+
T
T
Setting N 2 we obtain the desired result.
D.2 Sample complexity of swap agnostic learning
For the squared loss, the result of the previous section already gives (dde-a) sample complexity for swap agnostic learning. However, in this section, we improve the bound to (.de-2.5) Similar to Section D.I, we perform an maline-to-batee reduction using our online algorithm Theorem 3, which refer to Aswap-ag for brevity. Given T instances (11. ..... (DT, yr) that are sampled ii.d from D, we feed the instances to Aswap-ag ag to obtain predictors PI..... pr. Subsequently, the predictor p is sampled from the uniform distribution over Pı....,PP Pr.
To derive the improved sample complexity rate, we show an improved bound on the deviation between the swap agnostic error and the contextual swap regret. Notably, our bound on the deviation is stronger than the O
1 N2
+
log
+
JN
log
N. bound obtained in Section x
N
D.I. Comparing the two bounds, in the latter, we incur N term due to an approximation of proper losses in terms of V-shaped losses (p y) (u y) sign(p - v) and subsequently, we replace the supremum over E [0, 1] with o' 2, which incurs an additive N error. However, for the squared loss, this step is no longer needed since we can directly apply Freedman's inequality. This enables us to get an improved 1 contextual swap regret (which is better than the Ö(T3) bound the online swap omniprediction error), we obtain the improvement from -3 to = 2.5 thereby saving a -0.5 factor. To formalize the above discussion, define the deviation
N2 dependence. Finally, on combining this with the Ō(T3) ) bound on the
A = sup (J.EFlezz
E B(za)~D,por (p(xx) y)² (z)
((p((x)) y1)² ((m(()))())) y0)))
Since p is sampled from n, we have
E E( [(p(x) - y) (x)()(() y)
T
E (D [(p((x) - y)² (fm())())) y)²].
T
The expectation the right hand side of the equation above be rewritten Evez P(r((x)
v) E [v y)² (f) l)) = w]. Therefore,
T
A T
sup
Σ
Σ
((p((z) v) El(v y)² w)
TEE
Z
Ip((xx)) = o) ((v - -- (fo(z)) - -1)))
33

---

T
- Σ sup VE /EF
Σ P(pi(x) = v) 1B [(v - ((= - (f(x) 1) = o)
[((((z)) = v] ((v- - ((v- - (f(xz)
(1f())))1)) - -v))
(21)
where the inequality follows by Triangle inequality and sub-additivity of the supremum function. In the next lemma, we bound A when FF is finite. Subsequently, we bound A for F == by covering-numtn based argument.
Lemma 13. Let F [-1, 1]x
be a finite hypothesis class. For a 7o with probability at least
1- 8, we have A O (V + log NIFI
Proof. Fix a E / E F, and consider the sequence XI...., XT, where X₁ is defined as
X₁ = P(p = v) E (v y)² (f(x) y) px()) = (x,) = v) ((v y²)² - (f()))))()))
Observe that the above sequence is a martingale difference sequence. Furthermore, since f E [-1,1], Σ X S HVx + log / with
we have X,| S 8 for all t E [T]. Applying Lemma 6, we obtain
probability at least 1 - 6, where E [0, ] is fixed and the cumulative conditional variance Vx can be bounded
T
T P(p.(x) = v).
Vx S
Σ
((p((x)= = u) (E [v y)² (p) < 16 Σ
-
Repeating a similar analysis as in the proof of Lemma 9, we obtain
(V(
r
T
Σ
X =
Σ ((p((x) = =0) log + log
Taking a union bound over all Z. F, we obtain that with probability at least 8
Σ F(pe(x) u) E (v y)² -f(()= =)) (x())(())
sup feF
[p((ax)) u] (w- y²)² 2- (f(xz) yr)2)
(VE
Σ (x) (x))
=0)
log
F 5
+
log
N |F
(22)
holds simultaneously for all v E Therefore, we can finally upper bound as
TV
1
Σ
Σ
((p((z) = log
N F
log
8
F
(V
(VT
N
log
N
[
DEZ
where the first equality follows from (22) and the Cauchy-Schwartz Schwartz inequality, while the second equality follows by dropping the lower order term. This completes the proof.
Using the result of Lemma 13 and by covering number-based argument, bound To for F = Flin in the following lemma.
Lemma 14. When F Flin, for a s to with probability at least - ô, we have
log
N
T
34

---

Proof. Let & be the squared loss and C. be an E-cover for F Observe that the squared loss is 6-Lipschitz in p for p [-1.1]. For a f F, letting fx be the representative of f. we have [e([(z). y) ((f((x) v) = 61f(z) [c(x) s 68 for all X, E (0, 1j. It then follows from (21) that
A -
Σ sup
Σ
((p((x)) = u) B [e ((f(z), v)lc(())))))))))))))))))))){))) v]
T
MEZ FEF
1lpx(x) o] (L(v, we) ((f(ze).
S 1 Σ sup T fEC,
Σ 1=1
P(p((z) = E))(u())) ((f(z).))lll)) = =b]
[ppe(x) = v) (e(v, m1 (((())). v1))
T
T
6
6
+
P(pe(x) = u) +
1ppe(x) = w]
T
T
DEZ
(=
VEZ
N
N
CC
1
d.N
N
=
=
c
T
log
5
= 0
N2
T
log
8
where the second inequality follows by bounding ((f(x), y) in terms of ((fe y); the first equality follows from Lemma 13, while the final equality follows by choosing NZ and bounding [Cgl as per Proposition This completes the proof.
Combining the result of Lemma 14 with the bound on SRegz! (Theorem 3), we bound the expected swap agnostic error incurred by p.
Theorem 5. With probability at least 1 1-6, 5, the randomized predictor p learned via the online-to batch reduction satisfies
SAE F. = ((4) 3 +
d
log
T
Consequently, (255 samples are sufficient for to be achieve a swap agnostic error at most e.
2.5
Proof. The expected swap agnostic error incurred by p can be bounded by
SReg pt
dN
N
d T
T
O
N2
+
V
T
log
= ō
+
T
log
on choosing N (2) Note that the first equality above, we have used the bound
N N2 + Ndlog T + V /dNT log 8
T
SReggtn
which follows from Theorem 3. This completes the proof.
D.3 Sample complexity of swap multicalibration
In this section, we establish Ō(E-5), ((552.5) sample complexities for learning E1, Ewws multical- ibrated predictors respectively. We first establish the sample complexity of f2-swap multicalibration by using characterization of swap multicalibration terms of swap agnostic learning. Subsequently, we utilize the sample complexity result derived from the previous section.
35

---

Lemma 13. (Globus-Haree Harris et al., 2023, Theorem 3.2) Fix predictor and assume that there exists a Range(p). f E Fi such that f' E such that
v| 2 a. for some a >> 0. Then, there exists E ()) (f'(x) y)² pp())
2 a
The above result was concurrently obtained by Globus-Harris et al. (2023) and Gopalan et al. (2023b), and subsequently extended to the online setting by Garg et al. (2024) (see also Lemma 3). Using Lemma 15, we establish the following result that relates the Eg-swap multicalibration error and the swap agnostic error.
Lemma 16. Fix a distribution over predictors, and assume that there exists such that ((o.))DD.pr [p(x)) - y)² - (Jp(a)(v) - y) S a.
sup (feETahee2
Then,
sup (.EFi)vc
E Ep Ex
(y (y--v)plee w))p(x) = u1² aa [[f((x)
Proof. The proof follows similar approach to that of Lemma 4. Assume on the contrary that
E Ep E (f) (v v)]p(z) = u1² >
sup (S (f.EFieee
Then, there exists comparator profile (So FijuEz such that
E
Bpou
Σ P(p(x) -) (xf - w)(p(r)) o|² > a.
DEZZ
For simplicity, define Ogg P(p(x) = u) (x)f(()() v)(p(x) = =]}². Then, for all v E Z, we have
(l - w)(p(>) = u|1 P(p(x)- =))
Oh
Clearly, there exists function f which either fo or -o such that V Pip(z)mu) Furthermore, ft E Fi since F satisfies Assumption As per Lemma 15, for each there exists f E F4 such that (p((x)) v) [[(p(z) y)² - (z) v) = au
v)(p(>) = =
for all Z. Summing over Z, we obtain E,E [p((z) y)² (f((x) 11)(p(()) ol
EvEz ag. Taking expectation over IT, we obtain
Epus E.E.E. (p(x)- - v)² - (z) - = = 2 EpR Σ >a
L
which contradicts the assumption
B(ew))-D,p' [(p(x) -2²² (Jp(a)(() w) S a
sup
(J.FFthez
This completes the proof.
Since 2 s -2. samples are sufficient to achieve a swap agnostic error at most (as per Theorem 5), we obtain -2.5) sample complexity of learning a fa-swap multicalibrated predictor with error at most Therefore, we have the main result of this section.
Theorem With probability least 5, the randomized predictor p (Section D.2) learned via the online-to- to--ttohhhhhhhh reduction satisfies
d
d
DSMCal 2
+
log
T
T
d
d
DSMCal =
+
log
T
Consequently, Ωdde- (dd--5) samples are sufficient to achieve E,, -s-wp multicalibration errors most e, respectively.
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Justifications to the claims made in the abstract and introduction are either provided the main body or the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Limitations are discussed in the section Conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
37

---

Justification:
Assumptions are explicitly written in the main body and proofs can be found
in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper is theory work and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
38

---

Answer: [NA]
Justification:
The paper is a theory work and does not have any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ Stapcc/guiies//oodeeee
wwwissssssoolllioeeeooeooeeeeeee plyycyy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //iips.co.o wttpccccpppccceeeeccec.cccccccct wwwicc/ggg////eeeee /CodeSubmiia
seniibiisssii sesiiissinnne.iii oniioniyl / for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper is a theory work and does not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper is a theory work and does not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
39

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper is theory work and does not have any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //tp///eerpp//e/eee cc
Answer: [Yes]
Justification:
The research abides in every respect with the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theory work and does not have any immediate societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
40

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper is theory work and doesn't 't poses any such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper is a theory work and does not use any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi sepoorswithodeee thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
41

---

Answer: [NA]
Justification:
The paper is a theory work and does not release any new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper is a theory work and does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper is theory work and does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact core methodology, scientific rigorousness, originality of the research, declaration is not required.
42

---

Answer: [NA]
Justification: The paper is a theory work and the core method development in this research does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to our LLM policy (https / /ttp///erippp//eeee cc/Conferencest /LLM) for what should or should not be described.
43


Reviews:
[{"review_id": "qh2G9wkCIs", "reviewer": "Reviewer_wMot", "summary": "This paper gives novel bounds on the multicalibration and ominprediction errors in the both the adversarial (online) and distributional settings. The proven error bounds in the adversarial setting are as follows:\n* swap multi-calibration regret: $T^{1/3}$ (improved from $T^{3/4}$)\n* swap omniprediction regret: $T^{2/3}$ (improved from $T^{7/8}$)\nSimilar improvements have also been established in the distributional setting, with an online-to-batch conversion. The key idea is to connect to a particular notion of a pseudo-regret (where some of the randomness is removed) via a martingale concentration argument.", "questions": "* What does the notation $\\mathbb{R}^X$ mean? Is this the set of functions $X \\to \\mathbb{R}$?\n* The connections between multi-calibration and fairness are unclear. It would be good to dedicate some space to that aspect to appeal to a broader audience.\n* Are any lower bounds known for any of these problems? What about simplifications to known textbook-type problems?\n* I'm unable to parse $\\rho_{p, f}$ and the meaning of the definition in eq. (1). This needs some interpretation.m\\", "limitations": "N/A", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n* This paper gives significantly improved bounds across the board over prior works on swap multi-calibration and, via established reductions, on swap omniprediction. Both of these are previously studied problems in the literature.\n* While the techniques and individual steps appear to be known or inspired from very similar ones, the improved bounds are obtained by carefully putting together various pieces.\n* The paper seems well-polished and I did not see any typos.\n\n**Weaknesses**:\n\nI found the paper nearly impossible to parse. As somebody who is familiar with learning theory but never previously heard about multi-calibration or omniprediction (or swap contextual regret, or similar terms), I expected to be able to at least understand the definitions and the significance of the results. While the paper reads like something that researchers knowledgeable in this (apparently niche) area would appreciate, I did not even understand the basic definitions. Further, it tries to pack a lot of math into a small number of pages, making the text incredibly dense as well.\n\nI especially did not understand the definition of multi-calibration. While this is an established notion and has a prior literature, I believe the onus is on the authors to provide enough intuition about the definitions and significance of the results (at least in the appendix). Similarly, I do not understand where the \"swap\" versions come from or why they are interesting.\n\nIt would have been nice to see more special cases/connections as to why these bounds are interesting, such as connections to textbook examples that a reader such as myself would appreciate. For example, the introduction mentions connections to fairness: that would be a good setting to expand upon.", "was_revised": true, "final_justification": "I'm updating my score with the understanding that the authors will revise the paper to make it more broadly accessible (with interpretations, examples, etc.) and less mathematically dense.", "rebuttal": "We sincerely thank the reviewer for their comments and time in evaluating our paper. We are sorry to hear that the reviewer found our paper difficult to parse. We apologize for the same and shall revise the paper to make it appealing to the broader audience, keeping in mind several suggestions given by the reviewer. Below, we respond to all your questions and comments, along with an (additional) explanation of multicalibration, since the reviewer was unable to understand the concrete definition.\n\n> What does the notation $\\mathbb{R}^{\\mathcal{X}}$ mean? Is this the set of functions  $\\mathcal{X} \\to \\mathbb{R}$?\n\nYes, this is a standard notation used in set theory.\n\n> Are any lower bounds known for any of these problems? What about simplifications to known textbook-type problems?\n\nRegarding lower bounds, we would like to mention that Appendix A does provide some lower bounds for online $\\ell_1, \\ell_2$-Calibration (particularly, $\\text{Cal}_1, \\text{Cal}_2$ as defined in lines 167-168). In summary, proving lower bounds for online calibration is a significantly challenging problem and obtaining the minimax bound is still open, with recent breakthroughs establishing that $\\tilde{\\Omega}(T^{0.54389}) \\le \\mathbb{E}[\\text{Cal}_1] \\le \\tilde{\\mathcal{O}}(T^{\\frac{2}{3} - \\varepsilon})$ (for a sufficiently small $\\varepsilon > 0$) and $\\tilde{\\Omega}(T^{0.08778}) \\le \\mathbb{E}[\\text{Cal}_2] \\le \\tilde{\\mathcal{O}}(T^{\\frac{1}{3}})$ (Qiao and Valiant, Dagan et al., Fishelson et al.). Based on the above results, we infer the following: \n\n(a) Since contextual learning is harder than the non-contextual variant, and for the squared loss, the non-contextual swap regret is equivalent to $\\text{Cal}_{2}$, the lower bound for $\\text{Cal}_2$ also applies to $\\text{SReg}$ (contextual swap regret).\n\n(b) Since (swap) multicalibration is stronger than calibration, the same lower bounds also apply to $\\text{MCal}, \\text{SMCal}$.\n \n(c) For swap omniprediction, Garg et al. proved that for a loss class that comprises of convex Lipschitz functions, against a hypothesis class $\\mathcal{F}$ that consists of the constant $0, 1$ functions, $\\Omega(\\mathbb{E}[\\text{Cal}_1]) \\le \\mathbb{E}[\\text{SOmni}]$.\n\n\nRegarding simplifications to known textbook-type problems, we would like to mention that some reductions do exist; however, the reductions and the reduced problems are far from deserving a textbook treatment, e.g., a lower bound for $\\text{Cal}_{1}$ was proved by Qiao and Valiant by reducing to the sign preservation game and an improved lower bound was proved by Dagan et al. by reducing to the sign preservation game with reuse.\n\n> I'm unable to parse and the meaning of the definition in eq.(1). This needs some interpretation.\n\n $\\rho_{p, f}$ represents the average correlation between $f$ and the residual error sequence $\\{y_1 - p_1, \\dots, y_{T} - p_{T}\\}$ conditioned on the rounds that the forecaster predicts $p_{t} = p$. Noting the requirement for multicalibration in the distributional setting, i.e., $\\mathbb{E}[f(x) \\cdot (y - p(x)) | p(x) = v] = 0$ for all $f \\in \\mathcal{F}, v \\in \\text{Range}(p)$, the quantity $\\rho_{p, f}$ is an analogue to $\\mathbb{E}[f(x) \\cdot (y - p(x)) | p(x) = v]$, adapted to the online setting. Similarly, the normalized term $\\frac{1}{T}\\sum_{t = 1} ^ {T} \\mathbb{I}[p_{t} = p]$ in Equation (1) (normalization skipped in the manuscript) corresponds to the average frequency of the prediction $p$ and is an analogue to the quantity $\\mathbb{P}(p(x) = v)$. With this intuition, the quantity $\\sum_{t = 1} ^ {T} \\mathbb{I}[p_{t} = p] \\sup_{f \\in \\mathcal{F}} |\\rho_{p, f}| ^ {q}$ corresponds to the maximum correlation (weighted by the number of rounds the prediction made is $p$) achieved by an $f \\in \\mathcal{F}$ for the prediction $p_{t} = p$. The cumulative sum across all predictions corresponds to the quantity $\\text{SMCal}$ (we allow higher order $q$-th moments for $\\rho_{p, f}$ to consider the full generality). Intuitively, a small value for $\\text{SMCal}$ represents that no hypothesis in $\\mathcal{F}$ is able to detect correlation with the residual sequence $y_{1} - p_{1}, \\dots, y_{T} - p_{T}$ when conditioned on the level sets.\n\n> The connections between multi-calibration and fairness are unclear. It would be good to dedicate some space to that aspect to appeal to a broader audience.\n\n Thank you for pointing this out. We shall clarify this in the subsequent revisions. Intuitively, since multicalibration is defined at the scale of partitions of the instance space (the predictions are conditionally unbiased for the every set $s \\subseteq \\mathcal{X}$ in a collection of subsets $\\mathcal{S}$ of the input space $\\mathcal{X}$), it allows fairness guarantees for every subset $s$ of $\\mathcal{S}$ simultaneously, e.g., $\\mathcal{X}$ could represent the population of a province, the set $\\mathcal{S}$ can be several possibly overlapping demographic groups within that province, and $p$ can be the probability that an individual is affected by a particular disease. On the contrary, calibration is only a marginal requirement and cannot address such finer fairness concerns. For further discussion regarding the fairness implications of multicalibration, we refer to Obermeyer et al.\n\n Obermeyer, Z., Powers, B., Vogeli, C., & Mullainathan, S. (2019). Dissecting racial bias in an algorithm used to manage the health of populations. Science, 366(6464), 447-453.\n\n> I especially did not understand the definition of multi-calibration.\n\nWe begin with defining calibration in the distributional setting. Consider a binary classification problem with instance space $\\mathcal{X}$, label space $\\mathcal{Y}$ be {$0, 1$}, $\\mathcal{D}$ be an unknown distribution over $\\mathcal{X} \\times \\mathcal{Y}$, and $p^\\star(x) \\coloneqq \\mathbb{P}(y = 1 | x)$ be the Bayes optimal predictor. Let $p: \\mathcal{X} \\to [0, 1]$ be a predictor and $\\text{Range}(p)$ denote the range of $p$ (set of all values that $p$ predicts). The predictor $p$ is perfectly calibrated if for all $v \\in \\text{Range}(p)$, we have $\\mathbb{E}[y | p(x) = v] = v$, i.e., the predictions of $p$ are correct conditioned on its level sets. With this background, multicalibration can be interpreted as a refinement of calibration to partitions of the instance space $\\mathcal{X}$. Particularly, given a collection $\\mathcal{S}$ of potentially overlapping subsets of $\\mathcal{X}$, a predictor $p$ is perfectly multicalibrated if for all subsets $s \\in \\mathcal{S}$ and $v \\in \\text{Range}(p)$, we have $\\mathbb{E}[y| p(x) = v, x \\in s] = v$. As can be noted from the definition, the Bayes optimal predictor $p^\\star$ is multicalibrated. For both computational and information-theoretic reasons, obtaining the Bayes optimal predictor is considered impossible; therefore, the problem of multicalibration asks to efficiently find a predictor $p$ such that $\\mathbb{E}[y| p(x) = v, x \\in s] \\approx v$ for all $v \\in \\text{Range}(p), s \\in \\mathcal{S}$. Note that the above definition of multicalibration can be made more general. Specifically, since each subset $s$ of $\\mathcal{X}$ can be described via a function $g: \\mathcal{X} \\to$ {$0, 1$} ($1$ if $x \\in s$ and $0$ otherwise), the set $\\mathcal{S}$ can be equivalently described by a collection $\\mathcal{G}$ of set-membership functions. The above definition can be equivalently written as $\\mathbb{E}[y| p(x) = v, g(x) = 1] = v \\equiv \\mathbb{E}[g(x) \\cdot (y - p(x))|p(x) = v] = 0$. For an arbitrary real-valued hypothesis class $\\mathcal{F} \\subset \\mathbb{R}^{\\mathcal{X}}$, multicalibration requires $\\mathbb{E}[f(x) \\cdot (y - p(x)) | p(x) = v] = 0$ for all $f \\in \\mathcal{F}, v \\in \\text{Range}(p)$. Since the quantity $\\mathbb{E}[f(x) \\cdot (y - p(x))]$ corresponds to the correlation between $f$ and the residual $y - p(x)$, multicalibration for an arbitrary real-valued hypothesis class can be interpreted as the condition that the hypotheses in $\\mathcal{F}$ cannot find any correlation with the residual sequence $y - p(x)$ when conditioned on the level sets of $p$.\n\nShould you have any more questions, do not hesitate to reach out. If our responses have addressed your concerns, we would be grateful if you would consider updating your assessment accordingly."}, {"review_id": "fvFwm18Fkq", "reviewer": "Reviewer_bikt", "summary": "This paper derives improved online rates and sample complexity rates for swap omniprediction.\n  Swap omniprediction is a strengthening of omniprediction (learn a predictor that is close enough to Bayes optimal that it can be post-processed to be near-optimal for any loss) that was introduced by GKR24, who motivated the concept by noting that while multicalibration > omniprediction, swap multicalibration = swap omniprediction.  \n  The authors obtain these improved rates by instead first deriving faster rates for a 'pseudo' variant of swap multicalibration that allows them to reduce to a more tractable problem of pseudo contextual swap regret.  \n\n The main proofs are for the online setting, with the distributional sample complexity rates following from an online-to-batch reduction. The main intuition of the paper (which is nicely summarized in Figure 1) is that instead of obtaining swap multicalibration rates by reducing to swap regret minimization, the authors instead reduce to pseudo swap regret minimization. One way to understand what this detour through pseudo calibration measures is doing is that its effectively separating the analysis of the variance caused by the forecaster's random forecasts with the actual learning component.\n\n  The interesting thing (at least to me, who has not followed the recent work here closely) is that reducing from swap multicalibration to pseudo-swap multicalibration costs such little overhead: $O(N)$ . This is done in Lemma 1 which shows SMCal_{ F, 2} leq O(N log (|F| N / delta)) + 6 PSMCal_{ F,2} with the overhead term being negligible for the types of discreitizations we normally consider, e.g. N=T^1/3. The analysis is an adaptation of Freedman's inequality, which is currently not really talked about in the main text.  \n\n  The pseudo-multicalibration rates are obtained by reducing to pseudo contextual swap regret. This happens in Lemma 3 (through lemma 4). Specifically: if there is pseudo-multicalibration error, then that error can be captured by a linear competitor meaning that there must be some pseudo contextual swap regret. So, pseudo swap contextual regret for the affine closure of functions in F always upper bounds pseudo multicalibration for F.  The other step of the reduction, going from swap multicalibration to swap omniprediction is standard.  \n\nThe other chunk of the paper is actually obtaining good rates for pseudo swap regret minimization. The algorithm follows the usual Blum-Mansour algorithm for minimizing swap regret where you instantiate multiple algorithms, one for each action, and then act according to a stationary distribution over the algorithms. In this case, we use the BM algorithm with actions corresponding to discretized level sets and online newton step for external regret minimizers (because squared loss is exp-concave). The algorithm design and analysis follow a pretty standard recipe, with the main interesting component being the observation that relaxing to \"pseudo\" swap regret means that instead of the BM reduction getting noisy feedback it gets deterministic feedback, and so one doesn't need to add in an error term for stochastic approximation.", "questions": "I'm not very familiar with the swap omniprediction literature; is there a fundamental eps^-3-eps^-2 separation for swap vs normal omniprediction that's known?\n\nPrior offline swap omniprediction rates cited in Table 1 are attributed to [2, 13] rather than [5]: is there a challenge with online-to-batch adaptation of the rates of [1]?\n\nWhy do these detours into pseudo calibration measures arise with \"swap\" objectives whereas e.g. [6]'s optimal rates for omniprediction do not appear to need them?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well-written with concrete improvements in theoretical results (improved rates for swap omniprediction) and a clean conceptual contribution: when trying to get rates for swap calibration/omniprediction/agnostic-learning, it's often easier to mentally separate out how one analyzes the stochastic approximation errors from forecast randomness—reducing to pseudo calibration and pseudo swap regret is a nice way to think about how to do this.\n\nI don't have any particular concerns with weaknesses in presentation or results. I did not check the proofs, which are deferred entirely to the appendix, carefully though the results and steps seem reasonable.", "was_revised": true, "final_justification": "I maintain my original positive review.", "rebuttal": "We sincerely thank the reviewer for their comments and time in evaluating our paper. Below, we provide responses to all your questions.\n \n> I'm not very familiar with the swap omniprediction literature; is there a fundamental $\\varepsilon^{-3}-\\varepsilon^{-2}$ separation for swap vs normal omniprediction that's known?\n\n We are not aware of such a separation in the offline setting. However, in the online setting, Garg et al. [1] established that for a loss class of convex Lipschitz functions, against a hypothesis class $\\mathcal{F}$ that comprises the constant $0, 1$ functions, we have $\\tilde{\\Omega}(T^{0.54389}) \\le \\mathbb{E}[\\text{SOmni}]$, where the $\\tilde{\\Omega}(T^{0.54389})$ lower bound is due to a breakthrough result by Dagan et al. [19], Qiao and Valiant [18]. The lower bound on swap omniprediction also implies that an online-to-batch conversion for swap omniprediction cannot achieve $\\varepsilon ^ {-2}$ sample complexity, in general. For omniprediction, Garg et al. [1], Okoroafor et al. [6] established that $\\tilde{\\mathcal{O}}(\\sqrt{T})$ omniprediction error is achievable, therefore establishing a strict separation between the above notions in the online setting.\n\n> Prior offline swap omniprediction rates cited in Table 1 are attributed to [2, 13] rather than [5]: is there a challenge with online-to-batch adaptation of the rates of [1]?\n\n[5] established an equivalence between swap multicalibration and swap omniprediction, and also showed that the multicalibration algorithm of [2] is swap multicalibrated; therefore, we attributed the bound to [2], which had an explicit sample complexity bound. Moreover, a characterization of swap multicalibration in terms of swap agnostic learning was concurrently obtained by [13], who also derived an explicit sample complexity for swap agnostic learning; therefore, we chose to refer to [13]. However, we accept your suggestion and shall additionally refer to [5] for the result regarding swap omniprediction. For the second part of your question, a standard online-to-batch adaptation (using Azuma-Hoeffding's inequality) of the rates of [1] shall yield a $\\tilde{\\mathcal{O}}(\\varepsilon^{-8})$ sample complexity for swap omniprediction for the class of convex Lipschitz functions against the class $\\mathcal{F}_{\\text{aff}}^{\\text{res}}$ of scaled and shifted linear functions. Throughout the paper, we abstain from referring to this result since it was not mentioned in [1]; we instead tabulate the rates that were explicitly documented in the literature. \n\n> Why do these detours into pseudo calibration measures arise with \"swap\" objectives whereas e.g. [6]'s optimal rates for omniprediction do not appear to need them?\n\nExcellent question. The relationship between swap regret and calibration has been known since long, starting with the seminal work of Foster and Vohra [9]. It is known from several papers that $\\ell_{2}$-Calibration ($\\text{Cal}_{2}$) is equivalent to the swap regret of the squared loss. While this opens up a natural direction to developing algorithms for calibration, it also poses an immediate challenge --- minimizing swap regret is considerably challenging than minimizing external regret. Along the direction of minimizing swap regret, the well-known Blum-Mansour [11] reduction works for the non-stochastic component of learning, i.e., it bounds what we refer in the paper to as pseudo swap regret, which is related to pseudo calibration. While there exist other reductions, e.g., Ito et al., Dagan et al., that reduce swap regret minimization to external regret minimization, they either lead to suboptimal dependence on $T$ (Dagan et al.) or involve further randomization in the algorithm (Ito et al.), rendering their adaptation to minimizing the swap regret of the squared loss quite non-trivial. In summary, the relationship between calibration and swap regret, and the fact that minimizing pseudo swap regret (thus, pseudo calibration) is easier than swap regret, is a possible explanation of the detour.\n\nIto, S. (2020). A tight lower bound and efficient reduction for swap regret. Advances in Neural Information Processing Systems, 33, 18550-18559.\n\nDagan, Y., Daskalakis, C., Fishelson, M., \\& Golowich, N. (2024, June). From external to swap regret 2.0: An efficient reduction for large action spaces. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (pp. 1216-1222).\n\nWe hope that our responses answer your questions. Should you have any more questions, please feel free to reach out."}, {"review_id": "pLhsBKcZOv", "reviewer": "Reviewer_59sM", "summary": "This paper provides an algorithm and improved upper bounds for the problems of (swap) omniprediction and multicalibration in the online and (by an online-to-batch reduction) the offline batch settings. In particular, the authors employ an alternate proof strategy to solve an open problem proposed by Garg et al. on the possibility of achieving $O(\\sqrt{T})$ $\\ell_2$-multicalibration error against bounded linear functions. The authors' main technical result is an algorithm for achieving $\\ell_2$-swap multicalibration in $O(T^{1/3})$. This bound also implies significant rates for multicalibration, swap omniprediction for convex Lipschitz functions, and, accordingly, improved sample complexity in the offline analogues. The main argument, to my understanding, is as follows: \n\n1. The authors introduce two notions *pseudo swap multicalibration* and *pseudo swap contextual regret* that avoid dealing with averaging over the Learner's predictions in the online game, and a reduction exists from swap multicalibration to pseudo swap multicalibration (simply via a covering argument on the class of linear functions) \n2. The authors reduce pseudo swap multicalibration to pseudo contextual swap regret via properties of the linear function class\n3. **main technical contribution:** the authors develop an algorithm for pseudo contextual swap regret using a reduction to the classical external to swap regret reduction of Blum and Mansour and an improved rounding scheme. This reduction requires an external regret algorithm to exist, which the authors instantiate as simply Online Newton Step for a particular linear function class.\n\nThe upper bound obtained by this argument then implies improved results in online and offline (swap) omniprediction and $\\ell_1$-multicalibration through improvements of more standard arguments.", "questions": "1. Have these pseudo notions previously appeared in the literature? It seems that the argument hinges around the construction of these notions, and they do point towards a major difficulty in multicalibration-style regret bounds -- the conditioning on the $p_t$s.\n\n2. Is the bounded linear functional necessary in this argument because of the covering and reduction to $P_t$ (pseudo notions)? The argument seems specialized once we go to pseudo notions because of the ease of constructing a cover. To this note, would more general function classes need new techniques entirely?\n\n3. I'm curious as to the efficiency compared to the previous algorithm of Garg et al? To my understanding, the Blum/Mansour reduction is efficient because it just employs $N$ external regret algorithms (where $N$ is from the rounding). Even a qualitative comparison of the \"efficiency\" compared to the previous algorithm would be interesting, just to note the algorithmic differences of the approaches.", "limitations": "Yes (pure theory paper).", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I am quite positive on this paper -- the results are clearly presented with an eye towards giving a nice proof sketch and overview of the entire argument for the reader, the techniques themselves are combined in a novel way, and the authors provide good contextualization with the rest of the literature on omniprediction and multicalibration. The only weakness that the authors might address is to possibly provide a bit more intuition on why these particular techniques result in the improved bounds -- although it seems clear to me that the improvements come from the reduction to the *pseudo* notions, a comparison to why the pseudo notions combined with the standard Blum/Mansour external to swap regret reduction and improved rounding scheme give a key algorithmic improvement to the prior work of Garg et al. I understand that the rates go down, but it would be very nice to also have the insight on *why* the pseudo notion is \"easier to optimize\" in this particular context. A couple sentences on that would improve an already very good paper.\n\n## Strengths \n\n**Originality:** To my knowledge, the authors' techniques in proving the main improved upper bound on $\\ell_2$-swap multicalibration is novel, and, in particular, the key introduction of *pseudo* swap multicalibration and *pseudo* contextual swap regret is novel. In fact, I am interested in seeing if similar notions have cropped up in the literature (see \"Questions\"), as the move from having to condition using the empirical conditional distribution of the $p_t$ to just dealing with the true distributions at each step certainly simplify the \"conditioning\" problem that arises when dealing with these multicalibration notions in the online setting, and I'd be interested in seeing if this kind of strategy has been employed before. To my knowledge, this seems like a new move. \n\n**Quality:** The results of the paper themselves improve bounds for several open questions, and the authors \"use the full force\" of their main derived bound to fully address the implications downstream for ominprediction and multicalibration by also working out the details for the offline setting, which I appreciated. It answers an existing open question about a specific faster rate for $\\tilde{O}(\\sqrt{T})$ for the specific problem of swap multicalibration in the affirmative, and the new algorithm that results in this upper bound uses the authors' pseudo notions effectively.\n\n**Clarity:** The paper itself is very well-written and the results are presented in a clear manner, with intuitive proof sketches and a logical flow to the sections. The provided diagram is helpful in understanding the big picture of the argument, and the authors do not waste space on more routine details. I had little trouble following along with the paper (though I am quite familiar with the multicalibration/omniprediction subfield, so others' mileage may vary).\n\n**Significance:** I believe that the results the authors provide are significant enough to warrant publication and answer an existing open question. The reduction to the pseudo notions also give us insight on a particular difficulty in multicalibration/related problems in regret minimization, particularly their swap variants. \n\n## Weaknesses\nThe weaknesses I see in the work are minor. \n\nThe first pertains to motivation: the authors might address is to possibly provide a bit more intuition on why these particular techniques result in the improved bounds -- although it seems clear to me that the improvements come from the reduction to the *pseudo* notions, a comparison to why the pseudo notions combined with their algorithm nets an improvement. \n\nAnother weakness one might argue that the results themselves are too narrow -- that the result for just the class of bounded linear functions doesn't achieve the scope of previous multicalibration results. I don't really see this as a big weakness, as the existing open question asked if a faster rate was possible even for bounded linear functions, and that was not known. Although it seems to me that more general function classes may need different techniques entirely (it is unclear to me how to extend dealing with the \"pseudo\" notions for more complex function classes), the technical contribution of the authors for bounded linear functions does add knowledge to the subfield, in my opinion.", "was_revised": true, "final_justification": "I keep my original positive score.", "rebuttal": "We sincerely thank the reviewer for their comments and time in evaluating our paper. Below, we provide responses to all your questions and comments.\n\n> Have these pseudo notions previously appeared in the literature? It seems that the argument hinges around the construction of these notions, and they do point towards a major difficulty in multicalibration-style regret bounds -- the conditioning on the $p_{t}$'s.\n\nTo the best of our knowledge, the work by Fishelson et al. [8] was the first to introduce the notion of pseudo swap regret (referred to in their paper as full swap regret) and pseudo calibration. Their motivation was to minimize the pseudo swap regret for a broad class of loss functions (e.g., strongly convex, Lipschitz) in the high-dimensional setting. Following up on their work, Luo et al. [7] considered online calibration of binary outcomes and proposed a new calibration measure called KL-Calibration (along with an accompanying notion pseudo KL-Calibration), which they showed is equivalent to the swap regret (resp. pseudo swap regret) of the log loss. As mentioned in the manuscript, our introduction of pseudo contextual swap regret and pseudo swap multicalibration is motivated from the above works.\n\nMoreover, pseudo notions have previously appeared in the literature in several other contexts. For example, a recent line of work on UCalibration (Kleinberg et al. [24], Luo et al. [25]) also considered (pseudo) U-Calibration, where the U-Calibration error ($\\text{UCal}$) for a family $\\mathcal{L}$ of loss functions is defined as $\\text{UCal} \\coloneqq \\mathbb{E}\\left[\\sup_{\\ell \\in \\mathcal{L}} \\text{Reg}^\\ell\\right]$, where $\\text{Reg}^\\ell$ represents the external regret incurred by the forecaster for a loss function $\\ell \\in \\mathcal{L}$, where as the pseudo U-Calibration error is defined as $\\text{PUCal} \\coloneqq \\sup_{\\ell \\in \\mathcal{L}} \\mathbb{E}\\left[\\text{Reg} ^ \\ell\\right]$. A similar notion of pseudo regret has also previously appeared in the literature on multi-armed bandits (ref. the book by Bubeck and Cesa-Bianchi).\n\nBubeck, S., & Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, 5(1), 1-122.\n\n> Is the bounded linear functional necessary in this argument because of the covering and reduction to \n (pseudo notions)? The argument seems specialized once we go to pseudo notions because of the ease of constructing a cover. To this note, would more general function classes need new techniques entirely?\n\nAs you pointed out, two crucial steps that invoke specific properties of the linear class are: (a) the existence of a cover , which allows us to bound $\\text{SMCal}$ for the linear class in terms of $\\text{SMCal}$ for the cover (in Lemma 2, we relate the latter to the pseudo swap multicalibration error $\\text{PSMCal}$ for the cover via the concentration bound in Lemma 1; the $\\mathcal{O}(N)$ term in Lemma 1 is needed to obtain $\\tilde{\\mathcal{O}}(T^{\\frac{1}{3}})$ style bounds); (b) an explicit algorithm (ONS) that minimizes the scaled external regret $$\\mathbb{E}\\left[\\sup_{f \\in \\mathcal{F}} \\sum_{t = 1} ^ {T} \\alpha_{t} (w_{t} - y_{t}) ^ {2} - \\alpha_{t}(f(x_{t}) - y_{t}) ^ {2}\\right]$$ against the linear class. For an arbitrary $\\mathcal{F}$ which is closed under affine transformations (we require the closure property for the reduction from (pseudo) swap multicalibration to (pseudo) contextual swap regret (Lemma 3)), we suspect that Rademacher complexity arguments for obtaining fast rates for online learning of the squared loss can be generalized for minimizing the scaled external regret in the display above. However, for an arbitrary $\\mathcal{F}$ which does not admit a finite cover, we are not aware of any techniques to generalize and prove an equivalent of Lemma 2. While it is certainly possible to derive an equivalent of Lemma 1 for an arbitrary $\\mathcal{F}$ using results from the theory of empirical processes (in particular, following the chaining technique in Block et al., we bound the deviation of a martingale difference sequence $Z_{1}, \\dots, Z_{T}$), we do not hope to retrieve the $\\mathcal{O}(N)$ term appearing in Lemma 1 since the proof of Lemma 1 heavily relies on controlling the variance of the associated martingale difference sequence via Freedman's inequality. We are not familiar with whether similar results that bound the expected deviation of the supremum of a martingale difference sequence with the variance exist. \n\nIn summary, following our framework, generalizing the $\\tilde{\\mathcal{O}}(T^{\\frac{1}{3}})$ bound for swap multicalibration for the linear class to an arbitrary $\\mathcal{F}$ seems quite convoluted and requires significant heavy lifting.\n\nBlock, A., Dagan, Y., \\& Rakhlin, A. (2021, July). Majorizing measures, sequential complexities, and online learning. In Conference on Learning Theory (pp. 587-590). PMLR.\n\n> I'm curious as to the efficiency compared to the previous algorithm of Garg et al? To my understanding, the Blum/Mansour reduction is efficient because it just employs external regret algorithms (where $N$ is from the rounding). Even a qualitative comparison of the \"efficiency\" compared to the previous algorithm would be interesting, just to note the algorithmic differences of the approaches.}\n\nFor minimizing the contextual swap regret of the squared loss against the linear class, the algorithm of Garg et al. invokes the reduction from swap regret to external regret as proposed by Ito [10] and Azoury and Warmuth's algorithm for minimizing external regret against the linear class. In contrast, for minimizing pseudo contextual swap regret, we utilize the Blum-Mansour reduction and the ONS algorithm for minimizing the scaled external regret against the linear class. Qualitatively, both the Blum-Mansour reduction and the reduction by Ito require fixed-point computations, and roughly speaking, the AW algorithm requires similar computation as ONS, thereby rendering our computation cost similar to that of Garg et al. Notably, both our algorithm and that of Garg et al. are efficient due to the efficiency of the subroutines that they invoke.\n \n However, Garg et al. achieve $\\tilde{\\mathcal{O}}(T^{\\frac{3}{4}})$ $\\ell_{2}$-swap multicalibration error, whereas we achieve $\\tilde{\\mathcal{O}}(T^{\\frac{1}{3}})$ $\\ell_{2}$-swap multicalibration error (we also achieve a superior dependence on the dimensionality $d$), which is orders of magnitude better. In a restricted setting  ($|\\mathcal{F}|$ is finite), Garg et al. also proposed an algorithm that achieves $\\tilde{\\mathcal{O}}(\\sqrt{T})$ $\\ell_{2}$-multicalibration error. However, the above algorithm is inefficient since it has running time proportional to $|\\mathcal{F}|$.\n\n Azoury, K. S., \\& Warmuth, M. K. (2001). Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine learning, 43(3), 211-246.\n\nWe hope that our responses answer your questions. Should you have any more questions, please feel free to reach out."}, {"review_id": "Cq6ylFOzaA", "reviewer": "Reviewer_v3FW", "summary": "This paper studies multicalibration and omniprediction problems in distributional and online settings. In the online setting, they show an $O(T^{1/3})$ $\\ell_2$-swap multicalibration error, resolving an open question posed by Garg et al. The algorithm, which is based on Blum-Mansour reduction, is extended to significantly improve error and sample complexity bounds on several related notions of contextual swap regrets, multicalibration and omniprediction errors.", "questions": "Please see the questions in the \"Strengths and Weaknesses\" section above.", "limitations": "Yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Disclaimer: I am not familiar with the topic of the paper.\n\n## Assessment: \nThis paper makes significant contribution in improving a large number of existing error and sample complexity bounds. In most cases, the improvements are orders of magnitude better than existing results (e.g. Theorem 1, Corollary 1 and Theorem 4).\n\nThe two new notions on pseudo-swap multicalibration and pseudo contextual swap regret, as well as the reduction from the former to the latter, seem fundamentally important as they ultimately lead to improved $\\ell_2$-swap multicalibration error. \n\nIn addition to novel ideas and improved bounds, it appears that the paper also introduce new analysis techniques as stated in line 134: \"By\nperforming a careful martingale analysis using Freedman’s inequality on a geometric partition of the interval [0, 1], we finally establish the desired concentration bound.\" However, this new martingale analysis is not made clear in the main text. \n\nIn terms of weaknesses, I do not find anything significant. For a theoretical paper with many upper bounds, it is beneficial to have a formal argument on the sort of lower bounds one can obtain. However, it is understandable that lower bound proofs might take an entirely different paper.\n\n## Questions:\n1. Can the authors clarify where the \"careful martingale analysis using Freedman’s inequality on a geometric partition of the interval [0, 1]\" is? I did look at Appendix D.1, but I cannot find any new technical lemma on this. Is this hidden in the proof of Lemma 9? In any cases, could you briefly describe the nature of this new analysis?\n2. I cannot find the discussion on the computational complexity of your algorithms. In particular, I am concerned whether or not your algorithms have to explicitly construct a cover in Proposition 1. \n3. How robust are your results with respect to the particular finite discretization of $[0,1]$ line 76? (This might be a stupid question as I am not familiar with this setting).\n4. While I suppose the paper is sufficiently clear for expert reviewers who are familiar with swap regret and multicalibration, some parts of it should be improved for better clarity so that even people outside of the domain can understand. For example, I am unable to grasp what $\\mathcal{P}_t$ in line 154 is. Where does it come from, for example is it something that the algorithm computes in time step $t$?\n5. Can you clarify what it means for $\\mathcal{P}_t$ to be deterministic?\n6. Similarly, Algorithm 1 is not self-contained as it is written. Are $p_{t,i}$ and $ALG_i$ input to Algorithm 1?", "was_revised": true, "final_justification": "I keep my original positive score (4) since the authors have adequately addressed my questions.", "rebuttal": "We sincerely thank the reviewer for their comments and time in evaluating our paper. Below, we respond to all your questions and comments.\n\n> For a theoretical paper with many upper bounds, it is beneficial to have a formal argument on the sort of lower bounds one can obtain. However, it is understandable that lower bound proofs might take an entirely different paper.\n\nRegarding lower bounds, we would like to mention that Appendix A does provide some lower bounds for online $\\ell_{1}, \\ell_{2}$-Calibration (particularly, $\\text{Cal}_1, \\text{Cal}_2$ as defined in lines 167-168). In summary, proving lower bounds for online calibration is a significantly challenging problem and obtaining the minimax bound is still open, with recent breakthroughs establishing that $\\tilde{\\Omega}(T^{0.54389}) \\le \\mathbb{E}[\\text{Cal}_1] \\le \\tilde{\\mathcal{O}}(T^{\\frac{2}{3} - \\varepsilon})$ (for a sufficiently small $\\varepsilon > 0$) and $\\tilde{\\Omega}(T^{0.08778}) \\le \\mathbb{E}[\\text{Cal}_2] \\le \\tilde{\\mathcal{O}}(T^{\\frac{1}{3}})$ (Dagan et al., Fishelson et al.). Based on the above results, we infer the following:\n\n(a) Since contextual learning is harder than the non-contextual variant, and for the squared loss, the non-contextual swap regret is equivalent to $\\text{Cal}_2$, the lower bound for $\\text{Cal}_2$ also applies to $\\text{SReg}$ (contextual swap regret).\n\n(b) Since (swap) multicalibration is stronger than calibration, the same lower bounds also apply to $\\text{MCal}, \\text{SMCal}$.\n\n(c) For swap omniprediction, Garg et al. proved that for a loss class that comprises of convex Lipschitz functions, against a hypothesis class $\\mathcal{F}$ that consists of the constant $0, 1$ functions, we have $\\Omega(\\mathbb{E}[\\text{Cal}_1]) \\le \\mathbb{E}[\\text{SOmni}]$.\n\n> Can the authors clarify where the \"careful martingale analysis using Freedman’s inequality on a geometric partition of the interval [0, 1]\" is? I did look at Appendix D.1, but I cannot find any new technical lemma on this. Is this hidden in the proof of Lemma 9? In any case, could you briefly describe the nature of this new analysis?\n\nYes, the analysis is hidden in the proof of Lemma 9. Recall that Freedman's inequality (Lemma 6; Line 604) states that for a martingale difference sequence $X_1, \\dots, X_T$, where $|X_t| \\le B$ for all $t \\in [T]$, we have $|\\sum_{t = 1} ^ {T} X_t| \\le \\mu V_X + \\frac{1}{\\mu} \\log \\frac{2}{\\delta}$ with probability at least $1 - \\delta$, where $V_X = \\sum_{t = 1} ^ {T} \\mathbb{E}_t[X_t ^ {2}]$, $\\mu \\in [0, \\frac{1}{B}]$ is a fixed constant, and $\\delta \\in (0, 1)$. When $V_X$ is a deterministic quantity, the upper bound in the display above can be minimized with respect to $\\mu \\in [0, \\frac{1}{B}]$; the optimal $\\mu^\\star = \\min\\left(\\frac{1}{B}, \\sqrt{\\frac{\\log \\frac{2}{\\delta}}{V_X}}\\right)$. However, when $V_X$ is random (which is indeed the case in Lemma 9), we cannot merely substitute $\\mu^\\star$ in the bound above since $\\mu^\\star$ is random. To circumvent this difficulty, we partition the feasible interval for $\\mu$ geometrically (e.g., when $B = 2$, we partition to intervals of the form $[\\frac{1}{2^{k + 1}}, \\frac{1}{2^{k}}]$), apply Freedman's inequality within each interval, and subsequently take a union bound. Notably, each interval corresponds to a condition on $V_X$ for which the optimal $\\mu$ falls within that interval, and for that interval substituting $\\mu = \\frac{1}{2^{k}}$ or $\\mu = \\frac{1}{2^{k + 1}}$ leads to only a lower-order blow-up in the quantity $\\mu V_X + \\frac{1}{\\mu} \\log \\frac{2}{\\delta}$ compared to substituting $\\mu^\\star$.\n\n> I cannot find the discussion on the computational complexity of your algorithms. In particular, I am concerned whether or not your algorithms have to explicitly construct a cover in Proposition 1.\n\nNo, our algorithm does not construct a cover $\\mathcal{C}_\\varepsilon$. We only utilize Proposition 1 in the analysis (particularly Lemma 2) in two ways: (a) the $\\mathcal{O}(Nd\\log \\frac{1}{\\varepsilon})$ term is due to the bound on the size of the cover; (b) we upper bound $\\text{PSMCal}$ for the cover by $\\text{PSMCal}$ for the linear class. As can be observed from (b) above, instead of minimizing the pseudo swap multicalibration error over the cover, we instead minimize it over the linear class (since the cover is chosen as a subset of the linear class (ref. Proposition 1)). Regarding the overall computation cost, our algorithm in Section 2.3 operates over the ball $4 \\cdot \\mathbb{B}_2^d$ and all our subroutines (BM reduction, ONS, Randomized rounding) can be implemented efficiently over the ball.\n\n> How robust are your results with respect to the particular finite discretization of $[0,1]$ line 76?\n\nThe question of robustness with regard to the discretization scheme is generally not considered in online calibration since almost always the uniform discretization scheme (which arguably is the simplest discretization) yields the desired result. However, depending on the curvature of the loss function, or the problem itself a non-uniform discretization scheme might be required, e.g., a non-uniform discretization ($z_i = \\sin ^ {2} \\frac{\\pi i}{2 N}$ for all $i = 1, \\dots, N - 1$) scheme was used in Luo et al (2025) to minimize the swap regret for the log loss.\n\nLuo, H., Senapati, S., \\& Sharan, V. (2025). Simultaneous swap regret minimization via kl-calibration. arXiv preprint arXiv:2502.16387.\n\n> While I suppose the paper is sufficiently clear for expert reviewers who are familiar with swap regret and multicalibration, some parts of it should be improved for better clarity so that even people outside of the domain can understand. For example, I am unable to grasp what $\\mathcal{P}_t$ in line 154 is. Where does it come from, for example, is it something that the algorithm computes in time step $t$?\n\nWe apologize for the lack of clarity for the more general audience, and this is something that we shall work on for the subsequent revisions. $\\mathcal{P}_t$ represents a probability distribution over the set $\\mathcal{Z} = \\{0, \\frac{1}{N}, \\dots, \\frac{N - 1}{N}, 1\\}$. The elements of $\\mathcal{Z}$ represent predictions $(p_t)$ that our algorithm makes. At each time $t \\in [T]$, our algorithm computes $\\mathcal{P}_t$ and predicts $p_t$ by sampling according to $\\mathcal{P}_t$, i.e., $p_t \\sim \\mathcal{P}_t$.\n\n> Can you clarify what it means for $\\mathcal{P}_t$ to be deterministic?\n\nRecall that $\\mathcal{P}_t$ represents a probability distribution over the set $\\mathcal{Z} = $ {$0, \\frac{1}{N}, \\dots, \\frac{N - 1}{N}, 1$}, i.e., $\\mathcal{P}_t \\in \\Delta(\\mathcal{Z})$, where we have used the notation $\\Delta(\\Omega)$ to represent the simplex over $\\Omega$. $\\mathcal{P}_t$ being deterministic means that the algorithm does not sample $\\mathcal{P}_t \\sim \\mathcal{D}$, where $\\mathcal{D} \\in \\Delta(\\Delta(\\mathcal{Z}))$. Note that this is not necessarily true for an adaptive adversary, since the adversary can include its own randomness and make $\\mathcal{P}_t$ random, despite of the algorithm not randomizing over $\\mathcal{P}_t$; however, since we consider an oblivious adversary throughout the paper, we can abide by the above interpretation.\n\n> Similarly, Algorithm 1 is not self-contained as it is written. Are $p_{t,i}$ and $ALG_i$ input to Algorithm 1?\n\nAlgorithm 1 invokes $ALG_i$ as a subroutine, and $p_{t,i}$ is an input to $ALG_i$ (therefore, Algorithm 1 as well). We apologize if things were not clear and shall work on revising in the subsequent versions.\n\nShould you have any more questions, do not hesitate to reach out. If our responses have addressed your concerns, we would be grateful if you would consider updating your assessment accordingly."}]

Author rebuttal:

Meta-review: This paper provides an algorithm and improved upper bounds for the problems of (swap) omniprediction and multicalibration in the online and (by an online-to-batch reduction) the offline batch settings. It has made several important theoretical contributions, including resolving an open problem in SODA and unifying calibration, swap regret, and omniprediction under a pseudo framework. Thus, I would recommend its acceptance with a spotlight.
Decision: Accept (spotlight)