summaries: 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. This 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.  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.
abstractText: 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.
references.authors: Dario Amodei Chris Olah Jacob Steinhardt Paul Christiano John Schulman Dan Mané
references.title: Concrete problems in ai safety
references.venue: arXiv preprint arXiv:1606.06565,
references.authors: Martin Arjovsky Léon Bottou Ishaan Gulrajani David Lopez-Paz
references.title: Invariant risk minimization
references.venue: arXiv preprint arXiv:1907.02893,
references.authors: Shai Ben-David John Blitzer Koby Crammer Fernando Pereira
references.title: Analysis of representations for domain adaptation
references.venue: In Advances in neural information processing systems,
references.authors: Shai Ben-David John Blitzer Koby Crammer Alex Kulesza Fernando Pereira Jennifer Wortman Vaughan
references.title: A theory of learning from different domains
references.venue: Machine learning,
references.authors: Konstantinos Bousmalis George Trigeorgis Nathan Silberman Dilip Krishnan Dumitru Erhan
references.title: Domain separation networks
references.venue: In Advances in neural information processing systems,
references.authors: Corinna Cortes Yishay Mansour Mehryar Mohri
references.title: Learning bounds for importance weighting
references.venue: In Advances in neural information processing systems,
references.authors: Nicolas Courty Rémi Flamary Devis Tuia Alain Rakotomamonjy
references.title: Optimal transport for domain adaptation
references.venue: IEEE transactions on pattern analysis and machine intelligence,
references.authors: Nicolas Courty Rémi Flamary Amaury Habrard Alain Rakotomamonjy
references.title: Joint distribution optimal transportation for domain adaptation
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Yaroslav Ganin Victor Lempitsky
references.title: Unsupervised domain adaptation by backpropagation
references.venue: In International Conference on Machine Learning,
references.authors: Judy Hoffman Eric Tzeng Taesung Park Jun-Yan Zhu Phillip Isola Kate Saenko Alexei Efros Trevor Darrell
references.title: Cycada: Cycle-consistent adversarial domain adaptation
references.venue: In International Conference on Machine Learning,
references.authors: Jiayuan Huang Arthur Gretton Karsten Borgwardt Bernhard Schölkopf Alex J Smola
references.title: Correcting sample selection bias by unlabeled data
references.venue: In Advances in neural information processing systems,
references.authors: Fredrik Johansson David Sontag Rajesh Ranganath
references.title: Support and invertibility in domaininvariant representations
references.venue: In The 22nd International Conference on Artificial Intelligence and Statistics,
references.authors: Wouter M Kouw Marco Loog
references.title: A review of single-source unsupervised domain adaptation
references.venue: arXiv preprint arXiv:1901.05335,
references.authors: Meelis Kull Peter Flach
references.title: Patterns of dataset shift
references.venue: In First International Workshop on Learning over Multiple Contexts (LMCE) at ECML-PKDD,
references.authors: Yann LeCun Léon Bottou Yoshua Bengio Patrick Haffner
references.title: Gradient-based learning applied to document recognition
references.venue: Proceedings of the IEEE,
references.authors: Hong Liu Mingsheng Long Jianmin Wang Michael Jordan
references.title: Transferable adversarial training: A general approach to adapting deep classifiers
references.venue: In International Conference on Machine Learning,
references.authors: Mingsheng Long Yue Cao Jianmin Wang Michael I Jordan
references.title: Learning transferable features with deep adaptation networks
references.venue: In Proceedings of the 32nd International Conference on International Conference on Machine Learning-Volume
references.authors: Mingsheng Long Han Zhu Jianmin Wang Michael I Jordan
references.title: Unsupervised domain adaptation with residual transfer networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Mingsheng Long Zhangjie Cao Jianmin Wang Michael I Jordan
references.title: Conditional adversarial domain adaptation
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Yishay Mansour Mehryar Mohri Afshin Rostamizadeh
references.title: Domain adaptation: Learning bounds and algorithms
references.venue: In 22nd Conference on Learning
references.authors: Sinno Jialin Pan Qiang Yang
references.title: A survey on transfer learning
references.venue: IEEE Transactions on knowledge and data engineering,
references.authors: Joaquin Quionero-Candela Masashi Sugiyama Anton Schwaighofer Neil D Lawrence
references.title: Dataset shift in machine learning
references.authors: Swami Sankaranarayanan Yogesh Balaji Carlos D Castillo Rama Chellappa
references.title: Generate to adapt: Aligning domains using generative adversarial networks
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Jian Shen Yanru Qu Weinan Zhang Yong Yu
references.title: Wasserstein distance guided representation learning for domain adaptation
references.venue: In Thirty-Second AAAI Conference on Artificial Intelligence,
references.authors: Hidetoshi Shimodaira
references.title: Improving predictive inference under covariate shift by weighting the loglikelihood function
references.venue: Journal of statistical planning and inference,
references.authors: Masashi Sugiyama Shinichi Nakajima Hisashi Kashima Paul V Buenau Motoaki Kawanabe
references.title: Direct importance estimation with model selection and its application to covariate shift adaptation
references.venue: In Advances in neural information processing systems,
references.authors: Eric Tzeng Judy Hoffman Ning Zhang Kate Saenko Trevor Darrell
references.title: Deep domain confusion: Maximizing for domain invariance
references.venue: arXiv preprint arXiv:1412.3474,
references.authors: Yifan Wu Ezra Winston Divyansh Kaushik Zachary Lipton
references.title: Domain adaptation with asymmetrically-relaxed distribution alignment
references.venue: In International Conference on Machine Learning,
references.authors: Han Zhao Remi Tachet Des Combes Kun Zhang Geoffrey Gordon
references.title: On learning invariant representations for domain adaptation
references.venue: In International Conference on Machine Learning,
sections.heading: 1 INTRODUCTION
sections.text: In a standard Supervised Learning setup, we consider that training data is representative of testing 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 (Quionero-Candela et al. (2009); Kull & Flach (2014)) is recognized as a major challenge in Machine Learning (Amodei et al. (2016)). Domain Adaptation (DA) (Pan & Yang (2009)) is a widely adopted strategy to mitigate its effects. It consists in leveraging unlabeled testing data (the target domain) in order to 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 to approximate the risk in the target domain by weighting sample contribution (Shimodaira (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 context, 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 Ben-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 our understanding, this risk is not addressed in the original work from Ben-David et al. (2007; 2010). We demonstrate that taking into account this risk has two major advantages. First, it provides a better control on (non-trainable) terms involving the labels in the
  target domain. Second, it introduces a new trainable term which embodies a risk of Compression and then may open-up the path to new learning methods. We provide a theoretical analysis illustrated with experiments on a standard Domain Adaptation benchmark. We underline that a better control 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.
sections.heading: 2 BACKGROUND
sections.heading: 2.1 A DECADE OF DOMAIN ADAPTATION
sections.text: The classical setup for modelling distributional shift is to introduce two domains: the source domain i.e. dataset where the model is 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 × Y , we introduce two distributions on X × Y: the source distribution Ps(X,Y ) and the target distribution Pt(X,Y ). We use the exponent notation s and t to differentiate source and target terms. We define the hypothesis space H as a subset of functions from X to Y . The distributional shift situation is then characterized by the shift: Ps(X,Y ) 6= Pt(X,Y ). Learning under Distributional Shift (Quionero-Candela et al. (2009)) consists in minimizing the risk on the target domain εt(h) = Et[`(h(X), Y )] for a given loss ` : Y × Y → R+ and an hypothesis function h ∈ H. Assuming that w(X,Y ) = Pt(X,Y )/Ps(X,Y ) is tractable, it is straightforward to show that:
  εt(h) = Es[w(X,Y )`(h(X), Y )] (1)
  Roughly speaking, this equation shows that it is possible to minimize the target risk using data (xsi , y s i )1≤i≤ns sampled from the source domain (i.e. (xi, yi) ∼ Ps(X,Y )) while re-weighting their contribution in the source expectation with a factor w(xi, yi) (Importance Sampling). The difficulty of Learning under distributional shift arises when w(xi, yi) is not tractable. The first reason is that data sampled from Pt(X,Y ) is often not easily available. In order to get a reasonable estimation of w, practitioners are used to reformulate the problem as Unsupervised Domain Adaptation. Definition 1 (Unsupervised Domain Adaptation). Given a loss `, an hypothesis class H, a source domain (X ×Y,Ps(X,Y )) and a target domain (X ×Y,Pt(X,Y )), Unsupervised Domain Adaptation consists in minimizing the target risk (i.e. finding h? = arg minh∈H Et[`(h(X), Y )]) with finite labeled sampling of (xsi , ysi ) ∼ Ps(X,Y ) of the source domain and a finite unlabeled sampling (xtj) ∼ Pt(X) of the target domain.
  If unlabeled samples in the target domain are available, a first idea is then to approximate w(X,Y ) by w(X) = Pt(X)/Ps(X). This is equivalent to assuming that conditional distributions are conserved across domains (i.e. Ps(Y |X) = Pt(Y |X)), a situation known as Covariate Shift, that has already been the subject of an extensive literature (Sugiyama et al. (2008); Huang et al. (2007)). This formulation becomes ill-posed when feature domains (X ,Ps(X)) and (X ,Pt(X)) suffer from non-overlapping support: w(X) is then undefined. To address this issue, Invariant Representations learning (Long et al. (2015)) performs adaptation by looking for a representation Z = ϕ(X) whose distribution is conserved across domains Ps(Z) = Pt(Z). A common strategy consists in 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?, ϕ? = arg min (g,ϕ)∈G×Φ (1− α) · εs(g ◦ ϕ) + α · D(s,t)(ϕ) (2)
  where G is the set of classifiers and Φ is the set of representations. The hypothesis space is then defined as H = {g ◦ ϕ : g ∈ G, ϕ ∈ Φ}. D(s,t)(ϕ) is a distance between distributions Ps(Z) and Pt(Z) and α is a trade-off parameter.
  The choice of D(s,t)(ϕ) 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
  et al. (2018)), Integral Probability Measures such as Maximum Mean Discrepancy (Long et al. (2015; 2016)) or Optimal Transport (Shen et al. (2018)). 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. (2007; 2010) that we recall in the next section.
sections.heading: 2.2 THEORETICAL GUARANTEES OF DOMAIN ADAPTATION
sections.text: We consider the set of representations Φ and classifiers G. The hypothesis space is denoted H = {g ◦ ϕ : g ∈ G, ϕ ∈ Φ}. We introduce the loss ` : Y × Y → R+ which is assumed symmetric and verifies the triangular inequality. We note the risk ε(h) = E[`(Y, h(X))] for h ∈ H and ε(h, h′) = E[`(h(X), h′(X))] for (h, h′) ∈ H2. To emphasize the role of a representation Z = ϕ(X), we introduce f̃(Z) = E[Y |Z] and H̃ = {g ◦ϕ : g ∈ G} ⊂ H. We underline that ·̃ quantities depend on ϕ where, for the ease of reading, this dependence is omitted in notations when it is not ambiguous. Ben-David et al. (2007; 2010) have derived a theoretical bound of the additional risk when using a representation Z = ϕ(X) rather than raw features X: Inequality 1 (Ben-David et al. (2007; 2010)). For a given ϕ ∈ Φ and g ∈ G, there is:
  εt(g ◦ ϕ)︸ ︷︷ ︸ Target risk ≤ εs(g ◦ ϕ)︸ ︷︷ ︸ Source risk + sup (h,h′)∈H̃ ∣∣εs(h, h′)− εt(h, h′)∣∣︸ ︷︷ ︸ = 12 ·d(H̃∆H̃): Disagreement + inf h∈H̃ εt(h) + εs(h)︸ ︷︷ ︸ =λ(H̃): Adaptability
  (3)
  The inequality 1 ensures that the target risk is bounded by the sum of the source risk, the disagreement risk between two classifiers from representations (d(H̃∆H̃) named H̃∆H̃ distance), and a third term (λ(H̃)) which quantifies the ability to perform well in both domains from representations. In the rest of the paper, we refer to the latter as the adaptability. Since Et[Y |X] is unknown, λ(H̃) is intractable in practical applications. By conveniently assuming that λ(H̃) is negligible, it is possible to derive a Learning Objective 1 which minimizes ε̃s(g◦ϕ)+ 12d(H̃∆H̃). Indeed, minimizing D(s,t) on ϕ leads to learn representations Z = ϕ(X) such that Ps(Z) = Pt(Z), where such situation is sufficient to ensure that d(H̃∆H̃) = 0.
sections.heading: 2.3 THE CURSE OF INVARIANCE IN DOMAIN ADAPTATION
sections.text: Compressing representations is an easy way to achieve invariance. Assume Xs ∼ N (0, 1), Xt ∼ U(−1, 1) and Y = 1X>0 then a trivial way to obtain representations invariance while separating source data is to consider ϕ : x 7→ 1x>0. The main drawback is a potential loss of information from the original feature space. To explain this phenomenon, we first introduce formally the notion of Hypothesis space compression: Definition 2 (Hypothesis space compression). Let (ϕ1, ϕ2) ∈ Φ2, ϕ1 compresses more H if H̃(ϕ1) ⊂ H̃(ϕ2). By language abuse, we will say that Z1 = ϕ1(X) is more compressed than Z2 = ϕ2(X).
  Second, we build two possible solutions (g1, ϕ1) and (g2, ϕ2) of Learning Objective 1 by considering the following compositions X →ϕ Z1 →ψ Z2 →g Ŷ such that ϕ and ψ ◦ ϕ are both in Φ and g and g ◦ ψ are both in G. We set g1 = g ◦ ψ, ϕ1 = ϕ and g2 = g, ϕ2 = ψ ◦ ϕ. These solutions are chosen to ensure that g1 ◦ ϕ1 = g2 ◦ ϕ2 and Z2 = ϕ2(X) is more compressed than Z1 = ϕ1(X). In the case when D(s,t) is the Jensen divergence, the data processing inequality (see Lemma 4.6 in Zhao et al. (2019)) implies that (g2, ϕ2) is a better optimum than (g1, ϕ1) according to Learning Objective 1 since εs(g1 ◦ ϕ1) = εs(g2 ◦ ϕ2) and D(s,t)(ϕ2) ≤ D(s,t)(ϕ1). To conclude, learning under objective 1 will favor compressed representations to enforce invariance. However, as noted in Johansson et al. (2019); Zhao et al. (2019); Liu et al. (2019), more compressed representations will degrade adaptability. Indeed,
  λ(H̃(ϕ2)) = inf h∈H̃(ϕ2) εt(h) + εs(h) ≤ inf h∈H̃(ϕ1) εt(h) + εs(h) = λ(H̃(ϕ1)) (4)
  since H̃(ϕ1) ⊂ H̃(ϕ2). A question which remains not addressed in the literature (except in Johansson et al. (2019) under the Covariate Shift assumption) is:
  How compression may increase the risk of bad adaptability?
sections.heading: 3 THEORETICAL ANALYSIS OF COMPRESSION
sections.heading: 3.1 WORKING PLAN
sections.text: Our strategy aims to compare a representation ϕ with representations ϕ′ which act similarly on the source domain but differently on the target domain (source equivalence). First, by allowing to compute the minimal combined error on source equivalent representations ϕ′, we limit the risk of bad adaptability of a fixed representation. Through an inequality called Target Compression, we show this new control of adaptability comes at 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 H̃∆H̃ inequality (Ben-David et al. (2007; 2010)) for stating a 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.
sections.heading: 3.2 NOTATIONS AND DEFINITIONS
sections.text: In the following, we fix a given ϕ ∈ Φ. We restrict our analysis to the case of ` : (y, y′) ∈ Y2 7→ (y− y′)2 as a convenient choice for manipulating properly f̃(Z) = E[Y |Z]. Note that in the binary classification case (Y = {0, 1}), ` is the accuracy. We define the set of representations which act similarly on the source domain but differently in the target domain:
  Definition 3 (Source equivalence). We introduce the set of source equivalent representations Φ̃s = {ϕ′ ∈ Φ, ϕ′ = ϕ on Ds} (where Ds = supp(Ps(X))) and the source equivalent hypothesis space H̃s = {g ◦ ϕ′ : g ∈ G, ϕ′ ∈ Φ̃s}. Two elements of Φ̃s are said source equivalent.
  The source equivalent hypothesis space H̃s is an extension of H̃ adding hypothesis built using representations which are source equivalent to ϕ. For a given h ∈ H̃s, we exhibit an interesting subset of H̃ considering hypothesis with the same source error than h. Definition 4 (Source conservation). For a given h ∈ H̃s, we note H̃h = {h′ ∈ H̃ : εs(h, h′) = 0}.
  It is worth noting that for all h ∈ H̃s, H̃h is not empty (see Appendix A for details). We are now ready to introduce the projection of an hypothesis h ∈ H̃s and to this purpose, we note ϕ′ ∈ Φ̃s and g′ ∈ G such that h = g′ ◦ ϕ′. Intuitively, the projection of h is defined as its best approximation from ϕ in the target domain among those which verify the source conservation i.e. from hypothesis g ◦ ϕ with g ∈ G such that εs(g ◦ ϕ, h) = 0. Definition 5 (Projection). π : H̃s → H̃ is defined as follows: π(h) = arg minh′∈H̃h εt(h, h′) for h ∈ H̃s. π(h) is called the projected hypothesis. If there is no uniqueness of the minimum, any solution works.
  Illustrations of introduced definitions are provided in Figure 1. If h = g ◦ ϕ ∈ H̃, the projection aims to map h to g′ ◦ϕ with g′ = g both in source and target L2 norms. If, h = g′ ◦ϕ′ with ϕ′ ∈ Φ̃, the projection aims to map h to g ◦ ϕ such that g = g′ in source L2 norm while g ◦ ϕ achieves a minimal distance with g′ ◦ ϕ′ in target L2 norm. We can observe that ∀h ∈ Hs, π ◦ π(h) = π(h) in both source and target L2 norms hence the (abusive) analogy with projection.
  For ease of reading, we remind the notations and definitions in appendix B.
sections.heading: 3.3 OUR CONTRIBUTION
sections.text: In the following, we fix a given H◦ such that H̃ ⊂ H◦ ⊂ H̃s. We are now ready to state a new bound of the target risk:
  Inequality 2 (Target Compression). Given g ∈ G and noting h̃ = π(h), we have:
  εt(g ◦ ϕ) ≤ εt(g ◦ ϕ, f̃s ◦ ϕ) + sup h∈H◦ εt(h, h̃)︸ ︷︷ ︸ γ̃(H◦): Compression + inf h∈H◦ {εt(h) + εt(h̃, f̃s ◦ ϕ)}︸ ︷︷ ︸ λ̃t(H◦): Adaptability
  (5)
  Proof. See Appendix A.
  This inequality introduces two interesting terms γ̃(H◦) and λ̃t(H◦) with opposite roles; the former involves a supremum while the latter involves an infremum onH◦. The term λ̃t(H◦) is very similar to the adaptability λ(H̃) from Inequality 1 and will be further investigated. Before, we focus on the term γ̃(H◦) which reflects the possibility of finding hypotheses in H◦ that can 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 as follows:
  Theorem 1 (γ embodies the risk of compression). Let (ϕ1, ϕ2) ∈ Φ2 two source equivalent source representations. If ϕ1 is more compressed than ϕ2, then γ(ϕ1,H◦) ≥ γ(ϕ2,H◦).
  Proof. If ϕ1 is more compressed than ϕ2, there is H̃(ϕ1) ⊂ H̃(ϕ2) ⊂ H̃s then ∀h ∈ H̃s, H̃h(ϕ1) ⊂ H̃h(ϕ2). The projection involves an infremum then εt(h, h̃(ϕ2)) ≤ εt(h, h̃(ϕ1)) where h̃(ϕ) = arg minh′∈H̃h(ϕ) ε t(h, h′). The supremum on h ∈ H◦ conserves the inequality.
  We now focus our attention on λ̃t(H◦). It differs with λ(H̃) in two ways. First, the source labelling function is involved only with the intermediate f̃s(Z) = Es[Y |Z]. Second, the risk associated with it (εt(h̃, f̃s◦ϕ)) involves a target expectation. In order to obtain a comparable bound with Inequality 1, we state a new bound of the target risk which is our main contribution:
  Inequality 3 (Invariant and Compressed Representations). Given g ∈ G and noting h̃ = π(h), β = 2 infh∈H̃ ε s(h) + εt(h, f̃s), we have:
  εt(g ◦ ϕ) ≤ εs(g ◦ ϕ) + d(H̃∆H̃) + β + sup h∈H◦ εt(h, h̃)︸ ︷︷ ︸ γ̃(H◦): Compression + inf h∈H◦ εt(h) + εs(h)︸ ︷︷ ︸ λ̃(H◦): Adaptability
  (6)
  Proof. See AppendixA. The main idea is to bound εt(h, f̃s ◦ϕ) and εt(h̃, f̃s) using H̃∆H̃ inequality. This introduces respectively εs(h, f̃s ◦ϕ) and εs(h̃, f̃s ◦ϕ) with residual terms 12d(H̃∆H̃)+ 12β (two times). We use the source risk conservation to bound εs(h̃, f̃s ◦ ϕ) ≤ εs(h, f̃s ◦ ϕ). Then we bound εs(h, f̃s ◦ ϕ) ≤ εs(h) leveraging the Pythagorean theorem since ` is the L2 norm.
  We are now ready to show the better control of the adaptability of the representation ϕ:
  Theorem 2 (Better control of adaptability). λ̃(H◦) ≤ λ(H̃).
  The proof is given by the infremum on H◦ ⊃ H̃. Compression γ̃(H◦) and adaptability λ̃(H◦) have an opposite behavior. This reflects an interesting trade-off:
  Theorem 3 (Invariance and Compression trade-off). With H1◦ and H2◦ such that H̃ ⊂ H1◦ ⊂ H2◦ ⊂ H̃s, there is λ̃(H1◦) ≥ λ̃(H2◦) and γ̃(H1◦) ≤ γ̃(H2◦).
  The proof is obtained by observing that H1◦ ⊂ H2◦. Even if invariance may have a bad impact on adaptability, our bound shows it is possible to have a better control of the adaptability while conserving the same degree of invariance. This control comes at 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. Furthermore, this new bound has a 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 not 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) is possible. The two additional terms β and γ̃(H◦) can indeed be trained in an Unsupervised Domain Adaptation setting1.
sections.heading: 4 EXPERIMENTS
sections.text: We are now conducting an experimental analysis on a widely used DA benchmark of digits recognition (MNIST, USPS). We study two tasks M→U and U→M under the Learning Objective 1. The representation ϕ is a convolutional neural network with a LeNet architecture (LeCun et al. (1998)). We set the dimension of representations to 50 and G is the set of linear classifiers from the representation space to classes (with a softmax layer on top) and the Domain Adversarial Neural Network (DANN Ganin & Lempitsky (2015)) for D(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 representation. In the following, we note CE the cross-entropy.
  We suggest to study the trade-off between compression and invariance with the family:
  Hη◦ = {g ◦ ϕ′ ∈ H̃s : Et||ϕ′(X)− ϕ(X)|| ≤ ηEt||ϕ(X)||}, η > 0 (7) We interpret this choice as a method for testing robustness of the learned representation to adversarial attacks in the target domain.
  Enforcing h ∈ Hη◦ . Enforcing h ∈ Hη◦ is challenging in practrice. We suggest to rely on a penalization L◦ to promote ϕ ≈ ϕ̂ (in the sense of Ps) and ||ϕ− ϕ̂|| . η · ||ϕ̂|| (in the sense of Pt). We define the penalization L◦ as follows:
  L◦(ϕ) = Es||ϕ(X)− ϕ̂(X)|| Es||ϕ̂(X)|| + ReLU ( Et||ϕ(X)− ϕ̂(X)|| Et||ϕ̂(X)|| − η )
  (8)
  Source conservation. For a given h, the projected hypothesis is defined as h̃ = g̃ ◦ ϕ̂ where g̃ is obtained by minimizing on g:
  Π(g, h) = λπ · CEs(g ◦ ϕ̂(X), h(X)) + (1− λπ) · CEt(g ◦ ϕ̂(X), h(X)) (9) with λπ = 0.9 for enforcing the source conservation.
  1The trainability of β is shown in Appendix A
  Estimation of λ̃(H◦). We suggest to minimize on (g, ϕ) ∈ H the following loss: Λ(g, ϕ) = CEt(g ◦ ϕ(X), Y ) + CEs(g ◦ ϕ(X), Y ) + λ◦ · L◦(ϕ) (10)
  with λ◦ = 102. CEt(g ◦ϕ(X), Y ) and CEs(g ◦ϕ(X), Y ) are respectively two proxies of εt(h) and εs(h). L◦(ϕ) promotes h ∈ Hη◦ .
  Estimation of γ̃(H◦). We follow an adversarial training procedure alternating between
  1. maximizing an objective Γ(g, ϕ) on h = g ◦ ϕ ∈ H◦ (sup step) 2. computing the projected hypothesis (inf step)
  During experimentation, we have observed that simply setting Γ(g, ϕ) = −Π(ĝ◦ϕ̂, g◦ϕ)+λ◦L◦(ϕ) (where ĝ ◦ ϕ̂ is an estimation of the projected hypothesis) leads to learn noisy labels. We suggest to prevent such pathological solutions by enforcing a low entropy adding to Γ a regularizer λent · CE(h(X), Ŷ ) with (Ŷ = y) = 1(h(X) = y) with λent = −1. Then, we set:
  Γ(g, ϕ) = −Π(ĝ ◦ ϕ̂, g ◦ ϕ) + λ◦L◦(ϕ) + λent · CE(h(X), Ŷ ) (11) Furthermore, for a fair comparison, we correct γ by comparing it with a baseline. This baseline is allowed to train representations to fit the adversary.
  Analysis We build new target domains modifying the label distribution which is known to badly impact λ(H̃) (Johansson et al. (2019); Zhao et al. (2019)). For a given target dataset D with classes balanced, we define D1 ⊂ ... ⊂ D6 as follows: for 1 ≤ i ≤ 6, Di is obtained by removing half of digit < i from Di−1 and setting D0 = D. Main results are reported in Figure 2. Although estimator are trained using cross-entropy, the results are reported computing the accuracy on a test set in order to be consistent with our theoretical analysis.
  We can observe that stronger the adversary is (α→ 1) (and the more the target shift (i→ 6 forDi)), the more significant the difference between λ(H̃) and λ̃(H◦). This demonstrates a 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 is paid to the cost of a higher γ. In our example, the risk of compression is estimated to a potential drop of performances from ∼12.5% to ∼27.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 a pessimistic estimation of the risk of compression.
sections.heading: 5 WEIGHTS FOR INVARIANCE RELAXATION
sections.text: The fact that compression and invariance are conflicting objectives supports the point from Wu et al. (2019) which claims that invariance is too strict a constraint. In this section, we show that invariance can be relaxed leveraging Weighted Representations. More specifically, we show that taking into account the risk of 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 weightsW , a subset of functions w : X → R+ such that Es[w(X)] = 1 and we note for w ∈ W,Pw·s(X) := w(X)Ps(X). The condition Es[w(X)] = 1 ensures that Pw·s(X) is a distribution. We state a similar result than Inequality 1.
  Inequality 4 (Weighted version of Inequality1). For a given ϕ ∈ Φ and g ∈ H̃,
  εt(g ◦ ϕ) ≤ εw·s(g ◦ ϕ) + 1 2 dw(H̃∆H̃) + λw(H̃) (12)
  with dw(H̃∆H̃) = sup(h,h′)∈H̃ |εw·s(h, h′)− εt(h, h′)| and λw = infh∈H̃ εt(h) + εw·s(h).
  Interestingly, w and ϕ play similar role in inequality 4 since they are actionable parameters to minimize εw·s(g ◦ ϕ) + 12dw(H̃∆H̃) while we can not quantify their impact on λw(H̃). We show that taking advantage of compression leads to an adaptability which does not depend on weights. This needs to introduce some definitions:
  Definition 6 (Strong source conservation). For a given h ∈ H̃s, we note H̃h = {h′ ∈ H̃ : h = h′ on Ds} where Ds = supp(Pt(X)). Definition 7 (Strong projection). Π : H̃s → H̃ is defined as follows π(h) = arg minh′∈H̃h εt(h, h′) for h ∈ H̃s. If there is no uniqueness of the minimum, any solution works.
  We are now ready to state the role of weights as a relaxed invariance for a lower compression: Inequality 5 (Weighting Invariant and Compressed Representations). Given g ∈ G and noting h = Π(h), βw = 2 infh∈H̃ ε w·s(h) + εt(h, f̃s), we have:
  εt(g◦ϕ) ≤ inf w∈W
  { εw·s(g ◦ ϕ) + 1
  2 dw(H̃∆H̃) +
  1 2 βw } + sup h∈H◦ εt(h,h)+ inf h∈H◦ εt(h)+εt(h, f̃s◦ϕ)
  Proof. This is a straightforward extension of inequality 2 applied to Pw·s. Furthermore, infh∈H◦ ε
  t(h) + εt(h, f̃s ◦ ϕ) does not depend on w due to strong risk conservation (risk conservation would have been dependent on w through the constraint εw·s(h, h̃) = 0).
  Adding weights exposes to the risk of increasing the variance of estimators when considering finite sampling analysis (see Cortes et al. (2010) for an extensive theoretical analysis of Importance Sampling). In inequality 5, this can be controlled with a good choice ofW e.g. by considering weights w ≤M for a given M > 0.
sections.heading: 6 RELATED WORK
sections.text: Generalization bounds for DA have been the object of an extensive literature for both Importance Sampling Cortes et al. (2010) and Invariant Representations Ben-David et al. (2007; 2010); Mansour 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 the risk of using non-invertible representations. The present work differs in three ways. First, our work follows the formalism introduced in Ben-David et al. (2007) which is widely adopted in the community. Second, contrary to the information loss, our theory provides a tractable risk of compressing representations. Finally, we do not rely on the Covariate Shift assumption which gives our work a broader range of applications.
sections.heading: 7 CONCLUSION
sections.text: By addressing domain generalization under the perspective of compression, we have bounded the target risk by a sum of trainable terms (εs(g ◦ ϕ) + d(H̃∆H̃) + β + γ̃(H◦)) and a term λ̃(H◦) which embeds a new adaptability criterion of representations. We have shown that λ̃(H◦) can be better controlled by enriching the hypothesis class H◦. This control comes at a cost of a higher risk of compression underlying a 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, we have shown how our framework can be applied for studying adaptation robustness to adversarial attacks. Finally, as an attempt to obtain representation distributions invariance with a lower compression, we have emphasized the role of weighted representations for relaxing the constraint of invariance.
  Achieving representation invariance can reduce the generalization gap between two domains. However, 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 ofH◦ as future works.
  Promising directions (1) Our analysis is restricted to the comparison among source equivalent representations of a given representation ϕ ∈ Φ. Then, for two given representations ϕ1 and ϕ2 of Φ which does not verify the source equivalence, our analysis does not allow to state if ϕ1 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 a robust estimation of γ̃(H◦) by following an adversarial training procedure appeared to be challenging in practice. Finding fast and robust estimations of γ̃(H◦) (or a proxy of it) may help to 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 Ds ∩ Dt = ∅, we set ϕ such that ϕ(X) = X on Dt and ϕ(Ds) ⊂ Dt. If ϕ is fixed in the source domain (i.e. ϕ|Ds is fixed) the optimal representation from the compression perspective is ϕ|Dt(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. (2018); Bousmalis et al. (2016)) or by finding Optimal Transport between the source and the target domains (Courty et al. (2016; 2017)). (4) The Covariate Shift assumption can be stated as H◦ = {h ∈ H, εs(h, ĥ) = 0 with ĥ = arg minh∈H εs(h)}. Such H◦ may provide a new framework for addressing the case of non-overlapping supports in Covariate Shift adaptation.
sections.heading: A MAIN PROOFS
sections.text: Proposition 1 (The source conservation hypothesis is not empty). For a given ϕ ∈ Φ and h ∈ H̃s, H̃h is not empty.
  Proof. If h ∈ H̃s, it exists g ∈ G and ϕ′ ∈ Φ such that h = g ◦ ϕ′. We set h′ = g ◦ ϕ ∈ H̃, there is εs(h, h′) = εs(g ◦ ϕ′, g ◦ ϕ) = εs(g ◦ ϕ, g ◦ ϕ) = 0 since ϕ = ϕ′ on Ds then h′ ∈ H̃h.
  Inequality 6 (Target Compression). Given ϕ ∈ Φ, g ∈ G and noting h̃ = π(h), there is for anyH◦ such that H̃ ⊂ H◦ ⊂ H̃s:
  εt(g ◦ ϕ) ≤ εt(g ◦ ϕ, f̃s ◦ ϕ) + sup h∈H◦ εt(h, h̃) + inf h∈H◦ {εt(h) + εt(h̃, f̃s ◦ ϕ)} (13)
  Proof. Let ϕ ∈ Φ, g ∈ G and h ∈ H◦:
  εt(g ◦ ϕ) ≤ εt(f̃s ◦ ϕ) + εt(f̃s ◦ ϕ, g ◦ ϕ) (14) ≤ εt(h) + εt(h, f̃s ◦ ϕ) + εt(f̃s ◦ ϕ, g ◦ ϕ) (15) ≤ εt(h) + εt(h, h̃) + εt(h̃, f̃s ◦ ϕ) + εt(f̃s ◦ ϕ, g ◦ ϕ) (16) ≤ εt(f̃s ◦ ϕ, g ◦ ϕ) + εt(h, h̃) + εt(h) + εt(h̃, f̃s ◦ ϕ) (17)
  This is a succession of triangular inequalities which involve respectively f̃s ◦ ϕ, h and h̃. The last inequality is a convenient arrangement of terms. We bound εt(h, h̃) by its supremal value for h ∈ H◦, then εt(g ◦ ϕ) ≤ εt(f̃s ◦ ϕ, g ◦ ϕ) + suph∈H◦{εt(h, h̃)} + εt(h) + εt(h̃, f̃s ◦ ϕ). Since this holds for all h ∈ H◦, we bound εt(g ◦ ϕ) by the infremum for h ∈ H◦.
  Inequality 7 (Invariant and Compressed Representations). Given ϕ ∈ Φ, g ∈ G and noting h̃ = π(h), β = 2 infh∈H̃ ε s(h) + εt(h, f̃s), there is for anyH◦ such that H̃ ⊂ H◦ ⊂ H̃s:
  εt(g ◦ ϕ) ≤ εs(g ◦ ϕ) + d(H̃∆H̃) + β + sup h∈H◦ εt(h, h̃)︸ ︷︷ ︸ γ̃(H◦): Compression + inf h∈H◦ εt(h) + εs(h)︸ ︷︷ ︸ λ̃(H◦): Adaptability
  (18)
  Proof. First of all, we recall the H̃∆H̃ inequality from Ben-David et al. (2007; 2010), for any fs and f t, there is:
  ∀h ∈ H̃, εt(h, f t) ≤ εs(h, fs) + 1 2 d(H̃∆H̃) + inf h∈H̃ εt(h, f t) + εs(h, fs) (19)
  A particular case of that inequality applied to fs = f t = f̃s ◦ ϕ leads to bound:
  εt(g ◦ ϕ, f̃s ◦ ϕ) ≤ εs(g ◦ ϕ, f̃s ◦ ϕ) + 1 2 d(H̃∆H̃) + inf h∈H̃ εs(h, f̃s ◦ ϕ) + εt(h, f̃s ◦ ϕ)
  ≤ εs(g ◦ ϕ) + 1 2 d(H̃∆H̃) + inf h∈H̃ εs(h) + εt(h, f̃s ◦ ϕ) (20)
  where bounding εs(g ◦ ϕ, f̃s ◦ ϕ) ≤ εs(g ◦ ϕ) is a direct property of `(y, y′) = (y − y′)2 and f̃s(Z) = Es[Y |Z]: εs(g ◦ ϕ) = εs(g ◦ ϕ, f̃s ◦ ϕ) + εs(f̃s ◦ ϕ). Note that, it is not possible to do so for εt(g ◦ ϕ, f̃s ◦ ϕ) since the expectation is computed in the target domain. We define β = 2 infh∈H̃ ε
  s(h) + εt(h, f̃s ◦ ϕ). We apply a second time H̃∆H̃ inequality, there is for any h ∈ H◦:
  εt(h̃, f̃s ◦ ϕ) ≤ εs(h̃, f̃s ◦ ϕ) + 1 2 d(H̃∆H̃) + inf h∈H̃ εt(h, f̃s ◦ ϕ) + εs(h, f̃s ◦ ϕ)
  ≤ εs(h̃) + 1 2 d(H̃∆H̃) + inf h∈H̃ εt(h, f̃s) + εs(h) (21)
  which is licit since h̃ ∈ H̃. Relying on the projected hypothesis h̃ allows us to preserve the invariance: even if h ∈ H◦, d(H̃∆H̃) is involved, not d(H◦∆H◦). Then, we use the property of source risk conservation h ∈ H which enforces εs(h̃, h) = 0 for noting that εs(h̃) ≤ εs(h) + εs(h, h̃) = εs(h) then:
  εt(h̃, f̃s ◦ ϕ) ≤ εs(h) + 1 2 d(H̃∆H̃) + inf h∈H̃ εt(h, f̃s) + εs(h)
  Finally, taking the infremum:
  inf h∈H◦ εt(h) + εt(h̃, f̃s ◦ ϕ) ≤ 1 2 β + 1 2 d(H̃∆H̃) + inf h∈H◦ εt(h) + εt(h) (22)
  Combining all inequalities leads to the stated one.
  Theorem 4 (Better control on the adaptability). λ̃(H◦) ≤ λ(H̃).
  Proof. We simply use the fact that H̃ ⊂ H◦ then using the property of the infremum:
  λ̃(H◦) = inf h∈H◦ εt(h) + εs(h) ≤ inf h∈H̃ εt(h) + εs(h) = λ(H̃) (23)
  Theorem 5 (γ embodies the risk of compression). Let (ϕ1, ϕ2) ∈ Φ2 two source equivalent representations. If ϕ1 is more compressed than ϕ2, then γ(ϕ1,H◦) ≥ γ(ϕ2,H◦) for H̃ ⊂ H◦ ⊂ H̃s.
  Proof. If ϕ1 and ϕ2 are two equivalent representations, there is H̃(ϕ1) ⊂ H̃(ϕ2) ⊂ H̃s then
  ∀h ∈ H̃s, (H̃(ϕ1) ∩ {h′ ∈ H : εs(h, h′) = 0}) ⊂ (H̃(ϕ2) ∩ {h′ ∈ H : εs(h, h′) = 0})
  which guarantees H̃h(ϕ1) ⊂ H̃h(ϕ2). Finally
  εt(h, h̃(ϕ2)) ≤ εt(h, h̃(ϕ1))
  invoking the property of the infremum where h̃(ϕ) = arg minh′∈H̃h(ϕ) ε t(h, h′). The supremum on h ∈ H◦ conserves the inequality. Proposition 2 (β is trainable from the data). Let (gn, ϕn)n∈N a sequence such that α · ε̃s(gn ◦ϕn)+ (1− α) · D(ϕn)→ 0 then βn → 0.
  Proof. First of all, since D(ϕn)→ 0 then Pt(ϕn(X))→ Ps(ϕn(X)). We note that for any n ∈ N, β ≤ 2·(εs(gn◦ϕn)+εt(gn◦ϕn, f̃sn◦ϕn)) ≤ 2·(2·εs(gn◦ϕn)+(εt(gn◦ϕn, f̃sn◦ϕn)−εs(gn◦ϕn))) Since εs(gn ◦ϕn)→ and (εt(gn ◦ϕn, f̃s)−εs(gn ◦ϕn))→ 0 (because Pt(ϕn(X))→ Ps(ϕn(X))) there is βn → 0.
sections.heading: B NOTATIONS
sections.text: • Φ is the set of representations. • G is the set of classifiers. • H is the hypothesis spaceH = G ◦ Φ • For a given ϕ ∈ Φ, we note H̃(ϕ) = {g ◦ϕ : g ∈ G} = G ◦ϕ. When there is no ambiguity,
  we note H̃(ϕ) = H̃. • For a given h ∈ H, we note ε(h) = E[(Y − h(X))2]. For d = s, t, we note a domain risk εd(h) = Ed[(Y − h(X))2].
  • For d = s, t and a given ϕ ∈ Φ, we note the conditional expectation f̃d(Z) = Ed[Y |Z] with Z = ϕ(X).
  • Equivalence. For a given ϕ ∈ Φ, the set of source equivalent representations Φ̃s(ϕ) = {ϕ′ ∈ Φ, ϕ′ = ϕ on Ds} (where Ds = supp(Ps(X))) and the source equivalent hypothesis space H̃s(ϕ) = {g ◦ ϕ′ : g ∈ G, ϕ′ ∈ Φ̃s}. Two elements of Φ̃s are said source equivalent. When there is no ambiguity, we note Φ̃s and H̃s.
  • Conservation. – For a given h ∈ H̃s, we note H̃h = {h′ ∈ H̃ : εs(h, h′) = 0}. – For a given h ∈ H̃s, we note H̃h = {h′ ∈ H̃ : h = h′ on Ds} where Ds = supp(Pt(X)). • Projection.
  – π : H̃s → H̃ is defined as follows: π(h) = arg minh′∈H̃h εt(h, h′) for h ∈ H̃s. π(h) is called the projected hypothesis. If there is no uniqueness of the minimum, any solution works. – Π : H̃s → H̃ is defined as follows π(h) = arg minh′∈H̃h εt(h, h′) for h ∈ H̃s. If there is no uniqueness of the minimum, any solution works.