OOD-Chameleon: Is Algorithm Selection for OOD Generalization Learnable?

Many thanks for the thoughtful review. We are happy that you found our work novel and the analysis insightful.

---

Comment 1 (Theoretical analysis to explain the success of OOD-Chameleon): The bottom line is that our meta-learning-like approach turns algorithm selection into a supervised problem where, on the theoretical side, classical results from statistical learning theory apply. In particular, we use either an MLP or a decision tree to parametrize the algorithm selector. The approximated VC dimensions of these classes are well defined and can be used for bounding generalization errors of the selector.

---

Comment 2 (Theoretical analysis from an OOD framework): This is a valid question. Identifying generalization bounds when multiple types of shifts co-exist is an open problem. Most theoretical work focuses on a given type of distribution shift [1,2,3]. The difficulty of theoretically handling complex mixed types of shifts is a core motivation for our empirical approach (see L40, L66, L185). A theoretical treatment would be highly valuable but besides the point of this paper and deserves a full separate work.

[1] Understanding the Failure Modes of Out-of-Distribution Generalization. Nagarajan et al.

[2] A Unified View of Label Shift Estimation. Garg et al.

[3] A Theoretical Analysis on Independence-driven Importance Weighting for Covariate-shift Generalization. Xu et al.

---

Comment 3 (additional algorithms/baselines): Our approach is not tied to specific algorithms. The ones used in the current implementation are justified L245-255: (1) they belong to different categories, (2) can address different types of shifts, (3) were proven to be effective in seminal works. Most importantly, no method is strictly stronger than these [4,5], and we show that better algorithm selection with these 'simple' methods is sufficient to improve OOD generalization.

[4] Simple data balancing achieves competitive worst-group-accuracy, Idrissi et al.

[5] Change is Hard: A Closer Look at Subpopulation Shift, Yang et al.

Algorithm selection baselines: There are no existing competing methods; our evaluation includes various single-algorithm selection baselines. We propose an additional experiment with a new strong ensemble baseline: every algorithm is used to train a model whose predictions are ensembled (row 1). Our approach (row 2) significantly outperforms this ensemble. The ensemble also requires training and evaluating as many models as algorithms vs. only one for our method.

As suggested by Reviewer sRjw, we also investigated combining OOD-Chameleon with an ensemble (row 3): predictions are ensembled after weighting by the predicted score of the algorithm. This further improves OOD-Chameleon in certain cases. It confirms the quality of the predicted suitability of algorithms, but removes the benefit of only having to train a single model.

---

Comment 4 (meta-dataset diversity): This is true for any supervised model where the training data coverage will inevitably affect the performance (also similarly, the pretraining data coverage for a pre-trained model affects its capability). So we rather believe this is a feature instead of a limitation, since this allows for building a more powerful predictor with meta-dataset scaled up. This is confirmed in Figure 3-middle. Another point to note in that figure is that, only a relatively small size of meta-dataset (~200) is sufficient to outperform the best non-parametrized baseline by a large margin.

---

Q1: please see the response to Reviewer sPTX (Q4).

---

Q2 (Office-Home): We performed additional experiments as requested with Office-Home. We created 100 datasets by randomly sampling a pair of domains and a pair of classes for each dataset (e.g. classifying pen/knife in Art/Clipart). The number of samples is naturally imbalanced, creating mixed types of distribution shifts by design. We use the algorithm selector from the paper trained with the "CelebA" meta-dataset, which we use to predict suitable algorithms for these variants of Office-Home. The (worst group error) results are below. They provide strong additional support for the utility of our approach to select suitable algorithms across datasets and diverse types of shifts.

---

Let us know if there are remaining questions or weaknesses that could be addressed. Thanks!

Thanks for the constructive feedback. We are glad that you found our work timely, valuable, and appreciated its clarity and insights.

---

W1 (Would a predictor trained on a meta-dataset of small datasets generalize?): We performed additional experiments, reported below. The algorithm selector is now trained with datasets of size <= 1k and used to select algorithms for datasets of size 2k and 3k. We see that the algorithm selector still accurately predicts suitable algorithms.

This concurs with our hypothesis that, by training on meta-dataset of datasets with a range of smaller sizes, the model can learn to generalize to larger datasets by identifying patterns of the algorithms' performance w.r.t data sizes. We already showed (Figure 3-right) that the variability in dataset size during training was critical.

(Numbers are algorithm-selection accuracy; higher is better)

---

W2 (Generalization to unseen shifts): Because of space limits, we refer to the response to Reviewer sPTX (Q4). We are adding an extended discussion of this important point to the paper.

---

W3 (large-scale evaluation): Agreed, all of these points are important considerations that deserve an entire dedicated publication. Automating OOD algorithm selection is a completely new take on OOD generalization, and the point of this study (as stated in the title) is to investigate the feasibility of such a radically different approach.

We concur that these are all very exciting extensions, including automating the extraction of useful dataset characteristics, and we are actively working on it.

---

W4 (compute-matched baseline): It is unclear what would be the amount of compute to match: we clarified in the paper that the whole point of training an algorithm selector is to amortize its cost in the long run. I.e. the selector is trained once to generalize to unseen datasets and shifts, as addressed in our experiments.

Comparison with ensemble, a baseline with much higher cost. In the paper, we compared baselines with similar costs to solve a downstream task. To address the proposed suggestion, we now additionally compare our method with an additional baseline of ensembling multiple methods predictions, whose compute requirement is multiple times higher than our method for each new downstream task. For space reasons, these new results are reported in the response to Reviewer FvV1 (Comment 3). Our method performs significantly better than this much more expensive one.

Regarding your comment on 'synergies', we additionally explored the combination of our method with ensemble-based methods -- using the predicted algorithm selection to adjust ensemble weights. We found that this strategy further improves in certain cases, albeit with a higher cost. Please again refer to the response to Reviewer FvV1 (Comment 3) for more details.

---

Q1 (different levels of meta-data): The results indiate that the predictor does not have such as bias. For example, in Figure 3-left, the comparison between ERM/Undersample (orange) shows that ERM outperforms Undersample in many cases even though the latter uses meta-data (i.e. spurious attribute labels). Prior work [1,2,3] already pointed out that ERM can outperform complex methods that use rich meta-data, which is part of the underlying motivation for our work.

[1] OoD-Bench: Quantifying and Understanding Two Dimensions of Out-of-Distribution Generalization, Ye et al.

[2] In Search of Lost Domain Generalization, Gulrajani et al.

[3] MetaShift: A Dataset of Datasets for Evaluating Contextual Distribution Shifts and Training Conflicts, Liang et al.

---

Q2 (measuring distribution shifts): We reworked this section, which should now be much clearer. In summary, for each sample in the training data of a dataset, we have class label and attribute (or domain) label annotated. Then:

• The bias of class label distribution indicates the degree of label shifts.
• The bias of attribute (or domain) label distribution indicates the degree of covariate shifts.
• The correlation of class labels and attribute (or domain) labels indicates the degree of spurious correlation.
• Why is it sufficient to use only training data to measure the distribution shift? Because we use an unbiased test set, then how biased a distribution is (to an unbiased one) directly reflects the degree of shifts.

---

Let us know if there are remaining questions or weaknesses that we could address. Thanks again!

Thanks for the thoughtful feedback. We are glad that you found our work novel and well presented.

---

Q1 (algorithm selection at test time): We simply pick the method with the highest logit (L159 right column), which corresponds to the one the model is the most confident in.

An alternative would be to use binary predictions, and if multiple algorithms are predicted to be suitable, randomly select one of them. Empirically, the former option (top logits) is much better. See below for new experiments comparing these options (worst-group error is shown, lower is better, and experimental setup is the same as Table 2 in the paper).

---

Q2 (loss function): Yes it uses the binary cross-entropy, we will make this clearer.

---

Q3 (dataset descriptor): Each component in the vector is either a real number (e.g. the degree of distribution shifts or the availability of spurious feature) or an integer (e.g. size of the dataset). We will make the definition clearer.

---

Q4: The answer is subtle but absolutely critical to understanding the value of our approach. The key innovation is (1) to lift the challenge from OOD generalization across specific shifts, to a meta level of generalizing across distributions of distribution shifts. And (2) to show that we can automatically sample semi-synthetic datasets (to train an algorithm selector) after choosing a realistic distribution of distribution shifts.

This is conceptually a completely novel approach to OOD generalization. While it is true (for any learning method!) that there is no guarantee of generalizing beyond the support of the training distribution, the training distribution in our approach encompasses a wide variety of shift types, magnitudes and their combinations, which can be densely sampled (point (2) above). We acknowledge that new shift types might require additional curation (we only claim that our approach should work a distribution of distribution shifts, as noted in section 2.1). We propose to state more clearly our assumptions and limitations to avoid any overclaiming.

OOD generalization on data sizes: However, we hypothesize that it is possible to generalize to OOD data size -- the algorithm selector has learned to generalize to larger data sizes, potentially by exploring the different data sizes available. In our response to Reviewer 9QSc (W1), we show that this is indeed the case. This is a case where the algorithm selector generalizes to OOD data.

---

Let us know if there are remaining questions or weaknesses that we could address. Thanks again!

Thanks for the insightful review. We are glad that you found the studied problem and insights interesting. We address the questions below and propose several improvements to the paper.

---

W1: No guarantee beyond the support of the training distribution:

Correct, this is true of any learning method. The subtle but important innovation is (1) to lift the challenge from OOD generalization across specific shifts, to a meta level of generalizing across distributions of distribution shifts. And (2) to show that we can automatically densely sample semi-synthetic datasets (to train an algorithm selector) within a distribution of realistic distribution shifts.

This is a conceptually novel approach to OOD generalization. We propose to state more clearly our assumptions and limitations to avoid any overclaiming.

Please also see the response to Reviewer FvV1 (Comment 1/2) regarding theoretical claims.

---

W2: Variety of covariate shifts: Thanks for pointing this out, we clarified section 3. In summary, we simulate changes in $P(X)$ by intervening on the domain distribution. Covariate shifts can indeed happen in many ways, but this simple approach is both tractable and generates realistic shifts (e.g. with image data, introducing more from an indoor domain in one dataset vs. more from outdoor in another dataset).

To simulate different degrees of covariate shifts, we draw samples with different distributions of attribute or domain labels. The variability covers the full range with a ratio of samples from any domain in $[0,1]$ (thus including severe shifts).

Please also see the response to Reviewer 9QSc (Q2) for a general view of section 3.

---

W3: Techniques for estimating covariate/label shifts:

We added to the paper a discussion of the literature devoted to this (e.g. [1]). To clarify, the estimation method we use applies to both label and covariate shifts: all it does is to infer sample-wise domain labels then use them to compute the estimated degrees of shifts.

[1] Unified View of Label Shift Estimation, Garg et al.

---

Q1 (arbitrary shifts): We will expand and clarify: if shifts were arbitrary, inductive reasoning and machine learning would not be possible [2,3] and the proposed approach also could not help. We only claim the possibility of training an algorithm selector that is effective on a distribution of distribution shifts, not on any possible shift.

[2] The Lack of A Priori Distinctions between Learning Algorithms, Wolpert

[3] Domain Adaptation under Target and Conditional Shift. Zhang et al.

---

Q2: Great suggestion - done.

---

Q3 (worst-group error): Agreed. We repeated our experiments and now additionally report the averaged-group error. The conclusions are similar to those in the paper.

(The experimental setup follows Table 2 for all new results.)

---

Q4 (spurious attributes): Our main experiments follow the setup from much of prior work on OOD generalization (domain generalization, spurious correlation, e.g. [4,5], and many more) which indeed assumes access to attribute labels. We also evaluate scenarios without such labels (Appendix E).

[4] In Search of Lost Domain Generalization, Gulrajani et al.

[5] Change is Hard: A Closer Look at Subpopulation Shift, Yang et al.

---

Q5 ($\epsilon$): We performed additional experiments. The method proves quite robust to other choices than the $\epsilon=0.05$ used in the paper (bold row). Intuitively, when $\epsilon$ is too big, the meta-dataset loses discriminative power; too small, it is subject to noise.

---

Q6 (comparison of pairs): This highlights the discrepancy in performance among methods under different shifts. Without this, there would be nothing to learn. E.g. the comparison of under-/oversampling (blue) shows that many datasets benefit specifically from one or the other.

---

Q7 (oracle selection): Yes.

---

Q8 ($\mathcal{G}_i$): Number of samples in group $i$ (defined L114, illustrated in Figure 2). We will make it clearer.

---

Q9 (ensembling): It is indeed possible. We tested two ensemble methods in response to Reviewer FcV1 (Comment 3).

---

We incorporated the above clarifications and improvements into the manuscript. Let us know if there are remaining questions or weaknesses that we could address. Thanks!