Partially Frozen Random Networks Contain Compact Strong Lottery Tickets
Authors: Hikari Otsuka
Daiki Chijiwa
Ángel López García-Arias
Yasuyuki Okoshi
Kazushi Kawamura
Thiem Van Chu
Daichi Fujiki
Susumu Takeuchi
Masato Motomura
Venue: Accepted by TMLR ()

Abstract: Randomly initialized dense networks contain subnetworks that achieve high accuracy without weight learning—strong lottery tickets (SLTs). Recently, Gadhikar et al. (2023) demonstrated that SLTs could also be found within a randomly pruned source network. This phenomenon can be exploited to further compress the small memory size required by SLTs. However, their method is limited to SLTs that are even sparser than the source, leading to worse accuracy due to unintentionally high sparsity. This paper proposes a method for reducing the SLT memory size without restricting the sparsity of the SLTs that can be found. A random subset of the initial weights is frozen by either permanently pruning them or locking them as a fixed part of the SLT, resulting in a smaller model size. Experimental results show that Edge-Popup (Ramanujan et al., 2020; Sreenivasan et al., 2022) finds SLTs with better accuracy-to-model size trade-off within frozen networks than within dense or randomly pruned source networks. In particular, freezing $70\%$ of a ResNet on ImageNet provides $3.3\times$ compression compared to the SLT found within a dense counterpart, raises accuracy by up to $14.12$ points compared to the SLT found within a randomly pruned counterpart, and offers a better accuracy-model size trade-off than both.

Published in Transactions on Machine Learning Research (02/2025)
Partially Frozen Random Networks
Contain Compact Strong Lottery Tickets
Hikari Otsuka!*) +-f
örr isct ac.jp
Daiki Chijiwa?*
daiki. chijeua
Ángel López García-Arias".
lopexWiece.ory org
Yasuyuki Okoshi'
okoshi, yasuyuki@ortie. isr isci actt.
Kazushi Kawamura'
kawamur@uuricn tie. isr isc acc.p
Thiem Van Chu
thiem@ortic. ünr isct ac.jp
Daichi Fujiki'
dfujiki@ortic. ösr isct ac.jp susumuu tesumuu.lkeehhhiiniee com
Susumu Takeuchi²
Masato Motomura!
motomuro@articc.mmmmmmm itr isct ac.
Departmend of Informalion and Comamunications Engineering, Inslibute of Science Tokyo, Japan NTT Corporalion, Japun
Reviewed on OpenReview: https: opwnreview. net/ forum? id= ad=apPPfufhe
Abstract
Randomly initialized dense networks contain subnetworks that achieve high accuracy without weight learning strong lottery tickets (SLTs). Recently, Gadhikar et al. (2023) demonstrated that SLTs could also be found within a randomly pruned source network. This phenomenon can be exploited to further compress the small memory size required by SLTs. However, their method is limited to SL.Ts that even sparser than the source, leading to worse accuracy due unintentionally high sparsity. This paper proposes method for reducing the SLT memory size without restricting the sparsity of the SLTs that can be found. A random subset of the initial weights is frozen by either permanently pruning them or locking them as a fixed part of the SLT, resulting in a smaller model size. Experimental results show that Edge-Popup (Ramanujan et al., 2020; Sreenivasan et al., 2022) finds SLTs with better accuracy-to-mi toddel size trade-off within frozen networks than within dense or randomly pruned source networks. In particular, freezing 70% of ResNet ImageNet provides 3.3x compression compared to the SLT found within dense counterpart, raises accuracy by up to 14.12 points compared to the SLT found within a randomly pruned counterpart, and offers a better accuracy-model size trade-off than both.
1 Introduction
The strong lottery ticket hypothesis (SLTH) conjectured the existence of subnetworks within randomly weighted network-strow lottery tickets (SLTs)-t that achieve comparable accuracy to trained dense net- works (Zhou et al., 2019; Ramanujan et al., 2020: Malach et al., 2020). The existence of such subnetworks that do not require weight training, illustrated in Figure (left), has been demonstrated experimentally (Zhou
"Equl contribution. Correspondence to: Hikari Otsuka <otsuka. itw.rraa.........ttt..... ist..ac..t.....

---

Published in Transactions on Machine Learning Research (02/2025)
ImageNet
Optimization Target
Frozen Parameter (Pruned)
Frazen Parameter
(Locked)
Top-1 Test Acc. (%)
60
Model
45
ResNNet18
ResNet-34
ResNet-50
30
ResNet-101
v Wide ResNet-50
SLT Search Within Dense NN
SLT Within
Within
Strong Lottery Ticket
Pruned NN
Frozen NN
0.5
1.5
2.5
|Ramanujan et al., 2020]
(Gadhikar et al, 2023)
(Pruned Locked)
Model Size [MB]
(roposed]
Freezing Ratio (Pruning Ratio : Locking Ratio)
Memorize
Memorize
Memorize
0% (0.0% 0.0%)
- 77%%(65.0%% 5.0%)
20 Parameters
15 Parameters
5 Parameters
70% (70.0% 0.0%)
Figure 1: Freezing the source network by randomly pruming some parameters and locking others reduces the memorized supermask for finding an SLT.
improves the accuracy-to-mmodel size trade-off over pre- pruning only (o) or non-freezing (o).
Figure 2: Freezing
et al., 2019; Ramanujan et al., 2020: Huang et al., 2022; López García-Arias et al., 2023; Yeo et al., 2023) and proven theoretically for dense source networks (Malach et al., 2020; Orseau et al., 2020; Pensia et al., 2020; Diffenderfer & Kailkhura, 2021; da Cunha et al., 2021; Burkholz, 2022a; Burkholz et al., 2022; Ferbach et al., 2023; Gadhikar et al., 2023). They appear in networks with excessive amounts of parameters, and their existence indicates the possibility of new optimization strategics for deep neural networks based on a network connectivity perspective.
SLIs offer a particularly advantageous opportunity for specialized inference hardware (Hirose et al., 2022; Chen et al., 2022; 2023) since the random weights can be reconstructed from the seed (i.c., they do not need to be memorized), and the binary mask stte-massk- can be greatly compressed with entropy coding, vastly reducing off-chip memory access and its associated overheads. Furthermore, the binary nature of both the supermask and the random weights can be exploited for multiplier-less execution, as demonstrated practically by Hirose al. (2022).
Recently, Gadhikar et al. (2023) showed that accurate SLTs could be found even if the number of edges to be optimized was reduced by randomly pruning the source network at initialization (see Figure 1, center). Since the random pre-pruning mask can be reconstructed from the seed in the same way as the random weights, and thus there is no need to store the part of the supermask corresponding to pre-pruned weights, their approach can be exploited to further reduce the memory cost required by the SLT in specialized hardware. However, when aiming for high compression, their method can only search for SL.Ss in the relatively high sparsity region, and may even lead to layer collapse (Hayou et al., 2020; Tanaka et al., 2020). Furthermore, since the SLT sparsity regions where highly accurate SLTs exist depend the dataset and network architecture, a search limited to sparse regions may fail to find accurate SLTs. For instance, work on SLTs within graph neural networks has shown that dense SLTs are more accurate than sparse ones in some settings (Huang et al., 2022; Yan et al., 2023). Therefore, it would be desirable to use a method that allows for increased randomness in SLTs for further model compression, but has the freedom to allocate it in the SLT sparsity regions that lead to more accurate tickets.
This paper introduces such a novel method to reduce the memory cost of the optimized supermask without restricting the desired sparsity of SLTs to be searched for: in addition to random pruning at initialization, it also locks randomly chosen parameters at initialization to be permanent part of the SLT (i.e., never pruned), as exemplified in Figure 1 (right)). Both the randomly pruned and the locked parameters-the frozen parameters are left completely random and can be regenerated from seed. The weights corresponding to the optimized supermask region (less than 50% of the total) are also reconstructed from seed, and the supermask is binary and sparse, producing highly compressible model. Far from negatively impacting performance, this cost reduction efficient: as shown in Figure 2, the frozen SLTs achieve a higher accuracy than SLTs with a similar size resulting from conventional methods. The contributions of this paper summarized as follows:
2

---

Published in Transactions on Machine Learning Research (02/2025)
We propose novel method that vastly reduces the number of parameters to be memorized for finding an accurate SLT by freezing (pruning and locking) the source random nork
We experimentally validate our method in three scenarios corresponding to low, medium, and high optimal SLT sparsity regions, which reveal that parameter freezing consistently produces smaller yet accurate supermasks. Even with randomly frozen parameters, we find highly accurate SLTs that cannot be found within dense networks for some desired sparsitics.
Furthermore, the experimental results show that SLTs found in frozen networks achieve comparable or better accuracy-to-modd size tradc-off than SLTs found within dense (non-freczing) or sparse (non-locking) random networks.
As mentioned above, SLTs are quite attractive for neural engine design, they can vastly reduce the memory size for model storage, meaning that off-chip memory access by far the major bottleneck of energy and time consumption (Horowitz, 2014)-can can be drastically reduced for energy-efficient inference acceleration (Hirose et al., 2022). Our contributions have the potential to reduce off-chip memory access further and to make inference more energy-efficient than previous designs.
2
Preliminaries
This section outlines the background of strong lottery tickets (SLTs) within dense or sparse networks and SLT search algorithms.
2.1 Strong Lottery Tickets in Dense Networks
SLTs (Zhou et al., 2019; Ramanujan et al., 2020; Malach et al., 2020) are subnetworks within a randomly weighted neural network that achiove high accuracy without any weight training. Compared with learned dense weight models, SLTs can be reconstructed from a small amount of information: since the random weights can be regenerated from their seed, it is only necessary to store the binary supermask and the seed (Hirose et al., 2022). SLT scarch algorithms for deep neural networks (Zhou et al., 2019; Ramanujan et al., 2020; Zhou et al., 2021; Sreenivasan et al., 2022) find SLTs by updating weight scores, which are then used to generate the supermask, instead of updating weights. For example, the Edge-Popup algorithm (Ramanujan et al., 2020; Sreenivasan et al., 2022) used in this paper finds SLTs by applying a supermask generated from the connections with the top- scores.
SLT Existence via Subset-Sum Approximation Given set of random variables and target value, the subset-sum problem consists of finding subset whose total value approximates the target. Lueker (1998) showed that such subset exists with high probability if the number of random variables is sufficiently large:
Lemma 2.1 (Subsel-Sum Approximation (Lueker, 1998)). Let X1,..,,, X, ~ U(-1,1) be independent, uniformly distributed random variables. Then, ezcept with exponentially small probability, any z E [-1, 1] can be approrimated by subset-sum of X; is sufficiently large.
Based on this Lemma 2.1, which was first introduced into the SLT context by Pensia al. (2020), previous works (Burkholz, 2022a;b; da Cunha et al., 2021; Pensia et al., 2020) showed that an SLT that approximates arbitrary target network exists in dense source network if it is logarithmically wider and constantly deeper than the target network. In particular, Burkholz (2022a) proved that a source network with depth L+1 and larger width than the target network contains an SLT that can approximate the target network with depth L.
2.2 Strong Lottery Tickets in Sparse Networks
Recently, Gadhikar et al. (2023) revealed that SLTs also exist within sparse source networks, i.e., random networks that have been randomly pruned initialization (see Figure 1, center). They showed its existence experimentally as well as theoretically, as outlined later: an SLT that approximates a given target network exists with high probability in sparse source network that is sufficiently wider and deeper than the target.
3

---

Published in Transactions on Machine Learning Research (02/2025)
SLT Existence in Sparse Networks To prove the existence of SLTs within sparse networks, Gadhikar et al. (2023) extended the subset-sum approxination (Temma. 2.1) to the situation where randomly chosen variables are permanently pruned at initialization:
Lemma 2.2 (Subset-Sum Approximation in Sparse Networks (Gadhikar et al., 2023)). Let Xi...., Xn be as in Lemma 2.1, and M,...., Mn ~ Ber(p) be independent, Bernoulli distributed random variables with p (0, 1). Then, except with exponentially small probabilily, any Z E [-1,1] can be approrimated by a subset-sum of M,X; if n is sufficiently large.
By applying this extended lemma instead of Lemma 2.1 to the SLT existence theorem presented by Burkholz (2022a), Gadhíkar et al. (2023) proved the SLT existence in sparse networks as following theorem:
Theorem 2.1 (SLT Existence in Sparse Networks Gadhikar et al. (2023)). Let target network fr with depth L and a sparse source network fs with depth L+1 be given. Assume that the source network is randomly pruned with pruning ratio pt for each 1-th layer. Also assume that these nelworks have ReLU activation function and inittalized by using a uniform distribuution 1[- Then, exeept with exponentially small probability, a subnetwork fSLT exists in the sparse source network fs such that fSLT approzimates the torget network fI if the width of fs is sufficiently large.
Thus, by extending the subset-sum approximation lemma, the conventional SLT existence proof can be easily extended to various network settings.
3 Strong Lottery Tickets in Frozen Networks
The approach of finding SLTs within sparse networks by Gadhikar et al. (2023) offers a practical advantage: as the randomly pre-pruned parts can be reconstructed from the seed, this pre-pruning process can be exploited to reduce the memory requirement of the supermask.
However, this approach also imposes the limitation that it can only search for SLTs with a sparsity higher than the pre-pruning ratio. For example, random pre-pruning ratio of 90% vastly reduces the memory size of the supermask, but it limits the search to only SLTs sparser than 90%. Therefore, their method is incompatible with exploring the whole SLT sparsity range for optimal accuracy.
This paper proposes a novel method that allows us to find SLIs within the optimal sparsity range while still capitalizing on the compression gains offered by random connectivity initialization. We explore the performance of SLTs within a frozen source network, i.e., random network that (in addition to randomly pruned parameters) has randomly chosen parameters forced to be permanent part (i.e., never pruned) of the SLT locked parameters (see Figure 1, right). Since the random locking pattern can be reconstructed from seed in the same way as the random pro-pruning pattern, our freezing method allows us to compress SLTs further. Additionally, locking allows us to exlend the benefits of pre-pruning to the scenarios where the SLT sparsity should not be too high, e.g., as found graph neural networks (Huang et al., 2022; Yan et al., 2023).
This section first describes the construction of frozen networks and the freezing pattern encoding for model compression. Then, we perform preliminary experiment of the optimal settings for the proposed method in preparation for the evaluation experiments in Section 4.
3.1 Partial Freezing for Enhanced SLT Compression
In our method, since frozen regions in the source network are completely random and thus can be reconstructed from seed, we need to memorize only the optimized supermask region. The total amount of frozen parameters is determined by global freezing ratio F,,, which is the sum of the respective pre-pruning ratio P. and locking ratio L,. Therefore, we optimize the 1-F, F, of the parancters (i.c., non-frozen paramcters) of the original dense network. As explained previously, it is not possible to search for an SLT with a lower sparsity (denser) than the frozen source network. Consequently, as shown in Figure 3, the pre-pruning ratio P, sets the lower bound of the sparsity of the SLTs that can be found. On the other hand, is not possible to search for an SLT that prunes more parameters than those available, so the locking ratio L, sets the upper bound of the sparsity of the SLTs that can be found. (Specifically, the upper bound is given by 1- I.,.) Thus, these ratios
4

---

Published in Transactions on Machine Learning Research (02/2025)
allow to freely control the proportion of pre-pruning and locking ratios and memory size reduction ratio for the desired SL. sparsity.
Frozen network construction: We assume that the 1-th layer of network with depth L has weights w E Rn The number of frozen parame- ters is determined by the layer-wise freezing ratios (1) ....Pp.. where each py is defined as the sum of the layer-wise pre-praning ralio y and the layer- wise locking ratio Pi
Top-1 Acc.
Desired SLT Sparsity Range
Frozen Region
Frozen Region
P. (Pruned)
1 - P, (oon-Frozen)
L, (Locked)
(1) (1) (1) (1) and Pÿ .Pp .P: E [0,
SLT Sparsity
nn parameters and look pf?n!! To prune Pf
Pre-pruning and locking set the bounds of parameters, we generate two random masks, the SLT sparsity that can be found. These optimal bounds are investigated in Section 3.2.
(1)
Figure 3:
1)x()) and lock- ing mask mi E {0, 10.1) so that they satisfy Pp (n))),
pre-pruning mask m ()) {0,1)a
and (1 -1-We m,)) m m 0 (i.e., we require pre pre-pruning and lock- ing to be implemented without overlap). The layer-wise weights frozen with these masks calculated (1) ④ (1 m (()) + mm)) ()) @ w(. These masks are fixed during training, and we search for SLTs only in the parts where mp c (1 - (1-m))) (1) is one.
||| 11-ma m (9
= "e/"||=
w = (m
(1)
Setting the layer-wise ratios: Our method considers the following two existing strategies for determining the layer-wise pre- pre-pruming ratio from the desired global pre-pruning ratio of the network:
Reiis--eniiiKeeeee (ERK): The pre-pruning ratio of layer I is proportional to the scale
(c + ((l)) + k/ + k /(C(() o(l) k/ -kw ) where ((l) in C (1) and ko denote input chan- nels, output channels, kernel height, and kernel width of the layer 1, respectively (Evci et al., 2020).
Edge Per Layer (EPL): Each layer's pre-pruning ratio is set so that they all have the same number of remaining weights (Price & Tanner, 2021; Gadhikar al., 2023).
The same strategy is employed to determine the layer-wise pre-pruning and freezing ratios from their respective global ratios, and then the locking ratios are calculated as the difference between the corresponding freczing and pre-pruning ratios.
Freezing pattern encoding for model compression: The freezing pattern can be encoded during inference as a ternary mask freezing ttass indicates whether a parameter is pruned, locked, or part of the supermask. For example, encoding pre-pruning as -1, locking as +1, and supermask inclusion as 0, the layer-wise freezing mask can be encoded as m, + (m (2) - 1) {-1, 1] 1)a(). Since this freezing mask is also random and fixed, it can be regenerated from its seed and ratios, similarly to the random weights. Furthermore, the supermask size is roduced by excluding from it the frozen parameters, so the SLTs found by this method can be compressed in inference to an even smaller memory size than those produced by the existing SLT literature (Hirose et al., 2022; Okoshi al., 2022; López García-Arias et al., 2023), reducing costly off-chip memory access on specialized neural inference accelcrators (Hirose et al., 2022; Chen al., 2023), and thus offering opportunity to perform even faster and more energy-efficient inference processing.
3.2 Optimal Pruning:Locking Proportion for Freezing
Here, we perform a preliminary investigation of the optimal pruning:locking proportion for each given desired SLT sparsity by varying the proportion with fixed freezing ratio of the network. Figure explores different. configurations of 80% freezing ratio- the situation where the supermask memory size is 20% of the SLT in the dense source network-oo Conv6 network and compares the performance of the found SL.Ss on
5

---

Published in Transactions on Machine Learning Research (02/2025)
CIFAR-10. As expected, the best best-performing SLT of each prune:lock configuration is found at the center of the non-frozen region, where the number of candidate subnetworks is maximized. In other words, when the non-frozen region accounts for S E [0, 1] of the entire source network, the optimal SLT sparsity is k = P where P. =E (1) n Ex (8) is the global pre-pruning ratio of the network. Conversely, for a given freezing ratio F, of the network and desired SLT sparsity k, the optimal position of the frozen region is set by the pre-pruiing ratio P. k (1 F2 and the corresponding locking ratio L, F. Pr. In the cases where this would result in P. < 0 or L, <0 we choose best-effort approach that keeps the desired freezing ratio and sets the bounds to P. 0 or I,p 0,, respectively.
Additionally, Figure 4 compares the two strategies for setting ratios considered in Section 3.1, showing that EPL outper- forms ERK in all cases. Consequently, hereafter, the proposed method sets the global ratios in order to position the frozen region center as close as possible to the desired SLT sparsity, and then sets the layer-wise ratios using EPL.
CIFAR-10
Top-1 Test Acc. [%]
65
50
3.3
SLT Existence in Frozen Networks
One question comes to mind here: does SLT erist that ap- prozimales given largel network, even if the paramelers are randomly frozen (t.e., pruned or locked) in advance? It has been shown by Gadhikar et al. (2023) that an SLT that approximates a given target network exists in the pre- pre-pruned source network the source network is sufficiently wider and deeper than the target, but it not known whether such an SLT exists in the situation of a frozen source network. Here, we provide a rough theoretical result indicating that an SLT capable of approximating target network cxists in frozen network with sufficiently large width. This result is proved by extending the subset-sum approximation lemma (Lemma 2.1) to the case where some parameters are locked (for detailed proof, see Appendix A).
35
10
30
50
70
90
SLT Sparsity [%]
Pruning Ratio [%) Locking Ratio [%)
0 80
20 60
+00 40 -60 20
80:
10: 70
- 30 50
50 :0 - 700 10
EPL
ERK
Figure 4: Different prune:lock proportions of 80% freezing ratio using a Conv6.
Lemma 3.1 (Subset-Sum Approximation in Randomly Locked Networks). Let X1.-.., Xn be in Lemma 2. 1, and M,,..,, M₁ Ber(g) be independent, Bernoulli distributed random variables with E (0, 1). Then, ezcept with exponentially small probability, any E [-1,1] can be approzimated by the sum of Ei= MiX, and subset-sum of (1 X if n is sufficiently large.
Then, by using the same proof procedure as Lemma 3.1, we extend the subsct-sum approximation to the situation where some random variables are frozen (i.e., pruned or locked).
Lemma 3.2 SSubset-Sum Approximation in Frozen Networks). Let XI,..., be as in Lemma 2.1, MI..., Mn ~ Ber(p) be as in Lemma 2.2, and Mi...., M', ~ Ber(q) be as in Lemma. 3.1. Then, ex- cept with exponentially small probability, any = E [-1, can be approzimated by the sum of M,M,, and a subset-sum of M, - X,), if n is sufficiently large.
Finally, by applying Lemma 3.2 to the Theorem 2.5 in Gadhikar et al. (2023) instead of Lemma 2.2, it follows that an SLT approximating a target network exists within a frozen network.
Theorem 3.1 (SLT Existence in Frozen Networks). Let target network ST with depth L and partially frozen source network fs with depth L+1 be given. Assume that the source network is randomly frozen with pruning ratio Pt and locking ratio qi for each 1-th layer, except for 0-th and 1-st layers. Also assume that these networks use the ReLU activation function and are initialized with a uniform distribution U[-1, (, 1]. Then, except with exponentially small probability, subnetwork fsur erists in the frozen source network fs such that fSLT approzimates the target network fr if the width of fs is sufficiently large.
Note that this thoorem intended to provide an existential guarantee for the question raisod at the boginning of this subsection, whether the freezing operation hurts the existence of SLTs that can approximate an arbitrary network; thus, we do not focus the sharpness of the probability bound to keep the results simple.
6

---

Published in Transactions on Machine Learning Research (02/2025)
Freezing Ratio [%)]
90
Top-1 Test Acc. [%6]
70
90
68
88
75
66
70
64
50
70
10
SLT Sparsity [%)
SLT Sparsity [%)
SLT Sparsity [%)
(a) Conv6 (CIFAR-10)
(b) ResNet-18 (CIFAR-10)
(c) GIN (OGBN-Arxiv)
Figure 5: Impact of the freezing ratio on different archilectures. Pruning and locking ratios are set following Section 3.2.
Nevertheless, proving sharper bounds may lead to capturing the effect of the freezing operation, which left for future work.
4 Experiments
This section demonstrates that freezing reduces the SLT memory size in a broad range of situations by evaluating it image classification and graph node classification. We evaluate the impact of the freezing ratio various network architectures, identifying three scenarios. Then, we explore trade-offs between accuracy and model memory size for different network widths and architectures.
4.1 Experimental Settings
We evaluate the SLIs within frozen networks image classification using the CIFAR-10 (Krizhevsky, 2009) and ImageNet (Russakovsky et al., 2015) datasets, and on node classification using the OGEN-Arxiv (Hu et al., 2020) dataset. CIFAR-10 and ImageNet. train data are split into training and validation sets with a 4:1 ratio, while for OGBN-Arxi we use the default set split. We test the models with the best validation accuracy and report the mean three experiment repetitions for CIFAR-10 and OGBN-Arxiv, and the result of one experiment for ImageNet. The standard deviation of experiments conducted more than once is plottod error bars
For image classification employ the VGG-like Conv6 (Simonyan & Zisserman, 2014; Ramanujan al., 2020), ResNet (He et al., 2016), and Wide ResNet (Zagoruyko & Komodakis, 2016) architectures, and for graph node classification the 4-layer modified GIN (Xu et al., 2019) architecture in Huang et al. (2022), all implemented with no learned biases. ResNet and GIN use non-affine Batch Normalization (loffe & Szegedy, 2015), while Conv6 has no normalization layers. Random weights are initialized with the Kaiming Uniform distribution, while weight scores are initialized with the Kaiming Normal distribution (He et al., 2015).
SLTs are scarched using extension of Edge-Popup (Ramanujan et al., 2020) that enforees the desired SLT sparsily globally instead of per-layer (Sreenivasan el al., 2022). On CIFAR-10, scores are optimized for 100 epochs using stochastic gradient descent with momentum 0.9, batch size 128, weight decay 0.0001, and initial learning rates of 0.01 and 0.1 for Conv6 and ResNet-18, respectively. On ImageNet, scores are optimized by the same setting as ResNet-18 on CIFAR-10, but a 256 batch size. On OBGN-Arxt scores are optimized for 400 epochs using AdamW (Toshchilov Hutter, 2019) with weight. decay 0.0001 and initial learning rate 0.01. All experiments use cosine learning rate decay (Loshchilov & Hutter, 2017). These can be adequately verified with two NVIDIA H100 SXM5 94GB GPUs.
4.2 Varying Desired SLT Sparsity Different Freezing Ratios
This section investigates the effect of the freezing ratio of the network on desired SLT accuracy. We identify three scenarios, represented in Figure 5.

---

Published in Transactions on Machine Learning Research (02/2025)
Weight Init.
SKCC
Width
0.2.x
Top-1 Test Acc. [96]
85
90
65
85
55
65-
45
55
70
0.01
0.1
0.01
0.1
0.01
0.1
Model Size [MB]
Model Size [MB]
Model Size [MB]
Freezing Ratio (Pruning Ratio Locking Ratio)
Freezing Ratio (Pruning Ratio Locking Ratio)
Freezing Ratio (Pruning Ratio Locking Ratio)
0% (0.0%
50%(25.0%% 25. 0%)
(0.0%
-8%((82.5% 225%%)
-% 10.0% 0.0%) 50%(0.0% 0%)
(45.0% 0.0%)
630.3%%%% 30. 0%)
85% (85.0% 0.0%) 90%((85.0%, 5.0%%)
15% (15.0% 0.0%) 60%(0.0% 60. 0%)
(a) Conv6 (SLT Sparsity 50%)
(b) ResNet-18 (SLT Sparsity 90%)
(c) GIN (SLT Sparsity 20%)
Figure 6: Compared to sparse (+) or dense (+) source networks, freezing achieves better accuracy-to model
memory size trade-off (top-left is better).
In the cases where the optimal SLT sparsity is found at intermediate sparsity e.g,, around 50% for Conv6 in Figure 5a pa-pruning and locking can be applied with equally high ratios. Results show that the supermask memory size can be reduced by 40% with a small impact on accuracy, and by 70% with still a moderate accuracy drop of 5 points.
Applying the much larger ResNet-18 18 to the same task results in much stronger overparametrization. Therefore, optimal SLIss are found in the higher sparsity range, as revealed by Figure 5b, benefiting from much higher pruning than locking. Even though 90% of the memory size is reduced in this scenario, can find 90% sparse SLTs with 88.1% accuracy.
As an example of the scenario where optimal SLT sparsities are found in the denser range, benefiting from a higher locking ratio, we evaluate GIN in Figure 5c. Compared with the best-performing SLT found in the dense GIN, of 70.1% accuracy and 20% sparsity, by freezing 50% of the memory size, our method finds similarly performing SLTs of 69.8% accuracy with 40% sparsity.
Interestingly, with low SLT sparsity (e.g., 10% sparsity) in all three scenarios, despite the reduced parameters to be optimized, SLIs within frozen networks achieve higher accuracy than SLIs within dense networks. These results imply that parameter freezing at an appropriate ratio has the effect of avoiding the inclusion of low-grade local optimal solutions the search space. While searching for SLTs in a dense network by Edge-Popup leads to convergence to a local optimal solution (Fischer & Burkholz, 2022), a moderate random parameter freezing may roduce the number of less accurate local optimal solutions and facilitate convergence to more accurate local optimal solution within the reduced search space. In other words, we conjecture that if the network is properly frozen, the local optimal solution for the reduced search space is close to the global optimal solution of the entire search space.
4.3 Accuracy-to-Model Memory Size Trade-Off
The freezing mask compression scheme proposed in Section 3.1 allows to reduce the model memory size during inference by regenerating both the random weights and the freezing mask with random number generators. Here consider this compression and investigate the accuracy-to-modd size trade-off offered by the SLTs found in the frozen networks. Model size refers to the total memory size of model parameters that need to be stored. The random weights and the frozen parts of the supermask are excluded, since they can be regenerated from seed, whereas each non-frozen element of the supermask and each learned batchnorm parameter are counted as 1 and 32 bits, respectively. Furthermore, we also compare the Kaiming Uniform (KU) weight initialization used so far with the binary weights provided by the Signed Kaiming Constant. (SKC) initialization (Ramanujan al., 2020), which can be exploited for reduced computational cost in neural engines (Hirose et al., 2022). For SKC, scale weights by 1/v1 kj, where is the sparsity of each
8

---

Published in Transactions on Machine Learning Research (02/2025)
layer, as proposed by Ramanujan et al. (2000). Note that since we are interested in the accuracy of the SLTs compressed as much as possible obtained by each method, the pre-pruning ratio for the pruning-only case is determined as (target sparsity - 5)% to compress the SLT as much as possible while allowing to search for SLTs. On the other hand, we evaluate freezing with a higher compression ratio than pruning only. This setting means we evaluate our method under more strict conditions than pruning-only from the compression ratio perspective.
Figure 6 explores varying the width of the source network to analyze its impact on accuracy and model size. SLT sparsity is fixed to that of the best performing SLT found in dense source network in Figure 5: 50% in Conv6, 90% in ResNet-18, and 20% in GIN. Compared to the SLTs found in densc or sparse source networks, SLTs found by our method achieve similar or higher accuracy for similar or smaller model size, thus improving the accuracy-to to-y-del size trade-off in all scenarios.
Empirically, is known that SLTs within an SKC-initialized dense network achieve better performance than with continuous random weights (Ramanujan et al., 2020; Okoshi et al., 2022; López Gareía Arias et al., 2023; Yan et al., 2023). Our results show that such trend can also be observed in frozen source networks. Nonetheless, in all source networks, we find that this improvement is smaller the wider the source network is, suggesting that the requirement for source networks of larger width is weaker in the case of binary weights.
4.4 ImageNet Experiments
Finally, we evaluate our method using larger models on large-scale dataset: deeper and wider ResNets on ImageNet. Since SLTs with 80% sparsity achieve the highest accuracy in dense source ResNet-50 (for details, see Appendix B.1), we compare the three methods using 80% SL. sparsity.
Figure compares the accuracy-to-motke size trade-off in finding the 80% sparsity SLTs between the proposed and conventional methods with SKC using ImageNet. Despite the more challenging setting and the significant 70% memory size reduction, our method (green) finds SLTs that are more accurate than pre-pruning-only methods (orange) for the same model size. This result demonstrates that the effective combination of parameter pruning and locking at initialization can improve the SLT memory elficiency even on large-scale datasets and models.
4.5 Result Analysis
Table summarizes the presented results and compares the proposed method to weight training and SLT search in dense and sparse source networks for the same network architecture and SLT sparsity. As described in Scction 4.3, the model size is calculated as the sum of the unfrozen partial supermask (1 bit/ cat//arameter) and the batch normalization paramelers (32 hiss/praametrr Also, as described in Section 4.2, the target SLT sparsity is fixed to that of the best-performing SLT found in a dense source network, and we determine the pre-pruning ratio in sparse network as (SLT sparsity 5)% for high compression.
In the case of Conv6, compared to weight. training our method provides reductions of 66.4x of the model size, in exchange of a small accuracy drop. Compared to the SLT found in the sparse source network, the SLT found in the frozen source network achieves much higher accuracy.
Even in the more challenging case of ResNet- SLTs found in a frozen network are 250.8x smaller than the trainod-weight model. When comparing SLTs found in sparse and frozen networks with the same 85% freezing ratio, the accuracy is almost equivalent, demonstrating that the inclusion of locking does not introduce a degradation in accuracy even in the scenario that benefits more from pruning.
Interestingly, the SLT found in the frozen GIN model achieves comparable accuracy to the trained-weight network, even though the model size is reduced by 40.3x. The SLT found within dense network also achieves accuracy comparable to that of the trained-weight network, but the SLT found by our method is smaller. Generally, graph neural networks (GNNs) suffer from a generalization performance degradation due to the smoothho problem Li et al. (2018). Searching for SLTs within dense GNNs has been shown to mitigate the over-smoothing problem Huang et al. (2022) and achieve higher accuracy. As our method is
9

---

Published in Transactions on Machine Learning Research (02/2025)
Table Comparison between trained- networks and SLTs found in dense, sparse, and frozen networks.
CoNv6 & CIFAR-10
Method (Source Net.)
Weight Init.
Sparsity
Pruning Ratio [%]]
Locking Ratio [7]]
Top-1 Test
Model
[%]]
Acc. [%]]
Size [MB]
Weight Training
KU
87.1
8.63
SLT (Dense)
SKC
50
86.2
0.27
SLT (Sparse)
SKC
50
45
0
66.7
0.15
SLT (Frozen)
SKC
50
25
25
84.8
0.13
RESNET-18 & CIFAR-10
Weight Training
KU
92.4
42.63
SLT (Dense)
SKC
90
0
91.0
1.37
SLT (Sparse)
SKC
90
85
0
89.9
0.24
SLT (Frozen)
SKC
90
82.5
2.5
89.8
0.24
SLT (Frozen)
SKC
90
5
88.9
0.17
GIN & OGBBN-RRS
Weight Training
KU
70.1
1.452
SLT (Dense)
SKC
20
0
70.0
0.054
SLT (Sparse)
SKC
20
15
0
62.3
0.047
SLT (Frozen)
SKC
20
40
69.2
0.036
RESNET-50 & IMAGENET
Weight Training
KU
74.4
97.49
SLT (Dense)
SKC
80
0
0
66.8
3.24
SLT (Sparse)
SKC
80
70
0
47.1
1.11
SLT (Frozen)
SKC
80
65
5
55.2
1.11
RESNET-34 & IMAGENET
SLT (Dense)
SKC
80
0
62.5
2.66
SLT (Sparse)
SKC
80
40.7
0.84
SLT (Frozen)
SKC
80
65
5
51.2
0.84
RESNET-IE 18 & IMAGENET
SLT (Dense)
SKC
80
0
54.0
1.43
SLT (Sparse)
SKC
80
70
0
25.2
0.45
SLT (Frozen)
SKC
80
65
5
39.4
0.45
WIDE RESNET-50 IMAGENET
SLT (Dense)
SKC
80
0
0
70.8
8.46
SLT (Sparse)
SKC
80
70
0
57.7
2.72
SLT (Frozen)
SKC
80
65
5
63.9
2.72
similarly accurate compared to dense networks, it is possible that parameter freezing offers an even stronger solution to the over-smoothing problem.
Although the ImageNet experiment falls into the scenario where a relatively sparse SLT more accurate (like the ResNet-18 experiment on CIFAR-10), the SLT found in sparse network is significantly loss accurate. On the other hand, the inclusion of parameter locking shows significant improvement in SLT accuracy. These results suggest that the number of highly accurate SLT patterns decreases the difficulty of the problem increases, and the pruning:locking proportion affects the performance of the found SLTs more severely.
10

---

Published in Transactions on Machine Learning Research (02/2025)
5 Limitations
Our results have the following limitations: 1) Although the proposed method can effectively reduce the model memory size for inference in principle, actual hardware implementation remains for future work. The previous work of the SLT-specialized neural engine, Hiddenite Hirose et al. (2022), would be a promising direction for such futurr implementation. 2) This paper provides thcoretical support for the existence of SLTs in frozen networks, but it does not provide their superiority in the approximation capability compared random pruning, special case of random freezing, which may depend the sparsity nature of target. networks. Also, the theoretical consideration of the appropriate proportion of these ratios is left for future work. 3) Even though we demonstrate our method on various model architectures including CNNs, ResNet familics and GIN in Section 4, following previous SLT work (Zhou et al., 2019; Ramanujan et al., 2020; López Garcfa-Arias et al., 2023; Huang et al., 2022; Yan et al., 2023), we have to leave it for future work to apply our method to Transformers (Vaswani et al., 2017) because SLT itself has not yet been established for Transformers.
6 Conclusion
This paper capitalizes on the fact that pre-pruning a randomly weighted network reduces the supermask memory size, but identifies that doing so limits the search to suboptimal sparsity region. This problem is tackled by freezing (i.e., pruning or locking) some paramcters at initialization, excluding them from the search. Freezing allows to the search for SLTs in the optimal sparsity region, while further reducing the model size. Experimental results show that SLTs found in frozen networks improve the accuracy-lo-mood size trade-off compared to SLTs found in dense (Ramanujan et al., 2020; Sreenivasan et al., 2022) or sparse networks (Gadhikar et al., 2023). Interestingly, although for weight training random paramcter locking has only been found useful for reducing accuracy degradation in network compression (Zhou et al., 2019; Wimmer al., 2020), we identify scenarios in SLT training where they can be used for raising accuracy. Our method can be interpreted as being capable of generating more useful SLT information from random seed than previous methods, offering opportunity for reducing off-chip memory access in specialized SLT accelerators (Hirose et al., 2022). Additionally, the reduced number of parameters to be optimized may be exploited for training cost reduction. Appropriate freezing may improve the SLT search efficiency, including preventing convergence to local low-precision solutions as experimentally confirmed in Section 4.2, and improving convergence speed through reduced parameters to be optimized. Investigations about the SLT search efficiency remain as future work.
Acknowledgments
This work was supported in part by JSPS KAKENHI Grant Number JP23H05489 and JST-ALCA-Next Japan Grant # JPMJAN24F3.
Impact Statements
This paper presents work whose goal is to advance the field of machine learning. Among the many potential societal consequences of our work, highlight its potential to reduce the computational cost of inference of neural networks, and thus their energy consumption footprint.
References
Rebekka Burkholz. Most activation functions can win the lottery without excessive depth. Proc. Adv. Neural Inform. Process. Syst., 35:18707-18720, 2022a.
Rebekka Burkholz. Convolutional and residual networks provably contain lottery tickets. In Proc. Int. Conf. Mach. Learn., pp. 2414-2433. PMLR, 2022b.
Rebekka Burkholz, Nilanjana Laha, Rajarshi Mukherjee, and Alkis Gotovos. On the existence of universal lottery tickets. In Proc. Inl. Conf. Learn. Repr., 2022.
11

---

Published in Transactions on Machine Learning Research (02/2025)
Yiming Chen, Guodong Yin, Mingyen Lee, Wenjun Tang, Zekun Yang. Yongpan Liu, Huazhong Yang, and Xueqing Li. Hidden-ROM: A compute-in-rom architecture to deploy large-scale neural networks on chip with flexible and scalable post-fabrication task transfer capability, In Proc. IEEE Int. Conf. Comput.-Aide Design, pp. 1-9, 2022.
Yung-Chin Chin Chen, Shimpei Ando, Daichi Fujiki, Shinya Vakamaeda-Yanaaakki and Kentaro Yoshioka. HALO- CAT: A hidden network processor with redivation-lccalize CIM architecture and layer-penetrann tiling. Xrvi preprint Xrx:2291 2. 060086, 2023.
Arthur da Cunha, Emanuele Natale, and Laurent Viennot. Proving the lottery ticket hypothesis for convolutional neural networks. In Proc. Inl. Conf. Learn. Repr., 2021.
James Diffenderfer and Bhavya Kailkhura. Multi-prize lottery ticket. hypothesis: Finding accurale binary neural networks by pruning a randomly weighted network. In Proc. Int. Conf. Learn. Repr., 2021.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In Proc. Int. Conf. Mach. Learn., pp. 1943-2952 PMLR, 2020.
Damien Ferbach, Christos Tsirigotis, Gauthier Gidel, and Joey Bose. A general framework for proving the equivariant strong lottery ticket hypothesis. In Proc. Int. Conf. Learn. Repr., 2023.
Jonas Fischer and Rebekka Burkholz. Plant 'n' seek: Can you find the winning ticket? In Proc. Tnt. Conf. Learn. Repr., 2022.
Advait Harshal Gadhikar, Sohom Mukherjec, and Rebekka Burkholz. Why random pruning is all we need to start sparse. In Proc. Ind. Conf. Mach. Learn., pp. 10542 10570. PMLR, 2023.
Soufiane Hayou, FranFFraccois Ton, Arnaud Doucet, and Yee Whye Teh. Pruning untrained neural networks: Principles and analysis. arXiv preprint Xrxi::200 200::002.08797,, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- level performance on ImageNet classification. In Proc. IEEE Int. Conf. Comput. Vis., pp. 1026-1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proc. IEEE Comput. Soc. Conf. Comput. Vis. and Pottern Recognit., pp. 770-778 2016.
Kazutoshi Hirose, Jaehoon Yu, Kota Ando, Yasuyuki Okoshi, Ángel López García- Junnosuke Suzuki, Thiem Van Chu, Kazushi Kawamura, and Masato Motomura. Hiddenite: 4K-PE hidden network inference 4D-tensor engine exploiting on-chip model construction achieving 34.8-to-18 16.016.0 TOPS W for CIFAR-100 and TmageNet. In Proc. IEEE Int. Solid-State Circuits Conf., volume 65, pp. 1-3. IEEE, 2022.
Mark Horowitz. 1.1 computing's energy problem (and what we can do about it). In Proc. IEEE Int. Solid-State Circuits Conf., pp. 10-14, 2014. doi: 10.108//SSSCC.21145557333
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Proc. Adv. Neural Inform. Process. Syst., 33:22118-2211 2020.
Tianjin Huang, Tianlong Chen, Meng Fang, Vlado Menkovski, Jiaxu Zhao, Lu Yin, Yulong Pei, Decebal Con- stantin Mocamu, Zhangyang Wang, Mykola Pechenizkiy, and Shiwei Liu. You can have better graph neural networks by not training weights at all: Finding untrained GNNs tickets. In Learn. of Graphs Conf., 2022.
Sergey Toffe and Christian Szegedy. Batch normalization: Accolerating deep network training by reducing internal covariate shift. Proc. Int. Conf. Mach. Learn., pp. 448 456. pmlr, 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, Toronto, 2009.
12

---

Published in Transactions on Machine Learning Research (02/2025)
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Proc. AAAT Conf. on Arlij. Intell., volume 32, 2018.
Ángel López Garcia-Arias Yasuyuki Okoshi, Masanori Hashimoto, Masato Motomura, and Jachoon Yu. Recurrent residual networks contain stronger lottery tickets. IEEE Access, 11116588116044 2023. doi: AAA100//ACCESS.2223.2224224
llya Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In Proc. Int. Conf. Learn. Repr., 2017.
Πya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In Proc. Int. Conf. Learn. Repr., 2019.
George S Lucker Exponentially small bounds on the expected optimum of the partition and subset sum problems. Random Struct. Algor., 12(1):51-60) 62, 1998.
Eran Malach, Gilad Yehudai, Shai Shalev-Schwarlzz and Ohad Shamir. Proving the lottery ticket hypothesis: PMLR, 2020.
Pruning all you need. In Proc. Int. Conf. Mach. Learn., pp.
Yasuyuki Okoshi, Angel López Arias, Kazutoshi Hirose, Kota Ando, Kazushi Kawamura, Thiem Van Chu, Masato Motomura, and Jachoon Yu. Multicoated supermasks enhance hidden networks. In Proc. Inf. Conf. Mach. Leurn., pp. 17045 17055, 2022.
Laurent Orscau, Marcus Hutter, and Omar Rivasplata. Logarithmic pruning is all you need. Proc. Adv. Neural Inform. Process. Syst., 33:2925-2990 2934, 2020.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Optimal lottery tickets via subset sum: Logarithmic wee-paarametrrization is sufficient. Proc. Adv. Neural Inform. Process. Syst., 33:2599-200 2610, 2020.
Tlan Price and Jared Tanner. Dense for the price of sparse: Improved performance of sparsely initialized networks via subspace offset. In Proc. Int. Conf. Mach. Learn., pp. 8620 8629, PMLR, 2021.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's hidden in a randomly weighted neural network? In Proc. IEEE Comput. Soc. Conf. Comput. Vis. and Pallern Recognil., pp. 11893 11902, 2020.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. ImageNet large scale visual recognition challenge. Int. J. Comput. Vis., 115:211-222, 2015.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint ar 1409: 2014.
Kartik Sreenivasan, Jy-yong Sohn, Liu Yang, Matthew Grinde, Alliot Nagle, Hongyi Wang, Eric Xing, Kangwook Lee, and Dimitris Papailiopoulos. Rare gems: Finding lottery tickets at initialization. Proc. Adv. Neural Inform. Process. Syst., 35:14529 145400, 2022.
Hidenori Tanaka, Daniel Kunin, Daniel Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Proc. Adv. Neural Inform. Process. Syst., 33:6377-6389, 2020.
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-officient image transformers & distillation through attention. In Proc. Int. Conf. Mach. Learn., pp. 10347-10357. PMLR, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Proc. Adv. Neural Inform. Process. Syst., 30, 2017.
Paul Wimmer, Jens Mehnert, and Alexandru Condurache. Freezenet: Full performance by reduced storage costs. In Proc. Asian Conf. Comput. Vis., 2020.
13

---

Published in Transactions on Machine Learning Research (02/2025)
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proc. Tnl. Conf. Learn. Repr., 2019.
Jiale Yan, Hiroaki Ito, Ángel López Carcia-Arias Yasuyuki Okoshi, Hikari Otsuka, Kazushi Kawamura, Thiem Van Chu, and Masato Motomura. Multicoated and folded graph neural networks with strong lottery tickets. In Learn. of Graphs Conf., 2023.
Sangyeop Yeo, Yoojin Jang, Jy-yong Sohn, Dongyoon Han, and Jaejun Yoo. Can we find strong lottery tickets in generative models? In Proc. AAAI Conf. on Artif. Intell. volume 37, pp. 3267-3275, 2023.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXi::1605.0711 07146, 2016.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. Proc. Adv. Neural Inform. Process. Syst., 32, 2019.
Xiao Zhou, Weizhong Zhang, Hang Xu, and Tong Zhang. Effective sparsification neural networks with global sparsity constraint. In Proc. IEEE Comprul. Soc. Conf. Comput. Vis. and Pallern Recognil., pp- 3599 3608, 2021.
14

---

Published in Transactions on Machine Learning Research (02/2025)
A Proof for Strong Lottery Tickets (SLTs) Existence in Frozen Networks
This section describes the proofs of the lemma and theorem introduced in the manuscript.
We first extend the lemma of the subset-sun approximation shown by Lueker (1998) to the case where some random variables are always included in the subset-sum.
Lemma A.1 (Subset-Sum Approsimation in Randomly Locked Networks). Let XI.... Xn ~ ((-1,1) 1) be independent, uniformly distributed random variables, and M1,'.. Mn ~ Ber(q) be independent, Bernoulli distribuled random variables with q E (0, 1). Lel 0 < e, < 1. Then, with probabilily at least 6, for any [-1, 1], there erist indices {1,-.. ,n} such that - -i=1 M,X;- - (1 -M,)x S E
C"
n 2 C log
(1)
Eδ
where C, C" > O are constants, and C depends on
Proof. Let M Mn ~ Ber(g) and m == E; Ms. By Hoeffding's inequality, we have
P (Im qnl S EM/) 2 1 - 2 exx (-r7r
(2)
for Ear > O. Thus, if we set n log(2/8) and Eas == min(g.1-9 33
we have
2
(2g B)n & m S Bn
(3)
with 8 == 9 + eM = min( 3g 1+9) E (0, with probability at least. 1 - 5. Tn particular, the number of non-vanishing terms in the sum Eie (1 - M; is n m 2 (1 3) as long each X; is non-zero.
2
Now fix Mr.... Mn ~ Ber(g) with (2q - 8)n I m < An. The goal is to approximate 2 E [-1,1] and En_ M,X; by subset sum from {(1 - X, M, = 00. For simplicity, we split it into two parts:
(1-M)), : M, = 0} = (Xi,-. X,, ,X,,,,
(4)
where the former part is used for approximating E [-1, 1] and the latter part for approximaling Em. M.X.. To approximate = E [[1, 1}, we can directly apply Corollary 2.5 from Lueker (1998):
Vz [= (1, ,.. st. --- ΣxI Se 2 2-8 8
(5)
IE1
whenever ni 2 4C log((8/))).
To approximate Σ M,X,; we have to evaluate its norm. By Hoeffding's inequality on X''s with M, + 0,
we have
P M,X, am) 21 21 (-30) 3a²m
(6)
2
for any fixed a O, whose value will be specified later. Thus Em MiX; I am aßn holds with 2log(2/5) is enough.
probability at least - whenever m
2log(2/6) Since m S 8n holds, n 2 3a-8
3a²
From the proof of Corollary 3.1 in Lucker (1998), for any 7 (0. we know that
P V2 E [-792, m2), 31 C (1,..., s.l. | Σ X Se
(7)
iel
- 2
2 1 - 5- 2exp
(8)
32
15

---

Published in Transactions on Machine Learning Research (02/2025)
whenever ne 2 2C 2C'og( (x) Thus if
n2 2 max
22Clog
2 Ed
C'
log (5))
C"
(9)
(1 - 47)2
holds, we can approximate any E [-mm,, y22 by subset sum of X", X with probability 1 26.
1-0 and y = } the assumption is satisfied Now we assume (a:/7)m S ng. For example, if we set a = 10-3
when we split {(1- - -M,) by n1 = n2 = (1-0)m in (4). Then the approximation (7) can be applied to = = EE M,X; with high probability since E 2
M.Xi| S am S a,8n S 702 holds.
By combining (5), (6), (9) with the fact that n m + n1 n2; and replacing and 8 with e/2 and 6/6, rospectively, we obtain the desired results.
By similar arguments as in Lucker (1998) or Pensia et al. (2020), can easily generalize Lemma A.1 1.1 to the case where the distribution followed by X; contains the uniform distribution. Also, by using the saine proof procedure, we can prove the following extension of Lemma A.1:
Lemma A.2 (Subset-Sum Approximation in Frozen Networks.). Lel XI...,, Xn be independent, uniformly distributed random variables so that X ~ 1),, MI...,,M, Mr be independent, Bernoulli distributed random variables so that M; ~ Ber(p) for p E (0, 1), and M1. M2 be independent, Bernoulli distributed random vari- ables so that M2- ~ Ber(g) for q E (0, 1). Let E, E (0, 1) be given. Then for any 2 E [-11,] there exists a subset I S nI. so that with probability at least 1 we have -E M,M,X, - Eiee Mj (1 M;) X, S 8 if
n 2 C' log
(10)
where C, C" > O are conslants, and C depends on p and q-
These corollaries seem to be derived by taking == 2 Ei= M,X; as the target of the Lucker (1998) and Gadhikar et al. (2023) corollaries. However, it cannot. Their corollaries need the target to be deterministic and have constant bounds. On the other hand, since Σ M.X, is stochastic, z' is a stochastic value, and the bounds of z are not constant. Therefore, z' cannot be directly assigned to the conventional corollaries, and our approach is necessary for proofing the subsot-sum approximation with frozen variables.
Finally, by these extended lemmas, we can prove the SLT existence within the frozen network with sufficiently large width.
Theorem A.1 (SLT Existence in Frozen Networks). Let D be input data, fr be a target network with depth L, and is be source network with depth L 1, Os be a parameter of fs, and pt, q E (0, 1). Assume that these networks have ReLU activation functions, and each element of 0s is uniformly distributed over [-1, 1). Also assume that 0g is randomly pruned and locked with pruming ratio and locking ratio q for each 1-th layer, except for 0-th and 1-st lagers. Then, with probobility at least 1 1- 8, there exists a binary mask mg so that each oulput component i is approsimaled as max [l/T,((r)) (s. Os @ ms)ll < if
Ci
nss,1 2 C2
min(Er,
NT.b.
(121)
(11)
C% d
ns,0 2 Co log
(1=0)
(12)
min 8/p)
where Ct, Cf > are constants, and each Ct includes pt and q, ezcept for 0. Also, El and p are as defined in Burkholz (2022a); Gadhikar et al. (2023).
Proof. By following the proof procedure of Gadhikar et al. (2023) using our Lemma A.2 instead of Lemma 2.4 in Gadhikar et al. (2023), we can obtain the desired result extension of Theorem 2.5 in Gadhikar et al. (2023).
16

---

Published in Transactions on Machine Learning Research (02/2025)
B Additional Experimental Results
B.1 Accuracy of SLT within Dense ResNet-50
This section introduces the preliminary experiment used for determining the main experimental setup. Figure 7 compares the accuracy of SLTs within a dense ResNet-50 source at different SLT sparsity using ImageNet. The SLT with 80% sparsity the most accurate, reaching 66.8% accuracy.
ImageNet
Top-1 Test Acc. [%]
70
50
30
10
SLT Sparsity [%]
Figure 7: Accuracy comparison of SLTs of different sparsity within dense ResNet-50 ImageNet.
B.2 Accuracy of SLT within Transformer Architectures
In this section, we search for SLIs within DeïT'-S (Touvron et al., 2021), the Transformer architecture for vision tasks, using ImageNet. The experimental setup is same as in the DeiT paper, and we use Edge-Popup for finding SLTs.
As shown in Table 2, compared to the existing SLT search methods, we can find more accurate SLTs from the frozen network, even though the model size is the same smaller. However, the SLT accuracies are significantly lower than that of the weight- network. While CNN and GNN maintain some SLT accuracy regardless of network pro-processing (i.c., non-frozen, pruning only, or frozen), as shown in Table 1, DeiT shows a significant decrease in SLT accuracy even without freezing. It suggests there are some problems specific to the Transformer architecture with respect to SLT, As mentioned in Section 5, SLT within Transformer architectures has not yet been established experimentally and theoretically, and investigating this degradation is left for future work.
Table 2: SLT accuracy comparison in the DeīT-S architecture.
DEIT-S & IMAGENET
Method (Source Net.)
Weight Tnit.
Sparsity [%]
Pruning Ratio [%]
Locking Ratio [%]
Top-1 1 Test Acc. [%]
Model
Size [MB)
Weight Training
KU
78.4
83.59
SLT (Dense)
SKC
60
0
0
51.8
2.61
SLT (Sparse)
SKC
60
50
0
10.3
1.31
SLT (Frozen)
SKC
60
15
40.2
1.31
SLT (Frozen)
SKC
60
20
36.9
1.04
17


Reviews:
[{"review_id": "nVUx0q1H5H", "reviewer": "Reviewer_TKUm", "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- The paper is well-written and organized.\n- The rationale behind the work is solid.\n- The addressed topic is important for the model compression community.\n\n### Weaknesses:\n- The novelty is limited (compared to previous work, it seems the only improvement is the locking part of the source network), however the results are promising.\n- The proposed method is tested on a limited number of architectures and datasets. I know the authors pointed it out as a limitation in the main paper, but it would be interesting to show some preliminary experiments on transformers-based architectures ().", "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": "- Compared to previous works, this paper proposes a method that extracts strong lottery tickets (STLs) from random networks whose parameters are not only pruned but also locked (namely, random parameters that are for sure part of the STL).\n- They show that when applying the Edge-Popup method to these partially frozen random networks, the found STLs achieve better accuracy than on within dense or pruned-only random networks.\n- Their method enables the memorization of fewer parameters compared to Sota methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Minor comment: I think the color palette in the captions of Figures 2 and 6 differs from those in the legends.", "broader_impact_concerns": "I have no concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1M6IF4OxJT", "reviewer": "Reviewer_1gAq", "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": "**Strength:**\n   * The paper addresses the issue that previous methods restricted search to suboptimal sparsity regions.\n   * The proposed method demonstrates improved accuracy-to-model size trade-offs through empirical evaluation.\n   * The evaluation is comprehensive, including tests across multiple architectures, various datasets, and three sparsity scenarios.\n\n**Weakness**\n   * Although the proposed method for finding SLTs in a frozen network should work with different search methods, the paper primarily experiments with Edge-Popup. Is there a specific reason for this limitation?\n   * (Minor) While the authors acknowledge the lack of hardware implementation as a limitation, the paper could still be strengthened by providing quantitative results on storage reduction and inference efficiency through simulated experiments or analytical comparisons.\n   * (Minor) It might be beneficial to include more discussion on how different locking ratios affect convergence speed and computational cost during the search process.", "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 paper proposes a method for discovering Strong Lottery Tickets (SLTs) in neural networks by freezing parameters through random pruning and locking at initialization. It also provides preliminary theoretical evidence suggesting that SLTs can still be found within these frozen networks, given that the networks have sufficient width.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weakness section.\n\n**Some minor issues**:\n\nSome sections feel redundant, particularly the introduction and the beginning of Section 3. I think it would be helpful streamline these parts to avoid repetition.\n\nCertain sentences are unclear. For example, in Section 2.1, the sentence:\n\n     \"Such as this top-k, these methods determine the SLT sparsity to be explored as a hyperparameter explicitly or implicitly.\"", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QbMYvIy4aI", "reviewer": "Reviewer_JSuv", "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- Background and motivations are explained very well.\n- The theoretical result for SLT existence is provided in the setting with locked parameters.\n- Figures clearly represent the key points in the proposed idea.\n- The experimental results are provided not only in simple toy models but also in various model and dataset settings, such as GNN and ImageNet.\n\n### Weaknesses\nMy major concern is that the novelty compared to [Gadhikar+,2023] may be limited and whether the extension of the paper is sufficiently meaningful.\n\n- The practical advantages from [Gadhikar+,2023] are unclear. Is it aimed at accelerating the finding of SLTs or reducing the memory consumption required for obtained SLTs? It is mentioned that the supermask can be efficiently compressed through entropy coding, but how significant are the practical benefits of making the supermask smaller?\n- The specific calculation for the model sizes in the figures and table is unclear.\n- The selection of the target sparsity and pruning ratio in Table 1 seems arbitrary. If the target SLT sparsity is very close to the pruning ratio, test accuracy drops significantly, as shown in Figure 4. This might allow the pruning-only baseline in [Gadhikar+,2023] to be artificially lowered. Figures 2 and 6 use model size as the horizontal axis, making the actual SLT sparsity level unclear and giving the impression that this aspect is hidden.\n-  Regarding the theoretical analysis, by defining new target $z^\\prime = z - \\sum M^\\prime_i X_i$, where the subtraction comes from the contribution of the locked parameters, wouldn't the results of [Gadhikar+, 2023] immediately lead to the conclusions? If not, it would be better to write about the difficulty of the analysis.", "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 paper proposes a method to find strong lottery tickets (SLTs), which aims to increase the performance of SLTs at the desired sparsity level while compressing memory consumption used for parameter masks. The existence of SLTs is theoretically provided in the paper's setting. Experimental results for CNN and GNN are provided to support the strength of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weakness parts.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers appreciated the clarity of exposition. Although the incremental novelty relative to [Gadhikar et al., 2023] was raised as a concern, TMLR does not require a high degree of “novelty” if the submission provides new insights, solid evidence, and potential utility for readers. The partial-freezing strategy and accompanying experiments address a worthwhile niche in memory-constrained SLT discovery.

The authors’ rebuttals convincingly clarified their contributions, made improvements to the draft, and demonstrated that the claims are properly supported. The audience would likely learn from these findings and appreciate the new angle on “frozen” SLTs and their practical trade-offs.
Decision: Accept (poster)