One Reflection Suffice
Authors: Alexander Mathiasen
Frederik Hvilshøj
Venue:  (2021)
Keywords: Orthogonal Weights Householder Reflections Normalizing Flows

Abstract: Orthogonal weight matrices are used in many areas of deep learning. Much previous work attempt to alleviate the additional computational resources it requires to constrain weight matrices to be orthogonal. One popular approach utilizes *many* Householder reflections. The only practical drawback is that many reflections cause low GPU utilization. We mitigate this final drawback by proving that *one* reflection is sufficient, if the reflection is computed by an auxiliary neural network.

Under review as a conference paper at ICLR 2020
ONE REFLECTION SUFFICE
Anonymous authors Paper under double-blind review
ABSTRACT
Orthogonal weight matrices are used in many areas of deep learning. Much previ- work attempt alleviate the additional computational resources requires constrain weight matrices to be orthogonal. One popular approach utilizes many Householder reflections. The only practical drawback that many reflections cause low GPU utilization. We mitigate this final drawback by proving that one reflection is sufficient, if the reflection is computed by an auxiliary neural network.
INTRODUCTION
Orthogonal matrices have shown several benefits in deep learning, with successful applications in Recurrent Neural Networks, Convolutional Neural Networks and Normalizing Flows. One popular approach can represent any d x d orthogonal matrix using d Householder reflections (Mhammedi al. 2017). The only practical drawback low GPU utilization, which happens because the d flections needs to be evaluated sequentially (Mathiasen al., (020). Previous work often increases GPU utilization by using 1 < d reflections (TTomeza & Welling 2016 Mhammedi et al. 2017] Zhang et al. 2018 Berg et al. 2018). Using fewer reflections limits the orthogonal transformations the reflections can represent, yielding a trade-off between representational power and computation cireumvent the trade-off and attain full representa- tional power without sacrificing computation time?
time. This raises intriguing question:
We answer this question with surprising "yes.." The key idea is to to compute different reflection for each input. In theory, we prove that one such "auxiliary reflec- tion" can represent any number of normal reflections. In practice, reflection attains similar validation error to models with normal reflections, when training Fully Connected Neural Networks (Figure left), Recurrent Neural Networks (Figure center) and con- volutions in Normalizing Flows (Figure (Figure[rright) rrghht) Notably, auxiliary reflections train between 2 and 6 times faster for Fully Connected Neural Networks with orthogonal weight matrices (see Section
auxiliary neural network
demonstrate that auxiliary
Fully Connected Network
Recurrent Neural Network
Convolutions in Normalizing Flow
10
4.2
Many Reflections
8
One llayy Reflection
4.1
dalidation Error
Validation Errar
dation Error
3.9
4
3.8
2
3.7
0
0
3.6
0.0
2.5
5.0
7.5
10.0
20
40
60
50
75
100
Epochs
Epochs
Epochs
Figure I: Models with one auxiliary reflection attains similar validation error to models with many reflections. Lower error means better performance. See Section for details.

---

Under review as a conference paper at ICLR 2020
1.1
OUR RESULTS
The Householder reflection of E It around E Rdd can be represented by a matrix H()) E Rdxd
H(v)z (I (1-2 1
vy
An auxiliary reflection uses Householder matrix (v) with v n(x) for neural network n.
((x) H(n(x)) = (1 n(x))(()²
||(x)]]1
One auxiliary reflection can represent any composition of Householder reflections. We prove this claim even when restrict the neural network n(x)) have single linear layer n(x) Ww for W E Raxd such that f(z) ) = (W)x)..
Theorem 1. For any k Householder reflections U = ((i) (vx) there exists neural network (ax) Wr with W E paxd such that [(x) ([W)) Ux for all [00).
Previous work (Mhammedi et al. 2017 Zhang al. 2018) often employ k < reffecttins and com- pute Ur as k sequential Householder reflections H (2) )... H(v;) ([v)).z - with weights V (v) ... 2/.
is the evaluation of these sequential Householder reflection that cause low GPU utilization (Mathi- asen et al. 2020), so lower values of k: increase GPU utilization but decrease representational power. Theorem states that is sufficient to evaluate single auxiliary reflection H (W x) instead of reflections H (v1).-- ... H (vx) I, thereby gaining high GPU utilization while retaining the full repre- sentational power of any number of reflections.
In practice, we demonstrate that d reflections can be substituted with single auxiliary reflection without decreasing validation error. when training Fully Connected Neural Networks (Section 3.1), Recurrent Neural Networks (Section 3.2) and Normalizing Flows (Section 3.3) While the use of auxiliary reflections is straightforward for Fully Connected Neural Networks and Recurrent Neural Networks, we needed additional ideas to support auxiliary reflections in Normalizing Flows. In particular, we developed further theory concerning the inverse and Jacobian f(x) H (.. Note that f is invertible if there exists unique given y = H(W x and W.
Theorem 2. Let f(x) = H(Wx)x with f(0) == 0, then f is invertible on Rd with d 2 2 if W W and has eigenvalues which satisfy 3/2- Amin (W) > Am).
Finally, we present matrix formula for the Jacobian of the auxiliary reflection f(x) H(W))r. This matrix formula is used in our proof of Theorem 2 but it also allows us simplify the Jacobian determinant (Lemmal] [ which needed when training Normalizing Flows.
Theorem 3. The Jacobian of f(x)
W Wax
W I
J = H( x
where A 2
W.
We prove Theorem [ in Appendix
A.1.I while Theorems and are proved Section 2
2 NORMALIZING FLOWS
2.1 BACKGROUND
Let ~ NN, 1)a and f be an invertible neural network. Then (2) Pmodet defines a model distribution for which we can compute likelihood of x Paota (Dinh et al., 2015
(8f())
log Pinodet (z) log p=(((x)) log det
(1)
Ox
This allows train invertible neural network as generative models by maximum likelihood. Previous work demonstrate how to construct invertible neural networks and efficiently compute the log jacobian determinant DDinh et al. 2017 Kingma & Dhariwal 2018 Ho al. 2019).
2

---

Under review as a conference paper at ICLR 2020
2.2 INVERTIBILITY AND JACOBIAN DETERMINANT (PROOF SKETCH)
To use auxiliary reflections in Normalizing Flows we need invertibility. That is, for every E Rd there must exist unique IRd so [(x) Jacobian determinant is non-zero for all x in S (x E IR. [=]]=
((Wa)) -y We find that I is invertible if its
Theorem 4. Let f(x) H H(wx)r with f(0) = 0, then f is invertible on Bd with d 2 2 if the Jacobian determinant of f is non-zero for all æ E S and W is invertible.
The Jacobian determinant of H(Wx)r takes the following form.
Lemma 1. The Jacobian determinant of {(x) H(Wx)a is:
-det(A) ( A A-1w
TTT 1|
where T = x L,,,,o W, u = Wx and
W.
1|2113
is then sufficient that det,(A) (A) * 0 and 1 + 2v A A / O. We prove that this happens W W with eigenvalues 3/2nAmin (W) Amax (W). This can be achieved with W = VVV
if we guarantee maax (VVV) < 1/2 by spectral normalization (Miyato et al. 2018). Combining these results yields Theorem 2
Theorem 2. Let ((x) = H()x) with s(0) = O, then f is invertible on Re with d 2 if W W and has eigenvalues which satisfy 3/2 (w) Am).
Computing the Inverse. In practice, we use Newtons method to compute x so H (Wz)æ y. Figure 2 show reconstructions (n(x)) x for invertible neural network n with auxiliary reflections using Newtons method, see Appendix A.2.1 for details.
x
n (m(x))
Figure 2: CIFARIO Krizhevsky al. 2009) images x and reconstructions n (n+))())) for an vertible neural network n called Glow (Kingma & Dhariwal, 2018). The network uses auxiliary reflections and we compute their inverse using Newtons method, see Appendix A.2. for details.
2.3 PROOFS
The goal of this section is to prove that f(x) = H ((w)a ) is invertible. Our proof strategy has two parts. Section 2.3.1 1 first shows f invertible it has non-zero Jacobian determinant. Section (ection2.3..2 then present an expression for the Jacobian determinant, Lemma [ and prove the expression is non-zero if W = W and 3/2 Amin (W) Amin
2.3.1 NOR-ZERO JACOBIAN DETERMINANT IMPLIES INVERTIBIL.TT
In this section, prove that fx) H(Wr)æ is invertible Rd if f has non-zero Jacobian determinant. To simplify matters, we first prove that invertibility on 5dl impliis invertibility on Rd. Informally, invertibility on gd-1 is sufficient because H(Wx) is scale invariant, i.e. H(c Wx) H(Wx) for all e o 0. This is formalized by Lemma
Lemma 2. If (x) (WW x: is invertible on s it is also invertible ({0).
Proof. Assume that f(x) is invertible on Sd-1 Pick any y' E Rd such that ||8/l| = c for any c 0. Our goal is to compute x' such that (Wr'')'' y' By normalizing, we see y/ /|yy'l| sd-1 We can then use the inverse f-1 on y //le/1 to find such that ((Wx)x= y/ //ly// The result is then -l|l|| since H H(Wz')z H H( x > = y due scale invariance of H(Wx).
Note that do know HWw)) we cannot trivially compute I H(Wx) -'y H(Wa)y-

---

Under review as a conference paper at ICLR 2020
The main theorem use prove invertibiliy Sd is variant of Hadamards global function inverse theorem from (Krantz& & Parks 2012). On a high-level, Hadamard's 's theorem says that a function is invertible if has non-zero Jacobian determinant and satisfies a few additional conditions. turns out that these additional conditions are meet by any continuously differentiable function f(x) when (in the notation of Theorem 5) Mi M2 Sa-1
Theorem 5. (Krantz & Parks 2012 6.2.8) Let M1 and M2 be smooth, connected N-dimensional manifolds and let J M, M2 be continuously differentiable. (f) J is proper, (2) the Jacobian of I is non-zero, and (3) M2 is simple connected, then J is invertible.
For M1 -M Sd the additional conditions met if f continuously differentiable.
Corollary 1. Let f 5 - Sd-1 with 2 2 be continuously differentiable with non-zero Jacobian determinant, then is invertible.
Proof. Note that Sd-1 is smooth and simply connected if 2 2 Lee 2013
Continuously functions
on 1 are proper. We conclude is invertible on Sd by Theorem
We now show that (c) (War) is continuously differentiable on S Lemma 3. The function (x) H (Wwx) x) continuously differentiable on S if invertible.
Proof. Compositions of continuously differentiable functions are continuously differentiable by the chain rule. All the functions used to construct H H(W (Wr)æ are continuously differentiable, except the division. However, the only case where division is not continously differentiable is when |[ax| = O. Since W is invertible, |Wæ|| 0 iff 0. But 0 & S and conclude f is continuously differentiable on 5d-1
Theorem 4. Let f(x)= = H(Wx), with f(0) == O, then f is invertible on Red with d 2 if the Jacobian determinant of f is non-zero for all x E S and W is invertible.
Proof By Lemma 3] we see f is continuously differentiable since W is invertible, which by Corol- lary I meeass is invertible 5dd if f has non-zero Jacobian determinant on 5d-1. .. By Lemma 2 we get that f is invertible on TRd if has non-zero Jacobian on S 1
2.3.2 ENFORCING NON-ZERO JACOBIAN DETERMINANT
The goal of this section is present conditions on W that ensures the Jacobian determinant of f(r)
non-zero for all x E Sd-1, We first present matrix formula for the Jacobian of in Theorem
By using the matrix determinant lemma, we get formula for the Jacobian determinant Lemmal
By investigating when this expression can be zero, finally arive Lemma 4 which states that the Jacobian determinant is non- non-zero (and f thus invertible) W WT and 3/2-
Amin Amax-
Theorem 3. The Jacobian of fxx
H (WWx) is: WxxTW
WT |
J H=H(Wx)A-
where A= 2
W.
|| x
See Appendix A.2.2 for PyTorch implementation of J and test against PyTorch autograd.
Proof. The (i,j)'th 'hh entry of the Jacobian determinant is, by definition,
0(r x 2 Was" F WT I
TW i- a(Wx), 1
0x,
Then, by the product rule, we get a(Wx);
=F TW
a Fw [
a(Wz),
x TT
+ (W.);:
Ozz
Oz,
[[ x
0x,
x7 xT
Ox. WT ||Wi||2
Wi
+ (Wz),
>|>
4

---

Under review as a conference paper at ICLR 2020
The remaining derivative can be found using the product rule.
OxTW' "TT [W
Dr"
[ + +T" [|
1
0zz
First,
Petersen & Pedersen 2012) equation (81) gives 0r 0="W"= d2;
((WT + W)z)5.
Second
I|W xl can be found using the chain rule:
6 Wx
a(ll 112) a W
Jmg
W 12
On NeTWTWE W.
||
dr
1
(WWTW- + (WTW)")a))
(Petersen & Pedersen
2012 equ. 81)
||
|| ((WWxx)
Combining everything we get TTTTTx Jiy 1 [[[
Wú + (Wz);
(wlai ((WT + +W)2),
1
TT
(WTT)))))
||
In matrix notation, this translates into the following, we let A - [[
=" W.
1-1-2
r F'WFx x ||>]| x TTTTx ||>r|
W + Wx
[ x xT(W + WT) 2x W x
1
WTW)
1|
W 2 WaxTW
2- Wxx
(1 (1-2- xTTT=
=1-2
W
1|
||
1|
Wxa"W
Wxx WT
1|
[Wx|2
WaxTW"
Wxx W
Wxx |
-
H(Wx)
||
||x]
This concludes the proof.
Theorem allows us write J as a rank one update M + ab? for a, b E Ted which can be used to simplify (J) as stated in the following lemma.
Lemma 1. The Jacobian determinant of (xx) = H(Wx)) x)x is:
-de((A) (1+2 1
where vT = x TT,, u Wx and A = 1 WT
W.
|
1|
Proof. The matrix determinant lemma allows us write det + ab²) det( 6² M- Let M = H ((Wx)) A and b" = - x x"W//|Waa 21 and = Wx. The Jacobian J from Theorem then J .M abT. The determinant of J is then:
dJt = del(
M-
= det det(H((Wx)) AA 1-22 ((((w))) A)-"
||xx
-ed((A)) 11+2 x. --WA---a
||Wx||2
This is true because H(x))-1 HW)), H(Wx) Wa Wr and det (H((H)))))
We Lemma I to investigate when the Jacobian determinant is non-zero. In particular,
the Jacobian determinant must be non-zero if both det (A) * 0 and 1 1 TA u/|lu|l A O. the following lemma, we prove that both are non-zero if W WT and 3/2 Amin Amax-

---

Under review as a conference paper at ICLR 2020
Lemma 4. Let W WT and 3/2 Amin Amax then (A(A-)) -1/2 for A from Lemmal 1
These conditions imply that det(A) # 0 and + 20 u//lu// + #0 with v", u from Lemmal
Proof. We first show that the inequality 3/2- Amin (W) > Amax (W) implies {A(A7)) -1/2..
>x(AT²)=
((AA) 1 2
WT X.())
TWTT If IO TWai X(WW) E (1/2,3/2) we get that 1/(1-271) (-00, >; < 11/2.
==WT, x² p'W-iv This is the Rayleigh quotient of W-1 at y. which
we let y = Wr we get [Wa]
all
for W WT is within [Amin (W-1), Amax (W (W- Therefore 7' (W) Amin(W) (W)
Note first that Ymmn Σ and "mmax 2 1. It is left to show that Tymin 2 Amin/ Amax > 1/2 and 7max I max/ Ami < 3/2. Both conditions on eigenvalues are met if 3/2 Amin
Amax.
We now want to show that (e)(A) + 0 and 1 20"T===="" A * O. First, notice that det(A) IH (A) * 0 since (A) < -1/2. Second, note that W W implies that the v² from Lemma 1 can be written v" ="' x. W'" w², This means only need to ensure w 1---w. u/ ||u|| I2 the Rayleigh quotient of A at u, different to -1/2. But W = W implies W. The Rayleigh quotient is therefore bounded by [Amia (A-1), Amax (A 1) which means it is less than - 1/2 since Ax < 11/2. We can then w||2 u-
A = A because A = I 2x 2x" 'z 2/|[W>>]
conclude that also + 20 12--A-110
2n A 1011w/1 w/12 1 + 2 1/2
So det(J) + 0 by Lemma 4 and Lemma which by Theorem implies invertibility (Theorem
Remark. Note that the constraints W WT and 3/2 . Amin Amax were introduced only to guarantee det( * 0 and 1 + 20 A A-1u//lu/ 2 * 0. Any argument constraints on W that ensures (A) (1 o A u [/])) F are thus sufficient to conclude f(r) is invertible.
A-
EXPERIMENTS
We compare a single auxiliary reflections against d normal reflections when training Fully Con- nected Neural Networks (d = 784), Recurrent Neural Networks (d = 170) and Normalizing Flows (d = 48). The experiments demonstrate that neural networks with single auxiliary reflections attain similar performance to neural networks with many normal reflections. All plots show means and standard deviations over 3 runs. See Appendix for experimental details.
3.1 FULLY CONNECTED NEURAL NETWORKS
We trained four different Fully Connected Neural Networks (FCNNs) for classification MNIST. We compared a FCNN with 6 auxiliary reflections against FCNN with orthogonal matrices each represented by 784 normal reflections. For completeness, we also trained two FCNNs where the 6 orthogonal matrices where attained by the matrix exponential and Cayley map, respectively, as done in (Casado 2019 Lezcano-Casade & Martinez-Rubin Rubio 2019). The FCNN with auxiliary reflections attained slightly better validation error, see (Figure 3 left). Furthermore, we found the auxiliary reflections were to 6 times faster than competing methods, see (Figure3righht) This was true even though we used (Mathiasen et al. 2020) to speed up the sequential Householder reflections. See Appendix B. for further details.
3.2 RECURRENT NEURAL NETWORKS
We trained three Recurrent Neural Networks (RNNs) for classification MNIST as done in [Mhammedi et al. 2017). The RNNs had a transition matrix represented by one auxiliary reflec- tion, one normal reflection and 170 auxiliary reflections. See (Figure left) for validation error during training, including the model from (Mhammedi et al.) 2017). As indicated by the red curve, using only normal reflection severely limits the transition matrix. In the right plot, we magnify the first 20 epochs to improve readability. The RNNs with 1 auxiliary reflection attains similar mean validation accuracy the RNNs with 170 normal reflections. See Appendix B.2 B.2 further details.

---

Under review as a conference paper at ICLR 2020
Fully Connected Neural Network
10
10
Many Reflections
One Auxillary Reflection
Validation Error
Validation Error
(Casado, 2019)
6
(Casado Rubio, 2019)
2
2
8
10
0
100
200
300
Epochs
Seconds
Figure 3: MNIST validation classification error in over epochs (left) and over time (right). Lower error mean better performance.
Recurrent Neural Network
Recurrent Neural Network (zoom)
Many Reflections
80
30
One Auxillary Reflection
Validation Error
Validation Error
25
One Reflection
60
(Mhammedi al., 2017)
20
15
10
5
30
Epochs
Epochs
Figure 4: MNIST validation classification for RNNs performing classification done in Mhammedi et al., 2017). To improve readability, the right plot magnifies the first 20 epochs of the left. Lower error means better performance.
3.3 NORMALIZING FLOWS AND CONVOLUTIONS
We initially trained two Normalizing Flows (NFs) on CIFARIO. Inspired by (Hoogeboom et al., 2019), we used reflections parameterize the 1xl convolutions of an NF called Glow (Kingmal & Dhariwal 2018), see Appendix B.3 for details. We trained an NF with many reflections and an NF with a single auxiliary reflection constrained to ensure invertible (see Section 2.2 The single auxiliary reflection attained worse validation NLL compared to the model with 48 normal reflections.
We suspected the decrease in performance was caused by the restrictions put on the weight matri- ces W, of the auxiliary reflections to enforce invertibility, i.e., W, W and 3/2 Amin (Wa) > Amax To investigate this suspicion, we trained model with no constraints on W. This im- proved performance to the point were one auxiliary reflections tied with many normal reflections (see Figure
Even though the resulting auxiliary reflections are not provably invertible, we found that Newtons method consistently computed the correct inverse. Based on this observation, we conjecture that the training dynamics caused the auxiliary reflections to remain invertible. By this mean that the auxiliary reflections were initialized with non-zero Jacobian determinants (see Appendix B.3) and the loss function (Equation (I) encourages the auxiliary reflections increase their Jacobian determinants during training. Since Newtons method consistently computed the correct inverse, we were able to generate samples from all models, see (Figure right). right).

---

Under review as a conference paper at ICLR 2020
Normalizing Flow with Orthogonal Convolutions
4.4
Provably Invertible Auxillary Reflection
4.2
"Free" Auxillary Reflection
Validation
4.0
3.8
g
3.6
20
40
60
80
100
Epochs
Figure 5: (Left) Validation negative log-likelihood (NLL) of three Normalizing Flows CIFARIO. NLL is reported in bits per dimension, lower values mean better performance. (Right) Samples generated by different models, this required computing the inverse of auxiliary reflections.
4 RELATED WORK
Orthogonal Weight Matrices. Orthogonal weight matrices have seen widespread use in deep learning. For example, they have been used in Normalizing Flows (Hoogeboom al. 2019). Varia- tional Auto Encoders (Berg et al. 2018), Recurrent Neural Networks (Mhammedi et al. 2011) and Convolutional Neural Networks (Bansal et 2018).
Different Approaches. There are several ways of constraining weight matrices to remain thogonal. For example, previous work have used Householder reflections (Mhammedi et al. (017). the Cayley map (Lezcano-Casade & Martinez-Rubio, 2019) and the matrix exponential (Casado 2019). These approaches are sometimes referred to as hard orthogonality constraints, as opposed soft orthogonality constraints, which instead provide approximate orthogonality by using, e.g., regularizers like || WWWT T - 1 (see (Bansal et al. 2018) for a comprehensive review).
Reflection Based Approaches. The reflection based approaches introduce sequential computa- tions, which is, perhaps, their main limitation. Authors often address this by reducing the number of reflections, as done in, e.g., (Tomezak & Welling, 2016 Mhammedi et al. 2017 Berg et al. 2018). This is sometimes undesirable, as it limits the expressiveness of the orthogonal matrix. This moti- vated previous work to construct algorithms that increase parallelization of Houscholder products,
see, e.g. (Mathiasen et al. 2020 Likhosherstov et al. 2020).
Similar Ideas. Normalizing Flows have been used for variational inference, see, c.g., Tomezak & Welling 2016 Berg et al. 2018). Their use of reflections is very similar to auxiliary reflections, however, there is very subtle difference which has fundamental consequences. For full apprecia- tion of this difference, the reader might want to consult the schematic in (Tomezak & Welling 2016 Figure however, we hope that the text below clarifies the high-level difference.
Recall that auxiliary reflections compute (W so H(Wx) x)) can depend on x. In contrast, the previous work variational inference instead compute H()) where v and both depend on x. This limits (v) in that it can not explicitly depend on z. While this difference is subtle, it means our proof of Theorem I does hold for reflections as used in (Tomezak & Welling 2016).
CONCLUSION
In theory, we proved that a single auxiliary reflection is as expressive as any number normal reflec- tions. In practice, we demonstrated that single auxiliary reflection can attain similar performance to many normal reflections when training Fully Connected Neural Networks, Recurrent Neural Net- works and Normalizing Flows. For Fully Connected Neural Networks, reduced training time by a factor between 2 and 6 by using auxiliary reflections instead of previous approaches to orthogonal matrices (Mhammedi et al. 2017
Azcano-Cassad & Martine7-Rubio 2019; Casado 2019).
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary Evolution Recurrent Neural Networks. In ICML, 2016.
Nitin Bansal, Xiaohan Chen, and Zhangyang Wang. Can We Gain More From Orthogonality Regu- larizations in Training Deep Networks? In NeurlPS, 2018.
Rianne van den Berg, Leonard Hasenclever, Jakub M Tomezak, and Max Welling. Sylvester Nor- malizing Flows for Variational Inference. Conference on Uncertainty in Artificial Intelligence (UAI), 2018.
Mario Lezcano Casado. Trivializations for Gradient-Based Optimization on Manifolds. NeurlPS, 2019.
Laurent Dinh, David Krueger, and Yoshua Bengio. NICE: non-linear independent components esti- mation. In ICLR, Workshop Proceedings, 2015.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density Estimation using Real NVP. In ICLR, 2017.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. (RMSProp) Neural Networks for Machine Learning Lecture 6a: Overview of Mini-Batch Gradient Descent. 2012.
Jonathan Ho, Xi Chen, Aravind Srinivas, Yan Duan, and Pieter Abbeel. Flow++: Improving flow- based generative models with variational dequantization and architecture design. In ICMI., 2019.
Emiel Hoogeboom, Rianne Van Den Berg, and Max Welling, Emerging Convolutions for Generative Normalizing Flows. In ICML, 2019.
Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. ICLR, 2015.
Durk P Kingma and Prafulla Dhariwal. Glow: Generative Flow with Invertible Ixl Convolutions. In NeurlPS, 2018.
Steven G Krantz and Harold R Parks. The Implicit Function Theorem: History, Theory, and Appli- cations. Springer Science & Business Media, 2012.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning Multiple Layers of Features from Tiny Images. 2009.
John M Lee. Smooth Manifolds. In Introduction Smooth Manifolds. 2013.
Mario Lezcano-Casado and David Martinez-Rubio. Cheap Orthogonal Constraints in Neural Net- works: Simple Parametrization of the Orthogonal and Unitary Group. ICML, 2019.
Valerii Likhosherstov, Jared Davis, Krzysztof Choromanski, and Adrian Weller. CWY Parametriza- tion for Scalable Learning of Orthogonal and Stiefel Matrices. arXiv preprint arXiv:2004.08675; 2020.
Alexander Mathiasen, Frederik Hvilshoj, Jakob Rødsgaard Jørgensen, Anshul Nasery, and Davide Mottin. Faster Orthogonal Parameterization with Householder Matrices. In ICMI, Workshop Proceedings, 2020.
Zakaria Mhammedi, Andrew Hellicar, Ashfaqur Rahman, and James Bailey. Efficient Orthogonal Parametrisation of Recurrent Neural Networks Using Householder Reflections. In ICML, 2017.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral Normalization for Generative Adversarial Networks. In /CLR, 2018.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic Differentiation in PyTorch. 2017.
Kaare Brandt Petersen and Michael Syskind Pedersen. The Matrix Cookbook, 2012. Technical University of Denmark, Version 20121115.

---

Under review as a conference paper at ICLR 2020
Jakub M Tomezak and Max Welling. Improving Variational Auto-Encoders using Householder Flow. arXiv preprint 1rXiv:1611.096300 2016.
Ruye Wang, Lecture Notes: Householder Transformation and QR Decomposition, 2015, URL http:://ourreet eng. hmc. www.eddlllleeeeee
htt.eeen..cceeeeel////eeeeeeeeee http://////eeeetttee/////////ee/ 0hmml
Jiong Zhang, Lei, and Inderjit Dhillon. Stabilizing Gradients for Deep Neural Networks via Efficient SVD Parameterization. In ICML, 2018.
10

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 PROOFS
A.1.1 THEOREM
Our proof of Theorem is an follows Lemma which we state below.
Theorem 1. For any k Householder reflections U (.. (vu) there exists a neural network n(x)= = Wx with W E Raxd such that [(x) H(W Un all E (RA) (0).
Proof. Let W = I-U then H(W x) =
= Ux for all x E IR since |U=||| = ||-|||-
Lemma S. Let |||||| = lvll then Hxx - y)x = y.
Proof. The result is elementary, see, e.g., (Wagg 2015). For completeness, we derive it below.
y) (xr y)
H(x - y)æ =
|| - w1 T
x. T + yy xy² yxu
= x - 2
x² x. + y1 y 2x y E
xx.' T x0 + yn x 24 x - yx Ta
= x 2
x² x + y²
2x y
x: |:||0||| + yy x ry T x y y|120]
x
2/ 2 - 2x y
(xr
|>/| + (y - x) (v)
x
| x y
(x
|>11 + (y - xz) (uT xx)
||0||| x y
x
\|(1211 vTvv)
| x²-'
(x
y) = y

---

Under review as a conference paper at ICLR 2020
A.2 PYTORCH EXAMPLES AND TEST CASES
To ease the workload on reviewers, we opted to use small code snippets that can be copied into www.colab.research wwwpchhgooogg.oooooo and run few seconds without installing any dependencies. Some PDF viewers do not copy line breaks, we found viewing the PDF in Google Chrome works.
A.2.1
TEST CASE: INVERSE USING NEWTONS METHOD
Given y we compute z such that H(Wr) = using Newtons method. To be concrete, the code below contains toy example where TRd and W I+VVT /2-0 max (VVT)) R R4x4 The par- ticular choice of W makes H (Wæ)r invertible, because >: = 1+ (VVT) = 1 oV+ (1,3/2) because VVT is positive definite. Any possible way of choosing the eigenvalues in the range [1, 3/2) guarantees that 3/2 Amin > Amax which implies invertibility by Theorem
import torch print ("torch version: ", verchin Dorch.manullsseede
Create randon test-case.
I torch.eye (d) (d)
V = torcs. (d, ) uuniform_m
= torch.zeros( (d, _ caniform_f
V V.T torch.svd
V.T) [1] ()
Define the function (x) =H x.
def : return torch.eye (d) 2 v e V.I / (v.I 0 v)
def (()): return H( 8 x 3
Print input and output
print ("x)t\t", x.data.vies (-1). ())
print (*f(x) (()) data.vvess (-1) numpy ())
print (*")
Use Newtons Method compute inverse. y f(x) xi y
for i in range (10):
print
10), xi xi.data.viow numpyy ())
# Compute Jacobian using Theorem 3. (dr
(xi.f W.T ê xi) torch. norm (W xi) **2 x
J = -222 xi 0 xi.T a w/torch.ncrm (wt.nnrrm(((x))-e... x*2 + H xi) E A
xi = xi inorrseinvereeeee
@ (#(xi)-
assert allcose (xi, x, ato1=10+*<-11)
print ("The two vectors are torch.
torch versien: 1.6.0+cu10z
(0.8854429 0.57390445 0. 0.26658005 0. 6.74449915
(x)
[-0.77197534
-0.49936318
-0.5985155
-0.6120473
[01/10]
[-0.77197534
-0.49936318
-0.5985155
-0.6120473
[02/10]
0.72816867
0.78074205
-0.02241153
1.0435152
[03/10]
[0.7348436
0.6478982 0.14960966 0.8003925
[04/10]
[0.8262452
0.6155189 0.2279686 0.6997254]
[05/10]
(0.8765415
0.5831212 0.2525551 0.640691
[06/10]
(0.8852093
0.5742159 0.26631045 0.6278922
[07/10]
(0.88543946
0.5739097
0.26658094 0.62744874)
[08/10]
[0.88544315
0.57390547
0.2665805
0.6274475
[09/10]
[0.885443
0.57390594
0.26658088
0.6274466
[10/10]
18.8454088
0.57390743 0.2665809
0.6274484
The two vectors are torch.
12

---

Under review as a conference paper at ICLR 2020
Figure 2 contains reconstructions n= (n(2)) of the variant of Glow (Kingma & Dhariwal 2018) used in Section 3.3 The Glow variant has Ixl convolutions with auxilarr re- flections, I.c., for input E x where (c, h, w) (channels, heigh, width) it computes 2,úy
Figure 2
(..., E IR where = 1.... h and j = 1,.., w. Computing the inverse required computing the inverse of the auxiliary 1x1 convolutions, i.e., compute F.,i. given W and 2.j.j vi, j- The weights were initialized as done in the above toy example.
A.2.2 TEST CASE: JACOBIAN AND AUTOGRAD
import torch
print (*torch version: ", vorshi_ (orch.mamual_seed(11)
Create random test-case.
d =
torch. (d, d) .n).uuformmm (-1, 1) x torch. zeros (d, 11) (- 1) torch.eye (d)
Compute Jacobian using autograd. def ( return 2 v.r (v.I 0 vl
def (x) : return A( x 3
= torch. autograd wwu.torrra..untiinnna.. jacobian x) [t, 0, 0]
print (J)
Compute Jacobian using Lemma 4.
I (x.T W.T x) / terch.nora (W 8 x) + +
J_ H(W e x) A 2*M 8 x x.T 0 s/torch.norm (W3x) **2
print (J_)
Test the two matrices are close. assert torchoallclose. (J, J,, atol=10+*(-51)
print ("The two matrices are torch.allclose")
torch version: 1.6.0tcu101
tensor [[[ 0. 0.2011, -1.4628, 0.7696, -0.5376),
0.3125, 0.6518,
0.7197, -0.5997],
[-1.0764,
0.8388,
0.0020, -0.1107),
[-0.8789, -0.3006,
-0.4591,
1.370111)
tensor [[[ 0.2011, -1.4628,
0.7696,
-0.53761,
0.3125,
0.6518,
0.7197, -0.5997),
[-1.0764,
0.8388,
0.0020, -0.1107],
[-0.8789, -0.3006,
-0.4591,
1.3701]])
The two matrices are torchee
13

---

Under review as a conference paper at ICLR 2020
B EXPERIMENTAL DETAILS
In this section, we specify the details of the three experiments presented in the Section 3 The experiments were run on single NVIDIA RTX 2080 Ti GPU and Intel Xeon Silver 4214 CPU @ 2.20GHz.
B.1 FULLY CONNECTED NEURAL NETWORKS
For the experiment Section 3.1 we trained four Fully Connected Neural Networks (FCNNs) as MNIST classifiers. All FCNNs had the same structure which now explain. Inspired by ZZang their Singular Value Decomposition
et al. 2018) the layers of the FCNNs were parametrized (SVD). This just means each layer consisted of two orthogonal matrices U, U.V I and diagonal matrix E 784xx784 so the forward pass computes y UEVT x. The FCNNs had three such fully connected layers with relu non-linearity in between, and final linear layer of shape W E 781111 We used the Adam optimizer (Kingma & Ba 2015) with default parameten to minimize cross entropy. To speed up the network with 784 normal reflections, we used the FastH algorithm from (Mathiasen et al. (2020). For the network with auxiliary reflections, we had U, V be auxiliary reflections instead of orthogonal matrices. all experiments, we initialized the singular values Eij ~ (0.99, 1.01).
We used orthogonal matrices with reflections, the Cayley transform and the matrix exponential as done in (Mhammedi et al., 2017;; Casado 2019 Lezcano-Casan & Martinez-Rubio 2019). respec- tively. The orthogonal matrices are constructed using a weight matrix W. all cases, we initialized We ~ U[ Va Val. It is possible one could initialize W,, in smarter way, which could change the validation error reported in Figure That said, did try to initialize W using the Cayley initialization suggested by (Casado 2019) However, we did not find it improved performance.
B.2 RECURRENT NEURAL NETWORKS
For the experiment Section 3.2 we trained three Recurrent Neural Networks as MNIST classifiers
done in (Arjovsky et al., 2016 Mhammedi et al. 2017: Z Zhnng et al. 2018 Casado 2019). We
used the open-source implementation from (Casado 2019 They use clever type of "Cayley initialization" to initialize the transition matrix U. We found worked very well, so choose to initialize both the normal and auxiliary reflections so they initially represented the same transition
matrix U. For normal reflections, this be done by computing V1,-.., Ua so H1 ... Ha U by using the QR decomposition. For the auxiliary reflection, this can be done using W = 1 U so H (W Uz (see Theorem 4
In (Casado 2019). they use ha = 0 initial state and report "We choose as the initial vector ho = for simplicity, as we did not observe any empirical improvement when using the initialization given in (Arjovsky et al. (2016)." We sometimes encountered division by zero with auxiliary reflections
when hg = 0, so we used the initialization suggested by (Arjovsky et al. 2016) all experiments.
The open-source implementation (Casado) 2019) use RMSProp (Hinton et al. 2012) with different learning rates for the transition matrix and the remaining weights. This was implemented in PyTorch by using two R.MSProp optimizers. We found training auxiliary reflectons to be more stable with Adam (Kingma & Ba 2015). We believe this happens because the "averaged gradients" v become very small due to the normalization term >| l in H(Wx)æ = 2Wx." WF x>>// When e becomes small the scaling 1/(v2 e + e) of RMSProp becomes very large. We suspect the 1/(Vv/(11 3T) +e) scaling used by Adam fixed the issue, which caused more stable training with Adam. This caused us to use Adam optimizer for the transition matrix instead of RMSProp for all the RNNs we trained.
"Default parameters of the Adam implementation in PyTorch 1.6 https://gthhh.com/lcccca///pppp
Paszke et al 2017
14

---

Under review as a conference paper at ICLR 2020
B.3 NORMALIZING FLOW
For the experiment in Section 3.3 we trained three Normalizing Flows as generative models on
IO done in (Dinh al. 2015 2017 Kingma & Dhariwal 2018 Ho al. 2019). We used an open-source PyTorch implementation of Glow (Kingma & Dhariwal 2018 with default parameters, except for the number of channels "-C" and the number of steps "-K." particular, to decrease training time, we reduced "-C" from 512 to 64 and "-K" from 32 to 8. This caused an increase in validation NLL (worse performance) from 3.49 3.66 after 80 epochs.
Auxiliary Reflections for 1x1 Convolutions. Kingma & Dhariwal 2018) suggested using in- vertible 1 x convolutions for Normalizing Flows. That is, given an input x E Rexhxx and kernel W E Rcxc they compute ²,,.,j W for all j. The resulting function invertible if W is, and has Jacobian determinant hwe det was suggested by (Hoogeboom et al. 2019) to represent det(WW) dct(QR)
det(() det(R) det()))ec()))))) det RR) = II; R.i- To this end, they represent the orthogonal matrix Q as a product of reflections, in particular, they use 12, 24, 48 reflections at different places in the network. The main goal of this experiment, was to compare = 12, 24, 48 normal reflections against single auxiliary reflection. which computes 2. [[W..... Jas. instead of 2,,.j Wx.... To isolate the difference in performance due to reflections, we further removed the rectangular matrix.
W in its QR decomposition
Provably Invertible. One the Normalizing Flows with auxiliary reflections had the weights of its auxiliary reflections constrained to ensure invertibility. In particular, we let each weight matrix be W I+ VVT and used spectral normalization VVT 00777(22) (2o (VVT)) to ensure o, (VV')) < 1/2. The largest singular value be computed efficiently using power iteration (Miyato et al. 2018) For ease of implementation, we circumvented using power iteration due to known open issue the official PyTorch implementation. We instead used TORCH.SYMEIG value by computing the largest eigenvalue Amax(VV2 positive definite for V _ This was only possible because the matrices where at most 48 x 48, for larger problems one would be forced to use the power iteration.
compute the largest singular o max (VVT), which holds because VVT
Q with Q from For the case with normal reflections, we computed U1, Ve such that (v1) ... H(v)) = Q Wang 2015 For the auxiliary reflection without con- straints we let W I Q such that H H(W F H( Qz) Qx by Lemma
Initialization. TORCH.QR (TTTCCC.RANNX(CCCC))CCCCC
The open-source implementation of Glow initializes W = ==
However, for the experiment with constraints on W, we could not initiallize W = I- and instead used W I + VV where (initially) ViJ U(- Je: fa). This increased error at initialization from 6.5 8. We suspect this happens because the previous initialization of W has complex eigen- values which W = I + VVT does not (because it is symmetric). In practice, we mitigate the poor initialization by using an additional fixed matrix Q = Q" which does not change during training. This is essentially the same as using fixed permutation done in (Dinh al. (2017), but, instead of using a fixed permutation, we use a fixed orthogonal matrix. While using the fixed Q, we found simply initializing V worked sufficiently well.
15


Reviews:
[{"review_id": "sYetR2BSBPs", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Summary:\nConstraining 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.\n\n#### Pros:\n- The paper provides both theoretical (for the linear case) and empirical evidence supporting their claims.\n- Not being sequential in nature, the proposed method is more efficient on GPU.\n- Relaxation of the invertibility constraint is interesting. Please see the ControlVAE work on PID based annealing, there might be some connection.\n\n#### Cons:\n- While I understand that the method can utilize GPU much better, empirical evidence will certainly help. \n- 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?\n\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "gM8o6khS5nU", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "***Summary***\nThe 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.\n\n***Comments***\n\nCorollary 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.\n\nI 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 \\}$.\n\nThe 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.\n\nGiven 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.\n\n***Experiments***\n\nThe 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?\n\nExperiment 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.\n\nRelated 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.\n\nExperiment 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.\n\n***Related work***\n\nUnder \"Different Approaches.\" you mention that:\n\"the Cayley map (Lezcano-Casado & Martínez-Rubio, 2019) and the matrix exponential (Casado,2019).\"\nThis 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\nHelfrich, K., Willmott, D., and Ye, Q. Orthogonal recurrent neural networks with scaled Cayley transform. ICML 2018\n\n***Minor***\n\nPage 6. \"to conclude $f(x)$ is\" -> conclude that $f(x)$\n\nPage 11. \"Is an follows\" -> Follows\n\n\n***Conclusion***\n\nI 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.\n\nFirst, 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.\n\nSecond, 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.\n\nThird, 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.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "fV6dRl3XiQC", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**:\nOrthogonal 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. \n\nOverall, I think the paper is not ready to be published yet. In the current version, the motivation for me is not clear. \n\n\n**Comments**:\n- 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?\n- What is actually the accuracy of such representations? \n- Neural networks represented through Householder reflections are one layer neural networks with an identical activation function. Is it correct?  \n- Do you have ideas for future works? \n\n\n**Minor**: \n- A lot of missed articles \n- “Much previous work attempt to alleviate the additional computational resources it requires to constrain weight matrices to be orthogonal.” - There is a problem here. \n- Abstract: no commas before “if”\n- “because the d reflections needs“\n- “It is the evaluation of these sequential Householder reflection that cause”\n- “allows us simplify” -> to simplify \n- “to train invertible neural network as generative models” -> networks \n- “Newtons method” -> Newton’s \n- “Previous work demonstrate”\n- “Section 2.3.2 then present”\n- “invertibiliy”\n- “is simple connected”\n- “continously”\n- “we finally arive”\n- “a single auxiliary reflections”\n- “where the 6orthogonal matrices where attained”\n- “The RNNs with 1 auxiliary reflection attains”\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "TRbw7y0kEr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nMy 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. \n\nIn 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. \n\nThere are typo/grammatical errors in the paper's title and Figure 3 caption. \n\nWithout a better motivation and explanation of it is important, or more comprehensive experiments, I would recommend this paper be rejected. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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