Learning Conditional Invariances through Non-Commutativity

We thank the reviewer for precisely pointing out the theoretical aspects of our work that require further clarification. To this end, we have introduced a number of subsections, primarily in the Appendix, that attempt to address such lack of clarity. Below, we discuss our changes in further detail.

0. General theoretical clarity: Through our update, we make the notions of optimality (Appendix A.3.4, Definitions 3 and 4) and risk (Appendix A.3.3) more explicit, elaborate upon the necessity of introducing the construct of operators and their connection with encoders (Appendix A.3.2), as well as formalize the notion of separation on the space of domains (Appendix A.3.1). Following the suggestions of Reviewer tufY, we also expand upon the proof of Theorem 2, disambiguate the usage of $\delta$ by introducing $\Delta$ as a separate symbol for inter-domain distance, as well as state the assumption of asymmetry within a separate mathematical environment.

1. Optimality of $\Phi^*$: We have now concretized all the notions of optimality, i.e., domain-specific ($\Phi^*$) and domain-agnostic ($\varphi^*$) in Appendix A.3.4, Definitions 3 (Domain-Specific Optimality) and 4 (Optimal-on-Average), which details the exact conditions under which an encoder can be deemed as being optimal. From these definitions, it can be seen that the objective function that is minimized is the empirical risk, denoted by $R(\cdot)$, further details about which are provided in Section 3.4 (Training with NCI) of the main paper and Appendix A.3.3 (Risks).

2. and 3. Meaning and example of operators, and their connection with encoders: We have now added a dedicated subsection, Appendix A.3.2 (Operator-Encoder Duality), that discusses all of these. It first establishes the motivation for introducing the notion of operators into our theoretical framework, and then discusses the connection between the abstract operators and more concrete / practical, real-world encoders (which are essentially neural networks in our case). It accompanies the discussion with examples, both from the paradigm of NCI (non-commutatively invariant operator) and DANN (commutatively invariant operator) to make the ideas more relatable to practice.

4. Calculations in the space of domains: We have now described in Appendix A.3.1 (Metric Space of Domains), how the discrepancy between two domains can be calculated. In summary, the idea of $H_\eta$-divergence (Definition 5) allows us to quantify the separation between $s$ and $\tau$ as $s = \tau + \Delta$. In practice, this is calculated by the discriminator network $\eta$ that measures the separability of domains in the representation space of the encoder $\varphi$ through optimizing $\mathcal{L}_\eta$ (Equation 2).

5. Risks: We have now introduced Appendix A.3.3 (Risks) that explicitly defines the general form of the risks under consideration. In general, we minimize the empirical risk in all cases. Their specific forms depend on the kind of function that is being learned, as stated in Section 3.4 (Training with NCI) of the main paper.

We thank the reviewer for suggestions that not only improve the readability and comprehensibility of our paper, but also make our work more complete and thorough. To this end, we incorporate a number of changes throughout the main manuscript and the Appendix which we detail below.

1. Section 3.1 Assumption: We have now stated this as a separate, formal assumption as Assumption 1 (page 3), with the corresponding mathematical formulation.

2. Usage of $\delta$: We thank the reviewer for pointing out this error. We have now corrected and replaced the notation for distance between domains with $\Delta$ across the full paper. So now, Theorem 1 and all associated results use $\Delta$ to denote distance between domains, whereas $\delta$ is used in Theorem 2 and all associated discussions to denote probability of success.

3. Proof of Theorem 2: We agree with the reviewer that the jump to the conclusion about the sample complexity of learning the optimal target domain encoder $\Phi^*_\tau$ was indeed too abrupt in the proof of Theorem 2. In page 20, we have now extended the proof of Theorem 2 to address this by explicitly specifying the link between how non-commutatively combining the source and the target domains maps all samples to the target domain, and the sample complexity of learning $\Phi^*_\tau$. If there is some aspect of the proof that is still unclear, we would be happy to have further inputs from the reviewer about the same.

4. Technical comparison with Samarin et al., 2021: We thank the reviewer for pointing this out, as despite discussing this work in the introduction as being very relevant to our paradigm of conditional invariance learning, we missed out on a more detailed technical comparison of our NCI with theirs. As part of this rebuttal, we have now addressed this by evaluating their method (dubbed CICyc in our manuscript) on the PACS, Office-Home, and DomainNet benchmarks, reporting the results in Tables 1 and 4. We have accompanied this with a technical discussion on their work and how our proposed theoretical framework can explain the empirical behaviour of their algorithm in page 21.