Venue: ICLR 2021 Conference

Reviews:

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

Summary and contributions:

The paper provides a novel approach to normalizing flows. It models a normalizing flow as the gradient map of a convex potential function.  The gradient estimation and model inversion, that are the computationally expensive part of arbitrary complex NFs, are formulated as cheap convex optimization problems. It proves that  the proposed CP-flow is a universal density approximator and also shows that it is an optimal transport (OT) map. 

#####################

Reasons for score:

I vote for clear acceptance. The idea of convex potential flow sounds very interesting and the way the computational complexities are very useful for designing more advanced NFs. The paper is very well written. 

Strength:

1. The paper is very well written and structured and is easy to read for a wide audience. It also provides a good review of main papers in the literature
2. The motivation for using CP-flow is well explained. 
3. The claims are well supported by theoretical proofs and empirical studies.   
4. The gradient estimation and model inversion, that are the computationally complex part of arbitrary complex NFs, are formulated as convex optimization problems that gain advantage of fast converging and cheap optimization algorithms and it also leverages the efficient Hessian-vector product computation.
5. The experimental results show the proposed flow can perform competitively with much less number of parameters .

#####################

Additional Feedback and Questions:

1. After reading the paper it is not quite clear why we do need an optimality in Monge sense (Theorem 4) and what is the point of optimal transport in this work. It is worth expanding or adding more insights to the motivation given in the Introduction by the notion of rearrangement cost. 
2. Orthogonality or Lipschitzness constraints are mentioned without citation in introduction.
3. What is so special about the soft-plus type nonlinearity in theorem 3, can we use other non-linearities such as the symmetric-log derived in [1] that are monotonic and differentiable by construction ?
4. CP-flow looks more expressive than NAF in toy examples but why is it outperformed in density estimation? As a more insightful comparison, I suggest comparing the “transport cost” of the NAF with that of ICNN in section 5.2 (Figure 4) as NAF is outperforming ICNN in all the benchmarks and is universal.
5. It is worth comparing the number of parameters of the optimal CP-flow in Table 1 with the available methods to have a better understanding of models’ flexibility. Maybe, CP-flow can achieve the SOTA if the number of parameters are normalized.
6. I wonder if CP-flow can outperform the Residual flow which uses a similar gradient estimator routine if its number of parameters, in Table 2, is increased.
7. Compared to RealNVP, CP-flow requires an optimization solution per each training update. Also, as noted in the paper, the computational cost of the CP-flow is less than residual flows as it saves the Spectral normalization process. So how the speed and convergence rate of CP-flow is compared against the benchmarks, assuming all are using the same hardware e.g GPUs (and cvx opt are implemented in GPU). It looks better to have a sense of it in one of the experiments. 
8. I am willing to see the randomly generated sample of the CP-flow especially to compare its local/global stability against the Residual flow due to its Lipschitz constraint as discussed in [2].
9. A schematic architecture of the ICNN model helps better understand it.

Ref:
[1] M. Karami, D. Schuurmans, Jascha Sohl-Dickstein, Daniel Duckworth, Laurent Dinh, “Invertible Convolutional Flow", Advances in Neural Information Processing Systems (NeurIPS) 2019,

[2] Behrmann, Jens, et al. "Understanding and mitigating exploding inverses in invertible neural networks." arXiv preprint arXiv:2006.09347 (2020) 
review_title: gradient map of a convex potential function as a flow

final_score: rating: 5: Marginally below acceptance threshold
review_content: ### Summary
The authors introduce CP-Flows, a way to parameterize normalizing flows by constructing an input-convex neural net with softplus-type activation functions and considering its gradient as the flow. They add a quadratic term to ensure invertibility. Using convex optimization techniques their method only needs access to convex optimization solvers. They show that this architecture is universal (that is, starting from a measure $\mu$, there is a sequence of CP-Flows converging weakly to a desired distribution $\nu$). They also prove that the constructed flow converges pointwise to the optimal Brenier map for Euclidean cost. They perform a set of experiments on synthetic and real-world datasets, and show their method delivers its promises.

### Strong/Weak Points
+ The ideas described in the paper are simple and easy to understand.
+ The paper is generally well-written (with exceptions detailed below).
+ The ideas for computing the trace of log Hessian and its gradient are neat; however, I am not sure if they are novel and not present in the literature.
+ All the results are asymptotic. The convergence results are weak: convergence to the optimal map (Theorem 4) is point-wise, and convergence of the distributions is weak (Theorem 3). 
+ There are lots of tricks used here and there (computing the trace of log Hessian and its gradient) to reduce computational complexity, but nothing explicit is computed theoretically nor presented experimentally. 
+ I am not sure if Theorem 2 and Theorem 4 are already known or not. I might not recall the reference, but I am pretty confident that they have been existing in the literature.
+ In the experiments, looking at Table 1, NAF always outperfrom CP-Flow (and no explanation has given for why is it the case). The same is for Table 3, where Sylvester outperforms CP-Flow in every dataset.

I have decided to give a 5 to this paper, as theoretically it does not add significantly to the current theory of OT and NFs. Experimentally, I feel that the performance is (probably) marginally better than the other methods if it is not worse.

### Additional Feedback
Fixing the following errors improves readability of the paper:
- Section 1, paragraph 3, line 4, "the network" has not been introduced and not clear where it is referring to.
- same, line 7, universality and optimality is not clear (in what sense). It becomes clear later.
- page 2, line 2, "the network architecture" still is dangling.
- Section 2, two lines above "Universal Flows" does not make sense. "ordinary differential equations, orthogonality or Lipschitz constants" are not NN architectures.
- same, two lines above "Optimal Transport" there is no reference why "under very mild conditions a coupling exists". 
- same, "Optimal Transport". The problem described is not Monge's problem. It's Monge's formulation for optimal transportation.
- page 3, "Invertibility and ..." the activation changed from $s$ to $g$ suddenly.
- page 4, lines 11, 12 are hard to understand. Why NaNs creep in?
- page 4, (3), why the terms are in red? 
- page 5, "Sigmoidal Flow" activation is called $s$ while in the formula it is $\sigma$.
- same, "Flows with Potential ..." the last two lines, I do not see what the contrast is made against. 
- page 6, Section 5, I do not see why the notation changes from $z$ to $h$.
- page 7, I do not know how to interpret the middle plots for $f_\mathrm{iaf}(x)$ and $f_\mathrm{cp}(x)$.
review_title: Official Review by Reviewer #4

final_score: rating: 7: Good paper, accept
review_content: #### Summary and contributions
This paper presents CP-Flow, an alternative formulation of normalizing flows via the gradient of a strictly convex function. Concretely, an optimal transport map is constructed for the quadratic transport cost. This map can be constructed via the gradient of a strictly convex function owing to Brenier’s Theorem. The strict convexity of the potential function ensures that the gradient map is injective and surjective (i.e., invertible). This leads to relations with normalizing flows, invertible maps that can be trained via exact maximum likelihood. The authors borrow techniques from convex optimization to invert the gradient map and to compute the log-determinant of the Hessian (and its gradient), quantities that are required for density evaluation and gradient-based training. Using arguments from optimal transport literature, the authors prove the universality and optimality of the gradient maps when they are realized using input-convex neural networks (ICNNs). Experiments in various settings of density estimation and variational inference have been presented that demonstrate a competitive performance of CP-Flow against competing normalizing flow models.

#### Strengths
This work makes a significant contribution to the body of literature on optimal transport-based generative models. By parameterizing the flow as the gradient of a convex potential function ($R^d \rightarrow R$), this method improves the parameter efficiency of invertible models. Moreover, the network architectures, although restricted to ICNNs, can be much more flexible than in conventional normalizing flows where networks have to satisfy restrictive conditions to ensure invertibility. Theoretical results also demonstrate that ICNNs have the capacity to learn transport maps between arbitrary continuous probability measures. The theoretical results are supported by the empirical evaluation which, despite lacking scale, is sufficient to demonstrate the potential of the proposed method. 

#### Weaknesses
The primary weakness of this work is that some directly related works that utilize Brenier’s Theorem to learn transport maps via ICNNs have not been discussed in sufficient detail. Apart from flow-based setups, other works have also explored the construction of transport maps using ICNNs which have not been discussed (see for example [1, 2, 3]). Moreover, the experiments lack comparisons with these works or a discussion of why such comparisons are not possible.  Another recent related work is [4]. 
A potential concern is the efficiency of solving a quadratic optimization problem for computation of the gradient of the log-det of Hessian for each gradient step. Did the authors compare the runtimes of the different methods?

[1] Korotin, Alexander, et al. "Wasserstein-2 Generative Networks." arXiv preprint arXiv:1909.13082 (2019).    
[2] Taghvaei, Amirhossein, and Amin Jalali. "2-wasserstein approximation via restricted convex potentials with application to improved training for gans." arXiv preprint arXiv:1902.07197 (2019).    
[3] Makkuva, Ashok Vardhan, et al. "Optimal transport mapping via input convex neural networks." arXiv preprint arXiv:1908.10962 (2019).    
[4] Finlay, Chris, et al. "Learning normalizing flows from Entropy-Kantorovich potentials." arXiv preprint arXiv:2006.06033 (2020).


#### Additional feedback

Suggestions:
- Include a proper discussion of related works that use ICNNs to parameterize the Brenier potential and compare with these methods experimentally, if possible.

Questions:
- Is there a reason that the authors did not include a NSF ablation in Table 2?
- Did the authors investigate the quality of generated samples for the image datasets (using FID, IS, etc.) as the poor quality of images is a known problem for flow-based models?
-------
The authors have addressed most of my concerns. I believe the paper is a good contribution to the literature on normalizing flows; therefore, I firmly vote for acceptance. 
review_title: Official Blind Review #1

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:
This paper proposes the flow based representation of a probability distribution so that the corresponding density remains tractable. In particular, the push-forward map that generates the desired distribution is characterized by the gradient of a strongly convex potential function. The invertability of the mapping as well as the Jacobian of the mapping is hence guaranteed by such a convexity property of the potential function. The proposed CP-flows are proved to be universal density approximators and are optimal in the OT (2-Wasserstein) sense.

Comment:
It seems to me that the proposed CP-flow model is quite similar to a set of recent works that use the ICNN to parameterized the convex Brenier potential of 2-Wasserstein. This limits the novelty of this paper. 
On the other hand, I think one contribution of this paper is to study how the gradient of the log determinant of the Hessian of the potential function can be computed, which relies on a standard technique, the Hutchinson trace estimator.
Another contribution of this paper is to study universality of the CP-flow model as a density approximators. Since any convex function yields an affine-max representation which is a special case of the ICNN, the Brenier's theorem implies the universality.

Concerns:
1. Unlike the traditional flow models which consists of a sequence of simple transformations, it seems to me that CP-flow is not exactly a "flow" model as it only involves a single (but complex) transformation (which of course contains multiple layers). Correspondingly, the computation involved in the flow model (inversion, gradient evaluation) are substantially more expensive.
2. The presentation of the paper focuses on the description of the model. However, I would suggest the authors to add a few paragraphs to briefly discuss some problems that takes the CP-flow model as a subroutine, e.g. variational inference or maximum likelihood loss. This would make the paper more self-contained and it will also justify the need to have a traceable density.  
3. More on the writing of the paper. Some derivations to show that why (3) is important are appreciated, e.g. 
$det \frac{\partial f^{-1}(x)}{\partial x} = \frac{1}{det(\nabla f(f^{-1}(x)))}$. Again, it would be good for a broader audience if the paper is more self-contained.
4. How to efficiently implement the batch computation of the gradient of the model? What do you mean by "Inverting a batch of independent inputs is as simple as summing the convex potential over all inputs"?

*********
The authors partially addressed my concerns. Therefore I raise my score to 6.
review_title: Official Blind Review

Meta-review: The main contribution of the paper is a novel parametrization of normalizing flows using ideas from optimal transport theory. This new parametrization allows viewing a normalizing flow as the gradient of a convex function, which leads to an efficient method for gradient estimation for likelihood estimation, using only access to convex optimization solvers. The paper is overall well-written and provides a clean analysis. Theoretical results from the paper are supported by experiments. The paper was overall viewed favorably by the reviewers. 
Decision: Accept (Poster)