Domain-Invariant Representations: A Look on Compression and Weights
Authors: Victor Bouvier
Céline Hudelot
Clément Chastagnol
Philippe Very
Myriam Tami
Venue:  (2020)
Keywords: Domain Adaptation
Invariant Representation
Compression
Machine Learning Theory

Abstract:  Learning Invariant Representations to adapt deep classifiers of a source domain to a new target domain has recently attracted much attention. In this paper, we show that the search for invariance favors the compression of representations. We point out this may have a bad impact on adaptability of representations expressed as a minimal combined domain error. By considering the risk of compression, we show that weighting representations can align representation distributions without impacting their adaptability. This supports the claim that representation invariance is too strict a constraint. First, we introduce a new bound on the target risk that reveals a trade-off between compression and invariance of learned representations. More precisely, our results show that the adaptability of a representation can be better controlled when the compression risk is taken into account. In contrast, preserving adaptability may overestimate the risk of compression that makes the bound impracticable. We support these statements with a theoretical analysis illustrated on a standard domain adaptation benchmark. Second, we show that learning weighted representations plays a key role in relaxing the constraint of invariance and then preserving the risk of compression. Taking advantage of this trade-off may open up promising directions for the design of new adaptation methods.

Under review as a conference paper at ICLR 2020
DOMAIN-INVARIANT REPRESENTATIONS: A LOOK ON COMPRESSION AND WEIGHTS
Anonymous authors Paper under double-blind review
ABSTRACT
Learning Invariant Representations to adapt deep classifiers of a source domain new target domain has recently attracted much attention. In this paper, we show that the search for invariance favors the compression of representations. We point out this may have a bad impact on adaptability of representations expressed minimal combined domain error. By considering the risk of compression, we show that weighting representations can align representation distributions without impacting their adaptability. This supports the claim that representation invariance is too strict a constraint. First, we introduce a new bound on the target risk that re- veals trade-off between compression and invariance of learned representations. More precisely, our results show that the adaptability of a representation can be better controlled when the compression risk taken into account. In contrast, preserving adaptability may overestimate the risk of compression that makes the bound impracticable. We support these statements with thcoretical analysis illus- trated on standard domain adaptation benchmark. Second, we show that learning weighted representations plays key role in relaxing the constraint of invariance and then preserving the risk of compression. Taking advantage of this trade-off may open up promising directions for the design of new adaptation methods.
INTRODUCTION
In a standard Supervised Learning setup. we consider that training data is representative of test- ing data. This ideal framework is often violated in practical applications since the data generative process can be altered during the application phase e.g. different pre-processing, sample rejection, imbalanced classes, condition of data collection, time evolving data... This so-called Distributional Shift situation Cquionero-Candele et al. (2009); Kull & Flach 2014)) is recognized as a major chal- lenge in Machine Learning (Amodei et al. (2016)) Domain Adaptation (DA) (Pan & Yang (009)) is a widely adopted strategy to mitigate its effects. It consists in leveraging unlabeled testing data (the target domain) in order transfer knowledge learned on labeled training data (the source domain).
A first line of study, named Importance Sampling (IS), assumes some stationarity in distributions in order approximate the risk in the target domain by weighting sample contribution (Shimodairal (2000): |Huang et al.] (2007)). To be applied, IS needs statistical support sharing across domains limiting its range of application when addressing high dimensional data. In that challenging con- text, Ganin & Lempitsky (2015) have shown that deep classifiers can be adapted to a new target domain by learning domain Invariant Representations (IR) and find theoretical support in the work of Bann-David et al. (2007: 2010). It assumes that a classifier trained on representations of labeled data sampled from both domains will achieve a negligible combined error (adaptability). However, enforcing distribution invariance in the representation space can badly impact its adaptability, for instance in the context of Target Shift (Zhao et al. (2019) or when the support of the distributions do not overlap enough (Johansson et al. (2019). In the most general case of DA, it is not clear how IR helps aligning domains and removing spurious correlations as pointed by Arjovsky et al. (2019).
In the present work, we show that the search of invariance favors learning representations with a significant loss of information from the original features. We refer to this phenomenon as the risk of Compression. In understanding, this risk is not addressed in the original work from Ben- Ben-David et al.) (2007) 2010). We demonstrate that taking into account this risk has two major advantages. First, it provides better control on (non-trainable) terms involving the labels in the

---

Under review as a conference paper at ICLR 2020
target domain. Second, it introduces new trainable term which embodies risk of Compression and then may open-up the path to new learning methods. We provide a theoretical analysis illustrated standard Domain Adaptation benchmark. We underline that better control
with experiments on non-trainable terms may lead to an over-pessimistic risk of compression. This brings to light an inherent trade-off when learning representations for domain adaptation: How much compression risk is acceptable in order to obtain invariance? As a first try to answer to this question, we point that Learning Weighted Representations plays a key role in aligning representation distributions in order to obtain invariance. More precisely, we show that under a constraint of strong source risk conservation, weighting representations does not impact its adaptability.
BACKGROUND
2.1 A DECADE OF DOMAIN ADAPTATION
The classical setup for modelling distributional shift is to introduce two domains: the source do- main ie. dataset where the model trained with supervision and the target domain i.e. where the model is tested or applied. Formally, for two random variables (X, Y) of a given space X' x Y we introduce two distributions on X' x y: the source distribution (X, Y) and the target distri- bution 1Pt (X, Y). We use the exponent notation and to differentiate source and target terms. We define the hypothesis space H. as a subset of functions from X' to D. The distributional shift situation is then characterized by the shift: IP* Y) # P* Y). Learning under Distribu- tional Shift Quiooero-Canded
et al. (2009)) consists in minimizing the risk on the target domain e' e'(h) E [((h(X), Y)] for given loss : y x ) + R- and an hypothesis function h H. Assuming that w/ (X,Y) = (XX, (X)PP((x Y) is tractable, it is straightforward to show that:
(h)) = EE (X,, Y)((M(X)) Y)]
(1)
Roughly speaking, this equation shows that it is possible to minimize the target risk using data (1t y/ isisn= sampled from the source domain (i.e. (Iz, yi) ~ Ip [X, (X,Y)) while re-weighting their contribution in the source expectation with a factor w(x; y1) (Imporiance Sampling). The difficulty of Learning under distributional shift arises when wx ys) not tractable. The first reason that data sampled from IP' (X, Y) is often not easily available. In order to get reasonable estimation of w. practitioners are used to reformulate the problem as Unsupervised Domain Adaptation.
Definition 1 (Unsupervised Domain Adaptation). Given a loss E, an hypothesis class H. source domain (X xxy D.PP(L (x, Y)) and a target domain (X (XxYEE' (X,Y) Y)), Unsupervised Domain Adapta- tion consists in minimizing the target risk (i.e. finding h² = arg minkeH B+(((((X), Y)) with finite labeled sampling of (x²: vf) ~ (X,Y) of the source domain and a finite unlabeled sampling (xt) (X) of the target domain.
If unlabeled samples in the target domain are available, first idea is then to approximate w(X,, Y) by w(X)= = /IP (X). This is equivalent to assuming that conditional distributions are con- served across domains (i.e. [P*(Y = (X)))X), a situation known as Covariate Shift, that has already been the subject of an extensive literature (Sugiyama et al. (008); Huang et al. (2007), ) This formulation becomes ioo-po when feature domains (x, and (X' R.P (X)) suffer from non-overlapping support: wXX) is then undefined. To address this issue, Invariant Representations learning (Long et al. (2015) performs adaptation by looking for representation Z = ((X) whose
distribution is conserved across domains P (Z) TP' (Z). A common strategy consists extracting features Z to learn labels Y in the source domain while controlling representation invariance. That is formulated as follows:
Learning Objective 1 (Learning Invariant Representations for Domain Adaptation).
g" g²,p" = arg min (1 a1) a:) e u) + ()+.)(()) (g.+)
(2)
where G is the set of classifiers and & is the set of representations. The hypothesis space is then
defined as H = [go g G. E D). (1)))) is distance between distributions [=(2) and (Z) and a is a orade-off parameter.
The choice of ((()) (4p has been the object of an extensive literature including f- divergence measures such as domain adversarial learning (Ganin & Lempitsky (2015): Tzeng et al. 2014 Long
2

---

Under review as a conference paper at ICLR 2020
al. 2018)), Integral Probability Measures such Maximum Mean Discrepancy (Long al. (2015 2016 or Optimal Transport (Shen et al. (0118). See Kouw Loog (2019) for an extensive review. Interestingly, learning invariant representations to perform adaptation finds theoretical support from the work of Ben-David et al. (007) 2010) that we recall in the next section.
2.2 THEORETICAL GUARANTEES OF DOMAIN ADAPTATION
We consider the set of representations & and classifiers g. The hypothesis space is denoted H
{g o 9 E G 9 E } We introduce the loss / : 3 x y - IR+ which is assumed symmetric and verifies the triangular inequality. We note the risk e(h) [E{ h(x)) for h H and s s(h, I/) E]((h(X), 4 [X) for (h, h') E H². To emphasize the role of a representation Z (X)). we introduce f(Z) | Z] and H {gop 40 where, for the ease of reading, this dependence is omitted in notations when not ambiguous. Ben-David et al. (2007: 2010) have derived theoretical bound of the additional risk when using representation = (xX) rather than raw features X:
p
9 C H. We underline that quantities depend on
Inequality 1 (Ben- et al. (2007 2010). For a given up E + and 9 E G. there is: sup (b.A))H
(' 6 (go
(h, (h,h') + inf heR
(1(h)+ + (
(3)
Target risk
Source risk
A(H):: Adaptability
d(HA))) Disagreement
The inequality D Tnnsures that the target risk is bounded by the sum of the source risk, the disagree- ment risk between two classifiers from representations (d(HAH) named HAH distance), and third term (A(H)) which quantifies the ability perform well in both domains from representations. In the rest of the paper, refer to the latter as the adaptability. Since [Y is unknown, X(H) is intractable in practical applications. By conveniently assuming that X(H) is negligible, is possible derive a Learning Objective which minimizes (g) + AH) Indeed, minimizing D(s..) on op leads learn representations Z (xX) such that IP' (2) Pp (Z), where such situation is sufficient to ensure that d(HAH) = 0.
2.3 THE CURSE OF INVARIANCE IN DOMAIN ADAPTATION
~ (N 1). X Compressing representations is easy way to achieve invariance. Assume X"~ 1() and Y 1x>0 then a trivial way to obtain representations invariance while separating source data is to consider yp 1z>0. The main drawback is potential loss of information from the original feature space. To explain this phenomenon, we first introduce formally the notion of Hypothesis space compression:
Definition (Hypothesis space compression). Let (4F1, 422) E 22, Pi compresses more H. if ((())) C H(p22). By language abuse, we will say that Zi = (X)() more compressed than Ze (X)).
Second, build two possible solutions (g), 101) and (92, (22) of Learning Objective | by consider- ing the following compositions X - Zi - Z/2 , Y such that yP and si yp are both in t and and g to are both in G. We set
g. P2 = o sp. These solutions are chosen to ensure that 91 o 21 = 92 D2 and Ze = (x2 is more compressed than 21 = (X). In the case when D)s.() the Jensen divergence, the data processing inequality (see Lemma 4.6 in Zhao et al. (219)) implies that (92, (P2) is better optimum than (f1, according to Learning Objective since e (g(1 (11) = (22 and (1s2))(pp2) I ((())))(p1). To conclude, learning under objective will favor compressed representations to enforce invariance. However, as noted in Johansson et al. 2019); Zhao al. (2019): Liu al. (2019), more compressed representations will degrade adaptability. Indeed,
o v. Φ1
and
((H((12)) = inf (h( + e" eh(h) S inf c'(h) + EM)) x(H(()1)) NEH((P2)
(4)
hcH((1)
since H((()) ) C H(yp2). question which remains not addressed in the literature (except Johans- son et al. (2019) under the Covariate Shift assumption) is:
How compression may increase the risk of bad adaptability?
3

---

Under review as a conference paper at ICLR 2020
Source
Target
Sourer
Target
Fositive Negatio
Positis
Negative
ga
gove
M goo
goof f0"
Figure I: We fix ip E i and we note D' supp(E (X)) and D' ((pp(((((((( with s, t. Labels in domains are not necessary for the analysis but, for better understanding, draw yp which separates well labels the source domain since our analysis will consider representations trained by unsupervised domain adaptation. (Left) Illustration of the source conservation where yp and y are two source equivalent representations and h o ş and h = s' for given g E G. Since T1 E DD' n D' have ((x1) (x1)). Note that (p(a3) may differ with yp (xra)) since 23 D This is also the case for 22 even if (xx2) D since I2 & D (Right) Illustration of the projected hypothesis for given h E H- with = g oo s and g E G. ip embeds I1; 22 and Ig closely in the representation space. The source risk conservation enforces to have are in D nD', ip and yp coincide these points. şp' modifies I' and changes its output for g. Then h can not fit this switch of output for Ty without changing outputs of both 21 and T2 illustrating the impact of compression of 4p
on D Since I1 and 22
3 THEORETICAL ANALYSIS OF COMPRESSION
3.1 WORKING PLAN
Our strategy aims compare representation to with representations sf which act similarly on the source domain but differently on the target domain (source equivalence). First, by allowing to com- pute the minimal combined eгrоr on source equivalent representations s limit the risk of bad adaptability of a fixed representation. Through an inequality called Target Compression, we show this new control of adaptability comes the cost of a new risk which embodies the Compression. This is done by studying the projection of an hypothesis defined as its best approximation from representations in the target domain among those that conserve the source domain error (source conservation). Second, we rely on the HAH inequality (Ben- Deen-David al. (000 2010 for stating new bound of the target risk (Invariant and Compressed Representations inequality). Finally, we expose the particular interest of this bound: it allows a better control on adaptability by considering compression. This is formulated by the Invariance Compression trade-off.
3.2 NOTATIONS AND DEFINITIONS
In the following, we fix given & Φ. We restrict analysis to the case of E (y.v') E ) + (y y²)y'² convenient choice for manipulating properly f(Z) E[Y Note that in the binary classification case ()- = {0, 1)), L is the accuracy. We define the set of representations which act similarly on the source domain but differently the target domain:
Definition 3 (Source equivalence). We introduce the set of source equivalent representations क- {g' E Φ, sp = ip on D"} (where D = supp(IP* (X))) and the source equivalent hypothesis space H= = [g sp' :g e g E .h*.. Two elements of th are said source equivalent.
The source equivalent hypothesis space A² is an extension of 7. adding hypothesis built using representations which are source equivalent to yp. For a given h H., we exhibit an interesting subset of H considering hypothesis with the same source error than
Definition 4 (Source conservation). For a given h H., we note H, (h' H (h, 0}.
4

---

Under review as a conference paper at ICLR 2020
It is worth noting that for all h E H(" Hr is not empty (see Appendix A for details). We are ready to introduce the projection of an hypothesis h Hf and to this purpose, note of E o and g' E G such that = g xp. Intuitively, the projection of h is defined as its best approximation from yp in the target domain among those which verify the source conservation Le. from hypothesis + with E 9 such that E (g p, = 0.
Definition 5 (Projection).
H. H is defined as follows: x(h) arg w e h') for h E Ht. (h) is called the projected hypothesis. If there is no uniqueness of the minimum, any solution works.
Illustrations of introduced definitions are provided Figure [ If = o H. the projection aims map à to g' o op with g' = g both in source and target T.2 norms. If, = g' o with s' e o the projection aims to map h to vp such that g in source L2 norm while g sp achieves minimal distance with g' o yp in target L norm. We can observe that Vh E H o T(h) = (h) in both source and target L norms hence the (abusive) analogy with projection.
For ease of reading, we remind the notations and definitions in appendix
3.3 OUR CONTRIBUTION
In the following, fix given H. such that H Ho C. H. We now ready to state new bound of the target risk:
Inequality 2 (Target Compression). Given g G and noting h (h), we have:
e'(go S se'
sup e (h, NEHo
inf (e' e th, (0 kEH,
(5)
7(H)):: Compression
(HH)))): Adaptability
Proof. See Appendix A
This inequality introduces two interesting terms (H.) and X' (HH. with opposite roles; the former involves a supremum while the latter involves an infremum on Ho. The term (H.)) is very similar to the adaptability X(H) from Inequality [ and will be further investigated. Before, we focus on the term ((H)) which reflects the possibility of finding hypotheses in Ho that not be well approximated from target representations. The more information is lost from raw features, the higher the risk, hence its name Compression. This can be formally stated follows:
Theorem embodies the risk of compression). Let (P1, PP2 22 two source equivalent source representations. If 91 is more compressed than 92, then (1p1, Ho) 2 7(p2, He).
Proof. If 1 is more compressed than 22, there P((p11) C M()22) c 7t" then vh E H. Hul(p)) C Ha((2) The projection involves an infremum then e' (h, h(p2)) < e'(h, (h, h((p1) where h((p) =
arg min E² (h, h'). The supremum on f E H. conserves the inequality.
We now focus attention on (HH)). It differs with A(H) in two ways. First, the source labelling function is involved only with the intermediate (z) E. [Y|Z]] Second, the risk associated with
(e (h, f u))) involves target expectation. In order to obtain a comparable bound with Inequality I we state new bound of the target risk which is our main contribution:
Inequality (Invariant and Compressed Representations). Given g G and noting h =(h),
2 inf Nen (h) + (h, f²), we have:
(')00) < E d( + 3
sup & E(hh, h) hEHo
+
inf e'()) + 5 (1()) (6)
NEHo
5(H)): Compression
A(HL)): Adaptabiliy
5

---

Under review as a conference paper at ICLR 2020
Proof. See AppendixA The main idea is to bound e' e' f o p)) and E² e' fr) using HAH inequal- ity. This introduces respectively e (h, f ap)) and 5* (h, f op with residual terms _ ddHHA)) 8 (two times). We use the source risk conservation to bound E" (h, f o p) I E* e f 4). Then we bound (h, f p) I (h) leveraging the Pythagorean theorem since f is the L norm.
We are now ready show the better control of the adaptability of the representation yp: Theorem (Better control of adaptability). İ(Ho) S X(H).
The proof is given by the infremum on H. H. Compression ((H.) and adaptability X(H.) have an opposite behavior. This reflects an interesting trade-off:
Theorem 3 (Invariance and Compression trade-off). With H. and H such that H C Hgg H C
H there X(H!) 2 X(H2) and (HH)) S (7H2).
The proof is obtained by observing that H. C H... Even if invariance may have a bad impact on adaptability, our bound shows is possible to have better control of the adaptability while con- serving the same degree of invariance. This control comes the cost of an additional term involving compression of representations. The trade-off between invariance and compression emphasizes than the more control there is over adaptability, the higher the risk associated with compression. Further- more, this new bound has particular interest in providing theoretical support for the construction of new learning objectives. The difficulty in DA comes from in the fact that the adaptability is trainable since it uses the labelling function in the target domain. Our study shows that better control of adaptability (i.e. making the adaptation more reliable) possible. The two additional terms and (HH) can indeed be trained in an Unsupervised Domain Adaptation setting
EXPERIMENTS
We are now conducting an experimental analysis on widely used DA benchmark of digits recog- nition (MNIST, USPS). We study two tasks M-*U and U-* under the Learning Objective 1 The representation o convolutional neural network with LeNet architecture (LeCun et al.) (1998) We set the dimension of representations 50 and G is the set of linear classifiers from the represen- tation space to classes (with a softmax layer on top) and the Domain Adversarial Neural Network (DANN Ganin Lempitsky (2015) for ID(s.t), We use the implementation from Long et al. (2018) for good reproductibility. Models are trained during 30 epochs and we note the learned represen- tation. In the following. we note CE the cross- coos-ee
We suggest to study the trade-off between compression and invariance with the family:
H = (go h B'Ill' - xxX)] s |X())I)X)] 17 7>0
We interpret this choice as a method for testing robustness of the learned representation adversarial attacks in the target domain.
Enforcing h E H.. Enforcing h E H is challenging in practrice. We suggest to rely on
penalization f. to promote o &p (in the sense of Po)) and ||4p- اll S 17 ||lll| (in the sense of Pt). We define the penalization L. as follows:
(x) ((XII
E [' (xx)
Co(g)
ReLU
(8)
E (XX]]
E' 1
Source conservation. For given h, the projected hypothesis is defined as h ÿ & where ğ is obtained by minimizing on g:
11(g, h)) = >r CE ((), + +1 - Ax) (()))
(9)
with Ay = 0.9 for enforcing the source conservation.
'The trainahility of is shown in Appendix A

---

Under review as a conference paper at ICLR 2020
(p) E H the following loss: Estimation of İ(Ho). We suggest to minimize on (g) CB* (xX), Y) + -o((p)
Agg ()
(10)
with A 10 CI (g (X). Y) and CE (go Y) are respectively two proxies of E e'(h) and
(h), (P) promotes h E H..
Estimation of ((H)). We follow an adversarial training procedure alternating between
maximizing an objective [ig, sp) on h = g E Ho (sup step)
2. computing the projected hypothesis (inf step)
During experimentation, we have observed that simply setting [[g, (p) -I + (where 9 o is an estimation of the projected hypothesis) leads to learn noisy labels. We suggest to prevent such pathological solutions by enforcing low entropy adding I' regularizer deat (E(), Y) with (Ý y) (x)
with Aent = -1. Then, set:
[[g. (p) = (ī o g ()) + (o + Aent CE(M(X)
(11)
Furthermore, for a fair comparison, we correct 7 by comparing with a baseline. This baseline allowed to train representations to fit the adversary.
Analysis We build new target domains modifying the label distribution which is known to badly impact X(H) (Johansson et al. (201)) Zhao et al. (019 For a given target dataset D with classes balanced, define D, ... Da as follows: for digit < i from D and setting Do = D. Main results are reported in Figure Although estimator trained using cross-entropy, the results are reported computing the accuracy test set in order to be consistent with our theoretical analysis.
6, Dj is obtained by removing half of
We can observe that stronger the adversary is (a + 1) (and the more the target shift (i 6 for D;)), the more significant the difference between X(H) and A(Ho). This demonstrates better control over adaptability especially when IR fails to perform adaptation. By playing with the value of we see that the better control on adaptability paid to the cost of higher y. In our example, the risk of compression is estimated to potential drop of performances from ~ 12.55% to 2-7.5% of accuracy in the target domain while the gain on adaptability is marginal by reducing it of ~4%. To conclude, a better control on adaptability is obtained with pessimistic estimation of the risk of compression.
5 WEIGHTS FOR INVARIANCE RELAXATION
The fact that compression and invariance are conflicting objectives supports the point from Wu et al. (019) which claims that invariance is too strict constraint. this section, we show that invariance can be relaxed leveraging Weighted Representations. More specifically, show that taking into account the risk compression leads to introduce an adaptability term which does not depend on learned weights. Then, weighting representations can reduce the discrepancy between the source and the target distributions without impacting the adaptability. We introduce the set of weights W, subset of functions
X - R+ such that E E*[w(X) (X) 1 and we note for W, pX)) w(X X))I=((XX (X). The condition EE [x))) 1 ensures that (X) is a distribution. We state a
similar result than Inequality [
Inequality 4 (Weighted version of Inequality 1}. For a given E and g E H.
e'(0 < " p) + dw (ASAH) + A. (F)
1
(12)
with (HAHH) = sup (M Is " (h, - s'(hhh)) and A = inf nen R e'(h) + (h))
inf
Interestingly, and ip play similar role in inequality 4 since they are actionable parameters to min- imize etn (g p) + dd (HAAH)) while
not quantify their impact (Pt). We show that taking advantage of compression leads to an adaptability which does not depend on weights. This needs to introduce some definitions:
7

---

Under review as a conference paper at ICLR 2020
MAAST LISSS
USPS MANS
yand
corrected (y ndise)
AIHg)
27.5
corrected
APK3
Mone
Risk (%6)
Rick
17.5
15.0
10 12.5
0
0
Figure 2: Up: We report the A(A) = X(H) - A(H2) with 7 = 1, ((A) 2 which supports Theorem 2 More the adversary is strong in LO (a - 1), more A(A) increases (similar analysis for D2 to 2)). Down: Illustration of the trade-off from Theorem B in the particular case of Dj with 0.75 U - M. Both and its correction reported. When increases, the risk of compression increases while the adaptability assumption is better controlled. Better in color.
Definition 6 (Strong source conservation). For a given h E HP, we note H, {h' E H. hí' on }*) where D = supp(PP(X)))
Definition 7 (Strong projection). II H- + H is defined as follows n (h) = arg min weH, 8 e'(h, for h E H. If there is no uniqueness of the minimum, any solution works.
We are now ready to state the role of weights relaxed invariance for lower compression: Inequality (Weighting Invariant and Compressed Representations) Given g E 9 and noting -I),), Bw = 2inf RER E e"'"(h) + eh,h, f)), we have:
(g(o))) s inf { e wEW
d (HDH) Bi sup (h, h)+ inf el(h)+e'(h, foop)) NEH.
h
Proof. This is straightforward extension of inequality applied to pw- Furthermore, infnem, (h) + s (h, f o up) does not depend due strong risk conservation (risk con- servation would have been dependent on through the constraint sm""h,, h) 0).
Adding weights exposes to the risk of increasing the variance of estimators when considering finite sampling analysis (see Cortes al. (2010) for an extensive theoretical analysis of Importance Sam- pling). In inequality 5 this can be controlled with good choice of W e.g. by considering weights w < .M for given M 0.
RELATED WORK
Generalization bounds for DA have been the object of an extensive literature for both Importance Sampling Cortes et al. (2010) and Invariant Representations/ Ben- et al. (2007) Mansourr et al. (2009). It has attracted a lot of attention in order to understand failure cases observed when using IR (Zhao et al. (2019): Johansson et al.] (2019)). The theoretical analysis in Johansson et al. 2019 is the work closest to ours. They introduce a loss information metric which quantifies risk of using non-invertible representations, The present work differs in three ways. First, our work follows the formalism introduced in (Be--David et al. (2007) which widely adopted in the commu- nity. Second, contrary to the information loss, theory provides a tractable risk of compressing representations. Finally, we do not rely on the Covariate Shift assumption which gives our work broader range of applications.
8

---

Under review as a conference paper at ICLR 2020
7 CONCLUSION
By addressing domain generalization under the perspective of compression, we have bounded the target risk by a sum of trainable terms (= o p) + d(HAH) + 8 + i(H))) and a term X(Ho) which embeds a new adaptability criterion of representations. We have shown that X(Ho) can be better controlled by enriching the hypothesis class Ho. This control comes at a cost of a higher risk of compression underlying trade-off between invariance and compression when learning IR for DA. Through an empirical study on a standard benchmark, we have exhibited the better control of adaptability. Furthermore, have shown how framework can be applied for studying adapta- tion robustness to adversarial attacks. Finally, as an attempt to obtain representation distributions invariance with lower compression, have emphasized the role of weighted representations for relaxing the constraint of invariance.
Achieving representation invariance can reduce the generalization gap between two domains. How- ever, all invariances will not have the same guarantees for better generalization. Our work shows that we will look for representations which preserve the best the information in the original target features spaces. We leave both the design on new Domain Adaptation methods which incorporate such consideration and relevant design of H. as future works.
Promising directions (1) Our analysis is restricted to the comparison among source equivalent and
representations of a given representation op E Φ. Then, for two given representations 222 of & which does not verify the source equivalence, our analysis does not allow to state if y presents, or not, better guarantees on the success of the adaptation. Understanding how the source equivalence can be relaxed can provide to the present work a broader range of applications. (2) Obtaining robust estimation of (HH)) by following to be challenging in practice. Finding fast and robust estimations of (Ho) (or a proxy of it) may help derive new learning objectives or policy for model selection. For instance, Information Theory gives better suited devices for modelling the phenomenon of compression. (3) A strategy may to enforce invariance directly in the target domain by transporting source samples, Formally, assuming DD' n DD' = 0, we set & such that (X) X on D' and (D(")) C D'. If is fixed in the source domain (i.e. (PID= is fixed) the optimal representation from the compression per- spective is 1 (X) = X. This consideration is connected with two recent trends which perform adaptation by generating cross domain samples (Sankaranarayanan et al. (2018); Hoffman et al.) 20188;; Bouusmalis et al. (2016)) or by finding Optimal Transport between the source and the tar- get domains (Courty el al. (2016) 2017)). (4) The Covariate Shift assumption can be stated as H. = {h H. h) = O with = arg min (h)). Such H. may provide a new frame- work for addressing the case non-overlapping supports Covariate Shift adaptation.
adversarial training procedure appeared
REFERENCES
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Con- crete problems in ai safety. arXiv preprint arXiv: 1606.066666 2016.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint 1901v:1907.0200 2019.
Shai Ben-Davia John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In Advances in neural information processing systems, pp. 137-144, 2007.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine learning. 19(--))1511-775, 2010.
Konstantinos Bousmalis, George Trigeorgis. Nathan Silberman, Dilip Krishnan, and Dumitru Erhan. Domain separation networks. In Advances in neural information processing systems, pp. 343-351, 2016.
Corinna Cortes, Yishay Mansour, and Mchryar Mohri. Learning bounds for importance weighting. In Advances in neural information processing systems, pp. 442-450, 2010.

---

Under review as a conference paper at ICLR 2020
Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamoniy. Optimal transport for do- main adaptation. IEEE transactions on pattern analysis and machine intelligence, 39(9))1853- 1865, 2016.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamoniy. Joint distribution optimal transportation for domain adaptation. In Advances in Neural Information Processing Systems, pp. 3730-3739, 2017.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In International Conference on Machine Learning, pp. 1180- 1 1189, 2015.
Judy Hoffmann, Eric Tzeng, Taesung Park, Jun- Yan Zhu, Phillip Isola, Kate Saenko, Alexei Efros, and Trevor Darrell. Cycada: Cycle-consistent adversarial domain adaptation. In International Conference on Machine Learning, pp. 1994-2003, 2018.
Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Bernhard Schölkopf, and Alex J Smola. Cor- recting sample selection bias by unlabeled data. In Advances in neural information processing systems. pp. 601-608, 2007.
Fredrik Johansson, David Sontag, and Rajesh Ranganath. Support and invertibility in domain- invariant representations. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 527-536, 2019.
Wouter M Kouw and Marco Loog. A review of single-source unsupervised domain adaptation. arXiv preprint arXiv:1901.05335 2019.
Meelis Kull and Peter Flach. Patterns of dataset shift. In First International Workshop on Learning over Multiple Contexts (LMCE) at ECML-PKDD, 2014.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, al. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11))2278-2324 1998.
Hong Liu, Mingsheng Long, Jianmin Wang, and Michael Jordan. Transferable adversarial train- ing: A general approach to adapting deep classifiers. In International Conference on Machine Learning. pp. 4013 4022, 2019.
Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan. Learning transferable features with deep adaptation networks. In Proceedings of the 32nd International Conference Interna- tional Conference on Machine Learning- Volume 37, pp. 97-105. JMLR. org, 2015.
Mingsheng Long, Han Zhu, Jianmin Wang, and Michael Jordan. Unsupervised domain adaptation with residual transfer networks. Advances in Neural Information Processing Systems, pp. 136- 144, 2016.
Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael Jordan. Conditional adversarial domain adaptation. In Advances in Neural Information Processing Systems, pp. 1640-1650, 2018.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In 22nd Conference on Learning Theory, COLT 2009, 2009.
Sinno Jialin Pan and Qiang Yang. A survey transfer learning. IEEE Transactions knowledge and data engineering. 22110):3345-135 2009.
Joaquin Quionero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. The MIT Press, 2009.
Swami Sankaranarayanan, Yogesh Balaji, Carlos D Castillo, and Rama Chellappa. Generate to adapt: Aligning domains using generative adversarial networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8503-8512, 2018.
Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation. In Thirty-Secone AAAI Conference on Artificial Intelligence, 2018.
10

---

Under review as a conference paper at ICLR 2020
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of statistical planning and inference, 90(2):27-224,, 2000.
Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul V Buenau, and Motoaki Kawanabe. Direct importance estimation with model selection and its application covariate shift adaptation. In Advances in neural information processing systems, pp. 1433-1440, 2008.
Eric Tzeng, Judy Hoffman, Ning Zhang, Kate Saenko, and Trevor Darrell. Deep domain confusion: Maximizing for domain invariance. arXiv preprint
2014.
Yifan Wu, Ezra Winston, Divyansh Kaushik, and Zachary Lipton. Domain adaptation with asymmetrically--rlaxed distribution alignment. In International Conference on Machine Learn- ing. pp. 6872-6881, 2019.
Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon. On learning invariant representations for domain adaptation. In International Conference Machine Learning, pp. 7523-7532, 2019.

---

Under review as a conference paper at ICLR 2020
A
MAIN PROOFS
Proposition 1 (The source conservation hypothesis not empty). For a given E t and E H Hy is not emply.
Proof. If h E H., it exists g E 9 and vp E Φ such that h = = o o'. We set h' = o 2 E H. there is E" h/) = = go = e² p. p) = O since = o on D' then h' E Hr.
Inequality 6 (Target Compression). Given &p E &, g 9 and noting ì π (h), there is for any Ha such that H. C. Ho H": c'(go S e' lg + sup h'( + inf (h) t 9) hEMo
(13)
heHo
Proof. L E p. g E and h E Ho:
<g s (e
(14)
s <E'(h) o (0)
(15)
+f < + (1) o.ggo))
(16)
S < o e' h)) + (1)) (
(17)
This is succession of triangular inequalities which involve respectively f ye, and h. The
last inequality is convenient arrangement of terms. We bound ch(h, h) by its supremal value for
Ho. then (g o up) S ef p. g.ge o vp + supheH, f=" h)} + (h) + (h, f s). Since this holds for all h E Ho. we bound (g y)) by the infremum for h H..
O
Inequality (Invariant and Compressed Representations). Given & E Φ, g E 9 and noting h = (h)) 3 = inf NEH (h) + (h, fr), there is for any Ho such that H C Ho C H.:
c ==)00)))))))))) d(HM)) +3+
sup (h, h)
+
e' + (h) inf NEHL
(18)
kEH.
+(H.):: Compression
((H.): Adaptability
Proof. First of all, recall the HAH inequality from Ben-David et al. 2007 2010), for any f and fe, there is:
wh E (h, ( (") + ( d(Ais))) + inf (h, ft) + fh)
(19)
f"= particular case of that inequality applied f== =t = fr a yp leads bound:
E' j o p) < E" (g 8 p) + d(HLAT))) + inf E" f (0))))))))))) + Eh, o
2
<E + ! (HAA)) - inf (*(h) + (h, f o op)
(20)
where bounding (g p x) (g ()) is direct property of Ely,y') (y 5/ and fz( E- (g) (g p, o p) + ' :p). Note that, it is not possible to so for e'(g o p, p) since the expectation computed the target domain. We define = in 8* (h) + f* p). We apply a second time HAH H inequality, there is for any h Ho:
(T, j o v) S e (h, o④) - + inf e' j" o o + e j o
RER
$ (h) d((AAA)
+ inf e' f*) (h) hEN
(21)
12

---

Under review as a conference paper at ICLR 2020
which is licit since h H. Relying the projected hypothesis h allows to preserve the invari-
ance: even if h E Ho. d(HAH) is involved, not dHH..H.). Then, use the property of source risk conservation h H which enforces e"(h, h) 0 for noting that e*(h) =*(h) + E² (h, e* (h) then:
e f0 ad(HAA))
1 (0
inf (h,
heR
Finally, taking the infremum:
1 inf e (h) + (h, x) S 28 dd + inf s'(h) + +1)) bEM.
1
(22)
NER.
Combining all inequalities leads to the stated onc.
Theorem (Better control the adaptability). i(Ho) S ((H).
Proof. We simply use the fact that H. C Ho then using the property of the infremum:
X(Hl.) inf keHo
e'(h) =h) S inf e'(h) + =h) X(H)
(23)
hEH
Theorem (y embodies the risk of compression). Let (411 (22) E 2 two source equivalent repre- sentations. Pp more compressed than P2, then 7(P1, Ho) 2 (1P2, Ho) for H Ho H..
Proof. If p1 and are two equivalent representations, there is H(())) C. H((p2) c H then wh H. (H((p)) n (h' H (h, 0}) c. (Hl(()) (H' e H: : 0}) which guarantees (x1)) c (x2)))). Finally
e' e'th, ((,,))((p))))))))) 8 ((,)))))))
invoking the property of the infremum where h(yp) = arg
E² (h, N²). The supremum on
h E Ho conserves the inequality.
Proposition 2 (8 is trainable from the data). Let (gn, PN)NEN sequence such that a (" PPn) (1 a1) ((p..) + then S,, O.
Proof. First of all, since (Dpp)) + 0 then Pd (X), + ())(()))) We note that for any n E N. $ 2. 2-= (g)
F o) -E o(p))) Since e" (gn, o(p,) + and (c'(gn opn,, f*) - (g o pn)) )) - 0 (because Pe (X)()((X) + (x)
f(opp)) S 2. E2 (gn +
there is Bn 0.
B NOTATIONS
c is the set of representations.
G is the classifiers.
H is the hypothesis space H o
For a given y E 4, we note H((p)) = (go:: :g:::gE 9] = Go When there is no ambiguity,
we note k((pp) = H.
For a given E H. we note e(h) = E( - h(X)) For d = 8, t, we note domain risk
(h) Ed [Y h)
For = s, and given E ④, we note the conditional expectation fd(Z) = E
with 7 = (X).
13

---

Under review as a conference paper at ICLR 2020
Equivalence. For given d, the set of source equivalent representations ('(()) {4 E @ 4 = on D") (where D = supp(P"(X)) and the source equivalent hypoth- esis space (p) = {go p' g E g E }* Two elements of th are said source equivalent. When there is no ambiguity, we note $+ and 7t.
Conservation.
-For given H², we note Hr (h' H: (h, =0}.
For given h Ho, note H. {N' H h 1'' on D*) where D supp(PP(X)))
Projection.
H H. is defined as follows: *(h) arg min een. E' e' h²) for h E it. (h) is called the projected hypothesis. If there is uniqueness of the minimum, any solution works.
II : H. + H is defined as follows r(h) = arg min wet. <' h') for h E H.. If there no uniqueness of the minimum, any solution works.
14


Reviews:
[{"review_id": "S1x9j79pKS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces the compression risk in domain-invariant representations. Learning domain-invariant representations leads to larger compression risks and potentially worse adaptability. To this end, the authors presents gamma(H) to measure the compression risk. Learning weighted representations to control source error, domain discrepancy, and compression simultaneously leads to a better tradeoff between invariance and compression, which is verified by experimental results.\n\nThe paper presents an in-depth analysis of compression and invariance, which provides some insight. However, I have several concerns:\n* In Section 4, the authors propose a regularization to ensure h belongs to H_0. How is the regularization chosen? How does it perform on other datasets? Experimental results only on digit datasets are not convincing.\n* In Section 5, the authors introduce weighted representations to alleviate the curse of invariance. However, they do not provide experiments to validate their improvement. \n* The organization of this manuscript is poor and difficult to follow. Starting from Section 3, the authors use several definitions to introduce their main theorem. However, these definitions are somewhat misleading. I cannot get the point until the end of Section 3. Besides, the notations are confusing, so I have to go back to the previous sections in case of misunderstanding.\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HklaqN7yqH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This submission provides a new theoretical framework for domain adaptation. In order to tackle the adaptability term in the classical domain adaptation theory, this submission proposes a new upper bound that enlarge the hypothesis space in the adaptability term. A weighted version of this theory is also given. Authors further support their conclusion by empirical results.\n\nPros:\n1. This submission studies an important problem in domain adaptation.\n2. This submission proposes new theoretical insight about compression and adaptability.\n3. The conclusions of this paper can be partially proved by the empirical results.\n\nCons:\n1.\tAs the author says in their future work, the source constraint is too strong that need to control the feature unchanged across all source domain. For this condition is not build on samples but on the support of source domain. It seems that authors use $L_0$ to constrain \\phi’ to have same value with \\phi on source dataset, which may be only a small part with zero measure of source support set. \n2.\tThere is no generalization error analysis for these upper bounds. This submission provides weighted version of the main theory in the section 5. It seems that weighted version of upper bound could be further minimized by find a good weight. But add weight will add variance in the complexity term [A].\n3.\tThis submission adds \\beta term to change the adaptability term of $\\tilde{\\mathcal{H}}$ into the adaptability term of $\\mathcal{H}_0$. The reason why \\beta can be estimated from finite sample is not clarified, which is the premise of being trainable and should be mainly discussed in this paper. We can see that to estimate \\beta is a domain adaptation problem under the fact that the labeled functions are same. \\beta is a term that can’t be computed from small finite samples if there is no more assumption: It is not easy to approximate $\\tilde{f}_s$ uniformly, otherwise the estimation of \\beta will suffer from distribution shift. This submission claimed that the term can be trainable by giving Proposition 2, a proof of the consistency. However, this proposition is built on the assumption that there exists a series of \\phi minimizing the distribution distance to zero. But this is impossible for finite sample estimation, when there will always be generalization error of estimating the distribution distance. Furthermore, it is usually impossible to make the two embedded distributions completely the same in empirical. In addition, if there is a series of \\phi, how to control other terms in the upper bound? Every \\phi will induce new $\\tilde{\\mathcal{H}}$ and $\\mathcal{H}_0$ which will change all other terms. In summary, the main theory in this submission changes the unknown adaptability to a new term that is very hard to estimate. And there is no sufficient empirical or theoretical evidence in this paper that could support the fact that \\beta is small. The contribution is therefore limited.\n4.\tThe theory also fails to give upper bounds on compression term and adaptability term, or some explicit upper bounds for certain hypothesis spaces as examples. Readers could not have a clear image of how large will these terms be. Furthermore, if the support sets of source and target domain coincide a lot, the adaptability of $\\mathcal{H}^s$ will not be too smaller than the previous one.\n5.\tThe organization of the submission makes it hard to read:\na)\tThe symbol of this submission is chaotic. For example, $\\tilde{\\mathcal{H}}$, $\\tilde{\\mathcal{H}}^s$ ,$\\tilde{\\mathcal{H}}_h$ are defined based on $\\phi$, $\\pi(h)$ is defined based on $\\tilde{\\mathcal{H}}$, but all these facts are not revealed in their symbols. \nb)\tFor clarity, all loss functions defined in Section 4 should be stated in a independent line. The Section 5 should be moved to the front of Experiment part.\nc)\tI recommend the authors to restate all new defined symbols as a list on the top of appendix. It really troubles me during checking the proof.\n\nI think this submission discusses about an important problem and provides new insight, but it is not a thorough theoretical work because of above reasons. So, I vote for rejecting this paper.\n\n[A] Cortes, Corinna, Yishay Mansour, and Mehryar Mohri. \"Learning bounds for importance weighting.\" Advances in neural information processing systems. 2010.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJeSgyAaKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------\nThis paper presents a revisit of existing theoretical frameworks in unsupervised domain adaptation in the context of learning invariant representation. They propose a novel bound that involves trainable terms taking into account some compression information and a novel interpretation of adaptability. The authors mention also contribution showing that weighting representations can be a way to improve the analysis. \n\nEvaluation\n-----\nThe ideas are novel and the result brings novel and interesting light on the difficult problem of unsupervised domain adaptation. \nHowever, the practical interest in terms of applicability of the proposed framework is not fully demonstrated, the properties of the proposed analysis have to be studied more in details and some parts better justified. The experimental evaluation brings some interesting behavior but is somewhat limited. The weighting aspect of the contribution is not supported by any experiment.\n\nOther comments\n------------\n\n-I am a but puzzled by the use of the term \"compression\". This is maybe subjective, but in the context of learning representation, I would have interpreted it as a way to sparsify the representation, and thus compression could then be measured with respect to a given norm (L2?) or another criterion (Kolmogoroff, ...). \n\nIn the paper, the notion of compression is related to a reduction of the hypothesis space after application of a transformation \\phi, so I am wondering if using \"hypothesis space reduction\" would not be more appropriate.\nIn this case, however, there are maybe links with structural risk minimization that could be investigated here.\nA side remark: there is no particular restriction on the space of transformations, we wonder if it would be useful to indicate if all the possible transformations are included as subspaces of a given latent space. Since, to be very general, one can imagine the existence of an unbounded number of transformations that correspond to an increase of the input dimension. For transformations leading to different representations of different dimensions, the way the deduced hypothesis can be compared should also be indicated (for defining properly the inclusion H(\\phi_1)\\subset H(\\phi_2).\n\nOn the other hand, the authors seem to need the use of norms over transformations as illustrated in the definition of H_0^\\eta in the experimental section. So I suggest that the analysis could be revisited by directly incorporating (representation) norms in the theoretical framework and in particular for defining more properly H_0.\n\n-One weakness of the theoretical framework is for me the lack of definition of H_0 in Section 3. We just know that it is included between two classes of hypothesis of interest, but there is no clear characterisation of H_0 which makes the analysis fuzzy: we have a bound that involves an object without any clear definition and it is for me difficult to really interpret the bound. Trying to define H_0 with some restrictions related to the norm of the transformations, as evoked before, could be a way to address this point (and actually the way the experiments are done tend to confirm this point).\n\n-Another weak point is the lack of qualitative analyse of the bound in Inequality 3 (the same applies for Inequality 5). I would have appreciated if the authors could provide an analysis similar to the one of (Mansour et al., COLT 2009) - it is cited in the paper - when they compared their result to the one of (Ben-David et al., 2007). For example, what happens when source is equal to the target, when is the bound significantly loose, significantly tight, different from other existing results, ...\n\nIn particular, if we compare the bound with the one of Ben-David et al. (we can also consider the one of Mansour et al.), there is two additional term, one is weighted by a factor 2, another one involved a supremum and one can think that this bound is rather loose and does not provide any insightful information and said differently it could not give a strong framework for practical considerations.\nI may understand that when the bound is tight we could deduce that the compression term is low, but finding cases leading to a tight interesting bound does not seem obvious.\n\n-The experimental evaluation presents some expected behavior in the context of the bound, but I miss a real study trying to make use of the proposed framework to do adaptation in practice with comparisons to other strategies.\nAdditionally, having additional studies with other models and tasks will probably reinforce the analysis.\n\n-At the beginning of Section 3.2, the authors mention that they restrict their analysis to the square loss, however I think the analysis is true for larger class of losses with more general properties. In the experimental evaluation, the cross entropy is used, so I think that the experimental evaluation should also be consistent with the theoretical analysis by considering the square loss.\n\n\n-Paragraph below Definition 5 is unclear: the notion of L2 norm has not been introduced in this context, so the message of the authors is a bit unclear.\n\n-I do not find the notation \\gamma(\\phi,H) appropriate, I woud rather suggest to use \\gamma(H\\cdot \\phi)\n\n-The biblioggrgaphy can be improved by adding the right conferences/journals where the papers have been published in addition to the ArXiv reference.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a new theoretical framework for domain adaptation by exploring the compression and adaptability.

Reviewers and AC generally agree that this paper discusses about an important problem and provides new insight, but it is not a thorough theoretical work. The reviewers identified several key limitations of the theory such as unrealistic condition and approximation. Some important points still require more work to make the framework practical for algorithm design and computation. The presentation could also be improved.

Hence I recommend rejection.
Decision: Reject