Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper introduces an algorithm for training neural networks in a way that parameters preserve a given property. The optimization is based on using a transformation R that  perturbs parameters in a way that the desired property is preserved. Instead of directly optimizing the parameters of the network, the optimization is carried out on the parameters B of the auxiliary transformation R.  

The method is (only) exemplified with the particular case where one needs to optimize a network with the property of having invertible layers (which is an important use case for example for normalizing flows, and invertible networks). In this particular case, the paper shows that the transformation of the parameters can be cast as a perturbation of rank one matrices using closed-form formulas that can be used to check and guarantee the invertibility. The parameters are updated periodically, after a series of perturbations which helps to stabilize the optimization. The paper shows three experiments on two synthetic datasets (linear data and 2d manifold) and  one on Boltzmann generators to generate samples of Alanine Dipeptide.

The paper presents an interesting idea and some empirical evidence showing promising results. My main concern with the paper is that the experimental evidence is quite limited so it is hard to judge the real contribution of the method. Additionally, the paper could improve the organization.

In particular, Section 2 needs a better organization. The title mentions a general idea, but in practice only the case of invertible matrices is analyzed and discussed. Section 2.2. is rather disconnected from Section 1.1. There's no motivation why this is there. (Maybe this should be moved to a subpart of Section 2.3). Same applies to Section 2.4 (implementation details?). It might be better to specifically focus and present the method for the the case mentioned in Section 2.5. Also, it seems more reasonable to discuss the related work (Section 3) before jumping into the algorithm details (part of Section 2).

Some questions:

-- Update u and v. The optimization in u and v has too many degrees of freedom. For example, you could constrain to always have ||v||=1 without losing anything. Will this help to avoid local minima?

-- In the first experiment (linear data) it is mentioned that when training against linear training data P^4Inv can get stuck into local minima, and that this does not happen when using more complex data. Would you mind elaborating a little more on this observation?

-- What can be concluded from Figure 4? It seems to me that all the tested methods did a good job here.

Typos and minor comments:
--Pag2 - B_0 = ids. I think this should be R_{B_0} = ids

--Pag6 -  B=-I_{101}, I assume this should be A=-I_{101}.

--Pag7 - "since it with a given" (writing)

review_title: A method to optimize invertible matrices through rank one perturbations

final_score: rating: 6: Marginally above acceptance threshold
review_content: # Summary
This work proposes parameter perturbations for the training of neural networks while preserving some properties. It particularly focuses on the case of invertible layers and demonstrates improvements over classical architectures for density estimation with normalizing flows. It is empirically shown that parameter perturbations allow for sign changes in the determinant.

# Major comments
## Pros:
This work is original and tackles an important problem, that is learning invertible matrices. I think the approach is original and the fact that it could be applied for other properties makes the development and the proof of work very interesting. 
At some point you discuss some weaknesses of your work, I really liked that as it will definitely help people using your method. The paper is clearly written and so easy to follow. The experiments are insightful and help the reader to get a better feeling of what is happening at training time. Some results suggest that using your method clearly helps for certain density estimation tasks. Additional experiments could maybe show that P4 + Bent leads to efficient and expressive normalizing flows.

## Cons:
1) The focus of the paper is not really on parameter perturbations for training neural networks in general. Most of the paper discusses how perturbations can be applied for learning invertible matrices. Introducing the paper as if it could be applied successfully for any kind of properties does not make a lot of sense to me as only experiments on invertible matrices is presented.
2) The paper discusses some concurrent methods for learning invertible matrices such as https://arxiv.org/pdf/2006.15090.pdf. However, it is not clear which method is preferable in which situation. What is even more embarrassing is that no comparison at all is performed against this work.
3) A serious discussion about the computational cost of using perturbation instead of another method for learning an invertible matrix is lacking.
4) The benchmark you are using to assess the performance gain on the density estimation task is a bit odd to me and does not allow the reader to really assess the usefulness of your method in such a setting. 

## What could be done to address my comments
1) Either perform additional experiments showing the applicability of your method for a large bunch of interesting properties (e.g. orthogonality). Instead, I would suggest clarifying the title, the abstract, and the intro. Adding a discussion about other interesting properties that could be kept with your method between the experiments and the conclusion would make sense to me. As is I feel like you're selling something more generic than what you really show with your experiments whereas I believe learning invertible matrices is already an important and interesting achievement.
2) Add a comparison with the referenced paper. And discuss the potential advantage of each method.
3) Discuss the computational cost. As an example how long is the training of P4 inv in comparison to linear in fig 3.
4) Try to discuss the more general advantage of using learned invertible linear layers in flows instead of predefined PLU factorization. I don't think benchmarking your "flow" with respect to the UCI datasets will really improve the quality of your manuscript but it would help the reader to get a sense of some possible additional expressivity gained with your method.

If you address comments 1, 2, and 3 (or convince these are not important), I will raise my score. Addressing 4 is less important but it would definitely improve the manuscript's quality.

# Minor comments
Pages 2: B_0=id_S -> R_{B_0} = id_S ?
Page 3: Could clarify/elaborate on the last sentence just before algorithm 1.
page 5: I would avoid classifying NFs into two categories as you do.
page 6: Beginning, "quadratic matrix" -> "square matrix" ?!
4.3: "since it with" ?
Why not just using elu, sigmoid, or than instead of Bent identities? Could you explain why if it is important?
review_title: Parameter perturbations for building invertible matrices applied to density estimation

final_score: rating: 6: Marginally above acceptance threshold
review_content: ### Update: 
I'd like to thank the authors for carefully addressing my concerns.. 

Reviewer 2 claims $P^4$ training is a special case of previous work. It seems the authors agree at least to some extent *"we agree that the P4 update scheme is closely related to dynamic trivializations"*. It is not clear to me how harshly this should be penalized. In some cases, it is interesting to research special cases of known general results. Unfortunately, it is hard for me to judge if this is the case here, as I know of the previous articles reviewer 2 refer to, but I have not studied them carefully. As a result, I am decreasing my confidence from 3 to 1 and my score from 7 to 6. 

I hope this does not discourage the authors, and wish them good luck with future research. 

___

### Summary 
**Objective:** train neural networks while retaining properties like invertibility or orthogonality of layers. 

**Approach:** instead of optimizing normal weights optimize an rank 1 update. Occasionally, the rank 1 updates are merged with the network parameters.  

### Strengths
**[+]** Preserving properties like invertibility is important and has been studied by much previous work. The authors present a novel approach based on rank 1 updates, which, to the best of my knowledge, is completely novel.  

**[+]** The article is very clearly written, it seems to me that the authors spent a great deal of time polishing the paper. 

### Weaknesses
**[-]** I have a minor concern wrt. optimization of rank 1 updates which I elaborate below. 

### Recommendation: 6
**[+]** The paper presents a novel approach for preserving invertibility, which could benefit many deep learning researchers. 

**[+]** The paper demonstrates how rank 1 updates can be used in deep learning, which I believe will inspire further research into this interesting direction. 

I condition my recommendation on an MLP experiment I already discussed with the authors before submitting this review. Furthermore, I'll re-evaluate my conviction after reading the comments by the other reviewers. 

### Questions 
The following question was already answered by the authors before the submission of this review. I repeat the question here for completeness. 

---

Recent research explore the idea that SGD variants perform better with networks that has more parameters. Informally, it is argued it is harder to get stuck at local minima when SGD can move in more directions. If one optimize rank 1 updates, SGD would have $2d$ directions to move in instead of $d^2$ directions. I am concerned this might impacts the performance of SGD. This concern would be address by the following experiment: train two MLPs on MNIST, one with SGD and one with $P^4$, do they attain similar loss curves?

---

### Additional Feedback
I didn't find any typos, the article seems to be very polished. 
review_title: Review: Nice idea and very clear writing, uncertain about concern raised by reviewer 2. 

final_score: rating: 2: Strong rejection
review_content: ***Summary and general comments:***

This paper presents a method to parametrize a set of constraints via a linear space that may change. This method was already studied in much more depth in [1], where this idea is explored through the lens of vector bundles and retractions on them, with a convergence result appearing in the follow-up work [2].

The authors then instantiate these ideas in the setting of normalizing flows via the Sherman–Morrison inversion formula.

***Questions:***

1) For instance, parameterizing the whole orthogonal group (via the Cayley parameterization or matrix exponentials of skew-symmetric matrices) is computationally expensive. In contrast, orthogonal matrices can be cheaply perturbed into other orthogonal matrices using double Householder transforms or Givens rotations.

Why is that the case? Could you please justify the first assertion?

What do you mean by "it can be cheaply perturbed into an orthogonal matrix"? The best orthogonal approximation to a given matrix is the orthogonal projection given by the polar decomposition. That is expensive.

2) "In contrast to this related work our method reparameterizes the update step during gradient descent rather than the parameter matrix itself"

This is not really different as explained in [1]. Using a dynamic trivialization changes the metric that you are working with, but you can still use it as a parametrization. In your example, it would account for changing the problem
$$\min_{x \in \operatorname{GL}(n)} f(x)$$
to
$$\min_{u,v \in \mathbb{R}^{2n}} f(X_0 + uv^\intercal)$$
for a fixed $X_0$ and changing the problem via the dynamic trivialization framework every $N$ steps. Using this formulation, you can let the optimizer do all the heavy lifting for you. See also 5)

3) Trivializations are known to have a problem with the momentum and adaptive term. I see that you use Adam in the training of the 2D distributions. How do you solve the problem of the incorrect momentum and adaptive terms when you change the base?

4) A general question. I do not understand what is the motivation behind using the low-rank update besides the fact that it allows for an (amortized) low cost of the inversion.

5) A follow-up of the previous question: How is $R_{X}(u,v) = X + uv^\intercal$ a sensible map to use? This map does not have its image on $\operatorname{GL}(n)$ but on all $\mathbb{R}^{n\times n}$! For example, $R_{-uv^\intercal}(u,v) = 0$ which is clearly not invertible. As such, I do not understand the claims in section 2.3 about this being a "fully flexible invertible layer". This is the reason behind having to use Algorithm 2 in P⁴Inv. Given that Algorithm 2 is used, what is the reason behind using this parametrization at all over just doing unconstrained optimization?


***Citations:***
- Lezcano-Casado & Martínez-Rubio do not use Givens rotations but the exponential. The first to use Givens rotations in the context of ML was [3].

- When it comes to Riemannian gradient descent, it is probably better to cite Absil's book [4] as a general reference rather than two recent papers, as this is a well studied topic.

- I would recommend to clean-up the bibliography, as there are many citations that point to the arXiv when the articles have indeed been published in peer-reviewed venues.

Minor:
- "which is a R-diffeomorphism" -> "an"

***Conclusion:***

I really like the first experiment for its simplicity, trying to elucidate the behavior of the layer. It is also nice to see the improvement that this idea gives over RNVP. At the same time, when it comes to the experiments, I believe that it would have been of interest to compare this approach with other known ways to parametrize invertible linear layers, such as those that use QR, SVD or Choleski factorizations.

That being said, as mentioned in 4) and 5) I do not see the reason for this being a good way to obtain invertible layers, given that even the image of the parametrization does not lie in GL(n). Furthermore, the ideas behind the framework presented in this paper were already studied in previous papers in much more depth.


[1] M. Lezcano-Casado. “Trivializations for gradient-based optimization on manifolds”. NeurIPS, 2019

[2] M. Lezcano-Casado. “Curvature-Dependant Global Convergence Rates for Optimization on Manifolds of Bounded Geometry”. https://arxiv.org/abs/2008.02517

[3] U. Shalit, G. Chechik. “Efficient coordinate-descent for orthogonal matrices through Givens rotations”. ICML, 2014

[4] P.-A. Absil, R. Mahony, and R. Sepulchre.Optimization algorithms on matrix manifolds. PrincetonUniversity Press, 2009- .
review_title: The general framework is not new

Meta-review: This paper discusses a method to update/optimise invertible matrices via low-rank updates. The key property of the proposed method is that it keeps track of the matrix inverse and its determinant through the optimisation (with updates that are much cheaper to compute than a direct inversion/determinant computation).

While the method of performing low-rank updates for invertible matrices itself has already been extensively studied in the literature as pointed out by reviews, this work focuses (after extensive revision) on the properties of this update method.
 Since the updates may leave the manifold of invertible matrices, a numerical stabilisation step was introduce whereby updates that produce ill-conditioned matrices are rejected during optimisation.

Rank-one updates allow for fast update of matrix inverse and determinants. So this is particularly interesting when applied to normalising flows, as it allows for cheaper computation of the log-det-Jacobian terms.  

The novelty of this approach is rather limited (as also pointed out by R2). The experiments and, in particular, the application to normalising flows are interesting, well-executed. It is not clear if there are advantages of the method in other domains where log-det-Jacobians are not necessary relative to existing literature.

Decision: Reject