An Efficient Training Algorithm for Models with Block-wise Sparsity
Ding Zhu [email protected], Zhiqun Zuo [email protected], Mohammad Mahdi Khalili [email protected] · 2025
Read An Efficient Training Algorithm for Models with Block-wise Sparsity by Ding Zhu [email protected], Zhiqun Zuo [email protected], Mohammad Mahdi Khalili [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-21928.txt.
Introduction
Ding Zhu, Zhiqun Zuo, and Mohammad Mahdi Khalili present a computing paper from 2025 on training lean models. Big learning models cost much to train and run. Making most weights zero cuts that cost, and block patterns of zeros suit fast chips best. Yet training a block-sparse model from scratch had no efficient method.
Past methods started from a full dense model, which wastes the very savings sought. The team's method trains the sparse model directly, block by block. It also finds the right block size during training, rather than fixing it in advance. Tests and theory both showed large cuts in compute and memory costs. Accuracy held level with the dense baselines. The authors say block-sparse training can now start lean from step one.
Catalog record
| CREATOR | Ding Zhu [email protected], Zhiqun Zuo [email protected], Mohammad Mahdi Khalili [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-21928
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Efficient Training Algorithm for Models with Block-wise Sparsity Ding Zhu [email protected], Zhiqun Zuo [email protected], Mohammad Mahdi Khalili [email protected] 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 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. 1 1 1 A preliminary version of this work was presented at the NeurIPS Workshop on Machine Learning and Compression ( Zhu et al., 2024 ) . Reviewed on OpenReview: https://openreview.net/forum?id=nay3Kvw8BD 1 Introduction Deep learning models have achieved remarkable success across various domains, but training these models on resource-constrained devices remains challenging due to their computational and memory requirements. To decrease memory and computational costs, sparse machine learning models have been widely used in literature. Sparse networks are mainly categorized into two groups: fine-grained sparse networks and coarse-grained sparse networks (see Figure 1 which provides an example of a fine-grained sparse weight matrix and two examples of coarse-grained sparse weight matrices). In fine-grained sparse networks, 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-grained sparse weight matrices does not fit with the hardware accelerators, and they can speed up the inference time only if the sparsity ratio is higher than 95% ( Wang et al., 2018 ; Wen et al., 2016 ) . On the other hand, coarse-grained sparse matrices are better alternatives to speed up inference ( Parashar et al., 2017 ; Han et al., 2017 ; Han et al., 2016a ) . To train coarse-grained (structured) sparse weight matrices, it is common to use iterative pruning ( Tan & Motani, 2020 ; Yu et al., 2023 ) or group lasso techniques ( Behnke & Heafield, 2021 ; Rao et al., 2015 ; Ida et al., 2019 ) . Iterative pruning works as follows. First, a sparsity pattern is defined (e.g., 2:4 sparsity ( Mishra et al., 2021 ) or channel-wise sparsity ( Liu et al., 2017 ) ). 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 are not impacting the performance of the model. Figure 1 : Examples for fine-grained and coarse-grained sparse matrices. White entries represent zero value. Then, we 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 a group) and add a regularizer for each group to the objective function. As a 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 parameters. 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 decomposition to propose a new matrix factorization technique suitable for block-wise sparse matrices. Our contributions in this work can be summarized as follows, • To the best of our knowledge, this is the first work that focuses on efficient training for block-wise sparse models. This work is also the first work that makes a 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-wise sparse matrix can be represented using our proposed decomposition resulting in no significant performance drop. • Through extensive theoretical analyses, we 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 a 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. The remainder of the paper is organized as follows. We review related work in Section 2 . We present the preliminaries in Section 3 , followed by problem formulation in Section 4 . We discuss how our algorithm can be used for optimal pattern selection in Section 5 . We present numerical results in Section 6 , and conclude in Section 7 . 2 Related Work Pruning is an effective technique for reducing model parameters and has seen tremendous progress in recent years ( Reed, 1993 ; Tanaka et al., 2020b ; Han et al., 2016b ) . Pruning generally can be divided into structured pruning ( Cai et al., 2022 ; Liu et al., 2021a ; Li et al., 2017a ) and unstructured pruning ( Dong et al., 2017 ; Sanh et al., 2020 ) . Unstructured pruning finds fine-grained sparse matrices by setting the unimportant weights to zero (See Figure 1 ). 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, on the other hand, trains coarse-grained sparse matrices leading to a decrease in the memory cost and inference time. It