Restricted Random Pruning at Initialization for High Compression Range
Authors: Hikari Otsuka
Yasuyuki Okoshi
Ángel López García-Arias
Kazushi Kawamura
Thiem Van Chu
Daichi Fujiki
Masato Motomura
Venue: Accepted by TMLR ()

Abstract: Pruning at Initialization (PaI) makes training overparameterized neural networks more efficient by reducing the overall computational cost from training to inference. Recent PaI studies showed that random pruning is more effective than ranking-based pruning, which learns connectivity. However, the effectiveness of each pruning method depends on the existence of skip connections and the compression ratio (the before-after pruning parameter ratio). While random pruning performs better than ranking-based pruning on architectures with skip connections, the superiority without skip connections is reversed in the high compression range. This paper proposes Minimum Connection Assurance (MiCA) that achieves higher accuracy than conventional PaI methods for architectures with and without skip connections, regardless of the compression ratio. MiCA preserves the random connection between the layers and maintains the performance at high compression ratios without the costly connection learning that ranking-based pruning requires. Experiments on image classification using CIFAR-10 and CIFAR-100 and node classification using OGBN-ArXiv show that MiCA enhances the compression ratio and accuracy trade-offs compared to existing PaI methods. In VGG-16 with CIFAR-10, MiCA improves the accuracy of random pruning by $27.0\%$ at $10^{4.7}\times$ compression ratio. Furthermore, experimental analysis reveals that increasing the utilization of the nodes through which information flows from the first layer is essential for maintaining high performance at a high compression ratio.

Published in Transactions on Machine Learning Research (5/2024)
Restricted Random Pruning at Initialization for High Compression Range
Hikari Otsuka
Deportment of Information and Communicaaiios Engineering Tokyo Institute of Technology
Yasuyuki Okoshi
okoshi. wwwahi.yassuukkarriic..c fir. www.cttttccc....
Deportment Information and Communicaaiions Engineering Tokyo Institute of Technology
Ángel López García-Arias
lopez@artic. ürr www.tttech.ccc ac.jp
Department of Information and Communications Engineering Tokyo Institute of Technology
Kazushi Kawamura
kowammuoBarticc.in..t ac.jp
Department of Information and Communications Engineering Tokyo Institate of Technology
Thiem Van Chu
thiem Sliem.Brtti.it www.rrittchh... ac.jp
Deportment of Information and Communicatiins Engineering Tokyo Institute of Technology
Daichi Fujiki
dfujiki@urlic. ür. Kitech. ac.jp
Department of Information and Commuuiccatioss Engineering Tokyo Institute of Technology
Masato Motomura
motomun.@artic.it üur www.rrittecch..o tit.ihhhchh...ippppp
Department Information and Communications Engineering Tokyo Institute of Technology
Reviewed on OpenReview: https: opwnreveee.. net/ net/forun id-gf4cizoorg
Abstract
Pruning at Initialization (Pal) makes training overparameterizzed neural networks more ficient by reducing the overall computational cost from training inference. Recent PaT studies showed that random pruning is more effective than ranking-based pruning, which learns connectivity. However, the effectiveness of cach pruning method depends the ex- istence of skip connections and the compression ratio (the before-after pruning parameter ratio). While random pruning performs better than ranking- based pruming on architectures with skip connections, the superiority without skip connections is reversed in the high com- pression range. This paper proposes Minimum Connection Assurance (MiCA) that achieves higher accuracy than conventional PaT methods for architectures with and without skip connections, regardless of the compression ratio. MiCA preserves the random connection between the layers and maintains the performance at high compression ratios without the costly connection learning that lanking-based pruning requires. Experiments image clas- sification using CIFAR-10 and CIFAR-100 and node classification using OGBN-ArXiv show that MiCA enhances the compression ratio and accuracy trade-olls compared to existing Pal methods. In VGG-16 with CIFAR-10, 10, MiCA improves the accuracy random pruning by 27.0% at 10 x compression ratio. Furthermore, experimental analysis reveals that creasing the utilization of the nodes through which information flows from the first layer is essential for maintaining high performance at high compression ratio.

---

Published in Transactions on Machine Learning Research (5/2024)
1 Introduction
Although deep neural networks (DNNs) have high generalization capability, both their training and inference
are computationally expensive (Arora et al. 2019 Zhang et al. 2019
2021 Neyshabur et al. 2019 Wen et al. These high costs arise because their computation depends on a large amount of parameters (Shoeybi et al.
2022
2019 Brown et al. 2020 Dosovitskiy et al., 2021 Woo et al., 2023
Network pruning achieves high generalization capability despite fewer parameters and can solve this problem. There are various lypes of pruning, including methods that train while sparsifying the nelwork gradually by penalty terms (Chauvin [988] Weigend et al., 1990: Ishikawa, 1996), prune the network after training
and then finetune it (LeCun ct al. 1989 Hassibi et al. 1993: Lee et al. 2021), and prune and learn itera-
tively (Frankle & Carbin 2019 Frankle et al. 2019 Renda et al.) 2020 However, these aim to reduce the inference computational cost and need to train the dense model. By contrast, dynamic sparse training (Mo- canu et al. 2 Evei et al.) 2020; Jayakumar et al.) 2020) and pruning at initialization (Pal) train with sparse networks, thus reducing training computational costs and hence the learning speed can be faster. In particular, PaT has the lowest training computational cost among pruning methods because the network structure is fixed (Pricc& & Tanner 2021].
Basically, PaI calculates criterion to determine which parameters essential and selects the parameters to be pruned based on it. This type of Pal called ranking- based pruning at initialization (RbPI) (Lee et al., 2019 Wang et al., 2020; Tanaka et al., 2020) can learn the network connections explicitly but needs to calculate the criterion using an expensive process such as backpropagation. On the other hand, another type of Pal called random pruning at initialization (RPI) has a negligibly small additional cost because it only prunes a network randomly without calculating criterion. At first glance, RhPI scems to perform better than RPI since it learns connections, but some works suggested that RPI could construct subnetworks with similar or better performance obtained by RIPI. Frankle et al. (2021) revealed that RPI and RbPT had comparable accuracy at 1-10ax compression ratios when applying the same sparsity set separately for each layer (i.e., the sparsity distribution). Similarly, the work by [Su et al. (2020) showed that RPI with ad-hoc sparsity distribution improved the trade-off between parameter ratio of dense to sparse network- compression ratio-ant accuracy than RbPI. Furthermore, randomly pruned networks outperform dense networks in aspects such as out-of-distribution detection and adversarial robustness (Liu et al., 2022). Thus, RPI seems to combine simple pruning processing with high performance among Pal methods.
On the other hand, recent thread of Pal research (Vysogorets & Kempe 2023 showed a curious phenomenon of RPI: its efficiency at high compression ratios depends on skip connections in the DNN. At more than 10 x compression ratios, randomly pruned models without skip connections are less accurate than RbPI. It differs from the result in low compression ratio by Frankle et al. (2021) and implicates that highly sparse networks need to learn connection. However, whether connection learning is essential in the high compression range is debatable. For instance, the work by Gadhikar et al.] (2023) improved the performance of skip connection- free architecture by adding parameters (i.e., edges) to functincionaal neurons in a randomly pruned network at 10-103x x compression ratios. It indicates that even random pruning can improve performance if the connections between layers are preserved. However, this approach is not essential for higher compression ratios because the additional edges inhibit compression. Therefore, there is a need for more essential solutions to improve performance in skip connection-free architecture.
In order to address this problem, this paper introduces a novel Pal algorithm for high compression range: Minimum Connection Assurance (MICA). Specifically, it preserves top-to-bottom information propagation among randomly pruned layers by building a random connection minêmum connection using some of the pre-allocated edges. The minimum connection is constructed by pre-determining and connecting the neurons that the subnetwork uses, and the subnetwork with the connection maintains the pre-defined sparsity distribution even when connecting its neurons randomly. Thus, all allocated edges can be functional even in a high compression range. Since MiCA has this small constraint on the placement of the edges while keeping the connection random, it stands as restricted RPI algorithm in the field of Pal algorithms. We evaluate MiCA on image classífication using CIFAR-10, CIFAR-100 (Krizhevsky et al. 2009 ImageNet (Russakovsky et al. 2015) and on node classification using OGBN-ArXiv (Hu et al.) 2020). In each evaluation, we employ VGG (Simonyan & Zisserman 2014) and ResNet. (He et al. 2016) architectures for the former and graph
2

---

Published in Transactions on Machine Learning Research (5/2024)
Non-functional Unpruned Edges and Nodes
Pruned Edges
Figure 1: Some edges and nodes stop affecting the output (dashed line) the network becomes sparser by pruning dotted lines.
convolutional network (GCN) (Kipf & Welling, 2017) and graph isomorphism network (GIN) (Xu et al. 2019) architectures for the latter. MiCA enhances the performance for not only skip connection-free architectures such as VGG but also architectures with skip connections such as ResNet. Furthermore, despite the random connection, MiCA improves the trade-off between compression ratio and inference accuracy compared RPI and RbPI methods. In other words, MiCA shows that the connections learned by RbPI can be replaced by random connections even in the high-compression range.
The rest of the paper is organized as follows. Section 2 outlines existing Pal methods and describes how to calculate a compression ratio that correctly compares them with MiCA. Then, Section 3 proposes MiCA, and Section compares MiCA with the RPI and RbPI methods. Finally, Section concludes this paper.
2 Related Work
Pal algorithms can categorized into two groups: 1) those that learn the criterion of pruning before training weights (i.c., RbPI); and 2) those that prune randomly (i.c., RPI). The methods included in these groups can be compared by using the compression ratio obtained by eliminating unused edges (Vysogorets & Kempe 2023). This section recapitulates the method for calculating the corrected compression ratio and outlines the literature on RPI and RbPI.
Calculation of Corrected Compression Ratios. Recently, Vysogorets & Kempe 2023 found that Pal algorithms produce significant amounts of redundant parameters that can be removed without affecting the output. Figure [ illustrates this phenomenon. A pruned network has 10 edges, but the 4 dashed edges do not affect the output. Thus, the apparent compression ratio 21/10 2.1, but it can also be regarded 21/(10 4) 3.5. Correcting the compression ratio caleulation by removing them results in fairer comparison between subnetworks. Subsequent sections use this compression ratio calculation.
Random Pruning at Initialization (RPI). RPI prunes each layer randomly based on a pre-defined sparsity distribution calculated by a pre-defined compression ratio. To date, various sparsity distribution design methods have been proposed. For example, Frdös-Rényi-Keeee Kernel (ERK) (Evci et al. 2020), which was devised in the context. of random graphs, determines the density of 1-th layer to be proportional to kkW))) J/(C!! in x c(O) x k x xk((), ), where (((1) cill.. 1/ and A denote input channels, output channels, kernel height, and kernel width of the I-th layer, respectively. Ideal Gas Quotas (IGQ) Vysogorets & Kempe 2023) focuses on the fact that traditional global pruning methods (Lee et al. 2019 2021 Tanaka et al.] 2020) intensively remove parameter-heavy layers. It determines the constant F based the target compression ratio and calculates the density of I-th layer (Fe(") + +1) where e(!) is the number of edges in the I-th layer. The subnetworks to be pruned based on these sparsity distributions achieve comparable or better performance against RbPI and RPI using other distributions (Vysogorets & Kempe 2023). However, those with skip connection free architectures cannot achieve such performance as the compression ratio increases. Although some solutions, such as adding edges and resampling (Gadhikar ltt al. 2023), are proposed to address this RPI weakness, they are impossible at higher compression ratios inefficient. Unlike these methods, our approach is efficient and works at higher compression ratios.
the scale (C(9) + (1(1) + (1) + k0
3

---

Published in Transactions on Machine Learning Research (5/2024)
Case
Case 2
MiCA
Layer + 1)-th Layer
Layer
(1 1)-th Layer
I-th Layer (I+ 1)-th Layer
Non-functional Edge
Figure 2: In cases 1 and 2, randomly pruning the network make some edges non-functional. On the other hand, MiCA keeps all edges functional while allowing randomness in the conncctions.
Step 1
Step
Block
Block
L
L
r
Block
Block
L
Figure 3: Edge placement procedures to construct minimum connection. First, input node of each block is connected to output node, and then the remaining unconnected nodes are connected.
It constructs subnetwork with only pre-allocated edges, except that pre-defined sparsity distributions invariably cause non-functional neurons (i.e., nodes). Moreover, our approach does not require the iterative pruning operation.
Ranking-Based Pruning at Initialization (RbPI). RbPI determines the pruning priorities based on the initial state of a network and a dataset. For example, SNIP (Lee al.) 2019) uses the magnitude of the backpropagation gradient after iteration as parameter's pruning priority. GraSP (Wang et al. 2020) prunes the edges that do not reduce the gradient flow of subnetwork for dataset preferentially, SynFlow (Tanaka el al. 2020) updates parameter's pruning priority by using the li-path norm of a network (Neyshabur et al. 2015) as a loss and prunes iteratively without dataset. Unlike other RbPI methods, it can avoid layer-collapse (Hayou et al., 2020) at high compression ratios. As seen from these, RbPI takes into account the information flow the initialized network for the pruning criteria. Hence, its sparse sub-networks tend connect layers each other. On the other hand, RbPI requires pre-training calculate priorities, which is prohibitively expensive. RP1 and our approach have a lower cost because they do not need to calculate priorities.
3 MiCA: Minimum Connection Assurance
As demonstrated by Gadhikar et al. 2023) maintaining connections each layer can improve the sparse network's accuracy after training, especially when the compression ratio high. This section proposes MiCA, method make all pre-allocated edges as functional possible with few operations based on the fact that the connections at each layer guaranteed if all pre-allocated edges functional. MiCA
4

---

Published in Transactions on Machine Learning Research (5/2024)
Algorithm Number of Output Nodes Analysis
Require: Pre-defined maximum number of output nodes noul number of edges e(1), e(2) ..y e(4), maximum block size 80))8(2) b(.)),..,B()))
procedure NODEANAINSIS(nM (L)
el1), elW))e()) , smny -..,,,()) (01,,,00, ,,,,,... b(0)
Pout &- min (noat: e(L)
(L)
3: for 1= to 2 do
4:
if b(t) 2 (11))
idett then Douttident
(1-1)
x E {zEN
) S (e!0) /00)
6: else
7: nI nout,ideat f (m00 out,idenl
end if
9: end for
10: return (1)
(2)
(T)
"out, 7 "dutt .... 11 outt
11: end procedure
first constructs random connection named minimum connection from the input to the output layer using some pre-allocated edges. Then, it builds a subnetwork by randomly connecting the nodes involved in the connection. The presence of minimum connection ensures that randomly placod edges become functional. order to construct the minimum connection, it is necessary to determine how many nodes should be used at each layer to ensure that all placed edges are functional. Therefore, we first introduce an analytical method for determining the ideal number of nodes and then describe how construct the minimum connection.
The ideal number of nodes analysis: A layer has non-functional edges if and only if the mumber of nodes used in the adjacent layers is too large or too small relative to the number of edges pre-assigned to that layer. Figure 2 exemplifies the two situations: in case 1, the edges of (-th layer connect to all nodes of ([+1)-thh layer. causes some non-functional edges at I-th layer the number of edges of the (1+ (++t)thh layer is low; in case 2, all edges connect to a few nodes of the next layer. It causes some non-functional edges at (I+ 1)-th layer if the number of odges of the (I + 1)-th layer is high. Thus, basod on pre-defined sparsity distribution and each layer architecture, we pre-determine which nodes to use to avoid these situations.
We consider pruning neural network constructed with L layers. We first define the maximum number of input and output nodes pre-defined as network structure of I-th layer as n (1) and naut respectively. For instance, in convolutional layer with input channels C output channels C kernel height k/) and kernel width k.0), (!) and out are c:(9 x k x a!!!) and C:(() respectively. Similarly, in fully-connected layer with input features A!ll and output features p(l) ni and ( are /( and f!l) respectively. Furthermore, (1)
())
(I)
we denote the number of input and output nodes of the pruned I-th layer as v.(O) in S 21, n.. and (!!)) S 21.2.... (!))) respectively. Additionally, we define block Volk. S v(0) in the I-th layer as the input nodes corresponding to an output node in the (1 1)-th layer. Thore are v-ll-)) blocks in 1-th layer, and each size of block ranges from 1 to b(),, where ((0) is defined as follows:
(1) (1-1)
nt n oot (1>1) 1)
(d)
k (1) (1)
(1 1 and first layer convolutional layer) (otherwisc)
(I)
1
For example, if both the (1- 1)-th and 1-th layers are convolutional layers, the maximum size ((()) 1,(1) x 2,(0) and it if the (1 1)-th layer is a fully-connected layer. As a particular case, we also define block with maximum size ((1) in the first layer. If the first layer is convolutional layer, we consider kernel block; otherwise, consider single neuron block.
The pruned 1-th layer can be regarded a bipartite graph connecting nodes in viO and v-()) To ensure that all edges of 1-th layer and adjacent layers become functional, the number of edges ( in the I-th layer
5

---

Published in Transactions on Machine Learning Research (5/2024)
Algorithm 2 Step 1 of Minimum Connection Construction at (-th layer
Require: Network N, imput nodes V:(0, pre-defined number of edges e!!) the ideal number of output nodes T idut pre-calculated by Algorithm
1: procedure STEP1 (N, v _,00 ,, n oduti
2: Vused f O
+-1 Vill]
+0 0
5: for "lkii in blocks of 1-th layer do
(1)
+ x E v-(1) blk,i
6:
in
(
Vused= f Vused Fi
if lout S m nout,ideal then (1)
(1)
lout
10:
lout s iout +1
11:
else
(1) t I E EN 15 x S iout
(1)
12:
13:
end if
Connect Unn and yod in N
14:
v(0) aut { (0)
15:
(Vout)
e!l) t -el0--
16:
if c(9 5O then
17:
18:
break end if end for
19:
20:
return N, e,)(), Vused, ioat, V
21:
22:
end procedure
must satisfy max (vr10) 1ill
S ell)
<
(((h)
| Yout
Solving this inequality for ((())
leads to
in
e(t)
(())
S E(l)).
(2)
(1)
out
Additionally, considering that up b(0) imput nodes of the I-th layer connect an output node of the (I - 1)-th layer for < <15 L, (0) satisfies the inequality
out
| <
v)())
<
(1--1) 1)
x 8(1)
(3)
From these two inequalities, we need to satisfy
el))
e(0)
(((-1) out
S
(4)
(D)
b(1)
out
for < < E L. so that all edges in the network become functional.
We sequentially analyze the ideal number of output nodes
n iottiddea from the output layer to the input layer.
(1)
We select nou out,ideat randomly from the range ( Pout,ideut
(
< n out ideat
(1-1)
(4)
based on Equation Note that to minimize the
BIT
we define n idel == min mae e(?.). n
(L)
ideaa < b0), we set n out, as
(1-1)
(
nout, ideat
loss of input nodes. In cases where the network features branching structure, such residual connections,

---

Published in Transactions on Machine Learning Research (5/2024)
Algorithm 3 Step 2 of Minimum Connection Construction at (-th layer
Require: Network N, imput nodes V.( in pre-defined number of edges e(1), the number of output nodes
T "dut pre-calculated by Algorithm
1: procedure (NE vlt) ,e(0, ,e(0,m
(n(() mu iduat))
2: N, e,, Vused, loue, V.l) f- (N,, vl e n "outtideal
while ell) and
V Uueed
Vin
(1)
or iou n iut,a do
(1)
if |ueed (!))
then
in
(1)
v(()
in
Vased (
Vused Vused
in
7: else
Vin t x E (1
8:
in
end if
10:
if
iout"
I T2 idtt then
(1)
11:
Vout < lout
12:
lout lout + 1
13:
else
Vout c E x EN 15 S n (1)
(1)
14:
idtt
15:
end if
16:
Connect Vi and Vout in N
v(I)
out < v(1)
17:
Vout out
out
18:
e(l) +- e0 -1 end while
19:
20: return N, e,e(!, v-
21: end procedure
we choose the larger Rideal obtained at each branch to maintain connections across all input nodes. The computational cost of this analysis, depicted in Algorithml T negligibly small it relies solely simple operations with pre-defined constants.
(1-1)
Minimum connection construction: Upon determining the ideal mumber of output nodes used in each layer, the minimum connection construction is finalized through edge placement so that it is satisfied that (
(1) n iddatt We establish minimum connection in two steps, outlined in Figure 3
()()) 1. Select an input node from a block Mkk and connect it to an unconnected output node. This process is iterated for all blocks (for the detailed procedure, see Algorithm 2
2. Connect the remaining unconnected nodes. If the minimum degree of input or output nodes is already 1, we connect the unconnected nodes randomly to other nodes (for the detailed procedure, see Algorithm 3
These steps are execuled sequentially from the input lo the output layer. Finally, MiCA places the remaining edges randomly within the nodes of the minimum connection, as depicted in Algorithm 4 These edges are functional regardless of placement, owing to the minimum connection.
4 Experiments and Results
This scction evaluates MiCA using the experimental sctup described in Section 4.2 It shows that MiCA performs better than conventional RPI and RbPI methods, especially in the high compression range and regardless of whether skip connections exist.

---

Published in Transactions on Machine Learning Research (5/2024)
Algorithm 4 Minimum Connection Assurance
Require: Network N, the maximum number of imput nodes n/g the maximum number of output nodes
T Rout: pre-defined number of edges ,()),(?)) ,(.,), maximum block size 6(1, b(2) ,.., b(d) [1)
(I.)
n ioutl no Rdettideal! ..., n (L)
(L) ell), el?)) e..,,ee)) b(1) b(2) .... b(.)) ideal f- NoDEANALYSIS(M
2: V/( +- 1 1,, nin
(2)
for 111o L do
N,e Vueed, Rouds out f- STEP2(N,, Vi e (1)
idea!
5: while ell) > do
( + 2 k!ll) out f vl()
6:
8:
Connect Vnn and out e!l)) f- e(!)
10: end while
11: if I < L then
12: (((+1) + +1+ 1)-th layer input nodes connected to V
13: end if
14: end for
4.1 Notation of Methods
We briefly introduce the notation of the methods compared in the subsequent experiments in advance. RPI uses pre-defined sparsity distribution for ERK, IGQ, SNIP, GraSP, and SynFlow. Here, we consider the sparsity distribution of the network pruned by SNIP, GraSP, and SynFlow, which are RbP, as pre- defined sparsity distribution. RPI methods with these distributions are denoted RPI-ERK, RPI-IGQ, RPI-SNIP, RPI-GraSP, and RPI-SynFlow, respectively. Similarly, MiCA using these distributions are denoted MiCA-ERK, MICA-IGQ, MiCA-SNIP, MiCA-GraSP, and MiCA-SynFlow, respectively. For the RbPI experiments, SNIP, GraSP, and SynFlow are chosen RbPI methods, and these are specified RbPI-SNIP, RbPI-GraSP, RbPI-SynFlow, respectively. For more detail each RPI and RbPT method, see Section 2
4.2 Experimental Settings
This paper evaluates MiCA on two classification tasks: image classification and node classification. The latter one of the major tasks for graph neural networks (GNN), and this paper covers to investigate the versatility of our approach for general tasks that do not use convolutional architectures.
We employ the CIFAR-10, CIFAR-100, and ImageNet datasets in image classification. For CIFAR-10 and CIFAR-100, 40,000 images used as training data and 10,000 as validation data, while use the default set split for ImageNet. The architectures used in the image classification experiments are VGG-16, ResNet-20, and ResNet-50, and each implementation is based on the code provided by Tanaka et al. (2020). In particular, VGG-16 includes a batch normalization layer and removes the bias the convolutional layer. All experiments for this task use stochastic gradient descent (SGD) applying Nesterov's acceleration method (Nesterov) 1983) with a momentum of 0.9. CIFAR-10 and CIFAR-100 experiments are run five times with a batch size 128 for 160 epochs, and the ImageNet experiment is run once with batch size 256 for 90 epochs. For VGG-16,
the weight decay is set 0.0001, and the learning rate is started at 0.1 and multiplied by 0.1 after 60 and 120 epochs. For ResNet-20, the weight decay is set to 0.0005, and the learning rate is started at 0.01 and multiplied by 0.2 after 60 and 120 epochs. For ResNet-50, the weight decay is set to 0.0001, and the learning rate is started at 0.1 and multiplied by 0.1 after 30, 60, and 80 epochs.
On the other hand, node classification, we experiment with the OGBN-ArXiv dataset split by default proportion. We employ the GCN and GIN architectures, which are variants of GNN, with four layers and implement each architecture based the codes provided by Wang et. al. (2019): Huang et. al. (2022). We
8

---

Published in Transactions on Machine Learning Research (5/2024)
VGG-16 -6
ResNet-20
1.0
Ratio of Functional Edges
0.8
0.6
0.4
0.0
10
10a
10a
10*
10
10
10
10a
10a
10*
Pre-Defined Compression Ratio
Pre-Defined Compression Ratio
MICA-ERS ERK MiCA-IGQ
RPI-ERK RPI-IGQ
Figure 4: Comparison of the ratio of functional edges between RPI and MiCA with ERK and IGQ for pre-defined compression ratios. Unlike other RPI methods, MICA makes all edges functional, even at a high compression ratio.
use Adam Kingma & Ba 2014) and cosine learning rate decay for the node classification. Each architecture is set to an initial learning rate of 0.001 and trained for 400 epochs. Also, these experiments are run five times.
For all experiments, we use values 100.5 10 ...,, 109.5, and 10 pre-defined compression ratios. Note that results not plotted if all edges are fonntinntional after compression. SNIP and GraSP use 10x the training data amount relative to the dataset's number of classes and batch size of 128. SynFlow prunes the initialized network for 100 iterations.
4.3 Pre-Defined Sparsity Distribution Maintenance of MiCA
This section shows how much MiCA and RPI leave functional edges for each pre-defined compression ratio. The result is teo in Figure 4 The ratios of functional edges for RPI-ERK and RPI-IGQ begin to decrease around 103x x compression ratio for VGG-16 and 102x for ResNet-20. On the other hand, MiCA continues to use all the pre-allocated edges as much as possible and maintains the sparsity distribution even in the high compression range. MiCA-ERK and MiCA-IGQ have almost all functional edges even at 10 x compression ratio for VGG-16 and 103.5x compression ratio for ResNet-20. However, all edges be non-functional high compression ratios, is caused by the way the pre-defined sparsity distribution is designed. Some pre-defined sparsity distributions allocate no edges to few layers when the pre-defined compression ratio is exceptionally high. As result, all edges are non-functional, regardless of how they are placod.
in MiCA-ERK for VGG-16 at 103.5x compression ratio. This phenomenon
4.4 MiCA vs. Random Pruning
Figure compares MiCA and RPI with ERK, IGQ, SNIP, GraSP, and SynFlow. First, we focus on the ERK and IGQ experiments the two left columns. In the VGG-16 experiment (first column), RPI-ERK and RPI-IGQ have a sharp performance drop for 2 103x compression ratios for both CIFAR-10 and CIFAR-100. These with a pre-defined compression ratio of 10 have an actual compression ratio of > 10 and those with a pre-defined compression ratio of 10*x, 10 x,... 10 and 108x cannot be plotted as all edges are non-functional (i.e., the corrected compression ratio is infinite). On the other hand, MiCA-ERK and MiCA- IGQ maintain the same compression ratio as the pre-defined compression ratio and suffer less performance degradation. Note that MiCA-ERK is not plotted for 105.5 x and 10 x compression ratios. This phenomenon is due to ERK's design, as mentioned in Section 4.3 and the same occurs in other sparsity distributions (c.g., IGQ) and other experiments. As shown in Figure 5 (a) MICA-IGQ achieves an accuracy of 44.4% for 10 x compression ratio, significantly higher than RPI-GGQ's 's accuracy of 12.6% for 10 compression ratio. This result suggests that. the minimum connection supports learning in the high compression range.

---

Published in Transactions on Machine Learning Research (5/2024)
VGG-16
ResNet-20
VGG-16
ResNet-20
90
70
Top-1 Test
30
10
10a
10
10
10a
10
10a
10
10
10a Compression Ratio
Compression Ratio
Compression Ratio
Compression Ratio
MICA ERK
RPI-ERK RPI-IGQ
Dense
MICA-SNIP
RPI-SNIP
Dense
MiCA IGQ
-
MICA GraSP
RPI-GraSP
MICA SynFlow
Ryn-Swn
(a) CIFAR-10 experiments.
VGG-16
ResNet-20
VGG-16
ResNet-20 20
Top-1 Test (%)
10
101
10
10a
10
10a Compression Ratio
10
10a
10
10'
10a Compression Ratio
Compression Ratio
Compression Ratio
MiCA-ERK
RPI-ERK RPI-IGQ
Dense
MiCA-SNIP
RPI-SNIP
Dense
MICA-IGQ
MiCA-GraSP
RPI-GraSP
MICA SynFlow
EPI-SSyFlow
(b) CIFAR-100 experiments.
Figure 5: Comparison of accuracy between RPI and MiCA CIFAR-10 and CIFAR-100. In VGG-16, MICA reduces performance degradation in the high compression range and improves the accuracy and compression ratio trade-off. It also shows slight performance improvement for the sparsity distributions such as IGQ and SynFlow ResNet-20 experiments using CIFAR-10. Note that some plots are not plotted because the corrected compression ratio infinite.
In the ResNet-20 experiment (second column), the performance difference between MiCA and RPI is less drastic than in the VGG-16 experiment. In particular, CIFAR-100 experiments (Figure 5 (b) show little difference. However, it is hardly surprising considering that skip connections help randomly pruned net- works learn in the high compression range (Hoang et al. 2023 For CIFAR-10 experiments (Figure 5 (a)) MiCA-FRK slightly improves the trade-off between compression ratio and accuracy against RPI-ERK in the compression range of 102-103x. x. ResNet-20 has several layers that do not have skip connections, and is therefore considered that the minimum connection supports learning in those layers.
Then, we state the results of the right two columns in Figure 5 In the VGG-16 experiment (third column), MiCA-SNIP, MiCA-GraSP, and MiCA-SynFlow significantly improve the tradc-off between accuracy and compression ratio as in the ERK and IGQ experiments. It. is particularly evident in the CIFAR-100 experi- ment (Figure 5 (b)). Thus, MICA overcomes the performance degradation at a high compression range for skip connection-fre free architectures, regardless of the pre-defined sparsity distribution. However, the perfor- mance improvements in the ResNet-20 (fourth column) are still minute. This result seems regrettable but highlights the importance of skip connections to RPT.
10

---

Published in Transactions on Machine Learning Research (5/2024)
VGG-16
ResNet-20
VGG-15 16
ResNet: 20
70
90
Teg-1 Test Acc, (96)
70
50
10
10
10
10a
10
10a
10
10a Compression Ratio
Compression Ratio
Compression Ratio
Compression Ratio
MICA SNIP
RoPI-SNIP
Dense
MICA SNIP MiCA-GraSP
RbPI-SNI
Dense
MICA GrasP
GraSP
RbPI-GraSP
MiCA-SynFlow
RoPl-SynFlow
MiCA-SynFlow
RbPI-SynFlow
(a) CIFAR-10 experiments.
(b) CIFAR-100 experiments.
Figure 6: Comparison of accuracy between RbPI and MiCA. MiCA improves the accuracy and compres- sion ratio trade-off more than RbPI in ResNet-20. MiCA also performs as well as RbPI in the VGG-16 experiments. Interestingly, MiCA outperforms RbPI in both VGG-16 and ResNet-20 experiments using CIFAR-100.
ResNet-50
40
Top-1 Test Acc. (%)
70
30
50
30
20
10
10
10
10
10
Compression Ratio
102
103
104
MICA-IGQ
RPI-IGQ
Comparison of accuracy between RPI-IGQ and MiCA-IGQ using ResNet-50 on ImageNet. MiCA improves the accuracy and compression ratio trade-off slightly.
Figure 7:
4.5 MiCA vs. Ranking- Based Pruning
Figure 6 compares the compression ratio and accuracy between RbPI and MICA on CIFAR-10 (left two columns) and CIFAR-100 (right two columns). We employ SNIP, GraSP, and SynFlow as RbPI methods. Despite random connections, MiCA achieves comparable performance RbPT VGG-16. Although it has already been observed that randomly pruned networks achieve performance comparable to RbPI (Frankle et al. 2021 to the best of our knowledge, this is the first time that the same result is reported in the high compression range. In other words, this result shows that RbP1 only learns layer-to-layer connections, not high-performanee subnetworks, regardless of the compression ratio. Interestingly, the ResNet-20 experiments show & more pronounced performance difference than the RPI result in Figure 5 It suggests that. MiCA's 's RPI aspect helps it to maintain higher performance than RbPI in ResNet-20 because MiCA connects each layer randomly. Also, RbPI may have significant variations in compression ratio in the high compression range. On the other hand, MiCA robust regarding compression ratio and can achieve the pre-defined compression ratio.
11

---

Published in Transactions on Machine Learning Research (5/2024)
VGG-16
ResNet-20
VGG-16
ResNet:
90
70
Top-1 Test Acc.
30
10
10a
10
10
10
10
10a
10a
101
Compression Ratio
Compression Ratio
Compression Ratio
Compression Ratio
MiCA ERK
RPI-ERK
Dense
MiCA-SNIP
RbPI-SNIP
Dense
MICA IGQ
- RPI-IGQ
MICA-GraSP GraSP
RbPI-GraSP
MICA-SynFlow
RbPI SynFlow
(a) CIFAR-10 experiments.
VGG-16
ResNet-20
VGG-16
ResNet-20
50
Top-1 Tess
10
10a
105
10
10a
101
10a
10
10'
10a Compression Ratio
Compression Ratio
Compression Ratio
Compression Ratio
MICA-ERK
RPI-ERK
Dense
MiCA-SNIP
RbPI-SNIP
Dense
MICA-IGE
+ RPI-IGQ
MiCA-GraSP
RbPI-GraSP
MICA SynFlow
RbPI-SynFlow
(b) CIFAR-100 experiments.
Figure 8: Comparison of RPI and MiCA with the same corrected sparsity distribution CIFAR-10 and CIFAR-100. When the number of parameters used in each layer is matched, MiCA performs better than other Pal methods when the compression ratio is high.
4.6 ImageNet Experiments
Figure 7 compares the compression ratio and accuracy between RPI-IQQ and MiCA-IGQ on ImageNet the high compression range. MICA-IGQ improves the accuracy and compression ratio trade-off slightly over RPI-GQQ. As in the CIFAR-10/IN experiments, the accuracy improves even in the architecture with skip connections, suggesting the importance of the connection relationships between layers. RPI-IGQ has the same accuracy as a random network at a pre-defined compression ratio of 10*x. However, MiCA-IGQ maintains higher accuracy than a random network even at a pro-defined compression ratio of 104.5 x. Thus, maintaining the layer-wise connections enables one to learn from the data, even the case an extremely high compression ratio.
4.7 Performance Comparison for the Same Sparsity Distribution
Previous sections match the pre-defined sparsity distribution of MICA and other PaI methods and compare each method. contrast, this section evaluates the corrected sparsity distribution of RPI and RbPI as the pre-defined sparsity distribution of MiCA. Then, show that the network structure constructed by MiCA
12

---

Published in Transactions on Machine Learning Research (5/2024)
VGG-16
ResNet-20
VGG-16
ResNet-20
Ratio Functional Nodes
1.00
0.75
0.50
0.25
0.00
10
10a
10
10
10a
101
10a
10
101
10a Compression Ratio
Compression Ratio
Compression Ratio
Compression Ratio
MiCA ERK MiCA-IGQ
RPI-ERK - RPI-IGQ
MICA-SNIP
RbPI-SNIP
MICA GraSP
RbPI-GraSP
MICA SynFlow
RbPI-SynFlow
Figure 9: Comparison of the compression ratio with the ratio of functional nodes among the nodes flowing information from the first layer. MiCA maintains high functional node ratio even in high compression range compared to other Pal methods. Exceptions RbPI-SynFlow, which retains higher ratio than MiCA at high compression ratios.
(L+ 1)-th Layer
1-th Layer
Block (Kemel)
7
Block (Kemel)
Figure 10: the I-th convolutional layer, each output node has connections with up to ((++) = k/j ((+11 x ((+1) input nodes the + 1)-th convolutional layer. These connections, formed during the convolution process, may persist even after pruming, making input nodes of (1+1)-th layer non-functional.
achieves higher performance against other Pal methods, even when the number of edges each layer is matched.
Figure compares RPI, RbPT, and MiCA for the same sparsity distribution. The two columns on the left show RPI experiments, while the two on the right show RbP1 experiments. Even when using the same sparsity distribution, MiCA improves the accuracy more than RPI (left two columns). The results in VGG- on CIFAR-10 10 are remarkable: MiCA-ERK achieves 27.0% higher accuracy than RPI-ERK with 10 x compression ratio. Performance improvements of MiCA can also be seen in ResNet-20 at a high compression ratio. Both RPI and MiCA ought make similar networks due to the random connection in this situation, but the performance difference is more noticeable when the compression ratio is high. In addition, the subnetworks built by RbP1 suffer more performance degradation than those built by MiCA, regardless of compression ratio and architocture (right two columns). However, in the VGG-16 experiments (third column), RbPI-SynFlow is more accurate than MiCA in the compression range above 10 At 105.5x compression ratio in CIFAR-10 experiments, HiCA-SyuFlow achieves 10.0%, which is not different from the random performance, while RbPI-SynFlow achieves 20.3%. Furthermore, these accuracics are almost identical for CIFAR-100 experiments. In other words, RbPI-SynFlow superior to MiCA only when the compression ratio is extremely high and the architecture does not have skip connections.
13

---

Published in Transactions on Machine Learning Research (5/2024)
GCN
70
50
Top-1 Test
30
10
101
10
10
10
10a
10
101
10a
10
101
10a
10
Compression Ratio
Compression Ratio
Compression Ratio
Compression Ratio
MiCA-ERK
RPI-ERK
Dense
MiCA-SNI
RPI-SNIP
Dense
MiCA-IGQ
RPI-IGQ
MiCA-GraSP
RPI-GraSP
MiCA-SynFlow
RPI-SynFlow
GCN
GIN
Top-1 Test Acc. (96)
50
30
10
10
10
101
10
10
Compression Ratio
Compression Ratio
MiCA SNIP
RbPI-SNPP
Dense
MiCA-GraSP
GraSP
MiCA-SynFlow
RbPI-SynFlow
Figure 11: Comparison of the accuracy between RPI, RbPI, and MiCA on OGBN-ArXiv with same pre- defined sparsity distribution.
GCN
GIN
GCN
GIN
70
Top-1 Test (%)
50
30
10
10
10a
10
101
10a
105
10'
103
10F
101
103
105
Compression Ratio
Compression Ratio
Compression Ratio
Compression Ratio
MiCA-ERK MICA-IGO IGQ
RPI-ERK RPI-IGQ
Dense
MiCA SNIP
RoPI-SNIP RbPI-GraSP RoPl-SynFlow
Dense
MiCA-Gri GrasP
MiCA-SynFlow
Figure 12: Comparison of RPI, RbP1, and MICA accuracy on OGBN-ArXiv with the same corrected sparsity distribution.
4.8 Top-to-Bottom Bottom Information Propagation
This section shows that MiCA propagates information without loss compared other Pal methods. As in the previous section, the pre-defined sparsity distribution of MICA is matched the corrected sparsity distribution of each method.
14

---

Published in Transactions on Machine Learning Research (5/2024)
Figure compares the ratio of functional nodes to all nodes that information flows from the first layer for cach compression ratio. While RPI and RbPT methods reduce the ratio of functional nodes as the compression ratio increases, MiCA maintains the high ratio of functional nodes. In particular, RPI-ERK and RPI-IGQ have almost 3/4 of the nodes non-functional in VGG-16 at 10 compression ratio, whereas MiCA-ERK and MiCA-IGQ keep all nodes functional. Interestingly, RbPI-SynFlow keeps the ratio of functional nodes relatively higher than other Pal methods without MiCA, even in the high compression range. In contrast, RbPI methods make nodes non-functional even in the low compression range. At the compression ratio of > 10 in VGG-16 and > 10 x in ResNet-20, RbPI has higher ratio of functional nodes than MiCA. Given that RbPI-SynFlow achieves comparable or higher accuracy than MiCA at 2 10 x compression ratio in VGG-16 (Figure 8 and that RbPI builds specific network at the skip connection-free architecture (Hoang et al. 2023), it suggests that sparse nel worksrks with a high ratio of functional nodes maintain accuracy at a high compression ratio. MiCA makes nodes non-functional in a high compression range, but the ratio is lower than in other methods. At 104.7 compression ratio in VGG-16, MiCA-ERK keeps nearly 50% of the nodes functional, whereas RPI-ERK keeps most of the nodes non-functional. In the ResNet-20 experiments, MiCA also has a higher ratio of functional nodes than other methods, but the difference is lower than in VGG-16. It shows that information from the first layer flows to the subsequent layers even after pruning due to skip connections. In other words, the top-to-bottom information flow is narrowed by pruning, but skip connections allow it to flow to the subsequent layers.
Why do some nodes become non-functional even after recalculating the compression ratio? This is because the convolution process produces con-functional nodes. The convolution process connects one input node in I-th convolutional layer with several output nodes in (1 + 1)-th convolutional layer, as shown in Figure 10 This connection does not use network parameters; hence, it is preserved after recalculating the compression ratio. Consequently, nodes can be non-functional if the number of remaining edges in (1+ 1)-th layer is small.
4.9 Experiments with Conoooollllli Networks on Node Classification
Through the preceding experiments, we have observed that MiCA is effective in convolutional structures. However, what about for other architectures? This section examines the effectiveness of MiCA using archi- tectures for other tasks that do not involve convolutional networks. Specifically, we experiment with node classification using GCN and GIN, both of which are MLP-basod architoctures. Note that while GCN seems to have the convolutional layers from the name, the network structure that processes the features is an MLP.
Figure 1 and 12 compare the accuracy between RPI, RbP1, and MiCA on OGBN-ArXiv with the same pre- defined and corrected sparsity distribution, respectively. Similar to the convolutional network experiments, MiCA maintains high accuracy, comparable to RPI, in the low compression range and enables training similar to RbPT in the high compression range. In other words, MiÇA demonstrates the effects of restricted RPI, which lies between RPI and RbPl, even in non-convolutional networks.
5 Limitations and Implications of This Work
This section discusses the limitations of this work and the implications of the proposed MiCA.
Limitations: Our work has several limitations: 1) As shown the ImageNet experiment with ResNet-50, the impact of applying MiCA in the context of large-scale datasets is minimal. We have also conducted experiments with other settings using ImageNet, but results beyond the ResNet-50 experiment have not yet been verified. Thus, there is potential for further enhancement in handling large-scale datasets. 2) While the average accuracy improves, some variation in accuracy must be tolerated due to the random selection of non-pruned edges. Further analysis and refinement are necessary to minimize the accuracy variance by tightening the restrictions in the pruning procedure. 3) Since our work focuses on high compression ranges, accuracy is incvitably lower than in low compression cases. Thus, we must explore whether MiCA has advantages in the trade-off between accuracy and computational complexity, particularly considering sparse matrix operations.
15

---

Published in Transactions on Machine Learning Research (5/2024)
Implications: Our proposed method MiCA has several implications: 1) Our work offers new insights into the underlying mechanisms governing the functionality of a network pruned by the Pal method under ultra- sparse conditions. The field of Pal is still insufficiently researched under such circumstances, and our work implics an invostigation into uncharted territory within the field. 2) The accuracy improvement achieved with MiCA in the high compression range highlights the significance of locusing on layer-wise connectivity for enhanced performance ultra-sparse networks. Our work demonstrates that accuracy enhancement can be attained solely through simple node connectivity without relying on data or other costly information (e.g., gradients). Although this paper has not demonstrated practical-level accuracy in the high compression range, this empirical finding by MiCA within the field of PaI holds significance, particularly considering the recent trend of vver-parameterizztion and the potential importance of sparse network architectures in the future.
6 Conclusion and Future Work
This paper introduces Minimum Connection Assurance, novel approach Pal methods. It addresses the critical issue of achieving higher compression ratios while preserving model accuracy, particularly in the high compression range. MiCA enhances the accuracy and compression ratio trade-off, surpassing the performance limitations encountered by RPI on skip connection-free architectures.
Our experiments not only validate the efficacy of MiCA in achieving high compression ratios but also shed light on the underlying factors that govern accuracy after training, which are present within the network created by Pal. Notably, MiCA demonstrates the ability of random connections to substitute for those learned by RbPI, especially in the high compression range. That is phenomenon previously observed only in the low compression range. In other words, this paper first revcals that learned connections are less than or equivalent to random connections at any compression ratio. Furthermore, our analysis suggests that it is necessary to make all nodes from which information flows functional to improve accuracy.
Our finding has potential for future applications in the arca of large-scale models such as foundation mod- els (Bommasani al., 2021) and large language models (Brown et al., 2020). As the size of state-of- saaee-ofthhhaarr models grows, the associated training and inference costs become increasingly prohibitive. In order to re- duce these costs, model compression needs to be sufficiently higher before training than the present. In this respect, our finding in the high compression range can be expected to be important in the future. More- over, it also has the potential contribution in areas such as fine-tuning large models to downstream tasks by pruning (Jiang et al. 2022).
A promising avenue for future work lies in exploring the appropriate selting method of pre-defined sparsity distributions depending on the minimum connection. While MiCA demonstrates superior performance conventional Pal methods, the accuracy is contingent upon the pre-defined sparsity distribution. Investi- gating novel sparsity distributions based on the minimum connection while maintaining critical connections could unveil further optimizations in model compression.
Acknowledgement
This work was supported in part by JSPS KAKENHI Grant Number JP23H05489.
References
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Proc. Int. Conf. Mach. Learn., pp. 322 332. PMLR, 2019.
Rishi Bommasani, Drew Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bossclut, Emma Brunskill, al. On the opportunities and risks of foundation models. Xiu preprint ar Xrx::22008.00 072588 2021.
16

---

Published in Transactions on Machine Learning Research (5/2024)
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Proc. Adv. Neural Inform. Process. Syst., 33:1877 191177--91,,, 2020.
Yves Chauvin. A pack-propagation algorithm with optimal use of hidden units. Proc. Adv. Neural Inform. Process. Syst., 1, 1988.
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. In Proc. Inl. 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. 2943-2952. PMLR, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In Proc. Iul. Conf. Learn. Repr., 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Stabilizing the lottery MexX::119..... 10t::993.000 190.001611, 2019.
ticket hypothesis. arXiv preprint Xiv:
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural networks at initialization: Why are we missing the mark? In Proc. Int. Conf. Learn. Repr., 2021.
Advait Harshal Gadhikar, Sohom Mukherjee, and Rebekka Burkholz. Why random pruning is all we need to start sparse. In Proc. Int. Conf. Mach. Learn., pp. 10542-10570. PMLR, 2023.
Babak Hassibi, David G Stork, and Gregory Wolff. Optimal brain surgeon and general network pruning. IEEE Int. Conf. Neural Networks, pp. 293 299. IEEE, 1993.
Soufiane Hayou, dean-Francoff Ton, Arnaud Doucet, and Yee Whye Teh. Pruning untrained neural networks: Principles and analysis. arXiv preprint orXiv:2002.0877 2020.
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.
Duc N.M Hoang, Shiwei Liu, Radu Marculescu, and Zhangyang Wang. Revisiting pruning at initialization through the lens of ramanujan graph. In Proc. Int. Conf. Learn. Repr., 2023.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs Proc. Adv. Newral Inform. Process. Syst., 18:22118-221133 2020.
Tianjin Huang, Tianlong Chen, Meng Fang, Vlado Menkovski, Jiaxu Zhao, Lu Yin, Yulong Pei, Docebal Con- stantin Mocanu, 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, on Grahhs Conf-, 2022.
Masumi Ishikawa. Structural learning with forgetting. Neural Networks, 9(3):509-522 1996.
Siddhant Jayakumar, Razvan Pascanu, Jack Rae, Simon Osindero, and Erich Elsen. Top-kast: Top-k always sparse training. Proc. Adv. Neural Inform. Process. Syst., 33:20744 20754, 2020.
Ting Jiang, Deqing Wang, Fuzhen Zhuang, Ruobing Xie, and Feng Xia. Pruming pre- gre-trained language models without fine-tuning. arXiv preprint arXim:2210.06: 062100 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6900 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proc. Inl. Conf. Learn. Repr., 2017.
17

---

Published in Transactions on Machine Learning Research (5/2024)
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, John Denker, and Sara Solla. Optinal brain damage. Proc. Adu. Neural Inform. Process. Syst. 2, 1989.
Jacho Lee, Sejun Park, Sangwoo Mo, Sungsoo Ahn, and Jinwoo Shin. Layer-adaptive sparsity for the magnitudo-based pruning. Proc. Int. Conf. Learn. Repr., 2021.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. SNIP: Single-shot network pruning based on connection sensitivity, In Proc. Int. Conf. Learn. Repr., 2019.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Li Shen, Decebal Constantin Mocanu, Zhangyang Wang, and Mykola Pechenizkiy. The unreasonable effectiveness of random pruning: Return of the most naive bascline for sparse training. In Proc. Inl. Conf. Learn. Repr., 2022.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and An- tonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature Comm., 9(1):2383, 2018.
Yurii Evgen'en evich Nesterov. A method of solving a convex programming problem with convergence rate (k1ssqr(k)). In Doklady Akademii Nauk, volume 269, pp. 343-547. Russian Academy of Sciences, 1983.
Behnam Neyshabur, Russ Salakhutdinov, and Nati Srebro. Path-SGD: Path-normalized optimization in deep neural networks. Proc. Adv. Neural Inform. Process. Syst., 28, 2015.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parametrization in generalization of neural networks. In Proc. Int. Conf. Learn. Repr., 2019.
Ilan Price and Jared Tanner. Dense for the price of sparse: Improved performance of sparsely initialized networks via a subspace offset. In Proc. Int. Conf. Mach. Learn., pp. 8620-8629. PMLR, 2021.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In Proc. Int. Conf. Learn. Repr., 2020.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. Inf. J. Comput. Vis., 115:211 252, 2015.
Mohammad Shocybi, Mostofa. Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-LM: Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv:1909.0800 08055, 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint orXim:1400. 1556, 2014.
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason Lee. Sanity- checking pruning methods: Random tickets can win the jackpot. Proc. Adu. Neural Inform. Process. Syst.. 33:20390 20401, 2020.
Hidenori Tanaka, Daniel Kunin, Daniel L 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.
Artem Vysogorets and Julia Kempe, Connectivity matters: Neural network pruning through the lens of effoctive sparsity. J. Mach. Learn. Res., 24:99-1, 2023.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In Proc. Inl. Conf. Learn. Repr., 2020.
18

---

Published in Transactions on Machine Learning Research (5/2024)
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint #XXim:909.01315 2019.
Andreas Weigend, David Rumelhart, and Bernardo Huberman. Generalization by weight-climination with application to forecasting. Proc. Adv. Neural Inform. Process. Syst., 3, 1990.
Kaiyue Wen, Jiaye Teng, and Jingzhao Zhang. Benign overfitting in classification: Provably counter label noise with larger models. In Proc. Inl. Conf. Learn. Repr., 2022.
Sanghyun Woo, Shoubhik Debnath, Ronghang Hu, Xinlei Chen, Zhuang Liu, In So Kweon, and Saining Xie. Convnext v2: Co-designing and scaling convnets with masked autoencoders. In Proc. IEEE Comput. Soc. Conf. Comput. Vis. and Pattern Recognit., pp. 16133-16142, 2023.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proc. Int. Conf. Learn. Repr., 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Comm. of the ACM, 64(3):107 115, 2021.
Guodong Zhang, James Martens, and Roger Grosse. Fast convergence natural gradient descent for over-parameterized neural networks. Proc. Adv. Neural Inform. Process. Syst., 32, 2019.
19


Reviews:
[{"review_id": "bydih4g9C6", "reviewer": "Reviewer_APXS", "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": "\\+ The minimum connection is constructed by pre-determining and connecting the neurons that the subnetwork uses, and the subnetwork with the connection maintains the pre-defined sparsity distribution even when connecting its neurons randomly. Thus, all allocated edges can be functional even in a high compression range.\n\n\\+ In VGG-16 with CIFAR-10, MiCA improves the accuracy of random pruning by 27.0% at 104.7× compression ratio.\n\n\\- The novelty may be limited. It is mainly based on some observations and examples in Figure 2 and 3 to derive the inequalities. it does not have a well defined problem formulation, or formal proof. The rules it uses in the inequalities are straightforward. The technical contribution may be limited.\n\n\\- It is better to provide a detailed algorithm to formally describe the proposed method. For example, it selects  $|V_{out}^{l-1}|$  randomly from the range. If it selects the random output nodes for each layer, I am not sure how to make the final model follow certain predefined sparsity requirement. Although it lists some key steps, I am still not sure like what is the constraint for the model at beginning, what are the detailed steps from the beginning to the final stage to obtain the sparse model. It is better to have a clear definition about what is the constraint, what are the steps, what they want  to achieve and so on. \n\n\\- Although it claims to have a better accuracy for extremely sparse models, the accuracy of these extremely sparse models are still very low, and probably people may not use these models. It is better to discuss the application of the proposed method and the generated models. \n\n\\- The experiments are conducted on CIFAR-10 and CIFAR-100 for VGG and resnet models. I have some concerns about this part. Most pruning works have results on ImageNet. And VGG and resnet are very basic models. There are new models and architectures with better performance. The results on CIFAR with VGG or resnet does not seem to be strong.\n \n\\- I have some concerns about the results. In some cases, the improvements seem to be marginal, such as figure 6 (a) and (b) for resnet. The results of the proposed method are very close to the baselines. It seems not very effective on resnet. \n\n\\- It is better to discuss the advantages of the pruning at initialization. Maybe the training can be faster. But the authors need to have some results or discussions to explain they want to explore this area and investigate this problem. Currently I do not find a clear motivation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 introduces a  pruning at initialization algorithm for high compression range: Minimum Connection Assurance (MiCA). Specifically, it preserves top-to-bottom information propagation among randomly pruned layers by building a random connection—minimum connection—using some of the pre-allocated edges.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "see the weakness.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4PFVDOmRWf", "reviewer": "Reviewer_yeKp", "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 main question that this paper aims to address, i.e., finding the additional conditions that help RPI work well, is interesting.\n- The background of the research has been described comprehensively, placing the paper in the context well.\n- The proposed method is quite simple, easy to implement, and does not require much computation.\n- The proposed method indeed seems to work as intended, in the sense that it preserves the number of functional nodes well.\n\n\n### **Weaknesses**\n- The empirical performance of the method is, in my opinion, somewhat marginal. Most of the performance only takes place after a significant degradation of performance has been taken place, undermining the practical usefulness of the idea.\n- The type of model architectures discussed in the paper is restricted; the paper uses VGG-16 and ResNet-20. As the proposed method is quite simple, I expect them to be applicable to other model architectures. But this has not been validated, which is a clear weakness.\n- Similarly, the type of tasks and datasets considered is restricted and relatively small-scale. The paper tests on two datasets: CIFAR-10 and CIFAR-100. In fact, two datasets are too similar to each other (again, in my humble opinion), and does not fully provide the advantage of having two different datasets. I recommend adding more datasets, tasks (other than image classification), or even data modality.\n- Also, the discussions and analyses could have been richer. For instance, I am quite curious whether the apparent gain comes from a better generalization, or a better training accuracy.", "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 contributes a new way to construct a random sparse network, which aims to prevent the scenarios where some neurons monopolize all edges, or some edges are wasted due to dead neurons. The idea is to have a pre-processing step that ensures some minimum level of connectivity. The method works by first selecting the minimum set of neurons in each layer to be connected. Then, one adds connections so that each input and output node has at least one edge connected. Then, one adds additional edge until the desired number of edges are met. Experiments show that the proposed method can improve the performance of sparse models at extremely low rate.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Given that the performance of the randomly pruned models are quite unstable (i.e., has a large variance), I strongly recommend the authors to perform experiments over multiple seeds and include the error bars. By doing so, one could even illustrate the advantages of this method better; MiCA should have better worst-case performance than RPI.\n- I also recommend adding some diversity to the experiments, in terms of model architectures, datasets, and even tasks.", "broader_impact_concerns": "I do not think there should be a broader impact section for this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2WwBECikZf", "reviewer": "Reviewer_vomQ", "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": "1. The motivation of this paper is well described.\n2. Authors provided extensive 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 paper introduces Minimum Connection Assurance (MiCA), a novel pruning at initialization (PaI) method for neural networks, aimed at maintaining high performance at high compression ratios without the need for costly connection learning. MiCA preserves random connections between layers while ensuring minimum necessary connections are maintained, enabling better accuracy and efficiency, particularly in architectures with and without skip connections across various compression ratios. Experimental results on CIFAR-10 and CIFAR-100 datasets demonstrate MiCA's superiority over conventional PaI methods, improving compression ratio and accuracy trade-offs significantly. The study suggests a future direction in exploring sparsity distributions tailored for MiCA to further enhance performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The proposed subnetwork construction method is only studied for convolution layers. I don't see why this method cannot be extended to transformers.\n2. This method \"sequentially analyze the number of connectable nodes \f from \f the output layer to the input layer.\" This analysis will not be scalable once we switch to large-scale models of billions of parameters or hundreds of layers.\n3. This work only test CIFAR-10 and CIFAR-100, which is limited.", "broader_impact_concerns": "1. Although being effective, the proposed subnetwork construction (two steps on page 5) is still ad hoc, which may not be principled enough to be adopted in different settings (models, datasets).\n2. The novelty and impact will be limited if the method can only work for convolutional layers.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all agreed on submission meeting  `Claims And Evidence`  and  `Audience` criteria while raising concerns with current set of results and presentation. 

In summary, motivation of the paper is well described and the question of finding conditions for random pruning at initialization to work well is an interesting question and would be of TMLR readers interest. While MiCA's effectiveness  are supported with convolutional networks on CIFAR-10/100 experiments,  reviewers also raised concerns about the generalizability of the paper's claim to architectures beyond convolutional networks and different dataset; moreover scalability which also related to usefulness / effectiveness of proposed method still remains as unanswered as well as concerns for reproducibility. 

Here's some comment from reviewers in the reviews & recommendations for improvement of the paper:

`vomQ`: "the proposed subnetwork construction (two steps on page 5) is still ad hoc, which may not be principled enough to be adopted in different settings (models, datasets)", "work only test CIFAR-10 and CIFAR-100, which is limited.", "analysis will not be scalable once we switch to large-scale models of billions of parameters or hundreds of layers."

`APXS`: "runs the experiments for three times, ... using large amounts of randomness in the framework does not seem to be robust and the results may also be affected by randomness.", "results on ImageNet in Fig 7 show that the performance of the proposed method is very close to the baseline with marginal improvements"

`yeKp`: "gain over other methods is very small", "lacks a formal verification that the 'proposed algorithm' is an effective way.", "the advantages only takes place in not-so-practical sparsity level"

AE recommends considering following changes for improvement:

1) Address robustness over randomness with more repetition
2) Empirical demonstration of MiCA's effectiveness on compression <> accuracy tradeoff beyond convolutional networks
3) Demonstration of the method on general tasks: beyond CIFAR-10/100 (two are very similar type of tasks); ideally beyond just image classification task
4) Demonstration of scalability: e.g. effectiveness in ImageNet on both architecture with and without skip-connection (Note as reviewers pointed out current ImageNet experiments doesn't seem to convincingly support claimed improvements)
5) Better justification of why improvement of MiCA at high compression ratio is important despite still being quite low performance

As we understand these make take some effort to incorporate, for the changes that’s not able to achieve by camera ready, AE suggest the authors to clearly state these as limitations of the paper (e.g. in a limitations section).
Decision: Accept (poster)