Efficient Riemannian Optimization on the Stiefel Manifold via the Cayley Transform
Authors: Jun Li
Fuxin Li
Sinisa Todorovic
Venue:  (2020)
Keywords: Orthonormality
Efficient Riemannian Optimization
the Stiefel manifold.

Abstract: Strictly enforcing orthonormality constraints on parameter matrices has been shown advantageous in deep learning. This amounts to Riemannian optimization on the Stiefel manifold, which, however, is computationally expensive. To address this challenge, we present two main contributions: (1) A new efficient retraction map based on an iterative Cayley transform for optimization updates, and (2) An implicit vector transport mechanism based on the combination of a projection of the momentum and the Cayley transform on the Stiefel manifold. We specify two new optimization algorithms: Cayley SGD with momentum, and Cayley ADAM on the Stiefel manifold. Convergence of Cayley SGD is theoretically analyzed. Our experiments for CNN training demonstrate that both algorithms: (a) Use less running time per iteration relative to existing approaches that enforce orthonormality of CNN parameters; and (b) Achieve faster convergence rates than the baseline SGD and ADAM algorithms without compromising the performance of the CNN. Cayley SGD and Cayley ADAM are also shown to reduce the training time for optimizing the unitary transition matrices in RNNs.

Published as a conference paper at ICLR 2020
EFFICIENT RIEMANNIAN OPTIMIZATION ON THE STIEFEL MANIFOLD VIA THE CAYLEY TRANSFORM
Jun Li, Li Fuxin, Sinisa Todorovic
School of EECS Oregon State University
Corvallis, OR 97331 {1iju2, 1if, sinissa@orrggonstate.ee
ABSTRACT
Strictly enforcing orthonormality constraints on parameter matrices has been shown advantageous deep learning. This amounts to Riemannian optimiza- tion on the Stiefel manifold, which, however, is computationally expensive. To address this challenge, we present two main contributions: (1) A new efficient re- traction map based on iterative Cayley transform for optimization updates, and (2) An implicit vector transport mechanism based on the combination of pro- jection of the momentum and the Cayley transform specify two new optimization algorithms: Cayley SGD with momentum, and Cay- ley ADAM on the Stiefel manifold. Convergence of Cayley SGD is theoretically analyzed. Our experiments for CNN training demonstrate that both algorithms: (a) Use less running time per iteration relative existing approaches that enforce orthonormality of CNN parameters; and (b) Achieve faster convergence rates than the baseline SGD and ADAM algorithms without compromising the performance of the CNN. Cayley SGD and Cayley ADAM are also shown to reduce the training time for optimizing the unitary transition matrices in RNNs.
the Stiefel manifold. We
INTRODUCTION
Orthonormality has recently gained much interest, as there are significant advantages of enforcing orthonormality on parameter matrices of deep neural networks. For CNNs, [Bansal et al. (2018) show that orthonormality constraints improve accuracy and gives faster empirical convergence rate, HHang et al. (2018a) show that orthonormality stabilizes the distribution of neural activations in training, and Cogswell et al. (2015) show that orthonormality reduces overfitting and improves generalization. For RNNs, AArjvssyy et al.] (2016); Zhou et al. (2006) show that the orthogonal hidden-to-hidden matrix alleviates the vanishing and exploding-gradiees problems.
Riemannian optimization on the Stiefel manifold, which represents the set of all orthonormal matri- of the same size, is elegant framework for optimization under orthonormality constraints. But its high computational cost is limiting its applications, including in deep learning. Recent efficient approaches incorporate orthogonality in deep learning only for square parameter matrices (Arjovsky et al. 2016 Dorobantu et al., 2016). or indirectly through regularization (Bansal et al. 2018). which however does not guarantee the exact orthonormality of parameter matrices.
To address the aforementioned limitations, our first main contribution is an efficient estimation of the retraction mapping based on the Cayley transform for updating large non-square matrices of parameters on the Stiefel manifold. We specify an efficient iterative algorithm for estimating the Cayley transform that consists of only a few matrix multiplications, while the closed-form Cayley transform requires costly matrix inverse operations (Vorontsov al., 22177; Wisdom et al.) 2016). The efficiency of the retraction mapping is both theoretically proved and empirically verified in the paper.
Our second main contribution is aimed at improving convergence rates training by taking into account the momentum in optimization the Stiefel manifold. We derive new approach to move the tangent vector between tangent spaces of the manifold, instead of using the standard parallel transport. Specifically, we regard the Stiefel manifold submanifold of Fuclidean

---

Published as a conference paper at ICLR 2020
space. This allows for representing the vector transport (Absil et al. 2009) projection onto the tangent space. As we show, since the Cayley transform implicitly projects gradients onto the tangent space, the momentum updates result in an implicit vector transport. Thus, first compute linear combination of the momentum and the gradient in the Fuclidean space, and then update the network parameters using the Cayley transform, without explicitly performing the vector transport.
We apply the above two contributions to generalize the standard SGD with momentum and ADAM (Kingma & Bal 2014) to the Stiefel manifold, resulting in our two new optimization algorithms called Cayley SGD with momentum and Cayley ADAM. A theoretical analysis of the convergence of Cayley SGD is presented. Similar analysis for Cayley ADAM omitted, since it is very similar to the analysis presented in (Becigneul & Ganea 2019).
Cayley SGD and Cayley ADAM are empirically evaluated on image classification using VGG and Wide ResNet on the CIFAR-10 and CIFAR-100 datasets (Krizhevsky & Hinton| 2009). The ex- periments show that Cayley SGD and Cayley ADAM achieve better classification performance and faster convergence rate than the baseline SGD with momentum and ADAM. While the baselines take less time per epoch since they do not enforce the orthonormality constraint, they take more epochs until convergence than Cayley SGD and Cayley ADAM. In comparison with existing optimization methods that also account for orthonormality - e.g., Polar decomposition. QR decomposition, or closed-fome formd-fommm Cayley transform our Cayley SGD and Cayley ADAM run much faster and yield equally good or better performance in image classification.
Finally, we apply the aforementioned two contributions to training of the unitary RNNs. Wisdom et al.] (2016) proposes the full capacity unitary RNN that updates the hidden-to-hidden transition matrix with the closed-form Cayley transform. In contrast, for our RNN training. we use the more efficient Cayley SGD with momentum and Cayley ADAM. The results show that our RNN training takes less running time per iteration without compromising performance.
2 RELATED WORK
There is a host of literature on using orthonormality constraints in neural-network training. This section reviews closely related work, which can be broadly divided in two groups: orthonormality regularization and Riemannian optimization.
Regularization approaches can be divided as hard, which strictly enforce orthonormality, and soft. Hard regularizations are computationally expensive. For example, et. (2018b) extend Batch Normalization (loffe & Szegedy, (015) with ZCA, and hence require costly eigenvalue decomposi- tion. Huang ct al. (2018a) derive a closed-form solution that also requires eigenvalue decomposition. Bansal et al. (2018); Cisse et al. (2017); Xiong et al. (2016) introduce mutual coherence regulariza- tion and spectral restricted isometry regularization, however, these regularizations are soft in that they can not guarantee orthonormality.
Riemannian optimization guarantees that the solution respects orthonormality constraints. For ex- ample, Cho Caopee,Cho&& & Lee (2017) replace Batch Normalization layers in CNN with Riemannian optimiza- tion on the Grassmann manifold G(n, 1), where the parameters are normalized but not orthonor- malized. Also, Vorontsov et al. (2017): Wisdom al. (2016); Lezcano- Casado & Martinez-Rubio 2019); Helfrich et al. (017)) perform Riemannian optimization on the group of unitary matrices to stablize RNNs training, but their technique cannot be applied non-square parameter matrices. Becigneul& & Ganea 2019) introduce a more general Riemannian optimization, but do not show how to efficiently perform this optimization on the Stiefel manifold.
The key challenge of Riemannian optimization is that exponential mapping - the standard step for estimating the next update point - computationally expensive on the Stiefel manifold. Some methods use an efficient iseudo-geodest
retraction instead of the exponential mapping. For exam- plc, Absil & Malick (2012); Gawlik & Leok] (0188); Manton (2002) use a projection-based method to map the gradient back to the Stiefel manifold that rely on computational expensive SVD. Other approaches are based on the closed-form Cayley transform (Fiori et al. 2012 Jiang & Dail 2015] Nishimori & Akaho, 2005 Zhu 2017). but require the costly matrix inversion. Also, Wen & Yin (2013) reduce the cost of the Cayley transform by making the restrictive assumption that the matrix size p is such that 2p & n. Unfortunately, this algorithm is not efficient when 2p 2 n.
2

---

Published as a conference paper at ICLR 2020
3 PRELIMINARY
This section briefly reviews some well-known properties of the Riemannian and Stiefel manifolds. The interested reader referred to Boothby (1986): Edelman et al. (1998) and references therein.
3.1 RIEMANNIAN MANIFOLD
Definition Riemannian Manifold: A Riemannian manifold (M, p) is a smooth manifold M equipped with Riemannian metric p defined the inner product on the tangent space T.M for each point T, P=(:.-)= T.M x T,M + IR.
Definition 2. Geodesic, Exponential map and Retraction map: A geodesic a locally shortest curve on munifold. An exponential map, Ex (-), maps a langent vector, E Ta. to manifold,
M. Expx, (tv) represents a geodesic 7(t) : t E [0, 1] on a manifold, s.t. 7(0) = I. (0) = V. A retraction map is defined as smooth mapping Rg T + M a mamifold iff R. (0)
and Re (0) = idr.M. where D2₂ denotes the derivative of Rz, idT.M denotes an identity map defined on M. It is easy show that any exponential map retraction map. As computing an exponential map is usually expensive, a retraction map is often used as an efficient alternative.
Definition 3. Parallel transport and vector transport: Parallel transport is a method to translate vector along a geodesic on a manifold while preserving norm. A vector transport is smooth map defined on a retraction R of a manifold M, T T,M x T&M - TR(g)) (flz Ex) + Tna (Ex). t satisfies the following properties: (1) Underlying retraction: Tup (Ex) E TRim.) (2) Consistency: Se = Ex. V&, E MT (3) Linearity: Tne (aC, + +ba) = aTn (Ex) + bTn (Sx). Usually, a vector transport is computationally efficient alternative to a parallel transport.
3.2 STIEFEL MANIFOLD
The Stiefel manifold St(n, 2 p. is a Riemannian manifold that is composed of all p orthonormal matrices {X E Rnxp : St(n.p) p) to denote the Stiefel manifold. We regard M space. Hence, the Riemannian metric p is the Euclidean metric as:px (21, Z2) = (r Z2), where Z1, Z2 are tangent vectors in My The tangent space of M at X is defined as
[]. In the rest of the paper, we will use notation M =
embeded submanifold of Euclidean
TxM = Z 2 x
x
Z =}
(1)
The projection of matrix Z E Ruxp to T can be computed as
TTx (Z) WX
1 _ ZXT). 2
where: W W WT, W = =x
(2)
Given a derivative of the objective function VS(X) at X in the Euclidean space, we can com- pute the Riemannian gradient V.Mf(X) on the Stiefel manifold as a projection onto M using TIx (XX) given by Eq. 2 It follows that optimization of f on the Riemannian manifold can be computed as follows. First, compute (x,)(X. in M. Second, transport the momentum M, to the current tangent space TxM and combine it linearly with the current Riemannian gradient M,,((X, ) to update the momentum M,+1. Finally, third, update the new parameter X along a curve on the manifold with the initial direction as M
While the exponential map and parallel transport can be used to update parameters and momen- tums in optimization on the Riemannian manifold, they are computationally infeasible on the Stiefel manifold. In the following section, we specify our computationally efficient alternatives.
3.2. 1 PARAMETER UPDATES BY ITERATIVE CAYLEY TRANSFORM
The Cayley transform computes parametric curve the Stiefel manifold using skew-symmetric matrix (Nishimori & Akaho 2005). The closed-form of the Cayley transform is given by:
Y(a) = (I 2-- (w) a W)X,
(3)
2
3

---

Published as a conference paper at ICLR 2020
where W is skew-symee akew-symmetric matrix, i.e. W =W,, X is on the Stiefel manifold, and a: 0 is a parameter that represents the length on the curve. It is straightforward to verify that
Y())= = x and Y (0) W.
(4)
From Definition 2 and the definition of the tangent space of the Stiefel manifold given by Eq. D. the Cayley transform is a valid retraction map on the Stiefel manifold. By choosing W = W WT, where W = V
XX VV(())x) as in Eq. we see that the Cayley transform im- plicitly projects gradient on the tangent space as its initial direction. Therefore, the Cayley transform can represent an update for the parameter matrices on the Stiefel manifold.
However, the closed-form Cayley transform in Eq.(3) involves computing the expensive matrix in- version, which cannot be efficiently performed in large deep neural networks.
Our first contribution an iterative estimation of the Cayley transform that efficiently uses only matrix multiplications, and thus is more efficient than the closed form in E3. We represent the Cayley transform with the following fixed deed-point iteration:
((a) x + W (X (Ya)))) (
(5)
which can be proved by moving (a) on the right hand side to the left-hand side in Eq. The ex- pression in Eq. (5) is an efficient approximation of Eq. In Sec. we will analyze its convergence rate the closed-form (3)
3.2.2 MOMENTUM UPDATES BY THE IMPLICIT VECTOR TRANSPORT
Our second contribution is an efficient way to perform momentum updates on the Stiefel manifold. We specify an implicit vector transport by combining the Cayley transform and momentum updates in elegant way without explicitly computing the vector transport. As the Stiefel manifold can be viewed as a submanifold of the Euclidean space R, we have a natural inclusion of the tangent space Tx M R. Consequently, the vector transport the tangent space. Formally, for two tangent vectors εx, 1|x E M,,, the vector transport of &x along retraction map r(nx). denoted as Tyx (Ex), can be computed
the Stiefel manifold is the projection
Tax (5x) TT (Ex).
(6)
We specify the retraction map r(-) the Cayley transform Y in Bq. At optimization step k. in (6) we choose εx = 7ix Mr. where Ma is the momentum in step k - 1. Then, we compute the vector transport of Ma as TM, (Mx) TTx, (Ma). As the projection onto tangent space is OTIx, (Mx) + BTTX, (Vx().)) TTx, (a.Me +
linear map, then aTM, (M&) + BV Mf (Xx)) Thus we first compute a linear combination of the Euclidean gradient V and the momentum Mr. as in the Euclidean space, and then use the iterative Cayley transform to update the parameters, without explicitly estimating the vector transport, since the Cayley transform implicitly project a vector onto the tangent space.
ALGORITTMS
This section specifies our Cayley SGD and Cayley ADAM algorithms. Both represent our efficient Riemannian optimization on the Stiefel manifold that consists of two main steps. As the Cayley transform implicitly projects gradient and momentum vectors onto the tangent space, we first lin- early combine the momentum of the previous iteration with the stochastic gradient of the objective function of at the current point X, denoted as ( Then, we use the iterative Cayley transform to estimate the next optimization point based on the updated momentum. This is used to gener- alize the conventional SGD with momentum and ADAM algorithms to our two new Riemannian optimizations the Stiefel manifold, described in Section 4.1 and Section 4.2
4

---

Published as a conference paper at ICLR 2020
Algorithm 1 Cayley SGD with Momentum
1: Input: learning rate I, momentum coefficient 9, e-10- .9 . 0.5, 8
2: Initialize X₁ as an orthonormal matrix; and M1 =
3: for k = 0 to do
4: Mx+1 < 8MM g(Xx),
Update the momentum Compute the auxilirry matrix
5: Ws + Mx+1Xx 1 Xx Mc+
6:
W& x W W
7:
Ma+1 < W..
D Project momentum onto the tangent space Select adaptive learning rate for contraction mapping iterative estimation of the Cayley Transform
8:
min(t, 2// (IlWal +c]
9:
Initialize yo +- X +aMa+1
for to
11:
Y + X4 Wa(Xa + y
12:
Update X4+1 +- Y
Algorithm 2 Cayley ADAM
Input: learning rate momentum coefficients 31 and $8, e 10 8. = 0.3,
2: Initialize X, as an orthonormal matrix. M1 = 0, 01
3: for k = to T do
4: Ma+1 M1
((xs)
Estimate biased momenium
5: Uk+1 B2U4
(Xx))
6:
06t1 /ee11(11 (5)
Update biased second raw moment estimate b Estimate biased-corrected ratio Compute the auxiliary skew-symmetric matrix
7:
r + (1 (1 (1-Bt) /viti +c
8:
W& + Mx+1X. - [Xxx M
9:
W& + (Wx- - W/ 3/r
10:
Me+1 < rWW.
y Project momentum onto the langent space Select adaptive learning rate for contraction mapping Iterative estimation of the Cayley Transform
11:
minfl, (11 +c]
Initialize yu +Xx aMa+1
13:
for to
14:
Y + Xx (Xx +Y-1))
15:
Update X Y
4.1
CAYLEY SGD WITH MOMENTUM
We generalize the heavy ball (HB) momentum update (Ghadimi et al. 2015 Zavriev Kostyuk 1993 in the kth optimization step" to the Stiefel manifold. Theoretically, can be represented as:
M BTTX, (M+) GM(( Xx+1 Y(, Wi)
where Y(a, W is a curve that starts at X₃ with length a on the Stiefel manifold, specified by the Cayley transform in E3. In practice. we efficiently perform the updates in Eq. by the proposed iterative Cayley transform and implicit vector transport on the Stiefel manifold. Specially, first update the momentum as if it were in the Euclidean space. Then, update the new parameters by iterative Cayley transform. Finally, we correct the momentum Ma+1 by projecting Tx.M The details of Cayley SGD algorithm are shown in Alg [
4.2 ADAM ON THE STIEFEL MANIFOLD
ADAM is recent first-order optimization method for stochastic objective functions. estimates adaptive lower-order moments and uses adaptive learning rate. The algorithm is designed to combine the advantages of both AdaGrad, which performs well in sparse- -gandent cases, and RMSProp, which performs well in non-stationary cases.
We generalize ADAM the Stiefel manifold by making three modifications the vanilla ADAM. First, we replace the standard gradient and momentum with the corresponding ones the Stiefel manifold, as described in Section 4.1 Second, we use manifold adaptive learning rate that
Note that use index in superscript to indicate our iterative steps in estimation of the Cayley transform, and index in subscript indicate optimization steps.
5

---

Published as a conference paper at ICLR 2020
assign a same learning rate for all entries in parameter matrix as in (Absil al. 2009). Third, use the Cayley transform to update the parameters. Cayley ADAM is summarized in Alg
CONVERGENCE ANALYSIS
In this section, we analyze convergence of the iterative Cayley transform and Cayley SGD with momentum. To facilitate our analysis, we make the following common assumption. Assumption 1.
The gradient f of the objective function f is Lipschitz contimuous
|VX(X) V f(OI < L|X - YIl. VX,Y, where L >> 0 is constant.
(8)
Lipschitz continity is widely applicable to deep learning architectures. For some models using ReLU, the derivative of ReLU is Lipschitz continuous almost everywhere with an appropriate Lips- chitz constant L in Assumption except for small neighbourhood around 0, whose measure tends to O. Such cases do not affect either analysis in theory or training in practice.
The above assumption allows proving the following contraction mapping theorem.
2 Theorem 1. For a E (0, min [[T }), the iteration yi+1 X + S (X + Y is a contraction mapping and converges to the closed-form Cayley transform ((a) given by Eq. 3 Specifically, at iteration i, || - (a)ll = o(a2+1)
Theorem D shows the iterative Cayley transform will converge. Specially, it converges faster than other approximation algorithms, such as, e.g., the Newton iterative and Neumann Series which achieves error bound o(a") the 7th iteration. We further prove the following result on convergence:
Theorem 2. Given objective function f(X) that satisfies Assumption
| let Cayley SGD with L w where A is positive
momentum run for t iterations with ((Xx). For min 1-8 A
constant, have: minkk=,.....
ol ((())) - 0, as 1
The proofs of Theorem 1 and Theorem 2 are presented in the appendix.
EXPERIMENTS
6.1 ORTHONORMALITY IN CNNS
In CNNs, for a convolutional layer with kernel K E Xotn Xein we first reshape K into a matrix K of size p n, where p Couts Gin h w. In most cases, we have Then, we restrict the matrix K on the Stiefel manifold using Cayley SGD or Cayley ADAM, while other parameters are optimized with SGD and ADAM.
Datasets: We evaluate Cayley SGD or Cayley ADAM in image classification on the CIFAR 10 and CIFARI00 100 datasets (Krizhevsky & Hinton 2009). CIFARIO and CIFARI00 consist of of 50,000 training images and 10,000 test images, and have 10 and 100 mutually exclusive classes.
Models: We use two networks VGG (Simonyan & Zisserman 2014) and Wide ResNet (Zagoruyko & Komodakis 2016) - that obtain state of the art performance on CIFARIO and CI-
FART00. For VGG, every convolutional layer is followed by batch normalization layer and ReLU. For Wide ResNet, we use basic blocks, where two consecutive 3-by-3 convolutional layers are followed by the batch normalization and ReLU activation, respectively.
Training Strategies: We use different learning rates le and lst for weights on the Fuclidean space and the Stiefel manifold, respectively. We set the weight decay as 0.0005, momentum as 0.9, and minibatch size 128. The initial learning rates are set 4 0.01 and lee 0.2 for Cayley SGD and 4 = 0.01 and L,t = 0.4 for Cayley ADAM. During training, we reduce the learning rates by factor of 0.2 60, 120, and 160 epochs. The total number of epochs in training is 200. In training, the data samples are normalized using the mean and variance of the training set, and augmented by randomly flipping training images.
Our baselines include SGD with momentum and ADAM. We follow the same training strategies as mentioned above, except for the initial learning rates set 0.1 and 0.001, respectively.

---

Published as a conference paper at ICLR 2020
Table Classification errors(%) on CIFARIO.
METHOD
VGG-13
VGG-16
VGG-19
WRN 52-1
WRN 16-4
WRN 28- 10-10
SGD
5.88
6.32
6,49
6.23
4.96
3.89
ADAM
6.43
6.61
6.92
6.77
5.32
3.86
CAYLEY SGD
5.90
5.77
5.85
6.35
5.15
3.66
CAYLEY ADAM
5.93
5.88
6.03
6.44
5.22
3.57
Table 2: Classification errors(% ) on CIFARIO0.
METHOD
VGG-13
VGG-16
VGG-19
WRN 52-1
WRN 16-4
WRN 28- 10
SGD
26.17
26.84
27.62
27.44
23.41
18.66
ADAM
26.58
27.10
27.88
27.89
24.45
18.45
CAYLEY SGD
24.86
25.48
25.68
27.64
23.71
18.26
CAYLEY ADAM
25.10
25.61
25.70
27.91
24.18
18.10
Performance: Table and Table show classification errors on CIFARIO and CIFAR100 respec- tively using different optimization algorithms. As shown in the tables, the proposed two algorithms achieve competitive performance, and for certain deep architectures, the best performance. Specif- ically, the network WRN-28-10 trained with Cayley ADAM achieves the best error rate of 3.57% and 18.10% on CIFARIO and CIFARING 100 respectively. Fig. compares training curves of our al- gorithms and baselines in terms of epochs, and shows that both Cayley SGD and Cayley ADAM converge faster than the baselines. In particular, the training curves of the baselines tend to get stuck plateau before the learning rate drops, which not the case with our algorithms. This might be because the baselines do not enforce orthonormality of network parameters. In training, the backpropagation of orthonormal weight vectors, general, does not affect each other, and thus has greater chances to explore new parameter regions. Fig. [ also compares the training loss curve terms of time. Our Cayley SGI) and Cayley ADAM converge the fastest among methods that also address orthonormality. Although the baselines SGD and ADAM converge faster the beginning due to their training efficiency, our Cayley SGD and Cayley ADAM can catch up with the baseline after I 12000 seconds, which corresponds to the 120th epoch of SGD and ADAM, and the 60th epoch of Cayley SGD and Cayley ADAM.
0.45
1.4
Adum
Cayle6000
1.2
CayleyS50
0.35
Coyleyldamm
0.3
0.25
0.8
0.6
0.15
0.4
0.1
0.2
0.05
80
100
120
140
160
180
200
(a) CIFARIO
(b) CIFAR100
Figure 1: Training loss curves of different optimization algorithms for WRN-28-10 10 for epoach 40- 200. (a) Results on CIFAR10. (b) Results on CIFAR100. Both figures show that our Cayley SGD and Cayley ADAM achieve the top two fastest convergence rates.
Comparison with State the Art. We compare the proposed algorithms with two sets of state of soft orthonormality regularization approaches (Bansal et al.
the art. The first set of approaches 2018). Specially, for a weight matrix E TR=P,, SO penalizes || | K ?. DSO penalizes -
[KKKT- I 2 +||K T K I ( the SRIP penalizes the spectral norm of [ - I). The second set of approaches includes the following hard orthonormality methods: Polar decomposition(ADor et al. 2009), closed-form Cayley transform, Wen& Yin (Wen al. 2018a). DBN al. 2018b). Note that do not
et al. 2009), QR decomposition
& Yin 2013). OMDS

---

Published as a conference paper at ICLR 2020
0.6
1.8
500
1.8
Adam
0.5
ClyleySD
Coyleyfdom SRIP
Cayleydamm
1.2
0.5
0.2
0.1
0.2
2000
8000
2000
4000
6800
5000
10000
12000
14000 18030 18000 20000
CIFARIO
(b) CIFARI00
Figure 2: Training loss curves of different optimization algorithms for WRN-28-10 in terms of seconds. (a) Results on CIFARIO. (b) Results on CIFAR100.
clude momentum in Polar decomposition and QR decomposition previous work does specify the momentum. Also, we use the closed-form Cayley transform without momentum as an ablation study of the momentum effect. All experiments are evaluated on the benchmark network WRN- 28-10. 10. Table shows that our algorithms achieve comparable error rates with state of the art. All algorithms are run on one TITAN Xp GPU, and their average training time are compared per epoch. Table 3 shows that our algorithms run much faster than existing algorithms, except for the baseline SGD and ADAM which do impose orthonormality constraints.
6.2 ORTHONORMALITY IN RNNS
In RNNs, the hidden-toe Midden-to-hine to-hidden transition matrix K can be modeled as a unitary matrix (Arjovsky) al., 2016). Wisdom et al. (2016) model the hidden-to-hidden transition matrix full-capacity unitary matrix on the complex Stiefel manifold: St(CN) = (K E NNNN K =
We evaluate the proposed algorithms the challenging pixel-by-pixel MNIST task for long-term memory. The task was used to test the capacity of uRNNs (Arjovsky) al. 2016; Wisdom et al. 2016). Following the same setting in Wisdom al. (2016), we shape MNIST images of 28 x 28 pixels to a = 784 pixel-by-pixel sequences, and select 5,000 out of the 60,000 training examples for the early stopping validation.
Pixel-by-pixel MNIST:
Training: Wisdom et al. (016)) restricted the transition unitary matrix on the Stiefel manifold via closed-form Cayley transtorm. On the contrary, we use Cayley SGD with momentum and Cayley ADAM to reduce the training time. Table shows that the proposed algorithms reduce the training
Table 3: Error rate and training time per epoch comparison to baselines with WRN-28-10 on CI-
FARIO and CIFAR100. All experiments are performed on one TITAN Xp GPU.
Error Rate(%)
Method
CIFARIO
CIFAR100
Training time(s)
SGD
3.89
18.66
102.5
Baselines
ADAM
3.85
18.52
115.2
SO (Banaal et al. 2018
3.76
18.56
297.3
Soft orthonormality
DSO Bansal al. 2018
3,86
18.21
311.0
SRIP Bansal al.
3.60
18.19
321.8
OMDSM (Huang et 2018a)
3.73
18.61
943.6
DBN (Huang al. 2013 3b)
3.79
18.36
889,4
Polar (Absil ct al.
2009)
3.75
18.50
976.5
QR (Absil al.
2009)
3.75
18.65
469.3
Hard orthonormality
Wen& Yin [Wen & Yin 2013)
3.82
18.70
305.8
Cayley closed form w/o momentum
3.80
18.68
1071.5
Cayley SGD (Ours)
3.66
18.26
218.7
Cayley ADAM (Ours)
3.57
18.10
224.4
8

---

Published as a conference paper at ICLR 2020
Table 4: Pixel-by-pixel MNIST accuracy and training time per iteration of the closed-form Cayley
Transform, Cayley SGD, and Cayley ADAM for Full-uRNNs (Wisdom et al. 2016 All experi- ments are performed on one TITAN Xp GPU.
Closed-Fooe Form
Cayley SGD
Cayley ADAM
Model
Hidden Size
Acc(%)
Time(s)
Acc(%)
Time(s)
Acc(%)
Time(s)
Full-uRNN 116 512
92.8
2.10
92.6
1.42
92.7
1.50
Full-uRNN
96.9
2.44
96.7
1.67
96.9
1.74
time by about 35% for all settings of the network, while maintaining the same level of accuracy. All experiments are performed one TITAN Xp GPU.
Checking Unitariness: To show that the proposed algorithms are valid optimization algorithms on the Stiefel manifold, we check the unitariness of the toaden-tt-hidder matrix K by computing the error term || " K - r during training. 5 iterations As can be seen, the iterative Cayley transform can approximate the unitary matrix when 8 = 2. The iterative Cayley transform performs even better than the closed form Cayley transform, which might be an effect of the rounding error of the matrix inversion as E3.(3.
average errors for varying numbers of
Checking unitariness by computing the error IKK I|e for varying numbers of itera- tions in the iterative Cayley transform and the fosed-form Cayley transform.
Table 5:
Hidden Size
s=0
s=1
s=2
$=3
s=4
Closed-form
n=116
3.231e-3
2.852e-4
7.384e-6
7.353e-6 2.547e-5
7.338e-6 2.544e-5
8.273e-5 3.845e-5
n=512
6.787e-3
5.557e-4
2.562e-5
7 CONCLUSION
We proposed an efficient way enforce the exact orthonormal constraints parameters by opti- mization on the Stiefel manifold. The iterative Cayley transform was applied to the conventional SGD and ADAM for specifying two new algorithms: Cayley SGD with momentum and Cayley ADAM, and the theoretical analysis of convergence of the former. Experiments show that both algo- rithms achieve comparable performance and faster convergence over the baseline SGD and ADAM in training of the standard VGG and ResNet CIFARIO and CIFARI00, as well as RNNs on the pixel-by-pixe MNIST task. Both Cayley SGD with momentum and Cayley ADAM take less run- time per iteration than all existing hard orthonormal methods and soft orthonormal methods, and can be applied to non- con-rquare parameter matrices.
ACKNOWLEDGEMENTS
This work was supported in part by NSF grant IIS- DARPA XAI Award N66001-17-2-4029 and AFRL STTR AF18B-T002.
REFERENCES
P-A Absil and Jérôme Malick. Projection-like retractions on matrix manifolds. SIAM Journal on Optimization, (2(1):135-188 2012.
P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2009.
Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks. In International Conference on Machine Learning, pp. 1120-1128, 2016.
Nitin Bansal, Xiaohan Chen, and Zhangyang Wang. Can we gain more from orthogonality regular- izations in training deep enns? arXiv preprint arXiv: 1000.09102 2018.

---

Published as a conference paper at ICLR 2020
Gary Becigneul and Octavian- Eugen Ganea. Riemannian adaptive optimization methods. In In- ternational Conference on Learning Representations, 2019. URL
n het//ErrumiioozzeelliQKKK
William M Boothby. An introduction to differentiable manifolds and Riemannian geometry, volume 120. Academic press, 1986.
Minhyung Cho and Jachyung Lec. Riemannian approach to batch normalization. In Advances in Neural Information Processing Systems, pp. 5-25-522555555 2017.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In Proceedings of the 34th International Conference Machine Learning- Volluee 70, pp. 854-863. JMLR. org, 2017.
Michael Cogswell, Faruk Ahmed, Ross Girshick, Larry Zitnick, and Dhruv Batra. Reducing overfit- ting in deep networks by decorrelating representations. arXiv preprint arXiv:1511.06068, 2015.
Victor Dorobantu, Per Andre Stromhaug, and Jess Renteria. Dizzyrnn: Reparameterizing recurrent neural networks for norm-preserving backpropagation. arXiv preprint arXiv: 1612.0400 2016.
Alan Edelman, Tomás A Arias, and Steven T Smith. The geometry of algorithms with orthogonality constraints. SIAM journal on Matrix Analysis and Applications, 20(2):303-335 1998.
Simone Fiori, Tetsuya Kaneko, and Toshihisa Tanaka. Learning on the compact stiefel manifold by cayley- -ranley-taasfoommeeee bassd pseudo-retraction map. In The 2012 International Joint Conference Neural Networks (IJCNN), pp. 1-8. IEEE,
Evan Gawlik and Melvin Leok. High-order retractions on matrix manifolds using projected poly- nomials. SIAM Journal Matrix Analysis and Applications, 39(():801-98)) 2018.
Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. In Control Conference (ECC), 2015 European, pp. 310-315. IEEE, 2015.
Kyle Helfrich, Devin Willmott, and Qiang Yc. Orthogonal recurrent neural networks with scaled cayley transform. arXiv preprint WiXiv:107.009222 2017.
Lei Huang, Xianglong Liu, Bo Lang, Adams Wei Yu, Yongliang Wang, and Bo Li. Orthogonal weight normalization: Solution to optimization neural networks. In Thirty Second AAAI Conference on Artificial Intelligence, 2018a.
multiple dependent Stiefel manifolds in deep
Lei Huang, Dawei Yang, Bo Lang, and Jia Deng. Decorrelated batch normalization. In The IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2018b.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Francis Bach and David Blei (eds.). Proceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 448 456, Lille, France, 07-09 Jul 2015. PMLR. URL URL.httppp//proceddngs mlr. 2...ppers//3333/fe115...5
Bo Jiang and Yu-Hong Dai. A framework of constraint preserving update schemes for optimization on stiefel manifold. Mathematical Programming, 153(2)5535557, 2015.
Diederík Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14X1v:1412.6980 2014.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
Mario Lezcano-Casado and David Martinez-Rubio. Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group. arXiv preprint 1rXiv:1901.08425 2019.
Jonathan H Manton.
Optimization algorithms exploiting unitary constraints. IEEE Transactions on (0cesssinn..03):3355--45
Signal Processing, 50(3):635-650 2002.
10

---

Published as a conference paper at ICLR 2020
Yasunori Nishimori and Shotaro Akaho. Learning algorithms utilizing quasi-geodesic flows on the stiefel manifold. Neurocomputing, 67:106-1353 135, 2005.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint urXiv:1409.15553 2014.
Eugene Vorontsov, Chiheb Trabelsi, Samuel Kadoury, and Chris Pal. On orthogonality and learn- ing recurrent networks with long term dependencies. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 3570-3578. JMLR. org. 2017.
Zaiwen Wen and Wotao Yin. A feasible method for optimization with orthogonality constraints. Mathematical Programming. 142(1-2):397 2013.
Scott Wisdom, Thomas Powers, John Hershey, Jonathan Le Roux, and Les Atlas. Full-capacity unitary recurrent neural networks. In Advances in Neural Information Processing Systems, pp- 4880-4888, 2016.
Wei Xiong, Bo Du, Lefei Zhang, Ruimin Hu, and Dacheng Tao. Regularizing deep convolutional neural networks with structured decorrelation constraint. In 2016 IEEE 16th International Con- ference on Data Mining (ICDM), pp. 519-528. IEEE, 2016.
Sergey Zagoruyko and Nikos Komodakis. arXiv:1605.07146. 2016.
Wide residual networks.
arXiv
preprint
SK Zavriev and FV Kostyuk. Heavy-ball method in nonconvex optimization problems. tional Mathematics and Modeling, 4(4):336-341, 1993.
Computa-
Jianping Zhou, Minh N. Do, and Jelena Kovacevic. Special paraunitary matrices, Cayley transform, and multidi- mensional orthogonal filter banks. IEEE Trans. Image Processing, 15(2)511-551, 2006.
Xiaojing Zhu. A riemannian conjugate gradient method for optimization the stiefel manifold. Computational Optimization and Applications, 67(1):73-110, 2017.

---

Published as a conference paper at ICLR 2020
A PRELIMINARY
In this section, we derive some properties of the Stiefel manifold in this section facilitate the proof's of Theorem 1 and Theorem 2 in the main paper.
Considering the Stiefel manifold M is a bounded set and Lipschitz Assumption D on the gradi- ent in Sec. [] one straightforward conclusion is that both V and its Stiefel manifold gradient (x) that a projection onto the tangent space are bounded. Formally, there exists a positive constant G, such that
VI MVMf(XII S IVV G,
As stochastic gradient ((X) = () is the gradient of a sub-dataset, where & is a stochastic variable for data samples and we are working are finite dataset, it's straightforward show that (XX) and its Riemannian stochastic gradient (X) are also bounded. For brevity, we still use the same upper bound G, such that:
(X)]l & ((()) & V. E M
(10)
Recall the recursion in 7 we show that the momentum is also bounded:
|| || S M||Ma|| + (X
k
g
G
(11)
Therefore, we know that W in Eq. is bounded.
B PROOF OF THEOREM
Proof. By subtracting the iterative relationship Eq. 5 by its 8th iteration yi1 = X + +Y), we have:
a ||| y Y(a)ll
|| -
Y(a)ll
(12)
2
Therefore, since W is bounded, for 2
1. the iteration in Eq. is contraction mapping, and it will converge to the closed-from solution Y(a)..
[W such that [||
2-
By differentiate Eq. 55. we have:
dY
X +Y(aa)
w dY 2
W(
Y (I a w) t (a
(13)
da²
2
da
therefore,
dY da and
(a) da2
are bounded, i.c. there exist a positive constant C, such that:
(a S
(14)
da²
Using the Taylor expansion of Y in Eq. 3), have:
(
Y(a) = Xx + aM+1 + aa
(15)
2
da
where "A E 10. Given y = X2 + aM we have:
| =
(16)
Since W is bounded and a||W|| 1, then,
yy-YY(a)l S <alll]] a||W||
"111""0 Y((a)l o(a2t))
(17)
2
12

---

Published as a conference paper at ICLR 2020
C PROOF OF THEOREM 2
Proof. Use Taylor expansion of Y (a), the process of Cayley SGD with momentum Eq. can be written as:
Mk+1 TTx, (BMr) (m(Xx)
Xk+1 = Xx + +aM++1 + a² d
(18)
2 da?
where 7A E 1). Using the fact that
M TTx (M) + TN> (M)
(19)
where TNx (M) is the projection the normal space, and
xxxx (M) = X M M
(20)
2
Then, the projection of momentum can be represented as:
Txx, (Mx) = Mr TNxx (M&)
X Mr + + X
-M Xx
d'y (1k-10)) Mr
MM Xxf(X + aM a
da²
1 + M (x + a. + aa 2 (1k-1)) (24-111)))1)
2
da²
d2Y (Tk-)a1
d (T)-1)1))
= Mr - ax Mr
a X
Me + M
(21)
da²
do
Then the momentum update in Eq. is equivalent to:
M BM
M Ms (M()
1
d (
T
y
a
3X
Ma + M2
(22)
4
da²
da²
Therefore, the paramter update in Eq. can be represented as:
X Xx + aBMr agM(XL,
1 a2xxal (Tk-11a))
Mr + +M²
daz
da
-a² Mr + =a²
da² +x++B(AX Xx-1) aGM((*) a²
(23)
where
PP (
&y (
U - ax3xl
Mr + M₁
da²
do²
(dY((aa)
Sd (7-
8 Mr
(24)
2 da
2
d
Since ||M]]. [X]], and &Y 4o2
are bounded, there is positive constant D, such that
||U||| < D
(25)
13

---

Published as a conference paper at ICLR 2020
To facilitate the analysis of Cayle SGD with momentum, introduce auxiliary variables {Ps), such that:
a² U 3
Zk+1 Zx 1 [M((x)
(26)
where
Z4 = Xx + Pk.
(27)
and
3
(Xx - -x-1),
Pk
1- B
0,k=0
Since S(X) is a smooth function according to Assumption
we have:
1(Y) (() - - -X)
Vtr(J(Y + + (Y (xV
-11
(VF(Y + +(Y- - -X)) - Vx(()) -X-
LIIKY X)lldt x 1 -XII
マ || - X112
(28)
Then, we have
1(Z++1) (T((K) + (V(V) (T
(Z++1 Zx-)) + Z Zx12
a²
=f(Z() + (TVV/(Z))T(2 ((x++1 ((x)) + a
GM((K) - T B U11
La²
La
<f(7)) + (V(\ (7x+1- - 7x)) + (1 8)² |19M(X*)]1 + (1- - 8)2 |11
<S(2)) T-
a
+ In (UU + - B32 G2
2
La
La
+ (1- (1-8)2 D2
2(1 3) (|U) [| + La²
a²
<f(Ze) 1-
(V((2() vV(z)) +
(1 By² G2
La
+ (1 (1-3 D²
<f(Zk) tr(5m(Xxx) (VF(m(X))TV((Z) + a²
(D² G
2(1 2(1-3) 3)
La
G2 La
D
(29)
(1 8)2 (1-
14

---

Published as a conference paper at ICLR 2020
By taking expectation over the both sides, we have:
- - f(Zx)))
<
a tv(()(22) T vMf(X))) + 2(1 3) (D2 +G2)
a²
(1 (1- G² La
La²
(1- 3)2 D2
1
<EI (r(()(Z))) VS(X))) VVMJ(Xx) 1- tr((((((X (r(Ff(X))VVvM()) V.M((X)))
a
La²
La
+
(D² +G+)+
+ (1 (1-3)2
G²
(1 (1-3)- 3)² D²
2(1 9)
-EI
(( vf(Xx)) (M
3 [M
a²
La²
La D2
(D² + G2) +
G² +
(30)
2(1 2(1-3)
(1 B)²
(1 (1- 3)2
By noticing that:
a
- - V VMf()()
3
La
2T. -V +
V MXx)11
(31)
2(1 B-
Then
B[f(Z++1) - -
La²
2L F[I[S(Z)) V/(xx11
E V (Xxx1l
2(1 - -82
1 3
a²
La²
La
+ 2(1 - 3)
(D² + +G)+ + (1- 3)2
G² +
D2
(32)
(1 3)2
According to the Lipschitz continuous property in Assumption I we have:
[V}(Z)) - vx(x)) <1> X2112
T22
1 11-
(1 - B)2
122/2
_ y (TRa)
1
llaMM
12
(1 B)2
2
da²
222
L d2 Y
(TRa) (12)
(llaMal12
+ +11
(1 - B)2
da²
2L2028²
G²
+ d'C²
(33)
(1 - 3)2
(1 - 3)2
4
Therefore,
B[((Zx+1) - [(Zx))]
< - BE V 2
(34)
where
B a
La²
(35)
1- 3
2(1 B)²
L
2
D2 + G
LG
La²
B' (1 B)²
+
D)2
(36)
(1 - -3)2
2(1 3)
(1 3)2
(1
3)22
15

---

Published as a conference paper at ICLR 2020
Since 1-2 then
L-
La 2
B
1 3 2(1 8)2
aL
(1 2(1 3))
2(1 3) 0
(37)
By summing Eq.
34
over all k, we have
B
(I - f(Z++1) + + 1)a2
0=0
$ f((o) - fo + (t 1)+
(38)
Then
f(Zo) - fx
B
min BIIl
a²
(39)
(t + 1)B
B
min Bill MM 2(f(2o) - f.) - 3)
+ a2B's (1 (1-3)
(40)
(1+1)a
Use the fact that a min ق- v }. and notice that Zo Xo, therefore,
min
Blll MM (xx))
k-
2(f(X)) - f.)(1 - B) max
L
Vt+
2AB (1 - B) V
1+1 1
1- 3
A
(()(Xx) - -1.)(1-) -8)
L
VT+I
max (
++1
1- A
2A(1 - 8) T
G2
A²C²
V++I (1 - 8)2
(1 B)2
+
4(t +1)
D2 + G2
LG
LA-
2(1 3) +
(1+ 1)(1 3)2 D2
(41)
(1 3)2
Therefore, min k=U....!
B|IlV ([IIVM((XXx)11]] of ( 0, 00.
16


Reviews:
[{"review_id": "SJx4F9R-9r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "The paper proposes a fast algorithm to train a NN under orthogonality\nconstraints on the weights for each layer. Using a new retraction\nthe paper proposes an adaptation of SGD or ADAM on the Stiefel\nmanifold.\n\nThe idea of the paper is to use a truncated fixed point iteration to\nobtain the Cayley transform. By doing so one has an approximation\nof a cheap retraction by just doing some matrix vector products\n(no matrix inversion or SVD needed). The idea is seducing but I\nsee some difficulties due to this approximation.\n\nTheorem 2 proves that the relative gradient tends to zero but\nthis does not control how \"orthogonal\" are the obtained weights.\nBasically I fear that the proposed iterative solver moves\nthe iterates away from the manifold although some empirical\nresults in Table 5 suggest otherwise.\n\nFigure 1 should be replaced or complemented by a convergence plot\nin running time. What matters is that test error decreases\nfaster as function of time (not epoch). Because of this,\nexperiments are not fully convincing.\n\ntypos:\n\n- non-suquare -> non-square", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkg1qrA6KS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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\nThis paper aims to improve upon current solutions for optimizing neural networks with orthonormal convolutional kernels/MLP layers. Optimizing neural networks while restricting the parameter matrices to remain orthonormal/on the Stiefel manifold is said to lead to faster convergence in terms of the number of epochs, and could reduce overfitting. One way to enforce orthonormality is to use the Cayley transform, which requires a matrix inversion that becomes expensive for large weight matrices in neural networks. The authors instead propose an iterative approximation to the Cayley transform that does not require a matrix inversion, and empirically only requires two iteration steps to lead to similar precision as a closed-form Cayley transform with numerical inverse. The authors combine this with SGD + momentum and ADAM by first performing the update step in Euclidean space and afterwards projecting the result back onto the stiefel manifold by using the iterative Cayley transform. They provide one assumption and two theorems on the convergence of the iterative approximation and its effect on optimization. The method is evaluated on classification for cifar10 and cifar100 and for modeling the hidden-to-hidden transition matrix in an RNN trained on MNIST.\n\nDecision:\nWeak reject. Although the motivation of the paper is sound. The empirical validation of the proposed method is insufficient. For instance, assumptions that are the basis of one of the theorems are violated in the experiments and converges are only shown as a function of epoch and not wall clock time.\n\nSupporting arguments for decision:\nThe main issue with the paper is that the claims made are not sufficiently supported. I have the following three main issues with the evaluation: \n1)  Assumption 1, which is required to prove convergence of the proposed Cayley SGD/ADAM optimizer, appears to be violated in experiments. The assumption states that the gradient of the objective function is Lipschitz continuous. However, in the VGG and wide Resnets ReLU’s are used. The derivative of a ReLU is a step function, which is not Lipschitz continuous. Therefore the objective function used in the experimental validation violates assumption 1. Now, I can imagine that perhaps in practice this does not matter too much, but surely the evaluation is not correct according to the theoretical claim. The authors should clarify this and experiments should be done with other activation functions that do not violate the assumption. \n\n2) The paper claims to improve the convergence speed, as compared to baseline Euclidian SGD+momentum and ADAM, but learning curves are only shown as a function of epoch, and not of wall clock time. Table 3 displays per-epoch training times and clearly shows that when compared to SGD+momentum and ADAM the runtime is slowed down by a factor of 2. I am not convinced that if figure 1 would be plotted as a function of wall clock time, the proposed method would actually come out as having converged faster. \n\n3) The learning rate decay schedule used in obtaining the results in figure 1 and table 1 seems more optimized for the proposed methods than for the baseline SGD and ADAM optimizers. ADAM and SGD have reached a plateau “earlier” (in terms of epoch number), and could have benefited from a decay in learning rate earlier on. It is also extremely hard to see what is going on after the 50th epoch due the scale of the plot in figure 1. Please zoom in on epoch 50 and onwards or also show a plot in log scale. The total number of epochs is also the same for all methods. Perhaps it would also be more fair to give every method the same total budget of wall clock time.\n\nThe following issues are more minor, but I would still like to see them addressed.\n1) In the last section of the related work, the work by Wen & Yin is said to be “not suitable for training common deep neural networks”. This gives the impression that this method simply cannot be used for VGG/wide resnets. However, table 3 certainly shows results for the work by Wen & Yin for a large wide resnet with a per epoch run time that is much better than the Cayley closed form w/o momentum baseline. \n2) In table 3, why is the SO training time per epoch slower than the Cayley SGD/ADAM optimization?\n\n---- Post Rebuttal Update ----\n\nAssumption one in the paper states that the derivative of the objective function must be Lipschitz continuous - the authors use ReLU in all experiments whose derivative is not Lipschitz continuous.\n\nThe authors address this concern with the following (page 6 in paper)\n\n\"... For some models using ReLU, the derivative of ReLU is Lipschitz continuous almost everywhere with an appropriate Lipschitz constant in Assumption 1 , except for a small neighborhood around 0, whose measure tends to 0. Such cases do not affect either analysis in theory or training in practice.\"\n\nOn the theory side: If the authors want to rely on the assumption that for a measure zero part of the domain the function is not Lipschitz, then the authors should adjust assumption 1 to loss functions whose derivatives are locally Lipschitz continuous, and this will require a redo of the proofs under this new assumption.\nFrom the experimental side: they provide no direct comparison with models where assumption 1 does hold, e.g by comparing ReLU with a scaled SoftPlus as suggested in the review. So the claim that it does not matter in practice is not completely supported.\n\nAs this is an optimization paper the wall-clock convergence rates are important and was not included in the initial submission. The authors have addressed this by adding figure 2 in the appendix, which shows convergence rates from 0 - 20000 seconds. Presumably this is a subset (likely epoch 0 to 80) of the data shown in figure 1 showing 0 to 200 epochs. Why they choose not to show the full data is not completely clear to me. The authors claim that Cayley Adam catches up with Adam after 12000 seconds which might be true for cifar10 (not really visible in the figure) but is definitely not true for cifar100 where Adam seems to be better all the time.\n\nIn summary: Claims that deviating from assumption 1 does not impact theory or experiment are not supported. Important run time experiments are relegated to the appendix and only  incomplete training curves as a function of time are shown, which is potentially misleading.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "B1lfdOP6KH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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:\n\nThis paper proposes an efficient method to perform Riemannian optimization over the Stiefel manifold using an efficient computation of the Cayley transform via fixed point iteration. While simple, the method is to my knowledge novel. Empirically, the authors validate that their method is able to tightly enforce the orthogonality constraint with a reasonable computational budget. Further experiments highlight the benefits of orthogonality in deep learning but the explanations feels lacking. The paper is missing references to some related work but is otherwise well written.\n\nOverall:\n\n1) In abstract, \"This amounts to Riemannian optimization on the Stiefel manifold\". Other approaches exist to enforce orthogonality throughout the network. In general, I felt that this paper was missing related work which enforces orthogonality constraints in deep learning. Some examples: [1,2,3,4] though this is by no means exhaustive.\n\n2) In order for the fixed-point iteration to have guaranteed convergence, the \"learning rate\" for the contraction mapping depends on the largest singular value of the weight matrix $W_k$. Could you please clarify how this is computed in practice?\n\n3) I am not convinced that the second change made to the Adam algorithm is reasonable (at least, not if we wish to continue calling the algorithm Adam). Adam preconditions the gradient by an estimate of the diagonal of the Fisher information matrix. Algorithm 2 presented is closer to a spherical approximation to the Fisher. The algorithm still looks sensible to me but the name is perhaps inaccurate.\n\n\n4) I am a little unsure of the motivation behind the experiments. For experiments validating the efficiency of the proposed method this is clear but for the classification experiments this is less obvious. Are the authors claiming that orthogonality is a good regularizer? Or is the only benefit in optimization? I did not understand the proposed explanation that that the orthogonal weights do not affect eachother during backpropagation --- could you please clarify? Even if this were true, why would this encourage exploration? There is existing literature which suggests that orthogonal networks will be easier to train (see e.g. [5] and others).\n\n5) The orthogonality of the convolutional layers is enforced by reshaping the kernel and imposing an orthogonality constraint there instead. Unfortunately, this does not guarantee that the actual convolution operator is orthogonal (see e.g. [2] for an example in 1D and [5] which characterizes orthogonal convolutions correctly).\n\nMinor:\n\n- Section 2, TYPO: \"non-suquare parameter matrices\".\n- The momentum $M_t$ is used below Equation 2 before it is defined.\n\nReferences:\n\n[1] Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group, Mario Lezcano-Casado and David Martínez-Rubio\n[2] Parseval Networks: Improving Robustness to Adversarial Examples, Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier\n[3] Orthogonal Recurrent Neural Networks with Scaled Cayley Transform, Kyle Helfrich, Devin Willmott, and Qiang Ye\n[4] Variational Inference with Orthogonal Normalizing Flows, Leonard Hasenclever, Jakub M. Tomczak, Rianne van den Berg, and Max Welling\n[5] Dynamical Isometry and a Mean Field Theory of CNNs: How to Train 10,000-Layer Vanilla Convolutional Neural Networks, Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel S. Schoenholz,  and Jeffrey Pennington", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a method for optimizing parameter matrices of deep learning objectives while enforcing orthonormality constraints.  While advantageous in certain respects, such constraints can be expensive to maintain when using existing methods.  To address this issue, an new algorithm is proposed based on the Cayley Transform and analyzed in terms of convergence.  After the discussion period two reviewers supported acceptance while one still voted for rejection.  Consequently, in recommending acceptance here for a poster, it is worth examining the significance of unresolved concerns.

First, the reject reviewer raised the valid point that the convergence proof relies on the assumption of Lipschitz continuous gradients, and yet the experiments use ReLU activation functions that do not satisfy this criteria.  In my view though, it is sometimes reasonable to derive useful theory under the assumption of Lipschitz continuous derivatives that nonetheless provides insight into the case where these derivatives may not be Lipschitz on a set of measure zero (which would be the case with ReLU activations).  So while ideally it might be nice to extend the theory to remove this assumption, the algorithm seems to work fine with ReLU activations in practice.  And this seems reasonable given the improbability of any iterate exactly hitting the measure-zero points where the gradients are discontinuous.  Beyond this issue, some criticisms were mentioned in terms of how and where the timing comparisons were presented.  However, I believe that these issues can be easily remedied in a final revision.
Decision: Accept (Poster)