Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Paper summary:

The authors propose ImpFlow, an implicit normalizing flow defined around solving the equation x + g_x(x) = z + g_z(z) where g_x and g_z have Lipschitz < 1.

Solving z given x, or x given z, gives the forward and inverse passes of ImpFlow. Both directions require solving a root finding problem, hence this model is implicit in both directions, contrasting with prior works (e.g. ResFlow) where at least one direction is always explicit.

ImpFlow is equivalently a composition of ResFlow and the inverse of a ResFlow. 

In the context of expressiveness, the forward pass a ResFlow is (1 + L)-Lipschitz while, importantly, the inverse is (1 / (1 - L))-Lipschitz, for some L < 1. Since ImpFlow makes use of the inverse of ResFlows in its construction, it can model arbitrary Lipschitz transformations. 

In the context of likelihood evaluation and training, the estimators from ResFlows can be used and the main difference is the use of implicit function theorem to differentiate through the root finding procedure. Authors claim the total compute cost is comparable, though solving the root finding problem does seem to introduce some overhead, going from 3.189s to 4.462s (~40% increase) for each iteration of training on CIFAR-10.

Strong points:

The use of the inverse of ResFlows in both directions of a normalizing flow is interesting, and result of having higher Lipschitz is convincing. 

In addition to the well-written series of lemmas and theorems, the additional capacity of ImpFlow over ResFlow is nicely illustrated on a 1D example.

Experiments indicate ImpFlow is slightly more performant in log-likelihood than ResFlows for the same number of parameters.

Weak points:

Is being implicit really useful? Outside of the Lipschitz requirement in this particular formulation of ImpFlows using the inverse of ResFlows, it's not clear whether having implicit formulations in both directions of a normalizing flow is advantageous. In addition to the use of a general title and method name advocating for implicit formulations, the authors do claim that "bijections with explicit forward mapping only covers a fraction of the broad class of invertible functions suggested by the first requirement, which may limit the model capacity" in the introduction. This ideally should be accompanied by a reference or rephrased to be a conjecture.

The experiments do not compare to other existing normalizing flows outside of ResFlows. The numbers reported in Table 2 (for tabular experiments) are worse than the baselines reported in Table 1 of Papamakarios et al. "Masked Autoregressive Flow for Density Estimation" while the results on CIFAR10 (Table 3) are closer to Real NVP (2016) than models like Glow or FFJORD (2018). This is likely simply due to the use of smaller models than those used previously, but if so, perhaps the authors could comment a bit more on the problems for scalability of ImpFlows. A ~40% additional time cost is mentioned once when compared to ResFlows, and an extra usage of GPU memory cost is only mentioned in the Appendix. The other parts of the paper are rather well done, but I'd liked to have seen explicit diagnostics of ImpFlows. For instance: 
  - How many function evaluations were used for solving the implicit formulation? 
  - Are results sensitive to the value of epsilon (for convergence of fixed point) hyperparameters? (A problem for implicit formulations is controlling the numerical error. Is this a problem for ImpFlows?)
  - Since the Lipschitz of ResFlows grows exponentially, does the empirical difference between ImpFlow and ResFlow shrink as model sizes increase?

Since the differences between ResFlow and ImpFlow are rather small (e.g. 0.01~0.02 bits/dim on CIFAR10), it'd be good to have some standard deviation across random seeds for all experiments.

Additional comments:

The citation under Lemma 1, "Chen et al. (2019, Lemma 2)" should probably be "Behrmann et al. (2019, Lemma 2)". (I assume the authors meant to refer to the bi-Lipschitz bounds derived in Behrmann et al.?)

Post-discussion:

I thank the authors for responding swiftly to all of my main concerns and for providing additional experimental results. I'm happy that authors have promised standard deviations and comparisons to ResFlow in the newly updated experiments for the camera-ready version, and I have adjusted my rating accordingly. I think this paper makes a very solid contribution to the normalizing flows literature.
review_title: review

final_score: rating: 7: Good paper, accept
review_content: Summary: The paper introduces an invertible transformation implicitly via the roots of an equation. As a result, they claim that this implicit transformation is in theory a superset of Residual Flows. Further, they show improved performance empirically in NLL on CIFAR10 in varying settings.

Review:
The paper introduces a novel an interesting method to parametrize invertible transformations via an implicit. The method in its current form can actually be interpreted as two Residual Blocks, but where the inverse parametrisation of the second block is used in the forward direction (as the authors show in Eq. 6). Nevertheless, I find the proposed perspective interesting and a promising future direction. The authors give detailed proofs of the flexibility of their method. The authors also propose a more memory efficient solution for training.

Weaknesses: Experimentally there are some unanswered questions.
- As Implicit flows require iterative solutions during training, they will most likely be slower. Even if ImpFlows are slower, it is really necessary to clearly highlight this difference in computation time. Further, ImpFlows are probably even faster during sampling as half of the Residual Blocks are now aligned with the sampling direction.
- The new gradient computation from Eq (16) is only very briefly discussed in the paper. Since the authors claim gains in memory efficiency, these results need to be backed up empirically.
- Thm 1 can also be derived from the perspective of two stacked residual blocks (second inverted). It would help readers to already introduce that perspective here. 

If the authors address the points raised in Weaknesses, I will consider raising my score. 

Minor comments:
Typos. The paper has some typos and in many cases a spell checker could correct these. For instance: Inverible (Sec 3.2) Esitamated (algorithm 1.).
Rephrasing (sec. 4.2). "Note that we define R_1 = R" -> "By definition of Eq. 4 and Eq. 5, R_1 = R"
The overload in Algorithm 1 is somewhat difficult to parse, consider changing "g(z) = F (z, x; theta)"

After rebuttal:
I am satisfied with the reply of the authors and I have raised my score to 7.
review_title: Good idea, some important details missing.

final_score: rating: 7: Good paper, accept
review_content: # Summary
This work is about a new architecture for normalizing flows inspired by implicit neural networks. In particular, the authors show that a specific implicit neural network build from residual blocks defines a bijective map. From this insight, they show how to efficiently train such architecture by estimating the log Jacobian and solving the inverse problem related to the implicit architecture. On top of this achievement, the authors thoroughly study the attractiveness of their architecture compared to i-res-flow. They demonstrate analytically and empirically that implicit normalizing flows are strictly more expressive than i-res-flow.

# Major comments
## Pros:
Overall the paper is well written and pleasant to read. The idea is novel and is well introduced. Moreover, the paper provides a theoretical justification for the expressivity gain made by the newly introduced architecture with respect to I-res-flow. The experimental results are good although not defining a new standard in density estimation tasks. 

## Cons:
1) As I said the paper is well written overall. However, I took quite some time to fully understand section 4 (in particular 4.2), I think this section should be clarified. After taking the time, everything appears convincing but I think the flow could be improved. I checked the proofs in 4.2 and everything seems correct, great job! You should mention that everything is proved in the appendix, I was not sure it was the case the first time I read it.
2) Regarding the experiments I have two concerns. First, you provide only results about one specific value of L without stating how you chose it. It feels like you selected it to show the performance gain brought by your method, it may be fine but you should at least mention it clearly. Else you should perform a full architecture search both for resflow and for impflow and show the best results of each architecture. My second concern is about table 2, I think you should mention other sota NF architectures (such as the ones based on monotonic transformation) and maybe discuss a possible explanation for the large gap.

## What could be done to address my comments
1)  You could maybe directly state that $\mathcal{R}_2 \subset_\neq \mathcal{F}_2 = \mathcal{I}$ instead of corollary 1.
2) Clarify how you selected the number of steps. I saw you mention that you copy the experimental setting of Chen et al. 2019. However, they use 200 steps for the 2D grid and do not provide results for the UCI dataset (or I missed it maybe).

# Minor comments
p3: "inverible".
4.1: $J_f$ inconsistent notation wrt (1).
def 2: missing . at the end of the equation.
"2-norm": do you mean $L_2$ norm?
"in 1-D input" -> "In the 1D input"
D.4: "Tablular"
review_title: Overall a nice work!

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: # Summary
The authors concerns the question of how expressive invertible functions can be constructed. Their ansatz is the defining an invertible layer implicitly, using the root of an equation. While this approach is more general, they employ residual flows (ResFlows) to formulate a particular realisation of such an equation, calling the model ImpFlow. They show that the resulting function space is strictly richer than that of ResFlows. They further demonstrate how ImpFlows can be trained and evaluated. Empirically, ImpFlows outperform ResFlows on all considered tasks.

# Strong and weak points
## Pros:
- Implicit functions are a new way to formulate invertible functions
- The proposed formulation using ResFlows is clearly presented
- ImpFlows are strictly more expressive than ResFlows, allowing arbitrary Lipschitz constants
- Experiments highlight the improvements
- In general: very concise and well-guiding writing

## Cons:
- Implicit functions are more expensive to evaluate than explicit functions (here, +50% in execution time)

# Recommendation
The development of expressive invertible functions is key in applications that involve invertible functions, like density estimation using normalising flows. This paper proposes a novel framework to formulate such invertible expressive functions implicitly. The results are not game-changing, but consistently outperform its closest relative. Together, this is a solid work that should clearly be accepted.

# Questions
- I would like to see some analysis on how a Lipschitz function influences the Lipschitzness of the inverse. In particular, in Section 6 you could mention the relation between the "Lipschitz coefficient" c and the achievable Lipschitz constants of an ImpFlow layer. I naively would guess the bound $L < (1 + c) / (1 - c)$.
- Can you give an intuition how large the improvements on the density estimation datasets are? I checked [paperswithcode](https://paperswithcode.com/sota/density-estimation-on-uci-power) on the POWER dataset and the models are clearly outperformed by other methods. To be explicit: I don't require that every new architecture has to beat the state of the art in all possible tasks, especially when it comes with a fresh idea and thorough theory. But can you give your best guess about why other approaches achieve significantly better results?
- When comparing ImpFlow and ResFlow, I suggest that you should additionally have a variant of ResFlow with the same *execution time* in addition to *number of parameters* as a corresponding ImpFlow. I think the tradeoff involved is not only between quality and the number of parameters to store, but the also execution time of a model.

review_title: Very good submission, minor points remain open

Meta-review: This is a clear accept. Solid and timely work extending normalizing flows to implicitly defined mappings. Convincing presentation. Supported by all four reviewers. Best paper in my batch. Has the potential to spark further developments in the field. I recommend to feature this paper as a spotlight.
Decision: Accept (Spotlight)