Learning Conditional Invariances through Non-Commutativity
Authors: Abhra Chaudhuri
Serban Georgescu
Anjan Dutta
Venue: ICLR 2024 poster (2024)
Keywords: Invariance Learning
Domain Adaptation
Primary area: learning theory
TL;DR: Non-commutatively mapping source domain samples to the representation space of the target domain can efficiently learn conditional invariances, satisfying the sample-complexity needs for generalization on the target with samples from the source.

Abstract: Invariance learning algorithms that conditionally filter out domain-specific random variables as distractors, do so based only on the data semantics, and not the target domain under evaluation. We show that a provably optimal and sample-efficient way of learning conditional invariances is by relaxing the invariance criterion to be non-commutatively directed towards the target domain. Under domain asymmetry, i.e., when the target domain contains semantically relevant information absent in the source, the risk of the encoder $\varphi^*$ that is optimal on average across domains is strictly lower-bounded by the risk of the target-specific optimal encoder $\Phi^*_\tau$. We prove that non-commutativity steers the optimization towards $\Phi^*_\tau$ instead of $\varphi^*$, bringing the $\mathcal{H}$-divergence between domains down to zero, leading to a stricter bound on the target risk. Both our theory and experiments demonstrate that non-commutative invariance (NCI) can leverage source domain samples to meet the sample complexity needs of learning $\Phi^*_\tau$, surpassing SOTA invariance learning algorithms for domain adaptation, at times by over 2\%, approaching the performance of an oracle. Implementation is available at https://github.com/abhrac/nci.

Published as a conference paper at ICLR 2024
LEARNING CONDITIONAL INVARIANCES MON-COMMUTATIVITY
THROUGH
Abhra Chaudhuri University of Exeter
Serban Georgeseu
Anjan Dutta University of Surrey
2 Fujitsu Research of Europe
ABSTRACT
Invariance learning algorithms that conditionally filter out domainn-ppciin ran- dom variables as distractors, do so based only on the data semantics, and not the target domain under evaluation. We show that provably optimal and sample- efficient way of learning conditional invariances is by relaxing the invariance cri- terion be non-commutatively directed towards the target domain. Under domain asymmetry, i.e., when the target domain contains semantically relevant informa- tion absent in the source, the risk of the encoder yp that optimal on average across domains is strictly sower-bounded by the risk of the target-specific opti- mal encoder D-- We prove that non-commutativity steers the optimization to- wards " instead of sp", bringing the H-divergence between domains down to zero, lcading to stricter bound on the target risk. Both our theory and exper- iments demonstrate that non-commutative invariance (NCI) can leverage source domain samples to meet the sample complexity needs of learning Φ surpass- ing SOTA invariance learning algorithms for domain adaptation, times by over 2%, approaching the performance of an oracle. Implementation available at https://github.c com abbrac/nchaacc
INTRODUCTION
The idea of learning robust representations by identifying invariants across domains/views has found applications in several areas of machine learning including domain adap-
Sketches
tation (Ganin & Lempitsky [2015] |015 AArjvskyy et al. (019)),
self-supervised learning (Federici al. [2020] [ Chavhan
et al. 2023), and causal inference (Pogodin et al. 2023
Peters al. 2016) to name few. The traditional way of learning such representations is based on the assumption that domain shifts are semantically irrelevant transforma-
Photos
tions T applied to shared, underlying concept (p(x) (Nguyen et al.) 2021 Qiao et al. [2220] /Vlpii et al. 20188)
The process of invariance learning would thus be formu- lated as identifying the marginal distribution P(xx(x4)
Dogs
Giraffes
that matches across all training domains d (Ganin & Lem- pitsky 2015 Rosenfeld et al. 2021).
Figure 1: Dogs and giraffes may not be fully distinguishable the free-hand sketch domain due to shared geometric structures. However, they are clearly separable in the photo domain based on color and texture. Thus, mapping photos and sketches to the same invari- ant representation loses out such critical domain-specifie, but useful information when inference has to be performed in the photo domain test time.
A number of works, however, also identified that esti- mating the above marginal is not sufficient, as different classes have different invariance requirements. Instead, conditional form of invariance that matches the distribu- tion of P( for all labels y across domains a more realistic solution, idea which came to be known as conditional invariance (Li et al. 2018; Long et al. 2018 Samarin al. 22221) This further studied by Stojanov et al. (2021), 1), who narrowed down the reason for the requirement of conditional invariance as follows
AAhra Chaudhuri (acl 151 11155eeee @exeter.ac.uk) is the corresponding author.

---

Published as a conference paper at ICLR 2024
tasks not only depend on the shared information across domains, but also domain specific attributes, that can be retained only when the representation learning is conditioned as P(p(a ly), as opposed to the traditional marginal-only learning of P(y((x). This reason
also echoed in the work of Fastwood et al. (202)), based on the fact that encoders that perform better on average across domains do not do well on specific domains (Fastwood et al. (022), due to the No Free Lunch Theorem (Wolpert & Macready [197). Despite its promise, the idea of retaining domain-specific features for identifying meaningful invariants has remained relatively unexplored since SSooaanvv et al.. (021), with some applications to tasks like cross-modal retrieval (Chaudhuri et al. 2022).
The necessity of conditional invariance is observable when the target domain contains more seman- tically relevant information than the source domain, a condition we refer to as Asymmetry (Assump-
tion [T. This phenomenon is depicted with an example in Figure | from the PACS dataset (Li al. 2017]. In the free hand sketch domain, dogs and giraffes may look very similar in scenarios where the full body is not drawn. But in real photos, they can be easily distinguished based on colors and textures. Mapping photos and sketches to unconditionally invariant representation space gets rid of such useful domain-specific information, retaining only the shared aspects like object geometry. This significantly harms prediction performance when the target domain is that of photos, which can potentially provide asymmetrically greater semantic information relative to sketches.
We provide novel -canning-theoreic theoretic view based commutativity that establishes why uncondi- tionally invariant representations exhibit such limitations. We do so by framing the process of in- variance learning discovering operators, the choice of which determines whether the set of source and target domains form a commutative group. As a consequence of our formulation, we observe that a significantly simpler and efficient approach to achieving conditional invariance is by relaxing the invariance criterion (in approaches that learn the shared marginal ((ş(()) such as Domain Ad- versarial Training (Ganin & Lempitsky 2015) to be non-commutatively directed towards the target domain. One of the primary bases of our results is that, for a hypothesis class Hyp the risk of the encoder 40" E Ho that is optimal across domains lower bounded by the risk of the target-specific encoder hh that is optimal for the target, but not necessarily for other domains. When training sam- ples from the source domain are semantically complementary to the ones in the target domain (for example, photos and sketches of different objects, rather than that of the same object), we find that non-commutative invariance (NCI) can leverage source domain samples to meet the sample com- plexity needs of learning $.. NCI provides stricter upper bound target risk relative to existing unconditional (Ganin et al., (016) and conditional (Gulrajani & Lopez- Paz 2021 Stojanov et al.
2 paradigms through lower value of H-divergence (Ben-David et al. 2006 2010 Kifer al.
2004
Ganin et al. 2016).
Intuitively, NCI produces representations such that samples from the source domain get mapped to the representation space of the target domain, while those from the target domain continue to live in the representation space of the target domain. This allows the retention of task-relevant target domain features, while still being able to leverage the semantic augmentations from the training source domains. As inference needs be performed in the target domain at test-time, this a desirable property. We back our theory with number of empirical results which establish how NCI can leverage semantic complementarity across domains to achieve SOTA performance domain adaptation, approaching an oracle that has access to both source and target domains at test time.
In summary, we (I) show that conditional invariance can be achieved by simply relaxing the in- variance operator to be non-commutative; (2) derive stricter and efficient generalization and sample complexity bounds for learning the optimal target encoder; (3) conduct experiments demonstrating that with the right direction of invariance, non-commutativvity can leverage complementary semantic information across domains to achieve SOTA performance in domain adaptation.
2 RELATED WORK
Invariance Learning and Domain Adaptation: State-of-the-art in domain adaptation can be pri- marily classified into approaches that (1) learn invariant features that are robust to domain shifts (Ganin & Lempitsky 2015 Ganin et al., 2016); (2) represent domains as learnable transformations
of the shared, underlying semantics (Nguyen et al. 2021 Qiao et al.) 2020 Volpi et al., 2018);
and (3) smoothen the loss landscape (Rame et al. 2022 Rangwani et al. 2022 Wortsman et al.
2022), or by penalizing localized features (Wang et al. 2019). Our work primarily belongs to (1),
2

---

Published as a conference paper at ICLR 2024
which is what will focus on in this section. The idea of learning invariant features for domain adaptation (DA) was first proposed in Ganin & Lempitsky (2015): Ganin et al. (2016) via gradi- ent reversal. A causal take on invariance learning view that the underlying causal factors remain the same under domain shift, which also constitutes the foundation for probable domain generalization (Fastwood et al.] 2022). [Arovssyy al. (2019) concretely instantiated this idea through Invariant Risk Minimization (IRM), which was followed by several subsequent extensions (Wang al.] 2022 Lu et al., 2022) However, Rosenfeld et al. (202T) showed that when the training and test distributions sufficiently diverge, nothing is funda- mentally better than vanilla Empirical Risk Minimization (ERM), a claim that was experimentally supported by Gulrajani & Lopez-Paz (2021). Other promising approaches to invariance learning involve imposing various regularizers based on the information bottleneck principle (Tishby et al.) 2000 Federici et al.) 2020; Ahuja et al. (202T. However, the above approaches discard all domain- specific information, retaining only the shared features. It was consequently discovered that learning task dependent, conditional form of invariance instead of marginal invariance is much more ben- eficial, as certain domain-specific features may actually be helpful for downstream tasks (Pogodin et al. 2023] Stojanov et al.) 2021] Chavhan et al., (003) Quinzan al., (022). Our work further explores this idea through the lens of commutativity of domains under the invariance operator, and presents simple and efficient approach for conditional invariance learning. We also show that our approach can leverage source domain samples to meet the sample complexity needs of generaliza- tion the target domain (Theorem 2) So, we provide an extended literature review on approaches that endeavour to achieve the same in Appendix A.1
proposed by Peters al. (2166) with the
3
NON-COMMUTATIV INVARIANCE
3.1 PRELIMINARIES
Overview: We provide the complete set of general notations in Appendix A.2 We start by intro- ducing the notion of commutativity, which an abstract generalization of a large family of marginal invariance learning paradigms like Domain Adversarial Neural Networks (DANNs) (Ganin & Lem- pitsky 2015), Invariant Risk Minimization (Arjovsky et al. 2019; Ahuja al. 2021). and several of their derivatives under DomainBed (Gulrajani & Lopez- Paz, 2021). The idea of commutativity allows us to identify useful, domain-specific features that may be discarded by such marginal invari- ance learning algorithms. As remedy, define the dual notion of Con-Commutative Invariance (NCI), which we find to has stronger theoretical properties in terms of (1) a stricter generalization bound on the target risk under asymmetry condition; and (2) the ability to meet the sample com- plexity for learning the optimal target domain encoder कh with samples from the source domain. Associated preliminaries and proofs are provided in Appendix A.3 and Appendix A.4 respectiiiv. Definition 1 (Asymmetry). Domains D, and D, said to be asymmetric iff':
[x()x and x, = (x) + [(0)(x.):)) = I(0) (x+))))
where X, ~ D., X, ~ D,, and T, and T, are transformations applied on the underlying concept X X to derive such domain sppecfff instantiations.
Even though X, and X, may be derived as transformations of the same underlying concept (Nguyen et al. 2021; Qiao et al., 2020 Volpi et al., 2018). it is not necessary that the two domains would contain the same amount of label information y. This is because different transformations (x) and T, (x) may differ in the degree to which they preserve the label information in x. The optimal encoder 4- of the respective domain S/T would be able reflect this asymmetry by cap- turing different amounts of label information. As result, performing downstream task with the optimal encoding would result in different accuracies across the two domains. In other words, the domain-specific optimal encoding $x (x)e/r is not invariant to the domain information.
Assumption 1. For the remainder of our analysis, we assume that the target domain contains more semantically relevant information than the source domain, ie.,,
((); > (x.)))))
thus warranting the preservation of target domain specific information. This assumption quantifies the example illustration in F
3

---

Published as a conference paper at ICLR 2024
( r)
(s))
(T)
( U (
S
T
S
T
Commutative Invariance
Con-Comuutative Invariance
Figure 2: Abstract comparison of commutative and non-commutative invariance (NCI) learning. Commutative invariance aims to capture components that are shared across both the source D, and target D, domains (simplified in the diagram as s and T respectively) by mapping samples from one domain to the semantic space -p-)) of the other. NCI, on the other hand, captures components that the source domain shares with the target domain by mapping source samples to the target's representation space, but retains all the components in the semantic space of the target domain unchanged. NCI is thus invariant to the domain-specific, semantically relevant components of the source domain, but not the target domain.
Definition 2 (Commutative and Non-Commutative Invariance). Let x, D, and X, Dr be domain-specific samples for an instance x. We call the operator @ commutatively invariant iff:
X₃ X = @ X, = "0 (x),
i.e. produces the same output as (-) that is optimal when the downstream task is performed on the the joint distribution (D., Dz) (but not necessarily optimal in the individual domains, due
the No Free Lunch Theorem Wolpert & Macready (1997)) and hence is independent of the
order of the operands. Algorithms that try to recover the marginal distribution P(X). eliminating all comain--peciffc information across both D, and D, in the process (Ganin Lempitsky, [015 Arjovsky et al. 2019, Ahuja et al. (021) fall in this category. Essentially, they induce commutative semigroup on the of domains under @ (Theorem 4.. Now, the operator is right-invariant iff:
X, & X, (x) and X, @ X, (x)
@ is right-invariant as it always returns encoding of that is optimal in the domain of the left operand, no matter what domain the right operand comes from. notion of left-invariance can be symmetrically defined. We call such operators that invariant the domain of one operand, but is sensitive to the domain of the other, non-commutatively invariant (NCT). Figure 2 graphically depicts an abstract comparison between commutative invariance and NCL. An associated notion is that of the discrepancy between the domains that & aims to reduce, which we discuss below.
H., divergence and generalization bound on the target risk:
The Hiv-direreence between DD and D, is a measure of the capacity of the discriminator hypothesis class H., to distinguish between the source and the target sample representations. It has found use in number of formal treatments of domain adaptation (Ben-Davit et al., 2006] 2010 Kifer et al. 2004 Ganin et al. 2016).
used to quantify the discrepancy between domains, often in the representation space of encoder sp(.), and is proportional to the difference in domain-specific information between D, and D,. Primarily, used by Ben-David al. (2006) derive an upper bound for the target risk Ro, (-) (test-time error in the target domain) of an encoder sf.)) that is trained with labelled source and unlabelled target samples. The complete definition of -/-divergence, along with its empirical estimate, and the associated generalization bound on the target risk are provided in Definition (5) and Theorem respectively. Below, we show that the bound Theorem can achieve a stricter form under non-commutatively invariant encoding of the domains.
3.2 TARGET RISK UNDER NON-COMMUTATIVITY
Result 1. If the VC (Vapnik-Chervonenkil Chervonenkis) dimension @aannik & Chervonenkis 1971) of H.gs VC(H)) 2 N, the total number of training samples, then the target risk of the optimal NCI encoder
4

---

Published as a conference paper at ICLR 2024
RD, (P7) is related to the target risk of the commutatively invariant encoder RD, (10") as:
RD, (pt) S RD, (p*) - dii, ("" (v",
where du,, is the empirical -ivveereee between source and target samples S and T respectively.
The proof of Result is based on the observation that (5, T, (p) does not reach 0 if (p()) is trained with commutative invariance. Commutative invariance maps data from the source to the target domain and vice versa thereby solving a swapped prediction problem. That way. although the "min" part of Equation (5). which quantifies the generalization eπror (Definition D. takes value of O, the overall Hy -iy-divergence does not become O. To bring dz,, (S. (P) down to O, the objective in the "min" part has to evaluate to 1. One way to achieve that is by finding a (p()) that maps all the data to the source domain. Although Result provides stricter generalization bound on the target risk, it does not establish the practicality of non-commutativity. Below, we show that is possible to give further guarantees for the optimality of non-commutativity when test- test-time evaluation is performed in the target domain. We establish that training with NCI results on samples from the source domain being treated as augmentations in the target domain. As consequence, as the number of source samples increase, the NCT encoder (-) approaches the optimal encoder for the target domain, which we denote by "
3.3 SAMPLE COMPLEXITY OF NCI AND ITS OPTIMALITY
We start this section by exploring the relationship between the target risks of the global encoder op" that is optimal on average in Hyp and the optimal encoder for the target domain " We show that R((²") ) is no less than the risk of the optimal encoder for the target domain R((7). We finally demonstrate how non-commutativity surpasses this bound and achieves the optimal risk for the target domain R())), by meeting its comple-complexigg needs with source domain samples.
Theorem 1. Let the Hy -iv-divereence between the source (s) and the target (T) domains be A, i.e.,
$ T A A.ppendix(A.3.Iy Under asymmetry (Assumption D. i.e., I($) the risk of the optimal-one on-average encoder R(y²") for predicting Y across all domains up to distance A from the domain T admits the following upper bound:
< (x+)))
T+A
A(p²)
min EH A
/
(Do)
6=T
where I(---) calculates the encoding risk of a domain, and (-) is the optimal encoder for T.
From Lemma we know, the average risk is greater than the shared risk, i.e., R(y") > min 1(yp (D, DD),.) Now, the shared risk has to be greater than or equal to the max- imum of the source risk and the target risk. If the target risk is greater than the source risk, then the shared risk is at least large as the target risk. If the source risk is greater than the target risk, then the shared risk is strictly greater than the target risk. In other words, the caatmallon-average predictor xp* across all domains up to a distance A from the target domain 7 cannot do any better than the optimal predictor of the target domain yp, This means that learning the globally optimal predictor is a sub-optimal solution when the downstream task has to be performed in single target domain т. The bound for R((p") in Theorem [ becomes strictly greater when the transformation T from which the target domain was obtained preserves the causal factors for the label y of x, and there exists some domain in the distance d < A from 7 where the causal factors are not preserved, i.e.:
x, (x) y( y(x and TTg [T, x,, (x),, T(x,y) T(x,,y), (1)
where x lies in the ground-truth concept basis C (Lemma Hence, looking for the optimal pre- dictor specifically for the target domain is always guaranteed give at least good solution for domain adaptation, if not better. The below theorem establishes that NCI solves this very problem by leveraging samples from the source domain meet the sample complexity needs of learning the optimal target encoder Φ;,, and exhibits the same error bound on D, as that of th.
Theorem 2. Consider a function class T of transformations that defines target domains such that T,x,= X+ T(x), Xx Dr. Let (.)..) be the optimal encoder for the target domain with
5

---

Published as a conference paper at ICLR 2024
sample complexity for incurring error of with probability 6. From Haussler's theorem, the ervor incurred by the optimal target domain encoder & with probability á and M target domain samples is given by:
In T 1
M
With my target domain samples and my source domains samples, such that M S. my + my M my the optimal NCI encoder xp, achieves the same error bound e with probability ò.
Note that the constraints on the sample size in Theorem 2 requires the number of source samples be O. When my samples from the target alone cannot attain the sample complexity M for achieving the optimal еrгоr bound of D;, NCI can leverage m, novel samples from the source domain to achieve the same error bound as that of $ This suggests that NCI treats the additional samples from the source domain as augmentations in the target, property that is also reflected in the proof of Theorem 2 Note that the constraints on the sample size in Theorem requires the number of both source and target samples to be > 0, and the total number of source and target samples must at least add up to achieve the sample complexity of D Thus, the source and target samples must each come from unique support in order qualify distinct. We empirically validate this fact in Section 4 by varying degrees of complementary (and shared) information between the source and the target domains, and tracking its effects classification accuracy.
With the above results, although we can guarantee the optimality of NCI, we cannot guarantee its uniqueness under the given semantic constraints. This is because there could be multiple ways to bring the source-target H,,-divergence down to O, which may be dependent on the constraints imposed by the downstream task. A related finding by Volpi al. (2018) shows that domain-shifted augmentations penalize deviations from the parameter vector corresponding to that of the true label instead of regularizing towards zero unlike classic regularizers. We conjecture that this property also applies to NCI, and can be an alternative approach to proving Theorem 2 and perhaps, understanding the uniqueness of the solution.
3.4 TRAINING WITH NCI
Below provide example of converting commutative invariance objective into its non- commutative form. We choose the Domain Adversarial Neural Network (Ganin & Lempitsky 2015) as the candidate for this example because of its simplicity and ubiquity across the conditional invari- ance learning literature (Long et al., [2018] Li et al. 2018 Stojanov et al. [202]). The discriminator v(() is trained to distinguish between the source and the target domain from the representation space of ypr by minimizing the following:
Cy = y log (x) + (1 y) log(1 - (x)+(x)))
The encoder for the target domain , is trained to maximize the C, through con-commutativeey mapping the source samples to the target domain by minimizing the following objective:
S = (1 y) log(n((e+(x)))
(3)
Note that the above objective is non-commutatively invariant to the source domain because the loss is only minimized for source domain samples with label 0, and not for the target domain samples with label 1. In other words, sp(-) learns representations such that the discriminator sees source domain samples as being from the target domain, but not the other way around. Optimizing the above set of objectives should thus lead to the convergence of ip()) towards the optimal encoder for the target domain yp. (t) according to Theorem 2
EXPERIMENTS
Datasets and Experimental Settings: We perform experiments with NCI on three standard domain adaptation benchmarks, namely, PACS (Li et al.) 2017). Office-Home (Venkateswara et al. 2017). and NomainNet (Peng et al. 2019). We evaluate NCI on the task multi-source domain adaptation (Zhao al., 2018) experiments with complementary semantics across domains. We model this setting by not sharing the full instance support across domains. Specifically for PACS and Office- Home, 70% of the sample supports are shared between both sources and targets, and each of the

---

Published as a conference paper at ICLR 2024
PACS
Office-Home
Method
Photo
Art
Cartoon
Sketch
Photo
Clipart
Product
Real
ERM (Wiley 1998)
81.33
77.60
88.76
78.30
49.15
45.66
54.32
60.60
DANN 15)
78.86
75.32
90.37
80.66
47.31
46.15
54.79
58.17
CDANN 18C
78.95
76.72
90.02
80.00
47.64
46.02
54.50
59.45
MDAN (NeurIPS' 18)
79.37
77.05
88.90
79.15
48.00
45.77
54.45
60.90
MDD (ICML'19 19)
79.55
77.62
87.61
79.48
47.99
45.31
54.37
59.16
CICyc (GCPR221)
80.02
76.67
89.35
78.86
48.96
45.50
55.11
60.02
IB-IRM (NeurIPS'2I1
77.01
75.11
90.78
80.95
45.40
46.91
55.25
57.96
EQRM (NeurlPS'22)
80.35
78.00
90.11
78.10
49.55
45.10
55.21
60.90
CIRCE (ICLR'22 23)
80.78
79.48
89.72
80.55
48.20
44.97
54.21
60.75
SDAT+ELS (ICLR'23)
81.25
80.21
89.32
80.27
48.50
45.43
55.39
60.97
NCI (Ours)
83.40
81.55
91.05
81.37
50.02
47.90
56.00
63.50
Table
Comparison with SOTA invariance learning approaches on PACS and Office-Home.
PACS
Office-
Method
Photo
Art
Cartoon
Sketch
Photo
Clipart
Product
Real
Fishr (ICML'22)
81.19
80.06
89.05
79,68
48,25
45.15
54.39
59,92
+ NCI
84.90
82.22
92.00
82.55
51.37
48.07
56.86
64.02
SDAT (ICMI:22)
81.00
79.95
88.11
79.32
48.07
45.20
54.55
60.37
+ NCI
83.80
82.06
91.92
82.07
51.44
48.05
56.95
64,22
Model Soups (ICML'22)
81.26
79.37
89.76
79.05
48.55
45.71
54.48
60.91
+ +NCI
85.09
82.56
92.77
82.62
51.95
48.49
57.20
64.50
Table 2: Accuracy gains from NCI on top of flat-minima based OoD generalization algorithms.
3 targets provide 10% unique data support instances. For DomainNet, 75% of the instances shared across domains, and each of the 5 source domains provide 5% novel support instances. For comparing NCI against an oracle that has access all the domains at test time, we perform separate set of experiments on the multi-modal material segmentation task introduced by Liang al.) (2022) on their proposed dataset. For all our experiments, we use the NCI version of Domain Adversarial Neural Networks (DANN) (Ganin & Lempitsky 2015), as described in Section 3.4 with all hyperparameters and experimental settings based on the DomainBed (Gulrajani Lopez- Paz, 2021) version of DANN, as that provides fair ground for comparison with existing arts. Through our experiments, we not only aim to verify the domain adaptation performance NCI relative to SOTA, but also our theory (Theorem 2 on the ability of NCI to leverage samples of complementary semantics from source domains to learn the optimal target encoder, along with our Asymmetry assumption (Assumption [ We also wish to understand how NCI compares with oracle that has the liberty to optimally choose useful features from all domains at test time.
Comparison with SOTA invariance learning approaches: We report the performance of NCI compared to existing SOTA invariance learning algorithms in T and Office-Home) and Table (DomainNet). We provide a discussion on the algorithms that we compare NCI with, as well as the results on DomainNet in Appendix A.5 The observations agree with our premise that invariance to all domain-specific information may may not be helpful depending on the target domain. For instance, in Table [] although DANN outperforms ERM in Cartoon and Sketch in PACS, lags behind in Photo and Art by similar margins. This indicates that the domain -pecifff information it "discards" is somehow helpful for classification of Photos and Art paintings. This happens because the Cartoon and the Sketch domains can expressed as approximate subsets of Photo and Art. So, discarding information that is specific to Photo and Art helps the classifier to be robust when applied to Cartoon or Sketch. However, this backfires when the evaluation is performed on Photo and Art, as the invariant representation is unable to capture the semantic diversity that their domain-specitfe information introduces. This effect can also be seen to be amplified in IB-IRM, which imposes stronger commutative invariance across domains via information bottleneck.
Orthogonality to flat-minima based algorithms: Methods like Fishr (Rame et al. 2002 Rangwani al. 2022), and Model Soups (Wortsman et al. 2022), all aim to achieve general inneralization across do-
7

---

Published as a conference paper at ICLR 2024
Accuracy
92
02
82
01
01
01
80
80
70
10
20
30
40
50
10
20
40
55
10
60
50
Art
Cartoon
Sketch
Figure 3: Effects of increasing the number of semantically complementary source samples (horizon- tal axis) on classification accuracy (vertical axis) across different complementary source domains.
mains by smoothing the loss landscape. For such algorithms, the domain asymmetry property, that the commutative invariance learning algorithms do not utilize described above, do not have clear effect as illustrated in Table 2 Their performance is generally close to, or in some cases, better than the best of both classes of algorithms ones that do (eg. DANN) and the ones that do not (eg. ERM) learn any form of invariance. Our conjecture is that loss landscape smoothing has the effect of mapping all the domains to unified landscape with a prominent global minimum, which aids performance across all domains. When combined with NCI, the gains obtained on top of such algorithms do not seem to depend upon the degree of shared domain-speciffi information, suggesting that the idea of commutativity is orthogonal to the flatness of the loss landscape. Specifi- cally, if one were to choose semain--ppccffe / shared information as the criterion, the gains provided by these methods seem to be random. This, however, is in addition to NCI providing non-trivial accuracy boosts when combined with the loss landscape smoothing algorithms, which shows that these algorithms can also benefit from the idea of non-commutativity. The priori reasons behind these observations, unfortunately, fall outside of the scope of this work; something we would like to leave as an open problem at the intersection of invariance learning and function smoothness.
to
Varying degrees of complementarity across domains: Theorem 2 shows that NCI is particularly helpful when the semantic information provided by different domains is complementary to each other, enabling source domain samples to act as augmentations for meeting the sample complexity needs of learning the optimal target domain encoder. To evaluate this empirically, we conduct ex- periments on the PACS dataset with "Photo" as the target domain, where we start by sharing 50% of data support (sample IDs) across all domains. We designate one of the source domains the "com- plementary source". Retaining the originally shared 50%, we progressively incorporate additional samples from the complementary source, varying from 5-50%, while removing the same amount of shared samples from the complementary source train set. This keeps the total number of instances in the train set constant, while increasing the degree of complementarity between the target and the complementary source. We repeat this experiment by assigning different domains the comple- mentary source, and report our results in Figure 3 where the horizontal axis represents the varying degrees of complementarity from 5-50%, and the vertical axis shows classification accuracy.
We observe that as we increase the degree of complementarity, the classification accuracy ap- proaches the setting where the model has access to all the corresponding samples from the target (as well as the other source domains) (Table DT. The rise in the classification accuracy is smoother for domains that are similar to photos, i.e., Art and Cartoon (perhaps because both have color informa- tion), and is more abrupt for sketches, which is relatively more disjoint from photos. However, once the total number of samples cover the full support (50% complementarity). the accuracies across all the complementary sources are similar and close to the maximum attainable value in Table This shows that NCI can leverage semantically complementary samples from any of the source domains, and make them act augmentations in the representation space of the target, achieving similar performance as that of using all target-specific samples.
Discovering semantic asymmetries: One of the conditions under which NCI has an advantage is that of the existence of semantic asymmetries semantically relevant factors of variation that are formalize in Assumption [[ We test the cxis-
present in some domain, but not in the others, tence of these factors by performing an additional set of experiments on the multi-modal material
8

---

Published as a conference paper at ICLR 2024
Standalone
NCI
Backbone
Oracle
Image
AOLP
DOLP
NIR
Image
AOLP
DOLP
NIR
TopFormer (C)PR'22)
45.10
33.60
29.80
28.77
48.10
39.30
35.82
29.60
48.44
DPT (ICCV'21)
37.80
30.55
23.86
23.40
42.72
32.33
27.52
25.23
43.50
SegFormer (Neur[PS'2) 21)
41.81
24.90
29.00
22.99
46.37
34.33
36.24
35.81
47.25
FPN (CVPR' 19)
30.20
28.68
33.21
26.79
39.86
32.79
41,35
29.22
41.68
DeepLabV3+ 3+ (ECCV"18)
35.86
27.76
22.56
25.87
41.96
30.76
29.82
30.50
42.90
PSPNet (CVPR' 17)
27.99
25.71
32.50
23.60
37.68
30.50
39.20
27.45
40.06
UNet (MICCAT' 15)
29.00
26.02
23.51
21.27
36.93
31,58
27.29
25.63
37.70
Table 3: Left: Discovering semantic asymmetries inform the direction of invariance learning in NCL. Right: Comparison with oracle performance.
segmentation dataset, the results of which we report in Table 3 We hypothesise that if the distri- bution of semantic information is asymmetric across domains, then the standalone performance of single domain training should vary across domains. This domain where the model performs the best should be the one that contains the most domain-specific information that is semantically relevant. Under circumstances where the cost of acquiring data from each domain is the same, this insight can be used to determine the most optimal direction for learning non non-commutative invariances. The target domain for NCI in that case should be the domain that provides the highest accuracy with standalone training. From Table 3 it can be seen that for given model, the performance of NCI correlates with standalone performance. The domain that gives the highest standalone accuracy (un- derlined) is also the one that has the highest accuracy when it becomes the target domain for NCI. This observation holds for all backbones and domains, indicating the validity of our hypothesis.
Comparison with oracle performance: To empirically validate whether NCI is, in fact, the correct form of invariance to learn, we compare its performance with that of an oracle, across a number of backbones. We choose the task of multimodal material segmentation, which is a recently emerg- ing image segmentation task that requires leveraging material information from multiple imaging modalities to segment material types (Liang et al. 2022 ZZhng et al. (023a). A multi-modal mate- rial segmentation model can be viewed as an oracle, since it has access to all the domains (modalities for a multi-modal model) at test-time, allowing it to choose from meaningful and superftuous fea- tures that may or may not be specific to the domain. The ability of the model to make predictions based on multiple input modalities thus provides a unique setup to simulate the oracle behavior. Note that our setup of evaluating domain invariant features do not assume access to multiple input modalities at test time. The ordinary (non-oracle) models of NCI only have access the target domain (single modality) data at test time. On the other hand, the oracle model has the advantage of accessing information across all modalities, both source and target during test. Specifically, we choose the model by Liang al. (2022) to maintain consistency in terms of the network backbone. From T the performance of NCI can be seen to approach that of the oracle with access to just single modality, indicating that it is able to capture the semantically meaningful invariances.
CONCLUSION
We presented the idea of learning non-commutative invariances (NCT), an invariance learning ap- proach that is conditioned upon the target domain of inference. Along with the shared concepts across domains, NCI preserves -specffc information for the target only. We prove this ap- proach to be theoretically beneficial for domain adaptation when (1) the target domain contains semantically relevant information that is not present in the source domain, a condition that we call Asymmetry (Assumption]) D] and (2) the source domain samples are semantically complementary to those from the target domain, which allows NCI to satisfy the sample complexity needs for the op- timal target domain encoder, with additional samples from the source domain (Theorem Z. Under these conditions, we empirically showed that NCI achieves SOTA performance in domain adapta- tion relative existing invariance learning objectives. NCI is a novel conditional invariance learning paradigm, and as such, leaves room for a number of open questions: (1) Is the NCI solution of learn- ing & unique? (2) Does y - Φ² in a measure theoretic sense, and not just in terms of sample complexity or error bound? (3) What is the relationship between class-conditional invariance learn- ing and NCI? (4) Is NCI provably orthogonal to flat-minima based algorithms? We believe that these can be explored as both theoretical and empirical research problems on invariant representations.

---

Published as a conference paper at ICLR 2024
REFERENCES
Kartik Ahuja, Ethan Caballero, Dinghuai Zhang, Cha--Chrsttophe Gagnon-Audet, Yoshua Bengio, Ioannis Mitliagkas, and Irina Rish. Invariance principle meets information bottleneck for out-of- distribution generalization. In NeurIPS, 2021.
H. Akada, S. Bhat, I. Alhashim, and P. Wonka. Self-supervised learning of domain invariant features for depth estimation. In WACV, 2022.
Martín Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk minimization. ArXiv, abs/1907.0285 022993, 2019.
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. In NeurIPS, 2006.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Vaughan. A theory of learning from different domains. Machine Learning, 2010.
Konstantinos Bousmalis, Alex Irpan, Paul Wohlhart, Yunfei Bai, Matthew Kelcey, Mrinal Kalakrish- nan, Laura Downs, Julian Ibarz, Peter Pastor, Kurt Konolige, et al. Using simulation and domain adaptation to improve efficiency deep robotic grasping. ICRA, 2018.
Abhra Chaudhuri, Massimiliano Mancini, Yanbei Chen, Zeynep Akata, and Anjan Dutta. Cross- modal fusion distillation for fine-grained sketch-based image retrieval. In BMVC, 2022.
Ruchika Chavhan, Jan Stuehmer, Calum Heggan, Mehrdad Yaghoobi, and Timothy Hospedales. Amortised invariance learning for contrastive self-supervision. ICLR, 2023.
Yun-Chun Chen, Yen-Yo Lin, Ming-Hsuan Yang, and Jia-Bin Huang. Crdoco: Pixel-level domain transfer with cross-domain consistency. CVPR, 2019.
Cian Eastwood, Alexander Robey, Shashank Singh, Julius Von Kügelgen, Hamed Hassani, George J. Pappas, and Bernhard Schölkopf. Probable domain generalization via quantile risk minimization. In NeurlPS, 2022.
Marco Federici, Anjan Dutta, Patrick Forré, Nate Kushman, and Zeynep Akata. Learning robust representations via multi-view information bottleneck. In ICLR, 2020.
Chuang Gan, Jeremy Schwartz, Seth Alter, Damian Mrowca, Martin Schrimpf, James Traer, Ju- lian De Freitas, Jonas Kubilius, Abhishek Bhandwaldar, Nick Haber, Megumi Sano, Kuno Kim, Elias Wang. Michael Lingelbach, Aidan Curtis, Kevin Tyler Feigelis, Daniel Bear, Dan Gutfre- und, David Daniel Cox, Antonio Torralba, James J. DiCarlo, Joshua B. Tenenbaum, Josh Me- dermott, and Daniel I.K Yamins. ThreeDWorld: A platform for interactive multi-modal physical simulation. In NewrlPS Datasets and Benchmarks Track, 2021.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In ICMI,, 2015.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario March, and Victor Lempitsky. Domain-adversarial training of neural networks. JMLR, 2016.
Ishaan Guirajani and David Lopez-Paz. In search of lost domain generalization. In ICLR, 2021.
Lukas Hoyer, Dengxin Dai, Haoran Wang, and Lue Van Gool. MIC: Masked image consistency for context-enhanced domain adaptation. In CVPR, 2023.
Daniel Kifer, Shai Ben-David, and Johannes Gehrke. Detecting change in data streams. In Very Large Data Bases Conference, 2004.
Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M. Hospedales. Deeper, broader and artier domain generalization. In ICCV, 2017.
10

---

Published as a conference paper at ICLR 2024
Ya Li, Xinmei Tian, Mingming Gong, Yajing Liu, Tongliang Liu, Kun Zhang, and Dacheng Tao.
Deep domain generalization via conditional invariant adversarial networks. In ECCV, 2018.
Yunsheng Li, Lu Yuan, and Nuno Vasconcelos. Bidirectional learning for domain adaptation of
semantic segmentation. In CVPR, 2019.
Yupeng Liang, Ryosuke Wakaki, Shohei Nobuhara, and Ko Nishino. Multimodal material segmen- tation. In CVPR, 2022.
Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael Jordan. Conditional adversarial domain adaptation. NeurlPS, 2018.
Chaochao Lu, Yuhuai Wu, José Miguel Hernández-LLoatto and Bernhard Schölkopf. Invariant causal representation learning for out-of-distribution generalization. ICLR, 2022.
Samarth Mishra, Rameswar Panda, Cheng Perng Phoo, Chun-Fu Chen, Leonid Karlinsky, Kate Saenko, Venkatesh Saligrama, and Rogério Schmidt Feris. Task2sim: Towards effective pre- training and transfer from synthetic data. CVPR, 2022.
A. Tuan Nguyen, Toan Tran, Yarin Gal, and Atilim Gunes Baydin. Domain invariant representation learning with domain density transformations. NeurIPS, 2021.
Xingchao Peng, Baochen Sun, Karim Ali, and Kate Saenko. Learning deep object detectors from 3d models. In ICCV, 2015.
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang. Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In ICCV, 2019.
Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference using invariant pre- diction: identification and confidence intervals. Journal of the Royal Statistical Society. Series (Statistical Methodology), 2016.
Roman Pogodin, Namrata Deka, Yazhe Li, Danica J. Sutherland, Victor Veitch, and Arthur Gretton. Efficient conditionally invariant representation learning. In ICLR, 2023.
Aayush Prakash, Shaad Boochoon, Mark Brophy, David Acuna, Eric Cameracei, Gavriel State, Omer Shapira, and Stan Birchfield. Structured domain randomization: Bridging the reality gap by context-aware synthetic data. In ICRA, 2019.
Fengchun Qiao, Long Zhao, and Xi Peng. Learning to learn single domain generalization. CVPR, 2020.
Francesco Quinzan, Cecilia Casolo, Krikamol Muandet, Yucen Luo, and Niki Kilbertus. Learning counterfactually invariant predictors. arXiv preprint urXiv:2207.09768 2022.
Alexandre Rame, Corentin Dancette, and Matthieu Cord. Fishr: Invariant gradient variances for out-of-distribution generalization. JCML, 2022.
Harsh Rangwani, Sumukh K Aithal, Mayank Mishra, Arihant and R. Venkatesh Babu. A closer look smoothness in domain adversarial training. In ICML, 2022.
German Ros, Laura Sellart, Joanna Materzynska, David Vazquez, and Antonio M. Lopez. The synthia dataset: A large collection of synthetic images for semantic segmentation of urban scenes. In CVPR, 2016.
Elan Rosenfeld, Pradeep Kumar Ravikumar, and Andrej Risteski. The risks of invariant risk mini- mization. In ICLR, 2021.
Maxim Samarin, Vitalii Igorevich Nesterov, Mario Wieser, Aleksander Wieczorek, S. Parbhoo, and Volker Roth. Learning conditional invariance through cycle consistency. In GCPR, 2021.
Petar Stojanov, Zijian Li, Mingming Gong, Ruichu Cai, Jaime G. Carbonell, and Kun Zhang. Domain adaptation with invariant representation learning: What transformations to learn? In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), NeurlPS, 2021.

---

Published as a conference paper at ICLR 2024
Ajay Tanwani. Dirl:
Domain- representation learning for sim-to-real transfer. In Jens Kober, Fabio Ramos, and Claire Tomlin (eds.), CoRL, 2021.
Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physics/0004057, 2000.
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojeiech Zaremba, and Pieter Abbeel. Do- main randomization for transferring deep neural networks from simulation to the real world. In IROS, 2017.
Y.-H. Tsai, W.-C. Hung. S. Schulter, K. Sohn, M.-H. Yang, and M. Chandraker. Learning to adapt structured output space for semantic segmentation. In CVPR, 2018.
Yi-Hsuan Tsai, Kihyuk Sohn, Samuel Schulter, and Manmohan Chandraker. Domain adaptation for structured output via discriminative patch representations. ICCV, 2019.
V.N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability Its Applications, 1971.
Vladimir Vapnik. Statistical learning theory. Wiley, 1998.
Vladimir Naumovich Vapnik. Principles of risk minimization for learning theory. NeurIPS, 1991.
Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan. Deep hashing network for unsupervised domain adaptation. In CVPR, 2017.
Riccardo Volpi, Hongseok Namkoong, Ozan Sener, John C Duchi, Vittorio Murino, and Silvio Savarese. Generalizing to unseen domains via adversarial data augmentation. NeurlPS, 2018.
Haohan Wang, Songwei Ge, Zachary Lipton, and Eric P Xing. Learning robust global represen- tations by penalizing local predictive power. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), NeurIPS, 2019.
Ruoyu Wang, Mingyang Yi, Zhitang Chen, and Shengyu Zhu. Out-of-distrbbttion generalization with causal invariant transformations. In CVPR, 2022.
Zhonghao Wang, Yunchao Wei, Rogerio Feris, Jinjun Xiong. Wen-mei Hwu, Thomas S. Huang, and Honghui Shi. Alleviating semantic-level shift: A semi-supervised domain adaptation method for semantic segmentation. In CVPR Workshop, 2020.
D.H. Wolpert and W.G. Macready. No free lunch theorems for optimization. IEEE Transactions Evolutionary Computation, 1997.
Mitchell Wortsman, Gabriel Ilharco, Samir Ya Gadre, Rebecca Roelofs, Raphael Gontijo-Lopes, Ari S Morcos, Hongseok Namkoong, Ali Farhadi, Yair Carmon, Simon Kornblith, and Ludwig Schmidt. Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time. In ICML, 2022.
Jiaming Zhang, Ruiping Liu, Hao Shi, Kailun Yang. Simon Reiß, Kunyu Peng, Haodong Fu, Kaiwei Wang, and Rainer Stiefelhagen. Delivering mbidra semantic segmentation. In CVPR, 2023a.
YiFan Zhang, xue wang, Jian Liang, Zhang Zhang, Liang Wang, Rong Jin, and Tieniu Tan. Free lunch for domain adversarial training: Environment label smoothing. In ICLR, 2023b. URL https::/
net f
Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael Jordan. Bridging theory and algorithm for domain adaptation. In ICML, 2019.
Han Zhao, Shanghang Zhang, Guanhang Wu, José M. F. Moura, Joao Costeira, and Geoffrey J Gordon. Adversarial multiple source domain adaptation. In NeurlPS, 2018
Chuanxia Zheng, Tat-Jen Cham, and Jianfei Cai. T2net: Symthetic-to-rralistiic translation for solving single-image depth estimation tasks. In ECCV, 2018.
12

---

Published as a conference paper at ICLR 2024
A APPENDIX
A.1 EXTENDED LITERATURE REVIEW
Augmentations with Domain Shift: A number of works have leveraged domain adaptation to use casy-to-acquire source domain samples data augmentations while training with target domain data. This one of the primary modes of data-augmentation in the task of robotic grasping (Tobin) al. 2017 Bousmalis al. 2018 TTawwnni 2021), where simulated data used as augmen- tation source along with real data, which is the target domain. This idea of leveraging simulated samples as source-side augmentations has also found application in a number of vision problems such as classification (Gan et al., 2021 Mishra et al. 2022), object detection (Peng et al.) 2015
Tobin al. 2017 Prakash al. 2019 Tanwani 2021). segmentation (Ros al. |016 Wang al, Hoyer et al.
2020
(023), and depth estimation Zheng et al., 2018: Chen et al., 2019 Akada et al.
2022
Most training objectives for such applications can be classified into the self self-supervised (Li
et al.
2019 Hoyer et al. 2023) or the adversarial invariance learning (T'ai et al. 2018 2019) cate- gories, some of which can provide gains that are complementary to existing task specific algorithms
(Tsai et al.] 2019). Via Theorem 2 show that our proposed NCI can provably leverage source domain samples as augmentations in the target domain, and hence, can possibly benefit all these
application areas.
A.2 NOTATIONS
D,: Source domain, only available during training.
D,: Target domain in which the model is to be evaluated.
X, Y, P(X, Y): Inputs, outputs, and their probability distribution respectively.
Hyy Hypothesis class (set of learnable functions) of domain discriminators.
Hyp Hypothesis class of encoders for domain adaptation.
yf: Domain discriminator that distinguishes between source and target domains.
Φ,: Encoder trained and evaluated in the target domain.
Φ Encoder trained and evaluated in the source domain.
c:: Optimal encoder for the target domain (trained only with target domain data).
Encoder trained with data from multiple domains.
x² Encoder that is optimal-on--n -n-aerrge across domains (trained with multi-domai data).
Py: Encoder trained with multi-domain data, but evaluated on domain D,.
Optimal encoder for D,, trained with multi-domain data.
Note that have separate symbols for Φ and 3 only to distinguish that the former only sees samples from the target domain during training, while the latter can be trained on samples from multiple domains (including the target). Under certain circumstances like NCI, sp Φ;.
A.3
ADDITIONAL PRELIMINARIES
A.3.1 METRIC SPACE OF DOMAINS
The set of domains D form metric space under hypothesis class of domain discriminators Hy- The associated distance metric between any two points (domains) 7 E D is their corresponding divvdieegee (Definition 5). It can be verified from Equation (4) that under any arbitrary encoder that preserves the semantics of the input, H,, diverreee satisties the axioms for being metric in D, i.e., for all domains s, m, D:
Positivity: Vr # y, (1,
Symmetry: (8, T, Hy 8,44)
Triangle inequality: H, (8, T, (p) (s, Ho T,PP)
13

---

Published as a conference paper at ICLR 2024
Hence, the distance A between any pair of source (s) and target (r) domains in the representation space of an encoder yp can be measured via their H, divergence as:
T H,, (,4)
A.3.2 OPERATOR-ENCOMS DUALITY
We introduce the notion of operators to summarize a learning objective in the form of an expression in terms of domains. This allows to make statements about (e.g.. Theorem 4 and invoke (e.g., Theorem 2) group-theoretic properties that are induced by an invariance learning algorithm on the set of domains. our analysis, an operator corresponds or more domains for performing some downstream task. In practical implementation, the operator would simply correspond to the data encoder network &e that produces feature representations given an input as ((x).. The operator expression corresponding to the encoder summarizes the behaviour of that encoder when applied to data from different domains, which therefore establishes a duality between an encoder and its corresponding operator. In other words, the kind of function that is learned by the algorithm can be expressed via its operator expression. For instance, the learning objective of Domain Adversarial Neural Networks DANNs (Ganin et al. (2016) can be written as a duality between a commutatively invariant operator & operating on samples from multiple domains (say, Dr and D,), and an optimal encoder y" for the shared concept between the domains as:
function that can be applied one
x, X,
X, 1p" (x)
The above equality means that the function learned by DANN is invariant to both the source and the target domain, producing the same output that corresponds to a domain-invariant encoding of the underlying concept x. The fact that DANNs treat both the source and the target domains the same is reflected through the commutative nature of @ - the same output is produced irrespective of the position of x, and x, around @ It also indicates (via y²") that a model trained with DANN is optimal on the shared concept x across the input domains in the operand list (x, and x, ) of the expression. On the other hand, the operator expression for NCI could be written in terms of non-commutatively right invariant operator as:
(x,) = X, X X X
(x,)
Note that unlike DANN, C represents a non-commutatively right invariant operator for NCI. The above expression indicates that an encoder P²/r trained with NCI is invariant the domain that appears to the right of &, but is sensitive to the domain that appears to the left. also says that the encoder that NCI produces is optimal in the domain that the left operand comes from.
In summary, the operator expression summarizes the invariance properties of a learning algorithm, whereas the encoder is the actual function (say, neural network) that computes such invariants, given the input data.
A.3.3 RISKS
In general, our thcoretical analysis (for instance, in Lemma with the empirical risk (Vapnik 1991) defined as:
Theorem I and Theorem 3)
deals
1 Σ (f) R(f) = N
where f could be an encoder to or a discriminator 7, and N is the number of train set samples in
D, UD, The complete expansion of ((.,-) depends the nature of f. As described in Section 3.4
I(-,-) takes the form Equation (3) for encoders sp, and that Equation (2) for discriminators 7).
A.3.4 DEFINITIONS
The generalization of model across multiple domains is governed by the No Free Lunch Theorem Wolpert & Macready 1997). As such, it is well known that models that perform well on average are not optimal for specific domains, and vice versa (Eastwood et al. (022). Inspired by this, we present the following domain-specific and domain-agnostic notions of optimality.
14

---

Published as a conference paper at ICLR 2024
Definition (Domain-Specifee Optimality). An encoder & is said to be optimal for the domain D, iff. for all & E He (bypothesis class of domain -pauiii-eecffic encoders) operating on D,, the following holds:
R((")= = / 1( vx). & / x()
X,Y
X.Y
where the samples x X, y Y are drawn from the domain т. other words, there exits no other encoder ① E Hgg with a true risk lower than what is achieved by 4' when operating in D,. Definition 4 (Optimal-on-average)
An encoder ot said be optimal on average across domains 1,,+41 iff, for all Hyp the following holds:
++
(PP) 1 () A O
/
R(o')=
O
where we use (D2) to denote the application of &p to all elements Dg for notational simplicity. In other words, all encoders &p H4p should have true risk that is least high R(yp") when averaged across [T, A].
Definition 5 diverrieeee David et al. 2006 2010 Kifer et al., 2004 Ganin et al. 2016
The diverrgee between D, and D, is a measure of the capacity of the discriminator hypothesis class H. to distinguish between the source and the target sample representations, It is quantified as:
dz,, (D,, (D,, D). = sup Pr [n([(x)) = 1] Pr [n(p(x)) n,,, x>D,
(4)
x>
In other words, the H--iivrgennce is a measure of the capacity of H. to distinguish between samples in (p(D) from the samples in to ). An empirical estimate of the -iv-erveeeence was also developed
by Ben-David et al. 2006 2010), which is defined when H,, is symmetric with samples S
(D and (D,) as:
Σ Tl((p(x))) - (5)
=1l) =1)
dz,, (S,
min nEH.
[m((((x))) = =0 +
where [[] is the indicator function that takes a value of 1 when the predicate a is true, and 0 otherwise, and S = X2,, .n]
X, ) T [Xn+1, Xn+2 ..., XN).
Definition 6 (AA-distance Been-aavid et al. (2006); Ganin al. (2066). The A-distance between
domains D and DI is empirical approximation of the H-divergence given by:
dA(D), ( = sup
(A
(A(
AEA
D
DX
d D
2(1 k) +
2
where A is a subset of X, and c, which approximates the "min" part of Equation 5 can be viewed as the generalization Ganin Lempitsky (2015).
Theorem (Generalization Bound on the Target Risk -Ben-David et al. (0066). Let the VC (Vap-
nik iik-Chervonenkis) dimension (Vapnik & Chervonenkis 1971] of H., be d. With probability 1 over the choice of samples S ~ DD and ~ Dr, every H.y
4 Ro, (v) < Re(()) + (dlog + log ) (S, (S,T, 1 (d d
4
Zen
2n 4 log + ) (6)
with 3 2 inf, [RD, (+*) Ro. (o.((²)) (0²)}, 12 |S| [T], and
1 Σ 7xx(x;) vil
Rs(
1=1
the empirical source risk.
A hypothesis class H is symmetric iff Vh H and any permutation of labels Y Y, we have <(h) H (Ganin al. 2016).
15

---

Published as a conference paper at ICLR 2024
Ganin al. 2016) minimized the RHS of the bound by minimizing dx,, via domain adversarial traniig (a form of commutative invariance learning), which achieves a lower bound of 0 on the show in the section below, that such solution
generalization error (Definition D However, not optimal, as there exists an for which, although the generalization error e is not 0, the Hop divergence is 0, without affecting the source risk R.g.
A.4 PROOFS
Result 1
If the VC (Vapnik-Cher (henik--Chervonekkss dimension (Vapnik & Chervonenkis 1971) of Hap
(C(H))) 2 N, the total number training samples, then the target risk the optimal NCI encoder Rp, (p²)) is related to the target risk of the commutatively invariant encoder RD, ((*)) as:
Ro, (+t) S (v²) ds, (S. pp < RDD(("")
Proof. If the VC
dimension @Vannk & Chervonenkis 1971 of H.p
VC(H,) 2 N, then for the optimal commutative adversarial hypothesis &p acting against the optimal discriminator 77" obtaineed via the minimization eriterion in Equation (5). we have:
N
Σ 11 = = 0] n
Σ 1=++1
[ (T="((x(xx))) = 1]=00 =0
In other words, (-) would produce representations such that all samples from the source domain would be misclassified being from the target domain and vice versa. So, under commutativity samples from both domains are equally likely to get misclassified by the domain classifier, as for example in Ganin & Lempitsky (2015): (Arjovsyy et al. (2019): [Ahuja al. (202T). Hence, the best possible H-divergence that can be obtained with (p(-) by substituting the above in Equation (5) is:
du,, (S, = 2(1 - 00 + 0]) =
However, for the optimal encoder y0, E H.p that is non-commutatively invariant towards the target domain r, the samples from the source would be classified as being from the target, the other way around. We would thus have:
Σ n
1|= and
(p;((x Σ
=
1=++1
Substituting the above in Equation 5):
dx, (S. T) = 2(1 -
Hence, under non-commutativvty, i.e., when the adversary forces only the misclassification of the domain labels of samples from the source domain, the theoretical limit of the divvevveeeence is lower giving stricter upper bound on
than that of the commutative setting, and in fact degenerates the target risk in Theorem Under NCI, Equation (6) thus becomes:
2n RD. S R. (v:) + (dlog d + log +++44 (dlog + log 5) +
2en
RD. (vt)) < Ro. (4*) - dr,, (S,T, < Ro, (4x)
as (x(7)) (yp") (non-commutativity does not affect the source risk as source samples still get mapped to the target domain, with commutativity), and dx(SS T)) thereby bringing down the upper-bound on the target risk of the optimal NCI encoder to R(y*) dr., (S,7,,4) This completes the proof.
L
Lemma 1. Let D. and D, be separated by dH,, > O. Then, the bases ofD, and Dr can be factorized
as D, [C D2] and D, [C Dr] such that:
D. Dr
An optimal discriminator 17" maximizes Equation
while an optimal commutative adversarial encoder
6p" minimizes Equation (5)
16

---

Published as a conference paper at ICLR 2024
Proof. Although D, and D, are separated by dx,, (D,, D,) 0, they share the same support, (X,Y) Y). Hence, they must have a subspace that corresponds to the shared concept, which is C.
Now, let the complements of C in D& be D., and that in D, be D,. Since concept, and a domain- specific expression of the concept, can vary independently. D and D, must be subspaces that are intrinsic to the domains, and hence, not shared between the domains (the extreme case is the scenario when the two domains share only the concept and no domain-specific components, for example, in texts and images (Federici et al. (0200). Since the Hiy-divergence between D. and D, 0, it means that they are distinct domains. This implies that the distinctness of DD and D,, which is expressed via their positive H, divergence, must be result of the fact that their respective Nomain-sppeiife components, namely D. and D, do not share any bases. Hence, D, and D, must be independent + D. Dr O. This completes the proof of the lemma.
Lemma 2. For source and target domains DD and D, respectively with dx, (D,; > 0, the following holds for commutatively invariant encoder 4p
80 (D. (DD.D..)= =-))))(())) ( (D-)7
Proof. (C) = y. Since sp is commutatively invariant to all domains, let (Dt)) = (²((2) = k. Without loss of generality, let both y and k be idempotent under self dot- dot-product, i.e., ÿ" and k" = k. Now, from Lemma] |
we can right the RHS in the lemma as,
40 (D.) (2.)),''((0) (D+) *=C( D.I) "p" ((C D+))" ( (C) 4 (D.)) (C) (D,))' = (y k]
and the LHS as,
(D. D,) = 40 ([C D. D,1") 4 ((CC" D,D.)) (CC") 4 (D.D.))
However, since CC is in the same concept basis, namely that of C, and should hence induce the same label prediction
(C( x0= y
Now, D' D.D. corresponds to the domains-specifer components shared between D, and D,. Given that (-)() is invariant to any domain -specifc information, if T0 (D.) = 40 (D+) = k.
D' D.D," = 4 (D.D?) k
We can therefore rewrite (D= D,)) as:
(D DD) = (CC") 4' (D.D.)) = lý k] = -Ds) (D+)
This completes the proof of the lemma.
Lemma 3. Let the diveirreee between the source (s) and the target (T) domains be A, i.e., + A. The risk of the optimal-on-averaan encoder 4p" (-) across domains is lower-bounded by
its prediction error on the shared semantics between the source and the target domains given by:
T+A
R(y*)= = min 11
1
/
(1p ())
min (D,
EHE
A
EHE
B=T
where U(--)) is the loss function for measuring prediction error.
Proof. Following from Lemma I for a given instance x E X, the shared semantics between do- mains must lie in the concept subspace, i.e., D, n D, C. Hence, the risk on the shared semantics can be written as:
(D n2.), =(()"(),,)
Let the integral in the lemma be denoted by JJ. Assuming the simplest case of domain discrepancy, where DD and D, are linearly related, considering the path on the domain manifold connecting the
17

---

Published as a conference paper at ICLR 2024
two, // can be lower-bounded by the risk on the dot-produce between D, and D, under yp" (-) which computes their similarity as follows:
T+A
== / (PP))))
2(()))) ((( (D++t),,))
6=T
The lincarization follows from the simplest form that the manifold can assume, and dot-product in
this regime would be estimate of the similarity, i.e. the degree of shared information between D, and Dr, which are nothing but domain-specift expressions of the support (X, Y). Now, applying
the factorization of D and D2 from Lemma to the form of in Equation
8 we have:
2 1(pp" ((C D.l) 40 ((C D2l"), = U(p" ([C c² D1 D1-D2 D2 D) = 1(p ((CC 0)),), (8)
where the distributive property of ge under the dot-product follows from Lemma 2 Equation ( and Equation (8) get:
Combining
R(Ø")= min 1 J 2 ((CC" = =)) (C)) min (D, (D,),,,,, EHE
E
since C and CCT represent the same concept subspace. This completes the proof of the lemma.
Theorem 1. Let the diverreee between the source (s) and the target (7) domains A, i.e. A. Under asymmetry (Assumption D i.e., [(p (x,)iy) < [(p (x)):y), the risk of the
chiiall-on-vveraee encoder R(y²)) for predicting across all domains up to a distance A from the domain admits the following upper bound:
T+A
f 1 (Do) ( (P) sp EH
R(y")
min
where ((:,.) calculates the encoding risk domain, and (2(() the optimal encoder for т.
Proof. From Lemma
we know:
R(6")) min EH.
(D,
i.e. the risk of the globally optimal encoder R(x=*) is upper-bounded by the information shared between the source and the target domains [(y>" (D, n D,), Y). Also, the global risk of (-(() must be least large as the maximum risk in the individual domains, i.e.
1(10 (D.)) EH,
min
[Rx R+(x")),
where R-(-) and (-)-) risks evaluated in the source and target domains respectively. Since are operating under asymmetry (Assumption) I of (x.):)) < [1p;; we also have:
(x)[(x)):) < (1x =
Y) > ((00 (D+), = R,(x²)) > R (v²)
(10)
Now, since (-)() can do only as good as I(D,, Y), and I(D,, Y) > I(D,, Y) from the asymmetry assumption, must be the case that:
3 , E Hdp (D.), ((p;(D,),)) = R,(x") R, (Φ;)
(11)
Therefore, putting Lemma 3 Equation
9 Eqquatin
10 and Equation
together, we get:
R(pp)) 2 min
(D (DF), 2 max[Ra (ax
RT(x;) (v) which completes the proof of the theorem.
18

---

Published as a conference paper at ICLR 2024
Theorem 2 Consider function class T of transformations that defines target domains such that T T, = T(x), X, ~ D,, Let (-(-) be the optimal encoder for the target domain with sample complexity for incurring error of e with probability 6. From Haussler's s theorem, the error incurred by the optimal target domain encoder x with probability 8 and M target domain samples is given by:
In T
+ In
M
With my target domain samples and m, source domains samples, such that M S. m, + my, M > my, the optimal NCI encoder yp (-) achieves the same error bound with probability ó.
Proof. Let (.) and {.)%, denote sets of n source and target domain samples respectively. When using o given a fixed sample size M, the only variability in e comes from the size of the function class T. Now. [T| directly models the number of domain-specint parameters in D, Hence, the train set samples must provide information specific to D,, for which purpose, they must be sampled from D,, Thus, to prove the theorem,
needs effectively show that, under the given constraints the number available samples, with NCI, the source domain samples can be leveraged to bridge the sample complexity needs of the target domain.
Without loss of generality, consider the most conservative case where the number of training samples M m + myy Then, the process of applying non-commutative invariance with yo between the source X, and the target X, train sets directed towards the target domain T can be expressed as follows:
X, & X, = {x],
m. @ fxt, x2, x, K
Using Lemma the sample vectors be decomposed as:
X, 8 X, = {c] + d!,, c @ di.,.... cm + d @ {c+ e di,, c + dZ......,"" + d where x = c d. The subscripts under the vectors с only represent the domains from which the samples containing these concepts are obtained. Since concepts are domain-agnostic, they do not contain any domain information. The concept and the dopain-specific components can then be rearranged as follows:
X, 8 X, (fc), E cTTT + {d d², d. {²)
m.
@ ((c), of ch Jm, + {d de
d }²) m,
Now, since is non-com con-cummutatively invariant the target domain, the source comain-specifie com- ponents can be removed from the above equation:
X, ② X, {c], c.. @ (fct, ce...., I Jm, + de " (² m.
Since @ distributes over any invariance operator we have: "...." J. (d,, df,..., d }'m,-
@ ((c), _., ch Jm, @ {d) dz dh }
= {c] @ d', of ( d' c th @ ) @ (cf @ d. of di..... cf e d. }mm
= [cc e di o od ch @ d c. @ d o de....., che @ d Jr, mm,tm,200 2M
such that (i.j...., b} [1, m.). In other words, the target domain components d, that the source concept vectors c, combine with, are the ones that are present in the target domain training samples. Therefore, from the above, the total number of samples in [X, X,| is:
X, X+1 m. m, M,
(12)
all of which belong the target domain т. Now, according to the Haussler's theorem mentioned in the statement of Theorem 2 the requirement of achieving an error bound of with probability have least M samples. This can be observed from the following rearrangement:
In | In
In
[
+ In
M
M
Composition of and should either add remove domain specific components.
19

---

Published as a conference paper at ICLR 2024
know that non-commutatively combining X, with X, with & effec- tively results in m, + m, 2 M samples in the target domain т. Therefore, @ satisfies the sample complexity requirement of having access to least M samples for learning the optimal target do- main encoder t that achieves an error bound of e with probability 6, when evaluated in the target domain т. This completes the proof of the theorem.
Now from Equation I2
Theorem 4. If operalor is commutatively invariant, it induces commutative semigroup on the sel of domains D = (D1, D2...., Dr (hat it is invariant to.
Proof. Below, we show that D satisfies the axioms of a commutative semigroup under 8.
Commutativity: Since is commutatively invariant, for any pair of domains D;, Dj. by Defini- tion and Lemma [ we have,
Dj 2 = D D
where C |C 0] E the domain containing only the shared concepts across all D with no domain-specific information, and assuming D is closed under 8.
Associativity: For all domains D,, Dj, D2 D, we have,
(D, x D,) @ Dz C Dr =C
D, 2 (D, 2 D&) = D, CC
(D, D, Dr D, 0 (Dj & D2)
This completes the proof of the theorem.
A.5 EXPERIMENTAL DETAILS AND RESULTS
Clipart
Inforgraph
Painting
QuickDraw
Real
Sketch
ERM (Wiley 1998)
44.24
43.68
46.79
39.31
37.86
40.50
DANN (5)
45.21
44.00
44.86
41.86
33.32
42.77
CDANN (ECCV') 18)
45.35
44.82
45.10
41.50
35.37
42.36
MDAN (NeurIPS' 18)
45.20
44.31
46.10
40.02
36.65
41.15
MDD (ICML' 19)
44.68
44.21
45.68
41.02
35.91
40.86
CICyc (GCPR'21)
44.60
44.42
45.06
40.20
34.33
40.80
IB-IRM (NeurIPS'211
45.55
44.68
43.21
41.95
32.86
42.88
EQRM (NeurIPS'22)
45.22
44.37
45.96
40.98
36.00
40.02
CIRCE (ICLR'2)
45.74
45.01
46.28
40.56
36.95
40.37
SDAT+ELS (ICLR'23)
45.68
44.88
46.45
41.28
36.37
42.09
NCI (Ours)
46.31
45.82
48.00
43.05
39.10
43.41
Table 4: Comparison with SOTA invariance learning approaches DomainNet.
Discussion SOTA invariance learning algorithms: Empirical Risk Minimization ERM Vap- nik (1998) is the classical domain transfer approach which uniformly minimizes the empirical risk all domains, still providing one of the best average performances, Ganin & Lempitsky (2015) introduced the idea of Domain Adversarial Neural Networks (DANN), to discover features that are shared between domains, which was extended in a number of later works including MDAN Zhao et al. (2018) and MDD MDD/Zhang et al.) (2019). IB-IRM (Ahuja et al. (221)) explores the idea of infor- mation bottleneck for invariance learning, while EQRM (Eastwood et al. (022)) presented proba- bilistic approach for generalizing across domains via quantile risk minimization. However, all of the above approaches learn some form of commutative invariance, wherein domain-specific information from both the source and the target are treated as being irrelevant. CDANN Li et al. (2018) one of the earliest works that introduced the idea of conditional invariance learning into DANNs. There- after, CICyc (Samarin al.) 2021) enhanced this paradigm via disentanglement learning through cycle consistency. They proposed disentangling the latent representation into a property subspace Zo and invariant subspace Zi encoding information about the label Y and the domain respec- tively achieve the conditional invariance of X Il Y Zg. This allows the generation of new X of
20

---

Published as a conference paper at ICLR 2024
specific class by keeping Zo fixed and varying Z1. However, such disentanglement is based on the assumption that the property and the invariant (domain) subspaces are independent from each other. We show via Theorem I that such assumption does not necessarily hold under domain asymmetry (Assumption D The empirical drawback of this assumption can be seen in Table [ and Table 4 CICyc has strong performance for domains whose underlying transformations (Equa- tion (T) preserve asymmetrically high property information (c.g., Real, Photo, etc.), but relatively weaker performance on domains that aggressively diverge from other source domains, sharing only the concept at the abstract level (e.g., Sketch, QuickDraw). The idea of preserving domain specific information was also explored in Environment Label Smoothing (ELS) Zhang et al. (2023b), which one of the most recent advancements in the domain adaptation literature to deal with environment label noise. ELS Zhang et al. (2023b) and CIRCE Pogodin et al. (2023) are two the most recent advances in invariance learning for adapting to novel domains that achieve conditional invariance through environment label smoothing, and kernel-based conditional independence learning mech- anisms respectively. However, unlike NCI, they require significant modifications of the invariance learning objectives, or inclusion additional constraints that enforce conditional invariance, and do not necessarily guarantee optimality in the target domain.
21


Reviews:
[{"review_id": "2XWklnrtBv", "reviewer": "Reviewer_tufY", "summary": "This paper studies Non-Commutative Invariance (NCI) as an efficient way of learning conditional invariances. The authors propose a method that leverages domain-specific information and focuses on the target domain while learning. They argue that relaxing the invariance criterion to be non-commutatively directed towards the target domain results in a more optimal and sample-efficient learning of conditional invariances. The paper highlights the superiority of NCI over SOTA invariance learning algorithms for domain adaptation.", "questions": "Section 3.1:\n\nI suggest presenting the following statement as a formal assumption within a mathematical environment for better clarity.\n\n\"For the remainder of our analysis, we assume that the target domain contains more semantically relevant information than the source domain, i.e., ...\"\n\nSection 3.2:\n\nPlease ensure consistency in the use of symbols across theorems. If the symbol $\\delta$ in Theorems 1 and 2 refers to different variables, this should be corrected to avoid confusion.\n\nClarification in Proof: The proof of Theorem 2 requires more clarity, particularly in the concluding part i.e. “ … samples from the target domain, which is the … This completes the proof of the theorem”. It's currently difficult to understand how the final result is derived from the given explanation. \n\nRelated Work:\n\nThe technical comparison with the paper \"Learning Conditional Invariance through Cycle Consistency\" requires more detail.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "**S1** The paper is well-written, with math notations clearly explained.\n\n**S2** The empirical observations are supported by theoretical guarantees.\n\n**S3** The discussion surrounding each theorem makes the theoretical results more understandable.\n\n**S4** The paper presents extensive numerical experiments and demonstrates that their NCI-based approach surpasses existing SOTA algorithms in invariance learning.", "weaknesses": "Please see below.", "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": "", "extra_scores": {}}, {"review_id": "jPHJbdIkqv", "reviewer": "Reviewer_a8sS", "summary": "This paper shows that a provably optimal and sampleefficient way of learning conditional invariances is by relaxing the invariance criterion to be non-commutatively directed towards the target domain. Both their theory and experiments show that non-commutative invariance can leverage source domain samples to meet the sample complexity of learning the optimal target-specific encoder, surpassing SOTA invariance learning algorithms.", "questions": "none", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical analysis is comprehensive.\n2. The experimental results are solid.", "weaknesses": "none", "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": "", "extra_scores": {}}, {"review_id": "ddJJvTt9EE", "reviewer": "Reviewer_C1qz", "summary": "The author present an idea of invariant learning, that is learning non-commutative invariances (NCI), which is conditioned on the target domain and therefore preserves target-specific information. When the target domain contains more semantically relevant information than the source domain, the authors theoretically show that the NCI approach is beneficial for domain adaptation. Empirical results are also provided and show the benefit of NCI approach.", "questions": "1. What is an optimal encoder $\\Phi^{\\star}$ (in what sense it is optimal, i.e., what is the objective function that it minimizes)?\n\n2. In definition 1, what does an operator mean in the context of invariant learning (or domain adaptation)? Can you give an example of an operator in an invariant learning algorithm (e.g., DANN)?\n\n3. You only give the definition of NCI for operators (in definition 1). What is a NCI encoder $\\phi^{\\star}$? Again, what does optimal mean in   Result 1?\n\n4. In Theorem 1,  you write $s=\\tau + \\delta$. But how to do calculations between domain $s$ and $\\tau$? You do not give any definition.\n\n5. All the risks are not defined.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The empirical results do show the benefit of the proposed NCI approach in domain adaptation tasks. The assumptions of asymmetry and non-commutative seems to be novel in the context of invariant learning. Also the authors aim to provide a general theoretical framework that captures the properties of invariant learning algorithms (through the lens of commutativity) and can explain the benefit of NCI.", "weaknesses": "The theory part of this work is very difficult to understand. Lack of necessary explanations of notations and definitions. See the questions for details.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)