Finding lost DG: Explaining domain generalization via model complexity
Authors: Da Li
Henry Gouk
Timothy Hospedales
Venue: ICLR 2022 Submitted (2022)
Keywords: domain generalisation
rademacher complexity

Abstract: The domain generalization (DG) problem setting challenges a model trained on multiple known data distributions to generalise well on unseen data distributions. Due to its practical importance, a large number of methods have been proposed to address this challenge. However most of this work is empirical, as the DG problem is hard to model formally; and recent evaluations have cast doubt on existing methods’ practical efficacy -- in particular compared to a well chosen empirical risk minimisation baseline. 
We present a novel learning-theoretic generalisation bound for DG that bounds novel domain generalisation performance in terms of the model’s Rademacher complexity. Based on this, we conjecture that the causal factor behind existing methods’ efficacy or lack thereof is a variant of the standard empirical risk-predictor complexity tradeoff, and demonstrate that their performance variability can be explained in these terms. Algorithmically, this analysis suggests that domain generalisation should be achieved by simply performing regularised ERM with a leave-one-domain-out cross-validation objective. Empirical results on the DomainBed benchmark corroborate this.

Under review as a conference paper at ICLR 2022
FINDING LOST DG: EXPLAINING DOMAIN GENERAL- IZATION VIA MODEL COMPLEXITY
Anonymous authors Paper under double-blind review
ABSTRACT
The domain generalization (DG) problem setting challenges model trained multiple known data distributions to generalise well on unseen data distributions. Due its practical importance, a large number of methods have been proposed address this challenge. However most of the work in general purpose DG is heuris- tically motivated, the DG problem hard to model formally; and recent evalu- ations have cast doubt on existing methods' practical efficacy in particular com- pared to well chosen empirical risk minimisation baseline. We present a novel learning-ther -eteoinntthoorticc generalisation bound for DG that bounds novel domain gener- alisation performance in terms of the model's Rademacher complexity. Based on this, we conjecture that existing methods' efficacy or lack thereof is variant of the standard empirical risk risk-predictor complexity trade-off, and demonstrate that their performance variability can be explained in these terms. Algorithmically, this analysis suggests that domain generalisation should be achieved by simply performing regularised ERM with a deave-one-domain-o0 tive. Empirical results on the Domain Bed benchmark corroborate this.
vross-validation objec-
INTRODUCTION
Machine learning systems have shown exceptional performance on numerous tasks in computer vision and beyond. However performance drops rapidly when the standard assumption of i.i.d. training and testing data is violated. This domain-shiff phenomenon occurs widely many appli- cations of machine learning (Csurka 2017 Zhou et al. 2021 Koh et al.) [021), and often leads to disappointing results practical machine learning deployments, since data 'in the wild' is almost inevitably different from reference training sets.
Given the practical significance of this issue, a large number of methods have been proposed that aim to improve models' robustness to deployment under different distribution than used for train- ing (Zhou et al. 202T), a problem setting known as domain generalisation (DG). These methods span diverse approaches such as specialised neural architectures, data augmentation strategies, and regularisers. Nevertheless, the DG problem setting is difficult to model formally for principled derivation and theoretical analysis of algorithms, the target domain of interest unobservable during training, and cannot be directly approximated by the training domains due to unknown distribution shift. Therefore the majority of these existing approaches are based on poorly understood empirical heuristics.
To make matters worse, a recent study by Gulrajani & Lopez-Paz 2021 assessed the state of DG research with a carefully conducted comparative evaluation of algorithms on a large benchmark suite under a common platform. They found that published methods were not as effective as claimed, and in particular reported that "no existing method reliably beats well tuned empirical risk minimization (ERM) baseline'. We argue that this negative result highlights the need for better theory this area in order to understand why existing algorithms have such erratic performance, and to guide the development of principled algorithms that are more effective and reliable.
To this end, our first contribution is to present intuitive learning-theoretis bound for DG perfor- mance. Intuitively, while the held-out domain of interest is indeed unobservable during training, we can bound its performance using learning theoretic tools similar to the standard ones used to bound the performance on (unobserved) testing data given (observed) training data. In particular we show that the performance a held out target domain is bounded by the performance known source

---

Under review as a conference paper at ICLR 2022
domains, plus two additional model complexity terms, that describe how much model can possibly have overfitted to the training domains. This theoretical contribution leads to several insights.
Firstly, our theory suggests that DG performance is governed by trade-off between empirical risk and model complexity that is analogous to the corresponding and widely understood trade-off that explains generalisation in standard i.i.d. learning
overfitting weefftting-underfttiingg trade-off (Geman
let al. T992). Based on this, we hypothesise that performance variability is determined by implicit or explicit regularisation. That is, the plethora of different strategies available (Zhou al. (021 from Gata-augmentation to specialised optimisers actually affect DG performance by explicitly or implicitly choosing different fitcomplyxity trade-offs. We corroborate this hypothesis by evaluating a number of models in the DomainBed suite in terms of complexity, and showing that their appar- ently erratic performance in Gulrajani Lopez-Par (021) is actually consistent with an explanation in terms of implied complexity.
Practically, our analysis suggests that the model selection strategy (Hastie et al. 2009 fac- tor in DG performance that is at least as important the actual mechanism of model complexity control (i.e., Tuning of regularisation strength vs specific parametric design of regulariser). In par- ticular, regularisation should be stronger when optimizing for future DG performance than when optimizing for performance on seen domains. Unfortunately, model complexity is hard to carefully control in deep learning due to the large number of relevant factors (architecture, regularisers, im- plicit regularisation from optimiser, etc). Gulraaani & Lopez-Paz (2021) attempted to address this by hyper-parameter search in the DomainBed benchmark, but are hampered by the computational in- feasibility of accurate hyper-paramelce search. In this paper, we use linear models and off-the-shelf self-supervised features to demonstrate much more clearly how cross-domain performance depends on complexity. Specifically, our theoretical and empirical results show that, contrary to the conclu- sion of Gulrajani Lopez-Paz (202I), simple domain- -wise cross-validatinn is better objective to drive DG model selection.
In summary, based on our new generalisation bound, and associated empirical analysis, our take- home messages are: (i) Model fit vs complexity trade-off is a key determinant of DG performance, that explains existing DG algorithm performance variability. (ii) The complexity control strategy used to determine bias-variance trade-off is crucial in practice, with peak DG performance achieved when optimizing model complexity based on domain-wise validation. (iii) Regularisation required performance.
for optimal DG is greater than for conventional optimization for
2 RELATED WORK
Theoretical Analysis of the DG Setting and Algorithms
The DG problem setting was first anal-
ysed in Blanchard et al. (201I) Since then there have been some attempts to analyse DG algorithms
from a generalisation bound perspective (Muandet et al. 2013 Blanchard et al. 202T Hu et al., 2020 Albuquerque et al. 2020: Rosenfeld et al. 2021). However these studies have theoretical results that are either restricted to specific model classes, such as kernel machines, or make strong assumptions about how the domains seen during training will resemble those seen at test time-e.g.. that all domains are convex combinations of a finite pre-determined set of prototypical domains. In contrast, our Rademacher complexity approach can be applied to a broad range of model classes (including neural networks), and makes comparatively milder assumptions about the relationship between domains they are i.i.d. samples from another arbitrary distribution over domains.
The majority of the existing work investigating the theoretical foundations of DG follow the initial formalisation of the domain generalisation problem put forth by Blaacharrd al. (201T). where the goal is to minimise the expected eтror over unseen domains. However, several recent works have also explored the idea of bounding the error on a single unseen domain with the most patholog- ical distribution shift (Janzing) 2019). This type of analysis is typically rooted in methods from causal inference, rather than statistical learning theory. As a consequence, they are able to make stronger claims for the problems they address, but the scope of their analysis is necessarily limited to the scenarios where their assumptions about the underlying causal structures are valid. For exam- ple, Janzing (2019) provides bounds that assume problems conform to specific class of structural equation models, and the analysis is performed under the assumption that infinite training data is available within each of the observed training domains. Throughout the work we address the stan-
2

---

Under review as a conference paper at ICLR 2022
dard DG formalisation given by Blanchard et al. (0111). where one is concerned with the expected performance of a model on domains sampled from some distribution over domains.
Others rely trying to link between domain adaptation objectives (where target domains are ob- servable for alignment to source domains) and domain generalisation (where target domains are not observable and thus cannot correctly be used in learning objective). [Albuquerque al. (2020) proceed by making assumptions on the structure of the distribution over possible domains (i.e., that has support determined by the convex hull of finite set of prototypical domains), which allows them to upper bound the domain alignment metric. Ye et al. (202T) provide a bound that depends on an unobservable domain distance quantity, which they then approximate in experiments using kernel density estimates.
Rosenfeld al. (2021) is another piece of work that theoretically investigates the generalisation of ERM in DG setting. They deal with online DG, where each time-step corresponds to observing new domain, and the learner must produce new model capable of generalising to novel domains. Another point of difference between their work and the standard DG problem setting of Blanchard jet al. (2011) is that the domain at each time-step chosen by an adversary. They analyse this game for finite number of time-steps, but they assume each domain has an infinite amount of data. They also put some limitations on the adversary: c.g., it must choose a domain that a convex combination of a finite number of pre-determined domains. In contrast, our theoretical analysis is in the more realistic setting where one has a finite amount of data per domain, and the domains we consider are not limited to convex combinations of set of prototypical domains. Possibly the most similar work to our theoretical contributions is due to Ahuja et al. (2021). who also provide learning- theoretic generalisation bounds for DG. However, their analysis only applies finite hypothesis classes (which does not include, e.g., linear models or neural networks), whereas ours can be applied to any class amenable analysis with Rademacher complexity.
Empirical Analysis The main existing empirical analysis on DG is Gulrajani & Lopez- (2021), who compared several state of the art DG methods under common evaluation and hyper-ppaaee parameter tuning protocol called DomainBed. They ultimately defend Empirical Risk Minimization (ERM) over more sophisticated alternatives on the grounds that no competitor consistently beats across the benchmark suite. We also broadly defend ERM, and build on the same benchmark, but dif- ferently we provide a much deeper analysis into when and why ERM works. More specifically: (i We provide new theoretical analysis of ERM's generalisation quality unlike the prior purely empirical evaluation, (ii) We re-use the DomainBed benchmark to directly corroborate this theory under controlled conditions using linear models where model complexity can be tractably and curately tuned. (iii) We use our complexity-based analysis to explain the previously erratic results of prior DomainBed competitors in terms of model complexity. (iv) We identify, and empirically validate, the preferred model selection criterion for DG, a point which was inconclusive in Gulrajani & Lopez-Paz (202T)
3 BOUNDING RISK FOR DOMAIN GENERALIZATION
Li.d. learning is concerned with learning a mapping from some input space X', to a label space ), given data drawn from a distribution on X' x J. One aims to find model, f E F, that minimises the expected loss (also called risk) on unseen data,
arg min (f),, fEF
Lp(f) = ((a,))-((((((
where p is the data distribution and ((:,-) is the loss function. In practice, we only have access to a finite set of data, S = ((T, m sampled i.i.d. from this distribution, so must minimise an empirical risk estimate,
f arg min i,),) JEF
L.(0= - ((((T.).
1
where m is the number of training examples. One of the central focuses of statistical learning theory is to bound the difference between these two types of risk. For example, in the standard single domain setting this can be done via
[n(1/8) T
Lp(s) s i,()) + 2Rm (F)+
(3)
3

---

Under review as a conference paper at ICLR 2022
which holds with probability least 1 - 6, and R(F) is known as the empirical Rademacher com- plexity the hypothesis class, F. This complexity term is defined as
m
Rm (F) Eg
sup feF
a.l(f(()))
m
For hypothesis class consisting of norm-consttained linear classifiers, achieve the follow- ing upper bound on the empirical Rademacher complexity (Shalev-Swaartz Ben-Davin 2014).
XB
Rm (F)
F ( | S B}.
Vm
where we assume that each input, F. has a Euclidean norm of at most X. There are variety of ways define hypothesis classes for neural networks, but most recent approaches take the view of fixing a particular architecture and specifying constraints on the norms of weights or distances they can
move from their initialisations (Bartlett et al. 2017 Neyshabur al. 2019 Gouk al. 202T).
Domain generalisation. While standard i.i.d. learning assumes all data come from the same dis- tribution, the DG problem setting assumes the existence of an environment &, of distributions p Blanchard et al. (20T)) Note that we do not restrict what types of differences one could see between different domains sampled from E: for any two distributions in p. (ssup(()) it could be the case that either p(#) o ( or p(ulz) ( F {))(z)), or even that both types of distribution shift have occurred. The conceptually simplest- and often implicitly issumed-gov of DG methods to minimise the expected risk across different distributions that could be sampled from the environment,
(f) = B (Tpp
(5)
This object is also the most commonly analysed idealised objective the learning theory literature (Blanchard et al.) 2 Muandet et al., 2013 Blanchard et al., 2021; Rosenfeld et al.) 2021). but other formulations also exist (Arjovsky et al. 2019). As with the single domain learning problem, only have access empirical estimate of the risk,
L iE( = Σ (f).
(6)
j=1
where we assume for ease of exposition that all n domains have the same number of examples.
3.1 BOUNDING THE GENERALISATION GAP
We next bound the generalisation gap between the observed empirical risk, i.F. on the source do- mains and the expected risk, I on unseen domains that holds uniformly for all hypotheses in F.
Theorem 1. For I-Lipschitz loss, E(.)),, taking values in [0, 1), with confidence least 1 25 for all f E F we have that
In (2/0))
1n(2/88
LE()) i. 2R (F) 2R, (F) 3v
3/
2mn
2n
where is the number of training domains and m is the number of training examples in each training domain.
The proof can be found in Appendix
Discussion Theorem tells us that expected risk on unseen domains is bounded by the empirical risk (training loss) on seen domains, plus Rademacher complexity terms and sampling error terms that decay with the number of domains and training instances per domain. As with typical single- domain bounds, the latter sampling error terms are not under control of the model designer. The former Rademacher terms describe the complexity of the chosen model class and govern how much could possibly overfit to the seen domains while minimising empirical risk. In the case of linear models, these terms depend on properties the chosen network architecture. Mirroring conventional generalisation in standard i...d. learning, very simple model may minimise the Rademacher terms, R. while producing high
weight norms, while in the case of deep models they further depend
4

---

Under review as a conference paper at ICLR 2022
empirical risk, L and vice-versa. Thus good generalisation critically depends on a carefully chosen empirical risk vs model complexity trade-off. The difference between Theorem and single domain bounds (e.g., Equation B] is the additional dependence the number of domains n and additional Rademacher complexity term. This implies that when the goal is to generalise to new domains, the optimal for held out domain performance compared to seen domain performance in standard i.i.d. learning.
risk of overfitting is higher. Therefore expect lower complexity model
3.2 BOUNDING THE EXCESS RISK OF ERM
As a second theoretical contribution, we next bound the excess expected risk between the ERM solution f and the best possible model f within the function class F. Note that bounding excess risk, as opposed to the generalisation gap, overcomes some of the known issues with theoretically analysing the generalisation properties of deep networks (Belkin et al.) 2018).
Corollary 1. With probability as least 1 - 26, the excess risk of the empirical risk minimiser in F bounded as
ln(2/5)
In(2/8)
B BIT - T, ((*) 2m (F) (F) + +
2mn + +2
2n.
uses the same technique as the usual proof for excess risk (see, e.g., Pontil & Maurer (2013)). and some of the intermediate results required for Theorem []
The proof (in Appendix B
Discussion Corollary D tells us that the gap between ERM and the best possible predictor in the function class depends on the same complexity terms observed in Theorem [ In par- ticular, for any typical hypothesis class, ERM converges to the optimal classifier at a rate of (m//mmm) ((1/ Vn). To justify itself theoretically, any future DG method that claims to be better than ERM should either: (1) demonstrate a faster convergence rate than this-at least by an improved constant factor, or (2) formally show that the chosen hypothesis class is composed of models that can extrapolate to new domains without additional data. The latter would likely involve making specific assumptions about the underlying data generation process, coupled with analysis of a specific hypothesis class using methods from causal inference. An example of such analysis given by Janzing] (2019). Methods based on causal inference have the potential to give bounds with much better convergence rates than the rate given above. However, because one must make assumptions about the underlying family of structural equation models, the applicability of such bounds is much more restricted than our Rademacher complexity technique, which does not require these assumptions.
4 EXPERIMENTS
Based on our previous theoretical analysis, we conduct experiments on DomainBed (Gulrajani & Lopez- Lopez-Pazz 2021). In particular we aim to address the following questions: (1) Theorem shows that novel domain generalisation performance is governed by empirical-risk complexity trade-off. Can we directly demonstrate the dependence of generalisation on complexity by controlling for model complexity? (2) Can the erratic performance state of the methods previously observed on DomainBed be explained in terms of model complexity? (3) Given that model complexity is crucial determinant of generalisation, what the best objective for luning regularisation strength?
4.1 DOMAIN GENERALISATION PERFORMANCE DEPENDS ON MODEL COMPLEXITY
To directly investigate the impact of model complexity on domain generalisation performance, we first work with Linear SVM applied to pre-computed deep feature |] In this function class model complexity can be directly controlled by a scalar hyper-parameter, the objective is convex so con- founding factors in deep network training (optimiser choice, carly stopping, etc) disappear, and training fast enough that we can densely and exhaustively evaluate wide range of complexities.
Note that when a fixed feature extractor, any other preprocessing is used, it does not impact the model complexity associated generalisation bound.
5

---

Under review as a conference paper at ICLR 2022
0.3
0.7
Tel securse
0.50
0.5
0.6-
0.5
0.7
0.70
Acress coma (2ble)
Acrosa-dommn id vibal
Acrssa-deman dins viae
0.4
Wilte-damaln (jredl
0.6
White damal (dio vi58)
0.65
W Widdman forn visal
509
Across danain varsa Witte-comuh an Offictume
Adozi-daman vesus W W.n.ddmannnncoommm Snhoo
As doma vesus Wit i Tunamoagn
100
0.3
Ter ScruNC
0.7-
0.3
Tee
0.7
0.6
WeNi-domth
G=2"
Figure I: Linear SVC performance on DomainBed benchmark datasets is governed by model com- plexity parameter C. Optimal tuning for performance on novel target domains (DG condition, red) always requires stronger regularisation (lower C*) than for performance on seen domains (blue).
Setup We use DINO (Caron et al. 2021 pre-trained models, such as DINO-ViTB8 and DINO-
ViTS8 to extract features, and then train LinearS classifiers. We experiment on six different DG benchmarks, including RotaTedMNIST (Ghifary et al., 2015), PACS (Li al.) 2017). VLCS (Fang
et al. 2013). OfficeHome (Venkateswara et al. 201 7. SVIRO (Dias Da Cruz et al. 2021) and
Terra Incognita (Beery et al.) 2018). Different trials have different numbers of training instances in practice, so we used linear SVM objective of the form e Σ (z,, 9:)++ +| [|el] with parameter C' conttolling the complexity of model w through loss-regularisation trade-off. We searched a wide range of log, C' in {-10, 10). We then conduct two experiments, holding training and test split size constant across both: (i) Training on the train splits of all domains, and testing on the test splits of all domains (i.e., standard i.i.d. learning). (ii) Training on the train splits of three domains, and testing on the test splits of a held out domain (i.e., DG performance).
The results in Fig 1 average over 5 random seeds for dataset splitting, and all choices of hold-out target domain. From these we can see that: (i) all experiments exhibit the classic trade-off between fitting the data well and constraining hypothesis class complexity appropriately. We ob- serve underfitting for high regularisation (small C), and overfitting at low regularisation (large C). (ii) Comparing the within- and across-domain evaluation: across-domain leads to lower performance- which is to be expected, due to the distribution shift. A more noteworthy observation is that, the optimal regularisation for novel-domain performance is stronger than for seen-domain performance (red vertical lines left of blue). This corroborates our theoretical result that the ideal model com- plexity lower for DG than for conventional i.i.d. learning. Note that these results are using an exhaustive oracle to explore mode complexity, and do not constitute complete algorithm, which would need to chose a specific complexity. We discuss an algorithm in See 4.3
Results
4.2 EXPLAINING DOMAINBED DG PERFORMANCE IN TERMS OF COMPLEXITY
Our experiment in Section 4.1 showed that linear models exhibit very clean trade-off between com- plexity and generalization. However there are many subtle factors that influence effective model complexity in neural networks besides architecture: learning rate, learning rate schedule, weight decay, early stopping, etc; and the repeatably of learning is hampered by non-convexity, stochas- tic initialization, and stochastic mini-batches, etc. The previous evaluation study of Gulrajani & Lopez-Paz (202I) attempted some degree of control over these factors for state of the art neural DG methods by applying a common hyperparameter search strategy that aimed to find the best tuning (cf: Fig [T for each competitor. They nevertheless found existing methods to perform unreliably. search trials (20) used was far too few to reliably tune the deep networks evaluated, and therefore the tuning of each model
Our conjecture is that the number of seed samples (3) and

---

Under review as a conference paper at ICLR 2022
was inaccurate and performance estimates unreliable. Since dense and accurate hyper- parammeeeeeeer tuning for neural networks is more challenging than our linear models in Section 4.1 we take a different approach. Rather than trying to control complexity directly, we take trained DomainBed methods and measure their complexity retrospectively.
Setup To ensure that complexity can be measured accurately, work with 2-layer MLPs. Specif- ically, we take fixed ImageNet pre-trained ResNet- 18 features, and feed them to MLPs, which are then trained using the DomainBed framework. 2-layer MLPs are sufficient instantiate many of the state of the art DG algorithms in DomainBed, We train and compare ERM, CORAL (Sun & Saenko, 2016), Mixup (Wang al. 2020), MMD (Li et al., 2018), RSC (Huang et al. 2020). SD (Pezeshki et al. 2020). VRex (Krueger et al.) 2020). and IRM (Arjovsky et al. (2019) with two hyperparameter choices. We also report the results of an ERM model, checkpointed at a range of training iterations.
Measuring Model Complexity Because we have limited our attention to 2-layer MLPs, we can take advantage of model capacity metric that is specialised for this class of models. We retro- spectively determine the complexity of trained network using the measure proposed by Neyshabur (et al. (2019), who also use this measure to bound the Rademacher complexity of a 2-layer MLP hypothesis classes. More concretely, the expression used for computing complexity is
c(fo.v) = -VII= U0 + 12).
where U is the weight matrix of the first layer, U is its random initialisation, and V is the weight matrix of the second layer. We use ||. ||e to denote Frobenius norm, and ||-112 to indicate the spectral norm. Note that for simplicity we have omitted constant factors that depend only on the architecture and problem setting, and not the learned weights, as we use the same architecture for all methods investigate.
The results in Figure 2 summarise the trade-off between measured model complexity (x- axis), and held-out domain test accuracy (y-axis), averaged over all choices of held out domain for each dataset (See Supplementary for full breakdown across all held-out domains). The top plot compares several of the published neural DG methods implemented in DomainBed. The main message of the top plot is that results are consistent with the hypothesis that the resulting complexity of the models trained by various DG methods is key factor in determining domain generalisation accuracy (compare Fig. 2 with the clean result for linear where models we are able to intervene and control complexity directly in Fig. 1 thus explaining the previously erratic hehaviour observed in domain-bed.
Results
To provide a different view of the same issue, the bottom plot reports vanilla untuned ERM model check-pointed every 300 training iterations between (up to a total of 15,000) but expressed in the same complexity units as above. Because neural models can gain complexity with iterations (see, e.g., [1998); Hardt et (2116)) we also see typical overfitting-unde underfitting trade-off curves. This shows that, as expected, proper choice of early stopping criterion is important. It also shows that over similar dynamic range of complexity (0.5-3), ERM (below) and alternative models (ahove) span a similar dynamic range of accuracy (e.g.. 6% for PACS). This suggests that complexity, as controlled by whatever mechanism, is a key determinant of DG performance.
How Do DG Models Control Complexity? By introducing different modifications to standard ERM, DG models explicidy implicitly modify the bias and variance of the function class to be learned. Gulrajani & Lopez-Paz (202T) highlight neural models as being dependent on learning rate, batch size, dropout rate, and weight decay; with other factors being choice of optimiser and weight initialiser, etc. For example, higher dropout rate and weight decay tend to reduce complex- ity, while some other factors influence complexity in a less transparent way. RSC introduce more sophisticated dropout-like mechanisms, which would be expected to reduce complexity. Meanwhile alignment-basee methods like CORAL and MMD effectively add auxiliary losses, which will im- plicitly affect complexity, but are hard to explicitly link to it. Consistency based methods like IRM and VRex penalise loss variance, which also tends to reduce the generalisation gap in the single task case (Maurer & Pontil 2009). The specific setting of all the corresponding (e.g.. regulariser strength, dropout rates) influence final model complexity, which we argue is the key determinant of performance.
7

---

Under review as a conference paper at ICLR 2022
OffecHonme
FACS
VLCS
+
CORAL
0.60
Aucracy
Accrnny
Accuazy
0.5
Mixup
0.04
MMD
0.4
IESC
0.02
(al))
0.3
1.2
Complesiy
Complesity
Complesit
FIM Checkguints OfficcHomee
EXM Checkpoints PACS
EXM Checspoints VLCS
0.75
Alcuacy
0.5
Acamay
0.74
0.64
0.58
0.73
0.02
0.1
0.6
0.8
1.2
1.4
1.5
0.5
1.5
0.5
2.5
Complesity
Complesiry
Complesity
Figure 2: Performance of neural networks as a function of their measured model complexity after training using DomainBed (DB). The overall results consistent with standard bias-variance trade-off (cf. Dig[[or for linear models): performance depends on how well each model was tuned by DB's hyper-parameter search procedure. Top: Leave-one-domainnou of various neural DG algorithms evaluated by DomainBed. Horizontal error bars correspond to the standard deviation of the model complexity measured for each cross-vare validation iteration. Bottom: Performance of ERM model checkpointed at different training iterations. The central tendency obtained via fitting a support vector regression model (Shevade al., 2000) with a 6th order polynomial kernel.
cross-validation performance
4.3 EVALUATING LINEAR MODELS DOMAINBED
Having demonstrated control of generalisation with linear model regularisation (Sec. 4.1) and ex- plained DomainBed performance post-hoc via measuring complexity of neural models (Sec. 4.2) next evaluate algorithms for practical complexity tuning. From Fig, we saw that within-domai and cross dooss-dominn evaluation have different optimal tuning. If we consider automating the search for good regularisation parameter, these two final evaluation criteria correspond respectively to hyper- parameter selection based on a validation set from the seen source domains, vs based on a validation unbiased
set drawn from held out source domain. The latter validation criterion corresponds estimator of expected cross-domain generalisation performance R (f), which our theorem bounds.
Setup We performed DG evaluation DomainBed using ERM with linear models using the same DINO features as Section 4.1 For each held out domain, we performed hyperparameter tuning with either instance-wiss cross-validation (where validation folds drawn from the same source domains used for training) or domain -iise cross-validation (where validation folds are drawn from held-out domains not seen during training).
The results in Table I report the average accuracy across held out domains, and the aver- age selected log C' regularisation strength (See Supplementary for the full breakdown of results for each held-out domain). We can see that the domain wise cross-validation objective leads to similar or better accuracy, and similar or smaller value selection (i.c., stronger regularisation). This out- come is opposite to the observation made by Gulrajani & Lopez-Paz (2021). Given the theoretical support for our domain- wise objective, and our clear empirical outcome when freed of confounding factors such stochasticity in neural network training, consider result to be decisive and attribute the different observation Gulrajani & Lopez-Pazz (202T) to the inaccuracy and stochasticity of hyperparameter tuning in neural networks.
Results
8

---

Under review as a conference paper at ICLR 2022
Domain Wisc
Instance Wisc
Acc
log C
Acc
log C
Raw pixel
RotatedMNIST
71.6
4.97 (#0.52)
71.2
6.82 (=0.228)
PACS
74.3
-1.73 (#0.40)
70.6
1.56 (#0.66)
VLCS
80.4
-1.04 (#00699)
80.5
-0,87 (#0.35)
DINO VIT-B8
OfficeHome
73.6
-0.17 (=0.35)
73.1
1.04 (=0.40)
SVIRO
97.2
0.21 (4-0.3))
95.3
4.85 (+-0.46)
Terra Incognita
45.4
-0.17 (4-0.87)
38.8
5.37 (+0.35)
PACS
73.0
-1.91 (+1.43)
71.6
1.04 (+0.89)
VI.CS
80.4
-1.91 (+0.66)
80.6
-1.21 (+0.35)
DINO VIT-S8
OfficeHome
72.2
-0.69 (+0.57)
72.3
0.35 (+0.40)
SVTRO
94.5
-1.18 (+0.47)
91.3
5.68 (+0.97)
Terra Incognita
37.1
0.00 (+1.50)
33.1
4.85 (+0.57)
Table 1: Comparing model selection criteria using LinearSVC. Accuracy and selected SVM reg- ularisation parameter 'C", Domain-wise validation outperforms instance-wise and selects stronger regularisation (lower C).
4.4 DISCUSSION
At the start of this section set out address three questions, which be answered as: (1) The dependence of cross-domain generalisation on complexity can be directly and precisely when using linear models. (2) The erratic performance of state of the methods in DomainBed can be largely explained in terms of implied model complexity. (3) If the goal is to optimise for domain generalisation, then then domain-wise validation preferred to rsstanee-wise validation as a model- selection objective.
Our analysis suggests that several existing methods that tried to tune learnable DG ppram-errameters by performance on held-out domain (Balaji et al. [2018] [i et al. 2019) were broadly on the right track, and concurs with Guttaaanr Lopez-Paz (2021) that those methods with underspecified hyper- parameter and model selection procedures are unhelpful. However, given that most neural methods have many more complexity hyperparameters than the single hyperparameter that we were able to carefully control for linear models, obtaining accurate tuning and reliable performance evaluation is likely to be challenge. Gradient- based hyper-parameter parameter estimation methods, as initially attempted in Balaji et al. (2018); [ et al.) (2019), together with efficient methods for long-inner loop hyper- gradient calculation (Lorraine et al., (020), may benefit the former problem by making search in larger numbers of hyperparameters more feasible. Alternatively, using general purpose pre-trained features (Caron et al. 202T) as we did here, and focusing on learning shallow models that can be accurately tuned for DG may another promising avenue in practice. Although achieving state of the art performance is not our focus, we note that our results in Table [ are quite competitive with end-to-end trained state of the art (Gulrajani Lopez-Paz 2021). despite using fixed features and shallow models.
5 CONCLUSION
In this paper we explained the performance of domain generalisation methods in terms of model complexity (bias-variance trade-off) from both theoretical and empirical perspectives. Both per- spectives show that complexity impacts cross-domain generalisation in way that closely mirrors the bias-variance trade-off conventional i.i.d. learning - but where stronger regularisation is required if optimising for cross-domain generalisation than if optimising for conventional within-domain generalisation. We clarified the preferred model selection criterion in each case. This analysis de- mystifies the problem being posed by the DG problem setting, why existing algorithms succeed or fail to work, and sets the bar for future theoretical theoretical studies to surpass in terms of conver- gence rates, well for future empirical studies to surpass in terms of strong baselines.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Kartik Ahuja, Jun Wang, Amit Dhurandhar, Karthikeyan Shanmugam, and Kush R. Varshney. Em- pirical or invariant risk minimization? sample complexity perspective. ICLR, 2021.
Isabela Albuquerque, João Monteiro, Mohammad Darvishi, Tiago H Falk, and Ioannis Mitliagkas. Generalizing to unseen domains via distribution matching, arXiv preprint arXiv:1911. 190,:0001,00 2020.
Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. arXiv, 2019.
Yogesh Balaji, Swami Sankaranarayanan, and Rama Chellappa. Metareg: Towards domain gener- alization using meta-regularization. In NeurIPS, 2018.
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. JMLR, 2002.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalized margin bounds for neural networks. NeurIPS, 2017.
Sara Beery, Grant Van Horn, and Pietro Perona. Recognition in terra incognita. In ECCV, 2018.
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. NeurIPS, 2018.
Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classification tasks to a new unlabeled sample. In NIPS, 2011.
Gilles Blanchard, Aniket Anand Deshmukh, Ürün Dogan, Gyemin Lee, and Clayton Scott. Domain generalization by marginal transfer learning. JMLR, 2021.
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties self-supervised vision transformers. arXiv preprint arXiv:2104. 14294, 2021.
Gabriela Csurka. Domain Adaptation in Computer Vision Applications. Springer, 2017.
Steve Dias Da Cruz, Bertram Taetz, Thomas Stifter, and Didier Stricker. Illumination normalization by partially impossible encoder-decoder cost function. In WACV, 2021.
Chen Fang, Ye Xu, and Daniel N Rockmore. Unbiased metric learning: On the utilization of multiple datasets and web images for softening bias. In CVPR, 2013.
Stuart Geman, Elie Bienenstock, and René Doursat. Neural networks and the bias/variance dilemma. Neural Computation, 1992.
Muhammad Ghifary, W. Bastiaan Kleijn, Mengjie Zhang, and David Balduzzi. Domain generaliza- tion for object recognition with multi-task autoencoders. In ICCV, 2015.
Henry Gouk, Timothy Hospedales, et al. Distance-based regularisation of deep networks for fine- tuning. In ICLR, 2021.
Ishaan Gulrajani and David Lopez-Paz. In search of lost domain generalization. In ICLR, 2021.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In /CLR, 2016.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009.
Shoubo Hu, Kun Zhang, Zhitang Chen, and Laiwan Chan. Domain generalization via multidomain discriminant analysis. In UAI, 2020.
Zeyi Huang, Haohan Wang, and Eric P Xing. Self-challenging improves cross-domain generaliza- tion. In ECCV, 2020.
10

---

Under review as a conference paper at ICLR 2022
Dominik Janzing. Causal regularization. In NeurIPS, 2019.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsub- ramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton Earnshaw, Imran Haque, Sara M Beery. Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. Wilds: A bench- mark of in-the-wild distribution shifts. In ICML, 2021.
David Krueger, Ethan Caballero, Jörn-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Rémi Le Priol, and Aaron C. Courville. Out-of-distribution generalization via risk extrapolation (rex). CoRR, abs/2003. 006688 2020.
Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy Hospedales. Deeper, broader and artier domain generalization. In ICCV, 2017.
Haoliang Li, Sinno Jialin Pan, Shiqi Wang, and Alex C. Kot. Domain generalization with adversarial feature learning. In CVPR, 2018.
Yiying Li, Yongxin Yang, Wei Zhou, and Timothy M. Hospedales. Feature-critic networks for heterogeneous domain generalization. In ICML, 2019.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. International Conference on Artificial Intelligence and Statistics, 2020.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penal- ization. In COLT, 2009.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In ICML, 2013.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of over-parametrization in generalization of neural networks. In ICLR, 2019.
Mohammad Pezeshki, Sékou-Oumar Kaba, Yoshua Bengio, Aaron Courville, Doina Precup, and Guillaume Lajoie. Gradient starvation: learning proclivity in neural networks. arXiv preprint arXiv:2011.09468, 2020.
Massimilianoo Pontil and Andreas Maurer. Excess risk bounds for multitask learning with trace norm regularization. In COLT, 2013.
Lutz Prechelt. Early dtopping-but when? In Neural Networks: Tricks of the trade, pp. 55-69. Springer, 1998.
Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. An online learning approach to interpo- lation and extrapolation in domain generalization. arXiv preprint arXiv:2102.131 2021.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Shirish Shevade, S Sathiya Keerthi, Chiranjib Bhattacharyya, and Karaturi Radha Krishna Murthy. Improvements to the smo algorithm for svm regression. IEEE transactions on neural networks, 11(5):1188-1 1198, 2000.
Baochen Sun and Kate Saenko. Deep coral: Correlation alignment for deep domain adaptation. In ECCV, 2016.
Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep hashing network for unsupervised domain adaptation. In CVPR, 2017.
Yufei Wang, Haoliang Li, and Alex C Kot. Heterogeneous domain generalization via domain mixup. In ICASSP, 2020.
11

---

Under review as a conference paper at ICLR 2022
Haotian Ye, Chuanlong Xie, Tianle Cai, Ruichen Li, Zhenguo Li, and Liwei Wang. Towards theoretical framework of distrb-diiti generalization. arXiv preprint 2el::2000004496, 2021.
Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization: A survey, 2021.
12

---

We use a slightly modified version of the standard empirical Rademacher complexity bound on generalisation error, as stated by Mohri al. (2018) but originally shown by |Bartlett & Mendel- sonj (2002), where the modification is to weaken the i.i.d. assumption to be only an independence Under review as a conference paper at ICLR 2022
A PROOF OF THEOREM 1
assumption-ie.. allow instances to be drawn from different distributions. The proof is exactly the same (because McDiarmid's 's inequality requires only independence, and not identical distributions), but we re-state it here for completeness.
Theorem 2. For .i..... Pn, independent samples from &, and I I-Lipschitz loss ((.:-) taking values in [0, 1), the following holds with confulence at least 1 - 8,
1 n TE
1 Σ Lp, (f) 2 (F) + 3/ ni j=1
In(2/0)
Σ p, (f)
S
(8)
2mn
where Lp, (f) is measured on Sp, [(Ei) (e)g,, a collection of m i...d. samples pj.
Proof. Let Sp. U...USp. and define
((S) = sup JEF
Σ (Lp, - (I)-
Note that (SS) satisfies the bounded differences property required by McDiarmid's inequality: i.e., we construct S' by replacing any one of the (Zij. Mky) in S with another random variable also drawn from Pj. then ($( - ( S 1. Therefore McDiarmid's ' inequality implies that with confidence at least 1
mn
ln(2/))
((S) < Esp Sp... ~Pin [+(S] V
(10)
2mn
We continue by bounding the expected value of (S).
Eg Spmn PPin ((S)
(11)
=Esp ppim
sup
1
Σ
(pp,
(f)
Lp, (n)
(12)
JEFT
j=1
1 n
m Σ m
1 m
Σ (((
=Esp Mim
sup JEF 11
Esg mps
(f v/s))
(13)
j=1
m
< &Sppin pim
Es Piin ppinn
sup
(L (. -(F(()))))))
(14)
JEF
j=1
=Esp ppp pin
Egg
xpin Eg
sup JEF T
-((()))))
(15)
< EEs
ppin Eg
sup SEF T1
(16)
Plim
1=1 m
Esy
Es
sup
ozy ()
(17)
f 11
m
j=1
2ES Pain
Ea sup- - Σ
Tn (((()))))
(18)
fEF j=1
-2Es Piim
Rmm (F),,
(19)
where the first inequality is from moving the supremum inside the expectation and the second is from subadditivity of suprema. Observing that the absolute difference of computing Rm, (F) on S and
13

---

Under review as a conference paper at ICLR 2022
S' cannot exceed 1 another application of McDiarmid's inequality tells that with confidence
least 1
In(2/6)
2Es pnn PPim [mm (F) S 2Rmm (F) + 2v
(20)
2mn
Combining Equations 10 and 20 with the union bound concludes the proof.
We now prove Theorem
1
Proof. Theorem 2tell tell us that with confidence at least 1 - Ö,
n
In ln(2/))
(f) -2Rmn (F)+ 3/
(21)
n
2mm
Thus, we must provide (high confidence) upper bound on
1 T2 Σ (f)
(F(
(22)
that holds uniformly for all E F. We can the same idea the proof for Theorem 2 show how Rademacher complexity controls generalisation to novel domains, rather than novel instances within the same domain. Begin by letting P (pI...,,n) be an i.i.d. sample of domains from E, and define
((P) sup L (J) fEF
n Σ (P)
1
(23)
If we construct P by replacing any Pj E P with p/} E, then we have (D()) x(P)) s 1 n so McDiarmid's inequality tells us that with confidence at least 1 -
(m(2/5)
(PP) S E Ep ~ [+[P]]
(24)
2n
We proceed by bounding the expected value of (PP),
- 1 Σ Ly, (f) )
E
Pin
sup FEF
(25)
1=1
1
(1) -Tpss (n))
E Expi E
sup B Bynme feF
(26)
n1
Lng (f) [n)
< E Epimn
sup
(27)
SEF n
1=1
sup Σ
1
oj (1n Log -1) (1)
(28)
[EF n1 j=1
< 2E <2maneEE Ea
sup- FEF
Lybbo (1)
(29)
1 o ((.)) ((((()), s)]
=2EpineeB Eg
sup FEF
(30)
< 2E 2E E (rp
Es
sup
Σ ()((((3)))))
(31)
hEF n
1=1
= ( B(8 (F),
(32)
14

---

Under review as a conference paper at ICLR 2022
where the first inequality comes from moving the supremum inside the expectation, 5 is vector of Rademacher random variables, the second inequality is due to the subadditivity of suprema, and the final inequality comes from moving the expectation outside of the supremum. Noting that placing one of the (T,, Vj) pairs the final equality will result in (F) changing by at most 1 McDiarmid's inequality can be used to say with confidence
x²
4 that (F)] s 2R, (FF)
+ 2V In(2/6)
2E pi:n -E (Fg,)))
(33)
2n
Combining Equations 21
24 and 33 using the union bound completes the proof.
B
PROOF OF COROLLARY
Proof. We begin with the expected excess risk, which can be bounded from above by
Es|L h1000:/hhhhaapp---------------1-
-
(34)
Es(L (F(I) (
(35)
= DESLL((F - 1F(
(36)
Es (f) - (f)
4p
+ +Bs
ΣΣ Lg, (f) ( -
(37)
where the incquality arises because, by definition, the empirical risk of f must be less than equal to the empirical risk of the optimal model. The second equality comes from the fact that f is determined independently of the particular training set that we sample, so Eg [i (f*)] = L (f*). For the final equality: the first term can be bounded from above (with confidence 1 -) using the bound for the expected value of (S)) derived in the proof of Theorem 2 and the second term can be bounded from above (with confidence 1 8) using the bound for the expected value of (PP) Combining these two high confidence bounds using the union
derived in the proof for Theorem I bound yields the result.
C DETAILED RESULTS
Complexity Measurement for DomainBed Competitors In Figure 2 we illustrated the perfor- mance of DomainBed competitors in terms of their resulting model complexity by averaging over held-out domains for each dataset. In Figure we present detailed results broken down by each held out dataset.
Detailed results on each DG benchmark In Table we reported results of our linear model competitors DomainBed summarised over choice of held out domain. In Tables report the detailed results of accuracy and choice of paramater for each held out domain.
Cross Validation
15
30
Ave.
Raw pixel
Acc
0.577
0.785
0.799
0.783
0.769
0.586
0.716 (0.096)
Domain Wise
C
256.0
128.0
128.0
128.0
64.0
256.0
Acc
0.582
0.774
0.788
0.783
0.765
0.579
0.712 (0.093)
Instance Wise
C
1024.0
512.0
1024.0
1024.0
1024.0
1024.0
Table Accuracy and selected 'C' on Rotated-MNIST, using Lin
15

---

Under review as a conference paper at ICLR 2022
Cross Validation
A
C
S
Ave.
DINO VIT B8
Acc
0.877
0.676
0,971
0.446
0.743 (0.201)
Domain Wise
C
0.25
0.125
0.25
0.125
Instance Wise
Acc
0.866
0.620
0.891
0.445
0.706 (0.184)
C
4.0
8.0
8.0
2.0
DINO VITS8
Domain Wise
Acc
0.864
0.666
0,948
0.441
0.730 (0.196)
C
0.5
0.0625
0.5
0.03125
Instance Wise
Acc
0.867
0.676
0.858
0.464
0.716 (0.164)
4.0
Table 3: Accuracy and selected 'C' on PACS, using LinearS
Cross Validation
C
S
V
Ave.
DINO VIT-B8
Acc
0.972
0.648
0.787
0.811
0.804 (0.11.5)
Domain Wise
0.5
0.125
0.5
Acc
0.977
0.648
0.785
0.811
0.805 (0.117)
Instance Wise
0.25
0.5
0.5
0.5
DINO VTTSS
Ace
0.959
0.785
0.823
0.804 (0.111)
Domain Wise
0.25
0.125
0.0625
0.25
Acc
0.959
0.651
0.789
0.823
0.806 (0.1
Instunce Wise
0.25
0.25
0,25
Table 4: Accuracy and selected 'C' on VLCS, using LVn
Cross Validation
C
R
Ave.
DINO ViT-B8
Acc
0.748
0.512
0.832
0.800
0.736 (0.135)
Domain
C
1.0
1.0
1.0
0.5
Acc
0.730
0.514
0.833
0.866
0,731 (0.133)
Instance Wise
C
4.0
2.0
4.0
DINO VITS8
Acc
0.740
0.496
0.820
0.834
0.722 (0.136)
Domain
C
1.0
0.25
0.5
0.5
Acc
0.726
0.508
0.824
0.833
0.723 (0.131)
Instance Wise
C
2.0
1.0
1.0
2.0
Table 5: Accuracy and selected 'C" on OfficeHome, using L LinearSVC.
Cross Validation
aclass
escape
hilux
i3
lexus
tesla
Liguan
lucson
x5
Ave.
DINO ViT-B8
Domain Wise
Acc
0.979
0.980
0.967
0.997
0.959
0.981
0.942
0.986
0.975
0.954
0.972 (0.016)
1.0
1.0
1.0
1.0
1.0
1.0
2.0
Instance Wise
Acc
0.922
0.991
0,910
0.998
0.902
0.960
0.937
0.983
0.976
0.955
0.953 (0.032)
128.0
64.0
128.0
64.0
256.0
128.0
256.0
128.0
128.0
128.0
DINO VITS8
Acc
0.961
0.959
0.959
0.971
0.958
0.964
0.933
0.979
0.957
0.814
0.945 (0.045)
Domain Wise
0.125
0.5
0.25
0.5
0.5
0.5
0.25
0.25
0.25
0.25
Instance Wise
Acc
0.914
0.969
0.952
0.996
0.966
0.838
0.843
0.989
0.810
0.851
0.913 (0.067)
C
1024.0
128.0
512.0
256.0
1024.0
64.0
512.0
128.0
512.0
128.0
Table 6: Accuracy and selected 'C" on SVIRO, using LV.
16

---

Under review as a conference paper at ICLR 2022
Offictione: (Domuis A)
VLES (Domain O
0.6
0.75
Avcuncy
0.4
0.96
0.05
0.5
6.5
1.2
1.1
1.5
1.5
0.5
1.2
1.6
0.5
0.5
1.4
1.0
Complexiy
Complessy
Complesty
Ofieeltone (Domain C)
PACS (Domiin C)
VLCS (Domain
0.64
0.02
0.4
Accuney
0.02
Acurac
0.5
0.58
0.55
Complexry OfficeHooee (Demain P)
Complesry
Complexity
PNCS (Domalt
VLCS (Domain
0.57
01005
0.50
0.6
0.06
Aconcy
0.50
Acounyy
0.01
0.94
0.62
Complesry
Compleesry PACS (Donuis
Complosty
Olisstoom:: (Dumain R)
VLCS (Damain
0.7
0.75
0.45
Accuney
Acciney
0.76
0.74
0.4
0.72
0.4
0:35
0.5
1.5
0.55
0.5
1.2
1.4
1.6
0.5
01.5
1.2
1.4
1.0
1.8
Cumplesit
Complexity
Complesik
OfficHlame
VL.CS
0.76
++
1
0.00
0.5
Accuaay
Accrra
0.64
Mixsp MMD
0.4
RSC
8.62
0.25
SD
ViEEs
0.72
0.5
0.8
0.5
Couplesity
Complesity
Complesiy
Figure 3: Performance of various neural network DG algorithms as function of their measured model complexity after training using DomainBed. Breakdown by held-out dataset. The top four rows correspond to individual domains, the bottom row the reave-oneddomann estimate of the DG performance, and horizontal error bars correspond to the standard deviation of the model complexities measured in each iteration of cross-validation
cross-validation
17

---

Under review as a conference paper at ICLR 2022
Cross Validation
L100
L38
L43
L46
Ave.
DINO VTT-88
Acc
0.444
0.457
0.516
0,399
0.454 (0.041)
Domain Wise
2.0
0.472
0.391
0.366
0.324
0.388 (0.054)
Instance Wise
C
256.0
128.0
256.0
256.0
DINO VrTS8
Acc
0.375
0,231
0.480
0.398
0.371 (0.090)
Domain Wise
0.407
0.157
0.488
0.322
0.331 (0.109)
Instance Wise
C
256.0
64.0
128.0
128.0
Table 7: Accuracy and selected 'C" on Terra Incognita, using LinearSVC.
18


Reviews:
[{"review_id": "xFHkGdXfEpX", "reviewer": "Reviewer_jRak", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n\n**Problem setting.**  The setting is well-motivated, in that recent results have indicated that most DG algorithms cannot surpass the performance of ERM.  New theoretical insights are needed to understand why this happens, and indeed this work tries to fill this gap.\n\n**Insights from Thm. 1**  The idea of treating the environments themselves as data is interesting, as it allows the derivation of this kind of bound which is agnostic of the form of $\\mathcal{E}$.  I feel that the authors may consider taking this analysis further, as there may be new insights if e.g. $\\mathcal{E}$ has some particular structure, or when the hypothesis class is linear (or has some structure).  In any case, Thm. 1 seems to be a nice starting point for this work.\n\n**Interesting insights regarding accuracy vs. complexity.**  I quite liked the experiments in Section 3.1.  The takeaway seems to be that \"the optimal regularization for [DG] is stronger than for [supervised learning].\"  This indicates that the complexity of DG methods needs to be controlled more tightly than it does for regular supervised learning.  So at least in the linear setting, it seems to be the case that there is a clear trade-off between accuracy and complexity WRT test-time generalization.\n\n### Weaknesses\n\n**Confusing notation.**  There were several places in the paper where the notation/word-choice was confusing.  One point of confusion was that the risk $R_p$ and the Rademacher complexity $\\mathcal{R}_m$ look rather similar. Perhaps the risk could be changed to $L_p$, which is the notation used in [Shalev-Shwartz & Ben-David, 2014].  The word-choice used to differentiate supervised learning from domain generalization was confusing.  If my understanding is correct, the former is referred to as supervised learning, seen-domain, and within-domain whereas the latter is referred to as novel-domain, cross-domain, and domain generalization.  Perhaps choosing just one term to refer to each of these would make the paper easier to read.  A further point\n\n**Typos.**  There are a number of typos.  Both \"regularizers\" (page 1) and \"regularisation\" (page 2) are used; the paper should be consistent in choosing the American or British spelling.  The dataset is Terra-Incognito (page 5).  \n\n**The formulation of the DG problem.**  The authors assert that the goal of DG is to solve the following optimization problem:\n\n$$ \\min_{f\\in\\mathcal{F}} \\mathbb{E}_{p\\sim\\mathcal{E}} [R_p(f)] $$\n\nwhere $\\mathcal{E}$ is a distribution over distributions $p$.  This is not the only formulation for domain generalization.  Indeed, some would argue that this is not the most standard formulation for the problem.  Another formulation was considered in [Arjovsky et al., 2019], wherein the authors advocate for the following \"worst-case\" problem:\n\n$$ \\min_{f\\in\\mathcal{F}} \\max_{p\\in\\Delta\\} R_p(f)$$\n\nwhere $\\Delta$ is something like the support of $\\mathcal{E}$ in the notation of this paper.  The reason I feel that this is important is that the authors make assertions like this:\n\n> \"any future DG method that claims to be better than ERM should...\"\n\nThese assertions are only relevant to the first \"average-case\" definition of the DG problem, and do not necessarily apply to other common formulations, e.g. the \"worst-case\" formulation shown above.  One way to remedy this would be to move the proofs to the appendix and to add a more detailed discussion of related work and of past formulations and approaches for DG.\n\n**Lack of sufficient detail.**  There were numerous places where I thought the paper could have benefitted from providing more detail.  Here are some questions I had while reading, all of which could be addressed by adding details:\n* What do the authors mean by the \"domain-shift phenomena?\"  Of late there has been quite a bit of work on domain shift in the sense of Section 1.8 in [Quiñonero-Candela, et al., 2009], which defines domain shift to be a particular form of covariate shift.  However, it seems that the authors may be using domain-shift to informally refer to the problem of domain generalization, wherein there can be arbitrary shifts in the joint distribution over (X,Y) from domain to domain.  Resolving this confusion would make the problem setting clearer.\n* Define what is meant by \"data in the wild\" (page 1).  \n* A recurring question I had was the following: What do the authors mean when they say that X is a **causal factor** in the success or failure of DG methods.  Is \"causal\" meant informally?  Or does it mean something more technical vis-a-vis the field of causal inference.  This term is used repeatedly, and after reading the paper several times, I still am not sure what it means.\n* The authors talk quite a bit about the \"performance variability\" (page 2) or \"erratic performance\" (page 1) \"unreliable\" performance (page 6) of existing DG methods.  It's unclear whether we should read this as \"poor performance\" or \"non-stable performance.\"  I find this distinction important because the results of [Gulrajani & Lopez-Paz, 2020] indicate that on the contrary, the collective performance of DG baselines is actually quite stable in the sense that they almost all algorithms do more or less the same as ERM.  Now to be fair, this performance isn't all that great, given that there is a very large gap between in-distribution and out-of-distribution performance of each of these methods.  Thus, I think that there needs to be a bit more subtlety in how the authors specify the weakness of the DG algorithms that they want to improve.  Additionally, I think that this perspective that ERM is optimal for this \"average-case\" is not new; [Rosenfeld et al., 2021] also advocates for this view, so it may be good to cite their work here.\n* At the start of the experiments, the authors say they will work with linear SVM.  But then, the authors say that they train linear SVC (which I assume is the classification analog of SVM, although it's never stated).  This should be clarified.\n* What do the authors mean by a \"dynamic range of accuracy\" (page 7)?  What is \"dynamic\" about it?\n\n**Unclear explanation of experiments.** I didn't understand the result sin Section 3.3.  What is the difference between instance-wise and domain-wise validation?  This is never explained from what I can tell.  Does this simply mean in-domain validation vs. cross-domain validation?  It's also unclear to me what claim in [Gulrajani & Lopez-Paz, 2020] the authors of this paper are disputing at the bottom of page 7.  From my understanding, [Gulrajani & Lopez-Paz, 2020] argues that DG algorithms should be responsible for specifying a hyperparameter selection criteria.  How do these results refute this claim?\n\n**Claims in the abstract.**  Some of the claims in the abstract are somewhat dismissive of past work.  They say that \"most of the [past work in DG] is empirical, as the DG problem is hard to model formally.\"  They go on to say that they do something more principled with a learning-theoretic analysis of the problem.  This dismisses the large and growing body of work that has sought to understand the theoretical underpinnings of the DG problem.  Indeed, many of the proposed algorithms for DG are past on concrete theory; the fact that they don't in general significantly improve over ERM is a separate issue.  Furthermore, in the end, the authors actually do something quite empirical, in the sense that they extract features using a deep classifier and look at the performance of small neural networks on DomainBed.  This to me seems no less \"empirical\" than many of the other works that have sought to study this problem.  So from my reading of this paper, the authors also fall into the pitfall that they claim to identify early on in the paper.  More than anything else, I think this is an issue with how the idea proposed in this paper is discussed, rather than being a critique of the proposed method itself.  So I would recommend softening these claims and expanding the related works section, given that there is a great deal of related work in DG that has been left out.\n\n**Formal-ness of the proofs.**  In my opinion, the proofs here are presented too informally.  The authors use terms like \"ghost sample\" without defining or describing them for the reader.  I think that eq(7) should be proved formally, rather than hand-waving over the argument (whether or not the authors feel it is trivial).  The same can be said for Thm. 2 (which I would call Corollary 2 rather than Theorem 2), for which the proof is more of a sketch.  \n\n**Softening some of the claims.**  The authors have a section titled called \"Solving Domain-Bed with Linear Models.\"  I think that this is misleading, as the authors are not \"solving\" DomainBed.  \"Solving\" would indicate that they found a way to achieve perfect domain generalization by generalizing OOD. \n\n### References\n\n[Shalev-Shwartz & Ben-David, 2014] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.\n\n[Arjovsky et al., 2019] Arjovsky et al. \"Invariant risk minimization.\" arXiv preprint arXiv:1907.02893 (2019).\n\n[Quiñonero-Candela, et al., 2009] Joaquin Quiñonero-Candela, et al., eds. Dataset shift in machine learning. Mit Press, 2009.\n\n[Gulrajani & Lopez-Paz, 2020] Ishaan Gulrajani and David Lopez-Paz. \"In search of lost domain generalization.\" arXiv preprint arXiv:2007.01434 (2020).\n\n[Rosenfeld et al., 2021] Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. \"An online learning approach to interpolation and extrapolation in domain generalization.\" arXiv preprint arXiv:2102.13128 (2021).", "summary_of_the_paper": "This paper considers the problem of domain generalization (DG), wherein predictors are trained on a related set of training domains and evaluated on an unseen test domain.  The authors first present a learning-theoretic bound on the performance of an average-case formulation for DG, and then present a set of experiments that consider the trade-off between complexity and out-of-distribution (OOD) performance.  The experiments indicate that such trade-offs exist for linear models, and there is also evidence that the trade-off persists for shallow neural networks.", "summary_of_the_review": "On the one hand, I think that this paper offers an interesting perspective for thinking about DG.  The theoretical work gives a new way of thinking about the accuracy-complexity trade-off in DG, and this leads to some interesting experiments.  However, I think that the paper tends to overclaim, in particular with regard to \"solving DomainBed\" and the implications of its theory for ERM.  Furthermore, I think that the writing is particularly unclear, and that the claims made in the introduction are not fully validated (e.g. the claims about the \"causal\" factor behind poor performance in DG).  Overall, despite the interesting insights, I think that this paper is not yet ready, and so I recommend that it not be accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WYdAzlfqfry", "reviewer": "Reviewer_LqhM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n1. Generalization bound for DG setting\n2. Empirical experiments support that ood generalization requires smaller model complexity\n3. Propose cross-domain validation as a metric to optimize DG models \n\n**Weaknesses**\n1. No discussion on the size of n in theory section. Usually n is very small. \n2. Overclaiming model complexity as the main reason explaining the DG results.\n\nI feel that it is a good paper shedding light on ill-formed DG problem. I summarize my feedback for the authors below:\n\nThe generalization bound is a nice characterization to show that we may need additional regularization for OOD generalization. It may be good to discuss this relative to other papers that have made similar claims about regularization (e.g., causal regularization by Janzing https://arxiv.org/abs/1906.12179). The conclusion on regularization does not seem a novel idea to me, but I do like the theoretical rigor to support it.\n\nThe discussion after Theorem 2, however, misses the point of what empirical domain generalization is about. With enough diverse domains (e.g., 100-1000), of course any method (including ERM) would be good. But the tasks typically have 4-5 domains which makes generalization harder. Given extreme domain shift, DG methods can easily outperform ERM (see e.g., Arjovsky et al. IRM paper, or Mahajan et al. MatchDG paper). The only issue is that in the DG benchmark datasets (and many real-world settings with small domain shifts), ERM seems to perform better. So while Theorem 2 may be true, I do not think it has much of an insight for empirical DG. Perhaps the point that authors want to make is that ERM would work well for all settings, while a DG algorithm would work well in some datasets, but not all (based on its assumptions).\n\nI appreciate the empirical results. Nice formulation to use linear models over pre-trained representation, that helps to confirm the model complexity hypothesis. For Figure 2, however,  I would like to caution that the results only show that model complexity is _one_ of the factors that contribute to  ood accuracy. It is no surprise that ood accuracy increases up to a certain model complexity and then decreases. I would suggest the authors to stick to the main claim (ood gen requires smaller model complexity than iid gen). The claim that complexity determines the OOD generalization is not supported by the experiments. Are the authors saying that a more complex model can _never_ achieve higher OOD generalization? That would be a very strong statement.\n\nI would also tone down section 3.3: \"solving domainbed\". All the numbers reported are lower than state-of-the-art. The paper just compares a linear model with different validation schemes. \n\nIn theorem 1, did not see a derivation for the last term O(sqrt(ln(1/\\delta)/n) in the proof. How is that derived?\n", "summary_of_the_paper": "In domain generalization, recent work has shown that ERM has comparable out-of-domain accuracy to state-of-the-art DG methods. The paper aims to explain this result through model complexity. The main argument is that ood generalization requires a smaller model complexity. The upshot is that DG methods can utilize cross-domain validation to obtain better generalizing models.", "summary_of_the_review": "Good paper explaining the recent empirical results against DG algorithms", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "DS8kx2W97lU", "reviewer": "Reviewer_YVsq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrenths:\n* The paper is one of the few early attempts to establish the theoretical framework of OOD/Domain Generalization.\n* The connections with Rademacher complexity is interesting.\n\nFlaws:\n* The title seems to be a response to [3] but the evidence is not solid enough in comparison. I strongly recommend toning down and rename it to emphasize the theoretical contribution of this work.\n* Some very relevant theoretical works are not cited and discussed like [1,2]. And indeed some findings are alreadly manifested in those works.\n* The theoretical significance is not enough for publication. Domain generalization is unachivable without the formalization of distribution shifts but here only considers the risk over the mixtures of source domain, which is insufficient to provide out-of-distribution generalization guarantees.\n\n\n[1] Towards a Theoretical Framework of Out-of-Distribution Generalization\n[2] Empirical or Invariant Risk Minimization? A Sample Complexity Perspective\n[3] In Search of Lost Domain Generalization\n", "summary_of_the_paper": "This paper has several findings taking a bias-variance trade-off of DG performance, that explains existing DG algorithm performance variability. (ii) The complexity control strategy used to determine bias-variance trade-off is crucial in practice, with peak DG performance achieved when optimizing model complexity based on domain-wise validation. (iii) Regularisation required for optimal DG is greater than for conventional optimization for within-domain performance.", "summary_of_the_review": "The paper has promising motivations but lacks of theoretical significance for DG community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "0TcScqfmluI", "reviewer": "Reviewer_ZKqa", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strong point\n\n- Modeling domain generalization performance from a domain-complexity view is novel. The paper shows an interesting trade-off between model complexity and training loss in a derived upper bound.\n\n- Extensive experiments showcase the validity of the theory. A better model selection strategy is proposed.\n\n- It is nice to see that the optimal regularization of across-domain acc is consistently larger than the one of within-domain acc in Fig (1).\n\n# Weakness\n\n- The demonstration of the trade-off in Theorem 1 is nice. The results of the arguments rely on concentration bounds such as McDiarmid's inequality, which is typically used for large $n$. However, in reality, the number of training domains is small, e.g., 4~5 training domains. The bound seems vacuous when $n$ is small.\n\n- Another caveat is that theorem 1 bound the average risk w.r.t some environmental prior $\\mathcal{E}$. One would imagine that the average risk is dominated by the risk of environments in the high probability regions of the prior. The model can exploit the environmental-specific feature in those environments regardless of loss of the environments in the low probability region, which is the motivation of many existing DG works. \n\n- According to Eq (16), it seems that the Rademacher term $\\mathcal{R}_n(F)$ is the Rademacher complexity but not empirical Rademacher complexity. In addition, the notations are confusing. The underlying joint distributions for (x,y) are different for the two Rademacher complexity terms in Eq (7).\n\n- It seems that there is no clear trait of the trade-off in Fig (2). One interesting observation is that IRM has the smallest model complexity and held-out domain accuracy in the baselines, which contradicts existing works. [1] theoretically shows that it is easy to fit the IRMv1 objective while behaving like ERM on held-out domains. The empirical results in [2], sec 3.2 also suggests that the IRMv1-trained model behaves like the ERM-trained model. Is such discrepancy caused by disparate architectures (MLP versus ResNet)? Also, the held-out accuracy in VLCS datasets of ERM models seems to decrease with model complexity.\n\n\n# Minors \n\n- Across-domain accuracy and held-out domain accuracy are used interchangeably.\n- What is ``instance-wise\" model selection? The average loss of data instances in training domains?\n\n[1]: Elan Rosenfeld, P. Ravikumar, and Andrej Risteski.  The risks of invariant risk minimization. ArXiv, abs/2010.05761, 2020\n\n[2]:Yilun Xu and T. Jaakkola. Learning Representations that Support Robust Transfer of Predictors. ArXiv, abs/2110.09940, 2021", "summary_of_the_paper": "This paper presents a theory of domain generalization based on statistical learning theory (Rademacher complexity) and demonstrates a trade-off between training loss and model complexity. They show that existing methods are actually controlling the model complexity. Based on the analysis, the authors argue that proper model selection is critical for complexity control. Instead of hyper-parameter search, they propose to use domain-wise cross-validation as the model selection strategy. Experiments on the DomainBed benchmark show the effectiveness of the proposed method.", "summary_of_the_review": "\n\nTo summarize above, I find the theoretical results are somewhat unsatisfying due to limited domain numbers in practice. The experimental parts report results on small models, which contradicts some existing results on larger ones. All in all, I find the paper in its current form to be somewhat below the standard for ICLR acceptance, unless the authors address some of the points above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a learning theoretic account of domain generalization in which domains themselves are treated as data, generated from some domain generating distribution. All of the reviewers were positive about this approach and found it interesting. There were, however, a couple of critiques raised by reviewers that lead me to recommend that it is rejected:

- the theory provided in this paper does not remotely apply to the datasets that are used in the experiments. While, I agree with one of the author responses that DG benchmarks exist with many domains, DomainBed has very few domains, and it's not clear that their theory is a remotely satisfactory account of the experimental results presented in the paper.
- Despite some back and forth on the wording and positioning of the paper, I think the writing still does not give enough credit to worst-case analyses of DG.
Decision: Reject