Practicality of generalization guarantees for unsupervised domain adaptation with neural networks
Authors: Adam Breitholtz
Fredrik Daniel Johansson
Venue: Accepted by TMLR ()

Abstract: Understanding generalization is crucial to confidently engineer and deploy machine learning models, especially when deployment implies a shift in the data domain. 
For such domain adaptation problems, we seek generalization bounds which are tractably computable and tight. If these desiderata can be reached, the bounds can serve as guarantees for adequate performance in deployment.
However, in applications where deep neural networks are the models of choice, deriving results which fulfill these remains an unresolved challenge; most existing bounds are either vacuous or has non-estimable terms, even in favorable conditions.
In this work, we evaluate existing bounds from the literature with potential to satisfy our desiderata on domain adaptation image classification tasks, where deep neural networks are preferred. We find that all bounds are vacuous and that sample generalization terms account for much of the observed looseness, especially when these terms interact with measures of domain shift. To overcome this and arrive at the tightest possible results, we combine each bound with recent data-dependent PAC-Bayes analysis, greatly improving the guarantees. We find that, when domain overlap can be assumed, a simple importance weighting extension of previous work provides the tightest estimable bound. Finally, we study which terms dominate the bounds and identify possible directions for further improvement. 

Published in Transactions on Machine Learning Research (10/2022)
Practicality of generalization guarantees for unsupervised domain adaptation with neural networks
Adam Breitholtz
adambre @ccalmerseeeceeeee..ee
Department of Computer Science
Chalmers University of Technology
Fredrik D. Johansson
Department Computer Science
Chalmers University of Technology
Reviewed on OpenReview: openreveee. net/ forum? id= Wss
net/forum?
Abstract
Understanding generalization crucial to confidently engineer and deploy machine learning models, especially when deployment implies a shift in the data domain. For such domain adaptation problems, we seek generalization bounds which are tractably computable and tight. If these desiderata can be reached, the bounds can serve as guarantees for adequate performance in deployment. However, in applications where deep neural networks are the models of choice, deriving results which fulfill these remains an unresolved challenge; most existing bounds are either vacuous or has non-ostimable terms, even in favorable conditions. In this work, we evaluate existing bounds from the literalur ure with potential to satisfy our desiderata on domain adaptation image classification tasks, where deep neural networks are preferred. We find that all bounds are vacuous and that sample generalization terms account for much of the observed looseness, especially when these terms interact with measures of domain shift. To overcome this and arrive at the tightest possible results, we combine each bound with recent data-dependent PAC-Bayes analysis, greatly improving the guarantees. We find that, when domain overlap can be assumed, simple importance weighting extension of previous work provides the lightest estimable bound. Finally, we study which terms dominate the bounds and identify possible directions for further improvement.
1 Introduction
Successful deployment of machine learning systems relies generalization to inputs seen in training. In many cases, training and in-deployment inputs differ systematically; these domain adaptation (DA) problems. An example of setting where these problems arise is healthcare. Tearning a classifier from data from one hospital and applying to samples from another is an example of tasks that machine learning often fail at (AlBadawy et al.] 2018 Perone et al. 2019 Castro et al. 2020). In high-stakes settings like healthcare, guarantees on model performance would be required before meaningful deployment is accepted. Modern machine learning models, especially neural networks, perform well on diverse and challenging tasks which conventional models have had only modest success. However, due the high flexibility and opaque nature of neural networks, it is often hard to quantify how well can expect them to perform in practice.
Performance guarantees for machine learning models are typically expressed as generalization bounds. Bounds for unsupervised domain adaptation (UDA), where no labels are available from the larget domain, have been explored in a litany papers using both the PAC [Ben-Davie et al. 2007 Mansour et al. 2009) and PAC-Bayes (Germain al. 2020) frameworks; see Redko et al. (2020) for an extensive survey. Despite great interest in this problem, very few works actually compute or report the value of the proposed bounds. Instead, the results used only to guide optimization or algorithm development. Moreover, the bounds

---

Published in Transactions on Machine Learning Research (10/2022)
presented often contain terms which are non-estimable without labeled data from the target domain even under lavourable conditions (Johansson et al. 2019 Zhao et al. 2019).
For deployment in sensitive settings we wish to find bounds which are: a) Amenable to calculation; they do not contain non-estimable terms and are tractable to compute. b) Tight; they are close to the error in deployment (or least non-vacuous). How do existing bounds fare in solving this problem? As we will see, for realistic problems under favorable conditions, most, if not all, bounds in the literature struggle to satisfy one or both of these goals to varying degrees.
In this work, we examine the practical usefulness of current UDA bounds as performance guarantees in the context of learning with neural networks. Examining the literature with respect to our desiderata, we identify bounds which show promise in being estimable and tractably computable (Section 2.1). We find that terms related to sample generalization dominate existing bounds for neural networks, prohibiting tight guarantees. To remedy this, we apply PAC-Bayes analysis (McAllester) 1999) with data-dependent priors (Dziugaite & Roy 2019) in four diverse bounds (Sections 2.3 2.4). Two are existing PAC-Bayes bounds from the UDA literature and two are PAC-Bayes adaptations of bounds based on importance weighting (IW) and integral probability metrics (IPM). We evaluate the bounds empirically under favorable conditions in two tasks which fulfill the covariate shift and domain overlap assumptions; one task concerns digit image classification and the second X-ray classification (Section 3). Our results show that all four bounds are vacuous on both tasks without data-dependent priors, but some can be made tight with them (Section 4). Furthermore, we find that the simple extension of applying importance weights to previous work outperforms the best fully observable bound from the literature in tightness. This result highlights amplification of bound looseness due interactions between domain adaptation and sample generalization terms. We conclude by offering insights into achieving the tightest bounds possible given the current state of the literature (Section 5).
2 Background
In this section, we introduce the unsupervised domain adaptation (UDA) problem and give survey of existing generalization bounds through the lens of practicality: do the bounds contain non-estimable terms and are they tractably computable? We go on to select a handful of promising bounds and combine them with data-dependent PAC-Bayes analysis to arrive at the tightest guarantces available.
We study UDA for binary classification, in the context of an input space X' C Rdd and a label space y = 11, While our arguments are general, we use as rumning example the case where X' a set of black-and- white images. Let S and T, where S * T, be two distributions, or domains, over the product space X' x V, called the source domain and target domain respectively. The source domain is observed through a labeled sample S = {z1, 1 ~ (S)" and the target domain through a sample Sy = =x+) ~ (Ta)" which lacks labels, where T, is the marginal distribution on X' under T. Throughout, (D) denotes the distribution of a sample of N datapoints drawn i.dd. from the domain D.
The UDA problem to learn hypotheses h from a hypothesis class H. by training on S and Sy such that the hypotheses perform well on unseen data drawn from T. In the Bayesian setting, we learn posterior distributions p over H from which sampled hypotheses perform well on average. We measure performance using the expected target risk Ri of a single hypothesis h or posterior p.
(h) = E (((h(z),)) v)l or
E RT (h) heep
(x.y)~
Risk for single hypothesis
Gibbs risk of posterior P
for a loss function : 3 x y + R_. In this work, we study the zero-one loss, (ly.3') = [ * y'I. The
Gibbs risk is used in the PAC-Bayes guarantees (Shawe-Tavee & Williamson 1997 McAllester 1998). a generalization of the PAC framework (Valiant 1984 Vapnik 1998).
When learning from samples, the empirical risk An can be used as an observable measure of performance,
(b) = m Σ ((h(x)).)))
(2)
2

---

Published in Transactions on Machine Learning Research (10/2022)
for sample {(z,, Uz) 12 (D)", with the empirical risk of the Gibbs classifier defined analogously. However, since no labeled sample from T is available, the risk of interest is not directly observable. Hence, the most common way to approximate this quantity is to derive an upper bound on the target risk. We refer to these as UDA bounds. Crucially, any practical performance guarantee must be made using only observed data and assumplions on how and T relate. Throughout, we make the following common assumptions.
Assumption (Covariate shift & overlap). The source domain S and larget domain T satisfy for all x,y
Covariate shift:
Ty X = x) S X =x and To(X = x) + Sx =x) T = 2) = S2(X = =)
Overlap:
These are strong assumptions and covariate shift cannot be verified statistically. They are not required by every bound in the literature but together they are sufficient to guarantee identification and consistent estimation of the target risk (Shimodaira 2000). More importantly, the generalization guarantees we study more closely are not fully observable without them unless target. labels are available. Finally, this setting is among the most simple and favorable ones for UDA which should make for an interesting benchmark if existing bounds are vacuous also here, significant challenges remain.
2.1 Overview of existing UDA bounds
Most existing UDA bounds on the larget risk share a common structure due to their derivation. The ly typical process starts by bounding the expected target risk using the expected source risk and measures of domain shift. Thereafter, terms are added which bound the sample generalization error, the difference between the expected source risk and its empirical estimate. The results can be summarized conceptually, with and arguments variously defined, expressions on the form
RT S / [EEmiiriaal source risk, Measures domain shift, Sample generalization error)
There are two main forms taken by this function; one which sample generalization terms are related domain shift terms through addition and one where they are multiplied. We call these additive and multiplicative bounds respectively. One example is the classical result due to Ben-David et al. (2007) which uses the so-called A-distance to bound the target risk of h E H with probability 2 0,
4(dlog 2am log +
(T( s Rh( +V
dn T) +
(3)
m
Emp. risk
Sample goneralization
Domain shift
where d is the VC dimension of the H. is the sum of the errors on both domains of the best performing and (S, T) supAe((==Me)==))eee)) Prs[AA]-Pr[AA] is the
classifier ht = arg (R) A-distance for the characteristic sets of hypotheses in H.
Three challenges limits the practicality of this bound: i) À is not directly estimable without target labels and must be assumed small for an informative bound. This a pattern in UDA theory which illustrates a fundamental link between estimability and assumption. ii) The VC dimension can easily lead a vacuous result for modern neural networks. For example, the VC dimension of piecewise polynomial networks is 2(pl log F) where is the number of parameters and I is the number of layers (Bartlett et al. 2019). iii) The A-distance can be tractably computed only for restricted hypothesis classes. These issues not unique the bound above, they are exhibited to varying degrees by any UDA bound.
In response to concerns for icactical generalization bounds in deep learning, Valle-Pérez & Louis 2020 put forth seven desiderata for predictive bounds. While these are of interest also for UDA, we concern ourselves primarily with the fifth (non-vacuity of the bound) and sixth (efficient computability) desiderata as they are of paramount importance to achieving practically useful guarantees. In this work, study UDA bounds with emphasis on how each term influences the following properties when learning with deep neural networks.
1. Tightness. Is the term a poor approximation? Is it likely to lead to loose bound?
3

---

Published in Transactions on Machine Learning Research (10/2022)
Table 1: Overview of existing UDA bounds with respect to a) measures of domain divergence, b) whether domain and sample generalization terms add or multiply, e) non-estimable terms, d) whether the bounds were computed empirically, e) computational tractability. The highlighted rows represent a selection of bounds which are possible estimate under the assumptions we make and which hold promise in fulfilling other desiderata. X denotes that under the assumptions made in this work we do not have non-estimable terms.
Non-est. terms
Evaluated bound
Paper/referenu
Divergence A-distance
Add/Mult
Tractable
Ben-David et al. (2007)
Add
X
Blitzer et al. (2088)
H
Add
X
BeviDavid et al. (2010)
HAH
Add
X
Morvant et al.
2012
H&H
Add
X
X
Mansour et al.
2009)
Discrepancy dist.
Add
X
AANKK
Redko al.
2019
Discrepancy dist.
Add
Kuroki et a.l
2019
S-discrepancy
Add
C Cortes & Mohri
(2014)
Gen. discrepancy
Add
Cortes et al.
2015
Gen. discrepancy
Add
Zhang et al.
2012
IPM
Add
Redko (2015)
IPM, MMD
Add
Long 20015
MMD
Add
Redko al.
2017
IPM
Add
J Johansson el. al.
(00
IPM
Add
Zhang et a..
2019
Margin disparity
Add
X
Dhouib ct a..
(2020)
Wasserstein
Add
J
Shen et al.
2018
Wasserstein
Add
AXXAX
Courty et al. 201 7b
Wasserstein
Add
Germain et a..
2013
Domain disagreement
Add
Zhang al.
2020
Localized discrepancy
Add
Cortes al.
2019
Localized discrepancy
Add
Acuna ct al.
2021
f-divergences
Add
Germain et al.
(2016)
8-divergence
Mult
X
Cortes et al. (2010)
Rényi
Mult
X
X
Dhouib Redko (2018)
L ,²
Mult
X
Estimability. Is the term something which we can estimate from observed data?
3. Computability. Can we tractably compute it for real-world data sets and hypothesis classes?
Next, we give a short summary of existing UDA bounds, with the excellent survey by Redko et al. (2019) as starting point, while evaluating whether they contain non-estimable terms, if the bound was computed in the paper and if the bound computationally tractable for neural networks. We have listed considered bounds in Table
We will now reason about the bounds' potential to reach our stated desiderata, starting with tractability. We begin by noting that several divergence measures (c.g., A-distance, H A-ddittance, Discrepancy distance) are defined as suprema over the hypothesis class H. Typically, these are intractable to compute for neural nets due to the richness the class, and approximations would yield lower bounds rather than upper bounds. Several works fail yicld practically computable bounds for neural networks for this reason (Ben-David
et al.
2007
Blitzer al.] 2008 Ben-David al. 2010 Morvant et al. 2012 Mansour al. 2009 Redko
al.
2019 Cortes & Mohri, 2014: Cortes et. al.
2015). There also
works which deal with
called localized discrepancy which depends finding subset of promising classifiers and bounding their
performance instead. (Zhang et al.) 2020 Cortes et al.
2019) However, this subset is not easy to find in
general and as such we view these approaches as int.ractable also.
this we mean the whole bound. Some of the works listed have computed or several parts of their bound. However, the computation generally done for simpler model classes than neural networks.
4

---

Published in Transactions on Machine Learning Research (10/2022)
Contimuing with estimability, we may remove from consideration also those whose non-estimable term cannot be dealt with without assuming that they are small -n an untestable assumption which does not. follow from overlap and covariate shift. This immediately disqualifies a large swathe of bounds which all include the joint error of the optimal hypothesis on both domains, or some version thereof, a very common non-cstimable
term DA bounds Kurooi et al. 2019 Redko 2015 Long et al. 2015 Redko et al., 2017 Johansson el al.
2019; Zhang et al. 2019 Dhouib al., 2020 Shen et al. 2018 Courty et al. 2017b Germain et al. 2013
Dhouib & Redko 2018; Acuna al. 2021p. In principle, we might be able to approximate this quantity optimization
under overlap, e.g. by using importance sampling. However, this would entail solving
problem to find hypothesis which has a low joint error (see discussion after equation If we instead wish to upper bound the term, we must solve an equivalent problem to the one we are trying to solve in the first
place.
Three bounds remain: Zhang et al. 2012) use inte- gral probability metrics (IPM) between source and larget domains to account. for covariate shift. in their bound, which are tractable to compute under as- sumptions on the hypothesis class; Cortes et al. (2010) use importance weights (IW) and Renyi di- vergences which are well-defined and easily com- puted under overlap; Germain et al. (2016) use a re- lated metric based on the norm of the density ratio between domains with similar properties. Respec- tivcly, the first two rosults bound sample generaliza- tion error using the uniform entropy number and the covering number. These measures are intractable to compute for neural networks, and while they may be upper bounded by the VC dimension (Wainwright, 2019), this typically large enough to yield unin- formative guarantees (Zhang al., 2021). In con- trast, Germain al. (2016) use PAC-Bayer analy- sis which we can apply to neural networks by speci- fying prior and posterior distributions over network weights. Using Gaussian distributions for both pri- ors and posteriors, the PAC-Bayes bound can be readily computed. Thus, to enable closer comparison and tractable computation,
5
Worse than random
Uninformative region
Target error
Minimum of bound
Error
3-
2
0
Add.
Mult.
MMD
IW
Figure 1: Best. bounds achieved without data- dependent priors on the MNIST MNIST/MMISTTNN MMNISTMMMM task using LcNet-5 as well as the target error for the same poste- rior hypothesis. Note that all the bounds are vacuous, ie. they above
the coming sections, we unify each bounds' dependence on sample generalization by adapting IW and IPM bounds to the PAC-Bayes framework. For completeness, we include an additional PAC-Bayes bound from the UDA literature, which has non-estimable term, namely Germain et al. (2013)
The selected bounds are given in Sections 2.3 2.4 Germain et al. (2066) will be referred to as the multi- plicative bound (Mult), Germain et al. (2013 as the additíve bound (Add), the adaptation of importance weighting to PAC-Bayes as IW; and the adaptation of IPM bounds as MMD. Unfortunately, also the re- sulting Bayes bounds are uninformative for even simple image classification UDA tasks; see Figure [ Consistent with our understanding of standard learning with neural networks, we find both classical PAC and PaC-Bayes bounds vacuous in the lasks most frequently used as empérical benchmarks in popers deriving UDA bounds. Next, detail how to make use of data-dependent priors to get the tightest possible bounds.
2.2 Tighter sample generalization guarantees using PAC-Bayes with data-dependent priors
PAC-Bayes theory studies generalization of a posterior distribution p over hypotheses in H, learned from data, in the context of prior distribution over hypotheses, æ. The generalization error in p may be bounded using the divergence between p and π seen in the following classical result due to McAllester.
Theorem (Adapted from Thm. McAllester 2013)). For a prior æ and posterior p on H, a bounded loss function f y - [0, 1] and any fired 7, (0, 1), we have w.p. at least 1 - over the draw of

---

Published in Transactions on Machine Learning Research (10/2022)
samples from D, with Qpll)) the Kullback-Lieble (KL) divergence between and 9,
RD(h) - E (h) + (KI(P](T) +ln()) 2y(1 - 7mm
hoep 7houp
The bound in Theorem 1 grows loose when prior и and posterior p diverge when the posterior is sensitive to the training data. When learning with neural networks, and p are typically taken to be distributions the weights of the network before and after training. However, the weights of trained deep neural network
will be far away from any uninformed prior after only a few epochs. For this reason, Dziugaite et al. (2021)
developed a methodology, based on work by Ambroladze et al.] (2007) and Herraadd- et al. (0012)
for learning data- mata-dependert neural network priors by a clever use of sample splitting, To ensure that the bound remains valid, any data which is used fit the prior must be independent of the data used to evaluate the bound. In this work, we learn π and p following Dziugaite et al. (2021), , as described below.
1. A fraction a E [0, 1) is chosen and the available training data, S, is split randomly into two parts, Sa and \ S. of size am and (1 - a)m, respectively.
2. A neural network is randomly initialized and trained using stochastic gradient descent on Sa for one epoch. From this we get the weights, W..
3. The same network is trained, starting from wa, on all of S until stopping condition satisfied. In this work, we terminate training after epochs. We save the weights, Wpp
4. From Wa and up we create our prior and posterior from Normal distributions centered on the learned weights, π = N(w,,, ol) and p = NNw,, al) respectively. a is a hyperparameter governing the specificity (variance) of the prior which may be chosen when evaluating.
5. Finally, we use the learned prior and posterior to evaluate the bounds on S Sa.
2.3 PAC-Bayes bounds from the domain adaptation literature
Both the additive and multiplicative PAC-Bayes UDA bounds described Scction 2.1 are defined in Germain et al. 2020)) and make use of a decomposition of the zero-one risk into the expected joint error
ep(p)
E
E (((()).))(((((()).)))
h. 2.0-D
which measures how often two classifiers drawn from P make the same errors, and the expected disagreement
do, (p)
E E ((((),,((a)) (x)),
h.N/pxpp D~D.
which measures how often two classifier disagree on the labeling of the same point. Empirical variants (p)) and di, (p) replace expectations with sample averages analogous to equation 2
In the bound of Germain et al. 2016)) the sample generalization component (KL-divergence between prior and posterior) is multiplied with domain shift component (supremum density ratio).
Theorem 2 (Multiplicative bound, Germain et al. (2016)). For any real numbers a, b.b > 0 and 5 E (0, 1), il holds, under Assumption 7 with probability at least 1 over labeled source samples S ~ (S) and unlabeled a target samples Tz ~ (Ta)", with constants a' = -- V = To for every posterior p on H that
b
E (h) < a' dr. + +1 ( + (T(()) heup
(2DkL(olIT) + in 2 2) + +
na
with Boo (T]())
sup xESupp(S.)
(z(2)/S and ITI
E (2.0)
(I) & supp(S)]] supneh (Tys(h).
TTerms 9g based on the gith moment of the density ratio q < are considered in Germain 2020 but here.
6

---

Published in Transactions on Machine Learning Research (10/2022)
The bound is simplified slightly in our setting due to Assumption 1 as 77,s will be 0. By Bayes rule, 3x0 can be computed as the maximum ratio between conditional probabilities of an input being sampled from T or S. The second result due to Germain et al. is additive in its interaction between domain and sample gencralization terms.
Theorem (Additive bound, Germain et al. (2013)). For any real numbers w. > and & E (0, 1), with probabilily al least 1 - over labeled source samples (S)m and unlabeled largel samples Ta mm; for every posterior p H. it holds with constants w'
and > = 2y
that
E RT(h)) S E w' wh) + +7' (S, W )) (KI(T) + log houp
3 8
- 2(( -1,, 1),
+ +
hwpp
where (S, = ldr, ds.l the empirical domain disagreement, X, - es(p))-
Next will combine the main techniques used to account for domain shift in Cortes et al. (2010) and Zhang producing two corollaries for the UDA setting.
ct al. 2012) with the PAC-Bayes analysis of Theorem [
2.4
Adapting the classical PAC-Bayes bound to unsupervised domain adaptation
First, we adapt the bound in Theorem 1 to UDA by incorporating importance weighting (Shimodaira] 2000; Cortes al. 2010). We define a weighted loss e" (h(z), y) = w(z))(((x))))) y) where w(x) zero-one loss. The risk of a hypothesis using this loss is denoted by R
T and is the S(x)
Corollary 1. (IW bound) Consider the conditions in Theorem 7 and let Brx supamx w(x). We have, for any choice of 7, (0, and any pick of prior and posterior p H.
1 E. RT (T) hrup
(pl(T + In(
E Rgg(h) + Box 2y(1 7)m "houp
Proof. Since Theorem 1 holds for loss functions mapping onto [0, 1], divide the weighted loss e by the maximum weight, B The argument then follows naturally when we apply Theorem witt the loss function
8
Wmax
((h(T))
E" (h(x))
S L + (Kl()) + In(
E <T
E
Boo
Boo
78.0
2x(1 - -7)m
The first equality holds due to Assumption and the definitions of w and e".
Now we contimue with applying an argument basod on integral probability motrics (IPM) drawn from Zhang let al.
2012) and similar works. IPMs, such as the kernel maximum mean discrepancy (MMD) (retton et al. 2012) and the Wasserstein distance have been used to give tractable and even differentiable bounds on target error in UDA guide algorithm development (Courty et al., 2017aa Long al. 2015). The kernel MMD is IPM, defined as follows, in terms of its square, given reproducing kernel kc X x X R
E (P,)2 X~PXX'P
-2
E X~P.Y~Q
E [XX,Y)] + Y~Q.Y''~
1k (Y,Y")).
Here, X and Y are random variables, and X' is an independent copy of X with the same distribution and Y' is an independent copy of Y. This measures a notion of discrepancy between the distributions P and Q based on their samples.
We combine the MMD with the bound from McAllester 2013 bound.
arrive at what we will call the MMD
Corollary 2. (MMD bound) Let (x( = B[)(M()), Y) X = x] be the expected pointwise loss at x E X and assume that, for any h E H, ln can be uniforrll bounded by function in reproducing- Hilbert L space with kernel k such that Va,a' d E xx:00 0 S k(æ, x') < K. Then, under Assumplion 1 with 7,6 ō E (0, 1) and : probability > 11-60 over labeled source samples S (S)m and unlabeled target samples Sy T
1 E. (T) < hrip
E Rs(h))+ 7hmu
(KI(P + log 2y(1 7)m
+ (ST + m
K 2 V log 4
1og
(4)

---

Published in Transactions on Machine Learning Research (10/2022)
where (S, T) is the biased empirical estimate of the macimun mean discrepancy between S and T computed from Sz and S22, see eq. (2) in Grelion et al. 2012).
Proof. By assumption, for any hypothesis MET H, RT(h) = Rs( + -) Es(((h(X), Y) & Rs(h) + sup ET, [X)) Es, (X)]]
IEC
The inequality holds because (s(e(h(2), Y) X = x] X (covariate shift) and the assumption that ln is uniformly bounded by a function in L. The RHS of the incquality is prociscly MMD₂ and the full result follows by lincarity of expectation (over p), since the MMD term is independent of h, and application of Theorem [ The right-most term in equation { follows from a finite-sample bound on MMD, Theorem 7 in Gretton et al. (2012). and a union bound w.r.t. 8.
((((((()) xx=xi x] due to Assumption 1
Representation learning. When no function family & satisfying the conditions of Corollary 2 is known, an additional unobservable error term must be added to the bound, to account for excess error. Bounds based on the MMD and other IPMs have been used heuristically in representation learning to find representations which minimize the induced distance between domains and achieve better domain adaptation (Long et al., 2015). However, even covariate shift holds in the input space, these are not guaranteod to hold in the learned representation. For this reason, we do not explore such approaches even though they might. hold some promise. An example of this is recent work by Wu et al. (2019) which provided some interesting ideas about assumptions which constrains the structure of the source and target distributions under a specific representation mapping. Exploring such ideas further is an interesting direction for future work.
3 Experimental setup
We describe the experimental setup briefly, leaving more details in Appendix A We examine the dynamics of the chosen bounds (Add, Mult, MMD, IW), which parts of the bounds dominate their value, the effect of varying the amount of data used to inform the prior and if the bounds have utility for early stopping indication or model selection. In addition to these we also want to answer if these bounds practically useful as guarantees, and not, what lacking and what future directions should be explored to reach our desiderata? Since the term Xo in Add (Theorem 3) depends on target labels, we give access these for purposes of analysis and illustration, keeping in mind that the bound is not fully estimable practice.
We perform experiments on two image classification tasks, described further below, using three different neural network archilectures. The architectures used are: modified version of LeNet-5 due to Zhou et al. (2019), fully connected network and version of ResNet50 (He et al. 2016). These specific architectures were picked as examples due to their varying parameter size and complexity. The experiments are repeated for 5 distinct random seeds, with the exception of the varying of image size where we only conduct the experiment for one seed.
We learn prior and posterior network weights as described in Scction 2.2 When both sets of weights have been trained, we use these as the means for prior and posterior distributions and p, chosen to be isotropic Gaussians with equal variance, a. Each bound is calculated for each pair of prior and posterior. To estimate the expectation over the posterior we sample 5 pairs of classifiers from the posterior and average their bound components (c.g., source risk) to get an estimate of the bound parts. When this has been calculated, we perform a small optimization step to choose the free parameters of the different bound through a simple grid search over a small number of combinations. We use the combination that produces the lowest minimum bound and account for testing all k combinations by applying a union bound argument, modifying the certainty parameter 5 to 8/k. When calculating the MMD, we use the linear statistic for the MMD detailed in Gretton et al. (2012) with the kernel k(æ, v) = exp( = This calculation is averaged over 10 random shuffles of the data for a chosen bandwidth, λ > 0. The process is repeated for different choices of bandwidth (see Appendix for details) and the maximum of the results is taken as the value of the MMD. Note that we caleulate the MMD in the input space and have not adjusted it for sample variance. When caleulating the importance weights we assume here that the maximum weight, Box, is uniformly bounded
8

---

Published in Transactions on Machine Learning Research (10/2022)
Label distribution
1.2
MNIST MINISTMM
1.3-
0.5
0.5-
Labada
Figure 2: Example of source label densities in the task with the mix of MNIST and MNIST-M samples. An example from each of the two data sets can be seen on the right, the upper one being from MNIST and lower one from MNIST-M. The target domain the complement of source samples.
the bound would potentially be vacuous otherwise. In addition, we will consider the importance weights to be perfectly computed for simplicity.
We construct two tasks from standard data sets which both fulfill Assumption design, one based on digit classification and one real-world task involving classification of X-ray images. These are meant to represent realistic UDA tasks where neural networks are the model class of choice.
3.1 Task 1: MNIST mixture
MNIST Lecun 1998) is a digit classification data set containing 70000 images widely used as benchmark for image classifiers. MNIST-M was introduced by Ganin et al. (2016) to study domain adaptation and is a variation of MNIST where the digits have been blended with patches taken from images from the BSDS500 data set (Arbeláez al. 2011). We use MNIST and MNIST-M to construct source and target domains, both of which contain samples from each data set, but with different label density for images from MNIST and MNIST-M. To create the source data set, we start with images labeled "0" by adding 1/12th of the samples from MNIST-M and 11/12th of the samples from MNIST, 1/12 for each subsequent label, "1", "2", and so on. The complement of the source samples is then used as the target data, see Figure 2 for an illustration. We make this into a binary classification problem by relabeling digits 0-4 to "0" and the rest to "1". The supremum density ratio BB0 x 11 (see Theorem 2 is known and the mixture guarantees overlap in the support of the domains (Assumption
increase the proportion from MNIST-M by
3.2 Task 2: X-ray mixture
ChestX-ray14 (Wang al. 2017) and CheXpert IIriin et al. 2019) are data sets of chest X-rays and labeled according to the presence of common thorax diseases. The data sets contain 112,120 and 224,316 labeled images, respectively. Since the two data sets do not have full overlap in labels, we use the subset of labels for which there is overlap. The labels which occur in both data sets are: No finding, Cardiomegaly, Edema, Consolidation, Atelectasis, and Pleural Effusion. the CheXpert data set which indicates how certain a label is. As we consider binary classification, we set all labels that are uncertain to positive. Therefore, a single image in the CheXpert data set might have multiple associated labels. For most experiments we resize all the images in the data sets to 32x32 to be able to use the same architectures for both tasks. However, we also conduct small experiment with ResNet50 where larger image sizes are considered.
addition, there an uncertainty parameter present
We take 20% of chestX-ray14 and add to CheXpert to create our source data set. The target is the remaining part of ChestX-ray14 which then 89,696 images compared to the 246.072 of the source. With this, we know from Appendix B that foo 11 and we have overlap. We turn this into binary classification problem in one-vs-rest fashion by picking one specific label to identify, relabeling images with "1" if it is
9

---

Published in Transactions on Machine Learning Research (10/2022)
1.75
1.75
than random
Turget
Minisum bound
Mintmam of bound
1.25
1.00
0.75
0.25
0.25
Add.
Mult.
XMD
IW
Add.
Mol:
MMD
IW'
(a) MNIST/MNISS task.
(b) CheXpert ChartetraeetttXlllly task
Figure 3: The lightest bounds achieved on the LeNet-5 architecture. This illustrates the tightening effect of using data-dependent priors. Non-vacuous bounds are obtained when using data to inform the prior. The shaded area between 0.5 and is where random classifier would perform on average, and the shaded area. above signifies vacuily.
Source etror
MMD
0.6
Seunco
KL
0.5
0.4
0.4
Fraction
0.1
0.0
0.9
0.0
630
1900
1500
2000
2500
2000
000
1000
15.00
2000
2009
500
1000
1500
2000
2500
weight spíates
Woight updates
Weitht
(a) Mult bound,
(b) Add bound, 0.3
(c) MMD bound, 0.3
Figure 4: An illustration of constituent parts for three of the bounds with the fully connected architecture on the MNIST mixture task. = 0.03
present, and setting the labels of images with any other finding to 40" In this work, consider only the task of classifying "No Finding".
4 Results
As expected, when compute bounds with data-dependent priors, we achieve bounds which are substan- tially tighter than without them, seen clearly by comparing Figure Figure We also observe that the additive bound (Add) due to Germain et al. (203)) is the tightest overall for both tasks, followed closely by the IW bound. The latter is not so surprising as when we apply data-dependent priors, there is effectively a point in training where the Dku-divergence between prior and posterior networks very small. Morcover, due overlap, the weighted source error is equal to the larget error in expectation. Thus the only sources of looseness left the error the approximation of the expectation over the posterior and the log 1 term which is very small here. We can also see in Figure 5a and 5b that the minimum of the IW bound is often very close to the minimum of the additive bound. However, unlike IW, the Add bound relies access to target labels in to compute the term Ap (see further discussion below).
The evolution of the different bounds during training is shown for both (asks in Figure G Of course, all bounds will increase at some point as training progresses and the prior and posterior diverges further from each other and DEL increases. While Add is consistently very tight, we note that the A term which we cannot observe might be significant part of the bound when the DKL-term is low as we can see Figure 4b This is issue for the additive bound since if have sufficiently small variance of the posterior then the
10

---

Published in Transactions on Machine Learning Research (10/2022)
3.0
IW
IW
2.5
2.5
Add.
Minioum bound value
Mult.
Minimum bound value
Mult.
2.0
MMD
2.0
MMD
X
LeNet5
LeNet5
1.5
Fully connected
Fully connected
ResNet50
ResNet:5
1.0
1.0
0.5
0.5
0.0
0.0
Target error
Target error
(a) MNIST/MMN MNNISTM
(b) CheXpert+Chestt..ayyl
Figure 5: An illustration of the minimum bound value achieved by each of the three architectures on both tasks. The lowest target error achieved indicated by a black marker with a vertical dotted line through it.
disagreement will be low, using informed priors will make the DEL small while using neural networks often lead to having a low source error. This will leave only the constant term, log and the unobservable X, terms and in those situations the bound might even be dominated by the unobservable term.
The multiplicative bound of GGermain al., 2016) (Mult) suffers from the amplification of the source error es and DKL. term by the factor Boo, and is gemerally larger than the Add and IW bounds. Conceptually, the Mult and IW bounds are similar, but in the former, the loss is multiplied uniformly by the largest weight. For tasks where certain inputs with high loss are more uncommon in the target domain than in the source domain, this is especially detrimental. The MMD bound is initially dominated by the MMD distance between inputs from the source and target domains, as shown in 4c which is large and independent of the learned hypothesis. As such, this term cannot be reduced by optimization, without, for example, computing it in representation space (Long al. 2015).. With this approach, unobservable errors due to non-invertible representations must be accounted for (Johansson al. 2019).
Experiments using bounds for early stopping and model selection with different architectures yield the results seen in Figure|3) We can see that the errors achieved by terminating training at the smallest bound value (colored markers) do not coincide with the best-achieved target performance during training (denoted by the vertical dotted lines). Clearly, the bounds are not tight enough to do carly stopping. This is a result of the sample generalization term DRL. increasing during training. For other analyses, this need not be the case. For larger architectures, the early-stopped models are closer the best target models. If we instead look the same figure again, but this time focus utility for model selection we find something interesting. It seems that the bounds might be useful in this regard they consistently have lower values for cethiitccttrr/mmmodeee which perform well. However, to be able to say this conclusively a more thorough study with different learning setups must be done. Both of the two previous observations should be contextualised with the fact that the domain shift terms are not dependent on the model as such, but amplify looseness in the case of the Mult and IW bounds. For the MMD and Add bounds, increased looseness during training is an artifact only of sample generalization.
As can see in Figure 7a when we vary the size of the images give to the ResNet50 architecture observe that the error seems to decrease for the larger image sizes. Although, the minimum bound value achieved does not seem to follow the same trend consistently. This is likely the result of the amount of epochs trained for both prior and posterior. In Figure 7b we see that the choice of prior sample proportion a makes some change to the smallest bound achieved. We also see the minimum bound values grow for large values of a, indicating that the remaining data is better spent calculating the bound than informing the prior in this case. We can also infer from Figure | that using no data to inform the prior worse than using some. The overall shape is consistent, with the results reported in Dziugaite et al. 2021 Figure 1).
11

---

Published in Transactions on Machine Learning Research (10/2022)
Source
Source
2.0
Postetioe
Additive bound
2.0
Proct
Paskatio
Ad
Mruttpllrative bound
Multilleattv bould
XKD bound
MiMu bound
1.5
IW Wiihbundd..
3.5
IW bouab
1.0
1.0
0.5
0.5
0.0
500
1000
1500
2000
2500
0.0
2000
4000
6000
8000
10000
Weight updates
Weight updates
(a) MNIST/MNIST-N task
(b) CheXpert CheneettChetX task
Figure 6: Bounds evaluated at different points during training of the LeNet-5 architecture. a = 0.3, a 0.03. The shaded areas represent one standard deviation.
0.5
1.5
Add.
mult.
0.4
Bound value
MMD
0.3
1.0
0.2
0.5
0.1
Turpel cEoor Miniruum of bound
0.0
32
120
0.2
0.4
0.6
0.8
Lmnage size
a
(a) Minimum bound value and target error on the X- (b) The minimum value of the bounds on the task for different values of a. The architecture used is LeNet-5.
ray task with different sizes of input images. Archi- tecture used is ResNet50, a = 0.3, a 0.003
Figure 7: a) show results of varying image sizes when training the ResNet50 network on the X-ray task. b) shows how the minimum value of the bound varies with a.
5 Discussion
From our survey of the literature, it is clear that only a small handful of analyses of UDA generalization can be informative practical bounds target domain performance. The main obstacle for computing existing bounds is that they are vacuous or intractable to compute for the kinds of models which perform the best common UDA benchmarks- which perform well once they are applied with data-dependent priors; without this they are vacuous. In our experiments, the Add bound with the unobservable term is the tightest which is unsurprising given its dependence on target labels. Furthermore, we note that the application of importance weights also performs very well as the setting sufficiently benign. As such we can say that in this setting we can achieve the desiderata of a tractably computable, light bound using the IW bound. However, recall that the guarantee get is distribution over classifiers and not one specific classifier. It should be noted, however, that the IW bound can become vacuous in certain situations where the worst-case density ratio, 9xe, is large and either the DKL term or errors on underrepresented classes is large enough.
neural networks. A potential remedy is the use of PAC-Bayes bounds,
We found that the lowest value of the bounds achieved during training does not in general correspond to the best performing model on target. This tells us that these bounds are not useful metries for early stopping. Further, the findings for using bound values for model selection are inconclusive, more experiments have be conducted to answer this question satisfactorily. During training, we see that the dynamics are dominated by
12

---

Published in Transactions on Machine Learning Research (10/2022)
the KL-divergence term, inherent to PAC-Bayes analysis, as training progresses. This reinforces our view that these bounds might be useful in getting performance estimates of methods at one particular point and not over several points during training if we do not have access to a large sample. This issue might be ameliorated by regularizing towards the prior during training, although this introduces yet another optimization as we now have to find the optimal regularization strength. In addition, it is not certain whether this will have any adverse effects on the final performance of the learned classifier.
A limitation of this work is that the bounds are cumbersome to compute and it is possible to do several optimizations in the process of producing the bounds. We have tried to do as few as possible in the name of practicality. We list some of the possible further optimizations in Appendix A for the reader's consideration. The impracticality of computing PAC-Bayes bounds is known issue that has had some work done by Viallard et al. (021]) where they introduce an approach which would remove the computation of expectation over the posterior. In addition, in this work the computation of test errors have dominated the computation time. To produce the results one has to compute the prodictions at least 50 times(ō pairs of sampled models from the posterior and 5 random seeds) for each datapoint in the bound for single choice of prior. This will naturally consume increasing amounts of time with larger data sets.
Furthermore, the overlap assumption will not hold for all real-world applications. In fact, many of the benchnarks for algorithm development, such as the SVHN-MNIST task (Ganin et al. 2016) blatantly violate overlap, since images of house numbers and handwritten digits differ vastly in pixel space. Examples where overlap holds by definition include when the target domain represents a subpopulation of a larger population given by the source domain, e.g., women (target) among all patients (source) with a medical condition. Although an easy learning problem on its face, the optimal model in the full population may not be optimal for the subpopulation. Even when overlap is violated, many share the intuition that overlap may hold in transformed space (Wu et al. 2019). representative of the core aspects of the problem- digit is a digit, whether on house or a postcard.
The strictness of the overlap assumption has been studied by D'Amou et al. 2021 where it was found that even for Gaussian distributions with insubstantial differences mean parameters, overlap vanishes in high dimensions. Motivated by this fact we might wish to adopt relaxed versions of our assumptions or completely novel ones which still guarantee consistent estimation. A first step could be to require overlap only in a transformed space, not in the input space, like in Wu et al. (2019) or only requiring overlap in specific regions and leveraging assumptions on "closeness" in the other regions, as in Johanssonn et al. (2019). Further, task-specific assumptions are likely needed for a more complete description of out-of-distribution generalization. We mean task-specific in the sense that the assumptions will depend on the structure on the problem and the data--gneratiig process (Hansen 2008) or other approaches. Overcoming this gap is a important direction of future study.
Another limitation of this work is that the hypotheses do not optimize for adaptation to the target domain, which might be achieved through representation learning as in Ganin et al. (2016) or minimization of a weighted loss (Shimodaira, 2000). Our setting is representative for tasks where the target domain is unknown during training, but known when computing the bounds. Further, in this work we have assumnd that we are able to estimate the importance weights exactly which may not be feasible in high- high-dimensional settings. In addition, there is no guarantee that the estimation error of the weights is small and thus even a small misestination may have quite large implications for the resulting bound.
Future work regarding generalization bounds should preferably comment upon usefulness of their bound a practical guarantee for performance, which is something that is often lacking. Idcally this would extend to explicit calculation if the bound is possible to compute. New bounds are often used as inspiration towards new algorithms which are hoped to result in more generalizable models. However, this is seldom guaranteed by theory and verified only in limited settings empirically.
Our results offer indications for how to obtain tractable and tight bounds for neural networks used in UDA tasks with available tools. If overlap can be assumed to hold, then use the IW bound, estimate importance weights using density estimation (Sugiyama et al., 2012) or probabilistic classifiers and apply data-dependent priors. The amount of data to use and how long to train your prior etc. are all task dependent and thus some engineering is necessary to pick optimal values. If this cannot be assumed, the most promising approach
13

---

Published in Transactions on Machine Learning Research (10/2022)
to get bounds which fulfill desiderata in this case would be to use the MMD bound as this does not technically rely on overlap and is tractable to compute for neural networks. This relies on the added assumptions of the pointwise loss being bounded by function in the associated reproducing-kernee Hilbert space, which may or may not hold. The nature of this assumption makes it less useful since no test for this is available absent overlap and similar nature assuming that joint optimal error small. However, if the function under estimation believed to be smooth, the assumption is more plausible. In conclusion, is clear that the general case demands new research, and alternative, task-specific assumptions, allow tight performance guarantees for realistic problems. In either setting, conjecture that the tightest bounds will be coupled to the training procedure.
Acknowledgements
This work was supported part by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.
The computations and data handling were enabled by resources provided by the Swedish National Infras- tructure for Computinng (SNIC) at Chalmers Centre for Computational Science and Engineering (C3SE) partially funded by the Swedish Research Council through grant agreement no. 2018-05973. Mikael Óhman at C3SE is acknowledgod for his assistance concerning technical and implementation aspects in making the code run on the C3SE resources.
References
David Acuna, Guojun Zhang, Mare T. Law, and Sanja Fidler. f-domain adversarial learning: Theory and algorithms. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 66-75. PMLR, 18-24 Jul 2021. URL
.ll...mmr... htw.pa/.............eee.eeeeeeee hee//v133 v139/ v139/acun22aa. accna21a. html
Ehab A. AlBadawy, Ashirbani Saha, and Maciej A. Mazurowski. Deep learning for segmentation of brain tumors: Impact of cross-instiuutional training and testing. Medical Physics, 45(3):1150-1158, 2018.
Amiran Ambroladze, Emilio Parrado-herándezz, and John Shawe-taylor. Tighter pac-bayes bounds. In
B. Schölkopl, J. Platt, and T. Hoffman (eds.), Advances in Neural Informalion Processing Syslems, vol- ume 19. MIT Press, 2007.
Pablo Arbeláez, Michael Maire, Charless Fowlkes, and Jitendra Malik. Contour detection and hierarchical image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(5):898-916, 2011.
Peter Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension and Pseudodimension Bounds for Piecewise Linear Neural Networks. Journal of Machine Learning Research, pp. 1-17, 2019.
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In B. Schölkopf, J. Platt, and T. Hoffman (eds.), Advonces in Neural Information Processing Systems, volume 19. MIT Press, 2007.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Percira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Mach. Learn., 79(1-2):151- 175, May 2010.
John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman. Learning Bounds for Domain Adaptation. Proceedings of the Conference on Neural Information Processing Systems (NIPS), pp. 8, 2008.
Daniel C. Castro, Ian Walker, and Ben Glocker, Causality matters in medical imaging. Nature Communi- cations, 11(1):3673, July 2020. ISSN 2041-1723.
14

---

Published in Transactions on Machine Learning Research (10/2022)
Corinna Cortes and Mehryar Mohri. Domain adaptation and sample bias correction theory and algorithm for regression. Theoretioal Compuler Science, 519:103-1 126, January 2014. ISSN 0304-3975.
Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning Bounds for Importance Weighting. Tn J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta (eds.), Advances in Neural Information Processing Systems, volume 23, pp. 442-450. Curran Associates, Inc., 2010.
Corinna Cortes, Mchryar Mohri, and Andrés Muñoz Medina. Adaptation Algorithm and Theory Based on Generalized Discrepancy. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 169 178, Sydney NSW Australia, August 2015. ACM. ISBN 978-1-4503-366422
Corinna Cortes, Mchryar Mohri, and Andrés Muñoz Medina. Adaptation based on generalized discrepancy. Journal of Machine Learning Research, 20(1):1-30, 100, 2019. URL http::///n.....g//paaaapaa pptp/ppaaaa////1111222
html
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy. Joint distribution optimal transportation for domain adaptation. In Proceedings of the 31st International Conference on Newral Information Processing Systems, pp. 3733-374 3742, 2017a.
Nicolas Courty, Rémi Flamary, Amauy Habrard, and Alain Rakotomamonjy. Joint Distribution Optimal Transportation for Domain Adaptation. 1rXiu:1705.00 08848 fes, stat], October 2017b. arXiv: 1705.08848.
Sofien Dhouib, levgen Redko, and Carole Lartizien. Margin-aware adversarial domain adaptation with opti- mal transport. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 2514-2524 PMLR, 13-18 Jul 2020.
Sofien Dhouib and levgen Redko. Revisiting 6 T )-similarity learning for domain adaptation. NeurIPS, pp. 7408 7417, 2018.
Gintare Karolina Dziugaite and Daniel M. Roy. Data-dependent PAC-Bayes priors via differential privacy. WxXi::180.00958. fcs, stat), April 2019. arXiv: 1802.09583.
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel M. Roy. On the role of data in PAC-Bayes bounds. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), October 2021.
Alexander D' D'Amour, Peng Ding, Avi Feller, Lihua Lei, and Jasjeet Sekhon. Overlap in observational stud- ies with high-dinmensionall covariates. Journal of Econometrics, (21(2):644 654, 2021. ISSN 0304-4076. doi: article/pp1//00044766222333
010.00000.000..0.000..0.0....... 2019.10.14. URL https: //www. wtt.//die..ccccccdrrreet.... wwc.iinncctret....ccccceieeeeeee com/science/
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Lavi- olette, Mario Marchand, and Victor Lempitsky. Domain-Adversariil Training of Neural Networks. arXiv:1505.0768 [es, stat], May 2016. arXiv: 1505.07818.
Pascal Germain, Amaury Habrard, François Laviolette, and Emilie Morvant. A PAC-Bayesian Approach for Domain Adaptation with Specialization to Lincar Classificrs. In International Conference on Machine Learning, pp. 738 746. PMLR, May 2013. ISSN: 1938-7228.
Pascal Germain, Amaury Habrard, François Laviolette, and Emilie Morvant. A new pac-bayesian perspective on domain adaptation. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. New York, New York, USA, 20-22 Jun 2016. PMLR.
Pascal Germain, Amaury Habrard, François Laviolette, and Emilie Morvant. PAC-Bayes and Domain Adap- tation. Neurocompuling, 379:379 397, February 2020. ISSN 09252312. 2. arXiv: 1707.05712.
15

---

Published in Transactions on Machine Learning Research (10/2022)
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-777 -73, 2012.
Ben B. Hansen. The prognostic analogue of the propensity score. Biometrika, 95(2): 488, 06 2008, ISSN 0006-3444. doi: 10.1093/ ha0////ooet//snO// URL
Kaiming He, Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Jeremy A. Irvin, Pranav Rajpurkar, M. Ko, Yifan Yu, Silviana Ciurea-Tlcus, Chris Chute, H. Marklund, Behzad Haghgoo, Robyn L. Ball, K. Shpanskaya, J. Seekins, D. Mong, S. Halabi, J. Sandberg, Ricky H
Jones, D. Larson, C. Langlotz, B. Patel, M. Lungren, and A. Ng. Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison. In AAAI, 2019.
Fredrik Johansson, David Sontag, and Rajesh Ranganath. Support and invertibility in invariant representations. The 22nd International Conference on Artificial Intelligence and Statistics, pp. 527- 536. PMLR, 2019.
Seicchi Kuroki, Nontawat. Charoenphakdee, Han Bao, Junya Honda, Issei Sato, and Masashi Sugiyama. Un- supervised Domain Adaptation Based on Source-Guiee Guided Discrepancy. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):4122-4122, July 2019.
Yann Lecun. Gradient- Learning Applied to Document Recognition. proceedings of the IEEE, 86(11): 47, 1998.
Mingsheng Long, Yue Cao, Jianmin Wang, and Michael I. Jordan. Learning Transferable Features with Deep Adaptation Networks. arXim:1502.088 02791 [es], May 2015, arXiv: 1502.02791.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain Adaptation: Learning Bounds and Algorithms, In Proceedings of the Conference on Learning Theory, February 2009.
David A. McAllester. Some PAC-Bayesian theorems. In Proceedings of the eleventh annual conference on Compulational learning theory, COLT" 98, pp. 230 234, New York, NY, USA, July 1998. Association for Computing Machinery. ISBN 978-1-58113--67-7.
David A. McAllester. Pac-bayesian model averaging. Proceedings of the Twelfth Annual Conference on Computational Learning Theory, COLT '99, pp. 164-170, New York, NY, USA, 1999. Association for
Computing Machinery. ISBN 1581131674.
David A. McAllester. A PAC-Bayesian Tutorial with A Dropout Bound. ar e-prints, 1307: arXiv:1307.2118, July 2013.
Emilie Morvant, Amaury Habrard, and Stéphane Ayache. Parsimonious unsupervised and semi-supervised domain adaptation with good similarity functions. Knowledge and Information Systems, (3(3):309-34) 3499 November 2012. ISSN 0219-1377, 0219-3116.
Emilio Parrado- Parrado-Hernándde Hernández, Amiran Ambroladze, John Shyle-Taylor, and Shiliang Sun. Pac-bayes bounds with data dependent priors. J. Mach. Learn. Res., 13(1):3507-3531, dee 2012. ISSN 1532-4435.
Christian S Perone, Pedro Ballester, Rodrigo C Barros, and Julien Cohen-Adad. Unsupervised domain adaptation for medical imaging segmentation with sell-ensembling. NeuroTmage, 194:1-11, July 2019. ISSN 1053-8119, doi: n..001//..euurommge.2000 20t.:mmaee.20..3002222. 00...03.006.
Tevgen Redko. Nonnegative matria factorization for transfer learning. PhD thesis, Paris North University, 2015.
levgen Redko, Amaury Habrard, and Mare Sebban. Thcoretical Analysis of Domain Adaptation with Optimal Transport. arXiv:1610.00 002.6600.044000 fes, statf, July 2017. arXiv: 1610.04420.
16

---

Published in Transactions on Machine Learning Research (10/2022)
levgen Redko, Nicolas Courty, Rémi Flamary, and Devis Tuia. Optimal transport for multi-source domain adaptation under target shift. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the "wenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. $49- PMLR, 16-18 Apr 2019.
levgen Rodko, Emilic Morvant, Amaury Habrard, Mare Scbban, and Younès Bennani. A survey domain adaplation theory: learning bounds and theoretical guarantees. arXic:2004.11899 [cs, stalj, August 2020.
arXiv: 2004.
Omar Rivasplata, Tij Kuzborskij, Csaba Szepesvari, and John Shawe-Taylor. PAC-Bayes Analysis Beyond the Usual Bounds. orXiv:2006. 13057 fes, statj, December 2020. arXiv: 2006.13057.
John Shawe-Taayoo and Robert C. Williamson, A pac analysis of a bayesian estimator. In Proceedings of the Tenth Anmual Conference on Computational Learning Theory, COLT '97, pp. 2-9, New York, NY, USA, 1997. Association for Computing Machinery. ISBN 0897918916.
Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein Distance Guided Representation Learning for Domain Adaptation.
[cs, stat), March 2018. arXiv: 1707.01217.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of Statistical Plamning and Inference, 90(2):227- 244, October 2000. ISSN 0378-3758.
M. Sugiyama, T. Suzuki, and T. Kanamori. Density Ratio Estimation in Machine Learning. Cambridge books online. Cambridge University Press, 2012. ISBN 978-0-521-19011-6.
L. G. Valiant. A theory of the learnable. Communications of the ACM, pp- 1134-1142, 1984.
Guillermo Valle-Pérez and Ard A Louis. Generalization bounds for deep learning. arXiv preprint arXiv:2012.04 0155 2020.
Vladimir N. Vapník. Statistical Learning Theory. Wiley-Interscience, 9 1998. ISBN 0471030031.
Paul Viallard, Pascal Germain, Amaury Habrard, and Emilie Morvant. A General Framework for the Disintegration of PAC-Bayesian Bounds. arXim:2102.000 0864949.08888000 fcs, stat], October 2021. ar 2102.08649.
Martin J. Wainwright. High- Dineesiimnsi Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10.1017/9781108627711
Xiaosong Wang, Yifan Peng, Le Lu, Zhiyong Lu, Mohammadhadi Bagheri, and Ronald Summers. Chestx- ray8: Hospital-scale chest x-ray database and benchmarks on weakly-supervisee classification and local- ination of common thorax diseases. In 2017 TEEE Conference on Computer Vision and Pallern Recogni- tion(CVPR), pp. 3462-3471, 2017.
Yifan Wu, Ezra Winston, Divyansh Kaushik, and Zachary Lipton. Domain adaptation with asymmetrically- relaxed distribution alignment. In Kamalika Chaudhuri and Ruslan Salakhutdinov (ods.), Proceedings of the 36th International Conference on Machine Learningg, volume 97 of Proceedings of Machine Learning PMLR, 09-15 Jun 2019. URL https::/ppooceeeeeee
Research, pp. html
mlr www..ppres//ee.. htt///99////111 wttppp///ewwu////////e
Chao Zhang, Lei Zhang, and Jieping Ye. Generalization Bounds for Domain Adaptation. Advances Neural Information Processing Systems, 25:3320 3328, 2012.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Rocht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael I. Jordan. Bridging Theory and Algorithm for Domain Adaptation. arXic:1904. 05801 fcs, stat], April 2019. arXiv: 1904.05801 version: 1.
Yuchen Zhang, Mingsheng Long, Jianmin Wang, and Michael I. Jordan. On Localized Discrepancy for Domain Adaptation. arxiv2000.. 06242 (es, stot), August 2020. arXiv: 2008.06242.
17

---

Published in Transactions on Machine Learning Research (10/2022)
Han Zhao, Remi Tachet des Combes, Kun Zhang, and Geoffrey J. Gordon. On Learning Invariant Represen- tation for Domain Adaptation. In Proceedings of the 36th International Conference on Machine Learning, Jamuary 2019.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuous general- ization bounds at the imagenet scale: A pac-bayesian compression approach. In International Conference on Learning Representations, 2019.
A Experimental details
The experiments were carried out with a modified version of LoNet-5 due to Zhou et al. (0119) a 1024- 600-600-2 fully connected network similar to the one used in Rivasplata et al. (2020) and a ResNet50 architecture (He et al., 2016) as mentioned before. Since the 0-1 loss not differentiable we substitute it with the binary cross entropy loss which is and provides a tight upper bound on the 0-1 loss. We train with SGD with momentum 0.95 the optimizer with batch size of 128. The learning rate was chosen to be 3 x 10-3 for the LeNet-5 and fully connected architectures while for ResNet50 3 x 10-1 was used. The images from MNIST and MNIST-M were padded with zeros to 32x32 images. This was done to be able to use them with the ResNet50V2 implementation in Tensorflow which does not support smaller image sizes.
The training procedure went as follows. We load the data and construct our source and target. The source data then split into an a-fraction Sa which is used to train the prior network on for |Sal/b itcrations, where b is the batch size, to get an informed prior. This is then used as the starting point when training the posterior which is done network weights during the first epoch and then at the end of every subsequent epoch until termination. We terminate the training of the posterior network when we have trained 5 epochs.
all the available data. During training of the posterior network we save 10
When training the posterior terminated we save the weights and proceed with the computation of the bound. In contrast with Dziugaite et al. (2021) we not only consider the bound at the point of termination but also at previous points during training. This is done with the goal of gaining an understanding of the bounds' behaviour during training.
We assume that our prior can be modeled by an isotropic gaussian akin to earlier work, this is done to get an easily computable closed form expression of the KL divergence. To pick a good value of the a parameter one could sweep over some range of values and then use a union bound argument to be able to pick the best result with only a small penalty to the bound. We do not do such optimization and simply pick a value.
We perform a small optimization step when determining the free parameters of the bound. For the bounds from Germain et al. (2020), i.c. a, b, and w, we iterate over values in the range {1 x 10-3,5 5 x 10-3, 1 x 10-2 ...., x 10a 1 x 10º) for both free parameters and pick the combination which yields the lowest bound. For the MMD and IW bounds we pick y from the range (1 x 10-3, 5 x 10-3, 3, 1 x 10002, 55xx 10-2, x 10-1,66 1,5 10-1,9.9 9.9 x 10-1), choosing the one which yields the lowest bound.
A.1 Possible optimization when producing the bounds
When computing these bounds there are a lot of different parameter and hyperparameter choices to make, many of which can be optimized. We first have to train at least one model(depending on how many values of to consider) with all parameter choices that entails. Then we sample models according to whatever the posterior distribution is; the amount depending on how well we want to estimate the expectation over the posterior. All PAC-Bayes bounds contain some sort of parameter which is free to choose and we must do a at least a rudimentary parameter search lo arrive at a good bound. In addition to all these choices of parameters we can of course optimise these bounds even further. Some that we did not perform for this work are: Optimisc the representation for smaller MMD, L2 regularisation towards the prior for each specific parameter set (also entails finding the optimal regularization strength) and perform even finer grid searches for the optimal bound parameters to name just few.
18

---

Published in Transactions on Machine Learning Research (10/2022)
B Importance weights and how to derive them
So assume that we do mixing of two data sets (let's call them 0 and 1) to form two domains. We want to derive the way we should calculate and subsequently use the importance weights for this situation. We will do this first for the CXR task. In this task the underlying label set is multi-label and as such we need to make into categorical variables before calculating and applying weights. We achieve this by making the problem into a binary classification problem where we try predict if there finding or not. From this point we may calculate the importance weights follows:
T(r,)) T(>b))T())
T(xly)T(v)
8(x,y) S()ly)S(v) (S(rly, D 11y) S(xly, -
If we now assume that we have only no examples from data set 0 in the target as in the CXR task then we have the following
T(
T( = -))((11)))(_)00)
W = (S(xly, 1)S(D 1ly) +
D 0lu) )S())
T(y)=0 when this
Now we note that (a and S(rly, D = 1) cancel as the conditional distribution of these should be the same as we mixed uniformly over the initial label and T(xxx,D=1)=T(xx)) We are thus left with
T(y)
#examples with label y in T #examples with label y in which come from data set #T
w(y) S(y) = 11v)
#S
Through this argument we can see that the final importance weight is in the case where we use 20% of the images from data set. 1, which will become the target, mix with data set to become the source. Assume that the initial amount from data set 1 is mi.
#examples w/ label in #T #examples w/ label y in S which come from data set
#
#5 0.8m,
= 4 #5
#T 0.2m;
#T
We can do the same type of argument for the MNIST/MNIST-M mix. There we have more balanced data set where the classes are evenly distributed in amount across source and target.
T(z,y) T(ly,, D= 1)r(D 1ly) T(ly, 0)T(D - w S(x,y) DS(xly,D=11sSC 1)S(D 11yy + S(zly D = 0)S = 0ly))
Since the labels are balanced between the data sets T(y) 1. Since have mixed the datapoints for each 3(v)
label in uniform fashion know what T(aly. S(1),
1 for every label. As such can calculate the weight
#examples w/ label in T which come from data set wlrly, D 0) #examples w/ label in S which come from data set and similar for datapoints from the other data set.
C Additional results
C.1 Constituent parts of bounds
C.2 Best bounds achieved for different prior sample proportions
C.3 Bound during training
19

---

Published in Transactions on Machine Learning Research (10/2022)
2008 352
2010
1200
2000
1000
1000
12
100 300
1000 1000 2000
(a) Multiplicative bound
(b) Additive bound
(c) IW bound
(d) MMD bound
Figure 8: An illustration of constituent parts of cach of the four bounds with the fully connected architecture the MNIST mixture task.
0
2500
1000
6010
600
1900
1400
1000
2010
1806 1358
1300
1856 1300
2000
1270
1350
(a) Multiplicative bound
(b) Additive bound
(c) IW bound
(d) MMD bound
Figure 9: An illustration of constituent parts of each of the four bounds with the fully connected architecture the X-ray task. 0
1000 600 6508
1800
1866
1500
1002
40/0 1876 1350
1800
1806 T50
4500 1000 12:00 1350
(a) Multiplicative bound
(b) Additive bound
(c) IW bound
(d) MMD bound
Figure 10: An illustration of constituent parts of each of the four bounds with the LeNet-5 architecture on the X-ray task.
2000
0300
600
1900
1208
2400
1800
1800 600
100
1248
1800
1996 3300
4000
1208 1300
(a) Multiplicative bound
(b) Additive bound
(c) IW bound
(d) MMD bound
Figure 11: An illustration of constituent parts of each of the four bounds with the ResNet50 architecture on the X-ray task. 0
20

---

Published in Transactions on Machine Learning Research (10/2022)
1.0
Praction bound
Feaction of bound
0.6
Weighted source error
0.4
0.2
0.0
0.0
500
1000
1500
2000
2500
1000
1500
2000
2500
Weight updates
Weight updates
(a) Multiplicative bound, 0.03
(b) IW bound, 0.03
Figure 12: An illustration of constituent parts of each of the four bounds with the fully connected architecture the MNIST mixture task.
0.3
200 Vagu 1ptile
200 Gla 120 G00
opickes
Vieii
Peppe
(a) Multiplicative bound
(b) Additive bound
(c) IW bound
(d) MMD bound
Figure 13: An illustration of constituent parts of each of the four bounds with the fully connected architecture the X-ray task. a 0.3, 0.03
Greater
Vogit 1et
Weoil spatts
Peoii spates
(a) Multiplicative bound (b) Additive bound
(c) TW bound
(d) MMD bound
Figure 14: An illustration of constituent parts of each of the four bounds with the LeNet-5 architecture the X-ray task. = 0.3, a = 0.03
Voggu
(a) Multiplicative bound
(b) Additive bound
(c) IW bound
(d) MMD bound
Figure 15: An illustration of constituent parts of each of the four bounds with the ResNet50 architecture on the X-ray task. a = 0.3, a = 0.03
21

---

Published in Transactions on Machine Learning Research (10/2022)
2.00
2.50
Add.
2.25
Bound value
1.50
Add.
Bound value
2,00
1.75
IW
1.25
MMD
mult.
1.50
1.25
0.75
1.00
0.50
0.75
(a) Fully connected
(b) ResNet50
Figure 16: The minimum value the bound on the MNIST mixture task for different values a.
15
1.50
1.25
Add.
1.00
MMD
1.0
2Ad3
MHH
0.75
02-
6.5
(a) LeNet-5
(b) Fully connected
(c) ResNet50
Figure 17: The minimum value of the bounds on the X-ray task for different values of
Aiditan lecad
Paltetioo Ailras boadd acced
02-
2010
12:0
2000
2000
Vigga
(a) LeNet-5, 0.3, o 0.03
(b) Fully connected, 0.3, 0.03
(c) ResNet50, a = 0.3, or = 0.03
Figure 18: The evolution of the bounds during training on the MNIST mixture task when we use 30% of our sample to inform the prior.
Eurget
Mach
1.0
2800
8000
0000
1200
(a) LeNet-5, 0.3, = 0.03
(b) Fully connected, 0.3, 0 0.03
(c) ResNet50, 0.3, a = 0.03
Figure 19: The evolution of the bounds during training on the X-ray task when we 30% of our sample to inform the prior.
22

---

Published in Transactions on Machine Learning Research (10/2022)
2.5
Botino arme
Target arree
Prtc
Pistedtr
Addiive bound
Muttipliaane arin boud
2010 boees
NND bound
1.5
bound
0.5
2000
9203
80:00
8000
110.00
(a) LeNet-5, a = 0.3, a = 0.003
(b) Fully connected,
0.3, 0
0.003
(c) ResNet50, 0.3, 0.003
Figure 20: The evolution of the bounds during training the X-ray task when to inform the prior.
30% of our sample
23


Reviews:
[{"review_id": "mT66v15A5F", "reviewer": "Reviewer_vsaP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is well written, well organized and provides a good rationale for their motivation with a detailed review of the literature. Although the idea of using PAC-Bayes in domain adaptation is not new, the authors investigate this idea in details in the current paper, and give interesting results on the topic. They examine the tightness of existing bounds when using deep neural networks, identify those which could be estimable and tractably computable, and show that it is possible to get tight bounds when using standard PAC-Bayesian optimization techniques. The main results and the empirical study are of great interest.\n\nWeaknesses: A general criticism that I have is that some points in the paper could have been investigated more thoroughly. This is the case, for instance, of the computational practicality of the bounds. Also, the usefulness of the bounds in model selection, which is a huge interest of PAC-Bayes bounds, is inconclusive here and left for future research. I also have some minor concerns on the assumptions of the paper. As noticed by the authors, the overlap assumption is quite strong and is a huge limitation of the current work. I would have appreciated more discussion on this point. Furthermore, the other MMD bound is based on the assumption that the pointwise loss is bounded by a function in the RKHS, which is much less natural and intuitive. The authors could have detailed how the two bounds fit together and why these assumptions might (if possible) be complementary.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a PAC-Bayesian analysis of domain adaptation on image classification tasks, where most generalization bounds are vacuous. The authors incorporate PAC-Bayes theory into several bounds and use importance weighting to obtain tighter guarantees. They evaluate the bounds empirically on two tasks satisfying the covariate shift and domain overlap assumptions.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Overall, I think that this is a good work that is relevant to the TMLR community. I hope that the authors can elaborate on the points mentioned above.", "broader_impact_concerns": "N.A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "j5wKsdAFBi", "reviewer": "Reviewer_iFWv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written and easy to follow. The scope of the problem considered in this paper is clearly described, and the limitations of the results are also identified. I also appreciate the thorough review of existing bounds, and the annotations for each bound provided in Table 1.\n\nThe technical content is interesting. The theoretical contributions are, although \"easy\", still quite a useful combination of existing work that address an important gap in the literature. I found the idea of combining the data-dependent PAC-Bayes method from Dziugaite et al. and the importance weighting/MMD tools to be interesting.\n\nThe empirical results are also quite interesting. I especially liked the decomposition of the bounds into their constituent terms to determine where improvements can be made, and the investigation into the utility of using these bounds for model selection.\n\nSomething that would have been good to include is a plot (or several) demonstrating sample efficiency. I.e., as the total number of training examples is increased, how tight do the bounds get?", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates the utility of generalisation bounds for the unsupervised domain adaptation setting with two assumptions of the type of distribution shift: covariate-only shift, and $\\text{supp}(\\mathcal{T}) \\subseteq \\text{supp}(\\mathcal{S})$. A review of existing bounds is provided, where each is identified as being practically estimable/computable. Four PAC-Bayes bounds are identified/derived, and compared experimentally. The empirical results determine that these bounds are sometimes non-vacuous.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "In my view, the work does not need any significant changes to justify acceptance. Some additions the authors may consider are including sample efficiency experiments, and providing a brief introduction to the MMD tools used for one of the bounds.", "broader_impact_concerns": "There are no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gbsSloDiPn", "reviewer": "Reviewer_TMKi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and addresses an aspect of domain adaptation that is almost absent in the DA literature, namely the tightness of generalization bounds. However, it misses some aspects of the DA literature.  \n# Strengths:\n* The interest in the value of DA bounds, which is different from the mainstream role of inspiring algorithms: this is an important aspect as most of these bounds constitute an inspiration for designing DA algorithms.\n* The experimental procedure is well detailed in the main paper, and additional details are provided in the appendix.\n* Several limitations of the work are discussed in detail.\n# Weaknesses:\n* Some literature aspects of DA bounds are lacking, namely: \n  * Asymmetrically relaxed discrepancies [3], where the importance weight is only required to be bounded in order to guarantee good adaptation, instead of requiring equality of distributions.\n  * Localized discrepancies [1,2], where the restriction of the supremum defining the divergence to a proper subset of the hypothesis space yields significantly lower divergence measures as illustrated in [1]. \n  * Other important DA contributions with bounds leading to algorithms such as [4].\n* On importance weighting and the IW bound (Corollary 1):\n  * The IW bound proposed in the paper can become vacuous if $\\beta_\\infty = \\infty$. This can happen even if the source domain's support completely includes the target's. \n  * In the IW bound, the estimation error of the weights is not taken into account, i.e. it assumes perfect computation of the importance weights $w(x)$. This goes against the spirit of the paper concerned with the tightness of generalization bounds.\n\n* The MMD bound contains $K$, a parameter of the kernel that controls the estimation error of the MMD. However, no discussion is provided on its behavior for neural networks, whereas a main motivation of the paper is the vacuity of classic generalization bounds in the case of neural networks, notably those relying on the VC dimension.\n\n# References\n[1] Zhang, Yuchen, et al. \"On localized discrepancy for domain adaptation.\" arXiv preprint arXiv:2008.06242 (2020).\n\n[2] Cortes, Corinna, Mehryar Mohri, and Andrés Munoz Medina. \"Adaptation based on generalized discrepancy.\" The Journal of Machine Learning Research 20.1 (2019): 1-30.\n\n[3] Wu, Yifan, et al. \"Domain adaptation with asymmetrically-relaxed distribution alignment.\" International conference on machine learning. PMLR, 2019.\n\n[4] Acuna, David, et al. \"f-domain adversarial learning: Theory and algorithms.\" International Conference on Machine Learning. PMLR, 2021.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors are interested in the tightness, estimability, and computability of generalization bounds for domain adaptation. Their study is mainly motivated by the failure of most of the bounds in the literature to satisfy the three desiderata for neural networks, while the latter constitute the bulk of domain adaptation algorithm implementations. They restrict the study to the benchmark configuration where the covariate shift assumption holds and the source domain's support includes target's. To tackle such limitations, they advocate relying on PAC-Bayes analysis with a data-dependent prior. On the experimental side, they consider 4 generalization bounds and illustrate the advantage of data-dependent priors over uninformative ones. Finally, the limitations and possible extensions of the method are discussed.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "# Main points\nAccording to the weaknesses pointed out in the previous section, I kindly request the following changes/additions from the authors:\n* Including the lacking literature aspects, i.e. bounds based on asymmetrically relaxed divergences, localization, and f-divergences. In particular, there should be a theoretical discussion on the tightness of such bounds.\n* Since the experiments concern several seeds, including the deviation from the mean can be more informative on the behavior of the bounds.\n* Either taking into account the estimation of importance weights, or clearly stating that it is assumed that they are known. \n* Stating that the importance weights are assumed to be uniformly bounded.\n* Adding a discussion on how $K$ behaves for a neural network.\n\n# Minor points\n* In figure 5, a logarithmic scale figure for values close to the target error, and adding a grid, might facilitate reading.\n* In the discussion section, it is mentioned \"The main obstacle for using existing bounds is that they ... \". I would say \"computing\" rather than \"using\", are such bounds are used to propose DA algorithms in several cases.", "broader_impact_concerns": "This paper is concerned with a general aspect of DA theory with no focus on a particular application. Nevertheless, one can point out for example to the consequences of deploying domain adaptation methods on medical tasks, which might have important risks in case of failure of adaptation.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a PAC-Bayesian analysis of domain adaptation on image classification tasks. The key technique is the construction of PAC-Bayes type bounds with importance weighting for improving tightness. Some experiments on image classification are conducted as to verify the proposed bounds.

Although the use of PAC-Bayes is not new in domain adaptation, reviewers found the paper interesting and they agree the contributions made in this paper are worth publishing. 

I recommend for "accept with minor revision" to give the authors an opportunity to better reflect on the reviews. Specifically, the authors may want to further clarify the following points in the final version:
1. the usefulness of their proposed bounds for model selection (as the authors claimed the bounds are non-vacuous);
2. assumptions of the theoretical results, whether they can be further relaxed or not;
3. the IW bound: whether it might become vacuous under some circumstances, also the estimation error of the importance weights in practice.
Decision: Accept (poster)