Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a method (projUNN) for efficiently training neural networks with parameters that are constrained to be unitary/orthogonal matrices. 

The main strategy is to obtain a low rank approximation of the gradient update and then use Riemannian gradient descent either via retraction (method projUNN-D) or exact computation of the exponential map (method projUNN-T).

strengths_and_weaknesses: Overall, the paper is clear and well written; the appendix provides a nice mathematical background/review, many interesting remarks/extensions/experiments. The main strength of the paper arises from the observation that low rank matrices can accurately approximate gradients (where fidelity is measured by residual frobenius norm error). This approximation allows the proposed method to be essentially a factor of O(n) faster than its competitors.

One potential downside is that the proposed method (projUNN) and some of the baselines use eigen decomposition/QR decompositions which suffer some overhead due to parallelization issues in the GPU, causing some methods to appear slower in the experiments. Authors mention that this issue could be potentially fixed in the future with updates to DL libraries.

questions: 
It would be interesting to compare train/test loss evolution over iterations between projUNN and the other baselines (i.e. testing convergence in terms of iterations rather than time) as well as total time to achieve similar loss (as opposed to single iteration cost).


Minor Remarks:
Typo: pg. 23 $$\hat a = \tilde{M}^{\dagger} a \rightarrow \hat a = U^{\dagger} a$$ 


limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies the acceleration of unitary neural network training. By exploiting the low-rank structure of gradients (done with sampling), the authors design two efficient update methods of unitary matrices based on gradient descent: one that directly projects the updated weight to the unitary manifold, and one that projects the gradient to the tangent space followed by a rotation mapping. Experimental results on several RNN tasks show that the proposed algorithm is on par with existing unitary neural networks while achieving nearly optimal runtime complexity. The authors also perform some preliminary study on training orthogonal convolution layers. 
strengths_and_weaknesses: The paper is well-motivated and clearly-written. The proposed methods are simple-yet-effective, and the theoretical results are strong (which I have checked in details). Comparison with prior works looks comprehensive. Due to my limited knowledge in related works, I will leave the evaluation of novelty as well as experimental results to other reviewers. 
questions: The authors propose two methods (projUNN-D and projUNN-T). Is there any difference between these two methods other than the numerical issues? I would like to see some comparisons (e.g., the pros and cons) between them.
limitations: Yes. The authors discussed the numerical instability of the direct method as well as the memory concern when applied to orthogonal convolutions.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper present two efficient update rules for neural networks with unitary matrices parametrized as full n x n arrays. Unitary matrices have attractive properties for neural networks since they preserve the norm of vectors they are multiplied to, and unlike orthogonal matrices, they have differentiable parametrizations though the main drawback to their use is that full parametrizations and/or gradient updates are often inefficient ( O(n^3) as opposed to O(n^2) of arbitrary matrices ). This paper proposes efficient O(k n^2) gradient updates, where k is a gradient rank hyperparameter. The methods are based on the hypothesis that the training gradient w.r.t. the unitary matrix can be well approximated as a low-rank matrix. They propose to use existing randomized SVD methods to compute the low-rank approximation

The first method PROJUNN-D first computes a low-rank approximation of the gradient, then it applies a standard SGD step to the unitary matrix, and projects the result back to the unitary group, which can be done efficiently by exploiting the fact that the perturbation was low-rank. The author comments that this method can be subject to numeric instability.

The second method PROJUNN-T first computes a low-rank approximation of the gradient, then it rotates the unitary matrix along a projection of the approximated gradient on the unitary Lie algebra.

PROJUNN-D and PROJUNN-T are evaluated on learning a random unitary matrix and, as a URNN update rule, on various standard RNN benchmarks, with competitive results and a substantial reduction of runtime.

An extension to convolution is also discussed, but it is not shown to be competitive to vanilla convolution.

strengths_and_weaknesses: Strengths:
- Very compelling result, might enable making URNNs practical
- Very good exposition
- Extensive experiments

Weaknesses:
- Both methods seem fairly complicated to implement, full peudocode algorithm descriptions (including the low-rank gradient approximation) would be appreciated. Hopefully code will be released.
questions: None
limitations: None
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose two optimization algorithms for training deep networks with unitary weight matrices. Then they extend their approach to unitary convolutional operators. Unlike existing approaches, they exploit the low-rank structure of gradients that is a consequence of the relatively small batch sizes used in SGD-like optimization. This way they achieve significant speedups over existing unitary training approaches.
strengths_and_weaknesses: Strength
- The authors propose two novel projected gradient step procedures for training constraint to the space of unitary matrices. In contrast to exisitng approaches, we achieve more computational efficiency by exploiting the low-rank structure of gradients that is present in minibatch training.
- Experimental evaluations show that the low-rank approximation even allows ranks substantially smaller than the batch size ( times sequence length for RNN), increasing the computational complexity even more.
- Discussion of related work places this work among existing work, clearly stating advances and differences.
- The extension to convolutional layers by exploiting the relation between the Fourier transformation and the discrete convolution operation enables the use of unitary operators in the image domain. This may allow users more control about properties of the linear operators that have been linked to generalization in deep networks like spectral norm, stable rank or eigenvalue decay.
- Source code for recurrent networks is available which facilitates widespread use. Unfortunately the CNN code was not available in time for the review

Weaknesses
- The experiments mostly show technical advantages like increases in computational performance, not benefits in applications where this technique is strictly required


questions: -What are applications beside the RNN toy problems where unitary operators may be needed?

limitations: The authors have adequately addressed the limitations. I cannot think of any potential negative societal impact
review_title: null

Meta-review: metareview: This paper provides two routines to replace gradient updates with low-rank unitary updates, and provides extensive technical discussion and experiments.  Reviewers are uniformly positive, and I also voice similar praises, e.g., I too appreciate the extensive discussion in appendices A and B, and the detailed experiments in the later appendices.  As such, it is easy to recommend acceptance, and I will push for this to receive at least a spotlight.  Even so, I urge the authors to make careful revisions for remaining issues raised by the reviewers, and to perform a full pass of their own.
confidence: Certain
Decision: Accept