Low-rank lottery tickets: finding efficient low-rank neural networks via matrix differential equations
Authors: Steffen Schotthöfer
Emanuele Zangrando
Jonas Kusch
Gianluca Ceruti
Francesco Tudisco
Venue: NeurIPS 2022 Accept (2022)
Keywords: Neural Network Compression
Low Rank Matrices
Dynamical Low Rank Approximation
Neural Network Training
Pruning

Abstract: Neural networks have achieved tremendous success in a large variety of applications. However, their memory footprint and computational demand can render them impractical in application settings with limited hardware or energy resources. In this work, we propose a novel algorithm to find efficient low-rank subnetworks. Remarkably, these subnetworks are determined and adapted already during the training phase and the overall time and memory resources required by both training and evaluating them is significantly reduced. The main idea is to restrict the weight matrices to a 
low-rank manifold and to update the low-rank factors rather than the full matrix during training. To derive training updates that are restricted to the prescribed manifold, we employ techniques from dynamic model order reduction for matrix differential equations. Moreover, our method automatically and dynamically adapts the ranks during training to achieve a desired approximation accuracy.
The efficiency of the proposed method is demonstrated through a variety of numerical experiments on fully-connected and convolutional networks. 

Low-rank lottery tickets: finding efficient low-rank neural networks via matrix differential equations
Steffen Schotthöfer'
Emanuele Zangrando"
Karlsruhe Institute of Technology 76131 Karlsruhe (Germany) steffen.c www.eee..whoothheeeeeeeeeee edu
Gran Sasso Science Institute 67100 L' L'Aquila (Italy) emanuele zangrando@gsai. it
Jonas Kusch
Gianluca Ceruti EPF Lausanne 1015 Lausanne (Switzerland) g gianluca. cerut @epff........ ch
Francesco Tudisco
University of Innsbruck 6020 Innsbruck (Austria)
Gran Sasso Science Institute
67100 L' Aquila (Italy) francesco. tudiscodgssi. it
j jonas. aaasskuschh@gmme kuschh@gmail.c.mmm com
Abstract
Neural networks have achieved tremendous success in large variety of applica- tions. However, their memory footprint and computational demand can render them impractical application settings with limited hardware or energy resources. In this work, we propose novel algorithm to find efficient low-rank subnetworks. Remarkably, these subnetworks are determined and adapted already during the training phase and the overall time and memory resources required by both training and evaluating them are significantly reduced. The main idea is to restrict the weight matrices than the full matrix during training. To derive training updates that are restricted the prescribed manifold, employ techniques from dynamic model order reduction for matrix diffcrential equations. This allows us to provide approxima- tion, stability, and descent guarantees. Moreover, our method automatically and dynamically adapts the ranks during training to achieve the desired approximation accuracy. The efficiency of the proposed method demonstrated through variety of numerical experiments on fully- conteceddde and convolutional networks.
low-rank manifold and to update the low-rank factors rather
Introduction
While showing great performance in terms of classification records, most state-of-the-art neural networks require an enormous amount of computation and memory storage both for the training and only increase infrastructure costs and energy consumption, but also make the deployment of artificial neural networks to infrastructures with limited resources such as mobile phones smart devices prohibitive. On the other hand, it is well-known that networks' weights contain structures and redundancies that can be exploited for reducing the parameter space dimension without significantly affecting the overall accuracy
the evaluation phases (27). These requirements
I7].
Network pruning is popular line of research that addresses this problem by removing redundant parameters from pre-trained models. Typically, the initial network is large and accurate, and the goal is to produce a smaller network with similar accuracy. Methods within this area include weight sparsification 20 24 49] and quantization [IO 60), with different pruning techniques, including
search-based heuristics 24 reinforcement learning 2 23 and genetic algorithms (3). More recent
work has considered pruning during training, by formulating pruning as data-driven optimization
These authors contributed equally this work.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

problem 20 26 27 The resulting "dynamical pruning" boils down to parameter- constrriee- training phase which. however, has been mostly focused on requiring sparse or binary weights so far.
Rather than enforcing sparsity or binary variables, in this work we constrain the parameter space to the manifold of low-rank matrices. Neural networks' parameter matrices and large data matrices in general are seldom full rank IIS 48 53 56). Constraining these parameters to lie on a manifold defined by low-rank matrices is thus a quite natural approach. By interpreting the training problem as a continuous-time gradient flow, we propose a training algorithm based on the extension of recent Dynamical Low-Rank Approximation (DLRA) algorithms 4 use low-rank numerical integrators for matrix Ordinary Differential Equations (ODEs) to obtain modified forward and backward training phases that only use the small-rank factors in the low-rank representation of the parameter matrices and that are stable with respect to small singular values. This is a striking difference with respect to recent alternative "vanilla" low-rank training schemes which simply factorize the weight matrices as the product of two low-rank factors UVT and
6 This approach allows us to
31 57 apply a descent algorithm alternatively on the two variables U and V.
We perform several experimental evaluations on fully-connected and convolutional networks showing that the resulting dynamical low-rank training paradigm yields low-parametric neural network architectures which compared to their full-rank counterparts are both remarkably less-demanding in terms of memory storage and require much less computational cost to be trained. Moreover, the trained low-rank neural networks achieve comparable accuracy to the original full architecture. This observation is reminiscent of the so-called lottery tickets hypothesis - dense neural networks contain sparse subnetworks that achieve high accuracy 17 and suggests the presence of low-rank winning tickets:
low-rank subnetworks of dense networks. Remarkably, our dynamical low-rank training strategy seems to be able to find the low-rank winning tickets directly during the training phase independent of initialization.
2 Related work on low-rank methods
Low-rank factorization using the SVD and other matrix decomposition techniques have been ex- tensively studied in the scientific computing and machine learning communities. The challenge of compressing and speeding up large-scale neural networks using low-rank methods has sparked wide-spread research interest in recent years and significant effort has been put towards developing low-rank factorization strategies for deep neural networks.
Previous works can roughly be categorized in approaches with fixed low rank and variable low rank during training time. Fixed rank approaches decompose weight matrices using SVD or tensor de- compositions of pre-trained networks and fine-tune the factorized network 12 38 50 55,, constrain weight matrices to have a fixed low rank during training 130 31 57], or create layers as linear combination of layers of different rank (29). Hence, these methods introduce the rank of the matrix decomposition as another hyperparameter to be fine-tuned. Rank-adaptive methods mitigate this issue by automatic determination and adaption of the low-rank structure after training. In particular, apply heuristics to determine the rank of the matrix decomposition ahead of time, whereas encourages low-rank weights via penalized loss that depends on approximated matrix ranks.
33
34
59
Few methods have been proposed recently that adapt the ranks of the weight matrix alongside the main network training phase. In 44), the authors set up the neural network training as a constrained optimization problem with an upper bound on the ranks of the weights, which is solved in an alternating approach resulting in an NP-hard mixed integer program. The authors of (8 formulate similar constrained optimization problem resulting in mixed discrete-continuon optimization scheme which jointly addresses the ranks and the elements of the matrices. However, both these approaches require knowledge of the full weight matrix (and of its singular value decomposition) during training and overall are more computational demanding than standard training.
In this work we overcome the above issues and propose a training algorithm with reduced memory and computational requirements. To this end, we reinterpret the optimization problem of neural network as gradient flow of the network weight matrices and thus as matrix ODE. This continuous formulation allows us to use recent advances in DLRA methods for matrix ODEs which aim at evolving the solution of the differential equation on a low-rank manifold. The main idea of DLRA 355. which originates from the Firac-Frenkel variational principle [14 18), is to approximate the solution through low-rank factorization and derive evolution equations for the individual factors.

---

Thereby, the full solution does not need to be stored and the computational costs can be significantly reduced. To ensure robustness of the method, stable integrators have been proposed in 44 and [ Instead of evolving individual low-rank factors in time, these methods evolve products of low-rank factors, which yields remarkable stability and exactness properties (32,, both in the matrix and the
tensor settings [ 36 45
46). In this work, we employ the "unconventional" basis update & Galerkin
step integrator [6] as well as its rank-adaptive extension [4], see also 7 37]. The rank-adaptive
unconventional integrator chooses the approximation ranks according to the continuous-time training dynamics and allows us to find highly-performing low-rank subnetworks directly during the training phase, while requiring reduced training cost and memory storage.
3 Low-rank training via gradient flow
Consider ford-forward fully-connected neural network M(xx) = ZM, with 20 = R"o, 2x (W + by) E IR A = 1,.... .M (the convolutional setting is discussed in the supplementary material (6.6). We consider the training of A based on the optimization of loss function L(W,,... W War; (x)), y) by means of a gradient-based descent algorithm. For example, when using gradient descent, the weights of N at iteration & E N are updated via
(1) with learning rate A. When the weight matrices W₁ are dense, both the forward and gradient evalu- ations of the network require a large number of full matrix multiplications, with high computational expense and large memory footprint. This renders the training and the use of large-scale neural networks a difficult challenge on limited-resource devices. At the same time, a wealth of evidence shows that dense networks are typically overparameterized and that most of the weights learned this way are unnecessary [15] 48). In order to reduce the memory and computation costs of training, we propose a method that performs the minimization over the manifold of low-rank matrices.
W W AVw,L(W, L(W,... War:
1k.1,.... M
To this end, we assume that the ideal W₁ can be well-approximated by a matrix of rank r1 & Dt. n of the form SVV. E R x where Us R V& R are thin and tall matrices having orthonormal columns spanning optimal subspaces which capture essential properties of parameters, and S₁ E XT* is a tiny full-rank matrix that allows us to extrapolate the useful information from the learned subspaces Us and Vj.
Traditional descent algorithms such as T do not guarantee the preservation of the low-rank structure U.S.V, when updating the weights during training and require knowledge of the whole W₂ rather than the factors Uk, Sk, Vg. Here reinterpret the loss minimization as continuous-time gradient flow and derive a new training method that overcomes all aforementioned limitations.
Minimizing the loss function with respect to WE is equivalent to evaluating the long time behaviour of the following matrix ODE that allows us to interpret the training phase as a continuous process:
(1) Vw, Www L(W,,-. WM: (N))
(2)
where the "dot" denotes the time-derivative. Let Mr. denote the manifold of matrices with rank Tk and assume at certain time tu the weights are in the manifold, i.e., (to) E .r. Using this continuous-ting time interpretation allows us to derive a strategy to evolve the weights according to the dynamics in (2) that (t) E Mrz for all 2 to. To this end, in $3.1 we exploit the fact that (t) admits a time-dependent factorization 13 (t) = (t)S (t)V)) (L)) to rewrite ( as system of matrix ODEs for each of the individual factors Ug,Sz and Vg. Then, in $ we propose an algorithm to efficiently integrate the system of ODEs. We show in $4.1 that such algorithm reduces the loss monotonically and is accurate, in the sense that UgS V R Wt, i.e. the learned low-dimensional subspaces UR and V/2 well-match the behaviour of the full full-rank network W₁ solution of (2). through the action of the learned Sk- Remarkably, using the dynamics of the individual factors will also allow to adaptively adjust the rank ra throughout the continuous-time training process.
3.1 Coupled dynamics of the low-rank factors via DLRA
We consider the dynamical system of single weight matrix We, while the remaining weight matrices are fixed in time and are treated as parameters for the gradient. In the following, we omit writing these parameters down for efficiency of exposition. Assuming (t) E Mre. we can formulate (2) as
min { [I + Vw. ((W. Wo(()) E Tmcco,MM..)
3

---

where (t) is the tangent space of Mr, at position Ws(t). In order to solve 3 observe that (3) can be equivalently formulated as the following Galerkin condition 35
we further
(t) + Vw, <(W (t)), &W
voWa E (wa(t)
(4)
From Wx = V generic element &W2 of the tangent space (r, can be written as 8W V + U + UU.S&VV
where 6U4, and 8V are generic elements of the tangent space of the Stiefel manifold with rh orthonormal columns at the points UR and Vı. respectively, and 8S₁ is generic 73 7% matrix, see e.g. [35 $2] for details. Additionally, the Gauge conditions U/ oU 0 and V oV must be imposed ensure orthogonality of the basis matrices, and the uniqueness of the representation of the tangent space elements. Similarly, by the chain rule applied several times we have
d (USS U.SAVT + UUSAVT + UNSAV
WR- di
Now, the Galerkin condition becomes
( + V + U.SVV + Fw: oW,) = =0, voWA E Mra (5)
with U, 0 and V. 0. we choose ow U455 V in we obtain
(U. U, U.S.S U. V + U V ((W)), 85&) = 0.
Thus, using the Gauge conditions, we obtain ($A + U V w. (t) 85x) O, which has to hold for a generic r& X rx matrix 85,, We obtain this way an evolution equation for the (t(() factor. Similarly, specifying (5) for the two choices SW4 5 V and SW, = S allows to obtain the following system of differential equations for the individual factors of W
$ -U Vw. ((W)
Üs -I URU Vw, (OWAEE
(6)
1/2 - (w,
4 KLS-based training algorithm
In order to perform an efficient and robust rank-constrained training step, we numerically integrate the
system of ODEs (6). Our approach is based the "unconventional KLS integrator" [6] and its rank-
adaptive version [4]. The pseudocode of the proposed training strategy is presented in Algorithm
The main idea of the KLS algorithm is alternately represent the product W. U as W₂ V. and Wt Ug IT consider the corresponding coupled ODEs from o and then perform three main steps:
1.2. K&L-steps (in parallel). Update the current K₁ and La by integrating the differential equations
(k(()) V ((VK(VVT K2(0) Sk
(t) - (w, Tu, Lx(0) V&ST
from é 0 to уу; then form orthonormal basis matrices Uj and Vn spanning the range of the computed (x) and (n)).
S-step. Update the current St by integrating the differential equation
Sx()) = - U. Vw, C(, (( Vv
(8)
from / - 0 to / with initial value condition Sa(0) = U, UNS&VVVV
An important feature this algorithm is that it can be extended to rank adaptivity relatively straightforward manner 4), letting us dynamically evolve the rank of S₃ (and thus the rank of W during the computation. This is particularly useful, as we may expect the weight matrices to have low ranks but may not know what the "best" ranks for each layer are. Typically, dynamically adapting

---

the ranks of a low-rank optimization scheme is a challenging problem as moving from the manifold Mr, to Mr introduces singular points [9]. Instead, treating the training problem as a system of matrix differential equations allows us to overcome this issue with a simple trick: at each step of the KLS integrator we double the dimension of the basis matrices Ug and Vi. computed in the K- and L-steps by computing orthonormal bases spanning [Kx (1) Ux] and [T) V&J,, respectively, i.e. by augmenting the current basis with the basis computed in the previous time step. Then, after the new Sş matrix is computed via the S-step, a truncation step is performed. removing from the newly computed Sg matrix all the singular values that are under certain threshold 0.
Of course, adding the rank-adaptivity to the integrator comes at cost. In that case, each step requires to perform SVD dccomposition of twice the size of the current rank of Sş, in order to be able to threshold the singular values. Moreover, the dimension of the bases Ux and Vi may grow, which also may require additional computational effort. However, if the ranks remain small throughout the dynamics, this computational overhead is negligible, as we will further discuss in $4.3 and $
4.1 Error analysis and convergence
In this section we present our main theoretical results, showing that (a) the low-rank matrices U..&&V V formed by the weights' factors computed with Alg. 1 are close to the true solution of (2). and (b) that the loss function decreases during DLRT, provided the singular value threshold 1 is not too large, i.e., is bounded by a constant times the square of the time-step size 1) (see Theorem 1). In the version we present here, part of the statements are presented in an informal way for the sake of brevity. We refer to the supplementary material for details and for the proofs.
Assume the gradient flow FZ) = -V w C(W1. Z.... WM, 3) in is locally bounded and locally Lipschitz continuous, with constants C1 and C2. respectively. Then.
Theorem 1. Fixed and y. let Wt(() be the (full-rank) continuous-
solution of (2) and let UK, Sg. Vv be the factors computed with Algorithm Srriithmmaffa aater I steps. Assume that the K,I.S steps 7 and (8) are integrated exactly from O to n,. Assume moreover that, for any Z E Mrr sufficiently close to W. 2 (tn), the whole gradient flow Fx(Z) is "e-close" " to Mrx- Then,
SU Wn(ll)l S 61 + 622) + cg0011
k 1 M
where the constants C₁, C2 and ca depend only on C₁ and Cz. In particular, the approximation bound does not depend on the singular values of the exact nor the approximate solution.
Observe that, while the loss function C decreases monotonically along any continuous-tin -tim solution (t) of ( it is not obvious that the loss decreases when the integration is done onto the low-rank manifold via Algorithm [ The next result shows that this is indeed the case, up to terms of the order of the truncation tolerance More precisely, we have
Theorem Let Wt U (V)) be the low rank weight matrix computed step t of Algorithm 1 and let L(I) = L(WE, W M (xx), y). Then, for a small enough time-step y) we have
C(t + 1) S C(t) am + 33
where a and are positive constants that do not depend on t, n) and 9.
4.2 Efficient implementation of the gradients
All the three K,L.S-steps require the evaluation of the gradient flow of the loss function with respect to the whole matrix WR- Different approaches to efficiently compute this gradient may be used. The strategy we discuss below aims at reducing memory and computational costs by avoiding the computation of the full gradient, working instead with the gradient with respect to the low-rank factors.
To this end, we note that for the K-step holds Vw, (L) V = VK, (()V ). Hence, the whole gradient can be computed through forward run of the network with respect to K₃
2 ox (K& (t)V 24-1 bb),
k= 1, M
and taping the gradient with respect to Kg. In this way, the full gradient does not need to be computed and the overall computational costs are comprised of running a forward evaluation while taping gradients with respect to Kg, analogously to the traditional back-propagation algorithm. The L- and
5

---

Algorithm 1: Dynamic Low Rank Training Scheme (DLRT)
Input: Initial low-rank factors 5% ~ r X Tk Ug ~ nu x Tg:V ~ 7 1 x r for h ;,...; M;
iter: maximal number of descent iterations per epoch;
adaptive: Boolean flag that decides whether or not to dynamically update the ranks; d: singular value threshold for adaptive procedure.
for each epoch do
for 1 0 iter do
for each layer k do
K + S
/* K- K-step */
K x++1 + one-step-imtegrate ((t) = - Vx((K(O(VE) Σ4-1 +b),, ((0) = k%)
/ L-step */
4 + one-step-integrate -Vvc(U( 2k-1 -
L(0) = ]
adaptive then
/* Basis augmentation step
Kt [ Ut]
[++ + [ V
10
11
U orthonormal basis for the range of K++1
/* S-step +/
ME f (U
12
V t- orthonormal basis for the range of 7++1
13
N₂ + (Ve+1)
14
15
S N
St -one---onpp---eeeeeeeee men-step-integrate ($(t)= - - S((VVt))) -x-1+)))))))))) "
16
17
adaptive then
Rank compression step */
P.E. Q SVD(S**1)
18
19
$t + truncate y using the singular value threshold 0
Ut+1 -ut+1 where P = [first r(+t columns of P]
V + va Q where Q = [first r
++1 columns of Q]
21
/* Bias update step */
22
b
one one-step-integrate (b(t)= V.C(UL ( +b)))))))
S-steps can be evaluated efficiently in the same manner, by evaluating the network while taping the gradients with respect to La and Sg, respectively, Hence, instead single gradient tape (or chain rule evaluation) of the full weight matrix network, we have three gradient tapes, one for each low rank step, whose combined computational footprint is less than the full matrix tape. We provide detailed formulas for all the three gradient tapes in the supplementary material 6.5
4.3 Implementation details, computational costs and limitations
Each step of Alg. I requires the computation of two orthonormal bases for the ranges of Kt+1 and L There are of course different techniques to compute such orthonormal matrices. In our implementation we use the QR algorithm, which is known be one of the most efficient and stable approaches for this purpose. In the adaptive strategy the singular values of S(+1 are truncated according to parameter To this end, in our implementation, we use the Frobenius norm of Σ. Precisely, we truncate Σ diag (a;) step 19 of Alg. [ by selecting the smallest principal r submatrix such that (E of 1/21/2222 < 0. Finally, one-step-integrat denotes numerical procedure that integrates the corresponding ODE from time = 0 to
In practice one employ different numerical integrators, without affecting the ability of the algorithm to reduce the loss function (see 4 Thm. 5]) while maintaining the low-rank structure. In implementation used two methods:
Explicit Fuler. This method applied to the gradient flow coincides with one step of Stochastic Gradient Descent (SGD), applied to the three factors KR, Læ, Ss independently.
Adam. Here we formally compute the new factors by modifying the explicit Fuler step as in the Adam optimization method. Note that Nesterov accelerated SGD is known to coincide with

---

0.8
DLRT
1.4
1.2
0.6
time 13
1.0
time
0.2
0.4
DURT
dense reference
0.2
200
500
2000
1500
2000
2500
rank
(a) Training timings
(b) Prediction timings
Figure Comparison of batch execution and training times of 5-layer, 5120-neurons low-rank networks of different ranks and a non-factorized reference network with the same architecture on the MNIST dataset. Training times shown correspond to one epoch for batch of 256 datapoints. Prediction times refer instead to the whole dataset. All the times are the average over 1000 runs.
particular linear multistep ODE integrator [5I]. While Adam does not directly correspond to a numerical integrator our knowledge, in our tests it resulted in faster decrease of the loss than both Euler (SGD) and Nesterov accelerated SGD.
For both choices, the target time step corresponds to the value of the learning rate, which we set to 0.2 for Euler. For Adam, we use the default dynamical update, setting 0.001 starting value.
Computational cost. To obtain minimal computational costs and memory requirements for the K-step, the ordering of evaluating K₂ V. Zk-1 in (9) is important. First, compute ž V z IR* which requires (f operations. Second, we compute K₃ which requires ((r.Ti)) operations. Adding the bias term and evaluating the activation function requires O(ng) operations. Hence, combined over all layers we have asymptotic cost of O (Ex [ + (1++1)). Taping the forward evaluation compute the gradient with respect to Kg discussed in $4.2 does affect the asymptotic costs, i.c. the costs of computing the K-step at layer k assuming a single data point x requires CK I Σx + operations.
similar manner, we obtain the computational costs of the L- and S-steps, which are again CL.S S Σx (n + +*++1). Moreover, the QR decompositions used in the K- and L-step require O (Ex rx(ng + m)-1)) operations and computing the SVD in the truncation step has worst-case cost of O E r2). Hence, assuming т < Tkk, Tk the cost per step of our low-rank method is CDLRA Ee (2 + n2-1)), opposed to the dense network terms of memory cost, note that we only need to store Tı (r 74 + m*+11) parameters per layer during the algorithm, corresponding the matrices St. U V.. Moreover, at the end of the training we can further compress memory by storing the product of the trained weight factors Sk, rather than the individual matrices.
training, which requires Cdense $ Ex ngn+++1 operations.
Limitations. A requirement for DLRT's efficiency that I'ss & Tu 1+ When the truncation threshold / is too small, Alg. does not provide advantages with respect to standard training. This is also shown by Fig. [ Moreover, in the terminology of [54], DLRT is designed to reduce training costs corresponding to model parameters and to the optimizer. To additionally decrease activation costs, DLRT can be combined with micro- micro-batching or checkpointing approaches. Finally, the choice of d introduces additional hyperparameter which the moment requires external knowledge for tuning. However, our experiments in show that relatively large values of yield competing performance compared number of baselines, including standard training.
5 Numerical Results
We illustrate the performance of DLRT Algorithm on several test cases. The code implemented in both Tensorflow https///thhub.com//CMMMMMMM///// The networks are trained on an AMD Ryzen 3950X CPU and Nvidia RTX 3090 GPU. Timings are measured pure CPU execution.
and PyTorch
5.1 Performance analysis MNIST dataset
partition MNIST dataset [I]] randomly sampled train-validation-e sets size 50K-10K- 10K. Images are pixelwise normalized; no further data augmentation regularization has been used.
7

---

rank layer
26
layer
24
rank layer
layer
rank layer
700
rank
rank layer 2
rank layer
20
rank layer
18
50
16
50
100
150
200
250
100
150
200
250
apoch
epach
(a) Rank evolution for 7 0.15
(b) Rank evolution of r 0.05
Figure 2: Rank evolution (layers 1-4) of 5-layer (500,500,500,500,,00 fully-connected net on MNIST.
Fixed-rank fully-connected feed-forward network timings. First, we compare the training time of the adaptive DLRT Alg. [ Jon a 5-layer fully-connected [5120, 5120, 5120, 5120, 10] network fixing the ranks of layers 1 1-4, i.e. choosing specific starting rank re for the input weight factors and truncating 2 at line 19 of Alg. [ to the principal re x rg submatrix, rather than via threshold. Next, we measure the average prediction time on the whole MNIST dataset over 1000 runs. Fig. aa) and [bb) show that both timings scale linearly with the rank of the factorizations, and that for sufficienlly small ranks DLRT is faster than the full-rank baseline both in terms of training and of prediction.
Rank evolution and performance of DLRT for different singular value thresholds. Next, we demonstrate the capabilities of DLRT to determine the rank of the network's 's weight matrices automatically during the network training using Algorithm [ The Adam optimizer with default learning rate is used for the gradient update. We train fully connected 5-layer networks, of which the first 4 are replaced by low-rank layers in the subsequent tests. The activation function is chosen to be ReLU for the hidden layers, and softmax for the output layer. The training loss is sparse categorical cross entropy and additionally measure the model's ss accuracy. We use batch size 256 and train for 250 epochs. We choose 0 = r ||Σ|| thus we truncate the singular values of the current S by fraction 7 of the total Frobenius norm. The smaller т, the more singular values kept.
Figures 2 (a) and (b) show the evolution of the rank adaptive layers of a 5-layer 500-neuron network 0.15. We
in long time case study for 0.05 and full matrix ranks are reduced significantly, to 27 for T = 0.15, and to ~ 85 for J = 0.05 respectively. Within the first 50 epochs, the layer ranks are already close to their final ranks. This indicates that the rank adaptive algorithm is only needed for the first few training epochs, and can then be replaced by the computationally cheaper fixed-low low-knkk training (by setting the Boolean variable adaptive to False in Algorithm|] [].. Figure [eguree]comper compares the mean test accuracy of 5-layer networks with 500 and 784 neurons with different levels of low-rank compression, over five independent runs with randomly sampled train-test-val sets. The networks can be compressed via dynamical low-rank training by more than 95%, while only losing little more than 1% test accuracy compared to the dense reference network marked in red. Remark that restricting the space of possible networks to given rank regularizes the problem, since such a restriction can be understood as adding a PCR regularization term to the loss function. This can be seen from the tendency of not overfitting and reaching improved test accuracies compared the corresponding dense network for moderate compression ratios. Also note that adaptive-low rank training eliminates the need for hyperparameter grid search in terms of layer-wein weights, due to automatic rank adaptation. The rank dynamics for all configurations can be seen in the supplementary material [6.3] Finally, in the supplementary material $6.4 we compare the use of DLRT with the vanilla approach which simply thresholds the singular values of the full-rank network. Our results show that advantageous low-rank winning tickets exist, but are not easy to find. In fact, the vanilla low-rank subnetworks perform very poorly. From this point of view, our approach can be seen as an efficient dynamical pruning technique, able to determine nigh-performing low-rank subnetworks in a given dense network. Remarkably, our numerical experiments suggest that low-rank winning tickets can be trained from the start and do not to heavily depend on the initial weight guess.
that within the first epoch the initial
Convolutional layers: LeNet5. Here we compare the proposed dynamical low-rank training scheme on LeNet5 (39 on MNIST, against the full-rank reference and several baselines. SVD prune 61 and LRNN 28 are the closest approaches to our DLRT: they dynamically train low-rank layers by adding rank-penalty to the loss function, and by complementing the standard training step via an
8

---

98.
98.25
96.25
test accuracy
98.00
96.00
97.75
97.75
07.50
97.50
97.25
500 neurons
500 neurons
97.00
784 neurons
97.00
7B4 neurons
network weights
compression [16]
Figure Mean test accuracy over parameters' number and compression rate for runs with randomly sampled train-test-val sets on 5-layer fully-connected nets. Red dots denote the full-rank baseline.
Test Accuracy
Train Loss
100
no decay
decay
2,5
no deeayy
decay
Fend atcurary [N]]
80
2,0
1.5
1.0
40
20
2661
34.4
0.0
2
2
6
epoch
epoch
epach
epach
Figure 4: Mean learning curves with standard deviation of Lenet5 on MNIST over 10 runs of DLRT compared to a vanilla layer factorization W₂ = V Both methods are implemented with fixed learning rate of 0.01, and batch size of 128. The weight matrices are either completely randomly initialized ("no decay") or are initialized with a random choice forced to have an exponential decay on the singular values ("decay"".
SVD projection step in the latter and pruning step in the former. While computing low-rank factors for each layer, thus reducing memory storage of the network, this training approach is more expensive than training the full network. GAL 22 SSL [62]. and NISP [58] are pruning methods which aim at learning optimal sparse weights (rather than low-rank) by adding terms to the training loss. As for LRNN, these methods do not reduce the computational cost of the training phase (as indicated with the < 0% in Table [ Analogously to [28), our adaptive low- low-rank training technique is applied convolutional kernel into a matrix. Details are provided in the supplementary material $6.6 All the models are trained for 120 epochs using SGD with fixed learning rate of 0.2. Results in Table I show that the DLRT algorithm is able to find low-rank subnetworks with up to 96.4% less parameters than the full reference, while keeping the test accuracy above 95%. Compared to the baseline methods, we achieve better compression rates but observe lower accuracy. However, unlike the baseline references, DLRT automatically prunes the singular values during training, without requirement to solve any additional optimization problem, thus significantly improving time and memory efficiency of both forward and backward phases, with respect to the full reference.
regularization
the convolutional layers by flattening the tensor representing the
Robustness with respect to small singular values and comparison with vanilla low-rank parametrization. direct way to perform training enforcing a fixed rank for the weight ma- trices is to parameterize each weight as W, = V. and alternating training with respect to Us and to V.. This is the strategy employed for example in [31 177. This vanilla low-rank parametrization approach has a number of disadvantages with respect to DIRT,, on top of the obvious non-adaptive choice of the rank. First, DLRT guarantees approximation and descent via Theorems and 2 Second, we observe that the vanilla factorization gives rise to an ill-conditioned optimization method when small singular values occur. This problem is peculiar to the low-rank manifold itself [16] 35), whose local curvature is proportional to the inverse of the smallest singular value of the weight matrices. In contrast, the numerical integration strategy at the basis of DLRT is designed to take advantage of the structure of the manifold and is robust with respect to small singular values [32. This can be seen from the bound of Theorem [ where the constants are independent the singular values the weight matrices, and is illustrated by Figure 4. where DLRT shows a much faster convergence rate with respect to vanilla SGD performed on each factor of the parametrization U&V T when applied to train LeNet5 on MNIST. Both methods are implemented with the same fixed learning rate.

---

Table 1: Results of the training of LeNet5 on MNIST dataset. Effective parameters represent the number of parameters we have to save for evaluating the network and those we need in order to train via the DLRT Alg The compression ratio (c.r.) is the percentage of parameter reduction with respect the full model << 0% indicates that the ratio is negative). "ft" indicates that the model has been fine-tuned. "LeNet5" denotes the standard LeNet5 architecture trained with SGD.
NN metrics
Evaluation
Train
method
test acc.
ranks
params
c.r.
params
C.I.
LeNet5
99.2%
20, 50, 500, 10]
430500
0%
430500
0%
0.11
98.0%
[15, 46, 13, 10]
47975
88.86%
50585
88.25%
DLRT
7 0.15
97.8%
13,31,9.10
34435
92.0%
35746
91.7%
T
97.2%
10,20. 20, 7.10
25650
94.04%
26299
93.89%
0.3
95.3%
6,
15520
96.4%
15753
96.34%
SSL 662 (ft)
99.18%
110000
74.4%
< 0%
NISP [58] (fit)
99.0%
100000
76.5%
< 0%
GAL 142
98.97%
30000
93.0%
< 0%
LRNN 28
98.67%
3.3.9 9.9
18075
95.8%
0%
SVD prune 61
94.0%
2,5, 89, 10]
123646
71.2%
< 0%
Table 2: Results ImageNet1k (left) and Cifar10 (right). The compression ratio is the percentage of parameter reduction with respect to the full model. DLRT used with r = 0.1. The number of parameters of the full models are: 33.6M (VGGI6); 23.6M (AlexNet); 29.6M (ResNet-50). We report difference in test accuracy (top-5 test accuracy for ImageNetIk) with respect to the full baselines.
ImageNetIk
test acc. [%]
compression rate
Cifar
method
(to baseline)
eval[%]
train[ %]
test acc.
compression rate
DLRT 52 PP.2
0.56
54.1
14.2
method
(to baseline)
evall %)
train| %]
VGG16 ResNet- 50
-08
52.2
< 0
PP.1
0.2
44.2
AlexNet VGG16
DLRT GAL LRNN
-1.89 -1.87
56
77.5 X
CP SF
-1.4
50.0
0
77
-0.2
41.8
-1.9
60
ThiNet
1.5
36.9
DLRT 15-1
-2.99
86
78 4
-019
80.2
DLRT
-1.79
86.3
84.2
-1.80
80.0
AAV
NISP 58
-1.06
<
ThiNet 4p
0.47
69.04
RNP(3X)
-2,33
66.67
5.2 Results on ImageNetIK and Cifar10 with ResNet-50, AlexNet, and VGG16
Finally, we assess the capability of compressing different architectures on large scale training sets. We train a full-rank baseline model and compare DLRT using the same starting weights on an Nvidia A-100 GPU. The used optimizer is SGD with momentum factor 0.1 and no aatta-augmentttion techniques are used. We compare the results on ResNet-50, VGG16, and AlexNet models, on the Cifarl0 10 and ImageNetlk datasets, and with respect to number of low low-parametric alternative baselines methods. For DLRT, the last layers of the networks have been adapted to match the corresponding classification tasks. Detailed results are reported in Table 2 where we show the test accuracy (reported as the difference with respect the full baseline) as well as compression ratios. With Cifar10, we archive a train compression of 77.5% with accuracy loss of just 1 1.89% for VGG16 and 84.2% train compression 1.79% accuracy loss for AlexNet. In the ImageNet benchmark, we achieve train compression rate of 14.2%, with an test accuracy loss of 0.5% in top-5 accuracy on ResNet-50 and 78.4% train compression with 2.19 top-5 accuracy loss on VGG16.
Acknowledgements. The work of S. Schotthöfer was funded by the Priority Programme SPP2298 "Theoretical Foundations of Deep Learning" by the Deutsche Forschungsgemeinschaft (DFG). The work of J. Kusch was funded by the Deutsche Forschungsgemeinschaff (DFG) 491976834. The work of Ceruti was supported by the SNSF research project "Fast algorithms from low-rank updates". grant number 200020- 178806. The work of F. Tudisco and E. Zangrando was funded by the MUR-PNRR project "LLowpparametri" machine learning". Special thanks to Prof. Martin Frank for the PhD mentorship of Steffen Schottöfer.
10

---

References
[1] P.-.. Absil, R. Mahony, and R. Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2009.
[2] A. Ashok, N. Rhinchart, F. Beainy, and K. M. Kitani. N2n learning: Network to network com- pression via policy gradient reinforcement learning. In International Conference on Learning Representations, 2018.
[3] D. Blalock, J. J. Gonzalez Ortiz, J. Frankle, and J. Guttag. What is the state of neural network pruning? Proceedings of machine learning and systems, 2:129-146, 2020.
[4] G. Ceruti, J. Kusch, and C. Lubich. rank- aank-adaptive robust integrator for dynamical low-rank approximation. BIT Numerical Mathematics, 2022.
[5] G. Ceruti and C. Lubich. Time integration of symmetric and anti-symmettrc low-rank matrices and Tucker tensors. BIT Numerical Mathematics, 60(3):591-611 2020.
[6] G. Ceruti and C. Lubich. An unconventional robust integrator for dynamical low-rank approxi- mation. BIT. Numerical Mathematics, 62(1):23-444 2022.
[7] G. Ceruti, C. Lubich, and D. Sulz. Rank-adaptive time integration of tree tensor networks. arXiv:2201. 10291, 2022.
[8] G. Ceruti, C. Lubich, and H. Walach. Time integration of tree tensor networks. SIAM Journal on Numerical Analysis, 59(1):289-313, 2021.
[9] Y. Cheng, F. X. Yu, R. S. Feris, S. Kumar, A. Choudhary, and S.-F. Chang. An exploration of parameter redundancy in deep networks with circulant projections. In Proceedings of the IEEE international conference on computer vision, pages 2857-2865, 2015.
[10] M. Courbariaux, I. Hubara, D. Soudry, R. El-Yaniv, and Y. Bengio. Binarized neural networks: Training deep neural networks with weights and activations constrained to +1 or -1. Advances in neural information processing systems, 2016.
[11] L. Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-144 2012.
[12] E. I.. Denton, W. 7aremba, J. Bruna, Y. LeCun, and R. Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. Advances in neural information processing systems, 27, 2014.
[13] I.. Dieci and Eirola. On smooth decompositions of matrices. SIAM Journal on Matrix Analysis and Applications, 20(3):800-8)) 1999.
[14] P. A. M. Dirac et al. The principles of quantum mechanics. Number 27. Oxford university press, 1981.
[15] R. Feng, K. Zheng, Y. Huang, D. Zhao, M. Jordan, and Z.-J. Zha. Rank diminishing in deep neural networks. arXiv:2206.0600 06072, 2022.
[16] F. Feppon and P. F. Lermusiaux. A geometric approach to dynamical model order reduction. SIAM Journal on Matrix Analysis and Applications, 39(1):510-533 2018
[17] J. Frankle and M. Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. International Conference on Learning Representations, 2018
[18] J. Frenkel. Wave mechanics, advanced general theory, volume 1. Oxford, 1934.
[19] B. Gao and P.-. Absil. A riemannian aank-adatiive method for low-rank matrix completion.
Computational Optimization and Applications, 81(1):67-90, 2022.
[20] Y. Guo, A. Yao, and Y. Chen. Dynamic network surgery for efficient dnns. Advances in neural
information processing systems, 29, 2016.
[21] E. Hairer, S. P. Nørsett, and G. Wanner. Solving ordinary differential equations. I. Nonstiff problems, volume 8 of Springer Series in Computational Mathematics. Springer-Verlag. Berlin, second edition, 1993.
[22] Y. He. G. Kang, X. Dong, Y. Fu, and Y. Yang. Soft filter pruning for accelerating deep convolutional neural networks, 2018.
[23] Y. He, J. Lin, Z. Liu, H. Wang, L.-J. Li, and Han. AMC: AutoMI. for model compression and acceleration on mobile devices. In Proceedings of the European conference on computer vision, pages 784-800, 2018.
11

---

[24] Y. He, X. Zhang, and J. Sun. Channel pruning for accelerating very deep neural networks. In IEEE International Conference on Computer Vision, pages 1389-1397, 2017.
[25] Y. He, X. Zhang, and J. Sun. Channel pruning for accelerating very deep neural networks, 2017.
[26] G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700-4705 2017.
[27] Z. Huang and N. Wang. Data-driven sparse structure selection for deep neural networks. In Proceedings of the European conference on computer vision (ECCV), pages 304-320, 2018.
[28] Y. Idelbayev and M. A. Carreira- Perpiiän.. Low-rank compression of neural nets: Learning the rank of each layer. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 8046-8056, 2020.
[29] Y. Toannou, D. Robertson, J. Shotton, R. Cipolla, and A. Criminisi. Training CNNs with low-rank filters for efficient image classification. In International Conference on Learning Representations, 2016.
[30] M. Jaderberg, A. Vedaldi, and A. Zisserman. Speeding up convolutional neural networks with low rank expansions. In Proceedings of the British Machine Vision Conference. BMVA Press,
2014.
[31] M. Khodak, N. Tenenholtz, L. Mackey, and N. Fusi. Initialization and regularization of factorized neural layers. In International Conference on Learning Representations, 2021.
[32] E. Kieri, C. Lubich, and H. Walach. Discretized dynamical low-rank approximation in the presence of small singular values. SIAM Journal on Numerical Analysis, 54(2):1020-1038 2016.
[33] H. Kim, M. U. K. Khan, and C.-M. Kyung. Efficient neural network compression. In Pro- ceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 12569-12577 2019.
[34] Y.-D. Kim, E. Park, S. Yoo, T. Choi, L. Yang, and D. Shin. Compression of deep convolutional neural networks for fast and low power mobile applications, 2015.
[35] O. Koch and C. Lubich. Dynamical low-rank approximation. SIAM Journal on Matrix Analysis and Applications, 29(2):434-454 2007.
[36] O. Koch and C. Lubich. Dynamical tensor approximation. SIAM Journal on Matrix Analysis and Applications, 31(5):2360-22) 2375, 2010.
[37] Kusch and P. Stammer. A robust collision source method for rank adaptive dynamical low-rank approximation in radiation therapy. arXiv:2111.07166 2021.
[38] V. Lebedev, Y. Ganin, M. Rakhuba, I. Oseledets, and V. Lempitsky. Speeding-up convolutional neural networks using fine-tuned cp-decomposition. In International Conference on Learning Representations, 2015.
[39] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE,
22724, 1998.
[40] C. Li and C. J. R. Shi. Constrained optimization based low-rank approximation of deep neural networks. In Proceedings of the European Conference on Computer Vision (ECCV), September 2018.
[41] J. Lin, Y. Rao, J. Lu, and J. Zhou. Runtime neural pruning. In I. Guyon, U. V. Luxburg, Bengio, H. Wallach. R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[42] S. Lin, R. Ji, C. Yan, B. Zhang, L. Cao, Q. Ye, F. Huang, and D. Doermann. Towards optimal structured CNN pruning via generative adversarial learning. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 2790-2799, 2019.
[43] H. Liu, K. Simonyan, O. Vinyals, C. Fernando, and K. Kavukcuoglu. Hierarchical representa- tions for efficient architecture search. In International Conference on Learning Representations, 2018.
[44] C. Lubich and Oseledets. A projector-spliting integrator for dynamical low-rank approxi- mation. BIT Numerical Mathematics, 54(1):171-188, 2014.
12

---

[45] C. Lubich. T. Rohwedder. R. Schneider, and B. Vandereycken. Dynamical approximation by hierarchical Tucker and tensor-train tensors. SIAM Journal on Matrix Analysis and Applications, 34(2):470-4)) 490000--4444000 2013.
[46] C. Lubich, B. Vandereycken, and H. Walach, Time integration of rank-constrained Tucker tensors. SIAM Journal on Numerical Analysis, 56(3):1273-12990 2018.
[47] J.-H. Luo, J. Wu, and W. Lin. Thinet: A filter level pruning method for deep neural network compression, 2017.
[48] C. Martin and M. W. Mahoney, Implicit self-regularizatiion in deep neural networks: Evidence from random matrix theory and implications for learning. Journal of Machine Learning Research, 22(165):
2021.
[49] Molchanov, S. Tyree, T. Karras, Aila, and J. Kautz. Pruning convolutional neural networks for resource efficient inference. In International Conference on Learning Representations, 2017.
[50] T. N. Sainath, B. Kingsbury, V. Sindhwani, E. Arisoy, and B. Ramabhadran. Low-rank matrix factorization for deep neural network training with high eigh-iimessionl output targets. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 6655-6659, 2013.
[51] D. Scieur, V. Roulet, F. Bach, and A. d' Aspremont. Integration methods and accelerated optimization algorithms. In Advances In Neural Information Processing Systems, 2017.
[52] Singh, V. Kumar Verma, P. Rai, and V. Namboodiri. Play and prune: Adaptive filter pruning for deep model compression. In Proceedings of the Twenty-Eighe International Joint Conference on Artificial Intelligence, IJCAI-19, pages 3460-3460 0300-366. International Joint Conferences on Artificial Intelligence Organization, 7 2019.
[53] S. P. Singh, G. Bachmann, and T. Hofmann. Analytic insights into structure and rank of neural network Hessian maps. In Advances in Neural Information Processing Systems, volume 34, 2021.
[54] N. S. Sohoni, C. R. Aberger, M. Leszezynski, J. Zhang, and C. Ré. Low-memory neural network training: A technical report. 19X4 2019,
[55] A. Tjandra, S. Sakti, and S. Nakamura. Compressing recurrent neural network with tensor train. In 2017 International Joint Conference on Neural Networks (IJCNN, pages 4451 4458. IEEE, 2017.
[56] M. Udell and A. Townsend. Why are big data matrices approximately low rank? SIAM Journal on Mathematics of Data Science, 1(1):144-160, 2019.
[57] H. Wang, S. Agarwal, and D. Papailiopoolls. Pufferfish: communication--effiiene models no extra cost. Proceedings of Machine Learning and Systems, 3:365-3888 2021.
[58] W. Wen, C. Wu, Y. Wang, Y. Chen, and H. Li. Learning structured sparsity in deep neural networks. Advances in neural information processing systems, 29, 2016.
[59] W. Wen, C. Xu, C. Wu, Y. Wang, Y. Chen, and H. Li. Coordinating filters for faster deep neural networks. In Proceedings of the IEEE International Conference on Computer Vision, pages 658-666, 2017.
[60] J. Wu, C. Leng, Y. Wang, Q. Hu, and J. Cheng. Quantized convolutional neural networks for mobile devices. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 4820-4828, 2016
[61] H. Yang, M. Tang, W. Wen, F. Yan, D. Hu, Ai, Li, and Y. Chen. Learning low-rank deep neural networks via singular vector orthogonality regularization and singular value sparsification. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops, pages 678-66788677 679, 2020.
[62] J. Ye, X. Lu, Z. Lin, and J. Z. Wang. Rethinking the smaller- noreeer-ooo-llssss lesm-eess-iffommmatv assumption in channel pruning of convolution layers. International Conference on Learning Representations, 2018.
13


Reviews:
[{"review_id": "wdgQipyFOtJ", "reviewer": "Reviewer_j9XY", "summary": "This paper studies a new training strategy for finding a low-rank sub-network by solving matrix differential equations and tools of matrix decompositions. The idea is novel and the implementation is convincing. However, if this method can be applied to much large scale and frequently used networks instead of current test settings, this work can be definitely more compelling.", "questions": "1. Eq 6, what is `min!' ?\n2. The description to Fig. 2 is not clear. The timings for what? A gradient descent step, a feed forward pass for a batch of samples?", "limitations": "The main limitations are two:\n1. Lack theorems or enough theoretical analysis to rigorously support the soundness of the algorithm. Readers may not be familiar with the classical results in related backgrounds. Some very important theory results, like convergence and error analysis, should be clearly stated.\n\n2. I do not understand why the authors do not apply this method in large networks like ResNet50 on ImageNet.\n\nApart from these two points, I think this is good work. If the authors can successfully address my concerns on these two issues, I will raise my rating.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n### Originality\nThe idea of using matrix differential equations to capture the underlying low-rank weights is novel and attractive. Researchers in many domains have wondered about efficient methods to train the network weights under the factorization of SVDs. So this work may have a broad audience in the machine learning domain. The formulation and implementation of this method also seem to have a rather solid background in numerical analysis and pdes.\n\n### Quality\nThe basic idea is good, however, the theoretical analysis is a bit limited, and the empirical study is too narrow. \n1. The authors should give clear theorems about the convergence and convergence analysis of the proposed algorithm, without which I cannot fully judge the soundness of this work. I am eager to such results in the response of the authors.\n2. The authors should also give theorems on what $S_k$ learns during the training, and what is the geometry or intuitive meaning of the final decomposition $USV$ since $S_k$ is not a diagonal matrix,  and $USV$ is not an SVD.\n3. Is there any theoretical results that support the universal approximation ability of networks decomposed by this algorithm?\n4. Is there any theory analysis on the relationship between hyper-parameters of this method and the test accuracy or approximation error?\n5. I am also wondering why the author did not test this method in ResNet, Transformer, or deep generative networks? This seems no barrier to doing so.\n\n### Clarity\nThe clarity needs many improvements. The authors should summarize the major conclusions in the context into theorems, which can significantly improve the readability and soundness of this work. The background knowledge of this method is also missed, especially the minimum preliminary knowledge for readers to understand the `DLRA' and `KLS'.\n\n### Siginificance\nThe paper lacks clear theorems to support it theoretical soundness and significance. The numerical results are also a bit narrow for practical usage. There are also some previous methods[3] for leveraging SVD in the training of deep networks, the authors may consider comparing the proposed method with them.\n\n### My suggestions:\n1. In Line 105-107, I strongly recommend the authors cite some papers on this topic to enhance the argument. The most relevant two papers could be [1][2]. [1] gives both theoretical and empirical evidence of low rank weight matrix in over-parametric deep networks with tools from recent advances in random matrix theory. Using the theory of dynamic systems and Lyapunov exponents, [2] further describe how chain rules, i.e., large amounts of matrix multiplications can lead to low-rank results and network gradient, which exactly support the motivation here. Besides, [3],[4], and [5] also give support for low-rank networks from different aspects.\n2. In line 122-123, I think it would be better to say `$W_k(\\tau)\\in\\mathcal{M}_{r_k}$' for some $\\tau>0$. Most networks are initialized with Gaussians, thus initially they have full rank, but there is evidence that training will eventually converge to some low-rank status.\n\n[1]Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learning. Charles H. Martin Michael W. Mahoney\n[2] Rank Diminishing in Deep Neural Networks.  Ruili Feng, Kecheng Zheng, Yukun Huang, Deli Zhao, Michael Jordan, Zheng-Jun Zha\n[3] Learning Low-rank Deep Neural Networks via Singular Vector Orthogonality Regularization and Singular Value Sparsification. Huanrui Yang, Minxue Tang, Wei Wen, Feng Yan, Daniel Hu, Ang Li, Hai Li\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": "afE4TVbdn8H", "reviewer": "Reviewer_mpYM", "summary": "This paper presents a dynamic adaptive low-rank training algorithm for deep neural networks that is able to find efficient low-rank subnetworks during training time. It achieves improvement in both memory and computation efficiency. Experimental results on MNIST show that the proposed approach outperforms some other pruning and low-rank methods.", "questions": "No other specific questions. Please refer to weaknesses above.", "limitations": "Yes. The authors have addressed the limitations and potential negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* I really appreciate this work for exploring low-rank training. I think the overall novelty is above the line.\n* This paper has detailed equation derivation and algorithms.\n* This paper is well organized with sufficient materials to support the idea, especially the sections of computational cost and limitations analysis.\n\nWeaknesses\n* Is there a typo at line 298 (LNRR)?\n* Why only evaluate on MNIST? How about the performance on more complicated networks and datasets?\n* Is there any other related works that research on low-rank manifold and can be compared with in this paper? It would be better if more such comparison is included.", "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": "S_YqbUQuNxp", "reviewer": "Reviewer_kDdv", "summary": "This paper presents a Dynamic Low Rank Training Scheme (DLRT) algorithm, which aims at attaining low-rank networks during training directly for faster computation efficiency and lower memory footprint. Low-rank training is formulated via gradient workflow, then via incorporating the dynamics of the model weights, the proposed DLRT algorithms achieve adjusting the layer ranks dynamically (via explicit optimization). The complexity and efficiency of the DLRT algorithms are discussed. Empirical simulation is also provided to justify the effectiveness and efficiency of the proposed DLRT algorithm.", "questions": "Please refer to the \"Weaknesses\" part for answering my major questions. In summary:\n\n1. Is DLRT designed for efficient training or efficient inference, or both?\n2. How does DLRT compare against DeepCompression and EarlyBird Ticket?\n3. Why can't DLRT outperform LRNN? If not, why should people use DLRT in practice?\n4. DLRT scale to larger networks, e.g., ResNet-50, EfficientNet, ViT, BERT on larger tasks, e.g., ImageNet, WikiText, GLUE benchmark?", "limitations": "As discussed thoroughly in the section \"Strengths And Weaknesses\" and \"Questions\", the paper is not a theory paper. But in practice, the proposed DLRT method has a few flaws, e.g., computation efficiency, and training-time memory cost is not clear. The empirical results of this paper are weak, the experiments are only conducted on one toy dataset (even though, DLRT is off compared to at least one of the baseline methods).", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nOverall the proposed idea makes sense. The DLRT algorithm is a viable algorithm for attaining low-rank neural networks (presumably for faster inference after training). The simulated experiments support the major claims to some extent.\n\nWeaknesses:\nMy major concern is that it is not clear if the proposed method can serve as a useful method in practice. The paper is not a theory paper and comes with no theoretical analysis, thus I would justify it mainly from the application perspective. My detailed concerns are summarized below:\n1. It is not clear if the DLRT algorithm is designed for faster training or faster inference. For faster training, given the evidence in the current draft, I am not convinced that DLRT is even faster than normal training, e.g., DLRT requires conducting extra computation (in lines 8-21 of Algorithm 1, which requires conducting a full SVD per iteration). Not to mention the other baselines, e.g., [1-2], which claim much faster end-to-end running time compared to vanilla training.\n2. Memory saving is also claimed in the paper, but I do not believe the low-rank-based method can save memory costs largely during training. Low-rank networks have fewer (or much fewer number of parameters), but the bottleneck of memory cost comes from the layer activations, not model weights [3]. And low-rank neural networks can not reduce the activation size (during training). During inference, low-rank networks can efficiently reduce the memory cost as no activations are required to be saved. The authors should make the claims more clear.\n3. The paper does not compare against powerful enough baselines outside the low-rank domain. For instance, quantization+sparsification [5] and learned structured pruning [6] (as low-rank methods are versions of structured pruning after all). \n4. The experimental results are too weak, DLRT generates either larger networks than LRNN or with worse accuracy. Then why people should use DLRT in practice given that LRNN method can also adaptively adjust ranks?\n5. It has been shown in [2], that the low-rank method won't scale to large tasks, e.g., ImageNet without the proposed warm-up and hybrid network tricks. How does DLRT perform on the ImageNet dataset or even BERT language modeling tasks?\n6. It is claimed that DLRT automatically selects ranks, however, it seems the final ranks of the layer are controlled by another hyper-parameter \\tau, which is still required to be tuned in practice.\n\n[1] https://arxiv.org/abs/2105.01029  \n[2] https://arxiv.org/abs/2103.03936  \n[3] https://arxiv.org/abs/1904.10631  \n[4] https://ieeexplore.ieee.org/document/9157223  \n[5] https://arxiv.org/abs/1510.00149  \n[6] https://openreview.net/forum?id=BJxsrgStvr  ", "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