Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: **Summary**:
Orthogonal matrices $d\times d$ can be represented using $d$ Householder reflections. This paper shows that it is sufficient and, of course, computationally faster to use only one reflection. 

Overall, I think the paper is not ready to be published yet. In the current version, the motivation for me is not clear. 


**Comments**:
- It’s hard to get the motivation to consider the presented approach from the paper. I would like to see a better and more detailed introduction on orthogonal matrices, its connection to neural networks. There is a phrase in the abstract “the only practical drawback is that many reflections cause low GPU utilization”. The word “only” does not really motivate, does it mean that it’s not that good in terms of accuracy?
- What is actually the accuracy of such representations? 
- Neural networks represented through Householder reflections are one layer neural networks with an identical activation function. Is it correct?  
- Do you have ideas for future works? 


**Minor**: 
- A lot of missed articles 
- “Much previous work attempt to alleviate the additional computational resources it requires to constrain weight matrices to be orthogonal.” - There is a problem here. 
- Abstract: no commas before “if”
- “because the d reflections needs“
- “It is the evaluation of these sequential Householder reflection that cause”
- “allows us simplify” -> to simplify 
- “to train invertible neural network as generative models” -> networks 
- “Newtons method” -> Newton’s 
- “Previous work demonstrate”
- “Section 2.3.2 then present”
- “invertibiliy”
- “is simple connected”
- “continously”
- “we finally arive”
- “a single auxiliary reflections”
- “where the 6orthogonal matrices where attained”
- “The RNNs with 1 auxiliary reflection attains”

review_title: The motivation is not clear

final_score: rating: 6: Marginally above acceptance threshold
review_content: #### Summary:
Constraining weight matrices to be orthogonal is a useful but resource-intensive task in DL. This paper presents a simple yet powerful approach that shows the sequential Householder reflection method can be replaced by a single learned reflection to achieve orthogonality more efficiently.

#### Pros:
- The paper provides both theoretical (for the linear case) and empirical evidence supporting their claims.
- Not being sequential in nature, the proposed method is more efficient on GPU.
- Relaxation of the invertibility constraint is interesting. Please see the ControlVAE work on PID based annealing, there might be some connection.

#### Cons:
- While I understand that the method can utilize GPU much better, empirical evidence will certainly help. 
- Since it is claimed that other methods trade-off expressiveness for compute efficiency, a quantitative analysis will help. Also, as a result of the compute efficiency, can the current approach tackle larger datasets?

 
review_title: Simple yet powerful approach.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper presents a method for representing orthogonal weight matrices of neural networks by simulating an arbitrary number of Householder reflections using an additional neural network to compute a single auxiliary reflection. 

My first concern with this paper is that it does not seem well motivated (at least from the perspective of a non-expert). It does not explain why orthogonal matrices are important. I am not an expert in this field and it is possible that this is obvious, but I think it could be better explained to convince a reader of the importance of the work. 

In terms of experimental results, the authors report an improvement in validation error for a classification task on MNIST data for a few different network architectures. It would be nice to see more comprehensive experiments. In particular to see some results on datasets other than MNIST. 

There are typo/grammatical errors in the paper's title and Figure 3 caption. 

Without a better motivation and explanation of it is important, or more comprehensive experiments, I would recommend this paper be rejected. 
review_title: Why is this work important? 

final_score: rating: 4: Ok but not good enough - rejection
review_content: ***Summary***
The authors present a way to learn the action of an arbitrary orthogonal matrix on a vector via a map from $\mathbb{R}^{n\times n}$ onto $\operatorname{O}(n)$. They show that the map is surjective, and give conditions under which they can invert this action. They then compare against previous proposed schemes in one task and show the performance of their models in other two.

***Comments***

Corollary 1. It should be $d > 2$, as $S^1$ is not simply connected. Also, for the proof, when you are bringing results from a book, please cite the exact theorems that you are using, as citing a 700 pages book is not of much help.

I do not see how proof of Theorem 4 is correct. You define $f(0) = 0$, but I do not see where you prove that $\lim_{x\to 0}f(x) = 0$, as in Lemma 3 you explicitly work on $\mathbb{R}^n \backslash \{ 0 \}$.

The paper puts all the proofs in the main paper. I believe that all these should be moved to the appendix, as they are just standard algebraic computations. A more in-depth study of the developed action could go (see next point). If anything, proof of Theorem 1 should be in the main text, as it is the result that drives the paper and its proof is one line.

Given the topology of $\operatorname{O}(n)$, which has two disconnected components, any surjective action from $\mathbb{R}^{n \times n}$ is bound to be discontinuous and, in particular, will have exploding gradients at some points. This can be problematic in some situations, yielding instability in more difficult models. I think that it would be very beneficial for the paper to show this in an experiment.

***Experiments***

The exponential map has been recently implemented in a very stable and fast way in PyTorch 1.7.0, getting some notable speed improvements over previous implementations. How does the method in this paper compare time-wise with this implementation?

Experiment 3.2. Why don't you compare against Helfrich (Cayley), Casado (Riemannian exponential) and Lezcano-Casado & Martínez-Rubio (matrix exponential)? Their results seem to converge faster and to a lower minimizer than those shown in this paper. Even if that is the case that is fine, but please add them to the paper for a fair comparison.

Related to the previous two concerns, the paper shows how this method is faster than the Cayley and Exponential map when just ONE product is computed. On the other hand, they do not show what happens in the setting of an RNN, where they method has to compute the action $768$ times, while the Cayley and Exponential are just computed once and used throughout the RNN.

Experiment 3.3. How is the determinant computed? If it is computed every iteration using Lemma 1 this would make the parametrisation too expensive to use in general normalising flows.

***Related work***

Under "Different Approaches." you mention that:
"the Cayley map (Lezcano-Casado & Martínez-Rubio, 2019) and the matrix exponential (Casado,2019)."
This is not the case. In (Lezcano-Casado & Martínez-Rubio, 2019), they use the matrix exponential, while in (Casado, 2019), they use the Riemannian exponential. The work that used the Cayley map to perform optimisation over $\operatorname{SO}(n)$ was
Helfrich, K., Willmott, D., and Ye, Q. Orthogonal recurrent neural networks with scaled Cayley transform. ICML 2018

***Minor***

Page 6. "to conclude $f(x)$ is" -> conclude that $f(x)$

Page 11. "Is an follows" -> Follows


***Conclusion***

I like the idea of the paper as it is conceptually simple and fairly well implemented. On the other hand, I have three big concerns about the paper.

First, I do not think that it is competitive with other approaches when it comes to efficiency. The paper does not benchmark against the previous approaches under common benchmarks (MNIST, PMNIST, TIMIT, treebank...) , even though it shows plots on these datasets (MNIST, PMNIST), which is suspicious. Even then, I do not think that every presented method should introduce themselves as improving the SoTA on a given task, as that is just not possible. On the other hand, I do think that the authors should find their niche, as I do not see how this approach would be preferable over simpler approaches like using the Cayley map or the exponential, as it has the drawback of not having explicit access to the inverse transformation, and it does need of a fairly expensive operation to compute the determinant of its Jacobian. I believe that the authors should present a strong case for why this method is practical and preferable in some context over others.

Second, I believe that the paper could do with some cleaning. The paper has too many computations in it, which does not add to the point it tries to make. This does not help elucidating where this method could be of use over other methods, as mentioned in the previous point.

Third, as show in Lemma 1, and due to the need of using spectral normalisation, it seems like the authors have transformed the problem of optimisation with orthogonal constraints onto a problem of optimisation over symmetric matrices with some non-trivial eigenvalue constraints, which is arguably more difficult! This relates to the first problem I raised, as I fail to see how this method can be more useful than previous approaches in any context.


review_title: Nice idea, but I fail to see where it could be useful

Meta-review: This paper proposes to use a single parametric Householder reflection to represent Orthogonal weight matrices.
It demonstrates that this is sufficient provided that we make the reflection direction a function of the input vector. It is also demonstrated under which conditions this modified transformation is invertible. The derivations are sound. 
This insight allows for cheaper forwarding of the model but it also comes with extra costs: It has an increased computational cost for inversion (e.g. requires optimisation) and, importantly, it does not allow to cache the $O(d)$ matrix so  it is not clear there is an advantage of the method over exp maps when we have parameter sharing (e.g. as in RNNs), since the action of the matrix has to be recomputed every-time. The presented experiments are OK, but comparisons to other (potentially more efficient) methods are lacking as pointed out by the reviewers. As it stands it is not clear that this is an idea of broad interest, perhaps more suited to a specialised venue such as a workshop.
Decision: Reject