projUNN: efficient method for training deep networks with unitary matrices
Authors: Bobak Kiani
Randall Balestriero
Yann LeCun
Seth Lloyd
Venue: NeurIPS 2022 Accept (2022)

Abstract: In learning with recurrent or very deep feed-forward networks, employing unitary matrices in each layer can be very effective at maintaining long-range stability. However, restricting network parameters to be unitary typically comes at the cost of expensive parameterizations or increased training runtime. We propose instead an efficient method based on rank-$k$ updates -- or their rank-$k$ approximation -- that maintains performance at a nearly optimal training runtime. We introduce two variants of this method, named Direct (projUNN-D) and Tangent (projUNN-T) projected Unitary Neural Networks, that can parameterize full $N$-dimensional unitary or orthogonal matrices with a training runtime scaling as $O(kN^2)$. Our method either projects low-rank gradients onto the closest unitary matrix (projUNN-T) or transports unitary matrices in the direction of the low-rank gradient (projUNN-D). Even in the fastest setting ($k=1$), projUNN is able to train a model's unitary parameters to reach comparable performances against baseline implementations. In recurrent neural network settings, projUNN closely matches or exceeds benchmarked results from prior unitary neural networks. Finally, we preliminarily explore projUNN in training orthogonal convolutional neural networks, which are currently unable to outperform state of the art models but can potentially enhance stability and robustness at large depth.

ProjUNN: efficient method for training deep networks with unitary matrices
Bobak T. Kiani
Randall Balestriero Meta AI, FAIR rbalestriero@fb.cm com
Yann LeCun
MIT bkiani@mit.edd
NYU & Meta AI, FAIR yann com
Seth Lloyd MIT & Turing Inc. s slloyd@mit.ed
Abstract
In learning with recurrent or very deep feed-forward networks, employing unitary matrices in each layer can be very effective at maintaining long-range stability. However, restricting network parameters be unitary typically comes at the cost of expensive parameterizations or increased training runtime. We propose instead an efficient method based on rank-k updates their rank-k approximation that maintains performance at nearly optimal training runtime. We introduce two variants of this method, named Direct (projUNN-D) and Tangent (projUNN-T) pro- jected Unitary Neural Networks, that can parameterize full N N-dimensional unitary or orthogonal matrices with a training runtime scaling as O(kVz). Our method either projects low-rank gradients onto the closest unitary matrix (projUNN-T) transports unitary matrices in the direction the low-rank gradient (projUNN-D). Even in the fastest setting (k 1). ProjUNN is able train model's 's unitary parameters to reach comparable performances against baseline implementations. In recurrent neural network settings, ProjUNN closely matches exceeds bench- marked results from prior unitary neural networks. Finally, we preliminarily explore ProjUNN in training orthogonal convolutional neural networks, which currently unable to outperform state the art models but can potentially enhance stability and robustness at large depth.
Introduction
Learning in neural networks can often be unstable when networks are very deep or inputs are long sequences of data states that evolved via repeated application of linear transformation followed by a pointwise nonlinearity, which can become unstable when eigenvalues of the linear transformation are not of magnitude one. Unitary matrices, which have eigenvalues of magnitude one, can naturally avoid this issue and have been used as means to overcome these so-called vanishing and exploding gradients (5 [44] More recently, unitary convolutional layers have been similarly constructed to help build more stable deep networks that are norm-preserving in their transformations (58) (72..
For example, vanilla recurrent neural networks (RNNs) have recurrent
In the RNN setting, prior algorithms to apply X unitary matrices in RNNs have parameterized matrices into layers of unitary or orthogonal transformations or parameterized the Lie algebra of the unitary orthogonal group (see Table 1). In the layer-wise setting, unitarity is enforced for all values of parameters, but many layers are required to form a composition that can recreate any desired unitary, Le.. fully parameterizing
unitary requires ((n) layers. By parameterizing the Lie algebra [56] 41. algorithms perform better on common benchmarks but have the drawback
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table I: When training RNNs on inputs with sequence length T, PROJUNN achieves nearly optimal
runtime complexity while maintaining full parameterization of the unitary manifold.
Complexity
Layers to fully parameterize
Model
Method of parameterization
gradient step
EURNN (tunable, layers) 44
O
((n)
Sequence of rotations
oRNN (a layers) [66]
O(Tw²)
((n)
Sequence of householder reflections
full-capacity URNN
O + +
Parameterized matrix entries
expRNN 56
O + + 3
Parameterized matrix in Lie algebra
PROJUNN (our method)
O + J
Parameterized matrix entries
" layers needed to parameterize the full unitary space, & approximations exist which may reduce runtimes though these approximations not implemented here and can significantly bias the gradient [56).* runtime shown for typical setting when k < where & the rank of gradient updates
that performing gradient optimization on an n X unitary requires On operations generically per step. Though not an issue with the small medium sized models used today, this ((n)) is still O(n) slower than standard methods of forward- and back-propogation in RNNs.
Motivated by the feature that gradients in neural networks are typically approximately low rank, show that gradient updates to unitary/orthogonal matrices can be efficiently performed in low rank settings. We propose new model called PROJUNN where matrices are first updated via gradient based optimization and then projected back onto the closest unitary (PROJUNN-D) or transported in the direction of the gradient (PROJUNN-T), PROJUNN has near-optimal runtime complexity unlike other existing algorithms for unitary RNNs (Table T) and is especially effective even in the most extreme case where gradients are approximated by rank one matrices. In RNN learning tasks, PROJUNN matches or exceeds benchmarks of state-of-the-art unitary neural network algorithms.
Though present our model first in the RNN setting, we show that there is direct extension of PNOJUNN to the case of orthogonaluumitary convolution which we explore further. Here, we perform unitary/orthogonal convolution in the Fourier domain inspired by (76). Our algorithm runs efficiently in the convolutional setting especially for filters of large size and many channels (see Appendix F for more details).
2 Related works
Maintaining stability in neural networks via orthogonal or unitary matrices has rich history of study in machine learning, both from an applied and theoretical perspective. Here, we briefly mention the most related works and algorithms we use in comparison to our PROJUNN. For a more holistic review of prior work in unitary neural networks and other related topics, please see Appendixx
Unitary neural networks were first designed to address the issue of vanishing and exploding gradients in RNNs while learning information very long sequences of data more efficiently than existing parameterizations such as the long-short term memory unit (LSTM) [38]. Early algorithms [5] 66]
maintained unitarity by constructing a series of parameterized unitary transformations. Perhaps the most effective of these methods is the efficient unitary recurrent neural network (EUNN) 44 which parameterized unitary matrices by composing layers of Givens rotations, Fourier transforms, and other unitary transformations. The unitary RNN (uRNN) of (82) and the Cayley parameterization (scoRNN) of (35) parameterized the full unitary space and maintained unitarity by performing a Cayley transformation. Later, (56) introduced the exponential RNN (expRNN) which parameterized unitary matrices in the Lic algebra of the orthogonal/unitaa group. Though the uRNN, scoRNN, and expRNN perform well on benchmarks, their algorithms require matrix inversion or SVD steps which are time-consuming in high dimensions.
For convolutional neural networks, of a linear convolution and proposed an algorithm for projecting convolutions onto an operator- norm ball which relied on series of costly projection steps. [58] introduced a block convolutional orthogonal parameterization (BCOP) which was faster and more efficient than the methods in 72. but required extra parameters in its parameterization and only parameterized a subset of the space of orthogonal convolutions. Most recently, [73 implemented orthogonal convolutions by parameterizing the Lie algebra of the orthogonal group via their skew orthogonal convolution (SOC)
772 showed how to efficiently calculate the singular values
2

---

projUNN -D
100%
ProjUNN-T
portion gradient
80%
We dW -
100%
60%
95%
M. (W + dw)
Hlp (lpp (lab)
20%
90%
W
average over batches
0%
tangent space
100
300
500
approximation rank (dim.=512)
Un): unitary
(a) Low rank approximations
Lie group
(b) Illustration of algorithm
Figure 1: (a) Low rank approximations capture most of the Frobenius norm of the gradient 512 x 512 matrix in the convolution filter (512 channels) of the last residual block of Resnet-9. Blue lines plot gradients of a single batch during training our PROJUNN algorithm on CIFAR 10 over a single epoch (see Appendixx E] for details and equivalent plot for RNN architecture).
(b) Illustration of a single gradient update via gradient descent with learning rate PROJUNN-D (pictured in red) directly projects the gradient update back onto the unitary/orthogonal manifold. PROJUNN-T (pictured in green) first projects onto the tangent space (Lie algebra) and then performs rotation in that direction via the exponential map.
algorithm which approximates orthogonal convolutions especially well for small filter sizes. Finally, (76] performs convolutions in the Fourier domain via application of the Cayley transform. Our orthogonal/unitan convolutional parameterization is inspired by their approach and improves their runtime for convolutions over many channels.
3 Notation and background
Vectors and matrices are denoted with bold lower-case and upper-case script, v and V, respectively. Scalars are denoted by regular script and tensors are denoted by bold text The complex conjugate of complex-valued input is denoted by (ignored when real-valued). The transpose of matrix M denoted by MT and the conjugate transpose Frobenius norm of a matrix by || || and the spectral norm of a matrix by || 112.
matrix denoted by M We denote the
Here, we provide a brief overview of the unitary/orthogonal groups and refer readers to|Appendix for a more detailed mathematical background. The set of n x n orthogonal O(n) and unitary (() matrices are both Lie groups defined as
((n) (M E R M =
U(n) (M COX M =
Constraining matrices in (n) and (n) to have determinant equal to constructs the special orthogonal 50(n) and unitary (U(n) groups respectively. The Lie algebra or tangent space of the identity of (nn) and (n) the set of skew symmetric o(n) and skew Hermitian u(n) matrices,
(n) {A E =
AT -
u(n) (A CaXn A A =
The matrix exponential exp(-) is map from the Lie algebra to the associated Lie group. The map is surjective if the Lie group compact and connected property which holds for the unitary and special orthogonal groups but not the orthogonal group.
4 Projected unitary networks
Our PROIUNN algorithm is motivated by the simple observation that most of the "information" of typical gradient in deep learning task is captured in low rank subspace of the complete gradient.

---

Figure 13 iillustrates this feature when training our PROJUNN convolutional network on CIFARIO. We include further analysis and justification of this low rank behavior in AAppendix E| As we will show, we can perform updates on the low rank subspace of the gradient efficiently by approximating the gradient with low rank matrix and performing projections of parameters onto that low rank subspace. Our experiments show that this methodology, even with rank one approximations, is effective at learning and empirically introduces a form of "beneficial" stochasticity during gradient descent.
Based on how the projection performed, our PROJUNN algorithm takes two forms illustrated in Figure lb] The directly projected unitary neural network (PROJUNN-)) projects an update onto the closest unitary/orthooonal matrix in Frobenius norm. The tangent projected unitary neural network (PROJUNN-T) projects gradients onto the tangent space and transports parameters in that direction.
4.1 PROJUNN-D
PROJUNN-D takes advantage of the fact that the polar transformation returns the closest unitary or orthogonal matrix in the Frobenius norm to a given matrix (not necessarily unitary or orthogonal):
Lemma 4.1 (Projection onto unitary manifold [46).. Given a matrix A E C
(A) arg min || - UIE A(A A)= UEu(m)
where U(n) indicates the set of n X n unitary matrices.
Note, that if the matrix A is real, then the projection above will be onto an orthogonal matrix. Given Lemma 4.1. PROJUNN-D performs optimization in two steps, which are illustrated in Figure Ib First, matrix entries are updated via a standard learning step as in gradient descent, constructing a new matrix that is generally no longer unitary. In the second step. PROJUNN-D returns the unitary or orthogonal matrix closest in the Frobenius norm to the inputted matrix using Lemma 4.1 At first sight, the second step would require Onn²) time perform, but we can take advantage of the fact that gradient updates are typically approximately low rank (see Appendix E). Efficient low rank approximations
be obtained using sampling methods detailed in Section 4.3) With this in mind, we show that rank i updates can be performed in O(k)²) time when k & n.
Theorem 4.2 (Low rank unitary projection). Let U be X orthogonal/unitary matrix perturbed
by G2, a rank & matrix. Then the projection onto the closest orthogonal/unitary matrix defined below can be performed in Okk(n² + nk + k²)) steps.
U G + arg min II + G2. V
(4)
Veu
To achieve this runtime, we perform updates completely in an O(k) subspace of the full vector can be decomposed into a series of O(k)
space. The operation (U+ G2 GG) matrix-vector operations and an eigendecomposition of a 2 2 sub-matrix. The complete proof and details are deferred to /Appendix CJ One limitation of the above is that the eigendecomposition and inversion of low rank matrix can cause numerical instability after many update steps. We discuss this further in Appendix G.3 where we also provide options to alleviate this instability. PROIUNN-T, which we discuss next, does not require matrix inversion and is thus empirically more stable
4.2 PROJUNN-T
PROJUNN-T T maintains unitarity of matrices by orthogonally projecting gradient updates onto the tangent space and then performing a rotation in the direction of the projection (i.e., along the geodesic). As in PROJUNN-D, there closed form for the orthogonal projection:
Lemma 4.3 (Tangent space projection (82). Given the tangent space TuU(n) of an orthog- onal/unitary matrix U. the orthogonal projection HTg with respect to the canonical metric
(X,Y) = Re (Tr(XtY]) is
Ir (X) (x) -
(5)
Similar to Lemma 4.1 this projection also returns the closest matrix in Frobenius norm to X the tangent space,
min (n)
||Y - 1xx1F = 1lTo (X).
(6)
4

---

Similar to PROJUNN-D D, PROJUNN-T T performs learning in two steps. First, gradient update G is projected onto the tangent space LemmaLeemaaaa 4.3 Then, the orthogonal/umitary matrix is transported or rotated in the direction of the projection by application of the exponential map via the update rule 56 82
U U exp [T (G)]:
where 7) denotes the learning rate. This update rule is an example of Riemannian gradient descent where we use the exponential map to transport gradient updates along the unitary/orthogondd manifold [5]. Here, we transport the matrix U along the geodesic in the direction of IT, (G). This can be related to the update of PROJUNN-D which is an example of a retraction or an approximation to the exponential map of PROJUNN-T (see Appeeddix C.3).
The update rule above requires matrix exponentiation and multiplication, both costly steps which can be sped up when G is a low rank matrix. Namely, to perform a rank kt gradient update, we obtain an equivalent runtime scaling of O(kr²) for the PROJUNN-D when k < n1
Theorem 4.4 (Low rank tangent transport). Let U be an by Gk, a rank k matrix. Then projecting Gk onto the tangent space and performing a rotation in that direction as defined in Equation (7) can be performed in O(k(n² + nk k²)) steps.
orthogonal/unitary matrix perturbed
As with the PROJUNN-D, we achieve this runtime by performing the update above completely in an (kk) subspace of the full vector space. The update via the exponential map can similarly be decomposed into a series (k) matrix-vector operations and an eigendecomposition of a 2k x 2k sub-matrix, Proper manipulations of the cigenvalues of the sub-matrix implement updates via the exponential map. The complete proof and details are deferred to Appendix
4.3 Sampling methods
Commonly. gradients can have large rank but have still have many small singular values (e.g., see Figure lap. Here, matrix A is deemed approximately low rank (see more details in Appendix E). and one can obtain a rank k approximation A; of A by sampling from rows and columns of A. We use two sampling algorithms. The LSI sampling algorithm [68] obtains a rank approximation to an n X n matrix A in time Okn?² log n). The algorithm projects the matrix A onto random orthogonal subspace and then applies SVD based methods to the projected matrix to obtain the low rank approximation to that matrix. This algorithm features low approximation errors even for small k and is used extensively in our implementation. The column sampling (linear time SVD) algorithm (3 samples from the columns of an X matrix A to obtain rank k approximation in OC time, where c is a hyperparameter indicating the number of columns sampled. Typically, e is chosen as multiple of k so the runtime is O(k2n + k=3). In implementing this algorithm, calculate the right singular vectors via matrix multiplication of the left singular vectors so the total runtime is O(kn² + k2n + 1²9).
We note that the two procedures described above, though sufficient for our purposes, can be further optimized in their asymptotic runtime. For sake of completeness, we discuss two of these other sampling algorithms in Appendix
4.4 Extension unitary or orthogonal convolution
Unitary/orthogonal convolutions are linear convolution operations that also preserve the 2-norm (iso- metric). Restricting convolutions to be unitary/orthogonal typically results in drop in performance on standard imaging tasks when used in isolation, but prior work has explored unitary/orthogonal convolutions to potentially improve algorithmic stability and robustness (see Appendix B. for more background) [58 76). We describe here how PROJUNN can be used to implement unitary/orthogonal convolutions in potentially more efficient manner.
Given input tensor X E X where is the number of channels of an M x N input, lincar convolution (or technically cross-correlation) with filter W E CMXXXCXC is defined as
C M N ΣΣΣ
[convw (X) p.g.d
W Wm,ndd Xiirndd.Xtttmtt.....
1=1 m=====1
where the indexing above assumed to be cyelic (taken modulus the corresponding dimension) 55 28). Orthogonal/unitary convolutions form a subset of filters that preserve norms, i.c., filters W
5

---

such that || (X)] | Equivalently c-nvw(-) is orthogonal/unitary if the Jacobian of the transformation is also orthogonal/unitary. To maintain uniaarty/orthooonaliyy we set the dimensions of the filter W above such that it returns an output Y of the same dimension the input X. One can also perform semi-orthogonal or semi-unitary convolution by appropriately rero-padding an input or truncating from dimensions in the output.
Standard convolutional filters are typically supported over a sparse set of local elements, but per- forming orthogona//unitary convolution generally requires implementing convolutions with filters supported over all elements resulting in slower runtimes. One can locally parameterize convolutional filters in the Lie algebra of the orthogonal/unitary group; nevertheless the exponential map into the Lie group expands the support of the filter:
1 L +
exp/convL] [X) = X + L
X
*² 2
X
+
L X 6
(9)
Thus, enforcing unitarity convolutions generally requires additional overhead over the traditional setting of locally supported filters, but by performing convolution in the Fourier domain, runtimes for hull-width filters can be optimally improved to O log(Coog(N))))) + N2? (64]:
FFT conve F.3,
FFT X F,8,
(10)
where W j. is the value of the i and frequency of W across all channels in the Fourier domain and FFT is the 2-dimensional fast Fourier transformation.
Our method is inspired by that of 76 which transformed W into Fourier space and performed a Cayley transformation (approximation to the exponential map into the Lie group) over the matrices indexed by WF.3... which requires C log(N) + N² operations. For our algorithm, parameterize W the Fourier domain and only manipulate W (see Appenddx B.1 for depiction of our parameterization). By parameterizing W directly and performing rank i updates using our PROJUNN, this runtime can be improved to O Cog(NN) + kN?C²²) which is optimal when k < N. Our procedure for performing unitary/orthogonal convolution on an input X with filter W essentially follows the steps in Equation (10) perform FFT on X, block-multiply this by W, and perform an inverse FFT on the output to obtain the final result.
Limitations Unitary/orthogonal convolutions are implemented in cyclic fashion (i.e., indices are taken modulus the dimension) which is not the standard approach but has been used before to accelerate convolutional operations (64]. Additionally, we parameterize convolution filters have support over all possible elements (full-width), which can be expensive in memory. One can restrict the convolution to local terms in the Lie algebra, but this would not improve runtime as our algorithm runs in the Fourier space. To target local terms in a convolution, we instead propose for future work implement a regularizer which has specified support and penalizes the norm of the filter outside that support. Finally, the space of orthogonal convolutions has multiple disconnected components, which can present challenges for gradient based learning [58]. However, we can avoid this draw back by implementing PROJUNN using fully supported filters in the space of unitary convolutions which connected (proof deferred to Appendix C.4).
Theorem 4.5 (Unitary convolutional manifold is connected). The space of unitary convolutions with filters fill support has single connected component.
4.5 Pseudocode for performing PNojUNN updates
Pseudocode for performing an update step on a unitary or orthogonal matrix U with gradient update of AU is shown in Algorithm I In convolutional settings, the steps in Algoottth I are applied across blocks of the convolution in Fourier space which can be performed in parallel. As cautionary note, especially in the last step of Alggorthmm I where there a composition of multiple matrix-vector multiplications, the order of these multiplications must be chosen to only perform matrix-vector operations to ensure optimal runtime. In other words, two N N matrices should never be multiplied by each other at any point in this algorithm.

---

Algorithm PROJUNN update step
orthogonaal matrix U RNXN Require: gradient update AU CNN AU R N
Require: unitary matrix U CN*N
Require: hyperparameter corresponding to rank of approximation
1: Obtain rank & approximation to AU with output م
a.b! R AU (see Section 4.3
Follow steps in Theorem 4.2 (PROJUNN-D) or Theorem 4.4 (PROJUNN- Appendix C
3: Perform Gram-Schmidt (via QR decomposition) concatenation of vectors U and for all E [k]:
output Q C. x semi-orthogonal matrix containing basis after Gram-Schmidt
4: Form matrix K E C 2k below:
PROIUNN-DI K Σ Q'Ui a.b Q + Q'b.a Σ (d
see Equation (C.I) to Equation (C.6)
PROIUNN-T: K
E Q
a Q Q'b:a,UQ
see Equation (C.12) to Equation (C.15)
5: Find eigenvalues -1,--.3 824 and eigenvectors un,..., U2k of K
Perform update step by applying eigenvalue function:
PROIUNN-D: < -U Ei= a;b!) I Σド= +1+)))= unuu
see Equation (C.8) (n8)andee Equation (C.9) added for stability when s, = (we set é 10 10-*)
PROIUNN-T: U <
Σ3 (exp( (oxp(-nss0 (-n8)) ) 1 }) uu| where 17 is the learning rate
see Equation (C.17) Equation (C.18)
RNN model
SCORNN
optimization step runtime
10a
expRNN
103
proJUNN (exact)
vanilla RNN
Frobenius Error
10
rank
k=
projUNN (LSI sampling)
10
ProJUNN (column sampling)
10-1
k=2
k=4
10-3
10-1
k=16
10-5
exact
10-2
150000
300000
450000
step
10
10a
10a
(b) Learning random unitary
hidden size dimension
(a) Runtime comparison
Figure 2: (a) Runtime of PROJUNN (with low rank approximation) scales asymptotically same rate of vanilla RNN and much faster than other unitary RNN models or the exact version PROJUNN (not using low rank approximation). Practical runtime improvements are achieved when the hidden dimension is large (see Appeedix F for details). (b) PROJUNN-T can learn a random target unitary matrix using SGD. For fixed learning rate, the loss decays rate proportional the approximation rank & up to = 16 where the approximation captures the full batch size (see exact PROJUNN which employs approximation). The y-axis plots Frobenius error | Utar
4.6 Runtime comparisons
PROJUNN has nearly optimal asymptotic runtime scaling which offers practical benefits in high dimensions. In the RNN setting, Figure 2a shows that the low rank version of PROJUNN has runtime that scales at the same rate that of vanilla RNN albeit with increased overhead. Updating the unitary matrix of PROJUNN takes (kk??) time for performing updates of rank A: < n, only a factor & more than vanilla RNN which performs updates in O(n²) time. Note, that exact (full rank) updates to the n x n unitary matrices a PROJUNN take roughly (nn3) time corresponding to the runtime of SVD and equivalent the runtime of expRNN and ScoRNN (66 35
In the convolutional setting, PROIUNN offers the most benefit when there are many channels, filters with large support (very wide), or need for exact unitary/orthogonal operations (in contrast with an
7

---

0.2
T= 200
kw4
0.2
T= 750
test loss
test loss
K- 16
K-16
baseline
baseline
0.1
0.1
0.0
0.0
0
10
20
30
40
0
10
20
30
40
epoch
epoch
Figure 3: PROJUNN-T learns the adding task with T = 200 and T = 750. Test error is smoothed by taking the running average of 5 sequential points. See Appendix D.2 for more details.
Given an N N input with channels, forward and backward pass of PROJUNN runs in time log((N))))) + kN2 when performing rank & updates. This is factor of C' faster than the Cayley implementation [76] which runs in time O(N C2 (og(N)+ +N2+N2 C2 For more complete analysis of the asymptotic and empirical runtimes of various models including
approximate method like 73
many not listed here, please see Appendix
5 Experiments
We propose in this section a variety of benchmarked experiments to validate the efficiency and performance of the proposed PROJUNN method focusing mostly RNN tasks] [ We include further
details of the experiments in Appenddix Djincluding a preliminary empirical analysis of PROJUNN in convolutional tasks.
learning random unitary To study the learning trajectories of PROJUNN, consider a simple toy model aimed at learning a target random unitary. More specifically, we parameterize a large unitary matrix U E 22048x2048 to learn Haar random target unitary Utar E 22048x2045 given a dataset {I,, yE = 21; 14096 of size 4096 where æ; E 2048 has entries drawn i.idd. random normal. U is initialized descent over a batch of 16 training points using mean-squared error loss f(x,, y:) = |Ux yell.. Approximations of rank & to the gradient are obtained using the column sampling algorithm.
Toy model:
a random unitary matrix, and each step, perform vanilla gradient
Figure 2b which plots the Frobenius error | - Uzer I/?-, shows that PROJUNN-T equipped equipee-Tequipped with the column sampling approximator is able to learn the random target unitary even when à = (see Appendix D.I for plots with PROJUNN-D). Furthermore, for fixed learning rate, learning requires fewer steps with larger A up k 16, the maximum rank of the gradient (note that Vol(x; y/) is rank 1). Therefore, approximating the gradient via low rank approximations can significantly speed up learning in this task (see Appendix for further details).
Adding task In the adding task, an RNN must learn to add two numbers in long sequence. We consider a variant of the adding task studied (5), where the input consists two data sequences of length T. The first is a list of T numbers sampled uniformly from [0, 1], and the second is list of binary digits set to zero except for two locations (those which must be summed) set to one located uniformly at random within the intervals (1, and [2/ T') respectively.
Consistent with 35 we train our PROJUNN-T using an RNN with hidden dimension of 170 and the RMSprop optimizer to reduce the mean squaree eтror of the output with respect to the target. Naively predicting the average value of one for random input achieves mean -qcares error of approximately 0.167. As shown in Figuure 3) PROJUNN- T is able to learn the target function even with rank k = 1 approximations. Surprisingly, for a fixed learning rate and scheduler, convergence to the true solution is almost equally fast for k = 1, k = 4, and & = 16. Further details are provided in Appendix D.2
Copy memory task The copying memory task a common benchmark for RNNs 38 5
36
where the aim to memorize input data by ignoring a long sequence of void tokens.
Given an
code repository: http:///htthoooo//oooooooooeeear

---

T= T=1000
T=2000
0.02
Km
0.02
k-1
test loss
Km4
test loss
km4
k= baseline
k-16
0.01
0.01
baseline
0.00
0.00
4000
8000
12000
4000
8000
12000
iteration
iteration
Figure 4: PROJUNN-T equipped with the column sampling approximation learns the copy task with 1000 and T 2000 even with rank one approximations.
Table 2:
Result of gradient descent optimization using the RMSprop optimizer on a single layer RNN for the permutedMNIST classification task. Each result is averaged over 3 runs, the same cross validation done for all settings and includes the learning rate and its schedule. Training occurs for 200 epochs, and 10% of the training set (same for all models) is set apart as validation set. The training curves are provided Figure 13
PROJUNN-D
PROJUNN-T
Width RGD
LSTM ScoRNN ExpRNN DT DT DT, k=
16 k=
2
4
16 8
116
92.5
91.8
92.8 93.0 93.0 92.9 93.2 92.5 92.6 92.5 93.0 92.8
170
92.0
94.8
94.9
95.0
95.1 95.2 94.3 94.3 94.4 94.7 94.3 94.4 94.3
94.4
94.1
94.3
360
93.9
92.9
96.2
96.2
96.5
96.4 96.3 96.4 96.4 96.3 96.5
96.4 96.2 96.4
512
94.7
92.0
96.6
96.6
96.8
96.7 96.7 97.0 97.0 96.8 96.9 97.0
96.7 96.7 96.8 96.8 96.7
alphabet of n + 2 symbols {a:);=t 1- n of which represent data (sequence letters A, B,...) and additional void (-) and start recall (:) tokens, the RNN must output the first K input tokens as the last K output tokens and void otherwise. example input/output for M with n
n++
Input: ABCDAD
Output:
ABCDAD
Here, T 1000 or T = 2000 so the network must memorize data over a very long sequence of void tokens. As in 44 consider 8 and input length K 10 and train networks with batch size 128 using the RMSProp algorithm. Naively predicting T + K void tokens followed by K random selections of the possible tokens achieves a baseline loss of K log(n)/(T*) + 2K). PROJUNN-T is able to learn the copy task efficiently as shown in Figure 4 In fact, for fixed learning rates, rank one approximations using the column sampling algorithm provide the fastest convergence to the true solution in comparison to higher rank approximations. Networks were initialized using Henaff initialization (see Appendix G.4) and the learning rate for unitary parameters was set to 32 times less than that of regular parameters (see Appendix D.3 for more details).
Another challenging long-term memory task we consider the permuted pixel-by-pixcl MNIST dataset. Here, MNIST images are flattened, and pixels are randomly shuffled and placed in sequence thereby creating some non-local dependencies. MNIST images have 28 resolution, so the pixel-by-phl by-pixel sequences have length T = 784. The task is digit classification (10 classes) as in standard MNIST models. We employ the same data processing, shuffle permutation, and formatting as that in prior works [56). We perform cross-validation over different learning rates and evaluate both PROJUNN-T
Permuted MNIST
PROJUNN-D with different low-rank values {1,2, 4, 8, 16). The final test accuracy is shown in Table 2 As observed in the copy and adding tasks, we find that using h > 1 does not lead improved performances.
fact, we provide the evolution of the test set accuracy during training in Figure 13 and note that the number of updates is large (hundreds per epoch), even rank & update are able to move the model's parameters to their local optimum.
CNN experiments To explore the performance of our PROJUNN training algorithm for convolu- tional layers, we first analyzed its performance on CIFARIO classification using Resnet architecture 34 Our aim was not to "beat" benchmarks but provide honest comparison of the performance of PROIUNN existing methods. fact, as noted earlier, enforcing unitarity generically results in drop in accuracy for commonly used architectures. Consistent with prior work [76) we employ

---

100
Figure 5: PROJUNN can stably train very deep CNNS. Training on MNIST done for 50 epochs conv2d-BN-Rel.U blocks (repeated "depth"" times) and learning rate cross-validation (RMSprop)) 32 channels throughout, and a final linear classifier. For 100 epochs and a depth 100, we obtain 92.7, 23.5 for the train/test accuracy of unconstrained CNN, and 95.7, 94.6 for ProjUNN-T.
90
cases with
test accuracy
80
Unconstrained (train)
Unconstrained (test)
70
ProjUNN-T (train)
ProjuNN-T (test)
depth
data- -ata-auummntttion of random translations and left-right flips. Previous analysis in the RNN setting showed that rank i = 1 sufficient for convergence so we always set 11 when using PROJUNN in the convolutional setting. For Resnet9 trained using the RMSprop optimizer. PROJUNN- T and PROJUNN-D reached 75% and 82.06% accuracy respectively, matching or outperforming re- ported results from existing unitary CNN models which achieved accuracies of 80.72% for BCOP 58 and 81.70% for Cayley (66 (further details in Appendix D.5) Note, that all of these methods resulted in performance drop compared to the standard model (without unitary constraints) which achieved accuracy of 92. Hence, we believe that there remain a large potential for unitary models to close this gap. Separate from just performance and to motivate the use of unitary parameterization. we provide in Figure 5] test accuracy results from simple CNN model with progressively increasing depth trained with and without unitary parameterization weights might provide benefits for vanilla CNN architectures that have not been designed to handle very deep settings. Of course, various techniques and tricks have been designed to enable CNNs to be trainable at large depths [83 34 [4]. Unitary convolutions, which are simple and theoretically motivated, can potentially be used either separately in-tandem with these other techniques.
MNIST data. We observe that unitary
Discussion
Our PROJUNN shows that one need not sacrifice performance or runtime in training unitary neural network architectures. Our results broadly take advantage of the approximate low rank structure of parameter gradients to perform updates at nearly optimal runtime. Looking beyond the setting studied here, it is an interesting question how our framework can be applied to other neural network architectures or parameter manifolds. Group convolutional neural networks and Riemannian gradient descent offer two promising avenues for further application of our techniques.
References
[1] Scott Aaronson. Read the fine print. Nature Physics, 11(4):291-295 2015.
[2] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Jeffree Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens. Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large- scale machine learning on heterogeneous systems, 2015. Software available from tensorflow.org.
[3] Jonathan Allcock, Chang-Ya Yu Hsieh, Iordanis Kerenidis, and Shengyu Zhang. Quantum algo- rithms for feedforward neural networks. ACM Transactions on Quantum Computing, 1(1):1-24, 2020.
[4] Eric R Anschuetz. Critical points in hamiltonian agnostic variational quantum algorithms. arXiv preprint 17Xiv:2109.066957 2021.
[5] Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks.
In International Conference on Machine Learning, pages 1120-118,, 2016.
10

---

[6] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization, Advances in Neural Information Processing Systems, 32:7413-7424, 2019.
[7] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In International Conference Machine Learning, pages 254-263. PMLR, 2018.
[8] Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, and Seth Lloyd. Quantum-inspired algorithms in practice. arXiv preprint vrXivv:905... 10415, 2019.
[9] Nitin Bansal, Xiaohan Chen, and Zhangyang Wang. Can we gain more from orthogonality regularizations in training deep cnns? arXiv preprint 1rXiv:1810.09100 2018.
[10] Kerstin Beer, Dmytro Bondarenko, Terry Farrelly, Tobias J Osborne, Robert Salzmann, Daniel Scheiermann, and Ramona Wolf. Training deep quantum neural networks. Nature communica- tions, 11(1):1-6, 2020.
[11] Souheil Ben- Yacoub, B Fasel, and Juergen Luettin. Fast face detection using mlp and fft. In Proc. Second International Conference on Audio and Video-based Biometric Person Authentication (AVBPA '99), number CONF, pages 31-36, 1999.
[12] Mathias Berglund, Tapani Raiko, Mikko Honkala, Leo Kärkkäinen, Akos Vetek, and Juha T Karhunen. Bidirectional recurrent neural networks as generative models. Advances in Neural Information Processing Systems, 28:856-864, 2015.
[13] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(7671 195--2022 2017.
[14] Nils Bjorck, Carla P Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normalization. Advances in neural information processing systems, 31, 2018.
[15] Silvere Bonnahel. Stochastic gradient descent on riemannian manifolds. IEEE Transactions on Automatic Control, (89)):211222222 2013.
[16] Grecia Castelazo, Quynh T Nguyen, Giacomo De Palma, Dirk Englund, Seth Lloyd, and Bobak T Kiani. Quantum algorithms for group convolution, cross-correlation, and equivariant transformations. arXiv preprint arXiv:2109. 1330, 2021.
[17] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. arXiv preprint arXiv:2012.09265. 2020.
[18] Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles. Cost-function- dependent barren plateaus in shallow quantum neural networks. arXiv e-prints, pages arXiv 2001, 2020.
[19] Bo Chang, Minmin Chen, Eldad Haber, and Ed H Chi. Antisymmetricrnn: A dynamical system view on recurrent neural networks. arXiv preprint 1902v 096699999 2019.
[20] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder- decoder for statistical machine translation. arXiv preprint 1rXiv:1406.1078 2014.
[21] Mark A Davenport and Justin Romberg. An overview of low-rank matrix recovery from incomplete observations. IEEE Journal of Selected Topics in Signal Processing, 6262),08-622, 2016.
[22] Pierre De Fouquieres and Sophie G Schirmer, A closer look at quantum control landscapes and their implication for control optimization. Infinite dimensional analysis, quantum probability and related topics, 16(03):135002) 2013.
[23] Petros Drineas, Ravi Kannan, and Michael W Mahoney. Fast monte carlo algorithms for matrices ii: Computing a low-rank approximation to a matrix. SIAM Journal on computing, 36( 36(1):15--182 2006.
11

---

[24] Rainer Engelken, Fred Wolf, and Larry F Abbott. Lyapunov spectra of chaotic recurrent neural networks, arXiv preprint arXiv:2006.0244: 2020.
[25] N Benjamin Erichson, Omri Azencot, Alejandro Queiruga, Liam Hodgkinson, and Michael W Mahoney. Lipschitz recurrent neural networks. arXiv preprint arXiv:2006. /2070, 2020.
[26] Thomas Frerix and Joan Bruna. Approximating orthogonal matrices with effective givens factorization. In International Conference Machine Learning, pages 1993-2001. PMLR,
2019.
[27] Alan Frieze, Ravi Kannan, and Santosh Vempala. Fast monte-carlo algorithms for finding low-rank approximations. Journal of the ACM (JACM), 516)):0025-11 1041, 2004.
[28] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
[29] Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. Hippo: Recurrent memory with optimal polynomial projections. arXiv preprint arXiv:2008.0760 2020.
[30] Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. arXiv preprint arXiv:2111.00330 2021.
[31] Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Implicit regularization in matrix factorization. 2018 Information Theory and Applications Workshop (ITA), pages 1-10. IEEE, 2018.
[32] Brian Hall. Lie groups, Lie algebras, and representations: an elementary introduction, volume 222. Springer, 2015.
[33] Awni Y Hannun, Andrew Maas, Daniel Jurafsky, and Andrew Y Ng. First-pass large vocabulary continuous speech recognition using bi-directional recurrent dnns. arXiv preprint 1408. 2873, 2014.
[34] Kaiming He, Xiangyu Zhang, Shaoging Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[35] Kyle Helfrich, Devin Willmott, and Qiang Ye. Orthogonal recurrent neural networks with sealed cayley transform. In International Conference on Machine Learning, pages 1969-1978. PMLR, 2018.
[36] Mikael Henaff, Arthur Szlam, and Yann LeCun. Recurrent orthogonal networks and long- memory tasks. In International Conference Machine Learning, pages 2034-2042 PMLR, 2016.
[37] Nicholas J Higham. The scaling and squaring method for the matrix exponential revisited. SIAM review, 5 5144777477 2009.
[38] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 98): 1997.
[39] Emiel Hoogeboom, Victor Garcia Satorras, Jakub M Tomczak, and Max Welling. The convolu- tion exponential and generalized sylvester flows. arXiv preprint arXiv:2006.0 2020.
[40] Lei Huang, Li Liu, Fan Zhu, Diwen Wan, Zehuan Yuan, Bo Li, and Ling Shao. Controllable orthogonalization in training dnns. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages (429-6438, 2020.
[41] Stephanic Hyland and Gunnar Rätsch. Learning unitary operators with help from (n). In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[42] Yani Ioannou, Duncan Robertson, Jamie Shotton, Roberto Cipolla, and Antonio Criminisi. Train- ing cnns with low-rank filters for efficient image classification. arXiv preprint 151.0445,,,06744, 2015.
12

---

[43] Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks with low rank expansions. arXiv preprint arXiv:1405.3866, 2014.
[44] Li Jing, Yichen Shen, Tena Dubcek, John Peurifoy, Scott Skirlo, Yann LeCun, Max Tegmark, and Marin Soljačié. Tunable efficient unitary neural networks (eunn) and their application to mns.. In Proceedings of the 34th International Conference on Machine Learning- Voluuee 70, pages 1733-1741. JMLR. org. 2017.
[45] Jaroslav Kautsky and Radka Turcajová. A matrix approach to discrete wavelets. In Wavelet Analysis and Its Applications, volume 5, pages 117-135. Elsevier, 1994.
[46] Joseph B Keller. Closest unitary, orthogonal and hermitian operators to given operator. Mathematics Magazine, 48(4)::92-197, 1975.
[47] Iordanis Kerenidis, Jonas Landman, and Anupam Prakash. Quantum algorithms for deep convolutional neural networks. arXiv preprint arXiv:19/L00117,, 2019.
[48] Amir Khoshaman, Walter Vinci, Brandon Denis, Evgeny Andriyash, Hossein Sadeghi, and Mohammad H Amin. Quantum variational autoencoder. Quantum Science and Technology, 4(1):014001, 2018.
[49] Bobak Toussi Kiani, Giacomo De Palma, Milad Marvian, Zi- Liu, and Seth Lloyd. Quan- tum earth mover's distance: new approach learning quantum data. arXiv preprint arXiv:2101.03037, 2021.
[50] Bobak Toussi Kiani, Seth Lloyd, and Reevu Maity. Learning unitaries by gradient descent. arXiv preprint arXiv:2001. 11897, 2020.
[51] Nathan Killoran, Thomas Bromley, Juan Miguel Arrazola, Maria Schuld, Nicolás Quesada, and Seth Lloyd. Continuous-variable quantum neural networks. Physical Review Research, 1(3)0033063, 2019.
[52] Alexander Kirillov Jr. An introduction to Lie groups and Lie algebras. Number 113. Cambridge University Press, 2008
[53] Jan Koutnik, Klaus Greff, Faustino Gomez, and Juergen Schmidhuber. A clockwork mnn In International Conference on Machine Learning, pages 1863-1871. PMLR, 2014.
[54] Hannah Lawrence, Kristian Georgiev, Andrew Dienes, and Bobak T Kiani. Implicit bias of linear equivariant networks. arXiv preprint arXiv:21 2021.
[55] Yann LeCun, Yoshua Bengio, et al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, 3361(10):1995, 1995.
[56] Mario Sezzano--aaaado and David Martinez-Rubio. Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group. In International Conference on Machine Learning, pages 3794-3803. PMLR, 2019.
[57] Jun Li, Li Fuxin, and Sinisa Todorovic. Efficient riemannian optimization on the stiefel manifold via the cayley transform. arXiv preprint arXiv:2002.01113. 2020.
[58] Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Jörn-Henrik Jacobsen. Preventing gradient attenuation in lipschitz constrained convolutional networks. Advances in neural information processing systems, 12:15590-15402. 2019.
[59] Shuai Li, Kui Jia, Yuxin Wen, Tongliang Liu, and Dacheng Tao. Orthogonal deep neural networks. IEEE transactions on pattern analysis and machine intelligence, 43(4): 1368, 2019.
[60] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. regularzzain in over-parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pages 2-47. PMLR, 2018.
13

---

[61] Weiyang Liu, Rongmei Lin, Zhen Liu, James M Rehg, Liam Paull, Li Xiong, Le Song, and
Adrian Weller. Orthogonal over peerpaaameter training. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 7251-7260, 2021.
[62] Yi-Kai Liu. Universal low-rank matrix recovery from pauli measurements. Advances in Neural Information Processing Systems, 24: 14:1168-1646 2011.
[63] Charles H Martin and Michael W Mahoney. Implicit self-regularization in deep neural net- works: Evidence from random matrix theory and implications for learning. arXiv preprint arXiv:1810.01075, 2018.
[64] Michael Mathieu, Mikael Henaff, and Yann LeCun, Fast training of convolutional networks through ffts. arXiv preprint arXiv:13/2.5851 2013.
[65] Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature communications, 9(1):1-6, 2018.
[66] Zakaria Mhammedi, Andrew Hellicar, Ashfaqur Rahman, and James Bailey. Efficient orthogonal parametrisation of recurrent neural networks using householder reflections. In International Conference on Muchine Learning, pages 2401-2409. PMLR, 2017.
[67] Yasunori Nishimori and Shotaro Akaho. Learning algorithms utilizing quasi-geodesic flows on the stiefel manifold. Neurocomputing, 67:106-135, 2005.
[68] Christos H Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, and Santosh Vempala. La- tent semantic indexing: A probabilistic analysis. Journal of Computer and System Sciences, 61(2):217-335, 2000.
[69] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary Vitoo, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
[70] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, Curran Associates, Inc., 2019.
pages
[71] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. The quest for a quantum neural network. Quantum Information Processing, 13(11):2567-2586 2014.
[72] Hanie Sedghi, Vineet Gupta, and Philip M Long. The singular values of convolutional layers. arXiv preprint arXiv: 1805. 10408, 2018
[73] Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. arXiv preprint arXiv:2105.11411 2021.
[74] Sridhar Swaminathan, Deepak Garg. Rajkumar Kannan, and Frederic Andres. Sparse low rank factorization for deep neural network compression. Neurocomputing, 398:185-196 2020.
[75] Cheng Tai, Tong Xiao, Yi Zhang, Xiaogang Wang, et al. Convolutional neural networks with low-rank regularization. arXiv preprint arXiv:1571.06067 2015.
[76] Asher Trockman and Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. arXiv preprint arXiv:2 2021.
[77] Aaron Voelker, Ivana Kajié, and Chris Eliasmith. Legendre memory units: Continuous-time representation in recurrent neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Bue, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
14

---

[78] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. 2019.
[79] Daochen Wang, Oscar Higgott, and Stephen Brierley. Accelerated variational quantum eigen- solver. Physical review letters, 122(14):140500) 2019.
[80] Jiayun Wang. Yubei Chen, Rudrasis Chakraborty, and Stella Yu. Orthogonal convolutional neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11505-11515, 2020.
[81] Dave Wecker, Matthew Hastings, and Matthias Troyer. Progress towards practical quantum variational algorithms. Physical Review A, 92(4):042303, 2015.
[82] Scott Wisdom, Thomas Powers, John R Hershey, Jonathan Le Roux, and Les Atlas. Full-capacity unitary recurrent neural networks. arXiv preprint arXiv:1611.00035, 2016.
[83] Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel Schoenholz, and Jeffrey Pen- nington. Dynamical isometry and a mean field theory of cnns: How to train 10,000-layer vanilla convolutional neural networks. In International Conference on Machine Learning, pages 5393-5402. PMLR, 2018
[84] Xiyu Yu, Tongliang Liu, Xinchao Wang, and Dacheng Tao. On compressing deep models by low rank and sparse decomposition. Pruceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 7370-7379, 2017.
[85] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li, and Simon C Benjamin. Theory of variational quantum simulation. Quantum, 3:191, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes] Contributions and scope of the paper are specified in the abstract and introduction.
(b) Did you describe the limitations of your work? [Yes] Limitations are addressed throughout this work, including after the descriptions of the algorithm in in/eecionn 4.1 and [Section 4.4 in Inppenddx G.3] our comparison to related work in Appendix in the runtime comparison of Appendix F, and various other places.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We confirm that we have read the ethics guideline to ensure our paper conforms to it.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions are given in the sections themselves or part of the statements of the relevant theorems, propositions, and lemmas.
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs are included for all results and deferred to the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] An anonymized demo is included in this anonymous manuscript. Full code will be made available upon publication.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Relevant details are included in Section 5 and Appendix D
15

---

(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] we employed the same experiment setup as prior work that consists in reporting the best test performance based on validation set performances after pross-validation As we report such numbers for variety of settings, error bars could be derived from our tables.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Relevant details are included in Appendix G
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Please refer to Appendix G
(b) Did you mention the license of the assets? [Yes] Please refer to Appendix G
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're ree using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "zwAIBLdqLmY", "reviewer": "Reviewer_3SuC", "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. ", "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "n85nIkpKW19", "reviewer": "Reviewer_o9su", "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.", "questions": "-What are applications beside the RNN toy problems where unitary operators may be needed?\n", "limitations": "The authors have adequately addressed the limitations. I cannot think of any potential negative societal impact", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n- 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.\n- 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.\n- Discussion of related work places this work among existing work, clearly stating advances and differences.\n- 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.\n- Source code for recurrent networks is available which facilitates widespread use. Unfortunately the CNN code was not available in time for the review\n\nWeaknesses\n- The experiments mostly show technical advantages like increases in computational performance, not benefits in applications where this technique is strictly required\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NUrpnjLQ5yW", "reviewer": "Reviewer_Kc6Q", "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\n\nThe 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.\n\nThe 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.\n\nPROJUNN-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.\n\nAn extension to convolution is also discussed, but it is not shown to be competitive to vanilla convolution.\n", "questions": "None", "limitations": "None", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Very compelling result, might enable making URNNs practical\n- Very good exposition\n- Extensive experiments\n\nWeaknesses:\n- 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.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "M0mTBqsFewb", "reviewer": "Reviewer_BcYz", "summary": "This paper proposes a method (projUNN) for efficiently training neural networks with parameters that are constrained to be unitary/orthogonal matrices. \n\nThe 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).\n", "questions": "\nIt 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).\n\n\nMinor Remarks:\nTypo: pg. 23 $$\\hat a = \\tilde{M}^{\\dagger} a \\rightarrow \\hat a = U^{\\dagger} a$$ \n\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nOne 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.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept