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$.
In 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.
Next, 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).
Lastly, experiments are conducted which demonstrate the usefulness of multicalibration in achieving distributional robustness for simple neural networks on the PovertyMap and ACSIncome datasets.
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!
Significance: 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.
I 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.
W1: 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.
W2: 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.
W3: 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.
As 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.
There 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?
Also, how does Kim et al. [22] relate to theorem 2.3? These should all be explicitly discussed.
As 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.
W4: 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?
Minor comments
35: 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.
41-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.
In line 120, there is some motivation for covariate shift and concept shift. I believe this discussion should go far earlier, perhaps in the introduction.
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.
Q2. 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.
Q3. 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.
Q4. 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?
Q5. 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.
Q6. 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.