Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The paper proposes a fast algorithm to train a NN under orthogonality
constraints on the weights for each layer. Using a new retraction
the paper proposes an adaptation of SGD or ADAM on the Stiefel
manifold.

The idea of the paper is to use a truncated fixed point iteration to
obtain the Cayley transform. By doing so one has an approximation
of a cheap retraction by just doing some matrix vector products
(no matrix inversion or SVD needed). The idea is seducing but I
see some difficulties due to this approximation.

Theorem 2 proves that the relative gradient tends to zero but
this does not control how "orthogonal" are the obtained weights.
Basically I fear that the proposed iterative solver moves
the iterates away from the manifold although some empirical
results in Table 5 suggest otherwise.

Figure 1 should be replaced or complemented by a convergence plot
in running time. What matters is that test error decreases
faster as function of time (not epoch). Because of this,
experiments are not fully convincing.

typos:

- non-suquare -> non-square
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: 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.

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: Summary:

This 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.

Overall:

1) 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.

2) 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?

3) 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.


4) 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).

5) 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).

Minor:

- Section 2, TYPO: "non-suquare parameter matrices".
- The momentum $M_t$ is used below Equation 2 before it is defined.

References:

[1] Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group, Mario Lezcano-Casado and David Martínez-Rubio
[2] Parseval Networks: Improving Robustness to Adversarial Examples, Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier
[3] Orthogonal Recurrent Neural Networks with Scaled Cayley Transform, Kyle Helfrich, Devin Willmott, and Qiang Ye
[4] Variational Inference with Orthogonal Normalizing Flows, Leonard Hasenclever, Jakub M. Tomczak, Rianne van den Berg, and Max Welling
[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
review_title: Official Blind Review #3

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)