Improved Bounds for Swap Multicalibration and Swap Omniprediction

We sincerely thank the reviewer for their comments and time in evaluating our paper. Below, we respond to all your questions and comments.

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.

Regarding 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:

(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).

(b) Since (swap) multicalibration is stronger than calibration, the same lower bounds also apply to $\text{MCal}, \text{SMCal}$.

(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}]$.

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?

Yes, 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$.

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.

No, 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.

How robust are your results with respect to the particular finite discretization of $[0,1]$ line 76?

The 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.

Luo, H., Senapati, S., & Sharan, V. (2025). Simultaneous swap regret minimization via kl-calibration. arXiv preprint arXiv:2502.16387.

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$?

We 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$.

Can you clarify what it means for $\mathcal{P}_t$ to be deterministic?

Recall 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.

Similarly, Algorithm 1 is not self-contained as it is written. Are $p_{t,i}$ and $ALG_i$ input to Algorithm 1?

Algorithm 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.

Should 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.

We sincerely thank the reviewer for their comments and time in evaluating our paper. Below, we provide responses to all your questions and comments.

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.

To 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.

Moreover, 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).

Bubeck, 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.

Is the bounded linear functional necessary in this argument because of the covering and reduction to (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?

As 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.

In 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.

Block, A., Dagan, Y., & Rakhlin, A. (2021, July). Majorizing measures, sequential complexities, and online learning. In Conference on Learning Theory (pp. 587-590). PMLR.

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.}

For 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.

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}|$.

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.

We hope that our responses answer your questions. Should you have any more questions, please feel free to reach out.

We sincerely thank the reviewer for their comments and time in evaluating our paper. Below, we provide responses to all your questions.

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?

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.

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]?

[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.

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?

Excellent 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.

Ito, S. (2020). A tight lower bound and efficient reduction for swap regret. Advances in Neural Information Processing Systems, 33, 18550-18559.

Dagan, 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).

We hope that our responses answer your questions. Should you have any more questions, please feel free to reach out.

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.

What does the notation $\mathbb{R}^{\mathcal{X}}$ mean? Is this the set of functions $\mathcal{X} \to \mathbb{R}$?

Yes, this is a standard notation used in set theory.

Are any lower bounds known for any of these problems? What about simplifications to known textbook-type problems?

Regarding 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:

(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).

(b) Since (swap) multicalibration is stronger than calibration, the same lower bounds also apply to $\text{MCal}, \text{SMCal}$.

(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}]$.

Regarding 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.

I'm unable to parse and the meaning of the definition in eq.(1). This needs some interpretation.

$\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.

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.

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.

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.

I especially did not understand the definition of multi-calibration.

We 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$.

Should 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.