An Efficient Training Algorithm for Models with Block-wise Sparsity
Authors: Ding Zhu
Zhiqun Zuo
Mohammad Mahdi Khalili
Venue: Accepted by TMLR ()

Abstract: Large-scale machine learning (ML) models are increasingly being used in critical domains like education, lending, recruitment, healthcare, criminal justice, etc. However, the training, deployment, and utilization of these models demand substantial computational resources. To decrease computation and memory costs, machine learning models with sparse weight matrices are widely used in the literature. Among sparse models, those with special sparse structures (e.g., models with block-wise sparse weight matrices) fit better with the hardware accelerators and can decrease the memory and computation costs during the inference.  Unfortunately, while there are several efficient training methods, none of them are designed to train a block-wise sparse model efficiently. As a result, the current methods for training block-wise sparse models start with full and dense models leading to inefficient training.  In this work, we focus on training models with \textit{block-wise sparse matrices} and propose an efficient training algorithm to decrease both computation and memory costs during training and inference.  
In addition, we will show that our proposed method enables us to efficiently find the right block size for the sparsity pattern during the training process. Our extensive empirical and theoretical analyses show that our algorithms can decrease the computation and memory costs significantly without a performance drop compared to baselines.

Published in Transactions on Machine Learning Research (03/2025)
An Efficient Training Algorithm for Models with Block-wise Sparsity
Ding Zhu
chu.37230oss
Deportment of Computer Science and Engineering The Ohio State University
Zhiqun Zuo
zuo. 167 edu
Deportment Computer Science and Engineering The Ohio State University
Mohammad Mahdi Khalili
khaliti, 1 17@osu.ccmm edu
Department of Computer Science and Engineering The Ohio State University
Reviewed on OpenReview: https: // openreview. net/ forum? id- nay3Kvu6BD
Abstract
Large-scale machine learning (ML) models increasingly being used in critical domains like education, lending, recruitment, healthcare, criminal justice, etc. However, the training, deployment, and utilization of these models demand substantial computational resources. To decrease computation and memory costs, machine learning models with sparse weight matrices are widely used the literature. Among sparse models, those with special sparse structures (c.g., models with block-wise sparse weight matrices) fit better with the hardware accelerators and can decrease the memory and computation costs during the inference. Unfortunately, while there several efficient training methods, none of them designed to train a block-wise sparse model efficiently. As result, the current methods for training block-wise sparse models start with full and dense models leading to inefficient training. In this work, we focus on training models with block-wise sparse matrices and propose an officient training algorithm to decrease both computation and memory costs during training and inference. In addition, we will show that our proposed method enables us efficiently find the right block size for the sparsity pattern during the training process. Our extensive empirical and theoretical analyses show that our algorithms decrease the computation and memory costs significantly without performance drop compared to baselines H
1 Introduction
Deep learning models have achieved remarkable success across varions domains, but training these models on resource-constrainee devices remains challenging due to their computational and memory requirements. To decrease memory and computational costs, sparse machine learning models have been widely used literature. Sparse networks are mainly categorized into two groups: fnn-grained sparse networks and coarse- grained sparse networks (see Figure which provides example of fine-grained sparse weight matrix and two examples of coarse-grained sparse weight matrices). In fine-grained sparse nel works, the weight matrices are sparse but they do not have any special structure. This type of sparsity generally improves the storage cost but does not improve the inference time significantly. This is because the random distribution in fine-graine grained sparse weight matrices does not fit with the hardware accelerators, and they can speed up
IA preliminary version of this work presented the NeurIPS Workshop Machine Learning and Compression Zhu 2024

---

Published in Transactions on Machine Learning Research (03/2025)
Fine-Grained
Coarsp-Graieed binck-wwe
Coarse Grainod
Block-via
Figure 1: Examples for fine-grained and coarso- coarso-grained sparse matrices. White entries represent zero value.
the inference time only if the sparsity ratio is higher than 95% Wang al. 2018 Wen et al. 2016). On the other hand, coarso-grained sparse matrices are better alternatives to speed up inference (Parashar et al. 2017
Han et al.
2017 2016a).
To train coarse-grained (structured) sparse weight matrices, it is common to use iterative pruning (Tan & Yu ct al. 2023 or group lasso techniques (Behnke & Hcafield 2021 Rao et al., 2015 Ida et al. 2019 Lerative pruming works as follows. First, sparsity pattern delined (e.g. 2:4 sparsity Mishra
Motani
2020:
jtt al. 2021 or channel-wise sparsity (Liu al.) (017)). Based on this pattern, the weight parameters are divided into separate groups. A deep model is trained and then by looking at weight matrices, we prune some of the groups that not impacting the performance of the model. Then, re-train (fine-tune)
the remaining weights and again prune those groups that have the smallest impact on the performance. This procedure is repeated until we achieve the desired sparse network. Group LASSO technique adds a regularizer to the objective function which ensures that weights in several groups go to zero during the training. In particular, for Group LASSO, first, we divide the parameters in each weight matrix into several groups (each block can be considered as group) and add regularizer for each group to the objective function. As result, the weights in certain groups with minimal impact on accuracy will eventually go to zero during training. Nevertheless, iterative pruning and group lasso techniques mainly focus on reducing memory and computation costs at the time of inference. However, they can be very costly during the training as the training process starts with the full network (i.e., all the weights are non-zero at the beginning) and the gradient needs to be calculated with respect to all the model paramcters.
In this paper, we propose a technique that enables us to train block-wise sparse matrices that improve both computation and memory costs during training and inference. We leverage the Kronecker product dccomposition to propose new matrix factorization technique suitable for block-wise sparse matricos. Our contributions in this work can be summarized as follows,
To the best of our knowledge, this the first work that focuses on efficient training for block-wise sparse models. This work is also the first work that makes connection between block-wise sparse matrices and the Kronecker product decomposition for efficient training. While there have been
several algorithms for training block-wise sparse models (Cai et al. 2022 Liu et al. 2021a Li et al. 2017a Oyedotun et al. 2020a). they are not efficient during training.
We theoretically demonstrate every block-wind wise sparse matrix can be represented using our proposed dccomposition resulting in no significant performance drop.
Through extensive thcoretical analyses, show that our proposed approach decreases the number of flops and training parameters during the training compared to existing methods for training block-wise sparse models.
Through extensive empirical study, we show that in some cases, our proposed method can reduce the number of training parameters and training FLOPs by 97% with minimal accuracy drop.
We also show that our proposed algorithm is able to find the optimal block size for block-wise sparse matrices efficiently in one round of training.
We present the The remainder of the paper organized as follows. We review related work in Section 2
preliminaries in Section followed by problem formulation in Section We discuss how our algorithm
2

---

Published in Transactions on Machine Learning Research (03/2025)
be used for optimal pattern selection in Section 5 We present numerical results in Section 6 and conclude in Section 7
2 Related Work
Pruming is an effective technique for reducing model parameters and has seen tremendous progress in recent Tanaka et al., 2020b; Han et al. 2016b). Pruning generally can be divided into structured 2017a 7a and unstructured pruning (Dong et al.] 2017 Sanh let al. 2020 Unstructured pruning finds fine-grained sparse matrices by setting the unimportant weights to zero (See Figure D. While unstructured pruning can decrease the number of model parameters at the inference time, it generally does not improve the inference time (Wang et al., 2018). Structured pruning, the other hand, trains coarse-grained sparse matrices leading to a decrease in the memory cost and inference time. It is important to note that pruning methods generally start with a dense full network and prune the network in one-shot or in several iterations and retrain the network to improve the performance. As a result, memory and computation costs during the training can be expensive. Recently, several pruning methods have been proposed to decrease the training cost as well. These mothods try to prune the network right after initialization and train the sparse network (Lee et al., 2019a). The current Pruming After Initialization (PAI) methods are able to perform unstructured pruning, and they need large memory at the time of initialization which makes it impossible to do training on small devices. On the other hand, our proposed method is able to decrease the nunber of parameters and flops from the beginning of the initialization and train block-wise sparse mat.rices to decrease inference memory and time.
years Reed 1993:
pruning Cai el al. 2022 Liu et al. 2021a) la Li et al.
Rogularization is another method for training network with sparse weight matrices. It is common to add 11 or 10 regularizer the loss function (Ma et al., 2019: Louizos et al.] 2017) to find unstructured sparse weight matrices. Group LASSO, an extension of the LASSO method, is method that imposes regularizer to pre-defined groups of model parameters leading to block-wise or group wise sparsity structures in deep neural networks (Liu et al., 2015 Scardapanc et al. 2017 Behnke & Heaffeld 2021). To improve the performance of group LASSO, recently a new variation of group LASSO called elastic group LASSO (Oyedotun et al. 2020a has been proposed. It is worth mentioning that group LASSO is only able to remove the computation and memory cost during inference. The training cost associated with group LASSO is relatively high as this method starts the training with a dense network.
Matrix/tensee factorization (Yu et al. 2017 Wu & Feng, 2022 is compression method that is able to reduce the training and inference cost by reducing the number of training parameters from the beginning of the training process. While matrix/ /terixr factorization has been widely used for model compression (Hsu
et al. 2022 Hameed et al.) 2022 Edalati et al. 2021 Yin et al. 2022). these methods are not able to find block- wisc sparse matrices for deep models.
Knowledge Distillation (KD) methods train a smaller student network based on the guidance of a bigger teacher network (Hinton et al. 2015 Li et al., 2017b). Knowledge distillation methods try to make sure that the student network mimics the behavior of teacher network by comparing outputs (Cho & Hariharan
2019 Furlanello et al.] 2018 Mirzadeh et al. 2020 Zhang el. al. 2018) or intermediate features (Heo et al.
2019a by Huang & Wang 2017 Kim et al.) 2018 Park et al.) 2019 Tian et al. 2019) The training process
under KD can be computationally heavy as we need to train a teacher model first and then use the teacher model to train a student model (Yim et al. 2017).
Block-wisc Sparsity is a spocial type of structured sparsity. Zero clements of block-wise sparse matrix can be stored contiguously in memory redueing irregular memory access and taking advantage of array-data- path in modern processors. D'Allerto et all (2024) show that block-wise sparse models can run efficiently on specific devices. In the literature, block-wise sparsity has been implemented by using LASSO regulation
[Narang et al. 2017). group regulation (Wen et al. 2016 Vooturi et al. 2018 and filtering Anwar et al. 2015).
Sparse Training aims to docrease number of parameters that are being updated during gradient descent. Sparse training methods generally are categorized into two groups: static sparse training and dynamic sparse
training. Static sparse training (Dao al. 2022 Lee et. al. 2019b Yuan al. 2021 identifies important
3

---

Published in Transactions on Machine Learning Research (03/2025)
parameters and finds the sparse mask at beginning of training based heuristic metric. As a result, only a subset of parameters are updated during the gradient descent. For example, Grasp method (Wang) et al. 2020) uses gradient flow, SynFlow method (Tanaka et al. 2020a) uses synaptic strengths, and FISH mask [Sung et al. 2021 uses Fisher information to find the sparse mask. Dynamic sparse training, on the other hand, allows to modify the sparsity pattern during training to reduce the training footprint. For example, Mocanu et al. (2018) use the weight magnitude to prune the connection between neurons during the training, and RigL (Evci et al., (2200) uses both weight magnitude and gradient magnitude to identify important weights in each epoch and update them. However, these efficient training methods are working with unstructured sparse mask and may not lead to training acceleration. Fang et al. (2024) consider N:M sparsity pattern for hardware acceleration and implement an efficient training for this sparsity pattern. Jiang et al. (2024) also propose an efficient training scheme by shullling rows or column based on the Jaccard similarity. While these approaches can reduce the number of training parameters with structured sparsity, they are designed to find bise sparse models.
In this paper, our goal is to propose a new method for training block-wise sparse model that is efficient during both training and inference. The proposed method can decrease the number of training parameters and flops significantly without degrading the model performance compared to the basclines.
3 Preliminary
Group LASSO: LASSO is a method for learning spanse models by adding penalty term to the cost function, which is proportional to the I norm of the model's coefficients. This encourages the model to be sparse and sets some of the model parameters to be zero. Group LASSO is an extension of LASSO which divides the model parameters into several groups and imposes a regularizer on each group. This encourages the coefficient several groups to go to zero during the training. Group LASSO can be used to train block-wise sparse matrices (see Figure 2 by defining each block as a group. In particular, consider neural network with L layers, with W being the weight matrices of the whole network and Will) being the weight matrix in layer I. Also, let w!ll denotes the block/group g layer I. Then, the group L.ASSO solves the following optimization problem,
Wx arg min J J(Wll, W
wll, D) + Ile
9
where WA is the optimized weight matrices with hyperparameter X, J the loss function, and D is the training dataset, and ||-I|r denotes the Frobenius norm.
Kronecker Product Decomposition: The Kronecker product, denoted by Ø is a mathematical opera- tion that combines two matrices to form larger matrix. Given two matrices A and B, if A is of size mi x n and B is of size my X n22, then the Kronecker product of A and B results in a matrix of size my x 12 Let W be an m by n matrix, where m = m, n = R2 we can decompose this matrix using the Kronecker product decomposition as follows [Van Loan 2000).
W = Σ A. R W.
(2)
where A, is an my by n1 matrix Bg is an my by n2 matrix, and R = decomposition, Wr (where & E Rnxx)) also can be calculated as follows, Wa vec(_> B, where ø is n2 by n, matrix and can be obtained by re-arranging the elements of vector (Van Loan 2000
m2 Given this
It turns out that the low-rank approximation is a special case of decomposition equation 2 More precisely, if we set my = 1 and n1 1, Equation 2 is equivalent to the low-rank approximation. Let's assume that we want to approximate matrix W by r terms of equation In this case, W v W, = Ei A 0 B,, where W, is expressed by r(min + m2R2) parameters.
It worth mentioning that similar to the low-rank approximation, Kronecker product decomposition can be used for compressing deep models (Jagtap et al. 2022: Hameed et al. 2022). However, to the best of our
4

---

Published in Transactions on Machine Learning Research (03/2025)
S
A
B
Figure Illustration of why equation leads to block-wiss sparsity when stll is sparse. White entries represent zero value.
knowledge, there is no censor/matrin factorization for generating and training block-wise sparse matrices. In the next section, we will explain how we can take advantage of Kronecker product decomposition to train efficiently block-wise sparse matrices and reduce the memory footprint during the training process.
4 Problem Statement and Proposed Solution
As we discussed in Section 2 there are several methods including iterative pruning or group LASSO to train block-wisc sparse weight matricos. However, these methods have to start with a full uncompressod model and sparsify the weight matrices gradually during the training. As a result, these methods do not decrease computation and memory during training. However, in this part, we propose a new matrix decomposition method leveraging the Kronecker product decomposition algorithm to train block-wise sparse matrices with fewer training parameters and fewer flops for forward and backward propagation compared to the group LASSO and structured pruning approaches during training. During the training period, we utilize decom- posed matrices, which reduces the number of training paramcters and flops. This allows the training process to be deployed on resource constrained devices. During inference, our algorithm directly uses block-wise sparse matrices without any decomposition to improve efficiency.
To demonstrate how learn a structured sparse weight matrix efficiently, assume that W is the weight matrix associated with layer I (if we are working with convolutional neural network, Will can be tensor.) Instead of learning W:ll,, we propose to estimate it by
w!l = Σ s o B",
(3)
called rank, ② is element- wise product, sill and A." are mi by nı matrices and B is an m2 by n2 matrices. Then, train ,(9, (A4", D()) directly during the training process (we calculate the gradient of the loss function with respect to these parameters). By imposing an 4 regularizer on 8!'l, we can make sure that s(4 is sparse in the following problem,
where ri is a
min B keraas
7 B. lsmuSLL)) D) + A ||
(4)
[SD),
where A is a constant and controls the sparsity rate. If s!ll is an unstructured sparse matrix, w:"l A(") & Bill will be block-wise sparse matrix (sec Figure 2 After training, depending
application, we can use w:!" during the inference time or we can use St0 inference time. It is worth mentioning that the decomposition in equation 3 provides several degrees of freedom and hyper-pane paper-prrametess (i.., m1, M2, 72, r1). Note that the block size in w/") is determined by the size of matrix Bi!l (i.e., n2)). To choose the right hyper-parameters, is common to choose to try different sets of syper-parameters and pick the one with desirable performance and efficiency. If our only goal is to minimize the number of parameters using equation 3 then the by an optimization problem. In particular, we set T 1 and solve the following integer programming.
,t.(AA))) (A!", "al",,"" directly during the
can be determined
min 2m m2n2, s.t., m2 m. R2 71
(5)
my R
5

---

Published in Transactions on Machine Learning Research (03/2025)
where the objective function is equal to the number of parameters in equation 3 The above optimization problem is nonconvex. We can solve it by setting m2 m/m1 and n2 n//1- The above optimization problem reduces to minmy,n, 2m + minii is m111 = v0.5 mn if v0.5 mn is integer (if v0.5 mn is not an integer, we can use integer programming tools like branch and bound to solve the problem). To clarify, we provide an example.
_.nm mn. By the first order condition, the minimizer of 2m + mm
Example 1. Let m = -2 and n = =2. In this case, for the minimum possible space complecity under faclorization equation 3 we nead to have min1 = 32. For ezample, we can sel m. = 4, 01 = 8, m2 = n2 = 32. In this case, the total rummeer of parameters would be 128. The original matriz W has 2048 training parameters. Therefore, at the time of training, using equation 3 we need to train 128 variables while the group LASSO technique needs to train 2048 variables. At the inference time, can use directly sparse matrir (s @ A and B to make an inference. We can also use block-wise sparse matrix w!lll to make an inference.
The above example shows the proposed factorization in equation 3 can reduce the training parameters significantly. We can also optimize Tı, 71, R1, mig T2 for maximizing accuracy and performance. We will discuss how we can choose r2, ma, n1, m,, M2, n2, and the right block size for better accuracy in Section
In the remaining part of this section, we explain how any block wise sparse matrix can be represented by equation 3 and why the proposed factorization can decrease the number of flops during forward and backward propagation compared to group LASSO Struccturd Pruning.
Proposition 1. Let Willl be block-wise sparse matrix trained by group LASSO iterative pruning. If the blocks have the same size, then there erists ft and Si)) and (A!". B such that Will Σ D
(SUI o -
A!") )
Intuitively, the above proposition implies that if the hyper-parameters rt, nI, R2, mi, m2 are chosen correctly, then training matrices sit), (A"",,,"),, ,, should have the same performance of a model trained by the group LASSO or pruning technique.
Proof. Here, we will prove that each block-wise sparse matrix can be decomposed by the decomposition in equation
We assume the biock-wise sparse matrix Will has size of m by n, the mumber of groups is m. x n1 and the block size is m2 by n2 where my x m2 = m and nı x m2 = n. We want to find $11, A!" Bl!1 such that the following holds,
W = Ei o A!") 8 B!"
(6)
where Will is given.
Assume that T groups among m1m1 groups are non-zero in matrix Will and the index of the groups are 4, 41,22,..,,7 lr. We set r= T and we generate a series of Al and Bl for i= 1,.,, to make sure equation 0 holds. In particular, we set L matrix to be equal to the block of t; in matrix W111, and A!" is matrix that only has one entry equal to 1 which is associated with block &; and the other entries are zeros. We also can set $00) to be a binary matrix. Each entry in S1 corresponds to a block in Will If block in WIll is non-zero (resp. zero), then the entry associated with that block in Sll would be 1 (resp. 0). By this construction, $11, A!l Bi!l satisfy equation 6
Proposition [Number of Flops for Forword and Backward Passes in A Linear Model] Consider mul- tivariate linear regression model h(x) Wx, where W is m by matria, and E Rn is the input Jeature veclor. Lei D = {(r,,,1))ū vy)li = 1,.... I.....NN NN be the training datusel, and J(W; =)=30 = be the objective function. If we estimate W by Ei O Ad) 8 B, and write J(S, (A,, B)) = 11 @ A;) 60 BoJa, - y) 12, then,
[W,, - 1
6

---

Published in Transactions on Machine Learning Research (03/2025)
Forward pass: Number of flops for calculating DW is O(2(n + 1)mN). On the other hand, J(S (A,, B)) can be calculated by O (2Nrmin1 (m + n2) Nr(m + 2m2m1 + 3Nm) flops.
Backward pass: Number of flops for calculating gradient of J(W: D) with respect to W is (2n + 1)). On the other hand, 03... and B. can be calculated by O(2Nn1ma(n2 + m1) 10nnnmm 1 +mnn) flops and O(2Nmann(m + +n + + Nngm1)) flops, re- spectively. In addition, B.)).,A, needs O (N + Nr(4m11271 m2 + 2m2n1122)) flops.
DA,
0B,
85
The above proposition implies forward and backward passes for J(S, (A,, B.) D) can be more efficient compared to calculating J(W, D) right values for parameters m1, R1, m2, n2. r are chosen. This is be- cause the forward and backward passes for J(W, D) needs (mmnN) while mn does not appear in the time complexity of forward and backward passes of J(S, (A,, Be) Tn addition to flops for calculating the gradient, in each epoch of gradient descent for J ((W,)) we need to update mn parameters which needs (mm) flops. On the other hand, in cach epoch of gradient descent for [(S, B,), ",,,), D), after caleulating the gradient, we update r[m1n1 + m2n22) parameters which need O(r(m)n1 + m2?2)) flops. This is another reason that the training process can be more efficient under decompasition equation 3
We want to emphasize that our experimental results also show that number flops during the training can be significantly decreased by decomposition equation 3 (e.g., Table | shows 87% reduction in number flops without any accuracy drop, and Table 3 shows 97% reduction performance drop compared to the dense model.) Next, we exlend the results of Proposition 2 to a network with two layers. We will also perform analysis for larger network in Section [6]
number flops with 1 percentage point
Proposition 3. Consider two-layer mullivariate regression model 1((x)) (W where W E Rm xm the weight matrie of the first layer, and W(2] E Rm xm!1)) is the weight matriz of the second layer. I E Rmll is the impul feature vector. Let D = ((zr,u;)l = ......N) be the training dataset, and yj 1i be the objective function. Assume that we estimate Will by EE((S @ A!" ) I." and W by (stel @ A!²))e @ r=!al In the first layer, S and A!"l E Rm xm PI [1] where m, 11 m2 = ml',, m m2 ml2) In the second layer, 512] and [2 E Rm 19 xm!")
J(WII, =)
B. 1 Rm xmm",
m
B
2) Rm xm!") where mi my ml Then,
[3] [3]
Forward pass:
Number of flops for colculating JWWPI, wIEI; D) Number of flops with the decomposition in equation 3 is
is
O (2N m [2] + m [ m + ml)))).
O (1 + rl + Nm + 3/ where Ci = =1=2Nwm 2l [2] + 2l Nm, (2) (m + m Nm,
[1]
C2 = ml 2 13
[3] (ml + m
Backward pass: Number of flops for calculating gradients with respect to W and W(2.
is O (2(2m/()m + 4m
+ mmm))))))) m) Number of flops with the decomposition in equation
is O (m + ml + C3 + Ca), where C3 = Nm) (4m mm²)) ) + 2r Nm m Ca [3] (4ml2) - m )+ + 21 Nm!"
The above proposition implies that the results of Proposition 2 can be extended to non-linear models. In particular, Proposition 3 implies that if ranks r!ll and ,!8 are small enough and right dimensions for .4 B,"i B.a are selected, then the decomposition in equation 3 can make the forward and backward passes more efficient in a two-layer neural network. This is because mill mnl2 and ml m333 do not appear in the time complexity after the decomposition.
While we solve the proposed optimization problem f during training, at the inference time, we use sparse matrix Wi = Σ ($!)) @ ) @ B.". As a result, during inference, the memory and flops reduction for the proposed method compared to the the dense model is approximately proportional to the sparsity rate (note that actual reduction depends on the implementation of sparse matrices in pytorch, tensorflow, or other deep learning librarics, and sparsity rate is only a proxy for reduction in memory and flops during inference.). During training, the memory required for model parameters is proportional to the number of training parameters in optimization problem
7

---

Published in Transactions on Machine Learning Research (03/2025)
5 Pattern Selection for Performance Improvement
As we discussed in the previous section, the block size for training block-wise sparse matrices a hyper-parameter, and selecting the right block size depends on our objective. For instance, by solv- ing equation D we can find the block size that minimizes the number of training parameters. In this section, we explain how we can find the right block size for maximizing accuracy with only one round of training. We will argue that under factorization stated in equation 3 we can ef- ficiently find the right block size compared to group LASSO and iterative pruning. First, we want to emphasize the number of possible block sizes for training block-wise sparse matrices is nite. For example, if the size of matrix W is 10 by 10, then there are 14 possible block sizes: by 10, 1 by 5, by 2, 2 by 10, by 5, 2 by 2, 2 by 1, by 10, 5 by 5, by 2, 5 by 10, 10 by 1, 10 by 2, 10 by If we want to consider a block size with an exponent of 2, then 2 by 2 will be the only option. Let P= [P,, P2, ..., Px) be set of finite sparsity patterns that we are interested in Each Pa. determines the block size for all the layers. If we want to use iterative pruning or group LASSO technique to find the best pattern, we have to run the training procodure for each Ps and pick the one that achieves the highest accuracy. On the other, our method can select a pattern leading to the best accuracy in one round of training while keeping the number of training parameters less than that of group LASSO or iterative pruning. Tn particular, we estimate Wlll(0k) = - @ A! ( & Blll(()) where 511,,0)) A00,000 B!ll.(kk, s 1 follows pattern Ps. Then, for the pattern selection, we solve the following optimization problem,
K min J(SS Alll(()) BB!1.00 lisnsss D) A
K Σ
K
L
Σ
A2
|s01.00 Ih:
(7)
==
where [S01,00) A00.000 (0 I lig are the training parameters, and a and x2 are regularizer parameters. The above optimization problem can be solved using gradient descent. The second term in equation 7 imposes a separate regularizer on each pattern. Since the square root is not differentiable at zero, this type of regularizer encourages all the weight associated with a pattern to go to zero if the pattern does not provide high performance (similar to the group LASSO technique). In the training process, we would gradually increase Å until only one group of parameters remains non-zero. The third term encourages the trained (((((k) to be sparse. If matrix (il).(k) is sparse, then the weight matrices in later I are block-wise sparse.
The benefit of using optimization problem equation 7 for pattern selection is that the number of training parameters signíficantly reduced compared to group LASSO or iterative pruning. Also, compared with the iterative pruming or group LASSO, we only need one round of training to get the right pattern structure. On the other hand, under group LASSO or iterative pruning, we need to run the training process for each pattern separately leading to heavy computation costs. To make this clear, we provide an example.
Example Consider linear model with a weight matriz with dimension (m =0 n 2a). Assume that we have K = options for the block-size: 4 by 4 and by 8. Let fie ri 4. In this case, for oplimization problem equation 7 have x (2 x 26 + +2) + x (4 x 4 8 x 8) 1120 parameters for pattern selection. On the other hand, the group LASSO technique needs to train 2048 variables for each pattern.
6
Experiment
6.1 Linear Model on MNIST
The MNIST dataset contains 60000 training images and 10000 testing images which are gray pictures of digits to The size of each image is 28 28 pixels. In the first experiment, we train a linear layer with softmax activation function that takes flattened image as its input.
"Gencrally, need to consider handful of options for block size. For instance, common the block size across different layers and choose block that is an exponent of 2 Grry et 2017 In experiment, we consider
K < 5.
8

---

Published in Transactions on Machine Learning Research (03/2025)
Table 1 compares our algorithm which is based on KDP with group LASSO [Scardapane et al. 2017 and the elastic group LASSO (Oyedotun et al.] 2020b), and RigT. (Evci et al.) 2020). We run our algorithm, group LASSO, elastic group LASSO, and RigL for different block sizes. Note that RigL algorithm has not been designed for training block-wise sparse models. However, we can modify this algorithm for block-wise sparse models. In particular, instead of pruning based on the absolute value of each parameter and absolute value of the gradient, we use the norm 1 of each block and the norm of the gradients within each block identify important blocks that needs to be updated during the training.
We keep the rank of our decomposition equal to 2 2 To report the standard deviation, run our experiment five times. Column FLOPs indicate the number of FLOPs nceded during forward and backward paths. We used PyTTrch package ptflops to calculate the number of flops. This table shows that our method generally can achieve better accuracy and better sparsity rate compared to group LASSO and elastic group LASSO. The number of FLOPss and training parameters also are smaller under our algorithms. For instance, when the block size is 16 by 2, the number of FLOPs and training paramcters is significantly lower than the baselines. However, our algorithm is able to achieve a higher accuracy and a higher sparsity rale compared to the baselines.
As another baseline, we compare our algorithm with unstructured pruning (Han et al. pruming in the table). Generally, unstructured pruning can achieve better accuracy compared to structured and block-wise pruming. This table shows that when block size is 2 by 2, our algorithm can achieve better accuracy and better sparsity rate compared to all the baselines including iterative pruning. For other block sizes, our algorithm decreases the number of flops and training parameters significantly compared to baselines. As result, some of the baselines may achieve better accuracy compared to our method.
2015 (iterative
Table 1: One Linear Layer Model compression results on MNIST dataset
Block size
Models
Accuracy
Sparsity Rate
Training Params
Training FLOPs
(222)
Group LASSO
85.18 + 0.37
49.67 = 0.10
7.84K
7.85k
(2,2)
elastic group LASSO
80.61 + 0.44
42.11 = 0.76
7.84K
7.85k
(2,2)
Blockwise Rigl
86.66 + 0.36
50.61 + 0.00
7.84K
7.85k
(2,2)
Ours
88.97 + 1.50
86.43 = 0.30
5.89K
7.84k
(4,2)
Group LASSO
74.12 + 0.98
44.38 = 1.09
7.84K
7.85k
(4,2)
elastic group LASSO
76.66 + 1.59
44.32 3.35
7.84K
7.85k
(4,2) Blockwise Rigl
87.13 + 0.44
50.61 = 0.00
7.84K
7.85k
(4,2)
Ours
81.75 - 0.77
38.57 = 0.48
2.96k
3.92k
(8,2) Group LASSO
75.82 + 0.73
40.87 = 0.89
7.84K
7.85k
(8,2)
elastic group LASSO
80.61 + 0.44
42.11 = 0.76
7.84K
7.85k
(8,2)
Blockwise Rigl
87.32 + 0.38
50.61 = 0.00
7.84K
7.85k
(8,2)
Ours
75.08 + 2.05
50.85 + 0.70
1.96k
1.50k
(16,2)
Group LASSO
75.82 + 0.73
40.87 = 0.89
7.85k
7.84K
(1622)
elastic group LASSO
80.61 + 0.44
42.11 + 0.76
7.85k
7.84K
(1622)
Blockwise Rigl
86.95 + 0.35
50.61
0.00
7.84K
7.85k
(16,2)
Ours
81.57 + 2.05
50.85
0.70
0.80k
0.98k
Iterative Pruning
86.72 + 0.24
50.06 0.46
7.84K
7.85k
Pattern Selection In addition, we conduct an experiment on the effectiveness of our method in pattern selection. We use the same patterns as those used in Table [ Our goal is to use optimization problem equation 7 to pick the pattern that achieves the highest accuracy among the patterns stated in Table [ We set X1 = A₂ 0.01 and increase these paramcters by 0.002 every 5 epochs. We continue training for 50 epochs. We can see in Figure 3a that the parameters associated with patterns k 2, 2,3,4 4 go to zero after 40 epochs, and only 5(1) (k = 1 is associated with block size 2 by 2) remains non-zero at epoch 40. This shows that pattern k = 1 is the best pattern in terms of accuracy. After finding the best pattern, we can fine-tune
We choose rank to demonstrate the capability our algorithm. Clearly, selecting a larger rank can improve the perfor mance our algorithm even further.
9

---

Published in Transactions on Machine Learning Research (03/2025)
the parameters associated with this pattern to get the best accuracy. After fine-tuning for 5 epochs, the accuracy of the first pattern can achieve 88.86 %.
6.2 LeNet on MNIST
In this part, we conduct an experiment with the LeNet-5 Network (Lecun et al., 1998) and the MNIST dataset. Similar to the previous part, compare our algorithm with group LASSO, elastic group LASSO, and unstructured iterative pruning. The results shown in Table Since LeNet-5 has three fully connected layers, the column block size indicated the block sizes for these layers. For example, (16,8)(8,4)442)) indicates that the block size in the first layer is 16 by 8, in the second layer is 8 by 4, in the third layer is 4 by 2. The rank of the decomposition under our algorithm is 5 for all the layers in all the experiments. We can see our algorithm achieves better accuracy compared to the baselines. However, the number of FLOPs and the number of training paramcters of our algorithm are significantly lower compared to basclines.
Table 2: Accuracy, sparsity rate, number of training parameters, and number of FLOPs for LeNet-5 network trained on MNIST dataset for different block sizes.
Block-size
Methods
Accuracy
Sparsity Rate
Train Param
Train FLOPs
(16, 8) (8, 4) [4, 2)
group LASSO
98.31 + 0.54
49.43 = 0.06
61k
435.85k
(16, 8) (8, 4) (4, 2)
Elastic group LASSO
98.23 + 0.60
49.47 1.02
61k
435.85k
(16, (8, 4) 2)
Blockwise Rigl
98.28 + 0.01
50.04 0.00
61k
435.85k
(1,,8)(8,4) (8 24
Ours
98.55 + 0.56
50.85 0.70
6.2k
270.59k
(), 22
group LASSO
97.96 + 0.51
72.97
14.01
61k
435.85k
(8, (4, 22
Elastic group LASSO
98.02 + 0.51
63.28 + 12.89
61k
435.85k
(4, (2
Blockwise Rigl
97.77 + 0.09
50.03 0.00
61k
435.85k
(4.
Ours
99.06 + 0.52
52.49 = 1.23
22.6k
287.54k
(4, (4, (2,2)
group LASSO
98.08 + 0.60
52.58 + 4.94
61k
435.85k
(4, 4) (4, 4) (2.
Elastic Group LASSO
98.17 + 0.55
52.77 + 5.93
61K
435.85k
(4, 4) (4, 4) 2)
Blockwise Rigl
97.70 + 0.05
50.01 + 0.00
61k
435.85k
(4, 4) (4, 4) 2)
Ours
99.08 + 0.53
54.02 1.53
13.7k
306.74k
(4, 4) (2, 2) (2.
group LASSO
98.08 + 0.53
63.29 9.21
61k
435.85k
(4, 4) (2, 2) 2)
Flastic Group LASSO
99.08 + 0.68
54.30 1.59
61k
435.85k
(4, 4) (2, 2)
2)
Blockwise Rigl
97.72 + 0.12
50.01 0.00
61k
435.85k
(4, (,,4)- (2, 2)
2)
Ours
99.08 + 0.68
54.30 1.59
9.7k
319.34k
(2, (2,
2)
(2, 2)
group LASSO
98.27 + 0.73
49.38 0.02
61k
435.85k
12, 2)
(2, 2)
(,,
Elastic group LASSO
97.58 + 0.60
84.43 8.43
61k
435.85k
[2,
2)
(2,
2)
2)
Blockwise Rigl
98.31 + 0.17
60.03 + 0.00
61k
435.85k
[2, 2)
(2,
2)
2)
Ours
98.66 + 0.59
56.27 + 2.71
6.1k
357.74k
iterative pruning
98.02 + 0.82
58.56 1.32
61k
425.85k
0.4
0.8
Epoch
(a)
(b)
(c)
Figure a) Pattern selection for linear model. b) Pattern selection for LeNet-5 network. e) Pattern selection for ViT tiny network.
10

---

Published in Transactions on Machine Learning Research (03/2025)
Pattern Selection Similarly, we also have experimented with the pattern selection. In particular,
optimization problem in equation 7 to pick the pattern that achieves the highest accuracy among the patterns stated in Table 2 We set Å X2 0.01 and we increase these parameters by 0.002 every 5 epochs. We run the training for 200 epochs and we report Σ |1 for different S k Σ 5 in Figure 3b In this experiment = corresponds to pattern (16,8) (8, ()(4 2), 2 corresponds pattern (8, () 4)(4, corresponds pattern (4, (2, 2),2, 2), and k corresponds to pattern (2, (2, (2, 2). As we expected, the weight corresponding to the pattern k 3 remains non-zero after 130 epochs. After finding the best pattern, can fine-tune the selected pattern to
: corresponds pattern (4, (4, 2),
achieve the maximum possible accuracy.
6.3 ViT/Swin-Transfomne on CIFAR-100
We conduct experiment with approach with the ViT-tiny, ViT-baso(Dosovitaa et al. 2021 Touvron et al. 2021 and Swin-translormer Tiny (Liu et al. 2021b) CIFAR-100 image classification dalaset (He et al. 2016 The dataset has 60 thousand pictures of 100 different categories. The model is trained using this dataset for 300 epochs. We keep the rank of our algorithm equal to 4. Since most of the modules in transformer architecture are linear layers, our method can significantly decrease the number of parameters. It can be seen in Table 3 that our model's number of parameters during the training is only 3% of that of the original model for ViT--tnn, The number of training parameters also decreases by 86% for ViT- base In the case of the Swin Transformer, want to emphasize that both elastic group LASSO and our method can achieve high accuracy, However, as we expected, the number of training parameters and training FLOPs are significantly smaller under our proposed algorithm.
achieve 80% compression rate during the training. We
Pattern Selection. In this part, we validate the possibility using equation 7 to find a pattern that achieves the highest accuracy for ViT-tiny model. We consider three patterns: pattern k associated with ViT-tiny model with block-size 4
associated
with a ViT-tiny model with block-size 2 by 2, k by 4, and k = 3 is associated with ViT-tiny model with block-size 8 by 8. We solve optimization problem 7 and illustrates E [| in each epoch in Figure 3c We can the weights associated with pattern k = 1 is the only one that remains non-zero after 180 epochs implying that pattern & = 1 can achieve the highest accuracy compared to patterns = 2,3. Note that we train ViT-tiny under these patters, we can achieve an accuracy of 64.56, 62.99, 62.88 for = 2,2,3, respectively. This implies that pattern best pattern. No
is the
Table 3: Experiment with CIFAR-100 dataset. Our method can significantly reduce the training parameters and training FLOPs while maintaining the accuracy close to the original model and (elastic) group LASSO method.
Method
Block-size
accuracy
Sparsity Rate
Training Params
Training FLOPs
ViT-t (Original Model)
64.32 + 1.92
5.5M
2.16G
Group LASSO
4 x 4
60.41 4.24
49.99 + 0.02
5.5M
2.16G
clastic group LASSO
4 x 4
61.92 3.01
49.92 = 0.11
5.5M
2.16G
Blockwise Rigl
4 x 4
49.56 0.48
50.67 + 0.00
5.5M
2.16G
Ours
4 x 4
62.99 0.73
49.64 + 0.72
0.16M
65.37M
ViT-b (Original Model)
71.34 0.42
87.34M
35.34G
Group LASSO
4 x 4
68.41 1.24
48.92 + 1.34
87.34M
35.34G
elastic group LASSO
4 x 4
66.95 + 2.17
51.93 + 0.37
87.34M
35.34G
Ours
4 X 4
69.82 + 0.22
60.31 + 3.61
11.58M
10.11M
SOrignal Model)
81.44 = 0.05
27.60M
26.18G
Group LASSO
4 x 4
75.87 + 2.17
50.24 + 0.13
27.60M
26.18G
clastic group LASSO
4 x 4
76.34 = 0.82
50.19 + 0.25
27.60M
26.18G
Blockwise Rigl
4 x 4
60.30 0.22
50.03 + 0.00
27.60M
26.18G
Ours
4 X 4
77.54 0.42
53.25 + 0.36
5.3M
167.3 637.33M
11

---

Published in Transactions on Machine Learning Research (03/2025)
6.4 Ablation Experiments
Table 4: The impact of rank of the decomposition in equation 3 on the model's accuracy, sparsity rale, number of training parameters, and number of FLOPs.
Model
Rank
accuracy
sparsity
Training Params
Training FLOPs
Linear
48.40 1 0.40
53.57 + 2.43
0.26k
0.56k
Linear
66.79 + 0.91
53.57 = 1.57
0.46k
1.13k
Linear
4
84.58 + 3.55
55.36 = 0.72
0.85k
2.24k
Linear
6
88.19 + 0.32
51.79 = 0.56
1.24k
3.36k
ViI-t 1
36.86 + 2.41
52.20 = 0.13
0.88M
0,54M
ViT-t 2
59.71 + 2.63
50.74 = 0.27
1.22M
1.02M
VIT-t
4
62.99 + 0.73
49.64 = 0.72
1.88M
1.88M
VIT-1
1
53.27 + 1.46
57.32 + 1.84
39.19M
34.1G
ViT-I
62.79 + 0.43
61.32 = 1.29
58.13M
92.51G
VIT-1
73.46 + 0.36
66.59 + 2.94
96.01M
329.44G
Swin-t
58.46 + 0.16
51.39 + 0.67
3.53M
55.78M
Swin-t
68.22 + 0.04
54.37 = 1.01
5.25M
108.65M
Swin-t
77.54 + 0.42
53.25 + 0.36
8.69M
167.33M
In this part, we conduct an experiment to understand the impact of the rank on the accuracy, mumber of training parameters, and number of training flops during the forward path and backward path. We set the block size equal to x 4. We conduct ablation experiments on the linear model, ViT-tiny, ViT-large, and Swin Transformer separately. As we expected, we can improve the accuracy of the model by increasing the rank. In this experiment, we kept the regularizer parameter the same for different ranks. As result, the sparsity rate is not sensitive to the rank and remains almost the same for different ranks.
7 Conclusion
We introduce novel approach for training block-wise sparse matrices using Kronecker product dccomposi- tion. This method offers an alternative to group LASSO/structun ured pruming, enabling training block-wise sparse matrices with fewer parameters and FLOPs. Our theoretical results show that our proposed method can decrease the number of training parameters and the number of FLOPs without hurting accuracy com- pared to the group LASSO and structured pruning algorithms. Our experiments demonstrate the effective- ness of our approach in terms of efficiency and accuracy. We further show that our algorithm enables us automate the pattern selection and efficiently find the right block size for the sparsity pattern to achieve the best accuracy.
Tt is also known that the model compression can negatively impact the fairness Tran et al. 2022). Therefore, future study is needed to study the impact of the proposed method on the fairness of the model.
8 Acknowledgment
This work is supported by the U.S. National Science Foundation under award IIS-2301599 and CMMI- 2301601, and by grants from the Ohio State University's Translational Data Analytics Institute and College of Engineering Strategic Research Initiative.
References
Sajid Anwar, Kyuyeon Hwang, and Wonyong Sung. Structured pruning of deep convolutional neural net- works, 2015. URL httpt:t//raxii..oot http://///a////..0050555
Maximiliana Behnke and Kenneth Heafield. Pruning neural machine translation for speed using group lasso. In Proceedings of the sirth conference machine transtation, pp. 1074-1084 2021.
12

---

Published in Transactions on Machine Learning Research (03/2025)
Yaohui Cai, Weizhe Hua, Hongzheng Chen, G. Edward Suh, Christopher De Sa, and Zhiru Zhang. Structured pruning is all you need for pruning cnns at initialization 2022.
Jang Hyun Cho and Bharath Hariharan. On the efficacy of knowledge distillation. In Proceedings of the TEEE/CVF international conference computer vision, pp- 4794-4802, 2019.
Paolo D' D'Alberto, Taehee Jeong, Akshai Jain, Shreyas Manjunath, Mrinal Sarmah, Samuel Hsu, Yaswanth Raparti, and Nitesh Pipralia. Weight block sparsity: Training, compilation, and ai engine accelcrators, 2024. URL https://arxiv..rrg wwtps//org.bbb///.ooooo/
Tri Dao, Boidi Chen, Kaizhao Liang, Jiaming Yang, Zhao Song, Atri Rudra, and Christophor Ré. Pixclated butterfly: Simple and efficient sparse training for neural network models, 2022. URL https://arxii
org/abs/2112.0o 00029
Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. Advances in neural information processing systems, 30, 2017.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale, 2021.
Ali Edalati, Marzieh Tahaei, Ahmad Rashid, Vahid Partovi Nia, James J Clark, and Mehdi Rezagholizadeh. Kronecker decomposition for gpt compression. arXiv preprint arXiv:21 10. 08152, 2021.
Ctku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In Proceedings of Machine Learning and Systems 2020, pp. 471-481. 2020.
Chao Fang, Wei Sun, Aojun Zhou, and Zhongfeng Wang. Efficient n.m sparse dan training using algorithm, architecture, and dataflow co-design. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 43(2):506-511 2024. doi: 10.1109/TCAM (TA 2023.331778..
Tommaso Furlanello, Zachary Lipton, Michael Tschannen, Laurent Itti, and Anima Anandkumar. Born again neural networks. In International Conference on Machine Learning, pp. 1607-1616. PMLR, 2018.
Scott Gray, Alec Radford, and Diederik P. Kingma. Gpu kernels for block-sparse weights. 2017. URL
https://appl wtw.p..smmmticccolllaa.a. Ditpaaaaiisiaaooooooooooo/oiiiis 52220661
Marawan Gamal Abdel Hameed, Marzieh S Tahaei, Ali Mosleh, and Vahid Partovi Nia. Convolutional neural network compression through generalized kronccker product decomposition. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 771-779 779, 2022.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances in newral information processing systems, 28, 2015.
Song Han, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark A Horowitz, and William J Dally. Eie: Effficient inference engine compressed deep neural network. ACM SIGARCH Computer Architecture News, 24(3)2243 254, 2016a.
Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding. In Yoshua Bengio and Yann LeCun (eds.), 4th Inter- national Conference Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016b. URL http::://arxi..o//aab/////// wtwp/oo/////a/ooeeooe 2ttg/abs/1110.014333
Song Han, Junlong Kang, Huizi Mao, Yiming Hu, Xin Li, Yubin Li, Dongliang Xie, Hong Luo, Song Yao, Yu Wang, al. Ése: Efficient speech recognition engine with sparse Istm on fpga. In Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, pp. 75-84, 2017.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016. doi: 10. N0.1100/CVPP.2016.000
13

---

Published in Transactions on Machine Learning Research (03/2025)
Byeongho Heo, Jeesoo Kim, Sangdoo Yun, Hyojin Park, Nojun Kwak, and Jin Young Choi. A comprehensive overhaul of feature distillation. In Proceedings of the IEEE/CVF International Conference Compuler Vision, pp. 1921 1921-1930, 2019a.
Bycongho Hco, Minsik Lee, Sangdoo Yun, and Jin Youn Choi. Knowledge transfer via distillation of activation boundaries formed by hidden neurons. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 9779-3787 2019b.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint arXiv:1503.0955 2015.
Yen-Chang Hsu, Ting Hua, Sungen Chang, Qian Lou, Yilin Shen, and Hongxia Jin. Language model compression with weighted low-rank faclorization. arXiv preprint ar Xix::2207.000 2022.
Zehao Huang and Naiyan Wang. Like what you like: Knowledge distill via neuron selectivity transfer. arXiv preprint 1iXt:1707.01219, 2017.
Yasutoshi Ida, Yasuhiro Fujiwara, and Hisashi Kashima. Fast sparse group lasso. Advances in neural information processing systems, 32, 2019.
Ameya D. Jagtap, Yeonjong Shin, Kenji Kawaguchi, and George Em Karniadakis. Deep kronecker neural
networks: A general framework for neural networks with adaptive activation functions. Newrocompuling, 468:165 180, 2022. ISSN 0925-2312. doi:
URL https:
// www.sciencedirect... htt.://ccccccccoooooooooooooooaa
Peng Jiang, Lihan Hu, and Shihui Song. Exposing and exploiting fine-grained block structures for fast and accurate sparse training. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS 222 Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9781713871088.
Jangho Kim, SeongUk Park, and Nojun Kwak. Paraphrasing complex network: Network compression via factor transfer. Advances in neural information processing syslems, 31, 2018.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 2324, 1998. doi: 10.1109/5.726791.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr. Snip: Single-shot network pruning based on connection sensitivity, 2019a.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr. Snip: Single-shot network pruning based 02340
connection sensitivity, 2019b. URL httpe://arxiv.org//eee
Hao Li, Asim Kadav, Tgor Durdanovie, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets, 2017a
Quanquan Li, Shengying Jin, and Junjic Yan. Mimicking very efficient network for object detection. Proceedings of the ieve conference on compuler vision and pollern recognition, pp. 6356 6364, 2017b.
Baoyuan Liu, Min Wang, Hassan Foroosh, Marshall Tappen, and Marianna Penksy. Sparse convolutional neural networks. In 2015 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 806 814, 2015. doi: (0000//CVR.201..29955560
Liyang Liu, Shilong Zhang, Zhanghui Kuang, Aojun Zhou, Jing-Hap Hao Xue, Xinjiang Wang, Yimin Chen, Wemming Yang, Qingmin Liao, and Wayne Zhang. Group fisher pruning for practical network compression. International Conference on Machine Learning, pp. 7021-7032. PMLR, 2021a.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows, 2021b. URL https: https://arxiv.org abs/ bba/2103. 14030
14

---

Published in Transactions on Machine Learning Research (03/2025)
Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang. Learning efficient convolutional networks through network slimming. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), Oct 2017.
Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through L_ regularization. ar preprint 1oXx::111..0130 2017.
Rongrong Ma, Jianyu Miao, Lingleng Niu, and Peng Zhang. Transformed regularization for learning sparse deep neural networks. Neural Networks, 119:286 298, 2019.
Seyed Iman Mirzadeh, Mehrdad Farajtabar, Ang Li, Nir Levine, Akihiro Matsukawa, and Hassan Ghasemzadeh. Improved knowledge distillation via teacher assistant. In Proceedings of the AAAI confer- ence on artificial intelligence, volume 34, pp. 5191-5198, 2020.
Asit Mishra, Jorge Albericio Latorre, Jeff Pool, Darko Stosic, Dusan Stosic, Ganesh Venkatesh, Chong Yu, and Paulius Micikevicius. Accelerating sparse deep neural networks, 2021.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H. Nguyen, Madeleine Gibescu, and Anto- nio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by net- work science. Nature Communicatiions, 9(1, June 2018. ISSN 2041-1723. doi: 10.1038/s4 10.1038//41147-0118-0000 04316-3
URL http: wtt.:.....r///11.010//4441177771
Sharan Narang, Eric Undersander, and Gregory F. Diamos. Block-sparse recurrent neural networks. CoRR, abs/1711.02782, 2017. URL
02782
Oyebade Oyedotun, Djamila Aouada, and Bjorn Ottersten. Structured compression of deep neural networks with debiased elastic group lasso. In Proceedings of the IEEE/CVF Winler Conference Applications of Computer Vision, pp. 2277-227777 2286, 2020a.
Oyebade K. Oyedotun, Djamila Aouada, and Björn Ottersten. Structured compression of deep neural networks with debiased elastic group lasso. In 2020 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 2266 2275, 2020b. doi: 10.1109/ 10.1109/WACVV WWAVA55722200000003333
Angshuman Parashar, Minsoo Rhu, Anurag Mukkara, Antonio Puglielli, Rangharajan Venkatesan, Brucek Khailany, Joel Emer, Stephen W Keekler, and William J Dally. Scnn: An accelerator for compressed-sparse convolutional neural networks. ACM SIGARCH computer architecture news, 45(2):27-40, 2017.
Wonpyo Park, Dongju Kim, Yan Lu, and Minsu Cho. Relational knowledge distillation. Proceedings of the IREE/CVE conference on computer vision and pallern recoguition, pp. 3967-3976, 2019.
Nikhil Rao, Robert Nowak, Christopher Cox, and Timothy Rogers. Classification with the sparse group lasso. IEEE Transactions on Signal Processing, 64(2):448-466) 2015.
R. Reed. Pruning algorithms-a survey. IEEE Transactions on Neural Networks, 4(5):740-747, 1993. doi: 10.1109/72.244552
Victor Sanh, Thomas Wolf, and Alexander Rush. Movement pruning: Adaptive sparsity by fine-tuning. Advances in Neural Information Processing Systems, 33:20378 20389, 2020.
Simone Scardapane, Danilo Comminiello, Amir Hussain, and Aurelio Uncini. Group sparse regularization for deep neural networks. Newrocomputing, 241:81 89, June 2017. ISSN 0925-2312. doi: 10.1016/j.
2017.02.029. URL http://dtt.t..//// http:/xxxxxoii..o www.doo..ooooo.... http://xxxddo..og/1.../ 1016/j nww.con. 2017 www..021..22... 02.
Yi-Lin Sung, Varun Nair, and Colin A Raffel. Training neural networks with fixed sparse masks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (ods.), Advances in Neural Information Processing Systems, volume 34, pp. 24193 24193-24205. 24205. Curran Associates, Inc., 2021. URL https://prroceedings www.ipp.cc.pppprrrrr htcp//pper..leee/ppp//////////// coc2114488700ssee55777773333
15

---

Published in Transactions on Machine Learning Research (03/2025)
Chong Min John Tan and Mehul Motani. Dropnet: Reducing neural network complexity via iterative pruning. Tn International Conference on Machine Learning, pp. 9356-935660 036699366. PMLR, 2020.
Hidenori Tanaka, Daniel Kumin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Newral Information Processing Systems, volume 33, pp. 6377 6389. Cur- ran Associates, Inc., 2020a. URL https::/proceeddngg neurips wew..pp..c/pppprrtteeee......... /flee///aper/2222//1111 46a4378f835d 25a47776888600000000077662222223
pdf
Hidonori Tanaka, Daniel Kunin, Danicl L. K. Yamins, and Surya Ganguli. Pruming neural networks without any data by iteratively conserving synaptic flow, 2020b.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive representation distillation. arXiv preprint arXiv:1910. 10699, 2019.
Hugo Touvron, Matthicu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Herve Jegon.
Training data-efficient image transformers amp; distillation through attention. In International Conference on Machine Learning, volume 139, pp. 11347-10355 July 2021.
Cuong Tran, Ferdinando Fioretto, Jung-Eun Kim, and Rakshit Naidu. Pruning has a disparate impaac on 2022.
model accuracy. Advonces in Neural Information Processing Systems,
Charles Van Loan. The ubiquitous kronecker product. Journal of computational and applied mathemalics, 123(1-2):85 -000 2000.
Dharma Teja Vooturi, Dheevatsa Mudigere, and Sasikanth Avancha. Hicrarchical block sparse neural net- works, 2018. URL httpp:://aaxiv.or/aabbb////// 03420
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020. URL /RL/pttps//ppeerrriiei het/fforum/iidsSkasAcvve
Huan Wang, Qiming Zhang, Yuehai Wang, and Haoji Hu. Structured probabilistic pruning for convolutional neural network acceleration. In BMVC, volume 3, pp. 7, 2018.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances in newral information processing systems, 29, 2016.
Sanyou Wu and Long Feng. Sparse kronecker product decomposition: A general framework of signal region detection in image regression, 2022.
Junho Yim, Donggyu Joo, Jihoon Bae, and Junmo Kim. A gift. from knowledge distillation: Fast optimiza- tion, network minimization and transfer learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4133-4141, 2017.
Miao Yin, Huy Phan, Xiao Zang, Siyu Liao, and Bo Yuan. Batude: Budget- neural network compres- sion based on tucker decomposition. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 8874 8882, 2022.
Lci Yu, Xinpeng Li, Youwci Li, Ting Jiang, Qi Wu, Haoqiang Fan, and Shuaicheng Liu. Dipnet: Efficiency distillation and iterative pruning for image super-resolution. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1692-1701, 2023.
Xiyu Yu, Tongliang Liu, Xinchao Wang, and Dacheng Tao. On compressing deep models by low rank and sparse decomposition. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 67 76, 2017. doi: 10.1109/CV PV..220....
Geng Yuan, Xiaolong Ma, Wei Niu, Zhengang Li, Zhenglun Kong, Ning Liu, Yifan Gong, Zheng Zhan, Chaoyang He, Qing Jin, Siyue Wang, Minghai Qin, Bin Ren, Yanzhi Wang, Sijia Liu, and Xue Lin. Mest: Accurate and fast memory-cconomic sparse training framework on the edge, 2021. URL https:
16

---

Published in Transactions on Machine Learning Research (03/2025)
Ying Zhang, Tao Xiang, Timothy M Hospedales, and Huchuan Lu. Deep mutual learning. In Proceedings of the IEEE conference on computer vision and poltern recognition, pp. 4320-4328, 2018.
Ding Zhu, Zhiqun Zuo, and Mohammad Mahdi Khalili. Training block- wise sparse models using kronecker product decomposition. In NeurIPS Workshop on Machine Learning and Compression, 2024.
17

---

Published in Transactions on Machine Learning Research (03/2025)
A Appendix / supplemental material
A.1 Proof [Proposition 2
Consider layer network without bias term. The imput dimension of it is The output dimension of it is m.. We can knoe the shape of the weight matrix W is mm Since we have N data points, the input matrix X E gxxn
A.1.1 Forward FLOPs with full matrix
Proof. When using full weight matrix, the first step is to compute the output E RNmm as
0 == D=XWT
(8)
The FLOPs of this step Nm(2n 1). Then calculate the loss
I= - - YII
(9)
where E Nxm the label matrix. The FLOPSs for this step 3Nm Therefore, the FLOPPs of the forward computation
Nm(2n-17 (3Nm 1) (2Nm(nn++ + 1)).
(10)
A.1.2 Backward FLOPs with full matrix
Proof. In the backward process, we ncod calculate the gradient of J on W. Using chain rule, the first step is to compute
0J
2(0 - YY).
(11)
80
Since Y has been calculated in the forward pass, the FLOPs is Nm. The gradient of W
0J
(0J) X.
(12)
oW 30
The FLOPP for this step mn(2N 1). Therefore, the FLOPs for the backward pass
Nm - m2 - 1) (Nm 1)).
(13)
A.1.3 Forward FLOPs with sparse matrix
With Kronecker product decomposition, we replace W by (S Ar) 8 B. S and A, E Rmixns B, E m where m1my = m, ni n.
Proof. In the forward pass, we need to firstly reshape X Nxx into reshape(X) E R Then calculate (rreshape(X) e pm with FLOPs Nnimy(2ng 1). The result is reshape into (eshapp((rrehhaee(X)) E I Nm2xn1
Then we calculate @ A, E Rrixm with FLOPs mmm- After this, we get
O reslape((.ressaaee A,) e B Nmaxmj
(14)
18

---

Published in Transactions on Machine Learning Research (03/2025)
with FLOPs Nm1my(2n;
1). We denote O as the output of the layer, which is to say
0 O
reshape((rreshaae(([)]] A.)"
(15)
1=1
==
The total FLOPs to get O is
r(Nmam2(2m)
1) + mym + N21m22222 -1) (r 1)
(16)
Then we reshape O in reshape(O) V xm The loss calculated as
J |reshape(O)-X)
(17)
The FLOPs for this step is 3Nm 1. Therefore the FLOPs of the forward computation is
r(2Nmaman Nm myn1 + 2Nmmmmn Nm2m)) (r 1). 3NM =0 (2Nrmin1 (m2 n2) - Nr(m 2m2n1 + +3Nm)
(18)
0
A.1.4 Backward FLOPs with sparse matrix
Proof. In the backward process, we need to calculate the gradient of J on S, A, and Bü Using chain rule, the first step is compute
8J 2(reshape(O) YY.
(19)
Oreshape(O)
Since reshape(O) Y has been calculated in the forward pass, the FLOPs is Nm. Then we reshape into 07 E Xmmm Then can get 00
0J O A.)
T
reshapo(B,reshap((())
(20)
a0
Since reshape(B.reshapeee has been obtained in the forward pass, the FLOPs for this step is m2Nm22 1). To get the gradient on S and Ad, we have
aJ =
aj
AA
(21)
0S
0(
O A.)
1=1
with FLOPs rmin + (r 1)m and
aj
0J a(S A.)
(22)
0A,
with FLOPs mint. The gradient on (eesape(,reshhaeeEX) is
0J
0J d0
(S ② Ax).
(23)
3 reshape (eeesaaee(
The FLOPs for this step is Nm (2m; 1). We reshape the gradient into B.reshape( we can get the gradient on B, as
07
m2, So.
0J
0J
a B,reshape(X) reshape(X)",
(24)
0B,
with FLOPs of m2ng(2Nn1 1). Therefore, get the total FLOPs for the backward pass as Nm + n (2Nm2 rm,n n (r 1)mmn rmin rrNman, (2m, 1) (2N
=0 (Nm (4 m2n 2222(1n2)
(25)
19

---

Published in Transactions on Machine Learning Research (03/2025)
A.2 Proof [Proposition
Consider two-layer network without bias term. The input dimension of the first linear layer is mll), The output dimension of the linear layer is ml2, So, the input dimension for the second linear layer is m The output dimension of the linear layer is ml)) With the network architecture, we can know that w E [m]!) and ( pm Since have N data points, for the input matrix of the first layer denoted by x!!,, we have, X Nxm") We use o represent the activation function for the first layer.
xm!I
A.2.1 Forward FLOPs with full matrix
Proof. When using full weight matrix, the first step is to compute the pre-activated output Ol!) RN
a8
o = xlWII.
(26)
The FLOPs of this step is Vml3(2m!)) 1). Then, we compute the activation X RRRxX Nxm
follows,
x =
(27)
The FLOPs for calculating the activation is Nm For the second layer, we need to compute O R as O (22 The FLOPs are Nm (2mL) [2] 1). The last step is calculating the loss
J | -11
(28)
where E Nx is the label matrix. The FLOPs for this step is 3Nm 1. Therefore, the FLOPss of the forward computation is
Nm P2 1) + Nm + Nm (2m 1) + 3Nm 2Nm ml + Pl + 2N -
= 0 (2N(m ml2 ml ml + m m))) (29)
A.2.2 Backward FLOPs with full matrix
Proof. In the backward process, we need to calculate the gradient of J on Wil and W Using chain rule, the first step is compute
8J
2(0 Y).
(30)
00
Since O!2 Y has been calculated in the forward pass, the FLOPPs is Nm The gradient of W is
0J
0J
T X
(31)
2W
0012
The FLOPs for this step is m ml (2N 1).
To compute the gradient on W[1), we need to first compute
0J
0J
W|21
(32)
ax
with the FLOPs (2m - 1). Then compute
a5
aJ (a(O!l)))
(33)
J00e
axP]
20

---

Published in Transactions on Machine Learning Research (03/2025)
with the FLOPs Nml?.. The final step is
0J
0J T 800n
x1I
(34)
aw
The FLOPs m ml (2N - 1). Therefore, the FLOPs for the backward pass is
Nm + m P] Pl - 1) + Nm - 1) + Nm + mm (2N
-2Nm + 4Nm ml [3] + Nm m m ml
=0 (2(2m())ml 4l ml + m
(35)
A.2.3 Forward FLOPs with sparse matrix
With the Kronecker product decomposition, we replace Will by Ei (S ④ A! 60 B!ll and W by
E 1
2 ( ( & In the first layer, 5(1 and A!") Rm (2) xmm" B E Rm xm where m; [1] 1'mm" ml
= m ml))
2 2 =l In the second layer, 5 and A!9 E Rm xm B.a Rm xmp) 12) where m [3] (m)m [3] ml
m m2
m2
Proof. In the forward pass, we need to firstly reshape X E RRNxml into reshape(X E Rm xNm!". !!]
Then we calculate B! reshhhape)("")) E Rm Nmm"" with the FLOPs Nmm"mm [2) (2ml) - 1). The result is reshaped into reshapo( Bi" reshape (xl")) e [Nmf")mmm"
Then we calculate 5!ll A!") Rm [) xm]
with the FLOPs mf'mp] After this, we get
[|] reshape( (B. reshape( (sS" o A."' e R Nm. xm!!
(36)
with FLOPs Nm2 mi
(2] (2ml
[1]
1). We denote O as the pre-activated result of the first layer, which is to
say
[1]
0
Σ
reshape(B reshape(x!))) A.T)TT
(37)
i=1
The total FLOPs to get O is
n!ll ( (Nm, []] m2 (2ml)) - 1) mi mm'mm"" + Nm! ml [2] (2m [1] - 1)) (7!l)) 1)ml?I
[1]
- 22 41 ml! + 22 ml (m) + mll)) + mi 1 (n))) + (n 1)ml N.
(38)
The input for the second layer x e Nm xm! is obtained by
x = =Oll").
(39)
[2] 2m Then we reshape it into reshape(X IRm! xNm! "
We caleu- late Bia reshape E m x with the FLOPs Nmfmmm (3) (2ml²) 1). The result is reshaped into reshape( (2) g Nm xm!
with FLOPs Nm, mi
After this, we get Similar to the first layer, we calculate stl o A E Rm xm! with the FLOPs m m Pl
0.¹1 reshape( ( o A.7)TT e I Nm. xm
(40)
21

---

Published in Transactions on Machine Learning Research (03/2025)
[3] with FLOPs Nmz mi
[3] (2m]
2
1).
We denote O the output of the second layer, which is to say
[
0
Σ
0
reshape ( A!1)T.
(41)
i=1
The lotal FLOPs to get 0 is
[P Nm
[2 mi (2m²
[3]
[2]
1) + mi 1i2imm mi
[8]
Nm2 mi
[3] 13
(2m² [2] 1)) + (v 11m |
-p1= 22
(2 m
3
2N m 2 Nm
[3] [m
[]
+ m (a)) m 2 m (3) + (r12) 1)mll1 19 N.
(42)
Then we shape Ol3 into reshape(OPP) E Nx The loss is calculated as
J = reshape(OE)) - r
(43)
The FLOPs for this step is 3 1. Therefore, the FOLPs the forward computation is
2N mn mg + 2N 19 m/ Nm (mn" + ml()) + mi ) (r' 1) N
,1
(2 + 2N 18 mi Nm, (m + ) + m m
+ (r 1)m [l 3
=0
(n11)) m + 2N ( ml) Nmf (mm) + m + (2] (2 ml + 2N 13 m/
Nm, (m)
[3] m (3))
Nm (2)
+ 3N
(11)
Let C1 2N m + 2N [1 Nm 3 (m - m C2 2) 14l + 2N
Pl
Nmm 13l (m12 m=))),
have the FLOPs as O (1 Ci 12 C2 + Nm 3N (9).
A.2.4 Backward FLOPs with sparse matrix
Proof. In the backward process, we need calculate the gradient of on sti,, A!" , Using chain rule, the first step is compule
s(2), A!") and B!!.
aJ
((reshape(O@))) -Y))
(45)
roshapc(O)j2
Since reshape(O(2) Y has been calculated in the forward pass, the FLOPs is Nm Then we reshape it a7
E NNNm b9 xm!" Then we can get
into
P0PT
0J
0J 7 reshape( [essapp))
reshape(x(21)).
(46)
0(S O A.2)
2012
Since reshape(B reshape(x((1)) has been obtained in the forward pass, the FLOPs for this step is m 2 m (2N2m - 1). To get the gradient on s(3) and A we have
0J =
aJ
+ 1!. 3 A 12))
(47)
08
a(S
T=1
with FLOPs y [2] [3]
m m + 22
1, and
0J
0J
A! S!9)
(48)
0.4
0(
22

---

Published in Transactions on Machine Learning Research (03/2025)
22 [3] with FLOPs mi mi The gradient on reshape(B, (ee reshape(X11)) is
0j
0J (s 3 A
(49)
reshape( Re reshape
80
The FLOPs for this step is Nm, m2 m2 (2m))
1).
We reshape the gradient into aB _ reshape(X(1))
0J
E
Rm x Nom!" So, we can get the gradient on B!
05
aj
(achape(X(21)
(50)
a
OB roshapo(X111)
with the FLOPs of m2 m2 (2Nm)
12
1).
The gradient on reshape(X ( is
11
0J reshape(X12)
Σ
B
2
0J
(51)
aB reshape(X12))
[2] with the FLOPSs (m Nm (2m 13 - 11++ (r - 1) Nm Then we reshape it to get
axPI E R R. xm!!!
8J
Then we calculate the gradient on O0' as
aJ
aJ
@ (o(O!)))
(52)
d00l
0
with FLOPs Nml2 Then we can get
0(S O A! 2017
OJ
=
0J
"
reshape( (B: reshape(x(!!)) (essaape
(53)
The FLOPs for this step is mi mi (2Nm²)
[2]
[2]
1). So, the gradients st' and A!" are
aJ
aJ
A!"!
(54)
aS
a( @ A!TI)
with FLOPPs p00lm/)
[1 12l ml + (n11) - 1)ml [1] mm) and
0J
0J 0(S
(55)
A
[1] m The gradient on reshape(B)) B!"l reshape(X is with FLOPs my
aj
aJ (S @ A(")).
(56)
i reshape B
reshape(X(!)))
The FLOPs for this step is Nm m2 (2m
[1]
[2]
1). - Then we reshape it get aB, reshape(X(11) Rm! x
07
So, we can get the gradient on B. 1]
as
aJ
aj
(eshape(x(1)]"
(57)
B (X!l)
[1] (2) with FLOPPs my m2 (2Nm)) [1]
1).
23

---

Published in Transactions on Machine Learning Research (03/2025)
Therefore, we get the total FLOPs for the backward pass as
Nm 31 + (m,
3 m m )2. [ - 1) + m 1 [3] (r - 1) - m m m! [3]
m
+ n Nm (3] m (2m [3 1)+
ml meffimm? m2
33 (2Nm [ 1) |2| [m m (2) (2m)
1) + (r 1) Nm 12 (Nmm 411 m (2] (2.N (2N (2))
1)+
, m [1] m
[2] (rl 1 11m m + +rmm m [2] الd Nm -0 m0
(2m - 1) rl m 22] (2N -1 1)
=0 (m ml Nm, (4m m 21 N [9] + y Nm (4m m² ) 2 12) Nm 1t mg
(58)
7
B Computation resource
we used server with 64 CPUs of AMD EPYC 7313 16-Core Processor. The server has RTX A5000 GPUs, with 24GB memory for each one. For the experiment with linear model and LeNet, we used only one single GPU. And for the ViT-tiny experiment, use GPUs at the same time.
24


Reviews:
[{"review_id": "CPQb8kEccr", "reviewer": "Reviewer_89D7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The work is novel as the first end-to-end block sparse training method.\n2. Experiment results show its good performance in comparison with other block sparse training method.\n3. The author provides theoretical analysis to show the effectiveness of proposed method.\n\nWeaknesses:\n1. In this work, the efficient training is achieved by the Kronecker products instead of block sparsity, which means that we can also reduce the parameters during training using dense A, and B with Kronecker products. From this view, I was wondering why only use Kronecker products cannot improve efficiency. Additionally, some other sparse training method like Monarch [1] also use different factorizations to represent the dense, full weight matrix. I will expect the authors to further explain the advantages of Kronecker products with these factorizations.\n2. The experiments only include MNIST and CIFAR-100 with very small models. Therefore, with the increased model size these days, I am concerning about the performance on more modern models\n3. This work do not explain why using block sparsity for sparse training. Instead, it directly focus on the new method from block sparse training.\n\nReference:\n[1]. Dao, Tri, et al. \"Monarch: Expressive structured matrices for efficient and accurate training.\" International Conference on Machine Learning. PMLR, 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work introduces a novel approach to training sparse deep learning models by focusing on block-wise sparsity from initialization. The authors propose decomposing the weight matrix using Kronecker products, representing it as (S ⊙ A) ⊗ B, where S, A, and B are smaller matrices. This decomposition allows the model to learn sparse patterns efficiently through S while maintaining a compact parameter representation from the start of training. By leveraging this structure, the method achieves sparsity without the typical dense-to-sparse training pipeline. Theoretically, the authors prove that this method have the same performance of a model trained by the group LASSO or pruning technique, highlighting the improvement of training sparsely from the beginning without sacrificing performance. Additionally, the flops during forward and backward further indicates the efficiency of the proposed methods. At last, from experiments with different model architectures on MNIST and CIFAR-100, the proposed method outperforms group LASSO, iteratively pruning, and other baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I would like the authors to further compare with other factorization methods for matrix decomposition to show the advantages of the proposed method.\n2. The author should further separate the block sparsity part and Kronecker product part. Currently, it is still not clear how much each component contribute to the reduction of memory and computation during training and inference.\n3. I would like to see more experiments on model size larger than 100M or even 1B. The current model size is too small, and I don't think it is very meaningful to use sparse training for these models.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wr7dNISXtx", "reviewer": "Reviewer_DyU9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengthes：\n1. The paper introduces a new perspective on training block-wise sparse models by connecting them with Kronecker product decomposition, which is a unique contribution to the field.\n2. The authors provide a solid theoretical basis for their method, demonstrating that every block-wise sparse matrix can be represented using their decomposition without significant performance loss.\n3. Extensive empirical studies support the claims, showing substantial reductions in training parameters and FLOPs, in some cases by up to 97%, with minimal impact on accuracy.\n\nWeaknesses:\n1. The Kronecker product decomposition may introduce complexity in implementation, which could be a barrier for some practitioners. Especially, the reshape of input activations and the multiplication of inputs and Kronecker weights.\n2. The success of the method in finding the optimal block size might depend heavily on initial conditions or the specific characteristics of the data, which is not extensively discussed. Generally, the accuracy in one turn or epoch is not a good feedback for determine the pattern.\n3. The method of Kronecker product decomposition deduces the parameters and FLOPs significantly. however, the reduced calculation is similar to the low-bit quantization method, which contains low-bit multiplication and scales out of matrix multiplication. The performance of these simplified computaion methods will be reduced in contrast to general computation method, this is also verified in the experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The article presents a novel approach to training large-scale machine learning models with block-wise sparse matrices, aiming to reduce computational and memory costs specially in the training process. The authors argue that current methods for training such models are inefficient as they start with dense models and only later apply sparsity, leading to high training costs. The proposed method leverages Kronecker product decomposition to factorize block-wise sparse matrices, enabling efficient training. The article claims significant reductions in training parameters and floating-point operations (FLOPs) without compromising performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weaknesses.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "J5s43wdNtd", "reviewer": "Reviewer_dSGQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths \n- **Theoretical grounding**: The idea of using KPD for training of block-wise sparse models is straightforward and great. This study also provides a solid theoretical grounding on how block-wise sparse matrices can be represented using KPD, and what is theoretical FLOPs savings that it can achieve.\n\n- **block size selection**: It is a novel idea to find optimal block size by having multiple patterns as a regularization term. It can significantly reduce searching time or make block-size searching more systematic.\n\n### Weaknesses:\n- **Practical limitation** : Although this work has thorough theoretical grounding in regards to the reduction in training parameters, it has some practical limitations. Since LeNet-5 has 3 FC layers, 5 different patterns might be enough. However, the number of different patterns increase with the number of layers. I doubt the loss function with pattern selection would work with large K value in regularization term. If #patterns K is not scalable and has to be limited (e.g. K <= 5), then the proposed algorithm cannot find the optimal block size in one round.\n\n- **Inappropriate metric** : This study uses `FLOPs` and training parameters (`Train Param`) as metrics to indicate the reduction in training time. Lower `FLOPs` does not mean anything if it does not lead to reduced computation time. For instance Nvidia H100 supports 2:4 sparsity, where two zero weight values in contiguous block of four weight values can be efficiently accelerated. The study does not show how different block sizes can actually reduce the training time (or the step time).\n\n- **Limited scope of experiments**:\n  - The experiments uses MNIST and CIFAR-100 dataset and very outdated small neural networks such as Linear model and LeNet-5. More evaluations on large-scale datasets are needed. In particular, modifying regularization (such as this work) has a high impact on the number of training steps needed. Worse, if the training dataset is scarce, increasing the effect of regularization may lead the training to not converge at all. As pattern selection logic is part of regularization term in the equation, thorough evaluations on larger dataset and model is definitely needed to see if the new loss function with pattern selection is robust.\n  - Also for larger models and datasets, I wonder how the accuracy would drop with the proposed algorithm.\n  - VitT and Swin experiments are weak. How did you choose block-size for this experiment? Did you use pattern selection optimization or just choose one block size? You can always choose the block-size that works best for your work, but not for others, so more explanation is needed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work introduces an efficient training algorithm with block-wise sparse weight matrices. Key contributions include:\n\n  - **Matrix decomposition**: The study proposes to use Kronecker Product Decomposition (KPD) to decompose weight matrices into block-wise sparse matrices for efficient training.  It represents weight matrices with fewer parameters and reduces FLOPs.\n  - **Theoretical analysis**: The study provides theoretical grounding that any block-wise matrices can be decomposed using KPD.\n  - **Block size selection**: The study proposes an algorithm that efficiently find the optimal block size for the block-wise sparse matrices with only one round of training.\n  - **Experiments**: The study validates its work with training experiments on MNIST and CIFAR-100 datasets using linear models, LeNet-5, ViT, and Swin and claims to achieve better or similar accuracy with lower FLOPs and less training parameters.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Metrics:\n    - To claim that the proposed algorithm can reduce training time, it needs to show the training time, not just FLOPs or number of parameters. I suggest to include some training time numbers in the experiment.\n1. More experiments\n    - As discussed in Weaknesses section, I'm not convinced that this would work with larger models. (1) How does rank affect with larger model? Do we need large rank not to lose accuracy? (2) Does loss function with pattern selection would work with larger model? How do you find the optimal pattern? (3) How does added regularization terms affect the step time and convergence for larger models? Maybe you can re-use ViT and Swin experiments, but further develop it.\n1. Address limitations\n    - Add a section discussing limitations of the proposed method.\n1. Clarity (Nit)\n    - Needs consistent usage between lasso and LASSO\n    - 60 thousand -> 60,000 (p10)\n    - Change k=2 corresponds to pattern `(8,4)(4,4)(4,2)` to `(8,4)(4,4)(2,2)` (p10)\n    - **Table 4**: When discussing the impact of rank of the decomposition, why LeNet-5 is not included in this ablation experiment? Is there a specific reason?\n\n\nI really like the idea of selecting optimal block size with just one training round. If you can have some back-ups to show that it works with medium sized models that may have 10s or 100s possible sparsity patterns, that would be great.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents novel work, namely the first end-to-end block sparse training method. 
Although it relies on known ingredients, the approach is overall novel.
 Experimental results show the good performance of the proposed approach in comparison with other block sparse training method. Finally, the author provides theoretical analysis to show the effectiveness of proposed method.
Decision: Accept (poster)