An Investigation of Domain Generalization with Rademacher Complexity
Authors: Da Li
Henry Gouk
Timothy Hospedales
Venue: Submitted to ICLR 2023 (2023)

Abstract: The domain generalization (DG) setting challenges a model trained on multiple known data distributions to generalise well on unseen data distributions. Due to its practical importance, many methods have been proposed to address this challenge. 
However much work in general purpose DG is heuristically motivated, 
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 tuned empirical risk minimisation baseline. 
We present a novel learning-theoretic generalisation bound for DG that bounds unseen domain generalisation performance in terms of the model’s empirical risk and Rademacher complexity -- providing a sufficient condition for DG. Based on this insight, we empirically analyze the performance of several methods and show that their performance is indeed influenced by  model complexity in practice. 
Algorithmically, our analysis suggests that tuning for 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 2023
AN INVESTIGATION OF DOMAIN GENERALIZATION WITH RADEMACHER COMPLEXITY
Anonymous authors Paper under double-blind review
ABSTRACT
The domain generalization (DG) setting challenges model trained multiple known data distributions to generalise well on unseen data distributions. Due to its practical importance, many methods have been proposed address this challenge. However much work in general purpose DG is heuristically motivated, as the DG problem is hard to model formally; and recent evaluations have cast doubt on exist- ing methods' practical efficacy- in particular compared to a well tuned empirical risk minimisation baseline. We present novel -eeemiingthhooettc generalisation bound for DG that bounds unseen domain generalisation performance in terms of the model's empirical risk and Rademacher complexity providing a sufficient condition for DG. Based this insight, empirically analyze the performance of several methods and show that their performance is indeed influenced by model complexity in practice. Algorithmically, main generalisation should be achieved by simply performing regularised ERM cross-validation objective. Empirical results the
analysis suggests that tuning for do-
with ontee--onedommin DomainBed benchmark corroborate this.
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 applications of machine learning (14 37 (25), and often leads to disappointing results practical machine learning deployments, since data 'in the wild' is almost inevitably different from training sets.
Given the practical significance of this issue, numerous methods have been proposed that aim to improve models' robustness to deployment under train-test domain shift (37), problem setting known as domain generalisation (DG). These span diverse approaches including 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; since the target domain(s) of interest cannot be observed during training, and cannot be directly approximated by the training domains due to unknown distribution shift. Therefore the many popular approaches (37) are based on poorly understood empirical heuristics problem highlighted by (20), who found that no DG methods reliably outperform a well-tune empirical risk minimisation (ERM) baseline.
Our first contribution to present an intuitive learning-theoree bound for DG performance. In- tuitively, while the held-out domain of interest is unobservable during training, we can bound its performance using learning theoretic tools similar to the standard ones used bound the performance on (unobserved) testing data given (observed) training data. In particular we show that the perfor- mance on held out target domain is bounded by the performance on known source domains, plus two additional model complexity terms, that describe how much a model possibly have overfitted to the training domains. This provides a sufficient condition for DG and leads to several insights.
Firstly, our theory suggests that DG performance is influenced 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 an serfittinngundrrfitttin trade-off (17). Based on this, we conjecture that the efficacy of the plethora of available strategies (37) - from data-augmentation to specialised optimisers is largely influenced by explicitly or implicitly choosing

---

Under review as a conference paper at ICLR 2023
different fit-copllextty trade-offs. And further, that the importance of proper tuning as discussed by (20) may be mediated in part by the impact of hyperparameters on model complexity.
Analyzing these issues empirically is difficult, as model complexity is hard to carefully control in deep learning due to the large number of relevant factors (explicit regularisers, data augmentation, optimiser parameters, etc). (20) attempted to address this by random hyper-paramedd search in the DomainBed benchmark, but are hampered by the computational infeasibility of accurate In this paper, we use linear models, random forests, and shallow MLPs to demonstrate more clearly how cross-domain performance depends on model complexity.
search.
Secondly, our theory further suggests that the model selection criterion 22 an important factor in DG performance. In particular, regularisation should be stronger when optimizing for future DG performance than when optimizing for performance on seen domains, which we confirm empirically, Further, our theoretical and empirical results show that, contrary to the conclusion of (20), domain- wise cross-validation a better objective to drive DG model selection than instance-wise.
In summary, the take- home messages of our analysis are: (i) When achievable, low empirical risk combined with low complexity provides sufficient condition for DG. (ii) Model fit vs complexity trade-off is key factor in practical DG performance. (iii) The complexity control strategy used to determine bias-variance trade-off crucial, with peak DG performance achieved when optimizing model complexity based on domain- wise validation. (iv) The regularisation strength required for optimal DG is greater than for conventional optimization for within-domain performance.
RELATED WORK
Theoretical Analysis of the DG Setting and Algorithms The DG problem setting was first analysed in (9). Since then there have been some attempts to analyse DG algorithms from a generalisation bound perspective (29 8 23 2 33). 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 test time-e.8 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 broad range of model classes (including neural networks), and makes comparatively milder assumptions about the relationship between domains i..., 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 in (), 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 pathological distribution shift (3) 24). 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 example, (24) provides bounds that assume problems conform to a specific class of structural equation models, and the analysis assumes that infinite training data is available within each observed training domain. We primarily address the standard DG formalisation of @, which is concerned with the expected performance of model on new domains sampled from distribution over domains. However, we also provide a means to transform any bound on the expected (or "average-case") risk to a high-confidence bound on the worst-case risk. Possibly the most similar work to our theoretical contributions is (I) that also provides generalisation bounds for DG. However, their analysis only applies to finite 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 (0),, who compared several state of the art methods using DomainBed, a common benchmark and hyper-parament tuning protocol. They ultimately defend Empirical Risk Minimization (ERM) over more sophisticated alternatives on the grounds that no competitor consistently beats it. We also broadly defend ERM, and build on the same benchmark, but differently we provide deeper analysis into when and why ERM works. More specifically: (i) We provide a theoretical analysis of ERM's generalisation quality unlike the prior purely empirical evaluation, (ii) We re-use the BemainBed benchmark to directly
2

---

Under review as a conference paper at ICLR 2023
corroborate this theory under controlled conditions using linear models and random forests, where model complexity can be more feasibly tuned. (ii)) Our complexity analysis provides a possible explanation of the hyperparameter sensitivity observed by (20), and possible explanation for why ERM is hard to beat (if methods primarily influence complexity). (iv) We identify, and empirically validate, the preferred model selection criterion for DG, point which was inconclusive in (20).
3 BOUNDING RISK FOR DOMAIN GENERALIZATION
Lid. learning is concerned with learning a mapping from some imput space X', to a label space ), given data drawn from distribution on X V. One aims to find model, f E F, that minimises the expected loss (also called risk) on unseen data,
arg min (f).
Lp(f) = -(
(1)
jeF
where p is the data distribution and f(:,-) is the loss function. In practice, we only have access to a finite set data, S = (:),) sampled i..dd from this distribution, so must minimise an empirical risk estimate,
m Lp()= = 1 Σ (f(E.)....
f = arg min (f), JEF
where is the number of training examples. A 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 with a loss function bounded between zero and one (e-g., the misclassification rate) this can be done via
ln(2/8)
Lp(f) S Lp(f) + 2R (F) 3v
(3)
2m
which holds with probability least 1 6, and R(F) is known the empirical Rademacher complexity of the hypothesis class, F. This complexity term is defined as
m
Rm
Eg
sup SEF
o,e(((()).))
(4)
m i=1
where o, are Rademacher random variables, distributed such that For hypothesis class consisting of norm-constrained linear classifiers depth-restricted decision trees (or ensembles of decision trees), one can achieve a bound on Rademacher complexity that scales as Om There are variety of ways to define hypothesis classes for neural networks, but most recent approaches fix an architecture and specify constraints on the norms of weights or distances they can move from their initialisations (4] 30 19).
0.5.
Domain generalisation. While standard i.i.d. learning assumes all data come from the same distribution, the DG problem setting assumes the existence of an environment E, of distributions p (.) Throughout the remainder we assume all probability density functions in Supp(E) are measurable according to some common base measure. Note that do not restrict what types of differences one could see between different domains sampled from E: for any two distributions in p. q E supp(E) it could be the case that either p( q(z), or p(y(²) * q(ylT), even that both types of distribution shift have occurred. The conceptually simplest-and often implicitly assumed-gou goal of DG methods is minimise the expected risk across different distributions that could be sampled from the environment,
(5)
This object also the most commonly analysed idealised objective in the learning theory literature ( 22 (8 33), but other formulations also exist (3), As with the single domain learning problem, only have access to an empirical estimate of the risk,
-
= 1
(6)
where we assume for ease of exposition that all n domains have the same number of examples.
See Section 26.2 of (34) for texthook example of bounding the Rademacher complexity of linear models with bounded weight norms.
3

---

Under review as a conference paper at ICLR 2023
3.1 TARGET DEEANNET GENERALISATION BOUND
One can construct a bound on the error of a model operating on a novel domain, by measuring the mean total variation distance between q and each source domain pt, follows.
Theorem 1. For 1-Lipschitz loss, :). taking values in [0, 11. with confidence at least - 5 for all f F we have that
1g(5) (F)+++++ 2R (F)
2
Σ - - - 3V 2mn
1
In ln(2/8)
where n. is the number of training domains and m is the number of training examples in each domain.
The proof can be found in the appendix. While such bounds at first glance seem intuitive and appealing, they are of limited practical use in the DG setting, because it is not possible to either measure or change the TV distance between the source and target distributions in the DG setting.
3.2 TARGET DOMAIN-INDEPENDO GENERALISATION BOUND
We next bound the generalisation gap between the observed empirical risk, ie the source domains and the expected risk, Le, on unseen domains that holds uniformly for all hypotheses in F. Theorem 2. For a 1-Lipschitz loss, -(:,,,, taking values in [0, 1]. with confidence least 8 for all f E F we have that
In(4/8)
In(4/8)
LF( S ()) mm (F) 2R, (F) 3V
3/
2mrrn
2n
where n is the number of training domains and m is the number of training examples in each domain.
The proof can be found in Appendix A We remark that this theorem makes assumption the distribution over domains &, model invariances, or similarity between source and target domain. The key assumption-Sharee with - that source and target are independent samples from E.
Discussion Theorem 2 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 overfit 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..d. learning, a very simple model may minimise the Rademacher terms, R. while producing high empirical risk, i,F, and vice-versa. Thus good generalisation critically depends on a carefully chosen empirical risk model complexity trade-off. The difference between Theorem and single domain bounds (e.g., Equation 3 is the additional dependence on the number of domains n and additional Rademacher complexity term. This highlights an important insight: When the goal is generalise to new domains, the risk of overfitting is higher. Therefore lower complexity model is optimal for held out domain performance compared for seen domain performance in standard i..dd learning.
3.3 BOUNDING THE EXCESS RISK OF ERM
As 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 (7).
Corollary 1. With probability at least 1 - ô, the excess risk of the empirical risk minimiser in F is bounded as
In(4/0)
Im(4/8)
BIT (1 ((²) 2mm 2R) + +
2
2mn
2n
4

---

Under review as a conference paper at ICLR 2023
The proof (in Appendix (B) uses the same technique as the usual proof for excess risk (see, e.g.. (31) and some of the intermediate results required for Theorem 2
Discussion Corollary [ 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 particular, for any typical hypothesis class, ERM converges the optimal classifier a rate of O ///m/m))/ +01/ To justify itself theoretically, any future DG method that claims to be better than ERM should either: (I) demonstrate faster convergence rate than this-at least by an improved constant factor; (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 is given by (24). 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.
3.4 FROM AVERAGE-CAR CASE TO TTORST-CASE
For some applications- such as safety critical systems that cannot be allowed to fail one is interested in the bounding the error in the worst-case domain,
[f(
sup (f(.)
(9)
pEsupp(E)
Some papers accomplish this by making assumptions about the distribution &. E.g.. by explicitly constructing as a convex combination of known domains. or showing that all models in F are "invariant" to all domains in the support (4)). We instead aim to construct a bound that will hold for bust-but not necessarily all domainn that could be seen at test time. This allows us to instead only make relatively mild assumption about bounded variance, as shown in the following result.
Lemma 1. For p ~ E, the following holds with confidence at least 1 - K.
L,U S L +
K Var [T
Proof. The statement follows by aggregating performance on each domain into a scalar (from the definition of (.)), then computing the variance via the law of the unconscious statistician. Finally, an application of the confidence interval formulation of one-sided variant of Chebyshev's 's inequality is used. This concentration inequality is also sometimes known as Cantelli's ' inequality.
As K goes zero, this Lemma allows us bound the error for individual domains in increasingly larger subsets of the support of E, thus achieving something practically similar to bounding Equation 9 Interestingly. those methods that attempt address worst-case domain generalisation by proving invariance of models to the underlying domain (i.e., those that show (p( Lg(f), ), * q) will have zero variance, by definition. Thus, the average-case bound in Theorem 2 also provides a bound on the worst-case generalisation error in the case of invariant hypothesis classes.
For those methods that do not rely on domain expertise to prove invariance, it should be noted that minimising the sample variance on the available training domains will not necessarily lead to minimising the population variance in Lemma However, it is possible to construct an upper bound to the population variance, yielding the worst-case bound below.
Theorem 3. For E, the following holds with confidence at least 1 - (ō + k).
(p(f)s+t
A,
where is a bound on F (J) that holds with confidence I (e.g.. from Theorem 2
The proof for this result can be found in Appendix C This result suggests that one can apply simple transform to the average-case bound provided by Theorem in order to obtain a high-confidence upper bound on the worst-case error in unseen domains.
5

---

Under review as a conference paper at ICLR 2023
3.5 FROM BOUNDS TO ALGORIHTMM
The analyses above suggest that to optimise for performance on held-out domains, one should simultaneously minimise empirical risk and model complexity. In practice the simplest way to tune complexity is via regularisation. To find the regularisation hyperparameters that work best for the average-case performance, one should measure held out domain performance via cross-validation (if there are few domains available), or with single validation set of held-out domains (if many domains are available). This provides an unbiased estimate of the expected risk, I. (denoted as domain-wise CV criterion). In contrast, optimising for performance on held out instances of known domains as recommended by (20) (denoted instance-wise) is an optimistically biased estimator.
If worst-case performance is of interest, one typically cannot obtain an unbiased estimate of i,f. However, it is interesting to note that the link between Theorems 2 and B somewhat surprisingly suggests that any strategy that works well for the average-case objective also work for the worst-case objective. This is because, although the worst case bound is more pessimistic, both bounds will be minimised for the same regulariser strength (Rademacher complexity); the transform from average- case to worst-case bound is monotonically increasing function, so the location of extreme points (i.e., optimal fit-complexity trade-off) is preserved. Thus a novel insight is that we can use the single domain-wise validation strategy above optimise for both average and worst-case DG performance.
EXPERIMENTS
Based on our previous theoretical analysis, conduct experiments on DomainBed (20) and we study the following questions: (1) Theorem shows that novel domain generalisation is governed by empirical-risk complexity trade-off. Can we directly demonstrate the dependence of generalisation on complexity by controlling model complexity? (2) Could the hyperparameter sensitivity of DG methods observed by (20) be mediated by model complexity? (3) Given that model complexity is key determinant of generalisation, what is the best objective for tuning regularisation strength? (4) Could our bounds ever generate non-trivial guarantees for cross- noms-n recognition performance?
4.1 DOMAIN GENERALISATION PERFORMANCE DEPENDS ON MODEL COMPLEXITY
To directly investigate the impact of model complexity domain generalisation, we use me-computed deep features I and shallow classifiers linear SVM and Random Forest (RF). For linear models, tight bounds on model complexity are known and can be directly controlled by a scalar hyperparameter (5). The objective is convex so confounding 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. Similarly for RF. complexity is controlled by the depth of the trees when the models are applied to binarised features (0)). This a direct consequence of the resulting hypothesis class being finite, and an application of Massart's 's lemma (5).
Setup We use DINO 12) pre-trained DINO- as deep features, and then train classifiers using seikit-learn. We experiment on six different DG benchmarks, including RotatedMNIST (18), PACS (26). VLCS (6). OfficeHome (36), SVIRO (15) and Terra Incognita (6) For linear SVM, we use the objective _ Σ. {( (2:), y:) + || with parameter C' controlling the complexity of model w through loss-regularisation trade-off, and search a range of log, C in {-10,... ..). For RF we search a range of depths D in {1,.. 303. 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. average over 5 random seeds for dataset splitting, and all choices of held-out target domain. From these we can see that: (i) Experiments exhibit the classic trade-off between fitting the data well and constraining hypothesis class complexity appropriately. For SVM we observe underfitting for high regularisation (small C), and overfitting at low regularisation (large C). RF is similar but with less severe overfitting, (ii) Comparing the within- and across-domain evaluation: across- coross-domain leads to lower performance- which is to be expected, due to the distribution shift.
Results
Note that using fixed feature extractor trained on independent data does not impact the model complexity associated generalisation bound.

---

Under review as a conference paper at ICLR 2023
0.35
0.9
0.80
Texe SccuPsKY
0.8
0.75
97
0.7
0.70
Acress soman idnz vibal
karsss-doma +tbs)
0.5
Acros-demmah (dto v858)
0.6
Wolte-demah (ine vit0)
0.65
Wihn-omann (oro vibal
Wihincoman viail
Across Jomain vesus Wttn-domain PACS
Aposs darran veraas Wittnn VLCS
Acros-soman versu Wthnddmman on officuomm
0.30
0.8
0.75
0.7-
0.7
0.70
0.85
0.5
0.4
0.4-
0.60
0.1
0.53-
0.2
0.
Day
Day
Figure 1: Linear SVM (Top) and Random Forest (Bottom) performance on DomainBed benchmark datasets. Optimal tuning for performance on novel target domains (red) always requires stronger regularisation (lower C' or D) than for performance on seen domains (bluc).
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 complexity is lower for DG than for conventional i.i.d.
learning. More examples are in Appendix Fig. 4 Note that these results are an exhaustive search of model complexity, and do not constitute a complete algorithm, which would need to chose a specific complexity. We evaluate this in Section 4.3
4.2 IMPACT OF HYPER-PARAMETELS ON COMPLEXITY AND DG PERFORMANCE
Our experiment in Section showed that linear models exhibit very clean trade-off between complexity 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. The prior evaluation (20) attempted to control 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. Under these conditions, they found that existing state of the methods failed outperform well tuned ERM. We observe that many of these factors controlled by DomainBed directly (e.g., weight decay) or implicitly (e.g.. batch size) impact model complexity. To study such hyrae-parameter tuning through the lens of complexity, we take one representative factor of stopping iteration, and measure its impact on model complexity as possible explanation of why it is important control.
Setup To ensure that complexity can be measured well, we work with 2-layer MLPs. Specifically, we take fixed ImageNet pre-trained ResNet-18 18 features, and feed them MLPs, which are then trained using the DomainBed framework. We then report the results of an ERM model, checkpointed 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 retrospectively determine the complexity of a trained network using the measure proposed by (30), which bounds the Rademacher complexity of a 2-layer MLP hypothesis classes. More concretely, the expression used for computing complexity is [[|U U F + ||0"))2), where U is the weight matrix of the first layer, 0 is its random initialisation, and V is the weight matrix of the second layer. We use || || to denote Frobenius norm, and ||. ||2 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.
7

---

Under review as a conference paper at ICLR 2023
BRM Checkpotes or Officeloeee
ERM Checkpsitts oz PACS
ERM Checkpotra VLCS
0.0
Accumcy
0.5
0.33
11.4
0.5
0.3
0.6
0.2
10
Comptesit
Complestyy
Complesity
Figure 2: Leave-one-domain out cross-validation performance of shallow neural networks as function of their measured model complexity while training on DomainBed (DB) when checkpointed every 300 iterations up to 50,000. The overall results are consistent with standard bias variincee trade-off (cf. Fig T for linear models), with peak performance in the middle of the complexity range.
Results The results in Fig. summarise the trade-off between measured model complexity (x-axis), and unseen domain test accuracy (y-axis), averaged over all held out domains for each dataset for an ERM model checkpointed every 300 iterations against the corresponding complexity. Neural models typically gain complexity with iterations (32) 21). and we see this in the plot. The overall result is one of overfiting-undeefttinng trade-off curves mirroring Fig. [ This explains why checkpoint selection was found to crucial in (20) directly affects complexity and hence generalisation via Thm 2 More generally, to the extent that all the other considered prper-parameters influence complexity (we selection more generally is crucial to control for DG (0).. A limitation of this analysis is that we do not have tight bounds for deep neural networks, so can not repeat this same analysis for popular models such as ResNet.
leave quantifying this to future work), it may explain why syyper-paramed
4.3 EVALUATING LINEAR MODELS ON DOMAINBED
Having shown that model complexity is major factor in DG performance, next consider practical algorithms for complexity tuning. From Fig. we see within-domain and cross-domain evaluation have different optimal tuning. When automating the search for a good regularisation parameter, these evaluation criteria correspond respectively to hyperparameter selection based on a validation set from the seen source domains (instance-wise). vs a validation set drawn from held out source domain (domain-wise As discussed in Section 3.5 the latter criterion corresponds to a unbiased estimator of expected cross-domain generalisation performance 7 (f), which our theorem bounds.
Setup We performed DG evaluation on DomainBed using ERM with linear models using DINO features as in Section 4.1 and pre-trained ResNet-50 for direct comparability to (2)) For each held out domain, performed hyperparameter tuning with either instance-wise cross-validation (where validation folds are drawn from the same source domains used for training) or domain-wisg wise voos-vvaiiotion (where validation folds are drawn from held-out domains not seen during training).
The results in Tab. D rreport the average accuracy across held out domains, and the average selected log C' regularisation strength (See Appendices for the full breakdown of results for each held-out domain). The domain- cross-validation objective lcads to similar or better accuracy, and similar or smaller C value selection (i.e., stronger regularisation). This outcome is as predicted by our theory, but different to the conclusion of (20). We attribute this difference to the difficulty of accurately tuning tuning stochastically trained neural networks attempted in (20).
Results
4.4 INSTANTIATING THE BOUND
A limitation of our theory, shared by most existing work on statistical learning theory, is that while derived bounds give insights into the factors affecting generalization such as complexity - they are often not tight enough to provide useful performance guarantees for many problems and models of interest. As a counterpoint to this we illustrate one example where our bound provides non- non-trivial guarantees. While benchmarks within DomainBed have relatively small number of domains, many problems in the broader AI community have a larger number of domains, making them more amenable to guarantees. For example, the LEAF (TT) suite of benchmarks popular in the Federated
8

---

Under review as a conference paper at ICLR 2023
Table 1: Comparing model selection criteria using linear SVMs. Domain-wise validation usually outperforms instance-wise and selects stronger regularisation (lower C)) as predicted by our theory.
DINO VIT-B8
ResNct-50
Domain Wise
Instance Wise
Domain Wise
Instance Wise
Ace
log C
Acc
log
Acc
log C
Acc
log
PACS
74.3
-1.73 (#:0.40)
70.6
1.56 (=0.66)
68.1
2.43 (#0.69)
66.9
5.03
(=0.66)
VLCS
80.4
-1.04 (#:0699)
80.5
-0.87 (+0.35)
76.7
1.73(11.20)
77.6
2.25
(=0.35)
Officellome
73.6
-0.17 (+0.35)
73.1
1.04 (=0.40)
70.0
1.91 (+0.35)
69.1
3.64 (=0.66)
SVIRO
97.2
0.21 (1:0.33)
95.3
4.85 (100.6)
93.3
4.16(##092)
92.7
6.93 (10.00)
Terra Inc.
45.4
-0.17 (100.77)
38,8
5.37 (230355)
28.3
2.08 (1:1277
26.9
6.93 (10.00)
Learning community have a larger number of domains. We consider the multi-domain text analysis task defined in LEAF. The task is binary sentiment classification of tweets from different users, with each user detining a domain. We train a random forest on this task, and show the guaranteed DG classification accuracy along with the empirical DG classification accuracy in Figure
CONCLUSION
From the results we can see that our Theorem (together with the RF bound from (10) provides a mostly non-trivial (bet- ter than random performance) guarantee for small depth RFs. We studied the performance of domain generalisation methods through the lens of model complexity (bias-variance trade-off) from both theoretical and empirical perspectives. Both perspec- tives show that complexity impacts cross-domain generalisation in way that mirrors the Mlas-variance trade-off in conventional i..d. learning- but where stronger regularisation is required optimising for cross-domain generalisation than if optimising for conventional within-domain generalisation. We clarified the preferred model selection criterion in each case.
Test ernor
Bound
0.5
Random Gurssing
Lanor
0.6
0.4
2
Tree Depth
We set out to address four questions, which can be answered as: (1) Yes. The influence of cross-domain generalisation on complexity can be directly demonstrated using linear models and RFs. (2) Maybe. Hyperparameter choice DomainBed influences neural network complexity, and this may in turn influence neural generalisation.
Figure 3: Empirical and guaranteed DG performance on LEAF Senti- ment analysis using RF.
(3) If the goal is to optimise for domain generalisation, then domain- wise validation is preferred to instance-wise validation for model-selection. This will lead to stronger regularisation for better out-of-domain generalisation (at a cost to in-domain generalisation). (4) Yes. While current complexity bounds may not be tight enough to provide useful guarantees for DomainBed and deep neural networks, many benchmarks and models popular in the broader AI community can already support non-trivial performance guarantees for cross domain generalisation.
Using general purpose pre-trained features (12) as we did here, and focusing on learning shallow models that can be accuralely tuned for DG may be a promising alternative avenue for improving DG in practice compared to popular focus on sophisticated neural DG methods (37). Although achieving state of the art performance is not focus, note that results in Tab. | are not far behind end-to-end trained state of the art (20), despite using fixed features and shallow models.
While we focused on ERM, we remark that our bound applies to any class of models for which Rademacher complexity can be computed-our analysis is rooted in uniform convergence, so is agnostic to the training algorithm used to obtain that model. For example, the choice of auxiliary loss function, whether (9) or not (13) the training algorithm uses domain labels, or whether some form of adversarial training employed (35) will not have any bearing on our bounds unless they also change the underlying hypothesis class in some way.

---

Under review as a conference paper at ICLR 2023
REFERENCES
[1] Kartik Ahuja, Jun Wang, Amit Dhurandhar, Karthikeyan Shanmugam, and Kush R. Varshney. Empirical or invariant risk minimization? sample complexity perspective. In ICLR, 2021.
[2] Isabela Albuquerque, João Monteiro, Mohammad Darvishi, Tiago H Falk, and Ioannis Mitliagkas. Generalizing to unseen domains via distribution matching. arXiv preprint arXiv:1911.00804 2020.
[3] Martin Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk mini- mization. arXiv, 2019.
[4] Peter L Bartlett, Dylan J Foster, and Matus J Tellgarkk. Spectrally-normalized margin bounds for neural networks. In NeurlPS, 2017.
[5] Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. JMLR, 2002.
[6] Sara Beery, Grant Van Horn, and Pietro Perona. Recognition in terra incognita. In ECCV, 2018.
[7] Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. NeurIPS, 2018.
[8] Gilles Blanchard, Aniket Anand Deshmukh, Ürün Dogan, Gyemin Lee, and Clayton Scott. Domain generalization by marginal transfer learning. JMLR, 2021.
[9] Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classifica- tion tasks to new unlabeled sample. In NIPS, 2011.
[10] Sebastian Buschjäger and Katharina Morik. There is no double-descent in random forests. arXiv preprint arXhv:2111.04400 2021.
[11] Sehastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv: 2018
[12] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski. and Armand Joulin. Emerging properties in self-supervised vision transformers. In ICCV, 2021.
[13] Junbum Cha, Sanghyuk Chun, Kyungjae Lee, Han-Cheo Cho. Seunghyun Park, Yunsung Lee, and Sungrae Park. Swad: Domain generalization by seeking flat minima. NeurlPS, 2021.
[14] Gabriela Csurka. Domain Adaptation in Computer Vision Applications. Springer, 2017.
[15] Steve Dias Da Cruz, Bertram Taetz, Thomas Stifter, and Didier Stricker. Illumination normal- ization by partially impossible encoder-decoder cost function. In WACV, 2021.
[16] 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.
[17] Stuart Geman, Elie Bienenstock, and René Doursat. Neural networks and the bias/variance dilemma. Neural Computation, 1992.
[18] Muhammad Ghifary, W. Bastiaan Kleijn, Mengjic Zhang, and David Balduzzi. Domain generalization for object recognition with multi-task autoencoders. In ICCV, 2015.
[19] Henry Gouk, Timothy Hospedales, et al. Distance-based regularisation of deep networks for fine-tuning. In ICLR, 2021.
[20] Ishaan Guirajani and David Lopez-Paz. In search of lost domain generalization. In ICLR, 2021.
[21] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In ICLR, 2016.
[22] Trevor Hastie. Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media, 2009.
10

---

Under review as a conference paper at ICLR 2023
[23] Shoubo Hu, Kun Zhang, Zhitang Chen, and Laiwan Chan. Domain generalization via multido- main discriminant analysis. In UAI, 2020.
[24] Dominik Janzing. Causal regularization. In NeurIPS, 2019.
[25] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, 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 benchmark of in-the-wild distribution shifts. In /CML, 2021.
[26] Da Li, Yongxin Yang. Yi-Zhe Song, and Timothy Hospedales. Deeper, broader and artier domain generalization. ICCV, 2017.
[27] Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. In COLT, 2009.
[28] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[29] Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In JCML, 2013.
[30] 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.
[31] Massimiliano Pontil and Andreas Maurer. Excess risk bounds for multitask learning with trace norm regularization. In COLT, 2013.
[32] Lutz Prechelt. Early stopping-but when? In Neural Networks: Tricks of the trade, pages 55-69. Springer, 1998.
[33] Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. An online learning approach to interpolation and extrapolation in domain generalization. arXiv preprint arXiv:2102.13128, 2021.
[34] Shai Shalev-Shwartz and Shai Ben-David, Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[35] Shiv Shankar, Vihari Piratla, Soumen Chakrabarti, Siddhartha Chaudhuri, Preethi Jyothi, and Sunita Sarawagi. Generalizing across domains via cross- gooss-gradient training. arXiv preprint 1oXv::180.11744. 2018.
[36] Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep hashing network for unsupervised domain adaptation. In CVPR, 2017.
[37] Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization: survey, 2021.

---

Under review as a conference paper at ICLR 2023
A PROOF OF MAIN RESULTS
We use a slightly modified version of the standard empirical Rademacher complexity bound on generalisation error, as stated by (28) but originally shown by (5), where the modification 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 re-state it here for completeness.
Theorem 4. For Pi.....PP Pn independent samples from E, and I-Lipschitz loss E(.,-) taking values in [0, 1], the following holds with confidence at least 1 8,
1 Σ Lo (1)
S
1 Σ n
Ln, (f) + 2RmM (F) + 3/
(n(2/))
(10)
2nn
j=1
j=1
where Lpg (f) is measured on Sp;- (Geg
vo)) ( a collection of m i.i.d. samples from pj-
Proof. Let = Sp U...USp. and define
((S) = sup fEF
(1) (f))
(11)
Note that (SS) satisfies the bounded differences property required by McDiarmid's inequality: i.e., if we construct S' by replacing any one of the (Iaa, (ui)) in S with another random variable also drawn from Py. then ($) ((S)) S mm Therefore McDiarmid's inequality implies that with confidence
at least 1 6
2
In ln(2/5)
((S) Esp... Pi:n [0())
(12)
2mn
We continue by bounding the expected value of (SS).
Es EppI.. Pien [((S]]
(13)
1
=EspI.n Mim
sup FEF 71
(Lp, (f)
(14)
j=1
= =Espi.n upin
sup FEF 1=1
1
Ess, mps
m (( [66)
1 Σ
(f vs)
(15)
< Esyyn upin
Eg
PPln
sup fEF 1
((EE)))))))) - - [(((Ft))
(16)
m
= =Espni PPim
Egg Plan
PPim EN
sup fEF
oi ((U() 164 - e(((F.5)
(17)
1
< Esy pn
upin
Ex sup JET n
Jig ((
(18)
m
+ Esp upinn
Eg
sup
o,y -o)(((((E)))
(19)
fEF 11
m
j=1
2 Σ
2EE 2ESpun Piim
Es
sup
Σ Tiy (f 9t)
(20)
FEF
22R pim (R)n()))
(21)
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 R.na (F) S and S
12

---

Under review as a conference paper at ICLR 2023
cannot exceed another application of McDiarmid's inequality tells us that with confidence at least 1 2
ln(2/6)
2Es pI.. MPinn Rmm (F) S 2Rmm (F) 2
(22)
2mn
Combining Equations 12 and with the union bound concludes the proof.
A.1 PROOF OF UNOBSERVABLE BOUND
Proof. We start by bounding the left-hand side of the main theorem statement as
1 Σ
n
Lg
L, (f) [f(()
(p) (f)
(23)
n j=l
n j=1
1
Lp, (f) + +
1
<
f(z)(a(Z) - -p(()) dz
(24)
11 j=1
j=1 2
Lp, (1) + 1
Σ
|1 1acllll-ssll
Psll -
(25)
j=1
j=1
2 Σ
Lp, (f)
- 1y-pll
(26)
j=1
(27)
The result follows by applying Theorem to the first summation.
A.2 PROOF OF OBSERVABLE BOUND
We now prove Theorem
Proof. Theorem tell us that with confidence least 1 5,
ln(2/)) 2mn
2mm (F)+ +3
(28)
Thus, we must provide a (high confidence) upper bound on
Lf(I) 1 n Σ (f)
(29)
that holds uniformly for all f E F. We can use the same idea the proof for Theorem 4 to show how Rademacher complexity controls generalisation to novel domains, rather than novel instances within the same domain. Begin by letting P = {PI....,P. be an i.i.d. sample of n domains from E, and define
((P) sup L JEF
n Σ Lf)
1
(30)
If we construct P' by replacing any Py P with p'z ~ E, then we have ((()) x(P)) < 2, so McDiammid's inequality tells that with confidence at least
In (2/0))
((P) < E Ep ~ [o(P]
(31)
2n
13

---

Under review as a conference paper at ICLR 2023
We proceed by bounding the expected value of (PP).
- _ Σ Lp, (f))
Ep E
~
sup /EF
E [f
(32)
12 ==1
1
Les (1) Lips (12
= E Ee
sup B ByreiNE JEF
(33)
1
Lag (f) Lyg (n)
sup /EF TI
(34)
j=1
1 Σ
Lo L,, -o,, (1))
(a, -
-ia Eo
sup JEF TI
oj
(35)
1=1
n Σ o 1 (1)
S 2R <PRpineeE Edg
sup SEF 71
(36)
j=1
= =2RpineER
sup FEF
J (a,))>> (E (((((E)
(37)
1
S 2R B (1p,)))
E
sup hEJ Ti
o (((((())))))
(38)
(F),.
(39)
where the first inequality comes from moving the supremum inside the expectation, o is a 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 replacing one of the (ž,, 3j) pairs in the final equality will result in (F) changing by at most A. McDiarmid's ss inequality can be used to say with confidence
A that 2
2E Pi. (,, [F)( < 2R. (F) + 2/ 1n(2/0)
(40)
2n
Combining Equations
28
31 and 40 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
ET(I.F()) (f) B -
f.f
1
(f")
(41)
< Es(TF( (f) - i. (.( +
- [.m
(42)
Es(LE(F) iF(
(43)
Es 1.(( n - Taps (f)
1
n Σ
(
-1()
Ess
(44)
where the inequality arises because, by definition, 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( = LF For the final equality: the first term can be bounded from above (with confidence 8) using the bound for the expected value of (S)) derived in the proof of Theorem 4. and the second term can be bounded from above (with confidence 1 6) using the bound for the expected value of (PP) derived in the proof for Theorem 2 Combining these two high confidence bounds using the union bound yields the result.
14

---

Under review as a conference paper at ICLR 2023
C
PROOF OF THEOREM! 3
Proof. The result follows from Lemma and the following bound on the population variance,
Varg |argLLg(f) = Vargua
Lg. (F)
(45)
im n
1
E Bginee mn
Lg (f)
E
L (f)
(46)
11
11
i=1
n
1 (f)
(47)
- T. (f),
(48)
where the first inequality is from the positivity of the second term, and the second is because takes values in the range [0, 1].
D FURTHER ANALYSIS
D.1 COMPLETE RESULTS FOR DEPENDENCE ON MODEL COMPLEXITY
In Section 4.J we showed three of six datasets due to space constraint. The full set of resuts across six datasets are shown here in Figure
D.2 WORST-CASE ANALYSIS
We also consider the worst case scenario in Fig. where the worst out of all held out domains is reported, in contrast to the average case in Fig. From the results, we can see that: (i) worst case performance is also governed by model complexity, and (ii) the best complexity value for worst case metric very similar to the corresponding complexity for average case, as predicted in Section 3.5
D.3 ANALYZING DOMAINBED METHODS
In Section 4.2 analyzed the performance and complexity of ERM in DomainBed as function of the a representative hyper-parameter - the number of training iterations. Here we analyze the performance and complexity of several published neural DG methods implemented in DomainBed, run repeatedly with random syper-parameters can lead the same model have different complexity and different accuracy. (ii) While the decay with respect to overfitting is less pronounced here than for linear models in Fig. D. there is a slow decay past the peak complexity, which around in each dataset. The reason for the less pronounced decay with higher complexity may be that our measure is upper bound on complexity, with effective complexity likely being lower. Ongoing developments in tighter Rademacher complexity bounds may reveal clearer structure in future. Overall these results provide possible explanation for the influences complexity and hence generalisation via Thm 2 and possible explanation for differing performance state of the art methods - if each method provides different kind of explicit or implicit regularisation, then they could each find different empirical risk and complexity tradeoff.
From the plot in Figure we we can see that: (i) different
sensitivity highlighted in (20) hyper-parameter parameter choice
How Do DG Models Control Complexity? By different modifications to standard ERM, DG models explicitly or implicitly modify the bias and variance the function class to be learned. (20) highlight neural models as being dependent learning rate, batch size, dropout rate, and weight decay; with other factors being choice of optimiser and weight initialiser, etc. 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 implicitly affect complexity, but are hard to explicitly link to it. Consistency based methods like IRM and VRex penalise loss variance on the training data, which also tends to reduce the generalisation gap in the single task case (27), and may have links to the worst-case analysis in Section 3.4 that depends
15

---

Under review as a conference paper at ICLR 2023
0.3
0.50
0.5
0.6-
0.5
0.7
0.70
Acress coma (2ple)
Acrosa-doman idna vibal
Acrssa-deman dins viat
0.4
Wilte-damaln (prdi
0.6
White domal (din vi18)
0.65
W Windoan forn visal
509
P Conneneee wng
Across donais varas Witti-comuh an Offictume
Adozi-daman vesus W W.nndamann Snho
As doma vesus Wit Tunamoogn
100
0.3
Tea scruncy
0.7-
0.3
Tee
0.7
0.6
WhNi-dmmth
G=2"
Across-domane in venuus Withn-domaan on RotatscMMMST
Acresa-domann versus W ton-mmma on PACS
wwws--domaan-ooo veraua Withi-domain en WLCS
0.75
0.7
0.76
0.7-
0.5
0.65
0.60
0.5
Acroos-domain [pae]
03:
Across-domain (in
0.55
Across-domah oiins (
Wirlndomain (Nlr0)
02
slbe)
0.50
Withndommin
Ar Acrone-comm versus W mndoma on Officel bm
Acroce-omaain verus co-ti- on SVRO
Acroee-oorain veroue Withnddrrrann on Bersinooghite
0.5
0.7
044
0.3
0.3
Acros-damah +838)
n-smman
0.4-
Acroco domai (chn
1b41
0.2
0.1
Figure 4: Linear SVM (Top two rows) and Random Forest (Bottom two rows) performance on DomainBed benchmark datasets. Optimal tuning for performance on novel target domains (red) always requires stronger regularisation (lower C or D) than for performance on seen domains (blue).
upon the population variance. The specific setting of all the corresponding hyperparameters (e.g., regulariser strength, dropout rates) influence final model complexity, which influences performance.
E DETAILED RESULTS
Detailed results each DG benchmark In Tab. I we reported results of our linear model competitors on DomainBed summarised over choice of held out domain. In Tabs. 2 7 detailed results of accuracy and choice of C' paramater for each held out domain. we report the
Cross Validation
15
30
45
60
75
Ave.
Raw pixel
Ace
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
Ace
0.582
0.774
0.788
0.783
0.765
0.579
0.712 (0.093)
Instance Wise
1024.0
$12.0
1024.0
1024.0
1024.0
1024.
Table 2: Accuracy and selected 'C' on Rotated-MNIST using LVn
16

---

Under review as a conference paper at ICLR 2023
Acmoo-damain PeTaledHeV.ST
Acrosodematn PACS
Acrosedomath on Vids
0.45
0.55
0.41
0.45
0.43
0:63
0.40
0.02
THe
0.40
0.38
0.00
0.2-
Acrosadomann odino
0.59
Acroes-domain (d
0.36
C=2
C=2*
C+2
Acress cons-commhhoooo Offictfmme
Adras-dmmain Tamanogiils
0.1
0.400
0.455
0.400
0.35
0.350
Arroes-oomann
O+2
Cm2
Armoedoman RetaneNNIIST
Acrosodematt
Acrosodomaat ViCs
0.8
0.7-
7.0.0
0.55
0.15
0.4
0.10
0.45
03
Acriss doma Armss--dmmn Qliss
0.02
Acress Somain (ibs
Across domam (n Vibsl
Arrosodomaal Offichiome
OHRO
Arross de mish on Temineagrits
0.27
0.32
0.05
0.03
ACTISS Jemain Man (8))
Access Jumain (in vibs)
Across Jomain (d vibsi
Diy
Figure 5: Worst case linear SVM (Top: Row 1-2) and Random Forest (Bottom: Row 3-4) performance on DomainBed benchmark.
Cross Validation
A
C
DINO VTT-B8
Domain Wise
Acc
0.877
0.676
0.971
0.446
0.743 (0.201)
0.25
0.125
0.25
0.125
Instance Wise
Acc
0.866
0.620
0.891
0.445
0.706 (0.184)
4.0
8.0
8.0
2.0
ResNet.
Domain
Acc
0.74
0.532
0.975
0.477
0.681 (0.196)
8.00
8.00
32.00
8.00
Instance Wise
0.550
0.969
0.669 (0.193)
256.00
128.00
256.00
64.00
Table 3: Accuracy and selected 'C' on PACS, using LinearSVC.
17

---

Under review as a conference paper at ICLR 2023
OffecHoone
14
CHRAAL ERM IRM
Acciney
0.5
Atcura
Accteay
0.0
0.4
0.4
MMD
GrozpD00
0.2
6.6
1.5
Comploxiy
Cumplenity
Complexit
Figure 6: Leave-one-domain out cross-validation performance of neural networks as a function of their measured model complexity after training on DomainBed (DB). The overall results consistent with a standard bias-variance trade-off (cf. Fig foor linear models), with peak performance in the middle of the complexity range. Various neural DG algorithms evaluated by DomainBed (Each method is trained with five different random hyperparameters). Horizontal error bars correspond to the standard deviation of the model complexity measured for each cross-vaas validation iteration.
Cross Validation
C
L
V
Ave.
DINO VTT-B8
Acc
0.972
0.648
0.787
0.811
0.804 (0.115)
Domain Wise
0.5
0.125
0.5
0.648
0.785
0.805 (0.117)
Instance Wise
C
0.25
0.5
0.5
0.5
ResNet-50
Domain Wise
Acc
0.986
0.598
0,730
0.755
0.767 (0.140)
C
16.00
8.00
8.00
1.00
Instance Wise
Acc C
.986
0.598
0.730
0.792
0.776 (0.140)
16.00
8.00
8.00
8.00
Table 4: Accuracy and selected 'C' VLCS, using LinearS
Cross Validation
C
R
Ave.
DINO VIT-
Domain Wise
Acc
0.748
0,512
0.832
0.850
0.736 (0.
C
1.0
1.0
0.5
Acc
0.730
0,514
0.833
0,846
0.731 (0.133)
Instance
C
4.0
2.0
2.0
4.0
ResNet-50
Acc
0.681
0,521
0.784
0.813
0.700 (0.114)
Domain Wise
C
8.00
8.00
8.00
Instance Wise
Acc
0.652
0.513
0.794
0.803
0.691 (0.119)
C
64.00
32,00
16.00
64.0
Table 5: Accuracy and selected 'C' on OfficeHome, using LVC.
Closs Validation
acloss
hilux
13
lexus
tesla
tiguan
racson
x
Ave.
DINO
Donuin Wise
Acc
0.979
0.980
0.967
0.997
0.959
0.981
0.942
0.986
0.975
0.954
(0.016)
C
1.0
1.0
1.0
1.0
2.0
1.0
2.0
1.0
1.0
2.0
Acc
128.0
64.0
128.0
64.0
256
128.0
256.0
128.0
128.0
128.0
R5sNer-50
Acc
0.963
0.941
0.961
0.926
0.942
0.940
0.947
0.951
0.133
0.847
0.933 (0.032)
64.00
128.00
32.00
Instance Wise
Acc
0.968
0.928
0.959
0.877
0.954
0.931
0.954
0.958
0.827
0.913
0.927 (0.042)
C
1024.00
1024.00
1024.00
1024,00
1024.00
1024,00
1024.00
1024.00
1024.00
1024.00
Table 6: Accuracy and selected 'C" on SVIRO, using LVC
18

---

Under review as a conference paper at ICLR 2023
Cross Validation
L100
L338
L43
L46
Ave.
DINO VIT-88
Domain Wise
Acc
0.444
0.457
0,516
0.399
0.454 (0:041)
0.25
1.0
2.0
Instance Wise
Acc
0.472
0.391
0.366
0.324
0.388 (0.054)
256.0
128.0
256.0
256.0
ResNet-50
Domain Wise
Acc
0,305
0.145
0.338
0.344
0,283 (0.08))
32.00
Instance Wise
Aoc
0.211 1024.00
0.336
0.271
0.257
0.269 (0.045)
1024.00
1024.00
1024.00
Table 7: Accuracy and selected 'C' on Terra Incognita, using LinearSVC.
19


Reviews:
[{"review_id": "jODcZncP9i1", "reviewer": "Reviewer_EU2D", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "summary_of_the_paper": "The paper studies domain generalization where the domains are drawn from a prior and applies standard rademacher bounds.", "summary_of_the_review": "See above", "strength_and_weaknesses": "Unfortunately, I think the contribution of this work is extremely limited. First of all, the work situates itself by claiming that previous works make either structural assumptions, or \"restrict to specific classes, such as kernel machines\", and then purports to do something different. This is incorrect.\n\nIn domain generalization, there are really only two options for hoping to be able to generalize. We could (a) assume the domains are drawn from a prior (as this work and several previous works do [1, 2]), or we could (b) make a structural assumption. This work presents option (b) as if it is undesirable, when it is one of only two options and is in fact the more popular one---and the one that most people mean when they use the term \"domain generalization\" in a modern context. The reason option (b) is more popular is because option (a) is somewhat trivial: just use ERM, with sufficient regularization. This was shown by [1, 2] a *long* time ago to be sufficient (and it is unsurprising), and so the fact that ERM does not work in practice implies that assuming a prior is still missing something important and that option (b) is a possible way to address this.\n\nNow, *conditioning on the use of option (b)*, this work doesn't really make any contributions. [1, 2] already study the setting of a prior over domains. They don't make a \"kernel machine modeling assumption\", they derive bounds on the OOD risk which uses RKHS norms. What does this work do instead? They apply standard Rademacher bounds to the prior over environments. Obviously, the risk of a function class $\\mathcal{F}$ converges uniformly to its expected risk with respect to the distribution of environments, so by assuming this prior we can just plug in existing Rademacher bounds, which is exactly what this work does. The \"assuming a prior\" idea (i.e., option (b)) is not new, and there is no mathematical contribution. Replacing the RKHS norm with the Rademacher complexity of neural networks is not an improvement, it's just another option.\n\nI don't think the experiments really show much either, but even if they did, 3/4 of the paper is devoted to what amounts to plugging existing bounds into a known setting. Unfortunately I don't think this is a matter of making changes to the draft---the premise of the paper as it currently stands just doesn't really say anything new.\n\n[1] Generalizing from Several Related Classification Tasks to a New Unlabeled Sample. Blanchard et al. 2011\n\n[2] Domain Generalization by Marginal Transfer Learning. Blanchard et al. 2017", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cHckSYCcSp", "reviewer": "Reviewer_rAHY", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "", "summary_of_the_paper": "This paper gives a few generalization bounds in the domain generalization setting. They assume there are n domains that are i.i.d. sampled from some “distribution of domains”, and for each domain there are m i.i.d. sampled datapoints. In this case, they provide a generalization bound where the Rademacher complexity depends on both n and m. Furthermore, they provide a high probability bound for the worst domain in the “distribution of domains” using standard Chebyshev’s inequality. They justify the practical relevance of their method with some experiments (with simple models like svm and random forest).  ", "summary_of_the_review": "It think the paper is not really considering OOD problems as the authors claim. Also, the technical novelty is very limited as far as I can tell. Thus, I would say this is below the bar of acceptance. ", "strength_and_weaknesses": "Strength\n- As far as I know, the problem of considering a distribution of i.i.d. domains is novel.\n- The paper is clearly written and every theorem is followed by detailed discussions.\n- The experiments, despite only using simple models, are very extensive. Many datasets are used, and experiment details are clearly stated.\n\nWeakness\n- My main criticism is that, to some extent, the paper is cheating in the sense that the testing data is not really o.o.d, because the domains are assumed to be sampled i.i.d. from the “distribution of domains”. My feeling is that the authors are simply rephrasing an in-domain generalization problem and making it look like an out-of-domain generalization problem. In fact, suppose m=1, then the problem recovers exactly the same problem of in-domain generalization. \n- Also, from the bound it looks like n (number of observed domains) does need to be very large to make the bound non-vacuous, which is not practical at all. In most domain generalization problems, we only have one source domain. \n- There’s very limited technical novelty. The proof is simply reusing the standard Rademacher complexity bound but with simple adjustment to the two levels of i.i.d. samples (sampling of the domain and sampling of data within a domain).   \n- The experiments are all using simple models like linear models or random forest. It’s unclear how these results are relevant in the deep learning era.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "_cb0UnpVNR", "reviewer": "Reviewer_ss4Y", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "", "summary_of_the_paper": "This paper studies the problem of domain generalization where we are given data from multiple domains, and a model has to work well on an unseen domain. The paper theoretically bounds the performance on the unseen domain via a uniform convergence bound involving the Rademacher complexity of the classifier. I see this result as analagous to standard generalization bound, but with IID samples replaced by IID environments. This bound tells us that smaller capacity models are more likely to generalize better to unseen domains than higher capacity models. The paper then verifies this experimentally on linear networks over pretrained features, or two-layer networks, that model complexity (in addition to model fit) plays an important role in determining performance on new domains, in a manner that mirrors the bias-variance tradeoff. ", "summary_of_the_review": "The paper studies an important question of domain generalization, but ends up studying an uninteresting regime (with no assumptions on the data generating process) leading to pretty unsurprising conclusions with no clear actionable takeaway. It would be very valuable if the authors had some discussion on how these results (both theoretical and empirical) inform us on what to do, and how they would help advance the state-of-the-art in domain generalization. In particular, how does the notion of complexity in domain generalization differ from standard supervised learning? If we haven't solved the latter, what hopes are for the former?", "strength_and_weaknesses": "Strengths: \n(a) The paper studies an important problem of domain generalization and tries to characterize the effect of hyperparameters on the final performance on an unseen domain \n(b) The paper is generally well written and easy to follow\n(c) The experimental conclusions are well-substantiated \n\nWeaknesses:\nMy main concern with the paper is regarding its foreseeable impact: the theoretical contributions seem like straightforward generalization of the standard uniform convergence analysis for generalization in distribution and there are new tools or insights. It would help if the authors clarify the main theoretical contributions and novelty/significance. \n\nFrom a practical perspective, it seems almost obvious that lower capacity would generalize better and that one can try to do cross validation using a held-out domain. The main challenges in practice are: we do not know a good complexity measure of deep networks and this is a big open problem in standard supervised learning. Could the authors please clarify how their notions of complexity are different from those in standard supervised learning?\n\nThe experiments provided on linear networks, shallow networks and RBFs make  but how do they compare to the state-of-the-art results with deeper models? If simpler models with appropriate regularization beat claimed state-of-the-art methods with larger models, then this result is interesting. Otherwise, I wonder what takeaways could we use for further development (it seems obvious to me that \"regularization\" will help, but what's the right regularization is the question which this paper fails to answer). \n\nI agree with the discussion on page 5 that you probably need more assumptions on the different domains in order to get a stronger result, but I think that's the actual interesting regime. Otherwise domain generalization just reduces to standard generalization problem. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "CQPRuXgMhS", "reviewer": "Reviewer_ECRP", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "", "summary_of_the_paper": "The author provides domain generalization bound from Rademacher Complexity aspect and shows there’s a tradeoff between empirical risk and model complexity in domain generalization. The author provides experimental results to support their theoretical findings.", "summary_of_the_review": "Overall I’m not convinced by the findings of the paper. The technical proof idea is not novel, and the contribution is not significant. The writing of some parts of the paper I believe needs to be improved.", "strength_and_weaknesses": "This paper has clearly stated its objective, the approach and the corresponding evaluations. Most part of the paper is easy to follow.\n\n1. I’m worried the contribution is not significant. The technical analysis in terms of Rademacher complexity is rather standard.\n2. Some discussion needs to be clarified. For example, in the discussion of corollary 1, I do not completely follow why ``any future DG method that claims to be better than ERM should demonstrate a faster convergence rate than this — at least by an improved constant factor’’. Since you are not providing a lower bound on the excess expected risk, and your upper bound is also in Big-O notation,  what does it mean by an improved constant factor? \n3. I believe the worst-case scenario is more interesting for domain generalization even requires mild assumption. Yet the bound provided here (Lemma 1 and Theorem 3) gives us vacuous bounds that do not have any insights.\n4. I’m suspicious about the tradeoff proposed by the author. The author makes that assumption based on theorem 2, but it’s unclear whether the bound is tight or not, and the Rademacher complexity bound may be vacuous in reality. The author makes an analogy with the standard overfitting-underfitting trade-off, yet recent experiments observe the double descent phenomena. Thus I’m wondering whether the same double descent phenomena happens in the domain generalization scenario, and how overparameterized model performs in the domain generalization scenario.", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject