Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper aims to analyze and improve IDFs for lossless compression. The authors claim is mainly three following points:
1. IDFs treat the random variable as integers with a countably infinite number of classes, so it does not have a limited factorization capacity. 
2. Hoogeboom et al. (2019) demonstrated that the performance of IDFs can deteriorate when the number of coupling layers is too large, gradient bias induced by the straight-through estimator (STE) was suggested to be the cause. In this paper, authors claim that gradient bias due to the STE is less of a problem, and it highly depends on architectural choice of coupling layer. 
3. Some architectural changes (invert the channel permutations, rezero trick, group normalization) can get better results.

Pros: 
- It is interesting that several types of quantizing functions are evaluated (Fig. 3) and the results shows that STE is less of a problem.
- Architectural changes seems make better results than conventional IDFs (Table 1).
- Authors shows theoretical background of IDFs and theoretical analysis and characteristics are well written.

Cons: 
- Hoogeboom et al. (2019) shows adding more flow layers than 16 coupling layers per level hurts performance as is depicted (Figure 5 at Hoogeboom et al. (2019)). But in this paper, Fig. 3 shows only 8 coupling layers experimental results is shown, so I think it is little weak as a rationale for above claim 2..
- In contrast to the author's finding (It can be deeper depending on the architecture) in Chapter 5, IDF++ optimization in Chapter 6 was seems to relatively close to detailed tuning, and relevance is a little weak. It seems more convincing if you examine the effect of deepening the coupling layers with IDF++.
review_title: Review

final_score: rating: 6: Marginally above acceptance threshold
review_content: **Update after author response**
I thank the reviewers for their response.  I appreciated the more careful discussion of the discrete claims (as other reviewers also noted). I also appreciated the efforts to give more justification for your architecture changes.  While the actual experimental results still seem incremental in terms of raw performance, I think the other contributions of the paper are solid and worth having in the literature.  Thus, I've updated my score.

**Summary**
This paper focuses on lossless compression using integer discrete flows (IDF).  The paper explores the theoretical flexibility of IDF models showing that (with a countably infinite number of possible values for one dimension) any distribution can be factorized.  The paper also explores the bias in the gradient estimates and gives evidence that architecture seems to be more important than unbiased gradient estimators.  The paper proposes a few architecture changes including inverting channels, initializing transform to identity, initializing base distribution to standard logistic distribution, and using GroupNorm and Swish layers.  Finally, the paper shows better compression results than the original IDF model across CIFAR-10, ImageNet-32 and ImageNet-64.

**Strengths:**
- Investigates the potential gradient bias issue of IDFs and demonstrates that this may not be the core issue. (a very nice observation)
- Suggests architecture changes and shows improved performance compared to baseline IDF.
- Nice illustrations of discrete transformations.

**Weaknesses:**
- Claims about "refuting" the claim in [Papamakarios et al. 2018] seem too strong. It seems that Papamakarios et al. [2018] had a restricted case in mind of finite discrete values. And the point still seems interesting for finite discrete values (e.g., binary data).  The first theoretical result in this paper (Lemma 1) seems to be a still interesting but an almost obvious result that if you allow for infinite number of discrete values you can factorize any distribution (i.e., by just putting all possible non-zero configurations along one dimension). Again, while it is interesting and useful to discuss this, a more nuanced discussion is likely needed.  And this should be seen not as refuting the claim but as showing that relaxing one of the assumptions (i.e., finite to countably infinite values) allows for the potential of an arbitrarily flexible distribution.  There should also be a discussion that this transformation could inherently be bad for estimation since it would require the estimation of an exponential number of values.  Thus, the theoretical result may not be practically useful.

- Architecture changes seem to lack clear motivation and insight. While I appreciated the motivation that the limitation may not be gradient bias, I did not understand the reasons for the architecture changes.  Insights into why these architecture changes lead to an improvement in performance are critical.  Why is Swish better than ReLU in this context?  Why is GroupNorm really needed?  Without deeper insights, it is challenging to build off of this work or generalize this work to other contexts.

- The results seem incremental.  The results, while better than IDF, seem relatively incremental (-0.08,-0.06,-0.09).  I appreciated the context of other compression models but it seemed that IDF++ only marginally improves over the baseline IDF.

**Other comments or questions**
- The gradient-bias experimental section is a bit hard to parse.  A rewrite for clarity and simplicity would help the paper.

- Wouldn't finite difference be very expensive to compute?  This would require $O(|\theta|)$ number of model evaluations compared to $O(1)$ model evaluations for gradient estimates. Was this experiment only on a very small dataset and model?

- Why does inverting the channels help?  This still seems unclear to me since it seems to be a trivial modification though I'm probably missing something.

- What does "We furthermore use an exponential moving average for evaluation" mean? Is this related to GroupNorm or  to calculating the log likelihood/BPD?

review_title: While the paper contains interesting observations, the proposed approach seems incremental and lacks clear insight that can be generalized.

final_score: rating: 7: Good paper, accept
review_content: #### DESCRIPTION
This paper (i) notes that discrete flows are not limited in representation ability when the discrete data is embedded in the integer lattice, (ii) demonstrates that bias due to the straight-through gradient estimator is not as severe as previously thought, and (iii) investigates some architectural tweaks for integer discrete flows which lead to better performance.  

#### DISCUSSION 
I suppose the degree to which the claim in Papamakarios et al 2019 concerning the representational ability of discrete flows can be considered 'not correct' largely depends on whether you decide to initially embed your discrete data in the integer lattice (Z^D) before formulating a model. If you view a discrete flow on e.g. 8-bit images as a bijection on the support of this data (Z_{2^8}^{D} in the case of 8-bit images), then the claim of Papamakarios et al is correct. I'd argue this is the implicit assumption, since the language is centred around a view of discrete flows as permutations, which are by definition bijections. On the other hand, if you begin by embedding discrete data in the integer lattice before formulating a model as a bijection on this integer lattice, then the same limit on representational ability doesn't hold, as you show in the example and in Lemma 1. My point here is that the distinction made by this paper is useful, but not mutually exclusive with the discussion in Papamakarios et al. 

The analysis of gradient bias is good, and works to dispel the result I had taken from Hoogeboom et al 2019 regarding the limitations of deep IDFs. It's maybe not very comforting that performance degradation seems to rely on careful choice of architecture for the nets parameterizing the translations though, and it's not immediately clear to me why a simple CNN deteriorates more quickly -- do you have any explanation for why this might be the case? 

Even though it's maybe expected, it's also nice to see that careful consideration of initialization in the nets parameterizing the translations also leads to better performance.   

Finally, the experimental result on image data are fine, but I'm not necessarily convinced discrete flows will see practical use a compression tool just yet, as you mention in your conclusion. 

#### EXTRA NOTES
Figure 1 is neat and is quite a good visual aid. Despite lacking the same production quality, I also found the 2D grid in eq. 6 helpful for conveying the concept, and a generalization of this 2D grid might have provided a nice geometric proof of Lemma 1. 

Because the discretized logistic base distributions are used to parameterize a distribution over the integers rather than the usual 8-bit range, do you find there are any numerical issues with large outputs from the model, or accurately evaluating the CDF for these possible outliers?

Figures 3 & 4: Could both be made larger, with increased label, tick, and legend font sizes. Also (nitpick), "The right two panels in Figure 4 show the loss surface and optimization trajectory of a discrete model trained on the 1-bit data, showing that the optimization landscape is hard to traverse for low bit-depths" -- do those panels really show it definitively, or just suggest it?  

#### CONCLUSION
Overall I think the contributions are worthwhile to have in the literature, and would like to see the paper accepted. 
review_title: Some nice theoretical and practical discussion of normalizing flows for discrete data.

final_score: rating: 7: Good paper, accept
review_content: This paper investigated the weakness of Integer Discrete Flow (IDF) and improved it for the lossless compression task.
 Specifically, the contributions of this paper are:

1. The authors theoretically analyzed the flexibility of normalizing flows for discrete random variables, showing that normalizing flows for discrete random are capable of mapping from a distribution with dependencies across all dimensions to a distribution which is fully factorized.  By relaxing the assumption in Papamakarios et al. (2019) that the domain of the invertible function is the same as the original random variables, the authors denied the claim in Papamakarios et al. (2019) invertible flows for discrete random variables cannot map all distributions to a factorized base distribution (Lemma 1). The authors further demonstrated that the additive coupling layers in IDF is sufficient to model such mapping (Lemma 2).

2. The authors empirically discussed the potential influence of gradient bias on training IDFs, showing that the straight-through estimator is not the cause of gradient bias. Furthermore, the  influence of gradient bias is highly dependent on architecture choices.

3. Based on the previous analysis, the authors proposed an improved architecture for IDF, named IDF++. Experiments on three benchmarks -- CIFAR-10, ImageNet-32 and ImageNet-64 -- show that IDF++ outperforms IDF on all the three benchmarks.

Overall, this paper is well-written and well-motivated. Experimental details are provided to reproduce the results. Ablation studies are conducted to help analyze the effect of different modifications of IDF++.
review_title: Official Review for IDF++

Meta-review: The reviewers of this paper unanimously agreed that this paper adds an interesting theoretical and practical discussion to discrete flows. The paper has improved from the first version to the final one, in which the comments and suggestions by the reviewers have been followed. 

The paper is still incremental with respect to the previous paper and the reviewers all recommended a poster presentation.
Decision: Accept (Poster)