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

We thank the reviewer for their time and effort, and for acknowledging the advantages and new insights of our work.

W1. Requires more theoretical support.

The whole point of this paper is the possibility of going beyond existing theoretical characterizations of shifts and of assumptions of OOD algorithms. We will make this clearer in the paper. Many theoretical results have limited real-world applicability because the data often contains mixtures of different types of shifts, which cannot be easily characterized by theory. Our meta-learning approach turns algorithm selection into a supervised problem where classical results from statistical learning theory apply.

We also refer to prior work [1-4] (Section 5) that also used dataset characteristics as input for model selection with an empirical approach. The goal was then selecting among pretrained models, rather than OOD algorithms.

[1] Quick-Tune: Quickly Learning Which Pretrained Model to Finetune and How. Arango et al. ICLR 2024
[2] Zero-shot AutoML with Pretrained Models. Öztürk et al. ICML 2022
[3] TASK2VEC: Task Embedding for Meta-Learning Achille et al. ICCV 2019
[4] Model Spider: Learning to Rank Pre-Trained Models Efficiently Zhang et al. NeurIPS 2023

W2. Few datasets.

The CelebA and COCO were deemed the most suitable for the controlled, yet realistic experiments that would support our claims. As mentioned at L409, other datasets such as MetaShift have an insufficient number of samples per each group for creating resampled versions. We welcome suggestions from the reviewer and we will be happy to include additional evaluations in the final version of the paper.

W3. The performance of a model also depends on how well it is optimized on the dataset. Please provide specific details on the training process for each model, particularly whether the model’s parameters have been optimized.

Most of the algorithms we chose do not have multiple hyperparameters to be tuned, unlike other OOD generalization algorithms. Only GroupDRO has a hyperparameter and we keep it the default value as suggested by the original paper. For each algorithm, we keep the learning rate and batch size the same value after searching over a smaller set of datasets, and we run the algorithm long enough so that the convergence is ensured.

This whole procedure is valid because in practice one should not expect a sufficient number of OOD validation samples for hyperparameter search, otherwise why not just bypass OOD generalization by training on OOD validation samples? We will clarify in the paper, thanks for pointing out.

Q1. Advantages over ensemble?

Reasons against ensembles:

• Inefficient. This requires training and evaluating multiple models. Our approach predicts a single algorithm to train a single model on the target dataset.

• Do not address distribution shifts unless the majority of the models already make correct predictions. If most of the models used for output aggregation suffer from the same problem (e.g. a spurious correlation), aggregating their outputs does not help.

Thank you for your reply. However, I believe that for a purely experimental paper, more datasets (like iwilds, nico++), model types (like ensemble approach), and comprehensive testing are needed to reflect the paper's contribution. Therefore, I am maintaining the original score.

We thank the reviewer for the effort in reviewing our paper, and for the positive comments on the motivation and proposed solution.

W1 & W2: Choice of attributes. Need to know the attributes that are shifting a priori.

Most prior work on OOD generalization does assume some knowledge on the attribute that is shifting, or of some labels of a spurious attribute. Some of our experiments therefore follow this setting.

Taking a step beyond, we also provide experiments on scenarios where the shifting attribute is not known. Appendix E considers a practical setting where we assume no knowledge of the shifting attribute. We then perform a clustering in feature space to infer pseudo spurious attribute labels. Such ‘attribute pseudo-labels’ have been evaluated in prior work. Results in this setting indicate only a minor performance drop (Table 10).

W3. Why other baselines like Öztürk et al. cannot be compared to?

We compared with Öztürk et al. in both controllable experiments (Table 1) and real-world dataset experiments (Table 6). This is the strongest baseline we can compare to, since there is no prior work in selecting learning algorithms for OOD generalization.

Q1. How to construct a meta-dataset when the shift is not obvious or when the attribute is not labeled in the datasets?

There are two solutions provided in the paper, both supported with experiments.

• The meta-dataset can be constructed from an existing dataset (such as CelebA) or a synthetic dataset where the spurious attribute is known. In Section 4, we experimented with an algorithm selector trained on a meta-dataset built from CelebA, then evaluated on target datasets built from COCO. Results indicate generalization across domains. I.e. the algorithm selector can be trained on a meta-dataset (with known attributes) and reused on another domain. This is made possible by the choice of dataset descriptors that are relevant across domains.

• As mentioned above in this response, the spurious attribute can be inferred with a clustering method (Appendix E).

We propose to better highlight these results in the paper.

Q2. Does the coverage of the distribution over shifts impact results?

Yes, we believe the coverage of the distribution shifts would impact the results. In our experiments, we evaluate the algorithm selection on unseen datasets where either the types or magnitudes (or both) of distribution shifts are unseen when training the algorithm selector, and we observe that the algorithm selector generalizes well. The extent of this generalizability is an empirical question to be evaluated for different selectors' architectures, training objectives, etc.

Q3. Space required to store the meta-dataset?

The reviewer is correct that the search space is larger when we consider algorithms plus a few hyperparameters, which consequently makes the meta-dataset larger. The most straightforward way of mitigating is to use less fine-grained values for hyperparameters, which sacrifices the performance but reduce the storage required. This trade-off between performance and computation/storage budget is unavoidable in most if not all systems, but in our setting the storage is utilized efficiently since each entry of the meta-dataset is only a fixed-length vector.

We thank the reviewer for the effort in reviewing our paper, and for acknowledging the significance and practical value of this new problem.

W1. The three proposed methods are all based on existing simple techniques. No new insights into algorithm selection for different OOD problems.

There were no real insights about OOD algorithm selection in the existing literature. Mutliple works (L70-71) called the need for work on this topic as a future direction, but no advance had been made.

We claim as novel are:
(1) evaluating the feasibility of algorithm selection for OOD generalization;
(2) designing a proof-of-concept method (OOD-Chameleon).

As examples of novel insights, we show that:

• the algorithm selection is learnable in a data-driven way from a collection of datasets;
• the effectiveness of algorithm selection depends on the parametrization of the selector;
• there exist non-trivial relationships between data and algorithms that can't be captured e.g. by a linear model;
• the training of an algorithm selector with a classification objective is much more effective than a regression, even though the latter is conceptually more straightforward;
• examining the trained selector indicates which characteristics of a dataset make some algorithms preferred over others (Section 3.4).

None of these findings were obvious or simple, neither are the design and results of (2) above. We would like to know from the reviewer which exact contributions aren't novel enough or too simple, with precise references to prior work.

W2. Why is the problem learnable?

The algorithm selection is made learnable by turning it into a supervised problem, and learning from a collection of datasets. This meta learning approach turns the algorithm selection into a regime where classical results from statistical learning theory applies. We propose to make this clearer. Please also see the discussion in Section 2.1 ("Is the Selection of the Best Learning Algorithm Even Possible?") including the relevance of the no-free lunch theorem.

We also refer to prior works [1-4] (Section 5) on the analogous problem of learning-based selection of pretrained models (rather than OOD algorithms) that is also approache in an empirical and data-driven manner.

[1] Quick-Tune: Quickly Learning Which Pretrained Model to Finetune and How. Arango et al. ICLR 2024
[2] Zero-shot AutoML with Pretrained Models. Öztürk et al. ICML 2022
[3] TASK2VEC: Task Embedding for Meta-Learning Achille et al. ICCV 2019
[4] Model Spider: Learning to Rank Pre-Trained Models Efficiently Zhang et al. NeurIPS 2023

Q1 & Q2. How efficient is OOD-Chameleon?

The method is both time- and space-efficient.

• Time: the trained algorithm selector only takes the characteristics of the target dataset as input and directly predicts the suitable algorithm, and the algorithm selector is parametrized by MLPs.
• Space: each entry of the meat-dataset only consists of the dataset descriptor of size l, the one-hot algorithm vector of size M and the corresponding scalar OOD performance, which means the storage only grows linearly (this is most likely very light because l and M is a small to moderate constant).

We thank the reviewer for the effort in reviewing our paper, and for acknowledging the novelty of the problem (algorithm selection for OOD generalization).

W1.1. Using simple characteristics of the dataset and an algorithm represented by a one-hot vector does not really make sense.

These design choices are supported by prior work. See [1,2] about the analogous problem of selecting a pre-trained model to fine-tune on a target dataset. These works use even simpler characteristics of the dataset as input (e.g. number of classes and channels).

The choice of one-hot encodings to represent algorithms is an irrelevant implementation choice. The criticism misses the fact that the purpose of our approach is to learn about each algorithm from examples. For example, [1,2] also use one-hot encodings to represent pre-trained models. This choice may have been suboptimal because of possible known relations (e.g. similar architecture) that could have been encoded otherwise. This is not the case in our setting. We would like to know how the one-hot representations are problematic in the reviewer's eye to clarify this in the paper.

[1] Quick-Tune: Quickly Learning Which Pretrained Model to Finetune and How. Arango et al. ICLR 2024
[2] Zero-shot AutoML with Pretrained Models. Öztürk et al. ICML 2022

W1.2. Hyperparameters are ignored in this setting.

A straightforward extension is to include necessary hyperparameters (such as learning rate) to the search space (mentioned at L511), and then the algorithm selector is trained to predict the optimal algorithm along with its suitable hyperparameters.

W2. Experiments not sufficient to support the claims

We were very careful in making claims supported by concrete evidence. Hence we would appreciate a precise statement of the problematic claims from the reviewer, so as to tone them down or clarify the evidence in a revision.

The fact that more datasets/models/algorithms can be evaluated is always true. Remember that this paper introduces a new setting and a whole new take on the field of OOD generalization which has been stagnant for a couple of years.

We propose to clarify upfront (in the abstract) that the paper does not provide a new off-the-shelf solution. It opens a new research direction, and the main claim is about evaluating whether OOD algorithm selection is viable as a learning problem (cf. the title). Our experiments are designed to support this claim by using proven methods known to address specific types of distribution shifts, which are actually used in deployments of ML (not only in one-off academic papers).

The experiments are also designed to support our claims by using controlled conditions. The setups based on COCO and CelebA were deemed most suitable, but we welcome suggestions that we could add to the final version of the paper. Extensions to other algorithms/datasets are clearly stated as new avenues opened up by this paper.

Q1. Why is label shift required when shift on P(X) and P(Y|X) both exist?

The reviewer is correct that a shift in $P(Y)$ manifests indirectly in $P(X)$ or $P(Y|X)$. However modeling $P(Y)$ directly is preferred in practice for efficiency and clarity in the analysis and generation of data, when there is a need to focus on label distribution. See e.g. [3,4].

[3] Change is Hard: A Closer Look at Subpopulation Shift. Yang et al. ICML 2023
[4] A Unified View of Label Shift Estimation. Garg et al. NeurIPS 2020

Q2. Previously the spurious correlation is stated as shift of P(Y|X). However, if Xc is a subset of variables of X, and if there is no shift on P(Y|Xc), there should not be shift on P(Y|X) since P(Y|X)=P(Y|Xc).

The equality $P(Y|X)=P(Y|X_c)$ holds only if

• $X_c$ is sufficient for predicting Y (which is satisfied), and
• features in $X$ \ $X_c$ are conditionally independent of $Y$ given $X$ (which is not satisfied because $A$ is spuriously correlated with $Y$).

We will make this clearer in the paper.

Q3. In Equation 2, why is the positive correlation between y and a considered as spurious correlation, while the negative correlation is not considered?

We did consider it and defined the range appropriately in [0,1] (L203, below Equation 2).

We thank again the reviewers for their efforts. We used the feedback to improve the manuscript with additional experiments, clarifications and details, and we enhanced the overall readability. Major updates are in blue in the PDF:

• Additional training details;
• Clarification of the notations;
• Clarifications of the motivations;
• Rationale for the choice of algorithms;
• Clarification of limitations and avenues for future work;
• New experiments (Appendix F, Table 11) on more dataset (Colored-MNIST, for its sufficiency of samples in each group) in response to the ‘limited datasets’ weakness. The algorithm selector is trained on the meta-dataset constructed from CelebA and evaluated on 150 unseen datasets. These experiments further validate that the algorithm selector can be trained once on a meta-dataset of synthetic distribution shifts, and then reused on new unseen datasets.

We will be grateful to the reviewers for sharing whether our efforts have addressed their concerns, and improved their assessment of this work.