THE ROLE OF MINIMAL COMPLEXITY FUNCTIONS IN UNSUPERVISED LEARNING OF SEMANTIC MAPPINGS
We discuss the feasibility of the following learning problem: given unmatched samples from two domains and nothing else, learn a mapping between the two, which preserves semantics. Due to the lack of paired samples and without any definition of the semantic information, the problem might seem ill-posed. Specifically, in typical cases, it seems possible to build infinitely many alternative mappings from every target mapping. This apparent ambiguity stands in sharp contrast to the recent empirical success in solving this problem. We identify the abstract notion of aligning two domains in a semantic way with concrete terms of minimal relative complexity. A theoretical framework for measuring the complexity of compositions of functions is developed in order to show that it is reasonable to expect the minimal complexity mapping to be unique. The measured complexity used is directly related to the depth of the neural networks being learned and a semantically aligned mapping could then be captured simply by learning using architectures that are not much bigger than the minimal architecture. Various predictions are made based on the hypothesis that semantic alignment can be captured by the minimal mapping. These are verified extensively. In addition, a new mapping algorithm is proposed and shown to lead to better mapping results.
The paper addresses the problem of learning mappings between different domains without any supervision. It belongs to the recent family of papers based on GANs.
The paper states three conjectures (predictions in the paper):
1. GAN are sufficient to learn « semantic mappings » in an unsupervised way, if the considered networks are small enough
2. Controlling the complexity of the network, i.e. the number of the layers, is crucial to come up with what is called « semantic » mappings when learning in an unsupervised way. 
More precisely there is tradeoff to achieve between the complexity of the model and its simplicity. A rich model is required in order to minimize the discrepancy between the distributions of the domains, while a  not too complex model is necessary to avoid mappings that are not « meaningful ».
 To this aim, the authors  introduce a new notion of function complexity which can be seen as a proxy of Kolmogorov complexity. The introduced notion is very simple and intuitive and is defined as  the depth of a network  which is necessary to  implement the considered function. 
Based on this definition, and assuming identifiability (i.e. uniqueness up to invariants), and for networks with Leaky ReLU activations,  the authors prove that if the number of mappings which preserve a degree of discrepancy (density preserving in the text) is small, then the  set of « minimal » mappings  of complexity C   that achieve the same degree of  discrepancy is also small. 
This result is related to the third conjecture of the paper that is :
3. the number of the number of mappings which preserve a degree of discrepancy  is small.
The authors also prove a byproduct result stating that identifiability holds for Leaky ReLU networks with one hidden layer.
The paper  comes with a series of experiments to empirically « demonstrate » the conjectures. 
The paper is well written. The different ideas are clearly stated and discussed, and hence open interesting questions and debates.
Some of these questions that need to be addressed IMHO:
- A critical general question: if the addressed problem is the alignment between e.g. images and not image generation, why not formalizing the problem as a similarity search one (using e.g. EMD or any other transport metric). The alignment task  hence reduces to computing a ranking from this similarity. I have the impression that we use a jackhammer to break a small brick here (no offence). But maybe that I’m missing something here.
- Several works consider the size and the depth of the network as hyper-parameters to optimize, and this is not new. What is the actual contribution of the paper w.r.t. to this body of work?
- It is considered that the GAN are trained without any problem, and therefore work in an optimal regime. But the training of the GAN is in itself a problem. How does this affect the paper statements and results?
- Are the results still valid for another measure of discrepancy based for instance on another measure, e.g. Wasserstein?
Some minor remarks :
- p3: the following sentence is not clear  «  Our hypothesis is that the lowest complexity small discrepancy mapping approximates the alignment of the target semantic function. »
- p6: $C^{\epsilon_0}_{A,B}$ is used (after Def. 2) before being defined. 
- p7: build->built
Section II :
A diagram explaining  the different mappings (h_A, h_B, h_AB, etc.) and their spaces (D_A, D_B, D_Z) would greatly help the understanding.
Papers 's pros :
- clarity
- technical results
cons:
- doubts about the interest and originality
The authors provided detailed and convincing answers to my questions. I thank them for that.  My scores were changed accrodingly.