Set Valued Predictions For Robust Domain Generalization
Authors: Ron Tsibulsky
Daniel Nevo
Uri Shalit
Venue: ICML 2025 poster (2025)
Keywords: Set Valued Prediction
Domain Generalization
PAC Learnability
Primary area: general_machine_learning->transfer_multitask_and_metalearning
TL;DR: We develop a method for robust out-of-domain set-valued prediction, give theoretical performance guarantees, and show our method works well on several WILDS datasets

Abstract: Despite the impressive advancements in modern machine learning, achieving robustness in Domain Generalization (DG) tasks remains a significant challenge. In DG, models are expected to perform well on samples from unseen test distributions (also called domains), by learning from multiple related training distributions. Most existing approaches to this problem rely on single-valued predictions, which inherently limit their robustness. We argue that set-valued predictors could be leveraged to enhance robustness across unseen domains, while also taking into account that these sets should be as small as possible. 
We introduce a theoretical framework defining successful set prediction in the DG setting, focusing on meeting a predefined performance criterion across as many domains as possible, and provide theoretical insights into the conditions under which such domain generalization is achievable. We further propose a practical optimization method compatible with modern learning architectures, that balances robust performance on unseen domains with small prediction set sizes. We evaluate our approach on several real-world datasets from the WILDS benchmark, demonstrating its potential as a promising direction for robust domain generalization.

Set Valued Predictions For Robust Domain Generalization
Ron Tsibulsky' Daniel Nevo Uri Shalit
Abstract
the data the model was trained on (Nagarajan et al., 2020; Miller et al., 2020; Recht al., 2019). These distributions are referred to "domains", and the challenge of general- izing to domains unseen during training time is known as (OOD) generalization, or Domain Gen- eralization (DG) (Li et al., 20; Krueger et al., 2021). DG is especially important in high-stakes fields like medicine, where, for instance, a disease diagnosis system might be trained on data from specific group of patients, each with records from multiple visits to health centers, or multiple medical scans. Such system must be effective new patients for which it has no prior data. Moreover, beyond merely performing well on average, it is desirable that such a system provide robust performance across all new pa- tients, requiring worst-case performance guarantees across domains rather than average-case performance.
Despite the impressive advancements in modern machine learning, achieving robustness Do- main Generalization (DG) tasks remains a signif- icant challenge. In DG, models expected to perform well on samples from unseen test distribu- tions (also called domains), by learning from mul- tiple related training distributions. Most existing approaches to this problem rely on single-valued predictions, which inherently limit their robust- ness. We argue that set-valued predictors could be leveraged to enhance robustness across unseen domains, while also taking into account that these sets should be as small as possible. We intro- duce a theoretical framework defining success- ful set prediction in the DG setting, focusing on meeting predefined performance criterion across as many domains as possible, and provide theo- retical insights into the conditions under which such domain generalization is achievable. We further propose practical optimization method compatible with modern learning architectures, that balances robust performance on unseen do- mains with small prediction set sizes. We evaluate our approach on several real-world datasets from the WILDS benchmark, demonstrating its poten- tial a promising direction for robust domain generalization.
Recent efforts to address this challenge have focused on learning "stable" predictors that focus only on domain- invariant features, discarding information that might be domain-specific (Peters et al., 2016; Arjovsky et al., 2019; Heinze-Deml & Meinshausen, 2021; Veitch et al., 2021; Wald al., 2021). While these methods have made strides in maintaining stability across various domains, achieving this stability remains challenging, and sometimes infeasible (Chen et al., 2021; Kamath et al., 2021). Furthermore, stabil- ity often comes at the cost of sub-optimal and even poorly- performing predictors, as "overly stable" predictors might ignore valuable parts of the data (Rosenfeld et al., 2021; 2022; Zhao et al., 2019; Stojanov et al., 2021). As an illus- tration, disease diagnosis system that consistently achieves only 60% accuracy, despite being stable across different pa- tient populations, may not be practically viable.
1. Introduction
In recent years, Machine Learning (ML) methods, particu- larly deep neural networks (DNNs), have achieved remark- able success in various tasks, including language under- standing and image recognition. However, despite these advancements, many models struggle in real-world scenar- ios when the data comes from different distribution than
We propose an alternative approach for dealing with the considerable challenge of DG: employing predictors with set-valued outputs. Our set-valued framework for OOD problems recognizes that a key challenge in distribution- shift problems is the absence of a single, universally optimal prediction across all domains, as different domains induce different probabilistic relationships between features X and label Y. To handle these variations, our approach provides set-valued outputs that capture a range of potential relation- ships learned from the training domains. Such an approach is sensible for multi-domain settings, where expecting a single predictor to perform optimally across all domains
DDepartment of Computer Science, Tel Aviv University, Tel Aviv, Israel Department of Statistics and Operations Research, Tel Aviv University. Tel Aviv, Israel 'Department of Data and Decisions Science, Technion, Haifa, Israel. Correspondence to: Ron Tsibulsky <ront65 @ gmail.com>>
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Set Valued Predictions For Robust Domain Generalization
often impractical, yet worst-case performance guarantees still desirable.
2.2. Learning Objective
To formalize our learning objective, we first define a per- domain loss function [(h, e), which measures the perfor- mance of set-valued predictor h within a specific domain e. For set-valued predictors, the loss function should evaluate the coverage of the prediction set. Since set-valued predic- tors can be decomposed into per-label binary classifiers, it is natural to require that each of these classifiers performs well, especially when worst-case performance is desirable. For instance, in disease diagnosis it is crucial prioritize per-label recall for each y V avoid missed diagnoses. The following loss function captures this focus on per-label recall:
A useful set-valued prediction should not only include the correct label with high probability, it should idcally output small prediction sets. Consider a degenerate predictor that always predicts the entire label space y While it would always include the correct label, such a predictor will have no practical value. Therefore, is essential aim for predictor that achieves desirable performance level, while keeping the prediction set size to minimum. This obser- vation represents our learning objective: instead of seeking to maximize performance with a singleton set, we suggest targeting a predefined performance level while minimizing the prediction set size.
Crecaut e) max P.ly & h(X)YY = v/- BEY
To summarize, our contributions in the paper are as follows: In Section 2 we introduce learning paradigm for DG problems with set-valued predictors, where the goal is to achieve predefined coverage level across unseen domains. In Section we formulate and prove generalization bounds with respect to the above paradigm, giving conditions which guarantee robust performance on unseen domains.
Balancing this loss with the size of the prediction set ensures that set-valued predictors include each correct label Y when appropriate while refraining from including incorrect ones, ensuring that the prediction sets are both informative and concise. This balance mirrors the trade-off between recall and precision in single valued predictors.
In Section we propose practical methods for learning set- valued predictors within the above paradigm. Finally, in Section 5 we demonstrate the effectiveness of our proposed methods using real-world datasets from the WILDS benchmark (Koh et al., 2021).
The focus on recall loss for set-valued predictors is also adapted by other works set-valued predictors, such as Mauricio Sadinle & Wasserman (2019); Wang & Qiao (2018); Guan & Tibshirani (2022).
Returning to the disease prediction example, when devel- oping a model to predict diseases using data from multiple patients each with multiple visits, it is desirable that the model performs robustly on new patients, rather than merely perform well on average. To obtain this, we begin by defin- ing a performance indicator for loss function L. and a threshold as: (h, e) = 1[C(h, e) 2 7/. Our objective then becomes:
2. Multi Domain Set Valued Learning
2.1. Problem Setting
Consider features X E X, a label Y E Y,, and a domain e E & coupled with distribution P.. over (X) J. In this work, we focus on classification tasks, meaning )' is a known finite set. Let also D be a distribution over the set of domains E. This setting can be viewed as a meta-learning problem, where the data generation process is hierarchical, involving distributions at both the domain and instance levels.
min E Lc, min P [C(h, e) 2 7]. hEHe>D
heH enD
Achieving a zero objective implies that our predictor de- livers a satisfying performance (according to L, 7) across all domains. For example, with Creeatt loss, achieving an objective value of zero would mean our predictor achieves at least 1 - recall for all labels in V, across all domains. In practice, we aim for a low objective value, though not necessarily zero. With generalization bounds on
We assume that during training we observe set Etrain of m domains drawn according to D. From each domain E Erain, we observe a sample Se of ne instances, sampled according to Pe. This brings us to an overall sample S = UeEEraai S. of N = Ex= ne instances of (X,, Y., e.). At test time, we observe an instance X sampled from some domain étest (sampled according to D), which may differ from any of the training domains. We note that while we observe the value of e during training, it is neither required nor utilized at test time.
E e>D
(c,
Σ eb,) N eEE
1
we can bound the expected fraction of domains where pre- dictor does not deliver satisfying performance. A significant advantage of this approach is that it frames the robustness problem as mean optimization problem, allowing to lever- age established methods from classical ML and adapt them to the of VC dimension is presented in Section 3.
Throughout this paper we consider set-valued predictors. Such predictors take inputs from X, and output a subset of V. i. h: X - P()).
context. An example using the concept
2

---

Set Valued Predictions For Robust Domain Generalization
2.3. Related Work
minimizing E[1 (l) We argued that bounding EEED (h,, N E EeEEioon (h,, e)] will allow us to focus minimizing the empirical average of the perfor- mance indicator over training domains.
Set-valued predictions are well studied in the single-domain framework, often through the lens of conformal prediction widely used method for constructing set-valued predic- tions with a predefined level of coverage guarantee (Shafer & Vovk, 2008; Vovk et al., 2005); see also Section 4.2. In the single-domain scenario, Mauricio Sadinle & Wasser- man (2019) and Lei (2014) tackle the challenge of aiming at set-valued predictions with a pre-defined level of coverage, while keeping the prediction sets small. They present that challenge as constrained optimization problem and define its solution using acceptance regions, leveraging Neyman- Pearson Lemma to construct optimal regions.
This concept mirrors the way Probably Approximately Ac- curate (PAC) bounds provide a foundation for Empirical Risk Minimization (ERM) in classical ML (Shalev-Shward, & Ben-Davidd 2014). We therefore explore how classical machine learning tools can be adapted to the hierarchical structure of domains. In this section, we will formally define the concept of VC-dimension within our hierarchical frame- work and derive generalization bounds based on this defini- tion. While definitions and generalization bounds adapt nat- urally from classical MI to our setting, we show that the multi-domain set-valued context, even basic hypothesis sets like linear hypotheses, which have a finite VC-dimension in standard supervised learning, have infinite VC-dimension when no assumptions on & are made. Nevertheless, we also demonstrate that under certain assumptions on E, such hypothesis sets retain finite VC-dimension.
Wang & Qiao (2018; 2023a) tackle the same constrained optimization problem using support vector machines, build- ing another method for set-valued predictions in the single- domain scenario.
Dunn et al. (2018) suggest set-valued predictions for DG tasks, however they focus optimizing average risk over domains, instead of worst-case type risk as we do in our work. In addition, the work of Dunn et al. (2018) does not consider the size of the prediction set, and does not aim at small prediction sets.
3.1. VC-dim In Meta Learning - Definitions and Generalization Bounds
Wang & Qiao (2023b) also use set-valued predictions in OOD setting, continuing the work on support vector ma- chines for optimal set-valued predictions. However, they assume the conditional distribution P. [X is constant across domains, and specifically tackle OOD detection of unseen classes, when unlabeled data from the test domain is available. For this setting, they derive an empirical optimiza- tion problem similar to the one we derive for our setting, which is presented in section 4.1.
One of the classical results in the context of standard ML considers generalization of binary classifiers with regard to 0-1 loss 1 (x. y)). The La-1 loss serves as a measure for whether an hypothesis performs well on a data point (x, v). The VC-dimension quantifies the ability of an hy- pothesis set H. to exactly classify any subset of points from a finite set in X' x y. To adapt the idea of VC-dimension, and its implications on generalization, we start by replacing the Co-1 loss with the performance indicator 1 Ic,, (h, e) as the measure of how well an hypothesis h performs on domain e. Then, we define the VC-dimension such that it measures the ability of an hypothesis set H to perform perfectly on any subset of domains from a finite set in E.
Guan& & Tibshirani (2022) tackle an OOD problem with single train domain and single test domain, where unla- beled data from the test domain is available, and use confor- mal prediction to achieve per-label recall guarantee.
One work that approaches worst-case robustness in DG tasks with a single-valued predictor is that of Eastwood al. (2022) which suggests the Quantile Risk Minimization (QRM) method for minimizing the c-quantile risk among domains. This method is built upon an assumption that there exists a high-level distribution over the domains, same as we do in our work. However, the applicability of this method constrained by its reliance on single-valued predictions, which, as discussed in Section 1, can lead to suboptimal and degraded performance in certain domains.
Definition 3.1 (Shattering). Given hypotheses set H. a finite set C S E, loss function L, and threshold 7, we say that H shatters C with respect to L., 7 if for any subset č C C there exists h E H such that
e e - (c,(,)) =1 EEC'C - -CCC-+
+Icn = O.
Definition 3.2 (VC-Dimension). The VC-dimension of a hypothesis class H with respect to L, is the maximum size M such that there exists a set C' C E with |C| M that H can shatter with respect to L, 7. We denote it by V (H)
3. Generalization Bounds
In the previous section we introduced the concept of a performance indicator (2,,(h,c) c) measuring whether the predictor h gives satisfactory performance in do- main (w.r.t. 7,,), and set forth the objective of
Definition 3.3 (Uniform Convergence). We say that a hy- pothesis class H. has the uniform convergence property with respect to loss function and threshold y if, for ev- ery d,c E (0, 1), there exists an integer m(5, <) such that
3

---

Set Valued Predictions For Robust Domain Generalization
for every distribution D over &, if S c & is sample of |S] > m(ō, e) domains drawn i.i.d according to D, then, with probability at least 1 - å (over the sample of S) the following holds:
3.2. Failure To shatter By Linear Hypotheses Set
In the following sections, we will consider hypothesis sets of set-valued predictors. These predictors can be defined using [ binary classifiers by X {0, for y ) in
the following manner: h(x) = {v E h2(X)) (X)= = 1}. If
each hy adheres to a particular structure (e.g., hy is a linear classifier), we say that h possesses this structure.
vh E H:
E en D
(b,e)]]
Even(he Se. |S]
1
.ES
We demonstrate the divergence between classic supervised learning and example of linear hypotheses sets. In the classical sense of shattering, a linear hypotheses set cannot shatter more than d + points "Shalev-Shwarte & Ben-David, 2014), thus having a finite VC dimension. However, in the multi-domain set-valued setting, without imposing structural assumptions on the domains in E, the finiteness of the VC dimension depends on the dimensionality d.
set-valued learning using the
Theorem 3.4. A hypothesis class H has the uniform con- vergence property with respect to a loss function C and threshold 7 if and only if V C, (H) < co. More- over. = VCdimg,, (H) < oo, the sample size from the uniform-convergence definition is m(0,e) e) = e ((
Theorem 3.4 is proved in appendix A. and provides way to derive generalization bounds for the hierarchical setting by demonstrating finite VC-dimension for hypothesis class H. analogous to how the VC-dimension is used in classical machine learning. While Theorem 3.4 closely mirrors classical VC-dimension theory, its proof requires special care due to two key differences from the standard setting. First, instead of using the 0-1 loss on individual data points, we work with a performance indicator 1 1t,y (h,,(h,e) e) that measures whether a hypothesis achieves satisfactory performance entire domain Second, classical results apply to distributions over input-label pairs X' {0, 1). whereas our setting involves distributions over domains E, which are more complicated objects. These differences necessitate a careful adaptation of the uniform convergence argument, including a mapping to derived hypothesis class over & {0, to apply classical VC theory. Further details outlined in appendix A.
Theorem 3.5. For d 1, linear H. cannot shatter more than 2 2| domains with respect to Frecalt and any < % < 1.
According to Definition 3.2 this means that for linear H and d = 1, we have V VCCdim C.imma..att (H) S 2/)/ Proof for theorem 3.5 is given in appendix A.2.
Theorem 3.6. For d > 1, and any size m, there exists a set of m domains that can be shattered by linear hypotheses H with respect to Creeatt and any < 7 <.
According to Definition 3.2 this means that for linear H. and d 1, we have VCdim Crecati by (H) co.
Proof for theorem 3.6 is given in appendix A.3.
3.3. Imposing Restrictions on 3
The previous results may seem discouraging, as an infinite VC-dimension suggests that generalization from observed to new domains via uniform convergence is impossible. How- ever, when real-world data is collected from various environ- ments, it is reasonable to assume that the Data Generation Processes (DGP) of these environments share some com- mon structure. Thus, we examine cases where restrictions are placed on E. Following Wald al. (2021); Rosenfeld et al. (2022) we examine the assumption that all domains in E are conditionally Gaussian:
Proving finite VC-dimension for certain hypothesis sets in the hierarchical context with the Creeatt loss requires assumptions on the structure of ε, as we show in sections 3.2 and 3.3. This is unlike standard results in the classic framework, where assumptions on the inputs are usually not required. Informally, this difference can be seen as stemming from the fact that the space of all domains is of in- finite dimension, while in the classical framework inputs are typically considered to belong to dimeensooaa space. In accordance with that, the restrictions on & that we ex- plore in section 3.3 limit the domains to a fiite-dimensional subspace.
Ve E E Vy y [X N(He.g Ee,y)-
While the previous subsection shows negative results for learnability when there are restrictions the domains, the following result suggests that with some restrictions as mentioned above, learnability is possible with sufficient training domains.
In this section, we focus on generalization from training domains to new, unseen domains. We do not address gener- alization within individual domains, which can be viewed as effectively assuming an infinite sample size for each domain. In appendix B, we provide a comprehensive analysis of both the number of domains required for effective generalization and the sample size needed within each domain.
Theorem 3.7. If domains are restricted to being Condition- ally Gaussian, and there exist Vyey Ey E Bddd such that for each e, y Eeey = Ge.y F.y for some de.y E R, then for
4

---

Set Valued Predictions For Robust Domain Generalization
each e, > O there exist m = e (DDF"aatogg())/)))) such that if (trriai Z m then with probability higher than 1 1-6 5 over the training domains sample Etrain and regardless of
(i Se : Y== y}. and Gy (i 8 Y, y) UcEErraw Gay.
the distribution D over & for any linear hypothesis h
4.1. SET-COVER: Optimized Set Prediction
Our goal to minimize prediction set size while maintaining the required min-recall level. We formalize the following constrained optimization problem:
VeEErrain Er e) = - IE
C eh] S.
The proof is provided in Appendix A.4, building on Theo- rem3 3.4.
1 Σ [b(x,)]
min NEH
N iES
Theorem 3.7 provides a rigorous justification for seeking linear predictor h H that achieves Creeatt e) < Y for each E Etrain- In the next section, we will intro- duce practical methods to find such predictors h, while also considering the efficiency of the set sizes generated by h.
Σ s.t. GGayl iEGn.v
1/v ((X)) S Ve E Eirain Vy E V
Since [k(X)]= [[0]1=Eyee Eyey (X). this problem can be solved for each label y individually:
1 min 1 WEH
h)y(X,)
While the result of 3.7 is strictly valid for linear predictors, we experimentally evaluate its applicability to neural net- works.
N
Σ s.t Go.yl iEG..y
(X,) = 0J S Ve Etrain (I)
In addition, a limitation of Theorem 3.7 lies in its assump- tion that for each label E y. the Gaussian DGPs across all domains share the same covariance structure, up to a scaling factor de.y- In Appendix E.3, we empirically demonstrate that generalization achievable even without this assump- tion. Specifically, we report the results of experiments on synthetic data with Gaussian DGPs that feature separate random covariance matrix for each domain. Additionally, in Section 5.2 we empirically evaluate the generalization capability of our proposed method (introduced in the next section) to new domains with complex DGPs using real- world datasets.
Problem is non-smooth and becomes computationally in- tractable for high dimensions and large datasets. To leverage standard gradient- caudentt-based optimization methods, we introduce a relaxation of the optimization problem along with a pa- rameterization of the predictor. Suppose the hypothesis class H. is parameterized by 0 E RR (where q may differ from the feature dimension d), such that (X) if and only if (X) 0. This leads us to the following relaxed optimization problem:
min 11
max 1+ 1, (X.))
EES
4. Practical Optimization Methods
s.t Ve E
max 10 (1)()))(())) ST. (2)
In previous sections we discussed the necessity of finding set-predictor h that consistently delivers satisfactory per- formance across all training domains, as measured by a loss function C(h, e), while also minimizing the size of the pre- diction set. In this section, we introduce our method, SET Coverage Optimized with Empirical Robustness (SET- COVER), which addresses this dual objective. In addition, we present series of baseline predictors that leverage con- formal prediction for DG.
Ge LEG..v
In appendix we provide detailed derivations for this re- laxation and show that its objective is a surrogate for the objective of problem (I), and that its constraints are also surrogate for those in the original formulation. We note
that Wang & Qiao (2023b) derive a similar optimization problem for a setting of OOD class detection with two do- mains.
To ground our discussion, we will focus on the per-label recall metric as our performance criterion, continuing the earlier discussion on disease diagnosis system. However, the methods we develop can be naturally extended to other per- formance metrics. Throughout the next sections will call this metric "min-recall", since achieving required recall level for all labels simultaneously implies that the minimum recall across labels meets the required threshold.
We solve problem 2 by introducing Lagrange multipliers C R and define the Lagrangian:
(0, Σ
max 1 A
Σ Caw
max 10, 11, -7) 1=,(x:))>7)
eEErrain
iEG
We begin by introducing some key notations. Given a training dataset UceEvaac Se, we define: Ge,y
Gradient descent can then be performed on 8, combined with a gradient ascent on C.
5

---

Set Valued Predictions For Robust Domain Generalization
To optimize 0, we focus on the relevant part of the La- grangian:
to train a base model and its predicted logits "con- formal scores" measure of how well input features X relate to each of the labels in V. Then, a calibration pro- cess produces thresholds for these conformal scores, so that prediction sets that include labels for which the conformal scores fall within these thresholds guarantee a certain level of marginal coverage (Shafer & Vovk, 2008; Vovk et al., 2005). Conformal predictors have been widely used for providing set-valued predictions in single-domain settings, offering marginal coverage guarantees (Lei et al., 2013; Fontana et al., 2023).
Ly(0, max 1 (x(()+
Ce.a GooMl iEG..V
max 1 1111--g(X0 (X:))
eE
This can be simplified further by absorbing the |..اा fac- tor into Co.y. resulting in the following loss function for optimizing 8:
Ly(0, = Σ max 1 +x))+
1.2.1. ROBUST CONFORMAL FOR DOMAIN GENERALIZATION
iES
We suggest an adaptation of conformal prediction to pro- vide robust performance across domains, calling it Robust Conformal Prediction:
LigGan C -11
Fitrain
For wrong classification, the above loss will punish the predictor h. For correct classification, the second term will not punish it, but the first term will do (specifically for true positives). We found during experimentation that changing the first term to punish only wrong classifications helps stabilizing the learning process (Further details are given in Appendix E.6.2). Therefore we further adjust the loss to be
We first train a single classifier on the pooled data from all training domains and use its output logits as conformal scores for each label separately. We denote this as f(x (f. (z))
For each training domain separately, we calibrate thresholds so that conformal scores within these thresh- olds provide the desired coverage in that specific do- main. To achieve 1 7 recall for each label in ) and for each training domain, we define the following set of thresholds:
Ly(
Σ ma 10 hg(x)))
igG
Σ LiEG EE Etrain
(0, 1 h1, (X.)).
te.y = inffa |Ge.yl iEG..v
Σ [[(((x,) > 2
To optimize C, we suggest updating it once every few batches (the frequency is treated as a training hyper- parameter) and at the end of each epoch. The updates are aimed to increase Ce,y when the recall of iy in domain and label y is lower than 1 --,, and decrease Ce,y otherwise. The implementation details of these updates are outlined in Algorithm 1 (in Appendix D).
At prediction time, a label is added to the prediction set if its conformal score exceeds the threshold in any of the training domains:
(X,) = max.e 1[f(Xi) > te
4.2.2. POOLING CDFs
Dunn et al. (2018) proposed Pooling- for regression tasks, DG approach based on conformal prediction. Unlike robust conformal methods, Pooling-CIFFs aims achieve average coverage across domains. In Pooling-CUI MDiinng--DFss base model is trained on a pooled training data, gathered from several training domains. Then, the calibration is done on calibration data, gathered from different calibration domains, and thresholds are calculated to provide an average coverage guarantee across domains.
We call this approach SET Coverage Optimized with Empir- ical Robustness (SET-COVER) and outline it in Algorithm 1 (in Appendix D). In Section 5 we demonstrate the effec- tiveness of this algorithm through experiments on synthetic and real-world data.
4.2. Conformal Prediction Baselines
To evaluate the performance of SET-COVER we present several set-prediction baselines that extend conformal pre- diction to DG and compare SET-COVER to them. Confor- mal prediction models have gained popularity in recent years for providing well-grounded prediction sets with strong marginal coverage guarantees (Gibbs& & Candes, 2021; Ro- mano et al., 2020; Tibshirani et al., 2019). The central idea behind conformal prediction for classification tasks is
For our experiments, we adapt Pooling-CDF's to our min- recall objective by calculating thresholds for each label individually, aiming for 90% recall across domains. Addi- tionally, we test a variant that performs both training and calibration on the full dataset available during training. We call this variant Pooling CDFs - Train Calibration (TrainC), and the original variant we call Pooling CDFs Cross Vali-
6

---

Set Valued Predictions For Robust Domain Generalization
dated Calibration (CVC).
Heinze-Deml & Meinshausen (2021)'s original setup, where invariant features alone sufficient for optimal predic- tion, we adjusted the data generation process, ensuring that ignoring variant features would lead to a decline in perfor- mance.
5. Experiments
We conduct several experiments to evaluate the performance of five different approaches to the problem of DG. In line with the setup presented in previous sections, we aim to achieve 90% recall for each label and each domain, while keeping the prediction set size as small as possible. We evaluate the following predictors:
The DGP is as follows:
Zr ~ U UlMow Whight
Y ~ Bernoulli (0.5)
X ~ Y + Zov) + (0,
ERM: We train Neural Network (NN) to make single- valued predictions by minimizing a cross-entropy loss across the entire shuffled training dataset. This method represents the conventional method for training and deploying machine learning models.
where M, R
We experiment with d = 10, 50. For all methods we used a 2-layer multi-layer perceptron (MLP) as the base architec- ture. See details in Appendices E. and E.2.
Pooling CDFs (TrainC) and Pooling CDFs (CVC): We implement the two variants of Pooling CDFs described in section 4.2.2, building on the ERM classifier as the base model.
The results Figure I consistently show that both the robust conformal method and the SET-COVER method achieve the required coverage in test domains. As expected, the SET- COVER approach maintains a smaller average prediction set size.
Robust Conformal: We implement a robust conformal pre- dictor as described in Section 4.2.1, again building on the ERM classifier as the base model.
ard-tet
SET-COVER: We train NN using the optimization pro- cess outlined in Section 4.1, with the aim of producing model with a small prediction set size while maintaining the desired coverage.
6.55
6.00
0.55
5.00
Evaluating set-valued predictions presents challenges since models need to balance coverage with prediction set size. It also complicates model comparisons because it unclear which metric should be prioritized. We choose to tackle this by presenting the following comparisons. First, compare models on two key aspects: (1) the average size of prediction sets and (2) the minimum recall per domain. We visualize these results using cross-plots where the y-axis represents min-recall, and the x-axis represents average set size. Each cross shows the median and the 25th and 75th percentiles for both metries across domains, as shown in Figures 1 and 2. Additionally, we present in Table 1 the percentage of domains achieving at least 90% min-recall, which is our predefined performance target. All our experiments in this section are repeated with five different random seeds, with results averaged across the seeds.
CER acaing 129 10V0 Sescowe
Pool2 POORI CORE IOST SercOveR
0/0
Any
(a) 50d
(b) 10d
Figure I. Min Recall distribution VS Mean Set Size distri- bution. Blue represents ERM predictor, Orange represents Pooling CDFs (TrainC), Grey represents Pooling CDFs (CVC), Green represents robust conformal predictor, and Pink represents SET-COVER, The horizontal solid line represents the 90% recall target value.
In Appendix E.3 we conduct experiments on a similar DGP where the covariance matrices vary randomly across do- mains. The results show that the performance of the models, including SET-COVER, remains stable even with domain- dependent covariance.
While the experiments in this section compare mainly set predictors (with ERM as the singleton-predictio baseline), in Appendix E.5 we also compare SET-COVER to few com- mon singleton-prediction OOD baselines.
5.2. WILDS Data
We evaluate set-valued models on benchmarks from the WILDS (Koh et al., 2021) suite of benchmarks, which is designed to test models against real-world distribution shifts across various datasets and modalities. The benchmarks we use include:
5.1. Synthetic Data
We first evaluate our proposed methods on synthetic data. We follow data generation process proposed by Heinze- Deml & Meinshausen (2021), that incorporates both in- variant features, i.c. features that do not depend on the domain, and domain-dependent features. However, unlike
Camelyon (Bandi et al., 2018): This dataset consists of pathological scans from 43 patients across hospitals. Each
7

---

Set Valued Predictions For Robust Domain Generalization
scan is divided into thousands of patches, each labeled
Table I. Summary of OOD Results Wilds Datasets
if it contains tumor and O otherwise. Patients treated
Camelyon
domains, and the task of predicting whether tumor appears in patch (an image) is a binary classification.
Model
Median Min Recall f
Median
Recall 2 90%
FMoW (Christie et al., 8): A satellite image dataset categorized by different land or building use types. Images come from different geographic areas and years, with each area-year pair defining domain. We focus on the three most prevalent categories, constructing a multi-class classi- fication task.
Avg Size J
Petg
ERM
0.93 = 0.04
1.0 0
0.63 + 0.11
CDF Pooling-
0.88 = 0.03
1.07 + 0.15
0.45 + 0.10
(TrainC)
CDF Pooling-
0.81 = 0.14
1.24 + 0.17
0.33 + 0.19
WWildCam (Beery et al., 2020): This dataset includes im- ages of animals in the wild, taken from different locations, with the locations defining the domains. We again focus on the three most prevalent classes. The original images in- clude frame that reveals its domain, we crop the images discard these frames.
(CVC)
Robust Conformal
0.98 = 0.01
1.79 0.16
0.93 0.05
SET-COVER
0.96 + 0.03
1.05 0.03
0.71 0.14
FMoW
Amazon (Ni et al., 2019): A dataset of textual reviews, each is associated with star rating from to 5. The reviews are written by different reviewers, each has multiple reviews in the dataset. Each reviewer is considered a different domain, and the task to predict the star rating of a review, ic a multi-class classification task.
Model
Median Min Recall 1
Median
Recall 2 90%
Avg Size J
Petg
ERM
0.76 = 0.06
1.0 0.00
0.08 0.06
CDF Pooling-
0.81 + 0.01
1.01 + 0.05
0.07 1 0.04
(TrainC)
We discard data instances if they come from any (domain, la- bel) pair with less than 100 samples. For Camelyon, FMoW, and iWildCam data sets, we use a pre-trained ResNet- 18 network (He et al., 2016), fine-tuning it on the training set. For the Amazon dataset we use the embeddings of a pre-trained Bert (bert-base-une base---e--nn) model (Devlin et al., 2018) to calculate average embedding of the input text, and then pass it through 2-layer MIP. All training composed of randomly sampled instances from randomly sampled domains, and for all data sets the methods are eval- uated on unseen test domains. Further experimental details are available at Appendix 1. Training time comparisons are provided Appendix E.6.3.
CDF Pooling-
0.83 + 0.03
1.10 + 0.02
0.23 + 0.10
(CVC)
Robust Conformal
0.89 = 0.01
1.17 0.07
0.43 + 0.15
SET-COVER
0.91 + 0.02
1.10 1 0.04
0.72 1 0.22
iWildCam
are
Model
Median Min Recall f
Median
Recall > 90%
Avg Size J
Petg
ERM
0.99 + 0.00
1.0 + 0.00
0.71 + 0.03
CDF Pooling-
0.92 + 0.03
0.92 0.03
0.53 + 0.06
(TrainC)
Results Figure 2 and Table show consistently that both the robust conformal predictor and the SET-COVER pre- dictor improve coverage in test domains, compared to the other methods. Furthermore, SET-COVER maintains sig- nificantly smaller prediction set size compared to the ro- bust conformal predictor. These results suggest that the SET-COVER method might be a promising step towards an efficient set-valued domain generalization.
CDF Pooling-
0.99 + 0.01
1.14 0.12
0.73 0.06
(CVC)
Robust
0.99 + 0.01
2.00 + 0.63
0.86 + 0.07
Conformal
SET-COVER
0.99 + 0.00
1.01 0.02
0.82 + 0.09
Amazon
Model
Median
Median
Recall 90%
Min Recall f
Avg Size +
Petg 1
ERM
1.0 + 0.00
1.0 + 0.00
0.68 + 0.06
CDF Pooling-
0.94 = 0.01
4.31 + 0.17
0.63 + 0.02
(TrainC)
CDF Pooling-
0.99 + 0.00
2.48 + 0.53
0.70 + 0.06
(CVC)
Robust
1.0 + 0.00
4.68 0.28
0.99 0.00
Conformal
SET-COVER
1.0 0.00
2.43 0.09
0.96 0.02
8

---

Set Valued Predictions For Robust Domain Generalization
ing the reliability of machine learning systems in critical real-world settings.
1.2
033
As this paper presents work whose goal is to advance the field of Machine Learning, there are many potential socictal consequences of this work, none which we feel must be specifically highlighted here.
305
0.02
275
6.5
IMM Peaing LIF X013 anscown
Foe sriinggo camnoOo
130
References
1430 120 5050 Lan: Lid: site Las 120
Arjovsky, M., Bottou, L., Gulrajani. I., and Lopez- Paz, Invariant risk minimization. arXiv preprint arXiv: 1907 0907002893, 2019.
(a) Camelyon
(b) FMoW
Bandi, P., Geessink, O., Manson, Q., Van Dijk, M., Balken- hol, M., Hermsen, M.. Bejnordi, B. E., Lee, B., Paeng, K., Zhong, A., et al. From detection of individual metas- tases to classification of lymph node status at the patient level: the camelyon17 7 challenge. IEEE Transactions on Medical Imaging, 2018.
(Tanc) PaKlng CIP-
Pokinn (TANCI
SEECOVE
Beery, S., Cole, E., and Gjoka, A. The iwildcam 2020 competition dataset. arXiv preprint arXiv:2004. 103400. 2020.
(c) iWildCam
(d) Amazon
Figure 2. Each figure represents Min-Recall Avg Set Size cross. y-axis represents min-recall, and x-axis represents average set size. Fach cross shows the median and the 25th and 75th per- centiles for both metrics across domain. Blue represents ERM predictor, Orange represents Pooling CDFs (TrainC), Grey repre- sents Pooling CDFs (CVC), Green represents robust conformal predictor, and Pink represents SET-COVER. The horizontal solid line represents the 90% recall target value, and dashed yellow di- agonal line represents performance of a random predictor.
Chen, Y., Rosenfeld, E., Sellke, M., Ma, T., and Risteski, A. Iterative feature matching: Toward provable domain generalization with logarithmic environments, 2021. URL bttps://arxien org/ wtwpr//////////eea/e 2106 09913.
Christie, G., Fendley, N., Wilson, J., and Mukherjee. R. Functional map of the world. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, 2018.
Devlin, J., Chang, M., Lee, K., and Toutanova, K. BERT: pre-training of deep bidirectional transformers for lan- guage understanding. CoRR, abs/1810.04800 2018.
Reproducibility Code
We release all code and evaluation scripts at https: / //gittubs com/ hottt/ootoft 65/ -aalvaalede sed to facil- itate reproducibility.
Dunn, R., Wasserman, L., and Ramdas, A. Distribution-
free prediction sets with random effects. arXiv preprint
2018.
Acknowledgments
We would like thank the anonymous reviewers of the paper for their helpful comments and suggestions. RT and US were supported by ISF grant 2456/23, RT and DN were supported by ISF grant 827/21.
Eastwood, C., Robey, A., Singh, S., Von Kügelgen, J., Has- sani, H., Pappas, G. J., and Schölkopf, B. Probable do- main generalization via quantile risk minimization. Ad- vances in Neural Information Processing Systems, 35: 17340-17358 2022.
Impact Statement
Fontana, M., Zeni, G., and Vantini, S. Conformal prediction: a unified review of theory and new challenges. Bernoulli, 29(1): 2023.
This work proposes a novel approach to Out of Distribution (OOD) generalization by introducing set-valued predictors to tackle the challenges of domain shifts. The proposed method emphasizes robust, worst-case performance guaran- tees across unseen domains, which is crucial for high-stakes applications like healthcare. By advancing the understand- ing of domain generalization and providing practical tools for set-valued prediction, this research contributes to improv-
Gibbs, I. and Candes, E. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 34: 1660-1672, 2021.
Guan, L. and Tibshirani, R. Prediction and Outlier Detection in Classification Problems. Journal of the Royal Statis-

---

Set Valued Predictions For Robust Domain Generalization
lical Society Series B: Statistical Methodology, 84(2): 524-546, 02 2022. ISSN 1369-7412. doi: 10.1111/rssb. 12443. URL htttp:://do..org/111// 12443.
1395341. URL https: /tt::://dooiio http///ti..oo.g///////o/// 1080/ 11621499.2077.13522
Miller, J., Krauth, K., Recht, B., and Schmidt, L. The effect of natural distribution shift on question answering models. In International conference machine learning, pp.
Gulrajani, I. and Lopez-Paz, D. In search of lost domain generalization. arXiv preprint arXiv:2007.01444 2020.
PMLR, 2020.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual leam- ing for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), June 2016.
Nagarajan, V., Andreassen, A., and Neyshabur, B. Under- standing the failure modes of out-of-distribution general- ization. arXiv preprint arXiv:2010. 15775, 2020.
Ni, J., Li, and McAuley, J. Justifying recommendations using distantly-labeled reviews and fine-grained aspects. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Pro- cessing MOMNLP-IJCNLP) 2019.
Heinze-Deml, C. and Meinshausen, N. Conditional variance penalties and domain shift robustness. Machine Learning,
110(2):303-344 -48. 2021.
Kamath, P., Tangella, A., Sutherland, D., and Srebro, N. Does invariant risk minimization capture invariance? In International Conference Artificial Intelligence and Statistics, pp. 0069-4077.6 PMLR, 2021.
Peters, J., Bühlmann, P., and Meinshausen, N. Causal in- ference by using invariant prediction: identification and confidence intervals. Journal of the Royal Statistical So- ciety Series B: Statistical Methodology, 78(5):947-1012, 2016.
Koh, P. W., Sagawa, S., Marklund, H., Xie, S. M., Zhang, M., Balsubramani, A., Hu, W., Yasunaga, M., Phillips, R. L., Gao, I., Lee, T., David, E., Stavness, I., Guo, W., Earnshaw, B. A., Haque, I. S., Beery, S., Leskovec, J., Kundaje, A.. Pierson, E., Levine, S., Finn, C., and Liang. WILDS: benchmark of in-the-wild distri- bution shifts. In International Conference on Machine Learning (ICMI., 2021.
Recht, B., Roelofs, R., Schmidt, L., and Shankar, V. Do imagenet classifiers generalize to imagenet? In Interna- tional conference on machine learning, pp. 5389-5400 PMLR, 2019.
Romano, Y., Sesia, M., and Candes, E. Classification with valid and adaptive coverage. Advances in Neural Infor- mation Processing Systems, 33:3581-3599 2020.
Krueger, D., Caballero, E., Jacobsen, J.-H., Zhang, A., Bi- nas, J., Zhang, D., Le Priol, R., and Courville, A. Out-of- distribution generalization via risk extrapolation (rex). In International conference machine learning, pp. 5815- 5826. PMLR, 2021.
Rosenfeld, E., Ravikumar, P., and Risteski, A. The risks of invariant risk minimization, 2021. URL https:// arxiv, orgoorgg//aoooo hbs///b///// 2000 05761.
Lei, J. Classification with confidence. Biometrika, 101(4): 755-769, 2014. ISSN 00063444. URL http:// www. jstor. wtt.staeeee333030
Rosenfeld, E., Ravikumar, P., and Risteski, A. Domain- adjusted regression or: Erm may already learn features sufficient for out-of-distribution generalization, 2022. URL https::////...... arxiv. wttp/ors/222.....22.oooo 06856.
Lei, J., Robins, J., and Wasserman, L. Distribution-Fe free prediction sets. Journal of the American Statistical Asso- ciation, 108(501):278 227788287711188 2013.
Shafer, G. and Vovk, V. A tutorial on conformal prediction.
Journal of Machine Learning Research, 9(3), 2008
Li, D., Yang, Y., Song, Y.-Z., and Hospedales, T. Learning to generalize: Meta-learning for domain generalization. In Proceedings of the AAAI conference artificial intel- ligence, volume 32, 2018a
Shalev-Shwartz, S. and Ben-David, S. Understanding Ma- chine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014. ISBN 1107057132.
Stojanov, P., Li, Z., Gong, M., Cai, R., Carbonell, J., and Zhang, K. Domain adaptation with invariant representation learning: What transformations to learn? In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, vol- ume 34, pp. 24791-24803. Curran Associates, Inc., 2021. URL
Li, H., Pan, S. J., Wang, S., and Kot, A. C. Domain general- ization with adversarial feature learning. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 5400-5409, 2018b.
Mauricio Sadinle, J. L. and Wasserman, L. Least am- biguous set-valued classifiers with bounded error lev- els. Journal of the American Statistical Association, 114(525):233-23, 2019. doi: 10.
newrips...ppp. cc/paper Saapper_fileespppee/222220
10

---

Set Valued Predictions For Robust Domain Generalization
2 Paper. pdf.
Sun, B. and Saenko, K. Deep coral: Correlation alignment for deep domain adaptation. In Computer Vision-ECcV 2016 Workshops: Amsterdam, The Netherlands, October 8-10 and 15-16, 2016, Proceedings, Purt III 14, pp. 443-
450. Springer. 2016.
Tibshirani, R. J., Foygel Barber, R., Candes, E., and Ramdas, A. Conformal prediction under covariate shift. Advances in neural information processing systems, 32, 2019.
Veitch, V., D' Amour, A., Yadlowsky, S., and Eisenstein, Counterfactual invariance to spurious correlations in text classification.. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 16196-16208. Curran Associates, Inc., 2021. URL cc httpppe_fflleepeprrr/00////ee1e hteef//lhabbaaafaaaeeeeeeee63--3 pdf.
neuriss.
Vovk, V., Gammerman, A., and Shafer, G. Algorithmic learning in random world, volume 29. Springer, 2005.
Wald, Y. Feder, A., Greenfeld, D., and Shalit, U. On calibration and out-of-domain generalization. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang. P. and Vaughan, W. (eds.), Advances in Neural Information Processing Systems, vol- ume 34, pp. 2215-2227. Curran Associates, Inc., 2021. URL https://proceednng/ neurips. oc /ttppeee..lllee/pppr//////////// 11 11B65300331000c02256666633333223 pdf.
Wang, W. and Qiao, X. Learning confidence sets using support vector machines. Advances in Neural Information Processing Systems, 31, 2018.
Wang, W. and Qiao, X. Set-valued support vector machine with bounded error rates. Journal of the American Statis- tical Association, 118(54))2847-28555 2023a.
Wang, Z. and Qiao, Set-valued classification with ouittf-distribution detection for many classes. Jour- nal of Machine Learning Research, 24(375):1-39, 2023b. URL http:// jmmr..mr..../ http:://ml...oo//pppptte/////// ottpppapers/v24/ 23- 0712 2. htmm....html.
Zhao, H., Des Combes, R. T., Zhang, K., and Gordon, G. On learning invariant representations for domain adapta- tion. International conference on machine learning, pp. 7523-7532. PMLR, 2019.

---

Set Valued Predictions For Robust Domain Generalization
A. Proofs For Theoretical Claims
A.1. Proof of Theorem 3.4
The definitions we provide for uniform convergence and shattering in the multi-domain setting differ slightly from those in classical machine learning. First, in classical ML, the connection between VC-dimension and uniform convergence is typically defined with respect to the 0-1 loss, whereas in our case, it is defined in terms of performance indicator. Second, while classical ML defines uniform convergence with respect to distributions over X' {0, 1). in our setting, it is defined distributions on & alone. These distinctions require careful consideration when linking VC-dimension uniform convergence in the multi-domain framework, do in Theorem 3.4. We will now address this and provide a proof for the theorem.
Theorem 3.4. A hypothesis class H has the uniform convergence property with respect to a loss function & and threshold if and only if CCdim..,, < co. Moreover, if VCdimc., < oc, the sample size from the unfform-convergence definition is m(0 @ (
We start by proving that if H. has the uniform convergence property, then VCdimc,, Assume H possesses the uniform convergence property. This means that for any 0 c, 8 < 0.5 there exists m[c, 5) such that for any distribution D over & and for any training sample S C drawn according to D with |S| 2 m(e, 6) the probability
Proof. First Direction:
(over the draw of S) that
3he H. s.t
E [1,,
(h,
1 |5|
Σ 1c, (h, =e
cES
less than
Now, suppose by contradiction that c,, (H) co. This means that there exist set C & with |C| 22m(e, 8) that can be shattered by H. Let us define distribution D over & such that:
E
((e)
C
0
otherwise
Since H. shatters C, for any subset S C C' with [8| = m(c, = |C|
there exist h, E H such that:
2
0 if e S
(har)
{
else
For this hypothesis h2 we have
Σ
(c, =0 and
EB en
(hs, = 0.5
S
eES
Thus, for a specific choice we have shown that:
3h, E H.
E E (cc,((h))))) amD)
Σ EES
(h,
0.5
Since this holds for any sample S, the probability of the above condition occuring is 8, which contradicts the uniform convergence property. Therefore, our assumption that V CCdim (Hl)
must be false.
Second direction: Next, we will prove that if V VCdimc.; < co, then H has the uniform convergence property.
Let < e, < 1. Given a hypothesis set H. loss function C and 0 < 7 S 1 we define a new hypothesis set H. as follows:
Ht = (1c,,,h,)) : h H}. Each hypothesis (h,, in H- maps elements of to 1}.
is straight forward from the definitions that VCdim (H) < oo according to definition 3.2 of VCdim, than V VCdim(H") oc according the classical definition of VCdim, and that both VCdim values are equal (we denote
12

---

Set Valued Predictions For Robust Domain Generalization
them d). By classical results VCdim, this implies that H" has the uniform convergence property, with sample size m(,, c) = O (0
We would like to argue that if H0 has the uniform convergence property (according the classical definition), so does H. according definition 3.3. However, there two subtle differences in the definitions that require special care.
First, the uniform convergence of H is with regard to destributions D* over & x {0, Therefore we will translate our distribution D, which is over &, to destribution D required, and explain the connection between them.
Second, the uniform convergence of 7t is with regard to Lo-1 loss. Therefore we will need to connect the Lo-1 loss of H to our expression of interest, 1 Ic,, (h, e).
We will now tackle these two points to prove uniform convergence of H.
First, let D be distribution over E, and define D" to be distribution over the space I where {0, 13 such that:
(e, = ((e) i
else
In words, D has the same density over & as D when and zero density otherwise.
By the uniform convergence property of H.," for a sample S c I with |S| 2 m(c, 8) = 0 ( drawn according
D", , holds with probability least 1 over S that
(1,,(1, E 7t"
IE e,
Σ eJES
Lo
se
||]
Since D* constructed such that i = always, we have
Co Lo-1 e), (h,
thus, we can rewrite the above as:
1 el)
AAEH.
E D
[1,
S
EES
Overall we have shown that whenever [S] 2 m(c, = O ((atlog(1/))) for any distribution over & the above condition holds with probability at least 8, which precisely matches the definition of uniform convergence outlined in Definition 3.3.
A.2. Proof of Theorem 3.5
Theorem 3.5. For d 1, linear H cannot shatter more than 2|y| domains with respect to Creeall and any < <>> < 1.
Proof. Let X E and y y. Consider any set of n domains: & = {c1, 62, ...).
A linear classifier hy is of one of the forms:
0
i otherwise
if <<<<
(x))
hy(x)
otherwise
We start by showing that for each of these options, there is domain E such that if hy archives "good" coverage in that domain (i.e Pe (X) = Y = yl 2 1 - y), it must also achieve such coverage in all E. From this, we willl conclude that there exists subset of domains in E such that achieving "good" recall-loss within this subset will necessarily result in "good" recall-loss across all of é.
For each domain we can consider the conditional CDF Fe, Fe,ly= = p [X < x = v). Note that F (g) the value z E such that pe, [X x = y] = 4-
13

---

Set Valued Predictions For Robust Domain Generalization
Assume by is of the form
0 {1
if
Ny hy(x)=
otherwise
Let us define:
Amax.y = arg max F rr= -7)
ic(n]
Now assume that:
Permax 1| = 2 -
Then for each i E [n] is holds that
Cyman,y 1y=y(1- (1-1)) 2 F.- 1y=y(1 (1-7) = Pe, (Xy = 2117 21
In similar way, if hy is of the form
0 if x <a
hy (x)
otherwise
Let us define:
minn. = arg min F (x) (E(n]
and assume that:
Peiminx 1 = y) 2 1 -
Then for each e [n] is holds that
S F
(7) S Fei (y= = De: Phi (X) 1/Y = 2 y
Eimmnny
We see that whenever the recall condition, given Y y, holds for both imin.y and imaz,y then it holds for all i E [n]]. Now, if n > 2/3)|. there must be some E [n]] such that i + imnn. and i * imaz.y for any y E y.
From the above results, it holds that it is not possible to achieve any assignment such that
YyEY Cremutiiy (h,, Cimin..)
Yyey 1 Erecatt (h, Ciman.y) Creaatiy (h, c,) =0
Therefore, linear classifiers cannot shatter any set of n > 2| domains in the case of X' C R.
A.3. Prof of Theorem 3.6
Theorem 3.6. For 1. and any size n, there exists a set of n domains that can be shattered by linear hypotheses H. with respect to Freeatt and any < 7 1.
Proof. prove this, it enough to consider the case of 2, as for d we can always consider domains that represent degenerate distributions on 2d subspace with linear classifiers that practically operate in that subspace.
In RD consider domains such that their feature distributions (i.e the marginal distributions over X') have support on the unit circle, and linear classifiers that pass through the origin. It is not hard to see that in that case the problem reduces to distributions in the interval [0, 2T] C. R with classifiers that are rectangles of length æ. In Lemma A. we prove that for any n E N there are n domains that can be shattered by rectagles. That proof also holds when we limit the distributions to be on a closed interval R, with classifiers that are rectangles of a fixed length (no matter what the length is, as long as is smaller than the length of D). Therefore, the same proof holds in our reduced case.
14

---

Set Valued Predictions For Robust Domain Generalization
Lemma A.I. For any d and any size n, there is set of n. domains that can be shattered by rectangular H with respect frecalt and any O < Y 1.
Proof. For a given E N we need to present set of n domain C = {E1, ...9 End such that:
V Vgg(a] Bne s.t Pe,y E h(X))Y = y| 2 1 - + iel
We consider few simplifications for the proof:
First, it is enough to show the above for d = 1. This is because for d > 1 we can always define the domains in C to be degenerate distributions on a 1d subspace, and then follow the same construction as will be presented here for d = 1.
We can define the domains in C' to be such that Pa[x]y = y] will not depend on the value of y. Then, because h can be break down to hg. it enough to show that for some y E EV
Vigial Bny s.t Pe.l ly E h(X))* = y] 1 21-7 = iE!
Where Hy-reer the set of rectangular hypothesis for hy. This true because we can use the same function hy for all values of y to get the original goal.
We will now define distributions for X|Y = y for the domains in C' and show that our simplified goal holds.
Consider some order on all the subsets of [n]] such that the first subset is the empty one:
To 0, h 1,,,,,... ... Iz E P((nn)
We need to construct domains for C and show that for each 0 و j S 2 - there is a rectangular classifier hig such that
(x)
= 1 vl 2
- I
The idea of our construction is as follows. We will define the density of X on the interval (0, 3). We split the intervals (0, 1) and 3) to 2" sub-intervals, and recognize these sub-intervals with the subgroups / of [m]] Then, we will look at sliding window, such that each progress of the window adds one sub- sub-interval from (2, to the cover, and discards one interval from (0, 1). We will spread the density between the sub-intervals such that the sub-interval that is being discarded causes the associated domains to loss cover, while the sub-interval that is being included causes the associated domains to gain required coverage. This way our sliding window represents rectangular classifies that can achieve any assignment for the domains.
The formal construction is follows:
2--141 0.01(1 77)
2
if fosi22-1 $ S S
i+1 nd
& iel,
0.99
X 2--144 (1-7)
7)
[ y]
2
if (2+
ال
S X < (2 7F & ii
a
if 25 -1
0
otherwise
Where we assume that 1 - 7 is small enough such that the total integral for X > 0 is less than 1, and completes the density to totally integral to 1. If 1 7 is not small enough we just need to modify the factors 0.99 and 0.01 of the density, so WLOG assume 1 - y is small enough.
We will now prove by induction that for 0 S
< 2
1 we have:
1
j
i i - Pej
<
x
x
2+
Y = y
= =1-7
2
2n
j
2
i i P..
Y y
2- 0.01(1 ()) + 0.99(1 -) <
<1 x1->
2
2m
Therefore, for the rectangular binary classifier h2(x)= = = 1 2
1 2m
we have
= = و =1 = ieb
15

---

Set Valued Predictions For Robust Domain Generalization
This will conclude the proof, as it means that rectangular classifiers can shatter the set C' required.
Induction base case, j=0. Each domain takes part in 2n of the subgroups I, therefore from the domains construction the followng holds for each domain:
1 2 2
2n-1 0.01 -7) = 2n + 0.01(1-1 -7)
P. = y| = 2n-1
+ 2n21
Therefore for each domain Ci.
j Pes 2 5
2n-1
2n Y = Pa. [ X 2 x = - = 2n +
0.01(1 -7) + 0.90 -7)< <1 --
Together with the fact that So- = 0 this proves the base case.
Induction step, j + j+1. From the induction assumption we know that
j
j
i E 1 - Pe.
< x
2
Y = y
= 1 - y
2
2"
j
j
2n-1
i 1 Pa.
S X
2
Y y
0.01(1 -7) + 0.99(1 - 7)
2
2"
2
From the domains construction we have:
j
j+1
2n
i 1 = Pe.
<
X
<
Y = y
0.01(1-1) -7)
2n
2n
2 2
j
+ 1
i 1 - Pes
<
X
<
Y = y
=0 0
2
2
Putting these together will give us:
j+1_ i 11 Pei
1
1 2"
Y
y
7
0.01 - -7)
2n
2n
2 2n-1
1
2n
= 0.99(1 - 7) + 0.01 - 7)
2 +1 0.01(1 - 7) = 2n + 0.01 - 7) + 0.99(1 - 7)
j++1
3
y = y/
2n-1
i i = Pes
< x 2
2 0.01(1 7) 0.99(1 7)
2
2"
Le, we have for each domain
j++1 x 22 2a
j Y = y/
2n-1
Per
2a
=
2- +
0.01(1 - 7) + 0.99
Now, from the construction of the domains we have
j
j+ 1 x
2
iE 1 = Pe.
2
Y = 1/
2n 2n 1 0.01(1 7)
2n
2n
j
j i+1
i 1 + Poo
2
<
X
<2
Y = 1/
0
2n
2n
Therefore, we have
[1+1
j+1
i 1ب41 Pc
X 2
Y =
c,
2
2n
2n
1 2
0.01(1 -7) + 0.99(1 7) +
0.01 77
2 2n +1 1
2n 2n
2
+1
0.01(1 7) 0.99 - 7) = -
2--1 +1
1+
j+1
2n-1
$ 1++1 = Pa
x
<2
Y y
2n-1 + 0.01 7)) + 0.99 - 7) + 0
2"
2n
That completes our induction.
16

---

Set Valued Predictions For Robust Domain Generalization
A.4. Proof of Theorem 3.7
Theorem 3.7. If domains are restricted being conditionally Gaussian, and there exists YyE Ey RRxd such that for each e, y Bey 2y for some de.y R. then for each e, > there exist m O D ( such that if [tttrainl 2 m than with probability higher than 1 - 8 over the training domains sample Etrains and regardless of the distribution D over E, any linear hypothesis h such that
e²
VeEErrain 1 Erocuss (h, G) =0
will also have
I [L Cracaui Sc.
e
Proof. We begin by reminding that for a set-valued to be a linear hypothesis means it can be decomposed into | linear binary classifiers hy. We will break the proof into two stages. First, we define for each y E 3 a loss (hy: e) Pe (X) = OjY y] and show that linear binary classifiers cannot shatter more than + 1 domains with regard to Ly: 7- Then, we will use this result show that linear binary classifiers have the uniform convergence property with regard to Cy. 7, and with that in hand we will conclude the theorem.
Lemma A.2. In the terms of theorem A.2, linear binary classifiers cannot shatter more than d + domains with respect Cy and any 0 < y < 1
We start by proving the Leamma.
As this Lemma focuses on a specific value of y. we will omit y from some notations where it is clear from the context. We assume hy is linear binary classifiers, ie there exists Rd such that
(x) =1
8t x 2
Let C = {e1, e2, be a set of n = + 2 domains that are conditionally normal, i.e
v1 sisn [X = vl Pec N(u; 02 E).
We will mark
1, = 1 Pay 1yy (X) 1|Y v) 2 and show that there must be an assignment of [1,) {0, 13"d that cannot be achieved.
else
Given 0 Rd let us consider the variable Z = 0²h X. For each domain, this is a conditionally normal 1d variable:
[ = y| ~ N(OTT ps. ε0).
Therefore,
0" 0TH
0r pi
pz > O/Y = y] = pec
2
= v1)
Vo,02 02 21
Vo 50
where (6.) is the CDF of a standaridized normal variable. Letting be such that d(c) = 1 11 - we have
0 pi
1 + ped Z 0|Y v) 2121-9 0 Σ0
c = 8T pM 0TH, cv /o 0,0 20 0.
Defining 0 (0,cV0''00) ndd+1 v3 = (ms, vo.) Rd+1 we get
1, 1
0Th v 20
17

---

Set Valued Predictions For Robust Domain Generalization
We note that the fact that Ô does depend on i at all, and that y does depend on 0 is important, as will be seen next. Now, have d + 2 domains in C, we have d + corresponding vectors vi in Rd+1, there must be one vector that is non-trivial linear combination of the others. WLOG assume that vector is M1;
V1 Σ ai
Now, let us consider the following assignment for 1,:
if 2 0
1, = 0
if a; <0
i=1
Assuming there is a 0 that achieves this assignment would mean that:
i> a. a 220
8TH 1 = Σ i>1
which contradicts the requirement 11 = As i depends solely on 0 (and on c, Σ, which are constants), and does not depend this means that f cannot satisfy the above assignment. As the suggested assignment is not dependent on 0 (it depends only on the set of {v:}, which are not dependent on 0), it means that have found an assignment that no @ can satisfy.
We have shown that no 0 can satisfy the above assignment, which means linear classifiers are not able to shatter the set C,, as required.
This proves the Lemma. Now, consider c, from the theorem statement, immediate result of Lemma A.2 and theorem 3.4 is that, focusing on single y V, the hypothesis set Hy, of linear binary classifiers have the uniform convergence property with regard to Lyy 7. i.e there exists my p
b e pPP((tHog(()1/))) such that with probability higher than
&
1
|
8
1 Eueen(hhe)) + D
|S| > my
[D D why Hy E (h, enD
[|] cES
If take m max my D 157) 0 (D) than the above holds simultaneously for all y E with probability higher than -
Now, we note that Crecalt (h, e) = maxyey Cy, e), therefore if |S| > m we have with proaility least 1
VNEN
E [1 (1 (h, = P
[Frecat (h, e) > rl S Σ
P (h) >
e>D
vEy
Σ (h,
+ [1)
)
ΣΣ
[1 eh) +
S
[
S
yEy
eES
EES DES
And finally, as for any h such that it also holds that
1 Cranteyy (h, e) =0 - eh
(t, =0
VeEEuram (1, =0
E [1 Eraan e)) D
1
ΣΣ (t,,) |s|
>> 0+csc
[S]
eES vey
eES yEy
18

---

Set Valued Predictions For Robust Domain Generalization
B. Sample Size Analysis
In this section, we examine the sample size requirements for achieving generalization from training domains with finite samples to new, unseen domains. We start with some notations:
We recall the definition of performance indicator: (h, e) (1, e)
We denote the training set, collected from the training domains Etrain S Ueeltrain Se, where Se is the sample set from domain e.
B.1. Sample Size Within Domains General Case In this subsection assume L(h, e) ((,,))),,,((()), v)] for some cost function 1.
Theorem B.1. Let H. L, follow the definitions from theorem 3.4 Assume that:
1. H. has the uniform-comee convergence property with respect to L, according to definition 3.3 with sample size m( e).
2. H has also the uniform-convergenn property according to the classical definition (in a single domain setting) with sample size n(8, e).
For each 61, 62, 0, if Eraiil m(3. 62) == m, and Ve E Etrain [Sel n( ( 2m, 61) than with probability higher than 1 5, and regardless of the distribution D over & and all the distributions feror E Etrains it holds that:
1 Σ ((h(x)) s>]=
Wh H MeeEerain
I [e (h, se.
SScl
enD
iES.
Proof. let 61, E2, > 0 be positive numbers, and assume UcEErran S. such that Etrainl 2 m and for each e Etrain [Se] 2 n.
From the uniform-convergence of H in the classical, single-domain, sense, know for each domain Etrain that with probability at least 1 2m
& it holds that:
1 ((h((x)).)) +
vh E H. e(h,e) v
SSc
And
wh H.
Σ
L(h, + Ic.ttr =
[eel iES.
This is true for each Etrains therefore with probability at leat & true for all training domains once:
vh E H NeeEsrawn Se LES.
I(h(X.). 31) S] Etrain
Σ
(h,t, =0
eEErrain
From the uniform-convergenn property of H in the OOD sense, we know that with probability at least 4 it holds that
4h H
[1,nter (h1
Σ
(cntee(h,,)) S E2.
1Erain
anD) 1entt (he,, (he,e) 8)
pEEtraco
And the case of
EeeErvin
we get:
Esrainl
vh E 76
E enD
[1 c (h, (h, S
Overall, we have shown that with probability at least 1 - 8::
Vh E H.
VeeErrain
1(h(X;), ui) ~
IB
[lrtt (h,ee) S
S.
enD
iES.
19

---

Set Valued Predictions For Robust Domain Generalization
B.2. Sample Size Within Domains Recall Loss
Now we focus on Crecall- We start by reminding its definition:
Crecatt (h, e)
max Pely & h()) = y]. vEY
Now we also assume that H is an hypothesis of set-prediction hypotheses, where each h E be decomposed to [ bi- nary classifiers h, presented in the paper. We assume also that the Ry binary classifiers come from some 7t'" hypothesis set.
The following result differs from that of section B.1 mainly because Crecall is not an expectation over some other loss L. The result we derive for Lreealt is almost the same as in the previous section, with only one change: Instead of requiring a sample size of n 6 2m {1) at each training domain, we need to require a sample size of n 2m <1) for each training domain and each label E y. For completeness we present here the full result for Creeatt and provide a full proof for it.
We add single notation to this section:
= Se Y, = y)
Theorem B.2. Let H. Crecall, follow the definitions from the paper. Assume that:
1. H has the uniform-convergence property with respect to Crecaut, Y according to definition 3.3 with sample size m(6, e).
2. H. has the uniform-convergence property according the classical definition (in a single domain setting) with sample size n(ō,e c).
For each e1, E2, 5 O, if |Etrain| 2 m2()e2) e2) := m, and Ve E EtrainVy E y |Se.yl 2 nl , = than with probability higher than 1 8, and regardless of the distribution D over & and all the distributions P. for e E Etrains holds that:
wh [VesEran VeEy
Σ 1-
57 =
E evD
crecatyyy (h, E2.
Se.
iES..v
Proof. The main difference in this proof will be to show that with high probability
Wh E H Crecau((he) S max yEy [Se.v ieS.,y
Σ (
For completness we provide below the full proof.
Let 61, 6 be positive numbers, and assume S UeEEmann S. such that |Etrain] 2 m and Ve E Etrain Vy Y [Se..p 2 n.
sense, know for each domain Exaann and for each y y that with probability at least 1 2m it holds that:
From the uniform-cone convereee of 7 in the classical,
E (x(h(X) + 1|Y = yl = E. M(X)) vl |Seyal iES...
\1-M(X) +
This is true for each y separately, so with probability at least
this is true for all y at once:
2m
vh HEE Vy yy Pa(M(X) + 11V = v)
Σ p h(x)) +
Sey
SES..
We note that the above is true for hypotheses from H., which are binary classifiers.
Now, for a given E H. which a set-valued predictor, let
y arg max Paly & M(X)Y v]- vEy
20

---

Set Valued Predictions For Robust Domain Generalization
Then, with probability at least
holds that:
2m
Drecall (h,
max Pelv E ((()) = = y +1 yEY
1 = 11 s
$
Σ
[1
hy (X,)) +1 S
max yEy
Σ 11 +
Se,ar
Senyl
iESe,0'
iES..v
Overall, we have shown that with probability at least
2m
H
Crecau (h,
max yey
See
h1
iESe.y
And so,
vh E H
max yEy
Σ
11 $- 5y ()
Seeyy
iES..v
7 c) e)= =0
This is true for each Etrain, therefore with probability at leat 6 true for all training domains once:
2
vh E
MeeEErain
max yey
Σ [1-
(X,)) s- EEroii
Cracaut (h, e) =
Sey
iESc.o
eEEivain
From the uniform-convergence property of H in the OOD sense, we know that with probability at least it holds that
vh H
Cracaliitto tre (hr,))] Erraia
Σ
Cracattirte (n,e) c2.
enD
eEEtrain
And the case of
Exeerami
Ereaultter (h = we get:
Earatal
Vh E
E [1 tre (aettee(hhe,,e (h, e)] S enD
Overall, have shown that with probability least 1 8:
Wh E H
VeEEmran YEEY
Σ 11 hy
s IE enD
(r (h, S E2.
SSe.l sES..v
B.3. Sample Size Within Domains Recall Loss With Linear Hypotheses finally, we show the sample complexity for Crecall when H. is the set of linear hypotheses.
Theorem B.3. Let be the hypothesis set of linesr set predictors in Rdd, Assume domains are restricted being Conditionally Gaussian described in theorem 3.7.
For each E2, 8 > 0, if (Etriinl 2 O (D/P(/440)g(())))0) := m. and Ve E Exrain Vy E y [Se.yl 2 O 24tt
of
than with probability higher than 8, and regardless of the distribution D over & and all the distributions Po Eirain it holds that:
vh E H [VeEEraen VyEY SSe.l iES..v
1- S 5] = E [1 Crecaaaaatt (h, 62. anD
21

---

Set Valued Predictions For Robust Domain Generalization
Proof. Let E 62, > 0 be positive numbers, and assume and Ve Etrain Vy y |Se.yl O
UeEErman Se such that [Etrain
2
O
D (d+1og(2[)] /61)
of
In the classical, single-domain context, linear hypotheses have VC dim = d + 1, and they hold the uniform-coovergence property with ní(, e) O /d4fo((1/6)) (Shalev-Shwarze & Ben-David, 2014).
holds that:
d + (og(22(()11)))) = |Sc.yl 2 n 2m 61)
Ve E Etroin E y |S 2 O
of
Following the exact same steps from the proof of the previous section, derive that with probability leat 6. 2
vh E H MeEEerain
max Seey
11-h,
S 7 = Ve E Etrain 1 2re (h, e) 0
Now, from theorem 3.7 we know that with probability at leat 1 - 8. 2
vh E H Ve E Etrain I Crecaus,to (h, = =
E [1 tte (h, sc c2
enD
Together, we get that with probability at least 1 - 8:
1 Σ 11-hh - E [1 craausytr (h,c)] S c2.
th H (eEEEraan
yEY Se..y ieSc.v
eND
C. Developing set-size optimization method In section 4.1 we presented our learning objective as a constrained optimization problem for each E ) separately:
min Σ (X,) NEH
iES
s.t Ve Exrain Ge ieGeN
Σ (X, = 0] S
This problem can also be written as:
N (X.)
min NEH
(3)
Ve Etrain
Σ (X-)(( S:
/ey
iEGa.v
We now investigate the problem and further develop it, until we get lagrangian that approximates the original problem, and which is possible optimize using common methods.
C.1. Relaxed Problem
In order to leverage common gradient- gradient-based optimization methods, we parameterize our predictors as mentioned section 4.1 and present slack variables form the following relaxed problem:
22

---

Set Valued Predictions For Robust Domain Generalization
min Σ &.
N
s.t Vi xx) - -1+
Vi Gy (x) 2 21-6 S2
(4)
Ve E
Σ Se
Gew igGa.
Vi 4 20
Vi 520
Theorem C.1. The objective of the relaxed problem (4) is surrogate for the objective of the original problem (3)
Proof. From the first constraint of (4) we have for each 0
&
(x)) 2 0 >hy(zs)
0 S E <1 - k2(X,) <0 = hy((z)) =
Thus, & 2 (X,), making Σg & a surrogate loss for (y(i).)
Theorem C.2. The recall constraint of the relaxed problem (4) is surrogate for the recall constraint of the original
problem 3)
Proof. From the second constraint of (4) we have for E Gy:
C 2 1 = (x()))) 50 = hy (3rc) = 0 = hy,))) =
0 4 <1 {g(x))> > + lz(1z) =1 = 1 - by (Xi) =
Thus, G 2 1 (Xx) for i E Gy, making [Gaxl Exego, Si surrogate loss for 1 |Gu.l Eiege 1 1 hX,).
C.2. Lagrangian Form
Solving the relaxed problem for & and Ça we get:
& max (0, + (X.))
mar (x.)
Where the expression for Çi is one of the optimal solutions for it (there are additional optimal solutions). Substituting these into the optimization problem (4) yields:
min
max [0, 1 + (X.))
(5)
8.t VEEB
max (0, 1 (X.)) S
G BEG
This problem can be optimized using common methods like Stochastic Gradient Descent (SGD) by defining the la- grangian: T(O,, Σ max (0, + (x)))
Σ
Capl Ge,yl iEG..u
Σ
max(0, 1 A,(X,)] Y)
eEEurain
23

---

Set Valued Predictions For Robust Domain Generalization
Solving ming maxc L(0, C)) will give 0 that solves the constrained optimization problem 5, common approach is to
gradient descent on 0, and gradient ascent on C. This is being done by SET-COVER, described in section 4.1
D. SET-COVER Pseudo Code
Algorithm SET-COVER
Initialize C,C for i from to NUM EPOCHS do for in batches do
Call COMPUTE (8,
L(B,C) C) Eyey (0, C)
perform GD step for 9 with respect C)
IF % C UPDATE FREQUENCY = 0 do
Call UPDATE C
end for Call UPDATE_C
end for Subroutine: COMPUTE C0,
(), = = Ly max 1 + (x,))+
sEb
1Y Ce..x max hx,))
Subroutine: UPDATE_C
for Etrain do for y E y do
coverage TG.yl Eieg.,, (X,) 0]
+ (coverage... c.y - (1 - 7))
8 if else 1
Ca.y Ce. v
end for end for
E. Experiments
E.1. Experiments Hyper- Parame-aarsetters
Table 2.
used for our experiments
Hyper-Parameter
Camelyon
Fmow
Iwildcam
Amazon
Synthetic
Batch Size
128
64
128
Learning Rate
0.001
0.001
0.001
0.001
0.001
Number of Epochs
5
5
5
5
30
Number of train domains Number of test domains Max train domain size Max test domain size Relevant for SET-COVER:
20
20
80
500
25
20
18
40
100
25
6,000
4,500
3,000
1,000
2,000
2,000
3,000
1,000
1,000
1,000
Initial C value Frequency values update
S
5
5
S
5
500
500
500
500
Table 3. Hidden dimension of 2-layer MLP (in the relevant experiments)
Synthetic, d=10 Synthetic, d=50
Amazon
Hidden dim
5
25
10
24

---

Set Valued Predictions For Robust Domain Generalization
E.2. Synthetic Data Generarion Process Parameters
We set Σ to be diagonal covariance matrix with value on the diagonal. detailed table below. Also, we set R to be concatenation of vectors VI, V2 IRU.5d i.e (V1, v2). MI, V2 are detailed in table below.
Table 4. Synthetatic data generation parameters.
dimension d
Mhrgh
H E R..
Vi
R 0.5d
12 IR 0.5d
d 10
-0.5
0.5
(0.1.
0.1)
(I.
(-1
0.2
50
-0.3
0.3
(0.05, 0.05)
(l... 1)
(1....11)
0.25
E.3. Additional Synthetic Data Experiments
In Theorem 3.7 we have shown a theoretical generalization result, but under the limitation of shared covariance structure across domains (up scaling factor). Our results in the synthetic data experiment, presented in section 5.1 empirically support this result. In this section want to test whether the generalization new domains hold also in DGPs where the covariance between domains does not share exactly same structure. To this end, we recall the DGP presented in section 5.1:
Ze ~ U [looo Wnigh]
Y ~ (ernoulli(O.5)
~ (n + Zov)+ + N(O,
In the following experiment we change the covariance matrix to be domain-specific in the following way:
1. We sample for each domain diagonal matrix, De, with diagonal values sampled from normal distribtuion with μ = a and std 0.05 (this process generates std values, which than squared to form the diagonal values of D.). values are the same as set in the original experiment from section 5.1.
D. diag((De (e D2 aa
V1 sisd De, ~ (o,,
2. For each domain sample uniformly rotation matrix Qe.
3. For each domain we set the covaraince matrix Σ. = Q D.Qe
All other experiments' hyper-parameters are the same as the original experiment from section 5.1. The results are presented Figure and Table 5.
Table 5. OOD Performance on synthetic Datasets with Random Covariance
10d
50d
Model
Median Min Recall
Median
Recall > 90%
Median
Median
Recall 2 90%
Avg Size 4
Petg t
Min Recall f
Avg Size
Pctg
ERM
0.88
1.0
0.39
0.90
1.0
0.52
CDF Pooling-
0.87
1.02
0.30
0.86
0.98
0.19
(TrainC)
CDF Pooling-
0.87
1.04
0.32
0.86
1.04
0.27
(CVC)
Robust-
0.94
1.24
0.94
0.90
1.24
0.71
Conformal
SET-COVER
0.94
1.23
0.92
0.91
1.18
0.68
25

---

Set Valued Predictions For Robust Domain Generalization
ood-test
ood-test
0.95
0.90
0.925
0.900
ERM
Min Recall
0.80
Pooling CDFs (TrainC)
Min Recall
0.875
Pooling CDFs (CVC)
Robust Conformal
0.850
SET-COVER
0.825
0.70
ERM
0.800
Pooling CDFs (TrainC)
Pooling CDFs (CVC)
0.775
Robust Conformal SET-COVER
0.60
0.750
1.00
1.55
1.55
1.25
1.35
1.00
110
1.15
1.20
1.25
1.30
1.35
Size
(a) 50d
(b) 10d
Figure 3. Min Recall distribution VS Mcan Set Size distribution. Blue represents ERM model, Orange represents Pooling CDFs (TrainC), Grey represents Pooling CDFs (CVC), Green represents robust conformal, and Pink represents SET-COVER, The horizontal solid line represents the 90% recall target value.
26

---

Set Valued Predictions For Robust Domain Generalization
E.4. Exploring Different y Values
The ? parameter sets the desired recall level, and is supposed to be set in practice by practitioners according to task requirement. In our main experiments, which are presented the body of this work, targeted 0.9 recall level, which is associated with y 0.1. In this subsection present results also for targeted recall levels of 0.8 and 0.95.
E. 0.8 RECALL
ood-test
ood-test
1.0
0.90
Pooling CDFs (TrainC)
Pooling CDFs (CVC)
Robust Conformal
0.9
0.85
SET-COVER
Recall
Min Recall
0.80
0.8
0.75
ERM
0.70
Pooling CDFs (TrainC) Pooling CDFs (CVC)
Robust Conformal
0.65
SET-COVER
1.6
0.850
0.875
0.900
0.925
0.950
0.975
1.000
Size
Size
Camelyon
FMoW
ood-test
ood-test
10
0.9
0.8
0.7
Recall
0.6
ERM
Pooling CDFs (TrainC)
0.2
Pooling CDFs (TrainC)
Pooling CDFs (CVC)
Pooling CDFs (CVC)
Robust Conformal
Robust Conformal
0.3
SET-COVER
0.0
SET-COVER
0.6
0.8
1.0
1.2
1.4
1.6
1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
Size
Size
(c) iWildCam
(d) Amazon
Figure 4. Results for recall target of 0.8 (7 = 0.2)
27

---

Set Valued Predictions For Robust Domain Generalization
Table 6. Summary of OOD Results for recall level of 0.8 (7 0.2)
Camelyon
FMoW
Model
Median
Median
Recall 2 90%
Median Min Recall f
Median
Recall 2 90%
Min Recall
Avg Size +
Potg t
Avg Size
Petg
ERM
0.91
1.0
0.75
0.75
1.0
0.42
CDF Pooling-
0.74
0.81
0.38
0.67
0.84
0.05
(TrainC)
CDF Pooling-
0.67
1.09
0.45
0.72
0.94
0.16
(CVC)
Robust
0.95
1.77
0.90
0.79
1.00
0.50
Conformal
SET-COVER
1.00
0.71
0.89
1.01
iWildCam
Amazon
Model
Median Min Recall
Median
Recall 2 90%
Median Min Recall f
Median
Recall 2 90%
Avg Size +
Pctg 1
Avg Size
Petg
ERM
0.99
1.0
0.71
1.0
1.0
0.69
CDF Pooling-
0.91
0.91
0.60
0.83
3.75
0.56
(TrainC)
CDF Pooling-
0.95
1.01
0.70
0.99
2.40
0.70
(CVC)
Robust
0.98
1.31
0.76
1.0
4.41
1.0
Conformal
SET-COVER
0.99
1.00
0.71
1.0
2.72
0.98
28

---

Set Valued Predictions For Robust Domain Generalization
E.4.2. 0.95 RECALL
ood-test
ood-test
1.000
0.975
0.950
0.90
0.925
ERM
Recall
0.85
Pooling (TrainC)
0.900
Pooling CDFs (CVC)
Robust Conformal
SET-COVER
0.80
ERM
Pooling CDFs (TrainC)
0.75
Pooling CDFs (CVC)
Robust Conformal
SET-COVER
0.70
1.0
1.2
1.4
1.6
1.8
2.0
1.0
1.2
1.4
1.6
1.8
2.0
2.2
Size
Size
Camelyon
(b) FMoW
ood-test
ood-test
1.
0.9
0.8
Recall
0.6
0.7
0.6
ERM
Pooling CDFs (TrainC)
Pooling CDFs (TrainC)
Pooling CDFs (CVC)
Pooling CDFs (CVC)
Robust Conformal SET-COVER
Robust Conformal
0.0
SET-COVER
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
1.0
1.5
2.0
2.5
3.0 Size
3.5
4.0
4.5
5.0
Size
(c) iWildCam
(d) Amazon
Figure 5. Results for recall target of 0.95 (7 = 0.05)
29

---

Set Valued Predictions For Robust Domain Generalization
Table 7. Summary of OOD Results for recall level of 0.95 (7 0.05)
Camelyon
FMoW
Model
Median
Median
Recall 2 90%
Median Min Recall f
Median
Recall 2 90%
Min Recall
Avg Size +
Pctg t
Avg Size
Petg
ERM
0.91
1.0
0.48
0.75
1.0
0.03
CDF Pooling-
0.95
1.53
0,5
0.90
1.21
0.07
(TrainC)
CDF Pooling-
0.88
1.39
0.26
0.89
1.29
0.14
(CVC)
Robust
0.99
1.94
0.93
0.96
2.13
0.64
Conformal
SET-COVER
0.95
1.15
0.65
0.94
1.22
0.53
iWildCam Median
Amazon
Model
Median Min Recall
Recall 2 90%
Median Min Recall f
Median
Recall 2 90%
Avg Size +
Pctg 1
Avg Size
Pctg
ERM
0.99
1.0
0.70
1.0
1.0
0.69
CDF Pooling-
0.93
0.94
0.45
0.98
4.54
0.69
(TrainC)
CDF Pooling-
0.99
1.14
0.72
1.0
3.07
0.72
(CVC)
Robust
0.99
2.34
0.85
1.0
4.69
1.0
Conformal
SET-COVER 0.99
1.07
0.77
1.0
3.02
0.97
F.4.3. RELATIONSHIP BETWEEN RECALL AND SET SIZF
In Figure 6 illustrate how varying the recall target affects the resulting prediction set size, across methods and datasets. The results are based on the three values presented carlier. corresponding to target recall levels of 0.8, 0.9, and 0.95. As expected, increasing the desired recall level generally leads to a corresponding increase in set size. This trade-off reflects the fundamental tension between coverage and specificity: higher recall necessitates larger prediction sets to ensure that the correct label is included. The trend is consistent across datasets and methods, although the magnitude of the size increase varies. Notably, SET-COVER tends achieve high recall with relatively smaller increases in size, indicating better efficiency in balancing recall and compactness. These observations reinforce the importance of selecting 7 (and the associated recall target) with awareness of the practical constraints and cost associated with larger prediction sets.
Camelyon
TMO
WhhaCam
Amazznn
2.0-
3.42
0.7
0.50
3.55
0825
0.00
3.00
0.5
0.2
0373
900
Voal
0.70
Pouking CO0 CVC
Pool 120) XVO
Phdkin CDCV
D357
Iviigg CDC TOYO)
SESCONER
S1E0060
144
24
10
14
14
14
24
22
24
35
22
Figure 6. Relationship between recall and set size. Each curve corresponds to method and shows results for three target recall levels (Y E {0.2, O, 0.05), corresponding target recalls of 0.8, 0.9, and 0.95). The Y-axis indicates the actual minimum recall achieved, while the X-axis shows the corresponding prediction set size.
30

---

Set Valued Predictions For Robust Domain Generalization
E.5. Experiments Other OOD Baselines
For the main experiments of this work we chose the ERM method as the single- preeelptnii basekine, due to its vast popularity in real-world applications, and its superior, at least compatible performance in various OOD baselines (Koh al., 2021; Guirajani & Lopez-Paz, 2020). In the next section compare SET-COVER to additional common OOD baselines. These include IRM (Arjovsky et al., 2019), VREx (Krueger et al., 2021), MMD (Li et al., 201 8018,,, and CORAL (Sun & Saenko, 2016). We use the DomainBed (Gulrajani & Lopez-Paz, 2020) package to train these models.
The results show that common
baselines do not maintain the 90% min-recall target across most OOD domains, SET-COVER presents an advantage in getting the target min-recall level across unseen domains, suggesting that set-valued predictors may be a step in the right direction for robust OOD generalization.
cod test
ood-test
0.5
0.7
FRDA
0.6
Nih HOC0
VREK
0.0-
HINLD
CORAL
CEVER
SETICOVER
1.00
1.22
2,04
2.00
1.08
100
2.04
2.08
1.22
114
3.0
2.1
1.5
5i2e
(a) Camelyon
(b) FMoW
(c) iWildCam
Figure 7. Each figure represents Min-Recall over Avg Set Size cross. y-axis represents min-recall and x-axis represents average set size. Each cross shows the median and the 25th and 75th percentiles for both metrics domain. The horizontal solid line represents the 90% recall target value, and dashed yellow diagonal line represents performance of a random predictor.
67
BRM
ERM
V9E4
VREK
VREK
PERD
07
PMU
CIHALL
COROL
CO
6.-
SE1 COVER
5c COVER
SE1 COVER
0-4
0.2
0.
0.
08
Recal
Recall
PCTC
(a) Camelyon
(b) FMoW
iWildCam
Figure& Percentage of OOD domains where the min-recall is higher than 90%. Each bar represents a different model.
31

---

Set Valued Predictions For Robust Domain Generalization
cod-test
206-7942
306-7912
0.5
-0.
-1.
-1.5
SET conti
8RM
MAD
coMe
5e7cov
DH
Vin Rocal
Nn Recall
Kn Rocall
(a) Camelyon
(b) FMoW
(c) iWildCam
Figure 9. Boxplots represent the distribution of min-recall OOD domains.
Table 8. Summary of OOD Results for different OOD baselines.
Camelyon
FMoW
Model
Median Min Recall
Median Avg Size 4
Recall 2 90%
Median
Median
Recall > 90%
Petg t
Min Recall
Avg Size 4
Petg
ERM
0.91
1.0
0.61
0.75
1.0
0.09
IRM
0.17
1.00
0.13
0.22
1.00
0.03
VREX
0.90
1.00
0.60
0.82
1.00
0.11
MMD
0.48
1.00
0.50
0.84
1.00
0.20
CORAL
0.50
1.00
0.50
0.83
1.00
0.18
SET-COVER
0.95
1.05
0.68
0.93
1.12
0.81
iWildCam Median Avg Size 4
Model
Median Min Recall
Recall 2 90%
Petg f
ERM
0.99
1.0
0.71
IRM
0.88
1.00
0.50
VREx
0.94
1.00
0.60
MMD
0.78
1.00
0.44
CORAL
0.68
SET-COVER
1.00
1.02
0.87
E.6. Additional Results of Main Experiments present here additional results of the WILDS experiments presented in section 5.2.
32

---

Set Valued Predictions For Robust Domain Generalization
E. COVERAGE GENERALIZATION PLOT
000-esst
0ec-test
red bast
00d Rest
0.1
0.15
4.25
8.30
0.5
Fasling Ta
Foclig (TanC
0:41
Failng (hP
Faolng CoC' (hanC) Fotee Cenferal srncome
Corteraa arrccon
Conteca
Peous Corfera SETcOOm
Any
Any
Ang
(a) Camelyon
(b) Fmow
(c) Iwildcam
(d) Amazon
Figure Y-axis represents the percentage domains with min-recal 2 90%. X-axis represents average set size. Blue represents ERM predictor, Orange represents Pooling CDFs (TrainC), Grey represents Pooling CDFs (CVC), Green represents robust conformal predictor, and Pink represents SET-COVER.
E.6.2.
Loss VARIATIONS COMPARISSON
In section we argue that SET-COVER should not penalize correctly predicted label in the set-size loss term of the Lagrangian (the first addend of the Lagrangian). This led us update the Lagrangian we optimize from
(0, = Σ max (0, (x,)++
iES
Σ
LieGe,, CaN max (X.)),
ereannn
to
(0, Σ max (0, 1+ hg,
sgG,
Σ
1iEG., Cey max max(0, - (x.)).
ef Etrain
Here compare the two variants. The first variant we call "Full Set Penalty",, as it penalizes also the correct label in the set-size term of the Lagrangian. The second variant is called "Wrong Prediction Penalty", as it only penalizes the wrong labels in the prediction set. Figure 11 shows that the "Full Set Penalty" does not consistently improve set size, and in Camelyon and Iwildcam it even outputs somewhat larger sets. addition, it does not lead to an improvement coverage, and in Camelyon and Iwildcam even leads moderate degradation in coverage.
33

---

Set Valued Predictions For Robust Domain Generalization
1.20
3.30
0.40
0.54
6.73
0350
037
840
maably
1003 1090 8.00
1.5 sub0 Lifo 1200 1200
1.2
1.31
1.00
15
13
24
24
(a) Camelyon
(b) Fmow
(c) Twildcam
(d) Amazon
Figure 11. Each figure represents Min- Recalleell over Avg Set Size cross. y-axis represents min-recall, and X-axis represents average set size. Each cross shows the median and the 25th and 75th percentiles for both metrics across domain. Pink represents SET-COVER as presented in the paper, ie the "Wrong Prediction Penalty" variant. Yellow represents SET-COVER with loss penalizing entire set size, including correct labels,
"Full Penalty".
E.6.3. TRAINING TIME AND COMPUTATIONAL COST
We report the average training times (measured on a single NVIDIA GPU) for ERM and SET-COVER on each dataset in Table 9. SET-COVER incurs moderate increase in training time (approximately 30% on average) compared to ERM, primarily due to the optimization of Lagrange multipliers (C in our algorithm). Aside from this, SET-COVER shares similar computational requirements with ERM, relying on hinge-loss-based optimization without substantial architectural complexity.
Table 9. Average training times (in minutes) for ERM and SET-COVER across datasets.
Dataset
ERM (min)
SET-COVER (min)
Camelyon
98
133
FMoW
45
56
iWildCam
46
58
Amazon
12
15
The current implementation of SET-COVER can be further optimized by, for example, exploiting GPU parallelism more effectively. We anticipate that such improvements would significantly reduce the additional computational overhead.
Other set-valued predictors (Pooling CDFs, Robust Conformal) are trained in two stages where the first stage involves training ERM classifier, which dominates the overall runtime. For simplicity, approximate their training time by that of ERM. Additionally, some OOD baselines discussed in Appendix E.5 rely DomainBed implementations, which apply various runtime optimizations, making direct training time comparisons inconsistent.
E.6.4. CROSS PLOTS ON TRAINING DOMAINS
We present in Figure 12 the cross-plot that is presented in Figure 2, Section 5.2, but here we present it for Train set and In- Domain test set, alongside the OOD test set (which is also presented in Figure 2).
34

---

Set Valued Predictions For Robust Domain Generalization
brin
Indooman-tts
2od-tast
1.00
Pil Houal
Pecchl
085
Mith
0.79
ETN
FBM
MM
Pazling Cala
Pooting (Thant))
Paaking (TtanC)
Posking ICVC
Posting
Pocking (CYE)
contermal
SET-COVER
SET-COVER
1.0
12
14
3.8
1.0
1.2
1.4
3.0
1.
1.4
3.6
Par Sine
Aagg Sinn
Avg itme
(a) Camelyon
train
doddoooomneeee Dest
ood test
0.90
0.5
CDtss conternal
Pooling CDrs Peoling
Se1:cover
1.050
1.0%
1.00 MTT 1 ion 1005 1150 122 1395
16t0 1605 Woo 1i0s 1 180
195 1 1125 196 Svg
1.00 1.005 1,50 1,00
1100 195 1i/ 1135 hen
Aug soee
(b) Fmow
Irein
domain test
Do0 rest
3.0
03
Noca
0.0
Pocling
0.75
1.00
1.2
1.50
1.75
7.50
2.55
3.75
3.00
1.25
1.30
1.75
7.00
7.55
075
1.00
3.5
1:20
1.75
2.00
2.75
Aug
502
AP 5ize
/0g 3020
(c) Iwildcam
train
in-oomainttest
68
10
15
20
2.5
30
3.
45
5.0
2.
15
2.0
255
3.0
3.5
4.8
45
50
1.0
15
200
25
3.0
3.5
600
45
50
Sum
(d) Amazon
Figure 12. Cross Plots For All Data Sets
35


Reviews:
[{"review_id": "hQLs3EskD5", "reviewer": "Reviewer_Z3og", "summary": "This paper introduces set-valued predictions for domain generalization (DG) problems. They propose a framework based on counting threshold violations for per-label recall. The paper introduces SET-COVER (SET Coverage Optimized with Empirical Robustness), a relaxed (differentiable) version of the proposed metric. They evaluate their approach on synthetic data and several datasets from the WILDS benchmark.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your constructive review. We have gained many important insights from your questions, and believe we can address your concerns. Below, we have organized our response by the key topics raised in your review:\n\n1. Our primary focus was on comparing SET-COVER with other set-valued methods suitable for DG, balancing both recall and set size. However, recognizing the importance of benchmarking against SOTA DG methods, we wish to direct your attention to Appendix E.5 where we provided additional comparisons. While these methods typically produce single-valued predictions, limiting the ability to compare them with set-valued predictors, we believe this comparison still provides useful insights, showing that set-valued predictions made by SET-COVER increase recall robustness in unseen domains.\n\n2. SET-COVER incurs a somewhat higher training time (~30% increase over ERM) due to the additional optimization of Lagrangian multipliers (denoted as C in our algorithm). Below are the average training times (single GPU) for our experiments:\n\n* Camelyon: ERM: 98 min, SET-COVER: 133 min\n\n* Fmow: ERM: 45 min, SET-COVER: 56 min\n\n* iWildCam: ERM: 46 min, SET-COVER: 58 min\n\n* Amazon: ERM: 12 min, SET-COVER: 15 min\n\nWe will include these results in the final version. Notably, our current implementation can be  further optimized by, for example, exploiting GPU parallelism. We anticipate that a more efficient implementation would significantly reduce the additional computational overhead. Apart from this step, SET-COVER primarily involves optimizing a loss function composed of hinge losses, which does not introduce substantial extra computation beyond standard architectures.\n\nTrain times of  other set-prediction methods are approximated by those of ERM, as other set-prediction methods train ERM as a first stage, which consumes most of the training time.\nAdditionally, other SOTA DG methods that we have tested in appendix E.5 are implemented in the Domain-Bed package, which incorporates runtime optimizations that make direct comparisons inconsistent.\n\n3. We agree that the selection of the target recall (γ parameter) is important. We view this as an application-dependent choice, best determined by the user's specific requirements. However, we understand that studying the performance of the method as a function of the target recall can be helpful. We wish to point out the analysis of the role of this parameter in Appendix E.4; due to space constraints we could not include this analysis in the main body of the paper.\n\n4. We appreciate the suggestion to provide a clearer visualization of recall vs. set size. In our paper, we analyze how varying  γ values, which determine the recall, affect also set sizes across methods. We will summarize this analysis with a clearer graph, as suggested, to better illustrate the trade-off.", "claims_and_evidence": "- The claim that set-valued predictors can enhance robustness is backed by theoretical generalization bounds and experimental results showing improved performance metrics.\n- Empirical results on four WILDS datasets show SET-COVER achieves the target 90% recall level across more test domains than baseline methods while maintaining smaller set sizes than robust conformal methods.", "methods_and_evaluation_criteria": "The average set size metric provides a meaningful measure of prediction efficiency. The recall@90 pctg metric is appropriate for set-valued prediction problems.", "theoretical_claims": "I read the statements and skimmed the proofs.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "This paper builds on the distribution shift literature and that of conformal prediction methods.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "- Proposes a novel framework for tackling domain generalization through set-valued predictions. Lays out a strong theoretical foundation within this setting with VC-dimension analysis and generalization bounds.\n- Clear presentation of the trade-off between prediction set size and robust performance\n- Proposes a practical surrogate objective (SET-COVER).\n- Consistent performance improvements across multiple real-world datasets\n\n- Limited comparison with recent domain generalization methods beyond ERM and conformal prediction\n- Limited discussion of how to determine appropriate target recall levels in practice\n- Could show more metrics for a fuller picture of performance and tradeoffs. For example, you could draw a graph of Recall@N pctg as a function of N.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- How does SET-COVER compare with the baseline ERM method in terms of training / inference computational cost?\n- Have you explored how to automatically determine an appropriate target recall level for a new problem? The current approach treats it as a fixed hyperparameter.", "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": "NTf1nRcozt", "reviewer": "Reviewer_z1ne", "summary": "This paper proposed set valued predictions for domain generalization, with theories and experimental justifications. This work builds upon some theoretical basis on uniform convergence considering domains and the conditions of uniform convergence based on the finite VC-dimension. The paper further prove the achievable low loss in domain generalization under the conditional Gaussian domains. The SET-COVER model was proposed by minimizing prediction size and the loss across various domains, further modeled based on hinge-losses, and iterative optimized. In experiments on synthetic dataset and WILDS datasets, the proposed DG method demonstrated improved performance compared with ERM, CDF Pooling, CDF pooling, robust conformal predictor.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful review. Your questions and comments are very valuable and we appreciate the opportunity to clarify the key points raised. \n\n1. Our theoretical results address whether achieving a target performance level (e.g., passing a recall threshold level) on training domains generalizes to new domains and under what conditions this generalization holds. Based on this, we developed SET-COVER, which explicitly optimizes for a predefined recall level on training domains, while also minimizing prediction set sizes. The latter objective complements the generalization goal by ensuring efficiency in the learned sets. In our experiments we show that indeed the recall performance generalizes to new domains, as evident by the fact that recall levels of SET-COVER are above the target recall of 90% in most test domains.\n\n2. We acknowledge that Theorem 3.7 has limited scope, as it assumes normal distributions with all domains sharing the same covariance matrix up to a scaling factor. However, this assumption, though restrictive, aligns with common practices in DG research (e.g., Wald et al. (2021)). In our case, theoretical results with weaker assumptions have an additional difficulty, as briefly discussed in Section 3.1 of our paper. We thus view Theorem 3.7 as an illustration and motivation leading to our method and our empirical results.\nTo address potential limitations, we validate our claims empirically, including:\n* Experiments on synthetic Gaussian data where each domain has a different covariance matrix (Appendix E.3).\n* Real-world datasets to test robustness beyond the Gaussian assumption.  \n\n3. While our proofs build on VC-dimension and uniform convergence literature, their extension to a multi-domain setting introduces subtle but nontrivial modifications. Throughout the proofs in the appendices we attempt to highlight those subtle points and shed light on the differences that arise in the multi-domain setting compared to the classical one (As one example, the fact that in the multi-domain setting we focus on performance indicators instead of 0-1 loss requires a careful consideration). We recognize the need to emphasize these points further in the main text, and thank you for highlighting this issue. We will add details on these differences in the main text of our final submission.  \n\n4. We appreciate the concern regarding novelty. SET-COVER is derived from a principled, hard to compute optimization problem, and its intuitive design and ease of implementation are, in our view, key advantages.\nWe have included comparisons with SOTA DG methods from the DomainBed package, which were included in Appendix E.5 due to space constraints.  In these results we can see that our method, while being intuitive and relatively simple to implement, achieves competitive results compared to advanced DG methods (e.g., feature alignment approaches). We view this result as a strength of our work.\n\n5. In our literature review, after briefly describing the main research efforts put into DG problems in recent years, we focus on works that integrate set-valued predictions within some variants of DG settings, as these are the most directly relevant to our approach. However, we acknowledge the broader DG literature and as mentioned above in Appendix E.5 of our submission we included experimental comparisons with leading single-valued prediction methods.", "claims_and_evidence": "The paper claimed a theoretical framework defining successful set prediction in DG setting, and provide theoretical insight on the condition that DG is achievable. However, the major concern is on the applicability and impact of these theoretical analysis. For example, the Theorem 3.7 is restrictive by assuming conditional Gaussian of domains, which is  unrealistic in the real world domain data.", "methods_and_evaluation_criteria": "How the above theoretical analysis inspire the design of the optimization model and algorithm? The deduced model is intuitive and simple, lacking novelty comparing with diverse kinds of DG models in literature, e.g., by aligning feature distributions, data augmentations, etc. Moreover, the compared datasets and methods are quite limited, hardly justifying the performance compared with the sota DG methods.", "theoretical_claims": "I did not fully check the proof but the proof is based on the VC-dimension, and the novelties of these math deductions should be clarified, including not only the deduced theoretical results for DG, but also the key contributions in the proof process.", "experimental_designs_or_analyses": "The compared baseline methods are limited to some baseline methods, including ERM, Pooling CDFs, Robust Conformal. As we know, the DG methods are diverse in the context of CV and ML literature. The manuscript should fully refer to the related DG methods and conduction full comparisons with sota methods.", "relation_to_broader_scientific_literature": "Domain adaptation is an important task, and this work presents the theoretic analysis on the conditions of DG across domains. However, these theories lack significant impact on the design of novel DG methods, and the contributions of this paper is limited in the context of DG literature.", "essential_references_not_discussed": "The paper lacks the full survey of DG literature, especially on the more recent DG methods.", "other_strengths_and_weaknesses": "The major strength of this paper is on the theoretical analysis on the conditions of achieving domain generalization. However, the novelty and significance of these theories are not clearly presented. Especially, they did not fully inspire the novel and effective designs of DG models and algorithms. The limited experimental comparisons are also the major limitation of this work.", "other_comments_or_suggestions": "None", "questions_for_authors": "(1) Set valued prediction is common in the multi-class classification tasks in the DG setting. This paper claimed the novelty on the set valued prediction, which should be more careful in the claim. The question is what is the major novelty on the set valued prediction in this work?\n\n(2) What is the relationship between the model in section 4 with the theoretical analysis in the previous sections?\n\n(3) The deduced model contains the minimization of size of the prediction set as one objective, which is confusing in the motivation and the meaning of  \"prediction set\".\n\n(4) Please extend the compared methods to include more sota DG methods.", "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": "FJHsbte2bs", "reviewer": "Reviewer_g5ia", "summary": "This paper introduces a set-valued predictor approach for domain generalization (DG) to address the limitations of single-valued predictions in unseen domains. The authors argue that set-valued outputs can capture diverse feature-label relationships across domains, enhancing robustness. They present a theoretical framework defining success criteria for set prediction in DG and derive generalization bounds under specific conditions. The proposed method, SET-COVER, optimizes prediction set size while ensuring coverage guarantees through constrained learning. Experiments on synthetic data and real-world WILDS benchmarks demonstrate that SET-COVER achieves higher coverage with smaller set sizes compared to conformal prediction baselines, offering a promising direction for reliable ML systems in critical applications like healthcare.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable feedback. We appreciate your insights and are happy to address your concerns.\n\n1. SET-COVER incurs a higher training time (~30% increase over ERM) due to the additional optimization of Lagrangian multipliers (denoted as C in our algorithm). Below are the average training times (single GPU) for our experiments:\n\n* Camelyon: ERM: 98 min, SET-COVER: 133 min\n\n* Fmow: ERM: 45 min, SET-COVER: 56 min\n\n* iWildCam: ERM: 46 min, SET-COVER: 58 min\n\n* Amazon: ERM: 12 min, SET-COVER: 15 min\n\nWe will include these results in the final version. Notably, our current implementation can be  further optimized by, for example, exploiting GPU parallelism. We anticipate that a more efficient implementation would significantly reduce the additional computational overhead. Apart from this step, SET-COVER primarily involves optimizing a loss function composed of hinge losses, which does not introduce substantial extra computation beyond standard architectures.\n\nTrain times of  other set-prediction methods are approximated by those of ERM, as other set-prediction methods train ERM as a first stage, which consumes most of the training time.\nAdditionally, the other SOTA DG methods that we tested in appendix E.5 are implemented in the Domain-Bed package, which incorporates runtime optimizations that make direct comparisons inconsistent.\n\n2. We recognize the importance of evaluating SET-COVER in scenarios with more training domains. Our initial focus was on datasets with sufficiently rich domains to first validate our method.\nAlthough the field of Domain Generalization (DG) gained popularity in recent years, the availability of datasets for DG experiments remains limited. WILDS is one of the most comprehensive sources of datasets for DG problems, which led us to focus on utilising it for our experiments. Out experiments included:\n* 20 training domains for Camelyon dataset\n* 20 training domains for Fmow dataset\n* 80 training domains for ICamWild dataset\n* 500 training domains for Amazon dataset (however each data point consisted of a relatively short test instance)\n\nAs larger and more diverse DG datasets become available, we look forward to further testing SET-COVER’s performance in multi-domain settings. We view this as an important direction for future work.", "claims_and_evidence": "The paper's claims are validated through both theoretical and empirical evidence.", "methods_and_evaluation_criteria": "Yes the proposed methods make sense for the problem or application at hand.", "theoretical_claims": "Theoretically, generalization bounds based on VC-dimension are established, proving that linear hypotheses under conditional Gaussian assumptions achieve coverage guarantees on unseen domains with sufficient training domains.", "experimental_designs_or_analyses": "The validation experiments cover synthetic data and multimodal datasets such as real medical and satellite images, and the data show that the new method not only maintains more than 95% of the recognition rate of key features in tasks such as tumor recognition and geographic classification, but also reduces the probability of false alarms to one-third of that of the traditional method, which provides a new technological path for scenarios with a very low tolerance for error such as autonomous driving and precision medicine.", "relation_to_broader_scientific_literature": "This paper opens a new direction for domain generalization research by introducing an ensemble prediction and theoretical analysis framework, which promotes the exploration of machine learning at the intersection of out-of-distribution generalization and uncertainty modeling.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strengths:\nThis paper presents the first theoretical framework for domain generalization based on ensemble prediction, which provides a new theoretical perspective on multi-domain robustness.\nThe approach proposed in this paper provides more reliable coverage guarantees and reduces the risk of missed diagnosis in high-risk domains such as healthcare.\n\nWeakness:\nSET-COVER's dual optimization process may increase training time and has limited scalability for large-scale data.\nThe effectiveness of the method proposed in this paper may decrease with the number of training domains, and the performance of small-sample multi-domain scenarios is not fully explored.", "other_comments_or_suggestions": "no", "questions_for_authors": "no", "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": "M02czf9z5d", "reviewer": "Reviewer_Taio", "summary": "The paper introduces a set-valued prediction approach for robust Domain Generalization (DG). It argues that single-valued predictions limit robustness, proposing instead to predict sets of labels to achieve reliable coverage across unseen domains. The authors provide theoretical generalization bounds and introduce an optimization algorithm (SET-COVER) to minimize set size while maintaining performance guarantees. Experimental results on WILDS datasets show improvements over existing baselines in robustness and prediction set efficiency.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful  review. We have gained many important insights from your questions, and appreciate the opportunity to address your concerns.\n\n1. SET-COVER incurs a higher training time (~30% increase over ERM) due to the additional optimization of Lagrangian multipliers (denoted as C in our algorithm). Below are the average training times (single GPU) for our experiments:\n\n* Camelyon: ERM: 98 min, SET-COVER: 133 min\n\n* Fmow: ERM: 45 min, SET-COVER: 56 min\n\n* iWildCam: ERM: 46 min, SET-COVER: 58 min\n\n* Amazon: ERM: 12 min, SET-COVER: 15 min\n\nWe will include these results in the final version. Notably, our current implementation can be  further optimized by, for example, exploiting GPU parallelism. We anticipate that a more efficient implementation would significantly reduce the additional computational overhead. Apart from this step, SET-COVER primarily involves optimizing a loss function composed of hinge losses, which does not introduce substantial extra computation beyond standard architectures.\n\nTrain times of  other set-prediction methods are approximated by those of ERM, as other set-prediction methods train ERM as a first stage, which consumes most of the training time.\nAdditionally, other SOTA DG methods that we have tested in appendix E.5 are implemented in the Domain-Bed package, which incorporates runtime optimizations that make direct comparisons inconsistent.\n\n2. We acknowledge that Theorem 3.7 has limited scope, as it assumes normal distributions with all domains sharing the same covariance matrix up to a scaling factor. However, this assumption, though restrictive, aligns with common practices in DG research (e.g., Wald et al. (2021)). In our case, theoretical results with weaker assumptions have an additional difficulty, as briefly discussed in Section 3.1 of our paper. We thus view Theorem 3.7 as an illustration and motivation leading to our method and our empirical results.\nTo address potential limitations, we validate our claims empirically, including:\n* Experiments on synthetic Gaussian data where each domain has a different covariance matrix (Appendix E.3).\n* Real-world datasets to test robustness beyond the Gaussian assumption.  \n\n3. We would like to highlight the novelty our paper brings to the field of Domain Generalization (DG). While conformal predictors are a powerful approach to DG problems, we primarily use them as baselines to compare against our proposed method, SET-COVER. Unlike conformal prediction, SET-COVER is an optimization-based approach designed for modern neural network architectures, offering set-valued predictions with optimized sizes. We see this as a fundamentally new alternative for set-valued predictions in DG.\n\nAdditionally, while our theoretical analysis builds on VC-dimension and uniform convergence literature, extending these concepts to a multi-domain setting requires subtle but significant modifications. In the appendices, we aim to highlight these nuances and the key differences that arise in the multi-domain context compared to classical settings. For example, we found that shifting the focus from 0-1 loss to performance indicators required a careful consideration, as further described in Appendix A1. We acknowledge the importance of further emphasizing these distinctions in the main text and appreciate your feedback on this point. We will incorporate additional details on these differences in our final submission.", "claims_and_evidence": "Overall, the paper's claims are largely supported, though some gaps remain.\n\nThe theoretical generalization results (VC-dimension-based bounds) rely on restrictive assumptions (e.g., conditional Gaussianity, identical covariance structures across domains.", "methods_and_evaluation_criteria": "Yes, the methods and evaluation criteria generally make sense.\n\nHowever, the paper could further strengthen evaluation by considering metrics beyond average recall and set size, such as computational overhead or interpretability.", "theoretical_claims": "Yes, I checked the theoretical claims—particularly the generalization bounds involving VC-dimension (Theorem 3.7).\n\nA potential issue is that the theoretical results hinge on overly restrictive assumptions: specifically, the conditional Gaussian assumption with identical covariance structures (up to a scaling factor) across all domains. This assumption is highly unrealistic for most real-world DG scenarios, and the paper does not sufficiently justify or empirically validate its reasonableness, weakening the theoretical claims substantially.", "experimental_designs_or_analyses": "Yes, I reviewed the experimental designs, especially those involving real-world datasets from the WILDS benchmark. \n\nOne notable issue is that the paper's main experiments primarily emphasize recall and prediction set size but do not sufficiently analyze trade-offs such as computational cost, calibration robustness, or practical usability of large prediction sets.", "relation_to_broader_scientific_literature": "The paper extends the idea of set-valued predictions—commonly explored in conformal prediction literature—to Domain Generalization (DG). It builds upon prior work by explicitly addressing worst-case performance guarantees rather than average-case coverage.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "**Strengths:**\n\n- Clearly addresses the important problem of robust domain generalization from a fresh perspective (set-valued predictions).\n- Combines theoretical and practical aspects effectively, offering well-motivated theoretical bounds alongside a practical optimization approach.\n- Empirical results convincingly demonstrate improved robustness on realistic and challenging datasets.\n\n**Weaknesses:**\n\n- Key theoretical results depend heavily on restrictive assumptions (Gaussianity, identical covariance), limiting their practical relevance.\n- Experimental analysis lacks consideration of important practical trade-offs (e.g., computational overhead, interpretability of set predictions).\n- Methodological novelty is incremental; the paper largely adapts existing conformal prediction and classical learning theory concepts without significant theoretical breakthroughs or novel algorithmic contributions.", "other_comments_or_suggestions": "Line 665: destributions\" → \"distributions\"", "questions_for_authors": "See weeknesses.", "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: This paper presents a domain generalization (DG) method based on set-valued predictors to enhance robustness. The main strengths and weaknesses initially pointed out by the reviewers are summarized as follows.

Strengths: 
- Proposes a novel framework for tackling domain generalization through set-valued predictions
- Provides theoretical foundation to support the claim that set-valued predictors can enhance robustness
- Proposes a practical optimization method (SET-COVER) based on a surrogate objective with reliable convergence guarantees 
- Empirical results convicingly support the claim that the method improves robustness in DG

Weaknesses:
- Insufficient experiments in terms of benchmark datasets and compared DG methods
- Lack of analysis and evaluation regarding computational overhead of the methods
- Provided theoretical foundation heavily relies on restrictive assumptions (conditional Gaussianity, identical covariance across domains) which are unrealistic in the real world
- Novelty and significance of the math deduction process is not clear since the paper largely adapts existing conformal prediction and classical learning theory concepts 
- The deduced model is also lacking novelty when compared to broader DG models in literature

The authors responded to those concerns with some new results and clarifications. Notably, they clarified that comparison to broader SOTA DG methods has been done in appendix, and also added some results and discussion regarding computation overhead.   
Overall, the authors’ response was favorably received by the reviewers, and two of them (z1ne, Taio) have increased the scores from 1 to 2 and 3 to 4, respectively. As a result, the final review scores are [3, 2, 3, 4].   
While the AC agrees with the z1ne’s point of view that strong assumptions behind the theory and incremental novelty in the resultant method remain limitations, the AC believes that the paper explores a novel direction in DG and sets a good starting point for later research to follow, supported by a reasonable theoretical foundation as well as extensive empirical observations. Overall, the AC concludes that the pros of this paper outweigh the cons, therefore recommends acceptance.
Decision: Accept (poster)