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 the 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 which also enforce orthonormality of CNN parameters; and (b) Achieve faster convergence rates than the baseline SGD and ADAM algorithms without compromising the CNN's performance. The Cayley SGD and Cayley ADAM are also shown to reduce the training time for optimizing the unitary transition matrices in RNNs.
Summary
This 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.
Decision:
Weak 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.
Supporting arguments for decision:
The main issue with the paper is that the claims made are not sufficiently supported. I have the following three main issues with the evaluation: 
1)  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. 
2) 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. 
3) 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.
The following issues are more minor, but I would still like to see them addressed.
1) 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. 
2) In table 3, why is the SO training time per epoch slower than the Cayley SGD/ADAM optimization?
---- Post Rebuttal Update ----
Assumption 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.
The authors address this concern with the following (page 6 in paper)
"... 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."
On 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.
From 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.
As 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.
In 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.