Bridging Multicalibration and Out-of-distribution Generalization Beyond Covariate Shift
Authors: Jiayun Wu
Jiashuo Liu
Peng Cui
Steven Wu
Venue: NeurIPS 2024 poster (2024)
Keywords: Multicalibration
Robustness
Invariant Risk Minimization
Primary area: fairness
TL;DR: We extend the current definition of multicalibration to tackle general distribution shift, particularly beyond covariate shift.

Abstract: We establish a new model-agnostic optimization framework for out-of-distribution generalization via multicalibration, a criterion that ensures a predictor is calibrated across a family of overlapping groups. Multicalibration is shown to be associated with robustness of statistical inference under covariate shift. We further establish a link between multicalibration and robustness for prediction tasks both under and beyond covariate shift. We accomplish this by extending multicalibration to incorporate grouping functions that consider covariates and labels jointly. This leads to an equivalence of the extended multicalibration and invariance, an objective for robust learning in existence of concept shift. We show a linear structure of the grouping function class spanned by density ratios, resulting in a unifying framework for robust learning by designing specific grouping functions. We propose MC-Pseudolabel, a post-processing algorithm to achieve both extended multicalibration and out-of-distribution generalization. The algorithm, with lightweight hyperparameters and optimization through a series of supervised regression steps, achieves superior performance on real-world datasets with distribution shift.

Bridging Multicalibration and Out-of-distribution Generalization Beyond Covariate Shift
Jiayun Wu*
Jiasuuo Liu Depart. of Computer Science & Tech. Tsinghua University Beijing, China 100084
Depart. of Computer Science & Tech. Tsinghua University Beijing, China 100084
vujy228mails. tsinghua edu. cn
liuj mwuiiaaho7770mmal..ooo com
Peng Cui
Key Laboratory of Pervasive Computing, Ministry of Education Depart. of Computer Science & Tech., Tsinghua University Beijing, China 100084
cuip@tsinghua. edu. cn
Zhiwei Steven Wu School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 zhiweiwecs. cmu edu
Abstract
We establish new model-agnostic optimization framework for out-of-distribution generalization via multicalibration, a criterion that ensures predictor is calibrated across a family of overlapping groups. Multicalibration is shown to be associated with robustness of statistical inference under covariate shift. We further establish link between multicalibration and robustness for prediction tasks both under and beyond covariate shift. We accomplish this by extending multicalibration to incor- porate grouping functions that consider covariates and labels jointly. This leads to equivalence of the extended multicalibration and invariance, objective for robust learning in existence of concept shift. We show a linear structure the grouping function class spanned by density ratios, resulting in unifying frame- work for robust learning by designing specific grouping functions. We propose MC-Pseudolabel post-processing algorithm achieve both extended multical- ibration and out-of-distrio -f--triiitiiitionn generalization. The algorithm, with lightweight hyperparameters and optimization through series of supervised regression steps, achieves superior performance on real-world datasets with distribution shift.
Introduction
We revisit the problem of aut-of-distributin generalization and establish new connections with multi- calibration [17]. criterion originating from algorithmic fairness. Multicalibration is strengthening of calibration, which only requires predictor f to be correct on average within each level set:
E f(X) f(X) =
"This research conducted as part of visit to Carnegie Mellon University. Code available at:
com IC- http//M--PPeeuollabbll
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Calibration is a relatively weak property, as it can be satisfied even by the uninformative constant predictor f(X) = ] that predicts the average outcome. More broadly, calibration provides only a marginal guarantee that does not extend to sub-populations. Multicalibration [17] mitigates this issue by requiring the calibration to hold over a family of (overlapping) subgroups H: for all h E H.
E[(Y f(X)) ((X) | [(X)= -0
Multicalibration is initially studied as measure of subgroup fairness for boolean grouping functions h, with (X) = 1 indicating X is a member of group h [17]. Subsequently, Gopalan et al. [14] and Kim et al. [20] adopt broader class of real-valued grouping functions that can identify sub- populations through reweighting. The formulation of real-valued grouping function has enabled surprising connections between multicalibration and distribution shifts. Prior work [21 37l studied how distribution shift affects the measure of multicalibration, with a focus on covariate shift where the relationship between X and Y remains fixed. Kim et al. [2]] show that whenever the set of real- valued grouping functions H includes the density ratio between the source and target distributions, a multicalibrated predictor with respect the source remains calibrated in the shifted target distribution.
Our work substantially expands the connections between multicalibration and distribution shifts. At a high level, our results show that robust prediction under distribution shift can actually be facilitated by multicalibration. We extend the notion of multicalibration by incorporating grouping functions that simultaneously consider both covariates X and outcomes Y. This extension enables to go beyond covariate shift and account for concept shift, which is prevalent in practice due to spurious correlation, missing variables, confounding [31]
Our contributions. Based on the introduction of joint grouping functions, we establish new connec- tions between our extended multicalibration notion and algorithmic robustness in the general setting of outto--distribution generalization, where the target distribution to assess the model is different from the source distribution to learn the model.
We first revisit the setting of covariate shift and show multicalibration implies Bayes optimality under covariate shift, provided a sufficiently rich class of grouping functions. Then, in the setting of concept shifts, we show the equivalence of multicalibration and invariance (2] a learning objective to search for a Bayes optimal predictor E| (( under a representation over features ((X), even though E is different across target distributions. We show correspondence between an invariant representation (X) and multicalibrated predictor E|Y ( (X)). with grouping function class containing all density ratios of target distributions and the source distribution.
2. As part of our structural analysis of the new multicalibration concept, we investigate the maximal grouping function class that allows for nontrivial multicalibrated predictor. For traditional covariate- based grouping functions, the Bayes optimal predictor f(X) = | is always multicalibrated. which is no longer the case for joint grouping functions. We show the maximal grouping function class is a linear space spanned by the density ratio of the target distributions where the predictor is invariant. As structural characterization of distribution shift, this leads to an efficient parameterization of the grouping functions by linear combination of a spanning set of density ratios. The spanning set can be flexibly designed incorporates implicit assumptions of various methodologies for robust learning. including multi-enviromment learning 39 and hard sample learning (29]
3. We devise post-processing algorithm multicalibrate predictors and simultaneously producing invariant predictors. As a multicalibration algorithm, we prove its convergence under Gaussian distributions of data and certify multicalibration upon convergence. As robust learning algorithm, the procedure is plainly supervised regression with respect to models' hypothesis class and grouping function class, introducing an overhead of linear regression. This stands out from heavy optimiza- tion techniques for out-of- oo-diitributton generalization, such as bi-level optimization [12 30 and multi-objective learning 2 24), which typically involves high-order gradients [36]. The algo-
rithm introduces no extra hyperparameters. This simplifies model selection, which is a significant challenge for distiiiiuitttiiiiionn generalization since validation is unavailable where the model is deployed [15]. Under the standard model selection protocol of DomainBed [15), the algorithm achieves superior performance to existing methods in real-world datasets with concept shift, including
porverty estimation 44), personal income prediction [ and power consumption 32 33 prediction.
2

---

2 Multicalibration and Bayes Optimality under Covariate Shift
2.1 Multicalibration with Joint Grouping Functions
We consider prediction tasks where covariates are denoted by a random vector X E X and the target by Y E y. Lowercase z, y denote the specific values of these random variables. Predictors are defined as real-valued functions/ f X' + y. Our theoretical analysis focuses on the setting where y [0, 1]. In this context, we propose a new definition of lg approximate multicalibration with joint grouping functions.
Definition 2.1 (Multicalibration with Joint Grouping Functions). For probability measure P(X,Y Y) and predictor f. let H RxXy be a real-valued grouping function class. We say that f is a-approximately &2 multicalibrated w.r.l. H and P for all h E H:
K2 h, K=( ( (Ex
(P)())()) Sa.
(I)
P(cx(())=((-((0) the pushforward measure. We say f is a-approximately calibrated if includes the constant function h = 1. We say f is multicalibrated (calibrated) for = 0. If the grouping function is defined on X, which implies h(x,,)) 31) = h(x,, (2) for any x X and yı y2 E y. we abbreviate h(x,-) by h(x))
Our definition generalizes several notions of (mullt)ccaiibration in the literature by specific choices of grouping functions. For example, (2. P)) recovers the overall calibration error in the case of constant grouping function h 1. For boolean grouping functions defined on X [17, K2(f, h, P) computes the calibration error of the subgroup with h(z) = 1. For real-valued grouping functions defined on X [1 20.. (2 h, P) evaluates a reweighted calibration error, whose weights h(x) are proportional to the likelihood of sample belonging to the subgroup. Furthermore,
propose
extended domain of grouping functions defined on covariates and outcomes jointly, for which the Bayes optimal predictor [a may not be multicalibrated, in contrast to all existing multicalibration frameworks with X X-based grouping functions. Multicalibration with joint groupings thus implies a distinct learning objective from accuracy, which we will characterize as invariance in section 3
Example 2.2 (Multicalibration Does Not Imply Bayes Optimality). Consider covariates X X2) and an outcome Y generated by the following structural equations:
== YXx++0 +1.
X2 x2=Y+0
X1, E1, 62 are independent gaussian variables with zero mean, and variances E[e]] of and B[e]] ož. For a singleton grouping function class containing h(z, v) = y 22, the Bayes optimal predictor
D2 is not multicalibrated be- a² =o of
f(x) |[ oftoz + oftog
cause EEI(XX [(X))
oftoz + 0. However, g(x) Iı is multicalibrated since E[i(X, x(X)))((x)) -E(c2 =0
While the Bayes optimal predictor always multicalibrated for covariate based grouping functions, it may not be multicalibrated for grouping functions that depend the outcome. In fact, there may be no predictor that achieves multicalibration in such cases. For example, when we consider grouping function class that includes both h = 1 and h1x,, y) = y, multicalibrated predictor satisfies f(X) = E| [[(X) for h = 1, and [[{" = E|Y (())((())
(E[Y)s(X))) for h(x,)) y. This implies (ar[Y] = 0, which is impossible for regression with label noise. Therefore, we study the structure of the maximal grouping function class that allows for a multicalibrated predictor in section 4
Most importantly, multicalibration with joint grouping functions is useful for capturing more general distribution shifts. By interpreting multicalibration error as calibration error reweighted by grouping functions, quantifies the maximal calibration error for all subgroups associated with grouping functions in H. If grouping functions defined on X, only the covariate distribution P(X) distinguishes between subgroups. In contrast, the joint distribution P(X, Y) differentiates subgroups for joint grouping functions. We will discuss multicalibration with covariate-based grouping functions in the next sub-section and joint grouping functions in section
3

---

2.2 Multicalibration Implies Bayes Optimality under Covariate Shift
Settings of Out-of-distribution Generalization. We characterize distribution shift by an uncertainty set of absolutely continuous probability measures, denoted by P(X,, Y), where there is an accessible source measure Ps P and unknown target measure Pr E P. We use capital letters such as P to denote single probability measure and lowercase letters such as p to denote its probability density function. A predictor f is learned in the source distribution Ps and assessed in the target distribution Pr. Given loss function E. ) x ) - R, we evaluate the average risk of a predictor f w.r.t. a probability measure P. defined by Rf( == Ex((([(X), Y)). We focus on {(j. y) = (Ú y) in our theoretical analyses.
In this subsection we focus on grouping functions h(x)) defined on covariates. We will prove approximately multicalibrated predictors simultancous approaches Bayes optimality in each target distribution with covariate shift, bridging the results of Kim al. [2]] and (lobus-Harriss
al. [3.. To recap, Kim et al. [2]] studies multicalibration under covariate shift and shows that a multicalibrated predictor remains calibrated in target distribution for a sufficiently large grouping function class. Further, it is shown that multicalibration predictors remain multicalibrated under covariate shift [21 37 assuming the grouping function class H closed under some transformation by density ratios (Assumption 2.3 1). Second, Globus-Harris et al. [13] shows multicalibration implies Bayes optimal accuracy [3). assuming H. satisfies a weak learning condition (Assumption 2.3 2).
Detailed discussion on other related works is deferred to section A in the appendix.
Assumption 2.3 (Sufficiency of Grouping Function Class (informal, see Assumption
1. (Closure under Covariate Shift) For a set of probability measures P(X) containing the source measure (x(X), h E H implies p/ps- E H. for any density function p of distributions in P.
2. ((";, p)- Week Learning Condition) For any P E P(X)Ps(Y = (P' with the source measure XX), and every subset G X with P(X E G) > p. if the Bayes optimal predictor [ [ has lower risk than the constant predictor Ep E G] by margin there exists a predictor h H. that is also better than the constant predictor with the margin %
X): P' E
Theorem 2.4 (Risk Bound under Covariate Shift). For a source measure Ps Px(X, Y) and set of probability measures P(X) containing (X(X), given a predictor f x [0, 1] with finite range m == |Range(f)) consider a grouping function class H. closed under affine transformation and satisfying Assumption 2.3 with p == >//m. If 256m² 256m==aappone approximately Eg multicalibratte w.n. Ps and H1 = {h E H maxxex h(x)²² s 1). then any target measure Pr E ((X))ss((XX)
inf (r) [=:10
Rry (f*))++ +
(2)
Remark 2.5. Following prior work in multicalibration cardinality, which can be obtained by discretization.
13
37 J, we study functions f with finite
3 Multicalibration and Invariance under Concept Shift
Theorem 2.4 shows multicalibration implies Bayes optimal accuracy for target distributions under covariate shift. However, in practical scenarios, there are both marginal distribution shifts of covariates (X) and concept shift of the conditional distributions (). Concept shift especially prevalent in tabular data due to missing variables and confounding [31. In order to go beyond covariate shift, we will focus on grouping functions defined on covariates and outcomes jointly. We show that multicalibration notion w.r.t. joint grouping functions is equivalent to invariance, criterion for robust prediction under concept shift, Extending the robustness of multicalibration to general shift is non-trivial. The fundamental challenge is that there is no shared predictor that is generally optimal in each target distribution because the Bayes optimal predictor varies for different Y I|X distributions. As first step, we show multicalibrated predictors w.r.t. joint grouping functions are robust as they are optimal over any post-processing functions in each target distribution.
Theorem 3.1 (Risk Bound under Concept Shift). For a set of absolutely continuous probability measures P(X, Y) containing the source measure Ps(X, YY,)). consider a predictor f : + [0, 1]. Assume the grouping function class H. satisfies the following condition:
H ク h(x.v)
p(z,y) ps( v)
P P PEP(X,n)
(3)

---

f is a-approximmaeey &g multicalibrated w.E. H. and Ps. then for any measure P E P(X,Y),
Rp(f)
inf Rplg o +2 a:(0.1--0.11
The theorem shows an approximately multicalibrated predictor on the source almost cannot be improved by post-processing for each target distribution. To ensure such robustness, the grouping function class must include all density ratios between target and source measures, which are functions over X' x y. This characterization of robustness in terms of post-processing echoes with Invariant Risk Minimization (IRM) [2]. a paradigm for out-of-distribution generalization with Y Y|X shift. However, their analysis focuses on representation learning.
Definition 3.2 (Invariant Predictor). Consider data selected from multiple environments in the set & where the probability measure in an environment e is denoted by Po(X. Y). Denote the repre- sentation over covariates by measurable function functioon invariant predictor g" o Q across if there exists a function g" E EG == {g- suppp()) - [0, 1]} such that for all e 8:
((x). We say that 1b elicits a-approximately
Rp, (g" o b) S inf Rp, (g D) + gEG
(5)
Remark 3.3. (1) Predictors 9 take a representation T extracted from the covariates as input. For general predictor f(x) if we take ((z)= = f(x) and g² as an identity function, Equation 5 reduces to the form of Equation 4 Therefore, f in Equation 4 is a Da/aapprrxiimmtel invariant predictor across environments collected from the uncertainty set P. (2) We give an approximate definition of invariant predictors, which recovers the original definition (2] when a = In this case, there exists shared Bayes optimal predictor g" across environments, taking o as input. This implies E,, [| = Ee, (Y|B) almost surely for any 61, C2
IRM searches for representation such that the optimal predictors upon the representation invariant across environments. Motivated from causality, the interaction between outcomes and their causes also assumed invariant, IRM learns representation of causal variables for stable prediction. We extend Theorem 3.1 representation learning and prove equivalence between multicalibrated and invariant predictors.
Theorem 3.4 (Equivalence of Multicalibration and Invariance). Assume samples are drawn from an environment e E & with a prior Ps(e) such that Eees Ps(e) = 1 and Ps(e) > 0. The overall population satisfies Ps(X, Y) = Eees (X, Ps(e) where (x, YYiss is the cettoommntt-ppcccje absolutely continuous measure. With measurable function (xx), define a function class H as:
pa(x;, y) h(a. v) ps(x, y)
If there a bijection g" supp(()) + [0, 1] such that g" o a-approximately &g multicalibrated w.r.t. H and Ps. then t elicits an 2 aapaapproximaaell invariant predictor g" o & across E.
2. If there is g" >supp(D)
[0.1] 1] such that & elicits an a-approximatell invariant predictor g" & across 8, then g" o is /al Dapproxximately &2 multicalibrated w.r.. H and Ps. where
D = min.es Ps(e).
Remark 3.5. (1) In the first statement, assuming g" is a bijection avoids degenerate cases where & contains redundant information. For example, every predictor g" ((X) upon representation equals g* (T) o T(X) upon representation X. Confining g" to bijections ensures some unique decomposition into predictors and representations. (2) Wald et al. [41] proves equivalence between exact invariance and simultaneous calibration in each environment. We strengthen their result to show multicalibration on single source distribution suffices for invariance. Moreover our results can be directly extended beyond their multi-envine colliieenironment setting to a general uncertainty set of target distributions, by the mapping between grouping functions and density ratios. Further, our theorem established for both exact and approximate invariance.
The theorem bridges approximate multicalibration with approximate invariance for out-of-distriburt generalization beyond covariate shift. The equivalence property indicates that the density ratios of target and source distributions constitute the minimal grouping function class required for robust prediction in terms of invariance.
5

---

4 Structure of Grouping Function Classes
construct richer grouping function classes for stronger generalizability. However, fewer predictors are multicalibrated to a rich function class, and a multicalibrated predictor may not exist at all, as illustrated by the example in section 2.1 In this section, we first study the maximal grouping function class that is feasible for a multicalibrated predictor. Then, we will leverage our structural results inform the design of grouping functions.
Section B inspires
4.1 Maximal Grouping Function Space
We focus on continuous grouping functions defined on a compact set X y Rd+1 i.e. h e C(X x V), and consider absolutely continuous probability measures supported on X' x y' with continuous density functions. Our first proposition shows that the maximal grouping function class for any predictor is linear space.
Proposition 4.1 (Maximal Grouping Function Class). Given an absolutely continuous probability measure (s(X. Y) and predictor f X' + [0, 1}, define the maximal grouping function class that is multicalibrated with respect to:
Hj [h E C(X )): K2(1,,, Ps) = -}.
Then Hy is a linear space.
In the following, we further analyze the spanning set of maximal grouping function classes for nontrivial predictors which are at least calibrated.
Theorem 4.2 (Spanning Set). Consider an absolutely continuous probability measure Ps(X, Y) and
calibrated predictor X [0, 1]. Then its maximal grouping function class Hly is given by:
p v)
Rp(g Rp(go f)
Hy- span
p is continuous and Rp(f) a:(0.1]-(0.1]
inf
(8)
ps (2r, v)
predictor's maximal grouping function class is spanned by density ratios target distributions where the predictor is invariant. Correspondingly, Theorem 3.1 gives the minimal grouping function class, comprised of density ratios between target and source distributions, in order to ensure f(x) is an invariant predictor. In contrast, Theorem 4.2 states the maximal grouping function class for f() is exactly the linear space spanned by those density ratios. Next, we further investigate sub-structures of the maximal grouping function class. We focus on the representation learning setting of IRM.
Theorem 4.3 (Decomposition Grouping Function Space). Consider an absolutely continuous probubility measure Ps(X, Y) and a measurable function Φb IRd + Rdd with da E Zt, We define the Bayes optimal predictor over as fx(x) = Eps [x)). We abbreviate His with Hz. Then Minkowski sum of H1, H2.4.
Ha can be decomposed
p( M( y)
inf Rp(g R fa0) (0.1
H1,4 span
p continuous and Rp(fe)
(9)
ps(2,8) y)
p(=:| v)
H2.6 span
ps(x y) p continuous
(10)
1. If a predictor is multicalibrated with Hi,g, then Rp (J) < (fo)
2. fa is an invariant predictor elicited by 4 across a set of environments & where P. Ps( for any e E 6. If predictor f is multicalibrated with H2,4. then f is also an invariant predictor across & elicited by some representation.
Remark 4.4. Hi, and H2, contain functions defined on x, 4(x), y which can both be rewritten as functions on I. y by variable substitution. Thus, Hi, &i, H2, are still subspaces of grouping functions. Hi, is spanned by the density ratio of P( Y) where the Bayes optimal predictor over & must be invariant the distribution of P. H2.4 is spanned by general density ratio of P(X
Multicalibration w.r.t. H1.0 ensures at least the accuracy of the Bayes optimal predictor on Q and multicalibration w.r.t. H2.6 ensures at least the invariance of this predictor. However, we show in the following proposition that sizes of two subspaces are negatively correlated. When a variable selector, Hi, expands with more selected covariates while H2, shrinks. By choosing combination of Hi.o and H2,0, we strike a balance between accuracy and invariance of the multicalibrated predictor.

---

Proposition 4.5 MMonooniictty), Consider X E R which could be sliced as X = (Φ. V/ and = (A. Define Hi, == {h(((x)) E C(X x V)}. with 1 Hi H2, and Hi, are
similarly defined. We have:
1. 1.H1,x H1.0 +. J Hi, C H1 {C}.
2. [C] = H C H2 C H22 C H2.0-
C is a constant value function.
4.2 Design of Grouping Function Classes
The objective of a robust learning method can be represented by a tuple consisting of an assumption about the boundary of distribution shift and metric of robustness. Multicalibration is equivalent to invariance as metric of robustness, while the grouping function class provides a unifying view for assumptions over potential distribution shift. Given any uncertainty set of target distributions P. Theorem 4.2 implies an efficient and reasonable construction of grouping functions as linear combinations density ratios from P. We implement two designs of grouping functions for the learning setting with and without environment annotations respectively.
From Environments If samples are drawn from multiple environments and the environment annota- tions are available, we assume the uncertainty set as the union of each environment's 's distribution Pe. This completely recovers IRM's objective, but we approach with a different optimization technique in the next section. Taking pooled data as the source S, density ratios spanning the grouping function class are he (z. y) (x, y)/ ps (z. y) = ps(e),r, y) (e(),, where (e| y) is estimated by an environment classifier. Then grouping function can be represented as a linear combination of he:
h(z v)
Σ Xeps(elz,)). Ae ER. EE
(11)
From Hard Samples When data contains latent sub- populations without annotations, the uncertainty
set can be constructed by identifying sub-populations. Hard sample learning (27 28 29 suggests
the risk is an indicator for sub-population structures. Samples from the minority sub-population
M are more likely to have high risks. For example, JTT (2) identified the minority subgroup
using risk threshold of a trained predictor fia- We adopt continuous grouping by assuming
Ps(X, Y E M) x (Xi - Y)2. We construct the uncertainty set as the union of the source S and minority sub-population M, resulting in grouping function represented as:
h(z. 9) = AM (fia(z) y)² + As Aas, As R.
(12)
Another design utilizing Distributionally Robust Optimization's 's assumption 10] is in section B
5 MC-PseudoLabel: An Algorithm for Extended Multicalibration
In this section, introduce an algorithm for multicalibration with respect to joint grouping functions. Simultaneously, the algorithm also provides a new optimization paradigm for invariant prediction under distribution shift. The algorithm, called MC-PseudoLabel, post- post-processes a trained model by supervised learning with pscudolabels generated by grouping functions. As shown in Algorithm I given predictor function class F and dataset D with an empirical distribution PD(X, Y), regression oracle solves the optimization: AD(D) arg min R R (f). We take as input model fu. possibly trained by Empirical Risk Minimization. fu has finite range following conventions of prior work in multicalibration [3]. For continuous predictors, we discretize the model output and introduce a small rounding error (see section C.. For each iteration, the algorithm performs regression with grouping functions on each level set of the model. The prediction of grouping functions rectify the uncalibrated model and serves as pseudolabels for model updates.
Since we regress Y with grouping functions defined on Y, poor design of groupings violating Theorem 4.2 can produce trivial outputs. For example, if grouping functions contain h((,, y) = y. then ert eēr, never decreases and the algorithm outputs fo. because there does not exist a multicalibrated predictor. However. the algorithm certifies a multicalibrated output if converges.
Theorem 5.1 (Certified Multicalibration). In Algorithm 7 for a, B > 0, if jrrrr-1 eìr, < B. the output fi ( (x) is a-approximately l multicalibrated w.r.t. HB {h E H. : sup h(, y)² < B}.
7

---

Algorithm MC-PseudoLLabel
Require: A dataset (Da, Dy), a grouping function class H. predictive function class F.
I: t 4 0:
2: fo Initialization; (For example, models trained with ERM.)
3: m < Range(Diserettie(ffo))
4: repeat
5: fi - (f;; == arg w//mm [f(()) - e/:
6: err; = La.DDDDDD.f (x) y)²
7:
for each [1/m] do
8:
Dd +- (x)((x)
9:
(x, f- An(D)); (Regression on level sets with grouping functions.)
10:
end for
11:
f4114, v) + Evelti (((()==))) k, (Generate pseudolabels. } y)
12:
eîr+t1 + -eag--l/Jt
13:
D+11 t -Dzz f(t1((D))
f41(2)) [ (D (Update the model with pseudolabels.)
15:
1-(+1;
16:
until err+-1 - e stops decreasing.
Ensure: (1)(2))
MC-PseudoLabed reduces to LSBoost Globus-Hamn et [13] boosting algorithm for multicali- bration if H. only contains covariate- covariate-based grouping functions. In this case, Line 14 of Algorithm reduces to ft+1 (x) = fet1 :) where fe+1 does not depend on y. For joint grouping functions, since fe+1 E xx we project it to models' space of IR. by learning the model with fe+1 as pseudolabels. The projection substantially changes the optimization dynamics. LSBoost constantly decreases risks of models, due to Rp,, (fe+1) = Ryr,, (f++1) < Rp,, (ft). The projection step disrupts the monotonicity of risks, implying that MC-Pseudolabel can output predictor with a higher risk than input. This is because multicalibration with joint grouping functions implies balance between accuracy and invariance, as is discussed in Theorem 4.3 The convergence of LSBoost relies on the monotonicity of risks, which is not applicable to MC MC-Pseudolabel. We study the algorithm's 's convergence in the context of representation learning. Assume we are given a grouping function class H4 with a latent representation O. If predictor is multicalibrated w.r. H1 H2, & respectively, then it is also multicalibrated w.r.t. H4. Therefore, we separately study the convergence with two grouping function classes. In Proposition F.26, we show the convergence for subset of H1, consisting of covariate-baze based grouping functions, which a corollary of Globus Harris et al. result. As a greater challenge, derive convergence for H2.0 when data follows multivariate normal distributions.
Theorem 5.2 (Covergence for H2, (informal, see Theorem F.27 Consider X E IR with X
( V)z. Assume that ( V Y) follows multivariate normal distribution Na+ (v,, E) where the random variables are in general position such that E is positive definite. For any distribution D supported X x take the predictor class F = Rx and the grouping function class H. as a subset of H2 which is defined in Equation I0
H =h 1l:hh h H2 and h(z.v) c. x Gyy Cb, Co E Rd Cy. Cb E].
(13)
For an initial predictor fo(x) = E[Y]z], run MCC-Peudollabe((D (D, H)F) without rounding, then fa(x) converges pointwise to E[Y|0(x)) as + oc, with convergence rate of (M)))) where 0 S M(E) 1.
MC-Pseudolabel is also an optimization paradigm for invariance. Certified multicalibration in Theorem 5.1 also implies certified invariance. Furthermore, MC-Pseudolabel introduces no extra hyperparameters to tradeoff between risks and robustness. Both certified invariance and light- weighted hyperparameters simplify model selection, which challenging for out-distribution generalization because of unavailable validation data from target distributions [15] MC- MIC-Pseudll has light- weighted optimization consisting of a series of supervised regression. It introduces an overhead to Empirical Risk Minimization by performing regression on level sets. However, the extra burden is linear regression by designing the grouping function class as linear space. Furthermore, regression on different level sets can be parallelized. Computational complexity is further analyzed in section

---

Experiments
6.1 Settings
We benchmark MC-Pseudolabel on real-world regression datasets with distributional shift. We adopt two experimental settings. For the multi-enviroument setting, algorithms are provided with training data collected from multiple annotated environments. Thereafter, the trained model is assessed on new environments. For the single-enviromment setting, algorithms are trained on single source distribution. There could be latent sub-populations in training data, but environment annotations are unavailable. The trained model is assessed on target dataset with distribution shift from the source. The grouping function class is implemented according to Equation IT and Equation 12 for the multi-enviromment and single-enviromment setting respectively.
Datasets We experiment on PovertyMap 44 and ACSIncome (7 for the multi-environment setting, and VesselPoower (3 for the single-environment setting. As the only regression task in WILDS 23) a popular benchmark for in-the-wild distribution shift, PovertyMap performs poverty index estimation for different spatial regions by satellite images. Data are collected from both urban and rural regions, by which the environment is annotated. The test dataset also covers both environments, but is collected from different countries. The primary metric is Worst-U/R Pearson, the worst Pearson correlation of prediction between rural and urban regions. The other two datasets are tabular, where natural concept shift (Y|X shift) more common due to existence of missing variables and hidden confounders [3. ACSIncome 77] performs personal income prediction with data collected from US Census sources across different US states. The task is converted to binary classification by an income threshold, but we take raw data for regression. Environments are partitioned by different occupations with similar average income. VesselPower comes from Shifts 33], a benchmark focusing on regression tasks with real-world distributional shift. The objective is to predict power consumption of a merchant vessel given navigation and weather data. Data are sampled under different time and wind speeds, causing distribution shift between training and test data.
Baselines For the multi-envirrmment setting, baselines include ERM (Empirical Risk Minimization); methods for invariance learning which mostly adopts multi- objective optimization: IRM (2), MIP (24]. IB-IRM M. CLOvE {ЛЛ. MRI (18), REX (25,, Fishr [6];; an alignment-based method from
domain generalization: IDGM [39;; and Group DRO 38 Notably, CL.OvE learns calibrated predictor simultaneously on all environments, but is optimized by multi-ohjective learning with a differentiable regularizer for calibration. For the Enneeenvironmeen setting, baselines include reweighting based techniques: CVaR (26). JTT [29] Tilted- ERRM [27); a Distributionally Robust
43 Other methods are not included because specification in classification 445 46) or exposure to target distribution
Optimization method x²-DRO [3] and data augmentation method C-Mixup
data during training 19 22 target distribution.
For all experiments, we train an Oracle ERM with data sampled from
We implement the predictor with MLP for ACSIncome and VesselPower, and Resnet18-Me 1--MS [16 for PovertyMap. following WILDS default architecture. We follow DomainBed's protocol [5 for model selection. Specifically, we randomly sample 20 sets of hyperparameters for each method, containing both the training hyperparameters and extra hyperparameters from the robust learning algorithm. We select the best model across hyperparameters based on three model selection criteria, including in-distribution validation on the average of training data, worst-environment validation with the worst performance across training environments, and oracle validation target data. Oracle validation is not recommended by DomainBed, which suggests limited numbers of access to target data. The entire run is repeated with different seeds for three times to measure standard errors of performances. Specifically for PovertyMap, we perform 5-fold cross validation instead of three repeated experiments, following WILDS' setup.
Implementation
6.2 Results
Results are shown in Table for multi-environment settings and Table for single-enviromment settings. MC-Pseudolabel achieves superior performance in all datasets with in-distribution and worst-environment validation which does not violate test data. For oracle validation, MC- Pseudolabel achieves comparable performances to the best method. For example, CLOVE, which also learns invariance by calibration, achieves best performance under oracle valida- tion in PovertyMap, but it sharply degrades when target validation data is unavailable. It's

---

Table 1: Results on multi-environment datasets, evaluated on test data using three model selection criteria. ID: validation with averaged performance on training data. Worst: validation with the worst performance across training environments. Oracle: validation with performance on sampled test set.
ACSIncome: RMSE
PovertyMap: Worst-U/R Pearson
Method
ID
Worst
Oracle
ID
Worst
Oracle
ERM
0.487
0.487=00000
0.452
0.48
0.4820.00
0.49
IRM
0.166:#0.002
0.166=0.00z
0.465500.00
0.38=a.07
0.39= 0G
0.45=00.08
MIP
0..57=0.000
0.15-1=0.02
0.45440.001
0.40=z0.0
0.39=0.10
0.4320.08
IB-IRM
0.463 003
0.463==0.08
0.438-+0.00 008
0.39
0.37=0.00
0.43:0.06
CLOVE
0.455 0.000
0.454=000002
0.450 005
0.46
0.42=00.13
0.51=t0.08
MRI
0.458 00.01
0.418
0.4455+0..0m
0.47 40.0
0.46:
0.49
REX
0.466
0.16-1=0.001
0.4558+0.000
0. 0.43=
0.42##0.00
0.45==0.00
Fishr
00000
0.115==0.112
0.45000.000
0.422=0.09
0.41 00.1
0.43+0.08
IDGM
1. 10,01
1.84320.00
10.011
0.02:10.07
0.01
0.13
GroupDRO
0,481 0.003
0.017
0.433
0..8
0.37
0.42
MC- Pac
0. 1.428:am 00000
0 0.425
0.41 10.011
0. 4.50
0.50=0.06
0.50=0.00
Oracle ERM
0.332
0.71
ERM
C-Mixup
MC-Pseudolabel
12
10
Test RMSE
R=50.5
R-
R-
ID Validation RMSE
Figure 1: Accuracy-on-the-ling beyond covariate shift: correlation between models' in-distribution and out-of outtrf-distribution risks on VesselPower.
because CLOvE tunes its regularizer's coefficient to tradeoff with ERM risk, whose opti-
mal value depends on the target distribution shift. In contrast, MC-Pseudolabel exhibits an advantage with in-distribution model selection. This is further supported by Figure 6.2
which shows that MC-Pseudolabed 's out-of-distrine of-diitriibutionn er- rors strongly correlates with in-distribution errors. The ex- periment spans across different hyperparameters and seeds with the same model architecture on VesselPowwrr. The phenomenon, known accuracy-on-thee -neeee-iieee (34,, is well known for a general class of models under covariate shift. However, Liu et al. [3 shows accuracy-on-the-llee not exist under concept shift, which is the case for ERM and C-Mixup. This introduces significant challenge for model selection. However, MC-Pseudolabel recovers the accuracy to the line.
Table 2: Single-enviromment results.
VesselPower: RMSE J
Method
ID
Oracle
does
ERM
1.9210.23
1.8610
CVaR
1.6910.18
1.49
JTT
1.75.1..2
1.5810.15
Tilted-ERM
1.7240.21
1.61:0.112
X D-RO
1.6944.20
1.5610.06
C-Mixup
1.72:1..1
1.5610.08
MCCPseudolabel
1.611.0.20
1.5210.16
7 Conclusion
Oracle ERM
1.18
To conclude, we establish new optimization framework for out-of-distribution generalization joint grouping functions. While the current algorithm focuses on regression, there is potential for particularly in terms of classification.
through extended multicalibration with
future work to extend our approach to general forms of tasks,
10

---

Acknowledgments and Disclosure of Funding
Peng Cui is supported in part by National Natural Science Foundation of China (No. 62425206. 62141607).
References
[1] Kartik Ahuja. Ethan Caballero, Dinghuai Zhang, Chan-Chisttpphe Gagnon-Audet, Yoshua Bengio, loannis Mitliagkas, and Irina Rish. Invariance principle meets information bot- tleneck for out-of-distriuution generalization. In Mare' Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang. and Jennifer Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems 34; Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 3438-3450, 2021. URL
neur httptppps.cpppppe/2/////aaaaae html
[2] Martín Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk mini- mization. CoRR, abs/1907 .02993, 2019. URL http:/tta/aiiii.orgggggee/// http//bb/19900 0wt.//077700093333
[3] Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. A unifying theory of distance from calibration. Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1727-1740. ACM, 2023. doi: 10.1145/35622463355518 URL
https://doi org/10. 1144/3564226635851122
[4] Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. When does optimizing proper loss yield calibration? In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neu- ral Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16. 2023, 2023. URL http://paperr. ct.ps..c//ppppeee filesfiiee///eee 10apee_f.1ee//pppr2222//aaaa /ppssr/2022//ash/ e4 MMBDeefrouass100200FF1111001 wtw.:ecfff11----btaaaaaaaae ConerraaattCooofeenceeeee html
[5] Elliot Creager, Jörn-Henrik Jacobsen, and Richard S. Zemel. Environment inference for invariant learning. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International
Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 2189-2200. PMLR, 2021. URLhtty //proceedings. mlr. press/ vvtss/v1////////// htt///1199///eeee cww.gereaaa.... html
[6] Zhun Deng, Cynthia Dwork, and Linjun Zhang. Happymap: generalized multicalibration method. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Con- ference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251
of LIPlcs, pages 41:1 11::23 Schloss Dagstuhl Leibniz- für Informatik, 2023, doi: 10. 1230LIPICSS.TCS..023....
URLhttps: //oii org/ 10. 4230/LIPICS ITCS. 2023 41
[7] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. In Marc' Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 6478-6490, 2021. URL h/tpop/t///////ppoaaaaaann nwwr cttpraape....p///ppr/////2 220aper/2022/hahh 35644416632277/accaa334646633333
[8] John C. Duchi and Hongscok Namkoong, Variance-based regularization with convex objectives. http:///gggggg//////////////////
J. Mach. Learn. Res., 20:68: 16:6:::-68:55, 2019. URL httt::////jmm1 ottgppappre//20/177775
html
[9] John C Duchi and Hongscok Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 1378):1378 2021.
[10] John C Duchi, Tatsunori Hashimoto, and Hongseok Namkoong. Distributionally robust losses against mixture covariate shifts. Under review, 2(1), 2019.
[11] John C. Duchi, Peter W. Glynn, and Hongseok Namkoong- Statistics of robust optimization: generalized empirical likelihood approach. Math. Oper. Res., 46(3):446-99)) 969, 2021. doi:
10. N0.1287/M0RR.2200.00 1085. URLhttpp https :/ //doi org/ 1287 2020..088.
11

---

[12] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnosee meta-learning for fast adapta- tion of deep networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICMI. 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1126-1135. mll. prwps/eesssspp. v70 minin.nn......... htmml
PMLR, 2017. http:/ttt:p//ceee/tieie
[13] Ira Globus-Harris, Declan Harrison, Michael Kearns, Aaron Roth, and Jessica Sorrell. Mul- ticalibration as boosting for regression. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Confer- ence on Machine Learning, ICML. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 11459-11444 11492. PMLR, 2023. URL https://prooceedings .mr.r.g..........mm..........ae. mlr. press/ v202/ 1::02//llbbue Alobusshaarris2 htmllmmml
[14] Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredictors. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31- February 3. 2022, Berkeley, CA, USA, volume 215 of LIPlcs, pages 79:1-79:21. Schloss Dagstuhl 4230/LIPICS ITCS. 20222.9. httpttss: org/ 11.1:1...4221111 4230/LIPICS ITCS. 2022.02222 79.
für Informatik, 2022. doi: 10.
[15] Ishaan Gulrajani and David Lopez-Paz. In search lost domain generalization. 9th Interna- tional Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OvenRevie 2021. URL BttLhttss///ppnrreeee
[16] Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEFE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 770-778. IEEE Computer Society, 2016. doi: 10.1 109/CVPR.2016.090 URL htt.htttt///oo.....
10. 1109/CVPR.. 2tA.0///VVRR.......... 2016.90
[17] Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Multi- calibration: Calibration for the (computationnlly--denffffii
masses. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässsan Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research. pages 1944-1953. PMLR, 2018. URL .ttml
http:://proceedings. mlr. wwmmm.rrreee wwwppprsssssos. wwwa////ebeetooosoooeeeeeeeeeeee
[18) Dongsung Huh and Avinash Baidya. The missing invariance principle found the re- ciprocal twin of invariant risk minimization. In Sanmi Koyejo, S. Mohamed, A. Agar- wal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Infor- mation Processing Systems 35: Annual Conference on Neural Information Process- ing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 Decem- ber 9, 2022, 2022. URL http::/papers nips. cc/ paper farrlsfiee//eele wwwrrrffleeeeeeeeeeeeeeereeeeeee pappp//222222 2022/ / 20b66222200811e00662244dddd33333 Abstratttee---ttttt----------- Conference. html
[19] Badr Youbi Idrissi, Martín Arjovsky, Mohammad Pezeshki, and David Lopez-Paz. Simple data balancing achieves competitive worst-group-accuracy. In Bernhard Schölkopf, Caroline Uhler, and Kun Zhang, editors, 1st Conference on Causal Learning and Reasoning, CLeaR 2022, Sequoia Conference Center, Eureka, CA, USA, 11-13 April, 2022, volume 177 of Proceedings of Machine Learning Research, pages 336-351 PMLR, 2022. httpt:::/trooeeeddiiit mlr. (rress/1777dddrsss222 html
[20] Michael P. Kim, Amirata Ghorbani, and James Y. Zou. Multiaccuracy: Black-box post- processing for fairness in classification. In Vincent Conitzer, Gillian K. Hadfield, and Shannon Vallor, editors, Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society,
AIES 2019, Honolulu, HI, USA, January 27-28, 2019, pages 247-254. ACM, 2019. doi: 0t55//3306611.3312220 URL / 10. 1....1165 1145/3306618 33144277
[21] Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold. Universal adaptability: Target-independent inference that competes with propensity scoring. Proceedings of the National Academy of Sciences, 1 19(4))e2108007113 19, 2022.
[22] Polina Kirichenko, Pavel Izmailov, and Andrew Gordon Wilson. Last layer re-training is sufficient for robustness to spurious correlations. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
htL.sttps: http::::////eeeeiieeeee n pet//pdfiid vdffiddzbbccAA-Fa
[23] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga Richard Lanas Phillips, Irena Gao, Tony Lee,
12

---

Etienne David, Ian Stavness, Wei Guo, Berton Earnshaw, Imran S. Haque, Sara M. Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. WILDS: A benchmark of in-the-wild distribution shifts. In Marina Meila and Tong Zhang. editors, Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18- 24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages html
5637-5664. PMLR, 2021. HtRL/tttp//ppoceeeeeee
mlr, ptwps/v13//eeeeee.
[24] Masanori Koyama and Shoichiro Yamaguchi. When invariance useful in an out-of-distribution generalization problem? arXiv preprint arXiv:2008, 01883, 2020.
[25] David Krueger, Ethan Caballero, Jörn-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Rémi Le Priol, and Aaron C. Courville. -ustrf-distributtin generalization via risk extrapolation (rex). In Marina Meila and Tong Zhang, editors, Proceedings of the 38th Interna- tional Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume PMLR, 2021. URL
139 of Proceedings of Machine Learning Research, pages htmll http:// http:://proceedings. mlr. www.srresssviiieee wwtpe/eeeee/eeeeeeeeeeeeeeeeeeee http///v/vvveeeeeea..aaaa
[26] Daniel Levy, Yair Carmon, John C. Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS
2020, December 6-12, 2020, virtual, 2020. URL. https: httpps:/pproceeddiiiiiee http://ppccceen..ceeee/ee mersssnnuuippe seurips.co paper/
Aabssract.htmm
[27] Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimiza- tion. In 9th International Conference on Learning Representationss ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL bttpss://openrevieet wwwp:eewwwwwwwweeeeeeeeeeeeeeeee net/forum? 1d=K5YasHZZT30
[28] Tsung- Yi Lin, Priya Goyal, Ross B. Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. IEEE Trans. Pattern Anal. Mach. Intell., 42(2):318-322 2020. doi: 10.1 1011///AA..210..2855555
htt.shtps://doi. org 10. 1109/ TPMMI. 2018. 2858826
[29] Evan Zheran Liu, Behzad Haghgoo, Annie S. Chen, Aditi Raghunathan, Pang Wei Koh, Shiori Sagawa, Percy Liang, and Chelsea Finn. Just train twice: Improving group robustness without training group information. In Marina Meila and Tong Zhang. editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 6781-6792. PMLR, 2021. mlr. press/ http//v19911///// hhmml
[30] Jiashuo Liu, Jiayun Wu, Bo Li, and Peng Cui. Distributionally robust optimization with data geometry. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Anmual Conference on Neural Information Processing Systems 2022, NeurIPS 2022. New Orleans, LA, USA, November 28 December 9, 2022 2022. URL http:://papert htt///aa359999111155255555e5 dd59933222dd999999 http://255994aa002222e2222222222 wwwptraattttttooeeeaaeaaeeeeeeee oet.eeaeeeee.a.eeeeeeeeeaeeeeeee .html
wwwp.cccppppppppppoeoccpp wttpcccppppppeeeeeeeee files/paper/2022
[31] Jiashuo Liu, Tianyu Wang, Peng Cui, and Hongseok Namkoong. On the need for a language describing distribution shifts: Illustrations on tabular datasets. In Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023.
[32] Andrey Malinin, Neil Band, Yarin Gal, Mark J. F. Gales, Alexander Ganshin, German Ches- nokov, Alexey Noskov, Andrey Ploskonosov, Liudmila Prokhorenkova, Ivan Provilkov, Vatsal Raina, Vyas Raina, Denis Roginskiy. Mariya Shmatova, Panagiotis Tigas, and Boris Yangel. Shifts: A dataset of real distributional shift across multiple large-scale tasks. In Joaquin Van- schoren and Kii-Kit Yeung, editors, Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual, 2021. URL httptp/ss//aattsttt--oamccceeeee wtwp://awaann-spoeeeceeeeeeeeeee wwwppppioeeee.....ooo..... heurips... cc/ html
[33] Andrey Malinin, Andreas Athanasopoulos, Muhamed Barakovic, Meritxell Bach Cuadra, Mark
J. F. Gales, Cristina Granziera, Mara Graziani, Nikolay Kartashev, Konstantinos Kyriakopoulos, Po-Jui Lu, Nataliia Molchanova, Antonis Nikitakis, Vatsal Raina, Francesco La Rosa, Eli Sivena, Vasileios Tsarsitalidis, Efi Tsompopoulou, and Elena Volf. Shifts 2.0: Extending the dataset of real distributional shifts. CoRR, abs/2206. 15407, 2022. doi: 10.48550//RXIV.22000 15077. httpstts::/// https://dooi org/ 10. 48550/ arxiv 2206 15407
13

---

[34] John Miller, Rohan Taori, Aditi Raghunathan, Shiori Sagawa, Pang Wei Koh, Vaishaal Shankar, Percy Liang. Yair Carmon, and Ludwig Schmidt. Accuracy on the line: on the strong cor- relation between out-of- distrii-ittiitto and in-distribution generalization. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML. 202 I 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 7721-7735 PMLR, 2021. URL http::/t///rrccceiingg mlr. presa/v139/ mtt.
miller21b html
[35] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[36] Alexandre Ramé, Corentin Dancette, and Matthieu Cord. Fishr: Invariant gradient variances for cutrof-distribution generalization. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Ma- chine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 18347-18377. PMLR, 2022. URL
nttps://prooeediings mlr press/v162/ramm22222 html
[37] Aaron Roth. Uncertain: Modern topics in uncertainty estimation, 2022.
[38] Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust
neural networks. In International Conference on Learning Representations, 2019.
[39] Yuge Shi, Jeffrey Seely, Philip HS Torr, N Siddharth, Awni Hannun, Nicolas Usunier, and Gabriel Synnaeve. Gradient matching for domain generalization. arXiv preprint
arXiv:2104. 099377 2021.
[40] Aman Sinha, Hongscok Namkoong, and John C. Duchi. Certifying some distributional robust- ness with principled adversarial training. In 6th International Conference on Learning Repre- sentations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Pro- ceedings. OpenReview.ner, 2018. URL.https: beattps://pperreviii opwnrevieeeeeeeeeeoeeeeeee nwt/tfruum? Soorrmmmi-HHe66pg22...
[41] Yoav Wald, Amir Feder, Daniel Greenfeld, and Uri Shalit. On calibration and out-of-domain generalization. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 22 2215-2227, 2021. URL https: //pp://einn/ceeenggs.mmm .eerr www. ips.cc/ http//hahhh11hhoe TTt.:/58000...1111..222266666660
Awstrftttsstccctt.cm html
[42] Haoxiang Wang, Bo Li, and Han Zhao. Understanding gradual domain adaptation: Improved analysis, optimal path and beyond. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Ma- chine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Reseurch, pages 22784-22801. PMLR, 2022. URL https://proceedings mlr prressvv62//e wang222 22mllmlmlmmmmmmmmm
[43] Huaxiu Yao, Yiping Wang, Linjun Zhang, James Y. Zou, and Chelsea Finn. C- mixup: Improving generalization in regression. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural In- formation Processing Systems 35: Anmual Conference
Neural Information Process- ing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 Decem- www.:nippscccc.... wwtpccccpppppeeeeeee files/ wttps//eepeeeeeee/////22 ppppp/pp22//aaa////// waw.ba/ooo--sstttttt---------- Con.eraatt--ooofeeeeeee html
ber 9, 2022, 2022. URL
[44] Christopher Yeh, Anthony Perez, Anne Driscoll, George Azzari, Zhongyi Tang, David Lobell, Stefano Ermon, and Marshall Burke. Using publicly available satellite imagery and deep learning to understand economic well-being in africa. Nature Communications, 2020.
[45] Hongyi Zhang. Moustapha Cissé, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018 URL ptlljtttps://opereviii
net/Forum?IddrIDdpp1BB
[46] Michael Zhang, Nimit S Sohoni, Hongyang R Zhang, Chelsea Fino, and Christopher Re. Correct-n-contrast: a contrastive approach for improving robustness to spurious correlations. In International Conference on Machine Learning, pages 26484-26516, PMLR, 2022.
14

---

A Related Work
Multicalibration Multicalibration is first proposed by Hébert-Johnson et al. 17 with binary grouping functions. Kim et al. [20] and Gopalan et al. [14) extend the grouping functions to real- valued functions. Hiobus-Harrrs et al. [33 shows that with a sufficiently rich class of real-valued et al. al.o provides a boosting algorithm for both regression and multicalibration. The connection between multicalibration and distribution shift is first studied by Kim et al. (21). who proves that & multicalibration error remains under covariate shift, given a sufficiently large real-valued grouping function class. Kim et al. further shows that under covariate shift, multicalibrated predictor can perform statistical inference of the average outcome of a sample batch. In contrast, we derive a robustness result for individual prediction of outcomes for & multicalibrated predictors. In addition, Wald et al. 41 studies the equivalence of Invariant Risk Minimization and simultancous calibration on each environment. Our equivalence results for multicalibration can be perceived Wald et al. results beyond the ratios and grouping functions. We also extend the equivalence to approximately multicalibrated and approximately invariant predictors. Furthermore, we move beyond Wald et al. multi-objective optimization with Lagrangian regularization, by proposing new post-processing optimization framework consisting of a series of supervised regression. Meanwhile, Blasiok et al. [4] discusses connections between calibration and post-processing which is an equivalent expression of invariance. There are other extensions of multicalibration, such as Deng et al. [6] who generalize the term Y - f(X) in multicalibration's 's definition to a class of general functions. While our work is the first to generalize the grouping functions h to consider the outcomes.
grouping functions, multicalibration actually implies accuracy. Globus-
generalization of setting, by deriving a mapping between density
Dutti--distribution Generalization Beyond Covariate Shift Despite abundant literature from domain generalization that focuses on image classification where covariate shift dominates, research on algorithmic robustness regression tasks beyond covariate shift is relatively limited. The setting can be categorized according to if the source distribution is partitioned into several environments. For the multi-environment generalization setting, Invariant Risk Minimization and its variants assume that outcomes are generated by a common causal structural equation across all environments, and aims to recover such an invariant (or causal) predictor [1 2 18 24 25 36). Group DRO (38) is simple but surprisingly strong technique that optimizes for the worst group risk with reweighting of environments. There are also meta-leariing methods 122 that handles multi-environment generalization with bi-level optimization. For the single environment setting, Distributionally Robust Optimization optimizes for the worst-case risk in an uncertainty set of distributions centering around the source distribution g 9 26) Another branch of research is targeted at mitigating spurious correlation with an assumption of simplicity bias, which utilizes a simple model discover latent sub-populations retraining on subgroup- or perform Invariant Risk Minimization discovered subgroups [5]. Data augmentation is prevalent technique to enhance algorithmic robustness for vision tasks. Quite a lot of these methods are tailored for classification. For example, Mixup 45) interpolates between features of samples with the same label. The approach is extended to regression settings by C-Mixup [43. Pseudolabelling is a common technique for out-of distriibbiittnonnn generalization, but typically adopted in setting with exposure to unlabelled samples from target distribution, known as domain adaptation [42). However, MC-Pseudolabel generate pseudolabels for the source distribution itself.
and then correct the biased predictor by sample reweighting [27
28 29
balanced dataset or small batch from target distribution [19 22
B Grouping Functions for Distributionally Robust Optimization
Distributionally Robust Optimization assumes the target distribution to reside in an uncertainty set P of distributions centering around the source distribution Ps. For example, Duchi et al. (10) formulates the uncertainty set as arbitrary subgroups that has a proportion of at least ag E (0, 1). Duchi et al. only consider subgroups of covariates:
P(X) (P(X): there exists a probability measure P'(X),
(14)
Ps(X) aP + (1 a)) ao..
(15)
15

---

By the correspondence between density ratios and grouping functions, the equivalent design of grouping function class given by:
H =={nERt hER :0 h()) axp
var
(16)
We can also extend the grouping functions consider both covariates and outcomes, such that general subgroups are incorporated into the uncertainty set:
{ h h R : = h(,, S Va,
H =
(17)
In the case of grouping functions defined on i and y jointly, the grouping function class not closed under affine transformation and is not a linear space spanned by density ratios, which suggests that
perfectly multicalibrated solution might not exist. However, approximately multicalibrated predictors can still be pursued.
C Model Discretization
For continuous predictors, we take a preprocessing step to discretize the model to as many bins as possible such that the rounding error negligible while still ensuring enough samples in individual bins. Specifically, we equally split the outcomes of predictors to bins with equal intervals from the minimum maximum of model output. We start from a minimum bin number keeps increasing m as long as 90% of the samples reside in a bin with at least 30 samples. When the criterion is violated, stop increasing m and select it as the final bin number. The model discretization procedure is fixed across all experiments.
10, and
D Computational Complexity
We assume that the predictor's outcomes are uniformly distributed. Denote the average bin size by Nr. which is constant around 30 in our implementation. The bin number is given by N/N, where N the sample size. For neural networks, N represents the batch size. The overhead of MC-Pseudolabel compared to Empirical Risk Minimization is linear regression on each bin, whose sample complexity is ((V)) with OLS. Please note that an individual linear regression for around 30 samples is extremely cheap. A non- non-parallel implementation of regression every bin scales linearly with the bin number m, so the overall complexity is O(N However, since the regression on adopt multi-processing implementation. Denote the number of jobs by J, the overall time cost of MC-Pseudolabel is ONNN//J. As a comparison, OLS on samples has a computational complexity of (NN)..
each bin is independent,
In conclusion, the complexity of MC-Pseudolabel scales linearly with sample size (or batch size for neural networks). Counterintuitively, increasing the bin number m (and thus decreasing the bin size) actually decreases the computational complexity. This is because linear regression scales cubically with sample size, so decreasing the sample size each bin is preferred to decreasing the bin number.
E
Experiments
E.1 An Additional Experiment: Synthetic Dataset
We start from multi-environment synthetic dataset with multivariate normal distribution cor- responding to Theorem 5.2 In this experiment, we examine the optimization dynamics of MC- Pseudolabel. The data generation process is inspired by Arjovsky et al. (2]. The covariates can be sliced into X (S, V with S E IR" and V e IR, where S is the causal variable for Y and V is the spurious variable. The data is generated by the following structural equations:
S NNO,
(18)
Y agS +ey, as = (1,.,,,, E RR,,er ((0,0.5)
(19)
V = (v Y + ar( = 1.25, ay (e2) = 0.75, ov (er) -1,cv ~ ~1(000.13)
(20)
16

---

The covariate V is spuriously correlated with Y because the coefficient (v depends on the specific environment We (E) 1.25, 0.75 respectively for two training environments while ay extrapolates to -1 during testing. A robust algorithm is supposed to bypass the spurious variable and output a predictor f(X) = a order to survive the test distribution where the correlation between V and Y is negated.
The predictor class for this dataset is linear models, and the environment classifier implemented by MLP with a single hidden layer. In this experiment, we fix the training hyperparameters for the base linear model, and perform grid search over the extra hyperparameter introduced by robust learning methods. Baselines except for ERM and Group DRO share a hyperparameter which the regularizer's coefficient, and Group DRO introduces temperature hyperparameter. We search over their hyperparameter space and report RMSE metric on the test set in Figure Most baselines exhibit U-turn with an increasing hyperparameter, and the minimum point varies across methods. The sensitivity of hyperparameters implies the dependence on strong model selection criterion, such as oracle model selection on target distribution. However, the dashed line for MC-PPeedolabells error langent to all the U-turns of baselines, indicating competitive performance of MC-Pseudolabel both with and without oracle model selection.
2.5
2.0
RMSE
10
10
10"
10
102
Hyperparameter (Log Scale)
MC-Pseudolabel
Fishr
GroupDRO
REX
MRI
IRM
CLOVE
IDGM
MIP
IB-IRM
ERM
Figure 2: Results (RMSE) on the synthetic dataset. Curves show method performances across hyperparameters. Methods without extra hyperparameters are marked with dotted lines.
We also investigate the evolution of pseudo labels ft in Algorithm to recover the dynamics of MC- Pseudolabel. The first row of Figure (auuee3dene demonsttatss how pseudolabelling results in multicalibrated predictor. It shows that pseudolabels for two environments deviate from model prediction at Step 0, but the gap quickly converges at Step 4, implying multicalibrated prediction. The second row provides insight about how pseudolabelling contributes to an invariant predictor. We observe that curve of two environments are gradually merging because pseudolabel introduces a special noise to the original label such that the correlation between the pseudolabel and spurious variable V weakened. As a result, the predictor will depend on the causal variable S which is relatively more strongly correlated with pseudolabels.
E.2 VesselPower
In figure we provide the correlation between models' in-distribution validation performance and out-of-distributiio test performance across all methods.
17

---

Step=0
Step=2
Step=4
3
alpha_v v 1.25
2
alpha_v v
Pseudo Labels
1
-7
-2
-2
-3
2
2
Model Prediction
Model Prediction
Model Prediction
alpha_v v
Pseudo Labels
alpha = 0.75
1
0
0
-3
-270
-2
0 V values
-2
2
2
V values
values
Figure 3: Evolution of pseudolabels during MC-Pseudolabel. The first row plots values of pseudola- bels against model predictions. The second row plots values of pseudolabels against V. Columns represent different snapshots during optimization.
E.3 Training Details
Datasets. In the ACSInome dataset, we focus on predicting personal income for California residents across four occupation fields: science professions (SCI), protective services (PRT), education (EDU), and military (MIL). While average incomes are similar across these fields, the correlation between income and usual hours worked per week (WKHP) varies significantly, as shown in Table This spurious correlation between income and WKHP introduces a concept shift across occupations. Therefore, train the model on environments comprising the SCI, PRT, and EDU occupations and evaluate it on MIL.
Table 3: Statistics of ACSIncome (California)
SCI
PRT
EDU
MIL.
Average Income ($10K)
4.8
4.6
4.5
4.5
Pearsonr (Income, WKHP)
0.38
0.51
0.59
-0.30
We follow the standard setup for PovertyMap specified in the WILDS benchmark 23) natural spatial distribution shift occurs between data collected from urban and rural regions, both of which are represented in the training and test sets. However, the test data is sourced from different countries than the training data. The primary evaluation metric is the worst Pearson correlation between predictions in urban and rural environments.
We use the synthetic split of VesselPower where the target power labels are generated through the simulation of physics model based on read data input features. The dataset include single environment training set, a dev-in set for in-distribution validation, and a dev-out set for evaluation. Distribution shifts arise due to variation in time and wind speeds. We report RMSE of prediction in megawatts (MW), rather than the kilowatts (KW) as used in the dataset's original paper [3].
Model Selction. We follow DomainBed's protocol 15 for model selection. Specifically, we randomly sample 20 sets hyperparameters for each method, containing both the training hyperpa- rameters of base models in Table 4 and extra hyperparameters from the robust learning algorithm
18

---

ERM
Tilted ERM
JTT
8 0.50
~000000
8000.66
C-Mixup
-DO
CVaR
14
10
12
Test RMSE
R² 0.67
0
0.62
PCe-uuuuuolabl
2-
R0
ID Validation RMSE
Figure 4: Correlation between models' in-distribution and dittr--disttibbttin risks on Powse.
in Table We select the best model across hyperparameters based on three model selection cri- teria. In-distribution (ID) validation selects the model with the best metric on the average of an in-distribution validation dataset, which is sampled from the same distribution as the training data. Worst-environment (Worst) validation selects the best model by the worst performance across all environments in the in in-distribution validation dataset. Worst validation is applicable only to the cellimeenvrromentt setting. Oracle validation selects the best model by an citt-f--distibutiin val- idation dataset sampled from the target distribution of test data. Oracle validation leaks the test distribution, so it is not recommended by DomainBed. However, most robust learning methods relies on out-of-distie dif--fffittrbbution validation, so Domainbed suggests limited numbers of access to target data when using Oracle validation. Though MC-Pseudolabel already performs well under III and Worst validation, we still report its performance under Oracle validation to compare the limit of robust learning methods regardless of model selection.
Following DomainBed, the entire model selection procedure is repeated with different seeds for three times to measure standard errors of performances. Thus, have totally 60 runs per method per dataset. Specifically for PovertyMap. we follow WILDS' setup [23] and perform 5-fold cross validation instead of three repeated experiments. For each fold of the dataset, we conduct the model selection procedure four times across three seeds, summing up to total of 12 experiments. And we report the average and standard error of performances across folds. Thus, the standard error measures both the difficulty disparity across folds and the model's 's instability.
Grouping Functions.
The grouping function class of MC-Pseudolabel is implemented according to Equation I and Equation for the multi-environment and single-enviromment setting respectively. For the multi-environment setting, the environment classifier p(ela (z., y) is implemented as MLP with
19

---

single hidden layer of size 100 for tabular datasets including Simulation and ACSIncome. For PovertyMap, the environment classifier implemented by Resnet18 with the same architecture as the predictor, except that the label y is fed into the last fully-connected layer. For the single- environment setting of VesselPower, the identification model fia is implemented as a Ridge regression model.
Table 4: Hyperparameters for model architecture.
Simulation
ACSIncome
VesselPower
Poverty
Architecture
Linear
MLP
MLP
8-
Hidden Layer Dimensions
None Adam
16 Adam 0
32, Adam 0 MSB
Standard 23
Optimizer
Adam
Weight Decay
0
0
Loss
MSE
MSE
MSE
Learning Rate
0.1
10 10Umioom|-33--
10 U0 33
0.001
Batch Size
1024
[256, 512, 1024, 2048]
[256, 512, 1024, 2048]
64'
The learning rate and batch size for training ResNet follow the setup of WILDS 25
Table 5: Hyperparameters for robust learning methods.
Range
Regularizer Coefficient
Uniioonm 332]
7) (GroupDRO)
10 Uniformm (33.2 3.2]
(JTT)
[0.1, 0.2, 0.5, 0.7]
A (JTT)
[5, 10, 20, 50]
7) (x2 -DRO)
[0.2, 0.5, 1, 1.5]
t (Tilted-ERe)
[0.1, 0.5, 5, 10, 50, 100, 200] 1, 1.5,
a (C-Mixup)
(C-Mixup)
[0.01, 0.1, 10, 100]
E.4
Software and Hardware
Our experiments based on the architecture of PyTorch (35]. Each experiment with single set of hyperparameters is run on one NVIDIA GefFrce RTX 3090 with 24GB of memory, taking at most 15 minutes.
F
Theory
F1 Multicalibration and Bayes Optimality under Covariate Shift
Assumption F.1 (Restatement of Assumption 2.3
1. (Closure under Covariate Shift) For a set of probability measures P(X) containing the source measure (x(
YPEP,EEH p(-)
h(-) E H. ps(-)
(21)
2. ((T), p)-Weak Learning Condition) For any P E (XX)))(()X)== = (P' X): P' P)
with the source conditional measure Px(Y(X) and every measurable sei G C X satisfying P(X E
G)> p. if
E G =
(22)
then there exists h E H satisfying
Ep[(h(X) -Y)1X E G E=([E))1XX Eq 7
(23)
20

---

Lemma F.2 (Globus-Ho Caauus-arrrieee et al. [33.. and any class of real valued functions H. that closed under affine transformation. Let:
Fix any distribution P P(X,Y), any model f : X - [0, 11.
Hi = (h E H: max ZEA
hx)² 1
be the set of functions in H upper-bounded by on X. Let m [Range(f)), O, and & 16m Then if H satisfies the (7, m) )-wek learning condition and f is a-approximately &2 multicalibrated with respect to H1 and P. then f has squared evror
Epl(f(z) - v) S Bx((f((x) - -) +3%
where f EE)
Definition F.3. For probability measure P(X.Y Y) and a predictor f: - 10, 11, let H C xxy be a function class. We say that f is a-approximately l multicalibrated w.r.t H and if for all
h E H:
Ki(,h,
(24)
/ Ep
= u] (d))
(25)
5
(26)
Lemma F.4 Roth (37). Suppose Ps, PT E have the same conditional label distribution, and
suppose J is a-approximately & multicalibrated with respect to Ps and H. If satisfis Equation 27 then J is also a-approximately l multicalibraated with respect to Pr and H::
Lemma F.S. For a predictor f X max,ex.yey h(zz, v)² B where B > 0,
[0,1] and grouping function h satisfying
KK VK2(f.h,P).
(27)
VB
Remark F.6. The lemma is extended from Roth (37y's result for B 1.
Proof. First we prove K2(S, h P) (J, h, P). For any [0, 1].
EE [MX, r))s(X) = w]
2
(28)
EP [I(X)(Y v)] = wi| Ep [h(X,
=
(29)
E (b(x,Y))ff(x)) = E [Y - u) f(x)
(30)
Ep [x(X, M) - -)) = -
(31)
- VBB B Ep
-
= w]
(32)
Equation 30 follows from the Cauchy-Schwarz inequality.
EE () = =1))
K2(J, h. P)
E < S
(33)
v~P
E PxP)
Ep (XX =0]
(34)
(F,K,
(35)
Then we prove K1,Sh,, P) S BB2(J.. h, Pj. Still from the Cauchy-Schwazz inequality:
Ki
E
Ep (X) r|
(36)
P~P
E
[12] E UNP
Er [A(X, ()(()=))(())))
(37)
-K,,J, P).
(38)
21

---

Theorem F.7 (Restatement of Theorem 2.4 For a source measure Ps(X,Y) Y) and a set of prob- ability measures P(X) containing Ps(X), given a predictor f X [0,1] with finite range m := |Range(f)), consider a grouping function class H closed under affine transformation sat- isfying Assumption 2.3 with - 7/m. If f 256m approximattl En multicalibrated w.r. Ps and His bounded subset Hi == {h E H: maxxex h(x)² I {1}, then for any target measure Pr E (XX)),
Rf) S (f* +3,
(39)
where (*(x) - Ep,, [x]] is the optimal regression function in each target distribution.
Proof. For |b(z)) and f E 10, according to Lemma ES
K2(f, S Ki(S,h, S ().
(40)
Since K2(f,h, Ps) S 256m²
for any h H1,
73
Kr h, Ps) S 16m
(41)
With Lemma F.4 for any E H1 and Pr E P. we have
7
Ki(f, h. Pr) <
(42)
16m
Again, it follows from Lemma E5 that:
33
K2(f.h, S
(43)
16m
With Lemma F22
we have
E [[(2)) - u) - Bpy ((f - u) 37:
(44)
which completes the proof.
0
F.2
Multicalibration and Invariance under Concept Shift
Theorem E8 (Restatement of Theorem 3.1 For set of absolutely continuous probability measures
P(X, Y) containing the source measure Ps Ps(X, Y), consider a predictor J - + [0, 1). Assume the
grouping function class H. satisfies the following condition:
H. (Ml.,)) p(z.8)
PEP(X,Y)
(45)
u)
If f is a-approximately l multicalibrated w.n.t. H and Ps. then for any measure P PE P(X,Y),
Rp(f) S inf Rp(g o f) +2Va.
(46)
[:0011|-0.11
Proof. For any h(,, y) p(z, w)/ps(z, v) where
Pe P. since f is a-approximately & multicali-
brated, Ke(f, h, Ps) S a. It follows from Lemma F.5 that Ki Ps) S Va.
Kj h, Ps) = / Er, VY - (()))))))))))))))))))))))))))))) u] dPs(s-
(47)
/ I p(z,y) (y ( v)s v)d(2, w) ps(
() (P)(f-1(w)
(48)
/ / dP (v)) (y - uplayy o)d(a,)) dPs(f-'()))
(49)
dPs(f-1(o)
= / dPs(f-((t))
(v)) / /O
o)d(z,)) dPs(F-1())
(50)
/ Ep (y-osf(x) o) (P(()
(51)
P).
(52)
22

---

Thus, we have (, S va for any PET P. We will prove an equivalent form of & calibration
error:
/ (()))p [V - -xs(x) = =0 d (1)
P)
sup -:(0.1)-[-1.11
(53)
sup - Eyln(f(2))
(54)
--0011)-(1111
Ki (fff,1,P) (0..-.0.)-- EpIn(f(X))( - f(())) can be proved by taking (70) = 21 >
0) - 1. On the other hand,
(U))Ep ( dP (U)
/ |n(o Ep [Y -() - w] wo]]dPpp (dP(())()) (55)
(56)
Actually the right hand side of Equation 53 resembles smooth calibration [3] which restricts
Lipschitz functions. Based on smooth calibration, Blasioo al. [4] shows that approximately
calibrated predictors cannot be improved much by post-processing. In the above we present a similar proof for ε calibration error.
For any E [0, 1].
[0, 1] + [0, 1]. there exists 7j :00 1] + [-1,1] such that g(u) = v + m7()) for any
Rr(g o f) = Er (r f(X) (((())))
(57)
Ep [Y 1 f(X)) 2Ep (Y ((X))(((X)) + Ep [n(((X)))
(58)
2 Rp(f) [110111--1111
sup
-
(59)
= =Rr(s) - -2,1(
(60)
2 Rr(s) - 2/a.
(61)
Theorem F9 (Restatement of Theorem 3.4). Assume samples are drawn from an environment
E with a prior Ps(e) such that Lese Ps(e) = 1 and Ps(e) > O. The overall population satisfies Ps(X.Y)= = Eess Yc( where Ye is the cesironment-specctee absolutely
continuous measure. For a representation T E (X) over features, define a function class H as:
H. = h(z.v) = Pe(x, v)
ps(x, E 8
(62)
1. If there exists bijection g" supp D) + [0, 1] such that g" + is a-approximately l multicali- brated wrt. H. and Ps, then for any 6,
R (g" 1)
inf Rr. (g o 1) 2
(63)
grupp( () -
2. For & (X). if there exists g* ()) [0, 1] such that Equation 63 is satisfied for any E 6, then g" 4 is /2/Da /4-aapaoximmmtety &g multicalibrated w.r.t H and Ps. where
D = minegg Ps(e).
Proof. We first prove statement 1.
For any g (
() + [o, 1], since 9" is a bijection, o +- - ">0""~>)('" b) where g g"g""""" [0, 11.01)) Since 9" + is a a-approximately &, multicalibrated, it follows from Theorem F.8 that for any 8,
Rp (g' o b) < Rr. ((g ")00" o b)) + 2
(64)
= =Rp, (g o 4) + 22a..
(65)
Then we give a proof of statement 2, which is inspired by Blasiok et al.
23

---

For simplicity let fr = g" Q.
For any e E & and any [0.1] - 1-1, 11, define
== Ep, 1(Y - (X)) (X))
[-1,1]. Construct k(v) projoo.j( (2 + Bn(v)), where
proj.o.1(+) = max min (1, ....
(n(())) = Ep
(Y ((((())))
(66)
I Ep. (Y -- (x)((
(67)
Ep. [Y - ((X)) - 2,3 + (
(68)
- Rp. (f*) 2,3² +
(69)
= Rp. (f)) BB
(70)
Rearranging the inequality above gives:
(Frr. [( (*
= (r Rr. (n(())).
(71)
Since o g" supp( - [0, 1], it follows from Equation 63 that:
Rr. (f*) Rr. (x((²)) Rr. (g" +) Rr. (Noog)) o S 2V
(72)
Combining Equation 71 and Equation
72 gives Ep. [(Y (XX-((X))(XX) S 1/01/11 for any
7: [0 [-1, 1]. From Equation 53 it follows that:
Ki(J,,1,P)
sup 11.11
Ep (X))
2/4
(73)
From Equation
52 Ki(F", h, Ps) 124 for any h H. Further, for any h H,
Mxx,0) v) (r(x, y)
(74)
ps(x, y)
(I
(75)
EveSPo (2, Ps
Pe(I,
(76)
(77)
D
By Lemma
F.5
it follows that K2(f" h, Ps) & V1/D- K,
Ps) V2/Da
F.3 Structure of Grouping Function Classes
In this subsection, we focus on Euclidean space where X' C Rdd is compact and measurable for some E = and y [0, 1]. Grouping functions are assumed to be continuous, i.e., E C(x x Y). We consider absolutely continuous probability measures with continuous density functions.
Proposition F.10 (Restatement of Proposition 4.1 Consider an absolutely continuous probability
measure (x, Y) and predictor f : X [0, II, define the maximal grouping function class that f is multicalibrated with respect to:
H, = {h E C(X' x x): K2(f,,, Ps) = -}-
(78)
Then Hy is linear space.
Particularly for fo(x) (xx)) where +b Rdd Red do 7 is measurable function, we abbreviate Hys with He. Then any finite subset G C Ho implies span(1, C Ho. where
denotes constant function.
24

---

Proof. For any 71, E IR and any h1, h2 E Hy, 714 + 22 E C(2 )))
Ki Ki(f, nhu + 7222, Ps) = / | [x + -x = dPs(s (v))
(79)
w)]f(x) = oa / E =|
dPs(f [dP
(80)
E (X V) - (x) = o) - (P)(1-((v))
(81)
mi Ki (J, /1 Ps) Ki ( Ps)
(82)
0.
(83)
According to Lemma
F55
Kg (J, h Ps) 0 is equivalent K2 h, Ps) 0 for bounded h. Thus, which implies h1 + 72h2 E H.y. Now we finishes the proof that H.
(2, 71 + 7222
Ps)
a linear space.
For (x) = E (x)).
[x)]
= [X) = [[[[][(([]]]]( = [X]
(84)
(85)
(86)
-Xx(X).
(87)
Thus, K2(fe, Ps)s = 0 which implies 1 E H4. Since Hy is linear space, & Hg implies span [} C H4.
Lemma F11. For any absolutely continuous probability measure P(X.Y) with continuous density function p, and any grouping function h E C(X x y), there exists Y & O and R such that yt + C(X x X),, and it is density ratio between some absolutely continuous probability measure P' and P, i.e., d. (P'(x,)) = (7)((ær,)) v) + p)) U), where P' also has a continuous density function.
Proof. Since h is bounded, there exists o' E R such that h(x, 9) + p > for any x X, y V. Define:
1 7- = J(h(I,)) v) + D (d),v))
(88)
D
(89)
[(h(I,)) +' pd)dP(z.)))
7h + p is still continuous.
We have 71(z,)) v) + p = ((((2,)) +p)) for any x E N, e y.
/ dd / (zl((z,))) p)dP(z.)))
(90)
= 7 (M(2,)) + +ddP((..))) = 1.
(91)
(92)
Thus, ('X Y) is an absolutely continuous probability measure. Its density function p' (7h + p)p is continuous.
Theorem F.12. Consider an absolutely continuous probability measure Ps(X, and a predictor
fo(x) = (Y,(Y((( where TR - RR do E 7 is a measurable function. We abbreviate
His with H4-
Ho {h E C(X' )): Covp, M(X,Y), /I5o of 0 for almost every E [0,
(93)
((I,)) EppY [.4] = Eps [Y] almost surely, p is continuous
span
(94)
(g)
25

---

Proof. First we prove:
No = (h E C(X x y) Covrs [ 8) = v] = for almost every u E 1].
(95)
For each v E [0, 1] and any h E C(X }),
Eps ((XXY) u/ = [] -Eps ((X,)) f4 = v Eps (((X fo = L
-Bps (xX, fw =
(96)
(97)
- Eps
|(X,, 8) fo B =
(98)
Covps [k(X, Y), 11/0 = m)
(99)
Equation 98 follows from Equation 87
For any h E C(X x )), h E He + K2(fb. Ps) =0
(100)
/ (EPs [h(X, - ) dPs(ft'(v) (v))
(101)
+ Ers [h(X, Y) - -v)(so = = 0 for almost every E [0, 1]
(102)
* Covps [h Y), fIf = = 0 for almost every eE [0, 1].
(103)
Next, we prove
p(x,)) ps(2,y) y)
Hg J span
Ep Eps [+] almost surely, p continuous
(104)
This is equivalent to saying that for any absolutely continuous probability measure satisfying [p[Y|fa = Eps [Y] Ifa] almost surely, Cov ()X = v] = 0 for almost every E 10.
p(X,Y) Y 1110-
CoNPs
(105)
Ps(X.V)
P(X,Y) r 1 Eps
pss Y) 16 = Ers (r|so o]
((X,Y)
Ers
(106)
= /
d.P(f (v)) p(2, y fo = v)
(fs(ST (v)) (I( f/5x w) y. dPs( = v)
(107)
-Eps Y L = -0] dP (v)) ulfo u)
= dP dds = v)
(108)
dPs(fo (v)
Ep | J = u] dP (v)) Eps Y y = dP (v))
(109)
(J (w))
dPs(JT (v)
dP (w)) dPs (v))
Ep Y fo u| Eps (Y f -0
(110)
0 almost surely.
(111)
Next, we prove
p(r, u) p2( y)
Ho span
Er[(([a) = Epp (V]Jo) almost surely, p is continuous
(112)
By Lemma F.11 any grouping function h E Ho could be rewritten as l( v) >>((,, y) w)/pss(s (a, v) p for some continuous density functions p and 7 o Thus, we just need to prove the statement that
26

---

Covps (hpp(XX)//pe //ps((X P,Y f4 = r] = =0 implies Ep|Y = v] = Ep, ff =v]
X)
Co
(Y + + fo
(113)
p(X,Y) Y 5050 + ppps (v 10 =
=>BPs
(114)
Ps(
-yErs
Ps(X, f4
p(X, Y)
EPs Y fo o) - pEpss ( fo =0
(115)
->Bps
(s 150 EEs
Y)
Ps(X, Y) 10 v Eps (r 10 [
p(x,
(116)
=>Covrs
PssXX 8110 = r)
P(X,Y)
(117)
(P(TT'(u) (u)
=> Ep Y fo 1) -Eps [x| 01
[BP
(118)
dfs (v))
Equation 118 follows from Equation
110 Ps hyp /))ps((X.)) + p, ft u
So we have Ep Ep(Y = =] = Ers = v]
O.
Corollary F13 (Restatement of Theorem 4.2 measure (s(X, Y) and calibrated predictor f.
Consider absolutely continuous probability
y {h e C(Xx)x Covps [h(X, Y), Ylf u] for almost every {00,1]
(119)
p(ar,y) v) (T,
span
Ep Y []] = Ers [Y] almost surely, p continuous
(120)
Remark F.14. [ [] = E. [V] almost surely implies [y(( J, which is equivalent as Rr(s) = inf (0.10] Rr(g f), since we adopt square error.
Proof. Since f is calibrated, we have Ep, [Y] = f. Take ((x) = fzz).
fa(x) = Erg (x)) Er, [VI[(=)) = f(x).
(121)
Apply Theorem F.12 and the proof is complete.
Theorem F.15 (Restatement of Theorem 4.3 (first part)). Consider an absolutely continuous proba-
bility measure Ps(X, Y) and predictor To Ey, [Y[((z) where T Rdd - Rdo da E Z is
measurable function. H4 can be decomposed as H4 H1, 4 + H2.4.
H1,4 (h E C(X )) Covps (1( f v] 0 for almost every v E [0, 1} (122)
p(D,y) y)
span
ps (2, v) Ep|Y fal Eps Y [f almost surely, p is continuous
(123)
H2.4 = {h E C(X x )) E[h(X, 2) Y| = Cj. 4 Y}
(124)
p(x T y)
=span (ps v.))
is continuous
(125)
Remark F.16. H1.D contains functions defined on supp( ()) x y which can be rewritten functions on X x y by variable substitution. Thus, Hi,0 still set of grouping functions. For H2 Cn is constant depending on h.
Proof. First we prove Ho C Hi + H2.0.
27

---

For any hy E H1,0 and h2 E H2,0,
Covrs [h1 Y) + (2(X, Y,,,,1 fo =
(126)
=Covrs [0, Y), fa = Covps
u
(127)
Covps [h2(X, Y), =
(128)
Erg (h2(X,Y)Yl =o] -Epy (X, v] Er, fo oj
(129)
Eps
[Epy ())( Y1
o| Eps Epy (X, f4 = Epp Y v]
(130)
Epp
[Erg (12 0) /| r|yl = -Eps Epg 112 (x, Ml = Epp Y
v]
(131)
= =b2 ( = Che Eps [o = v]
(132)
=0.
(133)
Next prove Ho C H1, + H22
For any h E Hg, let
hi (1(((x),)) Ep (xx 8(x), - v]
(134)
h2(2, = 112,, v) - X), =0x), = =y]-
(135)
Then we have
Covps
u| (,, f) = = - Eps (1, = Epg f u
(136)
=Ep,
=
(137)
=Eps
[Erg x)) = o] - Ers
= =] Ers
f = u]
(138)
Eps (MX,Y))\ff = - -n [h(X, - = = Ers 1 2)
(139)
Covps [h(X, f =]
(140)
=0 -0 for almost every E [0, 1].
(141)
Thus, h (9xx),)) E H1.0.
Epg 12222 Y) | = Eps () Ep, (h E Y|
Φ
(142)
=Er, ( Y) Φ Y] Ep, (), Y1
(143)
= 0.
(144)
Thus, 12(x, y) E H2,0. Following a similar proof of Theorem F.12
we have
v)
H1,4 span
( Ep [f almost surely, is continuous
(145)
(
Next, we prove H2. C span [p(x 2 v) h <.,) p continuous).
This is equivalent saying that p(: o w)/pp((s(()))) p,y)
H2o for any continuous density function p.
, Ps(X Φb Y)
Φ, /
2
Eps
ps(x dPs(a)(,
(146)
dP(x/
(147)
(148)
Thus, we have p(x/0; (x y) E H2.0.
Next, we prove H2 C span {p(x|4, p)/ps(>)/p))))) (
continuous].
By Lemma F.1 any grouping function h H2.5 could be rewritten as ha v)
Tp(a, ()/ps,))PP,,... + p for some continuous density function p and y + O. Thus, we just need to p/ Y Cb, implies p(X, ())s(XX)))
prove the statement that (x,((X
28

---

p (X)
p(X,))
p(X 11 Y) p(
Eps
Ps(XXY) + + 2, = =Eps
+ D.
(149)
ps X o Y) ps( Y)
p(
p Y)
Rps
$ ",, +
(150)
Y)
PP X $ Y)
Ep [ Y +p
(151)
Y)
(())))
Y)
+
(152)
ps( Y)
Thus, we have p Y) / Y) = (Chy 0)/7 which is constant.
Since
Eps (0, ()/ps(0 Y)] have p(0, Y)/Ds( 2 Y) 1. P(X|+,Y) Y) (
p(X,))
(153)
ps(X,
Ps(X @ Y) ()
(154)
Lemma F.17 (Theorem 3.2 from Globus-Harrts al. 13 )- If calibrated and there exists an (()) such that
(x(f(X YY²² - (h(X) (X) u) 2 a,
(155)
then:
E))(X)((
(156)
2
Proposition E.18 (Restatement of Theorem 4.3 (second part)). If predictor f is multicalibrated with Hi,0, then Rys (f) I Rps (fo).
Proof. We prove by contradiction. If Rpp (f) Rp (f+); then
/ B - 1)2-(66(X) - -) = (P] > 0.
(157)
Let at E ((f(x)-)]] -((()) ()2)(() 2].
Since is multicalibrated with H1,0. f is calibrated. follows from Lemma F.17
-X) = 2 0g
(158)
2
Then.
fs) = / (X - =
(159)
> andPs((-
(160)
>0
(161)
From Lemma F55 we have To, ////o,P Ps) > Ki(S, Ps) > O. Since so E Hi,o, a, it contradicts
with the fact that multicalibrated with H1,0-
Proposition F.19 (Restatement of Theorem 4.3 (third part)). fa is an invariant predictor elicited by & across a set of environments where ( Y) Ps(4, Y) for any E &. If a predictor multicalibrated with H2 then f also an invariant predictor across & elicited by some representation.
29

---

Proof.
Since P) -P( Y), we have Ep, [ = Eps [ fo for every E &.
Thus,
Rp. (f+ inf Rp, (g 4)
(162)
DEG
This implies f& is an invariant predictor elicited by d across 6.
For any 8, have:
Pe(2, v) pr( v) (a Phi, y)
(=(2)),))
E H2.0
(163)
ps(a, y) ps( ps(x ps(x v.
Since f is multicalibrated with H2 it follows from Theorem F.8
(f)
inf Rp. (g o
f).
(164)
a:10.1]-[(o.]
This implies that f is an invariant predictor across 6 elicited by
Proposition F.20 (Restatement of Proposition 4.5). Consider X Rd which could be sliced as
X (4), 4 and & (A, 92)". Define Hi == (h(((z)) E C(X V)}, with Hi C. H1
Hl,x and HL,A are similarly defined. We have:
Hi,x 3 Hi 3 Hii 3 H1 [C}.
2. [C] H2, H2 C H2,A H2.0-
C. is constant value function.
Remark F.21. The proposition shows that Hi, as subspace Hi, evolves monotonically and in opposite direction to H2. we perceive the representation & as a filter, gaining more information from covariates facilitates multicalibration w.r.t. Hi (and accuracy) but hampers multicalibration w.r.t Hz (and invariance). With Hi and H2 combined logether, a multicalibrated predictor is searching for appropriate level of information filter to balance the tradeoff between accuracy and invariance.
Proof.
We first prove Hi C Hi.e. According to Equation 122
H1. = {h E C(X x V): Cov [M(0, Y), YI v] for almost every v [0, 1]]. (165)
Since h()) Y L, we have Cov (())) =
Cov (h(
(166)
E [ [
(167)
E [ [f]] E [ fo
(168)
E [b(()){1] E [ falfa]
(169)
JE [E( [1()) YY [ [fa]
(170)
E [Cov [A(@), 1 f
(171)
0.
(172)
Thus, Hi Hi H1.0. Next, we prove the arguments in the proposition.
1. For any h(A) E Hi, since + = (A, 1), ((A) is also function of ②. Thus, we have h(A) Hi
It follows that H2 Hi. Similarly have H4.x H4 and H4, Hí.a-
2. For any h(A, Ω, M, Y) H2, such that (E[((,, V 2, Y] C., for any values of d; Y, have
EiKAA, R, Y) = E [B[N(A, 22, V Y [A, 2, A]
(173)
-E [E[[( V. 8) Y][A,Y]
(174)
[A,
(175)
= Cr for any values of A, Y.
(176)
Thus, M(A, Ω V. Y) E H2,A- It follows that H2 C H2.s. Similarly, we have H2,x C H2 and H2.5 C H2 Particularly for lix, y) H2 we have 1(X,Y) =,)))))),X) a constant for any values of X,Y. Y.
X)
30

---

Lemma F.22 (Globus-Haie Horbus-Harrris et al. [3).. Let H. C X be such a grouping function function class that h E H. implies y + p for any h H and 7. R. I satisfies the (0, 0--eak learning condition in Assumption E.7 predictor I is multicalibrated w.r.I. H if and only if (=) = =E(Y [a] almost surely.
Proposition F.23. For measurable function &b RR + Rd dx Zt predictor f supp( [0, 1] is multicalibrated w.r.t. H1 if and only if f is multicalibrated w.t.t. H1
Proof. Since Hi,0 C H,, f's multicalibration w.r.t H1,0 implies f's multicalibration w.r.t. Hi
On the other hand, Hi, satisfies the (0, OW-k learning condition with the pushforward measure on 2, because E|y [ E H' It follows from Lemma F.22 that f is multicalibrated w.r.t Hi implies
f( = E [ almost surely. By the definition of Hi,0. f(() is multicalibrated w.r.t. Hi.0-
E.4 MC-PseudoLabel: An Algorithm for Extended Multicalibration
Lemma F224 Fix model J X + [0, 1]. Suppose for some &Range(f) there is an h E such
that:
E[h(2, v) v)) >a
Let = nh((,,) for n== "|]"=/""())==']
a
Then:
B[([(x) - y) (1'(,,)) -) = -/> Blb
Proof. Following
[13] we have
[[(((x) y)² (h' v) y)) u
El(u - y)²² (v 110+mh(as n/(,, 1)²1f(x) =
E/u² 2vy + y² (u+ y))² 2y( n v)) f(x)
B[2mnyh(z, y) 20ph(2, ()),,, o|
= E[2nnh(z, y) - u) - ())(2,))))((a))
> 2nj 72 (() = a²
{()))
Theorem F.25 (Restatement of Theorem 5.1 In Algorithm 9 for a. B > 0. if the following is satisfied:
erT:11 erri
(177)
B
the output (x)) a-approximately E2 multicalibrated w.r.t. HB (h E : sup h(. y)² < B).
Proof. We prove by contradiction. Assume that fi-1 is not a-approximately multicalibrated with respect to HB. Then there exists h E HB such that:
Σ
P()+i(x)= = (E( (E ((x,,))) - se-1 = 00) a.
#E[1/m]
For each E [1/m] define
- au == P(f u) (B f- = =))²
Then we have Eve(1/m) Or a.
31

---

According to Lemma
F.24 for each v E [1/m], there exists he E H such that:
E ( - y)² (h. y) (z) u
(178)
(179)
Blh(2) f1-1(z) ( = v|
Ov
(180)
B ((f
Then.
E (1)) -)2 (f((t)) y)²
Σ P(f--((z) = = (fc-
-2)2- 1) = =
vE[l/m]
Σ ((f = -) [f) y)² - (1. v) - 3)2 f(-1 c]
eE[1/m]
a
B
which contradicts the condition in Equation 177
The following proposition is direct corollary from Globus-Harri Harris et [3''s Theorem 4.3.
Proposition F.26. For any distribution D supported X y and & E o(X), take the grouping function class
Hi == (h(((=)) C(X Y)} and the predictor class F R.a For
any 0 <a < 1, B > O and an initial predictor fo X - [0, 1] with |Range(fu) 2 2B then MC-Pseudolabel(() H)FF halts after at most T < 2B steps and outputs model f--1(() that is a-approximately & multicalibrated w.r.t D and HB {h E H sup h(x, y)² < B}.
Theorem F.27 (Restatement of Theorem 5.2p. Consider X Rd with X ( 1T)T. Assume that ( V Y) follows a multivariate normal distribution Na+1(14, Σ) where the random variables are in general position such that Σ is positive definite. We partition E into blocks:
E4.
Eg Egv
Eay
Σ
Ege Enyt
Evy Engy
(181)
Enye
For any distribution D supported on X x V, take the the predictor class F = B. and the grouping
function class as a subset of H2,3, which defined in Equation T24
H (h: H2. and hxx y) cx Cgl + Ch, Ca Rdd Cy. Cb ER.
(182)
For initial predictor (x) [x], run MC-Psendolabell DD H.F) without rounding, then there exists some constant C. depending on x and some constant M (E) depending on E, such that (x) - E [+x)] S (E)) where
M(E) (Ewv Eyo --
44 Eoy) 'EE
- En Eigb Fov) EΦv)
(183)
(Eev - Exp Dog Exerr 1(Ee Evo 2ig Eipyy.
(184)
We have S <EE 1.
Remark F228. f(() and E{Y [bxx) are both linear. Thus, the convergence of the functions f(a) is equivalent as the convergence their coefficients. The theorem essentially states that the coefficients of (0) converges to those E[Y ( (x)) at rate of (E))).
Remark F229, E[ (x))) multicalibrated with respect to H. Farthermore, any calibrated predictor on h denoted by g( (()), is multicalibrated with respect to H. This is because:
(X, Y) g(+)))l((() = E E [x Y) (l
(185)
E [C (())))
(186)
= 0.
(187)
However, E[ [b) is the most accurate predictor among all multicalibrated 9
32

---

Remark F.30. The convergence rate M (x) does not depend on the dimension d of covariates. When Y 1 & implying that & is sufficient for prediction, following from E (,, v = E|]
Evy = Ev - Eay
(188)
follows that M())) = and the algorithm will converge in one step.
On the other hand, when Y and vi are linearly dependent given Tb such that E is singular, which violates positive definiteness, following from the proof below:
Egy Enjo Egg Eay Egge
(Enyx E.v
Evo Eno Dov) (Evy
Eve E Dey). (189)
follows that (E) = and the algorithm can't I converge.
So the convergence rate depends on the singularity of the problem. Since the algorithm converges to a predictor that does not depend on V, stronger the "spurious" " correlatton between Y and Lp given in the distribution D. the algorithm takes longer to converge.
Proof. Without loss of generality, assume μ = 0.
Let c = (Car Cyp 0z)²² = (co, Co, Cap Cy, 0b)² Denote dimensions of o,, V by da, dy.
Let [ V (ag)= + (att) ) v and E[ Y] = (gg) T + (8;) Ty with ag TRd,,
O E IRd, f E Rda xdv .3g E R RIxdv.
We have:
a a1
EΦs Σvw
Edy Ever
(190)
(8
Egp
Egy Vay
-1
Σg v Ene
(191)
8
Dyb
According to Theorem
1.15
E.h( X, Y) Φ, y] is a constant for different values of Φ; Y
() = cf + o y + c E YJ
+|+c0 cb
(192)
Eeo Engo
Edy Eny
= c + TY + T (E Egn)
+ Cb.
(193)
Y
This implies:
Zoo Eye
Moy
Eyy
Zov
Egv
cx
Co Cy
0.
(194)
Rearranging to:
Exe
Edy
c= 0.
(195)
Eye
Eye
Evy
v Let (() = (0 + (T and f(() = (a (a())TT + (1 - We claim that
(1) = 0. Otherwise, consider F(t)' = (a TTp + {a
B f(01 | = E((ā (T YJ / क Yj = 0.
(196)
Thus, f(0) juy H.
On the other hand,
E((Y- - f(0))2] EE((Y - =
(197)
= E (a Tr [B[VVV Φ Y] - EEV Y|W 1 Y1 0
(198)
0.
(199)
33

---

The inequality follows from the fact that E 7 Φ. Y 1 L. YE d, Y] is the covariance matrix of f/ YY which is positive definite because positive definite. The inequality contradicts with the definition of fit). Thus, f(() = (a (1)
T (0% (a(e))T yTY.
Define a matrix C' E R(++))xd whose columns support the solution space of Equation 195 N = (S, Y"", E _d is random vector. According to the definition of f())
Then
f(+1) E| H]
(200)
= 18(0)(() + (c)
(1 (1))'' (a 10 +
(201)
= (a (0) T ( + 100
10 TT + (d))"r..
(202)
In the above equation, l((t) R.
(1) Since a (x + cv 0, we have ( 1:100
(1)
Substituting into Equation 194
(:
Eay Eyz
a
(e)
(203)
Substituting into Equation 202
(t-1)
(a(1)
p 0yy
((-1)
k((0)
(204)
= =k(())
Ido
a
(t)
(205)
(t)
Then we have f((+1)
sb w0] 11f(+1))100
(a )T' Φ + (āg
(1+ D) E Φ w..
This is equivalent as:
(++1) Og Chi (1+1)
(1+1)
Σ Exe Eve
Exv Eve
Eay Evy
a(t+2)
(206)
Lás
atp
a c ity
(1-1)
(1-1)
(207)
O
Combining the two equations above, we have:
axp [++]
(++1) o
= k(t))
Ido
Ogp a
("o
lio
B
(208)
a
(Too
B + 0
= k(t)
(209)
a gr
(0)
Thus,
a
(6)
K(O)
(Tos
S1 + 0 3t
(0)
(210)
(t)
a 3
a
k(1)
[Ido
S + a 3t
(211)
a
a
In the above equation, K(() Hosser k(m).
Define f(() = (a TT + ( TVV where
(0)
[dn
3 + t
(212)
a 3t
ag
à
34

---

In the following we show Oyp + O. Since (00) = (ag,3t)ox (a and ag E RRdo RRduxde xde has exactly
(8)
one nonzero eigenvalue a we just have to show 13 < 1.
3 = (Eigg Eno 2o -oy)
(213)
2ig (2yy Ey 2a Lip (Zive Vi 2i ) (Sio - Ei مللد Egny).
(214)
Since, (Eyy EypDig Eny and (Evpy Evp Egv are both Schur complements of E's principal submatrix, they are still positive definite.
Eg
Thus,
Enyy - Eneo L00 Eay > O.
(215)
(Engv Eno Doo Ege) (Evv - Evo Dov) (Evr - Evo Evo 2 O.
(216)
It follows that Byat 2 So we just have to show gy
Since det(E)) > 0, by applying row addition on E, we have:
Σie 0
Ega Enpr Egg I-1 Eg ad Eyw
Eay
det
Egy Exp I-1 1 Enpy
>0. 0.
(217)
Ege Exp Igy
Eyv Eyo Engi Eng
follows that:
(Eny Eng L Easy)
(218)
(Enu Eyo E E (Evv - Eve E Eov) - Egg 00.
(219)
Rearranging to:
85 = (Eyy - Eyo Ingi )
(220)
(Evv- - Evo Dod (Eny Enjo Eod E E
Eve Doo Eay)
(221)
1.
(222)
Thus, 0 5 0 <. In the following, we show dg + Eng Egy. By Equation 212 and (8 < 1, we have:
a& = a + (or + aa
(a (a at
(223)
osuct
11000
aq. + S + a (Ide (01
(224)
= aip + (B) + a B1 - -'a
(225)
a² 3ga
(226)
33
Equation 225
follows from the fact that (Ids - Orty 1,g,3)as = (1- 3o
Define 2á Egg Eay such that E|Y [b}
( Φ. We have
E
E
Y
V
0 (b ()
(227)
E
E
[(
[6] = (T..
(228)
E
(T.
(229)
(T))TT
T + (0) (>8) (T5)
(230)
a + a + 83 76
(231)
a 870g
3,0 74.
(232)
Thus, (0 - 2oo Eoy. Subsequently, f(1) - (5--) (.y, J / The convergence ratio M (2)= Br
35

---

We have:
a
(1+1)
k((+1)
(
Idn
a
(t)
(233)
((+1)
where
(To 0
Ide
B
(1)
14000
Ide 0
Big By
Do
Eoy
(234)
(2)
2o Eay 0
(235)
Define f()) = (a T + )
TY, where
ag
1(++1)
(To
Ido
3
ay alt+1)
=
By
(t)
(236)
Thus, f(n - B Since f() K(()) f(t) we have f( EE f - [Y]
Subsequently, f(+) E[f Φ2 V + E Ø].
G
Limitations
Both our theory and algorithm focuses on the bounded regression setting. The definition of extended multicalibration does not depend on the risk function. However, the analysis the maximal grouping function class linear space assumes a continuous probability distribution of observations, implying a continuous target domain. The convergence of JCC-sseuolaael is also established in a regression setting. All experiments
performed regression tasks. As most algorithms for out-of-distribution generalization are set up with classification problems, we fill the gap for regression and leave an extension to general risk functions for future work.
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: The abstract and introduction accurately outline research questions, and faithfully reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations in section G and analyze computational complexity of algorithm in section D
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 on 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 a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
37

---

Answer: [Yes]
Justification: Full assumptions, formal statements of theories and proofs can be found in section P
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 proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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 be 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: [Yes]
Justification: Experiment settings and implemention of methods described in section 6.1 Further training details can found section E.3 Codes are available in supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a 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 a 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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is 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 instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe 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.
38

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: All the datasets in this paper are public with citations (see section 6.1 Code is provided additional supplemental materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
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
/ httppp.cccpubllc/uuucccee
Codeeubmii ssi crrionPPoiccy 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,
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: [Yes]
Justification: Experiment settings are described section 6.1 Further training details can be found in section E3
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, 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: [Yes]
Justification: Standard errors are reported for all results. The factors of variability include random drawing of hyperparameters and seeds, and cross validation on dataset splits. See section for details.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
39

---

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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
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 errors 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 eтror rates).
If error bars reported in tables plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer:[Yes]
Justification:
Refer to section E.4
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't '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
Answer: [Yes]
Justification:
The research conducted in this paper conforms with the NeurIPS Code of
Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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 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: There negative social impacts for research conducted in this paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
40

---

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), faimess 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 tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to 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 to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used 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 unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how 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 poses safeguards 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 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.
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
Question: Are the creators or 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?
Answer: [Yes]
Justification: All datasets in this paper are cited. Codes are credited with original licenses provided.
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 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 (e.g., website). the copyright and terms of service of that source should be provided.
41

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
datasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of 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
Question: 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)?
Answer: [NA]
Justification: The paper 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.
Including this information 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 the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper 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.
Depending on 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.
42

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS 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.
43


Reviews:
[{"review_id": "MJhRgXaMzY", "reviewer": "Reviewer_7ztk", "summary": "This work studies an extension of multicalibration to include grouping functions of both covariates and labels. They show that just as multicalibration with respect to covariate density functions guarantees robustness to covariate shift, that extended multicalibration can imply robustness to concept shift. They further show a connection between extended multicalibrated predictors and invariant predictors. They study necessary and sufficient conditions on (covariate-dependent) grouping functions to achieve approximately Bayes optimal predictions on all target distributions, and introduce a boosting style algorithm that converges to an extended multicalibrated predictor under certain distributional assumptions. The usefulness of this new algorithm is empirically validated on PovertyMap, ACSIncome, and VesselPower.", "questions": "Repeated from weaknesses:\n\n1. Is there a correspondence between weak agnostic learning and extended multicalibration?\n\n2. On what kinds of distributions will the algorithm fail to convergence for H_{2, \\Phi}?", "limitations": "The authors largely addressed the limitations (with the exception of possible computational limitations mentioned in Questions).", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This is a very interesting work that as far as I know if the first to considering multicalibration with respect to grouping functions that depend on labels. This gives a new approach to handling concept shift, and a new perspective on invariant predictors. I'm personally looking forward to follow-up work. \n\nI found the paper very well-structured and easy to follow.", "weaknesses": "There are some questions regarding the feasibility of the MC-PseudoLabel that I did not see addressed in the work that would be helpful in understanding its usefulness. First, there's a known correspondence between multicalibration with respect to a hypothesis class H and weak agnostic learning for H, which unfortunately limits the grouping function classes for which we can efficiently obtain multicalibrated predictors. Does a similar correspondence also hold for extended multicalibration, or is a stronger weak learning condition required (alongside distributional assumptions)? I'm also curious about the necessary assumptions on the data for convergence of MC-PseudoLabel. On what kinds of distributions will the algorithm fail to convergence for H_{2, \\Phi}?\n\nTypos/suggested edits:\n\nAbstract\n\n“in existence” -> “in the presence”\n\nSection 1\n\n“flexibly designed to incorporates” -> “incorporate”\n\n“Simultaneoulsy producing invariant predictors” -> “produce”\n\n“porverty estimation”\n\nSection 2\n\n“which is learned in the source distribution” -> “which are learned”\n\n2.2 \n\n“simultaneous approaches” -> “simultaneously approach”\n\n“We show that multicalibration notion w.r.t.” -> “We show that our/this multicalibration notion”\n\n\nSection 5\n\nM(Sigma) is defined in the Appendix, but not in Theorem 5.2 where is first appears", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate the reviewer for pointing out the significance of our result for being the first to consider a label-dependent grouping function in multi-calibration, as well as the soundness and organization of our paper\\! The reviewer has raised questions over the learnability of the extended grouping function class, which we are ready to address below.\n\n### Q1: Correspondence between weak agnostic learning and extended multi-calibration.\n\nIt is possible to establish a correspondence between a weak condition of the grouping function class and extended multi-calibration under certain distributional assumptions. By considering grouping functions within a linear space (section 4), multi-calibration with respect to a finite but sufficiently large dimensional grouping function class can imply multi-calibration with respect to an infinite dimensional grouping function class, which resolves the learnability of extended multi-calibration. This relationship parallels the way weak agnostic learning addresses the learnability of original multi-calibration. This conclusion is derived from the generalization theory of invariant risk minimization \\[2\\] for a linear data generation model. Arjovsky et al \\[2\\] conclude that an invariant predictor obtained from $O(d)$ distributions (d for the dimension of covariates) can generalize to infinitely many distributions (respecting the invariance assumption) whose density functions are linearly independent. Since one distribution corresponds to a density ratio function in our grouping function class, we conclude that multi-calibration with respect to an $O(d)$-dimensional grouping function class can imply multi-calibration with respect to an infinite-dimensional grouping function class, under a specific linear model. It would be very interesting to explore in future work whether such weak learning conditions can be extended to more general cases.\n\n\\[2\\] Martín Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization.\n\n### Q2: Any distribution where the algorithm fails to converge?\n\nThe algorithm fails to converge for grouping functions that violate the distributional assumption in Theorem 4.2. For example (L258-261), the algorithm will output the initial model $f\\_0$ for the grouping function $h(x,y)=y$, because the pseudo labels always coincide with true labels. There does not exist a predictor that is multi-calibrated to $h(x,y)=y$, as it indicates an unresolvable concept shift where the outcome can arbitrarily change.  \nMore generally, the algorithm does not converge if the pseudo labels always coincide with the true labels, which also happens if the cardinality of the outcome’s support is smaller than the dimension of the grouping function class. This is more frequent for classification tasks, which is stated as a limitation of our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wMvSuZ0GfC", "reviewer": "Reviewer_TrUb", "summary": "The paper explores multicalibration in the context of concept shifts, theoretically demonstrating the equivalence of multicalibration and invariance while providing a structural analysis of multicalibration. It introduces a novel algorithm that simplifies model selection and improves performance on real-world datasets.", "questions": "- It seems that the setting you called \"out-of-distribution generalization beyond covariate shift\" is basically concept drift. I wonder why you choose to call that.\n- In theorem 4.2 and 4.3, you consider an \"absolutely continuous probability measure\" without stating what measure it is with respect to.", "limitations": "See weakness.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper provides rigorous and solid theoretical work for its claims.\n- MC-Pseudolabel algorithm offers a practical tool that appears to integrate well with their frameworks.", "weaknesses": "- The empirical work is limited and not that convincing.\n- Although technical solid, some assumptions might be too strong to achieve in reality.\n- The complexity and detailed mathematical theories/assumptions would make the paper challenging for a broader audience to easily digest.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s acknowledgement of our paper as both a solid theoretical work and a practical tool. Since the reviewer raises questions regarding the scope of experiments and the feasibility of assumptions, we are ready to offer more details for the reviewer’s evaluation.\n\n### W1: Scope of experiments.\n\nIn our paper, we have strived to conduct extensive experiments to cover a lot of ground, including multiple OOD learning settings, four different datasets across tabular and image modalities, various architectures of neural network predictive models, and multiple baselines both within and beyond the scope of invariant risk minimization. In detail, our experiments are performed on two settings of multi-environment learning with/wo environment annotation. We have a simulation dataset and three real datasets. Notably, PovertyMap comes from WILDS, the standard benchmark for OOD generalization, and ACSIncome is a popular benchmark for both fairness and algorithmic robustness, which features natural concept shifts \\[32\\]. Our models span linear, MLP and Resnet architectures. Our baselines include techniques from invariance risk minimization and other OOD methods, such as DRO and sample reweighting. The SOTA method (C-Mixup) from the WILDS open benchmark is also included. For all evaluations, we systematically select hyperparameters and conduct multiple repeated experiments according to the standard protocol of DomainNet. The proposed method achieves the best results in 7 out of the 8 reported evaluations.\n\n### W2: Assumptions of theories.\n\nThe main assumption of our results is stated in Equation 3, which requires that the grouping function class must include all density ratios between target and source measures. This assumption is general enough to essentially capture various practical OOD settings. Three such settings are discussed in Section 4.2 and Appendix B, where the assumption is satisfied, and the corresponding design of the grouping function class is given. For example, the subpopulation shift describes a setting where the target distribution is a different weighted mixture of subpopulations. This issue is effectively addressed by constructing the function class through interpolation of density ratios of several subpopulations in the data (Equation 11).\n\n### Q1: Edits of title: beyond covariate shift or under concept shift.\n\nBefore our work, the existing connection of multi-calibration and distribution shift was restricted to covariate shift. By using the term “beyond covariate shift,” we aim to highlight the gap we fill in the literature by being the first to extend the notion of multi-calibration and establish further connection to concept shift.\n\n### Q2: Reference measure of Theorem 4.2, 4.3.\n\nWe consider the Lebesgue measure as the reference measure.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tLv4VFQi4e", "reviewer": "Reviewer_HkL5", "summary": "The authors explore an extension of multicalibration which includes joint grouping functions; groups that depend on both x and y. They show that multicalibration confers robustness to distribution shift problems. The authors then develop an optimization framework that post-processes a model to multicalibrate it. Finally, empirical demonstration of the robustness properties are given through experimentation.", "questions": "Line 9 of Algorithm 1 is unclear to me. I had thought A finds low risk models f(x) on an empirical dataset {(x,y)}. What does it mean for a grouping function to have low risk on a dataset? What is risk here?\n\nWith regard to Algorithm 1, the authors state \"The prediction of grouping functions rectify the uncalibrated model and serves as pseudolabels for model updates.\" Can this statement be expanded, and details be provided?", "limitations": "The authors have adequately addressed limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The authors provide compelling reasons why multicalibration should be considered in modeling and model evaluation frameworks. In doing so, they provide a calibration framework that confers robustness on post-processed models. The proposed method appears significantly easier to use than methods that leverage actor-critic, domain confusion, and other modeling tricks to achieve robustness.\n\nSection 4 shows that the condition \"the grouping function class must include all density ratios between target and source measures\" is achievable in practice.\n\nThe paper is well written and easy to follow.", "weaknesses": "A few questions are given below. I have nothing else to add.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support\\! We really appreciate it that the reviewer identifies a compelling reason for applying multi-calibration to algorithmic robustness, and highly evaluates the simplicity and efficiency of our approach, the feasibility of our assumption, as well as the organization of the paper. The reviewer requests more details about an intuitive explanation for part of our algorithm, which we are ready to address below.\n\n### Q1: Intuition behind regression on the grouping function class.\n\nIn the following, we elaborate on the intuition described in Lines 255-257. In L9 of Algorithm 1, we perform regression on level sets with grouping functions. Here, the risk is the same as fitting a model $f(x)$. Since this regression is performed for each level of the predictor, it’s actually regressing the outcome on both the predictor’s output and the value of the grouping functions. Intuitively, this step rectifies the predictor given the distributional information conveyed by the grouping functions.   \nConsider a toy case of multi-environment learning where the distributions in each environment are significantly different from each other, such that one can almost infer which environment a sample is taken from by looking at the density ratio provided by the grouping function. Then, regression on the predictor’s output and the value of the grouping functions reveals how much can be improved by knowing the environment from which the sample is taken. If there is indeed much improvement, it implies that the predictor does not perform well for this specific environment. In other words, the predictor shows a bias on this environment, which makes it uncalibrated. The improved prediction by regression on the grouping function class then serves as a pseudo label. Updating the model towards this improved prediction de-biases the model and makes it more calibrated on this particular distribution. The procedure is repeated in the next iteration to find another distribution where the model is uncalibrated, continuing until convergence.   \nThe intuitive explanation above sketches the proof of certified multi-calibration for this algorithm in Theorem 5.1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Dbs0m1O8xQ", "reviewer": "Reviewer_ezjY", "summary": "The authors propose utilizing multicalibration algorithms to achieve distributional robustness w.r.t. both concept and covariate shift. They do this by allowing subgroups to not only be a function of the features X (as is standard in multigroup fairness), but also a function of the label Y. There are numerous theoretical and experimental results. The first result (thm 3.2) states that under closure properties of the hypothesis class $\\mathcal{H}$ w.r.t. possible distribution shifts, and a weak-learnability assumption on $\\mathcal{H}$, multicalibration w.r.t. a particular set of subgroups $\\mathcal{H}_1$ guarantees that the resulting predictor will achieve good error (relative to the bayes optimal predictor) under any possible covariate shifted distribution $P_T$. \n\nIn theorem 3.1., the authors show that an L2-multicalibrated predictor f cannot be significantly improved by any post-processing function in order to achieve robustness to concept shift. The authors then show an equivalence between approximate multicalibration and a notion called approximate invariance from prior work (theorem 3.4). Invariance is a property of a representation $\\Phi$ which says that there exists a predictor $g^*$ based only on $\\Phi$ which achieves good error across all environments. The equivalence between the two notions is up to considering subgroup functions defined by the density ratios between the target environments and the source distribution, similar to the result in theorem 3.1.\n\nNext, the authors demonstrate that (joint) multicalibration cannot always be achieved for all jointly defined subgroups. Thus, they are interested in the maximal feasible set of jointly defined groups for which we can achieve multicalibration towards. These groups turn out to lie in a linear space (Prop. 4.1.) and have a well-defined spanning set which looks similar to an invariant predictor (Thm. 4.2). Finally, they show that the subgroup function space can be decomposed into an invariant and multicalibrated part (Thm. 4.3).\n\nLastly, experiments are conducted which demonstrate the usefulness of multicalibration in achieving distributional robustness for simple neural networks on the PovertyMap and ACSIncome datasets.", "questions": "Q1. How does section 5 relate to the rest of the work? Why do we need another multicalibration algorithm? What problem is MC-PseudoLabel solving which existing OOD / domain adaptation algorithms do not already solve? I believe that these are critical and should be stated explicitly.\n\nQ2. Line 83: “We say that f is $\\alpha$-approximately calibrated if $h \\equiv 1$.” What does this mean? I think you mean if $\\mathcal{H}$ includes the constant function $h\\equiv 1$, then we can say that f is $\\alpha$ approximately calibrated. \n\nQ3. Line 18: “Multicalibration is a strengthening  of calibration, which requires a predictor f to be correct on average within each level set:” For clarity, perhaps you could introduce calibration first in an isolated way, without mentioning multicalibration? The discussion here could potentially be misconstrued by the reader.\n\nQ4. Line 80: Definition 2.1. Outside of extending to joint subgroups h(X) -> h(X, Y), how does this definition relate to existing multicalibration definitions?\n\nQ5. Theorem  3.1: In the appendix proof of this theorem, the authors state a similarity to Blasiok et al. [5] w.r.t. the theorem statement. How similar is the proof, and what complications arise from needing to consider joint grouping functions? This should be in the main paper, especially since others may notice a resemblance between the results as well.\n\nQ6. Line 180: “Section 3 inspires one to construct richer grouping function classes for stronger generalizability”. Why is this the case, or can you expand on what this means exactly? Is the idea that due to theorem 3.4, we understand that multicalibration w.r.t. Sufficiently rich joint grouping functions gives us a nice property, but we want to efficiently achieve this which may be difficult in practice?", "limitations": "The authors have stated the main limitation of the work, which is that most OOD generalization papers deal with classification, not regression. However, I see this as a feature, since regression can also be a useful consideration in practice.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "Originality: To my knowledge, the work is very original, especially the consideration of the maximal grouping function space. While extending subgroups to be defined on the label as well as feature is a natural generalization, the authors have unique function space decomposition results (section 4), which are interesting in their own right and whose proofs utilize classical results from linear algebra. Substantial theory is developed through most of the paper, mostly surrounding the inclusion of particular density ratios in the subgroup function classes. I think the results taken together are very original and interesting!\n\nSignificance: understanding what is possible with families of multicalibration post-processing algorithms is a very important and interesting direction, and combining this with out of distribution generalization is an area which is quite interesting.", "weaknesses": "I have not checked the proofs thoroughly.\n\nI believe the paper has much room for improvement in terms of clarity, organization, and discussion. In isolation, these may be minor, but taken together, the writing poses a major limitation to the greater community understanding the work (as well as its position in the literature). Throughout, I have asked explicit questions which I would like the authors to address, and labeled them as Q1, Q2, etc.\n\nW1: Firstly, I believe the introduction requires substantial re-writing. Currently, it makes sense to someone who is familiar with both the multicalibration and distributional robustness literature (most people are not). For example, the first sentence of the paper mentions both out-of-distribution generalization and multicalibration, without motivating either of these communities. (Q1) Why might we want to connect these notions? What do we stand to gain from applying multicalibration, and what does multicalibration address that the (substantial) work on OOD generalization has not considered? Perhaps these questions are answered implicitly elsewhere in the work (and I missed them), but I believe that the authors should do a better job of framing the problem they are trying to solve in the context of the literature.\n\nW2: I believe that an explicit discussion of related work in the introduction can be very helpful. I understand that the authors defer all related work discussion to the appendix, but as someone familiar with the multicalibration literature but not distributional robustness, the main paper was hard to follow.\n\nW3: Little interpretation of results. As this is predominantly a theoretical paper, I understand that it can be challenging to concisely state and provide intuitive explanations of each result. However, I believe that the paper can be substantially improved with some additional intuition. Even understanding the theorem statements in section 4 took substantial effort from my part.\n\nAs another example, in Section 2.2: line 101-106: it seems implied that these assumptions are from previous work, but it would be good to state explicitly. (Assuming that is the case). Further, any further discussion on the assumptions would be appreciated. I believe it could be useful to state the assumptions in 2.2 as two separate assumptions, in order to make references to them in the following theorem statement more clear.\nThere is no discussion after the statement of the theorem 2.3. What is the class H_1, and why does it help us achieve robustness to distribution shift? How does it relate to the two assumptions stated previously?\nAlso, how does Kim et al. [22] relate to theorem 2.3? These should all be explicitly discussed.\n\nAs a positive example, the authors do provide some discussion in lines 175-178. Expanding and including similar discussion throughout the paper can help make the ideas more parseable to the unfamiliar reader.\n\nW4: Section 4 is extremely difficult to parse. This also connects to W3, as there is little interpretation of the results. What are the implications of the grouping functions being a linear space? Why is the decomposition in theorem 4.3 a Minkowski sum?  Also, how do these results connect to the algorithm developed in section 5?\n\nMinor comments\n35: The authors use the term “joint” grouping functions, but have only implicitly described them in the previous paragraph. It would be clearer to concretely mention that you call these subgroups which depend on both X and Y joint grouping functions.\n\n41-43: The definition of invariance / IRM is not very clear here. I think it is ok to defer a formal description to later, and just mention that you provide an equivalence between the invariant learning framework and multicalibration. \n\nIn line 120, there is some motivation for covariate shift and concept shift. I believe this discussion should go far earlier, perhaps in the introduction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and efforts to improve our paper! We appreciate your recognition of our contribution's originality and significance. We believe we have included relevant details in our submission that address many of your questions. We will incorporate your questions and feedback to further enhance clarity, which we address below.\n\n### W1,Q1: Which OOD problem is solved by applying multi-calibration ?\n\nThe first advantage of multi-calibration is **universal adaptability**, i.e., generalization to any target distribution with a density ratio captured by the grouping function class [22]. Existing OOD methods target a specific distribution for domain adaptation [A1] or multiple subpopulations for domain generalization [16]. Universal adaptability is central to studies connecting multi-calibration and distribution shift, though restricted to robust statistical inference under covariate shift (L23-28, L585-589). Our research considers a general uncertainty set of target distributions (L69-73) and extends universal adaptability to prediction tasks and concept shift (L39-45).\n\nSecond, our algorithm offers a post-processing optimization framework more **computationally efficient** than current OOD generalization techniques (L55-64). MC-Pseudolabel, using a trained model as input, involves supervised regressions adding only linear regression overhead compared to a standard backward pass. Established OOD methods perform bi-level optimization or multi-objective learning, which involves higher-order derivatives or adversarial training.\n\n[A1] Zhao, H., Des Combes, R. T., Zhang, K., & Gordon, G. On learning invariant representations for domain adaptation.\n\n### W1,Q1: Why do we need another multi-calibration algorithm?\n\nIn section 5, we develop a new multi-calibration algorithm for joint grouping functions (dependent on x and y) because we cannot trivially extend existing algorithms for covariate-based grouping functions like LSBoost. The comparison between MC-Pseudolabel and LSBoost is detailed in L264-273. The main obstacle is that those algorithms produce predictors taking y as input. As a solution, we project the predictors back to x-based functions by tuning models with pseudo labels. This projection substantially changes optimization dynamics by disrupting the monotonicity of risks which LSBoost relies on, and also results in a different proof of convergence.\n\n### W2: Moving the discussion of related work from appendix to introduction.\n\nWe appreciate your suggestion. Complementing our current review of multi-calibration studies and their connection to distribution shift (L20-28), we will expand the discussion on key related methods for distributional robustness (L59-61) to highlight gaps in universal adaptability and computational efficiency.\n\n### W3: Interpretation of Theorem 2.3.\n\nWe expand the discussion on Theorem 2.3 in L96-104, focusing on its connection to two established results and assumptions. This theorem bridges results from Kim et al. and Globus-Harris et al. (L98) and serves as a warm-up solution to covariate shift before focusing on concept shift. Kim et al. show multi-calibrated predictors remain multi-calibrated under covariate shift, with Assumption 2.2.1. Globus-Harris et al. show multi-calibrated predictors approach Bayes optimality in a single distribution, with Assumption 2.2.2. Combining both assumptions, the theorem shows multi-calibrated predictors approach Bayes optimality in target distributions under covariate shift. ***We are ready to further discuss the assumptions during the discussion period.***\n\n### W4: The role of structural results for maximal grouping function space in section 4.\n\nSection 4 connects to Section 5 by designing the function class used as input to the MC-Pseudolabel algorithm. **Together, Sections 4 and 5 establish a two-step paradigm for robust prediction**: first, a function class capturing priors of distribution shift is designed, then a downstream universal multi-calibration algorithm is run for any feasible grouping function class. In Section 4, the goal is to certify robustness by designing a grouping function class large enough to include the target density ratio while ensuring a feasible solution without exceeding the maximal grouping function space (L180-187). ***We would be happy to elaborate on the theorems' implications in Section 4 during the discussion period.***\n\n### Q2, Q3: Edits for two sentences.\n\nThanks for the suggestions on L83 and L18. Your interpretation is correct.\n\n### Q4: Connection of extended multi-calibration definition with existing definitions.\n\nThe major difference between Definition 2.1 and existing definitions is the joint grouping functions. The closest covariate-based version is in Globus-Harris et al. We also consider predictors with a continuous range, unlike their discrete outputs.\n\n### Q5: Comparing Theorem 3.1 and Blasiok et al.\n\nTheorem 3.1 and its proof are essentially distinct from those of Blasiok et al. Blasiok et al. show a connection between smooth calibration error and post-processing gap. We follow a similar technique **only** in the last proof step for Theorem 3.1 (L740-741) to show a connection between a variation of their smooth calibration error and the post-processing gap. The rest of the proof shares no similarity with Blasiok et al. As a proof sketch, we first connect the multi-calibration error in the source distribution with the calibration error in each target distribution, then prove an equivalence between calibration error and a variation of smooth calibration error.\n\n### Q6: Why do richer grouping function classes induce stronger generalizability?\n\nAccording to Theorem 3.4, a richer grouping function class implies generalizability to **more** distributions, as characterized by the density ratios in the function class. However, a predictor that is multi-calibrated to the function class may not exist, which is addressed in section 4.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper provides new insights on multicalibration in the context of concept shifts. The reviewers unanimously acknowledge the notable technical contribution of the paper, however, the presentation can be improved for the final version. I recommend accept.
Decision: Accept (poster)