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 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 the work in general purpose DG is heuris-
tically motivated, as the DG problem is hard to model formally; and recent evalu-
ations have cast doubt on existing methods’ practical efﬁcacy – in particular com-
pared to a well chosen empirical risk minimisation baseline. We present a novel
learning-theoretic 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’ efﬁcacy or lack thereof is a variant of
the standard empirical 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 leave-one-domain-out cross-validation objec-
tive. Empirical results on the DomainBed benchmark corroborate this.
1
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-shift phenomenon occurs widely in many appli-
cations of machine learning (Csurka, 2017; Zhou et al., 2021; Koh et al., 2021), and often leads to
disappointing results in practical machine learning deployments, since data ‘in the wild’ is almost
inevitably different from reference training sets.
Given the practical signiﬁcance of this issue, a large number of methods have been proposed that
aim to improve models’ robustness to deployment under a different distribution than used for train-
ing (Zhou et al., 2021), 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 difﬁcult to model formally for principled
derivation and theoretical analysis of algorithms, the target domain of interest is 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 a well tuned empirical risk minimization
(ERM) baseline’. We argue that this negative result highlights the need for better theory in 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 ﬁrst contribution is to present an intuitive learning-theoretic 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 on a held out target domain is bounded by the performance on known source
1
Under review as a conference paper at ICLR 2022
domains, plus two additional model complexity terms, that describe how much a model can possibly
have overﬁtted to the training domains. This theoretical contribution leads to several insights.
Firstly, our theory suggests that DG performance is governed by a 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 as an overﬁtting-underﬁtting trade-off (Geman
et al., 1992). Based on this, we hypothesise that performance variability is determined by implicit
or explicit regularisation. That is, the plethora of different strategies available (Zhou et al., 2021) –
from data-augmentation to specialised optimisers – actually affect DG performance by explicitly or
implicitly choosing different ﬁt-complexity 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-Paz (2021) is actually consistent with an explanation
in terms of implied complexity.
Practically, our analysis suggests that the model selection strategy (Hastie et al., 2009) is a fac-
tor in DG performance that is at least as important as the actual mechanism of model complexity
control (i.e., Tuning of regularisation strength vs speciﬁc 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). Gulrajani & 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-parameter 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. Speciﬁcally, our theoretical and empirical results show that, contrary to the conclu-
sion of Gulrajani & Lopez-Paz (2021), simple domain-wise cross-validation is a 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 ﬁt 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
for optimal DG is greater than for conventional optimization for within-domain performance.
2
RELATED WORK
Theoretical Analysis of the DG Setting and Algorithms
The DG problem setting was ﬁrst anal-
ysed in Blanchard et al. (2011). Since then there have been some attempts to analyse DG algorithms
from a generalisation bound perspective (Muandet et al., 2013; Blanchard et al., 2021; Hu et al.,
2020; Albuquerque et al., 2020; Rosenfeld et al., 2021). However these studies have theoretical
results that are either restricted to speciﬁc 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 ﬁnite 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—i.e., 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 Blanchard et al. (2011), where the
goal is to minimise the expected error 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 a speciﬁc class of structural
equation models, and the analysis is performed under the assumption that inﬁnite 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. (2011), where one is concerned with the expected
performance of a model on domains sampled from some distribution over domains.
Others rely on 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 a learning objective). Albuquerque et al. (2020)
proceed by making assumptions on the structure of the distribution over possible domains (i.e., that
it has support determined by the convex hull of a ﬁnite set of prototypical domains), which allows
them to upper bound the domain alignment metric. Ye et al. (2021) provide a bound that depends
on an unobservable domain distance quantity, which they then approximate in experiments using
kernel density estimates.
Rosenfeld et al. (2021) is another piece of work that theoretically investigates the generalisation of
ERM in a DG setting. They deal with online DG, where each time-step corresponds to observing a
new domain, and the learner must produce a new model capable of generalising to novel domains.
Another point of difference between their work and the standard DG problem setting of Blanchard
et al. (2011) is that the domain at each time-step is chosen by an adversary. They analyse this
game for a ﬁnite number of time-steps, but they assume each domain has an inﬁnite amount of data.
They also put some limitations on the adversary: e.g., it must choose a domain that is a convex
combination of a ﬁnite number of pre-determined domains. In contrast, our theoretical analysis is
in the more realistic setting where one has a ﬁnite amount of data per domain, and the domains we
consider are not limited to convex combinations of a 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 to ﬁnite hypothesis
classes (which does not include, e.g., linear models or neural networks), whereas ours can be applied
to any class amenable to analysis with Rademacher complexity.
Empirical Analysis
The main existing empirical analysis on DG is Gulrajani & Lopez-Paz (2021),
who compared several state of the art DG methods under a common evaluation and hyper-parameter
tuning protocol called DomainBed. They ultimately defend Empirical Risk Minimization (ERM)
over more sophisticated alternatives on the grounds that no competitor consistently beats it 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 speciﬁcally:
(i) We provide a 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 ac-
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 (2021).
3
BOUNDING RISK FOR DOMAIN GENERALIZATION
I.i.d. learning is concerned with learning a mapping from some input space X, to a label space Y,
given data drawn from a distribution on X × Y. One aims to ﬁnd a model, f ∗∈F, that minimises
the expected loss (also called risk) on unseen data,
f ∗= arg min
f∈F
Lp(f),
Lp(f) = E(⃗
x,y)∼p[ℓ(f(⃗
x), y)],
(1)
where p is the data distribution and ℓ(·, ·) is the loss function. In practice, we only have access to
a ﬁnite set of data, S = {(⃗
xi, yi)}m
i=1, sampled i.i.d. from this distribution, so must minimise an
empirical risk estimate,
ˆ
f = arg min
f∈F
ˆ
Lp(f),
ˆ
Lp(f) = 1
m
m
X
i=1
ℓ(f(⃗
xi), yi).
(2)
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
Lp(f) ≤ˆ
Lp(f) + 2Rm(F) + O
 r
ln(1/δ)
m
!
,
(3)
3
Under review as a conference paper at ICLR 2022
which holds with probability at least 1 −δ, and R(F) is known as the empirical Rademacher com-
plexity of the hypothesis class, F. This complexity term is deﬁned as
Rm(F) = E⃗
σ
"
sup
f∈F
1
m
m
X
i=1
σiℓ(f(⃗
xi), yi)
#
.
(4)
For a hypothesis class consisting of norm-constrained linear classiﬁers, one can achieve the follow-
ing upper bound on the empirical Rademacher complexity (Shalev-Shwartz & Ben-David, 2014),
Rm(F) ≤XB
√m,
F = {⃗
x 7→⃗
x · ⃗
w : ∥⃗
w∥2 ≤B},
where we assume that each input, ⃗
x, has a Euclidean norm of at most X. There are a variety of ways
to deﬁne hypothesis classes for neural networks, but most recent approaches take the view of ﬁxing
a particular architecture and specifying constraints on the norms of weights or distances they can
move from their initialisations (Bartlett et al., 2017; Neyshabur et al., 2019; Gouk et al., 2021).
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 E, of distributions p
(Blanchard et al., 2011). 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, qsupp(E) it could be the case that
either p(⃗
x) ̸= q(⃗
x), or p(y|⃗
x) ̸= q(y|⃗
x), or even that both types of distribution shift have occurred.
The conceptually simplest—and often implicitly assumed—goal of DG methods is to minimise the
expected risk across different distributions that could be sampled from the environment,
LE(f) = Ep∼E[Lp(f)].
(5)
This object is also the most commonly analysed idealised objective in the learning theory literature
(Blanchard et al., 2011; 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,
we only have access to an empirical estimate of the risk,
ˆ
LE(f) = 1
n
n
X
j=1
ˆ
Lpj(f),
(6)
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, ˆ
LE, on the source do-
mains and the expected risk, LE, on unseen domains that holds uniformly for all hypotheses in
F.
Theorem 1. For a 1-Lipschitz loss, ℓ(·, ·), taking values in [0, 1], with conﬁdence at least 1 −2δ for
all f ∈F we have that
LE(f) ≤ˆ
LE(f) + 2Rmn(F) + 2Rn(F) + 3
r
ln(2/δ)
2mn
+ 3
r
ln(2/δ)
2n
,
where n 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 A.
Discussion
Theorem 1 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
it could possibly overﬁt to the seen domains while minimising empirical risk. In the case of linear
models, these terms depend on weight norms, while in the case of deep models they further depend
on properties of the chosen network architecture. Mirroring conventional generalisation in standard
i.i.d. learning, a very simple model may minimise the Rademacher terms, R, while producing high
4
Under review as a conference paper at ICLR 2022
empirical risk, ˆ
LE, and vice-versa. Thus good generalisation critically depends on a carefully chosen
empirical risk vs model complexity trade-off. The difference between Theorem 1 and single domain
bounds (e.g., Equation 3) is the additional dependence on the number of domains n and additional
Rademacher complexity term. This implies that when the goal is to generalise to new domains, the
risk of overﬁtting is higher. Therefore we expect a lower complexity model to me optimal for held
out domain performance compared to seen domain performance in standard i.i.d. learning.
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 −2δ, the excess risk of the empirical risk minimiser in F
is bounded as
E[LE( ˆ
f) −LE(f ∗)] ≤2Rmn(F) + 2Rn(F) + 2
r
ln(2/δ)
2mn
+ 2
r
ln(2/δ)
2n
,
The proof (in Appendix B) 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 1.
Discussion
Corollary 1 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 1.
In par-
ticular, for any typical hypothesis class, ERM converges to the optimal classiﬁer at a rate of
O(1/√mn) + O(1/√n). 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 speciﬁc assumptions about the underlying data generation process, coupled with analysis
of a speciﬁc hypothesis class using methods from causal inference. An example of such analysis
is 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-Paz, 2021). In particular we aim to address the following questions: (1) Theorem 1 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 of state of the art methods previously observed
on DomainBed be explained in terms of model complexity? (3) Given that model complexity is a
crucial determinant of generalisation, what is the best objective for tuning regularisation strength?
4.1
DOMAIN GENERALISATION PERFORMANCE DEPENDS ON MODEL COMPLEXITY
To directly investigate the impact of model complexity on domain generalisation performance, we
ﬁrst work with Linear SVM applied to pre-computed deep features1. 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, early stopping, etc) disappear, and
training is fast enough that we can densely and exhaustively evaluate a wide range of complexities.
1Note that when a ﬁxed feature extractor, or any other preprocessing is used, it does not impact the model
complexity or associated generalisation bound.
5
Under review as a conference paper at ICLR 2022
-10.0
-9.0
-8.0
-7.0
-6.0
-5.0
-4.0
-3.0
-2.0
-1.0
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
10.0
C=2x
0.4
0.5
0.6
0.7
0.8
Test accuracy
Across-domain versus Within-domain on RotatedMNIST
Across-domain (pixel)
Within-domain (pixel)
-10.0
-9.0
-8.0
-7.0
-6.0
-5.0
-4.0
-3.0
-2.0
-1.0
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
10.0
C=2x
0.6
0.7
0.8
0.9
Test accuracy
Across-domain versus Within-domain on PACS
Across-domain (dino_vitb8)
Within-domain (dino_vitb8)
-10.0
-9.0
-8.0
-7.0
-6.0
-5.0
-4.0
-3.0
-2.0
-1.0
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
10.0
C=2x
0.65
0.70
0.75
0.80
0.85
Test accuracy
Across-domain versus Within-domain on VLCS
Across-domain (dino_vitb8)
Within-domain (dino_vitb8)
-10.0
-9.0
-8.0
-7.0
-6.0
-5.0
-4.0
-3.0
-2.0
-1.0
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
10.0
C=2x
0.6
0.7
0.8
Test accuracy
Across-domain versus Within-domain on OfficeHome
Across-domain (dino_vitb8)
Within-domain (dino_vitb8)
-10.0
-9.0
-8.0
-7.0
-6.0
-5.0
-4.0
-3.0
-2.0
-1.0
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
10.0
C=2x
0.6
0.7
0.8
0.9
1.0
Test accuracy
Across-domain versus Within-domain on SVIRO
Across-domain (dino_vitb8)
Within-domain (dino_vitb8)
-10.0
-9.0
-8.0
-7.0
-6.0
-5.0
-4.0
-3.0
-2.0
-1.0
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
10.0
C=2x
0.2
0.4
0.6
0.8
Test accuracy
Across-domain versus Within-domain on TerraIncognita
Across-domain (dino_vitb8)
Within-domain (dino_vitb8)
Figure 1: 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 LinearSVC classiﬁers. We experiment on six different DG
benchmarks, including RotatedMNIST (Ghifary et al., 2015), PACS (Li et al., 2017), VLCS (Fang
et al., 2013), OfﬁceHome (Venkateswara et al., 2017), 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 a linear SVM objective of the form C
n
Pn
i ℓ(fw(xi), yi)+∥w∥2, with parameter
C controlling the complexity of model w through loss-regularisation trade-off. We searched a wide
range of log2 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).
Results
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 ﬁtting the data well and constraining hypothesis class complexity appropriately. We ob-
serve underﬁtting for high regularisation (small C), and overﬁtting 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 is 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 a complete algorithm, which
would need to chose a speciﬁc complexity. We discuss an algorithm in Sec 4.3.
4.2
EXPLAINING DOMAINBED DG PERFORMANCE IN TERMS OF COMPLEXITY
Our experiment in Section 4.1 showed that linear models exhibit a very clean trade-off between com-
plexity and generalization. However there are many subtle factors that inﬂuence 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 (2021) 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 ﬁnd the best tuning
(cf: Fig 1) for each competitor. They nevertheless found existing methods to perform unreliably.
Our conjecture is that the number of seed samples (3) and hyper-parameter search trials (20) used
was far too few to reliably tune the deep networks evaluated, and therefore the tuning of each model
6
Under review as a conference paper at ICLR 2022
was inaccurate and performance estimates unreliable. Since dense and accurate hyper-parameter
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, we work with 2-layer MLPs. Specif-
ically, we take ﬁxed ImageNet pre-trained ResNet-18 features, and feed them to MLPs, which are
then trained using the DomainBed framework. 2-layer MLPs are sufﬁcient to instantiate many of the
state of the art DG algorithms in DomainBed. We train and compare ERM, CORAL (Sun & Saenko,
2016), Mixup (Wang et 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 a model capacity metric that is specialised for this class of models. We retro-
spectively determine the complexity of a 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(fU,V ) = ∥V ∥F (∥U −U 0∥F + ∥U 0∥2),
(7)
where U is the weight matrix of the ﬁrst layer, U 0 is its random initialisation, and V is the weight
matrix of the second layer. We use ∥·∥F to denote Frobenius norm, and ∥·∥2 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
we investigate.
Results
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 a 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 behaviour observed in
domain-bed.
To provide a different view of the same issue, the bottom plot reports a 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., Prechelt (1998); Hardt et al. (2016)) we also see typical overﬁtting-underﬁtting trade-off curves.
This shows that, as expected, proper choice of early stopping criterion is important. It also shows that
over a similar dynamic range of complexity (0.5-3), ERM (below) and alternative models (above)
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 modiﬁcations to standard
ERM, DG models explicitly or implicitly modify the bias and variance of the function class to be
learned. Gulrajani & Lopez-Paz (2021) 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 inﬂuence complexity in a less transparent way. RSC introduce more
sophisticated dropout-like mechanisms, which would be expected to reduce complexity. Meanwhile
alignment-based 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 speciﬁc setting of all the corresponding hyper-parameters
(e.g., regulariser strength, dropout rates) inﬂuence ﬁnal model complexity, which we argue is the
key determinant of performance.
7
Under review as a conference paper at ICLR 2022
0.5
1
1.5
2
0.3
0.4
0.5
0.6
Complexity
Accuracy
OfﬁceHome
CORAL
ERM
IRM
Mixup
MMD
RSC
SD
VREx
IRM (alt)
0.6
0.8
1
1.2
1.4
1.6
0.62
0.64
0.66
0.68
Complexity
Accuracy
PACS
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
0.72
0.73
0.74
0.75
0.76
Complexity
Accuracy
VLCS
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
0.56
0.58
0.6
0.62
0.64
Complexity
Accuracy
ERM Checkpoints on OfﬁceHome
0.5
1
1.5
2
0.62
0.64
0.66
Complexity
Accuracy
ERM Checkpoints on PACS
0.5
1
1.5
2
2.5
0.72
0.73
0.74
0.75
Complexity
Accuracy
ERM Checkpoints on VLCS
Figure 2: Performance of neural networks as a function of their measured model complexity after
training using DomainBed (DB). The overall results are consistent with a standard bias-variance
trade-off (cf. Fig 1 for linear models): performance depends on how well each model was tuned by
DB’s hyper-parameter search procedure. Top: Leave-one-domain-out cross-validation performance
of various neural DG algorithms evaluated by DomainBed. Horizontal error bars correspond to the
standard deviation of the model complexity measured for each cross-validation iteration. Bottom:
Performance of ERM model checkpointed at different training iterations. The central tendency
is obtained via ﬁtting a support vector regression model (Shevade et al., 2000) with a 6th order
polynomial kernel.
4.3
EVALUATING LINEAR MODELS ON 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),
we next evaluate algorithms for practical complexity tuning. From Fig. 1 we saw that within-domain
and cross-domain evaluation have different optimal tuning. If we consider automating the search for
a good regularisation parameter, these two ﬁnal evaluation criteria correspond respectively to hyper-
parameter selection based on a validation set from the seen source domains, vs based on a validation
set drawn from a held out source domain. The latter validation criterion corresponds to a unbiased
estimator of expected cross-domain generalisation performance RE(f), which our theorem bounds.
Setup
We performed DG evaluation on 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-wise cross-validation (where validation folds are drawn from the same source
domains used for training) or domain-wise cross-validation (where validation folds are drawn from
held-out domains not seen during training).
Results
The results in Table 1 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 C value selection (i.e., 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 as stochasticity in neural network training, we consider our result to be decisive and
attribute the different observation Gulrajani & Lopez-Paz (2021) to the inaccuracy and stochasticity
of hyperparameter tuning in neural networks.
8
Under review as a conference paper at ICLR 2022
Domain Wise
Instance Wise
Acc
log C
Acc
log C
Raw pixel
RotatedMNIST
71.6
4.97 (±0.52)
71.2
6.82 (±0.28)
DINO VIT-B8
PACS
74.3
-1.73 (±0.40)
70.6
1.56 (±0.66)
VLCS
80.4
-1.04 (±0.69)
80.5
-0.87 (±0.35)
OfﬁceHome
73.6
-0.17 (±0.35)
73.1
1.04 (±0.40)
SVIRO
97.2
0.21 (±0.33)
95.3
4.85 (±0.46)
Terra Incognita
45.4
-0.17 (±0.87)
38.8
5.37 (±0.35)
DINO VIT-S8
PACS
73.0
-1.91 (±1.43)
71.6
1.04 (±0.89)
VLCS
80.4
-1.91 (±0.66)
80.6
-1.21 (±0.35)
OfﬁceHome
72.2
-0.69 (±0.57)
72.3
0.35 (±0.40)
SVIRO
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 we set out to address three questions, which can 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 art 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 is preferred to instance-wise validation as a model-
selection objective.
Our analysis suggests that several existing methods that tried to tune learnable DG hyper-parameters
by performance on a held-out domain (Balaji et al., 2018; Li et al., 2019) were broadly on the right
track, and concurs with Gulrajani & Lopez-Paz (2021) that those methods with underspeciﬁed 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 a challenge. Gradient-based hyper-parameter estimation methods, as initially attempted
in Balaji et al. (2018); Li et al. (2019), together with efﬁcient methods for long-inner loop hyper-
gradient calculation (Lorraine et al., 2020), may beneﬁt the former problem by making search in
larger numbers of hyperparameters more feasible. Alternatively, using general purpose pre-trained
features (Caron et al., 2021) as we did here, and focusing on learning shallow models that can be
accurately tuned for DG may be another promising avenue in practice. Although achieving state of
the art performance is not our focus, we note that our results in Table 1 are quite competitive with
end-to-end trained state of the art (Gulrajani & Lopez-Paz, 2021), despite using ﬁxed 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 a way that closely mirrors the
bias-variance trade-off in 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 clariﬁed the preferred model selection criterion in each case. This analysis de-
mystiﬁes 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, as well as for future empirical studies to surpass in terms of strong baselines.
9
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? a sample complexity perspective. In ICLR, 2021.
Isabela Albuquerque, Jo˜
ao Monteiro, Mohammad Darvishi, Tiago H Falk, and Ioannis Mitliagkas.
Generalizing to unseen domains via distribution matching. arXiv preprint arXiv:1911.00804,
2020.
Martin Arjovsky, L´
eon Bottou, Ishaan Gulrajani, 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 L 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. In 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. Overﬁtting or perfect ﬁtting? risk bounds for
classiﬁcation and regression rules that interpolate. NeurIPS, 2018.
Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classiﬁcation
tasks to a new unlabeled sample. In NIPS, 2011.
Gilles Blanchard, Aniket Anand Deshmukh, ¨
Ur¨
un Dogan, Gyemin Lee, and Clayton Scott. Domain
generalization by marginal transfer learning. JMLR, 2021.
Mathilde Caron, Hugo Touvron, Ishan Misra, Herv´
e J´
egou, Julien Mairal, Piotr Bojanowski, and
Armand Joulin.
Emerging properties in 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´
e 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 ﬁne-
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 ICLR, 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¨
orn-Henrik Jacobsen, Amy Zhang, Jonathan Binas, R´
emi Le
Priol, and Aaron C. Courville. Out-of-distribution generalization via risk extrapolation (rex).
CoRR, abs/2003.00688, 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. In International Conference on Artiﬁcial 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¨
olkopf. 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´
ekou-Oumar Kaba, Yoshua Bengio, Aaron Courville, Doina Precup, and
Guillaume Lajoie. Gradient starvation: A learning proclivity in neural networks. arXiv preprint
arXiv:2011.09468, 2020.
Massimiliano Pontil and Andreas Maurer. Excess risk bounds for multitask learning with trace norm
regularization. In COLT, 2013.
Lutz Prechelt. Early stopping-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.13128, 2021.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo-
rithms. Cambridge university press, 2014.
Shirish K 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–1193, 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 a
theoretical framework of out-of-distribution generalization. arXiv preprint arXiv:2106.04496,
2021.
Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization: A
survey, 2021.
12
Under review as a conference paper at ICLR 2022
A
PROOF OF THEOREM 1
We use a slightly modiﬁed version of the standard empirical Rademacher complexity bound on
generalisation error, as stated by Mohri et al. (2018) but originally shown by Bartlett & Mendel-
son (2002), where the modiﬁcation is to weaken the i.i.d. assumption to be only an independence
assumption—i.e., allow instances to be drawn from different distributions. The proof is exactly the
same (because McDiarmid’s inequality requires only independence, and not identical distributions),
but we re-state it here for completeness.
Theorem 2. For p1, ..., pn independent samples from E, and 1-Lipschitz loss ℓ(·, ·) taking values in
[0, 1], the following holds with conﬁdence at least 1 −δ,
1
n
n
X
j=1
Lpj(f) ≤1
n
n
X
j=1
ˆ
Lpj(f) + 2Rmn(F) + 3
r
ln(2/δ)
2mn ,
(8)
where ˆ
Lpj(f) is measured on Spj = {(⃗
xij, yij)}m
i=1, a collection of m i.i.d. samples from pj.
Proof. Let S = Sp1
S ... S Spn and deﬁne
Φ(S) = sup
f∈F
1
n
n
X
j=1
(Lpj(f) −ˆ
Lpj(f)).
(9)
Note that Φ(S) satisﬁes the bounded differences property required by McDiarmid’s inequality: i.e.,
if we construct S′ by replacing any one of the (xij, yij) in S with another random variable also
drawn from pj, then |Φ(S) −Φ(S′)| ≤
1
mn. Therefore McDiarmid’s inequality implies that with
conﬁdence at least 1 −δ
2
Φ(S) ≤ESp1:n∼p1:n[Φ(S)] +
r
ln(2/δ)
2mn .
(10)
We continue by bounding the expected value of Φ(S),
ESp1:n∼p1:n[Φ(S)]
(11)
= ESp1:n∼p1:n
"
sup
f∈F
1
n
n
X
j=1
(Lpj(f) −ˆ
Lpj(f))
#
(12)
= ESp1:n∼p1:n
"
sup
f∈F
1
n
n
X
j=1
 
ES′
pj ∼pj
"
1
m
m
X
i=1
ℓ(f(⃗
x′
ij, y′
ij)
#
−1
m
m
X
i=1
ℓ(f(⃗
xij, yij)
!#
(13)
≤ESp1:n∼p1:nES′
p1:n∼p1:n
"
sup
f∈F
1
n
n
X
j=1
1
m
m
X
i=1
(ℓ(f(⃗
x′
ij), y′
ij) −ℓ(f(⃗
xij), yij))
#
(14)
= ESp1:n∼p1:nES′
p1:n∼p1:nE⃗
σ
"
sup
f∈F
1
n
n
X
j=1
1
m
m
X
i=1
σij(ℓ(f(⃗
x′
ij), y′
ij) −ℓ(f(⃗
xij), yij))
#
(15)
≤ES′
p1:n∼p1:nE⃗
σ
"
sup
f∈F
1
n
n
X
j=1
1
m
m
X
i=1
σijℓ(f(⃗
x′
ij), y′
ij)
#
(16)
+ ESp1:n∼p1:nE⃗
σ
"
sup
f∈F
1
n
n
X
j=1
1
m
m
X
i=1
−σijℓ(f(⃗
xij), yij)
#
(17)
= 2ESp1:n∼p1:nE⃗
σ
"
sup
f∈F
1
n
n
X
j=1
1
m
m
X
i=1
σijℓ(f(⃗
xij), yij)
#
(18)
= 2ESp1:n∼p1:n[Rmn(F)],
(19)
where the ﬁrst inequality is from moving the supremum inside the expectation and the second is from
subadditivity of suprema. Observing that the absolute difference of computing Rmn(F) on S and
13
Under review as a conference paper at ICLR 2022
S′ cannot exceed
1
mn, another application of McDiarmid’s inequality tells us that with conﬁdence
at least 1 −δ
2
2ESp1:n∼p1:n[Rmn(F)] ≤2Rmn(F) + 2
r
ln(2/δ)
2mn .
(20)
Combining Equations 10 and 20 with the union bound concludes the proof.
We now prove Theorem 1.
Proof. Theorem 2 tell us that with conﬁdence at least 1 −δ,
1
n
n
X
j=1
Lpj(f) ≤ˆ
LE(f) + 2Rmn(F) + 3
r
ln(2/δ)
2mn .
(21)
Thus, we must provide a (high conﬁdence) upper bound on
LE(f) −1
n
n
X
j=1
Lpj(f)
(22)
that holds uniformly for all f ∈F. We can use the same idea the proof for Theorem 2 to show
how Rademacher complexity controls generalisation to novel domains, rather than novel instances
within the same domain. Begin by letting P = {p1, ..., pn} be an i.i.d. sample of n domains from
E, and deﬁne
Φ(P) = sup
f∈F
LE(f) −1
n
n
X
j=1
Lpj(f).
(23)
If we construct P ′ by replacing any pj ∈P with p′
j ∼E, then we have |Φ(P) −Φ(P ′)| ≤1
n, so
McDiarmid’s inequality tells us that with conﬁdence at least 1 −δ
2
Φ(P) ≤Ep1:n∼E[Φ(P)] +
r
ln(2/δ)
2n
.
(24)
We proceed by bounding the expected value of Φ(P),
Ep1:n∼E
"
sup
f∈F
 
Eq∼E[Lq(f)] −1
n
n
X
j=1
Lpj(f)
!#
(25)
= Ep1:n∼E
"
sup
f∈F
Eq1:n∼E
"
1
n
n
X
j=1

Lqj(f) −Lpj(f)
##
(26)
≤Ep1:n,q1:n∼E
"
sup
f∈F
1
n
n
X
j=1

Lqj(f) −Lpj(f)
#
(27)
= Ep1:n,q1:n∼EE⃗
σ
"
sup
f∈F
1
n
n
X
j=1
σj

Lqj(f) −Lpj(f)
#
(28)
≤2Ep1:n∼EE⃗
σ
"
sup
f∈F
1
n
n
X
j=1
σjLpj(f)
#
(29)
= 2Ep1:n∼EE⃗
σ
"
sup
f∈F
1
n
n
X
j=1
σjE(⃗
x,y)∼pj[ℓ(f(⃗
x), y)]
#
(30)
≤2Ep1:n∼EE(⃗
xj,yj)∼pjE⃗
σ
"
sup
h∈F
1
n
n
X
j=1
σjℓ(f(⃗
xj), yj)
#
(31)
= 2Ep1:n∼EE(⃗
xj,yj)∼pj[Rn(F)],
(32)
14
Under review as a conference paper at ICLR 2022
where the ﬁrst inequality comes from moving the supremum inside the expectation, ⃗
σ is a vector
of Rademacher random variables, the second inequality is due to the subadditivity of suprema, and
the ﬁnal inequality comes from moving the expectation outside of the supremum. Noting that re-
placing one of the (⃗
xj, yj) pairs in the ﬁnal equality will result in Rn(F) changing by at most 1
n,
McDiarmid’s inequality can be used to say with conﬁdence 1 −δ
2 that
2Ep1:n∼EE(⃗
xj,yj)∼pj[Rn(F)] ≤2Rn(F) + 2
r
ln(2/δ)
2n
.
(33)
Combining Equations 21, 24, and 33 using the union bound completes the proof.
B
PROOF OF COROLLARY 1
Proof. We begin with the expected excess risk, which can be bounded from above by
ES[LE( ˆ
f) −LE(f ∗)] = ES[LE( ˆ
f) −ˆ
LE( ˆ
f)] + ES[ˆ
LE( ˆ
f) −ˆ
LE(f ∗)] + ES[ˆ
LE(f ∗) −LE(f ∗)]
(34)
≤ES[LE( ˆ
f) −ˆ
LE( ˆ
f)] + ES[ˆ
LE(f ∗) −LE(f ∗)]
(35)
= ES[LE( ˆ
f) −ˆ
LE( ˆ
f)]
(36)
= ES
"
LE( ˆ
f) −1
n
n
X
j=1
Lpj( ˆ
f)
#
+ ES
"
1
n
n
X
j=1
Lpj( ˆ
f) −ˆ
LE( ˆ
f)
#
,
(37)
where the inequality arises because, by deﬁnition, the empirical risk of ˆ
f must be less than or 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 ES[ˆ
LE(f ∗)] = LE(f ∗).
For the ﬁnal equality: the ﬁrst term can be bounded from above (with conﬁdence 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 conﬁdence 1 −δ) using the bound for the expected value of Φ(P)
derived in the proof for Theorem 1. Combining these two high conﬁdence bounds using the union
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 3, we present detailed results broken down by each
held out dataset.
Detailed results on each DG benchmark
In Table 1 we reported results of our linear model
competitors on DomainBed summarised over choice of held out domain. In Tables 2-7, we report
the detailed results of accuracy and choice of C paramater for each held out domain.
Cross Validation
0
15
30
45
60
75
Ave.
Raw pixel
Domain Wise
Acc
0.577
0.785
0.799
0.783
0.769
0.586
0.716 (0.096)
C
256.0
128.0
128.0
128.0
64.0
256.0
Instance Wise
Acc
0.582
0.774
0.788
0.783
0.765
0.579
0.712 (0.093)
C
1024.0
512.0
1024.0
1024.0
1024.0
1024.0
Table 2: Accuracy and selected ’C’ on Rotated-MNIST, using LinearSVC.
15
Under review as a conference paper at ICLR 2022
Cross Validation
A
C
P
S
Ave.
DINO ViT-B8
Domain Wise
Acc
0.877
0.676
0.971
0.446
0.743 (0.201)
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)
C
2.0
4.0
8.0
1.0
Table 3: Accuracy and selected ’C’ on PACS, using LinearSVC.
Cross Validation
C
L
S
V
Ave.
DINO ViT-B8
Domain Wise
Acc
0.972
0.648
0.787
0.811
0.804 (0.115)
C
0.5
0.5
0.125
0.5
Instance Wise
Acc
0.977
0.648
0.785
0.811
0.805 (0.117)
C
0.25
0.5
0.5
0.5
DINO ViTS8
Domain Wise
Acc
0.959
0.648
0.785
0.823
0.804 (0.111)
C
0.25
0.125
0.0625
0.25
Instance Wise
Acc
0.959
0.651
0.789
0.823
0.806 (0.109)
C
0.25
0.5
0.25
0.25
Table 4: Accuracy and selected ’C’ on VLCS, using LinearSVC.
Cross Validation
A
C
P
R
Ave.
DINO ViT-B8
Domain Wise
Acc
0.748
0.512
0.832
0.850
0.736 (0.135)
C
1.0
1.0
1.0
0.5
Instance Wise
Acc
0.730
0.514
0.833
0.846
0.731 (0.133)
C
4.0
2.0
2.0
4.0
DINO ViTS8
Domain Wise
Acc
0.740
0.496
0.820
0.834
0.722 (0.136)
C
1.0
0.25
0.5
0.5
Instance Wise
Acc
0.726
0.508
0.824
0.833
0.723 (0.131)
C
2.0
1.0
1.0
2.0
Table 5: Accuracy and selected ’C’ on OfﬁceHome, using LinearSVC.
Cross Validation
aclass
escape
hilux
i3
lexus
tesla
tiguan
tucson
x5
zoe
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)
C
1.0
1.0
1.0
1.0
2.0
1.0
2.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)
C
128.0
64.0
128.0
64.0
256.0
128.0
256.0
128.0
128.0
128.0
DINO ViTS8
Domain Wise
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)
C
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 LinearSVC.
16
Under review as a conference paper at ICLR 2022
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
0.3
0.4
0.5
0.6
Complexity
Accuracy
OfﬁceHome (Domain A)
0.6
0.8
1
1.2
1.4
1.6
0.65
0.7
0.75
Complexity
Accuracy
PACS (Domain A)
0.4
0.6
0.8
1
1.2
1.4
1.6
0.95
0.96
0.97
0.98
Complexity
Accuracy
VLCS (Domain C)
0.6
0.8
1
1.2
1.4
1.6
1.8
2
0.25
0.3
0.35
0.4
0.45
Complexity
Accuracy
OfﬁceHome (Domain C)
0.6
0.8
1
1.2
1.4
1.6
0.48
0.5
0.52
0.54
Complexity
Accuracy
PACS (Domain C)
0.6
0.8
1
1.2
1.4
1.6
0.58
0.6
0.62
Complexity
Accuracy
VLCS (Domain L)
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
0.4
0.5
0.6
0.7
Complexity
Accuracy
OfﬁceHome (Domain P)
0.6
0.8
1
1.2
1.4
1.6
0.93
0.94
0.95
0.96
0.97
Complexity
Accuracy
PACS (Domain P)
0.6
0.8
1
1.2
1.4
1.6
1.8
0.62
0.64
0.66
0.68
Complexity
Accuracy
VLCS (Domain S)
0.5
1
1.5
2
0.4
0.5
0.6
0.7
Complexity
Accuracy
OfﬁceHome (Domain R)
0.6
0.8
1
1.2
1.4
1.6
0.35
0.4
0.45
0.5
Complexity
Accuracy
PACS (Domain S)
0.6
0.8
1
1.2
1.4
1.6
1.8
0.7
0.72
0.74
0.76
0.78
0.8
Complexity
Accuracy
VLCS (Domain V)
0.5
1
1.5
2
0.3
0.4
0.5
0.6
Complexity
Accuracy
OfﬁceHome
CORAL
ERM
IRM
Mixup
MMD
RSC
SD
VREx
0.6
0.8
1
1.2
1.4
1.6
0.62
0.64
0.66
0.68
Complexity
Accuracy
PACS
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
0.72
0.73
0.74
0.75
0.76
Complexity
Accuracy
VLCS
Figure 3: Performance of various neural network DG algorithms as a 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 is the leave-one-domain-out cross-validation
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.
17
Under review as a conference paper at ICLR 2022
Cross Validation
L100
L38
L43
L46
Ave.
DINO ViT-B8
Domain Wise
Acc
0.444
0.457
0.516
0.399
0.454 (0.041)
C
0.25
1.0
1.0
2.0
Instance Wise
Acc
0.472
0.391
0.366
0.324
0.388 (0.054)
C
256.0
128.0
256.0
256.0
DINO ViTS8
Domain Wise
Acc
0.375
0.231
0.480
0.398
0.371 (0.090)
C
0.125
1.0
2.0
4.0
Instance Wise
Acc
0.407
0.157
0.438
0.322
0.331 (0.109)
C
256.0
64.0
128.0
128.0
Table 7: Accuracy and selected ’C’ on Terra Incognita, using LinearSVC.
18
