Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.

review_title: 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. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: This  paper is  on ab important topic : unsupervised learning on unaligned data. 

The paper shows that is possible to learn the between domains mapping using GAN only without a reconstruction (cyclic) loss. The paper postulates that learning should happen on shallower networks first, then on a deeper network that uses the GAN cost function and regularizing discrepancy between the deeper and the small network.  I did not get the time to go through the proofs, but they handle the fully connected case as far as I understand. Please find my comments are below.

Overall it is an interesting  but long paper, the claims are a bit strong for CNN and need further theoretical and experimental verification. The number of layer as a complexity is not appropriate , as we need to take in account many parameters:  the pooling or the striding for the resolution, the presence or the absence of residual connections (for content preservation), the number of feature maps. More experimentation is needed.  



Pros:

Important and challenging topic to analyze and any progress on unsupervised learning is interesting.

Cons:

I have some questions on the shallow/deep in the context of CNN, and to what extent the cyclic cost is not needed, or it is just distilled from the shallow training: 

- Arguably the shallow to deep distillation can be understood as a reconstruction cost , since the shallow network will keep a lot of the spatial information. If the deep network match the shallow one , this can be understood as a form of “distilled content “ loss? and the disc of the deep one will take care of the texture , style content? is this intuition correct? 

- original cyclic reconstruction constraint is in the pixel space using l1 norm usually, the regularizer introduced matches in a feature space , which is known to produce better results as a “perceptual loss”, can the author comment on this? is this what is really happening here, moving from cyclic constraint on pixels to a  cyclic constraint in a feature space  (shallow network)?

-  *Spatial resolution*: 1) The analysis seems to be done with respect to DNN not to a  CNN. did you study the effect of the architectures in terms of striding and pooling how it affects the results?  I think just counting number of layers as a complexity is not reasonable when we deal with images, with respect to  what preserves contents and what matches texture or style. 

2) - Have you tried resnets generators and discriminators  at various depths , with padding so that the spatial resolution is preserved?

- Depth versus width: Another measure that is missing is also the number of feature maps how wide is the network , how does this interplays with the depth?

3) Regularizing deeper networks: in the experiments of varying the length did you see if the results can be stabilized using dropout with deep networks and small feature maps?

4) between training g and h ? how do you initialize h? fully at random ?

5) seems the paper is following implementation by Kim et al. what happens if the discriminator is like in cycle GAN acting on pixels. Pixel GAN rather then only giving a global score for the whole image? 
review_title: interesting topic, the measure of complexity for CNNs does not seem appropriate

final_score: rating: 7: Good paper, accept
review_content: Quality:
The paper appears to be correct

Clarity:
the paper is clear, although more formalization would help sometimes

Originality
The paper presents an analysis for unsupervised learning of mapping between 2 domains that is totally new as far as I know.

Significance
The points of view defended in this paper can be a basis for founding a general theory for unsupervised learning of mappings between domains.

Pros/cons
Pros
-Adresses an important problem in representation learning
-The paper proposes interesting assumptions and results for measuring the complexity of semantic mappings
-A new cross domain mapping is proposed
-Large set of experiments
Cons
-Some parts deserve more formalization/justification
-Too many materials for a conference paper
-The cost of the algorithm seems high 

Summary:
This paper studies the problem of unsupervised learning of semantic mappings. It proposes a notion of low complexity networks in this context used for identifying  minimal complexity mappings which is assumed to be central for recovering the best cross domain mapping. A theoretical result shows that the number of low-discrepancy (between cross-domains) mappings of low complexity is rather small.
A large set of experiments are provided to support the claims of the paper.


Comments:

-The work is interesting, for an important problemin representation learning, while in machine learning in general with the unsupervised aspect.

-In a sense, I find that the approach suggested by algorithm 1 has some connections with structural risk minimization: by increasing k1 and k2 - when looking for the mapping - you increase the complexity of the model searched while trying to optimize the risk which is measured by the discrepancies and loss.
The approach seems costly anyway and I wonder if the authors could think of a smoother version of the algorithm to make it more efficient.

-For counting the minimal complexity mappings, I wonder if one can make a connection with Algorithm robustness of Xu&Mannor(COLT,2012) where instead of comparing losses, you work with discrepancies.

Typo:
Section 5.1 is build of -> is built of

review_title: The paper presents an interesting new analysis about unsupervised learning of (semantic) mappings with new assumptions and theoretical results that could lead to new theoretical developments in representation learning. On the other hand, the paper is dense and some discussions lack of theoretical justification.

Meta-review: The reviewers were generally positive about this paper with a few caveats:

PROS:
1. Important and challenging topic to analyze and any progress on unsupervised learning is interesting.
2. the paper is clear, although more formalization would help sometimes
3. The paper presents an analysis for unsupervised learning of mapping between 2 domains that is totally new as far as I know.
4. A large set of experiments

CONS:
1. Some concerns about whether the claims are sufficiently justified in the experiments
2. The paper is very long and quite dense

Decision: Accept (Poster)